Skip to content

Commit 79de5e9

Browse files
authored
fix(lambda): only push referenced params into the merged batch (apache#24162) (#166)
* fix(lambda): only push referenced params into the merged batch (apache#24162) ## Which issue does this PR close? basically this PR apache#22853 + a few more tests ## Rationale for this change The current lambdas in DF only take a single parameter `(v -> ...)`, so nobody had noticed that `LambdaExpr` mishandles lambdas with more than one parameter. The bug surfaced while working on `transform_values` (apache#22689), which needs `(k, v) -> expr ` two parameters, one of which is very often unused (e.g. `(k, v) -> v * 2`, k never referenced). The bug is that when a higher order function with more than 1 param evaluates a lambda, it fills each parameter into a slot based on its declared position — for example for `(k, v) -> v` `k` always goes into slot 0, `v` always into slot 1. `LambdaExpr` separately scans the body and renumbers whatever it finds referenced into a dense `0..n` range, to avoid carrying around columns nothing uses (like `v` in this case). That renumbering is fine for outer captures, but applying it to the lambda's own parameters is wrong, because it changes where the body looks for a value without changing where the evaluator put it. ### Example: in `(k, v) -> v` `v` is declared second (slot 1), but since it's the only parameter the body references, the renumbering logic reassigns it to slot 0. The evaluator, unaware of this, writes `k`'s values into slot 0 and `v`'s into slot 1. So the body ends up reading slot 0 expecting `v` — and gets `k` instead. So the results end up being incorrect. ## What changes are included in this PR? - `LambdaExpr` now computes `used_params`: which is the subset of its own declared parameters that are actually referenced in the body. - `LambdaArgument::new` takes `used_params` and only pushes the referenced parameters in the body into the merged batch, in original declaration order — so the body's indices always line up with what's actually built. - `HigherOrderFunctionExpr::evaluate` forwards `lambda.used_params()` to `LambdaArgument::new` ## Are these changes tested? yes, added two new tests one for the unused-parameter case and nested-lambda for the shadowing case. ## Are there any user-facing changes? The only public api change is on `LambdaArgument::new ` which now requires a new argument: `used_params: &HashSet<String>`, however LambdaArgument::new is very unlikely to be called outside datafusion, see [this](apache#22853 (comment)) comment (cherry picked from commit 4e6acfe) * Adjust to API change
1 parent f6d73a8 commit 79de5e9

3 files changed

Lines changed: 479 additions & 37 deletions

File tree

‎datafusion/expr/src/higher_order_function.rs‎

Lines changed: 184 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -24,7 +24,7 @@ use crate::expr::{
2424
use crate::type_coercion::functions::value_fields_with_higher_order_udf;
2525
use crate::udf_eq::UdfEq;
2626
use crate::{ColumnarValue, Documentation, Expr, ExprSchemable};
27-
use arrow::array::{ArrayRef, RecordBatch};
27+
use arrow::array::{ArrayRef, RecordBatch, RecordBatchOptions};
2828
use arrow::datatypes::{DataType, FieldRef, Schema};
2929
use arrow_schema::SchemaRef;
3030
use datafusion_common::config::ConfigOptions;
@@ -239,6 +239,26 @@ pub struct LambdaArgument {
239239
/// For example, for `array_transform([2], v -> -v)`,
240240
/// this will be `vec![Field::new("v", DataType::Int32, true)]`
241241
params: Vec<FieldRef>,
242+
/// Indices into [`Self::params`] of the parameters that are actually
243+
/// referenced by [`Self::body`] (taking nested-lambda shadowing into
244+
/// account), in the original declaration order of `params`.
245+
///
246+
/// [`Self::evaluate`] only evaluates and pushes the closures whose
247+
/// corresponding parameter index appears here, so unused declared
248+
/// parameters leave no slot in the merged batch and the body's compressed
249+
/// column indices line up directly with what the evaluator built.
250+
///
251+
/// Callers who already have a `LambdaExpr` should pass
252+
/// `LambdaExpr::used_param_indices()` directly to [`Self::new`] — both
253+
/// are indices into the same positionally-aligned `params` list.
254+
///
255+
/// Every index here must be `< params.len()`; see the precondition on
256+
/// [`Self::new`].
257+
///
258+
/// Relies on captures sorting before this lambda's own params in the
259+
/// planner's (un-projected) index space, which is what makes
260+
/// `captures ++ used_params` below line up with the projected body.
261+
used_param_indices: Vec<usize>,
242262
/// The body of the lambda
243263
///
244264
/// For example, for `array_transform([2], v -> -v)`,
@@ -257,26 +277,45 @@ pub struct LambdaArgument {
257277
}
258278

259279
impl LambdaArgument {
280+
/// # Preconditions
281+
///
282+
/// Every index in `used_param_indices` must be `< params.len()`;
283+
/// violating this panics on out-of-bounds indexing below. Callers should
284+
/// pass `LambdaExpr::used_param_indices()`, which always indexes into the
285+
/// same `params` list, rather than constructing indices by hand.
260286
pub fn new(
261287
params: Vec<FieldRef>,
262288
body: Arc<dyn PhysicalExpr>,
263289
captures: Option<RecordBatch>,
290+
used_param_indices: &[usize],
264291
) -> Self {
265-
let fields = match &captures {
292+
debug_assert!(
293+
used_param_indices.iter().all(|i| *i < params.len()),
294+
"used_param_indices contains an index out of bounds for params \
295+
(len {}): {:?}",
296+
params.len(),
297+
used_param_indices
298+
);
299+
300+
let used_param_indices = used_param_indices.to_vec();
301+
let effective_params = used_param_indices.iter().map(|i| Arc::clone(&params[*i]));
302+
303+
let fields: Vec<FieldRef> = match &captures {
266304
Some(batch) => batch
267305
.schema_ref()
268306
.fields()
269307
.iter()
270308
.cloned()
271-
.chain(params.clone())
309+
.chain(effective_params)
272310
.collect(),
273-
None => params.clone(),
311+
None => effective_params.collect(),
274312
};
275313

276314
let schema = Arc::new(Schema::new(fields));
277315

278316
Self {
279317
params,
318+
used_param_indices,
280319
body,
281320
schema,
282321
captures,
@@ -287,6 +326,11 @@ impl LambdaArgument {
287326
/// `args` should evaluate to the value of each parameter
288327
/// of the correspondent lambda returned in [HigherOrderUDFImpl::lambda_parameters].
289328
///
329+
/// Only the closures in `args` for parameters the lambda body actually
330+
/// references are called; closures for declared-but-unused parameters
331+
/// are skipped entirely. Callers should not rely on every closure in
332+
/// `args` being invoked.
333+
///
290334
/// `spread_captures` is responsible for transforming the captured column arrays
291335
/// so they align with the evaluation batch. Captures are snapshotted from the
292336
/// outer batch at construction time, giving one value per outer row, but the
@@ -344,6 +388,7 @@ impl LambdaArgument {
344388
spread_captures.as_ref(),
345389
Arc::clone(&self.schema),
346390
&self.params,
391+
&self.used_param_indices,
347392
args,
348393
)?;
349394

@@ -355,6 +400,7 @@ fn merge_captures_with_variables(
355400
captures: Option<&RecordBatch>,
356401
schema: SchemaRef,
357402
params: &[FieldRef],
403+
used_param_indices: &[usize],
358404
variables: &[&dyn Fn() -> Result<ArrayRef>],
359405
) -> Result<RecordBatch> {
360406
if variables.len() < params.len() {
@@ -365,23 +411,42 @@ fn merge_captures_with_variables(
365411
);
366412
}
367413

414+
let push_param_arrays = |columns: &mut Vec<ArrayRef>| -> Result<()> {
415+
for &i in used_param_indices {
416+
columns.push(variables[i]()?);
417+
}
418+
Ok(())
419+
};
420+
368421
let columns = match captures {
369422
Some(captures) => {
370423
let mut columns = captures.columns().to_vec();
371-
372-
for arg in &variables[..params.len()] {
373-
columns.push(arg()?);
374-
}
375-
424+
push_param_arrays(&mut columns)?;
425+
columns
426+
}
427+
None => {
428+
let mut columns = Vec::with_capacity(used_param_indices.len());
429+
push_param_arrays(&mut columns)?;
376430
columns
377431
}
378-
None => variables
379-
.iter()
380-
.take(params.len())
381-
.map(|arg| arg())
382-
.collect::<Result<_>>()?,
383432
};
384433

434+
if columns.is_empty() {
435+
// No columns to derive a row count from, so borrow one variable's
436+
// array length instead (all variables have the same length).
437+
let row_count = variables.first().ok_or_else(|| {
438+
internal_datafusion_err!(
439+
"merge_captures_with_variables: no variables to derive a row count from"
440+
)
441+
})?()?
442+
.len();
443+
return Ok(RecordBatch::try_new_with_options(
444+
schema,
445+
vec![],
446+
&RecordBatchOptions::new().with_row_count(Some(row_count)),
447+
)?);
448+
}
449+
385450
Ok(RecordBatch::try_new(schema, columns)?)
386451
}
387452

@@ -1681,4 +1746,109 @@ mod tests {
16811746
Some(Arc::new(Field::new(name, dt, nullable))),
16821747
))
16831748
}
1749+
1750+
/// A physical expression that reads the column at a fixed index of the
1751+
/// batch it is evaluated against, for exercising [`LambdaArgument`]
1752+
/// directly without depending on `datafusion-physical-expr`.
1753+
#[derive(Debug, Eq, PartialEq, Hash)]
1754+
struct ColumnAt(usize);
1755+
1756+
impl std::fmt::Display for ColumnAt {
1757+
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
1758+
write!(f, "column_at({})", self.0)
1759+
}
1760+
}
1761+
1762+
impl PhysicalExpr for ColumnAt {
1763+
fn evaluate(&self, batch: &RecordBatch) -> Result<ColumnarValue> {
1764+
Ok(ColumnarValue::Array(Arc::clone(batch.column(self.0))))
1765+
}
1766+
1767+
fn children(&self) -> Vec<&Arc<dyn PhysicalExpr>> {
1768+
vec![]
1769+
}
1770+
1771+
fn with_new_children(
1772+
self: Arc<Self>,
1773+
_children: Vec<Arc<dyn PhysicalExpr>>,
1774+
) -> Result<Arc<dyn PhysicalExpr>> {
1775+
Ok(self)
1776+
}
1777+
1778+
fn fmt_sql(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
1779+
write!(f, "{self}")
1780+
}
1781+
}
1782+
1783+
/// `(k, v) -> v` with only `v` used must push `v`'s array, not `k`'s.
1784+
#[test]
1785+
fn test_lambda_argument_evaluate_pushes_only_used_param() {
1786+
use arrow::array::Int32Array;
1787+
1788+
let k_field = Arc::new(Field::new("k", DataType::Int32, true));
1789+
let v_field = Arc::new(Field::new("v", DataType::Int32, true));
1790+
1791+
let body = Arc::new(ColumnAt(0)) as Arc<dyn PhysicalExpr>;
1792+
let lambda_arg = LambdaArgument::new(vec![k_field, v_field], body, None, &[1]);
1793+
1794+
let k_values: ArrayRef = Arc::new(Int32Array::from(vec![100, 200, 300]));
1795+
let v_values: ArrayRef = Arc::new(Int32Array::from(vec![1, 2, 3]));
1796+
let k_closure = || -> Result<ArrayRef> { Ok(Arc::clone(&k_values)) };
1797+
let v_closure = || -> Result<ArrayRef> { Ok(Arc::clone(&v_values)) };
1798+
let args: Vec<&dyn Fn() -> Result<ArrayRef>> = vec![&k_closure, &v_closure];
1799+
1800+
let result = lambda_arg
1801+
.evaluate(&args, |arrays| Ok(arrays.to_vec()))
1802+
.unwrap();
1803+
let ColumnarValue::Array(result) = result else {
1804+
unreachable!()
1805+
};
1806+
1807+
assert_eq!(
1808+
result.as_any().downcast_ref::<Int32Array>().unwrap(),
1809+
&Int32Array::from(vec![1, 2, 3]),
1810+
"body should read v's values, not k's"
1811+
);
1812+
}
1813+
1814+
/// Same as above, but with a capture occupying the leading slot.
1815+
#[test]
1816+
fn test_lambda_argument_evaluate_pushes_only_used_param_with_captures() {
1817+
use arrow::array::Int32Array;
1818+
1819+
let cap_field = Arc::new(Field::new("cap", DataType::Int32, true));
1820+
let k_field = Arc::new(Field::new("k", DataType::Int32, true));
1821+
let v_field = Arc::new(Field::new("v", DataType::Int32, true));
1822+
1823+
let body = Arc::new(ColumnAt(1)) as Arc<dyn PhysicalExpr>;
1824+
1825+
let cap_values: ArrayRef = Arc::new(Int32Array::from(vec![9, 9, 9]));
1826+
let captures = RecordBatch::try_new(
1827+
Arc::new(Schema::new(vec![cap_field])),
1828+
vec![cap_values],
1829+
)
1830+
.unwrap();
1831+
1832+
let lambda_arg =
1833+
LambdaArgument::new(vec![k_field, v_field], body, Some(captures), &[1]);
1834+
1835+
let k_values: ArrayRef = Arc::new(Int32Array::from(vec![100, 200, 300]));
1836+
let v_values: ArrayRef = Arc::new(Int32Array::from(vec![1, 2, 3]));
1837+
let k_closure = || -> Result<ArrayRef> { Ok(Arc::clone(&k_values)) };
1838+
let v_closure = || -> Result<ArrayRef> { Ok(Arc::clone(&v_values)) };
1839+
let args: Vec<&dyn Fn() -> Result<ArrayRef>> = vec![&k_closure, &v_closure];
1840+
1841+
let result = lambda_arg
1842+
.evaluate(&args, |arrays| Ok(arrays.to_vec()))
1843+
.unwrap();
1844+
let ColumnarValue::Array(result) = result else {
1845+
unreachable!()
1846+
};
1847+
1848+
assert_eq!(
1849+
result.as_any().downcast_ref::<Int32Array>().unwrap(),
1850+
&Int32Array::from(vec![1, 2, 3]),
1851+
"body should read v's values, not k's or the capture's"
1852+
);
1853+
}
16841854
}

0 commit comments

Comments
 (0)