Skip to content
The Data EngineeringThe Data EngineeringBeta
About
Main content

Rule-based optimization

Why does rule order change plans?

There is one sharp test to tell a rule from a cost decision: can this transformation ever make the plan worse? If it can never make the plan worse, costing it is a waste, so you apply it always. If it can, it must be costed. This is the whole justification for a rule phase, and it implies that the rule set should be exactly the set of unconditionally good transformations.

In practice it is not. The truly unconditional set is small: , dead-column elimination (not carrying columns that nobody uses), removing conditions that are trivially false, and removing joins that constraints prove to be no-ops. Real rule engines contain many more transformations that are merely usually good.

Predicate pushdown (moving a filter below a join so it runs earlier) is the standard example. It is listed as a rule in every system, and it is not unconditionally beneficial:

  • Pushing an expensive user-defined function (UDF) below a join evaluates it on more rows than the join would have produced.
  • Pushing a predicate can destroy an ordering that would have avoided a sort.

Systems apply pushdown as a rule anyway, because costing every pushdown decision would multiply the search space for a win that is positive in the overwhelming majority of cases.

So there are three categories, not two:

  1. unconditional rules,
  2. heuristics applied as rules because costing them is not worth it,
  3. costed decisions.

Fixpoints and why rule order matters

A rule engine matches patterns on the plan tree and re-applies rules until nothing changes. That raises a problem nobody solves properly: iteration ends, and gives a unique result, only if the rule set is confluent (the order of rule application does not change the final result), and no one proves . Rules can undo each other. The industrial answer is to put rules into batches and cap the number of iterations. Spark Catalyst's Once and FixedPoint(n) batches are exactly this. The cap is an admission that the rule set is a program whose meaning has never been specified.

A consequence you can observe is the third thing Dev saw: rule order changes the plan. So a database upgrade can change a plan for reasons that have nothing to do with costs or . A new rule appears, or an old rule moves in the order, and the final form differs.

Constraint-based rewrites: join elimination

The rewrite most worth knowing here is the constraint-based rewrite. Its leverage in practice is out of proportion to its simplicity, and it needs no statistics at all.

Example. Suppose orders.store_id is a declared and enforced to stores.id, and stores.id is unique. Then this join:

SELECT o.order_id, o.amount
FROM orders o
JOIN stores s ON s.id = o.store_id;      -- no column of s is used anywhere

is provably a no-op: every order matches exactly one store (the FK guarantees at least one, the uniqueness guarantees at most one), and no store column is used. The deletes the join. BI tools generate SQL that joins six dimension tables and selects from two. removes four joins, which is a bigger win than any join-order decision over those same six tables. This is Dev's first problem.

The boundary condition is that the constraints must be enforced, not just declared. Many warehouse engines allow declared-but-unenforced constraints (RELY in Hive and Spark, NOVALIDATE in Oracle). Then you are trading a correctness guarantee for an optimization.

In one sentence: a rule is a transformation whose benefit does not depend on data; the real rule set is mixed with heuristics that are only usually right; and the order of the rules matters because nobody proved the set confluent.