Method, system, and program for determining the join ordering of tables in a join query

• US 6,397,204 B1
• Filed: 06/25/1999
• Issued: 05/28/2002
• Est. Priority Date: 06/25/1999
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Wang, Shyh-Yee, Liu, Lee-Chin Hsu, Tie, Hong Sang
• Primary Examiner(s): Mizrahi, Diane D.
• Application Number:
  US09/340,084
• Time in Patent Office: 1,068 Days
• Field of Search: 707/2,3,4
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24544 Join order optimisation
• CPC Class Codes: G06F 16/2456 Join operations
• 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

Disclosed is a system, method, and program for joining a multi-column table and at least two satellite tables. Each satellite table is comprised of multiple rows and at least one join column and each multi-column table is comprised of multiple rows and join columns corresponding to the join columns in the satellite tables. A query including predicates is received. A join predicate column comprises the satellite table and multi-column table join column to which at least one query predicate applies. A determination is then made as to whether there is at least one index on the multi-column table including at least one column for one join predicate column. One index is selected. The ordering of the join predicate columns in the selected index is used to determine the join order of the satellite tables and the multi-column table. The satellite tables and multi-column tables are then joined in the determined join order.

Claims

1. A method for joining a multi-column table and at least two satellite tables, wherein each satellite table is comprised of multiple rows and at least one join column and wherein the multi-column table is comprised of multiple rows and join columns corresponding to the join columns in the satellite tables, comprising:

receiving a query including predicates, wherein a join predicate column comprises the join column in the satellite table and multi-column table to which at least one query predicate applies;

determining whether there is at least one index on the multi-column table including at least one column for one join predicate column;

selecting one index;

using an ordering of the join predicate columns in the selected index to determine a join order of the satellite tables and the multi-column table; and

joining the satellite tables and multi-column tables in the determined join order.

2. The method of claim 1, wherein there are multiple indexes on the multi-column table each including at least one column corresponding to one join predicate column, and wherein selecting one index comprises:

determining the join order for each of the multiple indexes using the ordering of the join predicate columns;

estimating, for each index, a cost of performing the join operation using the determined join order for that index; and

selecting the index producing a join order having a lowest cost of the estimated costs for the determined join orders.

3. The method of claim 2, wherein determining the join order for one index comprises ordering the satellite tables having join predicate columns according to the ordering of the join predicate columns in that one index, wherein the multi-column table follows a last satellite table in the ordering defined by the join predicate columns in that one index.

4. The method of claim 2, further comprising:

determining whether an ordering within the join predicate column of one satellite table has the ordering of the corresponding join predicate column in the multi-column index; and

sorting each satellite join predicate column that is not in the order of the join predicate column in the multi-column index according to the ordering of the join predicate column in the multi-column index.

5. The method of claim 2, wherein determining the join order for one index comprises:

determining whether that one index has one column for each join predicate column in the satellite tables; and

defining the join order as the satellite tables ordered according to the ordering of the join predicate columns in that index followed by the multi-column table after determining that the one index has one column for each join predicate column in the satellite tables.

6. The method of claim 5, further comprising defining the join order as the satellite tables having corresponding join predicate columns in that one index followed by the multi-column table, and then followed by the satellite tables not having a join predicate column in that index after determining that the one index does not have one column for each join predicate column in the satellite tables.

7. The method of claim 6, wherein the satellite tables having one join predicate column in that index are ordered with respect to each other according to the order of the join predicate columns in that one index.

8. The method of claim 5, wherein joining the tables according to the join order is performed using nested loop joins.

9. The method of claim 6, further comprising:

determining whether there is an index for every satellite table that does not include one join predicate column;

wherein, after determining that there is an index for every satellite table not having one join predicate column, joining the tables comprises;

(i) using a nested loop join to join the satellite tables not having one join predicate column to form a first join result;

(ii) using a nested loop to join the satellite tables having one join predicate column according to the order of the join predicate columns in the selected index, followed by the multi-column table to form a second join result; and

(iii) sort merge joining the first and second join results.

