Dynamic partition selection

Patent metadata

Field	Value
Publication number	US-9652496-B1
Application number	US-201414314863-A
Country	US
Kind code	B1
Filing date	Jun 25, 2014
Priority date	Jun 25, 2014
Publication date	May 16, 2017
Grant date	May 16, 2017

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.

First claim

What is claimed is:

1. 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 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;
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, including:
determining, for each operator of a subset of operators in the query plan, whether the dynamic scan operator occurs in a subtree of the query plan that is rooted at the respective operator of the subset of operators; and
determining, using results of the determinations of whether the dynamic scan operator occurs in a subtree of the query plan that is rooted at the respective operator of the subset of operators, a first operator in the query plan that is i) a parent operator of the partition selector operator and the dynamic scan operator or ii) a child operator of the partition selector operator;
determining, using the first operator, the location in the query plan for the partition selector 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 method 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.

3. The method of claim 1 , wherein determining a location in the query plan for the partition selector operator comprises:
determining that the dynamic scan operator does not occur in a subtree rooted at a particular operator; and
in response to determining that the dynamic scan operator does not occur in a subtree rooted at the particular operator, adding the partition selector operator as a parent operator of the particular operator in the query plan.

4. The method of claim 1 , further comprising:
determining that the dynamic scan operator occurs in a subtree rooted at a particular operator; and
in response to determining that the dynamic scan operator occurs in a subtree rooted at the particular operator, pushing the partition selector operator to a child operator of the particular operator.

5. The method of claim 4 , wherein pushing the partition selector operator to a child operator of the particular operator comprises recursively calling a partition location function for the child operator.

6. The method of claim 4 , wherein the particular operator is a join operator that computes pairs of first tuples of a first table and second tuples of the table that have matching values.

7. The method of claim 6 , further comprising:
determining that the dynamic scan operator is defined in an outer subtree of the join operator; and
in response to determining that the dynamic scan operator is defined in an outer subtree of the join operator, pushing the partition selector operator to an outer child operator of the join operator.

8. The method of claim 6 , further comprising:
determining that the partition selector operator includes a predicate expression on a partitioning key; and
in response to determining that the partition selector operator includes a predicate expression on a partitioning key, pushing the partition selector operator to an outer child operator of the join operator.

9. The method of claim 6 , further comprising:
determining that the partition selector operator does not include a predicate expression on a partitioning key; and
in response determining that the partition selector operator does not include a predicate expression on a partitioning key, pushing the partition selector operator to an inner child operator of the join operator.

10. The method of claim 4 , wherein the particular operator is a select operator that requests, from the table, one or more tuples having respective values according to a first predicate expression in a query, and
wherein pushing the partition selector operator to a child operator of the particular operator comprises appending the first predicate expression to the partition selector operator,
wherein appending the first predicate expression to the partition selector operator causes a particular computing node to determine, from the first predicate expression and a partition selection function, one or more partitions of the table that may include tuples having respective values that satisfy the first predicate expression.

11. The method of claim 10 , wherein the table is a multilevel partitioned table,
wherein the first predicate expression references a first partitioning key of the table, wherein the query includes a second predicate expression on a second partitioning key of the table, and wherein the particular computing node determines, by providing the first predicate expression and the second predicate expression as input to the partition selection function, one or more partitions of the table that may include tuples having respective values that satisfy the first predicate expression and the second predicate expression.

12. The method of claim 10 , wherein appending the first predicate expression to the partition selector operator comprises:
receiving a second predicate expression of the partition selector operator; and
computing a combined predicate expression, the combined predicate expression comprising a conjunction of the first predicate expression with the second predicate expression, wherein the particular computing node determines, from the combined predicate expression and the partition selection function, one or more partitions of the table that may include tuples having respective values that satisfy the combined predicate expression.

13. A system comprising:
one or more first computers and one or more first storage devices storing instructions that are operable, when executed by the one or more first computers, to cause the one or more first computers to implement a select operator node that is operable to request, from a first table, one or more tuples having respective values according to a predicate expression in a query;
one or more second computers and one or more second storage devices storing instructions that are operable, when executed by the one or more second computers, to cause the one or more second computers to implement a partition selector node that is operable to determine, from the predicate expression in the query according to a partition selection function, one or more partitions of a table that may include tuples having respective values

Assignees

• Pivotal Software Inc

Inventors

• Antova Lyublena Rosenova
• El-Helw Amr
• Soliman Mohamed Y
• Gu Zhongxian
• Petropoulos Michail
• Waas Florian Michael

Classifications

• G06F16/24537

  of operators · CPC title

• G06F16/27

  Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor · CPC title

• G06F16/24544 Primary

  Join order optimisation · CPC title

• G06F16/284

  Relational databases · CPC title

• G06F16/9024

  Graphs; Linked lists (G06F16/9027 takes precedence) · CPC title