Skip to content

Commit bffdca1

Browse files
robert3005claude
andauthored
Replace filter-and-scatter RowFn fallback with filtered valid-row execution (#9645)
## Summary - Tracking issue: #9130 Instead of performing a gather/execute/scatter add a filtered execute method that avoids majority of intermediate state --------- Signed-off-by: Claude <[email protected]> Signed-off-by: Robert Kruszewski <[email protected]> Co-authored-by: Claude <[email protected]>
1 parent 402fd1d commit bffdca1

20 files changed

Lines changed: 652 additions & 253 deletions

File tree

‎vortex-array/src/scalar_fn/unstable/row/batch/execute/dense.rs‎

Lines changed: 12 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -33,7 +33,6 @@ impl RowFnExecutionArgs {
3333
/// recompute the error.
3434
pub(super) fn execute_dense_with_retry(
3535
&self,
36-
kernel: impl Fn(BorrowedRowFnArgs<'_>, &mut ExecutionCtx) -> VortexResult<ArrayRef>,
3736
execute_dense_attempt: impl FnOnce(
3837
BorrowedRowFnArgs<'_>,
3938
&mut ExecutionCtx,
@@ -43,6 +42,11 @@ impl RowFnExecutionArgs {
4342
MaskValuesRef,
4443
&mut ExecutionCtx,
4544
) -> VortexResult<Option<ArrayRef>>,
45+
execute_filtered_rows: impl FnOnce(
46+
BorrowedRowFnArgs<'_>,
47+
MaskValuesRef,
48+
&mut ExecutionCtx,
49+
) -> VortexResult<ArrayRef>,
4650
ctx: &mut ExecutionCtx,
4751
) -> VortexResult<ArrayRef> {
4852
let attempt =
@@ -51,20 +55,24 @@ impl RowFnExecutionArgs {
5155
match attempt {
5256
DenseAttempt::Values(values) => self.finalize_dense_output(values, ctx),
5357
DenseAttempt::DeferredError(error) => {
54-
self.resolve_deferred_error(error, kernel, try_valid_rows, ctx)
58+
self.resolve_deferred_error(error, try_valid_rows, execute_filtered_rows, ctx)
5559
}
5660
}
5761
}
5862

5963
fn resolve_deferred_error(
6064
&self,
6165
deferred_error: VortexError,
62-
kernel: impl Fn(BorrowedRowFnArgs<'_>, &mut ExecutionCtx) -> VortexResult<ArrayRef>,
6366
try_valid_rows: impl FnOnce(
6467
BorrowedRowFnArgs<'_>,
6568
MaskValuesRef,
6669
&mut ExecutionCtx,
6770
) -> VortexResult<Option<ArrayRef>>,
71+
execute_filtered_rows: impl FnOnce(
72+
BorrowedRowFnArgs<'_>,
73+
MaskValuesRef,
74+
&mut ExecutionCtx,
75+
) -> VortexResult<ArrayRef>,
6876
ctx: &mut ExecutionCtx,
6977
) -> VortexResult<ArrayRef> {
7078
let valid_rows = match self.validity.execute_mask(self.row_count, ctx)? {
@@ -85,7 +93,7 @@ impl RowFnExecutionArgs {
8593
return Ok(result);
8694
}
8795

88-
self.filter_and_scatter(kernel, &valid_rows, ctx)
96+
self.execute_filtered(execute_filtered_rows, &valid_rows, ctx)
8997
}
9098

9199
fn finalize_dense_output(

‎vortex-array/src/scalar_fn/unstable/row/batch/execute/filter_scatter.rs‎

Lines changed: 0 additions & 95 deletions
This file was deleted.
Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
// SPDX-License-Identifier: Apache-2.0
2+
// SPDX-FileCopyrightText: Copyright the Vortex contributors
3+
4+
//! Filtered execution for row kernels that cannot operate on the original partially valid inputs.
5+
//!
6+
//! Direct skip-invalid execution retains the original input columns: it decodes every column,
7+
//! initializes a full-length output, and visits only valid rows. Some input representations cannot
8+
//! decode unspecified payloads behind nulls, so there is no safe row loop to enter over the
9+
//! original columns.
10+
//!
11+
//! This path filters every input to the valid row domain before decoding it. The kernel then
12+
//! iterates only the valid rows: it reads consecutive rows from the compact, all-valid inputs and
13+
//! writes each result directly at its original row index into a full-length output. Skipped
14+
//! positions hold placeholders that batch execution masks, exactly like direct skip-invalid
15+
//! execution, so the output never needs a columnar scatter.
16+
//!
17+
//! Filtering nested or compressed inputs can materialize their selected representation, so batch
18+
//! execution tries direct skip-invalid execution first and filters only when a required input
19+
//! capability is unavailable. Calling the general scalar-extraction API once per valid row is not
20+
//! equivalent because it repeats array execution and scalar construction inside the row loop.
21+
22+
use smallvec::SmallVec;
23+
use vortex_error::VortexResult;
24+
use vortex_mask::Mask;
25+
use vortex_mask::MaskValuesRef;
26+
27+
use super::super::RowFnExecutionArgs;
28+
use super::super::args::BorrowedRowFnArgs;
29+
use crate::ArrayRef;
30+
use crate::ExecutionCtx;
31+
use crate::IntoArray;
32+
use crate::builtins::ArrayBuiltins;
33+
34+
impl RowFnExecutionArgs {
35+
/// Filter the batch to valid rows, then execute the kernel into the original row domain.
36+
pub(super) fn execute_filtered(
37+
&self,
38+
execute_filtered_rows: impl FnOnce(
39+
BorrowedRowFnArgs<'_>,
40+
MaskValuesRef,
41+
&mut ExecutionCtx,
42+
) -> VortexResult<ArrayRef>,
43+
valid: &MaskValuesRef,
44+
ctx: &mut ExecutionCtx,
45+
) -> VortexResult<ArrayRef> {
46+
let filtered_len = valid.true_count();
47+
let filter_mask = Mask::Values(MaskValuesRef::clone(valid));
48+
49+
let filtered_inputs: SmallVec<[ArrayRef; 4]> = self
50+
.inputs
51+
.iter()
52+
.map(|input| input.filter(filter_mask.clone()))
53+
.collect::<VortexResult<_>>()?;
54+
55+
let filtered_args = self.execution_args(&filtered_inputs, filtered_len);
56+
let values = execute_filtered_rows(filtered_args, MaskValuesRef::clone(valid), ctx)?;
57+
let values = self.validate_kernel_output(values, self.row_count, ctx)?;
58+
59+
let mask = valid.as_ref().into_array();
60+
self.finalize_output(values.mask(mask)?, self.row_count)
61+
}
62+
}

‎vortex-array/src/scalar_fn/unstable/row/batch/execute/mod.rs‎

Lines changed: 16 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -21,7 +21,7 @@ use crate::validity::Validity;
2121

2222
mod constant;
2323
mod dense;
24-
mod filter_scatter;
24+
mod filtered;
2525
mod valid_only;
2626

2727
mod output;
@@ -31,7 +31,8 @@ impl RowFnExecutionArgs {
3131
/// Apply constant folding and null handling around `kernel`.
3232
///
3333
/// For a partially valid batch, `try_valid_rows` can avoid filtering. `Ok(None)` filters the
34-
/// valid rows and scatters the output back. Every result is checked against the planned shape
34+
/// inputs to the valid rows and `execute_filtered_rows` runs the kernel over them while
35+
/// writing into the original row domain. Every result is checked against the planned shape
3536
/// and dtype.
3637
pub(crate) fn execute(
3738
&self,
@@ -45,6 +46,11 @@ impl RowFnExecutionArgs {
4546
MaskValuesRef,
4647
&mut ExecutionCtx,
4748
) -> VortexResult<Option<ArrayRef>>,
49+
execute_filtered_rows: impl FnOnce(
50+
BorrowedRowFnArgs<'_>,
51+
MaskValuesRef,
52+
&mut ExecutionCtx,
53+
) -> VortexResult<ArrayRef>,
4854
ctx: &mut ExecutionCtx,
4955
) -> VortexResult<ArrayRef> {
5056
// Strictness: an all-null batch has no observable row work. Keep the literal-constant
@@ -77,10 +83,15 @@ impl RowFnExecutionArgs {
7783

7884
match self.plan.policy() {
7985
RowPolicy::Dense => self.execute_dense(kernel, ctx),
80-
RowPolicy::DenseWithRetry => {
81-
self.execute_dense_with_retry(kernel, execute_dense_attempt, try_valid_rows, ctx)
86+
RowPolicy::DenseWithRetry => self.execute_dense_with_retry(
87+
execute_dense_attempt,
88+
try_valid_rows,
89+
execute_filtered_rows,
90+
ctx,
91+
),
92+
RowPolicy::ValidOnly => {
93+
self.execute_valid_only(kernel, try_valid_rows, execute_filtered_rows, ctx)
8294
}
83-
RowPolicy::ValidOnly => self.execute_valid_only(kernel, try_valid_rows, ctx),
8495
}
8596
}
8697
}

‎vortex-array/src/scalar_fn/unstable/row/batch/execute/valid_only.rs‎

Lines changed: 7 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -13,7 +13,7 @@ use crate::IntoArray;
1313
use crate::builtins::ArrayBuiltins;
1414

1515
impl RowFnExecutionArgs {
16-
/// Resolve validity and try direct valid-row execution before filter-and-scatter.
16+
/// Resolve validity and try direct valid-row execution before filtered execution.
1717
pub(super) fn execute_valid_only(
1818
&self,
1919
kernel: impl Fn(BorrowedRowFnArgs<'_>, &mut ExecutionCtx) -> VortexResult<ArrayRef>,
@@ -22,6 +22,11 @@ impl RowFnExecutionArgs {
2222
MaskValuesRef,
2323
&mut ExecutionCtx,
2424
) -> VortexResult<Option<ArrayRef>>,
25+
execute_filtered_rows: impl FnOnce(
26+
BorrowedRowFnArgs<'_>,
27+
MaskValuesRef,
28+
&mut ExecutionCtx,
29+
) -> VortexResult<ArrayRef>,
2530
ctx: &mut ExecutionCtx,
2631
) -> VortexResult<ArrayRef> {
2732
let validity = self.validity.clone().execute_mask(self.row_count, ctx)?;
@@ -42,7 +47,7 @@ impl RowFnExecutionArgs {
4247
return Ok(result);
4348
}
4449

45-
self.filter_and_scatter(kernel, &valid_rows, ctx)
50+
self.execute_filtered(execute_filtered_rows, &valid_rows, ctx)
4651
}
4752

4853
/// Try execution against the original inputs, then mask a returned full-length result.

‎vortex-array/src/scalar_fn/unstable/row/batch/tests.rs‎

Lines changed: 13 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -63,13 +63,13 @@ impl DeferredAdd {
6363
struct ValidOnlyIdentity;
6464

6565
#[derive(Clone)]
66-
struct FilterAndScatterIdentity;
66+
struct FilteredIdentity;
6767

6868
#[derive(Clone)]
6969
struct DenseRetryIncrement;
7070

7171
#[derive(Clone)]
72-
struct FilterAndScatterRepeat;
72+
struct FilteredRepeat;
7373

7474
#[derive(Clone)]
7575
struct InvalidKernelOutput;
@@ -245,7 +245,8 @@ impl OutputElement for NullProducingI64 {
245245
struct I64Sink(BufferMut<i64>);
246246

247247
// SAFETY: every row is initialized by `BufferMut::zeroed`, and the sink exposes exactly that
248-
// initialized slice. The `()` write token therefore proves no additional invariant.
248+
// initialized slice. The `()` write token therefore proves no additional invariant, and the
249+
// default skipped-row initializer only rewrites the zeroes.
249250
unsafe impl OutputSink for I64Sink {
250251
type Params = ();
251252
type Rows<'a> = &'a mut [i64];
@@ -365,14 +366,14 @@ impl RowFn for ValidOnlyIdentity {
365366
}
366367
}
367368

368-
impl RowFn for FilterAndScatterIdentity {
369+
impl RowFn for FilteredIdentity {
369370
type Options = EmptyOptions;
370371

371372
const ARG_NAMES: &'static [&'static str] = &["value"];
372373
const INFALLIBLE: bool = false;
373374

374375
fn id(&self) -> ScalarFnId {
375-
static ID: CachedId = CachedId::new("test.filter_and_scatter_identity");
376+
static ID: CachedId = CachedId::new("test.filtered_identity");
376377
*ID
377378
}
378379

@@ -416,14 +417,14 @@ impl RowFn for DenseRetryIncrement {
416417
}
417418
}
418419

419-
impl RowFn for FilterAndScatterRepeat {
420+
impl RowFn for FilteredRepeat {
420421
type Options = usize;
421422

422423
const ARG_NAMES: &'static [&'static str] = &["value"];
423424
const INFALLIBLE: bool = true;
424425

425426
fn id(&self) -> ScalarFnId {
426-
static ID: CachedId = CachedId::new("test.filter_and_scatter_repeat");
427+
static ID: CachedId = CachedId::new("test.filtered_repeat");
427428
*ID
428429
}
429430

@@ -436,7 +437,7 @@ impl RowFn for FilterAndScatterRepeat {
436437
vortex_ensure!(
437438
u32::try_from(*width).is_ok(),
438439
InvalidArgument:
439-
"test.filter_and_scatter_repeat width must fit in u32, got {width}",
440+
"test.filtered_repeat width must fit in u32, got {width}",
440441
);
441442

442443
visitor
@@ -789,14 +790,14 @@ fn test_valid_only_bool_output_skips_invalid_rows() -> VortexResult<()> {
789790
}
790791

791792
#[test]
792-
fn test_filter_and_scatter_skips_invalid_decode_payloads() -> VortexResult<()> {
793+
fn test_filtered_execution_skips_invalid_decode_payloads() -> VortexResult<()> {
793794
let validity = Validity::from_iter([false, true, false, true]);
794795
let input =
795796
PrimitiveArray::new(vec![i64::MIN, 10, i64::MIN, 30], validity.clone()).into_array();
796797
let args = VecExecutionArgs::new(vec![input], 4);
797798
let mut ctx = array_session().create_execution_ctx();
798799

799-
let actual = execute_rows(&FilterAndScatterIdentity, &EmptyOptions, &args, &mut ctx)?;
800+
let actual = execute_rows(&FilteredIdentity, &EmptyOptions, &args, &mut ctx)?;
800801
let expected = PrimitiveArray::new(vec![0_i64, 10, 0, 30], validity).into_array();
801802

802803
assert_arrays_eq!(&actual, &expected, &mut ctx);
@@ -806,7 +807,7 @@ fn test_filter_and_scatter_skips_invalid_decode_payloads() -> VortexResult<()> {
806807
#[rstest]
807808
#[case::width_two(2, vec![0_i64, 0, 7, 7])]
808809
#[case::zero_width(0, vec![])]
809-
fn test_filter_and_scatter_preserves_runtime_sink_params(
810+
fn test_filtered_execution_preserves_runtime_sink_params(
810811
#[case] width: usize,
811812
#[case] expected_elements: Vec<i64>,
812813
) -> VortexResult<()> {
@@ -815,7 +816,7 @@ fn test_filter_and_scatter_preserves_runtime_sink_params(
815816
let args = VecExecutionArgs::new(vec![input], 2);
816817
let mut ctx = array_session().create_execution_ctx();
817818

818-
let actual = execute_rows(&FilterAndScatterRepeat, &width, &args, &mut ctx)?;
819+
let actual = execute_rows(&FilteredRepeat, &width, &args, &mut ctx)?;
819820
let expected = FixedSizeListArray::new(
820821
PrimitiveArray::from_iter(expected_elements).into_array(),
821822
u32::try_from(width)

0 commit comments

Comments
 (0)