Skip to content
Tutorials Center
My learning

Topics

Lesson 62 of 79 ยท Query Processing and Optimization

Algebraic Equivalence and Heuristic Optimization

Learn relational algebra equivalence rules, selection and projection pushdown, subquery rewriting and how to write optimizer-friendly SQL, with live plan comparisons.

Before an optimizer starts costing plans, it first rewrites the query into an equivalent but cheaper form using rules that are always (or almost always) beneficial. The idea rests on relational algebra: the same query can be written as many different expression trees that return exactly the same rows, and some of those trees are enormously cheaper to evaluate than others. A rule such as "filter early" needs no statistics at all.

This lesson lists the main equivalence rules, shows the heuristics built from them (push selections and projections down, turn product plus selection into a join), explains how engines rewrite subqueries, and ends with habits that make your own SQL easy for an optimizer to improve. It continues from statistics and cost estimation, where the cost-based search happens after these rewrites, and from selection and projection and joins in algebra. For SQL-level tuning advice see also query optimization.

Rewrite before you cost

Push selections down Filter rows as early as possible.
Push projections down Drop unused columns early.
Product to join A product plus a join condition is a join.
Flatten subqueries Turn nested queries into joins.

These rewrites rarely make a plan worse.

1 / 2

Equivalence rules

Two algebra expressions are equivalent if they return the same relation on every database. Here are the rules an optimizer applies. In them, ฯƒ is selection, ฯ€ projection, โ‹ˆ join, and ฮธ a condition.

  1. Cascade of selections. ฯƒ_{ฮธ1 โˆง ฮธ2}(R) = ฯƒ_{ฮธ1}(ฯƒ_{ฮธ2}(R)). A conjunction can be applied in any order, one condition at a time.
  2. Selections commute. ฯƒ_{ฮธ1}(ฯƒ_{ฮธ2}(R)) = ฯƒ_{ฮธ2}(ฯƒ_{ฮธ1}(R)). The optimizer is free to evaluate the cheapest or most selective condition first.
  3. Cascade of projections. Only the last projection matters: ฯ€_A(ฯ€_B(R)) = ฯ€_A(R) when A โІ B.
  4. Selection with product or join. ฯƒ_ฮธ(R ร— S) = R โ‹ˆ_ฮธ S. A cartesian product followed by a condition that links both sides is a join. This is why the old comma syntax FROM a, b WHERE a.x = b.y is optimized exactly like JOIN ... ON.
  5. Joins commute and associate. R โ‹ˆ S = S โ‹ˆ R and (R โ‹ˆ S) โ‹ˆ T = R โ‹ˆ (S โ‹ˆ T). This is what makes join ordering a search problem.
  6. Pushing selection through a join. If a condition ฮธ1 mentions only attributes of R, then ฯƒ_{ฮธ1}(R โ‹ˆ S) = (ฯƒ_{ฮธ1}(R)) โ‹ˆ S. If ฮธ1 uses only R and ฮธ2 only S, both can be pushed to their own side.
  7. Pushing projection through a join. A projection can be pushed below a join if every column the join and later operators need is kept.
  8. Set operations. Union and intersection are commutative and associative; selection distributes over union, intersection and difference. Difference is not commutative.

Not every algebra identity applies to SQL as is. SQL works on bags (duplicates count) and has NULLs, so for example a projection can only be pushed past a duplicate-eliminating operator with care. The rules above are valid for bag semantics too, but rewrites involving DISTINCT, outer joins or three-valued logic need extra conditions. With a LEFT JOIN, for instance, a filter on the left (row-preserving) table can move below the join, but a filter on the right table cannot simply be moved, because it would turn the missing-match rows into something different.

The heuristic optimizer

A classical heuristic optimization algorithm applies these rules in a fixed order:

  1. Split conjunctive selections into individual ones (rule 1).
  2. Move each selection as far down the tree as possible (rules 2 and 6).
  3. Combine a selection above a product into a join (rule 4).
  4. Reorder leaves so that the most restrictive selections and smallest relations are joined first.
  5. Move projections down, keeping only columns needed above (rules 3 and 7).
  6. Identify subtrees that can be pipelined, and pick physical operators.
flowchart TB
  subgraph Before
    P1["ฯ€ name, total"] --> S1["ฯƒ country='NO' โˆง id=customer_id"] --> X1["C ร— O"]
  end
  subgraph After
    P2["ฯ€ name, total"] --> J2["โ‹ˆ id = customer_id"]
    J2 --> S2["ฯƒ country='NO'"] --> C2["C"]
    J2 --> O2["O"]
  end

Pushing the selection to the customers table and merging the product with the join condition.

Why does this matter? A selection pushed below a join shrinks one input before the expensive operator. The program below evaluates the same query in the literal order (product of everything, then filter) and in the pushed-down order, and counts the tuples at each step.

