Dynamic partition selection

• US 10,521,428 B1
• Filed: 04/17/2017
• Issued: 12/31/2019
• Est. Priority Date: 06/25/2014
• Status: Active Grant

• Current Assignee: Pivotal Software, Inc. (Broadcom, Inc.)
• Original Assignee: Pivotal Software, Inc. (Broadcom, Inc.)
• Inventors: Antova, Lyublena Rosenova, El-Helw, Amr, Soliman, Mohamed F., Gu, Zhongxian, Petropoulos, Michail, Waas, Florian Michael
• Primary Examiner(s): Vital, Pierre M
• Assistant Examiner(s): Antoine, Alicia M
• Application Number:
  US15/488,890
• Time in Patent Office: 988 Days
• Field of Search: 707714
• CPC Class Codes: G06F 16/24537 of operators
• CPC Class Codes: G06F 16/24542 Plan optimisation
• CPC Class Codes: G06F 16/24544 Join order optimisation
• CPC Class Codes: G06F 16/24554 Unary operations; Data partitioning operations
• CPC Class Codes: G06F 16/2456 Join operations
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 16/284 Relational databases
• CPC Class Codes: G06F 16/9024 Graphs; Linked lists G06F16/9027 takes precedence
• CPC Class Codes: G06F 16/9027 Trees

Abstract

Methods, systems, and apparatus, including computer programs encoded on computer storage media, for dynamic partition selection. One of the methods includes receiving a representation of a query plan generated for a query, wherein the query plan includes a dynamic scan operator that represents a first computing node obtaining tuples of one or more partitions of a table from storage and transferring the tuples to a second computing node that executes a parent operator of the dynamic scan operator. A partition selector operator is generated corresponding to the dynamic scan operator. A location in the query plan is determined for the partition selector operator. A modified query plan is generated having the partition selector operator at the determined location.

Claims

1. A system comprising one or more computers and one or more storage devices storing instructions that are operable, when executed by the one or more computers, to perform operations comprising:

receiving a representation of a query plan generated for a query, the query plan comprising a first plurality of operators that, when executed by one or more computing nodes, cause the one or more computing nodes to compute a result for the query, wherein the query plan includes a join operator and a dynamic scan operator, wherein the dynamic scan operator represents a first computing node obtaining tuples from a table that is partitioned into a plurality of partitions by a partitioning key and transferring the tuples to a second computing node that executes a parent operator of the dynamic scan operator, and the join operator represents a third computing node computing a join operation by comparing first tuples generated by an outer child operator of the join operator to second tuples generated by an inner child operator of the join operator to determine pairs of first tuples and second tuples that have matching attribute values;

generating a partition selector operator corresponding to the dynamic scan operator, wherein the partition selector operator represents a fourth computing node that executes the partition selector operator including determining one or more partition identifiers of partitions of the table and transferring the one or more partition identifiers to the dynamic scan operator of the first computing node;

determining a location in the query plan for the partition selector operator relative to the join operator, including;

determining that the dynamic scan operator is defined in a subtree of the outer child operator of the join operator; and

pushing the partition selector operator to the outer child operator of the join operator in response to determining that the dynamic scan operator is defined in a subtree of the outer child operator of the join operator; and

generating a modified query plan having the partition selector operator at the determined location, wherein the modified query plan includes a second plurality of operators that, when executed by one or more computing nodes, cause the one or more computing nodes to compute a result for the query.

2. The system of claim 1, the operations comprising:

determining that the dynamic scan operator is not defined in the subtree of the outer child operator of the join operator; and

in response to determining that the dynamic scan operator is not defined in in the subtree of the outer child operator of the join operator, determining whether the join operator includes a predicate expression on a partitioning key; and

determining the location in the query plan for the partition selector operator using a result of the determination whether the join operator includes a predicate expression on a partitioning key.

3. The system of claim 2, the operations comprising:

determining that the join operator does not include a predicate expression on a partitioning key; and

in response to determining that the join operator does not include a predicate expression on a partitioning key, pushing the partition selector operator to a subtree of an inner child operator of the join operator.

4. The system of claim 2, the operations comprising:

determining that the join operator includes a predicate expression on a partitioning key; and

in response to determining that the join operator includes a predicate expression on a partitioning key;

annotating the partition selector operator with the predicate expression from the join operator; and

pushing the partition selector operator to a subtree of the outer child operator of the join operator.

5. The system of claim 4, wherein:

the partition selector operator comprises one or more second predicate expressions; and

annotating the partition selector operator with the predicate expression from the join operator comprises annotating the partition selector operator with a conjunction of the predicate expression from the join operator and the one or more second predicate expressions.

