Custom operators for a parallel query engine

• US 8,521,721 B2
• Filed: 09/14/2010
• Issued: 08/27/2013
• Est. Priority Date: 09/14/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Toub, Stephen Harris, Ostrovsky, Igor, Liddell, Mike
• Primary Examiner(s): Jami, Hares
• Application Number:
  US12/882,168
• Publication Number:
  US 20120066250A1
• Time in Patent Office: 1,078 Days
• Field of Search: 707/705, 707/713, 707/758, 707/759, 707/764, 707/765, 707/769, 707/99.1, 707/999.3, 707/999.39
• US Class Current: 707/713
• CPC Class Codes: G06F 16/24532 of parallel queries

Abstract

Embodiments are directed to implementing custom operators in a query for a parallel query engine and to generating a partitioned representation of a sequence of query operators in a parallel query engine. A computer system receives a portion of partitioned input data at a parallel query engine, where the parallel query engine is configured to process data queries in parallel, and where the queries include a sequence of built-in operators. The computer system incorporates a custom operator into the sequence of built-in operators for a query and accesses the sequence of operators to determine how the partitioned input data is to be processed. The custom operator is accessed in the same manner as the built-in operators. The computer system also processes the sequence of operators including both the built-in operators and at least one custom operator according to the determination indicating how the data is to be processed.

Claims

1. At a computer system including a processor and a memory, in a computer networking environment including a plurality of computing systems, a computer-implemented method for implementing one or more custom operators in a query for a parallel query engine, the method comprising:

an act of receiving a portion of partitioned input data at a parallel query engine, wherein the parallel query engine is configured to process the partitioned input data using a sequence of operators, including one or more built-in operators that are part of the parallel query engine;

an act of incorporating at least one user-defined custom operator into the sequence of operators for processing the partitioned input data, the at least one user-defined custom operator being provided to the parallel query engine by a user and being configured for processing along with the one or more built-in operators by being configured to;

poll a predecessor operator of the at least one user-defined custom operator in the sequence of operators to determine the predecessor operator'"'"'s output information, the output information including (i) a number of partitions of the input data that are requestable by the at least one user-defined custom operator and (ii) one or more ordering guarantees that apply to output of the at least one user-defined custom operator;

repartition the input data by adding or reducing the number of partitions of the input data during processing of the input data; and

determine whether changes have occurred that affect the one or more ordering guarantees and, when changes have occurred that affect the one or more ordering guarantees, modify at least a portion of the one or more ordering guarantees that apply to the output of the at least one user-defined custom operator;

an act of accessing the sequence of operators to determine how the partitioned input data is to be processed, wherein the at least one user-defined custom operator is accessed in the same manner as the built-in operators as part of the sequence of operators; and

an act of processing the sequence of operators, including processing both the built-in operators and the at least one user-defined custom operator, according to the determination indicating how the data is to be processed.

2. The method of claim 1, wherein the parallel query engine maintains a set of threads to pull data from a final query operator in the sequence of operators, and wherein the final query operator pulls data from a preceding operator in the sequence of operators using the same set of threads.

3. The method of claim 2, wherein a processing thread is instantiated for each operator task that is ready for processing.

4. The method of claim 1, wherein the output information includes one or more configuration options identifying how the data is configured.

5. The method of claim 2, wherein one or more different execution mechanisms are employed including at least one of single-thread, multi-thread and one-thread-per-task parallelism.

6. A computer program product for implementing a method for generating a partitioned representation of a sequence of query operators in a parallel query engine, the computer program product comprising one or more hardware computer-readable storage devices having stored thereon computer-executable instructions that, when executed by one or more processors of a computing system, cause the computing system to perform the method, the method comprising:

an act of accessing a sequence of operators configured to process a portion of partitioned input data in a parallel query system, the sequence of operators comprising one or more built-in operators that are part of a parallel query engine and at least one user-defined custom operator, the at least one user-defined custom operator being provided to the parallel query engine by a user and being configured for processing along with the one or more built-in operators by being configured to;

poll a predecessor operator of the at least one user-defined custom operator in the sequence of operators to determine the predecessor operator'"'"'s output information, the output information including (i) a number of partitions of the input data that are requestable by the at least one user-defined custom operator and (ii) one or more ordering guarantees that apply to output of the at least one user-defined custom operator;

repartition the input data by adding or reducing the number of partitions of the input data during processing of the input data; and

determine whether changes have occurred that affect the one or more ordering guarantees and, when changes have occurred that affect the one or more ordering guarantees, modify at least a portion of the one or more ordering guarantees that apply to the output of the at least one user-defined custom operator;

an act of generating a list of partitions into which the input data has been partitioned;

an act of determining a number of partitions that will be made during a re-partitioning operation at an indicated built-in operator in the sequence of operators; and

an act of generating a partitioned representation of the sequence of operators, wherein the partitioned representation of the sequence of operators provides internal information regarding the processing of the input data by the indicated built-in operator, the internal information enabling processing of the input data by one of the at least one user-defined custom operator.

7. The computer program product of claim 6, wherein the input data is re-partitioned into a fewer number of partitions by the sequence of operators.

8. The computer program product of claim 6, further comprising:

an act of passing the partitioned representation to one or more other operators in the sequence of operators; and

an act of the receiving operators adding their own internal partition information to the partitioned representation.

9. The computer program product of claim 6, wherein the partitioned representation provides an indication of those characteristics that are necessary for operators to be included as part of the sequence of operators.

10. The computer program product of claim 6, wherein the partitioned representation provides an indication of those characteristics that are necessary for operators to be efficiently executed.

11. A computer system comprising the following:

one or more processors;

system memory;

one or more computer-readable storage media having stored thereon computer-executable instructions that, when executed by the one or more processors, causes the computing system to perform a method for implementing one or more custom operators in a query for a parallel query engine, the method comprising the following;

an act of receiving a portion of partitioned input data at a parallel query engine, wherein the parallel query engine is configured to process the partitioned input data using a sequence of operators, including one or more built-in operators that are part of the parallel query engine;

an act of incorporating at least one user-defined custom operator into the sequence of operators for processing the partitioned input data, the at least one user-defined custom operator being provided to the parallel query engine by a user and being configured for processing along with the one or more built-in operators by being configured to;

poll a predecessor operator of the at least one user-defined custom operator in the sequence of operators to determine the predecessor operator'"'"'s output information, the output information including (i) a number of partitions of the input data that are requestable by the at least one user-defined custom operator and (ii) one or more ordering guarantees that apply to output of the at least one user-defined custom operator;

repartition the input data by adding or reducing the number of partitions of the input data during processing of the input data; and

determine whether changes have occurred that affect the one or more ordering guarantees and, when changes have occurred that affect the one or more ordering guarantees, modify at least a portion of the one or more ordering guarantees that apply to the output of the at least one user-defined custom operator;

an act of accessing the sequence of operators to determine how the partitioned input data is to be processed, wherein the at least one user-defined custom operator is accessed in the same manner as the built-in operators as part of the sequence of operators; and

an act of processing the sequence of operators, including processing both the built-in operators and the at least user-defined one custom operator, processing the sequence of operators including processing the sequence of operators in reverse order such that a last operator in the sequence of operators polls its predecessor operator in the sequence of operators to determine the predecessor operator'"'"'s output information.