You are viewing a plain text version of this content. The canonical link for it is here.
Posted to github@datafusion.apache.org by "rluvaton (via GitHub)" <gi...@apache.org> on 2026/07/22 15:04:51 UTC
[PR] Debug why sort ordering get messed up [datafusion]
rluvaton opened a new pull request, #23807:
URL: https://github.com/apache/datafusion/pull/23807
## Which issue does this PR close?
<!--
We generally require a GitHub issue to be filed for all bug fixes and enhancements and this helps us generate change logs for our releases. You can link an issue to this PR using the GitHub syntax. For example `Closes #123` indicates that this PR will close issue #123.
-->
- Closes #.
Related to:
- #16217
## Rationale for this change
To be able to keep the same sorting order allowing for more optimizations
## What changes are included in this PR?
added
## Are these changes tested?
yes
## Are there any user-facing changes?
yes, breaking change, added `strictly_order_preserving` property to `ExprProperties`
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] Allow expression to report whether they keep the same ordering of the input (`a.cmp(b) == f(a).cmp(f(b))`) opening up for more optimization [datafusion]
Posted by "getChan (via GitHub)" <gi...@apache.org>.
getChan commented on code in PR #23807:
URL: https://github.com/apache/datafusion/pull/23807#discussion_r3632161143
##########
datafusion/physical-expr/src/expressions/cast.rs:
##########
@@ -214,8 +214,18 @@ pub(crate) fn cast_expr_properties(
target_type: &DataType,
) -> Result<ExprProperties> {
let unbounded = Interval::make_unbounded(target_type)?;
- if is_order_preserving_cast_family(&child.range.data_type(), target_type) {
- Ok(child.clone().with_range(unbounded))
+ let source_type = child.range.data_type();
+ // A widening cast is additionally one-to-one, so it is strictly
Review Comment:
I may not have full context, so please feel free to ignore this if it's a misunderstanding.
`CastExpr::check_bigger_cast` includes `Int32 -> Float32` and `Int64 -> Float64`. Due to float mantissa limits, large integers
lose precision and can collapse to the same float value (e.g. `16_777_216_i32 as f32 == 16_777_217_i32 as f32`), so they are not strictly 1-to-1
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] Allow expression to report whether they keep the same ordering of the input (`a.cmp(b) == f(a).cmp(f(b))`) opening up for more optimization [datafusion]
Posted by "rluvaton (via GitHub)" <gi...@apache.org>.
rluvaton commented on code in PR #23807:
URL: https://github.com/apache/datafusion/pull/23807#discussion_r3651093020
##########
datafusion/expr/src/udf.rs:
##########
@@ -981,10 +986,44 @@ pub trait ScalarUDFImpl: Debug + DynEq + DynHash + Send + Sync + Any {
/// the input ordering.
///
/// For example, `concat(a || b)` preserves lexicographical ordering, but `abs(a)` does not.
+ ///
+ /// This is a *non-strict* (monotone) property: distinct inputs may map to
+ /// equal outputs. See [`Self::strictly_order_preserving`] for a related
+ /// strict property and [`ExprProperties::strictly_order_preserving`] for
+ /// an explanation of the difference.
fn preserves_lex_ordering(&self, _inputs: &[ExprProperties]) -> Result<bool> {
Ok(false)
}
+ /// Returns true if the function is strictly order-preserving with respect
Review Comment:
`output_ordering` does not tell you whether you can reuse the existing ordering when you have multiple order by keys (with how ties are handled)
##########
datafusion/expr/src/udf.rs:
##########
@@ -981,10 +986,44 @@ pub trait ScalarUDFImpl: Debug + DynEq + DynHash + Send + Sync + Any {
/// the input ordering.
///
/// For example, `concat(a || b)` preserves lexicographical ordering, but `abs(a)` does not.
+ ///
+ /// This is a *non-strict* (monotone) property: distinct inputs may map to
+ /// equal outputs. See [`Self::strictly_order_preserving`] for a related
+ /// strict property and [`ExprProperties::strictly_order_preserving`] for
+ /// an explanation of the difference.
fn preserves_lex_ordering(&self, _inputs: &[ExprProperties]) -> Result<bool> {
Ok(false)
}
+ /// Returns true if the function is strictly order-preserving with respect
+ /// to its `Ordered` inputs: assuming those inputs advance simultaneously
+ /// (component-wise, i.e. all of them are sorted in the data), the output
+ /// is ordered in the same direction, equal outputs can only result from
+ /// equal values of those inputs (i.e. the mapping is one-to-one), and
+ /// nulls map to nulls.
+ ///
+ /// i.e. setting this to true means that `a.cmp(b) == f(a).cmp(f(b))`
+ ///
+ /// This is not simply a stricter [`Self::preserves_lex_ordering`] — the
+ /// two properties also assume different input orderings, and with
+ /// multiple ordered inputs neither implies the other. Monotone but
Review Comment:
moved
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] Allow expression to report whether they keep the same ordering of the input (`a.cmp(b) == f(a).cmp(f(b))`) opening up for more optimization [datafusion]
Posted by "rluvaton (via GitHub)" <gi...@apache.org>.
rluvaton commented on code in PR #23807:
URL: https://github.com/apache/datafusion/pull/23807#discussion_r3652101672
##########
datafusion/ffi/src/expr/expr_properties.rs:
##########
@@ -54,6 +54,9 @@ impl TryFrom<FFI_ExprProperties> for ExprProperties {
sort_properties,
range,
preserves_lex_ordering: value.preserves_lex_ordering,
+ // Not carried over the FFI boundary (it would break the ABI);
+ // stay conservative.
+ strictly_order_preserving: false,
Review Comment:
so I added the field 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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] Allow expression to report whether they keep the same ordering of the input (`a.cmp(b) == f(a).cmp(f(b))`) opening up for more optimization [datafusion]
Posted by "rluvaton (via GitHub)" <gi...@apache.org>.
rluvaton commented on code in PR #23807:
URL: https://github.com/apache/datafusion/pull/23807#discussion_r3632197857
##########
datafusion/physical-expr/src/expressions/cast.rs:
##########
@@ -214,8 +214,18 @@ pub(crate) fn cast_expr_properties(
target_type: &DataType,
) -> Result<ExprProperties> {
let unbounded = Interval::make_unbounded(target_type)?;
- if is_order_preserving_cast_family(&child.range.data_type(), target_type) {
- Ok(child.clone().with_range(unbounded))
+ let source_type = child.range.data_type();
+ // A widening cast is additionally one-to-one, so it is strictly
Review Comment:
You are right, unfortunately this moved from here (so no logic change has been made):
https://github.com/apache/datafusion/blob/e271f65c9f8188cb6b1876da099646f396e34e00/datafusion/physical-expr/src/equivalence/properties/mod.rs#L215
##########
datafusion/ffi/src/expr/expr_properties.rs:
##########
@@ -54,6 +54,9 @@ impl TryFrom<FFI_ExprProperties> for ExprProperties {
sort_properties,
range,
preserves_lex_ordering: value.preserves_lex_ordering,
+ // Not carried over the FFI boundary (it would break the ABI);
+ // stay conservative.
+ strictly_order_preserving: false,
Review Comment:
Should I make breaking change in FFI (by adding the field) while I'm here to avoid 2 breaking changes? I'm not really familiar with this module
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] Allow expression to report whether they keep the same ordering of the input (`a.cmp(b) == f(a).cmp(f(b))`) opening up for more optimization [datafusion]
Posted by "codecov-commenter (via GitHub)" <gi...@apache.org>.
codecov-commenter commented on PR #23807:
URL: https://github.com/apache/datafusion/pull/23807#issuecomment-5051200118
## [Codecov](https://app.codecov.io/gh/apache/datafusion/pull/23807?dropdown=coverage&src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) Report
:x: Patch coverage is `88.29787%` with `11 lines` in your changes missing coverage. Please review.
:white_check_mark: Project coverage is 80.71%. Comparing base ([`ed22a4a`](https://app.codecov.io/gh/apache/datafusion/commit/ed22a4aa19693fccfd47a5beded42d4be1ac3dee?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)) to head ([`7305547`](https://app.codecov.io/gh/apache/datafusion/commit/73055477288c4a56b21c5681872dcb6c9d5c1f9b?dropdown=coverage&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache)).
:warning: Report is 18 commits behind head on main.
| [Files with missing lines](https://app.codecov.io/gh/apache/datafusion/pull/23807?dropdown=coverage&src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) | Patch % | Lines |
|---|---|---|
| [...tafusion/physical-expr/src/equivalence/ordering.rs](https://app.codecov.io/gh/apache/datafusion/pull/23807?src=pr&el=tree&filepath=datafusion%2Fphysical-expr%2Fsrc%2Fequivalence%2Fordering.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-ZGF0YWZ1c2lvbi9waHlzaWNhbC1leHByL3NyYy9lcXVpdmFsZW5jZS9vcmRlcmluZy5ycw==) | 83.33% | [3 Missing and 2 partials :warning: ](https://app.codecov.io/gh/apache/datafusion/pull/23807?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
| [...on/physical-expr/src/equivalence/properties/mod.rs](https://app.codecov.io/gh/apache/datafusion/pull/23807?src=pr&el=tree&filepath=datafusion%2Fphysical-expr%2Fsrc%2Fequivalence%2Fproperties%2Fmod.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-ZGF0YWZ1c2lvbi9waHlzaWNhbC1leHByL3NyYy9lcXVpdmFsZW5jZS9wcm9wZXJ0aWVzL21vZC5ycw==) | 84.84% | [0 Missing and 5 partials :warning: ](https://app.codecov.io/gh/apache/datafusion/pull/23807?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
| [datafusion/physical-expr/src/scalar\_function.rs](https://app.codecov.io/gh/apache/datafusion/pull/23807?src=pr&el=tree&filepath=datafusion%2Fphysical-expr%2Fsrc%2Fscalar_function.rs&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache#diff-ZGF0YWZ1c2lvbi9waHlzaWNhbC1leHByL3NyYy9zY2FsYXJfZnVuY3Rpb24ucnM=) | 50.00% | [0 Missing and 1 partial :warning: ](https://app.codecov.io/gh/apache/datafusion/pull/23807?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache) |
<details><summary>Additional details and impacted files</summary>
```diff
@@ Coverage Diff @@
## main #23807 +/- ##
==========================================
+ Coverage 80.69% 80.71% +0.02%
==========================================
Files 1089 1089
Lines 368447 368979 +532
Branches 368447 368979 +532
==========================================
+ Hits 297332 297836 +504
+ Misses 53405 53376 -29
- Partials 17710 17767 +57
```
</details>
[:umbrella: View full report in Codecov by Harness](https://app.codecov.io/gh/apache/datafusion/pull/23807?dropdown=coverage&src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=apache).
<details><summary> :rocket: New features to boost your workflow: </summary>
- :snowflake: [Test Analytics](https://docs.codecov.com/docs/test-analytics): Detect flaky tests, report on failures, and find test suite problems.
- :package: [JS Bundle Analysis](https://docs.codecov.com/docs/javascript-bundle-analysis): Save yourself from yourself by tracking and limiting bundle sizes in JS merges.
</details>
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] Allow expression to report whether they keep the same ordering of the input (`a.cmp(b) == f(a).cmp(f(b))`) opening up for more optimization [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #23807:
URL: https://github.com/apache/datafusion/pull/23807#discussion_r3656656014
##########
datafusion/expr-common/src/sort_properties.rs:
##########
@@ -141,7 +141,61 @@ pub struct ExprProperties {
pub range: Interval,
/// Indicates whether the expression preserves lexicographical ordering
/// of its inputs.
+ ///
+ /// This is a *non-strict* (monotone) property: inputs advancing in
+ /// lexicographical order never make the output decrease, but distinct
+ /// inputs may map to equal outputs (ties). See
+ /// [`Self::strictly_order_preserving`] for the strict variant and an
+ /// explanation of the difference.
pub preserves_lex_ordering: bool,
+ /// Indicates whether the expression is strictly order-preserving with
+ /// respect to its inputs that are `Ordered`: the output is ordered in the
+ /// same direction, equal outputs can only result from equal values of
+ /// those inputs (i.e. the mapping is one-to-one), and nulls map to nulls.
+ ///
+ /// i.e. setting this to true means that `a.cmp(b) == f(a).cmp(f(b))`
Review Comment:
👍
##########
datafusion/expr/src/udf.rs:
##########
@@ -979,10 +984,58 @@ pub trait ScalarUDFImpl: Debug + DynEq + DynHash + Send + Sync + Any {
/// Returns true if the function preserves lexicographical ordering based on
/// the input ordering.
+ ///
Review Comment:
I think it would be ok to keep these descriptions short and refer readers to the very nice SortProperties description
Eg. something like
```suggestion
/// See [`ExprProperties::preserves_lex_ordering`] for more details
```
##########
datafusion/expr-common/src/sort_properties.rs:
##########
@@ -141,7 +141,61 @@ pub struct ExprProperties {
pub range: Interval,
/// Indicates whether the expression preserves lexicographical ordering
/// of its inputs.
+ ///
+ /// This is a *non-strict* (monotone) property: inputs advancing in
+ /// lexicographical order never make the output decrease, but distinct
+ /// inputs may map to equal outputs (ties). See
+ /// [`Self::strictly_order_preserving`] for the strict variant and an
+ /// explanation of the difference.
pub preserves_lex_ordering: bool,
+ /// Indicates whether the expression is strictly order-preserving with
+ /// respect to its inputs that are `Ordered`: the output is ordered in the
+ /// same direction, equal outputs can only result from equal values of
+ /// those inputs (i.e. the mapping is one-to-one), and nulls map to nulls.
+ ///
+ /// i.e. setting this to true means that `a.cmp(b) == f(a).cmp(f(b))`
+ ///
+ /// # Difference from [`Self::preserves_lex_ordering`]
+ ///
+ /// The two properties differ in both their premise and their strictness:
+ ///
+ /// - `preserves_lex_ordering` assumes the inputs advance in
+ /// *lexicographical* order (a later input may decrease whenever an
+ /// earlier one increases), and only promises a non-decreasing output,
+ /// allowing distinct inputs to collapse into equal outputs; `floor`,
+ /// `date_trunc` and narrowing casts do exactly that.
+ /// - `strictly_order_preserving` assumes every `Ordered` input advances
+ /// *simultaneously* (component-wise, which is what actually holds when
+ /// all of them are sorted in the data), and promises a strict output:
+ /// equal outputs only from equal inputs.
+ ///
+ /// For an expression with a single ordered input the premises coincide,
+ /// and this field is simply the stronger claim: it implies
+ /// `preserves_lex_ordering`. With multiple ordered inputs, neither
+ /// implies the other: a lexicographical-ordering-preserving expression
Review Comment:
Thank you for clarifying the difference. This makes sense
##########
datafusion/functions/src/datetime/from_unixtime.rs:
##########
@@ -147,6 +148,24 @@ impl ScalarUDFImpl for FromUnixtimeFunc {
}
}
+ fn output_ordering(&self, inputs: &[ExprProperties]) -> Result<SortProperties> {
+ // The optional timezone argument must be a constant string and only
+ // affects the display metadata, not the stored epoch value, so the
+ // output ordering follows the first argument.
+ Ok(inputs[0].sort_properties)
+ }
+
+ fn preserves_lex_ordering(&self, _inputs: &[ExprProperties]) -> Result<bool> {
+ Ok(true)
+ }
+
+ fn strictly_order_preserving(&self, _inputs: &[ExprProperties]) -> Result<bool> {
+ // `from_unixtime` stores the input's exact `Int64` value as a
Review Comment:
👍
##########
datafusion/physical-expr/src/equivalence/ordering.rs:
##########
@@ -376,6 +376,48 @@ mod tests {
Ok(())
}
+ #[test]
+ fn test_ordering_satisfy_strictly_order_preserving() -> Result<()> {
+ let schema = Arc::new(Schema::new(vec![
+ Field::new("a", DataType::Int32, true),
+ Field::new("b", DataType::Int64, true),
+ ]));
+ let col_a = col("a", &schema)?;
+ let col_b = col("b", &schema)?;
+ let asc = SortOptions::default();
+ let ordering = vec![
+ PhysicalSortExpr::new(Arc::clone(&col_a), asc),
+ PhysicalSortExpr::new(Arc::clone(&col_b), asc),
+ ];
+ let eq_properties =
+ EquivalenceProperties::new_with_orderings(Arc::clone(&schema), [ordering]);
+
+ // A widening cast is strictly order-preserving: `a` is constant
+ // within each group of equal `CAST(a AS BIGINT)` values, so `b`
+ // remains sorted within those groups.
+ let widening = Arc::new(CastExpr::new(Arc::clone(&col_a), DataType::Int64, None))
+ as PhysicalExprRef;
+ assert!(eq_properties.ordering_satisfy(vec![
+ PhysicalSortExpr::new(widening, asc),
+ PhysicalSortExpr::new(Arc::clone(&col_b), asc),
+ ])?);
+
+ // A narrowing cast is only monotonic: it satisfies as a leading key,
+ // but it may collapse distinct `a` values, so `b` is not guaranteed
+ // to be sorted within its tie groups.
+ let narrowing = Arc::new(CastExpr::new(Arc::clone(&col_a), DataType::Int16, None))
+ as PhysicalExprRef;
+ assert!(eq_properties.ordering_satisfy(vec![PhysicalSortExpr::new(
+ Arc::clone(&narrowing),
+ asc
+ )])?);
+ assert!(!eq_properties.ordering_satisfy(vec![
Review Comment:
It does still satisfy col_a I think -- it might be nice to add an assert here that it does satisfy
##########
datafusion/physical-expr/src/equivalence/ordering.rs:
##########
@@ -376,6 +376,48 @@ mod tests {
Ok(())
}
+ #[test]
+ fn test_ordering_satisfy_strictly_order_preserving() -> Result<()> {
+ let schema = Arc::new(Schema::new(vec![
+ Field::new("a", DataType::Int32, true),
+ Field::new("b", DataType::Int64, true),
+ ]));
+ let col_a = col("a", &schema)?;
+ let col_b = col("b", &schema)?;
+ let asc = SortOptions::default();
+ let ordering = vec![
+ PhysicalSortExpr::new(Arc::clone(&col_a), asc),
Review Comment:
We could probably reduce the text here (and make it easier to read) maybe by creating
```rust
let ordering_a_b = PhysicalSortExpr::new(..., asc),
```
?
##########
datafusion/expr/src/udf.rs:
##########
@@ -979,10 +984,58 @@ pub trait ScalarUDFImpl: Debug + DynEq + DynHash + Send + Sync + Any {
/// Returns true if the function preserves lexicographical ordering based on
/// the input ordering.
+ ///
+ /// This is a *non-strict* (monotone) property: distinct inputs may map to
+ /// equal outputs. See [`Self::strictly_order_preserving`] for a related
+ /// strict property and [`ExprProperties::strictly_order_preserving`] for
+ /// an explanation of the difference.
fn preserves_lex_ordering(&self, _inputs: &[ExprProperties]) -> Result<bool> {
Ok(false)
}
+ /// Returns true if the function is strictly order-preserving with respect
+ /// to its `Ordered` inputs, i.e. `a.cmp(b) == f(a).cmp(f(b))`.
+ ///
+ /// # Examples
+ ///
+ /// * `from_unixtime(a)` returns `true`: it reinterprets the input integer
+ /// as a timestamp without changing the value, so distinct inputs yield
+ /// distinct, identically-ordered outputs.
+ /// * `floor(a)` and `date_trunc('day', a)` must return `false`: they are
+ /// monotone, but collapse distinct inputs into equal outputs.
+ /// * An addition over ordered, overflow-free inputs may return `true`
+ /// even though it does not preserve *lexicographical* ordering.
+ ///
+ /// # Definition
+ ///
+ /// Assuming the `Ordered` inputs advance simultaneously (component-wise,
+ /// i.e. all of them are sorted in the data), the output is ordered in the
+ /// same direction, equal outputs can only result from equal values of
+ /// those inputs (i.e. the mapping is one-to-one), and nulls map to nulls.
+ ///
+ /// This is not simply a stricter [`Self::preserves_lex_ordering`] - the
+ /// two properties also assume different input orderings, and with
+ /// multiple ordered inputs neither implies the other (see the examples
+ /// above). See [`ExprProperties::strictly_order_preserving`] for a
+ /// detailed comparison.
+ ///
+ /// # Relationship to [`Self::output_ordering`]
+ ///
+ /// [`Self::output_ordering`] describes *whether and in which direction*
+ /// the output is ordered, which justifies using the expression as the
+ /// **last** (or only) sort key. This property is an additional,
+ /// independent claim of injectivity that justifies keeping the **suffix**
+ /// sort keys as well: optimizers rely on it to substitute a sort key with
+ /// an expression computed from it - if data is sorted by `[x, y]`, it is
+ /// also sorted by `[expr(x), y]`, which only holds when equal `expr(x)`
+ /// values imply equal `x` values.
+ ///
+ /// When in doubt, return `false` (the default). The `inputs` properties
+ /// allow conditional answers, e.g. based on the ranges of the inputs.
+ fn strictly_order_preserving(&self, _inputs: &[ExprProperties]) -> Result<bool> {
+ Ok(false)
+ }
Review Comment:
Similarly I think here it would be ok to point back to ExprProperties to make sure the text stays consistent
```suggestion
///
/// See [`ExprProperties::strictly_order_preserving`] for more details
fn strictly_order_preserving(&self, _inputs: &[ExprProperties]) -> Result<bool> {
Ok(false)
}
```
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] Allow expression to report whether they keep the same ordering of the input (`a.cmp(b) == f(a).cmp(f(b))`) opening up for more optimization [datafusion]
Posted by "alamb (via GitHub)" <gi...@apache.org>.
alamb commented on code in PR #23807:
URL: https://github.com/apache/datafusion/pull/23807#discussion_r3647826426
##########
datafusion/expr/src/udf.rs:
##########
@@ -981,10 +986,44 @@ pub trait ScalarUDFImpl: Debug + DynEq + DynHash + Send + Sync + Any {
/// the input ordering.
///
/// For example, `concat(a || b)` preserves lexicographical ordering, but `abs(a)` does not.
+ ///
+ /// This is a *non-strict* (monotone) property: distinct inputs may map to
+ /// equal outputs. See [`Self::strictly_order_preserving`] for a related
+ /// strict property and [`ExprProperties::strictly_order_preserving`] for
+ /// an explanation of the difference.
fn preserves_lex_ordering(&self, _inputs: &[ExprProperties]) -> Result<bool> {
Ok(false)
}
+ /// Returns true if the function is strictly order-preserving with respect
Review Comment:
How is this related to the output_ordering method? I am wondering if we can extend that rather tan introduce a new method
https://docs.rs/datafusion/latest/datafusion/logical_expr/trait.ScalarUDFImpl.html#method.output_ordering
##########
datafusion/expr/src/udf.rs:
##########
@@ -981,10 +986,44 @@ pub trait ScalarUDFImpl: Debug + DynEq + DynHash + Send + Sync + Any {
/// the input ordering.
///
/// For example, `concat(a || b)` preserves lexicographical ordering, but `abs(a)` does not.
+ ///
+ /// This is a *non-strict* (monotone) property: distinct inputs may map to
+ /// equal outputs. See [`Self::strictly_order_preserving`] for a related
+ /// strict property and [`ExprProperties::strictly_order_preserving`] for
+ /// an explanation of the difference.
fn preserves_lex_ordering(&self, _inputs: &[ExprProperties]) -> Result<bool> {
Ok(false)
}
+ /// Returns true if the function is strictly order-preserving with respect
+ /// to its `Ordered` inputs: assuming those inputs advance simultaneously
+ /// (component-wise, i.e. all of them are sorted in the data), the output
+ /// is ordered in the same direction, equal outputs can only result from
+ /// equal values of those inputs (i.e. the mapping is one-to-one), and
+ /// nulls map to nulls.
+ ///
+ /// i.e. setting this to true means that `a.cmp(b) == f(a).cmp(f(b))`
+ ///
+ /// This is not simply a stricter [`Self::preserves_lex_ordering`] — the
+ /// two properties also assume different input orderings, and with
+ /// multiple ordered inputs neither implies the other. Monotone but
Review Comment:
It would have helped me to move these examples up to the top of the docs
##########
datafusion/ffi/src/expr/expr_properties.rs:
##########
@@ -54,6 +54,9 @@ impl TryFrom<FFI_ExprProperties> for ExprProperties {
sort_properties,
range,
preserves_lex_ordering: value.preserves_lex_ordering,
+ // Not carried over the FFI boundary (it would break the ABI);
+ // stay conservative.
+ strictly_order_preserving: false,
Review Comment:
cc @timsaucer
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] Allow expression to report whether they keep the same ordering of the input (`a.cmp(b) == f(a).cmp(f(b))`) opening up for more optimization [datafusion]
Posted by "getChan (via GitHub)" <gi...@apache.org>.
getChan commented on code in PR #23807:
URL: https://github.com/apache/datafusion/pull/23807#discussion_r3632161143
##########
datafusion/physical-expr/src/expressions/cast.rs:
##########
@@ -214,8 +214,18 @@ pub(crate) fn cast_expr_properties(
target_type: &DataType,
) -> Result<ExprProperties> {
let unbounded = Interval::make_unbounded(target_type)?;
- if is_order_preserving_cast_family(&child.range.data_type(), target_type) {
- Ok(child.clone().with_range(unbounded))
+ let source_type = child.range.data_type();
+ // A widening cast is additionally one-to-one, so it is strictly
Review Comment:
I may not have full context, so please feel free to ignore this if it's a misunderstanding.
`CastExpr::check_bigger_cast` includes `Int32 -> Float32` and `Int64 -> Float64`. Due to float mantissa limits, large integers lose precision and can collapse to the same float value (e.g. `16_777_216_i32 as f32 == 16_777_217_i32 as f32`), so they are not strictly 1-to-1
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] Allow expression to report whether they keep the same ordering of the input (`a.cmp(b) == f(a).cmp(f(b))`) opening up for more optimization [datafusion]
Posted by "rluvaton (via GitHub)" <gi...@apache.org>.
rluvaton commented on PR #23807:
URL: https://github.com/apache/datafusion/pull/23807#issuecomment-5079523832
> Thank you @rluvaton -- this idea here seems sound to me
>
> Can we get some sql logic / explain test that show some of the optimizations that this allows for (that `preserves_lex_ordering` does not)?
>
>
> I think having those examples would make sure we have a good / minimal API to build on -- without such "end visible facing" tests I fear we may implement some features that are not ever used
I did not want to add uses of this api in this PR to reduce the amount of code to review, do you still want me to do so?
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] Allow expression to report whether they keep the same ordering of the input (`a.cmp(b) == f(a).cmp(f(b))`) opening up for more optimization [datafusion]
Posted by "rluvaton (via GitHub)" <gi...@apache.org>.
rluvaton commented on code in PR #23807:
URL: https://github.com/apache/datafusion/pull/23807#discussion_r3652101309
##########
datafusion/ffi/src/expr/expr_properties.rs:
##########
@@ -54,6 +54,9 @@ impl TryFrom<FFI_ExprProperties> for ExprProperties {
sort_properties,
range,
preserves_lex_ordering: value.preserves_lex_ordering,
+ // Not carried over the FFI boundary (it would break the ABI);
+ // stay conservative.
+ strictly_order_preserving: false,
Review Comment:
I've read `.ai/skills/datafusion-ffi/SKILL.md` (ironic) and saw that it is ok to make breaking change, just not release them in a patch version
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] Allow expression to report whether they keep the same ordering of the input (`a.cmp(b) == f(a).cmp(f(b))`) opening up for more optimization [datafusion]
Posted by "getChan (via GitHub)" <gi...@apache.org>.
getChan commented on code in PR #23807:
URL: https://github.com/apache/datafusion/pull/23807#discussion_r3632278835
##########
datafusion/physical-expr/src/expressions/cast.rs:
##########
@@ -214,8 +214,18 @@ pub(crate) fn cast_expr_properties(
target_type: &DataType,
) -> Result<ExprProperties> {
let unbounded = Interval::make_unbounded(target_type)?;
- if is_order_preserving_cast_family(&child.range.data_type(), target_type) {
- Ok(child.clone().with_range(unbounded))
+ let source_type = child.range.data_type();
+ // A widening cast is additionally one-to-one, so it is strictly
Review Comment:
filed. https://github.com/apache/datafusion/issues/23808
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] Allow expression to report whether they keep the same ordering of the input (`a.cmp(b) == f(a).cmp(f(b))` opening up for more optimization [datafusion]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #23807:
URL: https://github.com/apache/datafusion/pull/23807#issuecomment-5048011578
<!-- semver-check-comment -->
Thank you for opening this pull request!
Reviewer note: [cargo-semver-checks](https://github.com/obi1kenobi/cargo-semver-checks) reported the current version number is not SemVer-compatible with the changes in this pull request (compared against the base branch).
<details>
<summary>Details</summary>
```
Cloning apache/main
Building datafusion v54.1.0 (current)
Built [ 110.292s] (current)
Parsing datafusion v54.1.0 (current)
Parsed [ 0.034s] (current)
Building datafusion v54.1.0 (baseline)
Built [ 107.568s] (baseline)
Parsing datafusion v54.1.0 (baseline)
Parsed [ 0.036s] (baseline)
Checking datafusion v54.1.0 -> v54.1.0 (no change; assume patch)
Checked [ 0.693s] 223 checks: 223 pass, 30 skip
Summary no semver update required
Finished [ 220.777s] datafusion
Building datafusion-expr v54.1.0 (current)
Built [ 28.294s] (current)
Parsing datafusion-expr v54.1.0 (current)
Parsed [ 0.076s] (current)
Building datafusion-expr v54.1.0 (baseline)
Built [ 28.321s] (baseline)
Parsing datafusion-expr v54.1.0 (baseline)
Parsed [ 0.082s] (baseline)
Checking datafusion-expr v54.1.0 -> v54.1.0 (no change; assume patch)
Checked [ 1.343s] 223 checks: 223 pass, 30 skip
Summary no semver update required
Finished [ 59.732s] datafusion-expr
Building datafusion-expr-common v54.1.0 (current)
Built [ 19.607s] (current)
Parsing datafusion-expr-common v54.1.0 (current)
Parsed [ 0.018s] (current)
Building datafusion-expr-common v54.1.0 (baseline)
Built [ 19.409s] (baseline)
Parsing datafusion-expr-common v54.1.0 (baseline)
Parsed [ 0.018s] (baseline)
Checking datafusion-expr-common v54.1.0 -> v54.1.0 (no change; assume patch)
Checked [ 0.208s] 223 checks: 222 pass, 1 fail, 0 warn, 30 skip
--- failure constructible_struct_adds_field: externally-constructible struct adds field ---
Description:
A pub struct constructible with a struct literal has a new pub field. Existing struct literals must be updated to include the new field.
ref: https://doc.rust-lang.org/reference/expressions/struct-expr.html
impl: https://github.com/obi1kenobi/cargo-semver-checks/tree/v0.49.0/src/lints/constructible_struct_adds_field.ron
Failed in:
field ExprProperties.strictly_order_preserving in /home/runner/work/datafusion/datafusion/datafusion/expr-common/src/sort_properties.rs:199
Summary semver requires new major version: 1 major and 0 minor checks failed
Finished [ 41.074s] datafusion-expr-common
Building datafusion-ffi v54.1.0 (current)
Built [ 63.217s] (current)
Parsing datafusion-ffi v54.1.0 (current)
Parsed [ 0.059s] (current)
Building datafusion-ffi v54.1.0 (baseline)
Built [ 61.614s] (baseline)
Parsing datafusion-ffi v54.1.0 (baseline)
Parsed [ 0.063s] (baseline)
Checking datafusion-ffi v54.1.0 -> v54.1.0 (no change; assume patch)
Checked [ 0.238s] 223 checks: 223 pass, 30 skip
Summary no semver update required
Finished [ 127.539s] datafusion-ffi
Building datafusion-functions v54.1.0 (current)
Built [ 31.332s] (current)
Parsing datafusion-functions v54.1.0 (current)
Parsed [ 0.085s] (current)
Building datafusion-functions v54.1.0 (baseline)
Built [ 31.495s] (baseline)
Parsing datafusion-functions v54.1.0 (baseline)
Parsed [ 0.087s] (baseline)
Checking datafusion-functions v54.1.0 -> v54.1.0 (no change; assume patch)
Checked [ 0.396s] 223 checks: 223 pass, 30 skip
Summary no semver update required
Finished [ 64.615s] datafusion-functions
Building datafusion-physical-expr v54.1.0 (current)
Built [ 30.065s] (current)
Parsing datafusion-physical-expr v54.1.0 (current)
Parsed [ 0.047s] (current)
Building datafusion-physical-expr v54.1.0 (baseline)
Built [ 30.070s] (baseline)
Parsing datafusion-physical-expr v54.1.0 (baseline)
Parsed [ 0.049s] (baseline)
Checking datafusion-physical-expr v54.1.0 -> v54.1.0 (no change; assume patch)
Checked [ 0.437s] 223 checks: 223 pass, 30 skip
Summary no semver update required
Finished [ 61.601s] datafusion-physical-expr
```
</details>
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] Allow expression to report whether they keep the same ordering of the input (`a.cmp(b) == f(a).cmp(f(b))`) opening up for more optimization [datafusion]
Posted by "rluvaton (via GitHub)" <gi...@apache.org>.
rluvaton commented on PR #23807:
URL: https://github.com/apache/datafusion/pull/23807#issuecomment-5084817407
@alamb can you please take another look?
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] Allow expression to report whether they keep the same ordering of the input (`a.cmp(b) == f(a).cmp(f(b))`) opening up for more optimization [datafusion]
Posted by "rluvaton (via GitHub)" <gi...@apache.org>.
rluvaton commented on PR #23807:
URL: https://github.com/apache/datafusion/pull/23807#issuecomment-5080383165
> Can we get some sql logic / explain test that show some of the optimizations that this allows for (that preserves_lex_ordering does not)?
Done, `array_repeat` is now no longer remove the ordering
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] Allow expression to report whether they keep the same ordering of the input (`a.cmp(b) == f(a).cmp(f(b))` opening up for more optimization [datafusion]
Posted by "rluvaton (via GitHub)" <gi...@apache.org>.
rluvaton commented on PR #23807:
URL: https://github.com/apache/datafusion/pull/23807#issuecomment-5048017750
Cc @andygrove, @mbutrovich, @ozankabak
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org
Re: [PR] `ScalarUdfImpl::strictly_order_preserving`: Allow expression to report whether they keep the same ordering of the input [datafusion]
Posted by "rluvaton (via GitHub)" <gi...@apache.org>.
rluvaton merged PR #23807:
URL: https://github.com/apache/datafusion/pull/23807
--
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: github-unsubscribe@datafusion.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: github-unsubscribe@datafusion.apache.org
For additional commands, e-mail: github-help@datafusion.apache.org