Skip to content

Pass over udfs/physical expr that strictly_order_preserving and mark them as such #23920

Description

@rluvaton

After this is merged:

we now have a new property strictly_order_preserving that allow for more optimizations if the expression marked as keeping the same ordering

this property means that given expression f and 2 values from the input column a and b the following variants are kept:

  1. a.cmp(b) == f(a).cmp(f(b))
  2. nulls maps to nulls

Example of satisfying expression:
cast(col_a as BIGINT) where col_a is INT it is keeping the properties

Example of not satesfing:

floor - floor can not

array_repeat(my_col, 2) which might look like at first glance as keeping the property as well but in fact it does not.

the reason is that array_repeat(null, 2) will output list of 2 nulls which breaks the 2nd property that nulls must be kept as nulls

for more details on the property meaning and difference from preserves_lex_ordering see:

/// 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
/// need not be strict (distinct inputs may still produce equal outputs),
/// while `a + b` over two ordered, overflow-free inputs is strict but not
/// lexicographical (under the lexicographical premise `b` may decrease
/// while `a` increases, making the sum decrease).
///
/// The distinction matters for suffix sort keys. Optimizers use this
/// field 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]`.
/// That claim requires `y` to be sorted within each run of equal
/// `expr(x)` values, which only holds if equal outputs imply equal `x`
/// values. With a merely monotone expression such as `floor`, one output
/// run can span several `x` groups, and `y` restarts at each group:
///
/// ```text
/// sorted by [x, y]: (1.2, 5), (1.8, 1), (2.5, 3)
/// [floor(x), y]: (1, 5), (1, 1), (2, 3) <-- y not sorted within
/// the "1" run
/// ```
///
/// Hence a monotone expression only justifies the length-1 ordering
/// `[expr(x)]`, while a strictly order-preserving one keeps the entire
/// suffix valid. When in doubt, set to `false`.
pub strictly_order_preserving: bool,

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions