Skip to content

Commit b6c09be

Browse files
committed
Add filter-and-scatter RowFn execution
Signed-off-by: Connor Tsui <[email protected]>
1 parent 46a8d39 commit b6c09be

10 files changed

Lines changed: 171 additions & 42 deletions

File tree

Lines changed: 100 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,100 @@
1+
// SPDX-License-Identifier: Apache-2.0
2+
// SPDX-FileCopyrightText: Copyright the Vortex contributors
3+
4+
//! Fallback execution for row kernels that cannot operate directly on partially valid inputs.
5+
//!
6+
//! This path filters every input from the original row count to the valid row count. It runs the
7+
//! dense kernel on those filtered rows, then scatters the output back to the original row count.
8+
9+
use smallvec::SmallVec;
10+
use vortex_error::VortexResult;
11+
use vortex_error::vortex_bail;
12+
use vortex_mask::AllOr;
13+
use vortex_mask::Mask;
14+
15+
use super::super::RowFnExecutionArgs;
16+
use super::super::args::BorrowedRowFnArgs;
17+
use crate::ArrayRef;
18+
use crate::ExecutionCtx;
19+
use crate::IntoArray;
20+
use crate::arrays::BoolArray;
21+
use crate::arrays::MaskedArray;
22+
use crate::arrays::PrimitiveArray;
23+
use crate::builtins::ArrayBuiltins;
24+
use crate::dtype::Nullability;
25+
use crate::validity::Validity;
26+
27+
impl RowFnExecutionArgs {
28+
/// Filter the original batch to valid rows, run the dense kernel, then restore its row count.
29+
pub(super) fn filter_and_scatter(
30+
&self,
31+
kernel: impl Fn(BorrowedRowFnArgs<'_>, &mut ExecutionCtx) -> VortexResult<ArrayRef>,
32+
original_validity: &Mask,
33+
ctx: &mut ExecutionCtx,
34+
) -> VortexResult<ArrayRef> {
35+
let original_len = original_validity.len();
36+
let filtered_len = original_validity.true_count();
37+
38+
let filtered_inputs: SmallVec<[ArrayRef; 4]> = self
39+
.inputs
40+
.iter()
41+
.map(|input| input.filter(original_validity.clone()))
42+
.collect::<VortexResult<_>>()?;
43+
44+
let filtered_args = self.execution_args(&filtered_inputs, filtered_len);
45+
let filtered = kernel(filtered_args, ctx)?;
46+
47+
let filtered = self.validate_kernel_output(filtered, filtered_len, ctx)?;
48+
49+
let output = Self::scatter_to_original_rows(filtered, original_validity)?;
50+
51+
self.finalize_output(output, original_len)
52+
}
53+
54+
/// Scatter `filtered` back to the rows selected by `original_validity`.
55+
///
56+
/// The result has the original length and is null at each invalid position.
57+
fn scatter_to_original_rows(
58+
filtered: ArrayRef,
59+
original_validity: &Mask,
60+
) -> VortexResult<ArrayRef> {
61+
let original_len = original_validity.len();
62+
63+
let AllOr::Some(valid_slices) = original_validity.slices() else {
64+
// The caller handles the all-true and all-false masks.
65+
vortex_bail!(
66+
"filter-and-scatter requires valid and invalid rows, got an all-valid or all-invalid mask"
67+
);
68+
};
69+
70+
// Map each valid row to its position in `filtered`. Invalid rows use index zero because
71+
// their gathered values are masked below.
72+
let mut take_indices = vec![0u64; original_len];
73+
74+
let valid_rows = valid_slices.iter().flat_map(|&(start, end)| start..end);
75+
for (filtered_idx, original_idx) in valid_rows.enumerate() {
76+
take_indices[original_idx] = u64::try_from(filtered_idx)?;
77+
}
78+
79+
let take_indices = PrimitiveArray::new(take_indices, Validity::NonNullable).into_array();
80+
81+
let expanded = filtered.take(take_indices)?;
82+
83+
// A nullable gathered array cannot be wrapped because a `Masked` child must be all valid.
84+
// The general masking pass unions its nulls with the batch validity instead.
85+
if expanded.dtype().is_nullable() {
86+
let validity_array =
87+
BoolArray::new(original_validity.to_bit_buffer(), Validity::NonNullable)
88+
.into_array();
89+
90+
return expanded.mask(validity_array);
91+
}
92+
93+
// The gathered values are all valid, so attaching validity is sufficient.
94+
Ok(MaskedArray::try_new(
95+
expanded,
96+
Validity::from_mask(original_validity.clone(), Nullability::Nullable),
97+
)?
98+
.into_array())
99+
}
100+
}

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

Lines changed: 4 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -20,6 +20,7 @@ use crate::validity::Validity;
2020

2121
mod constant;
2222
mod dense;
23+
mod filter_scatter;
2324
mod valid_only;
2425

2526
mod output;
@@ -29,8 +30,9 @@ pub(crate) use output::finalize_kernel_output;
2930
impl RowFnExecutionArgs {
3031
/// Apply constant folding and null handling around `kernel`.
3132
///
32-
/// For a partially valid batch, `try_valid_rows` executes only valid rows over the original
33-
/// inputs. Every result is checked against the planned shape and dtype.
33+
/// 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
35+
/// and dtype.
3436
pub(crate) fn execute(
3537
&self,
3638
kernel: impl Fn(BorrowedRowFnArgs<'_>, &mut ExecutionCtx) -> VortexResult<ArrayRef>,

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

Lines changed: 24 additions & 30 deletions
Original file line numberDiff line numberDiff line change
@@ -2,7 +2,6 @@
22
// SPDX-FileCopyrightText: Copyright the Vortex contributors
33

44
use vortex_error::VortexResult;
5-
use vortex_error::vortex_panic;
65
use vortex_mask::Mask;
76

87
use super::super::RowFnExecutionArgs;
@@ -24,12 +23,7 @@ enum ResolvedValidity {
2423
}
2524

2625
impl RowFnExecutionArgs {
27-
/// Resolve validity, then execute valid rows over the original inputs.
28-
///
29-
/// # Panics
30-
///
31-
/// Panics if the concrete row signature cannot use direct valid-row execution. Inputs must
32-
/// support null-tolerant decoding, and output sinks must initialize skipped rows.
26+
/// Resolve validity and try direct valid-row execution before filter-and-scatter.
3327
pub(super) fn execute_valid_only(
3428
&self,
3529
kernel: impl Fn(BorrowedRowFnArgs<'_>, &mut ExecutionCtx) -> VortexResult<ArrayRef>,
@@ -40,19 +34,18 @@ impl RowFnExecutionArgs {
4034
) -> VortexResult<Option<ArrayRef>>,
4135
ctx: &mut ExecutionCtx,
4236
) -> VortexResult<ArrayRef> {
43-
let valid = match self.resolve_validity(&kernel, ctx)? {
37+
let original_validity = match self.resolve_validity(&kernel, ctx)? {
4438
ResolvedValidity::Output(output) => return Ok(output),
45-
ResolvedValidity::PartiallyValid(valid) => valid,
39+
ResolvedValidity::PartiallyValid(original_validity) => original_validity,
4640
};
4741

48-
if let Some(result) = self.try_execute_valid_rows(try_valid_rows, &valid, ctx)? {
49-
return Ok(result);
42+
let direct_output = self.try_execute_valid_rows(try_valid_rows, &original_validity, ctx)?;
43+
44+
if let Some(output) = direct_output {
45+
return Ok(output);
5046
}
5147

52-
vortex_panic!(
53-
"valid-only execution requires direct valid-row support; {} selected an unsupported signature",
54-
self.id,
55-
)
48+
self.filter_and_scatter(kernel, &original_validity, ctx)
5649
}
5750

5851
/// Materialize validity and handle all-valid or all-null batches.
@@ -61,24 +54,24 @@ impl RowFnExecutionArgs {
6154
kernel: &impl Fn(BorrowedRowFnArgs<'_>, &mut ExecutionCtx) -> VortexResult<ArrayRef>,
6255
ctx: &mut ExecutionCtx,
6356
) -> VortexResult<ResolvedValidity> {
64-
let valid = self.validity.clone().execute_mask(self.row_count, ctx)?;
57+
let validity = self.validity.clone().execute_mask(self.row_count, ctx)?;
6558

6659
// An array-backed validity can materialize to all valid even though the cheap checks in
6760
// `RowFnExecutionArgs::execute` could not prove that. Run the full-row kernel in that
6861
// case. Check all-true before all-false because an empty mask is both.
69-
if valid.all_true() {
62+
if validity.all_true() {
7063
let values = kernel(self.execution_args(&self.inputs, self.row_count), ctx)?;
7164
let values = self.validate_kernel_output(values, self.row_count, ctx)?;
7265
let values = self.finalize_output(values, self.row_count)?;
7366

7467
return Ok(ResolvedValidity::Output(values));
7568
}
7669

77-
if valid.all_false() {
70+
if validity.all_false() {
7871
return Ok(ResolvedValidity::Output(self.all_null()));
7972
}
8073

81-
Ok(ResolvedValidity::PartiallyValid(valid))
74+
Ok(ResolvedValidity::PartiallyValid(validity))
8275
}
8376

8477
/// Try execution against the original inputs, then mask a returned full-length result.
@@ -89,21 +82,22 @@ impl RowFnExecutionArgs {
8982
&Mask,
9083
&mut ExecutionCtx,
9184
) -> VortexResult<Option<ArrayRef>>,
92-
valid: &Mask,
85+
original_validity: &Mask,
9386
ctx: &mut ExecutionCtx,
9487
) -> VortexResult<Option<ArrayRef>> {
95-
let Some(values) = try_valid_rows(
96-
self.execution_args(&self.inputs, self.row_count),
97-
valid,
98-
ctx,
99-
)?
100-
else {
88+
let row_count = original_validity.len();
89+
let args = self.execution_args(&self.inputs, row_count);
90+
91+
let Some(values) = try_valid_rows(args, original_validity, ctx)? else {
10192
return Ok(None);
10293
};
103-
let values = self.validate_kernel_output(values, valid.len(), ctx)?;
10494

105-
let mask = BoolArray::new(valid.to_bit_buffer(), Validity::NonNullable).into_array();
106-
self.finalize_output(values.mask(mask)?, valid.len())
107-
.map(Some)
95+
let values = self.validate_kernel_output(values, row_count, ctx)?;
96+
97+
let validity_array =
98+
BoolArray::new(original_validity.to_bit_buffer(), Validity::NonNullable).into_array();
99+
let masked = values.mask(validity_array)?;
100+
101+
self.finalize_output(masked, row_count).map(Some)
108102
}
109103
}

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

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -40,7 +40,7 @@ pub(crate) struct RowFnExecutionArgs {
4040
/// The number of rows in the original execution scope.
4141
row_count: usize,
4242

43-
/// The input columns, collected once for validity, constant handling, and execution.
43+
/// The input columns, collected once for validity, constant folding, filtering, and execution.
4444
inputs: SmallVec<[ArrayRef; 4]>,
4545

4646
/// The input dtypes, collected with the columns and reused by both planning and execution.

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

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,9 @@ use vortex_error::VortexResult;
88
use vortex_error::vortex_bail;
99
use vortex_session::registry::CachedId;
1010

11+
use super::BatchPlan;
12+
use super::RowFnExecutionArgs;
13+
use super::RowPolicy;
1114
use super::finalize_kernel_output;
1215
use crate::ArrayRef;
1316
use crate::IntoArray;
@@ -21,6 +24,7 @@ use crate::dtype::NativePType;
2124
use crate::dtype::Nullability;
2225
use crate::scalar::Scalar;
2326
use crate::scalar_fn::EmptyOptions;
27+
use crate::scalar_fn::ExecutionArgs;
2428
use crate::scalar_fn::ScalarFnId;
2529
use crate::scalar_fn::VecExecutionArgs;
2630
use crate::scalar_fn::unstable::row::OutputElement;
@@ -182,6 +186,34 @@ fn test_finalize_kernel_output_rejects_nested_dtype_mismatch() -> VortexResult<(
182186
Ok(())
183187
}
184188

189+
#[test]
190+
fn test_valid_only_filters_and_scatters() -> VortexResult<()> {
191+
static ID: CachedId = CachedId::new("test.filter_and_scatter");
192+
193+
let input = PrimitiveArray::new(
194+
vec![10_i64, 20, 30, 40],
195+
Validity::from_iter([true, false, true, false]),
196+
)
197+
.into_array();
198+
let args = VecExecutionArgs::new(vec![input.clone()], 4);
199+
let batch = RowFnExecutionArgs::new(*ID, &args, |_| {
200+
Ok(BatchPlan {
201+
output_dtype: DType::from(i64::PTYPE),
202+
policy: RowPolicy::ValidOnly,
203+
})
204+
})?;
205+
let mut ctx = array_session().create_execution_ctx();
206+
207+
let actual = batch.execute(
208+
|args, _ctx| args.get(0),
209+
|_args, _valid, _ctx| Ok(None),
210+
&mut ctx,
211+
)?;
212+
213+
assert_arrays_eq!(&actual, &input, &mut ctx);
214+
Ok(())
215+
}
216+
185217
#[test]
186218
fn test_kernel_output_rejects_nulls_at_function_boundary() -> VortexResult<()> {
187219
let input = PrimitiveArray::new(vec![1_i64, 2], Validity::NonNullable).into_array();

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

Lines changed: 4 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -98,8 +98,8 @@ where
9898
/// Write only the rows set in `valid`, or decline when the inputs or sink cannot support
9999
/// skip-invalid execution.
100100
///
101-
/// `Ok(None)` signals that direct skip-invalid execution is unavailable. Batch execution decides
102-
/// how to handle the decline.
101+
/// `Ok(None)` signals batch execution to filter every input to the valid rows, run the dense
102+
/// kernel, and scatter the results back into a null-padded array.
103103
pub(crate) fn execute_sink_valid_rows<Args, Prepared, Sink, ApplyResult, Options>(
104104
args: &dyn ExecutionArgs,
105105
valid: &Mask,
@@ -222,8 +222,8 @@ where
222222
return Ok(None);
223223
};
224224

225-
// Null-tolerant decoding exposes values behind nulls without filtering. Decline when any input
226-
// cannot provide those values safely.
225+
// Null-tolerant decoding exposes values behind nulls without filtering. Decline so batch
226+
// execution can filter when any input cannot provide those values safely.
227227
let Some(columns) = Args::decode_null_tolerant(args, ctx)? else {
228228
return Ok(None);
229229
};

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

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -14,7 +14,8 @@
1414
//! Unlike a general strict function, a [`RowFn`] cannot produce null from valid inputs.
1515
//!
1616
//! A _partially valid_ batch contains both valid and invalid rows. _Skip-invalid_ runs the kernel
17-
//! only for valid rows without changing row positions.
17+
//! only for valid rows without changing row positions. _Filter-and-scatter_ compacts valid rows,
18+
//! runs the kernel, and restores their positions.
1819
//!
1920
//! Prepared visits move work derived from constant operands outside the hot loop. Deferred visits
2021
//! reduce compact failure evidence without constructing errors in that loop.

‎vortex-array/src/scalar_fn/unstable/row/types/sink.rs‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -84,7 +84,7 @@ pub unsafe trait OutputSink<Options>: 'static + Sized {
8484
/// `Some` enables this strategy. The initializer **must** make every row safe to finish.
8585
/// Callbacks overwrite valid rows, and batch execution masks skipped rows.
8686
///
87-
/// `None` makes skip-invalid execution unavailable for this sink.
87+
/// `None` makes the executor fall back to filtering the inputs.
8888
fn skipped_rows_initializer() -> Option<for<'a> fn(&mut Self::Rows<'a>)> {
8989
None
9090
}

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

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -4,8 +4,8 @@
44
//! Visitors that execute dense and skip-invalid row loops.
55
//!
66
//! Each visit revalidates its concrete signature and checks that its output dtype and execution
7-
//! policy match the plan before entering a row loop. [`ExecuteValidRows`] can decline when the
8-
//! signature cannot execute over the original inputs.
7+
//! policy match the plan before entering a row loop. [`ExecuteValidRows`] can decline, so the batch
8+
//! layer filters the inputs and retries with [`ExecuteRows`].
99
1010
use vortex_error::VortexResult;
1111
use vortex_error::vortex_ensure_eq;

‎vortex-array/src/scalar_fn/unstable/row/visitor/plan.rs‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -133,7 +133,7 @@ pub(crate) enum RowPolicy {
133133
/// Evaluate all rows and mask the result.
134134
Dense,
135135

136-
/// Execute only valid rows over the original inputs.
136+
/// Execute only valid rows, filtering inputs if direct execution is unavailable.
137137
ValidOnly,
138138
}
139139

0 commit comments

Comments
 (0)