Performance of join operations in parallel database systems

• US 7,054,852 B1
• Filed: 05/23/2001
• Issued: 05/30/2006
• Est. Priority Date: 05/23/2001
• Status: Active Grant

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: NCR Corporation
• Inventors: Cohen, Steven B.
• Primary Examiner(s): Corrielus, Jean M.
• Assistant Examiner(s): EHICHIOYA, FRED I
• Application Number:
  US09/863,638
• Time in Patent Office: 1,833 Days
• Field of Search: 707 2- 10, 707/100, 707/101, 707/201, 707/202, 709/202
• US Class Current: 1/1
• CPC Class Codes: G06F 16/284 Relational databases
• 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/99937 Sorting
• CPC Class Codes: Y10S 707/99938 Concurrency, e.g. lock management in shared database

Abstract

A database system includes a plurality of storage modules, with a first storage module storing rows of a first table and a second storage module storing rows of a second table, and a plurality of access modules adapted to manage access of respective storage modules. A first access module corresponds to the first storage module, and a second access module corresponds to the second storage module. The first access module is adapted to distribute rows of the first table to the second access module in response to a join request, and the first access module is adapted to further distribute row identifiers with the distributed rows. The distributed rows contain one or more columns that are part of one or more join conditions of the join request, but does not contain one or more columns that are in a specified result list of the join request or that are part of a subsequent operation specified in the join request.

Claims

1. A method for use in a database system having plural storage modules, comprising:

storing rows of a first table in a first storage module;

storing rows of a second table in a second storage module;

receiving a request to perform a join of the first and second tables;

distributing, in response to the join request, rows and one or more columns of the rows of the first table from the first storage module to the second storage module; and

sending row identifiers of the distributed rows with the distributed rows.

2. The method of claim 1, further comprising identifying the one or more columns of the first table that are part of one or more conditions of the join request.

3. The method of claim 2, wherein identifying the one or more columns that are part of the one or more conditions comprises identifying the one or more columns that are part of a join condition of the join request.

4. The method of claim 3, wherein identifying the one or more columns that are part of the one or more conditions further comprises identifying the one or more columns that are part of a residual condition of the join request.

5. The method of claim 3, wherein distributing the one or more columns does not comprise distributing columns that are part of a specified result list in the join request.

6. The method of claim 5, wherein distributing the one or more columns does not comprise distributing columns that are part of a subsequent operation specified in the join request.

7. The method of claim 3, wherein distributing the one or more columns does not comprise distributing columns that are part of a subsequent operation specified in the join request.

8. The method of claim 1, further comprising storing, in the second storage module, the distributed rows and one or more columns.

9. The method of claim 8, wherein storing the distributed rows and one or more columns comprises storing in a spool table.

10. The method of claim 9, wherein the second storage module is associated with an access module, the method further comprising performing a join, by the access module, of the spool table and the second table.

11. The method of claim 10, wherein performing the join comprises identifying rows of the second table that satisfy one or more conditions of the join request and sending one or more columns of the identified rows from the second storage module to the first storage module.

12. The method of claim 11, wherein sending the one or more columns of the identified rows comprises sending one or more columns of the second table that are part of the specified result list of the join request and that are part of a subsequent operation specified in the join request.

13. The method of claim 12, wherein the first storage module is associated with one other access module, the method further comprising selecting, by the one other access module, rows of the first table corresponding to the identified rows of the second table and placing the selected rows of the first table and identified rows of the second table into a result table.

14. The method of claim 9, further comprising generating a temporary index based on the spool table, the temporary index to match a column of the second table to a row identifier in the spool table.

15. An article comprising at least one storage medium containing instructions executable in a database system having plural access modules to control access of plural storage modules, the instructions when executed causing the database system to:

store rows of a first table with a first access module;

store rows of a second table with a second access module;

receive a join request to join the first table and second table;

identify one or more columns of the first table that are part of one or more conditions of the join request; and

distribute the identified one or more columns of the first table from the first access module to the second access module but not distributing columns of the first table that are part of a specified result list of the join request.

16. The article of claim 15, wherein the instructions when executed cause the database system to further:

distribute rows containing the one or more identified columns of the first table; and

distribute row identifiers of the distributed rows with the distributed rows.

17. The article of claim 16, wherein the instructions when executed cause the database system to receive, by the first access module, rows of the second table that satisfy the one or more join conditions of the join request.

18. The article of claim 17, wherein the instructions when executed cause the database system to receive the rows of the second table by receiving rows containing one or more columns of the second table that are part of the specified result list in the join request.

19. The article of claim 18, wherein the instructions when executed cause the database system to receive the rows of the second table containing one or more further columns that are part of a subsequent operation specified in the join request.

20. The article of claim 18, wherein the instructions when executed cause the database system to further not distribute columns of the first table that are part of a subsequent operation specified in the join request.

21. The article of claim 17, wherein the instructions when executed cause the database system to further:

receive the row identifiers of the first table along with the rows of the second table;

retrieve rows from the first table using the row identifiers; and

storing rows of first and second tables in a result table.

22. A database system comprising:

a plurality of storage modules, with a first storage module storing rows of a first table and a second storage module storing rows of a second table;

a plurality of access modules adapted to manage access of respective storage modules, a first access module corresponding to the first storage module, and a second access module corresponding to the second storage module; and

the first access module adapted to distribute rows of the first table to the second access module in response to a join request, the first access module adapted to further distribute row identifiers of the distributed rows with the distributed rows.

23. The database system of claim 22, wherein the distributed rows contain one or more columns that are part of one or more join conditions of the join request but do not contain one or more columns that are in a specified result list of the join request.

24. The database system of claim 23, wherein the distributed rows do not contain one or more columns that are part of a subsequent operation specified in the join request.

25. The database system of claim 22, wherein each row of the first table is associated with a primary index, and wherein each row identifier comprises a hash code of the primary index and a uniqueness value.

26. The database system of claim 25, wherein the first table is hash partitioned and hash ordered.

27. The database system of claim 22, wherein the first table is hash partitioned and value ordered, and wherein each row of the first table is associated with a primary index, and wherein each row identifier comprises a hash code of the primary index and a field used for value ordering.

28. The database system of claim 22, wherein the first table is value partitioned and hash ordered, and wherein each row of the first table is associated with a primary index, and wherein each row identifier comprises a hash code of the primary index, a uniqueness field, and a field used for value partitioning.

29. The database system of claim 22, wherein the first table is value partitioned and value ordered, and wherein each row identifier comprises at least one field used for one of value partitioning and for value ordering.

30. A database system comprising:

a plurality of storage modules, with a first storage module storing rows of a first table and a second storage module storing rows of a second table;

a plurality of access modules adapted to manage access of respective storage modules, a first access module corresponding to the first storage module, and a second access module corresponding to the second storage module; and

the first access module adapted to distribute rows of the first table to the second access module in response to a join request, the first access module adapted to further distribute row identifiers with the distributed rows,

the first access module adapted to further distribute columns of the first table that are part of one or more join conditions of the join request but to not distribute columns of the first table that are part of a specified result list in the join request and subsequent operation of the join request.