CSE: decide rule-based vs. cost-based framework for whether to actually share a detected common subexpression

[zzylol]

Summary

#223 (structural CSE detection, stages 1+2 landed in PR #235) explicitly separates detection ("are these two subtrees structurally identical and legally shareable") from stage 4 — wiring CSE credit into CostModel ("is it actually worth sharing them"), and deliberately defers stage 4 with "only then." This issue is about how that stage-4 decision should be made once it's picked back up — it's a real design choice with two well-established industry precedents pulling in different directions, not an obvious default.

The two models

Framework	Core mechanism	How it decides on CSE
Volcano/Cascades (SQL Server, Snowflake, Calcite)	Cost-based (CBO): explores a large space of logically equivalent trees via dynamic programming + a structural memo	Weighs the memory/IO cost of materializing the shared subexpression against the CPU cost of recomputing it at each use site — sharing only wins if the trade-off is favorable
System R (classic IBM, early databases)	Heuristic/bottom-up: fixed rules + basic selectivity statistics, no broad plan-space search	Applies rigid heuristic rules unconditionally (e.g. "always materialize if referenced more than once") — no per-case cost comparison

Why this matters here specifically

crates/asap-aware-mapping/src/cost_model.rs's own module doc already names "workload-level CSE credit" as planned, and share_common_subtrees (PR #235) currently shares every structurally-identical, legally-shareable (unique_keys-gated) subtree unconditionally once detected — there's no cost gate yet, which is fine for now (detection and "always share when legal" is a reasonable stage-1/2 default) but becomes a real question once cost enters the picture:

• Materializing a shared summary (a sketch, an accumulator) has a real memory/update cost, same as this repo's core stated purpose (mapping a workload to a plan, not a single query) already cares about for sketch-vs-exact selection (boundary/bind).
• Two subtrees might be structurally shareable but so cheap to recompute independently, or so rarely both actually queried, that materializing and maintaining one shared summary costs more than just doing the work twice — a Volcano/Cascades-style trade-off.
• Conversely, a System R-style unconditional rule ("share whenever legal") is far simpler to implement and reason about, and may be good enough if recomputation cost dominates memory cost for this workload's typical shapes.
• There are cases when we need to scan the data, and the scan part can be shared across multiple queries, wherein the summary is not necessarily an optimized operation; exact computation or passthrough may work as well for cost target. Sometimes, we need to do CSE for summaries and find the minimal summary instances to compute.

Scope of this issue

Decide which model (or a hybrid — e.g. unconditional sharing below some cheap-recompute threshold, cost-compared above it) CostModel's eventual CSE-credit wiring should follow, before implementing it. Not asking for an implementation yet — this is upstream of #223's still-deferred stage 4.

Related

• New feature: add common sub expr elimination #212 — parent CSE issue
• CSE detection should run in pre-ASAP IR; post-ASAP can run a secondary pass #222 — placement decision (pre-ASAP primary detection, post-ASAP secondary)
• Design: pre-ASAP structural CSE via bottom-up hash-consing over Rc<QueryExpr> #223 — detection algorithm; stage 4 ("wire CSE credit into CostModel") is what this issue's decision feeds into
• PR feat(pre-asap): structural CSE via bottom-up hash-consing (stages 1+2) #235 — stages 1+2 landed (unconditional sharing once legal, no cost gate — expected at this stage)
• crates/asap-aware-mapping/src/cost_model.rs — where the eventual decision logic would live

[zzylol]

@milindsrivastava1997 @Selvomega