Query Processing

The query optimizer does magic to find a good way to execute queries. There is an inherent tradeoff between finding the “best” plan and finding it quickly.

“Find sailor names who have reserved boat ID 103 and have a rating >5”

SELECT name
FROM Sailors S, Reserves R
WHERE S.id = R.sid
	AND bid = 103
	AND rating > 5

${\pi }_{\text{name}}({\sigma }_{\text{bid}=103\wedge \text{rating}>5}(\text{Sailors}{\bowtie }_{\text{S.sid}=\text{R.sid}}\text{Reserves}))$
or ${\pi }_{\text{name}}({\sigma }_{\text{rating}>5}(\text{Sailors}{\bowtie }_{\text{S.sid}=\text{R.sid}}{\sigma }_{\text{bid}=103}(\text{Reserves})))$
or ${\pi }_{\text{name}}({\sigma }_{\text{rating}>5}(\text{Sailors}){\bowtie }_{\text{S.sid}=\text{R.sid}}{\sigma }_{\text{bid}=103}(\text{Reserves}))$

This final one minimizes the data going into the join

How does it work?

1. Find the relational algebra equivalences, storing as relational algebra (RA) trees
2. Estimate the cost of different RA trees, using the size of the query result set, cost estimation for I/O and CPU
3. Explore the search space for different operations, like the choice of join algorithm, order of operations, index selection, etc.

A bad query processor does the simplest route, computing the cross product on all relations and then applying each selection predicate.

A good query optimizer picks a “good” plan “quickly,” using a faster implementation technique for each operator, exploring fast but equivalent query plans, and using cost modeling to find the cheapest plans

Optimizing Selection

Say you have two relations,
Sailor: sid, name, rating, age

• Tuple length $t_S=50$ B
• Tuples per page $B_S=80$
• Total pages $P_S=500$
  Reserves: sid, bid, day, rname
• Tuple length $t_R=40$ B
• Tuples per page $B_R=100$
• Total pages $P_R=1000$

Therefore, there are $40$K sailor tuples that take up $2$MB and $100$K reserves tuples that take up $4$MB

Selections can be point or range queries. To facilitate a query efficiently,

1. Check for indexes
2. Estimate the size of the result
3. Think about the access path

Selectivity $s$ (ranges from 0-1) is used to estimate the percentage of tuples that will qualify for a selection clause

When estimating a point query, if

1. Relation $R$ is stored as a heap file with no index: scan until the entry is found $P_R/2$
2. $R$ is stored as sorted on the query attribute with no index: binary search ${\log }_2{P}_R$
3. $R$ has an index on the query attribute
   probe the tree-index, read the data ${\log }_F{P}_R+1$
   or probe the hash-index, read the data $1.2+1$ (20% collision rate)

Indexes are super helpful on heap files, but not as important on sorted files.

When estimating a range query, if

1. Relation $R$ is stored as a heap file with no index: scan the whole file $P_R$
2. $R$ is sorted on the query attribute with no index: binary search and then scan to the end of the range ${\log }_2{P}_R+P_R\cdot s$
   Now if $P_R=1000$ and $s=0.1$ then the cost is $200$ I/Os
   If $s=1$ then the cost comes out to $1100$ I/Os, which means the binary search was redundant
3. $R$ has a clustered index on the query attribute: index probe, scan to the end of the range ${\log }_F{P}_R+P_R\cdot s$
4. $R$ has an unclustered index on the query attribute: index probe, scan each resulting page ${\log }_F{P}_R+(P_R\cdot B_R)\cdot s$

This last one is quite bad! A good query optimizer wouldn’t try to do this and would rather scan the heap file directly. The situation can be improved by fetching all the page IDs found from the index and then fetching them in order. This way, the same pages are not read more than once.

Optimizing Projections

SQL does not remove duplicates by default, so we must use DISTINCT

1. Read all qualifying tuples
2. Sort the result set (lexicographically)
3. Remove adjacent duplicates

If $P_R=1000$, $B_R=100$, $t_R=40$B, and the output size is $10$B
The total cost involves,

1. Reading $R$ and filtering necessary attributes $1000+250$
2. Sorting the runs takes $2\cdot 250$ and merging the runs takes another $2\cdot 250$
3. Then removing duplicates takes another $250$

The total here is 2500 I/Os

We can do better with in-memory heapsort, which has an average run length of $2\cdot B$

1. 1000 pages on disk are read $B-1$ pages at a time, 1000 I/Os
2. The individual pages are sorted and then filtered before going through the output buffer, 250 I/Os
3. In-memory heap sort $\lceil 250/(2\cdot 20)\rceil =7$ runs, remove duplicates on the fly as we merge in Pass 1, 250 I/Os

This makes a total of 1500 I/Os

Optimizing Joins

Joins are one of the most common operations in databases. Any interesting query has a join. However, they can also be very costly, especially if executed poorly.

The simplest join query

SELECT *
FROM Reserves R, Sailors S
WHERE R.sid = S.sid

