Logical optimisation: equivalence rules, rewrites

Logical optimisation rewrites a query into another query that returns the same rows on every possible database but is cheaper to run. It works on the query tree, before the engine picks indexes, join algorithms or a join order. Its rewrites come from the equivalence rules of relational algebra: a selection can be split, reordered and moved below a join to the table it filters; columns nobody needs can be dropped early; inner joins can be swapped and regrouped. The goal is small intermediate results, because every row an operator produces has to be built, held and handed on. Engines apply these rules without being asked, PostgreSQL in its rewriter and planner and SQLite while it compiles a statement. The familiar rules stop holding at outer joins and NULLs, where a wrong rewrite does not fail: it quietly returns different rows.

Why rewriting comes before choosing a plan

A query tree built straight from the SQL text follows the clauses in order: the joins of FROM, then WHERE, then SELECT. Run as written, it builds every joined row and discards most of them at the end. A rewrite changes the shape of the tree, never its result, and the planner then prices the cheaper shape. PostgreSQL’s manual gives that order: the rewrite system replaces each view with its tables, then the planner builds the possible paths and keeps the cheapest.

Two expressions are equivalent when they return the same result on every database that fits the schema, not only on today’s rows. SQL tables are bags, in which a row may appear more than once, so an equivalence rule must also keep the number of copies of each row.

The equivalence rules

Each rule says that two expressions return the same rows, and when that holds:

1. Split a selection, always: $\sigma_{p \wedge q}(E) \equiv \sigma_p(\sigma_q(E))$
2. Reorder selections, always: $\sigma_p(\sigma_q(E)) \equiv \sigma_q(\sigma_p(E))$
3. Push a selection below a join, when p uses only columns of E1: $\sigma_p(E_1 \bowtie E_2) \equiv \sigma_p(E_1) \bowtie E_2$
4. Turn a product into a join, when p compares columns of E1 and E2: $\sigma_p(E_1 \times E_2) \equiv E_1 \bowtie_p E_2$
5. Swap the inputs of a join, for inner joins, where only the column order changes: $E_1 \bowtie E_2 \equiv E_2 \bowtie E_1$
6. Regroup joins, for inner joins, with each condition kept beside the inputs it uses: $(E_1 \bowtie E_2) \bowtie E_3 \equiv E_1 \bowtie (E_2 \bowtie E_3)$
7. Push a projection below a join, when L1 and L2 keep the columns of L and the columns c compares: $\pi_L(E_1 \bowtie_c E_2) \equiv \pi_L(\pi_{L_1}(E_1) \bowtie_c \pi_{L_2}(E_2))$
8. Push a selection into a union, and in the same way into an intersection or a difference: $\sigma_p(E_1 \cup E_2) \equiv \sigma_p(E_1) \cup \sigma_p(E_2)$

Rules 1 and 3 do most of the work: split the WHERE clause into its conditions and move each one down to the lowest node that has all of its columns. Rule 7 does the same for columns, and rules 5 and 6 let the planner choose any order for inner joins, the search of the lesson on join ordering.

Pushing selections down, with numbers

Take a college database of 3,000 students, 40 courses and 15,000 enrolments, and ask for the enrolments of CSE students in 4-credit courses. The program evaluates both trees with a small evaluator of its own and counts the rows each operator produces:

# One question, two query trees: filter after the joins, or filter first.
# A tiny evaluator runs both on the same seeded college data and counts the
# rows each operator hands to the next one.
import random

rng = random.Random(7)
DEPTS = ["CSE", "ECE", "EEE", "MECH", "CIVIL", "CHEM"]
students = [{"sid": i, "name": f"S{i:04d}", "dept": rng.choice(DEPTS)} for i in range(1, 3001)]
courses = [{"cid": c, "credits": rng.choice([2, 3, 3, 4])} for c in range(1, 41)]
enrolments = [{"sid": s["sid"], "cid": c} for s in students for c in rng.sample(range(1, 41), 5)]

log = []


def scan(rows, name):
    log.append((f"scan {name}", len(rows)))
    return rows


def select(rows, label, keep):
    out = [r for r in rows if keep(r)]
    log.append((f"select {label}", len(out)))
    return out


def join(left, right, key, label):
    index = {}
    for r in right:
        index.setdefault(r[key], []).append(r)
    out = [{**l, **r} for l in left for r in index.get(l[key], [])]
    log.append((f"join {label}", len(out)))
    return out


def names(rows):
    return sorted(r["name"] for r in rows)


def run(title, plan):
    log.clear()
    result = plan()
    print(title)
    for step, n in log:
        print(f"  {step:<34}{n:>7,} rows")
    built = sum(n for step, n in log if step.startswith("join"))
    print(f"  {'rows built by the two joins':<34}{built:>7,}\n")
    return result


