Chapter 16: Query Optimization

Database System Concepts, 7th Ed.

©Silberschatz, Korth and Sudarshan
See www.db-book.com for conditions on re-use
 Outline

 Introduction
 Transformation of Relational Expressions
 Catalog Information for Cost Estimation
 Statistical Information for Cost Estimation
 Cost-based optimization
 Dynamic Programming for Choosing Evaluation Plans
 Materialized views

Database System Concepts - 7th Edition 16.2 ©Silberschatz, Korth and Sudarshan
 Introduction

 Alternative ways of evaluating a given query

• Equivalent expressions
• Different algorithms for each operation

Database System Concepts - 7th Edition 16.3 ©Silberschatz, Korth and Sudarshan
 Introduction (Cont.)

 An evaluation plan defines exactly what algorithm is used for each

operation, and how the execution of the operations is coordinated.

 Find out how to view query execution plans on your favorite database

Database System Concepts - 7th Edition 16.4 ©Silberschatz, Korth and Sudarshan
 Introduction (Cont.)

 Cost difference between evaluation plans for a query can be enormous

• E.g., seconds vs. days in some cases
 Steps in cost-based query optimization
1. Generate logically equivalent expressions using equivalence rules
2. Annotate resultant expressions to get alternative query plans
3. Choose the cheapest plan based on estimated cost
 Estimation of plan cost based on:
• Statistical information about relations. Examples:
 number of tuples, number of distinct values for an attribute
• Statistics estimation for intermediate results
 to compute cost of complex expressions
• Cost formulae for algorithms, computed using statistics

Database System Concepts - 7th Edition 16.5 ©Silberschatz, Korth and Sudarshan
 Viewing Query Evaluation Plans

 Most database support explain <query>

• Displays plan chosen by query optimizer, along with cost estimates
• Some syntax variations between databases
 Oracle: explain plan for <query> followed by select * from table
(dbms_xplan.display)
 SQL Server: set showplan_text on
 Some databases (e.g. PostgreSQL) support explain analyse <query>
• Shows actual runtime statistics found by running the query, in addition
to showing the plan
 Some databases (e.g. PostgreSQL) show cost as f..l
• f is the cost of delivering first tuple and l is cost of delivering all results

Database System Concepts - 7th Edition 16.6 ©Silberschatz, Korth and Sudarshan
 Generating Equivalent Expressions

Database System Concepts - 7th Edition 16.7 ©Silberschatz, Korth and Sudarshan
 Transformation of Relational Expressions

 Two relational algebra expressions are said to be equivalent if the two

expressions generate the same set of tuples on every legal database
instance
• Note: order of tuples is irrelevant
• we don’t care if they generate different results on databases that
violate integrity constraints
 In SQL, inputs and outputs are multisets of tuples
• Two expressions in the multiset version of the relational algebra are
said to be equivalent if the two expressions generate the same
multiset of tuples on every legal database instance.
 An equivalence rule says that expressions of two forms are equivalent
• Can replace expression of first form by second, or vice versa

Database System Concepts - 7th Edition 16.8 ©Silberschatz, Korth and Sudarshan
 Equivalence Rules

1. Conjunctive selection operations can be deconstructed into a sequence of

individual selections.
σ1  2 (E) ≡ σ1 (σ2 (E))
2. Selection operations are commutative.
σ1(σ2(E)) ≡ σ2 (σ1(E))
3. Only the last in a sequence of projection operations is needed, the others
can be omitted.
 L1( L2(…( Ln(E))…)) ≡  L1(E)
where L1 ⊆ L2 … ⊆ Ln
4. Selections can be combined with Cartesian products and theta joins.
a. σ (E1 x E2) ≡ E1 ⨝  E2
b. σ 1 (E1 ⨝2 E2) ≡ E1 ⨝ 1∧2 E2

Database System Concepts - 7th Edition 16.9 ©Silberschatz, Korth and Sudarshan
 Equivalence Rules (Cont.)

