Query Optimisation

To efficiently process a query, a RDBMS needs to be able optimise certain relational operators which are the backbone of every query. The main operations it needs to be able to perform and optimise are selection, projection and joins.

We use the same basic operation to

Also note that:

• $n$ = Number of records in the table
• $n_{pages}$ = Number of pages in the table

Selection §

Recall what a selection is:

In order to optimise a selection, a DBMS needs to know:

1. All available indexes/pointers to records (to actually find the files)
2. The expected size of the result i.e. number of pages (to know when to stop looking)

Reducing Factor §

A DBMS uses it’s optimiser to estimate the expected size using reducing factors, which is a fraction per predicate, which is a basic relational statement (i.e. involves only one relational comparators):

$$\text{Estimated Output Size}=\text{Size of relation}\times \prod _{i=1}^n{\text{RF}}_i$$

• $\text{RF}$: Reducing factor (also called selectivity), a fraction that states how many records satisfy the associated predicate
• $n$: Number of predicates/ basic relational statements

Once the estimated size is obtained, the DBMS can search through the database file structure to find records matching the selection criteria:

Searching: Heap Files §

For heap files (unsorted files), it needs to linear search through every single record so it doesn’t miss anything.

%%🖋 Edit in Excalidraw, and the dark exported image%%

$$\text{I/O Operations}=n_{pages}$$

Searching: Sorted Files §

For sorted files, the DBMS can simply binary search to find the first record matching condition, then iterate till until the estimate size of records have been scanned

%%🖋 Edit in Excalidraw, and the dark exported image%%

$$\text{I/O Operations}=\text{Binary search I/O Cost}+e_{pages}=\text{Binary search I/O Cost}+\text{RF}\cdot n_{pages}$$

$$={\log }_2(n_{pages})+\text{RF}\cdot n_{pages}$$

Searching Through Indexed Files §

First the DBMS needs to traverse through the B+ Tree (or use the hash table if the index is hash-based) to find indexes that satisfy the criteria.

Hash-based Indexes Only Work On Equality Checks!

Then, linearly iterate through the indexes (note that the indexes would be stored in their own pages, which need to be brought to RAM). Let $i_{pages}$ be the number of pages occupied by indexes.#todo B-tree has leaf nodes doubly linked.

If the indexes are clustered, then the total cost is:

$$\text{I/O Operations}=(i_{pages}+n_{pages})\cdot \text{RF}$$

Why? Every index points to a record, and so if only $\text{RF}\cdot n$ records satisfy the criteria, then we only need to iterate through $\text{RF}\cdot i$ indexes. For each index, we need to load up the page it points to, but because the indexes are clustered, many of the indexes point to the same page.

If the indexes are unclustered, then the total cost is:

$$\text{I/O Operations}=(i_{pages}+n)\cdot \text{RF}$$

This is because the index lookup does not guarantee indexes pointing to records in the same page (due to the unclustered nature), so we need do an I/O operation for each record (total $n$ records).

Composed Selection Criteria §

In most cases, the selection criteria contains multiple predicates, involving multiple attributes/columns.

A tree-based index can only match predicates that involve attributes in the prefix of the search key fields . What this means is that if we have a composed selection criteria of multiple predicates, an indexed database is only useful if at least one predicate has any of the prefixes of the search key field(s)

Predicates must involve search key field to be optimised

If we have a index on column $a$, we can only optimise selections if they have predicates involving $a$.

On the fly checking is checking predicates that are not part of the search key fields. It does not contribute to the I/O cost, because the page is already loaded when checking from key fields.

In terms of reduction factors, we only have them if the predicates involve search keys:

Example: Three different selections

Assume we have a database containing columns $a,b,c$ with a unclustered index on column $a,b$ (i.e. our indexes are $(a,b)$) Look at the following selection criteria:

• $a>5$
• $a=4\wedge b>5$
• $b>5\wedge c=5$
• $a<4\wedge b>7\wedge c=3$
• $c=2$
  The size estimations would be as follows:

1. $n\cdot \text{RF}(a)$ : Reduction factor involving $a$, because $(a)$ is a prefix of $(a,b)$
2. $n\cdot \text{RF}(a)\cdot \text{RF}(b)$: Reduction factors involving both $a$ and $b$, because $(a,b)$ is a prefix of $(a,b)$
3. $n$: No reduction factors, because $(b)$ is not a prefix of $(a,b)$. Would need to perform a full table scan
4. $n\cdot \text{RF}(a)\cdot \text{RF}(b)$: Reduction factors only involve $a$ and $b$ and $c$ needs to be checked on the fly
5. $n$: No reduction factors because $(c)$ is not in $(a,b)$

Projection §

Recall projection is:

Notice the Duplicate elimination warning? That’s what the DBMS aims to optimise: elimination of duplicates

Projecting Factor §

Like with the reducing factor for selection, the projecting factor is a ratio of projected columns to total columns, which lets us know what percentage of attributes are being projected. The DBMS uses this to estimate how much space the final output will take.

$$\text{PF}=\text{Projecting Factor}=\frac{n_{projected}}{n_{columns}}$$

This can be done by either sorting the data using sorting algorithms (which guarantees duplicates are next to each other) or use hash collisions

The main complication with sorting is that the data stored in disk is mostly much larger than the maximum space in RAM (where it can be processed). To solve this, we use an external sorting algorithm.

