Skip to content

Commit 69a7fef

Browse files
authored
fix: do not fail when an expression's ordering cannot be derived (apache#26884)
## Which issue does this PR close? - Related to apache#26481. No issue filed. ## Rationale for this change `sqrt`, `ln`, `log2`, `log10`, `acos`, `asin`, `acosh` and `atanh` cannot derive an ordering from their input when the input may be outside their domain (for `sqrt`, a negative `a`), so their `get_properties` returns an error. Two places in `EquivalenceProperties` treated that error as fatal, although it only means that nothing can be derived: - `update_properties` propagated it, which also discarded the ordering the expression already had from the plan. A plan sorted on `sqrt(c)` then does not satisfy a requirement on `sqrt(c)`, so on `main` this query fails in `SanityCheckPlan`: ```sql SELECT c, row_number() OVER (ORDER BY sqrt(c)) FROM (SELECT c FROM t ORDER BY sqrt(c) LIMIT 5); ``` - `discover_new_orderings` propagated it out of `FilterExec`'s properties. On a table with `DOUBLE` columns `a` and `b`, ordered by `(a, b)`, this query fails on `main` with `Execution error: Input range of SQRT contains out-of-domain values`: ```sql SELECT * FROM t WHERE a = sqrt(b); ``` ## What changes are included in this PR? - `update_properties` treats properties that cannot be derived from the children as unknown, with an unbounded range of the expression's type, instead of failing. The node's own known ordering is kept, and parents such as `-sqrt(c)` can still derive their ordering from it. - `discover_new_orderings` skips a candidate whose properties cannot be derived, so no new ordering is found from it. ## Are these changes tested? Yes. `equivalence_properties.slt` covers both queries above and `-sqrt(c)`; each case fails without its change. `test_known_ordering_when_expr_properties_fail` checks that a known ordering on `sqrt(a)` satisfies only a requirement with the same sort options, and that `sqrt(a)` is not ordered when nothing is ordered or only `a` is. ## Are there any user-facing changes? Yes: the two queries above now plan and run.
1 parent 8df818a commit 69a7fef

3 files changed

Lines changed: 133 additions & 4 deletions

File tree

‎datafusion/physical-expr/src/equivalence/properties/dependency.rs‎

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -592,6 +592,54 @@ mod tests {
592592
Ok(())
593593
}
594594

