Optimization of SQL queries involving aggregate expressions using a plurality of local and global aggregation operations

• US 5,884,299 A
• Filed: 02/06/1997
• Issued: 03/16/1999
• Est. Priority Date: 02/06/1997
• Status: Expired due to Term

• Current Assignee: Teradata US, Inc. (Teradata Corporation)
• Original Assignee: NCR Corporation
• Inventors: Kraus, Timothy Brent, Walter, Todd Allan, Ramesh, Bhashyam
• Primary Examiner(s): Black, Thomas G.
• Assistant Examiner(s): Alam, Hosain T.
• Application Number:
  US08/795,114
• Time in Patent Office: 768 Days
• Field of Search: 707/10, 707/1-3, 395/200.3, 395/200.31, 395/200.32, 395/200.35
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination
• 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 involving aggregate and grouping functions. A local aggregation operation is performed on one or more processors of a massively parallel processor (MPP) computer system, wherein rows of the table that are local to each processor are locally aggregated to create one or more aggregate result rows. The aggregate result rows created by each of the local aggregation operations are then re-distributed to one or more processors and coalesced into a global aggregate result row by a global aggregation operation.

Claims

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

(a) examining the query in the computer system to determine whether the query includes one or more aggregation operations on rows of a table in the relational database;

(b) performing a plurality of local aggregation operations in the computer system, wherein rows of the table are locally aggregated by each of the local aggregation operations to create a plurality of local aggregate result rows; and

(c) performing a plurality of global aggregation operations in the computer system, wherein the local aggregate result rows created by the local aggregation operations are re-distributed to the plurality of global aggregation operations to be coalesced thereby to create a plurality of global aggregate result rows.

2. The method of claim 1 above, wherein the computer system comprises a plurality of processors.

3. The method of claim 2 above, wherein the performing step (b) comprises the step of performing the local aggregation operations in two or more of the processors, wherein rows of the table are locally aggregated by the processors in the local aggregation operations.

4. The method of claim 3 above, wherein each of the local aggregation operations comprises the steps of:

scanning rows from the table and qualifying the scanned rows;

building one or more local aggregate result rows containing results from the local aggregation operation for the scanned rows;

caching the local aggregate result rows in a memory of the computer system; and

re-distributing the local aggregate result rows from the cache to the plurality of global aggregation operations in the computer system.

5. The method of claim 2 above, wherein the performing step (c) comprises the step of performing the global aggregation operations in two or more of the processors, wherein the local aggregate result rows created by the local aggregation operations are globally aggregated by the processors in the global aggregation operations to create the global aggregate result rows.

6. The method of claim 5 above, wherein each of the global aggregation operations comprises the steps of:

receiving the local aggregate result rows from the plurality of local aggregation operations in the computer system; and

building the plurality of global aggregate result rows containing results from the received local aggregate result rows.

7. The method of claim 2 above, further comprising the step of storing distinct sub-portions of the table on a different ones of the processors.

8. The method of claim 1 above, wherein the aggregation operations comprise one or more functions selected from a group comprising MAX, MIN, AVG, COUNT, and SUM functions.

9. The method of claim 1 above, wherein the aggregation operation comprises a grouping function.

10. The method of claim 1 above, wherein the performing step (b) further comprises the steps of:

(1) storing the local aggregate result rows in a cache;

(2) purging a purgeable portion of the cache to a spool file when there is an overflow of the cache; and

(3) upon completion of the local aggregation operation, performing a sort-coalesce function on the spool file to create the local aggregate result rows.

11. The method of claim 10 above, wherein the performing step (3) further comprises the steps of:

reading purged local aggregate result rows from the spool file;

sorting the read rows by result groups; and

coalescing the sorted rows that have identical result groups.

12. The method of claim 10 above, wherein the performing step (b) further comprises the step of re-distributing the local aggregate result rows from the spool file and the cache to the plurality of global aggregation operations.

13. The method of claim 1 above, wherein the performing step (c) further comprises the steps of:

(1) storing the global aggregate result rows in a cache;

(2) purging a purgeable portion of the cache to a spool file when there is an overflow of the cache; and

(3) upon completion of the global aggregation operation, performing a sort-coalesce function on the spool file to create the global aggregate result rows.

14. The method of claim 13 above, wherein the performing step (3) further comprises the steps of:

reading purged global aggregate result rows from the spool file;

sorting the read rows by result groups; and

coalescing the sorted rows that have identical result groups.

15. An apparatus for optimizing a query, comprising:

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

(b) means, performed by the computer system, for examining the query in the computer system to determine whether the query includes one or more aggregation operations on rows of a table in the relational database;

(c) means, performed by the computer system, for performing a plurality of local aggregation operations in the computer system, wherein rows of the table are locally aggregated by each of the local aggregation operations to create a plurality of local aggregate result rows; and

(d) means, performed by the computer system, for performing a plurality of global aggregation operations in the computer system, wherein the local aggregate result rows created by the local aggregation operations are re-distributed to the plurality of global aggregation operations to be coalesced thereby to create a plurality of global aggregate result rows.

16. The apparatus of claim 15 above, wherein the computer system comprises a plurality of processors.

17. The apparatus of claim 16 above, wherein the means for performing (c) comprises means for performing the local aggregation operations in two or more of the processors, wherein rows of the table are locally aggregated by the processors in the local aggregation operations.

18. The apparatus of claim 17 above, wherein each of the local aggregation operations comprises:

means for scanning rows from the table and qualifying the scanned rows;

means for building one or more local aggregate result rows containing results from the local aggregation operation for the scanned rows;

means for caching the local aggregate result rows in a memory of the computer system; and

