Introduction
In database systems, query processing cost refers to the resources required to execute a query. Understanding and calculating these costs is crucial for database optimization, ensuring efficient data retrieval and manipulation. This cheat sheet provides formulas and explanations to estimate the cost of various query operations, aiding in performance tuning and decision-making.
 
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.
 
5. Joins
Estimating the cost of different join algorithms between two relations, R (outer) and S (inner).
a. Nested Loop Join (NLJ)
i. Tuple-Oriented Nested Loop Join
[ \text{Cost} = \text{NPages(R)} + \text{NTuples(R)} \times \text{NPages(S)} ]
•	Explanation: Read all pages of R, then for each tuple in R, scan all pages of S.
ii. Page-Oriented Nested Loop Join
[ \text{Cost} = \text{NPages(R)} + \text{NPages(R)} \times \text{NPages(S)} ]
•	Explanation: Read all pages of R, then for each page in R, scan all pages of S.
iii. Block-Oriented Nested Loop Join (Block Size B)
[ \text{Cost} = \text{NPages(R)} + \left\lceil \frac{\text{NPages(R)}}{\text{B} - 2} \right\rceil \times \text{NPages(S)} ]
•	Explanation: Utilizes block I/O. B represents the number of blocks that can be loaded into memory. Reduces the number of scans on S by processing multiple pages of R simultaneously.
b. Hash Join
[ \text{Cost} = 3 \times (\text{NPages(R)} + \text{NPages(S)}) ]
•	Explanation: Involves building and probing hash tables, typically requiring three passes over both relations.
c. Sort-Merge Join
[ \text{Cost}_{\text{SMJ}} = \text{NPages(R)} + \text{NPages(S)} + 2 \times \text{NPages(R)} \times \text{num_passes(R)} + 2 \times \text{NPages(S)} \times \text{num_passes(S)} ]
•	Explanation: Costs include reading both relations, sorting them (each requires num_passes passes), and then merging.
 
6. Projections Cost
Estimating the cost associated with projecting specific columns from a relation.
a. Sort-Based Projection
[ \text{Cost} = \text{NPages(R)} + \text{NPages(R)} \times \text{PF} + 2 \times \text{num_passes} \times \text{NPages(R)} \times \text{PF} + \text{NPages(R)} \times \text{PF} ]
•	Explanation:
o	ReadTable: Read all pages of R.
o	WriteProjectedPages: Write projected pages based on the projection factor PF.
o	SortProjectedPages: Sort the projected pages, involving multiple passes (num_passes) over the data.
o	ReadProjectedPages: Read the sorted projected pages.
b. Hash-Based Projection
[ \text{Cost} = \text{NPages(R)} + \text{NPages(R)} \times \text{PF} + \text{NPages(R)} \times \text{PF} ]
•	Explanation:
o	ReadTable: Read all pages of R.
o	WriteProjectedPages: Write projected pages based on PF.
o	ReadProjectedPages: Read the projected pages without additional sorting passes.
 
7. Additional Considerations
•	Projection Factor (PF): Determines how much of the table's columns are being projected. For example, if a table has 10 columns and a projection retains 3, then PF = 3/10 = 0.3.
•	Number of Passes (num_passes): Influences the cost of sorting operations. More passes indicate more processing and higher costs.
•	Block Size (B): Represents the number of memory blocks available for processing. Larger block sizes can reduce the number of passes required for operations like joins and sorts.
Comprehensive Problem-Solving Instructions

Objective: When solving a problem, adhere strictly to the provided formulas where applicable to ensure accurate results. Follow the structured thinking process outlined below to systematically approach and solve the question.
Thinking Process

    Initial Analysis:
        A) Calculate the relevant formulas applicable to the question at hand.
        B) Determine if these formulas are applicable to the given question.
        C) State how the terms within each equation relate to the question.
        D) Use the formula to solve the question.
        Note on Reduction Factors:
            If the reduction factor is single (e.g., (A)), use the reduction factor of A.
            If multiple (e.g., (A,B)), use the product of the reduction factors of A and B.
            Ensure accurate application of reduction factors as they are crucial for the correct answer.

    Verification Steps for Counting or Enumeration Tasks:
        Double-Check Work: Approach the problem from a different angle or use an alternative method to verify results.
        Methodical Counting: Count elements individually, using marking or highlighting to ensure accuracy.
        Avoid Common Pitfalls: Be cautious of overlooking adjacent repeated elements or making assumptions based on initial impressions. Actively search for these potential errors.
        Question Initial Results: Continuously ask, "What if this is incorrect?" and attempt to disprove the first conclusion.
        Use Visual Aids: Employ diagrams, tables, or alternative representations of the problem to gain new insights.
        Reflect on Additional Steps: After implementing verification and counting strategies, reflect on their influence on your analysis and whether they led to changes in results.