6. The system of claim 5, wherein:

the table is a multilevel partitioned table with multiple partitioning keys including the partitioning key; and

annotating the partition selector operator with a conjunction of the predicate expression from the join operator and the one or more second predicate expressions comprises;

generating, for each partitioning key in the multiple partitioning keys, a set of predicate expressions by computing a conjunction of the predicate expression from the join operator and the one or more second predicate expressions; and

associating, for each partitioning key in the multiple partitioning keys, the partition selector operator with a set of sets of predicate expressions, each set corresponding to a different partitioning key of the multiple partitioning keys.

7. The system of claim 1, wherein the query plan is represented as a graph, wherein each operator in the query plan is a node in the graph, and wherein each edge between a first graph node and a second graph node in the graph represents a first computing node, that executes a first operator represented by the first graph node, transferring output of the first operator to a second computing node that executes a second operator represented by the second graph node.

8. A computer-implemented method comprising:

receiving a representation of a query plan generated for a query, the query plan comprising a first plurality of operators that, when executed by one or more computing nodes, cause the one or more computing nodes to compute a result for the query, wherein the query plan includes a join operator and a dynamic scan operator, wherein the dynamic scan operator represents a first computing node obtaining tuples from a table that is partitioned into a plurality of partitions by a partitioning key and transferring the tuples to a second computing node that executes a parent operator of the dynamic scan operator, and the join operator represents a third computing node computing a join operation by comparing first tuples generated by an outer child operator of the join operator to second tuples generated by an inner child operator of the join operator to determine pairs of first tuples and second tuples that have matching attribute values;

generating a partition selector operator corresponding to the dynamic scan operator, wherein the partition selector operator represents a third computing node that executes the partition selector operator including determining one or more partition identifiers of partitions of the table and transferring the one or more partition identifiers to the dynamic scan operator of the first computing node;

determining a location in the query plan for the partition selector operator relative to the join operator, including;

determining that the join operator includes a predicate expression on a partitioning key;

in response to determining that the join operator includes a predicate expression on a partitioning key, annotating the partition selector operator with the predicate expression from the join operator; and

pushing the partition selector operator to a subtree of an outer child operator of the join operator; and

generating a modified query plan having the annotated partition selector operator at the determined location, wherein the modified query plan includes a second plurality of operators that, when executed by one or more computing nodes, cause the one or more computing nodes to compute a result for the query.

9. The method of claim 8, comprising:

determining that the dynamic scan operator is not defined in the subtree of the outer child operator of the join operator; and

in response to determining that the dynamic scan operator is not defined in in the subtree of the outer child operator of the join operator, determining whether the join operator includes a predicate expression on the partitioning key, wherein determining that the join operator includes a predicate expression on the partitioning key is responsive to determining whether the join operator includes a predicate expression on the partitioning key.

10. The method of claim 8, wherein:

the partition selector operator comprises one or more second predicate expressions; and

annotating the partition selector operator with the predicate expression from the join operator comprises annotating the partition selector operator with a conjunction of the predicate expression from the join operator and the one or more second predicate expressions.

11. The method of claim 10, wherein:

the table is a multilevel partitioned table with multiple partitioning keys including the partitioning key; and

annotating the partition selector operator with a conjunction of the predicate expression from the join operator and the one or more second predicate expressions comprises;

generating, for each partitioning key in the multiple partitioning keys, a set of predicate expressions by computing a conjunction of the predicate expression from the join operator and the one or more second predicate expressions; and

associating, for each partitioning key in the multiple partitioning keys, the partition selector operator with a set of sets of predicate expressions, each set corresponding to a different partitioning key of the multiple partitioning keys.

12. The method of claim 8, wherein the query plan is represented as a graph, wherein each operator in the query plan is a node in the graph, and wherein each edge between a first graph node and a second graph node in the graph represents a first computing node, that executes a first operator represented by the first graph node, transferring output of the first operator to a second computing node that executes a second operator represented by the second graph node.

13. The method of claim 8, wherein the query plan includes a second join operator and a second dynamic scan operator, wherein the second dynamic scan operator represents a fifth computing node obtaining tuples from a table that is partitioned into a plurality of partitions by a second partitioning key and transferring the tuples to a sixth computing node that executes a parent operator of the second dynamic scan operator, and the second join operator represents a seventh computing node computing a join operation by comparing first tuples generated by an outer child operator of the second join operator to second tuples generated by an inner child operator of the second join operator to determine pairs of first tuples and second tuples that have matching attribute values, the method comprising:

