Flatten ASAP DAG Operators for Both Pre-ASAP and Post-ASAP IR

[Selvomega]

Problem

The post-ASAP DAG and the pre-ASAP plan are two separate operator sets. They meet at exactly one point: KeepPreAsap. It is an opaque leaf holding an entire pre-ASAP subtree, and no post-ASAP node can reference anything inside it. So that relational operators can sit above a summary, post-ASAP duplicates part of the pre-ASAP operator set:

pre-ASAP (QueryExpr)	post-ASAP duplicate
Project / Filter / Sort / Limit	ValueOperation::Project / Filter / Sort / Limit
Join	RelationalJoin
BinaryOp	BinaryOp
Aggregate	ValueOperation::Exact(Aggregate)
SetOp, Dedup, Concat, window functions, PromQL-only operators	none

This design causes three problems. Every example below was run on main (8acb472).

1. One operator, two spellings

WITH metric AS (SELECT avg(CASE WHEN l_quantity BETWEEN 1 AND 50 THEN 1.0 ELSE 0.0 END) AS in_range FROM lineitem)
SELECT in_range, in_range = 1.0 AS ok FROM metric

No summary is used at all, yet the three semantically identical Projects end up in two different types:

ValueOperation(Project in_range, ok)     ← post-ASAP
  ValueOperation(Project in_range)       ← post-ASAP
    KeepPreAsap(Aggregate(avg(expr)) ← Project(CASE WHEN …) ← Scan lineitem)
                                           ↑ pre-ASAP

Which spelling a node gets depends on where assemble_residual stopped peeling, not on semantics. Every downstream consumer handles each operator twice, and every new operator has to be duplicated again.

2. The opaque leaf blocks sharing

SELECT avg(l_extendedprice), approx_percentile_cont(l_discount, 0.99) FROM lineitem

On its own, the percentile gets a KLL sketch. Next to avg, the whole aggregate becomes KeepPreAsap(Aggregate). The immediate cause is that the rule only replaces single-measure aggregates.
But even if the rule could replace just the percentile and share one scan with avg, there is no way to express that today: Scan is inside the opaque leaf, and SummaryAgg cannot reference it.
The only option is to move Scan out of the leaf and rewrite Aggregate as its duplicate:

ValueOperation::Exact(Aggregate[avg])    SummaryAgg(Kll)
                   ╲                      ╱
                  KeepPreAsap(Scan lineitem)

In other words, sharing forces you onto the duplicates from problem 1.

3. An operator with no duplicate blocks every replacement below it

SELECT approx_distinct(l_partkey) FROM lineitem
UNION ALL
SELECT approx_distinct(l_suppkey) FROM lineitem

Each approx_distinct on its own gets a cardinality sketch (Theta on main). Joined by UNION ALL, the output is a single KeepPreAsap(SetOp) and neither side uses a sketch.
SetOp has no duplicate, so it can only live inside the opaque leaf, and the leaf cannot hold a summary. Window functions, Dedup, Concat and the PromQL-only operators behave the same way. There is no workaround short of adding another duplicate, which makes problem 1 worse.

Proposal

Keep a single set of relational operators, make summary operators an extension variant of it, and give every operator the same child type.

Concretely: one Operator type with two variants. Basic holds today's QueryExpr operators; Ext holds the summary operators. Every operator's children are Operator, so a summary node can sit anywhere a relational node can:

enum Operator {
    Basic(Relational),   // Scan / Filter / Project / Aggregate / Join / SetOp / Sort / Limit / BinaryOp / … — every operator QueryExpr has today
    Ext(SummaryOp),      // SummaryAgg / SummaryEstimate / SummaryMerge / SummarySubtract / SummaryDelete / SummaryJoin
}

Pre-ASAP and post-ASAP are the same type. The frontend produces only Basic nodes by convention; binding rules are the only place that creates Ext.

The three problems after the change:

Problem 1                       Problem 2                            Problem 3
Project(in_range, ok)           Aggregate[avg]   Ext(SummaryAgg)     SetOp(UnionAll)
  Project(in_range)                     ╲         ╱                    Ext(SummaryEstimate) ← Ext(SummaryAgg) ← Scan
    Aggregate(avg(expr))               Scan lineitem                   Ext(SummaryEstimate) ← Ext(SummaryAgg) ← Scan
      Project(CASE WHEN …)
        Scan lineitem

(Basic(...) wrappers omitted; only Ext nodes are marked.)

• KeepPreAsap and the opaque boundary are gone. When the executor needs "a subtree that can be handed to the native engine as one unit", it takes the largest subtree containing no Ext.
• ValueOperation keeps only the summary-specific variants (FinalizeExactAccumulator, MaintainPopulation / ReadPopulation).
• assemble_residual is no longer needed: replace only the selected nodes and leave everything else in place.

Open issues