5. Theta-join operations (and natural joins) are commutative.

E1 ⨝ E2 ≡ E2 ⨝ E1

6. (a) Natural join operations are associative:

(E1 ⨝ E2) ⨝ E3 ≡ E1 ⨝ (E2 ⨝ E3)

(b) Theta joins are associative in the following manner:

(E1 ⨝ 1 E2) ⨝ 2  3 E3 ≡ E1 ⨝1  3 (E2 ⨝ 2 E3)

where 2 involves attributes from only E2 and E3.

Database System Concepts - 7th Edition 16.10 ©Silberschatz, Korth and Sudarshan
 Pictorial Depiction of Equivalence Rules

Database System Concepts - 7th Edition 16.11 ©Silberschatz, Korth and Sudarshan
 Equivalence Rules (Cont.)

7. The selection operation distributes over the theta join operation under the
following two conditions:
(a) When all the attributes in 0 involve only the attributes of one
of the expressions (E1) being joined.

0 E1 ⨝ E2) ≡ (0(E1)) ⨝ E2

(b) When 1 involves only the attributes of E1 and 2 involves

only the attributes of E2.
1  2 E1 ⨝ E2) ≡ (1(E1)) ⨝ (2(E2))

Database System Concepts - 7th Edition 16.12 ©Silberschatz, Korth and Sudarshan
 Equivalence Rules (Cont.)

8. The projection operation distributes over the theta join operation as follows:
(a) if  involves only attributes from L1  L2:
 L1  L2(E1 ⨝ E2) ≡  L1(E1) ⨝  L2(E2)
(b) In general, consider a join E1 ⨝ E2.
• Let L1 and L2 be sets of attributes from E1 and E2, respectively.
• Let L3 be attributes of E1 that are involved in join condition , but are
not in L1  L2, and
• let L4 be attributes of E2 that are involved in join condition , but are
not in L1  L2.
 L1  L2(E1 ⨝ E2) ≡  L1  L2( L1  L3(E1) ⨝  L2  L4(E2))

Similar equivalences hold for outerjoin operations: ⟕, ⟖, and ⟗

Database System Concepts - 7th Edition 16.13 ©Silberschatz, Korth and Sudarshan
 Equivalence Rules (Cont.)

Database System Concepts - 7th Edition 16.14 ©Silberschatz, Korth and Sudarshan
 Equivalence Rules (Cont.)
13. Selection distributes over aggregation as below
(G𝛾A(E)) ≡ G𝛾A((E))
provided  only involves attributes in G
14. a. Full outerjoin is commutative:
E1 ⟗ E2 ≡ E2 ⟗ E1
b. Left and right outerjoin are not commutative, but:
E1 ⟕ E2 ≡ E2 ⟖ E1
15. Selection distributes over left and right outerjoins as below, provided 1
only involves attributes of E1
a. 1 (E1 ⟕ E2) ≡ (1 (E1)) ⟕ E2
b. 1 (E1 ⟖ E2) ≡ E2 ⟕ (1 (E1))
16. Outerjoins can be replaced by inner joins under some conditions
a. 1 (E1 ⟕ E2) ≡ 1 (E1 ⨝ E2)
b. 1 (E1 ⟖ E1) ≡ 1 (E1 ⨝ E2)
provided 1 is null rejecting on E2

Database System Concepts - 7th Edition 16.15 ©Silberschatz, Korth and Sudarshan
 Equivalence Rules (Cont.)
Note that several equivalences that hold for joins do not hold for outerjoins
 year=2017(instructor ⟕ teaches) ≢ year=2017(instructor ⨝ teaches)
 Outerjoins are not associative
