Load balancing for complex database query plans

• US 20080147599A1
• Filed: 12/18/2006
• Published: 06/19/2008
• Est. Priority Date: 12/18/2006
• Status: Active Grant

• Current Assignee: iAnywhere Solutions Incorporated (SAP SE)
• Original Assignee: iAnywhere Solutions Incorporated (SAP SE)
• Inventors: Young-Lai, Matthew
• Granted Patent: US 7,849,073 B2
• Time in Patent Office: Days
• US Class Current: 707/2
• CPC Class Codes: G06F 16/24532 of parallel queries

Abstract

Methods, systems, and apparatuses for improving performance of parallel database query plans are described. An exchange operator is positioned in a query tree. A child operator of the exchange operator is parallelized into a plurality of parallel child operators, each of the parallel child operators coupled to the exchange operator in a respective branch of a plurality of parallel branches of the query tree. An output of each of the plurality of parallel child operators may be buffered at the exchange operator. Furthermore, child operators of the plurality of parallel child operators may also be parallelized. Query plans of any form and containing any number of operators may be parallelized in this manner. Any number of parallel branches may be used, independent of the number of operators in the original plan. The parallelized query plans achieve effective load balancing across all branches.

Claims

1. A method for parallelizing a database query plan, comprising:

positioning an exchange operator in a query tree; and

parallelizing a child operator of the exchange operator into a plurality of parallel child operators, each of the parallel child operators coupled to the exchange operator in a respective branch of a plurality of parallel branches of the query tree.

2. The method of claim 1, further comprising:

buffering an output of each of the plurality of parallel child operators at the exchange operator.

3. The method of claim 1, wherein the child operator is a hash join operator, wherein said parallelizing comprises:

partitioning a first input to the hash join operator into a plurality of first inputs;

replacing the hash join operator with a plurality of hash join operators, each of the plurality of hash join operators being positioned in a respective branch of the plurality of parallel branches;

generating a plurality of hash tables, comprising the step of generating a hash table for each of the plurality of first inputs;

merging the plurality of hash tables into a combined hash table; and

configuring each of the plurality of hash join operators to probe the combined hash table with a corresponding second input.

4. The method of claim 1, wherein the child operator is a bloom filter operator having a corresponding bloom filter generator operator, wherein said parallelizing comprises:

partitioning an input to the bloom filter generator operator into a first plurality of inputs;

partitioning an input to the bloom filter operator into a second plurality of inputs;

replacing the bloom filter generator operator with a plurality of bloom filter generator operators, each of the plurality of bloom filter operators being positioned in a respective branch of the plurality of parallel branches;

configuring each of the plurality of bloom filter generator operators to receive a respective one of the first plurality of inputs and to operate on a common bit array;

replacing the bloom filter operator with a plurality of bloom filter operators, each of the plurality of bloom filter operators being positioned in a respective branch of the plurality of parallel branches; and

configuring each of the plurality of bloom filter operators to receive a respective one of the second plurality of inputs and to compare a generated array of positions with the common bit array.

5. The method of claim 1, wherein the child operator is a predicate filter operator, wherein said parallelizing comprises:

partitioning an input to the predicate filter generator operator into a plurality of inputs;

replacing the predicate filter operator with a plurality of predicate filter operators, each of the plurality of predicate filter operators being positioned in a respective branch of the plurality of parallel branches; and

configuring each of the plurality of predicate filter operators to receive a respective one of the plurality of inputs.

6. The method of claim 1, wherein the child operator is a nested loop join operator having a first input and a second input, wherein said parallelizing comprises:

partitioning the first input to the nested loop join operator into a plurality of first inputs;

replacing the nested loop join operator with a plurality of nested loop join operators, each of the plurality of nested loop join operators being positioned in a respective branch of the plurality of parallel branches; and

configuring each of the plurality of nested loop join operators to receive a respective one of the plurality of first inputs and to receive the second input.

7. The method of claim 1, wherein the child operator is a hash group by operator, wherein said parallelizing comprises:

partitioning an input to the hash group by operator into a plurality of inputs;

