Skip to content

Commit a0cc90c

Browse files
rluvatonkosiew
authored andcommitted
ScalarUdfImpl::strictly_order_preserving: Allow expression to report whether they keep the same ordering of the input (apache#23807)
## Which issue does this PR close? - Closes apache#23798 Related to: - apache#16217 ## Rationale for this change To be able to keep the same sorting order allowing for more optimizations Now comet own `cast` implementation can be recognized as not modifying sort order in the same cases that datafusion cast does. ## What changes are included in this PR? added `strictly_order_preserving` property to `ExprProperties` + varius other places and replaced the hard coded logic for cast (`substitute_cast_ordering`) about keeping input order with more generic approach that now any expression can implement and have the same advantage of sort elimination also marked from_unixtime as keeping ordering to show a case of this optimization ## Are these changes tested? yes ## Are there any user-facing changes? yes, breaking change, added `strictly_order_preserving` property to `ExprProperties` and to `FFI_ExprProperties` 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 satisfying: `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 how to migrate: Option 1 - keeping the old behavior (safest but least performant) set `strictly_order_preserving` to false Option 2 - Using the new optimization that this opens up: set `strictly_order_preserving` only if the expression keep both variants
1 parent 7d9d02d commit a0cc90c

14 files changed

Lines changed: 519 additions & 58 deletions

File tree

‎datafusion/core/tests/physical_optimizer/enforce_sorting.rs‎

Lines changed: 154 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -33,7 +33,7 @@ use arrow::compute::{SortOptions};
3333
use arrow::datatypes::{DataType, SchemaRef};
3434
use datafusion_common::config::{ConfigOptions, CsvOptions};
3535
use datafusion_common::tree_node::{TreeNode, TransformedResult};
36-
use datafusion_common::{create_array, NullEquality, Result, TableReference};
36+
use datafusion_common::{create_array, DataFusionError, NullEquality, Result, TableReference};
3737
use datafusion_datasource::file_scan_config::FileScanConfigBuilder;
3838
use datafusion_datasource::source::DataSourceExec;
3939
use datafusion_expr_common::operator::Operator;
@@ -49,7 +49,7 @@ use datafusion_physical_plan::limit::{GlobalLimitExec, LocalLimitExec};
4949
use datafusion_physical_plan::repartition::RepartitionExec;
5050
use datafusion_physical_plan::sorts::sort_preserving_merge::SortPreservingMergeExec;
5151
use datafusion_physical_plan::sorts::sort::SortExec;
52-
use datafusion_physical_plan::{displayable, get_plan_string, ExecutionPlan};
52+
use datafusion_physical_plan::{displayable, get_plan_string, ExecutionPlan, ExecutionPlanProperties};
5353
use datafusion::datasource::physical_plan::CsvSource;
5454
use datafusion::datasource::listing::PartitionedFile;
5555
use datafusion_physical_optimizer::enforce_sorting::{PlanWithCorrespondingCoalescePartitions, PlanWithCorrespondingSort, parallelize_sorts, ensure_sorting};
@@ -60,12 +60,15 @@ use datafusion_physical_optimizer::ensure_requirements::EnsureRequirements;
6060
use datafusion_physical_optimizer::output_requirements::OutputRequirementExec;
6161
use datafusion_physical_optimizer::PhysicalOptimizerRule;
6262
use datafusion::prelude::*;
63-
use arrow::array::{record_batch, ArrayRef, Int32Array, RecordBatch};
63+
use arrow::array::{record_batch, Array, ArrayRef, Int32Array, RecordBatch};
6464
use arrow::datatypes::{Field};
6565
use arrow_schema::Schema;
6666
use datafusion_execution::TaskContext;
6767
use datafusion_catalog::streaming::StreamingTable;
6868

69+
use datafusion_expr_common::columnar_value::ColumnarValue;
70+
use datafusion_physical_expr::projection::ProjectionExpr;
71+
use datafusion_physical_plan::projection::ProjectionExec;
6972
use futures::StreamExt;
7073
use insta::{Settings, assert_snapshot};
7174

@@ -3255,3 +3258,151 @@ async fn test_does_not_push_fetch_sort_through_projection_over_union() -> Result
32553258

32563259
Ok(())
32573260
}
3261+
3262+
/// A pass-through wrapper around a column: just assert that column does not contain any nulls
3263+
#[derive(Debug, Eq)]
3264+
struct AssertNotNull {
3265+
inner: Arc<dyn PhysicalExpr>,
3266+
}
3267+
3268+
impl AssertNotNull {
3269+
fn new(inner: Arc<dyn PhysicalExpr>) -> Arc<Self> {
3270+
Arc::new(Self { inner })
3271+
}
3272+
}
3273+
3274+
impl PartialEq for AssertNotNull {
3275+
fn eq(&self, other: &Self) -> bool {
3276+
self.inner.eq(&other.inner)
3277+
}
3278+
}
3279+
3280+
impl std::hash::Hash for AssertNotNull {
3281+
fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
3282+
self.inner.hash(state);
3283+
}
3284+
}
3285+
3286+
impl std::fmt::Display for AssertNotNull {
3287+
fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
3288+
write!(f, "assert_not_null({})", self.inner)
3289+
}
3290+
}
3291+
3292+
impl PhysicalExpr for AssertNotNull {
3293+
fn data_type(&self, input_schema: &Schema) -> Result<DataType> {
3294+
self.inner.data_type(input_schema)
3295+
}
3296+
3297+
fn nullable(&self, _input_schema: &Schema) -> Result<bool> {
3298+
Ok(false)
3299+
}
3300+
3301+
fn evaluate(&self, batch: &RecordBatch) -> Result<ColumnarValue> {
3302+
let child = self.inner.evaluate(batch)?;
3303+
match child {
3304+
ColumnarValue::Array(a) if a.logical_null_count() > 0 => Err(
3305+
DataFusionError::Internal("AssertNotNull evaluated to null".to_string()),
3306+
),
3307+
ColumnarValue::Scalar(s) if s.is_null() => Err(DataFusionError::Internal(
3308+
"AssertNotNull evaluated to null".to_string(),
3309+
)),
3310+
child => Ok(child),
3311+
}
3312+
}
3313+
3314+
fn children(&self) -> Vec<&Arc<dyn PhysicalExpr>> {
3315+
vec![&self.inner]
3316+
}
3317+
3318+
fn with_new_children(
3319+
self: Arc<Self>,
3320+
children: Vec<Arc<dyn PhysicalExpr>>,
3321+
) -> Result<Arc<dyn PhysicalExpr>> {
3322+
Ok(Arc::new(AssertNotNull {
3323+
inner: Arc::clone(&children[0]),
3324+
}))
3325+
}
3326+
3327+
fn get_properties(
3328+
&self,
3329+
children: &[datafusion_expr::sort_properties::ExprProperties],
3330+
) -> Result<datafusion_expr::sort_properties::ExprProperties> {
3331+
Ok(children[0].clone())
3332+
}
3333+
3334+
fn fmt_sql(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
3335+
write!(f, "assert_not_null({})", self.inner)
3336+
}
3337+
}
3338+
3339+
#[tokio::test]
3340+
async fn test_passthrough_wrapper_projection_keeps_ordering() -> Result<()> {
3341+
fn sort_expr(name: &str, schema: &Schema) -> PhysicalSortExpr {
3342+
PhysicalSortExpr {
3343+
expr: col(name, schema).unwrap(),
3344+
options: Default::default(),
3345+
}
3346+
}
3347+
3348+
pub fn projection_exec(
3349+
expr: Vec<(Arc<dyn PhysicalExpr>, String)>,
3350+
input: Arc<dyn ExecutionPlan>,
3351+
) -> Result<Arc<dyn ExecutionPlan>> {
3352+
let proj_exprs: Vec<ProjectionExpr> = expr
3353+
.into_iter()
3354+
.map(|(expr, alias)| ProjectionExpr { expr, alias })
3355+
.collect();
3356+
Ok(Arc::new(ProjectionExec::try_new(proj_exprs, input)?))
3357+
}
3358+
3359+
let batch = record_batch!(
3360+
("a", Utf8, ["x", "y"]),
3361+
("b", Utf8, ["1", "2"]),
3362+
("c", Utf8, ["1", "2"])
3363+
)?;
3364+
let schema = batch.schema();
3365+
let source = Arc::new(DataSourceExec::new(Arc::new(
3366+
datafusion::datasource::memory::MemorySourceConfig::try_new(
3367+
&[vec![batch]],
3368+
schema.clone(),
3369+
None,
3370+
)?
3371+
.try_with_sort_information(vec![
3372+
LexOrdering::new([
3373+
sort_expr("a", &schema),
3374+
sort_expr("b", &schema),
3375+
sort_expr("c", &schema),
3376+
])
3377+
.unwrap(),
3378+
])?,
3379+
))) as Arc<dyn ExecutionPlan>;
3380+
3381+
let projection = projection_exec(
3382+
vec![
3383+
(AssertNotNull::new(col("a", &schema)?), "a".to_string()),
3384+
(AssertNotNull::new(col("b", &schema)?), "b".to_string()),
3385+
(AssertNotNull::new(col("c", &schema)?), "c".to_string()),
3386+
],
3387+
source,
3388+
)?;
3389+
3390+
let ordering = LexOrdering::new([
3391+
sort_expr("a", &projection.schema()),
3392+
sort_expr("b", &projection.schema()),
3393+
sort_expr("c", &projection.schema()),
3394+
])
3395+
.unwrap();
3396+
3397+
let sort_satisfied = projection
3398+
.equivalence_properties()
3399+
.ordering_satisfy(ordering.clone())?;
3400+
3401+
let plan_str = displayable(projection.as_ref()).indent(true).to_string();
3402+
assert!(
3403+
sort_satisfied,
3404+
"sort should be satisfied, ordering: {ordering}\nplan:\n{plan_str}"
3405+
);
3406+
3407+
Ok(())
3408+
}

