\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). \\
\texttt{$\prod$\texttt{RFi}} & The product of all reduction factors \texttt{RFi} applied in a query. \\
\texttt{$\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. \\ \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{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}

\textbf{Explanation:}
The cost includes traversing the index tree to its height (i.e., the number of levels) and accessing the data page containing the tuple.

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

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

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

\textbf{Explanation:}
The cost accounts for accessing the index pages (\texttt{NPages(I)}), accessing the clustered data pages (\texttt{NPages(R)}), and applying the reduction factors.

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

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

\textbf{Conditions:}
\begin{itemize}
    \item Applicable when using an unclustered B\textsuperscript{+}-Tree index to retrieve multiple tuples.
    \item Unclustered index implies that data pages are not ordered and may require random access.
    \item **Limitation:** Unclustered indexes are inefficient for range queries.
\end{itemize}

\textbf{Explanation:}
The cost includes accessing the index pages (\texttt{NPages(I)}}) and accessing individual data pages for each tuple (\texttt{NTuples(R)}), scaled by the reduction factors.

\subsection{b. Hash Index}

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

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

\textbf{Conditions:}
\begin{itemize}
    \item Applicable when performing a selection based on a primary key using a hash index.
    \item Retrieving a single tuple.
    \item **Limitation:** Hash indexes are not suitable for range queries.
\end{itemize}

\textbf{Explanation:}
A fixed cost incurred for hashing and accessing the tuple, comprised of 1.2 disk I/O units for hashing and 1 disk I/O unit for data access.

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

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

\textbf{Conditions:}
\begin{itemize}
    \item Applicable when using a clustered hash index to retrieve multiple tuples.
    \item Assumes that multiple tuples can be accessed efficiently due to clustering.
    \item **Limitation:** Even with clustering, hash indexes are inefficient for range queries.
\end{itemize}

\textbf{Explanation:}
The cost includes accessing the relevant data pages (\texttt{NPages(R)}), applying the reduction factors, and the fixed cost per tuple retrieval.

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

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

\textbf{Conditions:}
\begin{itemize}
    \item Applicable when using an unclustered hash index to retrieve multiple tuples.
    \item Each tuple may require separate access, leading to potentially higher costs.
    \item **Limitation:** Unclustered hash indexes cannot efficiently handle range queries.
\end{itemize}

\textbf{Explanation:}
The cost accounts for accessing each tuple individually in an unclustered manner, scaled by the reduction factors and the fixed retrieval cost.

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

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

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

\textbf{Conditions:}
\begin{itemize}
    \item Applicable when performing a full table scan (heap scan) without utilizing any indexes.
\end{itemize}

\textbf{Explanation:}
The cost is simply the number of pages in the relation since each page must be read sequentially.

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

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

\textbf{Conditions:}
\begin{itemize}
    \item Applicable when performing a tuple-by-tuple nested loop join.
    \item \texttt{R} is the outer relation and \texttt{S} is the inner relation.
    \item No indexes are used; hence, each tuple from \texttt{R} requires a full scan of \texttt{S}.
\end{itemize}

\textbf{Explanation:}
The cost includes reading all pages of \texttt{R} once, and for each tuple in \texttt{R}, scanning all pages of \texttt{S}.

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

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

\textbf{Conditions:}
\begin{itemize}
    \item Applicable when performing a page-by-page nested loop join.
    \item \texttt{R} is the outer relation and \texttt{S} is the inner relation.
    \item Utilizes page-level buffering to reduce the number of scans.
\end{itemize}

\textbf{Explanation:}
The cost includes reading all pages of \texttt{R} once, and for each page in \texttt{R}, scanning all pages of \texttt{S}.

\subsubsection{iii. Block-Oriented Nested Loop Join (Block Size \texttt{B})}

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