late = run("Filter after the joins (the query as written)", lambda: names(
    select(join(join(scan(students, "students"), scan(enrolments, "enrolments"), "sid", "on sid"),
                scan(courses, "courses"), "cid", "on cid"),
           "dept = CSE and credits = 4", lambda r: r["dept"] == "CSE" and r["credits"] == 4)))

early = run("Filters pushed down to their tables", lambda: names(
    join(join(select(scan(students, "students"), "dept = CSE", lambda r: r["dept"] == "CSE"),
              scan(enrolments, "enrolments"), "sid", "on sid"),
         select(scan(courses, "courses"), "credits = 4", lambda r: r["credits"] == 4), "cid", "on cid")))

print("same answer:", late == early, f"({len(early):,} enrolments)")

Filter after the joins (the query as written)
  scan students                       3,000 rows
  scan enrolments                    15,000 rows
  join on sid                        15,000 rows
  scan courses                           40 rows
  join on cid                        15,000 rows
  select dept = CSE and credits = 4     581 rows
  rows built by the two joins        30,000

Filters pushed down to their tables
  scan students                       3,000 rows
  select dept = CSE                     535 rows
  scan enrolments                    15,000 rows
  join on sid                         2,675 rows
  scan courses                           40 rows
  select credits = 4                      9 rows
  join on cid                           581 rows
  rows built by the two joins         3,256

same answer: True (581 enrolments)

Both trees return the same 581 enrolments. The tree as written builds 15,000 joined rows twice and keeps 581. The rewritten tree filters 3,000 students down to 535 and 40 courses down to 9 first, so its joins build 3,256 rows instead of 30,000, about a ninth. In a real engine the gain is usually larger: smaller join inputs fit in memory, and a condition that reaches its table can use that table’s index.

Rewrites engines make without being asked

Optimisers apply more rewrites than the eight rules, each with a name that appears in plans and manuals:

• View merging, or subquery flattening, replaces a view or a FROM subquery with its tables and conditions.
• Predicate pushdown copies an outer condition into a subquery that cannot be merged.
• Subquery unnesting, or decorrelation, turns a correlated subquery into a join.
• Outer-join reduction turns a LEFT JOIN into an inner join when WHERE removes every row padded with NULLs.
• Join elimination drops a LEFT JOIN that supplies no column and at most one matching row.
• Constant folding computes constant expressions while planning: PostgreSQL’s manual shows x = 2 + 2 becoming x = 4.

SQLite shows two of them in its plans, for a view that joins students to their enrolments:

-- A view over a join, queried with a filter: SQLite merges the view into the query.
CREATE TABLE students (sid INTEGER PRIMARY KEY, name TEXT NOT NULL, dept TEXT NOT NULL);
CREATE INDEX students_dept ON students (dept);
CREATE TABLE enrolments (sid INTEGER NOT NULL, cid INTEGER NOT NULL, PRIMARY KEY (sid, cid));
INSERT INTO students VALUES (1, 'Asha', 'CSE'), (2, 'Ravi', 'ECE'), (3, 'Meera', 'CSE'), (4, 'Kiran', 'MECH');
INSERT INTO enrolments VALUES (1, 10), (1, 11), (2, 10), (3, 11), (4, 12);

CREATE VIEW enrolled AS
  SELECT s.sid, s.name, s.dept, e.cid
  FROM students AS s JOIN enrolments AS e ON e.sid = s.sid;

SELECT name, cid FROM enrolled WHERE dept = 'CSE' ORDER BY name, cid;
EXPLAIN QUERY PLAN SELECT name, cid FROM enrolled WHERE dept = 'CSE';

-- DISTINCT stops the merge, but the filter is still pushed inside the view.
CREATE VIEW enrolled_once AS
  SELECT DISTINCT s.sid, s.name, s.dept
  FROM students AS s JOIN enrolments AS e ON e.sid = s.sid;

EXPLAIN QUERY PLAN SELECT name FROM enrolled_once WHERE dept = 'CSE';

┌───────┬─────┐
│ name  │ cid │
├───────┼─────┤
│ Asha  │ 10  │
│ Asha  │ 11  │
│ Meera │ 11  │
└───────┴─────┘
┌────┬────────┬─────────┬─────────────────────────────────────────────────────────────────────┐
│ id │ parent │ notused │                               detail                                │
├────┼────────┼─────────┼─────────────────────────────────────────────────────────────────────┤
│ 4  │ 0      │ 62      │ SEARCH s USING INDEX students_dept (dept=?)                         │
│ 9  │ 0      │ 56      │ SEARCH e USING COVERING INDEX sqlite_autoindex_enrolments_1 (sid=?) │
└────┴────────┴─────────┴─────────────────────────────────────────────────────────────────────┘
┌────┬────────┬─────────┬─────────────────────────────────────────────────────────────────────┐
│ id │ parent │ notused │                               detail                                │
├────┼────────┼─────────┼─────────────────────────────────────────────────────────────────────┤
│ 2  │ 0      │ 0       │ CO-ROUTINE enrolled_once                                            │
│ 7  │ 2      │ 62      │ SEARCH s USING INDEX students_dept (dept=?)                         │
│ 12 │ 2      │ 56      │ SEARCH e USING COVERING INDEX sqlite_autoindex_enrolments_1 (sid=?) │
│ 27 │ 0      │ 52      │ SCAN enrolled_once                                                  │
└────┴────────┴─────────┴─────────────────────────────────────────────────────────────────────┘