Structured Solution Format

    Enclose All Thoughts: Use <thinking> tags to explore multiple angles and approaches.

    Step-by-Step Breakdown:
        Use <step> tags to outline each step clearly.
        Start with a 20-step budget; request more if the problem complexity requires it.
        After each step, include <count> tags to show the remaining budget.
        Cease further steps when the budget reaches 0.

    Continuous Adjustment:
        Adjust reasoning based on intermediate results and reflections.
        Adapt strategies as you progress through the problem.

    Regular Evaluation:
        Use <reflection> tags to critically and honestly evaluate the reasoning process.
        Assign a quality score between 0.0 and 1.0 using <reward> tags after each reflection to guide the approach:
            0.8+: Continue the current approach.
            0.5-0.7: Consider minor adjustments.
            Below 0.5: Seriously consider backtracking and trying a different approach.

    Handling Low Reward Scores:
        If unsure or if the reward score is low, backtrack and attempt a different approach.
        Explain the decision within <thinking> tags.

    Mathematical Problems:
        Show all work explicitly using LaTeX for formal notation.
        Provide detailed proofs where necessary.

    Exploring Multiple Solutions:
        Individually explore multiple solutions if possible.
        Compare different approaches in reflections.

    Thoughts as a Scratchpad:
        Use thoughts to write out all calculations and reasoning explicitly.

    Final Answer:
        Synthesize the final answer within <answer> tags.
        Provide a clear, concise summary of the solution.

    Final Reflection:
        Conclude with a reflection on the overall solution.
        Discuss effectiveness, challenges, and how they were addressed.
        Assign a final reward score.

Example Structure:

markdown

<thinking>
  <!-- Explore different approaches and angles -->
</thinking>

<step>
  <!-- Step-by-step solution -->
</step>
<count>19</count>

<reflection>
  <!-- Evaluate the step taken -->
</reflection>
<reward>0.9</reward>

<!-- Continue with subsequent steps until the budget is exhausted -->

<answer>
  <!-- Final concise summary of the solution -->
</answer>

<reflection>
  <!-- Overall reflection on the solution process -->
</reflection>
<reward>0.95</reward>

Usage Instructions:

    Apply Formulas Appropriately: Ensure that all relevant formulas are identified and correctly applied to the problem.
    Maintain Structure: Follow the tagging system strictly to organize thoughts, steps, reflections, and answers.
    Monitor Budget: Keep track of the step budget to manage the depth of the solution process.
    Ensure Accuracy: Utilize verification and counting strategies to minimize errors.
    Reflect and Adapt: Continuously evaluate and adapt your approach based on reflections and reward scores.

By adhering to this comprehensive prompt, you will ensure a methodical, accurate, and reflective approach to problem-solving.

Comprehensive Problem-Solving Instructions

Objective: When solving a problem, adhere strictly to the provided formulas where applicable to ensure accurate results. Follow the structured thinking process outlined below to systematically approach and solve the question.
Thinking Process

    Initial Analysis:
        A) Calculate the relevant formulas applicable to the question at hand.
        B) Determine if these formulas are applicable to the given question.
        C) State how the terms within each equation relate to the question.
        D) Use the formula to solve the question.
        Note on Reduction Factors:
            If the reduction factor is single (e.g., (A)), use the reduction factor of A.
            If multiple (e.g., (A,B)), use the product of the reduction factors of A and B.
            Ensure accurate application of reduction factors as they are crucial for the correct answer.

    Verification Steps for Counting or Enumeration Tasks:
        Double-Check Work: Approach the problem from a different angle or use an alternative method to verify results.
        Methodical Counting: Count elements individually, using marking or highlighting to ensure accuracy.
        Avoid Common Pitfalls: Be cautious of overlooking adjacent repeated elements or making assumptions based on initial impressions. Actively search for these potential errors.
        Question Initial Results: Continuously ask, "What if this is incorrect?" and attempt to disprove the first conclusion.
        Use Visual Aids: Employ diagrams, tables, or alternative representations of the problem to gain new insights.
        Reflect on Additional Steps: After implementing verification and counting strategies, reflect on their influence on your analysis and whether they led to changes in results.

