Oregon State UniversityPractice problems Query Optimization
CS 540, Winter 2021
1: Query Optimization
Consider the following relational schema and SQL query: Suppliers(sid,sname,address,category)
Supply(sid,pid)
Parts(pid,pname,brand)
SELECT S.sname, P.pname
FROM Suppliers S, Parts P, Supply Y
WHERE sS.sid = Y.sid AND Y.pid = P.pid
1. Give two examples of join orderings that System R will not consider.
Solution:
System R optimizer does not consider join orderings that require the computation of cross-products to calculate this join. Further, it considers only left-deep joins. The followings are two join orderings that are not left-deep and/or contain Cartesian product.
• P ◃▹ (S ◃▹ Y) (right-deep join)
• (S ◃▹ P) ◃▹ Y (Cartesian product)
2. Enumerate all joins orderings that System R optimizer considers.
Solution:
System R optimizer does not consider join orderings that require the computation of cross-products to calculate this join. Further, it considers only left-deep joins. Thus, ot considers the following join orderings:
• (S ◃▹ Y) ◃▹ P • (Y ◃▹ S) ◃▹ P • (P ◃▹ Y) ◃▹ S • (Y ◃▹ P) ◃▹ S
2: Query Optimization
Consider relations R(A,B) and S(B,C). Assume that R contains 2,000 tuples, and that s contains 5,000 tuples. We want to compute the equi-join R ◃▹ S over attribute B.
1. Without any further assumptions, what is the maximum number of tuples that the resulting relation may contain?
Solution:
The join will have the maximum number of tuples if all values of attribute B in R and S have equal values, therefore, the maximum number of tuples is 2000 × 5000 = 10,000,000.
1
Oregon State UniversityPractice problems Query Optimization CS 540, Winter 2021
2. Now assume that we know that the number of distinct values of B in R is 500. What is now a reasonable estimate on the size of join?
Solution: 2000 × 5000 / 500 = 20,000.
3. Finally, assume we know that B is a primary key in S. What is now a reasonable estimate
on the size of join?
Solution:
If B is the primary key of S, it will have 5,000 distinct values in S. Hence, the size of join will be:
2000 × 5000 / max(500,5000) = 2,000.
2