SQL Query Optimization

Problem: How to actually process this:

Basic Strategies §

• SQL Query rewriting
  • Make everything into joins!
• De-correlation: Correlated subqueries are de-correlated using “Magic” de-correlation
• Iterated (=pipelined) algorithm processes
  • Process one tuple, up the chain, one at a time
  • Will start producing results faster, but may not be fast in total
• Bottom-up Evaluation
  • Process the bottommost query, then up one level, etc.
  • Use temporary files to store intermediate results

Heuristics-based Optimization §

• Idea: estimate size of intermediate results to calculate total operation count
  • Cardinality estimation
• Given knowledge: $|{\pi }_{A}R|,|R|$
• Principles:
  • Preservation of Value

Selection

$$\begin{array}{rl}|{\sigma }_{A=val}|& \approx |R|\cdot \frac{1}{|{\pi }_{A}R|}=\frac{\text{Size of }R}{\text{Distict }A\text{ values in }R}\\ |{\sigma }_{A=val}|& \approx |R|\cdot (1-\frac{1}{|{\pi }_{A}R|})\end{array}$$

• divide by the “selectivity factor”

Conjunction, Disjunction (AND, OR operations)

• Best when $A,B$ are independent columns

$$\begin{array}{rlr}|{\sigma }_{A=u\wedge B=v}|& \approx |R|\cdot \frac{1}{|{\pi }_{A}R|\cdot |{\pi }_{B}R|}& \text{Conjunction}\\ |{\sigma }_{A=u\vee B=v}|& \approx |R|\cdot \left(\frac{1}{|{\pi }_{A}R|}+\frac{1}{|{\pi }_{A}R|}-\frac{1}{|{\pi }_{A}R|\cdot |{\pi }_{B}R|}\right)& \text{Disjunction}\end{array}$$

Range

• Without $max,min$ values: just say $\frac{1}{3}$
• With $max=$hi(R.A) and $min=$lo(R.B)
  • & sometimes, highest and lowest is “invalid” → use second highest & lowest

$$|{\sigma }_{A>v}|\approx |R|\cdot \frac{max-v}{max-min}$$

Joins Estimation §

Natural Join

• Assumption: containment—every tuple in smaller table joins with bigger table
• ⇒ selectivity factor is the bigger one one

$$|R\bowtie S|\approx |R\times S|\cdot \frac{1}{max(|{\pi }_{A}R|,|{\pi }_{A}S|)}$$

Multi-way Join

• Assumption: preservation of value sets—non-join attribute doesn’t lose values
• ⇒ reduce by selectivity factor for every join

$$|R(A,B)\bowtie S(B,C)\bowtie T(C,D)|\approx |R\times S\times T|\cdot \underset{\text{selectivity of first join}}{\underbrace{\frac{1}{|{\pi }_{B}R|,|{\pi }_{B}S|}}}\cdot \underset{\text{selectivity of second join}}{\underbrace{\frac{1}{|{\pi }_{C}S|,|{\pi }_{C}T|}}}$$

Projection over Join

• Due to assumption of preservation of value sets…
• …when $R(A,B),S(B,C)$, $A$ does not appear in $S$. Therefore we estimate:

$$|{\pi }_A(R\bowtie S)|\approx |{\pi }_{A}S|$$

Nowadays people use histograms and ML for better estimation

Join Plans §

Q. given $n$ relations to join, how to join?

1. Brute Force: $\frac{(2n-2)!}{(n-1)!}$
2. Left-Deep Plan: $n!$
3. Greedy: $n^2$
4. Dynamic Programming:
   • Need to consider: interesting orders (=sorted? deduped? etc.) need to be considered too!
   •