Planning roadmap: move ASAPQuery planning into ASAPPlanner, MILP plan selection over shared DAGs, benchmark-based accuracy #671

Activity

1. zzylol commented on Oct 13, 2026

   

   zzylol

   on Oct 13, 2026

   ContributorAuthor

   More actions

   Survey: how existing query optimizers search for plans

   This is a survey of how existing systems search the plan space, written for part 2 (plan selection). Where a detail depends on a system's version or configuration, I say so.

   1. Bottom-up dynamic programming (System R family)

   • Selinger et al., System R (SIGMOD 1979). Bottom-up DP over subsets of relations for join ordering. The best plan for each subset is kept, plus "interesting orders" (sort orders worth keeping for later operators). The usual restriction is to left-deep plans.
   • DPsize / DPsub / DPccp. DPccp (Moerkotte & Neumann, VLDB 2006) enumerates only connected subgraphs and their complements, so it never considers cross products. DPhyp (SIGMOD 2008) extends this to hypergraphs, which covers outer joins and complex predicates.
   • In use:
     • PostgreSQL: exhaustive DP for joins of up to geqo_threshold relations (12 by default), and a genetic algorithm (GEQO) above that.
     • DuckDB: DPhyp for join ordering, with a greedy fallback for large queries.
     • Spark Catalyst: rule-based, plus an optional cost-based join reorder that is a DP up to spark.sql.cbo.joinReorder.dp.threshold (12 by default).
   • Why DP works there: optimal substructure. The best plan for a subset doesn't depend on how that subset is used later, apart from a few properties such as sort order.

   2. Top-down memoization with rules (Volcano / Cascades)

   • Graefe, Volcano (ICDE 1993) and Cascades (1995). A memo holds groups of logically equivalent expressions. Transformation rules add alternatives to a group, and implementation rules add physical operators. The search is top-down with memoized costs and branch-and-bound pruning, guided by required physical properties.
   • In use: SQL Server, Greenplum/Orca, CockroachDB (memo plus generated rules), and Apache Calcite's VolcanoPlanner. Calcite also has HepPlanner, which only rewrites by rules.
   • The same DP idea underneath: a group's best plan for a given set of required properties is computed once and reused.

   3. Rule-based rewriting to a fixed point (DataFusion)

   • DataFusion's logical optimizer is an ordered list of OptimizerRules, applied over several passes until the plan stops changing (with a configurable pass limit). Examples: SimplifyExpressions, PushDownFilter, OptimizeProjections, EliminateCrossJoin, decorrelation rules.
   • Its physical optimizer is likewise a list of PhysicalOptimizerRules. JoinSelection uses statistics to pick join sides and algorithms; others enforce distribution and sorting.
   • No general cost-based enumeration. DataFusion has no memo and no cost-based join-order search by default; plans keep the join order they were written in, except for side swaps. Optimizer::with_rules(...) lets a caller run a chosen subset of rules (Run selected DataFusion optimizer rules in SQL lowering; a rule-list API for ASAPPlanner rewrites #670).
   • Equality saturation (e-graphs, e.g. egg) has been tried experimentally on top of DataFusion's expressions. It keeps every equivalent form and extracts the cheapest one, which makes it a close cousin of a Cascades memo.

   4. MILP and other formulations

   • Trummer & Koch, "Solving the Join Ordering Problem via Mixed Integer Linear Programming" (SIGMOD 2017). Join ordering written as a MILP, solved by an off-the-shelf solver. The cost is approximated piecewise-linearly, and the solver gives anytime results with optimality bounds.
   • Randomized and greedy methods (genetic, iterative improvement, simulated annealing) are used where exhaustive DP is too expensive.

   5. Problems closest to ours: sharing and materialization

   Our Stage 3 picks plans for a whole workload DAG with shared sub-DAGs (Pass 2) and materialization choices (Stage 2). The closest prior work:

   • Multi-query optimization (MQO). Sellis (TODS 1988) gives an exact search over plans with shared subexpressions. Roy, Seshadri, Sudarshan & Bhobe (SIGMOD 2000) extend a Volcano AND-OR DAG with sharable nodes and choose what to materialize and share greedily, because exact MQO is NP-hard.

   • Materialized view selection.

     • Harinarayan, Rajaraman & Ullman (SIGMOD 1996): greedy selection over the data-cube lattice, with an approximation guarantee.
     • Gupta (ICDT 1997): view selection on AND-OR view graphs.
     • Later ILP formulations of view selection under a storage budget.

     This corresponds to our Stage 2 decision (MatAtIngestion / MatAtQuery / NotMaterialized) together with Stage 3: memory, disk and latency trade-offs per candidate, and cost models beyond cloud billing #660's memory and disk budgets.

   6. What this means for ASAPPlanner

   • DP needs optimal substructure, and sharing breaks it. Once a sub-DAG is shared, its best choice depends on every consumer: a sketch sized for the strictest consumer, and a cost paid once instead of once per consumer. A tree DP is then no longer exact. This is the MQO situation.
   • What we have now. CandidateLogicalASAPDAGs::global_selection in replacement.rs is a DP over the reference DAG. It memoizes each site's effective consumer count and re-decides share versus recompute against that count. Its doc says it is not an exhaustive global optimum, and there is an exhaustive fallback for cases where the DP's assumptions fail. (docs: propose workload-wide planning, summary sharing, and materialization #509 also notes that its MEMO-like layout resembles Cascades.)
   • Options for Stage 3:
     1. Exact DP plus enumeration over shared nodes. Fix the choices for the shared nodes, then run the DP independently on the tree-shaped rest. This is exact; its cost is exponential only in the number of shared nodes, which is usually small.
     2. A Cascades-style memo. One group per computation. Pass 1 candidates are the group's members, Pass 2 shared candidates are group alternatives, and Stage 2 materialization is a required property. Sharing is still handled as in option 1 or by a greedy pass.
     3. MILP, as in part 2 of this issue. An exact formulation is possible with indicator variables for each shared node and constraints that link consumers to it, including the strictest-consumer sizing rule. Budgets (Stage 3: memory, disk and latency trade-offs per candidate, and cost models beyond cloud billing #660) become linear constraints. Size has to be checked on real workloads, and costs may need piecewise-linear approximation.
     4. Greedy MQO (Roy et al.) as the baseline, and as the fallback when 1 or 3 are too expensive.
   • Suggested next step: prototype option 1 and option 3 on the Example 1–4 workloads, measure the optimality gap and the runtime, and compare both against the current global_selection.

   Related: #670 (running selected DataFusion optimizer rules during SQL lowering), #660 (deployment cost models and budgets), #509.