\textbf{Conditions:}
\begin{itemize}
    \item Applicable when performing a block-by-block nested loop join utilizing block I/O.
    \item \texttt{B} represents the number of buffer blocks available.
    \item At least three buffer blocks are required: one for each outer block and two for input/output operations.
\end{itemize}

\textbf{Explanation:}
The cost includes reading all pages of \texttt{R} once, and for each set of \(\text{B} - 2\) pages in \texttt{R}, scanning all pages of \texttt{S}. This approach reduces the number of scans on \texttt{S} by processing multiple pages of \texttt{R} simultaneously.

\subsection{b. Hash Join}

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

\textbf{Conditions:}
\begin{itemize}
    \item Applicable when performing a hash join between relations \texttt{R} and \texttt{S}.
    \item Assumes that both relations are being partitioned and probed using hash tables.
    \item Requires that the join attribute is suitable for hashing.
    \item **Limitation:** Not suitable for range-based join conditions.
\end{itemize}

\textbf{Explanation:}
The cost accounts for building and probing hash tables, typically requiring three passes (phases) over both relations.

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

\textbf{Conditions:}
\begin{itemize}
    \item Applicable when performing a sort-merge join between relations \texttt{R} and \texttt{S}.
    \item Assumes that both relations need to be sorted before merging.
    \item Requires that the join attribute is sortable.
    \item **Advantage:** Efficient for range-based join conditions due to sorted data.
\end{itemize}

\textbf{Explanation:}
The cost includes:
\begin{itemize}
    \item Reading both relations (\(\text{NPages(R)} + \text{NPages(S)}\)).
    \item Sorting both relations, which requires \(\text{num\_passes(R)}\) and \(\text{num\_passes(S)}\) passes, each involving reading and writing all pages twice for sorting.
    \item Merging the sorted relations.
\end{itemize}

\section{6. Projections Cost}

Evaluates the cost associated with projection operations in query processing.

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

\textbf{Conditions:}
\begin{itemize}
    \item Applicable when performing a projection using sort-based methods.
    \item \texttt{PF} represents the projection factor, indicating the fraction of columns retained after projection.
    \item Assumes that the projection results require sorting.
\end{itemize}

\textbf{Explanation:}
The cost components include:
\begin{itemize}
    \item Reading the entire table (\(\text{NPages(R)}\)).
    \item Writing the projected pages (\(\text{NPages(R)} \times \text{PF}\)).
    \item Sorting the projected pages, which involves multiple passes (\(2 \times \text{num\_passes} \times \text{NPages(R)} \times \text{PF}\)).
    \item Reading the sorted projected pages (\(\text{NPages(R)} \times \text{PF}\)).
\end{itemize}

\subsection{b. Hash-Based Projection}

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

\textbf{Conditions:}
\begin{itemize}
    \item Applicable when performing a projection using hash-based methods.
    \item \texttt{PF} represents the projection factor.
    \item Assumes that the projection does not require sorting.
\end{itemize}

\textbf{Explanation:}
The cost includes:
\begin{itemize}
    \item Reading the entire table (\(\text{NPages(R)}\)).
    \item Writing the projected pages (\(\text{NPages(R)} \times \text{PF}\)).
    \item Reading the projected pages (\(\text{NPages(R)} \times \text{PF}\)).
\end{itemize}

\section{Additional Explanations}

\subsection{Buffer Size (\texttt{B}) in Block-Oriented Nested Loop Join}

In the \textbf{Block-Oriented Nested Loop Join}, the buffer size \texttt{B} plays a crucial role in determining the number of blocks that can be loaded into memory simultaneously. The formula:

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

\textbf{Explanation:}
\begin{itemize}
    \item \texttt{B} represents the total number of buffer blocks available.
    \item \texttt{B - 2} accounts for the buffer blocks used for reading pages from \texttt{R} and writing intermediary results or for other operational buffers.
    \item The ceiling function \(\left\lceil \cdot \right\rceil\) ensures that partial blocks are considered as full blocks in the cost calculation.
