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

\geometry{a4paper, margin=1in}

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

\newcommand{\readop}[1]{\textcolor{blue}{#1}}   % Reading costs
\newcommand{\writeop}[1]{\textcolor{red}{#1}}   % Writing costs
\newcommand{\sortop}[1]{\textcolor{purple}{#1}} % Sorting costs
\newcommand{\probeop}[1]{\textcolor{green}{#1}} % Probing costs

\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 numbers of tuples of 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). \\
\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)}}
\]

\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)}}
\]

\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)}}
\]

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

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

\subsection{e. No Information Available}

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

\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}
\]

\subsection{b. Joins}

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

\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{Height(I)} + 1
\]

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

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

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

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

\subsection{b. Hash Index}

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

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

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

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

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

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

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

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

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

\section{5. Joins (Between Relations \texttt{R} and \texttt{S}, \texttt{R} = Outer, \texttt{S} = Inner)}

Evaluates the cost of different join algorithms between two relations.

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

\textbf{Description:}

In Nested Loop Join, for each tuple in the outer relation \texttt{R}, we scan the entire inner relation \texttt{S} to find matching tuples. There are three variations:

\subsubsection{i. Tuple-Oriented NLJ}

\textbf{Cost Formula:}

\[
\text{Cost} = \readop{\text{NPages(R)}} + \readop{\text{NTuples(R)} \times \text{NPages(S)}}
\]

\textbf{Explanation:}

\begin{itemize}
    \item \readop{\textbf{Reading Outer Relation \texttt{R}:}} We read all pages of \texttt{R}, which costs \(\text{NPages(R)}\).
    \item \readop{\textbf{Reading Inner Relation \texttt{S} for Each Tuple of \texttt{R}:}} For each of the \(\text{NTuples(R)}\) tuples in \texttt{R}, we read all pages of \texttt{S}, costing \(\text{NTuples(R)} \times \text{NPages(S)}\).
\end{itemize}

\subsubsection{ii. Page-Oriented NLJ}

\textbf{Cost Formula:}

\[
\text{Cost} = \readop{\text{NPages(R)}} + \readop{\text{NPages(R)} \times \text{NPages(S)}}
\]

\textbf{Explanation:}

\begin{itemize}
    \item \readop{\textbf{Reading Outer Relation \texttt{R}:}} Read all pages of \texttt{R}, costing \(\text{NPages(R)}\).
    \item \readop{\textbf{Reading Inner Relation \texttt{S} for Each Page of \texttt{R}:}} For each page in \texttt{R}, we read all pages of \texttt{S}, costing \(\text{NPages(R)} \times \text{NPages(S)}\).
\end{itemize}

\subsubsection{iii. Block-Oriented NLJ (Block Size \texttt{B})}

\textbf{Cost Formula:}

\[
\text{Cost} = \readop{\text{NPages(R)}} + \readop{\left\lceil \dfrac{\text{NPages(R)}}{\text{B} - 2} \right\rceil \times \text{NPages(S)}}
\]

\textbf{Explanation:}

\begin{itemize}
    \item \readop{\textbf{Reading Outer Relation \texttt{R}:}} We read all pages of \texttt{R}, costing \(\text{NPages(R)}\).
    \item \readop{\textbf{Processing Blocks of \texttt{R}:}} We divide \texttt{R} into blocks that fit into the buffer (size \(\text{B} - 2\) to reserve space for input and output buffers).
    \item \readop{\textbf{Reading Inner Relation \texttt{S} for Each Block of \texttt{R}:}} For each block, we read all pages of \texttt{S}, costing \(\left\lceil \dfrac{\text{NPages(R)}}{\text{B} - 2} \right\rceil \times \text{NPages(S)}\).
\end{itemize}

\subsection{b. Hash Join}

\textbf{Description:}

Hash Join uses a hash function to partition both relations into buckets, which allows matching tuples to be in the same bucket. It generally operates in two phases: the partitioning phase and the probing phase.

\textbf{Cost Formula:}

\[
\text{Cost} = 3 \times (\text{NPages(R)} + \text{NPages(S)})
\]

\textbf{Explanation:}

Breakdown of the cost:

