System, method, and program for extending a SQL compiler for handling control statements packaged with SQL query statements

• US 5,875,334 A
• Filed: 10/27/1995
• Issued: 02/23/1999
• Est. Priority Date: 10/27/1995
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Tran, Brian T., Fuh, You-Chin (Gene), Chow, Jyh-Herng, Mattos, Nelson Mendonca
• Primary Examiner(s): Trammell, James P.
• Assistant Examiner(s): Chavis, John Q.
• Application Number:
  US08/548,969
• Time in Patent Office: 1,215 Days
• Field of Search: 395/705, 707/4
• US Class Current: 717/141
• CPC Class Codes: G06F 16/2443 Stored procedures
• CPC Class Codes: G06F 16/24524 Access plan code generation and invalidation; Reuse of access plans
• CPC Class Codes: G06F 8/427 Parsing
• CPC Class Codes: G06F 8/433 Dependency analysis; Data or control flow analysis
• CPC Class Codes: G06F 8/443 Optimisation

Abstract

This invention provides an integrated compiler for compiling SQL3 control statements having procedural, i.e., control, information packaged together with query, i.e., non-procedural, statements. A query extractor contained within the parser extracts the query statement from the control statement leaving a control skeleton. The query statement is processed as usual through a query compiler for generating executable plans with the exception that the name resolution function for resolving variables is modified for looking up local variables. This modification takes into account the mapping of local and host variables to create a unification of local and host variables. The control skeleton is processed through a control analyzer which generates a representation of the control flow and a scope and symbol table. The control analyzer also unifies the local and host variables. A plan synthesizer then takes as input the control flow information, symbol tables, and individual executable plans for the query statements and generates a meta-plan comprising a merger of a top level plan for the control skeleton and sub-plans representing the executable plans of the query statement. Therefore, this invention provides a uniform way of treating local and host variables, provides an efficient way of performing bind-in/bind-out processes, creates a single execution plan requiring only a single run-time interpreter, and requires minimum enhancements to existing SQL2 compilers. In addition, this invention enables the application of global optimization techniques for optimizing both the control aspects and query aspects of the original control statement.

Claims

1. A system for compiling a database language statement having a procedural part packaged together with at least one declarative part, the system comprising:

a query extractor for separating the procedural part from the declarative part whereby the procedural part, separated from the declarative part, is a control skeleton;

an integrated compiler having a query compiler and a control analyzer wherein said control analyzer is specialized for compiling the procedural part;

the query compiler compiling the at least one declarative part and generating an executable plan;

the control analyzer generating a control flow representation of control flow information of the control skeleton; and

a plan synthesizer for synthesizing the output from the query compiler and the control analyzer by merging a code sequence generated from the control flow information of the control skeleton with the executable plan.

2. The system of claim 1 wherein the control skeleton comprises the procedural part of the database language statement and a token in place of the declarative part.

3. The system of claim 1 wherein the control flow representation preserves a semantic of the database language statement.

4. The system of claim 1 wherein the query extractor resides in a parser of the query compiler.

5. The system of claim 1 wherein the query compiler generates a representation of the declarative part independently from the control skeleton.

6. The system of claim 1 wherein the query compiler performs a name resolution function to determine a meaning of a local variable and invokes a symbol table look up routine to return a host variable name to a semantic routine of the query compiler if the name resolution function fails to find a column name.

7. The system of claim 1 further comprising at least one scope and a symbol table into which said control skeleton is fed for resolving local variables declared inside a compound statement used to create the scope.

8. The system of claim 1 wherein the control analyzer generates at least one scope and a symbol table from the control skeleton, populates a host variable table with each local variable, and populates an outer-most symbol table with each host variable.

9. The system of claim 8 wherein the query compiler handles all variables through the host variable table populated with host variables and local variables and a code generator allocating storage for the host and local variables from the symbol table.

10. The system of claim 1 wherein the plan synthesizer emits a global bind-in operator at the beginning of the executable plan to move host variable values into a SQL runtime.

11. The system of claim 1 wherein the plan synthesizer emits a global bind-out operator at the end of the executable plan to move host variable values out of a SQL runtime.

12. The system of claim 7 wherein the plan synthesizer utilizes information from the at least one scope, the symbol table, the control flow information and each executable plan for generating the meta-plan.

13. The system of claim 1 further comprising a global optimizer applying a procedural language optimization technique to the control skeleton sequence whereby the at least one declarative part is treated as a black box with certain characteristics.

14. The system of claim 5 wherein the representation of the declarative part is extended with a set of procedural nodes for the control flow representation.

15. The system of claim 1 wherein the control analyzer generates at least one scope and a symbol table when a compound statement is encountered in the database language statement.

16. The system of claim 1 wherein the control analyzer performs a control flow and data flow analysis for feedback to the query compiler in performing a global optimization.

17. The system of claim 16 wherein the control flow analysis is performed by traversing the control skeleton, and the plan synthesizer and query compiler operate interactively to generate an optimized executable meta-plan.

