2.2 Query Equivalence, Logical Rewriting, and SQL Semantic Boundaries

The optimizer searches logically equivalent plans for lower execution cost. A rewrite must first preserve the result for every allowed input. This lesson uses the SQLite fixture from Lessons 1.1 and 1.2 to test that requirement with outer joins, NULL, and duplicates. Fewer lines of SQL and fewer counted payments are both easy to achieve; the checks need to tell them apart.

Selection pushdown

Original expression:

σ Items.value_cents >= 50000 (Items ⋈ Items.type_id=Types.type_id Types)

Since the predicate references only Items, the selection can be pushed down:

(σ value_cents >= 50000 (Items))
⋈ Items.type_id=Types.type_id
Types

Pushing down a selection may reduce the number of rows before the join. However, if the predicate references attributes from both sides of the join, it cannot be fully pushed to either side. In the case of an outer join, additional checks are required to ensure that rows extended with NULL values are handled correctly.

SQL example:

SELECT i.name, t.code
FROM catalog_items AS i
JOIN item_types AS t
  ON t.item_type_id = i.item_type_id
WHERE i.value_cents >= 50000;

Databases typically perform such optimizations automatically, so application developers do not need to rewrite queries using subqueries to "force" early filtering. Whether pushdown is possible depends on the query optimizer and the properties of the expression.

Projection pushdown

After a join, only the i.name and t.code need to be projected, allowing irrelevant attributes to be discarded early. However, the join key and columns used in predicates must be preserved:

π name, code
  (
    (π name, type_id Items)
    ⋈ type_id
    (π type_id, code Types)
  )

Failing to retain type_id prevents the join from being computed. The expression uses classical set semantics; SQL column pruning normally preserves duplicates and must not introduce an extra DISTINCT. The physical engine might also retain different internal information for purposes such as index-only scans, tuple identity, or late materialization.

Inner Join Reordering

Under classical inner equijoin conditions, join operations are commutative and associative:

R ⋈ S = S ⋈ R
(R ⋈ S) ⋈ T = R ⋈ (S ⋈ T)

This allows the optimizer to choose to join smaller tables or those with high selectivity, or to use existing sorting or indexes. However, real SQL implementations also involve duplicate handling, type coercion, collation rules, and expression evaluation errors; the optimizer will only apply transformations that the target system considers valid.

The physical join order often differs from the SQL text order. Do not infer execution order from writing order; always refer to the execution plan.

Outer join cannot be arbitrarily reordered

SELECT a.name, q.task_id
FROM customers AS a
LEFT JOIN tasks AS q
  ON q.customer_id = a.customer_id
WHERE q.status = 'active';

A WHERE predicate removes NULL-extended rows that do not match q. If the goal is to retain customers without an active task, the query should be written as:

SELECT a.name, q.task_id
FROM customers AS a
LEFT JOIN tasks AS q
  ON q.customer_id = a.customer_id
 AND q.status = 'active';

These two queries are not equivalent. Operations such as predicate pushdown, join reordering, and null elimination in outer joins require additional proofs involving null rejection.

Duplicate Can Corrupt Certain Set Reasoning

Classical relations do not include duplicates, whereas SQL defaults to preserving them. For example:

SELECT customer_id
FROM tasks;

When a person has three tasks, the result appears three times; adding DISTINCT makes it behave like a set. Thus, UNION differs from UNION ALL, and COUNT(*) differs from COUNT(DISTINCT ...).

Duplicate elimination requires hashing or sorting and should not be indiscriminately applied with DISTINCT just for a "cleaner" appearance. If a join unintentionally inflates the result set, using DISTINCT may mask cardinality errors rather than fixing the underlying model.

NULL and Equivalence

In SQL's three-valued logic:

NOT (x = 1)

At x IS NULL, it is UNKNOWN, not equivalent to "x is an arbitrary value not equal to 1". NOT IN is especially dangerous with nullable subqueries:

SELECT i.item_id
FROM catalog_items AS i
WHERE i.item_id NOT IN (
    SELECT item_id FROM task_items
    UNION ALL
    SELECT NULL
);

