Query Processing 3

Kamal Karlapalem
Example 250
500
𝛅
⨝
𝛅
⨝ 1000
50 𝛅 𝛅 1000
𝜎(a=10)
S 2000
100 𝜎(a=10) 100 𝜎(a=10)
⨝

5000 R 2000 S 5000 R

R S
Right plan
Logical plan Left plan

R(a,b) S(b,c) • Left plan cost 100+50+1000=1150

T(R) = 5000 T(S) = 2000
V(R,a) = 50
• Right plan cost 100+1000=1100
V(R,b) = 100 V(S,b) = 200
V(S,c) = 100
Physical Plans
• One logical plan can have many physical plans
• There can be many equivalent logical plans
• Each physical plan has the cost for executing it
• Given a very large number of physical plans – the problem is to
quickly determine the physical plan that has the least cost
• For most of the cases we find a plan that has significantly reduced
cost compared to the initial plan cost
Enumerating Physical Plans
• Top Down
• Take root of the logical query plan – for each operation at the root, we consider each
possible way to evaluate its arguments and compute the cost of each combination,
taking the best
• Bottom Up
• For each subexpression of the logical query plan tree, we compute all possible ways
to compute the subexpression. The possibilities and costs for a subexpression E are
computed by considering the options for the subexpression of E and combining them
in all possible ways with implementations for the root operator of E
• Both explore all possible ways to execute a logical plan. We will consider
bottom-up approach
Heuristics used
• Use index on A if available for 𝛔A=c(R)
• Filter → select by index, if no index then scan
• If any join attribute has index – use it for index join
• If any relation is sorted on join attribute, prefer sort join
• When computing union across many relations do it for smallest
relations first
Branch and Bound Plan enumeration
• Let current cost of partial plan be C, then any extension or
replacement that costs more than C is eliminated from search
• Let the current cost of partial plan be C, then any replacement or
extension that has cost less than C replaces the current plan
• We can decide when to stop the search based on cost.
• No point in trying to minimize C by spending a lot of time in
exploration
Dynamic & Selinger Style
• Dynamic
• Keep for each subexpression only the plan of least cost
• Build on this subexpression to get larger expressions while maintaining the
above.
• Sellinger Style
• Keep for each subexpression the plan with least cost
• Keep other plans (interesting orders) but that have advantages in larger
expression (like sorted, index)
• Subexpression sorted on sort attribute
• Subexpression sorted on grouping attribute
• Subexpression sorted on join attribute
Join left and right Arguments
• R⨝S, R is left argument, S is right argument
• One-pass join algorithm, hash or index based.
• R is the build relation
• S is the probe relation
• For every row of R probe for matching rows of S
• Nested loop R is outer relation S is probe relation
• Index join; S has index for probing
• Hash join, S is hashed on join attribute
 Join Trees
⨝ ⨝

⨝ U U ⨝
⨝

⨝ T T ⨝
⨝ ⨝

R S S R
R S T U

• Left deep, Bushy and Right deep

• Since relations can have any order, 4!=24 same trees are possible
• Total number of trees
• T(1) = 1, T(n) = ∑i=1,..n T(i)T(n-i)
• Total trees = n!T(n)
Dynamic Programming to select join order
• R1 ⨝ R2 ⨝ … ⨝ Rn. Let R1→k be the set of k relations joined
• Construct a table
• An entry for each subset of one or more of the n relations (for k, nCk entries)
• The estimated size of join
• The least cost of computing the join of these relations
• The expression that yields the least cost

• Construction of above table is an induction on the subset size.

• Left-deep - R1→k is {R1→(k-1)} ⨝ {Rk} – we consider the least cost for {R1→k} for
further joins
Costs
• Initial relation access of results cost is zero (0) as we need to access
the relations for all plans
• Final join result cost is same for all plans, hence not considered
• Optimization is on the sizes of intermediate results which by careful
selection we can minimize
Example
Step 1 {R} {S} {T} {U}
R(a,b) S(b,c) T(c,d) U(d,a) size 1000 1000 1000 1000
T(R ) = 1000 T(S) = 1000 T(T) = 1000 T(U) = 1000 cost 0 0 0 0
V(R,a) = 100 V(U,a) = 50
Best R S T U
V(R,b) = 200 V(S,b) = 100 Plan
V(S,c) = 500 V(T,c) = 20
V(T,d) = 50 V(U,d) =100
Final Grouping Cost
Step 2 {R,S} {R,T} {R,U} {S,T} {S,U} {T,U} ((S⨝T) ⨝ R) ⨝U 12000
size 5000 1000000 10000 2000 1000000 1000 ((R⨝S) ⨝ U) ⨝T 55000
cost 0 0 0 0 0 0
((T⨝U) ⨝ R) ⨝S 11000
Best R⨝S R⨝T R⨝U S⨝T S⨝U T⨝U
Plan ((T⨝U) ⨝ S) ⨝R 3000
(T⨝U) ⨝(R⨝S) 6000
Step 3 {R,S,T} {R,S,U} {R,T,U} {S,T,U} (R⨝T) ⨝(S⨝U) 2000000
size 10000 50000 10000 2000 (S⨝T) ⨝(R⨝U) 12000
cost 2000 5000 1000 1000
Best (S⨝T) ⨝ R (R⨝S) ⨝ U (T⨝U) ⨝ R (T⨝U) ⨝ S
Plan
Cost Detailed
• Size of intermediate relation – number of rows was the cost
• Additional costs can be added
• Compute cost for operator
• Physical join operation – algorithm
• Selinger Style
• Maintain multiple plans
• Interesting plans
Logical Plan → Physical Plan
• Selection of algorithms to implement operations
• Intermediate results – materialized or pipelined
• Physical query plan includes details regarding access method (indices
used, or scans)
• Physical query plan includes details of join algorithm
• Physical query plan nodes and operators map to function calls
Pipelining vs Materialization
• Execute each operator separately, store the intermediate result, use it
for next operator – materialization.
• Interleave execution of several operators, tuples produced by one
operator are consumed by following operator – need not store
intermediate results – pipelining
• Materialization or pipeline can be based on sizes of intermediate
relations and following operators
Physical plan
• Operators for leaves
• TableScan(R), SortScan(R,L) L list of attributes, IndexScan(R,C) C is a condition,
IndexScan(R,A) A is attribute
• Output of above go to project, or join, or sort, or grouping operator
• Operators for intermediate nodes
• NestedLoopJoin(R,S,L), HashJoin(R,S,L,H), IndexJoin(R,S,L,I),
SortMergeJoin(R,S,L)
 Example
Two-pass
Hash-join Sort
101 buffers Merge join
101 buffers

Two-pass TableScan(U)
Hash-join Nested TableScan(U)
101 buffers Loop join
101 buffers

TableScan(R) TableScan(S)
TableScan(R) TableScan(S)