CS W186 Exam Prep Section 7

Query Optimization

Query Optimization

Query Optimization

SELECT travelers.name, cities.name

FROM travelers left outer join cities on city_id = dest_id

WHERE cities.name == ‘Berkeley’

ORDER BY cities.name;

​

• Many different orders to perform all these operations
• We use the System R optimizer (aka Selinger optimizer)
• Plan space: only left-deep trees (important!), avoid cartesian products
• Cost estimation: We’ll only use I/O cost for this class (exclude CPU)
• Search algorithm: dynamic programming

Selectivity Estimation

• To estimate the cost of a query, add up the estimated costs of each operator in the query
• Need to know the size of the intermediate relations (generated from one operator and passed into another)
• Need to know the selectivity of predicates - what % of tuples are selected by a predicate
• These are all estimates: if we don’t know, we make up a value for it (selectivity = 1/10)
• System R assume uniform and indep. distribution of values

Included for completeness - don’t memorize, just put on your reference sheet

​

|column| = the number of distinct values for the column

​

Note: If you have an index on the column, you can assume you know |column|, max(c), and min(c)

Selectivity Estimation - Equalities

Selectivity Estimation - Inequalities on Integers

Selectivity Estimation - Inequalities on Integers

Selectivity Estimation - Connectives

Query Optimization - Selinger

• Pass 1: find minimum cost access method for each (relation, interesting order)
• Index scan, full table scans
• Pass i (for 1 < i ≤ n): take in list of optimal plans for (i - 1 relations, interesting order) from Pass i-1, and compute minimum cost plan for (i relations, interesting orders) (every size i subset of the n relations)

Query Optimization Selectivity Order

• Apply single table predicates in the first pass such as WHERE student.age > 3000000000
• Multiple table predicates such as Student.SID = Cs186student.SID take place in subsequent passes

Query Optimization

​

• For n relations joined, perform n passes
• on the i-th path, output only the best plan for joining any i of the n relations
• Also keep around plans that have higher cost but have an interesting order
• This along with only considering left-deep plans forms the crux of most QO questions

Query Optimization - Interesting Orders

• Interesting orders are orderings on intermediate relations that may help reduce the cost of later joins
• ORDER BY attributes
• GROUP BY attributes
• downstream join attributes
• For instance, sort merge join will produce a relation that can help with an ORDER BY clause

Worksheet

Query Optimization 1

Query Optimization 1

Question 1a

Selectivity 1:

​

1/max(25000, 25000) = 1/25000. There are exactly 25000 values in Student.sid, and due to the foreign key, there are at most 25000 values of Application.sid.

Question 1b

Selectivity 2:

​

1/max(500, 500) = 1/500. Similarly to Selectivity 1, there are exactly 500 values in Company.cid, and due to the foreign key, there are at most 500 values in Application.cid.

Question 1c

Selectivity 3:

​

(10 - 6) / (10 - 0 + 1) = 4/11. We have 11 unique values, assumed to be equally distributed. Therefore we use the equation for less than or equal to which is (high key - value) / (high key - low key + 1).

Question 1d

Selectivity 4:

​

(1/130 + (1/10 + 1/500)) - (1/130 * (1/10 + 1/500)). We can find the selectivity that they are an EECS major by using the equation 1/distinct values. Next, we find the selectivity that open positions are less than or equal to 50 using the equation (v - low key) / (high key - low key + 1) + (1 / number distinct). Lastly we combine these two selectivities using S(p1) + S(p2) - S(p1)S(p2) to determine the selectivity of having one or the other.

Question 1e

Selectivity 5:

​

1 - (1/10) = 9/10. Given 10 unique values, the non-negated predicate has selectivity 1/10, so we can use the equation for NOT which is 1 - selectivity of the predicate. The selectivity of the predicate is 1/10 (because there are 10 unique values).

Question 2

For each predicate, which is the first pass of Selinger’s algorithm that uses its selectivity to estimate output size? (Pass 1, 2 or 3?)

​

Solution: Pass 2, Pass 2, Pass 1, Pass 3, Pass 1. C and E are pass 1 because they only involve filtering one table. A and B are pass 2 because they represent a join. Note that (d)—the OR predicate—is over 2 tables that have no associated join predicate, so the selection is postponed along with the cross-product, until after 3-way joins are done

Question 3

