US6397204B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method, system, and program for determining the join ordering of tables in a join query
Assignee: International Business Machines Corp
•
Filing: 1999-06-25
•
Granted: 2002-05-28
•
Expires: 2019-06-25
Abstract
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.
Inventors
- 👤 Lee-Chin Hsu Liu
- 👤 Hong Sang Tie
- 👤 Shyh-Yee Wang
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 11:47
CPC Classifications
G; G06; G06F; G06F16/00; G06F16/20; G06F16/24; G06F16/245; G06F16/2453; G06F16/24534; G06F16/24542; G06F16/24544; G06F16/2455; G06F16/24553; G06F16/24558; G06F16/2456; Y; Y10; Y10S; Y10S707/00; Y10S707/99931; Y10S707/99932; Y10S707/99933; Y10S707/99934
Claims Analysis
Total Claims: 36
Claim 1
Independent Claim
143 words
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.
Claim 2
Independent Claim
143 words
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.
Claim 3
Dependent Claim
91 words
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.
Claim 4
Dependent Claim
58 words
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.
Claim 5
Dependent Claim
69 words
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.
Claim 6
Dependent Claim
77 words
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.
Claim 7
Dependent Claim
66 words
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.
Claim 8
Dependent Claim
38 words
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.
Claim 9
Dependent Claim
21 words
The method of claim 5 , wherein joining the tables according to the join order is performed using nested loop joins.
Claim 10
Dependent Claim
121 words
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.
Claim 11
Dependent Claim
94 words
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.
Claim 12
Dependent Claim
55 words
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.
Claim 13
Independent Claim
191 words
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.
Claim 14
Independent Claim
191 words
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.
Claim 15
Dependent Claim
101 words
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.
Claim 16
Dependent Claim
62 words
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.
Claim 17
Dependent Claim
77 words
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.
Claim 18
Dependent Claim
85 words
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.
Claim 19
Dependent Claim
71 words
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.
Claim 20
Dependent Claim
38 words
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.
Claim 21
Dependent Claim
21 words
The system of claim 16 , wherein joining the tables according to the join order is performed using nested loop joins.
Claim 22
Dependent Claim
138 words
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.
Claim 23
Dependent Claim
94 words
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.
Claim 24
Dependent Claim
59 words
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.
Claim 25
Dependent Claim
173 words
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.
Claim 26
Dependent Claim
173 words
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.
Claim 27
Dependent Claim
93 words
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.
Claim 28
Dependent Claim
60 words
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.
Claim 29
Dependent Claim
75 words
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.
Claim 30
Dependent Claim
79 words
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.
Claim 31
Dependent Claim
72 words
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.
Claim 32
Dependent Claim
40 words
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.
Claim 33
Dependent Claim
23 words
The article of manufacture of claim 27 , wherein joining the tables according to the join order is performed using nested loop joins.
Claim 34
Dependent Claim
127 words
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.
Claim 35
Dependent Claim
95 words
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.
Claim 36
Dependent Claim
57 words
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.
References Cited (Backward Citations)
US5043872A
Cited
US5345585A
Cited
US5367675A
Cited
US5301317A
Cited
US5630120A
Cited
US5423035A
Cited
US5469568A
Cited
US6289334B1
Cited
US5758146A
Cited
US5724568A
Cited
US5680603A
Cited
US5701455A
Cited
US5765159A
Cited
US5799309A
Cited
US5671403A
Cited
US5615361A
Cited
US5548754A
Cited
US5548758A
Cited
US5706494A
Cited
US5546576A
Cited
US5548755A
Cited
US5930785A
Cited
US5734893A
Cited
US5873083A
Cited
US5761657A
Cited
US5706495A
Cited
US5758335A
Cited
US6029163A
Cited
US5848408A
Cited
US6272487B1
Cited
EP0875838A2
Cited
US5905985A
Cited
US5873075A
Cited
US5822750A
Cited
US6105018A
Cited
US6285997B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2005-05-27 | 2005-11-26 | 2006-05-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2009-05-27 | 2009-11-26 | 2010-05-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2013-05-27 | 2013-11-26 | 2014-05-28 | $7700.00 | Window Closed / Lapsed |