(r ⟕ s) ⟕ t ≢ r ⟕ (s ⟕ t)
• e.g. with r(A,B) = {(1,1), s(B,C) = { (1,1)}, t(A,C) = { }

Database System Concepts - 7th Edition 16.16 ©Silberschatz, Korth and Sudarshan
 Transformation Example: Pushing Selections

 Query: Find the names of all instructors in the Music department, along
with the titles of the courses that they teach
• name, title(dept_name= ‘Music’
(instructor ⨝ (teaches ⨝ course_id, title (course))))
 Transformation using rule 7a.
• name, title((dept_name= ‘Music’(instructor)) ⨝
(teaches ⨝ course_id, title (course)))
 Performing the selection as early as possible reduces the size of the
relation to be joined.

Database System Concepts - 7th Edition 16.17 ©Silberschatz, Korth and Sudarshan
 Multiple Transformations (Cont.)

Database System Concepts - 7th Edition 16.18 ©Silberschatz, Korth and Sudarshan
 Join Ordering Example

 For all relations r1, r2, and r3,

(r1 ⨝ r2) ⨝ r3 = r1 ⨝ (r2 ⨝ r3 )
(Join Associativity) ⨝
 If r2 ⨝ r3 is quite large and r1 ⨝ r2 is small, we choose

(r1 ⨝ r2) ⨝ r3
so that we compute and store a smaller temporary relation.

Database System Concepts - 7th Edition 16.19 ©Silberschatz, Korth and Sudarshan
 Join Ordering Example (Cont.)

 Consider the expression

name, title(dept_name= “Music” (instructor) ⨝ teaches)
⨝ course_id, title (course))))
 Could compute teaches ⨝ course_id, title (course) first, and join result with
dept_name= “Music” (instructor)
but the result of the first join is likely to be a large relation.
 Only a small fraction of the university’s instructors are likely to be from
the Music department
• it is better to compute
dept_name= “Music” (instructor) ⨝ teaches
first.

Database System Concepts - 7th Edition 16.20 ©Silberschatz, Korth and Sudarshan
 Enumeration of Equivalent Expressions

 Query optimizers use equivalence rules to systematically generate

expressions equivalent to the given expression
 Can generate all equivalent expressions as follows:
• Repeat
 apply all applicable equivalence rules on every subexpression of
every equivalent expression found so far
 add newly generated expressions to the set of equivalent
expressions
Until no new equivalent expressions are generated above
 The above approach is very expensive in space and time
• Two approaches
 Optimized plan generation based on transformation rules
 Special case approach for queries with only selections, projections
and joins

Database System Concepts - 7th Edition 16.21 ©Silberschatz, Korth and Sudarshan
 Cost Estimation

 Cost of each operator computer as described in Chapter 15

• Need statistics of input relations
 E.g., number of tuples, sizes of tuples
 Inputs can be results of sub-expressions
• Need to estimate statistics of expression results
• To do so, we require additional statistics
 E.g., number of distinct values for an attribute
 More on cost estimation later

Database System Concepts - 7th Edition 16.22 ©Silberschatz, Korth and Sudarshan
 Choice of Evaluation Plans

 Must consider the interaction of evaluation techniques when choosing

evaluation plans
• choosing the cheapest algorithm for each operation independently may
not yield best overall algorithm. E.g.
 merge-join may be costlier than hash-join, but may provide a sorted
output which reduces the cost for an outer level aggregation.
 nested-loop join may provide opportunity for pipelining
 Practical query optimizers incorporate elements of the following two broad
approaches:
1. Search all the plans and choose the best plan in a
cost-based fashion.
2. Uses heuristics to choose a plan.

Database System Concepts - 7th Edition 16.23 ©Silberschatz, Korth and Sudarshan
 Cost-Based Optimization

 Consider finding the best join-order for r1 ⨝ r2 ⨝ . . . ⨝ rn.

 There are (2(n – 1))!/(n – 1)! different join orders for above expression.
With n = 7, the number is 665280, with n = 10, the number is greater than
176 billion!
 No need to generate all the join orders. Using dynamic programming, the
least-cost join order for any subset of
{r1, r2, . . . rn} is computed only once and stored for future use.

