Query normalization

Why must predicates reach a standard form, and where do free inferred predicates come from?

Normalization means putting the query in a standard form. It exists for one reason: pattern matching does not work across syntactic variety. Every later mechanism (rule matching, common-subexpression detection, materialized-view matching, matching predicates to indexes) is a pattern match. Each syntactic variant you fail to standardize is a match you miss, silently.

Why predicates go to conjunctive normal form

The standard form for conditions is CNF (conjunctive normal form: a list of conditions joined by AND, where each item may itself contain ORs). Why this one? Because a conjunct can be moved independently, and a disjunct cannot. If a filter is A AND B AND C, you can push A down to the table scan and keep B for later. If it is A OR B, you cannot move A alone: the row might pass because of B. Pushdown, pruning and index matching all work on individually movable units, so the normal form is chosen to maximize the number of such units.

The price: converting to CNF can be exponentially large in the worst case. Engines cap the conversion and give up on deeply disjunctive conditions. That is exactly why Dev's long OR chain gets no partition pruning while the equivalent IN list does: the IN form is already a single, matchable unit, and the OR tree was too big to convert.

Equivalence classes and inferred predicates

The most valuable part of normalization is often forgotten: building equivalence classes and inferring predicates. The optimizer gathers equality conditions into classes. From

WHERE a.id = b.id AND b.id = c.id AND a.id = 42

it builds the class {a.id, b.id, c.id} (all three are equal) and the constant condition a.id = 42. From these it invents b.id = 42 and c.id = 42. One filter becomes three. Two of them can now prune partitions or use indexes on tables the user never mentioned in the WHERE clause.

This is where most real-world partition pruning on star queries that filter on a dimension actually comes from. When it fails, nothing warns you: the pruning just does not happen. Typical causes are a condition that is not an equality, or an equality hidden behind a cast or a function (a.id = CAST(b.id AS text) does not join the class).

In one sentence: normalization exists to make later pattern matches possible; the normal form is chosen by which operation must be decomposable; and the transitive closure of equality is where free predicates come from.