‎datafusion/expr-common/src/sort_properties.rs‎

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -141,7 +141,61 @@ pub struct ExprProperties {
141141
pub range: Interval,
142142
/// Indicates whether the expression preserves lexicographical ordering
143143
/// of its inputs.
144+
///
145+
/// This is a *non-strict* (monotone) property: inputs advancing in
146+
/// lexicographical order never make the output decrease, but distinct
147+
/// inputs may map to equal outputs (ties). See
148+
/// [`Self::strictly_order_preserving`] for the strict variant and an
149+
/// explanation of the difference.
144150
pub preserves_lex_ordering: bool,
151+
/// Indicates whether the expression is strictly order-preserving with
152+
/// respect to its inputs that are `Ordered`: the output is ordered in the
153+
/// same direction, equal outputs can only result from equal values of
154+
/// those inputs (i.e. the mapping is one-to-one), and nulls map to nulls.
155+
///
156+
/// i.e. setting this to true means that `a.cmp(b) == f(a).cmp(f(b))`
157+
///
158+
/// # Difference from [`Self::preserves_lex_ordering`]
159+
///
160+
/// The two properties differ in both their premise and their strictness:
161+
///
162+
/// - `preserves_lex_ordering` assumes the inputs advance in
163+
/// *lexicographical* order (a later input may decrease whenever an
164+
/// earlier one increases), and only promises a non-decreasing output,
165+
/// allowing distinct inputs to collapse into equal outputs; `floor`,
166+
/// `date_trunc` and narrowing casts do exactly that.
167+
/// - `strictly_order_preserving` assumes every `Ordered` input advances
168+
/// *simultaneously* (component-wise, which is what actually holds when
169+
/// all of them are sorted in the data), and promises a strict output:
170+
/// equal outputs only from equal inputs.
171+
///
172+
/// For an expression with a single ordered input the premises coincide,
173+
/// and this field is simply the stronger claim: it implies
174+
/// `preserves_lex_ordering`. With multiple ordered inputs, neither
175+
/// implies the other: a lexicographical-ordering-preserving expression
176+
/// need not be strict (distinct inputs may still produce equal outputs),
177+
/// while `a + b` over two ordered, overflow-free inputs is strict but not
178+
/// lexicographical (under the lexicographical premise `b` may decrease
179+
/// while `a` increases, making the sum decrease).
180+
///
181+
/// The distinction matters for suffix sort keys. Optimizers use this
182+
/// field to substitute a sort key with an expression computed from it:
183+
/// if data is sorted by `[x, y]`, it is also sorted by `[expr(x), y]`.
184+
/// That claim requires `y` to be sorted within each run of equal
185+
/// `expr(x)` values, which only holds if equal outputs imply equal `x`
186+
/// values. With a merely monotone expression such as `floor`, one output
187+
/// run can span several `x` groups, and `y` restarts at each group:
188+
///
189+
/// ```text
190+
/// sorted by [x, y]: (1.2, 5), (1.8, 1), (2.5, 3)
191+
/// [floor(x), y]: (1, 5), (1, 1), (2, 3) <-- y not sorted within
192+
/// the "1" run
193+
/// ```
194+
///
195+
/// Hence a monotone expression only justifies the length-1 ordering
196+
/// `[expr(x)]`, while a strictly order-preserving one keeps the entire
197+
/// suffix valid. When in doubt, set to `false`.
198+
pub strictly_order_preserving: bool,
145199
}
146200