\end{itemize}

\subsection{Handling Range Queries with Different Index Types}

\textbf{Unclustered Indexes:}
\begin{itemize}
    \item **Inefficient for Range Queries:** Unclustered indexes do not maintain the physical order of data, making it difficult to perform range queries efficiently. Each tuple satisfying the range condition may require accessing a different random page.
    \item **Increased Disk I/O:** Due to the lack of data ordering, range queries using unclustered indexes can significantly increase the number of disk I/O operations, as each qualifying tuple might be on a different data page.
\end{itemize}

\textbf{Clustered Indexes:}
\begin{itemize}
    \item **Efficient for Range Queries:** Clustered indexes maintain the physical order of data, allowing range queries to be executed with fewer disk I/O operations by accessing contiguous data pages.
    \item **Sequential Access Benefits:** Range queries can leverage sequential access patterns, reducing latency and improving overall query performance.
\end{itemize}

\textbf{Hash Indexes:}
\begin{itemize}
    \item **Not Suitable for Range Queries:** Hash indexes are designed for equality searches and do not support range queries effectively because the hashing mechanism does not preserve any order of the data.
    \item **Random Access Overhead:** Similar to unclustered indexes, hash indexes incur high disk I/O costs for range queries due to random data page accesses.
\end{itemize}

\subsection{Limitations of Hash Joins}

\begin{itemize}
    \item **Range-Based Joins:** Hash joins are not suitable for range-based join conditions as they rely on exact matches for efficient partitioning and probing.
    \item **Hash Function Dependence:** The efficiency of hash joins depends heavily on the quality of the hash function; poor hash functions can lead to excessive collisions, increasing the number of I/O operations.
\end{itemize}

\subsection{Projection Factor (\texttt{PF}) Impact}

\begin{itemize}
    \item **Higher \texttt{PF} Values:** Retaining more columns during projection increases the amount of data processed, leading to higher I/O costs for both sort-based and hash-based projection methods.
    \item **Lower \texttt{PF} Values:** Reducing the number of columns retained can decrease the I/O costs, making projection operations more efficient.
\end{itemize}

\subsection{Index Height (\texttt{Height(I)}})}

\begin{itemize}
    \item **Impact on Traversal Cost:** Higher index heights result in more levels to traverse in a B\textsuperscript{+}-Tree index, increasing the cost of index-based searches, especially for primary key lookups.
    \item **Balanced Trees:** Maintaining a balanced tree structure with minimal height optimizes traversal costs, ensuring faster query execution.
\end{itemize}

\section{Summary of Conditions for Formula Validity}

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

\begin{itemize}
    \item **Uniform Distribution:** Many formulas assume uniform distribution of key values or selected values.
    \item **Sufficient Buffer Space:** Algorithms like Block-Oriented Nested Loop Join require sufficient buffer space to minimize disk I/O operations.
    \item **Index Availability:** Index-based costs assume the presence and type (clustered or unclustered) of specific indexes.
    \item **Independent Selections:** Reduction factors are multiplicative under the assumption of independent selection predicates.
    \item **Join Key Independence:** Join reduction factors assume independence between join key distributions.
    \item **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 **Projection Requirements:** Projection operations may require sorting or hashing based on the projection method, influencing their cost.
    \item **Hash Function Quality:** For hash indexes and hash joins, the quality of the hash function affects the number of collisions and, consequently, the cost.
\end{itemize}

\section{Conclusion}

Understanding and correctly applying these query processing cost formulas is essential for optimizing database queries. Careful consideration of the conditions and assumptions underlying each formula ensures accurate cost estimations, leading to more efficient query execution strategies. Additionally, recognizing the limitations of various indexing methods, such as the inefficiency of unclustered and hash indexes for range queries, allows for more informed decisions in index selection and query optimization.

\end{document}
Also include the formula for the joins when considering the algorithm under a left deep join where previous information is stored or whatever im saying