Python Selection pushdown: intermediate result sizes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both plans return the same 100 rows, but plan 1 builds a 100,000-tuple product first, while plan 2 never holds more than 100 tuples. That factor of a thousand is exactly what the heuristics buy before any statistics are consulted.

Do real engines still need your help?

Mostly they do the pushdown themselves. In SQLite, writing the filter after the join or inside a derived table produces the same plan, because the engine flattens subqueries in the FROM clause. The next example shows both forms and checks that they return the same count.

SQL Filter after the join or inside a subquery: same plan

Press Run (or Ctrl + Enter) to see the result here.

Both plans start with a SEARCH on the country index and then probe idx_orders_customer, and both counts are 100. The optimizer saw through your rewriting. That is the normal outcome, and the reason you should write the clearest query first.

Sargable predicates

Rewrite rules can only help if a condition can be used by an index. A predicate is sargable (a search-argument-able predicate) when the indexed column stands alone on one side of a comparison. Wrapping the column in a function or arithmetic hides it from the index, and no equivalence rule can fix that automatically, because the engine does not know that total + 1 = 500 means total = 499.

SQL Sargable and non-sargable predicates

Press Run (or Ctrl + Enter) to see the result here.

The first and fourth queries use SEARCH ... USING INDEX, the second and third SCAN orders, and the last shows MULTI-INDEX OR, where SQLite runs one index lookup per branch and merges the results. The rewrite you do by hand, turning the month function into a half-open range, is the single most valuable optimization habit. You can also index the expression itself (see advanced indexes).

Rewriting subqueries

Nested queries are hard for an optimizer because a correlated subquery looks like "run this inner query once per outer row". Engines try to unnest (decorrelate) them into joins or semi-joins:

  • WHERE id IN (SELECT customer_id FROM orders) and WHERE EXISTS (SELECT 1 FROM orders o WHERE o.customer_id = c.id) are both semi-joins: keep each customer that has at least one match, once.
  • A plain JOIN is not equivalent, because it repeats a customer for every matching order. To get semi-join behaviour from a join you must add DISTINCT or group, which adds a sort or hash step.
  • NOT IN is not the same as NOT EXISTS when NULLs are present (see nulls and three-valued logic), so an engine cannot freely turn one into the other.
SQL IN, EXISTS and JOIN are different questions

Press Run (or Ctrl + Enter) to see the result here.

Only 60 of the 100 customers have orders. The IN, EXISTS and JOIN DISTINCT forms all return 60, while the plain join returns 1,000 rows, one per order. The plans differ in strategy: the IN form builds a list of order customers (with a Bloom filter), the EXISTS form scans customers and probes the index for each one, and the DISTINCT join needs a temporary B-tree to remove duplicates. Which is fastest depends on the sizes, and that is what the cost-based optimizer decides; your job is to choose the form that says what you mean.

Writing optimizer-friendly SQL

  • Say what you mean with the clearest form (EXISTS for "has at least one", JOIN for "combine rows") and let the optimizer pick the strategy.
  • Keep indexed columns bare in comparisons; move arithmetic and functions to the constant side, and use ranges for dates.
  • Do not wrap columns in implicit conversions (comparing a text column to a number can disable its index).
  • List only the columns you need, so covering indexes and early projection can work.
  • Add LIMIT with an ORDER BY that matches an index when you only need the top rows.
  • Keep statistics fresh, and read the plan instead of guessing.
  • Do not rely on tricks that depend on an engine version; test plans on your own data.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why is it usually beneficial to push a selection below a join?

    Filtering early reduces intermediate result sizes, so later operators handle fewer rows. The result is unchanged.
  2. 2. Which condition can use an ordinary index on the column placed?

    The column stands alone and the condition is a range. The other forms apply a function or operation to the column, which hides it from the index.
  3. 3. A query joins customers to orders and must list each customer with at least one order exactly once. Which is correct?

    A plain join repeats a customer once per order. EXISTS and IN are semi-joins that keep each customer once, and DISTINCT removes the duplicates a join creates.
  4. 4. What does the rule sigma_theta(R x S) = R join_theta S allow an optimizer to do?

    A product followed by a linking condition is semantically a join, so hash, merge or index nested loop joins become available instead of building the full product.

Summary

  • Equivalence rules (selection cascade and commutativity, selection and projection pushdown, product plus selection equals join, join commutativity and associativity) let an optimizer rewrite a query without changing its result.
  • Heuristic optimization applies the always-good rules first, especially pushing selections down and merging products into joins, and cost-based search follows.
  • Sargable predicates keep the indexed column bare; functions and arithmetic on the column force scans, and a range often replaces a function.
  • IN, EXISTS and JOIN ask different questions (semi-join versus join with duplicates); pick the one that matches your meaning, and verify with the plan.

Next: Replication, Sharding and Distributed Transactions.