CS 245: Database System Principles Notes 7: Query Optimization Hector Garcia-Molina CS 245 Notes 7 1 Query Optimization --> Generating and comparing plans Query Generate Pruning Plans

x x Estimate Cost Cost Select Pick Min CS 245 Notes 7 2 To generate plans consider: Transforming relational algebra expression (e.g. order of joins)

Use of existing indexes Building indexes or sorting on the fly CS 245 Notes 7 3 Implementation details: e.g. - Join algorithm - Memory management - Parallel processing CS 245 Notes 7

4 Estimating IOs: Count # of disk blocks that must be read (or written) to execute query plan CS 245 Notes 7 5 To estimate costs, we may have additional parameters: B(R) = # of blocks containing R tuples f(R) = max # of tuples of R per block

M = # memory blocks available CS 245 Notes 7 6 To estimate costs, we may have additional parameters: B(R) = # of blocks containing R tuples f(R) = max # of tuples of R per block M = # memory blocks available HT(i) = # levels in index i LB(i) = # of leaf blocks in index i CS 245

Notes 7 7 Clustering index Index that allows tuples to be read in an order that corresponds to physical order 10 A 15 17 A index 19 35

37 CS 245 Notes 7 8 Notions of clustering Clustered file organization R1 R2 S1 S2 R3 R4 S3 S4 .. Clustered relation R1 R2 R3 R4 R5 R5 R7 R8 .. Clustering index CS 245

Notes 7 9 Example attribute C R1 R2 over common T(R1) = 10,000 T(R2) = 5,000 S(R1) = S(R2) = 1/10 block Memory available = 101 blocks

CS 245 Notes 7 10 Example attribute C R1 R2 over common T(R1) = 10,000 T(R2) = 5,000 S(R1) = S(R2) = 1/10 block

Memory available = 101 blocks Metric: # of IOs (ignoring writing of result) CS 245 Notes 7 11 Caution! This may not be the best way to compare ignoring CPU costs ignoring timing ignoring double buffering requirements CS 245

Notes 7 12 Options Transformations: R1 R1 Joint algorithms: CS 245 R2, R2 Iteration (nested loops) Merge join

Join with index Hash join Notes 7 13 Iteration join (conceptually) for each r R1 do for each s R2 do if r.C = s.C then output r,s pair CS 245 Notes 7 14

Merge join (conceptually) (1) if R1 and R2 not sorted, sort them (2) i 1; j 1; While (i T(R1)) (j T(R2)) do if R1{ i }.C = R2{ j }.C then outputTuples else if R1{ i }.C > R2{ j }.C then j j+1 else if R1{ i }.C < R2{ j }.C then i i+1 CS 245 Notes 7 15 Procedure Output-Tuples While (R1{ i }.C = R2{ j }.C) (i T(R1)) do [jj j; while (R1{ i }.C = R2{ jj }.C) (jj T(R2)) do

[output pair R1{ i }, R2{ jj }; jj jj+1 ] i i+1 ] CS 245 Notes 7 16 Example i 1 2 3 4 5

R1{i}.C 10 20 20 30 40 50 52 CS 245 R2{j}.C j 51 202 203 304 305

6 7 Notes 7 17 Join with index (Conceptually) Assume R2.C index For each r R1 do [ X index (R2, C, r.C) for each s X do output r,s pair] Note: X index(rel, attr, value) then X = set of rel tuples with attr = value CS 245

Notes 7 18 Hash join (conceptual) Hash function h, range 0 k Buckets for R1: G0, G1, ... Gk Buckets for R2: H0, H1, ... Hk CS 245 Notes 7 19 Hash join (conceptual) Hash function h, range 0 k Buckets for R1: G0, G1, ... Gk

Buckets for R2: H0, H1, ... Hk Algorithm (1) Hash R1 tuples into G buckets (2) Hash R2 tuples into H buckets (3) For i = 0 to k do match tuples in Gi, Hi buckets CS 245 Notes 7 20 Simple example even/odd R1 R2 Buckets

2 5 Even 44 R1 R2 3 12 Odd: 5 3 8 13 9 8 11 14 CS 245 hash: 248

4 12 8 14 359 5 3 13 11 Notes 7 21 Factors that affect performance (1) Tuples of relation stored physically together? (2) Relations sorted by join attribute? (3) Indexes exist? CS 245

Notes 7 22 Example 1(a) R2 Iteration Join R1 Relations not contiguous Recall T(R1) = 10,000 T(R2) = 5,000 S(R1) = S(R2) =1/10 block MEM=101 blocks CS 245

Notes 7 23 Example 1(a) R2 Iteration Join R1 Relations not contiguous Recall T(R1) = 10,000 T(R2) = 5,000 S(R1) = S(R2) =1/10 block MEM=101 blocks Cost: for each R1 tuple:

[Read tuple + Read R2] Total =10,000 [1+5000]=50,010,000 IOs CS 245 Notes 7 24 Can we do better? CS 245 Notes 7 25

Can we do better? Use (1) (2) (3) our memory Read 100 blocks of R1 Read all of R2 (using 1 block) + join Repeat until done CS 245 Notes 7 26 Cost: for each R1 chunk:

