Skip to content

feat(plan_v2): Improve planner extraction#4182

Open
Ignition wants to merge 1 commit into
masterfrom
2026_03_18_planner_v2
Open

feat(plan_v2): Improve planner extraction#4182
Ignition wants to merge 1 commit into
masterfrom
2026_03_18_planner_v2

Conversation

@Ignition
Copy link
Copy Markdown
Contributor

@Ignition Ignition commented May 26, 2026

Bring planner v2 extraction to the point where it carries full expression trees (arithmetic, comparison, boolean, function, unwind, subquery) and selects plans on cost. The extractor now searches the equivalent plans held in the e-graph and picks the cheapest, scoring candidates with a cost model and a pluggable cardinality estimator. Candidates can be better on different axes - estimated cost, output cardinality, and demand (whether later operators actually use a value) - so it keeps a Pareto frontier of non-dominated candidates instead of committing early. Propagating demand lets it drop work nothing reads: unreferenced alternatives are pruned, and an operator like Bind takes its cheaper variant that skips evaluating the bound value wherever nothing downstream consumes it.

The per-symbol behaviour is organised into trait families spanning the make, cost, resolve, and build axes, with a single dispatcher across them. Adding a new operator is driven from one X-macro symbol list that flows into the enum, predicates, and round-trip; a missing trait specialisation is a compile error rather than a silent gap. plan_v2 is reorganised along these axes into egraph, cost, frontend, and resolve layers.

Extraction state is threaded through the interpreter via a planner context, replacing the previous ad-hoc plumbing. Test and benchmark support is consolidated under shared test_support libraries, with new algebra, cardinality, and extractor suites covering the Pareto cases and full operator round-trips, plus new extraction and match benchmarks.

@Ignition Ignition added this to the mg-v3.11.0 milestone May 26, 2026
@Ignition Ignition requested a review from imilinovic May 26, 2026 19:50
@Ignition Ignition self-assigned this May 26, 2026
@Ignition Ignition added feature feature Docs unnecessary Docs unnecessary CI -build=community -test=core Run community build and core tests on push CI -build=coverage -test=core Run coverage build and core tests on push CI -build=debug -test=core Run debug build and core tests on push CI -build=debug -test=integration Run debug build and integration tests on push CI -build=release -test=core Run release build and core tests on push CI -build=release -test=e2e Run release build and e2e tests on push Capability - planner CI -build=coverage -test=clang_tidy labels May 26, 2026
@Ignition Ignition changed the title feat(plan_v2): Imporved planner extraction feat(plan_v2): Improved planner extraction May 26, 2026
@Ignition Ignition force-pushed the 2026_03_18_planner_v2 branch 2 times, most recently from c3986e7 to 873b75b Compare May 27, 2026 00:39
@Ignition Ignition requested a review from colinbarry May 27, 2026 00:53
Comment thread src/planner/bench/bench_common.hpp Outdated
/// `append_children` and `children_of` are the only intended way to write into
/// or read from `child_indices`; they own the half-open-window invariant.
struct ResolvedBuildContext {
std::vector<ResolvedEntry> build_order;
Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Is there useful methods we can add for interacting with build_order rather than manipulating it directly?

Comment thread src/planner/include/planner/extract/extractor.hpp Outdated
Comment thread src/planner/include/planner/extract/extractor.hpp Outdated
}
}
return result;
auto entry = make_entry(key, self);
Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

better name? this is where recursion happens, what contractually makes this DFS?

