Query processing and optimization: join algorithms, equivalence rules, estimation

Last week we calculated the cost of selecting from a single table. This week the query combines several tables. The same SQL query can have dozens of different execution plans, and the cost difference between them can be thousands of times. The optimizer’s job is to find a cheap one among them. The exam has three types of questions: calculate a join cost, compare two plans, and rewrite a query tree with equivalence rules.

Golden rules:

1. Cost = block transfers + seeks. Do not forget the number of seeks; half of the question comes from there.
2. In nested-loop variants, put the smaller relation outside.
3. Push selection ($\sigma$) as far down as possible. Reducing the number of rows entering the join is the biggest gain.
4. An equivalence rule does not change the result. It only changes the cost.

Steps of query processing

1. Parsing and translation: the SQL syntax is checked, table and column names are validated, and the query is translated into a relational algebra expression.
2. Optimization: equivalent algebra expressions and the algorithms for each operation are considered. The cost of each plan is estimated (using statistics), and the cheapest is chosen. The result is a query evaluation plan: a tree that states which algorithm will be used at each node.
3. Evaluation: the plan is run.

The cost measure: for $b$ block transfers and $S$ seeks

$\text{cost} = b \cdot t_T + S \cdot t_S$

On this page too, $t_T = 0.1$ ms and $t_S = 4$ ms.

External sort-merge

If the table does not fit in memory, sorting happens in two phases. $M$ = the number of buffer blocks in memory.

1. Run creation: read $M$ blocks, sort them in memory, write them as a run. $\lceil b_r / M \rceil$ runs result.
2. Merging: in each pass $M - 1$ runs are merged (1 block is for the output). The number of passes is $\lceil \log_{M-1}(b_r / M) \rceil$.

$\text{transfers} = b_r \left( 2 \left\lceil \log_{M-1} \frac{b_r}{M} \right\rceil + 1 \right)$

Example: $b_r = 400$, $M = 11$. The number of runs is $\lceil 400/11 \rceil = 37$. In each pass 10 runs are merged: $37 \to 4 \to 1$, 2 passes. Transfers $400 \cdot (2 \cdot 2 + 1) = 2000$. Writing the final result to disk is not counted, because it is usually passed directly to the next operation.

Join algorithms

The example in the body: $r$ = takes ($n_r = 10000$, $b_r = 400$), $s$ = student ($n_s = 5000$, $b_s = 100$). The join condition is takes.stu_id = student.stu_id.

Nested-loop join

for each tuple t_r in r:
    for each tuple t_s in s:
        if (t_r, t_s) satisfies the condition, write to the output

In the worst case (one buffer per relation):

$n_r \cdot b_s + b_r \text{ transfers}, \qquad n_r + b_r \text{ seeks}$

With takes outer: $10000 \cdot 100 + 400 = 1\,000\,400$ transfers, $10400$ seeks. The time is $100040 + 41600 = 141640$ ms, about 2.4 minutes. With student outer: $5000 \cdot 400 + 100 = 2\,000\,100$ transfers. Here the factor is the number of tuples of the outer, so having fewer tuples outside is better.

Best case: if the smaller relation fits entirely in memory, both are read once: $b_r + b_s = 500$ transfers, 2 seeks.

Block nested-loop join

Match not tuple by tuple but block by block: for each block of the outer, the inner relation is scanned once.

$b_r \cdot b_s + b_r \text{ transfers}, \qquad 2 b_r \text{ seeks}$

With takes outer: $400 \cdot 100 + 400 = 40400$ transfers, 800 seeks. With student outer: $100 \cdot 400 + 100 = 40100$ transfers, 200 seeks. This time too the smaller relation wins on the outside.

If there are $M$ buffers, $M - 2$ blocks are given to the outer relation (one for the inner, one for the output):

$\left\lceil \frac{b_r}{M-2} \right\rceil b_s + b_r \text{ transfers}, \qquad 2 \left\lceil \frac{b_r}{M-2} \right\rceil \text{ seeks}$

With $M = 12$ and student outer: $\lceil 100/10 \rceil = 10$ chunks, $10 \cdot 400 + 100 = 4100$ transfers, 20 seeks.

Indexed nested-loop join

If there is an index on the join attribute in the inner relation, instead of scanning the inner relation, each outer tuple does a search in the index. $c$ = the cost of one search + fetching the match.

$b_r (t_T + t_S) + n_r \cdot c$

