Skip to content

Wire workload-level CSE into a cost model #6

Description

@zzylol

Background

PR #5 lands the workload-level CSE machinery in crates/core/src/intent_algebra/:

  • cse::dedupe_subtrees(roots) -> CseWorkloadPlan { bindings, roots } — hoists sub-expressions that are structurally identical across ≥2 query roots into shared LetBindings, leaving each root with a QueryExpr::Ref where the duplicate lived.
  • schema::cse_reuse_is_legal(schema, consumer_count) — the legality gate; refuses to share a producer whose output Schema has no unique_keys set.
  • Schema::unique_keys — the load-bearing field the gate reads.

Today this is scaffolding with no consumer: nothing calls dedupe_subtrees outside its own unit tests, and there is no cost model in the repo, so CSE never actually influences a plan. Single-query lowering doesn't exercise it at all.

Goal

Make workload-level shared-sub-expression reuse actually affect planning: when ≥2 queries are planned together and share a producer, its build cost should be credited once, and the planner should prefer the bundled plan when it's cheaper than N independent plans.

Proposed work

  1. Add a cost model (crates/core/src/optimizer/cost/ — new). Port the design of ASAPQuery-backend control_plane/src/optimizer/cost/mod.rs::workload_cost:
    • Per-node cost primitives (node_cost_scan/window/aggregate, …) over L3 QueryExpr.
    • workload_cost(plan) -> WorkloadCost { total_dollars, per_root_breakdown, reused_savings } via a post-order walk: each LetBinding costed once into a name → cost map; Ref(name) charges 0.0 (already paid). reused_savings = naive_sum − total_dollars.
    • The "Ref charges zero" rule is the credit mechanism that turns a shared producer into "paid once".
  2. Adapter from cse::CseWorkloadPlan → the cost model's plan view (both are { bindings, roots }; the backend keeps them as mirror structs so this is trivial).
  3. Driver: a multi-query entry point (pipeline / future analyzer) that runs dedupe_subtrees on the workload's L3 roots, costs the bundled plan, and compares against the naive per-query sum to decide whether to ship it.
  4. Generalise CSE beyond the basic case if needed (the current pass handles only structurally-identical Aggregate-child sub-trees across roots; alpha-equivalence / nested CSE / schema-merge are deferred).

Notes

  • The backend's workload_cost is itself not yet wired to its CSE pass (the two halves are mirror structs that never meet, both dead-code with unit tests only — "the analyzer wiring lands in a follow-up phase"). So this is net-new integration work in both repos; the backend supplies the design template, not a finished consumer.
  • Depends on PR feat(promql+sql): unified positional L3 intent algebra (PromQL & SQL lowering) #5 (which introduces the CSE machinery + unique_keys).
  • Cost-model node coverage in the backend is currently only Scan/Window/Aggregate/LetBinding/Ref; Filter/Project/Join/SetOp/Sort/Limit/BinaryOp walk children at zero node-cost (a TODO to carry over).

Activity

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions