Query Execution

Werner Nutt

Introduction to Databases

Free University of Bozen-Bolzano

Example Database
2

Our example queries will

be based on the relations
Sailors and Reserves
sid sname rating age
• Sailors:
22 Dustin 7 45.0
Each tuple 50 bytes long S=
31 Lubber 8 55.5
80 tuples per page 58 Rusty 10 35.0
500 pages
• Reserves: sid bid day rcode
Each tuple 40 bytes long R= 22 101 10/10/96 Hoho
100 tuples per page 58 103 11/12/96 007
1000 pages

Introduction to Databases Werner Nutt Free University of Bozen-Bolzano

 Query Processor: Architecture
3

Query

Query Parser

Parsed Query

Query Optimizer

Plan Plan Cost Catalog

Generator Estimator Manager

Evaluation Plan

Query Plan Evaluator

Queries are parsed, optimized, evaluated

Introduction to Databases Werner Nutt Free University of Bozen-Bolzano

Query Parser
4

SELECT [Link] sname

FROM Reserves R, Sailors S

WHERE [Link] = [Link] AND bid=100 rating > 5
[Link] = 100 AND
[Link] > 5

sid=sid

Reserves Sailors

Parser creates relational algebra expression of the form

πAttributes (σConditions (R1 1 · · · 1 Rn ))

i.e., first join, then select, then project

Introduction to Databases Werner Nutt Free University of Bozen-Bolzano

 Plan Generator
5

The Plan Generator

• generates a set of equivalent algebra expressions
• annotates the operators with procedures to compute them.
Example:
(On−the−fly)
sname

bid=100 rating > 5 (On−the−fly)

(Simple Nested Loop Join)

sid=sid

Reserves Sailors

Introduction to Databases Werner Nutt Free University of Bozen-Bolzano

The Cost of Plans

6

The optimizer
• estimates for each generated plan the cost,
• then chooses the cheapest plan
Important: Avoid the worst plans!

We will study
1. first, implementations of operators,
2. then, plans that combine operator implementations.

Introduction to Databases Werner Nutt Free University of Bozen-Bolzano

 Relational Operators
7

We will consider how to implement:

• Selection “σ”: selects a subset of rows from relation
• Projection “π”: deletes unwanted columns from relation
• Join “1”: allows us to combine two relations

Each operator returns a relation ; operators can be composed!

First cover operator, then discuss how to optimize queries

formed by composing them.

Introduction to Databases Werner Nutt Free University of Bozen-Bolzano

What is the Cost of an Operator Implementation?

8

Two parameters:

• Time: How many I/O operations are needed? Depends on

– #pages of input relations
– #records per page
– existence of index etc.
• Result Size: What is the size of the result? Factors as above plus
– selectivity of conditions in a selection or join
– size of attributes projected out
Usually expressed as a “reduction factor”
Both are combined to estimate overall cost of an evaluation plan

Introduction to Databases Werner Nutt Free University of Bozen-Bolzano

 Simple Selections
9

SELECT *
FROM Reserves R
WHERE [Link] < ’C%’

General form σR.A op Val (R)

Assumption: M pages of R, pR tuples per page

