Skip to content

Commit 9e4cda9

Browse files
masonh22dispanser
authored andcommitted
fix: The limit_pushdown physical optimization rule removes limits in some cases leading to incorrect results (apache#20048) (#394)
<!-- We generally require a GitHub issue to be filed for all bug fixes and enhancements and this helps us generate change logs for our releases. You can link an issue to this PR using the GitHub syntax. For example `Closes #123` indicates that this PR will close issue #123. --> None <!-- Why are you proposing this change? If this is already explained clearly in the issue then this section is not needed. Explaining clearly why changes are proposed helps reviewers understand your changes and offer better suggestions for fixes. --> Bug 1: When pushing down limits, we recurse down the physical plan accumulating limits until we reach a node where we can't push the limit down further. At this point, we insert another limit executor (or push it into the current node, if that node supports it). After this, we continue recursing to try to find more limits to push down. If we do find another, we remove it, but we don't set the `GlobalRequirements::satisfied` field back to false, meaning we don't always re-insert this limit. Bug 2: When we're pushing down a limit with a skip/offset and no fetch/limit and we run into a node that supports fetch, we set `GlobalRequirements::satisfied` to true. This is wrong: the limit is not satisfied because fetch doesn't support skip/offset. Instead, we should set `GlobalRequirements::satisfied` to true if skip/offset is 0. <!-- There is no need to duplicate the description in the issue here but it is sometimes worth providing a summary of the individual changes in this PR. --> This includes a one-line change to the push down limit logic that fixes the issue. <!-- We typically require tests for all PRs in order to: 1. Prevent the code from being accidentally broken by subsequent changes 2. Serve as another way to document the expected behavior of the code If tests are not included in your PR, please explain why (for example, are they covered by existing tests)? --> I added a test that replicates the issue and fails without this change. <!-- If there are user-facing changes then we may require documentation to be updated before approving the PR. --> No <!-- If there are any breaking changes to public APIs, please add the `api change` label. -->
1 parent 1481576 commit 9e4cda9

4 files changed

Lines changed: 136 additions & 22 deletions

File tree

‎datafusion/core/tests/physical_optimizer/limit_pushdown.rs‎

Lines changed: 111 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -22,7 +22,7 @@ use arrow::datatypes::{DataType, Field, Schema, SchemaRef};
2222
use datafusion_common::config::ConfigOptions;
2323
use datafusion_common::error::Result;
2424
use datafusion_execution::{SendableRecordBatchStream, TaskContext};
25-
use datafusion_expr::Operator;
25+
use datafusion_expr::{JoinType, Operator};
2626
use datafusion_physical_expr::expressions::BinaryExpr;
2727
use datafusion_physical_expr::expressions::{col, lit};
2828
use datafusion_physical_expr::{Partitioning, PhysicalSortExpr};
@@ -32,6 +32,7 @@ use datafusion_physical_plan::coalesce_batches::CoalesceBatchesExec;
3232
use datafusion_physical_plan::coalesce_partitions::CoalescePartitionsExec;
3333
use datafusion_physical_plan::empty::EmptyExec;
3434
use datafusion_physical_plan::filter::FilterExec;
35+
use datafusion_physical_plan::joins::NestedLoopJoinExec;
3536
use datafusion_physical_plan::limit::{GlobalLimitExec, LocalLimitExec};
3637
use datafusion_physical_plan::projection::ProjectionExec;
3738
use datafusion_physical_plan::repartition::RepartitionExec;
@@ -154,6 +155,16 @@ impl PartitionStream for DummyStreamPartition {
154155
}
155156
}
156157

