Skip to content

Commit 8dbc1dd

Browse files
committed
Refactor topk through join code
1 parent d5628e3 commit 8dbc1dd

2 files changed

Lines changed: 423 additions & 86 deletions

File tree

‎datafusion/optimizer/src/push_down_limit.rs‎

Lines changed: 23 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -15,7 +15,9 @@
1515
// specific language governing permissions and limitations
1616
// under the License.
1717

18-
//! [`PushDownLimit`] pushes `LIMIT` earlier in the query plan
18+
//! [`PushDownLimit`] pushes `LIMIT` earlier in the query plan, and pushes a
19+
//! `Sort` with a fetch limit (TopK) onto a join's preserved-side child (see
20+
//! the `topk_through_join` submodule).
1921
2022
use std::cmp::min;
2123
use std::sync::Arc;
@@ -33,7 +35,21 @@ mod topk_through_join;
3335
use topk_through_join::push_topk_through_join;
3436

3537
/// Optimization rule that tries to push down `LIMIT`.
36-
//. It will push down through projection, limits (taking the smaller limit)
38+
///
39+
/// It pushes `LIMIT` through projections, unions, joins and into scans
40+
/// (taking the smaller limit when one is already present), merges adjacent
41+
/// limits, and pushes a `Sort` carrying a fetch limit (a TopK) onto a join's
42+
/// preserved-side child so fewer rows enter the join. See
43+
/// `topk_through_join` for the latter.
44+
///
45+
/// The TopK-through-join rewrite has an implicit ordering dependency on
46+
/// `push_down_filter` and `eliminate_outer_join`: a `Filter` sitting between
47+
/// the `Sort` and the `Join` blocks this rule (a `Filter` can't sink below a
48+
/// fetch-bearing node without changing which rows survive), and an outer
49+
/// join only has a "preserved side" once `eliminate_outer_join` has already
50+
/// dropped joins it can prove are equivalent to an inner join. Both of those
51+
/// rules need a prior or concurrent pass to unblock this one; with
52+
/// `max_passes >= 2` this resolves on a later pass.
3753
#[derive(Default, Debug)]
3854
pub struct PushDownLimit {}
3955

@@ -53,13 +69,11 @@ impl OptimizerRule for PushDownLimit {
5369
fn rewrite(
5470
&self,
5571
plan: LogicalPlan,
56-
config: &dyn OptimizerConfig,
72+
_config: &dyn OptimizerConfig,
5773
) -> Result<Transformed<LogicalPlan>> {
5874
match plan {
59-
LogicalPlan::Limit(limit) => rewrite_limit(limit, config),
60-
LogicalPlan::Sort(s) if s.fetch.is_some() => {
61-
push_topk_through_join(LogicalPlan::Sort(s))
62-
}
75+
LogicalPlan::Limit(limit) => rewrite_limit(limit),
76+
LogicalPlan::Sort(s) if s.fetch.is_some() => push_topk_through_join(s),
6377
other => Ok(Transformed::no(other)),
6478
}
6579
}
@@ -76,11 +90,7 @@ impl OptimizerRule for PushDownLimit {
7690
/// Limit-side dispatch (split out from `rewrite` so that the top-level
7791
/// match in `OptimizerRule::rewrite` reads as a parallel branch alongside
7892
/// the Sort-with-fetch handler).
79-
#[expect(clippy::only_used_in_recursion)]
80-
fn rewrite_limit(
81-
mut limit: Limit,
82-
config: &dyn OptimizerConfig,
83-
) -> Result<Transformed<LogicalPlan>> {
93+
fn rewrite_limit(mut limit: Limit) -> Result<Transformed<LogicalPlan>> {
8494
// Currently only rewrite if skip and fetch are both literals
8595
let SkipType::Literal(skip) = limit.get_skip_type()? else {
8696
return Ok(Transformed::no(LogicalPlan::Limit(limit)));
@@ -106,7 +116,7 @@ fn rewrite_limit(
106116
};
107117

108118
// recursively reapply the rule on the new limit
109-
return rewrite_limit(new_limit, config);
119+
return rewrite_limit(new_limit);
110120
}
111121

112122
// no fetch to push, so return the original plan

0 commit comments

Comments
 (0)