# Query Processing and Optimization — Query Trees, Join Algorithms, Cost Estimates and EXPLAIN

Source: https://skills101.in/learn/dbms-sql/dbms-query-optimization — Skills101 free tutorial (DBMS & SQL). Updated 2026-11-21.

SQL is **declarative**: you say **what** you want ("names of Pune students"), not **how** to get it. The database chooses the how — which index to use, which table to read first, which join method. For one query there can be hundreds of possible plans whose run times differ by thousands of times. The part of the DBMS that picks a good one is the **query optimizer**. Knowing how it thinks helps you write fast queries and answer a common DBMS exam question.

## 1. The steps of query processing

![Query processing steps: the SQL query is parsed and translated into a relational algebra expression, the optimizer uses statistics from the catalog to choose an execution plan, and the evaluation engine runs the plan against the data to produce the result](https://skills101.in/learn-img/dbms-sql/query-processing-steps.svg)

1. **Parsing and translation** — check the syntax, check that the tables and columns exist (using the **catalog**, the database's data about its own tables), and translate the query into **relational algebra**.
2. **Optimization** — generate equivalent plans and estimate the cost of each; pick the cheapest.
3. **Evaluation** — the execution engine runs the chosen plan and returns the rows.

An **evaluation plan** is a relational algebra tree in which every operator is labelled with **how** it runs: "use index `idx_city` for this selection", "hash join here".

## 2. Equivalent expressions and heuristic rules

Many relational algebra expressions give the same answer. For "name and marks of students from Pune":

- **Plan A:** join `students` with `results`, then keep the Pune rows: σ[city='Pune'](students ⋈ results)
- **Plan B:** keep the Pune students first, then join: σ[city='Pune'](students) ⋈ results

Both are correct. Suppose there are 5,000 students spread evenly over 50 cities, each with 2 rows in `results`:

![Two equivalent query trees: joining first creates an intermediate result of 10,000 rows before the city filter; filtering students first leaves 100 rows, and the join then produces only 200 rows](https://skills101.in/learn-img/dbms-sql/query-trees.svg)

Plan A builds 10,000 intermediate rows and throws 98% of them away. Plan B never creates them. That leads to the classic **heuristic rules** that optimizers apply first:

| Rule | Why |
|---|---|
| **Push selections (σ) down** — filter as early as possible | smaller inputs to every later operation |
| **Push projections (π) down** — drop unneeded columns early | fewer bytes per row to move and sort |
| **Combine × with σ into a join** | never build a full Cartesian product |
| **Do the most selective operations and joins first** | keeps intermediate results small |

## 3. Cost-based optimization

Heuristics alone don't decide between two indexes or two join orders. A **cost-based optimizer** estimates the cost of each candidate plan, mostly as the number of **disk block transfers** (and seeks), because reading from disk is far slower than CPU work. To estimate it, the catalog keeps **statistics**:

| Statistic | Symbol | Example |
|---|---|---|
| number of rows in r | n_r | 5,000 students |
| number of disk blocks of r | b_r | 100 blocks |
| number of distinct values of A in r | V(A, r) | 50 cities |

**Selectivity estimate** for an equality condition: σ[A=v](r) returns about **n_r / V(A, r)** rows, assuming values are evenly spread. Here 5,000 / 50 = **100** Pune students. If real data is skewed (half the students are from one city), the estimate is wrong, which is why databases also keep **histograms**, and why you run `ANALYZE` (PostgreSQL, SQLite) or `ANALYZE TABLE` (MySQL) to refresh statistics after big data changes.

## 4. Join algorithms and their costs

Joins are usually the most expensive operation, so the method matters. Take r = `results` (n_r = 10,000 rows in b_r = 400 blocks) and s = `students` (n_s = 5,000 rows in b_s = 100 blocks), with worst-case memory (one block of each table at a time):

```python
n_r, b_r = 10_000, 400     # results  (outer)
n_s, b_s = 5_000, 100      # students (inner)

costs = {
    'nested loop, results outer':   n_r * b_s + b_r,
    'nested loop, students outer':  n_s * b_r + b_s,
    'block nested loop':            b_r * b_s + b_r,
    'inner table fits in memory':   b_r + b_s,
    'sort-merge (already sorted)':  b_r + b_s,
    'hash join (approx. 3(br+bs))': 3 * (b_r + b_s),
}
for name, c in costs.items():
    print(f'{name:30} {c:>10,} block transfers')
```

```text
nested loop, results outer      1,000,400 block transfers
nested loop, students outer     2,000,100 block transfers
block nested loop                  40,400 block transfers
inner table fits in memory            500 block transfers
sort-merge (already sorted)           500 block transfers
hash join (approx. 3(br+bs))        1,500 block transfers
```

| Algorithm | Idea | Best when |
|---|---|---|
| **Nested loop** | for every row of r, scan all of s | tiny tables; works for any join condition (even `<`, `LIKE`) |
| **Block nested loop** | for every **block** of r, scan s once | no index, no sort order; far better than plain nested loop |
| **Index nested loop** | for every row of r, **look up** matching rows of s through an index on s | an index exists on the inner table's join column |
| **Sort-merge join** | sort both on the join column, then merge in one pass | inputs already sorted, or output needed sorted; equi-joins only |
| **Hash join** | build a hash table on the smaller input, probe it with the other | large equi-joins without useful indexes |

For the **same** join, the worst method needs about 4,000 times as many block transfers as the best one. This is why a missing index or stale statistics can turn a 50 ms query into a minute.

## 5. Seeing the plan: EXPLAIN

Every major database shows the chosen plan: `EXPLAIN` in MySQL and PostgreSQL (`EXPLAIN ANALYZE` also runs the query and shows real times), and `EXPLAIN QUERY PLAN` in SQLite. The program below asks SQLite for its plans:

```python
import sqlite3

db = sqlite3.connect(':memory:')
db.executescript('''
CREATE TABLE students (roll INTEGER PRIMARY KEY, name TEXT, city TEXT, cgpa REAL);
CREATE TABLE results (roll INTEGER, subject TEXT, marks INTEGER);
''')

def plan(sql):
    for row in db.execute('EXPLAIN QUERY PLAN ' + sql):
        print('  ', row[3])

q = "SELECT name FROM students WHERE city = 'Pune'"
print('No index:')
plan(q)
db.execute('CREATE INDEX idx_city ON students(city)')
print('With index:')
plan(q)
print('Function on the column:')
plan("SELECT name FROM students WHERE lower(city) = 'pune'")
print('Join:')
plan("SELECT s.name, r.marks FROM students s JOIN results r ON r.roll = s.roll")
```

```text
No index:
   SCAN students
With index:
   SEARCH students USING INDEX idx_city (city=?)
Function on the column:
   SCAN students
Join:
   SCAN r
   SEARCH s USING INTEGER PRIMARY KEY (rowid=?)
```

How to read it:

- `SCAN students` — a **full table scan**: every row is read.
- `SEARCH ... USING INDEX idx_city (city=?)` — the index is used to jump to matching rows.
- With `lower(city)`, the index is **not** used: the index stores `city`, not `lower(city)`. A condition that can use an index is called **sargable**. Keep indexed columns bare: write `city = 'Pune'`, `order_date >= '2026-01-01'`, not `YEAR(order_date) = 2026`.
- The join is an **index nested loop**: scan `results`, and for each row look up the student by primary key.

(The exact wording comes from SQLite 3.43 and differs between versions and between database products, but every plan answers the same questions: scan or index, which join method, in what order.)

## 6. Writing optimizer-friendly SQL

- Select only the columns you need instead of `SELECT *` — less data to read and send, and sometimes the index alone can answer (a **covering index**).
- Index the columns used in `WHERE`, `JOIN ... ON` and `ORDER BY` of frequent queries (see the indexing lesson).
- Keep conditions sargable; avoid wrapping indexed columns in functions or calculations.
- Check the plan with `EXPLAIN` before and after a change, instead of guessing.
- Keep statistics fresh with `ANALYZE` after large loads.

## Common mistakes

- Thinking the database runs SQL clauses literally in the written order. The optimizer may reorder joins and filters as long as the result is the same.
- Assuming an index is always used. A function on the column, a leading `%` in `LIKE`, or a condition matching most rows makes a scan cheaper or necessary.
- Mixing up the nested loop formulas: plain nested loop is n_r × b_s + b_r (rows × blocks); block nested loop is b_r × b_s + b_r.
- Forgetting that sort-merge and hash joins work only for **equality** joins.
- Trusting estimates on skewed data without updated statistics.

## Quick recap

- Query processing: parse and translate → optimize (using catalog statistics) → evaluate.
- Heuristics: push selections and projections down, avoid Cartesian products, most selective first.
- Cost is estimated in block transfers; σ[A=v] returns about n_r / V(A, r) rows.
- Joins: nested loop, block nested loop, index nested loop, sort-merge, hash — cost can differ by thousands of times.
- `EXPLAIN` shows the plan: SCAN = full scan, SEARCH USING INDEX = index lookup.


Practice quiz and free certificate: https://skills101.in/learn/dbms-sql/dbms-query-optimization