10. The method of claim 1, wherein the selected index does not have any column corresponding to the join predicate column, wherein joining the satellite and multi-column tables comprises:

determining whether there is an index for each satellite table having a key column on the join predicate column in that satellite table; and

using the multi-column table as the outer table in a nested loop join with the dimension tables after determining that there is an index for each satellite table having a key column on one join predicate column in that satellite table.

11. The method of claim 10, further comprising performing, after determining that there is not an index for each satellite table having a key column on one join predicate column in that satellite table:

using nested loop joins to join the satellite tables; and

sort merge joining the joined satellite tables with multi-column fact table.

12. A system for determining a join ordering and performing a join operation involving a multi-column table and at least two satellite tables, comprising:

a computer;

a memory area accessible to the compute including one multi-column table and at least two satellite tables, wherein each satellite table is comprised of multiple rows and at least one join column and wherein the multi-column table is comprised of multiple rows and join columns corresponding to the join columns in the satellite tables; and

program logic executed by the computer, comprising;

(i) means for receiving a query including predicates, wherein a join predicate column comprises the join column in the satellite table and multi-column table to which at least one query predicate applies;

(ii) means for determining whether there is at least one index on the multi-column table including at least one column for one join predicate column;

selecting one index;

(iii) means for using an ordering of the join predicate columns in the selected index to determine a join order of the satellite tables and the multi-column table; and

(iv) means for joining the satellite tables and multi-column tables in the determined join order.

13. The system of claim 12, wherein there are multiple indexes on the multi-column table each including at least one column corresponding to one join predicate column, and wherein the program logic for selecting one index comprises:

means for determining the join order for each of the multiple indexes using the ordering of the join predicate columns;

means for estimating, for each index, a cost of performing the join operation using the determined join order for that index; and

means for selecting the index producing the join order having a lowest cost of the estimated costs for the determined join orders.

14. The system of claim 13, wherein the program logic for determining the join order for one index comprises ordering the satellite tables having join predicate columns according to the ordering of the join predicate columns in that one index, wherein the multi-column table follows a last satellite table in the ordering defined by the join predicate columns in that one index.

15. The system of claim 13, wherein the program logic further comprises:

means for determining whether an ordering within the join predicate column of one satellite table has the ordering of the corresponding join predicate column in the multi-column index; and

means for sorting each satellite join predicate column that is not in the order of the join predicate column in the multi-column index according to the ordering of the join predicate column in the multi-column index.

16. The system of claim 13, wherein the program logic for determining the join order for one index comprises:

means for determining whether that one index has one column for each join predicate column in the satellite tables; and

means for defining the join order as the satellite tables ordered according to the ordering of the join predicate columns in that index followed by the multi-column table after determining that the one index has one column for each join predicate column in the satellite tables.

17. The system of claim 16, wherein the program logic further comprises means for defining the join order as the satellite tables having corresponding join predicate columns in that one index followed by the multi-column table, and then followed by the satellite tables not having join predicate columns in that index after determining that the one index does not have one column for each join predicate column in the satellite tables.

18. The system of claim 17, wherein the satellite tables having one join predicate column in that index are ordered with respect to each other according to the order of the join predicate columns in that one index.

19. The system of claim 16, wherein joining the tables according to the join order is performed using nested loop joins.

20. The system of claim 16, wherein the program logic further comprises:

means for determining whether there is an index for every satellite table that does not include one join predicate column, wherein, after determining that there is an index for every satellite table not having one join predicate column, wherein the program logic for joining the tables comprises;

(i) means for using a nested loop join to join the satellite tables not having one join predicate column to form a first join result;

(ii) means for using a nested loop to join the satellite tables having one join predicate column according to the order of the join predicate columns in the selected index, followed by the multi-column table to form a second join result; and

(iii) means for sort merge joining the first and second join results.

21. The system of claim 13, wherein the selected index does not have any column corresponding to the join predicate column, wherein joining the satellite and fact tables comprises:

determining whether there is an index for each satellite table having a key column on the join predicate column in that satellite table; and

