mbutrovich commented on code in PR #332:
URL: https://github.com/apache/datafusion-spark/pull/332#discussion_r4615378605
##########
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) = ¤t_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:
> With the change below, the column case compiles to packed compares with no
branch per row
That overstated it, and the comment I suggested for the slice is wrong. At
78623c6 the packed loop covers most of each 64-row word, but `collect_bool`
leaves the first row and the last few rows of every word (for Float64, 8 of 64
on aarch64 and 4 of 64 on x86_64) to a scalar loop that keeps its bounds
checks. That scalar loop has no NaN branches anymore. Removing `let candidate =
&candidate[..len];` leaves the packed loop unchanged on both targets, so the
branchless `gt` is what vectorizes it. The slice only saves one check per word
on aarch64 and one of two checks per scalar row on x86_64.
Could we drop the slice and its comment at [lines
485-487](https://github.com/apache/datafusion-spark/blob/78623c670c8fbdf8658704ece1e4c3b48678bcd0/crates/spark/src/function/math/greatest_least.rs#L485-L487)?
The code would be shorter and keep the gain. I haven't benchmarked it without
the slice.
--
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]