Optimization of SQL queries using hash star join operations

• US 5,864,842 A
• Filed: 10/23/1995
• Issued: 01/26/1999
• Est. Priority Date: 10/23/1995
• Status: Expired due to Term

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: NCR Corporation
• Inventors: Pederson, Donald Raymond, Kostamaa, Olli Pekka
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Ho, Rauy Lian
• Application Number:
  US08/546,858
• Time in Patent Office: 1,191 Days
• Field of Search: 395/601, 395/602, 395/603, 395/604, 395/605, 395/606, 395/607, 395/608, 395/609, 395/610, 395/611, 395/616, 395/673
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 16/24537 of operators
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching

Abstract

A method, apparatus, and article of manufacture for optimizing SQL queries in a relational database management system uses hash star join operations. A hash star join operation is performed in place of the star join operation when the query includes the star join operation on a base table and the plurality of dimension tables. The base table is hash partitioned into a plurality of distinct and separate sub-portions thereof. Selecting and projecting rows from all of the dimension tables to separate temporary dimension tables. The query is split into a plurality of sub-queries, wherein each of the sub-queries comprises a hash star join operation on the temporary dimension tables and one or more of the distinct sub-portions of the base table. Each of the sub-queries are then performed independently of one another to create intermediate result tables. The intermediate result tables from each of the sub-queries are then merged together to create an output table.

Claims

1. A method of optimizing a query in a computer having a memory, the query being performed by the computer to retrieve data from a relational database stored in one or more electronic storage devices coupled to the computer, the method comprising the steps of:

(a) examining the query in the memory of the computer to determine whether the query includes a star join operation on a base table and a plurality of dimension tables; and

(b) performing, in the memory of the computer, a hash star join operation when the query includes the star join operation on the base table and the plurality of dimension tables, further comprising the steps of;

(1) hash partitioning the base table into a plurality of distinct and separate sub-portions thereof;

(2) selecting and projecting rows from all of the dimension tables to separate temporary tables;

(3) splitting the query into a plurality of sub-queries, wherein each of the sub-queries comprises a hash star join operation on the separate temporary tables and one or more of the distinct sub-portions of the base table;

(4) performing each of the sub-queries independently of one another to create intermediate result tables; and

(5) merging the intermediate result tables from each of the performed sub-queries to create an output table.

2. The method of claim 1 above, wherein the computer system comprises a plurality of processors, and the step of performing the sub-queries independently of one another further comprises the step of performing the sub-queries independently on different ones of the processors.

3. The method of claim 2 above, further comprising the step of storing each of the distinct sub-portions of the base table by a different one of the processors.

4. The method of claim 2 above, further comprising the step of duplicating the separate temporary tables across all of the processors.

13. The method of claim 1 above, further comprising the step of performing the hash star join operation in place of a sequence of binary join operations when the query includes a star join operation on a base table and a plurality of dimension tables.

14. The method of claim 1 above, wherein each of the sub-queries comprises a join operation on the rows of the temporary tables derived from the dimension tables and the hash partitioned base table.

15. The method of claim 1 above, wherein the join operation is a multi-table join step, which reads a row from each of the temporary tables, and hashes all the combinations of the dimension tables'"'"' connection clauses, so that a hash probe can be made to possibly find a matching row in the base table.

5. An apparatus for optimizing a query, comprising:

(a) a computer having a memory and one or more electronic storage devices coupled thereto, the data storage devices storing a relational database;

(b) means, performed by the computer, for accepting the SQL query into the memory of the computer, the query being performed by the computer to retrieve data from a relational database stored in the electronic storage devices;

(c) means, performed by the computer, for examining the query in the memory of the computer to determine whether the query includes a star join operation on a base table and a plurality of dimension tables; and

(d) means, performed by the computer, for performing a hash star join operation in the memory of the computer when the query includes the star join operation on the base table and the plurality of dimension tables, further comprising;

(1) means for hash partitioning the base table into a plurality of distinct and separate sub-portions thereof;

(2) means for selecting and projecting rows from all of the dimension tables to separate temporary tables;

(3) means for splitting the query into a plurality of sub-queries, wherein each of the sub-queries comprises a hash star join operation on the separate temporary tables and one or more of the distinct sub-portions of the base table;

(4) means for performing each of the sub-queries independently of one another to create intermediate result tables; and

(5) means for merging the intermediate result tables from each of the performed sub-queries to create an output table.

6. The apparatus of claim 5 above, wherein the computer system comprises a plurality of processors, and the means for performing the sub-queries independently of one another further comprises means for performing the sub-queries independently on different ones of the processors.

7. The apparatus of claim 6 above, further comprising means for storing each of the distinct sub-portions of the base table by a different one of the processors.

8. The apparatus of claim 6 above, further comprising the step of duplicating the separate temporary tables across all of the processors.

16. The apparatus of claim 5 above, further comprising the step of performing the hash star join operation in place of a sequence of binary join operations when the query includes a star join operation on a base table and a plurality of dimension tables.

17. The apparatus of claim 5 above, wherein each of the sub-queries comprises a join operation on the rows of the temporary tables derived from the dimension tables and the hash partitioned base table.

18. The apparatus of claim 5 above, wherein the join operation is a multi-table join step, which reads a row from each of the temporary tables, and hashes all the combinations of the dimension tables'"'"' connection clauses, so that a hash probe can be made to possibly find a matching row in the base table.

9. A program storage device, readable by a computer, tangibly embodying a program of instructions executable by the computer to perform method steps for executing a query in a computer having a memory, the query being performed by the computer to retrieve data from a relational database stored in one or more electronic storage devices coupled to the computer, the method comprising the steps of:

(a) examining the query in the memory of the computer to determine whether the query includes a star join operation on a base table and a plurality of dimension tables; and

(b) performing, in the memory of the computer, a hash star join operation when the query includes the star join operation on the base table and the plurality of dimension tables, further comprising the steps of;

(1) hash partitioning the base table into a plurality of distinct and separate sub-portions thereof;

(2) selecting and projecting rows from all of the dimension tables to separate temporary tables;

(3) splitting the query into a plurality of sub-queries, wherein each of the sub-queries comprises a hash star join operation on the separate temporary tables and one or more of the distinct sub-portions of the base table;

(4) performing each of the sub-queries independently of one another to create intermediate result tables; and

(5) merging the intermediate result tables from each of the performed sub-queries to create an output table.

10. The method of claim 9 above, wherein the computer system comprises a plurality of processors, and the step of performing the sub-queries independently of one another further comprises the step of performing the sub-queries independently on different ones of the processors.

11. The method of claim 10 above, further comprising the step of storing each of the distinct sub-portions of the base table by a different one of the processors.

12. The method of claim 10 above, further comprising the step of duplicating the separate temporary tables

19. The method of claim 10 above, further comprising the step of performing the hash star join operation in place of a sequence of binary join operations when the query includes a star join operation on a base table and a plurality of dimension tables.

20. The method of claim 10 above, wherein each of the sub-queries comprises a join operation on the rows of the temporary tables derived from the dimension tables and the hash partitioned base table.

21. The method of claim 10 above, wherein the join operation is a multi-table join step, which reads a row from each of the temporary tables, and hashes all the combinations of the dimension tables'"'"' connection clauses, so that a hash probe can be made to possibly find a matching row in the base table.