/// trait is detectable. Swapping operands inverts the ordering so a < b ⇒
/// "a dominates b" ⇒ `greater`.
struct LowerIsBetter {
static constexpr auto compare(auto const &a, auto const &b) { return b <=> a; }
Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

b <=> a how does that correlate with LowerIsBetter?

Comment thread src/query/plan_v2/cost/builtin_estimator.cpp Outdated
Comment thread src/query/plan_v2/cost/cost_model.hpp Outdated
Comment thread src/query/plan_v2/cost/cost_model.hpp Outdated
Comment thread src/query/plan_v2/cost/cost_model.cpp
Comment thread src/query/plan_v2/cost/cost_model.cpp Outdated
Comment on lines +126 to +127
.required = {},
.introduces = a.introduces,
Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Do we need a comment to explain these semantics, does the parent Output node clean up the .introduces + .required?

Comment thread src/query/plan_v2/cost/cost_model.cpp Outdated
/// the same expr), so the frontier still emits the valid combinations. This
/// also subsumes the post-inline-rewrite self-referential case where
/// `Identifier(sym)` is unioned into expr's e-class.
auto BindFlatMap(CostFrontier const &input, CostFrontier const &expr, planner::core::EClassId sym_eclass,
Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

BindFlatMap, OutputCombine, UnwindFlatMap, SubqueryFlatMap, FunctionCombine. Do they deserve there own named functions? Is there a common generalisation that they can use, or do we inline into their symbol_cost_traits?

Comment thread src/query/plan_v2/cost/cost_model.cpp
Comment thread src/query/plan_v2/cost/cost_model.cpp Outdated
Comment thread src/query/plan_v2/cost/cost_model.cpp Outdated
Comment thread src/query/plan_v2/cost/cost_model.cpp Outdated
// through unchanged. expr is evaluated once at bind-time.
emit({.cost = BindAliveCost(input_alt.cost, sym_cost, expr_alt.cost, input_alt.cardinality),
.cardinality = input_alt.cardinality,
.required = {},
Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Does this need reconsidering? will operators on inner branches need to communicate their requirements?

Comment on lines +242 to +251
auto result = args.empty() ? LeafFrontier(0.0, enode_id) : Restamp(*args[0], 0.0, enode_id);
for (auto const *arg : args.empty() ? args : args.subspan(1)) {
result = BinaryCombine(result, *arg, 0.0, enode_id);
}
result.mutate_pruning_invariant_preserving([&](Alternative &alt) {
alt.cost += 1.0;
alt.cardinality = cardinality;
alt.enode_id = enode_id;
});
return result;
Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This is not general, it special cases to handle the arity of the functions we have been testing (ie. range(_,_)). This requires code to be more general.

Comment thread src/query/plan_v2/cost/cost_model.cpp
Comment thread src/query/plan_v2/cost/cost_model.cpp Outdated
@Ignition Ignition linked an issue May 28, 2026 that may be closed by this pull request
@Ignition Ignition force-pushed the 2026_03_18_planner_v2 branch 2 times, most recently from 158307b to 75ca5d6 Compare May 28, 2026 23:56
@Ignition Ignition changed the title feat(plan_v2): Improved planner extraction feat(plan_v2): Improve planner extraction May 28, 2026
Comment thread src/query/interpreter.hpp
#include "memory/db_arena_fwd.hpp"
#include "query/context.hpp"
#include "query/db_accessor.hpp"
#include "query/plan_v2/frontend/egraph_converter.hpp"
Copy link
Copy Markdown
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

TODO: QueryPlannerContext coming from "frontend/egraph_converter.hpp" looks strange, change its header

Bring planner v2 extraction to the point where it carries full
expression trees (arithmetic, comparison, boolean, function, unwind,
subquery) and selects plans on cost. The extractor now searches the
equivalent plans held in the e-graph and picks the cheapest, scoring
candidates with a cost model and a pluggable cardinality estimator.
Candidates can be better on different axes - estimated cost, output
cardinality, and demand (whether later operators actually use a value)
- so it keeps a Pareto frontier of non-dominated candidates instead of
committing early. Propagating demand lets it drop work nothing reads:
unreferenced alternatives are pruned, and an operator like Bind takes
its cheaper variant that skips evaluating the bound value wherever
nothing downstream consumes it.

The per-symbol behaviour is organised into trait families spanning the
make, cost, resolve, and build axes, with a single dispatcher across
them. Adding a new operator is driven from one X-macro symbol list that
flows into the enum, predicates, and round-trip; a missing trait
specialisation is a compile error rather than a silent gap. plan_v2 is
reorganised along these axes into egraph, cost, frontend, and resolve
layers.

Extraction state is threaded through the interpreter via a planner
context, replacing the previous ad-hoc plumbing. Test and benchmark
support is consolidated under shared test_support libraries, with new
algebra, cardinality, and extractor suites covering the Pareto cases
and full operator round-trips, plus new extraction and match
benchmarks.
@Ignition Ignition force-pushed the 2026_03_18_planner_v2 branch from 75ca5d6 to 6ad2b53 Compare May 29, 2026 17:11
@sonarqubecloud
Copy link
Copy Markdown

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

Labels

Capability - planner CI -build=community -test=core Run community build and core tests on push CI -build=coverage -test=clang_tidy CI -build=coverage -test=core Run coverage build and core tests on push CI -build=debug -test=core Run debug build and core tests on push CI -build=debug -test=integration Run debug build and integration tests on push CI -build=release -test=core Run release build and core tests on push CI -build=release -test=e2e Run release build and e2e tests on push Docs unnecessary Docs unnecessary feature feature

Projects

None yet

Development

Successfully merging this pull request may close these issues.

Improve cost estimation and extraction

1 participant