Skip to content

Commit 5c5ca19

Browse files
committed
support lambda column capture, casewhen aware
1 parent 7255820 commit 5c5ca19

8 files changed

Lines changed: 439 additions & 64 deletions

File tree

‎datafusion/common/src/utils/mod.rs‎

Lines changed: 132 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -31,20 +31,20 @@ use arrow::array::{
3131
cast::AsArray,
3232
};
3333
use arrow::array::{
34-
BooleanArray, Datum, GenericListArray, Int32Array, Int64Array, MutableArrayData,
35-
Scalar, make_array,
34+
ArrowPrimitiveType, BooleanArray, Datum, GenericListArray, Int32Array, Int64Array, MutableArrayData, PrimitiveArray, Scalar, make_array
3635
};
3736
use arrow::buffer::OffsetBuffer;
3837
use arrow::compute::kernels::cmp::neq;
3938
use arrow::compute::kernels::length::length;
4039
use arrow::compute::kernels::zip::zip;
4140
use arrow::compute::{SortColumn, SortOptions, partition};
42-
use arrow::datatypes::{DataType, Field, SchemaRef};
41+
use arrow::datatypes::{ArrowNativeType, DataType, Field, Int32Type, Int64Type, SchemaRef};
4342
#[cfg(feature = "sql")]
4443
use sqlparser::{ast::Ident, dialect::GenericDialect, parser::Parser};
4544
use std::borrow::{Borrow, Cow};
4645
use std::cmp::{Ordering, min};
4746
use std::collections::HashSet;
47+
use std::iter::repeat_n;
4848
use std::num::NonZero;
4949
use std::ops::Range;
5050
use std::sync::{Arc, LazyLock};
@@ -1141,6 +1141,62 @@ fn truncate_list_nulls<O: OffsetSizeTrait>(
11411141
Ok(list.clone())
11421142
}
11431143

1144+
/// If `array` is a contiguos list, returns a new array of the same length as it's inner values
1145+
/// where each value is the 1-based index of the sublist it's contained. Example:
1146+
///
1147+
/// `[[1], [2, 3], [4, 5, 6]] => [1, 2, 2, 3, 3, 3]`
1148+
///
1149+
/// If it's not a contiguos list, return an error
1150+
pub fn list_values_row_number(array: &dyn Array) -> Result<ArrayRef> {
1151+
match array.data_type() {
1152+
DataType::List(_) => Ok(Arc::new(list_array_values_row_number::<Int32Type>(
1153+
array.as_list().offsets(),
1154+
))),
1155+
DataType::LargeList(_) => Ok(Arc::new(
1156+
list_array_values_row_number::<Int64Type>(array.as_list().offsets()),
1157+
)),
1158+
DataType::FixedSizeList(_, _) => {
1159+
let fixed_size_list = array.as_fixed_size_list();
1160+
1161+
Ok(Arc::new(fsl_values_row_number(
1162+
fixed_size_list.value_length(),
1163+
fixed_size_list.len(),
1164+
)?))
1165+
}
1166+
other => _exec_err!("expected list, got {other}"),
1167+
}
1168+
}
1169+
1170+
/// [0, 2, 2, 5, 6] -> [0, 0, 2, 2, 2, 3]
1171+
fn list_array_values_row_number<T: ArrowPrimitiveType>(
1172+
offsets: &OffsetBuffer<T::Native>,
1173+
) -> PrimitiveArray<T> {
1174+
let mut rows_number = Vec::with_capacity(
1175+
offsets[offsets.len() - 1].to_usize().unwrap() - offsets[0].to_usize().unwrap(),
1176+
);
1177+
1178+
for (i, len) in offsets.lengths().enumerate() {
1179+
rows_number.extend(repeat_n(T::Native::usize_as(i), len));
1180+
}
1181+
1182+
PrimitiveArray::new(rows_number.into(), None)
1183+
}
1184+
1185+
/// (2, 3) -> [0, 0, 1, 1, 2, 2]
1186+
fn fsl_values_row_number(list_size: i32, array_len: usize) -> Result<Int32Array> {
1187+
let list_size = list_size.to_usize().ok_or_else(|| {
1188+
_exec_datafusion_err!("fsl_values_index: invalid list_size {list_size}")
1189+
})?;
1190+
1191+
let mut rows_number = Vec::with_capacity(list_size * array_len);
1192+
1193+
for i in 0..array_len {
1194+
rows_number.extend(repeat_n(i as i32, list_size));
1195+
}
1196+
1197+
Ok(PrimitiveArray::new(rows_number.into(), None))
1198+
}
1199+
11441200
#[cfg(test)]
11451201
mod tests {
11461202
use std::sync::Arc;
@@ -1614,4 +1670,77 @@ mod tests {
16141670
expected.as_fixed_size_list().values()
16151671
);
16161672
}
1673+
1674+
#[test]
1675+
fn test_list_array_values_row_number() {
1676+
assert_eq!(
1677+
list_array_values_row_number::<Int32Type>(&OffsetBuffer::from_lengths([
1678+
1, 3, 0, 2,
1679+
])),
1680+
Int32Array::from(vec![0, 1, 1, 1, 3, 3])
1681+
);
1682+
1683+
assert_eq!(
1684+
list_array_values_row_number::<Int32Type>(&OffsetBuffer::from_lengths([])),
1685+
Int32Array::new_null(0)
1686+
);
1687+
1688+
assert_eq!(
1689+
list_array_values_row_number::<Int32Type>(&OffsetBuffer::from_lengths([0])),
1690+
Int32Array::new_null(0)
1691+
);
1692+
1693+
assert_eq!(
1694+
list_array_values_row_number::<Int32Type>(&OffsetBuffer::from_lengths([
1695+
0, 0
1696+
])),
1697+
Int32Array::new_null(0)
1698+
);
1699+
1700+
assert_eq!(
1701+
list_array_values_row_number::<Int32Type>(&OffsetBuffer::from_lengths([1])),
1702+
Int32Array::from(vec![0])
1703+
);
1704+
1705+
assert_eq!(
1706+
list_array_values_row_number::<Int32Type>(&OffsetBuffer::from_lengths([2])),
1707+
Int32Array::from(vec![0, 0])
1708+
);
1709+
}
1710+
1711+
#[test]
1712+
fn test_fsl_values_row_number() {
1713+
assert_eq!(
1714+
fsl_values_row_number(2, 3).unwrap(),
1715+
Int32Array::from(vec![0, 0, 1, 1, 2, 2])
1716+
);
1717+
1718+
assert_eq!(
1719+
fsl_values_row_number(1, 3).unwrap(),
1720+
Int32Array::from(vec![0, 1, 2])
1721+
);
1722+
1723+
assert_eq!(
1724+
fsl_values_row_number(2, 1).unwrap(),
1725+
Int32Array::from(vec![0, 0])
1726+
);
1727+
1728+
assert_eq!(
1729+
fsl_values_row_number(2, 0).unwrap(),
1730+
Int32Array::new_null(0),
1731+
);
1732+
1733+
assert_eq!(
1734+
fsl_values_row_number(0, 2).unwrap(),
1735+
Int32Array::new_null(0),
1736+
);
1737+
1738+
assert_eq!(
1739+
fsl_values_row_number(0, 0).unwrap(),
1740+
Int32Array::new_null(0),
1741+
);
1742+
1743+
fsl_values_row_number(-1, 2).unwrap_err();
1744+
fsl_values_row_number(-1, 0).unwrap_err();
1745+
}
16171746
}