In the first plan the view has disappeared: SQLite finds the CSE students through the index on dept, as if the query had named both tables. The second view uses DISTINCT, which SQLite’s documentation lists among the conditions that prevent flattening, so it runs as a CO-ROUTINE, with the condition on dept pushed inside it to the index.

Check yourself

Exercise

"""Selection pushdown on small query trees.

A tree is a tuple:
  ("table", name)                     a table of SCHEMA
  ("select", column, value, child)    the rows of child whose column equals value
  ("join", left, right)               the natural join of left and right
"""

SCHEMA = {
    "students": ("sid", "name", "dept"),
    "enrolments": ("sid", "cid"),
    "courses": ("cid", "title", "credits"),
}


def columns(tree):
    """The set of columns a tree produces."""
    if tree[0] == "table":
        return set(SCHEMA[tree[1]])
    if tree[0] == "select":
        return columns(tree[3])
    return columns(tree[1]) | columns(tree[2])


def push_down(tree):
    """An equivalent tree with every selection moved down as far as it can go."""
    # Replace this line with your code.
    return tree

from pushdown import push_down

S, E, C = ("table", "students"), ("table", "enrolments"), ("table", "courses")


def select(column, value, child):
    return ("select", column, value, child)


def join(left, right):
    return ("join", left, right)


def evaluate(tree, db):
    """Runs a tree on db (table name -> list of dicts): the result as a sorted list of rows."""
    def run(t):
        if t[0] == "table":
            return [dict(r) for r in db[t[1]]]
        if t[0] == "select":
            return [r for r in run(t[3]) if r[t[1]] == t[2]]
        left, right = run(t[1]), run(t[2])
        common = set(left[0]) & set(right[0]) if left and right else set()
        return [{**l, **r} for l in left for r in right if all(l[c] == r[c] for c in common)]
    return sorted(tuple(sorted(r.items())) for r in run(tree))


DB = {
    "students": [{"sid": 1, "name": "Asha", "dept": "CSE"}, {"sid": 2, "name": "Ravi", "dept": "ECE"},
                 {"sid": 3, "name": "Meera", "dept": "CSE"}],
    "enrolments": [{"sid": 1, "cid": 10}, {"sid": 1, "cid": 11}, {"sid": 2, "cid": 10}, {"sid": 3, "cid": 11}],
    "courses": [{"cid": 10, "title": "Databases", "credits": 4}, {"cid": 11, "title": "Writing", "credits": 2}],
}


def test_a_selection_moves_into_the_left_table():
    """dept is a column of students, so the selection goes below the join, onto students"""
    assert push_down(select("dept", "CSE", join(S, E))) == join(select("dept", "CSE", S), E)


def test_a_selection_moves_into_the_right_table():
    """credits is a column of courses only"""
    assert push_down(select("credits", 4, join(E, C))) == join(E, select("credits", 4, C))


def test_two_selections_each_find_their_table():
    """a cascade of selections is split between the two sides"""
    tree = select("credits", 4, select("dept", "CSE", join(join(S, E), C)))
    assert push_down(tree) == join(join(select("dept", "CSE", S), E), select("credits", 4, C))


def test_a_join_column_goes_to_the_left_side():
    """sid is on both sides of students JOIN enrolments: the left side gets the selection"""
    assert push_down(select("sid", 1, join(S, E))) == join(select("sid", 1, S), E)


def test_tables_and_joins_without_selections_stay_as_they_are():
    tree = join(join(S, E), C)
    assert push_down(tree) == tree
    assert push_down(S) == S


def test_the_rewritten_tree_returns_the_same_rows():
    """pushing down changes the shape, never the result"""
    tree = select("title", "Databases", select("name", "Asha", join(join(S, E), C)))
    assert evaluate(push_down(tree), DB) == evaluate(tree, DB)
    assert len(evaluate(tree, DB)) == 1

Proving a rewrite, and refuting one on 1,000 random databases Pro: opens with a Pro, Premium or Ultimate pass

Outer joins and subqueries: the conditions that make a rewrite legal Pro: opens with a Pro, Premium or Ultimate pass

Interview questions

Key takeaways

• Two queries are equivalent only if they agree on every database, copies of rows included.
• Push each condition of WHERE to the lowest node that has its columns: the college query’s joins built 3,256 rows instead of 30,000.
• Engines merge views, push conditions down, unnest subqueries and fold constants themselves: write the clearest query, then read its plan.