Index selection for an index access path

• US 5,924,088 A
• Filed: 02/28/1997
• Issued: 07/13/1999
• Est. Priority Date: 02/28/1997
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle Corporation
• Inventors: Ozbutun, Cetin, Jakobsson, Hakan, Cohen, Jeffrey I., Depledge, Michael
• Primary Examiner(s): Kulik, Paul V.
• Assistant Examiner(s): ROBINSON, GRETA LEE
• Application Number:
  US08/808,094
• Time in Patent Office: 865 Days
• Field of Search: 707/1, 707/2, 707/3, 707/7, 707/4
• US Class Current: 707/716
• CPC Class Codes: G06F 16/2246 Trees, e.g. B+trees
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

A list of indexes, from which indexes are selected for an index access path, is sorted by number of columns upon which each index is built. From the sorted list of indexes, a set of index access methods is generated in a heuristically ordered set of passes from a given WHERE clause. The index access methods that comprise the index access path are selected from the set of index access methods according to a cost/benefit analysis.

Claims

1. A method for generating an index access path for use in processing a query that includes a WHERE clause having a predicate that references a column of a table from a plurality of indexes built on the table, said method comprising the computer-implemented steps of:

generating a plurality of index access methods for the table from said plurality of indexes built on the table based on the WHERE clause;

computing costs for the index access methods; and

selecting said index access path based on the costs for the index access methods;

wherein each of the index access methods includes one or more index access keys, and each of the one or more index access keys includes a key value, based on a predicate of the WHERE clause, for comparison with values from a column of the table upon which one of the indexes was built.

2. The method of claim 1, wherein the step of generating a plurality of index access methods for the table from said plurality of indexes built on the table based on the WHERE clause includes the steps of:

performing a plurality of passes over the indexes in order of indexes with greatest number of columns to least number of columns; and

generating the plurality of index access methods during the passes based on WHERE clause.

3. The method of claim 2, wherein the step of generating the plurality of index access methods during the passes based on WHERE clause includes the steps of:

generating a fully matched index access method, wherein the fully matched index access method has a reference to an index built on a plurality of columns and an access key for each column of the plurality of columns;

generating a partially matched index access method, wherein the partially-matched index access method has a reference to an index built on a plurality of columns and an access key for each of a plurality of the plurality columns;

generating a single-column index access method, wherein the single column index access method has a reference to an index built on exactly one column and an access key for the column; and

generating a singly matched index access method, wherein the singly matched index access method has a reference to an index built on a plurality of columns and an access key for one column of the plurality of columns.

4. The method of claim 3, wherein the step of generating a fully matched index access method includes the steps of:

generating a plurality of index access methods, wherein each of said plurality of index access method has a reference to an index built on a plurality of columns; and

removing an index access method from the plurality of index access method, wherein the removed index access method does not have a key for each column of the plurality of columns.

5. The method of claim 3, wherein the step of generating a partially matched index access method includes the steps of:

generating a plurality of index access methods, wherein each of said plurality of index access method has a reference to an index built on a plurality of columns; and

removing an index access method from the plurality of index access method, wherein the removed index access method does not have a key for a plurality of columns of the plurality of columns.

6. The method of claim 3, wherein:

the step of generating a fully matched index access method is performed before the step of generating a partially matched index access method;

the step of generating a partially matched index access method is performed before the step of generating a single-column index access method; and

the step of generating of a single-column index access method is performed before the step of generating a singly-matched index access method.

7. The method of claim 2, further comprising the step of:

parsing said WHERE clause into a predicate tree.

8. The method of claim 7, wherein the step of parsing said WHERE clause into a predicate tree includes the step of parsing said WHERE clause into an AND/OR predicate tree.

9. The method of claim 1, wherein the step of generating the plurality of index access methods built on the table from said plurality of indexes based on WHERE clause includes the step of generating the plurality of index access methods, wherein no predicate of said WHERE clause is used for generating more than one access key of said plurality of indexes access methods.

10. The method of claim 1, wherein the step of computing costs for the index access methods includes the step of computing the cost for the index access method based on an estimated amount of data read from a non-volatile storage.

11. The method of claim 1, wherein the step of selecting said index access path based on the costs for the index access methods includes the steps of:

sorting said plurality of index access methods by cost;

calculating a marginal benefit for said index access method; and

if said marginal benefit for said index access method exceeds the cost for a lower cost index access method, then designating said index access method for said index access path.

