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