18. The system of claim 15 wherein the control analyzer utilizes the control flow representation, the at least one scope, and the symbol table to feed back information to the query compiler for global optimization.

19. The system of claim 1 wherein the control analyzer and query compiler operate interactively to perform global optimization.

20. The system of claim 1 wherein the control analyzer unifies local variables and host variables.

21. A system for compiling a database language statement having a procedural part packaged with at least one declarative part, the system comprising:

a parser for separating the procedural part from the declarative part whereby the procedural part, separated from the declarative part, is a control skeleton, and for generating a first representation of the declarative part and a control flow representation of the control skeleton;

an analyzer creating a table dependency graph from each declarative part;

a threaded code generator for generating a code sequence representing the control flow of the control skeleton;

a query rewrite applying rewrite rules to the declarative part based upon information from the analyzer to rewrite a query for each declarative part;

a query optimizer optimizing the code sequence and the plan for the declarative part based upon the information from the analyzer; and

a plan synthesizer synthesizing a final plan from an optimized code sequence and an optimized execution plan from the query optimizer.

22. The system of claim 21 wherein the analyzer associates each edge of the control flow representation with a cost by measuring a frequency of an execution of a corresponding query node in the control flow representation.

23. A system for compiling a database language statement having a procedural part packaged together with at least one declarative part, the database language statement embedded in an application program for querying a database managed by a server, the system comprising:

an integrated compiler having a first compilation path for compiling each declarative part apart from the procedural part and having a second compilation path for processing the procedural part;

a control analyzer, in the second compilation path, for analyzing a control flow of said procedural part;

populating a host variable table with local variables, and creating a symbol table of local and host variables;

a query compiler, in the first compilation path for handling all local variables as host variables from the host variable table populated with local variables in compiling each declarative part into an executable plan;

a threaded code generator, in the second compilation path, for generating a threaded code sequence of the control flow of the procedural part;

a plan synthesizer for embedding each executable plan into the threaded code sequence thereby creating a meta-plan, and allocating storage for local and host variables from the symbol table during code generation time;

a run time interpreter recursively executing each execution plan embedded within the threaded code sequence within the meta-plan wherein the meta-plan has one bind-in operator and one bind-out operator for communicating with the application input and output values of local and host variables.

24. A method for compiling a database language statement having a procedural part packaged together with at least one declarative part, said method comprising:

separating the procedural part from the declarative part;

generating, by a query compiler, an executable plan for each of the at least one declarative part;

generating a threaded code sequence based upon control flow information from the procedural part; and

embedding the executable plan for each of the at least one declarative part as a sub plan into the threaded code sequence to create an executable meta-plan.

25. The method of claim 24 wherein the step of separating the procedural part from the declarative part further comprises replacing the declarative part with a token in the procedural part to create a control skeleton.

26. The method of claim 24 further comprising:

invoking, recursively, an interpreter, when a sub plan is encountered at runtime, for an execution of the sub plan.

27. The method of claim 24 further comprising:

populating a host variable table with local variables for use by the query compiler in handling all variables as host variables.

28. The method of claim 27 further comprising:

populating, during a parsing phase, a symbol table with local variables and host variables and allocating storage, during the generation of the threaded code sequence, for the local variables and host variables.

29. The method of claim 28 further comprising:

executing the meta-plan utilizing one bind-in operator and one bind-out operator.

30. The method of claim 24 further comprising:

applying a procedural language optimization technique to the threaded code sequence whereby the at least one declarative part is treated as a black box with a certain characteristic.

31. A method for compiling a database language statement having a procedural part packaged together with at least one declarative part, the method comprising:

separating the database language statement into the procedural part and the declarative part;

utilizing a query compilation path, for the declarative part, for generating an executable plan for each one of the at least one declarative part;

utilizing a second compilation path, separate from said query compilation path, for the procedural part, for generating control flow information and a threaded code sequence based upon the control flow information; and

synthesizing a final execution plan for the database language statement from the threaded code sequence and the executable plan for each one of the at least one declarative part.

32. The method of claim 31 wherein the step of separating the database language statement further comprises:

transforming a SET statement into an equivalent query statement thereby directly translating the procedural part to the declarative part;

extracting a search condition of a procedural part and replacing the search condition with a compiler generated local variable and, based upon the search condition, assigning a first representation for true or a second representation for false to the local variable, thereby creating a pure procedural part; and

replacing each declarative part with a token to create a control skeleton for the procedural part of the database language statement.

33. The method of claim 31 wherein the first compilation path and second compilation path interchange information to perform a global optimization technique.

34. A method for compiling a database language statement having a procedural part packaged together with at least one declarative part, the method comprising:

transforming a SET statement into an equivalent query statement thereby directly translating the procedural part to a pure declarative part;

extracting a search condition of a procedural part and replacing the search condition with a compiler generated local variable and, based upon the search condition, assigning a first representation for true or a second representation for false to the local variable, thereby creating a pure procedural part;

