AdvancedAd
dQ
Query O
Optimization
i iiTechniques in a Parallel Computing
Environment(Parallelizing Query Optimization)
Wook-Shin Han*,, Wooseongg Kwak,, Jinsoo Lee
Guy M. Lohman, Volker Markl
Kyungpook National University
IBM Almaden Research Center
12Introduction to Our Recent
Research Efforts• Query Optimization– Progressive optimization in a shared-nothing parallel database(SIGMOD 2007)– Parallelizing
Pll li i query optimization
ti i ti (VLDB 2008)• Time-series Database & Ranking– Ranked Subsequence Matching (VLDB 2007)• XML Query Processing– StreamTX: Extracting Tuples from Streaming XML Data (VLDB2008)– Mapping-driven XML transformation (WWW 2007)– The Dynamic
Dynam c Predicate:
Pred cate Integrating
Integrat ng Access Control withw th Query
Processing in XML Databases (VLDB Journal 2007)• Moving Object Databases– Cost-BasedC t B
dP
Predictive
di ti S
Spatio-Temporalti Tl Join
J i (IEEE TKDE 2008(accepted))3

Myy Necessary
y conditions for yyour papers
p p
to be accepted in SIGMOD/VLDB/ICDE

COND1) Solve
S l REAL problems
bl– This gives a very strong motivation!

COND2) Solve a SMALL but NOVEL problem– Your paper must be focused and distinguishable!