Read chunk: 1000 IOs Read R2: 5000 IOs 6000 CS 245 Notes 7 27 Cost: for each R1 chunk: Read chunk: 1000 IOs Read R2: 5000 IOs 6000

Total = 10,000 x 6000 = 60,000 IOs 1,000 CS 245 Notes 7 28 Can we do better? CS 245 Notes 7 29 Can we do better?

Reverse join order: R2 R1 Total = 5000 x (1000 + 10,000) = 1000 5 x 11,000 = 55,000 IOs CS 245 Notes 7 30 Example 1(b) R1 Iteration Join R2

Relations contiguous CS 245 Notes 7 31 Example 1(b) R1 Iteration Join R2 Relations contiguous Cost For each R2 chunk:

Read chunk: 100 IOs Read R1: 1000 IOs 1,100 Total= 5 chunks x 1,100 = 5,500 IOs CS 245 Notes 7 32 Example 1(c) Merge Join Both R1, R2 ordered by C; relations contiguous Memory R1 R2

CS 245 R1 .. .. Notes 7 R2 33 Example 1(c) Merge Join Both R1, R2 ordered by C; relations contiguous Memory R1

R2 R1 .. .. R2 Total cost: Read R1 cost + read R2 cost = 1000 + = 1,500 IOs CS 245 Notes500 7 34

Example 1(d) Merge Join R1, R2 not ordered, but contiguous --> Need to sort R1, R2 first. HOW? CS 245 Notes 7 35 One way to sort: Merge Sort (i) For each 100 blk chunk of R: ... - Read chunk - Sort in memory

- Write to disk sorted R1 chunks R2 Memory CS 245 Notes 7 36 (ii) Read all chunks + merge + write out CS 245

... Chunks Sorted ... Sorted file Memory Notes 7 37 Cost: Sort Each tuple is read,written, read, written

so... Sort cost R1: 4 x 1,000 = 4,000 Sort cost R2: 4 x 500 = 2,000 CS 245 Notes 7 38 Example 1(d) Merge Join (continued) R1,R2 contiguous, but unordered Total cost = sort cost + join cost = 6,000 + 1,500 = 7,500 IOs CS 245

Notes 7 39 Example 1(d) Merge Join (continued) R1,R2 contiguous, but unordered Total cost = sort cost + join cost = 6,000 + 1,500 = 7,500 IOs But: Iteration cost = 5,500 so merge joint does not pay off! CS 245 Notes 7 40

But say R1 = 10,000 blocks contiguous R2 = 5,000 blocks not ordered Iterate: 5000 x (100+10,000) = 50 x 10,100 100 = 505,000 IOs Merge join: 5(10,000+5,000) = 75,000 IOs Merge Join (with sort) WINS! CS 245 Notes 7 41 How much memory do we need for

merge sort? E.g: Say I have 10 memory blocks R1 CS 245 ... 10 100 chunks to merge, need 100 blocks! Notes 7 42

In general: Say k blocks in memory x blocks for relation sort # chunks = (x/k) size of chunk = k CS 245 Notes 7 43 In general: Say k blocks in memory x blocks for relation sort # chunks = (x/k) size of chunk = k

# chunks < buffers available for merge CS 245 Notes 7 44 In general: Say k blocks in memory x blocks for relation sort # chunks = (x/k) size of chunk = k # chunks < buffers available for merge so... (x/k) k

or k2 x or k x CS 245 Notes 7 45 In our example R1 is 1000 blocks, k 31.62 R2 is 500 blocks, k 22.36 Need at least 32 buffers CS 245 Notes 7 46

Can we improve on merge join? Hint: do we really need the fully sorted files? R1 Join? R2 sorted runs CS 245 Notes 7 47 Cost of improved merge join: C = Read R1 + write R1 into runs

+ read R2 + write R2 into runs + join = 2000 + 1000 + 1500 = 4500 --> Memory requirement? CS 245 Notes 7 48 Example 1(e) Index Join Assume R1.C index exists; 2 levels Assume R2 contiguous, unordered Assume R1.C index fits in memory CS 245

Notes 7 49 Cost: Reads: 500 IOs for each R2 tuple: - probe index - free - if match, read R1 tuple: 1 IO CS 245 Notes 7 50 What is expected # of matching tuples?

(a) say R1.C is key, R2.C is foreign key then expect = 1 (b) say V(R1,C) = 5000, T(R1) = 10,000 with uniform assumption expect = 10,000/5,000 = 2 CS 245 Notes 7 51 What is expected # of matching tuples? (c) Say DOM(R1, C)=1,000,000 T(R1) = 10,000 with alternate assumption

Expect = 10,000 = 1 1,000,000 100 CS 245 Notes 7 52 Total cost with index join (a) Total cost = 500+5000(1)1 = 5,500 (b) Total cost = 500+5000(2)1 = 10,500 (c) Total cost = 500+5000(1/100)1=550 CS 245

Notes 7 53 What if index does not fit in memory? Example: say R1.C index is 201 blocks Keep root + 99 leaf nodes in memory Expected cost of each probe is E = (0)99 + (1)101 0.5 200 200 CS 245 Notes 7 54

