Query processing cost formulae
Legend
Symbol Description
NKeys(Col) The number of distinct values of column Col
High(Col) The highest value of column Col
Low(Col) The lowest value of column Col
NTuples(R) The number of tuples of relation R
NPages(R) The number of pages of relation R
NPages(I) The number of pages of index I
Height(I) The height of index I
 RFi The product of all reduction factors
 NTuples(Ri) The product of the numbers of tuples of all
relations taking part in a join
num_passes(R) The number of passes for sorting relation R
PF Projection factor (portion of all columns)
1. Reduction factor (Selectivity)
a. Col = value
RF = 1/NKeys(Col)
b. Col > value
RF = (High(Col) – value) / (High(Col) – Low(Col))
c. Col < value
RF = (val – Low(Col)) / (High(Col) – Low(Col))
d. Col_A = Col_B (for joins)
RF = 1/ (Max (NKeys(Col_A), NKeys(Col_B)))
e. In no information about NKeys or interval, use a “magic number” 1/10
RF = 1/10
2. Result size calculations
a. Single table
Result_size = NTuples(R) *  RFi
b. Joins
Result_size =  NTuples(Ri) *  RFi
3. Indexing Cost
a. B+-tree index
i. Just a single tuple (selection over a primary key)
Cost = Height(I) + 1
ii. Clustered index (multiple tuples)
Cost = (NPages(I)+NPages(R)) *  RFi
iii. Unclustered (multiple tuples)
Cost = (NPages(I)+NTuples(R)) *  RFi
b. Hash Index
i. Just a single tuple (selection over a primary key)
Cost = 1.2 + 1 = 2.2
ii. Clustered index (multiple tuples)
Cost = (NPages (R)) *  RFi * 2.2
iii. Unclustered index (multiple tuples)
Cost = (NTuples(R)) *  RFi * 2.2
4. Sequential Scan (i.e. Heap Scan) Cost
Cost = NPages(R)
5. Joins (between relations R and S, R = outer, S = inner) Cost
a. NLJ
i. Tuple-oriented NLJ
Cost = NPages(R) + NTuples(R) * NPages(S)
ii. Page-oriented NLJ
Cost = NPages(R) + NPages (R) * NPages(S)
iii. Block-oriented NJL (for block_size B)
Cost = NPages(R) + ceil(NPages (R)/(B-2)) * NPages(S)
b. Hash Join
Cost = 3*(NPages(R) + NPages(S))
c. Sort-Merge Join
CostSMJ = NPages(R) + NPages(S) +
2* NPages(R)* num_passes(R) +
2* NPages(S)* num_passes(S)
6. Projections Cost
a. Sort-based
Cost = ReadTable + WriteProjectedPages + SortProjectedPages +
ReadProjectedPages = NPages(R)+ NPages(R)*PF + 2*num_passes*
NPages(R)*PF + NPages(R)*PF
b. Hash-Based
Cost = ReadTable + WriteProjectedPages + ReadProjectedPages
= NPages(R) + NPages(R)*PF + NPages(R)*P

Question 3 Introduction (Total marks for Q3: 10 marks)

Consider the following relational schema and SQL query. The schema captures information about employees, departments, and company finances (organized on a per department basis).

Emp(eid: integer, did: integer, sal: integer, hobby: char(20))

Dept(did: integer, dname: char(20), floor: integer, phone: char(10))

Finance(did: integer, budget: real, sales: real, expenses: real)

Consider the following query:

SELECT D.dname, F.budget

FROM Emp E, Dept D, Finance F

WHERE E.did = D.did

AND D.did = F.did

AND E.sal > 100,000

AND E.hobby IN (‘diving’, ‘soccer’);

The system’s statistics indicate that employee salaries range from 50,000 to 150,000, and employees enjoy 50 different hobbies. There is a total of 25,000 employees and 1,200 departments (each with corresponding financial record in the Finance relation) in the database. Each relation fits 100 tuples in a page. Suppose there exists a clustered B+ tree index on (Dept.did) and a clustered B+ tree index on (Emp.salary), both of size 50 pages.

Assume that sorting of any relation (if required) can be done in 2 passes. NLJ is a Page-oriented Nested Loops Join. Assume that did is the candidate key, and that 50 tuples of a resulting join between Emp and Dept fit in a page. Similarly, 50 tuples of a resulting join between Finance and Dept fit in a page. Any selections/projections not indicated on the plan are performed “on the fly” after all joins have been completed.

Flag question: Question 12
Question 12 2 pts

Q3.1

Compute the reduction factors and the estimated result size in number of tuples. (2 marks)
Group of answer choices
RF(E.did=D.did)
RF(D.did=F.did)
RF(E.sal>100,000)
RF(E.hobby in ('diving' , 'soccer') )
Expected Number of Tuples
NOTE WHEN SOLVING THE ABOVE YOU MUST USE THE FORMULAS PROVIDED ABOVE WHERE APPLICABLE WITHOUT FAIL AS THEY WILL NET THE CORRECT ANSWER. YOUR THINKING PROCESS SHOULD BE THIS. YOU MUST A) CALCULATE THE RELEVANT FORMULAS APPLICABLE TO THE QUESTION AT HAND, AND SEE IF THEY ARE APPLICABLE TO THE GIVEN QUESTION. B) STATE HOW THE TERMS WITHIN THE EQUATION RELATE TO THE QUESTION AT HAND) C) USE THE FORMULA IN ORDER TO SOLVE THE QUESTION. NOTE THAT WITH THE REDUCTION FACTORS THEY ARE THE TERMS IN BRACKETS, IF ITS (AIRPLANE) THEN ITS JUST THE REDUCTION FACTOR OF AIRPLANE, IF ITS (AIRPLANE ,BIKE) ITS THE PRODUCT OF THE REDUCTION FACTOR OF AIRPLANE TIMES THE REDUCTION FACTOR OF BIKE. THIS IS CRITICALLY IMPORTANT. YOU MUST USE THIS THINKING PROCESS WHEN SOLVING QUESTIONS