‎datafusion/expr/src/udhof.rs‎

Lines changed: 113 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -22,7 +22,7 @@ use crate::{ColumnarValue, Documentation, Expr};
2222
use arrow::array::{ArrayRef, RecordBatch};
2323
use arrow::datatypes::{DataType, Field, FieldRef, Schema};
2424
use datafusion_common::config::ConfigOptions;
25-
use datafusion_common::{Result, ScalarValue, not_impl_err};
25+
use datafusion_common::{Result, ScalarValue, exec_err, not_impl_err};
2626
use datafusion_expr_common::dyn_eq::{DynEq, DynHash};
2727
use datafusion_expr_common::signature::Volatility;
2828
use datafusion_physical_expr_common::physical_expr::PhysicalExpr;
@@ -194,34 +194,136 @@ pub struct LambdaArgument {
194194
/// For example, for `array_transform([2], v -> -v)`,
195195
/// this will be the physical expression of `-v`
196196
body: Arc<dyn PhysicalExpr>,
197+
/// A RecordBatch containing at least the captured columns inside this lambda body, if any
198+
/// Note that it may contain additional, non-specified columns, but that's a implementation detail
199+
///
200+
/// For example, for `array_transform([2], v -> v + a + b)`,
201+
/// this will be a `RecordBatch` with at least two columns, `a` and `b`
202+
captures: Option<RecordBatch>,
197203
}
198204