Total cost (including probes) = 500+5000 [Probe + get records] = 500+5000 [0.5+2] uniform assumption = 500+12,500 = 13,000 b) CS 245 Notes 7 (case 55 Total cost (including probes)

= 500+5000 [Probe + get records] = 500+5000 [0.5+2] uniform assumption = 500+12,500 = 13,000 (case b) For case (c): = 500+5000[0.5 1 + (1/100) 1] = 500+2500+50 = 3050 IOs CS 245 Notes 7 56

So far not contiguous Iterate R2 R1 55,000 (best) Merge Join _______ Sort+ Merge Join _______ R1.C Index _______ R2.C Index _______ contiguous Iterate R2

R1 5500 Merge join 1500 Sort+Merge Join 7500 4500 R1.C Index 5500 3050 550 R2.C Index ________ CS 245 Notes 7 57 Example 1(f) Hash Join R1, R2 contiguous (un-ordered) Use 100 buckets

Read R1, hash, + write buckets ... ... R1 100 10 blocks CS 245 Notes 7 58 ...

-> Same for R2 -> Read one R1 bucket; build memory hash table -> Read corresponding R2 bucket + hash probe R2 R1 ... R1 memory Then repeat for all buckets CS 245

Notes 7 59 Cost: Bucketize: Read R1 + write Read R2 + write Join: Read R1, R2 Total cost = 3 x [1000+500] = 4500 CS 245 Notes 7

60 Cost: Bucketize: Read R1 + write Read R2 + write Join: Read R1, R2 Total cost = 3 x [1000+500] = 4500 Note: this is an approximation since buckets will vary in size and we have to round up to blocks CS 245 Notes 7 61

Minimum memory requirements: Size of R1 bucket = (x/k) k = number of memory buffers x = number of R1 blocks So... (x/k) < k k > x buffers CS 245 need: k+1 total memory Notes 7 62

Trick: keep some buckets in memory E.g., k=33 R1 buckets = 31 blocks keep 2 in memory memory R1 in G0 ... G1

31 33-2=31 called hybrid hash-join CS 245 Notes 7 63 Trick: keep some buckets in memory E.g., k=33 R1 buckets = 31 blocks keep 2 in memory

memory R1 in Memory use: G0 31 buffers G1 31 buffers Output 33-2 buffers R1 input 1 Total 94 buffers 6 buffers to spare!!

G0 ... G1 31 33-2=31 called hybrid hash-join CS 245 Notes 7 64

Next: Bucketize R2 R2 buckets =500/33= 16 blocks Two of the R2 buckets joined immediately with G0,G1 memory G0 ... G1 16 CS 245 R1 buckets 31

33-2=31 Notes 7 ... R2 in R2 buckets 33-2=31 65 Finally: Join remaining buckets for each bucket pair:

read one of the buckets into memory join with second bucket memory one R1 buffer CS 245 16 R1 buckets 31 33-2=31 Notes 7

... Gi R2 buckets ... ans out one full R2 bucket 33-2=31 66

Cost Bucketize R1 = 1000+3131=1961 To bucketize R2, only write 31 buckets: so, cost = 500+3116=996 To compare join (2 buckets already done) read 3131+3116=1457 Total cost = 1961+996+1457 = 4414 CS 245 Notes 7 67 How many buckets in memory? memory

in R1 memory G0 G1 R1 OR... in G0 ? See textbook for answer...

CS 245 Notes 7 68 Another hash join trick: Only write into buckets pairs When we get a match in join phase, must fetch tuples CS 245 Notes 7 69

To illustrate cost computation, assume: 100 pairs/block expected number of result tuples is 100 CS 245 Notes 7 70 To illustrate cost computation, assume: 100 pairs/block expected number of result tuples is 100 Build hash table for R2 in memory 5000 tuples 5000/100 = 50 blocks Read R1 and match

Read ~ 100 R2 tuples CS 245 Notes 7 71 To illustrate cost computation, assume: 100 pairs/block expected number of result tuples is 100 Build hash table for R2 in memory 5000 tuples 5000/100 = 50 blocks Read R1 and match Read ~ 100 R2 tuples Total cost =

Read R2: Read R1: Get tuples: 500 1000 100 1600 CS 245 Notes 7 72 contiguous So far:

CS 245 Iterate Merge join Sort+merge joint R1.C index R2.C index Build R.C index Build S.C index Hash join with trick,R1 first with trick,R2 first Hash join, pointers Notes 7 5500

1500 7500 5500 550 _____ _____ _____ 4500+ 4414 _____ 1600 73 Summary Iteration ok for small relations (relative to memory size) For equi-join, where relations not

sorted and no indexes exist, hash join usually best CS 245 Notes 7 74 Sort + merge join good for nonequi-join (e.g., R1.C > R2.C) If relations already sorted, use merge join If index exists, it could be useful (depends on expected result size)

CS 245 Notes 7 75 Join strategies for parallel processors Later on. CS 245 Notes 7 76 Chapter 16 [16] summary Relational algebra level

Detailed query plan level Estimate costs Generate plans Join algorithms Compare costs CS 245 Notes 7 77