Data skew insensitive parallel join scheme
AssigneeHewlett-Packard Development Company, L.P.
InventorsAwny K. Al-Omari, QiFan Chen, Gregory S. Battas, Kashif A. Siddiqui, Michael J. Hanlon
Life of this patent
Estimating the term…
Abstract
A method for creating a joined data set from a join input data set is disclosed. The method starts by categorizing the join input data set into a high-skew data set and a low-skew data set. The low-skew data set is distributed to the plurality of CPUs using a first distribution method. The high-skew data set is distributed to the plurality of CPUs using a second distribution method. The plurality of CPUs process the high-skew data set and the low-skew data set to create the joined data set.
Claims15
A data-processing system comprising:
- a hardware platform that includes two or more processors;
- and
- a database-management system that executes a join operation, carried out on two tables R and S that each has rows with one or more join-attribute values, on the two or more processors by on each processor,
- executing a first portion of the join operation by joining a first subset of the rows of table R, the join-attribute-value distribution of which is skewed above a skew threshold and which have been distributed among the two or more processors by a first distribution method, with a first subset of the rows of table S;
- and
- executing a second portion of the join operation by joining a second subset of the rows of table R, the join-attribute-value distribution of which is not skewed or is skewed below a threshold value and which have been distributed among the two or more processors by a second distribution method, with a second subset of the rows of table S;
- in which the skew threshold is determined by dividing an operator cardinality by the number of processors used during the join operations, deriving a quotient there from, and multiplying the derived quotient by an adjustment factor.
A database-management system, encoded as computer instructions in a non-transitory computer-readable medium, that that executes a join operation, carried out on two tables R and S that each has rows with one or more join-attribute values, on the two or more processors by:
- joining a first subset of the rows of table R, the join-attribute-value distribution of which is skewed above a skew threshold and which have been distributed among the two or more processors by a first distribution method, with a first subset of the rows of table S;
- and
- joining a second subset of the rows of table R, the join-attribute-value distribution of which is not skewed or is skewed below a threshold value and which have been distributed among the two or more processors by a second distribution method, with a second subset of the rows of table S;
- in which the skew threshold is determined by dividing an operator cardinality by the number of processors used during the join operations, deriving a quotient there from, and multiplying the derived quotient by an adjustment factor.
In a computing system having a plurality of interconnected central processing units (CPUs) and a memory storing a join input data set, a method for creating a joined data set, the steps of the method comprising:
- categorizing the join input data set into a high-skew data set and a low-skew data set during a query optimization phase;
- at query execution time, distributing the low-skew data set to the plurality of CPUs using a first distribution method;
- at query execution time, distributing the high-skew data set to the plurality of CPUs using a second distribution method wherein the first distribution method is different from the second distribution method;
- and
- wherein the plurality of CPUs process the high-skew data set and the low-skew data set to create the joined data set:
- wherein the high-skew data set is categorized by comparing an occurrence frequency of a join column value to a threshold value;
- and
- wherein a skew threshold is used to determine if an input data set is categorized as a high-skew data set, the skew threshold being determined by dividing an operator cardinality by the number of processors used during the join operations, deriving a quotient there from, and multiplying the derived quotient by an adjustment factor.
Dependencies are inferred from the claim text.