LiaCastaneda commented on code in PR #21895: URL: https://github.com/apache/datafusion/pull/21895#discussion_r3258909465
########## datafusion/functions-nested/src/array_filter.rs: ########## @@ -0,0 +1,490 @@ +// Licensed to the Apache Software Foundation (ASF) under one +// or more contributor license agreements. See the NOTICE file +// distributed with this work for additional information +// regarding copyright ownership. The ASF licenses this file +// to you under the Apache License, Version 2.0 (the +// "License"); you may not use this file except in compliance +// with the License. You may obtain a copy of the License at +// +// http://www.apache.org/licenses/LICENSE-2.0 +// +// Unless required by applicable law or agreed to in writing, +// software distributed under the License is distributed on an +// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY +// KIND, either express or implied. See the License for the +// specific language governing permissions and limitations +// under the License. + +//! [`HigherOrderUDF`] definitions for array_filter function. + +use arrow::{ + array::{ + Array, ArrayRef, AsArray, BooleanArray, BooleanBufferBuilder, LargeListArray, + ListArray, OffsetSizeTrait, new_empty_array, + }, + buffer::{OffsetBuffer, ScalarBuffer}, + compute::{filter as arrow_filter, take_arrays}, + datatypes::{DataType, Field, FieldRef}, +}; +use datafusion_common::{ + Result, ScalarValue, exec_err, plan_err, + utils::{adjust_offsets_for_slice, list_values_row_number}, +}; +use datafusion_expr::{ + ColumnarValue, Documentation, HigherOrderFunctionArgs, HigherOrderReturnFieldArgs, + HigherOrderSignature, HigherOrderUDF, LambdaParametersProgress, ValueOrLambda, + Volatility, +}; +use datafusion_macros::user_doc; +use std::sync::Arc; + +make_higher_order_function_expr_and_func!( + ArrayFilter, + array_filter, + array lambda, + "filters the values of an array using a boolean lambda", + array_filter_higher_order_function +); + +#[user_doc( + doc_section(label = "Array Functions"), + description = "filters the values of an array using a boolean lambda", + syntax_example = "array_filter(array, x -> x > 2)", + sql_example = r#"```sql +> select array_filter([1, 2, 3, 4, 5], x -> x > 2); ++--------------------------------------------+ +| array_filter([1, 2, 3, 4, 5], x -> x > 2) | ++--------------------------------------------+ +| [3, 4, 5] | ++--------------------------------------------+ +```"#, + argument( + name = "array", + description = "Array expression. Can be a constant, column, or function, and any combination of array operators." + ), + argument( + name = "lambda", + description = "Lambda that returns a boolean. Elements for which the lambda returns true are kept." + ) +)] +#[derive(Debug, PartialEq, Eq, Hash)] +pub struct ArrayFilter { + signature: HigherOrderSignature, + aliases: Vec<String>, +} + +impl Default for ArrayFilter { + fn default() -> Self { + Self::new() + } +} + +impl ArrayFilter { + pub fn new() -> Self { + Self { + signature: HigherOrderSignature::user_defined(Volatility::Immutable), + aliases: vec![String::from("list_filter")], + } + } +} + +impl HigherOrderUDF for ArrayFilter { + fn name(&self) -> &str { + "array_filter" + } + + fn aliases(&self) -> &[String] { + &self.aliases + } + + fn signature(&self) -> &HigherOrderSignature { + &self.signature + } + + fn lambda_parameters( + &self, + _step: usize, + fields: &[ValueOrLambda<FieldRef, Option<FieldRef>>], + ) -> Result<LambdaParametersProgress> { + crate::lambda_utils::single_list_lambda_parameters(self.name(), fields) + } + + fn return_field_from_args( + &self, + args: HigherOrderReturnFieldArgs, + ) -> Result<Arc<Field>> { + let (list, _lambda) = value_lambda_pair(self.name(), args.arg_fields)?; + + match list.data_type() { + DataType::List(_) | DataType::LargeList(_) => {} + other => return plan_err!("expected list, got {other}"), + } + + // array_filter preserves the input element type — it filters, not transforms + Ok(Arc::new(Field::new( + "", + list.data_type().clone(), + list.is_nullable(), + ))) + } + + fn invoke_with_args(&self, args: HigherOrderFunctionArgs) -> Result<ColumnarValue> { + let (list, lambda) = value_lambda_pair(self.name(), &args.args)?; + let list_array = list.to_array(args.number_rows)?; + + let list_values = match crate::lambda_utils::extract_list_values( + &list_array, + args.return_type(), + )? { + crate::lambda_utils::ListValuesResult::EarlyReturn(v) => return Ok(v), + crate::lambda_utils::ListValuesResult::Values(v) => v, + }; + + let field = match args.return_field.data_type() { + DataType::List(field) | DataType::LargeList(field) => Arc::clone(field), + _ => { + return exec_err!( + "{} expected return_field to be a list, got {}", + self.name(), + args.return_field + ); + } + }; + + let values_param = || Ok(Arc::clone(&list_values)); + let predicate_cv = lambda.evaluate(&[&values_param], |arrays| { + let indices = list_values_row_number(&list_array)?; + Ok(take_arrays(arrays, &indices, None)?) + })?; + + // Scalar predicate short-circuit: x -> true or x -> false/null + if let ColumnarValue::Scalar(ScalarValue::Boolean(b)) = &predicate_cv { + return match b { + Some(true) => Ok(ColumnarValue::Array(list_array)), + _ => Ok(ColumnarValue::Array(empty_filtered_list( + &list_array, + field, + )?)), + }; + } + + let predicate = predicate_cv.into_array(list_values.len())?; + let Some(predicate) = predicate.as_any().downcast_ref::<BooleanArray>() else { + return exec_err!( + "{} lambda must return boolean, got {}", + self.name(), + predicate.data_type() + ); + }; + + let filtered_list = match list_array.data_type() { + DataType::List(_) => { + let list = list_array.as_list::<i32>(); + let adjusted_offsets = adjust_offsets_for_slice(list); + let (filtered_values, new_offsets) = + filter_list_values(&list_values, predicate, &adjusted_offsets)?; + Arc::new(ListArray::new( + field, + new_offsets, + filtered_values, + list.nulls().cloned(), + )) as ArrayRef + } + DataType::LargeList(_) => { + let large_list = list_array.as_list::<i64>(); + let adjusted_offsets = adjust_offsets_for_slice(large_list); + let (filtered_values, new_offsets) = + filter_list_values(&list_values, predicate, &adjusted_offsets)?; + Arc::new(LargeListArray::new( + field, + new_offsets, + filtered_values, + large_list.nulls().cloned(), + )) + } + other => exec_err!("expected list, got {other}")?, + }; + + Ok(ColumnarValue::Array(filtered_list)) + } + + fn coerce_value_types(&self, arg_types: &[DataType]) -> Result<Vec<DataType>> { + crate::lambda_utils::coerce_single_list_arg(self.name(), arg_types) + } + + fn documentation(&self) -> Option<&Documentation> { + self.doc() + } +} + +/// Returns a list array with every non-null sublist emptied, preserving the null buffer. +/// Used for the `x -> false` / `x -> null` scalar predicate short-circuit. +fn empty_filtered_list(list_array: &ArrayRef, field: FieldRef) -> Result<ArrayRef> { + let n = list_array.len(); + let empty_values = new_empty_array(field.data_type()); + Ok(match list_array.data_type() { + DataType::List(_) => { + let list = list_array.as_list::<i32>(); + Arc::new(ListArray::new( + field, + OffsetBuffer::new(ScalarBuffer::from(vec![0i32; n + 1])), + empty_values, + list.nulls().cloned(), + )) + } + DataType::LargeList(_) => { + let list = list_array.as_list::<i64>(); + Arc::new(LargeListArray::new( + field, + OffsetBuffer::new(ScalarBuffer::from(vec![0i64; n + 1])), + empty_values, + list.nulls().cloned(), + )) + } + other => return exec_err!("expected list, got {other}"), + }) +} + +/// Filters flat list values using a boolean predicate, returning filtered values and +/// recomputed per-sublist offsets. Null predicate values are treated as false. +fn filter_list_values<O: OffsetSizeTrait>( + values: &ArrayRef, + predicate: &BooleanArray, + offsets: &OffsetBuffer<O>, +) -> Result<(ArrayRef, OffsetBuffer<O>)> { + let num_sublists = offsets.len().saturating_sub(1); + let mut new_offsets: Vec<O> = Vec::with_capacity(offsets.len()); + new_offsets.push(O::from_usize(0).expect("0 always fits in offset type")); + + if predicate.null_count() == 0 { + let bool_buf = predicate.values(); + for i in 0..num_sublists { + let start = offsets[i].as_usize(); + let end = offsets[i + 1].as_usize(); + let count = bool_buf.slice(start, end - start).count_set_bits(); + let prev = *new_offsets.last().unwrap(); + new_offsets.push( + prev + O::from_usize(count).expect("filtered count fits in offset type"), + ); + } + if new_offsets.last() == offsets.last() { + return Ok((Arc::clone(values), offsets.clone())); + } + let filtered_values = arrow_filter(values.as_ref(), predicate)?; + return Ok(( + filtered_values, + OffsetBuffer::new(ScalarBuffer::from(new_offsets)), + )); + } + + // Null predicate values present: build a selection mask with null → false. + let mut selection = BooleanBufferBuilder::new(values.len()); + for i in 0..num_sublists { + let start = offsets[i].as_usize(); + let end = offsets[i + 1].as_usize(); + let mut count = 0usize; + for j in start..end { + let keep = predicate.is_valid(j) && predicate.value(j); + selection.append(keep); + if keep { + count += 1; + } Review Comment: Maybe we should just follow what the arrow filter kernel does https://docs.rs/arrow/latest/arrow/compute/kernels/filter/fn.filter.html, if it skips the nulls it's probably fine. Also if the kernel skips/treats as false the nulls then I think we can skip manually builsing a mask here -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
