Optimizing an order of execution of multiple join operations

Patent metadata

Field	Value
Publication number	US-10061804-B2
Application number	US-201715796980-A
Country	US
Kind code	B2
Filing date	Oct 30, 2017
Priority date	Dec 4, 2012
Publication date	Aug 28, 2018
Grant date	Aug 28, 2018

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. 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.

First claim

What is claimed is:

1. 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;
estimating, by one or more processors, cardinalities of sub-tables derived by a respective joining of a subset of rows of the first data column and a subset of rows of the second data column which are processed by a same 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 x 0 =a;
x n =b;
x i ∈[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;
U 1 i is a number of unique values of the first data column R in a respective interval i;
U 2 i 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
⁡

Assignees

• IBM

Inventors

• Grochowski Marek
• Gruszecki Artur M
• Kazalski Tomasz
• Milka Grzegorz S
• Skibski Konrad K
• Stradomski Tomasz

Classifications

• G06F16/24544 Primary

  Join order optimisation · CPC title

• G06F16/2453

  Query optimisation · CPC title

• G06F17/30466 Primary

  Physics · mapped topic

• G06F17/30442

  Physics · mapped topic