Method for detecting and optimizing queries with encoding/decoding tables

• US 5,930,785 A
• Filed: 10/16/1997
• Issued: 07/27/1999
• Est. Priority Date: 03/31/1995
• Status: Expired due to Term

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Lohman, Guy M., Urata, Monica S., Schiefer, Bernhard
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Coby, Frantz
• Application Number:
  US08/950,674
• Time in Patent Office: 649 Days
• Field of Search: 707/2, 707/3, 707/4
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24544 Join order optimisation
• 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 join optimizer and method for a relational database management system including a data processor, a stored database, and a plurality of database relations, wherein one or more of the relations are retrieved by the processor by means of query commands by performing a plurality of join operations on the relations, the system employing a general purpose heuristic algorithm which excludes or defers Cartesian products as late in the join sequence as possible, the method includes the steps of determining, in association with the execution of, or preferably prior to executing the general purpose algorithm, whether tables referenced in a query command includes a hub table and at least two encoding tables related to the hub table and, when the query command references a hub table and at least two encoding tables, determining the best access plan for the hub table, determining whether the best access plan utilizes an index used to access the hub table and, if so, constructing a plan to join the encoding tables as Cartesian products, constructing a plan to join the hub table and the encoding tables and storing the plans in the data structures of the optimizer for enumeration with other access plans constructed by the optimizer.

Claims

1. In a relational database management system including a data processor, a stored database, and a plurality of database relations stored in the form of tables, wherein one or more of said relations are retrieved by the processor responsive to a query statement which specifies desired relations, the query statement including first, second, and third tables, and further including a join predicate between relations of the first and second tables and a join predicate between relations of the first and third tables, but not including a join predicate between the relations of the first and third tables, the system producing first plans for performing a plurality of join operations on the desired relations, an optimizing module for use in optimizing query commands, the optimizing module comprising:

means for determining that the first table referenced in the query statement is a hub table, and for determining that the second and third tables are spoke tables associated with the hub table because of the respective join predicates therebetween;

means, operable responsive to identification of the hub table, for constructing a second plan for joining the hub table and the associated spoke tables;

means for generating a third plan for joining the second and third tables of the desired relations referenced in said query statement; and

means for enumerating the first, second, and third plans to determine the best plan for joining said tables referenced in said query statement.

2. A query optimizer as defined in claim 1, said determining means further including:

means for determining the identity of the table in said query statement having the largest number of distinct tables of the tables in said query statement joined to it by a join predicate and the magnitude of said largest number;

means for determining the best access plan for said table having the largest number of tables which are joined to it; and

means for determining whether said best access plan utilizes an index.

3. In a query optimizer as defined in claim 1, said determining means further including:

means for determining whether said query statement includes more than two tables and, if so,

means for counting the number of distinct tables of each of the tables referenced in said query statement which are joined by join predicates to the other tables in said query statement; and

means for storing the identity of the table having the largest number of tables which are joined to it and the magnitude of said largest number.

4. A query optimizer as defined in claim 3, said determining means further including:

means for determining the best access plan for said table having the largest number of tables which are joined to it when all local predicates and push-down predicates are applied; and

means for determining whether said table having the largest number of tables which are joined to it utilizes an index and, if so, designating said table having the largest number of tables which are joined to it as a hub table;

join predicate push-down means for applying join predicates between said tables as local predicates.

5. A query optimizer as defined in claim 1, said determining means further including:

means for determining whether said query statement includes more than two tables and, if so,

means for counting the number of distinct tables of each of the tables referenced in said query statement which are joined by join predicates to the other tables in said query statement; and

means for storing the identity of the table having the largest number of tables which are joined to it and the magnitude of said largest number;

means for determining the best access plan for said table having the largest number of tables which are joined to it when all local predicates and push-down predicates are applied; and

means for determining whether said table having the largest number of tables which are joined to it utilizes an index and, if so, designating said table having the largest number of tables which are joined to it as a hub table.

6. In a query optimizer as defined in claim 1, said responsive means further including:

means for designating said table having the largest number of tables which are joined to it as a hub table and designating tables joined to said hub table by join predicates in said query statement as spoke tables;

means for computing the cost of constructing a Cartesian product of said spoke tables for each index of said hub table; and

means for storing each said plan for joining and all intermediate plans.

7. For use by a relational database management system, the system including a data processor, a stored database, and a plurality of database relations, wherein one or more of said relations are retrieved by the processor by means of a query command, the query command including first, second, and third tables, and further including a join predicate between relations of the first and second tables and a join predicate between relations of the first and third tables, but not including a join predicate between the relations of the first and third tables, by performing a plurality of join operations on said relations, the system further including an optimizer for optimizing the query command, the optimizer employing a general purpose heuristic algorithm which excludes or defers Cartesian products as late in the join sequence as possible, a method comprising the steps of:

