Operator movement optimization technique for procedures
In some embodiments, a method receives a statement graph for a procedure that is used to access data and determines a set of producer statements and a set of consumer statements in the statement graph. A producer statement produces a variable for a consumer statement, and the consumer statement consumes the variable from the producer statement. The method optimizes the statement graph to generate an optimized procedure by moving an operator from a consumer statement to a producer statement or by moving an operator from a producer statement to a consumer statement. The optimized procedure is output based on the optimized statement graph.
1 . A method comprising:
receiving, by a query processor operating on a computing device, a query to retrieve data from a database, the query comprising software code including a procedure to determine which data to retrieve from the database, wherein the procedure comprises a plurality of statements;
generating, by the query processor operating on the computing device, a control flow graph and a data dependency graph, wherein the control flow graph represents an execution plan for the procedure and the data dependency graph is a directed acyclic graph comprising nodes and edges, wherein the nodes represent one or more of statements, tables, or input parameters and edges represent control dependency between nodes;
determining, by the query processor operating on the computing device, a set of producer statements and a set of consumer statements from the control flow graph and data dependency graph, wherein a producer statement produces a variable for a consumer statement, and the consumer statement consumes the variable from the producer statement;
generating, by the query processor operating on the computing device, a statement graph for the procedure representing relationships between the producer statements and consumer statements;
optimizing, by the query processor operating on the computing device, the statement graph by moving an operator from a consumer statement to a producer statement or by moving an operator from a producer statement to a consumer statement, wherein optimizing further comprises one or more of:
performing an intra-statement transformation to move statements within a single query tree; and
performing an inter-statement transformation comprising one or more safety checks to move statements between a plurality of query trees;
outputting, the query processor operating on the computing device, the optimized procedure based on the optimized statement graph; and
executing the optimized procedure to retrieve data from the database.
2 . The method of claim 1 , wherein receiving the statement graph comprises:
analyzing the procedure to determine statements in the procedure.
3 . The method of claim 2 , wherein analyzing the procedure comprises:
determining the control flow graph for the procedure based on a traversal path of execution from the procedure.
4 . The method of claim 3 , wherein analyzing the procedure comprises:
determining the data flow graph of data through the traversal path, wherein the data flow graph is used to determine whether a statement is a producer statement or a consumer statement.
5 . The method of claim 1 , wherein optimizing the statement graph comprises:
moving the operator from the consumer statement to the producer statement; and
updating a link between another statement and the consumer statement to point to the producer statement.
6 . The method of claim 1 , wherein optimizing the statement graph comprises:
moving the operator from the producer statement to the consumer statement; and
updating a link between another statement and the producer statement to point to the consumer statement.
7 . The method of claim 1 , wherein optimizing the statement graph comprises:
blocking moving the operator from the consumer statement to the producer statement or moving the operator from the producer statement to the consumer statement when a violation of a transformation rule occurs.
8 . The method of claim 1 , wherein optimizing the statement graph comprises:
blocking moving another operator from a consumer statement to a producer statement or moving the another operator from a producer statement to a consumer statement when a variable that is produced by a statement S0 and a statement S1, the variable is consumed by the statement S1 and a statement S2, and the statement S1 updates the value of variable before being consumed by statement S2.
9 . The method of claim 1 , wherein optimizing the statement graph comprises:
blocking moving of another operator from a consumer statement to a producer statement or another moving the another operator from a producer statement to a consumer statement when the moving of the another operator results in a loop head or branch head being empty.
10 . The method of claim 1 , wherein optimizing the statement graph comprises:
determining a first optimization rule; and
moving the operator from the consumer statement to the producer statement or moving the operator from the producer statement to the consumer statement based on the first optimization rule to form a first intermediate plan for the statement graph.
11 . The method of claim 10 , wherein optimizing the statement graph comprises:
determining a second optimization rule; and
moving another operator from a consumer statement to a producer statement or moving the another operator from a producer statement to a consumer statement based on the second optimization rule to form a second intermediate plan for the statement graph.
12 . The method of claim 1 , wherein optimizing the statement graph comprises:
performing an optimization of the procedure based on a plurality of optimization rules to alter the statement graph, wherein the statement graph is iteratively optimized by each optimization rule.
13 . The method of claim 1 , wherein optimizing the statement graph comprises:
performing the intra-statement transformation to move an operator within a statement to transform the operator into an operator that can be moved from the consumer statement to the producer statement or from the producer statement to the consumer statement.
14 . The method of claim 1 , wherein optimizing the statement graph comprises:
determining sibling statements that provide a same variable to a consumer statement; and
performing the intra-statement transformation to move an operator within one of the sibling statements to make the operator movable from the producer statement to the consumer statement or from the consumer statement to the producer statement.
15 . A non-transitory computer-readable storage medium having stored thereon computer executable instructions, which when executed by a computing device, cause the computing device to be operable for:
receiving, by a query processor operating on a computing device, a query to retrieve data from a database, the query comprising software code including a procedure to determine which data to retrieve from the database, wherein the procedure comprises a plurality of statements;
generating, by the query processor operating on the computing device, a control flow graph and a data dependency graph, wherein the control flow graph represents an execution plan for the procedure and the data dependency graph is a directed acyclic graph comprising nodes and edges, wherein the nodes represent one or more of statements, tables, or input parameters and edges represent control dependency between nodes;
determining, by the query processor operating on the computing device, a set of producer statements and a set of consumer statements from the control flow graph and data dependency graph, wherein a producer statement produces a variable for a consumer statement, and the consumer statement consumes the variable from the producer statement;
generating, by the query processor operating on the computing device, a statement graph for the procedure representing relationships between the producer statements and consumer statements;
optimizing, by the query processor operating on the computing device, the statement graph by moving an operator from a consumer statement to a producer statement or by moving an operator from a producer statement to a consumer statement, wherein optimizing further comprises one or more of:
performing an intra-statement transformation to move statements within a single query tree; and
performing an inter-statement transformation comprising one or more safety checks to move statements between a plurality of query trees;
outputting, the query processor operating on the computing device, the optimized procedure based on the optimized statement graph; and
executing the optimized procedure to retrieve data from the database.
16 . The non-transitory computer-readable storage medium of claim 15 , wherein optimizing the statement graph comprises:
moving the operator from the consumer statement to the producer statement; and
updating a link between another statement and the consumer statement to point to the producer statement.
17 . The non-transitory computer-readable storage medium of claim 15 , wherein optimizing the statement graph comprises:
blocking moving another operator from a consumer statement to a producer statement or moving the another operator from a producer statement to a consumer statement when a variable that is produced by a statement S0 and a statement S1, the variable is consumed by the statement S1 and a statement S2, and the statement S1 updates the value of variable before being consumed by statement S2.
18 . The non-transitory computer-readable storage medium of claim 15 , wherein optimizing the statement graph comprises:
determining a first optimization rule;
moving the operator from the consumer statement to the producer statement or moving the operator from the producer statement to the consumer statement based on the first optimization rule to form a first intermediate plan for the statement graph;
determining a second optimization rule; and
moving another operator from a consumer statement to a producer statement or moving the another operator from a producer statement to a consumer statement based on the second optimization rule to form a second intermediate plan for the statement graph.
19 . An apparatus comprising:
one or more computer processors; and
a computer-readable storage medium comprising instructions for controlling the one or more computer processors to be operable for:
receiving, by a query processor operating on a computing device, a query to retrieve data from a database, the query comprising software code including a procedure to determine which data to retrieve from the database, wherein the procedure comprises a plurality of statements;
generating, by the query processor operating on the computing device, a control flow graph and a data dependency graph, wherein the control flow graph represents an execution plan for the procedure and the data dependency graph is a directed acyclic graph comprising nodes and edges, wherein the nodes represent one or more of statements, tables, or input parameters and edges represent control dependency between nodes;
determining, by the query processor operating on the computing device, a set of producer statements and a set of consumer statements from the control flow graph and data dependency graph, wherein a producer statement produces a variable for a consumer statement, and the consumer statement consumes the variable from the producer statement;
generating, by the query processor operating on the computing device, a statement graph for the procedure representing relationships between the producer statements and consumer statements;
optimizing, by the query processor operating on the computing device, the statement graph by moving an operator from a consumer statement to a producer statement or by moving an operator from a producer statement to a consumer statement, wherein optimizing further comprises one or more of:
performing an intra-statement transformation to move statements within a single query tree; and
performing an inter-statement transformation comprising one or more safety checks to move statements between a plurality of query trees;
outputting, the query processor operating on the computing device, the optimized procedure based on the optimized statement graph; and
executing the optimized procedure to retrieve data from the database.