# CS计算机代考程序代写 SQL Oregon State UniversityPractice problems Query Optimization

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