External Merge §

The main method for this is with external merge sort:

In terms of O operations, external merge sort over $n_{pages}$ has a runtime of:

$$2\cdot n_{passes}\cdot n_{pages}$$

There is a factor of two because we need to both read & write data when sorting.

Hash-based §

#todo

Operation Cost §

The total cost to remove duplicates with external merge sort is:

1. Reading the entire table, so we only keep the attributes that need to be projected: $n_{pages}$
2. Write pages with projected attributes to disk: $n_{pages}\times \text{PF}$
3. Sort pages with projected attributes using external merge sort: $2\cdot n_{passes}\cdot (n_{pages}\cdot \text{PF})$
4. Read sorted projected pages to discard adjacent duplicates: $n_{pages}\times \text{PF}$

Joins §

Joins are generally very expensive to perform, and in the worst case result in the cross product. Out of all the possible joins, the natural join is the most commonly queried one, and hence need to be the most optimised. A RDBMS can implement a join in many ways:

• Nested-loop joins
  • Simple nested-loop join
  • Page based nested-loop join
  • Block nested-loop join
• Sort-merge join
• Hash join

Simple Nested-Loop Join §

The most straight-forward method of performing a natural join over unsorted files is using a nested for-loop:

Algorithm SimpleNestedLoopJoin(A: Table, B: Table):
	For each tuple a in A do:
		For each tuple b in B do:
			If a.attribute == b.attribute then:
				Add (a,b) to the Join
			End If
		End do
	End do
	Return Join
End Algorithm

The final join is unsorted.

Total cost:

$$n_{pages}(A)+n_{tuples}(A)\cdot n_{pages}(B)$$

Page-based Nested-Loop Join §

Page-based nested-loop joins exploit the fact that multiple tuples are stored in a single page, so we can start by loading a page and then comparing every tuple in that page in order to minimise the number of I/O operations.

Algorithm PageBasedNestedLoopJoin(A: Table, B: Table):
	For each page a_page in A do:
		For each page b_page in B do:
			For each tuple a in A do:
				For each tuple b in B do:
					If a.attribute == b.attribute then:
						Add (a,b) to the Join
					End If
				End do
			End do
		End do
	End do
	Return Join
End Algorithm

The final join is unsorted.

Because we measure our total runtime in terms of page accesses, once we access a page, any tuples in it do not add extra time. Hence the final cost is:

$$n_{pages}(A)+n_{pages}(A)\cdot n_{pages}(B)$$

Block Nested-Loop Join §

A further optimisation is to exploit as much main memory (RAM) available. The block-based nested-loop join first reserves two pages in the RAM for an input and output buffer to reduce the number of I/O operations.

Assume we are treating $A$ as the outer loop table, and $B$ as the inner loop table

If the maximum capacity of the RAM (in pages) is $n$, then the block-based approach reads in $n-2$ sized ‘blocks’ of pages of $A$, comparing it with the input buffer for $B$. If the join conditions are satisfied, then writes $(A,B)$ to the output buffer page.

• Whenever the $n-2$ block is fully read, read in a new block (of $A$) from disk
• Whenever the input buffer is read, read in a new page (of $B$) from disk
• Whenever the output buffer is full, flush it (write to disk)

%%🖋 Edit in Excalidraw, and the dark exported image%%

The total I/O operations are:

$$n_{pages}(A)+n_{blocks}(A)\ast n_{pages}(B)$$

$$n_{blocks}(A)=\lceil \frac{n_{pages}(A)}{n-2}\rceil$$

Sort-Merge Join §

The sort-merge join is an improvement over nested-loop joins, because once $A$ and $B$ are sorted, there is no need to check all of $B$ for a single value of $A$, since if we have a value $B.id>A.id$, every value of $B$ after fails to satisfy the condition, so we can stop checking.

The ‘merging’ operation is simply taking the column values of $A$ and $B$ and merging them to form the join $A\bowtie B$.

$A$ is always only scanned once, and (approximately), $B$ is scanned once. Technically, there would be multiple scans when $B$ has duplicates, but the amortised cost is that $B$ is only scanned once.

The total I/O cost is:

$$sort(A)+sort(B)+n_{pages}(A)+n_{pages}(B)$$

Assuming we use external merge sort:

$$2\cdot n_{passes}(A)\cdot n_{pages}(A)+2\cdot n_{passes}(B)\cdot n_{pages}(B)+n_{pages}(A)+n_{pages}(B)$$

$$=n_{pages}(A)(1+2\cdot n_{passes}(A))+n_{pages}(B)(1+2\cdot n_{passes}(B))$$

Hash Join §

#todo

General Join Conditions §

For composed join conditions that consists of only equality checks, i.e. equi-joins, we can use any of the join techniques, with sort-merge join and hash join giving the best runtimes:

• For sort-merge join, sort over the combination of columns in $A$ and $B$. For example, if we have the join: $A{\bowtie }_{A.id=B.id\wedge A.age=B.id}B$ we sort $A$ with the combination of $(id,age)$ (this can be done by string concatenation, for example), and sort $B$ over $id$.
• For hash join, we partition over the combination of columns

For joins containing inequalities in their join conditions, i.e. theta-joins, we cannot* use hash join or sort-merge join! The best option is to use block nested-loop join.