Query Processing

Database System Concepts, 7th Ed.

©Silberschatz, Korth and Sudarshan
See www.db-book.com for conditions on re-use
 Basic Steps in Query Processing

1. Parsing and translation

2. Optimization
3. Evaluation

Database System Concepts - 7th Edition 15.2 ©Silberschatz, Korth and Sudarshan
 Basic Steps in Query Processing (Cont.)

 Parsing and translation

• translate the query into its internal form. This is then translated into
relational algebra.
• Parser checks syntax, verifies relations
 Evaluation
• The query-execution engine takes a query-evaluation plan,
executes that plan, and returns the answers to the query.

Database System Concepts - 7th Edition 15.3 ©Silberschatz, Korth and Sudarshan
 Basic Steps in Query Processing:
Optimization
 A relational algebra expression may have many equivalent expressions
• E.g., salary75000(salary(instructor)) is equivalent to
salary(salary75000(instructor))
 Each relational algebra operation can be evaluated using one of several
different algorithms
• Correspondingly, a relational-algebra expression can be evaluated in
many ways.
 Annotated expression specifying detailed evaluation strategy is called an
evaluation-plan. E.g.,:
• Use an index on salary to find instructors with salary < 75000,
• Or perform complete relation scan and discard instructors with salary
 75000

Database System Concepts - 7th Edition 15.4 ©Silberschatz, Korth and Sudarshan
 Basic Steps: Optimization (Cont.)

 Query Optimization: Amongst all equivalent evaluation plans choose

the one with lowest cost.
• Cost is estimated using statistical information from the
database catalog
 e.g.. number of tuples in each relation, size of tuples, etc.

Database System Concepts - 7th Edition 15.5 ©Silberschatz, Korth and Sudarshan
 Measures of Query Cost

 Many factors contribute to time cost

• disk access, CPU, and network communication
 Cost can be measured based on
• response time, i.e. total elapsed time for answering query, or
• total resource consumption
 We use total resource consumption as cost metric
• Response time harder to estimate, and minimizing resource
consumption is a good idea in a shared database
 We ignore CPU costs for simplicity
• Real systems do take CPU cost into account
• Network costs must be considered for parallel systems
 We describe how estimate the cost of each operation
• We do not include cost to writing output to disk

Database System Concepts - 7th Edition 15.6 ©Silberschatz, Korth and Sudarshan
 Measures of Query Cost

 Disk cost can be estimated as:

• Number of seeks * average-seek-cost
• Number of blocks read * average-block-read-cost
• Number of blocks written * average-block-write-cost
 For simplicity we just use the number of block transfers from disk and
the number of seeks as the cost measures
• tT – time to transfer one block
 Assuming for simplicity that write cost is same as read cost
• tS – time for one seek
• Cost for b block transfers plus S seeks
b * tT + S * tS
 tS and tT depend on where data is stored; with 4 KB blocks:
• High end magnetic disk: tS = 4 msec and tT =0.1 msec
• SSD: tS = 20-90 microsec and tT = 2-10 microsec for 4KB

Database System Concepts - 7th Edition 15.7 ©Silberschatz, Korth and Sudarshan
 Evaluation of Expressions

 Alternatives for evaluating an entire expression tree

• Materialization: generate results of an expression whose inputs
are relations or are already computed, materialize (store) it on
disk. Repeat.
• Pipelining: pass on tuples to parent operations even as an
operation is being executed
 We study above alternatives in more detail

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

 Materialized evaluation: evaluate one operation at a time, starting at

the lowest-level. Use intermediate results materialized into temporary
relations to evaluate next-level operations.
 E.g., in figure below, compute and store
 building "Watson " (department )
then compute the store its join with instructor, and finally compute the
projection on name.

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

 Pipelined evaluation: evaluate several operations simultaneously,

passing the results of one operation on to the next.
 E.g., in previous expression tree, don’t store result of
 building "Watson " (department )
• instead, pass tuples directly to the join.. Similarly, don’t store result of
join, pass tuples directly to projection.
 Much cheaper than materialization: no need to store a temporary relation
to disk.
 Pipelining may not always be possible – e.g., sort, hash-join.
 For pipelining to be effective, use evaluation algorithms that generate
output tuples even as tuples are received for inputs to the operation.

Database System Concepts - 7th Edition 15.10 ©Silberschatz, Korth and Sudarshan
 Query Optimization

Database System Concepts, 7th Ed.

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

 Alternative ways of evaluating a given query

• Equivalent expressions
• Different algorithms for each operation

Database System Concepts - 7th Edition 15.12 ©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 15.13 ©Silberschatz, Korth and Sudarshan
 Generating Equivalent Expressions

Database System Concepts - 7th Edition 15.14 ©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 15.15 ©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 15.16 ©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 15.17 ©Silberschatz, Korth and Sudarshan
 Pictorial Depiction of Equivalence Rules

Database System Concepts - 7th Edition 15.18 ©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 15.19 ©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 15.20 ©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 15.23 ©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 15.24 ©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 15.25 ©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 15.26 ©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 15.27 ©Silberschatz, Korth and Sudarshan