Maintained Symbol Table Only Index

• US 20090182720A1
• Filed: 01/15/2008
• Published: 07/16/2009
• Est. Priority Date: 01/15/2008
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Hu, Wei, Kethireddy, Shantan, Thiemann, Ulrich, Passe, Andrew Peter, Faunce, Michael S., Cain, Michael W.
• Granted Patent: US 7,792,823 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2272 Management thereof
• CPC Class Codes: G06F 16/24545 Selectivity estimation or determination

Abstract

A method, apparatus and program product is provided for optimizing a database query. A query syntax, system generated predicates, and requisite statistics of the database query are analyzed to determine if a predicate structure is a good candidate for a symbol table only data structure. The predicate structure is analyzed to determine if the predicate structure is already encompassed by an encoded vector index. The symbol table only data structure is generated for at least one column in a database table without generating a corresponding vector data structure from an encoded vector index if the predicate structure is a good candidate and not encompassed by an encoded vector index. The symbol table only data structure is maintained by detecting a change in data associated with the symbol table only data structure and updating the symbol table only data structure to reflect the change in the data.

Claims

1. A method of optimizing a database query, the method comprising:

analyzing a database query to determine if a predicate structure in the query is a good candidate for a symbol table only data structure;

analyzing the predicate structure to determine if the predicate structure is already encompassed by an encoded vector index; and

generating the symbol table only data structure for at least one column in a database table without generating a corresponding vector data structure from an encoded vector index if the predicate structure is a good candidate and not encompassed by an encoded vector index.

2. The method of claim 1 wherein analyzing a database query comprises:

analyzing a query syntax, system generated predicates, and requisite statistics of the database query.

3. The method of claim 1 further comprising:

amortizing a cost associated with the generation of the symbol table only data structure over multiple queries.

4. The method of claim 1 further comprising:

amortizing a cost associated with the generation of the symbol table only data structure based on symbol table only statistics.

5. The method of claim 4 wherein symbol table only statistics include at least one of cardinality, data skew, selectivity, and clusteredness.

6. The method of claim 1 wherein analyzing the predicate structure comprises:

analyzing a plurality of columns associated with the query to determine at least one of how the plurality of columns are grouped, distincted, and aggregated.

7. The method of claim 1 wherein determining if a predicate structure is a good candidate for a symbol table only data structure comprises:

analyzing a grouping, ordering, and distincting of the database query and system generated lookahead predicates.

8. The method of claim 1 wherein generating the symbol table only data structure is triggered when needed by a query optimizer.

9. The method of claim 1 wherein generating the symbol table only data structure is manually triggered by a user.

10. The method of claim 1 wherein generating the symbol table only data structure is triggered at startup of a computer system or at startup of a database engine.

11. A method of maintaining a symbol table only data structure, the method comprising:

detecting a change in data associated with the symbol table only data structure resulting in a change to a first row or a last row or the occurrence count of at least one key value in the symbol table only data structure; and

updating the symbol table only data structure to reflect the change to the first row or the last row or occurrence count of the key value.

12. The method of claim 11 wherein detecting a change comprises:

detecting data being eliminated from an underlying database table associated with the symbol table only data structure.

13. The method of claim 11 wherein detecting a change comprises:

detecting data being added to an underlying database table associated with the symbol table only data structure.

14. The method of claim 11 wherein detecting a change comprises:

detecting the creation of a new encoded vector index that is equivalent to or encompasses the symbol table only data structure; and

removing the symbol table only data structure.

15. The method of claim 11 wherein updating the symbol table only data structure comprises:

updating the symbol table only data structure in conjunction with the data changes to an underlying database table.

16. The method of claim 11 wherein updating the symbol table only data structure comprises:

deferring updates of the symbol table only data structure after changes to the data in an underlying table.

21. The apparatus of claim 16 wherein the program code is configured to generate the symbol table only data structure when manually triggered by a user.

17. An apparatus comprising:

a processor; and

program code configured to be executed by the processor to optimize a database query, the program code configured to analyze a database query to determine if a predicate structure in the query is a good candidate for a symbol table only data structure, analyze the predicate structure to determine if the predicate structure is already encompassed by an encoded vector index, and generate the symbol table only data structure for at least one column in a database table without generating a corresponding vector data structure from an encoded vector index if the predicate structure is a good candidate and not encompassed by an encoded vector index.

18. The apparatus of claim 17 wherein the program code is further configured to:

amortize a cost associated with the generation of the symbol table only data structure over multiple queries.

19. The apparatus of claim 17 wherein the program code is further configured to:

amortize a cost associated with the generation of the symbol table only data structure based on symbol table only statistics.

20. The apparatus of claim 17 wherein the program code is configured to generate the symbol table only data structure when needed by a query optimizer.

22. A program product, comprising:

a computer readable medium; and

a program code configured to maintain a symbol table only data structure, the program code resident on the computer readable medium and configured to detect a change in data associated with the symbol table only data structure resulting in a change to a first row or a last row or occurrence count of at least one key value in the symbol table only data structure, and update the symbol table only data structure to reflect the change to the first row or the last row or occurrence count of the key value.

23. The program product of claim 22 wherein program code is configured to detect a change by:

detecting data being eliminated from an underlying database table associated with the symbol table only data structure.

24. The program product of claim 22 wherein program code is configured to detect a change by:

detecting data being added to an underlying database table associated with the symbol table only data structure.

25. The program product of claim 22 wherein program code is configured to detect a change by:

detecting the creation of a new encoded vector index that is equivalent to or encompasses the symbol table only data structure; and

removing the symbol table only data structure.