![](https://csdnimg.cn/release/download_crawler_static/2418024/bg4.jpg)
– r is the outer relation: Cost = d
b
r
M−1
∗b
s
+b
r
, where M blocks
are allocated to r
• Sort Merge Join
– Soting cost of each reltion assuming they are not sorted is (M
is the number of pages available for sorting - 1 is for o/p and
M-1 for input):
∗ for r, b
r
(2dlog
M−1
(b
r
/M)e + 1 + 1
∗ for s, b
s
(2dlog
M−1
(b
s
/M)e + 1 + 1
– After sorting, assuming that all the tuples with the same value
for the join attributs fir in memory, the cost is: (Sorting Cost) +
b
r
+ b
s
• Hash Join
– Assume no overflow occurs
– Use smaller relation (say r) as the build relation and larger re-
lation (say s) as the probe relation
– If M > b
r
/M, no need of recursive paritioning and cost is:
Cost = 3(b
r
+ b
s
)
– Else, if recursive partioning occurs: Cost = 2(b
r
+
b
s
)dlog
M−1
(b
r
)−1e+b
r
+b
s
(included is the cost for reading
and writing partitions)
• A B-tree organization has b(m −1)n/mc entries for each node
Query Optimization
Equivalence Rules
(Set Version)
• Cascade of σ for conjunction selections
σ
θ
1
∧θ
2
(E) = σ
θ
1
(σ
θ
2
(E))
• Commutativity of selection operations
σ
θ
1
(σ
θ
2
(E)) = σ
θ
2
(σ
θ
1
(E))
• Only final projection in a sequence of proje ctions
π
L
1
(π
L
2
(. . . π
L
n
))) = π
L
1
(E)
• Selections can be combined with Cartersian products and theta joins:
–
σ
θ
(E
1
xE
2
) = E
1
on
θ
E
2
–
σ
θ
1
(E
1
σ
θ
2
E
2
) = E
1
on
θ
1
∧θ
2
E
2
• Theta joins and natural joins are commutative
E
1
on E
2
= E
2
on E
1
• Associativity of joins
– Natural Joins are associative:
(E
1
on E
2
) on E
3
= E
1
on (E
2
on E
3
)
– Theta joins are associative in the following manner: If θ
2
has
only attributes from E
2
and E
3
, then:
(E
1
on
θ
1
E
2
) on
θ
1
∧θ
3
E
3
= E
1
on
θ
1
∧θ
3
(E
2
on
θ
2
E
3
)
– Cartesian products are also associative
• Distributivity of selections
– If θ
0
only involves E
1
, then
σ
θ
0
(E
1
on
θ
E
2
) = (σ
θ
0
(E
1
)) on
θ
E
2
– If θ
1
only involves E
1
and θ
2
only involves E
2
, then
σ
θ
1
∧θ
2
(E
1
on
θ
E
2
) = (σ
θ
1
(E
1
)) on
θ
σ
θ
2
(E
2
))
• Distributivity of projections If L
1
are only attributes of E
1
and L
2
only of E
2
, then
π
L
1
∪L
2
(E
1
on
θ
E
2
) = π
L
1
(E
1
) on
θ
(π
L
2
(E
2
))
• Set operations of union and intersection are com mutative
E
1
∪ E
2
= E
2
∪ E
1
E
1
∩ E
2
= E
2
∩ E
1
However, Set Difference is not commutative.
• Set union and intersection are associative
(E
1
∪ E
2
) ∪ E
3
= E
1
∪ (E
2
∪ E
3
)
(E
1
∩ E
2
) ∩ E
3
= E
1
∩ (E
2
∩ E
3
)
• Selection operation distributes over union, intersection and set differ-
ence operations:
σ
P
(E
1
− E
2
) = σ
P
(E
1
) − σ
P
(E
2
)
Also,
σ
P
(E
1
− E
2
) = σ
P
(E
1
) − E
2
(this does not hold for intersection???)
• Projection operation distributes over union:
π
L
(E
1
∪ E
2
) = (π
L
(E
1
)) ∪ (π
L
(E
2
))
Join ordering: choose such that the size of th temporary results are re-
duced
Enumeration of Equivalent Expressions:
• Space requirements can be optimized by pointing to shared sub ex-
pressions
• Time requirements can be reduced by optimization (dynamic pro-
gramming, etc.)
Estimating Statistics of Expr Results
• Catalog Information:
– n
r
= number of tuples in r
– b
r
= number of block containing tuples of r
– l
r
= size of a tuple of r in bytes
– f
r
= blocking factor of r (= number of tuples of r that fit in one
block)
– V (A, r) = number of distinct values that appear in r for at-
tribute A
– If A is a key for r, then V (A, r) = n
r
– If tuples of r are phsyically stored togethe r, b
r
= d
n
r
f
r
e
– Histogram for a range of values of attribute can be used for
estimating (histograms can be equi-width o r equi-height)
• Selection Size Estimation:
– Equality ( σ
A=a
(r ))
∗ Assuming equi-probable, Num = n
r
/V (A, r)
∗ With histogram, num = n
range
/V (A, range)
– Comparison ( σ
A≤v
(r ))
∗ If v < min(A, r), num = 0
∗ If v ≥ max(A, r), Num = n
r
∗ Else, num = n
r
.
v−min(A,r)
max(A,r)−min(A,r)
(this can be modi-
fied to use a histogram, where available - use the number
in the ranges, instead of in the entire relation)
∗ If v is not known as in the case of stored procedures, as-
sume num = n
r
/2
– Complex selections
∗ Conjunctions (σ
θ
1
∧θ
2
...∧
n
(r )): num = n
r
.
s
1
∗s
2
∗...s
n
n
n
r
,
where s
i
is the number of tuples that satisfy the selection
σ
θ
1
(r ).
s
i
/n
r
is called the selectivity of the selection σ
θ
1
(r )
∗ Disjunctions (σ
θ
1
∨θ
2
...θ
n
(r )): num = n
r
∗ [1 − (1 −
s
1
n
r
)(1 −
s
2
n
r
) . . . (1 −
s
n
n
r
)
∗ Negations: Compute num as: num = n
r
− num(σ
θ
(r ).
If NULLs are present, compute as: num = n
r
−
num(σ
θ
(r ) −num(NU LLs).
• Join Size Estimation:
– Cartesian Product: Num(rxs) = n
r
xn
s
– Natural Joins