in association with the execution of said general purpose algorithm, determining that the first table referenced in the query command includes a hub table, and for determining that the second and third tables are related to said hub table as encoding tables because of the respective join predicates therebetween; and

responsive to the query command referencing a hub table and at least two encoding tables, performing the steps of;

(i) determining the best access plan for said hub table,

(ii) determining whether said best access plan utilizes an index used to access said hub table,

(iii) if so, constructing a plan to join said encoding tables as Cartesian products,

(iv) constructing a plan to join said hub table and said encoding tables, and

(v) storing said plans in the data structures of said optimizer for enumeration with other access plans constructed by said optimizer.

8. A method as defined in claim 7, said step of determining whether tables referenced in said query command include a hub table and at least two encoding tables related to said hub table further including the step of, for each table referenced in said query command, counting the number of tables which are joined to it by join predicates and storing the identity of the table having the largest number of tables joined to it and the magnitude of said largest number.

9. A method as defined in claim 8, further including the step of applying a predicate push-down algorithm with respect to said join predicates prior to determining said best access plan.

10. A method as defined in claim 9, further including the steps of:

for each index of said hub table, for each column of the index determining the join predicates which link said column to one of said encoding tables; and

applying said join predicates as local predicates, using said column of said index to access those rows of said table which satisfy join predicates in query statement.

13. A relational database management system as in claim 7, wherein the step of determining whether tables referenced in a query command includes a hub table and at least two encoding tables related to said hub table related to said hub table is carried out prior to executing said general purpose algorithm.

11. For use by a relational database management system including a data processor, a stored database, and a plurality of database relations, wherein one or more of said relations are retrieved by the processor by means of a query command, the query command including first, second, and third tables, and further including a join predicate between relations of the first and second tables and a join predicate between relations of the first and third tables, but not including a join predicate between the relations of the first and third tables, by performing a plurality of join operations on said relations, the system further including an optimizer for optimizing the query command, the optimizer employing a general purpose heuristic algorithm which excludes or defers Cartesian products as late in the join sequence as possible, a method comprising the steps of:

in association with the execution of said general purpose algorithm, determining that the first table referenced in the query command includes a hub table and for determining that the second and third tables are related to said hub table as encoding tables because of the respective join predicates therebetween, the step of determining including;

(i) the step, executed for each table referenced in said query command, of counting the number of tables which are joined to the referenced table by join predicates, and

(ii) the step of storing the identity of the table having the largest number of tables joined to it and the magnitude of said largest number;

responsive to the query command referencing a hub table and at least two encoding tables,

(i) determining the best access plan for said hub table,

(ii) determining whether said best access plan utilizes an index used to access said hub table and, if so;

(a) for each index of said hub table and for each column of the index, determining the join predicates which link said column to one of said encoding tables, and applying said join predicates as local predicates, using said column of said index, to access those rows of said table which satisfy the join predicates in the query statement;

(b) constructing a plan to join said encoding tables as Cartesian products;

(c) constructing a plan to join said hub table and said encoding tables; and

(d) storing said plans in the data structures of said optimizer for enumeration with other access plans constructed by said optimizer.

14. A relational database management system as in claim 11, wherein the step of determining whether tables referenced in a query command includes a hub table and at least two encoding tables related to said hub table related to said hub table is carried out prior to executing said general purpose algorithm.

12. For use by a relational database management system, the system including a data processor, a stored database, and a plurality of database relations, wherein one or more of said relations are retrieved by the processor by means of a query command, the query command including first, second, and third tables, and further including a join predicate between relations of the first and second tables and a join predicate between relations of the first and third tables, but not including a join predicate between the relations of the first and third tables, by performing a plurality of join operations on said relations, the system further including an optimizer for optimizing query commands and which employs a general purpose heuristic algorithm which excludes or defers Cartesian products as late in the join sequence as possible, the improvement comprising the steps of:

in association with the execution of said general purpose algorithm, determining whether the first table specified in the query command includes a hub table, and further determining whether the second and third tables specified in the query command include two tables related to the hub table as encoding tables because of the respective join predicates therebetween; and

when said tables include two or more encoding tables, executing the steps of;

(i) determining a best access plan for said table related to two or more encoding tables when said tables includes two or more encoding tables;

(ii) determining whether said best access plan employs an index used to access said table related to two or more encoding tables; and

(iii) if so, executing the steps of;

(a) constructing a plan to join said encoding tables as a first Cartesian product;

(b) constructing a plan to join said table related to two encoding tables; and

(c) storing each said plan in the data structures of said optimizer for enumeration with other plans constructed by said optimizer.

15. A relational database management system as in claim 12, wherein the step of determining whether tables referenced in a query command includes a hub table and at least two encoding tables related to said hub table related to said hub table is carried out prior to executing said general purpose algorithm 1.