Method, system, and program for performing a join operation on a multi column table and satellite tables

• US 6,446,063 B1
• Filed: 06/25/1999
• Issued: 09/03/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: Lin, Fen-Ling, Wang, Yun, Kyu, William Y., Sampatrai, Desai Paramesh, Hoa, Peter, Chen, Stephen Yao Ching
• Primary Examiner(s): Mizrahi, Diane D.
• Application Number:
  US09/340,352
• Time in Patent Office: 1,166 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: 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 performing a join operation on a multi-column table and at least two satellite tables having a join condition. Each satellite table is comprised of multiple rows and at least one join column. Each multi-column table is comprised of multiple rows and at least one column corresponding to the join column in each satellite table. A join operation is performed on the rows of the satellite tables to generate a first join result comprising concatenations of the rows of the satellite tables. Less than all the concatenated rows in the first join result that satisfy the join condition are then selected. The selected concatenated rows in the first join result are then joined to the multi-column table.

Claims

1. A method for performing a join operation on a multi-column table and at least two satellite tables having a join condition, 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 at least one column corresponding to the join column in each satellite table, comprising:

performing a join operation on the rows of the satellite tables to generate a first join result comprising concatenated rows of the satellite tables;

selecting less than all the concatenated rows in the first join result that satisfy the join condition; and

joining the selected concatenated rows to the multi-column table.

2. The method of claim 1, wherein the join condition is used in performing the first join operation on the rows of the satellite tables to generate the first join results that satisfy the join condition.

3. The method of claim 1, further comprising sorting the multi-column table to provide ordering on the join columns of the multi-column table before joining the selected concatenated rows to the multi-column table.

4. The method of claim 1, further comprising sorting at least one of the satellite tables on the join columns before performing the join operations on the rows of the satellite tables.

5. The method of claim 1, wherein at least one of the satellite and multi-column tables comprise an index ordered on the join columns.

6. The method of claim 1, wherein the selecting and joining the concatenated rows comprises:

receiving a feedback entry from the multi-column table in response to the join operation of one of the selected concatenated rows to the multi-column table;

processing the feedback entry to select a next concatenated row of the first join results; and

joining the selected next concatenated row to the multi-column table.

7. The method of claim 6, wherein the feedback entry is a next ordered entry in the multi-column table following the concatenated row used in the join operation to the primary table according to an ordering of the join columns in the multi-column table.

8. The method of claim 7, wherein processing the feedback entry to select the next concatenated row of the satellite tables from the first join results comprises selecting a concatenated row from the first join results that follows the feedback entry according to the join ordering of the columns in the satellite tables.

9. The method of claim 7, wherein selecting the next concatenated row comprises comparing the join columns of the concatenated row from the first join results used in a previous join operation with the corresponding join columns in the feedback entry.

10. The method of claim 9, wherein comparing the join columns comprises comparing a leading join column to a last join column to select a join column value to increment to the next concatenated row from the first join results.

11. A system for performing a join operation on a multi-column table and at least two satellite tables having a join condition, comprising:

a computer;

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

program logic executed by the computer, comprising;

(i) means for performing a join operation on the rows of the satellite tables to generate a first join result comprising concatenated rows of the satellite tables;

(ii) means for selecting less than all the concatenated rows in the first join result that satisfy the join condition; and

(iii) means for joining the selected concatenated rows to the multi-column table.

12. The system of claim 11, wherein the program logic further comprises means for using the join condition in the first join operation on the rows of the satellite tables to generate the first join results that satisfy the join condition.

13. The system of claim 11, wherein the program logic further comprises means for sorting the multi-column table to provide ordering on the join columns of the multi-column table before joining the selected concatenated rows to the multi-column table.

14. The system of claim 11, wherein the program logic further comprises means for sorting at least one of the satellite tables on the join columns before performing the join operations on the rows of the satellite tables.

15. The system of claim 11, wherein at least one of the satellite and multi-column tables comprise an index ordered on the join columns.

16. The system of claim 11, wherein the program logic for selecting and joining the concatenated rows comprises:

means for receiving a feedback entry from the multi-column table in response to the join operation of one of the selected concatenated rows to the multi-column table;

means for processing the feedback entry to select a next concatenated row of the first join results; and

means for joining the selected next concatenated row to the multi-column table.

17. The system of claim 16, wherein the feedback entry is a next ordered entry in the multi-column table following the concatenated row used in the join operation to the primary table according to an ordering of the join columns in the multi-column table.

18. The system of claim 17, wherein the program logic for processing the feedback entry to select the next concatenated row of the satellite tables from the first join results comprises means for selecting a concatenated row from the first join results that follows the feedback entry according to the join ordering of the columns in the satellite tables.

19. The system of claim 17, wherein the program logic for selecting the next concatenated row comprises means for comparing the join columns of the concatenated row from the first join results used in a previous join operation with the corresponding join columns in the feedback entry.

20. The system of claim 19, wherein the program logic for comparing the join columns comprises means for comparing a leading join column to a last join column to select a join column value to increment to the next concatenated row from the first join results.

21. An article of manufacture for use in programming a computer to perform a join operation on a multi-column table and at least two satellite tables having a join condition, 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 at least one column corresponding to the join column in each satellite table, 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:

performing a join operation on the rows of the satellite tables to generate a first join result comprising concatenated rows of the satellite tables;

selecting less than all the concatenated rows in the first join result that satisfy the join condition; and

joining the selected concatenated rows to the multi-column table.

22. The article of manufacture of claim 21, wherein the join condition is used in performing the first join operation on the rows of the satellite tables to generate the first join results that satisfy the join condition.

23. The article of manufacture of claim 21, further causing the computer to sort the multi-column table to provide ordering on the join columns of the multi-column table before joining the selected concatenated rows to the multi-column table.

24. The article of manufacture of claim 21, further causing the computer to sort at least one of the satellite tables on the join columns before performing the join operations on the rows of the satellite tables.

25. The article of manufacture of claim 21, wherein at least one of the satellite and multi-column tables comprise an index ordered on the join columns.

26. The article of manufacture of claim 21, wherein selecting and joining the concatenated rows comprises:

receiving a feedback entry from the multi-column table in response to the join operation of one of the selected concatenated rows to the multi-column table;

processing the feedback entry to select a next concatenated row of the first join results; and

joining the selected next concatenated row to the multi-column table.

27. The article of manufacture of claim 26, wherein the feedback entry is a next ordered entry in the multi-column table following the concatenated row used in the join operation to the primary table according to an ordering of the join columns in the multi-column table.

28. The article of manufacture of claim 27, wherein processing the feedback entry to select the next concatenated row of the satellite tables from the first join results comprises selecting a concatenated row from the first join results that follows the feedback entry according to the join ordering of the columns in the satellite tables.

29. The article of manufacture of claim 27, wherein selecting the next concatenated row comprises comparing the join columns of the concatenated row from the first join results used in a previous join operation with the corresponding join columns in the feedback entry.

30. The article of manufacture of claim 29, wherein comparing the join columns comprises comparing a leading join column to a last join column to select a join column value to increment to the next concatenated row from the first join results.