If a subquery contains NULL, the comparison chain might make none of the candidate results true. When expressing an anti-join, prioritize explicitly using NOT EXISTS and, at the schema level, minimize nullable keys that shouldn't be nullable.

Aggregation Cannot Cross a Join Without Considering Cardinality

SELECT SUM(q.reward_cents)
FROM tasks AS q
JOIN task_items AS qi
  ON qi.task_id = q.task_id;

Each reward is duplicated according to the number of items. To compute the total task reward, aggregation should first occur at the task level, or the join with task_items should be avoided entirely. Query optimization begins with clearly defining the output grain, not by guessing which index to use first.

SELECT SUM(q.reward_cents)
FROM tasks AS q
WHERE EXISTS (
    SELECT 1
    FROM task_items AS qi
    WHERE qi.task_id = q.task_id
);

This query sums rewards only for tasks that contain at least one item, with each task contributing once. On the initial Lesson 1.2 fixture, the ordinary JOIN sums to 145000, while the EXISTS version gives 95000: the first query counts task 1's 50000 twice.

Correlated Subquery and Decorrelation

SELECT a.customer_id, a.name
FROM customers AS a
WHERE EXISTS (
    SELECT 1
    FROM tasks AS q
    WHERE q.customer_id = a.customer_id
      AND q.status = 'active'
);

Logically, the inner query depends on the current outer tuple. The optimizer may decorrelate it into a semijoin; alternatively, it might retain a parameterized lookup. It is not valid to assume that every row undergoes a full scan simply because a subquery is present.

Only the combination of EXPLAIN/EXPLAIN ANALYZE and the actual cardinality can determine what execution plan the target database has chosen.

Relational Calculus Perspective

Relational algebra constructs results with operators; relational calculus states the conditions a result tuple must satisfy. For customers with an active task:

{ a | Customers(a)
      ∧ ∃q (tasks(q)
            ∧ q.customer_id = a.customer_id
            ∧ q.status = 'active') }

Relational calculus expresses queries through these logical conditions. Safe or range-restricted expressions ensure that results are composed only from a finite set of database values, preventing the generation of infinite results over an unbounded domain.

From Logical to Physical

The same logical join can correspond to:

• nested-loop join;
• index nested-loop join;
• hash join;
• merge join.

The choice depends on cardinality estimates, row width, memory availability, data ordering, available indexes, and parallelism capabilities. Inaccurate estimates can lead to suboptimal join order, hash table spills, or excessive random lookups.

When optimizing, record:

logical requirement
actual row counts per operator
estimated row counts
scan/index access
join algorithm and order
sort/hash spill
buffer/cache and I/O
execution time across representative parameters

Looking only at total execution time cannot distinguish between a poor execution plan and cache cold/warm behavior; relying solely on estimated cost does not prove actual runtime performance.

Safety Checklist for SQL Equivalence

Before asserting that two SQL queries are equivalent, verify the following:

• Whether the result is a set or a bag;
• Whether NULL values are present and whether predicates reject them;
• The type of join: inner, left, right, or full;
• Whether key, foreign-key, or uniqueness constraints are actually enforced;
• Whether expressions are deterministic and could potentially throw exceptions;
• Collation rules, type coercion, timezone handling, and overflow behavior;
• Whether the aggregation grain has changed;
• Whether ORDER BY or LIMIT clauses influence the semantics;
• Whether concurrent data modifications and isolation snapshot levels are consistent.

Exercises

1. Write the SQL query for "all item names in the active task" as an algebra tree.
2. Push down the predicate that references only item_types.code, then list the join columns that must be preserved in the projection.
3. Construct a customer with no tasks and prove that placing the status predicate in WHERE produces a different result from placing it in ON.
4. Build a nullable subquery and observe the behavior of NOT IN and NOT EXISTS.
5. Compare JOIN + DISTINCT and EXISTS, and explain the semantic differences and plan variations.

Chapter Summary

Relational algebra provides a set of rules for query rewriting, but SQL features such as duplicates, NULL values, outer joins, and type system implementation introduce additional constraints and preconditions to those rules. In professional query optimization, the correct sequence is to first establish semantic correctness, then analyze cardinality, and finally select and validate the physical plan.