158+
fn nested_loop_join_exec(
159+
left: Arc<dyn ExecutionPlan>,
160+
right: Arc<dyn ExecutionPlan>,
161+
join_type: JoinType,
162+
) -> Result<Arc<dyn ExecutionPlan>> {
163+
Ok(Arc::new(NestedLoopJoinExec::try_new(
164+
left, right, None, &join_type, None,
165+
)?))
166+
}
167+
157168
#[test]
158169
fn transforms_streaming_table_exec_into_fetching_version_when_skip_is_zero() -> Result<()>
159170
{
@@ -486,3 +497,102 @@ fn merges_local_limit_with_global_limit() -> Result<()> {
486497

487498
Ok(())
488499
}
500+
501+
#[test]
502+
fn preserves_nested_global_limit() -> Result<()> {
503+
// If there are multiple limits in an execution plan, they all need to be
504+
// preserved in the optimized plan.
505+
//
506+
// Plan structure:
507+
// GlobalLimitExec: skip=1, fetch=1
508+
// NestedLoopJoinExec (Left)
509+
// EmptyExec (left side)
510+
// GlobalLimitExec: skip=2, fetch=1
511+
// NestedLoopJoinExec (Right)
512+
// EmptyExec (left side)
513+
// EmptyExec (right side)
514+
let schema = create_schema();
515+
516+
// Build inner join: NestedLoopJoin(Empty, Empty)
517+
let inner_left = empty_exec(Arc::clone(&schema));
518+
let inner_right = empty_exec(Arc::clone(&schema));
519+
let inner_join = nested_loop_join_exec(inner_left, inner_right, JoinType::Right)?;
520+
521+
// Add inner limit: GlobalLimitExec: skip=2, fetch=1
522+
let inner_limit = global_limit_exec(inner_join, 2, Some(1));
523+
524+
// Build outer join: NestedLoopJoin(Empty, GlobalLimit)
525+
let outer_left = empty_exec(Arc::clone(&schema));
526+
let outer_join = nested_loop_join_exec(outer_left, inner_limit, JoinType::Left)?;
527+
528+
// Add outer limit: GlobalLimitExec: skip=1, fetch=1
529+
let outer_limit = global_limit_exec(outer_join, 1, Some(1));
530+
531+
let initial = get_plan_string(&outer_limit);
532+
let expected_initial = [
533+
"GlobalLimitExec: skip=1, fetch=1",
534+
" NestedLoopJoinExec: join_type=Left",
535+
" EmptyExec",
536+
" GlobalLimitExec: skip=2, fetch=1",
537+
" NestedLoopJoinExec: join_type=Right",
538+
" EmptyExec",
539+
" EmptyExec",
540+
];
541+
assert_eq!(initial, expected_initial);
542+
543+
let after_optimize =
544+
LimitPushdown::new().optimize(outer_limit, &ConfigOptions::new())?;
545+
let expected = [
546+
"GlobalLimitExec: skip=1, fetch=1",
547+
" NestedLoopJoinExec: join_type=Left",
548+
" EmptyExec",
549+
" GlobalLimitExec: skip=2, fetch=1",
550+
" NestedLoopJoinExec: join_type=Right",
551+
" EmptyExec",
552+
" EmptyExec",
553+
];
554+
assert_eq!(get_plan_string(&after_optimize), expected);
555+
556+
Ok(())
557+
}
558+
559+
#[test]
560+
fn preserves_skip_before_sort() -> Result<()> {
561+
// If there's a limit with skip before a node that (1) supports fetch but
562+
// (2) does not support limit pushdown, that limit should not be removed.
563+
//
564+
// Plan structure:
565+
// GlobalLimitExec: skip=1, fetch=None
566+
// SortExec: TopK(fetch=4)
567+
// EmptyExec
568+
let schema = create_schema();
569+
570+
let empty = empty_exec(Arc::clone(&schema));
571+
572+
let ordering = [PhysicalSortExpr {
573+
expr: col("c1", &schema)?,
574+
options: SortOptions::default(),
575+
}];
576+
let sort = sort_exec(ordering, empty).with_fetch(Some(4)).unwrap();
577+
578+
let outer_limit = global_limit_exec(sort, 1, None);
579+
580+
let initial = get_plan_string(&outer_limit);
581+
let expected_initial = [
582+
"GlobalLimitExec: skip=1, fetch=None",
583+
" SortExec: TopK(fetch=4), expr=[c1@0 ASC], preserve_partitioning=[false]",
584+
" EmptyExec",
585+
];
586+
assert_eq!(initial, expected_initial);
587+
588+
let after_optimize =
589+
LimitPushdown::new().optimize(outer_limit, &ConfigOptions::new())?;
590+
let expected = [
591+
"GlobalLimitExec: skip=1, fetch=3",
592+
" SortExec: TopK(fetch=4), expr=[c1@0 ASC], preserve_partitioning=[false]",
593+
" EmptyExec",
594+
];
595+
assert_eq!(get_plan_string(&after_optimize), expected);
596+
597+
Ok(())
598+
}

‎datafusion/physical-optimizer/src/limit_pushdown.rs‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -145,6 +145,7 @@ pub fn pushdown_limit_helper(
145145
);
146146
global_state.skip = skip;
147147
global_state.fetch = fetch;
148+
global_state.satisfied = false;
148149

149150
// Now the global state has the most recent information, we can remove
150151
// the `LimitExec` plan. We will decide later if we should add it again
@@ -162,7 +163,7 @@ pub fn pushdown_limit_helper(
162163
// If we have a non-limit operator with fetch capability, update global
163164
// state as necessary:
164165
if pushdown_plan.fetch().is_some() {
165-
if global_state.fetch.is_none() {
166+
if global_state.skip == 0 {
166167
global_state.satisfied = true;
167168
}
168169
(global_state.skip, global_state.fetch) = combine_limit(

‎datafusion/sqllogictest/test_files/limit.slt‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -711,8 +711,8 @@ ON t1.b = t2.b
711711
ORDER BY t1.b desc, c desc, c2 desc
712712
OFFSET 3 LIMIT 2;
713713
----
714-
3 99 82
715-
3 99 79
714+
3 98 79
715+
3 97 96
716716

717717
statement ok
718718
drop table ordered_table;

‎datafusion/sqllogictest/test_files/union.slt‎

Lines changed: 21 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -513,24 +513,27 @@ physical_plan
513513
01)CoalescePartitionsExec: fetch=3
514514
02)--UnionExec
515515
03)----ProjectionExec: expr=[count(Int64(1))@0 as cnt]
516-
04)------AggregateExec: mode=Final, gby=[], aggr=[count(Int64(1))]
517-
05)--------CoalescePartitionsExec
518-
06)----------AggregateExec: mode=Partial, gby=[], aggr=[count(Int64(1))]
519-
07)------------ProjectionExec: expr=[]
520-
08)--------------AggregateExec: mode=FinalPartitioned, gby=[c1@0 as c1], aggr=[]
521-
09)----------------CoalesceBatchesExec: target_batch_size=2
522-
10)------------------RepartitionExec: partitioning=Hash([c1@0], 4), input_partitions=4
523-
11)--------------------AggregateExec: mode=Partial, gby=[c1@0 as c1], aggr=[]
524-
12)----------------------CoalesceBatchesExec: target_batch_size=2
525-
13)------------------------FilterExec: c13@1 != C2GT5KVyOPZpgKVl110TyZO0NcJ434, projection=[c1@0]
526-
14)--------------------------RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1
527-
15)----------------------------DataSourceExec: file_groups={1 group: [[WORKSPACE_ROOT/testing/data/csv/aggregate_test_100.csv]]}, projection=[c1, c13], file_type=csv, has_header=true
528-
16)----ProjectionExec: expr=[1 as cnt]
529-
17)------PlaceholderRowExec
530-
18)----ProjectionExec: expr=[lead(b.c1,Int64(1)) ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING@1 as cnt]
531-
19)------BoundedWindowAggExec: wdw=[lead(b.c1,Int64(1)) ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING: Ok(Field { name: "lead(b.c1,Int64(1)) ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING", data_type: Int64, nullable: true, dict_id: 0, dict_is_ordered: false, metadata: {} }), frame: WindowFrame { units: Rows, start_bound: Preceding(UInt64(NULL)), end_bound: Following(UInt64(NULL)), is_causal: false }], mode=[Sorted]
532-
20)--------ProjectionExec: expr=[1 as c1]
533-
21)----------PlaceholderRowExec
516+
04)------GlobalLimitExec: skip=0, fetch=3
517+
05)--------AggregateExec: mode=Final, gby=[], aggr=[count(Int64(1))]
518+
06)----------CoalescePartitionsExec
519+
07)------------AggregateExec: mode=Partial, gby=[], aggr=[count(Int64(1))]
520+
08)--------------ProjectionExec: expr=[]
521+
09)----------------AggregateExec: mode=FinalPartitioned, gby=[c1@0 as c1], aggr=[]
522+
10)------------------CoalesceBatchesExec: target_batch_size=2
523+
11)--------------------RepartitionExec: partitioning=Hash([c1@0], 4), input_partitions=4
524+
12)----------------------AggregateExec: mode=Partial, gby=[c1@0 as c1], aggr=[]
525+
13)------------------------CoalesceBatchesExec: target_batch_size=2
526+
14)--------------------------FilterExec: c13@1 != C2GT5KVyOPZpgKVl110TyZO0NcJ434, projection=[c1@0]
527+
15)----------------------------RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1
528+
16)------------------------------DataSourceExec: file_groups={1 group: [[WORKSPACE_ROOT/testing/data/csv/aggregate_test_100.csv]]}, projection=[c1, c13], file_type=csv, has_header=true
529+
17)----ProjectionExec: expr=[1 as cnt]
530+
18)------GlobalLimitExec: skip=0, fetch=3
531+
19)--------PlaceholderRowExec
532+
20)----ProjectionExec: expr=[lead(b.c1,Int64(1)) ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING@1 as cnt]
533+
21)------GlobalLimitExec: skip=0, fetch=3
534+
22)--------BoundedWindowAggExec: wdw=[lead(b.c1,Int64(1)) ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING: Ok(Field { name: "lead(b.c1,Int64(1)) ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING", data_type: Int64, nullable: true, dict_id: 0, dict_is_ordered: false, metadata: {} }), frame: WindowFrame { units: Rows, start_bound: Preceding(UInt64(NULL)), end_bound: Following(UInt64(NULL)), is_causal: false }], mode=[Sorted]
535+
23)----------ProjectionExec: expr=[1 as c1]
536+
24)------------PlaceholderRowExec
534537

535538

536539
########

0 commit comments

Comments
 (0)