1. Two type guarantees are lost. Project(Ext(SummaryAgg)) becomes expressible, and so does an Ext node in frontend output. Validation can catch both: a relational operator checks that all of its inputs are Plain columns, and pre-ASAP consumers reject Ext. The rule "a read-out value must not be fed back into SummaryAgg" is already enforced by validate_execution_data_states today, not by the type system.
2. Node wrapper: schema, guarantee and timing currently hang off SummaryNode. After unification they need a common node wrapper.
3. Column references: pre-ASAP refers to columns by position (ColumnId); summary nodes use SummaryField. The two schemas have to merge into one.
4. Extra fields on the duplicates: for example RelationalJoin.pruning (the completeness proof for candidate pruning). It either moves into the extension operator or becomes an optional annotation on the relational operator.
5. Large blast radius: the frontend, search, assembly, cost model, DAG export, ExecutableDag and ASAPQuery-backend all depend on the current two type sets.

For discussion

1. Is one type enough, or should pre / post be distinguished with a type parameter? Operator<Ext> with PreAsap = Operator<Never> would make the frontend unable to produce Ext at compile time, and pre-only code (SQL / PromQL lowering, CSE, validation, DAG export) could drop its Ext arm. The cost is that every function touching both sides becomes generic.
2. The interim option "let ValueOperation wrap a pre-ASAP operator directly" reduces the duplication in problem 1, but the opaque boundary stays, so it does not solve problems 2 and 3. Is it worth doing first?

[milindsrivastava1997]

This is useful, thanks!

Regarding open issue 1 -- we might be able to solve this by introducing types to describe the input and output of each Basic and Ext node. @zzylol may have thoughts on this.

Discussion point 1 -- didn't understand @Selvomega

[zzylol]

Thanks! I completely agree with this. This is an issue indeed and I didn't solve it yet. We should follow what is being suggested in the issue.

[zzylol]

@milindsrivastava1997 Let me unpack discussion point 1, since it's closely related to the typing idea you raised for open issue 1.

What it's reacting to. Today the frontend cannot emit a summary operator — not by convention, but because QueryExpr simply has no such variant. Merging pre- and post-ASAP into one Operator type gives that away: Ext(SummaryAgg) becomes constructible anywhere, including in frontend output, and we're left catching it with runtime validation. Discussion point 1 asks whether we can get that guarantee back at compile time instead.

The mechanism. Parameterize Operator over which extension operators are permitted:

enum Operator<E> {
    Basic(Relational<E>),   // children are Operator<E>
    Ext(E),
}

type PostAsap = Operator<SummaryOp>;
type PreAsap  = Operator<Never>;   // Never = `!`, an uninhabited type

The trick is Never: no value of it can ever be constructed, so in Operator<Never> the Ext arm is statically dead. Two consequences:

1. The frontend returns PreAsap, and it is a compile error for it to produce an Ext node. No validation pass needed for that half of open issue 1.
2. Pre-only code — SQL/PromQL lowering, CSE, validation, DAG export — can drop its Ext arm entirely (match e {} on an uninhabited value) rather than carrying an unreachable!() it has to keep justifying.

The cost, which is the part that makes it a real trade-off: every function that has to work on both sides becomes generic (fn f<E>(op: &Operator<E>) -> ...), and we pay for that in trait bounds, inference, error messages, and general readability. Binding rules, the cost model, and anything walking a plan that may or may not contain summaries all fall in that bucket.

So the question is really: single concrete type (simpler code, guarantee enforced at runtime) vs. type parameter (guarantee enforced by the compiler, but the shared code goes generic).

Worth noting these are two different routes, not competing versions of the same one. Your suggestion types the inputs and outputs of nodes, which is what we need for the other half of open issue 1 — ruling out Project(Ext(SummaryAgg)), i.e. a relational operator consuming a summary value. That can't be expressed by the E parameter, since PostAsap legitimately contains both kinds of node; it needs something on the schema/column side (the ColumnId vs SummaryField merge in open issue 3 is the same question from a different angle). Discussion point 1 only addresses where Ext may appear at all. We could adopt either, both, or neither.

[Selvomega]

This is useful, thanks!

Regarding open issue 1 -- we might be able to solve this by introducing types to describe the input and output of each Basic and Ext node. @zzylol may have thoughts on this.

Discussion point 1 -- didn't understand @Selvomega

Basically the discussion point 1 is about: After flattening the operators (both pre and post) into one type, we might lose the operator type guarantee in pre-ASAP-DAG (no post-ASAP-nodes involved). Before it is guaranteed by a separate QueryExpr type, now we may also need a mechanism to check that.

What is proposed in the PR and by Zeying is a compile-time type check method. That's doable, yet I personally don't see any reason why we cannot do run-time check using a validate function traversing the pre-ASAP-DAG.

[milindsrivastava1997]

Okay understood. I don't have a strong opinion on this. If no one else does either, we can just go for the easy solution i.e. runtime type checking.

Meta -- the AI text in the issue is nowhere as clear as what you wrote above. Let's please try to have more readable communication, thanks