Method and apparatus for performing query aware partitioning

• US 10,394,813 B2
• Filed: 08/15/2016
• Issued: 08/27/2019
• Est. Priority Date: 07/30/2008
• Status: Active Grant

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Johnson, Theodore, Shkapenyuk, Vladislav, Spatscheck, Oliver
• Primary Examiner(s): Boccio, Vincent F
• Application Number:
  US15/237,200
• Publication Number:
  US 20160357814A1
• Time in Patent Office: 1,107 Days
• Field of Search: 707 2, 707999002, 707713
• CPC Class Codes: G06F 16/24539 using cached or materialised query results
• CPC Class Codes: G06F 16/2454 Optimisation of common expressions
• CPC Class Codes: G06F 16/24542 Plan optimisation

Abstract

A method and system for providing query aware partitioning are disclosed. For example, the method receives a query plan comprising a plurality of queries, and classifies each one of the plurality of queries. The method computes an optimal partition set for each one of the plurality of queries, and reconciles the optimal partition set of each one of the plurality of queries with at least one subset of queries of the plurality of queries. The method selects at least one reconciled optimal partition set to be used by each query of the plurality of queries, and stores the selected at least one reconciled optimal partition set in a computer readable medium.

Claims

1. A method for processing a query, the method comprising:

receiving, via a processor, a query plan comprising a plurality of queries;

classifying, via the processor, each one of the plurality of queries;

computing, via the processor, an optimal partition set for each one of the plurality of queries;

reconciling, via the processor, the optimal partition set of each one of the plurality of queries with a subset of queries of the plurality of queries, wherein the reconciling is performed after the computing, wherein reconciling comprises;

testing the optimal partition set of each one of the plurality of queries against all other queries to ensure compatibility;

selecting an optimal partition set that is compatible with at least two queries of the plurality of queries and has a lowest cost based upon a lowest cost computation, wherein the lowest cost computation comprises a reconciled optimal partition set that provides a least amount of data transfer between a plurality of nodes, wherein a cost is defined as 0 when a query node of the query plan processes only local data, as an input rate of the query node when the query node is incompatible with the optimal partition set and as an output rate of the query node when the query node is compatible with the optimal partition set; and

using the optimal partition set for the at least two queries of the plurality of queries;

selecting, via the processor, the reconciled optimal partition set to be used by each query of the plurality of queries;

storing, via the processor, the reconciled optimal partition set in a computer readable medium;

applying, via the processor, the reconciled optimal partition set to the query plan to transform the query plan into an optimized query plan, wherein the applying the optimized query plan comprises;

assigning an operator to each node of a plurality of nodes that each node will execute, wherein at least two of the plurality of nodes perform different operators;

providing a parameter for each operator at each of the plurality of nodes; and

informing each node of the plurality of nodes a source and a destination of a data stream;

applying, via the processor, the optimized query plan to the data stream; and

outputting, via the processor, a result of the applying to a user.

2. The method of claim 1, wherein the optimized query plan has a plurality of optimized queries.

3. The method of claim 1, wherein the optimized query plan distributes data received from the data stream to a plurality of nodes in accordance with the reconciled optimal partition set.

4. The method of claim 1, wherein the reconciling is repeated until all possible combination of subsets of the plurality of queries have been exhausted.

5. The method of claim 1, wherein the query plan is used for extracting data from a data stream.

6. A non-transitory computer-readable medium storing a plurality of instructions, which when executed by a processor, cause the processor to perform operations for processing a query, the operations comprising:

receiving a query plan comprising a plurality of queries;

classifying each one of the plurality of queries;

computing an optimal partition set for each one of the plurality of queries;

reconciling the optimal partition set of each one of the plurality of queries with a subset of queries of the plurality of queries, wherein the reconciling is performed after the computing, wherein reconciling comprises;

testing the optimal partition set of each one of the plurality of queries against all other queries to ensure compatibility;

selecting an optimal partition set that is compatible with at least two queries of the plurality of queries and has a lowest cost based upon a lowest cost computation, wherein the lowest cost computation comprises a reconciled optimal partition set that provides a least amount of data transfer between a plurality of nodes, wherein a cost is defined as 0 when a query node of the query plan processes only local data, as an input rate of the query node when the query node is incompatible with the optimal partition set and as an output rate of the query node when the query node is compatible with the optimal partition set; and

using the optimal partition set for the at least two queries of the plurality of queries;

selecting the reconciled optimal partition set to be used by each query of the plurality of queries;

storing the reconciled optimal partition set in a computer readable medium;

applying the reconciled optimal partition set to the query plan to transform the query plan into an optimized query plan, wherein the applying the optimized query plan comprises;

assigning an operator to each node of a plurality of nodes that each node will execute, wherein at least two of the plurality of nodes perform different operators;

providing a parameter for each operator at each of the plurality of nodes; and

informing each node of the plurality of nodes a source and a destination of a data stream;

applying the optimized query plan to the data stream; and

outputting a result of the applying to a user.

7. The non-transitory computer-readable medium of claim 6, wherein the optimized query plan has a plurality of optimized queries.

8. The non-transitory computer-readable medium of claim 6, wherein the optimized query plan distributes data received from the data stream to a plurality of nodes in accordance with the reconciled optimal partition set.

9. The non-transitory computer-readable medium of claim 6, wherein the reconciling is repeated until all possible combination of subsets of the plurality of queries have been exhausted.

10. The non-transitory computer-readable medium of claim 6, wherein the query plan is used for extracting data from a data stream.

11. An apparatus for processing a query, the apparatus comprising:

a hardware processor; and

a computer-readable medium storing a plurality of instructions, which when executed by the hardware processor, cause the processor to perform operations, the operations comprising;

receiving a query plan comprising a plurality of queries;

classifying each one of the plurality of queries;

computing an optimal partition set for each one of the plurality of queries;

reconciling the optimal partition set of each one of the plurality of queries with a subset of queries of the plurality of queries, wherein the reconciling is performed after the computing, wherein reconciling comprises;

testing the optimal partition set of each one of the plurality of queries against all other queries to ensure compatibility;

selecting an optimal partition set that is compatible with at least two queries of the plurality of queries and has a lowest cost based upon a lowest cost computation, wherein the lowest cost computation comprises a reconciled optimal partition set that provides a least amount of data transfer between a plurality of nodes, wherein a cost is defined as 0 when a query node of the query plan processes only local data, as an input rate of the query node when the query node is incompatible with the optimal partition set and as an output rate of the query node when the query node is compatible with the optimal partition set; and

using the optimal partition set for the at least two queries of the plurality of queries;

selecting the reconciled optimal partition set to be used by each query of the plurality of queries;

storing the reconciled optimal partition set in a computer readable medium;

applying the reconciled optimal partition set to the query plan to transform the query plan into an optimized query plan, wherein the applying the optimized query plan comprises;

assigning an operator to each node of a plurality of nodes that each node will execute, wherein at least two of the plurality of nodes perform different operators;

providing a parameter for each operator at each of the plurality of nodes; and

informing each node of the plurality of nodes a source and a destination of a data stream;

applying the optimized query plan to the data stream; and

outputting a result of the applying to a user.

12. The apparatus of claim 11, wherein the optimized query plan has a plurality of optimized queries.

13. The apparatus of claim 11, wherein the optimized query plan distributes data received from the data stream to a plurality of nodes in accordance with the reconciled optimal partition set.

14. The apparatus of claim 11, wherein the reconciling is repeated until all possible combination of subsets of the plurality of queries have been exhausted.

15. The apparatus of claim 11, wherein the query plan is used for extracting data from a data stream.