Method of converting query plans to native code

• US 9,767,147 B2
• Filed: 11/23/2015
• Issued: 09/19/2017
• Est. Priority Date: 03/12/2013
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Freedman, Craig Steven, Ismert, Erik
• Primary Examiner(s): Rostami, Mohammad S
• Assistant Examiner(s): ABRAHAM, AHMED M
• Application Number:
  US14/949,302
• Publication Number:
  US 20160078084A1
• Time in Patent Office: 666 Days
• Field of Search: 707718, 707719, 707720
• CPC Class Codes: G06F 16/24526 Internal representations for queries
• CPC Class Codes: G06F 16/24542 Plan optimisation

Abstract

Performing database queries. A method includes receiving a particular database query. The method further includes accessing a query plan based on the particular database query. The query plan has operators and specific operational parameters associated with each of the operators. The association of operators and specific operational parameters is specific to the particular database query. From the query plan, the method further includes instantiating a plurality of compiled code templates. Each code template includes executable code that when executed performs functionality of one of the operators from the query plan with the specific operational parameters applied in the compilation. The method further includes binding the code templates together using programmatic control flow to create a functioning program.

Claims

1. A computer-implemented method for translating database queries into native machine code so that use of an interpreter which employs statically written code to process a given query can be eliminated, to improve efficiency of processing the given query, the computer-implemented method being performed by one or more processors executing computer-executable instructions for the computer-implemented method, and the computer-implemented method comprising:

receiving a particular database query;

accessing a query plan based on the particular database query, the query plan having operators and specific operational parameters associated with each of the operators, the association of operators and specific operational parameters being specific to the particular database query;

from the query plan generating one or more mixed abstract trees that represent metadata, imperative logic, expressions and query plans; and

based on the one or more mixed abstract trees, using programmatic control flow to create code from which native machine code for the particular database query can be compiled and executed natively without having to process the query plan using an interpreter which employs statically written code, and wherein using said programmatic control flow comprises;

transforming the one or more mixed abstract trees into one or more simpler data structures which are convertible to said machine executable code; and

binding the one or more simpler data structures to create the native machine code for the particular database query that can be executed natively without having to process the query plan using an interpreter which employs statically written code.

2. The computer-implemented method of claim 1, wherein the programmatic control flow comprises labels and goto statements.

3. The computer-implemented method of claim 2, wherein the labels and goto statements of the programmatic flow control do not require passing control back through any intermediate operators.

4. The computer-implemented method of claim 1, wherein the programmatic flow control enables a child to return control to the child'"'"'s parent from more than one location.

5. The computer-implemented method of claim 1, wherein the one or more simpler data structures comprise one or more pure imperative tree structures that can be converted directly to low level machine code.

6. The computer-implemented method of claim 1, wherein the one or more mixed abstract trees comprise one or more abstract syntax trees that represent metadata, imperative logic, expression and query plans.

7. A computing system for translating database queries into native machine code so that use of an interpreter which employs statically written code to process a given query can be eliminated, to improve efficiency of processing the given query, the system comprising:

one or more computer readable media comprise computer executable instructions;

one or more processors which, when executing the computer-executable instructions, cause the computing system to be configured with a code generator architecture for translating database queries into native machine code so that use of an interpreter which employs statically written code to process a given query can be eliminated, to improve efficiency of processing the given query, and wherein the code generator architecture performs the following;

receives a particular database query;

access a query plan based on the particular database query, the query plan having operators and specific operational parameters associated with each of the operators, the association of operators and specific operational parameters being specific to the particular database query;

from the query plan, generates one or more mixed abstract trees that represent metadata, imperative logic, expressions and query plans; and

based on the one or more mixed abstract trees, uses programmatic control flow to create code from which native machine code for the particular database query can be compiled and executed natively without having to process the query plan using an interpreter which employs statically written code, and wherein using the programmatic control flow comprises;

transforming the one or more mixed abstract trees into one or more simpler data structures which are convertible to said machine executable code; and

binding the one or more simpler data structures to create the native machine code for the particular database query that can be executed natively without having to process the query plan using an interpreter which employs statically written code.

8. The computing system of claim 7, wherein the programmatic control flow comprises labels and goto statements.

9. The computing system of claim 8, wherein the labels and goto statements of the programmatic flow control do not require passing control back through any intermediate operators.

10. The computing system of claim 7, wherein the programmatic flow control enables a child to return control to the child'"'"'s parent from more than one location.

11. The computing system of claim 7, wherein the one or more simpler data structures comprise one or more pure imperative tree structures that can be converted directly to low level machine code.

12. The computing system of claim 7, wherein the one or more mixed abstract trees comprise one or more abstract syntax trees that represent metadata, imperative logic, expression and query plans.

13. A physical storage computer medium comprising computer executable instructions that when executed by one or more processors causes execution of a computer-implemented method for translating database queries into native machine code so that use of an interpreter which employs statically written code to process a given query can be eliminated, to improve efficiency of processing the given query, and wherein the computer-executable method is performed by:

receiving a particular database query;

accessing a query plan based on the particular database query, the query plan having operators and specific operational parameters associated with each of the operators, the association of operators and specific operational parameters being specific to the particular database query;

from the query plan generating one or more abstract syntax trees that represent metadata, imperative logic, expressions and query plans;

using programmatic control flow to create code from which native machine code for the particular database query can be compiled and executed natively without having to process the query plan using an interpreter which employs statically written code, and wherein using said programmatic control flow comprises;

transforming the abstract syntax trees to one or more simpler data structures which are convertible to said machine executable code; and

binding the one or more simpler data structures using programmatic control flow to create native machine code for the particular database query that can be executed natively without having to process the query plan using an interpreter which employs statically written code.

14. The physical storage computer medium of claim 13, wherein the programmatic control flow comprises labels and goto statements.

15. The physical storage computer medium of claim 14, wherein the labels and goto statements of the programmatic flow control do not require passing control back through any intermediate operators.

16. The physical storage computer medium of claim 14, wherein the programmatic flow control enables a child to return control to the child'"'"'s parent from more than one location.

17. The physical storage computer medium of claim 14, wherein the one or more simpler data structures comprise one or more pure imperative tree data structures.

18. The physical storage medium of claim 17, wherein the one or more pure imperative tree data structures can be converted directly to C code or to low level machine code.