\documentclass{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{geometry}
\usepackage{booktabs}
\usepackage{hyperref}

\geometry{a4paper, margin=1in}

\title{Query Processing Cost Formulas}
\author{}
\date{}

\begin{document}

\maketitle

\tableofcontents
\newpage

\section{Legend and Symbols}

Before delving into the formulas, it is essential to understand the symbols and terms used throughout this document.

\begin{table}[h!]
\centering
\begin{tabular}{@{}ll@{}}
\toprule
\textbf{Symbol} & \textbf{Description} \\
\midrule
\texttt{NKeys(Col)} & The number of distinct values in column \texttt{Col}. \\
\texttt{High(Col)} & The highest value in column \texttt{Col}. \\
\texttt{Low(Col)} & The lowest value in column \texttt{Col}. \\
\texttt{NTuples(R)} & The number of tuples (rows) in relation (table) \texttt{R}. \\
\texttt{NPages(R)} & The number of pages required to store relation \texttt{R}. \\
\texttt{NPages(I)} & The number of pages used by index \texttt{I}. \\
\texttt{Height(I)} & The height of index \texttt{I} (number of levels in a B-tree index). \\
$\prod$\texttt{RFi} & The product of all reduction factors \texttt{RFi} applied in a query. \\
$\prod$\texttt{NTuples(Ri)} & The product of the number of tuples in all relations \texttt{Ri} participating in a join operation. \\
\texttt{num\_passes(R)} & The number of passes required to sort relation \texttt{R}. \\
\texttt{PF} & Projection Factor: The portion (fraction) of all columns retained after a projection operation. \\
\texttt{B} & The number of buffer pages available in memory (buffer size). \\
\texttt{T(R)} & The size of relation \texttt{R} in tuples. (Same as \texttt{NTuples(R)}) \\
\bottomrule
\end{tabular}
\caption{Legend and Symbols}
\end{table}

\section{1. Reduction Factor (Selectivity)}

The 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.

\subsection{a. Selection: Column Equals a Value (\texttt{Col = value})}

\[
\text{RF} = \frac{1}{\text{NKeys(Col)}}
\]

\textbf{Conditions:}
\begin{itemize}
\item Assumes uniform distribution of values in the column.
\item Applicable when selecting tuples where a column equals a specific value.
\end{itemize}

\textbf{Explanation:}
If a column has \texttt{NKeys(Col)} distinct values, selecting a specific value reduces the data to \(\frac{1}{\text{NKeys(Col)}}\) of the original.

\subsection{b. Selection: Column Greater Than a Value (\texttt{Col > value})}

\[
\text{RF} = \frac{\text{High(Col)} - \text{value}}{\text{High(Col)} - \text{Low(Col)}}
\]

\textbf{Conditions:}
\begin{itemize}
\item Applicable for range queries where values greater than a specified value are selected.
\item Assumes uniform distribution of values within the range.
\end{itemize}

\textbf{Explanation:}
Calculates the proportion of data where the column's value is greater than the specified value, based on the column's range.

\subsection{c. Selection: Column Less Than a Value (\texttt{Col < value})}

\[
\text{RF} = \frac{\text{value} - \text{Low(Col)}}{\text{High(Col)} - \text{Low(Col)}}
\]

\textbf{Conditions:}
\begin{itemize}
\item Applicable for range queries where values less than a specified value are selected.
\item Assumes uniform distribution of values within the range.
\end{itemize}

\textbf{Explanation:}
Calculates the proportion of data where the column's value is less than the specified value, based on the column's range.

\subsection{d. Join: Column Equality (\texttt{Col\_A = Col\_B})}

\[
\text{RF} = \frac{1}{\max(\text{NKeys(Col\_A)}, \text{NKeys(Col\_B)})}
\]

\textbf{Conditions:}
\begin{itemize}
\item Applicable when performing an equijoin between two relations on columns \texttt{Col\_A} and \texttt{Col\_B}.
\item Assumes uniform distribution and independence of values in joined columns.
\end{itemize}

\textbf{Explanation:}
The reduction factor for joining two tables depends on the higher number of distinct keys in either column.

\subsection{e. No Information Available}

\[
\text{RF} = \frac{1}{10}
\]

\textbf{Conditions:}
\begin{itemize}
\item Used when there is no statistical information about the data distribution.
\end{itemize}

\textbf{Explanation:}
A default "magic number" of 0.1 (i.e., \(\frac{1}{10}\)) is used as an estimate in the absence of information.

\section{2. Result Size Calculations}

Estimates the number of tuples resulting from query operations.

\subsection{a. Single Table Query}

\[
\text{Result\_size} = \text{NTuples(R)} \times \prod \text{RFi}
\]

\textbf{Conditions:}
\begin{itemize}
\item Applicable when applying one or more selection predicates to a single relation.
\end{itemize}

\textbf{Explanation:}
Calculates the number of tuples remaining after applying the combined reduction factors from the selection predicates.

\subsection{b. Join Operations}

\[
\text{Result\_size} = \left( \prod \text{NTuples(Ri)} \right) \times \prod \text{RFi}
\]

\textbf{Conditions:}
\begin{itemize}
\item Applicable when performing joins between multiple relations.
\item Assumes independence of joins and uniform distribution of join keys.
\end{itemize}

\textbf{Explanation:}
Estimates the number of tuples resulting from joining multiple relations by multiplying the number of tuples in each participating relation and applying the combined reduction factors.

\section{3. Indexing Cost}

Evaluates the cost of using different types of indexes to execute queries.

\subsection{a. B\textsuperscript{+}-Tree Index}

\subsubsection{i. Single Tuple Selection (Primary Key Lookup)}

\[
\text{Cost} = \text{Index Traversal Cost} + \text{Data Access Cost}
\]

\textbf{Breakdown:}
\begin{itemize}
\item \textbf{Index Traversal Cost:} \(\text{Height(I)}\) (reading index nodes from root to leaf)
\item \textbf{Data Access Cost:} 1 (reading the data page containing the tuple)
\end{itemize}

\textbf{Total Cost:}
\[
\text{Cost} = \text{Height(I)} + 1
\]

\textbf{Conditions:}
\begin{itemize}
\item Applicable when performing a selection based on a primary key, which retrieves a single tuple.
\item Index is a B\textsuperscript{+}-Tree.
\end{itemize}

\subsubsection{ii. Clustered Index (Multiple Tuples)}

\textbf{Breakdown:}
\begin{itemize}
\item \textbf{Index Pages Read:} \(\text{NPages(I)} \times \prod \text{RFi}\)
\item \textbf{Data Pages Read:} \(\text{NPages(R)} \times \prod \text{RFi}\)
\end{itemize}

\textbf{Total Cost:}
\[
\text{Cost} = \left( \text{NPages(I)} + \text{NPages(R)} \right) \times \prod \text{RFi}
\]

\textbf{Conditions:}
\begin{itemize}
\item Applicable when using a clustered B\textsuperscript{+}-Tree index to retrieve multiple tuples.
\item Data is physically ordered according to the index key.
\end{itemize}

\subsubsection{iii. Unclustered Index (Multiple Tuples)}

\textbf{Breakdown:}
\begin{itemize}
\item \textbf{Index Pages Read:} \(\text{NPages(I)} \times \prod \text{RFi}\)
\item \textbf{Data Pages Accessed:} \(\text{NTuples(R)} \times \prod \text{RFi}\)
\end{itemize}

\textbf{Total Cost:}
\[
\text{Cost} = \left( \text{NPages(I)} + \text{NTuples(R)} \right) \times \prod \text{RFi}
\]

\textbf{Conditions:}
\begin{itemize}
\item Applicable when using an unclustered B\textsuperscript{+}-Tree index to retrieve multiple tuples.
\item Data pages are not ordered and may require random access.
\item Inefficient for range queries due to random I/O.
\end{itemize}

\subsection{b. Hash Index}

\subsubsection{i. Single Tuple Selection (Primary Key Lookup)}

\textbf{Breakdown:}
\begin{itemize}
\item \textbf{Hash Function Cost:} 1.2 (cost to compute hash and locate bucket)
\item \textbf{Data Access Cost:} 1 (reading the data page)
\end{itemize}

\textbf{Total Cost:}
\[
\text{Cost} = 1.2 + 1 = 2.2
\]

\textbf{Conditions:}
\begin{itemize}
\item Applicable for equality searches using a hash index.
\item Not suitable for range queries.
\end{itemize}

\subsubsection{ii. Clustered Hash Index (Multiple Tuples)}

\textbf{Breakdown:}
\begin{itemize}
\item \textbf{Data Pages Read:} \(\text{NPages(R)} \times \prod \text{RFi}\)
\item \textbf{Hashing Cost per Tuple:} Included in data page reads.
\end{itemize}

\textbf{Total Cost:}
\[
\text{Cost} = \left( \text{NPages(R)} \times \prod \text{RFi} \right) \times 2.2
\]

\textbf{Explanation:}
Each qualifying page involves a hashing cost and data page access.

\subsubsection{iii. Unclustered Hash Index (Multiple Tuples)}

\textbf{Breakdown:}
\begin{itemize}
\item \textbf{Hash Function Cost:} \(\text{NTuples(R)} \times \prod \text{RFi} \times 1.2\)
\item \textbf{Data Access Cost:} \(\text{NTuples(R)} \times \prod \text{RFi} \times 1\)
\end{itemize}

\textbf{Total Cost:}
\[
\text{Cost} = \left( \text{NTuples(R)} \times \prod \text{RFi} \right) \times 2.2
\]

\textbf{Conditions:}
\begin{itemize}
\item Inefficient for range queries and large result sets due to random access.
\end{itemize}

\section{4. Sequential Scan (Heap Scan) Cost}

Calculates the cost of scanning an entire table without using any indexes.

\textbf{Total Cost:}
\[
\text{Cost} = \text{NPages(R)}
\]

\textbf{Breakdown:}
\begin{itemize}
\item \textbf{Data Pages Read:} \(\text{NPages(R)}\)
\end{itemize}

\textbf{Conditions:}
\begin{itemize}
\item Used when no indexes are applicable, or for operations requiring full table access.
\end{itemize}

\section{5. Joins}

Evaluates the cost of different join algorithms between two relations, \texttt{R} (outer) and \texttt{S} (inner).

\subsection{a. Nested Loop Join (NLJ)}

\subsubsection{i. Tuple-Oriented Nested Loop Join}

\textbf{Breakdown:}
\begin{itemize}
\item \textbf{Read Outer Relation:} \(\text{NPages(R)}\)
\item \textbf{For Each Tuple in R, Read All Pages of S:} \(\text{NTuples(R)} \times \text{NPages(S)}\)
\end{itemize}

\textbf{Total Cost:}
\[
\text{Cost} = \text{NPages(R)} + \left( \text{NTuples(R)} \times \text{NPages(S)} \right)
\]

\subsubsection{ii. Page-Oriented Nested Loop Join}

\textbf{Breakdown:}
\begin{itemize}
\item \textbf{Read Outer Relation:} \(\text{NPages(R)}\)
\item \textbf{For Each Page in R, Read All Pages of S:} \(\text{NPages(R)} \times \text{NPages(S)}\)
\end{itemize}

\textbf{Total Cost:}
\[
\text{Cost} = \text{NPages(R)} + \left( \text{NPages(R)} \times \text{NPages(S)} \right)
\]

\subsubsection{iii. Block-Oriented Nested Loop Join}

\textbf{Breakdown:}
\begin{itemize}
\item \textbf{Read Outer Relation:} \(\text{NPages(R)}\)
\item \textbf{Number of Blocks in R:} \(\left\lceil \frac{\text{NPages(R)}}{\text{B} - 2} \right\rceil\)
\item \textbf{For Each Block, Read All Pages of S:} \(\left\lceil \frac{\text{NPages(R)}}{\text{B} - 2} \right\rceil \times \text{NPages(S)}\)
\end{itemize}

\textbf{Total Cost:}
\[
\text{Cost} = \text{NPages(R)} + \left( \left\lceil \frac{\text{NPages(R)}}{\text{B} - 2} \right\rceil \times \text{NPages(S)} \right)
\]

\subsection{b. Hash Join}

\textbf{Breakdown:}
\begin{enumerate}
\item \textbf{Partitioning Phase:}
    \begin{itemize}
    \item Read R: \(\text{NPages(R)}\)
    \item Write Partitioned R: \(\text{NPages(R)}\)
    \item Read S: \(\text{NPages(S)}\)
    \item Write Partitioned S: \(\text{NPages(S)}\)
    \end{itemize}
\item \textbf{Matching Phase:}
    \begin{itemize}
    \item For each partition:
        \begin{itemize}
        \item Read Partitioned R: \(\text{NPages(R)}\)
        \item Read Partitioned S: \(\text{NPages(S)}\)
        \end{itemize}
    \end{itemize}
\item \textbf{Total I/O:}
    \[
    \text{Cost} = 3 \times \left( \text{NPages(R)} + \text{NPages(S)} \right)
    \]
\end{enumerate}

\textbf{Explanation:}
\begin{itemize}
\item Each page is read and written once during partitioning.
\item Partitions are read again during matching.
\end{itemize}

\subsection{c. Sort-Merge Join}

\textbf{Breakdown:}
\begin{enumerate}
\item \textbf{Sorting Phase for R:}
    \begin{itemize}
    \item Initial Read: \(\text{NPages(R)}\)
    \item Write Runs: \(\text{NPages(R)}\)
    \item Subsequent Passes (per pass): \(2 \times \text{NPages(R)}\)
    \item Total for Sorting R: \((2 \times \text{num\_passes(R)} \times \text{NPages(R)})\)
    \end{itemize}
\item \textbf{Sorting Phase for S:}
    \begin{itemize}
    \item Similar to R.
    \item Total for Sorting S: \((2 \times \text{num\_passes(S)} \times \text{NPages(S)})\)
    \end{itemize}
\item \textbf{Merge Phase:}
    \begin{itemize}
    \item Read Sorted R: \(\text{NPages(R)}\)
    \item Read Sorted S: \(\text{NPages(S)}\)
    \item Write Join Output: Depends on result size.
    \end{itemize}
\end{enumerate}

\textbf{Total Cost:}
\[
\text{Cost} = \left( 2 \times \text{num\_passes(R)} \times \text{NPages(R)} \right) + \left( 2 \times \text{num\_passes(S)} \times \text{NPages(S)} \right) + \text{NPages(R)} + \text{NPages(S)} + \text{Write Cost}
\]

\textbf{Explanation:}
\begin{itemize}
\item Sorting involves multiple passes; each pass reads and writes the data.
\item Merge phase reads sorted relations once.
\item Write cost for join output depends on result size.
\end{itemize}

\section{6. Projections Cost}

Evaluates the cost associated with projection operations in query processing.

\subsection{a. Sort-Based Projection}

\textbf{Breakdown:}
\begin{enumerate}
\item \textbf{Read Original Relation:} \(\text{NPages(R)}\)
\item \textbf{Write Projected Relation:} \(\text{NPages(R)} \times \text{PF}\)
\item \textbf{Sorting Phase:}
    \begin{itemize}
    \item Initial Read: \(\text{NPages(R)} \times \text{PF}\)
    \item Write Runs: \(\text{NPages(R)} \times \text{PF}\)
    \item Subsequent Passes (per pass): \(2 \times \text{NPages(R)} \times \text{PF}\)
    \item Total Sorting Cost: \(2 \times \text{num\_passes} \times \text{NPages(R)} \times \text{PF}\)
    \end{itemize}
\item \textbf{Read Sorted Projected Relation:} \(\text{NPages(R)} \times \text{PF}\)
\end{enumerate}

\textbf{Total Cost:}
\[
\begin{split}
\text{Cost} = &\ \text{NPages(R)} \quad (\text{Read Original}) \\
&+ \left( \text{NPages(R)} \times \text{PF} \right) \quad (\text{Write Projected}) \\
&+ 2 \times \text{num\_passes} \times \left( \text{NPages(R)} \times \text{PF} \right) \quad (\text{Sorting}) \\
&+ \left( \text{NPages(R)} \times \text{PF} \right) \quad (\text{Read Sorted Projected})
\end{split}
\]

\subsection{b. Hash-Based Projection}

\textbf{Breakdown:}
\begin{enumerate}
\item \textbf{Read Original Relation:} \(\text{NPages(R)}\)
\item \textbf{Write Projected Relation:} \(\text{NPages(R)} \times \text{PF}\)
\item \textbf{Hashing Phase:}
    \begin{itemize}
    \item Read Projected Relation: \(\text{NPages(R)} \times \text{PF}\)
    \item Write Hashed Buckets: \(\text{NPages(R)} \times \text{PF}\) (in partitions)
    \item Read Hashed Buckets: \(\text{NPages(R)} \times \text{PF}\)
    \end{itemize}
\item \textbf{Eliminate Duplicates:} Processing in memory (minimal I/O if fits in memory)
\end{enumerate}

\textbf{Total Cost:}
\[
\text{Cost} = \text{NPages(R)} + 2 \times \left( \text{NPages(R)} \times \text{PF} \right) + \text{Hash Read/Write Cost}
\]

\textbf{Note:} \text{Hash Read/Write Cost} may be additional if partitions don't fit in memory.

\section{Additional Explanations}

\subsection{Breaking Down Costs into Components}

\textbf{Why Break Down Costs?}
Breaking down the total cost into components such as reading, writing, and processing helps in:

\begin{itemize}
\item Understanding which operations dominate the cost.
\item Identifying optimization opportunities (e.g., reducing disk I/O).
\item Comparing different algorithms more effectively.
\end{itemize}

\subsection{Cost Components Explanation}

\begin{itemize}
\item \textbf{Read Cost:} Cost of reading data pages from disk into memory.
\item \textbf{Write Cost:} Cost of writing data pages from memory back to disk.
\item \textbf{Processing Cost (CPU):} Cost associated with in-memory operations, such as comparisons, hashing, and sorting. Usually less significant than I/O costs.
\item \textbf{Random vs. Sequential I/O:} Random I/O is more expensive due to disk seek times. Sequential I/O benefits from faster data transfer rates.
\end{itemize}

\subsection{Importance of Disk I/O in Query Processing}

Disk I/O operations are often the most significant factor in query processing costs because accessing data from disk is much slower than accessing data from memory. Therefore, algorithms that minimize disk I/O, especially random I/O, are generally more efficient.

\section{Summary of Conditions for Formula Validity}

To ensure the correct application of the formulas, the following conditions must be met:

\begin{itemize}
\item \textbf{Uniform Distribution:} Many formulas assume uniform distribution of key values or selected values.
\item \textbf{Sufficient Buffer Space:} Algorithms like Block-Oriented Nested Loop Join require sufficient buffer space to minimize disk I/O operations.
\item \textbf{Index Availability:} Index-based costs assume the presence and type (clustered or unclustered) of specific indexes.
\item \textbf{Independent Selections:} Reduction factors are multiplicative under the assumption of independent selection predicates.
\item \textbf{Join Key Independence:} Join reduction factors assume independence between join key distributions.
\item \textbf{Non-Range Query Limitations:} Certain indexing methods (e.g., unclustered and hash indexes) are not suitable for range queries, affecting their applicability and cost.
\item \textbf{Projection Requirements:} Projection operations may require sorting or hashing based on the projection method, influencing their cost.
\item \textbf{Hash Function Quality:} For hash indexes and hash joins, the quality of the hash function affects the number of collisions and, consequently, the cost.
\item \textbf{Disk I/O Dominance:} Disk I/O operations are often the bottleneck in query execution costs, emphasizing the need to minimize them.
\end{itemize}

\section{Conclusion}

Understanding and correctly applying these query processing cost formulas is essential for optimizing database queries. By breaking down the costs into fundamental components such as reading, writing, and processing, we gain deeper insights into the efficiency of different query execution strategies. This detailed analysis enables database professionals to make informed decisions when choosing algorithms and optimizing queries, ultimately leading to better performance and resource utilization.

\end{document}
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
MAKE SURE ALL THE ABOVE FORMULAS ARE THE SAME AS WHATS WRITTEN IN THE EXPLANATION. IF THE FORM OF THE FORMULA IS DIFFERENT, REWRITE IT SO THAT IT IS CLOSER TO THE FORMULAS ON THE BOTTOM