199205
impl LambdaArgument {
200-
pub fn new(params: Vec<FieldRef>, body: Arc<dyn PhysicalExpr>) -> Self {
201-
Self { params, body }
206+
pub fn new(
207+
params: Vec<FieldRef>,
208+
body: Arc<dyn PhysicalExpr>,
209+
captures: Option<RecordBatch>,
210+
) -> Self {
211+
Self {
212+
params,
213+
body,
214+
captures,
215+
}
202216
}
203217

204218
/// Evaluate this lambda
205219
/// `args` should evaluate to the value of each parameter
206220
/// of the correspondent lambda returned in [HigherOrderUDF::lambda_parameters].
221+
///
222+
/// `adjust` should adjust the captured columns of this
223+
/// lambda, if any, relative to it's parameters
224+
///
225+
/// Tip: For adjusting multiple arrays by indices, use [`take_arrays`]
226+
///
227+
/// [`take_arrays`]: arrow::compute::take_arrays
207228
pub fn evaluate(
208229
&self,
209230
args: &[&dyn Fn() -> Result<ArrayRef>],
231+
adjust: impl FnOnce(&[ArrayRef]) -> Result<Vec<ArrayRef>>,
210232
) -> Result<ColumnarValue> {
211-
let columns = args
212-
.iter()
213-
.take(self.params.len())
214-
.map(|arg| arg())
215-
.collect::<Result<_>>()?;
233+
let adjusted_captures = self
234+
.captures
235+
.as_ref()
236+
.map(|captures| {
237+
let adjusted_columns = adjust(captures.columns())?;
238+
239+
RecordBatch::try_new(captures.schema(), adjusted_columns)
240+
})
241+
.transpose()?;
242+
243+
let merged = merge_captures_with_variables(
244+
adjusted_captures.as_ref(),
245+
&self.params,
246+
args,
247+
)?;
248+
249+
self.body.evaluate(&merged)
250+
}
251+
}
252+
253+
fn merge_captures_with_variables(
254+
captures: Option<&RecordBatch>,
255+
params: &[FieldRef],
256+
variables: &[&dyn Fn() -> Result<ArrayRef>],
257+
) -> Result<RecordBatch> {
258+
if variables.len() < params.len() {
259+
return exec_err!(
260+
"expected at least {} lambda arguments to merge with captures, got {}",
261+
params.len(),
262+
variables.len()
263+
);
264+
}
265+
266+
match captures {
267+
Some(captures) => {
268+
let old_fields = captures.schema_ref().fields();
269+
270+
let mut new_fields = old_fields
271+
.iter()
272+
.map(|field| {
273+
if !fields_contains(params, field.name()) {
274+
return Arc::clone(field);
275+
}
216276

217-
let schema = Arc::new(Schema::new(self.params.clone()));
277+
let mut i = 0;
218278

219-
let batch = RecordBatch::try_new(schema, columns)?;
279+
loop {
280+
let alias = format!("{}_shadowed_{i}", field.name());
220281

221-
self.body.evaluate(&batch)
282+
if !fields_contains(params, &alias)
283+
&& old_fields.find(&alias).is_none()
284+
{
285+
break Arc::new(Field::new(
286+
alias,
287+
field.data_type().clone(),
288+
field.is_nullable(),
289+
));
290+
}
291+
292+
i += 1;
293+
}
294+
})
295+
.collect::<Vec<_>>();
296+
297+
new_fields.extend_from_slice(params);
298+
299+
let mut columns = captures.columns().to_vec();
300+
301+
for arg in &variables[..params.len()] {
302+
columns.push(arg()?);
303+
}
304+
305+
let new_schema = Arc::new(Schema::new(new_fields));
306+
307+
Ok(RecordBatch::try_new(new_schema, columns)?)
308+
}
309+
None => {
310+
let columns = variables
311+
.iter()
312+
.take(params.len())
313+
.map(|arg| arg())
314+
.collect::<Result<_>>()?;
315+
316+
let schema = Arc::new(Schema::new(params));
317+
318+
Ok(RecordBatch::try_new(schema, columns)?)
319+
}
222320
}
223321
}
224322

323+
fn fields_contains(fields: &[FieldRef], name: &str) -> bool {
324+
fields.iter().any(|f| f.name().as_str() == name)
325+
}
326+
225327
/// Information about arguments passed to the function
226328
///
227329
/// This structure contains metadata about how the function was called

‎datafusion/functions-nested/src/array_transform.rs‎

Lines changed: 10 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -22,11 +22,14 @@ use arrow::{
2222
Array, ArrayRef, AsArray, FixedSizeListArray, LargeListArray, ListArray,
2323
new_null_array,
2424
},
25+
compute::take_arrays,
2526
datatypes::{DataType, Field, FieldRef},
2627
};
2728
use datafusion_common::{
2829
Result, exec_err, plan_err,
29-
utils::{adjust_offsets_for_slice, list_values, take_function_args},
30+
utils::{
31+
adjust_offsets_for_slice, list_values, list_values_row_number, take_function_args,
32+
},
3033
};
3134
use datafusion_expr::{
3235
ColumnarValue, Documentation, HigherOrderFunctionArgs, HigherOrderReturnFieldArgs,
@@ -200,7 +203,12 @@ impl HigherOrderUDF for ArrayTransform {
200203

201204
// call the transforming lambda
202205
let transformed_values = lambda
203-
.evaluate(&[&values_param])?
206+
.evaluate(&[&values_param], |arrays| {
207+
// if any column got captured, we need to adjust it to the values arrays,
208+
// duplicating values of list with mulitple values and removing values of empty lists
209+
let indices = list_values_row_number(&list_array)?;
210+
Ok(take_arrays(arrays, &indices, None)?)
211+
})?
204212
.into_array(list_values.len())?;
205213

206214
let field = match args.return_field.data_type() {

0 commit comments

Comments
 (0)