SYSTEMS AND METHODS FOR A QUERY OPTIMIZATION ENGINE

• US 20160034530A1
• Filed: 07/23/2015
• Published: 02/04/2016
• Est. Priority Date: 07/29/2014
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Metanautix, Inc. (Microsoft Corporation)
• Inventors: Nguyen, Patrick An Phu, Vassilakis, Theodore, Kryze, David, Viswanadha, Sreenivasa
• Granted Patent: US 10,437,843 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/2471 Distributed queries

Abstract

Various embodiments of the present disclosure can include systems, methods, and non-transitory computer readable media configured to receive at least one database query to be executed. At least one computation graph corresponding to the at least one database query is generated. The computation graph is transformed to an optimized computation graph. The respective portions of the optimized computation graph are distributed to a plurality of distributed computing systems for execution. A result for the at least one database query is provided.

Claims

1. A computer-implemented method comprising:

receiving, by a computing system, at least one database query to be executed;

generating, by the computing system, at least one computation graph corresponding to the at least one database query;

transforming, by the computing system, the computation graph to an optimized computation graph;

distributing, by the computing system, respective portions of the optimized computation graph to a plurality of distributed computing systems for execution; and

providing, by the computing system, a result for the at least one database query.

2. The computer-implemented method of claim 1, wherein transforming, by the computing system, the computation graph to the optimized computation graph further comprises:

evaluating, by the computing system, one or more candidate transformations for the computation graph, based at least in part on an objective function, to determine the optimized computation graph.

3. The computer-implemented method of claim 2, wherein evaluating, by the computing system, one or more candidate transformations for the computation graph based at least in part on the objective function further comprises:

determining, by the computing system, a respective cost for each candidate transformation, the cost indicating a respective computational complexity corresponding to the candidate transformation.

4. The computer-implemented method of claim 3, the method further comprising:

determining, by the computing system, the optimized computation graph based at least in part on the respective costs for the candidate transformations.

5. The computer-implemented method of claim 3, wherein the respective cost for each candidate transformation is determined over a threshold period of time, the method further comprising:

upon expiration of the threshold period of time, determining, by the computing system, the optimized computation graph based at least in part on the respective costs for the candidate transformations and on the respective costs for the threshold number of candidate transformations.

6. The computer-implemented method of claim 3, wherein the respective cost for a candidate transformation is based at least in part on one or more of:

a cost associated with a node of a candidate computation graph, a cost associated with a portion of the candidate computation graph, or a cost associated with the entire computation graph.

7. The computer-implemented method of claim 3, wherein the respective cost for each candidate transformation is determined based at least in part on an A-star search algorithm.

8. The computer-implemented method of claim 2, wherein the objective function is based at least in part on a weight vector that includes a plurality of weights.

9. The computer-implemented method of claim 8, wherein the weights included in the weight vector are tuned based at least in part one or more machine learning techniques.

10. The computer-implemented method of claim 9, wherein the machine learning techniques include Gaussian Processes.

11. The computer-implemented method of claim 8, wherein the weights included in the weight vector are tuned based at least in part weight regularization techniques.

12. The computer-implemented method of claim 8, wherein the weights included in the weight vector are tuned based at least in part on feature hashing techniques.

13. The computer-implemented method of claim 8, wherein the weight vector is automatically tuned based at least in part on respective amounts of time needed to execute one or more queries.

14. The computer-implemented method of claim 8, the method further comprising:

performing, by the computing system, adaptive learning by running one or more queries having a less than optimal cost; and

adjusting, by the computing system, one or more weights corresponding to the weight vector.

15. The computer-implemented method of claim 1, wherein the respective portions of the optimized computation graph are distributed to one or more of the distributed computing systems for which the respective portions are optimized for execution.

16. The computer-implemented method of 1, the method further comprising:

determining, by the computing system, a pipeline for executing one or more queries, the one or more queries including the at least one database query; and

optimizing, by the computing system, the one or more queries in the pipeline.

17. The computer-implemented method of claim 16, the method further comprising:

determining, by the computing system, that the pipeline is a repeated pipeline; and

determining, by the computing system, a cache for the pipeline.

18. The computer-implemented method of claim 16, wherein at least one input corresponding to the pipeline and at least one output corresponding to the pipeline are able to be defined using an extended Structured Query Language (SQL).

19. A system comprising:

at least one processor; and

a memory storing instructions that, when executed by the at least one processor, cause the system to perform;

receiving at least one database query to be executed;

generating at least one computation graph corresponding to the at least one database query;

transforming the computation graph to an optimized computation graph;

distributing respective portions of the optimized computation graph to a plurality of distributed computing systems for execution; and

providing a result for the at least one database query.

20. A non-transitory computer-readable storage medium including instructions that, when executed by at least one processor of a computing system, cause the computing system to perform:

receiving at least one database query to be executed;

generating at least one computation graph corresponding to the at least one database query;

transforming the computation graph to an optimized computation graph;

distributing respective portions of the optimized computation graph to a plurality of distributed computing systems for execution; and

providing a result for the at least one database query.