Optimized SQL code generation

• US 20050027701A1
• Filed: 07/07/2004
• Published: 02/03/2005
• Est. Priority Date: 07/07/2003
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: Netezza (International Business Machines Corporation)
• Inventors: Zane, Barry M., Hinshaw, Foster D., Kirkpatrick, Dana A., Ballard, James P., Yerabothu, Premanand
• Granted Patent: US 7,430,549 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/24524 Access plan code generation and invalidation; Reuse of access plans
• CPC Class Codes: G06F 16/24547 Optimisations to support specific applications; Extensibility of optimisers
• CPC Class Codes: G06F 16/24549 Run-time optimisation
• CPC Class Codes: G06F 16/2456 Join operations
• CPC Class Codes: G06F 16/2471 Distributed queries
• CPC Class Codes: G06F 8/30 Creation or generation of source code
• CPC Class Codes: Y10S 707/99932 Access augmentation or optimizing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

This invention relates generally to a system for processing database queries, and more particularly to a method for generating high level language or machine code to implement query execution plans. The present invention provides a method for generating executable machine code for query execution plans, that is adaptive to dynamic runtime conditions, that is compiled just in time for execution and most importantly, that avoids the bounds checking, pointer indirection, materialization and other similar kinds of overhead that are typical in interpretive runtime execution engines.

Claims

1. A method for generating machine executable code for implementing a query of a database, the database having tables and records of data, comprising the steps of:

receiving a subject query;

forming an execution plan corresponding to the subject query, the execution plan having a sequence of pieces and corresponding processes for implementing the pieces; and

for each piece of the plan, (a) generating source code using different code generation techniques as a function of any combination of data characteristics, current conditions and workload, and (b) compiling the generated source code to form machine executable code for implementing the subject query, said compiling being in a manner that optimizes total query processing time, including, compilation time and execution time.

2. A method as claimed in claim 1 wherein the data characteristics include any combination of precision of a value existing in the database, scale of a value existing in the database, size of affected data existing in the database and data type.

3. A method as claimed in claim 1 wherein the step of generating further includes selecting code generation techniques based on intermediate results from earlier pieces, such that source code generation is effectively adapted to dynamic conditions.

4. A method as claimed in claim 1 wherein:

the subject query is in a language native to the database; and

the generated source code is in a high level language.

5. A method as claimed in claim 1 wherein the step of generating source code includes generating source code for each process of each piece of the plan on a need-only basis, such that a savings on compilation time is achieved.

6. A method as claimed in claim 5 wherein the need only basis provides generating source code for only those relevant members of a declared structure.

7. A method as claimed in claim 1 wherein the subject query includes a join operation;

and

the step of generating source code includes (a) representing output stream of the join operation as local variables that reference current records in each input stream, and (b) projecting named fields of the records, such that use of intermediate materialization and auxiliary structures are minimized.

8. A method as claimed in claim 7 wherein the step of projecting includes utilizing structure offset expressions in the generated source code.

9. A method as claimed in claim 1 wherein the step of generating source code includes:

(a) minimally defining relevant structures and classes, and (b) forming therefrom optimized include statements in the source code, the optimized include statements enabling reduced compilation time.

10. A method as claimed in claim 1 wherein the step of generating source code includes, adjusting variables in the source code to have widths no larger than widths of actual data values of respective data in the database.

11. A method as claimed in claim 1 wherein the step of generating source code uses different combinations of the code generation techniques to provide different degrees of optimization in compiling.

12. A method as claimed in claim 1 wherein the step of generating source code further includes for each instance of a function call to a respective function recited in the source code, (i) determining size of data affected by the function call, and (ii) based on determined data size, replacing the instance of the function call in the source code with source code for implementing the respective function, such that the respective function itself is coded in-line.

13. A method as claimed in claim 12 wherein the step of replacing is performed as a function of determined data size relative to a threshold.

14. A method as claimed in claim 1 wherein the subject query includes an outer join operation;

and

the step of generating source code includes effectively overwriting field references in the outer join operation with null values.

15. A method as claimed in claim 14 wherein the step of generating source code includes using a null value indicator for overwriting field references in the outer join operation.

16. A method for generating machine executable code for implementing a query of a database, the database having tables and records of data, comprising the steps of:

receiving a subject query;

forming an execution plan corresponding to the subject query, the execution plan having a sequence of pieces and corresponding processing nodes for implementing the pieces;

generating high level language source code for each piece of the plan including (a) minimally defining relevant structures and classes, and (b) forming therefrom optimized Include statements in the source code; and

compiling the generated source code to form machine executable code for implementing the subject query, the formed optimized Include statements in the source code enabling relatively reduced compilation time.

17. A method as claimed in claim 16 wherein the step of forming optimized Include statements in the source code includes generating source code for only these relevant members of a declared structure.

18. A method as claimed in claim 16 wherein the step of minimally defining includes inserting in-line into the generated source code respective local declarations of a relevant structures and classes defining only those class members and structure members that will be used by the generated source code.

19. A method as claimed in claim 16 wherein:

the high level language is C++; and

the step of generating source code includes omitting a traditional #Include statement of a header of a structure declaration in the generated source code, where only certain members of the structure are relevant to the subject query.

20. A method for generating machine executable code for implementing a query of a database, the database having tables and records of data, comprising the steps of:

receiving a subject query;

forming an execution plan corresponding to the subject query, the execution plan having a sequence of pieces and corresponding processing nodes for implementing the pieces;

for each piece of the plan, generating high level language source code including adjusting variables in the source code to have widths equivalent to widths of respective actual data values existing in the database, such that optimized compilation is enabled; and

compiling the generated source code to form machine executable code for implementing the subject query, said compiling being done in optimal compile time.

21. A method as claimed in claim 20 wherein the step of adjusting variables is based on determined ranges of data values in the database.

22. A method as claimed in claim 21 wherein the step of adjusting variables further includes tracking ranges of data values in the database.

24. A method as in claimed in claim 20 wherein step of optimizing includes applying a higher degree of optimization for longer expected execution time.

23. A method for generating machine executable code for implementing a query of a database, the database having tables and records of data, comprising the steps of:

receiving a subject query;

forming an execution plan corresponding to the subject query, the execution plan having a sequence of pieces and corresponding processing nodes for implementing the pieces;

for each piece of the plan, generating high level language source code;

optimizing the source code for compilation, said optimizing being a function of expected query execution time; and

compiling the source code to form machine executable code for implementing the subject query.