means for re-distributing the local aggregate result rows from the cache to the plurality of global aggregation operations in the computer system.

19. The apparatus of claim 16 above, wherein the means for performing (d) comprises means for performing the global aggregation operations in two or more of the processors, wherein the local aggregate result rows created by the local aggregation operations are globally aggregated by the processors in the global aggregation operations to create the global aggregate result rows.

20. The apparatus of claim 19 above, wherein each of the global aggregation operations comprises:

means for receiving the local aggregate result rows from the plurality of local aggregation operations in the computer system; and

means for building the plurality of global aggregate result rows containing results from the received local aggregate result rows.

21. The apparatus of claim 16 above, further comprising means for storing distinct sub-portions of the table on different ones of the processors.

22. The apparatus of claim 15 above, wherein the aggregation operations comprise one or more functions selected from a group comprising MAX, MIN, AVG, COUNT, and SUM functions.

23. The apparatus of claim 15 above, wherein the aggregation operation comprises a grouping function.

24. The apparatus of claim 15 above, wherein the means for performing (c) further comprises:

(1) means for storing the local aggregate result rows in a cache;

(2) means for purging a purgeable portion of the cache to a spool file when there is an overflow of the cache; and

(3) means for performing a sort-coalesce function on the spool file to create the local aggregate result rows, upon completion of the local aggregation operation.

25. The apparatus of claim 24 above, wherein the means for performing 3) further comprises:

means for reading purged local aggregate result rows from the spool file;

means for sorting the read rows by result groups; and

means for coalescing the sorted rows that have identical result groups.

26. The apparatus of claim 24 above, wherein the means for performing (c) further comprises means for re-distributing the local aggregate result rows from the spool file and the cache to the plurality of global aggregation operations.

27. The apparatus of claim 15 above, wherein the means for performing (d) further comprises:

(1) means for storing the global aggregate result rows in a cache;

(2) means for purging a purgeable portion of the cache to a spool file when there is an overflow of the cache; and

(3) means for performing a sort-coalesce function on the spool file to create the global aggregate result rows, upon completion of the global aggregation operation.

28. The apparatus of claim 27 above, wherein the means for performing (3) further comprises:

means for reading purged global aggregate result rows from the spool file;

means for sorting the read rows by result groups; and

means for coalescing the sorted rows that have identical result groups.

29. A program storage device, readable by a computer system, tangibly embodying one or more programs of instructions executable by the computer systems to perform method steps for executing a query, 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 system, the method comprising the steps of:

(a) examining the query in the computer system to determine whether the query includes one or more aggregation operations on rows of a table in the relational database;

(b) performing a plurality of local aggregation operations in the computer system, wherein rows of the table are locally aggregated by each of the local aggregation operations to create a plurality of local aggregate result rows; and

(c) performing a plurality of global aggregation operations in the computer system, wherein the local aggregate result rows created by the local aggregation operations are re-distributed to the plurality of global aggregation operations to be coalesced thereby to create a plurality of global aggregate result rows.

30. The method of claim 29 above, wherein the computer system comprises a plurality of processors.

31. The method of claim 30 above, wherein the performing step (b) comprises the step of performing the local aggregation operations in two or more of the processors, wherein rows of the table are locally aggregated by the processors in the local aggregation operations.

32. The method of claim 31 above, wherein each of the local aggregation operations comprises the steps of:

scanning rows from the table and qualifying the scanned rows;

building one or more local aggregate result rows containing results from the local aggregation operation for the scanned rows;

caching the local aggregate result rows in a memory of the computer system; and

re-distributing the local aggregate result rows from the cache to the plurality of global aggregation operations in the computer system.

33. The method of claim 30 above, wherein the performing step (c) comprises the step of performing the global aggregation operations in two or more of the processors, wherein the local aggregate result rows created by the local aggregation operations are globally aggregated by the processors in the global aggregation operations to create the global aggregate result rows.

34. The method of claim 33 above, wherein each of the global aggregation operations comprises the steps of:

receiving the local aggregate result rows from the plurality of local aggregation operations in the computer system; and

building the plurality of global aggregate result rows containing results from the received local aggregate result rows.

35. The method of claim 30 above, further comprising the step of storing distinct sub-portions of the table on different ones of the processors.

36. The method of claim 29 above, wherein the aggregation operations comprise one or more functions selected from a group comprising MAX, MIN, AVG, COUNT, and SUM functions.

37. The method of claim 29 above, wherein the aggregation operation comprises a grouping function.

38. The method of claim 29 above, wherein the performing step (b) further comprises the steps of:

(1) storing the local aggregate result rows in a cache;

(2) purging a purgeable portion of the cache to a spool file when there is an overflow of the cache; and

(3) upon completion of the local aggregation operation, performing a sort-coalesce function on the spool file to create the local aggregate result rows.

39. The method of claim 38 above, wherein the performing step (3) further comprises the steps of:

reading purged local aggregate result rows from the spool file;

sorting the read rows by result groups; and

coalescing the sorted rows that have identical result groups.

40. The method of claim 38 above, wherein the performing step (b) further comprises the step of re-distributing the local aggregate result rows from the spool file and the cache to the plurality of global aggregation operations.

41. The method of claim 29 above, wherein the performing step (c) further comprises the steps of:

(1) storing the global aggregate result rows in a cache;

(2) purging a purgeable portion of the cache to a spool file when there is an overflow of the cache; and

(3) upon completion of the global aggregation operation, performing a sort-coalesce function on the spool file to create the global aggregate result rows.

42. The method of claim 41 above, wherein the performing step (3) further comprises the steps of:

reading purged global aggregate result rows from the spool file;

sorting the read rows by result groups; and

coalescing the sorted rows that have identical result groups.