Common subexpression elimination

When does sharing a sub-plan pay, and why can a tree-shaped plan not share at all?

Two mechanisms share the name common subexpression elimination (CSE) and behave in opposite ways.

• Expression-level CSE: the same scalar expression computed twice within an operator. It is local, cheap and unconditionally beneficial.
• Plan-level CSE: the same sub-plan appearing twice, from a CTE referenced twice, a self-join, or UNION branches over one scan. This is not unconditionally beneficial. Sharing requires materializing the shared result (writing it out in full), which turns a pipelined edge (rows flowing one by one) into a blocking one (everything must finish first). It also forces both consumers to accept the same physical form. If one consumer wanted the data sorted and the other wanted it partitioned, sharing buys an extra sort or exchange.

The condition is derivable. Share if and only if:

where k is the number of consumers. The left side is the work saved by computing once instead of k times. The right side is the price of storing the result plus converting it for each consumer.

The industry has visibly changed its mind about this. PostgreSQL materialized every CTE unconditionally before version 12 (the well-known "optimization fence": people used it deliberately as a hint). From version 12 it inlines CTEs by default, and MATERIALIZED is available to force the old behavior. Both defaults were defensible. The flip is evidence that the inequality above really lies near zero for common workloads. This is Ananya's third problem: a CTE referenced twice changed speed across versions because the default flipped.

One structural point reaches further: plan-level CSE requires a DAG representation. A tree cannot express "this node has two parents", so an engine whose plan is a tree cannot do this optimization at all, however good its rules are. The memo is a DAG, and that is not an accident.

This is the same inequality as materialization versus pipelining (Execution decisions) and as the materialized-view break-even (below): pay once, read k times. Three forms of one decision, all instances of "costs are moved, not removed."

In one sentence: sharing trades recomputation against materialization plus loss of physical specialization; the break-even sits near k = 2 for cheap producers; and a tree-shaped plan cannot express sharing at all.