• Size of result approximated as: (size of R) × (reduction factor)
• No index, unsorted: Relation scan ; cost is M (= #pages in R)
• With index on selection attribute:
Use index to find qualifying data entries,
then retrieve corresponding data records.
(Hash index useful only for equality selections.)

Introduction to Databases Werner Nutt Free University of Bozen-Bolzano

Using an Index for Selections

10

Cost depends on #qualifying tuples, and clustering:

Cost of finding qualifying data entries (typically small)
+
Cost of retrieving records (could be large w/o clustering)

Example: Uniform distribution of code names

; ≈ 10% of tuples qualify (100 pages, 10,000 tuples)
clustered index ; cost ≈ 100 IO’s
unclustered index ; cost up to 10,000 IO’s !

Introduction to Databases Werner Nutt Free University of Bozen-Bolzano

 Using an Index for Selections: Refinement
11

Important refinement for unclustered indexes:

1. Find qualifying data entries
2. Sort the rid’s of the data records to be retrieved
3. Fetch rid’s in order.

This ensures that each data page is looked at just once

(though # of such pages likely to be higher than with clustering).

Introduction to Databases Werner Nutt Free University of Bozen-Bolzano

More General Selection Conditions

12

(day<8/9/94 AND rcode=’Hiho’) OR bid=5 OR sid=3

• Each disjunct (i.e, part connected by OR) is processed separately,

. . . then the union is taken of the results.

• An index matches (a conjunction of) conditions

if they involve only attributes in a prefix of the search key, and
if all, but possibly the last, are involved in equality conditions
– E.g., index on a, b, c
matches a=5 AND b=3
but not b=3

Introduction to Databases Werner Nutt Free University of Bozen-Bolzano

 First Approach to General Selection
13

Find the most selective access path,

retrieve tuples using it, and
apply any remaining terms that don’t match the index

• Most selective access path: An index or file scan that we estimate will
require the fewest page I/O’s.
• Conditions that match this index reduce the number of tuples retrieved
• Other terms are used to discard some retrieved tuples,
but do not affect number of tuples/pages fetched.

Example: day<8/9/94 AND bid=5 AND sid=3

• First B+-tree index on day, then check bid=5 and sid=3, or
• First hash-based index on bid, sid then check day<8/9/94

Introduction to Databases Werner Nutt Free University of Bozen-Bolzano

Second Approach: Intersection of Rid’s

14
Applicable if we have 2 or more matching indexes that use
Alternatives (2) or (3) for data entries

Using each matching index, get sets of rid’s

Intersect these sets of rid’s (; How?)
Retrieve the records and apply any remaining terms

Example: day < 8/9/94 AND bid=5 AND sid = 3

Assumption: B+-tree index on day and hash-based index on sid

(both using Alternative (2))

– using the B+-tree, get rid’s of records satisfying day<8/9/94

– using the hash-based index, get rid’s satisfying sid=3
– intersect, retrieve records and check bid=5

Introduction to Databases Werner Nutt Free University of Bozen-Bolzano

 A Useful Technique: External Sorting
15

Example: 2-Way External Sorting with 3 Buffers

• Pass 0: Read a page, sort it, write it
– only one buffer page is used
• Pass 1, 2, 3, . . . , etc.
– three buffer pages used.

INPUT 1

OUTPUT

INPUT 2

Disk Main memory buffers Disk

Generalisations use more buffers

Introduction to Databases Werner Nutt Free University of Bozen-Bolzano

2-Way External Sorting: Example

16

• Each pass we read and 3,4 6,2 9,4 8,7 5,6 3,1 2 Input file
PASS 0
write each page in file 3,4 2,6 4,9 7,8 5,6 1,3 2 1−page ‘run’s
PASS 1

• M pages in the file 2,3 4,7 1,3

2−page ‘run’s
4,6 8,9 5,6 2

⇒ number of passes PASS 2

2,3
≈ log2 M 4,4 1,2 4−page ‘run’s
6,7 3,5

• Total cost is 8,9 6

PASS 3

≈ M × log2 M 1,2
2,3
• Idea: Divide and conquer 3,4
8−page ‘run’s
4,5
i.e., sort subfiles and merge 6,6
7,8
9

Introduction to Databases Werner Nutt Free University of Bozen-Bolzano

 General External Merge Sort
17

More than 3 buffer pages. How can we utilize them?

To sort a file with N pages using B buffer pages:

– Pass 0: use B buffer pages;
produce N/B sorted runs of B pages each
– Pass 1, 2,. . . , etc.: merge B − 1 runs

INPUT 1

INPUT 2
OUTPUT

INPUT B−1
Disk Disk
B main memory buffers

Introduction to Databases Werner Nutt Free University of Bozen-Bolzano

Cost of External Merge Sort

18

 
• Number of passes: 1 + logB−1 N/B

• Cost = 2N × #passes

Example: Sort 108 page file with 5 buffer pages

Pass 0: 108/5 = 22 sorted runs of 5 pages each
(last run is only 3 pages)
Pass 1: 22/4 = 6 sorted runs of 20 pages each
(last run is only 8 pages)
Pass 2: 2 sorted runs, 80 pages and 28 pages
Pass 3: Sorted file of 108 pages

Introduction to Databases Werner Nutt Free University of Bozen-Bolzano

 Number of Passes of External Merge Sort
19

N B=3 B=5 B=9 B = 17 B = 129 B = 257

100 7 4 3 2 1 1
1,000 10 5 4 3 2 2
10,000 13 7 5 4 2 2
100,000 17 9 6 5 3 3
1,000,000 20 10 7 5 3 3
10,000,000 23 12 8 6 4 3
100,000,000 26 14 9 7 4 4
1,000,000,000 30 15 10 8 5 4

Introduction to Databases Werner Nutt Free University of Bozen-Bolzano

Sorting: Summary
20

• External sorting is important:

DBMS may dedicate part of buffer pool for sorting!
• External merge sort minimizes disk I/O cost:
– Pass 0: produces sorted runs of size B ( = #buffer pages).
Later passes: merge runs.
– #runs merged at a time depends on B
– In practice, #passes rarely more than 2 or 3

Introduction to Databases Werner Nutt Free University of Bozen-Bolzano

 The Projection Operator
21

SELECT DISTINCT [Link], [Link]

FROM Reserves R

Approach based on sorting

• Modify Pass 0 of external sort to eliminate unwanted fields
; tuples in runs are smaller than input tuples
• Modify merging passes to eliminate duplicates
; number of result tuples smaller than input
• Cost
– Pass 0: read original relation (size M pages),
write out same number of smaller tuples
– In merging passes: fewer tuples written out in each pass

Introduction to Databases Werner Nutt Free University of Bozen-Bolzano

Discussion of Projection
22

• Sort-based approach is the standard

. . . but there are also hash-based techniques

• If an index contains all wanted attributes in its search key ,

do an index-only scan.
– Apply projection techniques to data entries (much smaller!)

• If a tree-based (i.e., ordered) index contains all wanted attributes

as prefix of search key, do even better:
– Retrieve data entries in order (index-only scan),
– Discard unwanted fields,
– Compare adjacent tuples to check for duplicates.

Introduction to Databases Werner Nutt Free University of Bozen-Bolzano

 Equality Joins With One Join Column
23

SELECT *
FROM Reserves R, Sailors S
WHERE [Link] = [Link]

• In algebra: R 1 S. Common! Must be carefully optimized

R × S is large ; R × S followed by selection is inefficient
• Assume: M pages of R, pR tuples per page,
N pages of S, pS tuples per page.
• In examples, R is Reserves and S is Sailors
• Cost metric: # of I/O’s

Introduction to Databases Werner Nutt Free University of Bozen-Bolzano

Simple Nested Loops Join

24

foreach tuple r in R do
foreach tuple s in S do
if ri = sj then add r, s to result

• For each tuple in the outer relation R

we scan the entire inner relation S
– Cost: M + pR × M × N = 1000 + 100 × 1000 × 500 I/O’s.

Page-oriented Nested Loops join:

• For each page of R, get each page of S,
and write out matching pairs of tuples r, s
where r is in R-page and s is in S-page.
– Cost: M + M × N = 1000 + 1000 × 500 I/O’s.

Introduction to Databases Werner Nutt Free University of Bozen-Bolzano

 Index Nested Loops Join: Idea
25

R 1R.i = S.j S !

Suppose, there is an index on attribute j of S

; make S inner relation of nested loops join
; exploit index!

foreach tuple r in R do
foreach tuple s in S where ri = sj do
add r, s to result

Introduction to Databases Werner Nutt Free University of Bozen-Bolzano

Cost of Index Nested Loops Join

26

Overall cost is

M + (M × pR × cost of finding matching tuples in S)

What is the “cost of finding matching tuples in S”?

• For each tuple in R, probe into S-index
– hash index: ≈ 1.2 I/O
– B+-tree: 2–4 I/O’s
• Then, retrieve all matching S-tuples
– clustered index: 1 I/O typically
– unclustered: up to 1 I/O per tuple

Introduction to Databases Werner Nutt Free University of Bozen-Bolzano

 Block Nested Loops Join
27

Why keep only one page of R in buffer? Better:

• one page as input buffer for scanning the inner S
• one page as the output buffer
• all remaining pages hold block of outer R
Relations R and S Join Result

Hash table for block R l

(k =< B−2 pages)

Input buffer Output buffer

(to scan all of S)

Disk B main memory buffers Disk

For each matching tuple r in R-block, s in S-page,

add r, s to result.
Then read next R-block, scan S, etc.

Introduction to Databases Werner Nutt Free University of Bozen-Bolzano

Sort-Merge Join (1)

28

R 1R.i = S.j S !

Idea: Sort R on R.i and S on S.j

then scan R and S to do a “merge” on join colums
. . . and output result tuples

After sorting, how do we find the next pair of matching tuples?

while (R.i = S.j)
{while (R.i < S.j) Under
advance scan of R; which assumption
while (R.i > S.j) is this code
advance scan of S;} correct?

Introduction to Databases Werner Nutt Free University of Bozen-Bolzano

 Sort-Merge Join (2)
29

At this point: (R.i = S.j)

From here on,

• all R tuples with the same value in R.i (the current R group)
• and all S tuples with same value in S.j (the current S group)
match!
; output r, s for all pairs of such tuples!
Then resume scanning R and S

Total cost: sorting (R) + sorting (S) + M + N

Introduction to Databases Werner Nutt Free University of Bozen-Bolzano

Hash Join: Principles

30

Two phases

• Partitioning (or “building”): Each of R and S are divided into

partitions R1 , . . . , Rk and S1 , . . . , Sk , using a hash function h

• Probing (or “matching”): Tuples in Ri and Si are matched using a

different hash function h2

Introduction to Databases Werner Nutt Free University of Bozen-Bolzano

 Hash Join: Partitioning
31

Partition R and S using a hash function h

⇒ R tuples in partition i will only match S tuples in partition i

Original Relation Partitions

OUTPUT 1 1
INPUT
2 2
hash
function
h

B−1 B−1

Disk B main memory buffers Disk

Introduction to Databases Werner Nutt Free University of Bozen-Bolzano

Hash Join: Probing

32

• Read in a partition of R, hash it using h2 ( = h!)

• Scan matching partition of S, search for matches

Partitions Join Result

of R and S
hash
function
h2

h2 Hash table for partition Ri

(k < B−1 pages)

Input buffer Output buffer

(To scan Si)

B main memory buffers Disk

Disk

Introduction to Databases Werner Nutt Free University of Bozen-Bolzano

 How Much Buffer Space Do We Need?
33

Constraints:
• k (= # partitions) ≤ B − 1
• size of largest partition to be held in memory ≤ B − 2
Assumption: all partitions have equal size. Then:
√
• k =B−1 and M/(B − 1) ≤ B − 2 ⇒ B≥ M

Optimisation: Use an in-memory hash to compute matching tuples

⇒ more memory is needed

Possible Problem: The hash function does not partition uniformly

⇒ one or more R partitions may not fit into memory
Solution: Apply hash-join technique recursively
to join this R-partition with corresponding S-partition

Introduction to Databases Werner Nutt Free University of Bozen-Bolzano

Hash Join: Analysis

34

Cost:
• Partitioning phase: read and write both R and S ⇒ 2(M + N ) I/Os
• Probing phase: read both R and S ⇒ M + N I/Os
• In the running example: 4500 I/Os in total

Sort-Merge Join vs. Hash Join

• Both have cost of 3(M + N ) I/Os if sufficient(?) memory is available
• Hash Join is superior if relation sizes differ greatly
(proof needs some assumptions about internal sorting method)
• Hash Join can be parallelized
• Sort-Merge is less sensitive to data skew

Introduction to Databases Werner Nutt Free University of Bozen-Bolzano

 Query Optimization: Example
35

sname

SELECT [Link]
bid=100 rating > 5
FROM Reserves R, Sailors S
WHERE [Link] = [Link] AND
[Link] = 100 AND
sid=sid
[Link] > 5

Reserves Sailors

• Cost of this plan: 500 + 500 × 1000 I/O’s

• Missed opportunities:
– selections have not been “pushed”
– no indexes are used

Introduction to Databases Werner Nutt Free University of Bozen-Bolzano

Alternative Plans: No Indexes

36

Main difference: sname

(On−the−fly)

selections pushed down

(Sort−Merge Join)
sid=sid

(Scan; (Scan;
write to bid=100 rating > 5 write to
temp T1) temp T2)
Cost of plan
(with 5 buffers): Reserves Sailors

scan Reserves (1, 000 pages)

+ write temporary T1 (10 pages, if #boats = 100 and uniform distribution)
scan Sailors (500 pages)
+ write temporary T2 (250 pages, if #ratings = 10)
sort T1 (2 × 2 × 10 I/O’s) + sort T2 (2 × 4 × 250 I/O’s)
+ merge T1 and T2 (10 + 250 I/O’s)

4, 060 page I/O’s

Introduction to Databases Werner Nutt Free University of Bozen-Bolzano

 Alternative Plan with Indexes
37

With clustered index on bid of Reserves:

100, 000/100 = 1, 000 tuples on 1, 000/100 = 10 pages (On−the−fly)
sname

Index nested loops join with “pipelining”

(i.e., outer relation is not materialized rating > 5 (On−the−fly)
; projection doesn’t help)

Join attribute sid is a key for Sailors (Index Nested Loops,

with pipelining )
sid=sid
at most one tuple in Sailors matches
; clustering wouldn’t help)
bid=100 Sailors

Selection σrating>5 is not pushed

Use index;
because join is based on index for sid Reserves do not write
result to
temp)

Introduction to Databases Werner Nutt Free University of Bozen-Bolzano

Alternative Plan with Indexes (Cntd.)

38

Cost:
(On−the−fly)
• Selection of Reserves tuples: 10 I/O’s sname

• For each, retrieve matching tuples from rating > 5 (On−the−fly)

Sailors: 1, 000 × 1.2 I/O’s

(Index Nested Loops,
• Total: 1, 210 I/O’s sid=sid
with pipelining )

bid=100 Sailors

Use index;
Reserves do not write
result to
temp)

Introduction to Databases Werner Nutt Free University of Bozen-Bolzano

 Summary
39

• Query optimization (QO) is an important task in a relational DBMS

• Understanding of QO is necessary to understand the impact
; of a given database design (relations, indexes)
; on the workload (= set of queries)
• QO has two parts:
– Enumeration of alternative plans
; pruning of search space: left-deep plans only
– Estimation of cost of enumerated plans
; size of results
; cost of each plan node
Key issues: Statistics, indexes, operator implementations

Introduction to Databases Werner Nutt Free University of Bozen-Bolzano

References
40

These slides are based on Chapters 12, 13, 14, and 15 of the book
Database Management Systems by R. Ramakrishnan and J. Gehrke, and
on slides by the authors published at
[Link]/~dbbook/openAccess/thirdEdition/slides/[Link]

Introduction to Databases Werner Nutt Free University of Bozen-Bolzano