Secondary index and indexed view maintenance for updates to complex types

• US 7,769,770 B2
• Filed: 07/14/2004
• Issued: 08/03/2010
• Est. Priority Date: 07/14/2004
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Stefani, Stefano, Denuit, Bruno H. M.
• Primary Examiner(s): Rones; Charles
• Assistant Examiner(s): Chojnacki; Mellissa M
• Application Number:
  US10/891,220
• Publication Number:
  US 20060015490A1
• Time in Patent Office: 2,211 Days
• Field of Search: 707/200, 707/759
• US Class Current: 707/759
• CPC Class Codes: G06F 16/24526 Internal representations for queries
• CPC Class Codes: G06F 16/24542 Plan optimisation

Abstract

Pursuant to receipt of a data modification command or statement, such as an Update command, it is determined which fields in a data structure, such as a UDT, computed column, indexed view, or index, for example, will be changed as a result of the command. Only those fields that are affected by the command will be changed. Thus, changes are propagated to only to those dependent data structures whose content is being modified. Tree representations are used to facilitate the determination as to whether a subfield in a hierarchy is changed.

Claims

1. A method of processing a data modification statement on a database in a computing device, comprising:

receiving a data modification statement to modify data within the database;

determining a tree representation for the received data modification statement;

receiving a data structure comprising an indexed view of the database, the indexed view expressing a result of a predefined query applied to the database, the indexed view to be employed when a query similar to the predefined query is applied to the database;

determining an operator tree as a relational tree that defines the received indexed view, the operator tree including a plurality of relational operators, each relational operator having child scalar expressions; and

for each relational operator in the determined operator tree;

obtaining the child scalar expressions of the relational operator;

comparing the obtained child scalar expressions to the determined tree representation for the received data modification statement to determine that a corresponding field of the indexed view of the database is affected by the data modification statement, and based thereon modifying a query plan corresponding to the data modification statement so as to update the indexed view of the database to be consistent with the modified data within the database,

wherein the data modification statement comprises an update command and the data structure comprises a user-defined type (UDT) derived by way of inheritance from another UDT, the derived UDT including each field of the another UDT and at least one additional field, the operator tree determined from the data structure referencing the another UDT and including an operator directing that the another UDT be treated as the derived UDT so as to access the at least one additional field, and

wherein comparing the obtained child scalar expressions to the determined tree representation comprises walking the determined tree representation, matching subfields used in the child scalar expressions with subfields updated in the determined tree representation, and generating for each match a query execution plan to propagate the corresponding updated subfield to the index.

2. The method of claim 1, comprising determining that a field is affected by the data modification statement by comparing the tree representation for the fields of the data structure and the tree representation for the data modification statement.

3. The method of claim 2, wherein comparing the tree representation for the fields of the data structure and the tree representation for the data modification statement comprises, for each relational operator in the tree representation for the fields of the data structure, determining scalar expressions and comparing the scalar expressions to the tree representation for the data modification statement.

4. The method of claim 1, comprising determining that a field is affected by the data modification statement by walking the tree representation for the data modification statement attempting to match fields of the data structure.

5. The method of claim 4, wherein walking the tree representation for the data modification statement proceeds in a top-down manner and matches the fields of the data structure from bottom to top.

6. The method of claim 1, comprising determining that a field is affected by the data modification statement by matching fields of the data structure with fields in the data modification statement.

7. A system comprising a processor for processing a data modification statement on a computing device, comprising:

a front end that receives a data modification statement to modify data within the database and determines a tree representation for the received data modification statement; and

the processor having a query optimizer implemented thereon, wherein the query optimizer that;

receives a data structure comprising an indexed view of the database, the indexed view expressing a result of a predefined query applied to the database, the indexed view to be employed when a query similar to the predefined query is applied to the database;

determines an operator tree as a relational tree that defines the received indexed view, the operator tree including a plurality of relational operators, each relational operator having child scalar expressions; and

for each relational operator in the determined operator tree;

obtains the child scalar expressions of the relational operator;

compares the obtained child scalar expressions to the determined tree representation for the received data modification statement to determine that a corresponding field of the indexed view of the database is affected by the data modification statement, and based thereon modifies a query plan corresponding to the data modification statement so as to update the indexed view of the database to be consistent with the modified data within the database,

wherein the data modification statement comprises an update command and the data structure comprises a user-defined type (UDT) derived by way of inheritance from another UDT, the derived UDT including each field of the another UDT and at least one additional field, the operator tree determined from the data structure referencing the another UDT and including an operator directing that the another UDT be treated as the derived UDT so as to access the at least one additional field, and

wherein comparing the obtained child scalar expressions to the determined tree representation comprises walking the determined tree representation, matching subfields used in the child scalar expressions with subfields updated in the determined tree representation, and generating for each match a query execution plan to propagate the corresponding updated subfield to the index.

8. The system of claim 7, wherein the front end comprises a parser and algebrizer that transforms the textual representation of the data modification statement into tree nodes.

9. The system of claim 7, wherein the query optimizer determines which fields of the data structure are affected by the data modification statement by comparing the tree representation for the fields of the data structure and the tree representation for the data modification statement.

10. The system of claim 9, wherein the query optimizer compares the tree representation for the fields of the data structure and the tree representation for the data modification statement by, for each relational operator in the tree representation for the fields of the data structure, determining scalar expressions and comparing the scalar expressions to the tree representation for the data modification statement.

11. The system of claim 7, wherein the query optimizer determines which fields of the data structure are affected by the data modification statement by walking the tree representation for the data modification statement attempting to match fields of the data structure.

12. The system of claim 11, wherein the query optimizer walks the tree representation for the data modification statement in a top-down manner and matches the fields of the data structure from bottom to top.

13. The system of claim 7, wherein the query optimizer determines which fields of the structure are affected by the data modification statement by matching fields of the data structure with fields in the data modification statement.