generating a second partition selector operator corresponding to the second dynamic scan operator, wherein the second partition selector operator represents an eighth computing node that executes the second partition selector operator including determining one or more partition identifiers of partitions of the table and transferring the one or more partition identifiers to the second dynamic scan operator of the fifth computing node;

determining a second location in the query plan for the second partition selector operator relative to the second join operator, including;

determining that the second dynamic scan operator is defined in a subtree of the outer child operator of the second join operator; and

pushing the second partition selector operator to the outer child operator of the second join operator in response to determining that the second dynamic scan operator is defined in a subtree of the outer child operator of the second join operator; and

generating a modified query plan having the second partition selector operator at the determined location, wherein the modified query plan includes a second plurality of operators that, when executed by one or more computing nodes, cause the one or more computing nodes to compute a result for the query.

14. A computer program product, encoded on one or more non-transitory computer storage media, comprising instructions that when executed by one or more computers cause the one or more computers to perform operations comprising:

receiving a representation of a query plan generated for a query, the query plan comprising a first plurality of operators that, when executed by one or more computing nodes, cause the one or more computing nodes to compute a result for the query, wherein the query plan includes a join operator and a dynamic scan operator, wherein the dynamic scan operator represents a first computing node obtaining tuples from a table that is partitioned into a plurality of partitions by a partitioning key and transferring the tuples to a second computing node that executes a parent operator of the dynamic scan operator, and the join operator represents a third computing node computing a join operation by comparing first tuples generated by an outer child operator of the join operator to second tuples generated by an inner child operator of the join operator to determine pairs of first tuples and second tuples that have matching attribute values;

generating a partition selector operator corresponding to the dynamic scan operator, wherein the partition selector operator represents a fourth computing node that executes the partition selector operator including determining one or more partition identifiers of partitions of the table and transferring the one or more partition identifiers to the dynamic scan operator of the first computing node;

determining a location in the query plan for the partition selector operator relative to the join operator, including;

determining that the dynamic scan operator is defined in a subtree of the outer child operator of the join operator; and

pushing the partition selector operator to the outer child operator of the join operator in response to determining that the dynamic scan operator is defined in a subtree of the outer child operator of the join operator; and

generating a modified query plan having the partition selector operator at the determined location, wherein the modified query plan includes a second plurality of operators that, when executed by one or more computing nodes, cause the one or more computing nodes to compute a result for the query.

15. The computer program product of claim 14, the operations comprising:

determining that the dynamic scan operator is not defined in the subtree of the outer child operator of the join operator; and

in response to determining that the dynamic scan operator is not defined in in the subtree of the outer child operator of the join operator, determining whether the join operator includes a predicate expression on a partitioning key; and

determining the location in the query plan for the partition selector operator using a result of the determination whether the join operator includes a predicate expression on a partitioning key.

16. The computer program product of claim 15, the operations comprising:

determining that the join operator does not include a predicate expression on a partitioning key; and

in response to determining that the join operator does not include a predicate expression on a partitioning key, pushing the partition selector operator to a subtree of an inner child operator of the join operator.

17. The computer program product of claim 15, the operations comprising:

determining that the join operator includes a predicate expression on a partitioning key; and

in response to determining that the join operator includes a predicate expression on a partitioning key;

annotating the partition selector operator with the predicate expression from the join operator; and

pushing the partition selector operator to a subtree of the outer child operator of the join operator.

18. The computer program product of claim 17, wherein:

the partition selector operator comprises one or more second predicate expressions; and

annotating the partition selector operator with the predicate expression from the join operator comprises annotating the partition selector operator with a conjunction of the predicate expression from the join operator and the one or more second predicate expressions.

19. The computer program product of claim 18, wherein:

the table is a multilevel partitioned table with multiple partitioning keys including the partitioning key; and

annotating the partition selector operator with a conjunction of the predicate expression from the join operator and the one or more second predicate expressions comprises;

generating, for each partitioning key in the multiple partitioning keys, a set of predicate expressions by computing a conjunction of the predicate expression from the join operator and the one or more second predicate expressions; and

associating, for each partitioning key in the multiple partitioning keys, the partition selector operator with a set of sets of predicate expressions, each set corresponding to a different partitioning key of the multiple partitioning keys.

20. The computer program product of claim 14, wherein the query plan is represented as a graph, wherein each operator in the query plan is a node in the graph, and wherein each edge between a first graph node and a second graph node in the graph represents a first computing node, that executes a first operator represented by the first graph node, transferring output of the first operator to a second computing node that executes a second operator represented by the second graph node.