Advanced Database Systems
Spring 2025
Lecture #16:
Query Optimisation: Costing
R&G: Chapter 15
2
W HAT IS N EEDED FOR Q UERY O PTIMISATION
Given: A closed set of operators
Relational operators (table in, table out)
Physical implementations (of those operators and a few more)
Plan space
Based on relational equivalences, different implementations
Cost estimation
Cost formula & size estimation for each physical operator
Search algorithm
To sift through the plan space and find lowest cost option!
13
C OST E STIMATION
For each plan considered, must estimate total cost:
Must estimate cost of each operation in plan tree
Depends on input cardinalities
Already discussed costs for various operators (sequential scan, index scan, joins, etc.)
Must estimate size of result for each operation in tree!
Because it determines downstream input cardinalities!
Use information about the input relations
For selections and joins, assume independence of predicates
In System R, cost boils down to a single number: #I/Os + CPU-factor * #tuples
Second term estimate the cost of tuple processing
14
S TATISTICS AND C ATALOGS
System catalogs store internal statistics about tables, attributes, and indexes
Typically contain at least:
STATISTIC MEANING
NTuples # of tuples in a table (cardinality)
NPages # of disk pages in a table or index
Low/High min/max value in a column
Can also keep more detailed statistical
NKeys # of distinct values in a column
information on data values (e.g., histograms)
Height the height of an index
Catalogs are updated periodically
Users can also manually refresh them (e.g,. ANALYZE in PostgreSQL)
Too expensive to do continuously. Lots of approximation anyway, so a little slop is OK
15
S IZE E STIMATION AND S ELECTIVITY
Max output cardinality = product of input cardinalities
Selectivity (sel) associated with each term
Reflects the impact of the term in reducing result size
Selectivity = |output| / |input|
Sometimes called “Reduction Factor” (RF)
Always between 0 and 1
Avoid confusion:
“highly selective” in common English is opposite of a high selectivity value
(|output|/|input| high!)
16
S ELECTION E STIMATES
The selectivity (sel) of a predicate P is the fraction of tuples that qualify
Equality predicates on unique keys are SELECT * FROM Students
easy to estimate WHERE sid = 123
What about more complex predicates?
SELECT * FROM Students
What is their selectivity?
WHERE age = 21
Formula depends on type of predicate
Equality, range, negation, conjunction, disjunction SELECT * FROM Students
WHERE age > 22
AND dept = ‘CS’
17
S ELECTIONS - C OMPLEX P REDICATES
Assume attribute age in relation Students has five distinct values (20-24)
NKeys(age) = 5
SELECT * FROM Students
Equality predicate WHERE age = 22
sel(A = constant) = 1 / NKeys(A)
SELECT * FROM Students
Example: sel(age = 22) = 1/5
WHERE age > 22
Range predicate
sel(A > a) = (High(A) – a) / (High(A) – Low(A) + 1) (when A is integer-valued column)
sel(A > a) = (High(A) – a) / (High(A) – Low(A)) (when A is floating-valued column)
Example: sel(age > 22) = (24 – 22) / (24 – 20 + 1) = 2/5
18
S ELECTIONS - C OMPLEX P REDICATES
Equality predicate
sel(A = B) = 1 / max { NKeys(A), NKeys(B) } (handy for joins, too)
Why MAX?
Assume that A-values and B-values are independent
Let there be 2 distinct A-values { v1, v2 } and 10 distinct B-values { v1, …, v10 }
What is the probability of matching values?
P(A = B) = Σi P(A = vi, B = vi) = Σi P(A = vi) · P(B = vi)
= (1/2 · 1/10) + (1/2 · 1/10) + (0 · 1/10) + …
= 1/10 = 1 / max { 2, 10 }
19
S ELECTIONS - C OMPLEX P REDICATES
Negation query
SELECT * FROM Students
sel(not P) = 1 – sel(P)
WHERE age != 22
Example: sel(age != 22) = 1 – 1/5 = 4/5
Observation: selectivity ≈ probability
Conjunction SELECT * FROM Students
sel(P1 ∧ P2) = sel(P1) · sel(P2) WHERE age = 22
Assumes that the predicates are independent AND name LIKE ‘A%’
Disjunction
SELECT * FROM Students
sel(P1 v P2) = sel(P1) + sel(P2) – sel(P1 ∧ P2) WHERE age = 22
Assumes that the predicates are independent OR name LIKE ‘A%’
20
R ESULT S IZE E STIMATION FOR J OINS
How to estimate the size of a join between R and S?
Key-foreign key join
Example: S has a foreign key referencing R
The foreign key constraint guarantees πA(S) ⊆ πA(R), thus |R ⋈ S| = |S|
Assumes non-null FK values (e.g., if A is part of a primary key in S); otherwise, |R ⋈ S| ≤ |S|
21
R ESULT S IZE E STIMATION FOR J OINS
General case: R join S on A which is not a key for either table
Recall algebraic equivalence: R ⋈p S ≡ σp(R x S)
Hence join selectivity is “just” selectivity sel(p) over a big input |R| · |S|!
Total rows: sel(p) · |R| · |S|
Equi-join on A
Match each R-tuple with S-tuple: |R ⋈ S| ≈ |R| · |S| / NKeys(S.A)
Symmetrically, for S: |R ⋈ S| ≈ |S| · |R| / NKeys(R.A)
The final estimate is the smaller of the two estimates sel(R.A = S.A)
Overall: |R ⋈ S| ≈ |R| · |S| · 1 / max { NKeys(R.A), NKeys(S.A) }
22
M ISSING S TATISTICS ? U SE D EFAULT VALUES
Postgres 13.0
src/include/utils/selfuncs.h
23
C OST E STIMATION
Our cost formulas assume that data values are uniformly distributed
Uniform Approximation
# of occurrences 10
0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Distinct values of attribute
24
C OST E STIMATION
In practice, attribute values typically have a non-uniform distribution
Non-Uniform Distribution
# of occurrences 10
0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Distinct values of attribute
25
H ISTOGRAMS
To keep track of this non-uniformity for an attribute A, we can
maintain a histogram to approximate the actual distribution
Divide the active domain of A into adjacent intervals
Collect statistical parameters for each interval (bi-1, bi], for example
# of tuples r with bi-1 < r.A ≤ bi
# of distinct A values in interval (bi-1, bi]
The histogram intervals are also called buckets
26
T YPES OF H ISTOGRAMS
Equi-width histograms
All buckets have the same width w or number of distinct values
I.e., boundary bi+1 = bi + w for some fixed width w
Equi-depth histograms
All buckets contain the same number of tuples (their width may vary)
Able to adapt to data skew (high uniformity)
The number of buckets is the tuning knob that defines the trade-off between
histogram resolution (estimation quality) and histogram size
Catalog space is limited!
27
E QUI -W IDTH H ISTOGRAMS
# of distinct values = 16, # of tuples = 64
28
E QUI -W IDTH H ISTOGRAMS
Maintain sum of value frequencies in each bucket
(in addition to bucket boundaries bi)
Divide active domain of A
into B buckets of equal width
Bucket width w:
29
E QUALITY S ELECTION
w
30
R ANGE S ELECTION
31
E QUI -D EPTH H ISTOGRAMS
Divide active domain of attribute A into B buckets with roughly the same
number of tuples in each bucket
Depth d of each bucket will be approximately |R|/ B
Maintain depth d and bucket boundaries bi
Intuition:
High-value frequencies are more important than low-value frequencies and
put in smaller buckets
Equi-depth provides better estimates than equi-width for highly frequent values
Resolution of histogram adapts to skewed value distributions
32
E QUI -D EPTH H ISTOGRAM
33
C OMPARISON
Equi-depth histogram
“invests” bytes in the
densely populated
customer age region
between 30 and 59
34
E QUALITY S ELECTION
35
R ANGE S ELECTION
36
S UMMARY : S ELECTIVITY E STIMATION
We need a way to estimate the size of the intermediate tables
Output size = input size * operator selectivity
Assumption 1: Uniform distribution within histogram bins
Within a bin, fraction of range = fraction of count
Assumption 2: Independent predicates
Selectivity of AND = product of selectivities of predicates
Selectivity of OR = sum of selectivities of predicates – product of selectivities of predicates
Selectivity of NOT = 1 – selectivity of predicates
General joins
Simply compute the selectivity of all predicates
And multiply by the product of the table sizes