Database System Concepts - 7th Edition 16.24 ©Silberschatz, Korth and Sudarshan
 Dynamic Programming in Optimization

 To find best join tree for a set of n relations:

• To find best plan for a set S of n relations, consider all possible plans
of the form: S1 ⨝ (S – S1) where S1 is any non-empty subset of S.
• Recursively compute costs for joining subsets of S to find the cost of
each plan. Choose the cheapest of the 2n – 2 alternatives.
• Base case for recursion: single relation access plan
 Apply all selections on Ri using best choice of indices on Ri
• When plan for any subset is computed, store it and reuse it when it is
required again, instead of recomputing it
 Dynamic programming

Database System Concepts - 7th Edition 16.25 ©Silberschatz, Korth and Sudarshan
 Join Order Optimization Algorithm

procedure findbestplan(S)
if (bestplan[S].cost  )
return bestplan[S]
// else bestplan[S] has not been computed earlier, compute it now
if (S contains only 1 relation)
set bestplan[S].plan and bestplan[S].cost based on the best way
of accessing S using selections on S and indices (if any) on S else for each
non-empty subset S1 of S such that S1  S
P1= findbestplan(S1)
P2= findbestplan(S - S1)
for each algorithm A for joining results of P1 and P2
… compute plan and cost of using A (see next page) ..
if cost < bestplan[S].cost
bestplan[S].cost = cost
bestplan[S].plan = plan;
return bestplan[S]

Database System Concepts - 7th Edition 16.26 ©Silberschatz, Korth and Sudarshan
 Left Deep Join Trees

 In left-deep join trees, the right-hand-side input for each join is a

relation, not the result of an intermediate join.

Database System Concepts - 7th Edition 16.27 ©Silberschatz, Korth and Sudarshan
 Cost of Optimization

 With dynamic programming time complexity of optimization with bushy trees

is O(3n).
• With n = 10, this number is 59000 instead of 176 billion!
 Space complexity is O(2n)
 To find best left-deep join tree for a set of n relations:
• Consider n alternatives with one relation as right-hand side input and the
other relations as left-hand side input.
• Modify optimization algorithm:
 Replace “for each non-empty subset S1 of S such that S1  S”
 By: for each relation r in S
let S1 = S – r .
 If only left-deep trees are considered, time complexity of finding best join
order is O(n 2n)
• Space complexity remains at O(2n)
 Cost-based optimization is expensive, but worthwhile for queries on large
datasets (typical queries have small n, generally < 10)

Database System Concepts - 7th Edition 16.28 ©Silberschatz, Korth and Sudarshan
 Interesting Sort Orders
 Consider the expression (r1 ⨝ r2) ⨝ r3 (with A as common attribute)
 An interesting sort order is a particular sort order of tuples that could
make a later operation (join/group by/order by) cheaper
• Using merge-join to compute r1 ⨝ r2 may be costlier than hash join but
generates result sorted on A
• Which in turn may make merge-join with r3 cheaper, which may reduce
cost of join with r3 and minimizing overall cost
 Not sufficient to find the best join order for each subset of the set of n given
relations
• must find the best join order for each subset, for each interesting sort
order
• Simple extension of earlier dynamic programming algorithms
• Usually, number of interesting orders is quite small and doesn’t affect
time/space complexity significantly

Database System Concepts - 7th Edition 16.29 ©Silberschatz, Korth and Sudarshan
 Cost Based Optimization with Equivalence Rules
 Physical equivalence rules allow logical query plan to be converted to
physical query plan specifying what algorithms are used for each operation.
 Efficient optimizer based on equivalent rules depends on
• A space efficient representation of expressions which avoids making
multiple copies of subexpressions
• Efficient techniques for detecting duplicate derivations of expressions
• A form of dynamic programming based on memoization, which stores
the best plan for a subexpression the first time it is optimized, and
reuses in on repeated optimization calls on same subexpression
• Cost-based pruning techniques that avoid generating all plans
 Pioneered by the Volcano project and implemented in the SQL Server