COND3)D ) DoD NOT BLAME
BE reviewers– Your faults, not reviewers’!
– DoD not ignore theirheven seeminglyl absurdb d (usually,(llonly to you!) reviews!
4

Success of Relational Database
Management Systems• Standardization
d doff theh SQL query llanguage
pof sophisticatedpqueryqy• Development
optimizers– Enumerate manyy alternative queryqy execution plansp(QEPs) using dynamic programming (DP)– Estimate the cost of each
– Choose the least expensive plan to execute5Motivation• As # off joins increases, # off alternativel
QEPs considered by DP grow exponentially• Although approximate search algorithms
reduce the enumeration time, this can resultin subsub-optimal
optimal plans

6*Motivation (Cont(Cont’d)d)• NewN
wave off multi-corelprocessors• Thus,Thiti isi obvious
b ito speed
d up CPU-boundCPU bdquery optimization by parallelizing it!
• In the typical parallel DBMS, only a single
coordinator node optimizes
pthe qquery!
y* http://news.softpedia.com/news/Intel-039-s-80-Core-CPU-Running-at-5-7-GHz-46881.shtml

7Problem Definition• Parallelize
Pll l
DP bDP-basedd query optimization to exp
loit multi-core processor architectures– the DP algorithm used in join enumeration belongs
to the non-serial polyadic DP class [8]8Contributions• firstfi t fframeworkkf
for parallel
ll l DP optimization
ti i tithat generates optimal plans• a parallel join enumeration algorithm,
algorithm alongwith various allocation• skipp vectort r array wwitht aalgorithms
g r t m speeding
png upour parallel join enumeration algorithm• formal analysis of why the various allocation
schemeshgeneratet different
difft sizes
ioff searchhspaces among threads• perform extensive experiments to show

– parallel algorithms allocate the work to threads evenly– Enhanced algorithm using the skip vector array outperforms
the conventional DP algorithm by up to orders of magnitude
9

A Running Example

10

Overview of Serial DP-based
Optimization

QEPs for single tables

QEPs for joins

11Overview of Our Solution• Goals
G l– partition the search space evenly among threads– process each partition independently without any dependencies
among threads• Keyy insights
g– By partitioning sub-problems by their sizes, sub-problems of
the same resulting size are mutually independent– AsA ththe number
b off quantifiers
tifiiincreases, ththe number
b off subbproblems of the same size grows exponentially– Each sub-problem
pm off size S ((=smallSZ+largeSZ)mg) is constructedusing any combination of one smaller sub-problem of size
smallSZ and another sub-problem of size largeSZ
12

Overview of Our Solution (Cont(Cont’d)d)• Transformf
theh enumeration problem
blintomultiple theta joins, multiple plan joins (MPJs),– disjoint and connectivity filters as join conditions• Each MPJ is then pparallelized using
g multiple
pthreads without any dependencies between
the threads.
• By judiciously allocating to threads portionsof the search space for MPJ, we can achieve
linear speed-up.
13

ExamplePlan partitions

P4 =P1

P2

P3P2(q1,qq1q2q3)(q1,q1q2q4)(q1,qq1q3q4)(q2,q1q2q3)(q2,q1q2q4)(q2,q1q3q4)(q3,q1q2q3)(q3,q1q2q4)(q3,q1q3q4)(q4,q1q2q3)(q4,q1q2q4)(q4,q1q3q4)(q1q2,q1q2)(q1q2,q1q3)(q1q2,q1q4)(q1q3,q1q2)(q1q3,q1q3)(q1q3,q1q4)(q1q4,q1q2)(q1q4,q1q3)(q1q4,q1q4)

thread 1

thread 2

14

Search Space Allocation Schemes• Totall Sum AllocationllSchemeh• Stratified Allocation– Equi-depth allocation– Round-robin outer allocation– Round-robin inner allocation

15

Example:p Round-Robin Outer
Allocation
thread 1

P1

P2

P3

P2

thread 2(q1,q1q2q3)(q1,q1q2q4)(q1,q1q3q4)(q2,q1q2q3)(q2,q1q2q4)(q2,q1q3q4)(q3,q1q2q3)(q3,q1q2q4)(q3,q1q3q4)(q4,q1q2q3)(q4,q1q2q4)(q4,q1q3q4)( 1q2,q1q2)(q( 1q2,q1q3)(q( 1q2,q1q4)(q(q1q3,q1q2)(q1q3,q1q3)(q1q3,q1q4)(q1q4,q1q2)(q1q4,q1q3)(q1q4,q1q4)

16

Basic MPJ• UUse block-nested
bl kd loop
lj i to bjoin
be cache-conscioushi• To represent an allocated search space for each thread,uses searchsh spaces
description
d s i ti vectort (SSDV)

17

Motivation for Skip Vector Array• Considerable
dbl overhead
h d in callingllexponentiall
number of disjoint filter calls!

18

Skip Vector Array
P1
1
2
3
4
5
6
7
8QSPlanList

SVq1q2q3q4q5q6q7q8…

23456789…
…
…
…
…

…

P3
1234
56789QSPlanList

SVq1q2q3q1q2q4q1q2q5q1q2q6q1q3q4
q1q4q7q1q4q8q2q5q6q4q7q8…

8 5 2
8 5 3
8 5 4
8 5 5
8 6 8
8 8 7
8 8 8
9 9 9
10 10 10

…
…
…
…
…
…
…
…

SKIP!

NOTE: Skip Vector Array can be built in one scan of quantifier sets.
19

How to allocate SVAs to threads?
• U
Use a pair
i off partitioned
i id SVAs
Vas theh unit
i off
allocation to threads– First,
First divide each plan partition into subsub-partitions
partitions– Second, build the SVAs for all sub-partitions
QS

q1q2q3

PlanList…

P3

P{3,1}
QS

P{3,3}
PlanList…

q1q2q4…

q1q2q5…

q1q2q

q1q2q6…

q1q2q

q1q3q4…

q1q4q7…

q1q4q8…

q1q2q5

q2q5q6…

q1q2q6q4q7q8…

3

Equi-depth partitioning& building SVAs

QS

SV

q1q3q4…

q1q4q7…

SV…

…

PlanList
…

SV

…

…

4

P{3,4}

P{3,2}QS

PlanList…

PlanList
…

SV

QS

…

q1q4q8…

…

q2q5q6…

…

q4q7q8…

…

…

20

Formal Analysis
yAbout Various
allocation schemes• Referf to theh paper

21

Experiments• Environment
E– Windows Vista PC with two Intel Xeon Quad Core
E5 10 1.6GHz
E5310
1 6GH CPUs
P
andd 8 GB off RAM– All serial/parallel algorithms prototyped in
P t
PostgreSQL
SQL

22Overall Comparisons
pof different
algorithms
17 hours to less then 2 minutes using only 8 threads!

23

Sensitivity
y Analysis
yfor BasicMPJ (8 threads)

24Sensitivity
y Analysis
yfor MPJ withSVA (8 threads)

25

For more experimental results• Referf to theh paper

26

Conclusions• proposedd a novell framework
fk forf parallelizing
ll li i query
optimization to exploit the coming wave of multi-coreprocessor architectures• By viewing enumeration as a join, we devised a way topartition the search space cleanly into independentproblems
minimizen m z unnunnecessary
ry calls to the disjoint
j n testing,ng,• To mwe proposed the skip vector array• We also formallyy analyzed
ywhyy our various allocation
schemes generate differently-sized search spaces
among threads, to ensure even allocation of the work
among threads
thd27

Thank you!
Anyy questions?
q28

Backup slides

29

30

Skip Vector Array• Avoidd unnecessary invocations off theh disjoint
dfilter• Augment each row in the plan partition with a
Skipp Vector for the quantifierq
set in that row• Plan partition is sorted in lexicographicalorder to skip large groups of quantifier sets•=31Equi depth Allocation
Equi-depth32

Round Robin Inner Allocation
Round-Robin

33