Skip to content

Commit 6520315

Browse files
ajegougabotechs
andauthored
fix(topk): call attempt_early_completion when filter rejects entire batch (apache#22852)
## Which issue does this PR close? - Closes apache#22849 - A related cross-partition starvation case is tracked separately in apache#22874 and addressed by an upcoming follow-up PR — see [discussion](apache#22852 (comment)) for details ## Rationale for this change `TopK::insert_batch` short-circuits when the heap's dynamic filter rejects every row in a batch: ```rust if !filter.has_true() { // nothing to filter, so no need to update return Ok(()); } ``` The early-exit check `attempt_early_completion(&batch)` lives later in the same function, gated on `replacements > 0`. So a batch that the filter rejects entirely bypasses the check. The heap's dynamic filter is derived from the heap's worst row (via `update_filter`). A batch whose rows all come from a strictly worse sort prefix is exactly the batch the filter rejects entirely — i.e. the very signal `attempt_early_completion` is designed to detect ("the next batch is past the heap's boundary, we can stop") is what causes the function to short-circuit *before* the check runs. This is a feature-interaction regression between two PRs that were both correct in isolation. The `attempt_early_completion` mechanism was added by apache#15563 (closing apache#15529). At the time, there was no heap-derived dynamic filter on TopK, so the only sensible call site was right after a successful heap insertion. Two months later, apache#15770 added the dynamic-filter pushdown for TopK sorts, introducing the `!filter.has_true()` short-circuit. The two features address different problems and the new short-circuit didn't connect to the existing prefix-completion check — which is how this gap opened up. **Consequence**: on a TopK over an input ordered on the sort prefix, `finished = true` is never set once the heap stabilizes. Since `finished` is the signal `SortExec` uses to stop pulling from its input (via `Poll::Ready(None)` from the TopK stream, which cascades into dropping the source stream), the source keeps being polled long past the point where no further row can improve the heap. The LIMIT optimization effectively degrades to "heap saves memory but reads everything"; sources with cancellable streams (e.g. networked sources) never receive the cancellation signal. ## What changes are included in this PR? Single behavioral change in `datafusion/physical-plan/src/topk/mod.rs`: call `attempt_early_completion(&batch)` immediately before the `return Ok(())` in the `!filter.has_true()` branch. Why this scope, not a broader restructuring: - The existing `attempt_early_completion` call inside `if replacements > 0` is load-bearing for a related case: a batch containing a mix of "still valuable" rows and "past the boundary" rows. The existing `test_try_finish_marks_finished_with_prefix` test covers this case — Batch 2 with `a=[2,3], b=[10,20]` against a heap where `heap.max.a = 2`; the `(2, 10)` row must be inserted before the check on the `(3, 20)` last row triggers. Moving the call earlier would skip the insertion of valuable rows and break that test. - The bug is specifically that the *short-circuit* path doesn't call the check. The fix targets exactly that path. - A related but separate gap is not addressed here: when `filter.has_true() == true` but `replacements == 0` (the filter accepts some rows but `find_new_topk_items` ends up inserting none of them), the existing call inside `if replacements > 0` is also skipped. This requires a divergence between the heap's filter predicate and the row-byte comparison used inside `find_new_topk_items`, which shouldn't normally happen (the filter is derived from the heap's worst row using the same comparator). A deterministic synthetic repro would likely require concurrent heap updates from sibling partitions or boundary-value edge cases (NaN/NULL semantics, type coercion). Happy to send a follow-up if reviewers want it covered; the workload that motivated this fix was the filter-rejection case empirically. ## Are these changes tested? Yes. Added a regression test `test_try_finish_fires_when_filter_rejects_entire_batch`. The assertion target is `topk.finished` — the flag that signals "stop pulling from the source" to upstream consumers (read by `TopKExec::poll_next` to emit `Poll::Ready(None)`). Asserting that the flag transitions on the fully-filter-rejected batch is equivalent to asserting that the source-stopping mechanism activates. - Builds a TopK over a `(a, b)` sort with prefix `a`, k=3. - Inserts a batch that fills the heap with rows from `a ∈ {1, 2}`; `update_filter` tightens the filter to `a < 2 OR (a = 2 AND b < 30)`. - Inserts a second batch with all rows at `a = 3` — filter rejects every row. - Without the fix: `insert_batch` short-circuits, `topk.finished` stays `false`. Test fails. - With the fix: `attempt_early_completion` fires (last-row prefix `a = 3` > heap.max prefix `a = 2`), `topk.finished` becomes `true`. Test passes. The test also asserts the emitted top-K is unchanged from after batch 1, confirming no candidate row was incorrectly excluded by the early bail. All 28 existing `topk::` tests continue to pass (including `test_try_finish_marks_finished_with_prefix`, which exercises the mixed-prefix case). ## Are there any user-facing changes? No public API or output changes. The fix only changes when TopK marks itself `finished = true` — specifically, it now fires `attempt_early_completion` for batches that are entirely rejected by the heap's dynamic filter, where previously it would silently skip the check. Output of TopK is unchanged; only the early-exit behavior improves. --------- Co-authored-by: Gabriel <[email protected]>
1 parent d428760 commit 6520315

1 file changed

Lines changed: 82 additions & 19 deletions

File tree

  • datafusion/physical-plan/src/topk

‎datafusion/physical-plan/src/topk/mod.rs‎

Lines changed: 82 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -255,7 +255,9 @@ impl TopK {
255255
let array = filtered.into_array(num_rows)?;
256256
let mut filter = array.as_boolean().clone();
257257
if !filter.has_true() {
258-
// nothing to filter, so no need to update
258+
// The heap is unchanged, but a fully rejected batch can still prove
259+
// that the shared sort prefix has passed the heap boundary.
260+
self.attempt_early_completion(&batch)?;
259261
return Ok(());
260262
}
261263
// only update the keys / rows if the filter does not match all rows
@@ -1099,20 +1101,15 @@ mod tests {
10991101
assert_eq!(record_batch_store.batches_size, 0);
11001102
}
11011103

1102-
/// This test validates that the `try_finish` method marks the TopK operator as finished
1103-
/// when the prefix (on column "a") of the last row in the current batch is strictly greater
1104-
/// than the max top‑k row.
1105-
/// The full sort expression is defined on both columns ("a", "b"), but the input ordering is only on "a".
1106-
#[tokio::test]
1107-
async fn test_try_finish_marks_finished_with_prefix() -> Result<()> {
1108-
// Create a schema with two columns.
1104+
/// Builds an `(a Int32, b Float64)` schema and a `TopK` with full sort
1105+
/// `(a ASC, b ASC)`, input prefix `[a]`, `k = 3`, `batch_size = 2`. Used by
1106+
/// the prefix-completion tests below to keep their per-scenario logic in focus.
1107+
fn build_ab_prefix_topk() -> Result<(Arc<Schema>, TopK)> {
11091108
let schema = Arc::new(Schema::new(vec![
11101109
Field::new("a", DataType::Int32, false),
11111110
Field::new("b", DataType::Float64, false),
11121111
]));
11131112

1114-
// Create sort expressions.
1115-
// Full sort: first by "a", then by "b".
11161113
let sort_expr_a = PhysicalSortExpr {
11171114
expr: col("a", schema.as_ref())?,
11181115
options: SortOptions::default(),
@@ -1122,28 +1119,33 @@ mod tests {
11221119
options: SortOptions::default(),
11231120
};
11241121

1125-
// Input ordering uses only column "a" (a prefix of the full sort).
1122+
// Input ordering uses only column "a" (a prefix of the full sort on (a, b)).
11261123
let prefix = vec![sort_expr_a.clone()];
11271124
let full_expr = LexOrdering::from([sort_expr_a, sort_expr_b]);
11281125

1129-
// Create a dummy runtime environment and metrics.
1130-
let runtime = Arc::new(RuntimeEnv::default());
1131-
let metrics = ExecutionPlanMetricsSet::new();
1132-
1133-
// Create a TopK instance with k = 3 and batch_size = 2.
1134-
let mut topk = TopK::try_new(
1126+
let topk = TopK::try_new(
11351127
0,
11361128
Arc::clone(&schema),
11371129
prefix,
11381130
full_expr,
11391131
3,
11401132
2,
1141-
runtime,
1142-
&metrics,
1133+
Arc::new(RuntimeEnv::default()),
1134+
&ExecutionPlanMetricsSet::new(),
11431135
Arc::new(RwLock::new(TopKDynamicFilters::new(Arc::new(
11441136
DynamicFilterPhysicalExpr::new(vec![], lit(true)),
11451137
)))),
11461138
)?;
1139+
Ok((schema, topk))
1140+
}
1141+
1142+
/// This test validates that the `try_finish` method marks the TopK operator as finished
1143+
/// when the prefix (on column "a") of the last row in the current batch is strictly greater
1144+
/// than the max top‑k row.
1145+
/// The full sort expression is defined on both columns ("a", "b"), but the input ordering is only on "a".
1146+
#[tokio::test]
1147+
async fn test_try_finish_marks_finished_with_prefix() -> Result<()> {
1148+
let (schema, mut topk) = build_ab_prefix_topk()?;
11471149

11481150
// Create the first batch with two columns:
11491151
// Column "a": [1, 1, 2], Column "b": [20.0, 15.0, 30.0].
@@ -1196,6 +1198,67 @@ mod tests {
11961198
Ok(())
11971199
}
11981200

1201+
/// Regression test for #22849: a batch whose rows are entirely rejected by the
1202+
/// heap's dynamic filter must still trigger `attempt_early_completion` when its
1203+
/// last row's prefix is worse than the heap's worst.
1204+
///
1205+
/// Before the fix, the `!filter.has_true()` short-circuit returned without calling
1206+
/// `attempt_early_completion`. Because the heap's filter is itself derived from the
1207+
/// heap's worst row, a batch from a strictly-worse prefix is exactly the case the
1208+
/// filter rejects entirely — i.e. the very signal the early-exit was designed to
1209+
/// detect was being silently dropped.
1210+
#[tokio::test]
1211+
async fn test_try_finish_fires_when_filter_rejects_entire_batch() -> Result<()> {
1212+
let (schema, mut topk) = build_ab_prefix_topk()?;
1213+
1214+
// Batch 1 fills the heap with (1, 20.0), (1, 15.0), (2, 30.0).
1215+
// heap.max becomes (a=2, b=30.0); update_filter tightens the heap filter to
1216+
// a < 2 OR (a = 2 AND b < 30.0).
1217+
let array_a1: ArrayRef =
1218+
Arc::new(Int32Array::from(vec![Some(1), Some(1), Some(2)]));
1219+
let array_b1: ArrayRef = Arc::new(Float64Array::from(vec![20.0, 15.0, 30.0]));
1220+
let batch1 = RecordBatch::try_new(Arc::clone(&schema), vec![array_a1, array_b1])?;
1221+
topk.insert_batch(batch1)?;
1222+
assert!(
1223+
!topk.finished,
1224+
"Expected 'finished' to be false after batch 1 \
1225+
(last row prefix a=2 equals heap.max prefix a=2, not strictly greater)."
1226+
);
1227+
1228+
// Batch 2: every row has a=3, so the heap's filter (a < 2 OR (a = 2 AND b < 30))
1229+
// rejects every row. Before the fix, `insert_batch` would short-circuit on
1230+
// `!filter.has_true()` and return without checking the prefix; `finished`
1231+
// would stay false even though no future batch could improve the heap.
1232+
let array_a2: ArrayRef = Arc::new(Int32Array::from(vec![Some(3), Some(3)]));
1233+
let array_b2: ArrayRef = Arc::new(Float64Array::from(vec![10.0, 20.0]));
1234+
let batch2 = RecordBatch::try_new(Arc::clone(&schema), vec![array_a2, array_b2])?;
1235+
topk.insert_batch(batch2)?;
1236+
assert!(
1237+
topk.finished,
1238+
"Expected 'finished' to be true after batch 2 \
1239+
(filter rejected every row, but the batch's last row prefix a=3 \
1240+
is strictly greater than heap.max prefix a=2)."
1241+
);
1242+
1243+
// The emitted top-k is unchanged from after batch 1 since none of batch 2's
1244+
// rows could improve the heap.
1245+
let results: Vec<_> = topk.emit()?.try_collect().await?;
1246+
assert_batches_eq!(
1247+
&[
1248+
"+---+------+",
1249+
"| a | b |",
1250+
"+---+------+",
1251+
"| 1 | 15.0 |",
1252+
"| 1 | 20.0 |",
1253+
"| 2 | 30.0 |",
1254+
"+---+------+",
1255+
],
1256+
&results
1257+
);
1258+
1259+
Ok(())
1260+
}
1261+
11991262
/// This test verifies that the dynamic filter is marked as complete after TopK processing finishes.
12001263
#[tokio::test]
12011264
async fn test_topk_marks_filter_complete() -> Result<()> {

0 commit comments

Comments
 (0)