Legend and Symbols
Before diving into the formulas, it's essential to understand the symbols and terms used:
Symbol Description
NKeys(Col) The number of distinct values in column Col.
High(Col) The highest value in column Col.
Low(Col) The lowest value in column Col.
NTuples(R) The number of tuples (rows) in relation (table) R.
NPages(R) The number of pages required to store relation R.
NPages(I) The number of pages used by index I.
Height(I) The height of index I (number of levels in a B-tree index).
Π RFi The product of all reduction factors RFi applied in a query.
Π NTuples(Ri) The product of the number of tuples in all relations Ri participating in a join operation.
num_passes(R) The number of passes required to sort relation R.
PF Projection Factor: The portion (fraction) of all columns retained after a projection operation.
1.	Reduction Factor (Selectivity)
Reduction Factor (RF) quantifies the fraction of data remaining after applying a selection predicate. It estimates how much a query reduces the data size based on certain conditions.
a. Selection: Column Equals a Value (Col = value)
[ \text{RF} = \frac{1}{\text{NKeys(Col)}} ]
• Explanation: Assumes uniform distribution of values. If a column has NKeys(Col) distinct values, selecting a specific value reduces the data to 1/NKeys(Col) of the original.
b. Selection: Column Greater Than a Value (Col > value)
[ \text{RF} = \frac{\text{High(Col)} - \text{value}}{\text{High(Col)} - \text{Low(Col)}} ]
• Explanation: Proportion of data where the column's value is greater than the specified value, based on the column's range.
c. Selection: Column Less Than a Value (Col < value)
[ \text{RF} = \frac{\text{value} - \text{Low(Col)}}{\text{High(Col)} - \text{Low(Col)}} ]
• Explanation: Proportion of data where the column's value is less than the specified value.
d. Join: Column Equality (Col_A = Col_B)
[ \text{RF} = \frac{1}{\max(\text{NKeys(Col_A)}, \text{NKeys(Col_B)})} ]
• Explanation: For joining two tables on columns Col_A and Col_B, the reduction factor depends on the higher number of distinct keys in either column.
e. No Information Available
[ \text{RF} = \frac{1}{10} ]
• Explanation: When there's no statistical information about the data distribution, a default "magic number" of 0.1 (1/10) is used as an estimate.
2.	Result Size Calculations
Estimates the number of tuples resulting from query operations.
a. Single Table Query
[ \text{Result_size} = \text{NTuples(R)} \times \prod \text{RFi} ]
• Explanation: The number of tuples after applying one or more selection predicates with reduction factors RFi.
b. Join Operations
[ \text{Result_size} = \prod \text{NTuples(Ri)} \times \prod \text{RFi} ]
• Explanation: For joining multiple relations, multiply the number of tuples in each participating relation and apply the combined reduction factors.
3.	Indexing Cost
Evaluates the cost of using different types of indexes to execute queries.
a. B+-Tree Index
i. Single Tuple Selection (Primary Key Lookup)
[ \text{Cost} = \text{Height(I)} + 1 ]
• Explanation: The cost includes traversing the index tree (height) and accessing the data page containing the tuple.
ii. Clustered Index (Multiple Tuples)
[ \text{Cost} = (\text{NPages(I)} + \text{NPages(R)}) \times \prod \text{RFi} ]
• Explanation: Accessing the index pages and the clustered data pages. Reduction factors apply if multiple tuples are retrieved.
iii. Unclustered Index (Multiple Tuples)
[ \text{Cost} = (\text{NPages(I)} + \text{NTuples(R)}) \times \prod \text{RFi} ]
• Explanation: Accessing index pages and individual data pages for each tuple (higher cost due to non-contiguous data storage).
b. Hash Index
i. Single Tuple Selection (Primary Key Lookup)
[ \text{Cost} = 1.2 + 1 = 2.2 ]
• Explanation: Fixed cost for hashing and accessing the tuple.
ii. Clustered Hash Index (Multiple Tuples)
[ \text{Cost} = \text{NPages(R)} \times \prod \text{RFi} \times 2.2 ]
• Explanation: Accessing data pages multiplied by the fixed cost for each tuple.
iii. Unclustered Hash Index (Multiple Tuples)
[ \text{Cost} = \text{NTuples(R)} \times \prod \text{RFi} \times 2.2 ]
• Explanation: Each tuple requires separate access, hence the multiplication by NTuples(R).
4.	Sequential Scan (Heap Scan) Cost
Calculates the cost of scanning an entire table without using any indexes.
[ \text{Cost} = \text{NPages(R)} ]
• Explanation: Simply the number of pages in the relation, as each page must be read sequentially.

 
Q6 Introduction  (Total marks for Q6: 6 marks)
Consider the following schema and the given SQL query. This database is about celebrities, their interviews by a tv channel, and the presenters doing the interviews.
Interview (InterviewID, StartTime, Duration, Date, Topic, CelebrityID, PresenterID, AmountPaid)
Celebrity (CelebrityID, FirstName, LastName, Type, Rating, Address, Phone)
Presenter (PresenterID, FirstName, LastName, Email, Expertise, Salary)
SELECT *
FROM Celebrity as C, Interview as I, Presenter as P
WHERE C.CelebrityID = I.CelebrityID AND I.PresenterID = P.PresenterID AND P.Salary >= 300,000  AND P.Expertise = ‘Sports’;
Our statistics show that the salary of a presenter ranges from 0 to 400,000 ([0, 400,000]) since some may work as volunteers. There are in total 10 different expertises. There are a total of 20,000 celebrities and 100,000 interviews and 500 presenters in the database. Each relation fits 10 tuples in a page. Given these, compute the estimated cost of the plans shown below.
You can assume that sorting of any relation (if required) can be done in 3 passes. NLJ is a Page-oriented Nested Loops Join. Assume that 10 tuples of a resulting join between Celebrity and Interview fit in a page. Similarly, 10 tuples of a resulting join between Interview and Presenter fit in a page. If selection over filtering predicates is not marked in the plan, assume it will happen on-the-fly after all joins are performed, as the last operation in the plan. Suppose there exists a clustered B+ tree index on (Presenter.Salary) of size 10 pages.
 Question 10 3 pts 
Q6.1
Compute the following values for the following plan. We first take a join between Celebrity and Interview using Hash Join and both tables are using heap scan and the left branch of the plan is the Celebrity table. Then this intermediate result is joined with Presenter where presenter is the right branch of the plan. Presenter again uses heap scan and this last join is SMJ as given in class/tute examples.
Group of answer choices 
The result size of the first join in PAGES 
The cost of the first join in I/Os 
The cost of the first join in I/Os if we had 5,000 celebrities instead

Flag question: Question 10 
Question 10 3 pts 
Compute the following values for the following plan. We explicitly mention that we first take the selection using predicate based on the salary as given in the query using the index in this plan. Then we do a Hash join with the outcome of the selection with Interview table using heap scan on the Interview table. Last we do the Celebrity join where Celebrity is the right branch of the plan and join is a NLJ with Celebrities are accessed using heap scan. (Recall to round the values up to the nearest integer when you think it is needed.)
Group of answer choices 
The result size of the selection mention above in PAGES 
The result size of the first join in PAGES 
The result size of the selection mentioned above in TUPLES 
The cost of the first join in I/Os




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 (AAIRPLANE,BETA) ITS THE PRODUCT OF THE REDUCTION FACTOR OF AIRPLANE AND BETA. FOLLOW THIS ESPECIALLY AS ITS IMPORTANT IN GETTING THE CORRECT ANSWER. USE THIS THINKING PROCESS WHEN SOLVING THE QUESTIONS