Dynamic reordering of operations in a query plan

Patent metadata

Field	Value
Publication number	US-9594804-B2
Application number	US-201113218898-A
Country	US
Kind code	B2
Filing date	Aug 26, 2011
Priority date	Aug 26, 2011
Publication date	Mar 14, 2017
Grant date	Mar 14, 2017

Abstract

There is provided a computer-implemented method of dynamically reordering operations in a query plan. An exemplary method comprises processing a first set of tuples according to a first operation. The query plan is pipelined and specifies that the first operation generates input for a second operation. The query plan further specifies that the second operation is executed after the first operation. The computer-implemented method further includes determining that the second operation is to precede the first operation based on a specified policy. The computer-implemented method further includes executing the second operation for a second set of tuples before executing the first operation for the second set of tuples. The second operation generates an input for the first operation. The first operation is executed after the second operation.

First claim

What is claimed is:

1. A computer-implemented method of dynamically reordering operations in a query plan, comprising:
processing a first set of tuples according to a first operation supported by a first sort key, wherein the query plan specifies that the first operation generates input for a second operation supported by a second sort key, the second operation is executed after the first operation, and the query plan is pipelined; and
determining that the second sort key is index supported and that the first sort key is not index supported, and based on the determining:
resequencing the first operation and the second operation so that the second operation is to precede the first operation; and
executing the second operation for a second set of tuples before executing the first operation for the second set of tuples, wherein the second operation generates an input for the first operation.

2. The method recited in claim 1 , comprising:
processing a third set of tuples according to the second operation;
determining that the first operation is to precede the second operation based on the specified policy; and
executing the first operation for a fourth set of tuples before executing the second operation for the fourth set of tuples, wherein the first operation generates the input for the second operation.

3. The method recited in claim 1 , comprising:
determining that a third operation is to precede the first operation based on the specified policy, wherein the query plan specifies that the third operation is executed after the second operation; and
executing the third operation for the second set of tuples before executing the first operation for the second set of tuples, wherein the third operation generates the input for the first operation.

4. The method recited in claim 1 , wherein the first operation and the second operation comprise corresponding sort-based algorithms, and wherein the first set of tuples and the second set of tuples comprise a value packet.

5. The method recited in claim 1 , wherein the first operation and the second operation comprise a hash function on a shared set of attributes, and wherein the first set of tuples shares a first partition, and wherein the second set of tuples shares a second partition.

6. The method recited in claim 1 , wherein the first operation and the second operation comprise a sorted scan of an order-preserving data structure.

7. The method recited in claim 6 , wherein the order-preserving data structure comprises a B-tree index.

8. The method recited in claim 1 , wherein the first operation and the second operation are implemented using one of the following algorithms:
merge join;
generalized join;
generalized aggregation; or
a user-defined function.

9. A computer system for executing a query plan, the computer system comprising:
a processor that is adapted to execute stored instructions; and
a memory device that stores instructions, the memory device comprising:
computer-implemented code adapted to process a first set of tuples according to a first operation supported by a first sort key, wherein the query plan specifies that the first operation generates input for a second operation supported by a second sort key, the second operation is executed after the first operation, and the query plan is pipelined;
computer-implemented code adapted to determine that the second sort key is index supported and the first sort key is not index supported and, based on the determining, resequence the first operation and the second operation so that the second operation is to precede the first operation; and
computer-implemented code adapted to execute the second operation for a second set of tuples before executing the first operation for the second set of tuples in response to determining that the second operation is to precede the first operation, wherein the second operation generates an input for the first operation.

10. The computer system recited in claim 9 , wherein the memory device comprises:
computer-implemented code adapted to determine that a third operation is to precede the first operation based on the specified policy, wherein the query plan specifies that the third operation is executed after the second operation; and
computer-implemented code adapted to execute the third operation for the second set of tuples before executing the first operation for the second set of tuples, wherein the third operation generates the input for the first operation.

11. The computer system recited in claim 9 , wherein the first operation and the second operation comprise corresponding sort-based algorithms, and wherein the first set of tuples and the second set of tuples comprise a value packet.

12. The computer system recited in claim 9 , wherein the first operation and the second operation comprise a hash function on a shared set of attributes, and wherein the first set of tuples shares a first partition, and wherein the second set of tuples shares a second partition.

13. The computer system recited in claim 9 , wherein the first operation and the second operation comprise a sorted scan of an order-preserving data structure.

14. The computer system recited in claim 13 , wherein the order-preserving data structure comprises a B-tree index.

15. The computer system recited in claim 9 , wherein the first operation and the second operation are implemented using one of the following algorithms:
merge join;
generalized join; or
generalized aggregation.

16. A tangible, non-transitory, machine-readable medium that stores machine-readable instructions executable by a processor to execute a query plan, the tangible, non-transitory, machine-readable medium comprising:
machine-readable instructions that, when executed by the processor, process a first set of tuples according to a first operation supported by a first sort key, wherein the query plan specifies that the first operation generates input for a second operation supported by a second sort key, the second operation is executed after the first operation, and the query plan is pipelined;
machine-readable instructions that, when executed by the processor, determine that the second sort key is index supported and the first sort key is not index supported and, based on the determining, resequence the first operation and the second operation so that the second operation is to precede the first operation; and
machine-readable instructions that, when executed by the processor, execute the second operation for a second set of tuples before executing the first operation for the second set of tuples wherein the second operation generates an input for the first operation.

17. The tangible, non-transitory, machine-readable medium recited in claim 16 , comprising:
machine-readable instructions that, when executed by the processor, determine that a third operation is to precede the first operation based on the specified policy, wherein the query plan specifies that the third operation is executed after the second operation; and
machine-readable instructions that, when executed by the processor, execute the third operation for the second set of tuples before executing the first operation for the second set of tuples, wherein the third operation generates the input for the first operation.

Assignees

• Graefe Goetz
• Hewlett Packard Entpr Dev Lp

Inventors

• Graefe Goetz

Classifications

• G06F16/24542 Primary

  Plan optimisation · CPC title

• G06F17/30463 Primary

  Physics · mapped topic