mbutrovich commented on code in PR #332:
URL: https://github.com/apache/datafusion-spark/pull/332#discussion_r4605653094


##########
crates/spark/src/function/math/greatest_least.rs:
##########
@@ -0,0 +1,961 @@
+// SPDX-License-Identifier: Apache-2.0
+// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for 
additional information regarding copyright ownership
+// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF) 
under one or more contributor license agreements
+
+//! Spark-compatible `greatest` and `least`.
+//!
+//! Spark evaluates the arguments in order, skips NULLs, and replaces its 
running result only
+//! with a value that is strictly greater (or smaller) in its SQL ordering, so 
the result is NULL
+//! only when every argument is NULL and the first of equal arguments wins. 
The SQL ordering
+//! (`SQLOrderingUtil.compareDoubles`) treats `-0.0` as equal to `0.0` and NaN 
as greater than
+//! every other value, at any depth of arrays and structs, and orders a NULL 
inside an array or
+//! struct before every other value.
+//!
+//! DataFusion's built-in `greatest` and `least` differ: they compare floats 
by IEEE 754 total
+//! order (so `-0.0 < 0.0`, and a NaN with the sign bit set is smaller than 
`-Infinity`), let a
+//! later argument win a tie, compare the constant arguments before the 
columns, accept a single
+//! argument, order a NULL inside an array or struct after every other value 
in `least`, and
+//! coerce their arguments with DataFusion's comparison coercion, which for 
example compares a
+//! number with a string. Spark rejects that.
+
+use crate::function::float_normalize::{contains_float, normalize_array};
+use crate::function::type_coercion::{is_orderable, spark_sql_type, wider_type};
+use arrow::array::{
+    Array, ArrayRef, ArrowPrimitiveType, AsArray, BooleanArray, Datum, Scalar,
+    make_comparator, new_null_array,
+};
+use arrow::buffer::BooleanBuffer;
+use arrow::compute::kernels::cmp::{gt, lt};
+use arrow::compute::kernels::zip::zip;
+use arrow::compute::{SortOptions, cast};
+use arrow::datatypes::{DataType, Field, FieldRef, Float32Type, Float64Type};
+use datafusion_common::config::ConfigOptions;
+use datafusion_common::{DataFusionError, Result, ScalarValue, plan_err};
+use datafusion_expr::{
+    ColumnarValue, Documentation, ReturnFieldArgs, ScalarFunctionArgs, 
ScalarUDF,
+    ScalarUDFImpl, Signature, Volatility,
+};
+use datafusion_macros::user_doc;
+use num_traits::Float;
+use std::sync::Arc;
+
+/// Spark-compatible `greatest` expression.
+///
+/// <https://spark.apache.org/docs/latest/api/sql/index.html#greatest>
+#[user_doc(
+    doc_section(label = "Math Functions"),
+    description = "Returns the greatest value of all arguments, skipping 
NULLs. The result is \
+        NULL only if every argument is NULL. At least two arguments are 
required. The \
+        arguments are cast to a common type as in Spark: numbers widen (an 
integer and a FLOAT \
+        widen to DOUBLE with `datafusion.execution.enable_ansi_mode` on and to 
FLOAT with it \
+        off), integers and decimals widen to a decimal that holds both, a 
decimal and a float \
+        widen to DOUBLE, a date and a timestamp widen to the timestamp, and 
arrays and structs \
+        widen element by element. Strings are never promoted: a string and a 
number, a string \
+        and a date, or a boolean and a number are an error, as are maps, which 
cannot be \
+        ordered. NaN is greater than every other value and `-0.0` equals 
`0.0`, also inside \
+        arrays and structs, and of equal values the first argument wins, so \
+        `greatest(-0.0, 0.0)` is `-0.0`. A NULL inside an array or struct is 
smaller than \
+        every other value. DataFusion's built-in `greatest` orders floats by 
IEEE 754 total \
+        order, lets a later argument win a tie, accepts a single argument, and 
compares \
+        numbers with strings.",
+    syntax_example = "greatest(expr1, expr2[, ..., expr_n])",
+    sql_example = r#"```sql
+> SELECT greatest(10, 9, 2, 4, 3);
+10
+> SELECT greatest(1, NULL, 3);
+3
+> SELECT greatest(1.0, 'NaN'::double);
+NaN
+```"#,
+    argument(
+        name = "expr1, expr2, ..., expr_n",
+        description = "Expressions of an orderable type that share a common 
type. NULLs are \
+            skipped."
+    )
+)]
+#[derive(Debug, PartialEq, Eq, Hash)]
+pub struct SparkGreatest {
+    inner: GreatestLeast,
+}
+
+impl Default for SparkGreatest {
+    fn default() -> Self {
+        Self::new()
+    }
+}
+
+impl SparkGreatest {
+    pub fn new() -> Self {
+        Self {
+            inner: GreatestLeast::new(true, false),
+        }
+    }
+
+    /// Creates a `greatest` that coerces its arguments as Spark does with
+    /// `datafusion.execution.enable_ansi_mode` set to `enable_ansi_mode`.
+    fn new_with_ansi_mode(enable_ansi_mode: bool) -> Self {
+        Self {
+            inner: GreatestLeast::new(true, enable_ansi_mode),
+        }
+    }
+}
+
+/// Spark-compatible `least` expression.
+///
+/// <https://spark.apache.org/docs/latest/api/sql/index.html#least>
+#[user_doc(
+    doc_section(label = "Math Functions"),
+    description = "Returns the least value of all arguments, skipping NULLs. 
The result is \
+        NULL only if every argument is NULL. At least two arguments are 
required. The \
+        arguments are cast to a common type as in `greatest`. NaN is greater 
than every other \
+        value and `-0.0` equals `0.0`, also inside arrays and structs, and of 
equal values the \
+        first argument wins, so `least(0.0, -0.0)` is `0.0`. A NULL inside an 
array or struct \
+        is smaller than every other value, so `least(array(1, NULL), array(1, 
0))` is \
+        `[1, NULL]`. DataFusion's built-in `least` orders floats by IEEE 754 
total order, lets a \
+        later argument win a tie, orders a NULL inside an array or struct 
after every other \
+        value, accepts a single argument, and compares numbers with strings.",
+    syntax_example = "least(expr1, expr2[, ..., expr_n])",
+    sql_example = r#"```sql
+> SELECT least(10, 9, 2, 4, 3);
+2
+> SELECT least(NULL, 2, NULL);
+2
+> SELECT least(1.0, 'NaN'::double);
+1.0
+```"#,
+    argument(
+        name = "expr1, expr2, ..., expr_n",
+        description = "Expressions of an orderable type that share a common 
type. NULLs are \
+            skipped."
+    )
+)]
+#[derive(Debug, PartialEq, Eq, Hash)]
+pub struct SparkLeast {
+    inner: GreatestLeast,
+}
+
+impl Default for SparkLeast {
+    fn default() -> Self {
+        Self::new()
+    }
+}
+
+impl SparkLeast {
+    pub fn new() -> Self {
+        Self {
+            inner: GreatestLeast::new(false, false),
+        }
+    }
+
+    /// Creates a `least` that coerces its arguments as Spark does with
+    /// `datafusion.execution.enable_ansi_mode` set to `enable_ansi_mode`.
+    fn new_with_ansi_mode(enable_ansi_mode: bool) -> Self {
+        Self {
+            inner: GreatestLeast::new(false, enable_ansi_mode),
+        }
+    }
+}
+
+macro_rules! impl_greatest_least_udf {
+    ($udf:ident) => {
+        impl ScalarUDFImpl for $udf {
+            fn name(&self) -> &str {
+                self.inner.name()
+            }
+
+            fn signature(&self) -> &Signature {
+                &self.inner.signature
+            }
+
+            fn coerce_types(&self, arg_types: &[DataType]) -> 
Result<Vec<DataType>> {
+                self.inner.coerce_types(arg_types)
+            }
+
+            fn return_type(&self, arg_types: &[DataType]) -> Result<DataType> {
+                self.inner.check_arg_count(arg_types.len(), true)?;
+                Ok(arg_types[0].clone())
+            }
+
+            fn return_field_from_args(&self, args: ReturnFieldArgs) -> 
Result<FieldRef> {
+                self.inner.check_arg_count(args.arg_fields.len(), true)?;
+                // As in Spark, the result is nullable only if every argument 
is.
+                let nullable = args.arg_fields.iter().all(|f| f.is_nullable());
+                Ok(Arc::new(Field::new(
+                    self.name(),
+                    args.arg_fields[0].data_type().clone(),
+                    nullable,
+                )))
+            }
+
+            fn with_updated_config(&self, config: &ConfigOptions) -> 
Option<ScalarUDF> {
+                Some(ScalarUDF::from(Self::new_with_ansi_mode(
+                    config.execution.enable_ansi_mode,
+                )))
+            }
+
+            fn invoke_with_args(
+                &self,
+                args: ScalarFunctionArgs,
+            ) -> Result<ColumnarValue> {
+                self.inner.invoke(args)
+            }
+
+            fn documentation(&self) -> Option<&Documentation> {
+                self.doc()
+            }
+        }
+    };
+}
+
+impl_greatest_least_udf!(SparkGreatest);
+impl_greatest_least_udf!(SparkLeast);
+
+/// The implementation shared by [`SparkGreatest`] and [`SparkLeast`].
+#[derive(Debug, PartialEq, Eq, Hash)]
+struct GreatestLeast {
+    signature: Signature,
+    greatest: bool,
+    /// Whether to coerce as Spark's `AnsiTypeCoercion` does, rather than 
`TypeCoercion`.
+    ansi_mode: bool,
+}
+
+/// Spark orders a NULL inside an array or struct before every other value.
+const SORT_OPTIONS: SortOptions = SortOptions {
+    descending: false,
+    nulls_first: true,
+};
+
+impl GreatestLeast {
+    fn new(greatest: bool, ansi_mode: bool) -> Self {
+        Self {
+            signature: Signature::user_defined(Volatility::Immutable),
+            greatest,
+            ansi_mode,
+        }
+    }
+
+    fn name(&self) -> &'static str {
+        if self.greatest { "greatest" } else { "least" }
+    }
+
+    fn check_arg_count(&self, count: usize, planning: bool) -> Result<()> {
+        if count > 1 {
+            return Ok(());
+        }
+        let message = format!(
+            "[WRONG_NUM_ARGS.WITHOUT_SUGGESTION] The `{}` requires > 1 
parameters but the \
+             actual number is {count}. Please, refer to \
+             'https://spark.apache.org/docs/latest/sql-ref-functions.html' for 
a fix. \
+             SQLSTATE: 42605",
+            self.name()
+        );
+        Err(if planning {
+            DataFusionError::Plan(message)
+        } else {
+            DataFusionError::Execution(message)
+        })
+    }
+
+    /// Spark's `TypeCoercion` rule for `Greatest` and `Least`: every argument 
is cast to
+    /// `findWiderTypeWithoutStringPromotion` of all the argument types, and 
the result must be
+    /// orderable.
+    fn coerce_types(&self, arg_types: &[DataType]) -> Result<Vec<DataType>> {
+        self.check_arg_count(arg_types.len(), true)?;
+        let common = arg_types
+            .iter()
+            .skip(1)
+            .try_fold(arg_types[0].clone(), |common, data_type| {
+                wider_type(&common, data_type, self.ansi_mode)
+            });
+        let Some(common) = common else {
+            return plan_err!(
+                "[DATATYPE_MISMATCH.DATA_DIFF_TYPES] Input to `{}` should all 
be the same \
+                 type, but it's [{}]. SQLSTATE: 42K09",
+                self.name(),
+                arg_types
+                    .iter()
+                    .map(|t| format!("\"{}\"", spark_sql_type(t)))
+                    .collect::<Vec<_>>()
+                    .join(", ")
+            );
+        };
+        if !is_orderable(&common) {
+            return plan_err!(
+                "[DATATYPE_MISMATCH.INVALID_ORDERING_TYPE] The `{}` does not 
support ordering \
+                 on type \"{}\". SQLSTATE: 42K09",
+                self.name(),
+                spark_sql_type(&common)
+            );
+        }
+        Ok(vec![common; arg_types.len()])
+    }
+
+    fn invoke(&self, args: ScalarFunctionArgs) -> Result<ColumnarValue> {
+        self.check_arg_count(args.args.len(), false)?;
+        let data_type = args.return_field.data_type();
+        let all_scalars = args
+            .args
+            .iter()
+            .all(|arg| matches!(arg, ColumnarValue::Scalar(_)));
+        let rows = if all_scalars { 1 } else { args.number_rows };
+
+        if data_type.is_null() {
+            return Ok(if all_scalars {
+                ColumnarValue::Scalar(ScalarValue::Null)
+            } else {
+                ColumnarValue::Array(new_null_array(&DataType::Null, rows))
+            });
+        }
+
+        // The planner casts every argument to the common type, but a field 
name or the
+        // nullability of a nested field can still differ when the function is 
called directly,
+        // and `zip` needs identical types.
+        let to_array = |arg: &ColumnarValue, rows: usize| -> Result<ArrayRef> {
+            let array = arg.to_array(rows)?;
+            Ok(if array.data_type() == data_type {
+                array
+            } else {
+                cast(&array, data_type)?
+            })
+        };
+        // Nested floats are compared in a copy where `-0.0` is `0.0` and 
every NaN is the
+        // canonical NaN, where Arrow's total order agrees with Spark's. The 
result keeps the
+        // original. Flat floats are compared in place by 
`spark_float_ordered`.
+        let normalize = data_type.is_nested() && contains_float(data_type);
+        let comparable = |array: &ArrayRef| -> Result<ArrayRef> {
+            if normalize {
+                normalize_array(array)
+            } else {
+                Ok(Arc::clone(array))
+            }
+        };
+
+        let mut result = to_array(&args.args[0], rows)?;
+        let mut result_cmp = comparable(&result)?;
+        for arg in &args.args[1..] {
+            let candidate = match arg {
+                // A NULL never replaces the result.
+                ColumnarValue::Scalar(scalar) if scalar.is_null() => continue,
+                ColumnarValue::Scalar(_) => {
+                    let value = to_array(arg, 1)?;
+                    let cmp = comparable(&value)?;
+                    Candidate {
+                        value,
+                        cmp,
+                        scalar: true,
+                    }
+                }
+                ColumnarValue::Array(_) => {
+                    let value = to_array(arg, rows)?;
+                    let cmp = comparable(&value)?;
+                    Candidate {
+                        value,
+                        cmp,
+                        scalar: false,
+                    }
+                }
+            };
+            let take = self.replaces(&candidate, &result, &result_cmp)?;
+            let take = BooleanArray::new(take, None);
+            let new_result = zip(&take, candidate.value_datum().as_ref(), 
&result)?;
+            result_cmp = if normalize {
+                zip(&take, candidate.cmp_datum().as_ref(), &result_cmp)?
+            } else {
+                Arc::clone(&new_result)
+            };
+            result = new_result;
+        }
+
+        if all_scalars {
+            Ok(ColumnarValue::Scalar(ScalarValue::try_from_array(
+                &result, 0,
+            )?))
+        } else {
+            Ok(ColumnarValue::Array(result))
+        }
+    }
+
+    /// For each row, whether `candidate` replaces the current result: it is 
not NULL, and
+    /// either the result is NULL or the candidate ranks strictly before it.
+    fn replaces(
+        &self,
+        candidate: &Candidate,
+        current: &ArrayRef,
+        current_cmp: &ArrayRef,
+    ) -> Result<BooleanBuffer> {
+        let len = current.len();
+        let current_nulls = current.logical_nulls();
+        let candidate_nulls = if candidate.scalar {
+            // A NULL constant is skipped before this is called.
+            None
+        } else {
+            candidate.value.logical_nulls()
+        };
+
+        if !current.data_type().is_nested() {
+            // Where either side is NULL the comparison's value is arbitrary, 
but such rows are
+            // decided by the null masks below.
+            let mut take = match current.data_type() {
+                DataType::Float32 => spark_float_ordered::<Float32Type>(
+                    &candidate.cmp,
+                    candidate.scalar,
+                    current_cmp,
+                    self.greatest,
+                ),
+                DataType::Float64 => spark_float_ordered::<Float64Type>(
+                    &candidate.cmp,
+                    candidate.scalar,
+                    current_cmp,
+                    self.greatest,
+                ),
+                _ => {
+                    let candidate_cmp = candidate.cmp_datum();
+                    let ordered = if self.greatest {
+                        gt(candidate_cmp.as_ref(), current_cmp)?
+                    } else {
+                        lt(candidate_cmp.as_ref(), current_cmp)?
+                    };
+                    ordered.values().clone()
+                }
+            };
+            if let Some(nulls) = &current_nulls {
+                take = &take | &!nulls.inner();
+            }
+            if let Some(nulls) = &candidate_nulls {
+                take = &take & nulls.inner();
+            }
+            return Ok(take);
+        }
+
+        let compare =
+            make_comparator(candidate.cmp.as_ref(), current_cmp.as_ref(), 
SORT_OPTIONS)?;
+        let scalar = candidate.scalar;
+        Ok(BooleanBuffer::collect_bool(len, |row| {
+            let candidate_row = if scalar { 0 } else { row };
+            if candidate_nulls
+                .as_ref()
+                .is_some_and(|nulls| nulls.is_null(candidate_row))
+            {
+                return false;
+            }
+            if current_nulls
+                .as_ref()
+                .is_some_and(|nulls| nulls.is_null(row))
+            {
+                return true;
+            }
+            let ordering = compare(candidate_row, row);
+            if self.greatest {
+                ordering.is_gt()
+            } else {
+                ordering.is_lt()
+            }
+        }))
+    }
+}
+
+/// For each row, whether `candidate` ranks strictly before `current` in 
Spark's float order,
+/// where NaN is greater than every other value and `-0.0` equals `0.0`. A 
scalar candidate is
+/// a one-row array.
+fn spark_float_ordered<T>(
+    candidate: &ArrayRef,
+    scalar: bool,
+    current: &ArrayRef,
+    greatest: bool,
+) -> BooleanBuffer
+where
+    T: ArrowPrimitiveType,
+    T::Native: Float,
+{
+    let candidate = candidate.as_primitive::<T>().values();
+    let current = current.as_primitive::<T>().values();
+    // IEEE 754 `>` already treats `-0.0` as equal to `0.0`, so only NaN needs 
handling.
+    let gt = |a: T::Native, b: T::Native| {
+        if a.is_nan() {
+            !b.is_nan()
+        } else {
+            !b.is_nan() && a > b
+        }
+    };
+    BooleanBuffer::collect_bool(current.len(), |row| {
+        let c = candidate[if scalar { 0 } else { row }];
+        let r = current[row];
+        if greatest { gt(c, r) } else { gt(r, c) }
+    })

Review Comment:
   Could `spark_float_ordered` slice the candidate to `current.len()` before 
the loop and compare without branches? When the candidate is a column, this 
loop doesn't vectorize. The compiler can't tie `candidate`'s length to 
`current`'s, so every row keeps its bounds checks, and the two `is_nan` tests 
are branches. Here is the inner loop of a release build of `invoke` on aarch64, 
for `greatest` with a column candidate:
   
   ```
   cmp   x15, x14
   b.eq  LBB784_532          ; candidate[row] out of bounds, calls 
