Load balancing for complex database query plans
First Claim
1. A computer-implemented method for parallelizing a database query plan, comprising:
- positioning, by a computer, a data flow exchange operator in a database query tree, wherein the exchange operator comprises a plurality of buffers, and wherein the exchange operator is configured to receive inputs from a plurality of parallel operators;
parallelizing, by the computer, a first child operator of the exchange operator into a plurality of parallel second child operators, each of the parallel second child operators coupled to the exchange operator in a respective branch of a plurality of parallel branches of the query tree;
wherein each branch of the parallel branches is configured to be processed by a respective processor thread;
wherein each of the plurality of second child operators has a first input, and wherein the parallelizing comprises;
partitioning an input of the first child operator into a plurality of first inputs; and
replacing the first child operator with the plurality of second child operators, each of the plurality of second child operators being positioned in a respective branch of the plurality of parallel branches and coupled to one of said plurality of first inputs; and
buffering, at the exchange operator, in respective ones of the plurality of buffers, an output of each of the plurality of parallel second child operators.
1 Assignment
0 Petitions
Accused Products
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.
41 Citations
28 Claims
-
1. A computer-implemented method for parallelizing a database query plan, comprising:
-
positioning, by a computer, a data flow exchange operator in a database query tree, wherein the exchange operator comprises a plurality of buffers, and wherein the exchange operator is configured to receive inputs from a plurality of parallel operators; parallelizing, by the computer, a first child operator of the exchange operator into a plurality of parallel second child operators, each of the parallel second child operators coupled to the exchange operator in a respective branch of a plurality of parallel branches of the query tree; wherein each branch of the parallel branches is configured to be processed by a respective processor thread; wherein each of the plurality of second child operators has a first input, and wherein the parallelizing comprises; partitioning an input of the first child operator into a plurality of first inputs; and replacing the first child operator with the plurality of second child operators, each of the plurality of second child operators being positioned in a respective branch of the plurality of parallel branches and coupled to one of said plurality of first inputs; and buffering, at the exchange operator, in respective ones of the plurality of buffers, an output of each of the plurality of parallel second child operators. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
13. A system comprising:
-
a processor; and a memory storing control logic, that when executed by the processor, causes the processor to generate a database query plan tree comprising; a data flow exchange operator comprising a plurality of buffers in the memory, wherein the exchange operator is configured to buffer received inputs from a plurality of parallel operators; 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, wherein each branch of the parallel branches is configured to be processed by a respective processor thread; wherein each of the plurality of parallel child operators has a first input, and wherein the data flow exchange operator is further configured to; partition the first input of each of the plurality of parallel child operators into a plurality of first inputs; and replace each of the plurality of parallel child operators with a plurality of child operators, each of the plurality of child operators being positioned in a respective branch of the plurality of parallel branches of the tree; wherein the exchange operator is further configured to store an output of each of the plurality of parallel child operators in respective ones of the plurality of buffers in memory. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24)
-
-
25. A computer program product comprising a computer-readable storage medium having computer readable program code stored thereon that, in response to execution by a processor, causes the processor to improve performance of a database query plan by performing operations comprising:
-
positioning a data flow exchange operator in a database query tree; 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, wherein each branch of the parallel branches is configured to be processed by a respective processor thread; wherein each of the plurality of parallel child operators has a first input, and wherein the parallelizing comprises; partitioning the first input of each of the child operators into a plurality of first inputs; and replacing the child operator with the plurality of child operators, each of the plurality of child operators being positioned in a respective branch of the plurality of parallel branches of the query tree; and buffering, in a plurality of buffers, an output of each of the plurality of parallel child operators at the exchange operator. - View Dependent Claims (26, 27, 28)
-
Specification