replacing the hash group by operator with a plurality of hash group by operators, wherein each of the plurality of hash group by operators is positioned in a respective branch of the plurality of parallel branches and receives a respective one of the plurality of inputs;

positioning an additional hash group by operator in the query tree; and

coupling an input to the additional hash group by operator to an output of the exchange operator.

8. The method of claim 1, wherein the first child operator of the exchange operator has a second child operator, further comprising:

parallelizing the second operator into a second plurality of child operators.

9. The method of claim 8, wherein the second child operator is a scan operator, wherein said parallelizing comprises:

replacing the scan operator with a plurality of scan operators, each of the plurality of scan operators being positioned in a respective branch of the plurality of parallel branches, and being coupled to an input of one of the first plurality of child operators.

10. The method of claim 9, further comprising:

configuring each of the plurality of scan operators to access a common table in a first-come first-serve manner.

11. The method of claim 10, further comprising:

configuring each of the plurality of scan operators to scan a page of data per access of the common table.

12. The method of claim 9, wherein each of the plurality of scan operators is configured to perform a table scan.

13. The method of claim 10, wherein each of the plurality of scan operator is configured to perform an index scan, further comprising:

configuring each of the plurality of scan operators to scan a leaf page of data per access of the common database.

14. A database query plan tree, comprising:

an exchange operator; and

a plurality of parallel child operators, each of the parallel child operators coupled to a respective input of the exchange operator in a respective branch of a plurality of parallel branches of the tree.

15. The database query plan tree of claim 14, wherein the exchange operator comprises a buffer for each of the plurality of parallel child operators.

16. The database query plan tree of claim 14, wherein each of the parallel child operators is a hash join operator, further comprising:

a combined hash table that is a merge of a plurality of hash tables, wherein the plurality of hash tables includes a hash join operator generated for each hash join operator from a first input of each hash join operator;

wherein each of the hash join operators is configured to probe the combined hash table with a corresponding second input.

17. The database query plan tree of claim 14, wherein each of the parallel child operators is a bloom filter operator, wherein each bloom filter operator is positioned in a respective branch of the plurality of parallel branches;

wherein each bloom filter operator is configured to generated array of positions from an input, and to compare the generated array of positions with a common bit array.

18. The database query plan tree of claim 14, wherein each of the parallel child operators is a predicate filter operator.

19. The database query plan tree of claim 14, wherein each of the parallel child operators is a nested loop join operator having a first input and a second input, wherein the first input of each nested loop join operator is coupled to a different child operator, wherein the second input of each nested loop join operator is coupled to a common child operator.

20. The database query plan tree of claim 14, wherein each of the parallel child operators is a hash group by operator, further comprising:

an additional hash group by operator coupled to an output of the exchange operator.

21. The database query plan tree of claim 14, further comprising:

a second plurality of parallel child operators, wherein each child operator of the second plurality of parallel child operators is coupled to an input of a respective one of the first plurality of parallel child operators.

22. The database query plan tree of claim 21, wherein each child operator of the second plurality of child operators is a scan operator.

23. The database query plan tree of claim 22, wherein each scan operator is configured to access a common database in a first-come first-serve manner.

24. The database query plan tree of claim 23, wherein each scan operator is configured to scan a page of data per access of the common database.

25. The database query plan tree of claim 24, wherein each scan operator is configured to perform a table scan.

26. The database query plan tree of claim 23, wherein each scan operator is configured to perform an index scan;

wherein each scan operator is configured to scan a leaf page of data per access of the common database.

27. The database query plan tree of claim 23, wherein each branch of the parallel branches is configured to be processed by a respective processor thread.

28. A computer program product comprising a computer usable medium having computer readable program code means embodied in said medium for improving performance of a database query plan, said computer readable program code means comprising:

computer readable program code means for enabling a processor to position an exchange operator in a query tree; and

computer readable program code means for enabling a processor to parallelize a child operator of the exchange operator into a plurality of parallel child operators, each of the parallel child operators coupled to the exchange operator in a respective branch of a plurality of parallel branches of the query tree.