Skip to content

Commit ec97d1c

Browse files
SubhamSinghalSubham SinghalblagininkumarUjjawal
authored
Push down topk through join (#21621)
## Which issue does this PR close? - closes #11900 ## Rationale for this change When a query has `ORDER BY <cols> LIMIT N` on top of an outer join and all sort columns come from the preserved side, DataFusion currently runs the full join first, then sorts and limits. We can push a copy of the `Sort(fetch=N)` to the preserved input, reducing the number of rows entering the join. **Before:** ``` Sort: t1.b ASC, fetch=3 Left Join: t1.a = t2.a Scan: t1 ← scans ALL rows Scan: t2 ``` **After:** ``` Sort: t1.b ASC, fetch=3 Left Join: t1.a = t2.a Sort: t1.b ASC, fetch=3 ← pushed down Scan: t1 ← only top-3 rows enter join Scan: t2 ``` ## What changes are included in this PR? A new logical optimizer rule `PushDownTopKThroughJoin` that: 1. Matches `Sort` with `fetch = Some(N)` (TopK) 2. Looks through an optional `Projection` to find a `Join` 3. Checks join type is LEFT or RIGHT with no non-equijoin filter 4. Verifies all sort expression columns come from the preserved side 5. Inserts a copy of the `Sort(fetch=N)` on the preserved child 6. Keeps the top-level sort for correctness ## Are these changes tested? Yes through UT ## Are there any user-facing changes? No API changes. --------- Co-authored-by: Subham Singhal <[email protected]> Co-authored-by: Dmitrii Blaginin <[email protected]> Co-authored-by: Kumar Ujjawal <[email protected]>
1 parent 32662e7 commit ec97d1c

4 files changed

Lines changed: 2160 additions & 219 deletions

File tree

‎datafusion/core/src/optimizer_rule_reference.md‎

Lines changed: 27 additions & 27 deletions
Original file line numberDiff line numberDiff line change
@@ -35,33 +35,33 @@ Rule order matters. The default pipeline may change between releases.
3535

3636
### Logical Optimizer Rules
3737

38-
| order | rule | summary |
39-
| ----- | ----------------------------------------- | --------------------------------------------------------------------------------------------------------------------------- |
40-
| 1 | `rewrite_set_comparison` | Rewrites `ANY` and `ALL` set-comparison subqueries into `EXISTS`-based boolean expressions with correct SQL NULL semantics. |
41-
| 2 | `optimize_unions` | Flattens nested unions and removes unions with a single input. |
42-
| 3 | `unions_to_filter` | Merges `UNION DISTINCT` branches that share the same source into a single filtered branch with a disjunctive predicate. |
43-
| 4 | `simplify_expressions` | Constant-folds and simplifies expressions while preserving output names. |
44-
| 5 | `replace_distinct_aggregate` | Rewrites `DISTINCT` and `DISTINCT ON` operators into aggregate-based plans that later rules can optimize further. |
45-
| 6 | `eliminate_join` | Replaces keyless inner joins with a literal `false` filter by an empty relation. |
46-
| 7 | `decorrelate_predicate_subquery` | Converts eligible `IN` and `EXISTS` predicate subqueries into semi or anti joins. |
47-
| 8 | `scalar_subquery_to_join` | Rewrites eligible scalar subqueries into joins and adds schema-preserving projections. |
48-
| 9 | `decorrelate_lateral_join` | Rewrites eligible lateral joins into regular joins. |
49-
| 10 | `extract_equijoin_predicate` | Splits join filters into equijoin keys and residual predicates. |
50-
| 11 | `eliminate_duplicated_expr` | Removes duplicate expressions from projections, aggregates, and similar operators. |
51-
| 12 | `eliminate_filter` | Drops always-true filters and replaces always-false or NULL filters with empty relations. |
52-
| 13 | `eliminate_cross_join` | Uses filter predicates to replace cross joins with inner joins when join keys can be found. |
53-
| 14 | `eliminate_limit` | Removes no-op limits and simplifies trivial limit shapes. |
54-
| 15 | `propagate_empty_relation` | Pushes empty-relation knowledge upward so operators fed by no rows collapse early. |
55-
| 16 | `filter_null_join_keys` | Adds `IS NOT NULL` filters to nullable equijoin keys that can never match. |
56-
| 17 | `eliminate_outer_join` | Rewrites outer joins to inner joins when later filters reject the NULL-extended rows. |
57-
| 18 | `push_down_limit` | Moves literal limits closer to scans and unions and merges adjacent limits. |
58-
| 19 | `push_down_filter` | Moves filters as early as possible through filter-commutative operators. |
59-
| 20 | `single_distinct_aggregation_to_group_by` | Rewrites single-column `DISTINCT` aggregations into two-stage `GROUP BY` plans. |
60-
| 21 | `eliminate_group_by_constant` | Removes constant or functionally redundant expressions from `GROUP BY`. |
61-
| 22 | `common_sub_expression_eliminate` | Computes repeated subexpressions once and reuses the result. |
62-
| 23 | `extract_leaf_expressions` | Pulls cheap leaf expressions closer to data sources so later pruning and filter rules can act earlier. |
63-
| 24 | `push_down_leaf_projections` | Pushes the helper projections created by leaf extraction toward leaf inputs. |
64-
| 25 | `optimize_projections` | Prunes unused columns and removes unnecessary logical projections. |
38+
| order | rule | summary |
39+
| ----- | ----------------------------------------- | --------------------------------------------------------------------------------------------------------------------------------------------------------------------- |
40+
| 1 | `rewrite_set_comparison` | Rewrites `ANY` and `ALL` set-comparison subqueries into `EXISTS`-based boolean expressions with correct SQL NULL semantics. |
41+
| 2 | `optimize_unions` | Flattens nested unions and removes unions with a single input. |
42+
| 3 | `unions_to_filter` | Merges `UNION DISTINCT` branches that share the same source into a single filtered branch with a disjunctive predicate. |
43+
| 4 | `simplify_expressions` | Constant-folds and simplifies expressions while preserving output names. |
44+
| 5 | `replace_distinct_aggregate` | Rewrites `DISTINCT` and `DISTINCT ON` operators into aggregate-based plans that later rules can optimize further. |
45+
| 6 | `eliminate_join` | Replaces keyless inner joins with a literal `false` filter by an empty relation. |
46+
| 7 | `decorrelate_predicate_subquery` | Converts eligible `IN` and `EXISTS` predicate subqueries into semi or anti joins. |
47+
| 8 | `scalar_subquery_to_join` | Rewrites eligible scalar subqueries into joins and adds schema-preserving projections. |
48+
| 9 | `decorrelate_lateral_join` | Rewrites eligible lateral joins into regular joins. |
49+
| 10 | `extract_equijoin_predicate` | Splits join filters into equijoin keys and residual predicates. |
50+
| 11 | `eliminate_duplicated_expr` | Removes duplicate expressions from projections, aggregates, and similar operators. |
51+
| 12 | `eliminate_filter` | Drops always-true filters and replaces always-false or NULL filters with empty relations. |
52+
| 13 | `eliminate_cross_join` | Uses filter predicates to replace cross joins with inner joins when join keys can be found. |
53+
| 14 | `eliminate_limit` | Removes no-op limits and simplifies trivial limit shapes. |
54+
| 15 | `propagate_empty_relation` | Pushes empty-relation knowledge upward so operators fed by no rows collapse early. |
55+
| 16 | `filter_null_join_keys` | Adds `IS NOT NULL` filters to nullable equijoin keys that can never match. |
56+
| 17 | `eliminate_outer_join` | Rewrites outer joins to inner joins when later filters reject the NULL-extended rows. |
57+
| 18 | `push_down_limit` | Moves literal limits to scans/unions, merges limits, and pushes `Sort(fetch=N)` onto a preserved join side only when every sort key is from it; the outer Sort stays. |
58+
| 19 | `push_down_filter` | Moves filters as early as possible through filter-commutative operators. |
59+
| 20 | `single_distinct_aggregation_to_group_by` | Rewrites single-column `DISTINCT` aggregations into two-stage `GROUP BY` plans. |
60+
| 21 | `eliminate_group_by_constant` | Removes constant or functionally redundant expressions from `GROUP BY`. |
61+
| 22 | `common_sub_expression_eliminate` | Computes repeated subexpressions once and reuses the result. |
62+
| 23 | `extract_leaf_expressions` | Pulls cheap leaf expressions closer to data sources so later pruning and filter rules can act earlier. |
63+
| 24 | `push_down_leaf_projections` | Pushes the helper projections created by leaf extraction toward leaf inputs. |
64+
| 25 | `optimize_projections` | Prunes unused columns and removes unnecessary logical projections. |
6565

6666
### Physical Optimizer Rules
6767

0 commit comments

Comments
 (0)