1 of 16

CSE 444: Database Internals

Section 5:

Query Optimizer

2 of 16

Plan for Today

Problem 1A, 1B: Estimating cost of a plan

You try to compute the cost for 5 mins
We will go over the solution together

Problem 2: Selinger Optimizer

We will do it together

3 of 16

1. Estimating Cost of a given plan

Student (sid, name, age, address)

Book(bid, title, author)

Checkout(sid, bid, date)

Query:

SELECT S.name

FROM Student S, Book B, Checkout C

WHERE S.sid = C.sid

AND B.bid = C.bid

AND B.author = 'Olden Fames'

AND S.age >= 13

AND S.age <= 19

4 of 16

Assumptions

Student: S Book: B Checkout: C

Sid, bid are foreign keys in C referencing S and B.
There are 10,000 Student records stored on 1,000 pages.
There are 50,000 Book records stored on 5,000 pages.
There are 300,000 Checkout records stored on 15,000 pages.
There are 500 different authors.
Student ages range from 7 to 24 uniformly (integers).

S(sid,name,age,addr)

B(bid,title,author)

C(sid,bid,date)

5 of 16

Physical Query Plan – 1A

5

Student S

Checkout C

_sid

(File scan)

(c) σ_13<=age<=19 _{Ʌ author = ‘Olden Fames’}

Compute

the cost and cardinality in steps (a) to (d)
the total cost

Assumptions:

Data is not sorted on any attributes

(a)

B(S)=1,000

B(B)=5,000

B(C)=15,000

T(S)=10,000

T(B)=50,000

T(C)=300,000

S(sid,name,age,addr)

B(bid,title,author)

C(sid,bid,date)

Book B

(File scan)

V(B,author) = 500

7 <= age <= 24

_bid

(Tuple-based nested loop

B inner)

(b)

(d) Π_name

(Block-nested loop,

S outer, C inner)

(On the fly)

6 of 16

Solution – 1A

6

Student S

Checkout C

_sid

(File scan)

(Block-nested loop,

S outer, C inner)

(c) σ_13<=age<=19 _{Ʌ author = ‘Olden Fames’}

(a)

B(S)=1,000

B(B)=5,000

B(C)=15,000

T(S)=10,000

T(B)=50,000

T(C)=300,000

S(sid,name,age,addr)

B(bid,title,author)

C(sid,bid,date)

Book B

(File Scan)

V(B,author) = 500

7 <= age <= 24

(a)

Cost (I/O)

B(S) + B(S) * B(C)

= 1000 + 1000 * 15000

= 15,001,000

Cardinality

= T(S) * T(C)/V(S, sid)

= 300,000 (foreign key join)

(b)

Cost(I/O)

= T(S join C) * B(B)

= 300,000 * 5,000 = 15 * 10⁸

Cardinality

= T(S join C) * T(B)/ V(B, bid))

= 300,000 (foreign key join)

(c, d)

Cost(I/O)

= 0 (on the fly)

Cardinality:

300,000 * 1/500 * 7/18

= 234 (approx)

(assuming uniformity and independence)

_bid

(Tuple-based nested loop

B inner)

(b)

(d) Π_name

(On the fly)

Total cost = 1,515,001,000

Final cardinality = 234 (approx)

7 of 16

Physical Query Plan – 1B

7

Student S

Checkout C

_bid

(Index scan)

(f) σ_13<=age<=19

Compute

the cost and cardinality in steps (a) to (g)
the total cost

Assumptions:

Unclustered B+tree index on

B.author

Clustered B+tree index on C.bid
All index pages are in memory
Unlimited memory

(c)

B(S)=1,000

B(B)=5,000

B(C)=15,000

T(S)=10,000

T(B)=50,000

T(C)=300,000

S(sid,name,age,addr)

B(bid,title,author)

C(sid,bid,date)

Book B

(File scan)

V(B,author) = 500