147201
impl ExprProperties {
@@ -152,6 +206,7 @@ impl ExprProperties {
152206
sort_properties: SortProperties::default(),
153207
range: Interval::make_unbounded(&DataType::Null).unwrap(),
154208
preserves_lex_ordering: false,
209+
strictly_order_preserving: false,
155210
}
156211
}
157212

@@ -172,4 +227,14 @@ impl ExprProperties {
172227
self.preserves_lex_ordering = preserves_lex_ordering;
173228
self
174229
}
230+
231+
/// Sets whether the expression is strictly order-preserving and returns
232+
/// the modified instance.
233+
pub fn with_strictly_order_preserving(
234+
mut self,
235+
strictly_order_preserving: bool,
236+
) -> Self {
237+
self.strictly_order_preserving = strictly_order_preserving;
238+
self
239+
}
175240
}

‎datafusion/expr/src/udf.rs‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -380,6 +380,11 @@ impl ScalarUDF {
380380
self.inner.preserves_lex_ordering(inputs)
381381
}
382382

383+
/// See [`ScalarUDFImpl::strictly_order_preserving`] for more details.
384+
pub fn strictly_order_preserving(&self, inputs: &[ExprProperties]) -> Result<bool> {
385+
self.inner.strictly_order_preserving(inputs)
386+
}
387+
383388
/// See [`ScalarUDFImpl::coerce_types`] for more details.
384389
pub fn coerce_types(&self, arg_types: &[DataType]) -> Result<Vec<DataType>> {
385390
self.inner.coerce_types(arg_types)
@@ -979,10 +984,20 @@ pub trait ScalarUDFImpl: Debug + DynEq + DynHash + Send + Sync + Any {
979984

980985
/// Returns true if the function preserves lexicographical ordering based on
981986
/// the input ordering.
987+
///
988+
/// See [`ExprProperties::preserves_lex_ordering`] for more details
982989
fn preserves_lex_ordering(&self, _inputs: &[ExprProperties]) -> Result<bool> {
983990
Ok(false)
984991
}
985992

993+
/// Returns true if the function is strictly order-preserving with respect
994+
/// to its `Ordered` inputs, i.e. `a.cmp(b) == f(a).cmp(f(b))`.
995+
///
996+
/// See [`ExprProperties::strictly_order_preserving`] for more details
997+
fn strictly_order_preserving(&self, _inputs: &[ExprProperties]) -> Result<bool> {
998+
Ok(false)
999+
}
1000+
9861001
/// Coerce arguments of a function call to types that the function can evaluate.
9871002
///
9881003
/// This function is only called if [`ScalarUDFImpl::signature`] returns
@@ -1194,6 +1209,10 @@ impl ScalarUDFImpl for AliasedScalarUDFImpl {
11941209
self.inner.preserves_lex_ordering(inputs)
11951210
}
11961211

1212+
fn strictly_order_preserving(&self, inputs: &[ExprProperties]) -> Result<bool> {
1213+
self.inner.strictly_order_preserving(inputs)
1214+
}
1215+
11971216
fn coerce_types(&self, arg_types: &[DataType]) -> Result<Vec<DataType>> {
11981217
self.inner.coerce_types(arg_types)
11991218
}

‎datafusion/ffi/src/expr/expr_properties.rs‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -29,6 +29,7 @@ pub struct FFI_ExprProperties {
2929
sort_properties: FFI_SortProperties,
3030
range: FFI_Interval,
3131
preserves_lex_ordering: bool,
32+
strictly_order_preserving: bool,
3233
}
3334

3435
impl TryFrom<&ExprProperties> for FFI_ExprProperties {
@@ -41,6 +42,7 @@ impl TryFrom<&ExprProperties> for FFI_ExprProperties {
4142
sort_properties,
4243
range,
4344
preserves_lex_ordering: value.preserves_lex_ordering,
45+
strictly_order_preserving: value.strictly_order_preserving,
4446
})
4547
}
4648
}
@@ -54,6 +56,7 @@ impl TryFrom<FFI_ExprProperties> for ExprProperties {
5456
sort_properties,
5557
range,
5658
preserves_lex_ordering: value.preserves_lex_ordering,
59+
strictly_order_preserving: value.strictly_order_preserving,
5760
})
5861
}
5962
}

