Iterate-aggregate query parallelization

• US 7,680,765 B2
• Filed: 12/27/2006
• Issued: 03/16/2010
• Est. Priority Date: 12/27/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Beckman, Brian C., Meijer, Henricus Johannes Maria, Lammel, Ralf
• Primary Examiner(s): Mofiz; Apu M
• Assistant Examiner(s): GIRMA, ANTENEH B
• Application Number:
  US11/616,712
• Publication Number:
  US 20080162409A1
• Time in Patent Office: 1,175 Days
• Field of Search: None
• US Class Current: 707/764
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 16/24554 Unary operations; Data partitioning operations
• CPC Class Codes: G06F 16/283 Multi-dimensional databases or data warehouses, e.g. MOLAP or ROLAP

Abstract

Iterate-aggregate shape queries are executable in an efficient parallel manner. Techniques are utilized that leverage properties of aggregations to implement such a query in a highly parallelized manner utilizing one or both of vertical and horizontal parallelism. More specifically, queries can be recursively evaluated in parallel utilizing partitioning and repartitioning mechanisms. Distributed query execution results over a subset of input data are repartitioned and aggregated to produce a final result.

Claims

1. A query execution system, comprising:

a processor configured to facilitate execution of queries, wherein the queries comprise an iterate-aggregate shape query;

an identification component configured to identify the iterate-aggregate shape query;

an execution component configured to process the iterate-aggregate shape query recursively in parallel over multiple partitions of data; and

an optimization component configured to;

identify optimal partitioning of data, based, at least, in part, on information about the data or available resources; and

employ a modified matrix multiplication technique to identify an optimal manner for parenthesizing associative operations associated with a specified number of partitions of data,

wherein the partitions of data have respective matrix sizes, and

wherein the optimal manner for parenthesizing associative operations minimizes a number of operations for executing matrix multiplication of the partitions of data.

2. The system of claim 1, wherein the iterate-aggregate shape query is integrated within a programming language.

3. The system of claim 2, wherein the iterate-aggregate shape query includes at least one of transformation, filtering, self-joins or user-defined aggregates.

4. The system of claim 1, further comprising a partition component configured to segment the data into the multiple partitions.

5. The system of claim 4, wherein the optimization component is also configured to infer optimal partitioning of the data based, at least, in part, on contextual information regarding at least one of the data or resources.

6. The system of claim 1, further comprising an evaluation component configured to evaluate the iterate-aggregate shape query iteration and a portion of the aggregation in parallel over the multiple partitions.

7. The system of claim 6, further comprising a repartition component configured to repartition results from the evaluation component by like keys.

8. The system of claim 7, further comprising an aggregation component configured to complete iterate-aggregate shape query aggregation for each range of keys.

9. The system of claim 7, wherein the repartition component is configured to repartition reduced results based, at least, in part, on a destination key.

10. The system of claim 9, further comprising a projection component configured to project the reduced results into a structure.

11. A parallel processing method, comprising:

executing computer-readable instructions stored on a computer-readable medium for performing the following acts;

identifying an iterate-aggregate shape language integrated query;

executing the iterate-aggregate shape language integrated query recursively in parallel;

identifying an optimal manner for grouping associative operations associated with a specified number of partitions of data,

wherein the partitions of data have respective matrix sizes, and

wherein the optimal manner for grouping associative operations minimizes a number of operations for executing matrix multiplication of partitions of data; and

segmenting the data to partition the data into the specified number of partitions based, at least, in part, on the identified optimal manner for grouping associative operations associated with the specified number of partitions of data.

12. The method of claim 11, further comprising partitioning input data.

13. The method of claim 12, further comprising mapping the partitioned input data to key-value pairs in accordance with the iterate-aggregate shape language integrated query.

14. The method of claim 13, further comprising grouping the key-value pairs in accordance with the iterate-aggregate shape language integrated query.

15. The method of claim 14, further comprising aggregating the data associated with each key of the key-value pairs to produce partial aggregate results.

16. The method of claim 15, further comprising repartitioning the partial aggregate results by each key of the key-value pairs.

17. The method of claim 16, further comprising concurrently aggregating the data and repartitioning the partial aggregate results.

18. The method of claim 17, further comprising aggregating the partial aggregate results.

19. An iterate-aggregate query execution system, comprising:

a processor configured to facilitate execution of queries, wherein the queries comprise a language integrated iterate-aggregate shape query;

a partition component configured to partition data identified by the language integrated iterate-aggregate shape query;

an evaluation component configured to perform parallel evaluation of the partitioned data in accordance with the language integrated iterate-aggregate shape query;

a repartition component configured to repartition results of the parallel evaluation;

an aggregation component configured to reduce the repartition results to a single response; and

an optimization component configured to;

identify optimal partitioning, based, at least, in part, on information about the data or available resources; and

employ a modified matrix multiplication technique to identify an optimal manner for grouping mathematical associative property operations associated with a specified number of partitions of data,

wherein the partitions of data have respective matrix sizes, and

wherein the optimal manner for grouping mathematical associative property operations minimizes a number of operations for executing matrix multiplication of the partitions of data.

20. The system of claim 19, wherein the information is static information.