US 10,592,531 B2Granted

Efficient partitioning of relational data

AssigneeOracle International Corporation

InventorsNegar Koochakzadeh, Nitin Kunal, Sam Idicula, Cagri Balkesen, Nipun Agarwal

Life of this patent

Estimating the term…

Loading patent…

Abstract

Techniques for non-power-of-two partitioning of a data set as well as generation and selection of partition schemes for the data set. In an embodiment, one or more iterations of a partition scheme is for a non-power-of-two number of partitions. Extended hash partitioning may be used to partition a data set into a non-power-of-two number of partitions by determining the partition identifier of each tuple of the data set using the extended hash partitioning algorithm. In an embodiment, multiple partition schemes are generated for multiple data sets, based on properties of the data sets and/or availability of computing resources for the partition operation or the subsequent operation to the partition operation. The generated partition schemes may use non-power-of-two partitioning for one or more iterations of a generated partition scheme. The most optimal partition scheme may be selected from the generated partition schemes based on optimization policies.

Claims24

Dependent claims

A computer-implemented method comprising:

determining an appropriate partition scheme for a partition operation to partition a first data set from a database among a cluster of nodes, determining the appropriate partition scheme comprising:
based on a size of a buffer allocated for the partition operation in a respective memory associated with each of a plurality of processing units of the cluster of nodes and based on a particular tuple size of the first data set, determining a per-iteration maximum number of partitions for the first data set that fit in the respective memory of said each of the plurality of processing units for distributing tuples of the first data set in an iteration of the partition operation;
determining a target number of partitions to be produced as a result of the partition operation on the first data set;
based on the per-iteration maximum number of partitions for the first data set and the target number of partitions, generating a set of two or more partition schemes, wherein each partition scheme of the set of partition schemes specifies, for each iteration of said each partition scheme, a respective number of partitions to distribute tuples of the first data set;
wherein at least one iteration in at least one partition scheme of the set of partition schemes specifies a non-power-of-two number of partitions into which to distribute tuples of the first data set;
evaluating said each partition scheme of the set of partition schemes based on one or more optimization policies;
and
based on evaluating said each partition scheme of the set of partition schemes based on the one or more optimization policies, selecting a particular partition scheme from the set of partition schemes as the appropriate partition scheme for partitioning the first data set by the partition operation;
and
performing the partition operation according to the selected particular partition scheme to generate and store a plurality of partitions for the first data set.

7 more elements

One or more non-transitory computer-readable media storing a set of instructions, wherein the set of instructions includes instructions, which when executed by one or more hardware processors, cause:

determining an appropriate partition scheme for a partition operation to partition a first data set from a database among a cluster of nodes, determining the appropriate partition scheme comprising:
based on a size of a buffer allocated for the partition operation in a respective memory associated with each of a plurality of processing units of the cluster of nodes and based on a particular tuple size of the first data set, determining a per-iteration maximum number of partitions for the first data set that fit in the respective memory of said each of the plurality of processing units for distributing tuples of the first data set in an iteration of the partition operation;
determining a target number of partitions to be produced as a result of the partition operation on the first data set;
based on the per-iteration maximum number of partitions for the first data set and the target number of partitions, generating a set of two or more partition schemes, wherein each partition scheme of the set of partition schemes specifies, for each iteration of said each partition scheme, a respective number of partitions to distribute tuples of the first data set;
wherein at least one iteration in at least one partition scheme of the set of partition schemes specifies a non-power-of-two number of partitions into which to distribute tuples of the first data set;
evaluating said each partition scheme of the set of partition schemes based on one or more optimization policies;
and
based on evaluating said each partition scheme of the set of partition schemes based on the one or more optimization policies, selecting a particular partition scheme from the set of partition schemes as the appropriate partition scheme for partitioning the first data set using the partition operation;
and
performing the partition operation according to the selected particular partition scheme to generate and store a plurality of partitions for the first data set.

7 more elements

Dependencies are inferred from the claim text.