‎datafusion/functions/src/datetime/from_unixtime.rs‎

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -22,6 +22,7 @@ use arrow::datatypes::TimeUnit::Second;
2222
use arrow::datatypes::{DataType, Field, FieldRef};
2323
use datafusion_common::{Result, ScalarValue, exec_err, internal_err};
2424
use datafusion_expr::TypeSignature::Exact;
25+
use datafusion_expr::sort_properties::{ExprProperties, SortProperties};
2526
use datafusion_expr::{
2627
ColumnarValue, Documentation, ReturnFieldArgs, ScalarFunctionArgs, ScalarUDFImpl,
2728
Signature, Volatility,
@@ -147,6 +148,24 @@ impl ScalarUDFImpl for FromUnixtimeFunc {
147148
}
148149
}
149150

151+
fn output_ordering(&self, inputs: &[ExprProperties]) -> Result<SortProperties> {
152+
// The optional timezone argument must be a constant string and only
153+
// affects the display metadata, not the stored epoch value, so the
154+
// output ordering follows the first argument.
155+
Ok(inputs[0].sort_properties)
156+
}
157+
158+
fn preserves_lex_ordering(&self, _inputs: &[ExprProperties]) -> Result<bool> {
159+
Ok(true)
160+
}
161+
162+
fn strictly_order_preserving(&self, _inputs: &[ExprProperties]) -> Result<bool> {
163+
// `from_unixtime` stores the input's exact `Int64` value as a
164+
// `Timestamp(Second)`: the mapping is one-to-one, order-preserving,
165+
// and maps nulls to nulls.
166+
Ok(true)
167+
}
168+
150169
fn documentation(&self) -> Option<&Documentation> {
151170
self.doc()
152171
}

‎datafusion/functions/src/math/monotonicity.rs‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -761,6 +761,7 @@ mod tests {
761761
.unwrap(),
762762
sort_properties: sp,
763763
preserves_lex_ordering: false,
764+
strictly_order_preserving: false,
764765
}
765766
}
766767

0 commit comments

Comments
 (0)