optimizer

Database System Concepts - 7th Edition 16.30 ©Silberschatz, Korth and Sudarshan
 Heuristic Optimization

 Cost-based optimization is expensive, even with dynamic programming.

 Systems may use heuristics to reduce the number of choices that must be
made in a cost-based fashion.
 Heuristic optimization transforms the query-tree by using a set of rules that
typically (but not in all cases) improve execution performance:
• Perform selection early (reduces the number of tuples)
• Perform projection early (reduces the number of attributes)
• Perform most restrictive selection and join operations (i.e., with smallest
result size) before other similar operations.
• Some systems use only heuristics, others combine heuristics with partial
cost-based optimization.

Database System Concepts - 7th Edition 16.31 ©Silberschatz, Korth and Sudarshan
 Structure of Query Optimizers

 Many optimizers considers only left-deep join orders.

• Plus heuristics to push selections and projections down the query tree
• Reduces optimization complexity and generates plans amenable to
pipelined evaluation.
 Heuristic optimization used in some versions of Oracle:
• Repeatedly pick “best” relation to join next
 Starting from each of n starting points. Pick best among these
 Intricacies of SQL complicate query optimization
• E.g., nested subqueries

Database System Concepts - 7th Edition 16.32 ©Silberschatz, Korth and Sudarshan
 Structure of Query Optimizers (Cont.)
 Some query optimizers integrate heuristic selection and the generation of
alternative access plans.
• Frequently used approach
 heuristic rewriting of nested block structure and aggregation
 followed by cost-based join-order optimization for each block
• Some optimizers (e.g. SQL Server) apply transformations to entire
query and do not depend on block structure
• Optimization cost budget to stop optimization early (if cost of plan is
less than cost of optimization)
• Plan caching to reuse previously computed plan if query is
resubmitted
 Even with different constants in query
 Even with the use of heuristics, cost-based query optimization imposes a
substantial overhead.
• But is worth it for expensive queries
• Optimizers often use simple heuristics for very cheap queries, and
perform exhaustive enumeration for more expensive queries

Database System Concepts - 7th Edition 16.33 ©Silberschatz, Korth and Sudarshan
 Statistics for Cost Estimation

Database System Concepts - 7th Edition 16.34 ©Silberschatz, Korth and Sudarshan
 Statistical Information for Cost Estimation
 nr: number of tuples in a relation r.
 br: number of blocks containing tuples of r.
 lr: size of a tuple of r.
 fr: blocking factor of r — i.e., the number of tuples of r that fit into one block.
 V(A, r): number of distinct values that appear in r for attribute A; same as
the size of A(r).
 If tuples of r are stored together physically in a file, then:

Database System Concepts - 7th Edition 16.35 ©Silberschatz, Korth and Sudarshan
 Histograms

 Histogram on attribute age of relation person

50

40

frequency
30

20

10

1–5 6–10 11–15 16–20 21–25

 Equi-width histograms value
 Equi-depth histograms break up range such that each range has
(approximately) the same number of tuples
• E.g. (4, 8, 14, 19)
 Many databases also store n most-frequent values and their counts
• Histogram is built on remaining values only

Database System Concepts - 7th Edition 16.36 ©Silberschatz, Korth and Sudarshan
 Histograms (cont.)

 Histograms and other statistics usually computed based on a random

sample
 Statistics may be out of date
• Some database require a analyze command to be executed to update
statistics
• Others automatically recompute statistics
 e.g., when number of tuples in a relation changes by some
percentage

Database System Concepts - 7th Edition 16.37 ©Silberschatz, Korth and Sudarshan
 Selection Size Estimation

 A=v(r)
• nr / V(A,r) : number of records that will satisfy the selection
• Equality condition on a key attribute: size estimate = 1
 AV(r) (case of A  V(r) is symmetric)