7 <= age <= 24

_sid

(Block nested loop

S inner)

(e)

(g) Π_name

(Indexed-nested loop,

B outer, C inner)

(a) σ_{author = ‘Olden Fames’}

(b) Π_bid

(d) Π_sid

(On the fly)

8 of 16

Solution – 1B

8

Student S

Checkout C

_bid

(Index scan)

(f) σ_13<=age<=19

(c)

B(S)=1,000

B(B)=5,000

B(C)=15,000

T(S)=10,000

T(B)=50,000

T(C)=300,000

S(sid,name,age,addr)

B(bid,title,author): Un. B+ on author

C(sid,bid,date): Cl. B+ on bid

Book B

(File scan)

V(B,author) = 500

7 <= age <= 24

_sid

(Block nested loop

S inner)

(e)

(g) Π_name

(Indexed-nested loop,

B outer, C inner)

(a) σ_{author = ‘Olden Fames’}

(b) Π_bid

(d) Π_sid

(On the fly)

(a)

cost (I/O)

= T(B) / V(B, author)

= 50,000/500 = 100 (unclustered)

cardinality = 100

(b) Cost = 0

cardinality = 100

(c)

one index lookup per outer B tuple
1 book has 6 checkouts (uniformity)
# C tuples per page = T(C)/B(C) = 20
6 tuples fit in at most 2 consecutive pages (clustered) – or 1 if all fit on the page

Cost = 100 * 2= 200

cardinality = 100 * 6 = 600

(d) Cost =0, cardinality= 600

(e) Outer relation is already in memory,

need to scan S relation

Cost B(S) = 1000

Cardinality = 600

(f) Cost = 0

Cardinality = 600 * 7/18 = 234 (approx)

(g) Cost= 0, cardinality = 234

Total cost = 1300 (compare with 1,515,001,000 in 1A)

Final cardinality = 234 (approx) (same as 1A!)

9 of 16

2. Selinger Optimization Example

Sailors (sid, sname, srating, age)

Boats(bid, bname, color)

Reserves(sid, bid, date, rname)

Query:

SELECT S.sid, R.rname

FROM Sailors S, Boats B, Reserves R

WHERE S.sid = R.sid

AND B.bid = R.bid

AND B.color = red

Example is from the Ramakrishnan book

10 of 16

Available Indexes

Sailors: S Boats: B Reserves: R

Sid, bid foreign key in R referencing S and B resp.
Sailors

Unclustered B+ tree index on sid
Unclustered hash index on sid

Boats

Unclustered B+ tree index on color
Unclustered hash index on color

Reserves

Unclustered B+ tree on sid
Clustered B+ tree on bid

S (sid, sname, srating, age)

B (bid, bname, color)

R (sid, bid, date, rname)

11 of 16

First Pass

Where to start?

How to access each relation, assuming it would be the first relation being read
File scan is also available!

Sailors?

No selection matching an index, use File Scan (no overhead)
unclusted!!!

Reserves?

Same as Sailors

Boats?

Hash index on color, matches B.color = red
B+ tree also matches the predicate, but hash index is cheaper

B+ tree would be cheaper for range queries

S (sid, sname, srating, age): 1. B+tree - sid, 2. hash index - sid

B (bid, bname, color) : 1. B+tree - color, 2. hash index - color

R (sid, bid, date, rname) : 1. B+tree - sid, 2. Clustered B+tree - bid

SELECT S.sid, R.rname

WHERE S.sid = R.sid

B.bid = R.bid, B.color = red

12 of 16

Second Pass

What next?

For each of the plan in Pass 1 taken as outer, consider joining another relation as inner

What are the combinations? How many new options?

S (sid, sname, srating, age): 1. B+tree - sid, 2. hash index - sid

B (bid, bname, color) : 1. B+tree - color, 2. hash index - color

R (sid, bid, date, rname) : 1. B+tree - sid, 2. Clustered B+tree - bid

