Method and apparatus for parallel processing aggregates using intermediate aggregate values

• US 5,850,547 A
• Filed: 01/08/1997
• Issued: 12/15/1998
• Est. Priority Date: 01/08/1997
• Status: Expired due to Term

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle Corporation
• Inventors: Waddington, William H., Cohen, Jeffrey I.
• Primary Examiner(s): Lim, Krisna
• Application Number:
  US08/780,591
• Time in Patent Office: 706 Days
• Field of Search: 395/607, 395/382, 395/376, 395/676, 395/672
• US Class Current: 718/102
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination

Abstract

The present invention performs parallel processing of aggregate functions in a computing system. Partitioned into multiple subsets of data and each of the multiple subsets of data is allocated to one of a plurality of processes. Intermediate aggregations are performed in parallel by the plurality of processes on each of the multiple subsets of data. Each intermediate aggregation yields at least one intermediate value, wherein the at least one intermediate value is represented in an internal type format. The intermediate values from each of the intermediate aggregations are merged into a final aggregation value.

Claims

1. A computer-implemented method for parallel processing aggregate functions in a computing system, said aggregate functions being performed on a set of data, the computer-implemented method comprising the steps of:

partitioning said set of data stored in an external type format into multiple subsets of data;

assigning each of said multiple subsets of data to one of a plurality of processes;

said plurality of processes performing intermediate aggregations and conversions in parallel on each of said multiple subsets of data, each of said intermediate aggregations yielding at least one intermediate value, wherein said at least one intermediate value is represented in an internal type format; and

merging said at least one intermediate value from each of said imtermediate aggregations and converting into a final aggregation value stored in said external type format.

2. The computer-implemented method of claim 1 wherein said step of performing intermediate aggregations in parallel on each of said multiple subsets of data includes the step of sorting each of said multiple subsets of data.

3. The computer-implemented method of claim 1 wherein said aggregate functions are linear aggregate functions.

4. The computer-implemented method of claim 1 wherein said step of performing intermediate aggregations in parallel on each of said multiple subsets of data includes the step of converting each of said multiple subsets of data into an internal representation.

5. The computer-implemented method of claim 1 wherein said aggregate functions include one or more of MAX, MIN, AVG, SUM, STDDEV, VARIANCE and COUNT.

6. The computer-implemented method of claim 1 wherein said step of assigning each of said multiple subsets of data to one of said plurality of processes includes the step of assigning each of said multiple subsets of data to one of said plurality of processes according to a predetermined mapping function.

7. The computer-implemented method of claim 6 wherein said predetermined mapping function is a hash function.

8. A computer system for parallel processing aggregate functions, said aggregate functions being performed on a set of data stored in an external type format, said computer system comprising:

a processor;

a plurality of process spawned by the processor;

processing logic for,

partitioning said set of data into multiple subsets of data;

assigning each of said multiple subsets of data to one of said plurality of processes;

said plurality of processes performing intermediate aggregations and conversions in parallel on each of said multiple subsets of data, each of said intermediate aggregations yielding at least one intermediate value, wherein said at least one intermediate value is represented in an internal type format; and

merging said at least one intermediate value from each of said intermediate aggregations and converting into a final aggregation value stored in said external type format.

9. The computer system of claim 8 wherein said aggregate functions are linear aggregate functions.

10. The computer system of claim 8 wherein processing logic also converts each of said multiple subsets of data into an internal representation.

11. The computer system of claim 8 wherein said aggregate functions include one or more or MAX, MIN, AVG, SUM, STDDEV, VARIANCE and COUNT.

12. The computer system of claim 8 wherein said processor logic for assigning each of said multiple subsets of data to one of said plurality of processes includes processor logic for assigning each of said multiple subsets of data to one of said plurality of processes according to a predetermined mapping function.

13. The computer system of claim 12 wherein said predetermined mapping function is a hash function.

14. The computer system of claim 8 wherein said processing logic further sorts each of said multiple subsets of data.

15. A machine readable medium having stored thereon data representing, sequences of instructions, which when executed by a computer system, cause said computer system to perform the steps of:

partitioning a set of data stored in an external type format into multiple subsets of data;

assigning each of said multiple subsets of data to one of a plurality of precesses;

said plurality of precesses performing intermediate aggregations and conversions in parallel on each of said multiple subsets of data, each of said intermediate aggregations yielding at least one intermediate value, wherein said at least one intermediate value is represented in an internal type format; and

merging said at least one intermediate value from each of said intermediate aggregations and converting into a final aggregation value stored in said external type format.

16. The machine readable medium of claim 15 wherein said step of performing intermediate aggregations in parallel on each of said multiple subsets of data includes the steps of converting each of said multiple subsets of data into an internal representation.

17. The machine readable medium of claim 15 wherein said aggregate functions include one or more of MAX, MIN, AVG, SUM, STDDEV, VARIANCE and COUNT.

18. The machine readable medium of claim 15 wherein said predetermined mapping function is a hash function.

19. The machine readable medium of claim 15 wherein said step of performing intermediate aggregations in parallel on each of said multiple subsets of data includes the step of sorting each of said multiple subsets of data.

20. The machine readable medium of claim 15 wherein said aggregate functions are linear aggregate functions.