• Let c denote the estimated number of tuples satisfying the condition.
• If min(A,r) and max(A,r) are available in catalog
 c = 0 if v < min(A,r)

 c=

• If histograms available, can refine above estimate

• In absence of statistical information c is assumed to be nr / 2.

Database System Concepts - 7th Edition 16.38 ©Silberschatz, Korth and Sudarshan
 Size Estimation of Complex Selections

 The selectivity of a condition i is the probability that a tuple in the relation

r satisfies i .
• If si is the number of satisfying tuples in r, the selectivity of i is given
by si /nr.
 Conjunction: 1 2. . .  n (r). Assuming independence, estimate of

tuples in the result is:

 Disjunction:1 2 . . .  n (r). Estimated number of tuples:

 Negation: (r). Estimated number of tuples:

nr – size((r))

Database System Concepts - 7th Edition 16.39 ©Silberschatz, Korth and Sudarshan
 Join Operation: Running Example

Running example:
student ⨝ takes
Catalog information for join examples:
 nstudent = 5,000.
 fstudent = 50, which implies that
bstudent =5000/50 = 100.
 ntakes = 10000.
 ftakes = 25, which implies that
btakes = 10000/25 = 400.
 V(ID, takes) = 2500, which implies that on average, each student who has
taken a course has taken 4 courses.
• Attribute ID in takes is a foreign key referencing student.
• V(ID, student) = 5000 (primary key!)

Database System Concepts - 7th Edition 16.40 ©Silberschatz, Korth and Sudarshan
 Estimation of the Size of Joins

 The Cartesian product r x s contains nr .ns tuples; each tuple occupies sr +

ss bytes.
 If R  S = , then r ⋈ s is the same as r x s.
 If R  S is a key for R, then a tuple of s will join with at most one tuple from
r
• therefore, the number of tuples in r ⋈ s is no greater than the number
of tuples in s.
 If R  S in S is a foreign key in S referencing R, then the number of tuples
in r ⋈ s is exactly the same as the number of tuples in s.
 The case for R  S being a foreign key referencing S is symmetric.
 In the example query student ⋈ takes, ID in takes is a foreign key
referencing student
• hence, the result has exactly ntakes tuples, which is 10000

Database System Concepts - 7th Edition 16.41 ©Silberschatz, Korth and Sudarshan
 Estimation of the Size of Joins (Cont.)

 If R  S = {A} is not a key for R or S.

If we assume that every tuple t in R produces tuples in R S, the number
of tuples in R ⨝ S is estimated to be:

If the reverse is true, the estimate obtained will be:

The lower of these two estimates is probably the more accurate one.
 Can improve on above if histograms are available
• Use formula similar to above, for each cell of histograms on the two
relations

Database System Concepts - 7th Edition 16.42 ©Silberschatz, Korth and Sudarshan
 Size Estimation for Other Operations

 Projection: estimated size of A(r) = V(A,r)

 Aggregation : estimated size of G𝛾A(r) = V(G,r)
 Set operations
• For unions/intersections of selections on the same relation: rewrite
and use size estimate for selections
 E.g., 1 (r)  2 (r) can be rewritten as 1 or 2 (r)

• For operations on different relations:

 estimated size of r  s = size of r + size of s.
 estimated size of r  s = minimum size of r and size of s.
 estimated size of r – s = r.
 All the three estimates may be quite inaccurate, but provide upper
bounds on the sizes.

Database System Concepts - 7th Edition 16.43 ©Silberschatz, Korth and Sudarshan
 Size Estimation (Cont.)

 Outer join:
• Estimated size of r ⟕ s = size of r ⨝ s + size of r
 Case of right outer join is symmetric
• Estimated size of r ⟗ s = size of r ⨝ s + size of r + size of s

Database System Concepts - 7th Edition 16.44 ©Silberschatz, Korth and Sudarshan
 End of Chapter

Database System Concepts - 7th Edition 16.45 ©Silberschatz, Korth and Sudarshan