Method of converting query plans to native code

• US 9,195,712 B2
• Filed: 03/12/2013
• Issued: 11/24/2015
• 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): Alam, Hosain
• Assistant Examiner(s): ABRAHAM, AHMED M
• Application Number:
  US13/797,035
• Publication Number:
  US 20140280030A1
• Time in Patent Office: 987 Days
• Field of Search: 707/718, 707/719, 707/720
• US Class Current: 1/1
• 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 instantiating a plurality of compiled code templates, each code template comprising compiled native machine 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, and wherein instantiating the plurality of code templates comprises;

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

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

binding the code templates together 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.

2. The computer-implemented method of claim 1, wherein the programmatic control flow comprises labels and go to 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 can be converted directly to C code.

6. The computer-implemented method of claim 1, wherein the one or more simpler data structures can be converted directly to low level machine code.

7. The computer-implemented method of claim 1, wherein instantiating a plurality of code templates further comprises using a compiler to optimize code for the functioning program.

8. A 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 processors; and

one or more computer readable media, wherein the one or more computer readable media comprise computer executable instructions that when executed by at least one of the one or more processors cause the system to execute in accordance with a code generator architecture configured to perform the following;

receive 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 instantiating a plurality of compiled code templates, each code template comprising compiled native machine 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, and wherein instantiating the plurality of code templates comprises;

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

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

bind the code templates together 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.

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

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

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

12. The system of claim 8, wherein the one or more simpler data structures can be converted directly to C code.

13. The system of claim 8, wherein the one or more simpler data structures can be converted directly to low level machine code.

14. The system of claim 8, wherein instantiating a plurality of code templates further comprises using a compiler to optimize code for the functioning program.

15. 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 instantiating a plurality of compiled code templates, each code template comprising compiled native machine 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, and wherein instantiating the plurality of code templates comprises;

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

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

binding the code templates together 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.

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

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

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

19. The physical storage computer medium of claim 15, wherein the one or more simpler data structures can be converted directly to C code.

20. The physical storage computer medium of claim 15, wherein the one or more simpler data structures can be converted directly to low level machine code.