METHODS AND APPARATUS OF SHARED EXPRESSION EVALUATION ACROSS RDBMS AND STORAGE LAYER

• US 20140258266A1
• Filed: 03/06/2013
• Published: 09/11/2014
• Est. Priority Date: 03/06/2013
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Cruanes, Thierry, Xie, Junyi, Lau, Yiu Woon
• Granted Patent: US 9,773,041 B2
• Time in Patent Office: Days
• US Class Current: 707/718
• CPC Class Codes: G06F 16/2453 Query optimisation
• CPC Class Codes: G06F 16/2454 Optimisation of common expressions
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/24544 Join order optimisation
• CPC Class Codes: G06F 16/24556 Aggregation; Duplicate elimination
• CPC Class Codes: G06F 16/2456 Join operations
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 16/2471 Distributed queries

Abstract

Techniques are provided for sharing expression evaluation across a database management system and a storage layer. According to an embodiment, a plurality of target operators are identified that include a common expression. Each respective target operator corresponds to a step that evaluates the common expression during query execution. The plurality of target operators are modified to enable sharing of an evaluation result of the common expression. The query is executed according to the target operators. During query execution, the evaluation result is shared by the target operators. In other embodiments, the evaluation of the common expression is pushed to a storage layer. During query execution, a database management system retrieves the evaluation result of the common expression from the storage layer.

Claims

1. A method for optimizing query execution, the method comprising:

identifying, in an query execution plan, a plurality of target operators that include a common expression;

wherein each respective target operator corresponds to a step that evaluates the common expression during query execution to perform a respective operation;

modifying the plurality of target operators to enable sharing of an evaluation result of the common expression;

executing the query according to the modified target operators;

wherein during said executing, the evaluation result is shared by the target operators;

wherein the method is performed by one or more computing devices.

2. The method of claim 1, further comprising:

pushing evaluation of the common expression to a storage layer;

wherein during said executing, a database management system retrieves the evaluation result of the common expression from the storage layer.

3. The method of claim 2, wherein the storage layer returns a set of rows that includes the evaluation result.

4. The method of claim 1, wherein the common expression is a hash computation on a common hash key.

5. The method of claim 1, wherein identifying the plurality of target operators comprises:

traversing operators of a query execution tree to identify a first target operator that is a hash-user;

wherein the first target operator includes an expression for computing a hash value from a particular hash key;

traversing a subtree of the query execution tree using the first target operator as a root to identify one or more operators in the subtree that are also hash-users;

for each hash-user identified in the subtree, determining whether a hash key is identical to the particular hash key;

in response to determining that the hash-user includes a hash key that is identical to the particular hash key, marking the respective operator as a target operator.

6. The method of claim 1, wherein modifying the plurality of target operators comprises:

for one or more target operators of the plurality of target operators, replacing the common expression with a reference to a shared expression;

wherein replacing the common expression with a reference to a shared expression causes a respective target operator to access the evaluation result without computing the evaluation result.

7. The method of claim 1,

wherein modifying the plurality of target operators comprises assigning responsibility for evaluating the common expression to a single target operator of the plurality of operators;

wherein the responsibility is assigned to a first target operator in a dataflow of a query execution tree.

8. The method of claim 1, further comprising:

modifying a dataflow among the plurality of target operators;

wherein modifying the dataflow comprises;

for at least a first target operator of the plurality of target operators, modifying a row output to include the evaluation result;

for at least a second target operator of the plurality of target operators, modifying a row input to include the evaluation result;

wherein the evaluation result is passed up a share path from the first target operator to the second target operator.

9. The method of claim 1,

wherein the plurality of target operators include different target operators;

wherein a first target operator of the plurality of target operators uses the evaluation result to perform a first type of operation;

wherein the second target operation of the plurality of target operators users the evaluation result to perform a second type of operation;

wherein the first type of operation is different than the second type of operation.

10. The method of claim 1, wherein the plurality of target operators includes two or more of:

a hash join, a hash group by, a bloom filter, or an output table queue.

11. The method of claim 1, further comprising:

determining whether a number of target operators identified satisfies a threshold;

wherein in said modifying is performed in response to determining that the number of target operators identified satisfies the threshold.

12. One or more non-transitory computer-readable storage media storing instructions, which, when executed by one or more processors, cause one or more computing devices to perform operations comprising:

identifying, in an query execution plan, a plurality of target operators that include a common expression;

wherein each respective target operator corresponds to a step that evaluates the common expression during query execution to perform a respective operation;

modifying the plurality of target operators to enable sharing of an evaluation result of the common expression;

executing the query according to the modified target operators;

wherein during said executing, the evaluation result is shared by the target operators.

13. The non-transitory computer-readable media of claim 12, further storing instructions that cause the one or more computing devices to perform operations comprising:

pushing evaluation of the common expression to a storage layer;

wherein during said executing, a database management system retrieves the evaluation result of the common expression from the storage layer.

14. The non-transitory computer-readable media of claim 13, wherein the instructions cause the storage layer to return a set of rows that includes the evaluation result.

15. The non-transitory computer-readable media of claim 12, wherein the common expression is a hash computation on a common hash key.

16. The non-transitory computer-readable media of claim 12, wherein instructions for identifying the plurality of target operators comprise instructions for:

traversing operators of a query execution tree to identify a first target operator that is a hash-user;

wherein the first target operator includes an expression for computing a hash value from a particular hash key;

traversing a subtree of the query execution tree using the first target operator as a root to identify one or more operators in the subtree that are also hash-users;

for each hash-user identified in the subtree, determining whether a hash key is identical to the particular hash key;

in response to determining that the hash-user includes a hash key that is identical to the particular hash key, marking the respective operator as a target operator.

17. The non-transitory computer-readable media of claim 12, wherein instructions for modifying the plurality of target operators comprise instructions for:

for one or more target operators of the plurality of target operators, replacing the common expression with a reference to a shared expression;

wherein replacing the common expression with a reference to a shared expression causes a respective target operator to access the evaluation result without computing the evaluation result.

18. The non-transitory computer-readable media of claim 12, further storing instructions that cause the one or more computing devices to perform operations comprising:

modifying a dataflow among the plurality of target operators;

wherein modifying the dataflow comprises;

for at least a first target operator of the plurality of target operators, modifying a row output to include the evaluation result;

for at least a second target operator of the plurality of target operators, modifying a row input to include the evaluation result;

wherein the evaluation result is passed up a share path from the first target operator to the second target operator.

19. The non-transitory computer-readable media of claim 12,

wherein instructions for modifying comprise instructions for assigning responsibility for evaluating the common expression to a single target operator of the plurality of operators;

wherein the responsibility is assigned to a first target operator in a dataflow of a query execution tree.

20. The non-transitory computer-readable media of claim 12,

wherein the plurality of target operators include different target operators;

wherein a first target operator of the plurality of target operators uses the evaluation result to perform a first type of operation;

wherein the second target operation of the plurality of target operators users the evaluation result to perform a second type of operation;

wherein the first type of operation is different than the second type of operation.

21. The non-transitory computer-readable media of claim 12, further storing instructions that cause the one or more computing devices to perform operations comprising:

determining whether a number of target operators identified satisfies a threshold;

wherein in said modifying is performed in response to determining that the number of target operators identified satisfies the threshold.