Query Plan

y query plan is an expression tree with relational algebra operators as internal nodes and file access paths as links. Leaf nodes are databases. Query optimisation is used to reduce costs of each operation on the tree.

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

They are evaluated i n a ‘bottom-up’ approach, with the subtrees of a node being evaluated before the node itself. This is similar to post-order traversal, except nodes are evaluated instead of just being visited.

Generation §

Query Blocks §

The query optimiser simplifies a complex query into it’s basic query blocks:

• A query block is any statement that starts with a SELECT operation.
• The optimiser attempts to optimise innermost blocks first, that is subqueries first.

---Outer block
SELECT name FROM A
	WHERE age IN
	--Inner block
	SELECT MAX(age) FROM B

Conversion to Relational Algebra expressions §

Each query block is then converted to it’s corresponding relational algebra expression:

• SELECT attribute FROM S is converted to ${\pi }_{attribute}(S)$
• WHERE conditiion is converted to ${\sigma }_{condition}(S)$
  • Any where condition which compares primary keys gets converted to a natural join

Relational algebra equivalences are used to control the order of operations:

Automatic Conversations §

• Cross Product + Selection over equal ids = Natural Join:

$${\sigma }_{A.id=B.id}(A\times B)\equiv A{\bowtie }_{A.id=B.id}B$$

• Selection is distributed over joins (to reduce join cost) when possible:

$${\sigma }_{A.age>10}(A{\bowtie }_{A.id=B.id}B)\equiv ({\sigma }_{A.age>10}(A))\bowtie B$$

• Projection is distributed over joins when possible. Ensure that the subset of attributes to be projected is in the ‘outer’ loop:

$${\pi }_{name}(A{\bowtie }_{A.id=B.id}B)={\pi }_{name}[({\pi }_{name,id}(A)){\bowtie }_{A.id=B.id}({\pi }_{name,id}(B))$$

Cost Estimation §

For every generated query plan, the cost estimator must estimate:

• The size of the result for each operation in the Query Plan Tree (in pages)
• The cost of each operation in the tree. See query optimisation for various methods

It uses catalogues to do this:

For each block, the maximum size of the result is given by the product of the number of tuples in the FROM clause. The maximum is when a cartesian product (cross product) is performed.

$$\max (n_{tuples})=n_{tuples}(A)\cdot n_{tuples}(B)\cdot \dots$$

Like in query optimisation, we can use the Reducing Factor:

When selecting from a single table $A$, with $k$ predicates, we have the estimated size:

$$\text{Estimated Size}=n_{tuples}(A)\cdot \prod _{i=1}^k{\text{RF}}_i$$

When combining it with joins, of $m$ tables, we have:

$$\text{Estimated Size}=\left(\prod _{i=1}^m{n}_{tuples}(T_m)\right)\cdot \left(\prod _{i=1}^k{\text{RF}}_i\right)$$

Note that there are no reduction factors if there is no selections being performed.

Reducing Factor §

Predicate	$\text{RF}=$	Why?
$attr=val$	$\frac{1}{n_{keys}(attr)}$	$n_{keys}$ is the number of distinct values If we match against a certain key, then only elements which are equal to that key are returned.
$attr>val$	$\frac{att{r}_{max}-val}{att{r}_{max}-att{r}_{min}}$	The domain of values is $[att{r}_{min},att{r}_{max}]$. Since we only match the fraction of the entire domain from $val$ to $att{r}_{max}$, we do the final fraction
$attr<val$	$\frac{val-att{r}_{min}}{att{r}_{max}-att{r}_{min}}$	Opposite of the above
$A.attr=B.attr$ (Joins)	$\frac{1}{\max (n_{keys}(A_{attr}),n_{keys}(B_{attr}))}$
Else	A magic number, $\frac{1}{10}$	Chosen only when no other option is available, is not very accurate

Single-Relation Queries Cost (No Joins) §

When querying over a single relation/table, the query optimiser tries multiple access paths to obtain the final result:

• Linearly scan through the unsorted data, checking all predicates at each instance. $\text{Cost}=n_{pages}$
• Indexed searching over a primary key
  • Either search in b+ tree for tree-based indices. $\text{Cost}=h+1$
  • Or search through the hashmap for hash-based indices.
• Clustered Index matching one or more predicates. $\text{I/O Operations}=(i_{pages}+n_{pages})\cdot {\prod }_{i=1}^k{\text{RF}}_i$
• Unclustered index matching one or more predicates. $\text{I/O Operations}=(i_{pages}+n_{})\cdot {\prod }_{i=1}^k{\text{RF}}_i$

Multi-relation Queries Cost (Joins) §

For join operations:

1. Select the order of joining (since join is commutative). $A\times B\times C,C\times A\times B,etc.$ There are $N!$ orderings (where $N$ is the number of relations)
2. For each join, select a joining algorithm. Commonly used are Hash Sort, Sort-Merge Join, and Block-Based Nested Loop Join
3. For each relation, treat as a single-relation query and use access methods as above

In total, the number of possible query plans are:

$$\text{\# Query Plans = }n!\times 3^{n-1}\times (i+1{)}^n$$

Since there are $n!$ possible join orderings, the possible configurations for the query plan tree increase very quickly. As such, a property is enforced on the tree, namely that it becomes a left-deep join tree. This also removes the need for any auxiliary arrays %%🖋 Edit in Excalidraw, and the dark exported image%%

#todo Examples: