Query Processing 2
Kamal Karlapalem
Relational Operations on Bags
• A bag has duplicate rows, whereas set does not
• R⋃BS, if a tuple t occurs n times in R and m times in S, it occurs m+n
times in the union
• R⋂BS, if a tuple t occurs n times in R and m times in S, it occurs
min(m,n) times in the intersection
• R-BS, if a tuple t occurs n times in R and m times in S, it occurs
max(0,n-m) times in the intersection
Projection & Selection
• ⌅B(R), gives a bag with one row for each row of the table.
• 𝜎C(R), gives all rows that satisfy the selection condition
• R ⨝ S over bags works by having one row in result for each matching
tuple
Sets and bags
• (R ⋃ S) – T = (R-T) ⋃ (S-T) holds for sets but not bags
• R⋃(S⋂T) = (R⋃S)⋂(R⋃T)
• R⋂(S⋃T) ≠ (R⋂S)⋃(R⋂T)
Laws involving duplicate elimination
• 𝛿(R) = R if R has no duplicates – key, group by, result of set operations
• 𝛿(RXS)=𝛿(R)X𝛿(S)
• 𝛿(R⨝S)=𝛿(R)⨝𝛿(S)
• 𝛿(𝝈C(R))=𝝈C(𝛿(R))
• 𝛿(R⋂BS) = 𝛿(R)⋂BS = R⋂B𝛿(S) = 𝛿(R)⋂B𝛿(S)
Estimating Cost of operations
• B(R) – number of blocks needed to hold relation R
• T(R) – number of tuples of relation R
• V(R,a) number of distinct values for attribute a
• V(R, [a1, a2, …, an]) number of distinct values for attributes a1, a2, …, an
• Give accurate estimates
• Easy to compute
• Logically consistent, irrespective of manner of getting the result the
estimate of the size of result must be the same
Estimating the sizes - Project
• Projection - 𝛿(⌅(Attrs)(R))
• R(a,b,c) is a relation, a, b, integers 4 bytes, c string 100 bytes. Tuple
headers 12 bytes.
• Length of tuple t is 120 bytes
• Block size 1024 bytes, block header is 24 bytes
• bfr=⌊1000/120⌋=8, T(R)=10,000; B(R)=⌈10,000/8⌉=1250
• S=⌅(a+b→s,c)(R), length is 100+4+12=116, bfr=8, B(S)=1250
• U=⌅(a,b)(R),length is 8=12=20, bfr=⌊1000/20⌋=50 B(U)= ⌈10,000/50⌉ = 200
Estimating the sizes - Select
S = 𝛔Condition(R); Condition: c is constant
sf: selectivity factor
• A=c → T(S) = T(R)/V(R,a) → sf=1/V(R,a)
• A<c → T(S) = T(R)/3; → sf=1/3 intuition inequality queries retrieve
smaller number of tuples.
• A≠c → T(S)=T(R) or [T(R)(V(R,a)-1)]/V(R,a) sf =1
• C1 and C2 …and Cn → T(R)*sf1*sf2*… sfn
• C1 or C2 → T(R)(1-(1-sf1)(1-sf2))
Estimating the sizes - EquiJoin
T(R(X,Y)⨝S(Y,Z))
1. ⌅Y(R)⋂⌅Y(S)=∅, T(R⨝S) = 0 jsf = 0
2. T(R⨝S)=T(R);Y is key of R, Foreign key of S
3. ⌅Y(R) = {a} = ⌅Y(S), T(R⨝S)=T(R)*T(S) jsf = 1
Estimating the sizes - EquiJoin
Containment of Value sets: If Y occurs in many relations, then each
relation selects values from the front of a fixed list of values y1, y2, …;
and V(R,Y) ≤ V(S,Y), every Y-value of R will be a Y-value of S
Preservation of Value Sets: Attribute A which is not a join attribute will
have its values preserved in the join result. V(R⨝S,A) = V(R,A)
Estimating the sizes - EquiJoin
T(R(X,Y)⨝S(Y,Z))
• V(R,Y)⩾V(S,Y) Y value of S is a Y value of R
• Y value of S appears in R – containment
• Y of R and Y of S have same value, 1/V(R,Y)
• V(R,Y)<V(S,Y), it is 1/V(S,Y)
• Y of R same as Y of S based on above is jsf = 1/max(V(R,Y),VS,Y))
• T(R(X,Y)⨝S(Y,Z))= T(R)*T(S)/max(V(R,Y),V(S,Y))
Example
R(a,b) S(b,c) U(c,d)
T(R ) = 1000 T(S) = 2000 T(U) = 5000
V(R,b) = 20 V(S,b) = 50
V(s,c) = 100 V(U,c) = 500
T(R⨝S⨝U) (a) (R⨝S)⨝U (b) R⨝(S⨝U)
• T(R⨝S) = T(R )*T(S)/max(V(R,b), V(S,b)) = (1000*2000)/max(20,50) = 40000
• T((R⨝S)⨝U )= T(R⨝S)*T(U)/max(V(T(R⨝S), c), V(U,c)); V(T(R⨝S), c) = V(S,c)
• 40000*5000/max(100,500) = 400000
• T(S ⨝U) = 2000*5000/500 = 20000
• V(S ⨝U, b) = V(S,b) = 50
• T(R⨝(S⨝U)) = 1000*20000/50 = 400000
Estimating the sizes - Equijoin
• If join is on multiple attributes, then use join selectivity factor for each
attribute independently
• T(R(X,Y)⨝S(Y,Z)) if Y is {b,c} – join attributes
jsf=(1/max(V(R,b),V(S,b)))* (1/max(V(R,c),V(S,c)))
T(R(a,b,c) ⨝b=d and c=e S(d,e,f))
R(a,b,c) S(d,e,f)
= 1000*2000/(max(20,50)*max(100,50))
T(R ) = 1000 T(S) = 2000
= 1000*2000/(50*100)
V(R,b) = 20 V(S,d) = 50
= 400
V(R,c) = 100 V(S,e) = 50
Estimating the sizes - Equijoin
• S = R1 ⨝ R2 ⨝ … ⨝ Rn multiple relations
• Attribute A occurs in k relations
• V(Ri,A) = vi, v1≤v2≤…≤vk
• Probability A has same value in R1, …, Rk is 1/(v2..vk)
• Product of tuples in each relation, for each attribute appearing twice divide by all but the least of
V(R,A)s
• It is same for two relation max((V(R,A), V(S,A))
R(a,b,c) S(b,c,d) U(b,e)
T(R ) = 1000 T(S) = 2000 T(U) = 5000
T(R(a,b,c) ⨝ S(b,c,d)) ⨝ U(b,e)
V(R,a) =100
• multiply tuples of relation =1000*2000*5000
V(R,b) = 20 V(S,b) = 50 V(U,b) = 200
• b thrice (top 2, V(R,b), V(U,b)) , c twice (top 1,
V(R,c)).
V(R,c) = 200 V(S,c) = 100
• (1000*2000*5000)/(50*200*200) = 5000
V(S,d) = 400
V(U,e) = 500
Estimating Sizes for ϴ join
• Perform cartesian product
• Apply condition selectivity
• R(a,b) ⨝ b>b S(b,c) condition b>b is almost a cartesian product
• Same for other conditions
Estimating sized for other operations
• Union – can be sum at max
• T(R⋃S) ≅ max(T(R),T(S)) + ½(min(T(R ),T(S))
• Union – can be 0 at min
• T(R⋂S) ≅ ½(min(T(R ),T(S))
• Difference
• T(R-S) = T(R) –T(S)/2
• Duplicate Elimination (R(a1, a2, …, ak)
• T(δ(R)) = min(T(R)/2, ∏i=1,k(V(R,ai))
• Grouping
• T(𝛾(R)) = min(T(R)/2, ∏i=1,k(V(R,ai)) - 𝛾 is grouping operator
Cost-based Plan Selection
Cost of evaluating a plan number of disk i/o’s, determined by the number of
tuples accessed
• Logical operator, based on equivalent expressions
• Sizes of intermediate relations
• Physical operators to implement logical operators (one-pass, two-pass)
• Ordering of joins
• Passing arguments from one physical operator to another
• Materialized (intermediate results are stored) vs. pipelined
Histogram
• Equal width, for fixed range of values how many rows are there
• Equal height, for which range of values is same number of rows
• Most frequent values and their occurrences, like Zipf distribution
• Histograms give more accurate estimates of intermediate result sizes
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