Mark the choices for all access plans that would be considered in pass 2 of the Selinger algorithm.

​

A, B, E, and F will be considered because they are not cross products. They are joined on a condition, so some rows can be filtered out, making our intermediate relations smaller.

Question 4

Which choices from the previous question for all access plans would be chosen at the end of pass 2 of the Selinger algorithm?

​

B and F will be chosen because they have the lower cost for joining the two tables, and we have the assumption that our optimizer does not consider interesting orders. (Even if we did, there are no interesting orders in the other joins.)

Question 5

Which plans that would be considered in pass 3?

​

F and H only. A-E can be immediately discarded because they aren’t left-deep. G won’t be considered because we chose (Company ⋈ Application) in pass 2. Similarly, choice I wouldn’t be considered because we choose Application ⋈ Student in the previous pass. Choice J wouldn’t be considered because there is no join condition on Student and Company, so this is a cross-join, which we avoid since we have other options.

Question 6

Which choice from the previous question for all plans would be chosen at the end of pass 3?

​

F, since F has the lower I/O cost between F and H.

Query Optimization 2

Query Optimization 2.1

True or False: When evaluating potential query plans, the set of left deep join plans are always guaranteed to contain the best plan

​

False: this is a heuristic that System R uses to shrink the search space

Query Optimization 2.1

True or False: As a heuristic, the System R optimizer avoids cross-products if possible

​

True

Query Optimization 2.1

True or False: A plan can result in an interesting order if it involves a sort-merge join

True: Sort-merge join leaves the joined tables in a sorted order which may be useful for future passes and/or if the query includes an ORDER BY clause

Query Optimization 2.1

True or False: The System R algorithm is greedy because for each pass, it only keeps the lowest cost plan for each combination of tables

False: it is not greedy because it keeps track of interesting orders which may not be the lowest cost plan, but may result in a lower cost plan in future passes (hence the use of dynamic programming)

Query Optimization 2.2

Assuming that (a) System R assumptions about uniformity and independence from lecture hold, and � (b) Primary key IDs are sequential, starting from 1

What is the selectivity of each predicate in the WHERE clause of the following query?

​

Query Optimization 2.2

Assuming that (a) System R assumptions about uniformity and independence from lecture hold, and � (b) Primary key IDs are sequential, starting from 1

What is the selectivity of each predicate in the WHERE clause of the following query?

​

F.to_id = C.id

50k tuples in City table, C.id is a PK and F.to_id is an FK, so there are 50k unique values of each. Apply formula (1 / MAX(nkeys(tab1), nkeys(tab2)))

= 1 / MAX(50k, 50k) = 1 / 50000

Query Optimization 2.2

Assuming that (a) System R assumptions about uniformity and independence from lecture hold, and � (b) Primary key IDs are sequential, starting from 1

What is the selectivity of each predicate in the WHERE clause of the following query?

​

F.aid = A.aid

5k tuples in Airline table, A.aid is PK, F.aid is FK so there are 5k values of each. Apply same formula as before:

= 1 / MAX(5k, 5k) = 1 / 5000

Query Optimization 2.2

Assuming that (a) System R assumptions about uniformity and independence from lecture hold, and � (b) Primary key IDs are sequential, starting from 1

What is the selectivity of each predicate in the WHERE clause of the following query?

​

F.aid >= 2500

5k values of F.aid (it is a PK for table of 5k tuples); values are 1-5000, so we can apply adjusted “>=” formula:

(High(col)-value)/(High(col)-Low(col) + 1) + 1/High(col)

= (5000 - 2500)/(5000-1+1) + 1/5000

= 2501/5000

Query Optimization 2.2

Assuming that (a) System R assumptions about uniformity and independence from lecture hold, and � (b) Primary key IDs are sequential, starting from 1

What is the selectivity of each predicate in the WHERE clause of the following query?

​

C.population > 5e6

Use range given in description of City table and apply formula for “>”:

(High(col)-value)/(High(col)-Low(col) + 1) + 1/High(col)

= (8e6 - 5e6)/(8e6-1e6 + 1)

= 3e6/(7e6 + 1)

= 3000000/7000001

​

Query Optimization 2.2

Assuming that (a) System R assumptions about uniformity and independence from lecture hold, and � (b) Primary key IDs are sequential, starting from 1

What is the selectivity of each predicate in the WHERE clause of the following query?