replacing each declarative part with a token to create a control skeleton representing the procedural part of the database language statement; and

compiling each declarative part through a query compiler and processing the control skeleton separate from the declarative part.

35. A method of compiling a database language statement having a procedural part packaged together with at least one declarative part, the method comprising:

separating the procedural part and the declarative part into a control skeleton and the declarative part;

compiling, through a first compilation path through a query compiler, each declarative part into an execution plan;

generating, separately from said first compilation path, a threaded code sequence representing a control flow of the control skeleton; and

synthesizing the threaded code sequence and each execution plan into one meta-plan.

36. A system for compiling a database language statement having a procedural part packaged together with at least one declarative part, said system comprising:

means for separating the procedural part from the declarative part;

means for processing the declarative part through a query compiler to generate an executable plan for each of the at least one declarative part;

means, separate from the query compiler, for analyzing control flow information of the procedural part and generating a threaded code sequence based upon the control flow information; and

means for merging the executable plan for each of the at least one declarative part into the threaded code sequence to create an executable meta-plan.

37. The system of claim 36 further comprising means for treating local variables as if they were host variables.

38. The system of claim 37 further comprising:

means for including local variables along with the host variables in a host variable table generated by the query compiler; and

means for allocating storage in the meta-plan as a persistent store for allowing values of local variables to exist across multiple declarative parts.

39. A system for compiling a database language statement having a procedural part packaged together with at least one declarative part, said system comprising:

means for separating the procedural part from the declarative part;

means for integrating a compilation of the declarative part in a first compilation path and a processing of the procedural part in a second path;

means, in the first compilation path, for compiling each declarative part into an execution plan;

means, in the second path for generating a threaded code sequence representing a control flow of the procedural part; and

means for synthesizing the threaded code sequence and each execution plan into a meta-plan.

40. The system of claim 39 wherein the means for compiling each declarative part further comprises means for treating local variables as host variables.

41. The system of claim 40 wherein the means for treating local variables as host variables further comprises means for populating a host variable table with local variables for use by said means for compiling each declarative part.

42. The system of claim 39 further comprising means for populating a table with both local and host variables during a parsing phase of the database language statement and means for allocating storage for all variables in the table during a generation of code.

43. The system of claim 39 further comprising means for generating one bind-in operator and one bind-out operator for the meta-plan.

44. The system of claim 39 further comprising means for globally optimizing the threaded code sequence.

45. The system of claim 39 further comprising means, in the second path, for performing a control flow analysis of the procedural part and means for feeding the analysis to the means for compiling the declarative part for performing global optimization.

46. A system for compiling a database language statement having a procedural part packaged with at least one declarative part, the system comprising:

means for separating the procedural part from the declarative part into a control skeleton and the at least one declarative part;

means for generating a first representation of the declarative part and generating a control flow representation of a control flow of the control skeleton;

means for performing an analysis on the control flow representation and creating a table dependency graph from each declarative part;

means for generating a code sequence representing the control flow of the control skeleton;

means for applying rewrite rules to the declarative part, based upon information from the means for performing an analysis, for generating a plan for each declarative part;

means for optimizing the code sequence and the plan for the declarative part based upon the information from the means for performing an analysis; and

means for synthesizing a final plan from an optimized code sequence and an optimized execution plan from the means for optimizing.

47. An article of manufacture having a computer usable medium having computer readable program code means embodied therein for enabling a compilation of a database language statement having a procedural part packaged together with at least one declarative part, said article of manufacture comprising:

means for enabling a separation of the procedural part from the declarative part;

means for enabling an integrated compilation of the declarative part in a first compilation path and a processing of the procedural part in a second path;

means for enabling, in the first compilation path, a compilation of each declarative part into an execution plan by a query compiler;

means for enabling, in the second path, a generation of a threaded code sequence representing a control flow of the procedural part; and

means for enabling a merging of the threaded code sequence and each execution plan into a meta-plan.

48. A system for compiling a database language statement having a procedural part packaged together with at least one declarative part, the system comprising:

means for compiling each declarative part into an executable plan;

means for generating a threaded code sequence of a control flow of the procedural part; and

means for embedding each executable plan into the threaded code sequence as a single executable meta-plan.

49. The system of claim 48 wherein the single executable meta-plan has one bind-in operator and one bind-out operator.

50. A method for compiling a database language statement having a procedural part packaged together with at least one declarative part, the method comprising:

compiling each declarative part into an executable plan;

generating a threaded code sequence of a control flow of the procedural part; and

embedding each executable plan into the threaded code sequence.

51. An article of manufacture having a computer usable medium having computer readable program code means embodied therein for enabling a compilation of a database language statement having a procedural part packaged together with at least one declarative part, said article of manufacture comprising:

means for enabling a compilation of each declarative part into an executable plan;

means for enabling a generation of a threaded code sequence of a control flow of the procedural part; and

means for enabling an embedding of each executable plan into the threaded code sequence as a single executable meta-plan.