This is an automated email from the ASF dual-hosted git repository. github-merge-queue[bot] pushed a commit to branch gh-readonly-queue/main/pr-23804-1bdff19402b62bad04f6c9cc8d5817f546a2fd7d in repository https://gitbox.apache.org/repos/asf/datafusion.git
commit 7fb2e2c7a6acbad5443c2631d7232b340160fd86 Author: Burak Şen <[email protected]> AuthorDate: Thu Jul 23 17:48:09 2026 +0300 fix: do not treat concat as preserving lexicographical ordering (#23804) ## Which issue does this PR close? - Closes #23793. ## Rationale for this change Please check the issue details but main idea is concat does not guarantee lexicographical ordering ## What changes are included in this PR? Main change is simply deleting `preserves_lex_ordering` method from concat and let it fallback to default `false`. Also added relevant tests and adjusted comments ## Are these changes tested? Yes adjusted existing and added new tests ## Are there any user-facing changes? No api changes but there is a behavior change I think on optimization part for concat --- datafusion/expr-common/src/sort_properties.rs | 3 +- datafusion/expr/src/udf.rs | 2 - datafusion/functions/src/string/concat.rs | 5 -- .../src/equivalence/properties/dependency.rs | 72 +++---------------- .../test_files/monotonic_projection_test.slt | 84 ++++++++++++++++++++++ 5 files changed, 94 insertions(+), 72 deletions(-) diff --git a/datafusion/expr-common/src/sort_properties.rs b/datafusion/expr-common/src/sort_properties.rs index 5d17a34a96..04da574882 100644 --- a/datafusion/expr-common/src/sort_properties.rs +++ b/datafusion/expr-common/src/sort_properties.rs @@ -140,8 +140,7 @@ pub struct ExprProperties { /// the expression. Used to compute reliable bounds. pub range: Interval, /// Indicates whether the expression preserves lexicographical ordering - /// of its inputs. For example, string concatenation preserves ordering, - /// while addition does not. + /// of its inputs. pub preserves_lex_ordering: bool, } diff --git a/datafusion/expr/src/udf.rs b/datafusion/expr/src/udf.rs index e206ce8b29..4c51ff46f7 100644 --- a/datafusion/expr/src/udf.rs +++ b/datafusion/expr/src/udf.rs @@ -979,8 +979,6 @@ pub trait ScalarUDFImpl: Debug + DynEq + DynHash + Send + Sync + Any { /// Returns true if the function preserves lexicographical ordering based on /// the input ordering. - /// - /// For example, `concat(a || b)` preserves lexicographical ordering, but `abs(a)` does not. fn preserves_lex_ordering(&self, _inputs: &[ExprProperties]) -> Result<bool> { Ok(false) } diff --git a/datafusion/functions/src/string/concat.rs b/datafusion/functions/src/string/concat.rs index af51f66faa..1c1f6d6407 100644 --- a/datafusion/functions/src/string/concat.rs +++ b/datafusion/functions/src/string/concat.rs @@ -30,7 +30,6 @@ use datafusion_common::{ }; use datafusion_expr::expr::ScalarFunction; use datafusion_expr::simplify::{ExprSimplifyResult, SimplifyContext}; -use datafusion_expr::sort_properties::ExprProperties; use datafusion_expr::{ColumnarValue, Documentation, Expr, Volatility, lit}; use datafusion_expr::{ScalarFunctionArgs, ScalarUDFImpl, Signature}; use datafusion_macros::user_doc; @@ -253,10 +252,6 @@ impl ScalarUDFImpl for ConcatFunc { fn documentation(&self) -> Option<&Documentation> { self.doc() } - - fn preserves_lex_ordering(&self, _inputs: &[ExprProperties]) -> Result<bool> { - Ok(true) - } } pub(crate) fn deduce_return_type(arg_types: &[DataType]) -> DataType { diff --git a/datafusion/physical-expr/src/equivalence/properties/dependency.rs b/datafusion/physical-expr/src/equivalence/properties/dependency.rs index 2ebc71559f..d2a8c2f654 100644 --- a/datafusion/physical-expr/src/equivalence/properties/dependency.rs +++ b/datafusion/physical-expr/src/equivalence/properties/dependency.rs @@ -1011,7 +1011,7 @@ mod tests { } #[test] - fn test_ordering_equivalence_with_lex_monotonic_concat() -> Result<()> { + fn test_ordering_equivalence_with_non_lex_monotonic_concat() -> Result<()> { let schema = Arc::new(Schema::new(vec![ Field::new("a", DataType::Utf8, false), Field::new("b", DataType::Utf8, false), @@ -1033,28 +1033,23 @@ mod tests { // Assume existing ordering is [c ASC, a ASC, b ASC] let mut eq_properties = EquivalenceProperties::new(Arc::clone(&schema)); - eq_properties.add_ordering([ + let initial_ordering: LexOrdering = [ PhysicalSortExpr::new_default(Arc::clone(&col_c)).asc(), PhysicalSortExpr::new_default(Arc::clone(&col_a)).asc(), PhysicalSortExpr::new_default(Arc::clone(&col_b)).asc(), - ]); + ] + .into(); + + eq_properties.add_ordering(initial_ordering.clone()); // Add equality condition c = concat(a, b) eq_properties.add_equal_conditions(Arc::clone(&col_c), a_concat_b)?; let orderings = eq_properties.oeq_class(); - let expected_ordering1 = [PhysicalSortExpr::new_default(col_c).asc()].into(); - let expected_ordering2 = [ - PhysicalSortExpr::new_default(col_a).asc(), - PhysicalSortExpr::new_default(col_b).asc(), - ] - .into(); - - // The ordering should be [c ASC] and [a ASC, b ASC] - assert_eq!(orderings.len(), 2); - assert!(orderings.contains(&expected_ordering1)); - assert!(orderings.contains(&expected_ordering2)); + // The ordering should remain unchanged since concat is not lex-monotonic + assert_eq!(orderings.len(), 1); + assert!(orderings.contains(&initial_ordering)); Ok(()) } @@ -1101,55 +1096,6 @@ mod tests { Ok(()) } - #[test] - fn test_ordering_equivalence_with_concat_equality() -> Result<()> { - let schema = Arc::new(Schema::new(vec![ - Field::new("a", DataType::Utf8, false), - Field::new("b", DataType::Utf8, false), - Field::new("c", DataType::Utf8, false), - ])); - - let col_a = col("a", &schema)?; - let col_b = col("b", &schema)?; - let col_c = col("c", &schema)?; - - let a_concat_b = Arc::new(ScalarFunctionExpr::new( - "concat", - concat(), - vec![Arc::clone(&col_a), Arc::clone(&col_b)], - Field::new("f", DataType::Utf8, true).into(), - Arc::new(ConfigOptions::default()), - )) as _; - - // Assume existing ordering is [concat(a, b) ASC, a ASC, b ASC] - let mut eq_properties = EquivalenceProperties::new(Arc::clone(&schema)); - - eq_properties.add_ordering([ - PhysicalSortExpr::new_default(Arc::clone(&a_concat_b)).asc(), - PhysicalSortExpr::new_default(Arc::clone(&col_a)).asc(), - PhysicalSortExpr::new_default(Arc::clone(&col_b)).asc(), - ]); - - // Add equality condition c = concat(a, b) - eq_properties.add_equal_conditions(col_c, Arc::clone(&a_concat_b))?; - - let orderings = eq_properties.oeq_class(); - - let expected_ordering1 = [PhysicalSortExpr::new_default(a_concat_b).asc()].into(); - let expected_ordering2 = [ - PhysicalSortExpr::new_default(col_a).asc(), - PhysicalSortExpr::new_default(col_b).asc(), - ] - .into(); - - // The ordering should be [c ASC] and [a ASC, b ASC] - assert_eq!(orderings.len(), 2); - assert!(orderings.contains(&expected_ordering1)); - assert!(orderings.contains(&expected_ordering2)); - - Ok(()) - } - #[test] fn test_requirements_compatible() -> Result<()> { let schema = Arc::new(Schema::new(vec![ diff --git a/datafusion/sqllogictest/test_files/monotonic_projection_test.slt b/datafusion/sqllogictest/test_files/monotonic_projection_test.slt index 7feefc169f..0045e51715 100644 --- a/datafusion/sqllogictest/test_files/monotonic_projection_test.slt +++ b/datafusion/sqllogictest/test_files/monotonic_projection_test.slt @@ -168,3 +168,87 @@ physical_plan 03)----ProjectionExec: expr=[CAST(a@0 + b@1 AS Int64) as sum_expr, a@0 as a, b@1 as b] 04)------RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1, maintains_sort_order=true 05)--------DataSourceExec: file_groups={1 group: [[WORKSPACE_ROOT/datafusion/core/tests/data/window_2.csv]]}, projection=[a, b], output_ordering=[a@0 ASC NULLS LAST, b@1 ASC NULLS LAST], file_type=csv, has_header=true + +# concat(a, b) is not lexicographically ordered just because a is ordered: +# "a" < "a0", but "a1" > "a01". The projected result still needs a sort. +query I +COPY ( + SELECT * FROM (VALUES ('a', '1'), ('a0', '1')) AS t(a, b) ORDER BY a +) TO 'test_files/scratch/monotonic_projection_test/concat_ordered.parquet'; +---- +2 + +statement ok +CREATE EXTERNAL TABLE concat_ordered (a VARCHAR, b VARCHAR) +STORED AS PARQUET +WITH ORDER (a) +WITH ORDER (b) +LOCATION 'test_files/scratch/monotonic_projection_test/concat_ordered.parquet'; + +query TT +EXPLAIN +SELECT concat(a, b) AS c +FROM concat_ordered +ORDER BY c; +---- +logical_plan +01)Sort: c ASC NULLS LAST +02)--Projection: concat(concat_ordered.a, concat_ordered.b) AS c +03)----TableScan: concat_ordered projection=[a, b] +physical_plan +01)SortExec: expr=[c@0 ASC NULLS LAST], preserve_partitioning=[false] +02)--DataSourceExec: file_groups={1 group: [[WORKSPACE_ROOT/datafusion/sqllogictest/test_files/scratch/monotonic_projection_test/concat_ordered.parquet]]}, projection=[concat(a@0, b@1) as c], file_type=parquet + +query T +SELECT concat(a, b) AS c +FROM concat_ordered +ORDER BY c; +---- +a01 +a1 + +# An ordering on (c, a, b) does not imply an ordering on (a, b), even when +# FilterExec establishes c = concat(a, b). EnsureRequirements must retain the +# sort required by ORDER BY a, b. +query I +COPY ( + SELECT concat(a, b) AS c, a, b + FROM (VALUES ('a0', '1'), ('a', '1')) AS t(a, b) + ORDER BY c, a, b +) TO 'test_files/scratch/monotonic_projection_test/concat_equality_ordered.parquet'; +---- +2 + +statement ok +CREATE EXTERNAL TABLE concat_equality_ordered (c VARCHAR, a VARCHAR, b VARCHAR) +STORED AS PARQUET +WITH ORDER (c, a, b) +LOCATION 'test_files/scratch/monotonic_projection_test/concat_equality_ordered.parquet'; + +query TT +EXPLAIN +SELECT a, b +FROM concat_equality_ordered +WHERE c = concat(a, b) +ORDER BY a, b; +---- +logical_plan +01)Sort: concat_equality_ordered.a ASC NULLS LAST, concat_equality_ordered.b ASC NULLS LAST +02)--Projection: concat_equality_ordered.a, concat_equality_ordered.b +03)----Filter: concat_equality_ordered.c = concat(concat_equality_ordered.a, concat_equality_ordered.b) +04)------TableScan: concat_equality_ordered projection=[c, a, b], partial_filters=[concat_equality_ordered.c = concat(concat_equality_ordered.a, concat_equality_ordered.b)] +physical_plan +01)SortPreservingMergeExec: [a@0 ASC NULLS LAST, b@1 ASC NULLS LAST] +02)--SortExec: expr=[a@0 ASC NULLS LAST, b@1 ASC NULLS LAST], preserve_partitioning=[true] +03)----FilterExec: c@0 = concat(a@1, b@2), projection=[a@1, b@2] +04)------RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1, maintains_sort_order=true +05)--------DataSourceExec: file_groups={1 group: [[WORKSPACE_ROOT/datafusion/sqllogictest/test_files/scratch/monotonic_projection_test/concat_equality_ordered.parquet]]}, projection=[c, a, b], output_ordering=[c@0 ASC NULLS LAST, a@1 ASC NULLS LAST, b@2 ASC NULLS LAST], file_type=parquet, predicate=c@0 = concat(a@1, b@2) + +query TT +SELECT a, b +FROM concat_equality_ordered +WHERE c = concat(a, b) +ORDER BY a, b; +---- +a 1 +a0 1 --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