\begin{itemize}
    \item \readop{\textbf{Reading Relations (Partitioning Phase):}} Read all pages of \texttt{R} and \texttt{S}, costing \(\text{NPages(R)} + \text{NPages(S)}\).
    \item \writeop{\textbf{Writing Partitions:}} Write the partitioned data of \texttt{R} and \texttt{S}, costing \(\text{NPages(R)} + \text{NPages(S)}\).
    \item \readop{\textbf{Reading Partitions (Probing Phase):}} Read all partitions of \texttt{R} and \texttt{S} during the join, costing \(\text{NPages(R)} + \text{NPages(S)}\).
\end{itemize}

\textbf{Total Cost:}

\[
\text{Cost} = \readop{2 \times (\text{NPages(R)} + \text{NPages(S)})} + \writeop{(\text{NPages(R)} + \text{NPages(S)})}
\]

\subsection{c. Sort-Merge Join (SMJ)}

\textbf{Description:}

Sort-Merge Join first sorts both relations on the join key and then merges them by scanning them sequentially.

\textbf{Cost Formula:}

\[
\begin{aligned}
\text{Cost} &= \text{Sorting Cost} + \text{Merge Join Cost} \\
&= \sortop{2 \times \text{NPages(R)} \times \text{num\_passes(R)}} + \sortop{2 \times \text{NPages(S)} \times \text{num\_passes(S)}} \\
&\quad + \readop{\text{NPages(R)} + \text{NPages(S)}}
\end{aligned}
\]

\textbf{Explanation:}

\begin{itemize}
    \item \sortop{\textbf{Sorting \texttt{R}:}} The cost to sort \texttt{R} is \(2 \times \text{NPages(R)} \times \text{num\_passes(R)}\). Each pass involves reading and writing all pages of \texttt{R}.
    \item \sortop{\textbf{Sorting \texttt{S}:}} Similarly, sorting \texttt{S} costs \(2 \times \text{NPages(S)} \times \text{num\_passes(S)}\).
    \item \readop{\textbf{Merge Phase:}} After sorting, we read the sorted relations once during the merge join, costing \(\text{NPages(R)} + \text{NPages(S)}\).
\end{itemize}

\textbf{Total Cost Simplified:}

\[
\text{Cost} = \sortop{2 \times \left( \text{NPages(R)} \times \text{num\_passes(R)} + \text{NPages(S)} \times \text{num\_passes(S)} \right)} + \readop{\text{NPages(R)} + \text{NPages(S)}}
\]

\textbf{Note:} The initial read of the relations during the sorting phase is included in the sorting cost.

\section{6. Projections Cost}

Evaluates the cost associated with projection operations in query processing.

\subsection{a. Sort-Based Projection}

\textbf{Total Cost:}

\[
\text{Cost} = \readop{\text{NPages(R)}} + \writeop{\text{NPages(R)} \times \text{PF}} + \sortop{2 \times \text{num\_passes} \times (\text{NPages(R)} \times \text{PF})}
\]

\textbf{Explanation:}

\begin{itemize}
    \item \readop{\textbf{Reading Table:}} Read all pages of \texttt{R}, costing \(\text{NPages(R)}\).
    \item \writeop{\textbf{Writing Projected Data:}} Write the projected columns to disk, costing \(\text{NPages(R)} \times \text{PF}\).
    \item \sortop{\textbf{Sorting Projected Data:}} Sort the projected data to eliminate duplicates, costing \(2 \times \text{num\_passes} \times (\text{NPages(R)} \times \text{PF})\) (each pass reads and writes the data).
\end{itemize}

\subsection{b. Hash-Based Projection}

\textbf{Total Cost:}

\[
\text{Cost} = \readop{\text{NPages(R)}} + \writeop{\text{NPages(R)} \times \text{PF}}
\]

\textbf{Explanation:}

\begin{itemize}
    \item \readop{\textbf{Reading Table:}} Read all pages of \texttt{R}, costing \(\text{NPages(R)}\).
    \item \writeop{\textbf{Writing Projected Data:}} Write the projected columns after hashing to remove duplicates, costing \(\text{NPages(R)} \times \text{PF}\).
    \item \textbf{Note:} In this simplified model, we do not account for the cost of reading the hashed partitions during duplicate elimination, as per curriculum scope.
\end{itemize}

\end{document}
For the indexing costs, also include a description of poetential limitaitons, ie unclustered has index can't be worked on range queries. Write the code in full without fail