​

C.state = ‘California’

There are 50 states, so

= 1/50

​

Query Optimization 2.3

Assuming that (a) System R assumptions about uniformity and independence from lecture hold, and � (b) Primary key IDs are sequential, starting from 1� (c) Optimizer hasn’t discarded rows� (d) B+ trees are of height 2

Fill in each blank in the dynamic programming table for a System R Pass 1

​

Query Optimization 2.3

Assuming that (a) System R assumptions about uniformity and independence from lecture hold, and � (b) Primary key IDs are sequential, starting from 1� (c) Optimizer hasn’t discarded rows� (d) B+ trees are of height 2

Fill in each blank in the dynamic programming table for a System R Pass 1

​

2 I/Os (read root, inner page of index)

+ (20 + 100k) (read 20 pg of index, 100k reads for unclustered)

* <selectivity factor for F.aid >= 2500 (R3)

50032

Query Optimization 2.3

Assuming that (a) System R assumptions about uniformity and independence from lecture hold, and � (b) Primary key IDs are sequential, starting from 1� (c) Optimizer hasn’t discarded rows� (d) B+ trees are of height 2

Fill in each blank in the dynamic programming table for a System R Pass 1

​

20 I/Os (no index used, just read the pages)

50032

Query Optimization 2.3

Assuming that (a) System R assumptions about uniformity and independence from lecture hold, and � (b) Primary key IDs are sequential, starting from 1� (c) Optimizer hasn’t discarded rows� (d) B+ trees are of height 2

Fill in each blank in the dynamic programming table for a System R Pass 1

​

2 I/Os (read root, inner node of index)

+ (10 + 20) (read 10 pages of index, 20 pages of data)

* <selectivity factor for C.population > 5e6>

50032

15

Query Optimization 2.4

After pass 2, which of the following plans could be in the dynamic programming table?

1. City [Index(III)] JOIN Airline [File scan]
2. City [Index(III)] JOIN Flight [Index(I)]
3. Flight [Index(II)] JOIN City [Index(III)]

15

50032

Query Optimization 2.4

After pass 2, which of the following plans could be in the dynamic programming table?

1. City [Index(III)] JOIN Airline [File scan] No: no condition joins City, Airline so this would be a cross product
2. City [Index(III)] JOIN Flight [Index(I)]
3. Flight [Index(II)] JOIN City [Index(III)]

15

50032

Query Optimization 2.4

After pass 2, which of the following plans could be in the dynamic programming table?

1. City [Index(III)] JOIN Airline [File scan] No: no condition joins City, Airline so this would be a cross product
2. City [Index(III)] JOIN Flight [Index(I)] Yes: City[Index(III)] kept for lowest cost, Flight [Index(I)] kept b.c. interesting order
3. Flight [Index(II)] JOIN City [Index(III)]

15

50032

Query Optimization 2.4

After pass 2, which of the following plans could be in the dynamic programming table?

1. City [Index(III)] JOIN Airline [File scan] No: no condition joins City, Airline so this would be a cross product
2. City [Index(III)] JOIN Flight [Index(I)] Yes: City[Index(III)] kept for lowest cost, Flight [Index(I)] kept b.c. interesting order
3. Flight [Index(II)] JOIN City [Index(III)] No: Flight[Index(II)] would not be kept from Pass 1; it is more expensive than full scan� and has no interesting orders

15

50032

Query Optimization 2.5

Suppose we want to optimize for queries similar to the query below; which of the following suggestions could reduce I/O cost?

1. Change Index(III) to be unclustered�
2. Store City as a sorted file on population

Query Optimization 2.5

Suppose we want to optimize for queries similar to the query below; which of the following suggestions could reduce I/O cost?

1. Change Index(III) to be unclustered: Won’t reduce I/O cost. Unclustered index results in more random � accesses so we might load a page more than once
2. Store City as a sorted file on population

Query Optimization 2.5

Suppose we want to optimize for queries similar to the query below; which of the following suggestions could reduce I/O cost?

1. Change Index(III) to be unclustered: Won’t reduce I/O cost. Unclustered index results in more random � accesses so we might load a page more than once
2. Store City as a sorted file on population: Could reduce I/O cost by making range lookups � (e.g. population > 5e6) more efficient

Attendance Link

​

https://cs186berkeley.net/attendance