SELECT S.sid, R.rname

WHERE S.sid = R.sid

B.bid = R.bid, B.color = red

Outer	Inner	OPTION 1	OPTION 2	OPTION 3
R (file scan)	B	(B+-color)	(hash color)	(File scan)
R (file scan)	S	(B+-sid)	(hash sid)	,,
S (file scan)	B	(B+-color)	(hash color)	,,
S (file scan)	R	(B+-sid)	(Cl. B+ bid)	,,
B (hash index)	R	(B+-sid)	(Cl. B+ bid	,,
B (hash index)	S	(B+-sid)	(hash sid)	,,

13 of 16

Second Pass

Which outer-inner combinations can be discarded?

B, S and S, B: Cartesian product!

S (sid, sname, srating, age): 1. B+tree - sid, 2. hash index - sid

B (bid, bname, color) : 1. B+tree - color, 2. hash index - color

R (sid, bid, date, rname) : 1. B+tree - sid, 2. Clustered B+tree - bid

SELECT S.sid, R.rname

WHERE S.sid = R.sid

B.bid = R.bid, B.color = red

Outer	Inner	OPTION 1	OPTION 2	OPTION 3
R (file scan)	B	(B+-color)	(hash color)	(File scan)
R (file scan)	S	(B+-sid)	(hash sid)	,,
S (file scan)	B	(B+-color)	(hash color)	,,
S (file scan)	R	(B+-sid)	(Cl. B+ bid)	,,
B (hash index)	S	(B+-sid)	(hash sid)	,,
B (hash index)	R	(B+-sid)	(Cl. B+ bid):	,,

OPTION 3 is not shown on next slide, expected to be more expensive

14 of 16

S (sid, sname, srating, age): 1. B+tree - sid, 2. hash index - sid

B (bid, bname, color) : 1. B+tree - color, 2. hash index - color

R (sid, bid, date, rname) : 1. B+tree - sid, 2. Clustered B+tree - bid

SELECT S.sid, R.rname

WHERE S.sid = R.sid

B.bid = R.bid, B.color = red

Outer	Inner	OPTION 1	OPTION 2
R (file scan)	S	(B+-sid) Slower than hash-index (need Sailor tuples matching S.sid = value, where value comes from an outer R tuple)	(hash sid): likely to be faster 2A. Index nested loop join 2B Sort Merge based join: (sorted by sid)
R (file scan)	B	(B+-color) Not useful	(hash color) Select those tuples where B.color = red using the color index (note: no index on bid)
S (file scan)	R	(B+-sid) Consider all join methods	(Cl. B+ bid) Not useful
B (hash index)	R	(B+-sid) Not useful	(Cl. B+ bid) 2A. Index nested loop join 2B. Sort-merge join (sorted on bid)

Keep the least cost plan between

(R, S) and (S, R)
(R, B) and (B, R)

15 of 16

Third Pass

Join with the third relation
For each option retained in Pass 2, join with the third relation
E.g.

Boats (B+tree on color) – sort-merged-join – Reserves (B+tree on bid)
Join the result with Sailors (B+ tree on sid) using sort-merge-join

Need to sort (B join R) by sid, was sorted on bid before
Outputs tuples sorted by sid
Not useful here, but will be useful if we had GROUP BY on sid
In general, a higher cost “interesting” plans may be retained (e.g. sort operator at root, grouping attribute in group by query later, join attribute in a later join)

S (sid, sname, srating, age): 1. B+tree - sid, 2. hash index - sid

B (bid, bname, color) : 1. B+tree - color, 2. hash index - color

R (sid, bid, date, rname) : 1. B+tree - sid, 2. Clustered B+tree - bid

SELECT S.sid, R.rname

WHERE S.sid = R.sid

B.bid = R.bid, B.color = red

16 of 16

Homework 3

Query Plan Cost Computation
Query Optimization