using the fact table as the outer table in a nested loop join with the dimension tables after determining that there is an index for each satellite table having a key column on one join predicate column in that satellite table.

22. The system of claim 21, wherein after determining that there is not an index for each satellite table having a key column on one join predicate column in that satellite table, the program logic includes means for using nested loop joins to join the satellite tables and sort merge joining the joined satellite tables with the multi-column table.

23. An article of manufacture for use in programming a computer to join a multi-column table and at least two satellite tables, wherein each satellite table is comprised of multiple rows and at least one join column and wherein each multi-column table is comprised of multiple rows and join columns corresponding to the join columns in the satellite tables, the article of manufacture comprising computer useable media including at least one computer program embedded therein that is capable of causing the computer to perform:

receiving a query including predicates, wherein a join predicate column comprises the satellite table and multi-column table join column to which at least one query predicate applies;

determining whether there is at least one index on the multi-column table including at least one column for one join predicate column;

selecting one index;

using an ordering of the join predicate columns in the selected index to determine a join order of the satellite tables and the multi-column table; and

joining the satellite tables and multi-column tables in the determined join order.

24. The article of manufacture of claim 23, wherein there are multiple indexes on the multi-column table each including at least one column corresponding to one join predicate column, and wherein selecting one index comprises:

determining the join order for each of the multiple indexes using the ordering of the join predicate columns;

estimating, for each index, a cost of performing the join operation using the determined join order for that index; and

selecting the index producing the join order having a lowest cost of the estimated costs for the determined join orders.

25. The article of manufacture of claim 24, wherein determining the join order for one index comprises ordering the satellite tables having join predicate columns according to the ordering of the join predicate columns in that one index, wherein the multi-column table follows a last satellite table in the ordering defined by the join predicate columns in that one index.

26. The article of manufacture of claim 24, further causing the computer to perform:

determining whether an ordering within the join predicate column of one satellite table has the ordering of the corresponding join predicate column in the multi-column index; and

sorting each satellite join predicate column that is not in the order of the join predicate column in the multi-column index according to the ordering of the join predicate column in the multi-column index.

27. The article of manufacture of claim 24, wherein determining the join order for one index comprises:

determining whether that one index has one column for each join predicate column in the satellite tables; and

defining the join order as the satellite tables ordered according to the ordering of the join predicate columns in that index followed by the multi-column table after determining that the one index has one column for each join predicate column in the satellite tables.

28. The article of manufacture of claim 27, further causing the computer to perform defining the join order as the satellite tables having corresponding join predicate columns in that one index followed by the multi-column table, and then followed by the satellite tables not having a join predicate column in that index after determining that the one index does not have one column for each join predicate column in the satellite tables.

29. The article of manufacture of claim 28, wherein the satellite tables having one join predicate column in that index are ordered with respect to each other according to the order of the join predicate columns in that one index.

30. The article of manufacture of claim 27, wherein joining the tables according to the join order is performed using nested loop joins.

31. The article of manufacture of claim 29, further causing the computer to perform:

determining whether there is an index for every satellite table that does not include one join predicate column;

wherein, after determining that there is an index for every satellite table not having one join predicate column, joining the tables comprises;

(i) using a nested loop join to join the satellite tables not having one join predicate column to form a first join result;

(ii) using a nested loop to join the satellite tables having one join predicate column according to the order of the join predicate columns in the selected index, followed by the multi-column table to form a second join result; and

(iii) sort merge joining the first and second join results.

32. The article of manufacture of claim 23, wherein the selected index does not have any column corresponding to the join predicate column, wherein joining the satellite and multi-column tables comprises:

determining whether there is an index for each satellite table having a key column on the join predicate column in that satellite table;

using the multi-column table as the outer table in a nested loop join with the dimension tables after determining that there is an index for each satellite table having a key column on one join predicate column in that satellite table.

33. The article of manufacture of claim 32, further comprising performing, after determining that there is not an index for each satellite table having a key column on one join predicate column in that satellite table:

using nested loop joins to join the satellite tables; and

sort merge joining the joined satellite tables with the fact table.