cs4432 - week 6 & 7

parse convert optimize execute

chooses the best query plan based on cost

relational algebra representation of a query

actual execution strategy with algorithms

estimated cost and statistics

minimize intermediate result size

push selections down

push projections down

reduces number of tuples processed

reduces number of attributes processed

rules that preserve query equivalence

indexing iteration partitioning

fast retrieval using conditions

scanning tuples sequentially

divide data into smaller parts using hashing or sorting

process data in one scan

requires two scans of data

requires multiple scans for large data

data must fit in memory

when smaller relation fits in memory

M ≥ B(S) + 1

B(R) + B(S)

result must fit in memory

B(R)

number of groups fits in memory

must process all input before output

can output tuples immediately

group by sorting

selection projection join

read M blocks sort write runs

merge sorted runs

B(R) ≤ M²

3B(R)

sort both relations then merge join

3(B(R)+B(S))

partition then process each partition

partition data using hash function

process each bucket independently

each bucket fits in memory

B(R) < M²

3B(R)

same hash function on join key

join matching buckets

3(B(R)+B(S))

smaller relation fits in memory per partition

number of blocks in relation

number of tuples

number of distinct values of attribute A

T(R)/V(R,A)

T(R)/3 if unknown distribution

T(R)

multiply fractions

sum or probabilistic formula

T(R) × T(S) / max(V(R,Y), V(S,Y))

uniform distribution