Structured Solution Format

    Enclose All Thoughts: Use <thinking> tags to explore multiple angles and approaches.

    Step-by-Step Breakdown:
        Use <step> tags to outline each step clearly.
        Start with a 20-step budget; request more if the problem complexity requires it.
        After each step, include <count> tags to show the remaining budget.
        Cease further steps when the budget reaches 0.

    Continuous Adjustment:
        Adjust reasoning based on intermediate results and reflections.
        Adapt strategies as you progress through the problem.

    Regular Evaluation:
        Use <reflection> tags to critically and honestly evaluate the reasoning process.
        Assign a quality score between 0.0 and 1.0 using <reward> tags after each reflection to guide the approach:
            0.8+: Continue the current approach.
            0.5-0.7: Consider minor adjustments.
            Below 0.5: Seriously consider backtracking and trying a different approach.

    Handling Low Reward Scores:
        If unsure or if the reward score is low, backtrack and attempt a different approach.
        Explain the decision within <thinking> tags.

    Mathematical Problems:
        Show all work explicitly using LaTeX for formal notation.
        Provide detailed proofs where necessary.

    Exploring Multiple Solutions:
        Individually explore multiple solutions if possible.
        Compare different approaches in reflections.

    Thoughts as a Scratchpad:
        Use thoughts to write out all calculations and reasoning explicitly.

    Final Answer:
        Synthesize the final answer within <answer> tags.
        Provide a clear, concise summary of the solution.

    Final Reflection:
        Conclude with a reflection on the overall solution.
        Discuss effectiveness, challenges, and how they were addressed.
        Assign a final reward score.

Example Structure:

markdown

<thinking>
  <!-- Explore different approaches and angles -->
</thinking>

<step>
  <!-- Step-by-step solution -->
</step>
<count>19</count>

<reflection>
  <!-- Evaluate the step taken -->
</reflection>
<reward>0.9</reward>

<!-- Continue with subsequent steps until the budget is exhausted -->

<answer>
  <!-- Final concise summary of the solution -->
</answer>

<reflection>
  <!-- Overall reflection on the solution process -->
</reflection>
<reward>0.95</reward>

Usage Instructions:

    Apply Formulas Appropriately: Ensure that all relevant formulas are identified and correctly applied to the problem.
    Maintain Structure: Follow the tagging system strictly to organize thoughts, steps, reflections, and answers.
    Monitor Budget: Keep track of the step budget to manage the depth of the solution process.
    Ensure Accuracy: Utilize verification and counting strategies to minimize errors.
    Reflect and Adapt: Continuously evaluate and adapt your approach based on reflections and reward scores.

By adhering to this comprehensive prompt, you will ensure a methodical, accurate, and reflective approach to problem-solving.


Q2 Introduction (Total marks for Q2: 5 marks)

Consider a relation with the following schema:

JobSeekers(id, firstname, lastname, city, soughtsalary)

The JobSeekers relation consists of 10,000 pages. Each page stores 100 tuples. The online software works in the 8 largest Australian cities and soughtsalary can have values between 60,000 and 160,000 (i.e., [60,000 – 160,000].)

Suppose that the following SQL query is executed frequently using the given relation:

SELECT *

FROM JobSeekers

WHERE city = ‘Melbourne’ AND soughtsalary > 80,000;

Your job is to:

    Compute the reduction factors and the estimated result size in number of tuples. (1 mark)
    Compute the estimated cost in number of disk I/O’s required to use a clustered B+ tree index on (city, soughtsalary) to answer this query. Suppose there are 2,000 index pages. (1 mark)
    Compute the estimated cost in number of disk I/O’s required to use an unclustered B+ tree index on (soughtsalary)to answer this query. Suppose there are 2,000 index pages. (1 mark)
    Compute the estimated cost in number of disk I/O’s required to use an unclustered Hash index on (city) to answer this query.  (1 mark)
    Compute the estimated cost in number of disk I/O’s required to use an unclustered Hash index on (soughtsalary) to answer this query.  (1 mark)