US 9,852,181 B2 · Optimizing an order of execution of multiple join operations

Abstract

A computer-implemented method, system, and/or computer program product optimizes an order of execution of column join operations. A first partitioning of the first data column splits the first data column into first subsets of rows. A second partitioning of the second data column splits the second data column into a second subsets of rows. A first value frequency information indicates a frequency of attribute values within a subset of rows of the first data column processed. A second value frequency information indicates a frequency of attribute values within a subset of rows of the second data column. Cardinalities of sub-tables derived by a respective joining of the subsets of rows of the first and second data columns are estimated, based on the first and second value frequency information. An order of execution of multiple join operations is then optimized based on the estimated cardinalities of the sub-tables.

A method for optimizing an order of execution of multiple join operations based on at least a first data column and a second data column in a database system having multiple processing units, the method comprising:

providing, by one or more processors, at least a first partitioning of the first data column, wherein said at least the first partitioning splits the first data column into a plurality of first subsets of rows, each of the first subsets of rows being correlated with a distinct processing unit from the multiple processing units, wherein each of the first subsets of rows are handled by processing units that differ from one another;
providing, by one or more processors, at least a second partitioning of the second data column, wherein said at least the second partitioning splits the second data column into a plurality of second subsets of rows, each of the second subsets of rows being correlated with a distinct processing unit from the multiple processing units, wherein each of the second subsets of rows are handled by processing units that differ from one another;
providing, by one or more processors, at least a first value frequency information for each processing unit from the multiple processing units, the first value frequency information indicating a frequency of attribute values within a subset of rows of the first data column processed by a respective processing unit from the multiple processing units;
providing, by one or more processors, at least a second value frequency information for each processing unit from the multiple processing units, the second value frequency information indicating a frequency of attribute values within a subset of rows of the second data column processed by the respective processing unit from the multiple processing units;
estimating, by one or more processors, cardinalities of sub-tables derived by a respective joining of the subset of rows of the first data column and the subset of rows of the second data column which are processed by a same processing unit from the multiple processing units, wherein estimated cardinalities of the sub-tables are based on the first and second value frequency information of the respective processing unit from the multiple processing units, wherein the cardinalities of the sub-tables describe a quantity of rows in the sub-tables, and wherein the cardinalities of the sub-tables derived by the respective joining of the subset of rows of the first data column and the subset of rows of the second data column are estimated according to:
F
⁡
(
a
,
b
)
=
∑
i
=
0
n
-
1
⁢
(
max
⁡
(
∫
x
i
x
i
+
1
⁢
f
⁡
(
x
)
⁢
dx
,
0
)
u
1
i
*
max
⁡
(
∫
x
i
x
i
+
1
⁢
g
⁡
(
x
)
⁢
dx
,
0
)
u
2
i
)
*
max
⁡
(
u
1
i
,
u
2
i
)
where x0=a;
xn=b;
x1ε[a,b];
f(x) is a density distribution function of a first data column R;
g(x) is a density distribution function of a second data column S;
a, b are a starting row and end row of respective columns R and S which are incorporated into a join;
u1i is a number of unique values of the first data column R in a respective interval i;
u2i is a number of unique values of the second data column S in the respective interval i;
F(a,b) is an estimated number of rows of a resulting joined table T by joining the first and second data columns R, S in an interval [a,b];
max
⁡
(
∫
x
i
x
i
+
1
⁢
f
⁡
(
x
)
⁢
⁢
ⅆ
x
,
0
)
u
1
i
represents an average number of rows per unique value in an [xi;xi+1]-section for the first data column R;
max
⁡
(
∫
x
i
x
i
+
1
⁢
g
⁡
(
x
)
⁢
⁢
ⅆ
x
,
0
)
u
2
i
represents an average number of rows per unique value in the [xi;xi+1]-section for the second data column S;
and
max (u1i, u2i) is used to derive a maximum value of numbers of unique values contained in [xi;xi+1]-sequences of the first and second data columns R, S;
and
optimizing, by one or more processors, an order of execution of multiple join operations based on the estimated cardinalities of the sub-tables, wherein optimizing the order of execution of the multiple join operations avoids intermediate data skew by joining sub-tables having quantities of rows that have a same value.

148 more elements

Optimizing an order of execution of multiple join operations

Life of this patent

Optimizing an order of execution of multiple join operations

Life of this patent

Abstract

Claims19