2.2 Query Equivalence, Logical Rewriting, and SQL Semantic Boundaries

The optimizer's task is not to "shorten the query" but to find a lower-cost physical plan among logically equivalent plans. Equivalence is defined by the requirement that both sides produce the same result under the target semantics for all allowed inputs.

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 vault_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 will prevent the join from being computed. 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 leverage 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, this is normal. Do not infer execution order from writing order; always refer to the execution plan.

Outer join cannot be arbitrarily reordered

SELECT a.name, q.quest_id
FROM adventurers AS a
LEFT JOIN quests AS q
  ON q.adventurer_id = a.adventurer_id
WHERE q.status = 'active';

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

SELECT a.name, q.quest_id
FROM adventurers AS a
LEFT JOIN quests AS q
  ON q.adventurer_id = a.adventurer_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 adventurer_id
FROM quests;

When a person has three quests, 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 vault_items AS i
WHERE i.item_id NOT IN (
    SELECT nullable_item_id
    FROM imports
);

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

Suppose a quest has multiple items:

SELECT SUM(q.reward_cents)
FROM quests AS q
JOIN quest_items AS qi
  ON qi.quest_id = q.quest_id;

Each reward is duplicated according to the number of items. To compute the total quest reward, aggregation should first occur at the quest level, or the join with quest_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 quests AS q
WHERE EXISTS (
    SELECT 1
    FROM quest_items AS qi
    WHERE qi.quest_id = q.quest_id
);

This query counts only quests that contain at least one item, with each quest contributing at most once.

Correlated Subquery and Decorrelation

SELECT a.adventurer_id, a.name
FROM adventurers AS a
WHERE EXISTS (
    SELECT 1
    FROM quests AS q
    WHERE q.adventurer_id = a.adventurer_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 describes how to construct results using operators, while relational calculus describes what conditions the resulting tuples must satisfy. For example, the set of adventurers involved in active quests:

{ a | Adventurers(a)
      ∧ ∃q (Quests(q)
            ∧ q.adventurer_id = a.adventurer_ id
            ∧ q.status = 'active') }

Calculus forms a foundational theoretical basis for declarative query languages. 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 weapon names in the active quest" 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 an adventurer with no quest to demonstrate how the status predicate behaves differently in a WHERE clause versus an ON clause.
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.