datafusion_physical_expr/equivalence/ordering.rs
1// Licensed to the Apache Software Foundation (ASF) under one
2// or more contributor license agreements. See the NOTICE file
3// distributed with this work for additional information
4// regarding copyright ownership. The ASF licenses this file
5// to you under the Apache License, Version 2.0 (the
6// "License"); you may not use this file except in compliance
7// with the License. You may obtain a copy of the License at
8//
9// http://www.apache.org/licenses/LICENSE-2.0
10//
11// Unless required by applicable law or agreed to in writing,
12// software distributed under the License is distributed on an
13// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14// KIND, either express or implied. See the License for the
15// specific language governing permissions and limitations
16// under the License.
17
18use std::fmt::Display;
19use std::ops::Deref;
20use std::sync::Arc;
21use std::vec::IntoIter;
22
23use crate::expressions::with_new_schema;
24use crate::{LexOrdering, PhysicalExpr, add_offset_to_physical_sort_exprs};
25
26use arrow::compute::SortOptions;
27use arrow::datatypes::SchemaRef;
28use datafusion_common::{HashSet, Result};
29use datafusion_physical_expr_common::sort_expr::PhysicalSortExpr;
30
31/// An `OrderingEquivalenceClass` keeps track of distinct alternative orderings
32/// than can describe a table. For example, consider the following table:
33///
34/// ```text
35/// ┌───┬───┬───┬───┐
36/// │ a │ b │ c │ d │
37/// ├───┼───┼───┼───┤
38/// │ 1 │ 4 │ 3 │ 1 │
39/// │ 2 │ 3 │ 3 │ 2 │
40/// │ 3 │ 1 │ 2 │ 2 │
41/// │ 3 │ 2 │ 1 │ 3 │
42/// └───┴───┴───┴───┘
43/// ```
44///
45/// Here, both `[a ASC, b ASC]` and `[c DESC, d ASC]` describe the table
46/// ordering. In this case, we say that these orderings are equivalent.
47///
48/// An `OrderingEquivalenceClass` is a set of such equivalent orderings, which
49/// is represented by a vector of `LexOrdering`s. The set does not store any
50/// redundant information by enforcing the invariant that no suffix of an
51/// ordering in the equivalence class is a prefix of another ordering in the
52/// equivalence class. The set can be empty, which means that there are no
53/// orderings that describe the table.
54#[derive(Clone, Debug, Default, Eq, PartialEq)]
55pub struct OrderingEquivalenceClass {
56 orderings: Vec<LexOrdering>,
57}
58
59impl OrderingEquivalenceClass {
60 /// Clears (empties) this ordering equivalence class.
61 pub fn clear(&mut self) {
62 self.orderings.clear();
63 }
64
65 /// Creates a new ordering equivalence class from the given orderings
66 /// and removes any redundant entries (if given).
67 pub fn new(
68 orderings: impl IntoIterator<Item = impl IntoIterator<Item = PhysicalSortExpr>>,
69 ) -> Self {
70 let mut result = Self {
71 orderings: orderings.into_iter().filter_map(LexOrdering::new).collect(),
72 };
73 result.remove_redundant_entries();
74 result
75 }
76
77 /// Extend this ordering equivalence class with the given orderings.
78 pub fn extend(&mut self, orderings: impl IntoIterator<Item = LexOrdering>) {
79 self.orderings.extend(orderings);
80 // Make sure that there are no redundant orderings:
81 self.remove_redundant_entries();
82 }
83
84 /// Adds new orderings into this ordering equivalence class.
85 pub fn add_orderings(
86 &mut self,
87 sort_exprs: impl IntoIterator<Item = impl IntoIterator<Item = PhysicalSortExpr>>,
88 ) {
89 self.orderings
90 .extend(sort_exprs.into_iter().filter_map(LexOrdering::new));
91 // Make sure that there are no redundant orderings:
92 self.remove_redundant_entries();
93 }
94
95 /// Removes redundant orderings from this ordering equivalence class.
96 ///
97 /// For instance, if we already have the ordering `[a ASC, b ASC, c DESC]`,
98 /// then there is no need to keep ordering `[a ASC, b ASC]` in the state.
99 fn remove_redundant_entries(&mut self) {
100 let mut work = true;
101 while work {
102 work = false;
103 let mut idx = 0;
104 'outer: while idx < self.orderings.len() {
105 let mut ordering_idx = idx + 1;
106 while ordering_idx < self.orderings.len() {
107 if let Some(remove) = self.resolve_overlap(idx, ordering_idx) {
108 work = true;
109 if remove {
110 self.orderings.swap_remove(idx);
111 continue 'outer;
112 }
113 }
114 if let Some(remove) = self.resolve_overlap(ordering_idx, idx) {
115 work = true;
116 if remove {
117 self.orderings.swap_remove(ordering_idx);
118 continue;
119 }
120 }
121 ordering_idx += 1;
122 }
123 idx += 1;
124 }
125 }
126 }
127
128 /// Trims `orderings[idx]` if some suffix of it overlaps with a prefix of
129 /// `orderings[pre_idx]`. If there is any overlap, returns a `Some(true)`
130 /// if any trimming took place, and `Some(false)` otherwise. If there is
131 /// no overlap, returns `None`.
132 ///
133 /// For example, if `orderings[idx]` is `[a ASC, b ASC, c DESC]` and
134 /// `orderings[pre_idx]` is `[b ASC, c DESC]`, then the function will trim
135 /// `orderings[idx]` to `[a ASC]`.
136 fn resolve_overlap(&mut self, idx: usize, pre_idx: usize) -> Option<bool> {
137 let length = self.orderings[idx].len();
138 let other_length = self.orderings[pre_idx].len();
139 for overlap in 1..=length.min(other_length) {
140 if self.orderings[idx][length - overlap..]
141 == self.orderings[pre_idx][..overlap]
142 {
143 return Some(!self.orderings[idx].truncate(length - overlap));
144 }
145 }
146 None
147 }
148
149 /// Returns the concatenation of all the orderings. This enables merge
150 /// operations to preserve all equivalent orderings simultaneously.
151 pub fn output_ordering(&self) -> Option<LexOrdering> {
152 self.orderings.iter().cloned().reduce(|mut cat, o| {
153 cat.extend(o);
154 cat
155 })
156 }
157
158 // Append orderings in `other` to all existing orderings in this ordering
159 // equivalence class.
160 pub fn join_suffix(mut self, other: &Self) -> Self {
161 let n_ordering = self.orderings.len();
162 // Replicate entries before cross product:
163 let n_cross = std::cmp::max(n_ordering, other.len() * n_ordering);
164 self.orderings = self.orderings.into_iter().cycle().take(n_cross).collect();
165 // Append sort expressions of `other` to the current orderings:
166 for (outer_idx, ordering) in other.iter().enumerate() {
167 let base = outer_idx * n_ordering;
168 // Use the cross product index:
169 for idx in base..(base + n_ordering) {
170 self.orderings[idx].extend(ordering.iter().cloned());
171 }
172 }
173 self
174 }
175
176 /// Adds `offset` value to the index of each expression inside this
177 /// ordering equivalence class.
178 pub fn add_offset(&mut self, offset: isize) -> Result<()> {
179 let orderings = std::mem::take(&mut self.orderings);
180 for ordering_result in orderings
181 .into_iter()
182 .map(|o| add_offset_to_physical_sort_exprs(o, offset))
183 {
184 self.orderings.extend(LexOrdering::new(ordering_result?));
185 }
186 Ok(())
187 }
188
189 /// Transforms this `OrderingEquivalenceClass` by mapping columns in the
190 /// original schema to columns in the new schema by index. The new schema
191 /// and the original schema needs to be aligned; i.e. they should have the
192 /// same number of columns, and fields at the same index have the same type
193 /// in both schemas.
194 pub fn with_new_schema(mut self, schema: &SchemaRef) -> Result<Self> {
195 self.orderings = self
196 .orderings
197 .into_iter()
198 .map(|ordering| {
199 ordering
200 .into_iter()
201 .map(|mut sort_expr| {
202 sort_expr.expr = with_new_schema(sort_expr.expr, schema)?;
203 Ok(sort_expr)
204 })
205 .collect::<Result<Vec<_>>>()
206 // The following `unwrap` is safe because the vector will always
207 // be non-empty.
208 .map(|v| LexOrdering::new(v).unwrap())
209 })
210 .collect::<Result<_>>()?;
211 Ok(self)
212 }
213
214 /// Gets sort options associated with this expression if it is a leading
215 /// ordering expression. Otherwise, returns `None`.
216 pub fn get_options(&self, expr: &Arc<dyn PhysicalExpr>) -> Option<SortOptions> {
217 for ordering in self.iter() {
218 let leading_ordering = &ordering[0];
219 if leading_ordering.expr.eq(expr) {
220 return Some(leading_ordering.options);
221 }
222 }
223 None
224 }
225
226 /// Checks whether the given expression is partially constant according to
227 /// this ordering equivalence class.
228 ///
229 /// This function determines whether `expr` appears in at least one combination
230 /// of `descending` and `nulls_first` options that indicate partial constantness
231 /// in a lexicographical ordering. Specifically, an expression is considered
232 /// a partial constant in this context if its `SortOptions` satisfies either
233 /// of the following conditions:
234 /// - It is `descending` with `nulls_first` and _also_ `ascending` with
235 /// `nulls_last`, OR
236 /// - It is `descending` with `nulls_last` and _also_ `ascending` with
237 /// `nulls_first`.
238 ///
239 /// The equivalence mechanism primarily uses `ConstExpr`s to represent globally
240 /// constant expressions. However, some expressions may only be partially
241 /// constant within a lexicographical ordering. This function helps identify
242 /// such cases. If an expression is constant within a prefix ordering, it is
243 /// added as a constant during `ordering_satisfy_requirement()` iterations
244 /// after the corresponding prefix requirement is satisfied.
245 ///
246 /// ### Future Improvements
247 ///
248 /// This function may become unnecessary if any of the following improvements
249 /// are implemented:
250 /// 1. `SortOptions` supports encoding constantness information.
251 /// 2. `EquivalenceProperties` gains `FunctionalDependency` awareness, eliminating
252 /// the need for `Constant` and `Constraints`.
253 pub fn is_expr_partial_const(&self, expr: &Arc<dyn PhysicalExpr>) -> bool {
254 let mut constantness_defining_pairs = [
255 HashSet::from([(false, false), (true, true)]),
256 HashSet::from([(false, true), (true, false)]),
257 ];
258
259 for ordering in self.iter() {
260 let leading_ordering = ordering.first();
261 if leading_ordering.expr.eq(expr) {
262 let opt = (
263 leading_ordering.options.descending,
264 leading_ordering.options.nulls_first,
265 );
266 constantness_defining_pairs[0].remove(&opt);
267 constantness_defining_pairs[1].remove(&opt);
268 }
269 }
270
271 constantness_defining_pairs
272 .iter()
273 .any(|pair| pair.is_empty())
274 }
275}
276
277impl Deref for OrderingEquivalenceClass {
278 type Target = [LexOrdering];
279
280 fn deref(&self) -> &Self::Target {
281 self.orderings.as_slice()
282 }
283}
284
285impl From<Vec<LexOrdering>> for OrderingEquivalenceClass {
286 fn from(orderings: Vec<LexOrdering>) -> Self {
287 let mut result = Self { orderings };
288 result.remove_redundant_entries();
289 result
290 }
291}
292
293/// Convert the `OrderingEquivalenceClass` into an iterator of `LexOrdering`s.
294impl IntoIterator for OrderingEquivalenceClass {
295 type Item = LexOrdering;
296 type IntoIter = IntoIter<Self::Item>;
297
298 fn into_iter(self) -> Self::IntoIter {
299 self.orderings.into_iter()
300 }
301}
302
303impl Display for OrderingEquivalenceClass {
304 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
305 write!(f, "[")?;
306 let mut iter = self.orderings.iter();
307 if let Some(ordering) = iter.next() {
308 write!(f, "[{ordering}]")?;
309 }
310 for ordering in iter {
311 write!(f, ", [{ordering}]")?;
312 }
313 write!(f, "]")
314 }
315}
316
317impl From<OrderingEquivalenceClass> for Vec<LexOrdering> {
318 fn from(oeq_class: OrderingEquivalenceClass) -> Self {
319 oeq_class.orderings
320 }
321}
322
323#[cfg(test)]
324mod tests {
325 use std::sync::Arc;
326
327 use crate::equivalence::tests::create_test_schema;
328 use crate::equivalence::{
329 EquivalenceClass, EquivalenceGroup, EquivalenceProperties,
330 OrderingEquivalenceClass, convert_to_orderings, convert_to_sort_exprs,
331 };
332 use crate::expressions::{BinaryExpr, Column, col};
333 use crate::utils::tests::TestScalarUDF;
334 use crate::{
335 AcrossPartitions, ConstExpr, PhysicalExpr, PhysicalExprRef, PhysicalSortExpr,
336 ScalarFunctionExpr,
337 };
338
339 use arrow::compute::SortOptions;
340 use arrow::datatypes::{DataType, Field, Schema};
341 use datafusion_common::Result;
342 use datafusion_common::config::ConfigOptions;
343 use datafusion_expr::{Operator, ScalarUDF};
344
345 #[test]
346 fn test_ordering_satisfy() -> Result<()> {
347 let input_schema = Arc::new(Schema::new(vec![
348 Field::new("a", DataType::Int64, true),
349 Field::new("b", DataType::Int64, true),
350 ]));
351 let crude = vec![PhysicalSortExpr {
352 expr: Arc::new(Column::new("a", 0)),
353 options: SortOptions::default(),
354 }];
355 let finer = vec![
356 PhysicalSortExpr {
357 expr: Arc::new(Column::new("a", 0)),
358 options: SortOptions::default(),
359 },
360 PhysicalSortExpr {
361 expr: Arc::new(Column::new("b", 1)),
362 options: SortOptions::default(),
363 },
364 ];
365 // finer ordering satisfies, crude ordering should return true
366 let eq_properties_finer = EquivalenceProperties::new_with_orderings(
367 Arc::clone(&input_schema),
368 [finer.clone()],
369 );
370 assert!(eq_properties_finer.ordering_satisfy(crude.clone())?);
371
372 // Crude ordering doesn't satisfy finer ordering. should return false
373 let eq_properties_crude =
374 EquivalenceProperties::new_with_orderings(Arc::clone(&input_schema), [crude]);
375 assert!(!eq_properties_crude.ordering_satisfy(finer)?);
376 Ok(())
377 }
378
379 #[test]
380 fn test_ordering_satisfy_with_equivalence2() -> Result<()> {
381 let test_schema = create_test_schema()?;
382 let col_a = &col("a", &test_schema)?;
383 let col_b = &col("b", &test_schema)?;
384 let col_c = &col("c", &test_schema)?;
385 let col_d = &col("d", &test_schema)?;
386 let col_e = &col("e", &test_schema)?;
387 let col_f = &col("f", &test_schema)?;
388 let test_fun = Arc::new(ScalarUDF::new_from_impl(TestScalarUDF::new()));
389
390 let floor_a = Arc::new(ScalarFunctionExpr::try_new(
391 Arc::clone(&test_fun),
392 vec![Arc::clone(col_a)],
393 &test_schema,
394 Arc::new(ConfigOptions::default()),
395 )?) as PhysicalExprRef;
396 let floor_f = Arc::new(ScalarFunctionExpr::try_new(
397 Arc::clone(&test_fun),
398 vec![Arc::clone(col_f)],
399 &test_schema,
400 Arc::new(ConfigOptions::default()),
401 )?) as PhysicalExprRef;
402 let exp_a = Arc::new(ScalarFunctionExpr::try_new(
403 Arc::clone(&test_fun),
404 vec![Arc::clone(col_a)],
405 &test_schema,
406 Arc::new(ConfigOptions::default()),
407 )?) as PhysicalExprRef;
408
409 let a_plus_b = Arc::new(BinaryExpr::new(
410 Arc::clone(col_a),
411 Operator::Plus,
412 Arc::clone(col_b),
413 )) as Arc<dyn PhysicalExpr>;
414 let options = SortOptions {
415 descending: false,
416 nulls_first: false,
417 };
418
419 let test_cases = vec![
420 // ------------ TEST CASE 1 ------------
421 (
422 // orderings
423 vec![
424 // [a ASC, d ASC, b ASC]
425 vec![(col_a, options), (col_d, options), (col_b, options)],
426 // [c ASC]
427 vec![(col_c, options)],
428 ],
429 // equivalence classes
430 vec![vec![col_a, col_f]],
431 // constants
432 vec![col_e],
433 // requirement [a ASC, b ASC], requirement is not satisfied.
434 vec![(col_a, options), (col_b, options)],
435 // expected: requirement is not satisfied.
436 false,
437 ),
438 // ------------ TEST CASE 2 ------------
439 (
440 // orderings
441 vec![
442 // [a ASC, c ASC, b ASC]
443 vec![(col_a, options), (col_c, options), (col_b, options)],
444 // [d ASC]
445 vec![(col_d, options)],
446 ],
447 // equivalence classes
448 vec![vec![col_a, col_f]],
449 // constants
450 vec![col_e],
451 // requirement [floor(a) ASC],
452 vec![(&floor_a, options)],
453 // expected: requirement is satisfied.
454 true,
455 ),
456 // ------------ TEST CASE 2.1 ------------
457 (
458 // orderings
459 vec![
460 // [a ASC, c ASC, b ASC]
461 vec![(col_a, options), (col_c, options), (col_b, options)],
462 // [d ASC]
463 vec![(col_d, options)],
464 ],
465 // equivalence classes
466 vec![vec![col_a, col_f]],
467 // constants
468 vec![col_e],
469 // requirement [floor(f) ASC], (Please note that a=f)
470 vec![(&floor_f, options)],
471 // expected: requirement is satisfied.
472 true,
473 ),
474 // ------------ TEST CASE 3 ------------
475 (
476 // orderings
477 vec![
478 // [a ASC, c ASC, b ASC]
479 vec![(col_a, options), (col_c, options), (col_b, options)],
480 // [d ASC]
481 vec![(col_d, options)],
482 ],
483 // equivalence classes
484 vec![vec![col_a, col_f]],
485 // constants
486 vec![col_e],
487 // requirement [a ASC, c ASC, a+b ASC],
488 vec![(col_a, options), (col_c, options), (&a_plus_b, options)],
489 // expected: requirement is satisfied.
490 true,
491 ),
492 // ------------ TEST CASE 4 ------------
493 (
494 // orderings
495 vec![
496 // [a ASC, b ASC, c ASC, d ASC]
497 vec![
498 (col_a, options),
499 (col_b, options),
500 (col_c, options),
501 (col_d, options),
502 ],
503 ],
504 // equivalence classes
505 vec![vec![col_a, col_f]],
506 // constants
507 vec![col_e],
508 // requirement [floor(a) ASC, a+b ASC],
509 vec![(&floor_a, options), (&a_plus_b, options)],
510 // expected: requirement is satisfied.
511 false,
512 ),
513 // ------------ TEST CASE 5 ------------
514 (
515 // orderings
516 vec![
517 // [a ASC, b ASC, c ASC, d ASC]
518 vec![
519 (col_a, options),
520 (col_b, options),
521 (col_c, options),
522 (col_d, options),
523 ],
524 ],
525 // equivalence classes
526 vec![vec![col_a, col_f]],
527 // constants
528 vec![col_e],
529 // requirement [exp(a) ASC, a+b ASC],
530 vec![(&exp_a, options), (&a_plus_b, options)],
531 // expected: requirement is not satisfied.
532 // TODO: If we know that exp function is 1-to-1 function.
533 // we could have deduced that above requirement is satisfied.
534 false,
535 ),
536 // ------------ TEST CASE 6 ------------
537 (
538 // orderings
539 vec![
540 // [a ASC, d ASC, b ASC]
541 vec![(col_a, options), (col_d, options), (col_b, options)],
542 // [c ASC]
543 vec![(col_c, options)],
544 ],
545 // equivalence classes
546 vec![vec![col_a, col_f]],
547 // constants
548 vec![col_e],
549 // requirement [a ASC, d ASC, floor(a) ASC],
550 vec![(col_a, options), (col_d, options), (&floor_a, options)],
551 // expected: requirement is satisfied.
552 true,
553 ),
554 // ------------ TEST CASE 7 ------------
555 (
556 // orderings
557 vec![
558 // [a ASC, c ASC, b ASC]
559 vec![(col_a, options), (col_c, options), (col_b, options)],
560 // [d ASC]
561 vec![(col_d, options)],
562 ],
563 // equivalence classes
564 vec![vec![col_a, col_f]],
565 // constants
566 vec![col_e],
567 // requirement [a ASC, floor(a) ASC, a + b ASC],
568 vec![(col_a, options), (&floor_a, options), (&a_plus_b, options)],
569 // expected: requirement is not satisfied.
570 false,
571 ),
572 // ------------ TEST CASE 8 ------------
573 (
574 // orderings
575 vec![
576 // [a ASC, b ASC, c ASC]
577 vec![(col_a, options), (col_b, options), (col_c, options)],
578 // [d ASC]
579 vec![(col_d, options)],
580 ],
581 // equivalence classes
582 vec![vec![col_a, col_f]],
583 // constants
584 vec![col_e],
585 // requirement [a ASC, c ASC, floor(a) ASC, a + b ASC],
586 vec![
587 (col_a, options),
588 (col_c, options),
589 (&floor_a, options),
590 (&a_plus_b, options),
591 ],
592 // expected: requirement is not satisfied.
593 false,
594 ),
595 // ------------ TEST CASE 9 ------------
596 (
597 // orderings
598 vec![
599 // [a ASC, b ASC, c ASC, d ASC]
600 vec![
601 (col_a, options),
602 (col_b, options),
603 (col_c, options),
604 (col_d, options),
605 ],
606 ],
607 // equivalence classes
608 vec![vec![col_a, col_f]],
609 // constants
610 vec![col_e],
611 // requirement [a ASC, b ASC, c ASC, floor(a) ASC],
612 vec![
613 (col_a, options),
614 (col_b, options),
615 (col_c, options),
616 (&floor_a, options),
617 ],
618 // expected: requirement is satisfied.
619 true,
620 ),
621 // ------------ TEST CASE 10 ------------
622 (
623 // orderings
624 vec![
625 // [d ASC, b ASC]
626 vec![(col_d, options), (col_b, options)],
627 // [c ASC, a ASC]
628 vec![(col_c, options), (col_a, options)],
629 ],
630 // equivalence classes
631 vec![vec![col_a, col_f]],
632 // constants
633 vec![col_e],
634 // requirement [c ASC, d ASC, a + b ASC],
635 vec![(col_c, options), (col_d, options), (&a_plus_b, options)],
636 // expected: requirement is satisfied.
637 true,
638 ),
639 ];
640
641 for (orderings, eq_group, constants, reqs, expected) in test_cases {
642 let err_msg = format!(
643 "error in test orderings: {orderings:?}, eq_group: {eq_group:?}, constants: {constants:?}, reqs: {reqs:?}, expected: {expected:?}"
644 );
645 let mut eq_properties = EquivalenceProperties::new(Arc::clone(&test_schema));
646 let orderings = convert_to_orderings(&orderings);
647 eq_properties.add_orderings(orderings);
648 let classes = eq_group
649 .into_iter()
650 .map(|eq_class| EquivalenceClass::new(eq_class.into_iter().cloned()));
651 let eq_group = EquivalenceGroup::new(classes);
652 eq_properties.add_equivalence_group(eq_group)?;
653
654 let constants = constants.into_iter().map(|expr| {
655 ConstExpr::new(Arc::clone(expr), AcrossPartitions::Uniform(None))
656 });
657 eq_properties.add_constants(constants)?;
658
659 let reqs = convert_to_sort_exprs(&reqs);
660 assert_eq!(eq_properties.ordering_satisfy(reqs)?, expected, "{err_msg}");
661 }
662
663 Ok(())
664 }
665
666 #[test]
667 fn test_ordering_satisfy_different_lengths() -> Result<()> {
668 let test_schema = create_test_schema()?;
669 let col_a = &col("a", &test_schema)?;
670 let col_b = &col("b", &test_schema)?;
671 let col_c = &col("c", &test_schema)?;
672 let col_d = &col("d", &test_schema)?;
673 let col_e = &col("e", &test_schema)?;
674 let col_f = &col("f", &test_schema)?;
675 let options = SortOptions {
676 descending: false,
677 nulls_first: false,
678 };
679 // a=c (e.g they are aliases).
680 let mut eq_properties = EquivalenceProperties::new(test_schema);
681 eq_properties.add_equal_conditions(Arc::clone(col_a), Arc::clone(col_c))?;
682
683 let orderings = vec![
684 vec![(col_a, options)],
685 vec![(col_e, options)],
686 vec![(col_d, options), (col_f, options)],
687 ];
688 let orderings = convert_to_orderings(&orderings);
689
690 // Column [a ASC], [e ASC], [d ASC, f ASC] are all valid orderings for the schema.
691 eq_properties.add_orderings(orderings);
692
693 // First entry in the tuple is required ordering, second entry is the expected flag
694 // that indicates whether this required ordering is satisfied.
695 // ([a ASC], true) indicate a ASC requirement is already satisfied by existing orderings.
696 let test_cases = vec![
697 // [c ASC, a ASC, e ASC], expected represents this requirement is satisfied
698 (
699 vec![(col_c, options), (col_a, options), (col_e, options)],
700 true,
701 ),
702 (vec![(col_c, options), (col_b, options)], false),
703 (vec![(col_c, options), (col_d, options)], true),
704 (
705 vec![(col_d, options), (col_f, options), (col_b, options)],
706 false,
707 ),
708 (vec![(col_d, options), (col_f, options)], true),
709 ];
710
711 for (reqs, expected) in test_cases {
712 let err_msg =
713 format!("error in test reqs: {reqs:?}, expected: {expected:?}",);
714 let reqs = convert_to_sort_exprs(&reqs);
715 assert_eq!(eq_properties.ordering_satisfy(reqs)?, expected, "{err_msg}");
716 }
717
718 Ok(())
719 }
720
721 #[test]
722 fn test_remove_redundant_entries_oeq_class() -> Result<()> {
723 let schema = create_test_schema()?;
724 let col_a = &col("a", &schema)?;
725 let col_b = &col("b", &schema)?;
726 let col_c = &col("c", &schema)?;
727 let col_d = &col("d", &schema)?;
728 let col_e = &col("e", &schema)?;
729
730 let option_asc = SortOptions {
731 descending: false,
732 nulls_first: false,
733 };
734 let option_desc = SortOptions {
735 descending: true,
736 nulls_first: true,
737 };
738
739 // First entry in the tuple is the given orderings for the table
740 // Second entry is the simplest version of the given orderings that is functionally equivalent.
741 let test_cases = vec![
742 // ------- TEST CASE 1 ---------
743 (
744 // ORDERINGS GIVEN
745 vec![
746 // [a ASC, b ASC]
747 vec![(col_a, option_asc), (col_b, option_asc)],
748 ],
749 // EXPECTED orderings that is succinct.
750 vec![
751 // [a ASC, b ASC]
752 vec![(col_a, option_asc), (col_b, option_asc)],
753 ],
754 ),
755 // ------- TEST CASE 2 ---------
756 (
757 // ORDERINGS GIVEN
758 vec![
759 // [a ASC, b ASC]
760 vec![(col_a, option_asc), (col_b, option_asc)],
761 // [a ASC, b ASC, c ASC]
762 vec![
763 (col_a, option_asc),
764 (col_b, option_asc),
765 (col_c, option_asc),
766 ],
767 ],
768 // EXPECTED orderings that is succinct.
769 vec![
770 // [a ASC, b ASC, c ASC]
771 vec![
772 (col_a, option_asc),
773 (col_b, option_asc),
774 (col_c, option_asc),
775 ],
776 ],
777 ),
778 // ------- TEST CASE 3 ---------
779 (
780 // ORDERINGS GIVEN
781 vec![
782 // [a ASC, b DESC]
783 vec![(col_a, option_asc), (col_b, option_desc)],
784 // [a ASC]
785 vec![(col_a, option_asc)],
786 // [a ASC, c ASC]
787 vec![(col_a, option_asc), (col_c, option_asc)],
788 ],
789 // EXPECTED orderings that is succinct.
790 vec![
791 // [a ASC, b DESC]
792 vec![(col_a, option_asc), (col_b, option_desc)],
793 // [a ASC, c ASC]
794 vec![(col_a, option_asc), (col_c, option_asc)],
795 ],
796 ),
797 // ------- TEST CASE 4 ---------
798 (
799 // ORDERINGS GIVEN
800 vec![
801 // [a ASC, b ASC]
802 vec![(col_a, option_asc), (col_b, option_asc)],
803 // [a ASC, b ASC, c ASC]
804 vec![
805 (col_a, option_asc),
806 (col_b, option_asc),
807 (col_c, option_asc),
808 ],
809 // [a ASC]
810 vec![(col_a, option_asc)],
811 ],
812 // EXPECTED orderings that is succinct.
813 vec![
814 // [a ASC, b ASC, c ASC]
815 vec![
816 (col_a, option_asc),
817 (col_b, option_asc),
818 (col_c, option_asc),
819 ],
820 ],
821 ),
822 // ------- TEST CASE 5 ---------
823 // Empty ordering
824 (
825 vec![],
826 // No ordering in the state (empty ordering is ignored).
827 vec![],
828 ),
829 // ------- TEST CASE 6 ---------
830 (
831 // ORDERINGS GIVEN
832 vec![
833 // [a ASC, b ASC]
834 vec![(col_a, option_asc), (col_b, option_asc)],
835 // [b ASC]
836 vec![(col_b, option_asc)],
837 ],
838 // EXPECTED orderings that is succinct.
839 vec![
840 // [a ASC]
841 vec![(col_a, option_asc)],
842 // [b ASC]
843 vec![(col_b, option_asc)],
844 ],
845 ),
846 // ------- TEST CASE 7 ---------
847 // b, a
848 // c, a
849 // d, b, c
850 (
851 // ORDERINGS GIVEN
852 vec![
853 // [b ASC, a ASC]
854 vec![(col_b, option_asc), (col_a, option_asc)],
855 // [c ASC, a ASC]
856 vec![(col_c, option_asc), (col_a, option_asc)],
857 // [d ASC, b ASC, c ASC]
858 vec![
859 (col_d, option_asc),
860 (col_b, option_asc),
861 (col_c, option_asc),
862 ],
863 ],
864 // EXPECTED orderings that is succinct.
865 vec![
866 // [b ASC, a ASC]
867 vec![(col_b, option_asc), (col_a, option_asc)],
868 // [c ASC, a ASC]
869 vec![(col_c, option_asc), (col_a, option_asc)],
870 // [d ASC]
871 vec![(col_d, option_asc)],
872 ],
873 ),
874 // ------- TEST CASE 8 ---------
875 // b, e
876 // c, a
877 // d, b, e, c, a
878 (
879 // ORDERINGS GIVEN
880 vec![
881 // [b ASC, e ASC]
882 vec![(col_b, option_asc), (col_e, option_asc)],
883 // [c ASC, a ASC]
884 vec![(col_c, option_asc), (col_a, option_asc)],
885 // [d ASC, b ASC, e ASC, c ASC, a ASC]
886 vec![
887 (col_d, option_asc),
888 (col_b, option_asc),
889 (col_e, option_asc),
890 (col_c, option_asc),
891 (col_a, option_asc),
892 ],
893 ],
894 // EXPECTED orderings that is succinct.
895 vec![
896 // [b ASC, e ASC]
897 vec![(col_b, option_asc), (col_e, option_asc)],
898 // [c ASC, a ASC]
899 vec![(col_c, option_asc), (col_a, option_asc)],
900 // [d ASC]
901 vec![(col_d, option_asc)],
902 ],
903 ),
904 // ------- TEST CASE 9 ---------
905 // b
906 // a, b, c
907 // d, a, b
908 (
909 // ORDERINGS GIVEN
910 vec![
911 // [b ASC]
912 vec![(col_b, option_asc)],
913 // [a ASC, b ASC, c ASC]
914 vec![
915 (col_a, option_asc),
916 (col_b, option_asc),
917 (col_c, option_asc),
918 ],
919 // [d ASC, a ASC, b ASC]
920 vec![
921 (col_d, option_asc),
922 (col_a, option_asc),
923 (col_b, option_asc),
924 ],
925 ],
926 // EXPECTED orderings that is succinct.
927 vec![
928 // [b ASC]
929 vec![(col_b, option_asc)],
930 // [a ASC, b ASC, c ASC]
931 vec![
932 (col_a, option_asc),
933 (col_b, option_asc),
934 (col_c, option_asc),
935 ],
936 // [d ASC]
937 vec![(col_d, option_asc)],
938 ],
939 ),
940 ];
941 for (orderings, expected) in test_cases {
942 let orderings = convert_to_orderings(&orderings);
943 let expected = convert_to_orderings(&expected);
944 let actual = OrderingEquivalenceClass::from(orderings.clone());
945 let err_msg = format!(
946 "orderings: {orderings:?}, expected: {expected:?}, actual :{actual:?}"
947 );
948 assert_eq!(actual.len(), expected.len(), "{err_msg}");
949 for elem in actual {
950 assert!(expected.contains(&elem), "{}", err_msg);
951 }
952 }
953
954 Ok(())
955 }
956}