12. The method of claim 11, wherein the step of calculating a marginal benefit for said index access method includes the steps of:

determining a selectivity factor for said index access methods; and

calculating the marginal benefit for said index access method based on the selectivity factor.

13. The method of claim 12, wherein the step of determining a selectivity factor for said index access method includes the steps of:

generating a histogram of key values based on an index referenced by said index access method; and

determining the selectivity for the index access method based on the histogram.

14. A computer readable medium having stored thereon sequences of instructions for generating an index access path for use in processing a query that includes a WHERE clause having a predicate that references a column of a table from a plurality of indexes built on the table based on a WHERE clause, said sequences of instructions including instructions for performing the steps of:

generating a plurality of index access methods for the table from said plurality of indexes built on the table based on the WHERE clause;

computing costs for the index access methods; and

selecting said index access path based on the costs for the index access methods;

wherein each of the index access methods includes one or more index access keys, and each of the one or more index access keys includes a key value, based on a predicate of the WHERE clause, for comparison with key values from one of the indexes.

15. The computer readable medium of claim 14, wherein the step of generating a plurality of index access methods for the table from said plurality of indexes built on the table based on the WHERE clause includes the steps of:

performing a plurality of passes over the indexes in order of indexes with greatest number of columns to least number of columns; and

generating the plurality of index access methods during the passes based on WHERE clause.

16. The computer readable medium of claim 15, wherein the step of generating the plurality of index access methods from the the passes based on the WHERE clause includes the steps of:

generating a fully matched index access method, wherein the fully matched index access method has a reference to an index built on a plurality of columns and an access key for each column of the plurality of columns;

generating a partially matched index access method, wherein the partially-matched index access method has a reference to an index built on a plurality of columns and an access key for a plurality of the plurality columns;

generating a single-column index access method, wherein the single column index access method has a reference to an index built on exactly one column and an access key for the column; and

generating a singly matched index access method, wherein the singly matched index access method has a reference to an index built on a plurality of columns and an access key for one column of the plurality of columns.

17. The computer readable medium of claim 16, wherein the step of generating a fully matched index access method includes the steps of:

generating a plurality of index access methods, wherein each of said plurality of index access method has a reference to an index built on a plurality of columns; and

removing an index access method from the plurality of index access method, wherein the removed index access method does not have a key for each column of the plurality of columns.

18. The computer readable medium of claim 16, wherein the step of generating a partially matched index access method includes the steps of:

generating a plurality of index access methods, wherein each of said plurality of index access method has a reference to an index built on a plurality of columns; and

removing an index access method from the plurality of index access method, wherein the removed index access method does not have a key for a plurality of columns of the plurality of columns.

19. The computer readable medium of claim 16, wherein:

the step of generating a fully matched index access method is performed before the step of generating a partially matched index access method;

the step of generating a partially matched index access method is performed before the step of generating a single-column index access method; and

the step of generating of a single-column index access method is performed before the step of generating a singly-matched index access method.

20. The computer readable medium of claim 15, further comprising the step of:

parsing said WHERE clause into a predicate tree.

21. The computer readable medium of claim 20, wherein the step of parsing said WHERE clause into a predicate tree includes the step of parsing said WHERE clause into an AND/OR predicate tree.

22. The computer readable medium of claim 14, wherein the step of generating the plurality of index access methods built on the table from said plurality of indexes based on WHERE clause includes the step of generating the plurality of index access methods, wherein no predicate of said WHERE clause is used for generating more than one access key of said plurality of indexes access methods.

23. The computer readable medium of claim 14, wherein the step of computing costs for the index access methods includes the step of computing the cost for the index access method based on an estimated amount of data read from a non-volatile storage.

24. The computer readable medium of claim 14, wherein the step of selecting said index access path based on the costs for the index access methods includes the steps of:

sorting said plurality of index access methods by cost;

calculating a marginal benefit for said index access method; and

if said marginal benefit for said index access method exceeds the cost for a lower cost index access method, then designating said index access method for said index access path.

25. The computer readable medium of claim 24, wherein the step of calculating a marginal benefit for said index access method includes the steps of:

determining a selectivity factor for said index access method and

calculating the marginal benefit for said index access method based on the selectivity factor.

26. The computer readable medium of claim 25, wherein the step of determining a selectivity factor for said index access method includes the steps of:

generating a histogram of key values based on an index referenced by said index access method; and

determining the selectivity for the index access method based on the histogram.