panic_bounds_check
   ...
   cmp   x16, x1
   b.hs  LBB784_528          ; current[row] out of bounds, calls 
panic_bounds_check
   ldr   d0, [x16, x14, lsl #3]
   ...
   ldr   d1, [x16, x14, lsl #3]
   fcmp  d0, d0
   b.vs  LBB784_266          ; candidate is NaN
   fcmp  d1, d1
   b.vs  LBB784_267          ; current is NaN
   fcmp  d0, d1
   cset  w16, gt
   ```
   
   With the change below, the column case compiles to packed compares with no 
branch per row: `fcmgt.2d` and `fcmeq.2d` over eight doubles per iteration on 
aarch64, and `cmpltpd` and `cmpunordpd` on x86_64. `(a > b) | (a.is_nan() & 
!b.is_nan())` gives the same result as the current closure for every pair, 
because `a > b` is already false when either side is NaN. The constant case 
already vectorizes, because `c` doesn't change inside the loop. I haven't 
benchmarked this. Could you run `benches/greatest_least.rs` with it?
   
   ```suggestion
       let candidate: &[T::Native] = candidate.as_primitive::<T>().values();
       let current: &[T::Native] = current.as_primitive::<T>().values();
       // IEEE 754 `>` already treats `-0.0` as equal to `0.0` and is false 
when either side is NaN.
       let gt = |a: T::Native, b: T::Native| (a > b) | (a.is_nan() & 
!b.is_nan());
       let len = current.len();
       if scalar {
           let c = candidate[0];
           if greatest {
               BooleanBuffer::collect_bool(len, |row| gt(c, current[row]))
           } else {
               BooleanBuffer::collect_bool(len, |row| gt(current[row], c))
           }
       } else {
           // Slicing first lets the compiler drop the bounds check on every 
row.
           let candidate = &candidate[..len];
           if greatest {
               BooleanBuffer::collect_bool(len, |row| gt(candidate[row], 
current[row]))
           } else {
               BooleanBuffer::collect_bool(len, |row| gt(current[row], 
candidate[row]))
           }
       }
   ```



-- 
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]

Reply via email to