Methods and apparatus of shared expression evaluation across RDBMS and storage layer

• US 9,773,041 B2
• Filed: 03/06/2013
• Issued: 09/26/2017
• 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
• Primary Examiner(s): GORTAYO, DANGELINO N
• Application Number:
  US13/787,663
• Publication Number:
  US 20140258266A1
• Time in Patent Office: 1,665 Days
• Field of Search: 707706, 707713, 707714, 707715, 707718, 707719, 707721
• 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 a query execution plan compiled for a query, a plurality of target operators that includes an expression that computes a common value;

for a first target operator of the plurality of target operators, modifying a row output of the first target operator to add a column for an evaluation result comprising the common value;

for at least one second target operator of the plurality of target operators, modifying a row input of the second target operator to add a column for the evaluation result comprising the common value;

after modifying the row output for the first target operator and the row input for at least the second target operator, executing the query according to the plurality of target operators;

wherein during said executing, the evaluation result comprising the common value is shared by passing the evaluation result from the row output for the first target operator to the row input for the at least one second target operator;

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

2. The method of claim 1, further comprising:

pushing evaluation of the expression to a storage layer;

wherein the storage layer evaluates the expression that computes the common value during a table scan of stored data indicated by the expression;

wherein during said executing, a database management system retrieves the evaluation result of the 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 comprising the common value.

4. The method of claim 1, wherein the expression is a hash expression that computes a common hash value 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 corresponding to the query execution plan to identify a first operator;

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

traversing a subtree of the query execution tree using the particular operator as a root to identify one or more additional operators, wherein the one or more additional operators also include an expression for computing the hash value on the particular hash key.

6. The method of claim 1, further comprising:

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

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

7. The method of claim 1, further comprising

assigning responsibility for evaluating the expression to a single target operator of the plurality of target operators.

8. The method of claim 1,

wherein the plurality of target operators includes different target operators;

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

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

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

9. 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.

10. The method of claim 1, further comprising:

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

wherein the first target operator and the second target operator are modified in response to determining that the number of target operators identified satisfies the threshold.

11. The method of claim 1, wherein:

the common value is a hash value;

the first target operator computes the hash value.

12. One or more non-transitory computer-readable media storing sequences of instructions, which, when executed by one or more processors, cause:

identifying, in a query execution plan compiled for a query, a plurality of target operators that includes an expression that computes a common value;

for a first target operator of the plurality of target operators, modifying a row output of the first target operator to add a column for an evaluation result comprising the common value;

for at least one second target operator of the plurality of target operators, modifying a row input of the second target operator to add a column for the evaluation result comprising the common value;

after modifying the row output for the first target operator and the row input for at least the second target operator, executing the query according to the plurality of target operators;

wherein during said executing, the evaluation result comprising the common value is shared by passing the evaluation result from the row output for the first target operator to the row input for the at least one second target operator.

13. The one or more non-transitory computer-readable media of claim 12, wherein the sequences of instructions further include instructions that, when executed by said one or more processors, cause:

pushing evaluation of the expression to a storage layer;

wherein the storage layer evaluates the expression that computes the common value during a table scan of stored data indicated by the expression;

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

14. The one or more non-transitory computer-readable media of claim 13, wherein the sequences of instructions further include instructions that, when executed by said one or more processors, cause the storage layer to return a set of rows that includes the evaluation result comprising the common value.

15. The one or more non-transitory computer-readable media of claim 12, wherein the expression is a hash expression that computes a common hash value on a common hash key.

16. The one or more 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 corresponding to the query execution plan to identify a first operator;

wherein the first 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 operator as a root to identify one or more additional target operators that also include an expression for computing the hash value on the particular hash key.

17. The one or more non-transitory computer-readable media of claim 12, further storing instructions that cause:

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

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

18. The one or more non-transitory computer-readable media of claim 12, further storing instructions that cause:

assigning responsibility for evaluating the expression to a single target operator of the plurality of target operators.

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

wherein the plurality of target operators includes different target operators;

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

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

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

20. The one or more non-transitory computer-readable media of claim 12, further storing instructions that cause:

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

wherein the first target operator and the second target operator are modified in response to determining that the number of target operators identified satisfies the threshold.

21. The one or more non-transitory computer-readable media of claim 12, 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.