rudb_opt/lib.rs
1//! The rewrite passes, cardinality estimation, join ordering, predicate transfer and layout adaptation.
2//!
3//! Rank 11 in the layer rule. See `xtask/layers.toml` and `spec/18-package-layout.md`.
4//!
5//! Twenty five passes so far. `spec/09-optimizer.md` section 9.1 describes a sequence and [`PASSES`]
6//! is the start of it. Column pruning came first, because it is the pass whose absence is measured
7//! in gigabytes: a scan that reads 105 columns to answer a question about three is the whole of the
8//! difference on ClickBench, and the Parquet reader has been able to read a subset since M1 with
9//! nothing able to tell it which subset.
10
11#![forbid(unsafe_code)]
12
13pub mod bounds;
14pub mod cluster;
15pub mod columns;
16pub mod cte;
17pub mod delim;
18pub mod dense;
19pub mod dependent;
20pub mod distinct;
21mod domain;
22pub mod eliminate;
23pub mod empty;
24pub mod estimate;
25pub mod explain;
26pub mod extremes;
27pub mod filter;
28pub mod fold;
29pub mod fromkey;
30pub mod keys;
31pub mod late;
32pub mod limit;
33pub mod link;
34pub mod nonulls;
35pub mod nulls;
36pub mod order;
37pub mod pass;
38pub mod presize;
39pub mod reorder;
40pub mod semi;
41pub mod sides;
42pub mod tables;
43pub mod topn;
44mod transitive;
45pub mod unnest;
46mod walk;
47
48use rudb_common::rules::Rule;
49use rudb_common::{Error, Result};
50use rudb_plan::{JoinKind, Node, NodeRef, Plan};
51
52use crate::pass::{Context, Pass};
53
54/// The crate this rank belongs to, so that the layer check has something to read.
55pub const RANK: u8 = 11;
56
57/// The passes, in the order they run.
58///
59/// A fixed sequence rather than a loop to a fixed point, which is what `spec/09-optimizer.md`
60/// section 9.1 asks for and what DuckDB does. A fixed point is easy to write and hard to bound: a
61/// pair of passes that undo each other runs forever, and the version that stops after a few rounds
62/// has a plan that depends on how many rounds it was given.
63///
64/// Folding is before pruning because folding removes column references and pruning drops the columns
65/// nothing refers to, so a `CASE WHEN false THEN t.a ELSE 1 END` costs a column read when the two run
66/// the other way around. Nothing in the other direction is given up: pruning drops columns and
67/// renumbers bindings, and neither of those makes anything foldable.
68///
69/// Filter pushdown goes between them. After folding, because a predicate that folds to a constant is
70/// a predicate with nothing to push and the pass that moves it should not be the one that finds out.
71/// Before pruning, because moving a filter below a projection rewrites it in terms of columns the
72/// projection reads, and pruning has to see the plan after the move or it drops a column that
73/// something now refers to.
74///
75/// Join ordering is immediately after filter pushdown, because pushdown is what turns the binder's
76/// cross products into joins with conditions on them, and which cross products are left over after
77/// it has placed every condition it can is the whole of what this pass reads. Running it first would
78/// be reading a plan where every join is still a cross product and none of the conditions have been
79/// placed, which says nothing about anything. Before everything else after that, because every later
80/// pass reads a join as it ends up. The build side is the clearest of those and is chosen last, but
81/// empty result pullup, column pruning and late materialisation all walk the join tree and all of
82/// them should walk the tree that is going to run.
83///
84/// The deliminator is between filter pushdown and join ordering, and both halves of that matter.
85/// After pushdown, because the shape it reads is a filter over the marker of one single join and
86/// before pushdown that test is one conjunct of the query's whole `WHERE`, sitting above however
87/// many other joins the `FROM` list turned into. Before join ordering, because what it leaves
88/// behind is a semi join where there was a join back to a domain, and the pass that decides which
89/// order to build a region in should be reading the joins that are going to run.
90///
91/// Pushing the keys of a correlated subquery into the aggregate that answers it goes between the
92/// deliminator and join ordering, for the two reasons the deliminator is there. After pushdown,
93/// because the relation it copies is the one the filters have already been moved into and copying
94/// it before they move would copy a whole table. Before join ordering, because the semi join it
95/// writes is a join that is going to run and a region the pass reads should be the region the
96/// executor gets.
97///
98/// Empty result pullup is after filter pushdown, because pushdown is what moves an unsatisfiable
99/// predicate down to the scan it should stop and what drops the conjuncts that were always true, so
100/// the pass that looks for a predicate nothing can satisfy should look after that has happened. It
101/// is before pruning for the same reason folding is: the subtrees it removes are subtrees pruning
102/// would otherwise walk and work out column lists for.
103///
104/// Limit pushdown is second to last, which is to say it is immediately before top N. A limit that
105/// has moved below the projections above it is a limit that may now be sitting directly on a sort,
106/// and that pair is what top N fuses, so running the two the other way around would leave the fusion
107/// with a plan it cannot see the shape of.
108///
109/// The distinct aggregate rewrite is second, ahead of everything that moves an operator around,
110/// because it is the one pass that changes what an aggregate is rather than where it sits. Every
111/// other pass here is written against a single aggregate node, and running this one ahead of them
112/// means none of them has to know that `COUNT(DISTINCT x)` has a second spelling. In particular the
113/// limit that fuses into an aggregate has to fuse into the outer one, and after this pass the outer
114/// one is the only one it can see.
115///
116/// What it is not ahead of is folding, and that order is the other way round for a reason the AST
117/// fuzz target found. The rewrite fires only when every `DISTINCT` call in a node has the same
118/// argument, and whether two arguments are the same is a question folding answers: `max(DISTINCT
119/// 1 + 1)` and `min(DISTINCT 2)` are two arguments before it and one after it. With the rewrite
120/// first the pass sees the unfolded pair, refuses, and a second run of the sequence over its own
121/// output fires, which is the idempotence assertion below failing. Folding has no opinion about
122/// either spelling of an aggregate, so nothing is given up by putting it in front.
123///
124/// Collapsing an aggregate onto its group key is fourth, immediately after the pass that takes
125/// dependent expressions out of a group key. Both of them end up with a projection over an
126/// aggregate, and the order between them decides how much the second one sees: `GROUP BY c, f(c)` is
127/// a two key aggregate until dependent group keys have run and a one key aggregate afterwards, and
128/// only the second of those is a shape the collapse applies to. It is also before filter pushdown,
129/// because the expressions it leaves in a projection are the ones a `HAVING` should get to run
130/// before, and pushdown is what moves the `HAVING` under them.
131///
132/// Group key pushdown is after the two passes that turn a mark into a semi join, and that is the
133/// difference between the pass firing on TPC-H q20 and not. It copies the relation that restricts
134/// the outer query so the aggregate underneath builds only the groups that will be read, and the
135/// restriction in q20 is `ps_partkey IN (SELECT p_partkey FROM part WHERE p_name LIKE 'forest%')`.
136/// Ahead of the mark rewrites that is a filter over a mark join, which is a shape with a column
137/// that exists only to be tested and a copy of which would have to reproduce it; afterwards it is a
138/// semi join, which is a shape that copies. Nothing is given up by waiting, because the copy it
139/// takes is then of a subtree join order has already ordered, and the semi join it inserts is still
140/// in front of the pass that pushes semi joins down.
141///
142/// Top N is last of the passes that rewrite the shape of a plan, because it is the one that fuses
143/// two operators into one rather than moving something around. Everything before it is written
144/// against a sort and a limit, and a pass that had to know about both spellings of the same plan is
145/// a pass with two of every rule in it.
146///
147/// The build side is chosen after all of them, and that is not an ordering preference so much as a
148/// consequence of what it reads. It picks a side per join from an estimate of how many rows each
149/// side produces, and a filter that has not been pushed down yet, a limit that has not reached the
150/// scan yet and a subtree that empty result pullup is about to delete are all estimates of a plan
151/// nobody is going to run. It is also the only pass here that writes a field rather than moving a
152/// node, so nothing after it would have anything to do with what it wrote.
153///
154/// Dropping an unread materialisation is after the empty result pullup and before everything that
155/// moves an operator around. After, because the pullup is what turns a body into an empty relation
156/// and a body that has become one reads nothing, so a run that looked before it would find the work
157/// on the next run instead, which is the fixed sequence not settling. Before the rest, because the
158/// subtree it removes is a subtree they would otherwise walk, and because the operators it leaves
159/// next to each other are the pairs limit pushdown and top N are looking for.
160///
161/// Filter pushdown and limit pushdown used to make work for each other, which is worth recording
162/// here because the fix is not in this list. Limit pushdown trades a limit with the projection under
163/// it, so `Filter / Limit / Project` became `Filter / Project / Limit`, and the filter that had
164/// nowhere to go then had a projection to go through, one position after the pass that would have
165/// taken it. Reordering does not help: filter pushdown has to be in front of join order, the mark
166/// rewrites and group key pushdown, all of which read a plan whose predicates have already landed,
167/// and limit pushdown has to be behind the unread materialisation drop for the reason above. Nor
168/// does running either of them twice, because each round the two of them trade moves one more level
169/// of a nested query, so the number of rounds it takes is how deeply the query is nested. What fixes
170/// it is filter pushdown crossing the limits itself, which is described where it does that.
171///
172/// Reading a link instead of building a hash table is last of all, after the build side has been
173/// chosen. It replaces a join outright, so a pass that ran after it would have to know about a
174/// second kind of join to say anything about one, and there is nothing any of them want to say:
175/// the join it leaves behind has the same inputs, the same condition and the same kind. It also
176/// needs the plan to have stopped moving, because what it asks about the parent is how many rows
177/// reach it and what it asks about the child is whether the rows are still the table's own, and
178/// both of those are questions about a plan somebody is going to run rather than a draft of one.
179/// Running after the build side costs nothing, because the side a link join builds is neither of
180/// them.
181pub static PASSES: [&(dyn Pass + Sync); 26] = [
182 &fold::ExpressionRewriter,
183 &distinct::DistinctAggregateRewrite,
184 &dependent::DependentGroupKeys,
185 &fromkey::AnswersFromTheKey,
186 &filter::FilterPushdown,
187 &delim::Deliminator,
188 &order::JoinOrder,
189 &semi::MarkToSemi,
190 &semi::DistinctToSemi,
191 &keys::GroupKeyPushdown,
192 &semi::SemiPushdown,
193 &eliminate::JoinElimination,
194 &nonulls::NoNulls,
195 &empty::EmptyResultPullup,
196 &extremes::StatisticsPropagation,
197 &cte::UnusedMaterialization,
198 &columns::UnusedColumns,
199 &reorder::FilterOrder,
200 &limit::LimitPushdown,
201 &topn::TopN,
202 &late::LateMaterialization,
203 &sides::BuildSideProbeSide,
204 &presize::AggregatePresize,
205 &dense::AggregateDense,
206 &cluster::AggregateCluster,
207 &link::LinkJoinRewrite,
208];
209
210/// Every name `SET disabled_optimizers` accepts, which is every name DuckDB accepts.
211///
212/// `SELECT name FROM duckdb_optimizers()` on the pinned binary, sorted, all forty four of them.
213/// Fifteen of them name a pass [`PASSES`] holds, and every name here is one rudb takes without
214/// complaint, because turning off a pass that does not exist is a thing that has already happened.
215///
216/// Accepting the other twenty nine is the whole point. Forty five files in the upstream corpus run a
217/// `SET disabled_optimizers`, and most of them name a pass rudb has not written,
218/// `compressed_materialization` and `common_subexpressions` and the rest. Refusing those makes the
219/// `SET` fail, and a failed `SET` in a sqllogictest file ends the file, so every record after it
220/// goes unasked over a pass whose absence changes no answer.
221///
222/// The list is written down rather than discovered, because there is nothing to discover it from:
223/// DuckDB is a binary that may not be on the machine and this has to answer the same way when it is
224/// not. It is pinned to the same commit the rest of the compatibility work is pinned to, and a
225/// release that adds a pass adds a name here.
226pub static UPSTREAM: [&str; 44] = [
227 "aggregate_function_rewriter",
228 "aggregate_reuse",
229 "build_side_probe_side",
230 "column_lifetime",
231 "common_aggregate",
232 "common_subexpressions",
233 "common_subplan",
234 "compressed_materialization",
235 "cte_filter_pusher",
236 "cte_inlining",
237 "deliminator",
238 "distinct_aggregate_rewrite",
239 "duplicate_groups",
240 "empty_result_pullup",
241 "expression_rewriter",
242 "extension",
243 "filter_pullup",
244 "filter_pushdown",
245 "grouping_sets",
246 "in_clause",
247 "join_elimination",
248 "join_filter_pushdown",
249 "join_order",
250 "late_materialization",
251 "limit_pushdown",
252 "materialized_cte",
253 "outer_join_simplification",
254 "partial_aggregate_pushdown",
255 "partitioned_execution",
256 "projection_pullup",
257 "regex_range",
258 "remote_pushdown",
259 "reorder_filter",
260 "row_group_pruner",
261 "sampling_pushdown",
262 "scalar_fn_pushdown",
263 "statistics_propagation",
264 "top_n",
265 "top_n_window_elimination",
266 "type_pushdown",
267 "unnest_rewriter",
268 "unused_columns",
269 "window_rewriter",
270 "window_self_join",
271];
272
273/// Rewrites a bound plan into the plan that runs, with every pass on.
274///
275/// # Errors
276///
277/// If a pass left the plan malformed or narrowed what it returns, which is a bug in the pass and
278/// not in the query.
279pub fn optimize(plan: &mut Plan) -> Result<()> {
280 optimize_with(plan, &Context::new())
281}
282
283/// Rewrites a bound plan into the plan that runs, skipping the passes the context turned off.
284///
285/// Every pass preserves the plan invariant, which is what [`Plan::validate`] checks, so this checks
286/// it once at the end rather than each pass checking itself. In a release build it does not, because
287/// a pass that breaks the invariant breaks it the same way in both builds and the debug build is
288/// where that gets found.
289///
290/// It also checks that the plan still returns as many columns as it did on the way in. A malformed
291/// plan is found by whatever runs next, but a rewrite that quietly changes what a query returns is
292/// the one failure that running the query afterwards would not notice, and column pruning in
293/// particular is a pass whose only way of being wrong is exactly that.
294///
295/// It also checks, in a debug build, that running the whole sequence a second time changes nothing.
296/// That is the property that makes a fixed sequence the right shape: a pass that keeps finding work
297/// on a plan it has already rewritten is a pass whose output depends on how many times it happened
298/// to run, and in a fixed sequence it runs once, so the plan that reaches the executor is whatever
299/// the first pass left behind. Each pass has its own test for this and the assertion is here anyway,
300/// because the pair that is not idempotent together is usually a pair that is idempotent apart.
301///
302/// # Errors
303///
304/// Whatever a pass reported, and then, in a debug build, if a pass left the plan malformed, narrowed
305/// what it returns or did not settle, all three of which are a bug in the pass and not in the query.
306pub fn optimize_with(plan: &mut Plan, context: &Context) -> Result<()> {
307 // The master ablation, and the whole of it. Every rule with a switch of its own also has
308 // `Rule::StatsAll` as its master and so is already off by the time a pass asks, but the passes
309 // are not the only readers: a cardinality the join order chose on, a bound a filter was ordered
310 // by and a distinct count an aggregate sized from are all answers that came from here. Taking
311 // the answers away is one line that reaches all of them, including the reader nobody has written
312 // yet.
313 if !context.allows(Rule::StatsAll) {
314 plan.forget_statistics();
315 }
316 unnest::lower(plan)?;
317 run(plan, context, &PASSES)
318}
319
320/// The sequence, over a list of passes the tests can choose.
321fn run(plan: &mut Plan, context: &Context, passes: &[&(dyn Pass + Sync)]) -> Result<()> {
322 let before = output_columns(plan, plan.root());
323 once(plan, context, passes)?;
324 if cfg!(debug_assertions) {
325 plan.validate()?;
326 let after = output_columns(plan, plan.root());
327 if after != before {
328 return Err(Error::internal(format!(
329 "a pass turned a query of {before} columns into one of {after}"
330 )));
331 }
332 let settled = plan.to_string();
333 once(plan, context, passes)?;
334 let again = plan.to_string();
335 if again != settled {
336 return Err(Error::internal(format!(
337 "the passes did not settle, since running them again gave a different plan\n\n{settled}\n{again}"
338 )));
339 }
340 }
341 Ok(())
342}
343
344/// One run of every pass that is turned on.
345fn once(plan: &mut Plan, context: &Context, passes: &[&(dyn Pass + Sync)]) -> Result<()> {
346 for pass in passes {
347 if context.is_disabled(pass.name()) {
348 continue;
349 }
350 pass.run(plan, context)?;
351 }
352 Ok(())
353}
354
355/// How many columns a node produces, which no pass is allowed to change at the root.
356///
357/// The count rather than the names and types, because the root of a plan the binder builds is a
358/// projection and what has to hold is that a pass did not add or drop one of its expressions. The
359/// recursion is over the operators that pass their input's width through, so its depth is the
360/// nesting the binder already walked to build the plan.
361fn output_columns(plan: &Plan, reference: NodeRef) -> usize {
362 match *plan.node(reference) {
363 Node::Get { columns, .. }
364 | Node::Values { columns, .. }
365 | Node::TableFunction { columns, .. }
366 | Node::Fetch { columns, .. }
367 | Node::TableFetch { columns, .. }
368 | Node::CteScan { columns, .. } => plan.field_list(columns).len(),
369 Node::Project { exprs, .. } => plan.expr_list(exprs).len(),
370 Node::Aggregate { groups, aggregates, .. } => {
371 plan.expr_list(groups).len() + plan.expr_list(aggregates).len()
372 }
373 Node::Window { input, expressions, .. } => {
374 output_columns(plan, input) + plan.expr_list(expressions).len()
375 }
376 Node::LateralFunction { input, columns, .. } => {
377 output_columns(plan, input) + plan.field_list(columns).len()
378 }
379 Node::Dummy => 0,
380 Node::Filter { input, .. }
381 | Node::Sort { input, .. }
382 | Node::Limit { input, .. }
383 | Node::LimitPercent { input, .. }
384 | Node::TopN { input, .. }
385 | Node::Distinct { input, .. } => output_columns(plan, input),
386 // A materialisation returns what the query that reads it returns. The held columns are not
387 // part of that: they go to the reads of it and never past this node.
388 Node::MaterializedCte { body, .. } => output_columns(plan, body),
389 // A set operation is as wide as either side, since the binder already required the two to
390 // agree. A join and a cross product are as wide as the two together.
391 Node::SetOp { left, .. } => output_columns(plan, left),
392 Node::Join { left, right, .. }
393 | Node::DependentJoin { left, right, .. }
394 | Node::CrossProduct { left, right } => {
395 output_columns(plan, left) + output_columns(plan, right)
396 }
397 // A semi or anti link join never touches the parent, so its width is the child's. The
398 // other two put the gathered parent columns after the child's and are as wide as both.
399 Node::LinkJoin { child, parent, kind, .. } => match kind {
400 JoinKind::Semi | JoinKind::Anti => output_columns(plan, child),
401 _ => output_columns(plan, child) + output_columns(plan, parent),
402 },
403 }
404}
405
406#[cfg(test)]
407mod tests {
408 use super::*;
409
410 use rudb_catalog::Catalog;
411 // The only test below that names a `Bound` builds under `debug_assertions`, so in a release
412 // test build this import is unused and `-D warnings` turns that into an error. That is the
413 // release job on main since #1092.
414 #[cfg(debug_assertions)]
415 use rudb_plan::Bound;
416
417 /// How wide the plan a text prints is, before anything has run over it.
418 fn width(text: &str) -> usize {
419 let plan =
420 Plan::parse(text).unwrap_or_else(|error| panic!("{text} did not parse: {error}"));
421 output_columns(&plan, plan.root())
422 }
423
424 /// Optimize the plan a text prints and hand back what it printed afterwards.
425 fn optimized(text: &str) -> String {
426 let mut plan =
427 Plan::parse(text).unwrap_or_else(|error| panic!("{text} did not parse: {error}"));
428 optimize(&mut plan).unwrap_or_else(|error| panic!("{text} did not optimize: {error}"));
429 plan.to_string()
430 }
431
432 #[test]
433 fn every_optimizer_allocation_keeps_a_source_span() {
434 let sql =
435 "SELECT count(DISTINCT x) FROM (VALUES ('a'), ('b'), ('b')) t(x) WHERE true LIMIT 1";
436 let mut plan = rudb_bind::bind_sql(sql, &Catalog::new()).expect("the query binds");
437 let nodes = plan.node_count();
438 let exprs = plan.expr_count();
439
440 optimize(&mut plan).expect("the complete optimizer sequence succeeds");
441
442 assert!(!plan.node_span(plan.root()).is_empty(), "the optimized root keeps a source range");
443 for at in nodes..plan.node_count() {
444 let at = u32::try_from(at).expect("the plan arena fits in a reference");
445 assert!(!plan.node_span(at).is_empty(), "optimizer node {at} has no source range");
446 }
447 for at in exprs..plan.expr_count() {
448 let at = u32::try_from(at).expect("the expression arena fits in a reference");
449 assert!(
450 !plan.expr_span(at).is_empty(),
451 "optimizer expression {at} has no source range"
452 );
453 }
454 }
455
456 #[test]
457 fn the_width_of_a_plan_is_the_width_of_whatever_produces_its_columns() {
458 assert_eq!(
459 width(
460 "Project #1 [#0.0::INTEGER AS a]\n Get memory.main.t AS t #0 [a::INTEGER, b::VARCHAR]\n"
461 ),
462 1
463 );
464 assert_eq!(width("Get memory.main.t AS t #0 [a::INTEGER, b::VARCHAR]\n"), 2);
465 assert_eq!(width("Dummy\n"), 0);
466 assert_eq!(
467 width(
468 "Aggregate #1 groups=[#0.0::INTEGER] aggregates=[count_star()::BIGINT]\n Get memory.main.t AS t #0 [a::INTEGER]\n"
469 ),
470 2
471 );
472 }
473
474 /// A `LIMIT` or a `SORT` is as wide as what is under it, which is the recursion this function
475 /// exists for and the part a single level check would get wrong.
476 #[test]
477 fn an_operator_that_passes_its_input_through_is_as_wide_as_its_input() {
478 assert_eq!(
479 width("Limit 1 offset 0\n Get memory.main.t AS t #0 [a::INTEGER, b::VARCHAR]\n"),
480 2
481 );
482 }
483
484 /// A join is both sides and a set operation is either one, since the binder already required
485 /// the two sides of a set operation to agree.
486 #[test]
487 fn a_join_is_both_sides_together_and_a_set_operation_is_one_of_them() {
488 assert_eq!(
489 width(
490 "Join INNER on=[]\n Get memory.main.t AS t #0 [a::INTEGER, b::VARCHAR]\n Get memory.main.u AS u #1 [x::INTEGER]\n"
491 ),
492 3
493 );
494 assert_eq!(
495 width(
496 "SetOp UNION ALL #2\n Get memory.main.t AS t #0 [a::INTEGER]\n Get memory.main.u AS u #1 [x::INTEGER]\n"
497 ),
498 1
499 );
500 }
501
502 /// The check is on the whole of `optimize` and not on one pass, so it keeps holding as passes
503 /// are added. This is the shape it runs over today.
504 #[test]
505 fn optimizing_keeps_a_query_as_wide_as_it_was() {
506 let before = "Project #1 [#0.1::VARCHAR AS b]\n Get memory.main.t AS t #0 [a::INTEGER, b::VARCHAR]\n";
507 let after = "Project #1 [#0.0::VARCHAR AS b]\n Get memory.main.t AS t #0 [b::VARCHAR]\n";
508 assert_eq!(optimized(before), after);
509 assert_eq!(width(before), width(after));
510 }
511
512 #[test]
513 fn no_two_passes_answer_to_the_same_name() {
514 // The name is the address, so two passes sharing one would make the toggle turn off
515 // whichever came first in the list and silently leave the other on.
516 let mut names: Vec<&str> = PASSES.iter().map(|pass| pass.name()).collect();
517 names.sort_unstable();
518 let held = names.len();
519 names.dedup();
520 assert_eq!(names.len(), held, "{names:?}");
521 }
522
523 #[test]
524 fn a_pass_that_is_turned_off_does_not_run() {
525 let text = "Project #1 [\"+\"(1::INTEGER, 1::INTEGER)::INTEGER AS n]\n Get memory.main.t AS t #0 [a::INTEGER]\n";
526 let mut plan = Plan::parse(text).expect("a well formed plan");
527 let context = Context::without("expression_rewriter").expect("a name that is a pass");
528 optimize_with(&mut plan, &context).expect("the other pass still runs");
529 assert_eq!(
530 plan.to_string(),
531 "Project #1 [\"+\"(1::INTEGER, 1::INTEGER)::INTEGER AS n]\n Get memory.main.t AS t #0 []\n"
532 );
533 }
534
535 /// A pass that finds the same work every time it looks, which is what the assertion is for.
536 #[derive(Debug)]
537 #[cfg(debug_assertions)]
538 struct Restless;
539
540 #[cfg(debug_assertions)]
541 impl Pass for Restless {
542 fn name(&self) -> &'static str {
543 "restless"
544 }
545
546 fn run(&self, plan: &mut Plan, _context: &Context) -> Result<()> {
547 let root = plan.root();
548 if !matches!(*plan.node(root), Node::Limit { .. }) {
549 return Ok(());
550 }
551 let stacked = plan.add_node(Node::Limit {
552 input: root,
553 count: Bound::Rows(1),
554 offset: Bound::Rows(0),
555 });
556 plan.set_root(stacked);
557 Ok(())
558 }
559 }
560
561 /// The settle check is a debug build check, so the test for it is a debug build test. Without
562 /// this the release profile job runs a test that asserts an error nothing was going to report,
563 /// which is what it had been doing since #196, because the per commit gate runs the tests once
564 /// and runs them in debug.
565 #[test]
566 #[cfg(debug_assertions)]
567 fn a_pass_that_never_settles_is_a_reported_error_and_not_a_plan() {
568 let text = "Limit 1 offset 0\n Get memory.main.t AS t #0 [a::INTEGER]\n";
569 let mut plan = Plan::parse(text).expect("a well formed plan");
570 let error = run(&mut plan, &Context::new(), &[&Restless]).expect_err("it never settles");
571 assert!(error.message().starts_with("the passes did not settle"), "{}", error.message());
572 }
573
574 /// The pair that made filter pushdown run twice. Limit pushdown trades the limit with the
575 /// projection under it, and the filter that was stuck above the limit then has a projection to
576 /// go through, which is work the one run of filter pushdown was already past. With one run this
577 /// is an `INTERNAL Error: the passes did not settle` on a query anybody could write.
578 #[test]
579 fn a_filter_over_a_subquery_that_ends_in_a_limit_settles() {
580 let text = concat!(
581 "Project #2 [#1.0::INTEGER AS x]\n",
582 " Filter (#1.0::INTEGER > 1::INTEGER)::BOOLEAN\n",
583 " Limit 4 offset 0\n",
584 " Project #1 [#0.0::INTEGER AS x]\n",
585 " Get memory.main.t AS t #0 [x::INTEGER]\n",
586 );
587 assert_eq!(
588 optimized(text),
589 concat!(
590 "Project #2 [#1.0::INTEGER AS x]\n",
591 " Project #1 [#0.0::INTEGER AS x]\n",
592 " Filter (#0.0::INTEGER > 1::INTEGER)::BOOLEAN\n",
593 " Limit 4 offset 0\n",
594 " Get memory.main.t AS t #0 [x::INTEGER]\n",
595 )
596 );
597 assert_eq!(width(text), 1);
598 }
599
600 /// Folding before pruning, which is the reason the order in [`PASSES`] is the order it is. The
601 /// column is read only by a branch that cannot be taken, so one pass has to remove the branch
602 /// before the other can see that nothing reads the column.
603 #[test]
604 fn folding_runs_first_so_that_pruning_sees_the_columns_it_freed() {
605 let text = "Project #1 [CASE WHEN FALSE::BOOLEAN THEN #0.1::INTEGER ELSE #0.0::INTEGER END::INTEGER AS n]\n Get memory.main.t AS t #0 [a::INTEGER, b::INTEGER]\n";
606 assert_eq!(
607 optimized(text),
608 "Project #1 [#0.0::INTEGER AS n]\n Get memory.main.t AS t #0 [a::INTEGER]\n"
609 );
610 }
611
612 /// Folding before the distinct aggregate rewrite, which is the other half of that order. The
613 /// rewrite wants every `DISTINCT` call in a node to have the same argument, and these two have
614 /// the same argument only once folding has run, so with the passes the other way around the
615 /// rewrite refuses here and fires on a second run over its own output.
616 #[test]
617 fn folding_runs_first_so_that_the_distinct_rewrite_sees_one_argument_rather_than_two() {
618 let text = concat!(
619 "Aggregate #1 groups=[] aggregates=[max(DISTINCT \"+\"(1::INTEGER, 1::INTEGER)::INTEGER)::INTEGER, min(DISTINCT 2::INTEGER)::INTEGER]\n",
620 " Dummy\n",
621 );
622 assert_eq!(
623 optimized(text),
624 concat!(
625 "Aggregate #1 groups=[] aggregates=[max(#2.0::INTEGER)::INTEGER, min(#2.0::INTEGER)::INTEGER]\n",
626 " Aggregate #2 groups=[2::INTEGER] aggregates=[]\n",
627 " Dummy\n",
628 )
629 );
630 }
631}