ITERATE-AGGREGATE QUERY PARALLELIZATION

• US 20080162409A1
• Filed: 12/27/2006
• Published: 07/03/2008
• 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
• Granted Patent: US 7,680,765 B2
• Time in Patent Office: Days
• US Class Current: 707/2
• 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:

an identification component that identifies an iterate-aggregate shape query; and

an execution component that processes the query recursively in parallel over multiple partitions.

2. The system of claim 1, the query is integrated within a programming language.

3. The system of claim 2, the query includes at least one of transformation, filtering, self-joins and/or user defined aggregates.

4. The system of claim 1, further comprising a partition component that segments data into multiple partitions.

5. The system of claim 4, further comprising an optimization component that identifies optimal partitioning based on information about the data and/or available resources.

6. The system of claim 4, further comprising an evaluation component that evaluates the query iteration and a portion of the aggregation in parallel over the partitions.

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

8. The system of claim 7, further comprising an aggregation component that completes query aggregation for each range of keys.

9. The system of claim 7, the repartition component repartitions reduced results based on a destination key.

10. The system of claim 9, further comprising a projection component that projects the reduced results into a structure.

11. A parallel processing method, comprising:

identifying an iterate-aggregate shape language integrated query; and

executing the query recursively in parallel.

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

13. The method of claim 12, further comprising mapping the partitioned data to key-value pairs in accordance with the query.

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

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

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

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

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

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

means for partitioning data identified by a language integrated iterate-aggregate query;

means for parallel evaluation of partitioned data in accordance the query;

means for repartitioning results of the parallel evaluation; and

means for evaluating the aggregation across the results.

20. The system of claim 19, further comprising a means for identifying optimal partitioning based on static information about the data and/or resource availability.