595+
/// `sqrt(a)` has no ordering that can be derived from `a`, which may be
596+
/// negative, so its ordering function fails. A plan sorted on `sqrt(a)`
597+
/// still satisfies a requirement on `sqrt(a)` with the same sort options,
598+
/// and nothing else makes `sqrt(a)` ordered.
599+
#[test]
600+
fn test_known_ordering_when_expr_properties_fail() -> Result<()> {
601+
let schema =
602+
Arc::new(Schema::new(vec![Field::new("a", DataType::Float64, true)]));
603+
let a = col("a", &schema)?;
604+
let sqrt_a: Arc<dyn PhysicalExpr> = Arc::new(ScalarFunctionExpr::try_new(
605+
datafusion_functions::math::sqrt(),
606+
vec![Arc::clone(&a)],
607+
&schema,
608+
Arc::new(ConfigOptions::default()),
609+
)?);
610+
611+
// `sqrt(a)` is nullable, so both the direction and the NULLS position
612+
// must match:
613+
let all_options = [(false, false), (false, true), (true, false), (true, true)]
614+
.map(|(descending, nulls_first)| SortOptions {
615+
descending,
616+
nulls_first,
617+
});
618+
for known in all_options {
619+
let mut eq_properties = EquivalenceProperties::new(Arc::clone(&schema));
620+
eq_properties
621+
.add_ordering([PhysicalSortExpr::new(Arc::clone(&sqrt_a), known)]);
622+
for required in all_options {
623+
let required_ordering =
624+
[PhysicalSortExpr::new(Arc::clone(&sqrt_a), required)];
625+
assert_eq!(
626+
eq_properties.ordering_satisfy(required_ordering)?,
627+
known == required,
628+
"known {known:?}, required {required:?}"
629+
);
630+
}
631+
}
632+
633+
// Without a known ordering on `sqrt(a)`, it is not ordered, even when
634+
// `a` is:
635+
let required_ordering = [PhysicalSortExpr::new_default(Arc::clone(&sqrt_a))];
636+
let mut eq_properties = EquivalenceProperties::new(Arc::clone(&schema));
637+
assert!(!eq_properties.ordering_satisfy(required_ordering.clone())?);
638+
eq_properties.add_ordering([PhysicalSortExpr::new_default(a)]);
639+
assert!(!eq_properties.ordering_satisfy(required_ordering)?);
640+
Ok(())
641+
}
642+
595643
#[test]
596644
fn test_update_properties() -> Result<()> {
597645
let schema = Schema::new(vec![

‎datafusion/physical-expr/src/equivalence/properties/mod.rs‎

Lines changed: 15 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -508,9 +508,13 @@ impl EquivalenceProperties {
508508
strictly_order_preserving: true,
509509
});
510510
}
511-
// Check if the expression is monotonic in all arguments:
512-
let expr_properties =
513-
equivalent_expr.get_properties(&child_properties)?;
511+
// Check if the expression is monotonic in all arguments. If
512+
// that cannot be derived, no new ordering is found:
513+
let Ok(expr_properties) =
514+
equivalent_expr.get_properties(&child_properties)
515+
else {
516+
continue;
517+
};
514518
if expr_properties.preserves_lex_ordering
515519
&& expr_properties.sort_properties
516520
== SortProperties::Ordered(leading_ordering_options)
@@ -1548,7 +1552,14 @@ fn update_properties(
15481552
if !node.expr.children().is_empty() {
15491553
// We have an intermediate (non-leaf) node, account for its children:
15501554
let children_props = node.children.iter().map(|c| c.data.clone()).collect_vec();
1551-
node.data = node.expr.get_properties(&children_props)?;
1555+
// Properties that cannot be derived from the children, for example of a
1556+
// function whose input may be outside its domain, are unknown. The
1557+
// ordering of the node itself can still be known, so do not fail here,
1558+
// and keep the type of its range so that parents can derive from it.
1559+
node.data = node.expr.get_properties(&children_props).or_else(|_| {
1560+
Interval::make_unbounded(&node.expr.data_type(eq_properties.schema())?)
1561+
.map(|range| ExprProperties::new_unknown().with_range(range))
1562+
})?;
15521563
} else if node.expr.is::<Literal>() {
15531564
// We have a Literal, which is one of the two possible leaf node types:
15541565
node.data = node.expr.get_properties(&[])?;

‎datafusion/sqllogictest/test_files/equivalence_properties.slt‎

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -134,6 +134,76 @@ SELECT l.c, s.x FROM (SELECT c FROM t) l CROSS JOIN (SELECT x FROM small WHERE x
134134
1 1
135135
2 1
136136

137+
###
138+
### Functions whose ordering cannot be derived from their input
139+
###
140+
141+
# sqrt has no ordering that can be derived from c, because c may be negative.
142+
# The inner ORDER BY still makes the subquery sorted by sqrt(c), so the
143+
# window's ORDER BY sqrt(c) needs no second sort.
144+
query TT
145+
EXPLAIN SELECT c, row_number() OVER (ORDER BY sqrt(c)) FROM (SELECT c FROM t ORDER BY sqrt(c) LIMIT 5);
146+
----
147+
physical_plan
148+
01)BoundedWindowAggExec: wdw=[row_number() ORDER BY [sqrt(t.c) ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW: Field { "row_number() ORDER BY [sqrt(t.c) ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW": UInt64 }, frame: RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW], mode=[Sorted]
149+
02)--SortExec: TopK(fetch=5), expr=[sqrt(CAST(c@0 AS Float64)) ASC NULLS LAST], preserve_partitioning=[false]
150+
03)----DataSourceExec: file_groups={1 group: [[WORKSPACE_ROOT/datafusion/core/tests/data/window_2.csv]]}, projection=[c], output_ordering=[c@0 ASC NULLS LAST], file_type=csv, has_header=true
151+
152+
query II
153+
SELECT c, row_number() OVER (ORDER BY sqrt(c)) FROM (SELECT c FROM t ORDER BY sqrt(c) LIMIT 5);
154+
----
155+
0 1
156+
1 2
157+
2 3
158+
3 4
159+
4 5
160+
161+
# -sqrt(c) is ordered opposite to sqrt(c), whose order is known only from the
162+
# inner ORDER BY. So the window's ORDER BY -sqrt(c) needs no second sort.
163+
query TT
164+
EXPLAIN SELECT c, row_number() OVER (ORDER BY -sqrt(c)) FROM (SELECT c FROM t ORDER BY sqrt(c) DESC NULLS LAST LIMIT 5);
165+
----
166+
physical_plan
167+
01)BoundedWindowAggExec: wdw=[row_number() ORDER BY [(- sqrt(t.c)) ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW: Field { "row_number() ORDER BY [(- sqrt(t.c)) ASC NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW": UInt64 }, frame: RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW], mode=[Sorted]
168+
02)--SortExec: TopK(fetch=5), expr=[sqrt(CAST(c@0 AS Float64)) DESC NULLS LAST], preserve_partitioning=[false]
169+
03)----DataSourceExec: file_groups={1 group: [[WORKSPACE_ROOT/datafusion/core/tests/data/window_2.csv]]}, projection=[c], output_ordering=[c@0 ASC NULLS LAST], file_type=csv, has_header=true
170+
171+
query II
172+
SELECT c, row_number() OVER (ORDER BY -sqrt(c)) FROM (SELECT c FROM t ORDER BY sqrt(c) DESC NULLS LAST LIMIT 5);
173+
----
174+
99 1
175+
98 2
176+
97 3
177+
96 4
178+
95 5
179+
180+
# On a table sorted by (a, b), the filter a = sqrt(b) would make it sorted by
181+
# b alone too, if sqrt(b) were known to be increasing in b. That cannot be
182+
# derived, because b may be negative, so no new ordering is found and the
183+
# query runs.
184+
statement ok
185+
CREATE EXTERNAL TABLE t_double (a0 DOUBLE, a DOUBLE, b DOUBLE, c DOUBLE, d DOUBLE)
186+
STORED AS CSV
187+
WITH ORDER (a ASC, b ASC)
188+
LOCATION '../core/tests/data/window_2.csv'
189+
OPTIONS ('format.has_header' 'true');
190+
191+
query TT
192+
EXPLAIN SELECT a, b FROM t_double WHERE a = sqrt(b);
193+
----
194+
physical_plan
195+
01)FilterExec: a@0 = sqrt(b@1)
196+
02)--RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1, maintains_sort_order=true
197+
03)----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
198+
199+
query I
200+
SELECT count(*) FROM t_double WHERE a = sqrt(b);
201+
----
202+
25
203+
204+
statement ok
205+
DROP TABLE t_double;
206+
137207
###
138208
### Order-preserving repartition of an unbounded input
139209
###

0 commit comments

Comments
 (0)