With takes outer and a $h_i = 3$ B+ tree on student.stu_id: since it is equality on a key, $c = h_i + 1 = 4$ block accesses. The number of accesses is $400 + 10000 \cdot 4 = 40400$. Since each is a seek + transfer, in terms of time this is more expensive than block nested-loop. Indexed nested-loop shines when the outer relation is small (for example, when a tight $\sigma$ has been applied first).

Merge join

If the two relations are sorted on the join attribute, they are scanned in parallel and read once:

$b_r + b_s \text{ transfers}$

In the example, $400 + 100 = 500$. If they are not sorted, the sorting cost is added first. With $M = 11$, sorting takes is 2000, and sorting student ($\lceil 100/11 \rceil = 10$ runs, 1 pass) is $100 \cdot 3 = 300$ transfers. Total $2000 + 300 + 500 = 2800$. It is used only for equality and natural joins (equi-joins).

Hash join

1. Partitioning: the two relations are divided into $n_h$ partitions with the same hash function. Tuples that can match fall into partitions with the same number.
2. For each $i$, $s_i$ is brought into memory and a hash table is built in memory (build input), then $r_i$ is read and probed against this table (probe input).

The smaller relation becomes the build input; each $s_i$ must fit in memory. If no recursive partitioning is needed:

$3 (b_r + b_s) \text{ transfers}$

Partitioning is read + write $2(b_r + b_s)$, and the build/probe phase is one read $(b_r + b_s)$. In the example $3 \cdot 500 = 1500$.

Summary comparison (takes ⋈ student)

PITFALL · $n$ or $b$ in the formulas? In simple nested-loop the factor is the tuple count of the outer $n_r$, in block nested-loop the block count of the outer $b_r$. In indexed nested-loop it is $n_r$ again. This is where the most points are lost in the exam.

Equivalence rules

Two algebra expressions are equivalent if they give the same result on every database instance. The main rules the optimizer uses:

Join commutativity changes the column order, but since columns in a relation are identified by name, the result is the same relation.

Heuristic optimization

Trying all plans is expensive. Heuristic rules give a good plan in most cases:

1. Break conjunctive selections apart with the cascade.
2. Push every selection as far down as possible in the tree.
3. Do the most restrictive selection (the one that leaves the fewest rows) and join first.
4. Turn the $\sigma$ + $\times$ pair into $\bowtie$. Avoid the Cartesian product.
5. Do projection early and drop unneeded columns. Do not forget to keep the columns needed for the join.

Example: transforming a query tree

On the sample university database: “the names of CS-department students who took a 3-credit course.” Since the course table also has dept_name, we rename it c_dept; otherwise the natural join would also try to equate the student’s department with the course’s department.

The naive translation:

$\pi_{name}\big(\sigma_{dept\_name='CS' \wedge credits=3}(\text{student} \bowtie (\text{takes} \bowtie \text{course}))\big)$

With cascade + pushing selection down + early projection:

$\pi_{name}\Big(\pi_{stu\_id,\, name}(\sigma_{dept\_name='CS'}(\text{student})) \bowtie \pi_{stu\_id}\big(\text{takes} \bowtie \sigma_{credits=3}(\text{course})\big)\Big)$

intermediate result sizes (sample DB)   naive plan   optimized plan
student ⋈ takes ⋈ course                14           -
σ dept_name='CS'(student)               -            3
σ credits=3(course)                     -            4
takes ⋈ σ(course)                       -            5
result                                  Ada          Ada

The two plans give the same result (only Ada). The naive plan first produces a 14-row join and then filters; the optimized plan enters the join with 3 and 5 rows. At real sizes this difference is millions of rows.

PITFALL · natural join and same-named columns. If you write student ⋈ takes ⋈ course without renaming, dept_name is equated too, and on the sample database 9 rows come out instead of 14: the courses taken outside the student’s own department are lost. This is not an optimization, it is a wrong query.

Statistics and size estimation

To estimate the cost of a plan, the optimizer uses the statistics in the catalog: $n_r$, $b_r$, $f_r$, and $V(A, r)$, the number of distinct values of $A$ in $r$.

Example: $n = 5000$ students, $V(dept\_name) = 20$. The estimate for dept_name = 'CS' is $250$. If tot_cred ranges from 0 to 240, the estimate for tot_cred <= 60 is $5000 \cdot 60/240 = 1250$. Both together: $5000 \cdot 0.05 \cdot 0.25 = 62.5$, that is, about 63 rows.

An estimate is an assumption. In our sample database student has 7 rows and COUNT(DISTINCT dept_name) = 3 (NULL is not counted). The estimate is $7/3 \approx 2.33$, while in reality there are 3 students in CS. If the distribution is not even, the estimate drifts; real systems keep histograms for this reason.

Common mistakes