The worst way you could do this is with a cross-product $R\times S$.

Simple nested-loop join,
$\forall$ tuple $r\in R$
$\forall$ tuple $s\in S$
if $r.\text{attr}==s.\text{attr}$, add $⟨r,s⟩$ to result
This is pretty bad, clearly there are many redundant I/Os and the cost is $P_R+(P_R\cdot B_R)\cdot P_S$
However, note that swapping the inner and outer relation does affect the cost

Page-oriented nested-loop join does first clear optimization for this procedure
$\forall$ page $P_R\in R$
$\forall$ page $P_S\in S$
$\forall$ tuple $r\in P_R$
$\forall$ tuple $s\in P_S$
if $r.\text{attr}==s.\text{attr}$, add $⟨r,s⟩$ to result
This is better, the cost is $P_R+P_R\cdot P_S$ I/Os

Index nested-loop join,
$\forall$ tuple $r\in R$
probe index on $S$
fetch tuple $s\in S$
such that $r.\text{attr}==s.\text{attr}$
add $⟨r,s⟩$ to result
This is much better, the cost is $P_R+(P_R\cdot B_R)\cdot (\text{index cost}+\text{expected matches})$
$\text{index cost}$ is the probe cost (about 3 I/Os for a $B^{+}$-tree index and 1.2 I/Os for a hash index
In this case, $\text{expected matches}$ is 1, since each $R$ refers to one $S$ (the relation is listed at the top of this document)

Block nested-loop join
Now what if we have $B$ buffers?

• 1 page is used to store the intermediate result
• 1 page is used to stream the inner relation $S$
• $B-2$ pages are used to store $B-1$ pages of the outer relation $R$

$\forall$ block of $B-2$ pages of $R$
$\forall$ page $P_S\in S$
$\forall$ tuple $r\in B-2$ pages of $R$
$\forall$ tuple $s\in P_S$
if $r.\text{attr}==s.\text{attr}$, add $⟨r,s⟩$ to result

The cost is $P_R+P_S\cdot \lceil \frac{P_R}{B-2}\rceil$

Sort-merge join
This takes two phases,

1. Sort: Sort both relations on the join attribute
2. Merge: Parse through the two sorted relations to find matching tuples

sort $R$ on the join attribute (sid)
sort $S$ on the join attribute (sid)
${\text{it}}_{\text{R}}\to {\text{R}}_{\text{sorted}}$; ${\text{it}}_{\text{S}}\to {\text{S}}_{\text{sorted}}$;
while ${\text{it}}_{\text{R}}$ and ${\text{it}}_{\text{S}}$
if ${\text{it}}_{\text{R}}>{\text{it}}_{\text{S}}$
increment ${\text{it}}_{\text{S}}$
if ${\text{it}}_{\text{R}}<{\text{it}}_{\text{S}}$
increment ${\text{it}}_{\text{R}}$
backtrack ${\text{it}}_{\text{S}}$ if necessary
else if ${\text{it}}_{\text{R}}={\text{it}}_{\text{S}}$
add $⟨r,s⟩$ to result
increment ${\text{it}}_{\text{S}}$

Backtracking is only necessary because of duplicate values

The best case cost of merging is the $P_S+P_R$
The worst case cost of merging is $P_S\cdot P_R$
Sorting (with external merge sort) takes $2\cdot P_R\cdot (1+\lceil {\log }_{B-1}{P}_R/B\rceil )+2\cdot P_S\cdot (1+\lceil {\log }_{B-1}{P}_S/B\rceil )$
This gets significantly better with more buffers

Sort-merge is useful in cases when the join output is expected to be sorted on the join attribute, or when either relation is already sorted

It should be avoided if either relation has many duplicates

Hash join
Again, there are two phases,

1. Hashing/Building: Use a hash function $h_1$ on the join attribute to populate the hash table
2. Probing: Scan the inner relation page-wise, use the same hash function $h_1$ to probe for matching tuples

$\forall$ tuple $r\in R$
hash $h_1(r)$ into hash table ${\text{HT}}_{\text{R}}$
$\forall$ tuple $s\in P_S$
if $h_1(s)\in {\text{HT}}_{\text{R}}$, add $⟨r,s⟩$ to result

In the hash table, we store key + value/id

The total cost is $P_R+P_S$
However, this requires that $P_R$ fits in memory

Partitioned hash join
Two phases,

1. Partitioning/Building: Use $h_1$ on the join attribute to create partitions, on both relations
2. Probing: Fetch partitions to memory, use a different hash function $h_2$ to probe and find matching tuples

First all the $R$ tuples are hashed, then all the $S$ tuples are hashed
When a buffer page is filled, it’s moved to memory as a partition

Then, for each potentially matching partition pair, we bring the partitions into memory, run a second hash function on them on a new table, and any matches are recorded

Each relation must be read, written, and read again: $3\cdot (P_R+P_S)$

If the smaller of the two partitions does not fit in $B-2$ pages then it must be further partitioned