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::{add_offset_to_physical_sort_exprs, LexOrdering, PhysicalExpr};
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 convert_to_orderings, convert_to_sort_exprs, EquivalenceClass, EquivalenceGroup,
330 EquivalenceProperties, OrderingEquivalenceClass,
331 };
332 use crate::expressions::{col, BinaryExpr, Column};
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::config::ConfigOptions;
342 use datafusion_common::Result;
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 =
643 format!("error in test orderings: {orderings:?}, eq_group: {eq_group:?}, constants: {constants:?}, reqs: {reqs:?}, expected: {expected:?}");
644 let mut eq_properties = EquivalenceProperties::new(Arc::clone(&test_schema));
645 let orderings = convert_to_orderings(&orderings);
646 eq_properties.add_orderings(orderings);
647 let classes = eq_group
648 .into_iter()
649 .map(|eq_class| EquivalenceClass::new(eq_class.into_iter().cloned()));
650 let eq_group = EquivalenceGroup::new(classes);
651 eq_properties.add_equivalence_group(eq_group)?;
652
653 let constants = constants.into_iter().map(|expr| {
654 ConstExpr::new(Arc::clone(expr), AcrossPartitions::Uniform(None))
655 });
656 eq_properties.add_constants(constants)?;
657
658 let reqs = convert_to_sort_exprs(&reqs);
659 assert_eq!(eq_properties.ordering_satisfy(reqs)?, expected, "{err_msg}");
660 }
661
662 Ok(())
663 }
664
665 #[test]
666 fn test_ordering_satisfy_different_lengths() -> Result<()> {
667 let test_schema = create_test_schema()?;
668 let col_a = &col("a", &test_schema)?;
669 let col_b = &col("b", &test_schema)?;
670 let col_c = &col("c", &test_schema)?;
671 let col_d = &col("d", &test_schema)?;
672 let col_e = &col("e", &test_schema)?;
673 let col_f = &col("f", &test_schema)?;
674 let options = SortOptions {
675 descending: false,
676 nulls_first: false,
677 };
678 // a=c (e.g they are aliases).
679 let mut eq_properties = EquivalenceProperties::new(test_schema);
680 eq_properties.add_equal_conditions(Arc::clone(col_a), Arc::clone(col_c))?;
681
682 let orderings = vec![
683 vec![(col_a, options)],
684 vec![(col_e, options)],
685 vec![(col_d, options), (col_f, options)],
686 ];
687 let orderings = convert_to_orderings(&orderings);
688
689 // Column [a ASC], [e ASC], [d ASC, f ASC] are all valid orderings for the schema.
690 eq_properties.add_orderings(orderings);
691
692 // First entry in the tuple is required ordering, second entry is the expected flag
693 // that indicates whether this required ordering is satisfied.
694 // ([a ASC], true) indicate a ASC requirement is already satisfied by existing orderings.
695 let test_cases = vec![
696 // [c ASC, a ASC, e ASC], expected represents this requirement is satisfied
697 (
698 vec![(col_c, options), (col_a, options), (col_e, options)],
699 true,
700 ),
701 (vec![(col_c, options), (col_b, options)], false),
702 (vec![(col_c, options), (col_d, options)], true),
703 (
704 vec![(col_d, options), (col_f, options), (col_b, options)],
705 false,
706 ),
707 (vec![(col_d, options), (col_f, options)], true),
708 ];
709
710 for (reqs, expected) in test_cases {
711 let err_msg =
712 format!("error in test reqs: {reqs:?}, expected: {expected:?}",);
713 let reqs = convert_to_sort_exprs(&reqs);
714 assert_eq!(eq_properties.ordering_satisfy(reqs)?, expected, "{err_msg}");
715 }
716
717 Ok(())
718 }
719
720 #[test]
721 fn test_remove_redundant_entries_oeq_class() -> Result<()> {
722 let schema = create_test_schema()?;
723 let col_a = &col("a", &schema)?;
724 let col_b = &col("b", &schema)?;
725 let col_c = &col("c", &schema)?;
726 let col_d = &col("d", &schema)?;
727 let col_e = &col("e", &schema)?;
728
729 let option_asc = SortOptions {
730 descending: false,
731 nulls_first: false,
732 };
733 let option_desc = SortOptions {
734 descending: true,
735 nulls_first: true,
736 };
737
738 // First entry in the tuple is the given orderings for the table
739 // Second entry is the simplest version of the given orderings that is functionally equivalent.
740 let test_cases = vec![
741 // ------- TEST CASE 1 ---------
742 (
743 // ORDERINGS GIVEN
744 vec![
745 // [a ASC, b ASC]
746 vec![(col_a, option_asc), (col_b, option_asc)],
747 ],
748 // EXPECTED orderings that is succinct.
749 vec![
750 // [a ASC, b ASC]
751 vec![(col_a, option_asc), (col_b, option_asc)],
752 ],
753 ),
754 // ------- TEST CASE 2 ---------
755 (
756 // ORDERINGS GIVEN
757 vec![
758 // [a ASC, b ASC]
759 vec![(col_a, option_asc), (col_b, option_asc)],
760 // [a ASC, b ASC, c ASC]
761 vec![
762 (col_a, option_asc),
763 (col_b, option_asc),
764 (col_c, option_asc),
765 ],
766 ],
767 // EXPECTED orderings that is succinct.
768 vec![
769 // [a ASC, b ASC, c ASC]
770 vec![
771 (col_a, option_asc),
772 (col_b, option_asc),
773 (col_c, option_asc),
774 ],
775 ],
776 ),
777 // ------- TEST CASE 3 ---------
778 (
779 // ORDERINGS GIVEN
780 vec![
781 // [a ASC, b DESC]
782 vec![(col_a, option_asc), (col_b, option_desc)],
783 // [a ASC]
784 vec![(col_a, option_asc)],
785 // [a ASC, c ASC]
786 vec![(col_a, option_asc), (col_c, option_asc)],
787 ],
788 // EXPECTED orderings that is succinct.
789 vec![
790 // [a ASC, b DESC]
791 vec![(col_a, option_asc), (col_b, option_desc)],
792 // [a ASC, c ASC]
793 vec![(col_a, option_asc), (col_c, option_asc)],
794 ],
795 ),
796 // ------- TEST CASE 4 ---------
797 (
798 // ORDERINGS GIVEN
799 vec![
800 // [a ASC, b ASC]
801 vec![(col_a, option_asc), (col_b, option_asc)],
802 // [a ASC, b ASC, c ASC]
803 vec![
804 (col_a, option_asc),
805 (col_b, option_asc),
806 (col_c, option_asc),
807 ],
808 // [a ASC]
809 vec![(col_a, option_asc)],
810 ],
811 // EXPECTED orderings that is succinct.
812 vec![
813 // [a ASC, b ASC, c ASC]
814 vec![
815 (col_a, option_asc),
816 (col_b, option_asc),
817 (col_c, option_asc),
818 ],
819 ],
820 ),
821 // ------- TEST CASE 5 ---------
822 // Empty ordering
823 (
824 vec![],
825 // No ordering in the state (empty ordering is ignored).
826 vec![],
827 ),
828 // ------- TEST CASE 6 ---------
829 (
830 // ORDERINGS GIVEN
831 vec![
832 // [a ASC, b ASC]
833 vec![(col_a, option_asc), (col_b, option_asc)],
834 // [b ASC]
835 vec![(col_b, option_asc)],
836 ],
837 // EXPECTED orderings that is succinct.
838 vec![
839 // [a ASC]
840 vec![(col_a, option_asc)],
841 // [b ASC]
842 vec![(col_b, option_asc)],
843 ],
844 ),
845 // ------- TEST CASE 7 ---------
846 // b, a
847 // c, a
848 // d, b, c
849 (
850 // ORDERINGS GIVEN
851 vec![
852 // [b ASC, a ASC]
853 vec![(col_b, option_asc), (col_a, option_asc)],
854 // [c ASC, a ASC]
855 vec![(col_c, option_asc), (col_a, option_asc)],
856 // [d ASC, b ASC, c ASC]
857 vec![
858 (col_d, option_asc),
859 (col_b, option_asc),
860 (col_c, option_asc),
861 ],
862 ],
863 // EXPECTED orderings that is succinct.
864 vec![
865 // [b ASC, a ASC]
866 vec![(col_b, option_asc), (col_a, option_asc)],
867 // [c ASC, a ASC]
868 vec![(col_c, option_asc), (col_a, option_asc)],
869 // [d ASC]
870 vec![(col_d, option_asc)],
871 ],
872 ),
873 // ------- TEST CASE 8 ---------
874 // b, e
875 // c, a
876 // d, b, e, c, a
877 (
878 // ORDERINGS GIVEN
879 vec![
880 // [b ASC, e ASC]
881 vec![(col_b, option_asc), (col_e, option_asc)],
882 // [c ASC, a ASC]
883 vec![(col_c, option_asc), (col_a, option_asc)],
884 // [d ASC, b ASC, e ASC, c ASC, a ASC]
885 vec![
886 (col_d, option_asc),
887 (col_b, option_asc),
888 (col_e, option_asc),
889 (col_c, option_asc),
890 (col_a, option_asc),
891 ],
892 ],
893 // EXPECTED orderings that is succinct.
894 vec![
895 // [b ASC, e ASC]
896 vec![(col_b, option_asc), (col_e, option_asc)],
897 // [c ASC, a ASC]
898 vec![(col_c, option_asc), (col_a, option_asc)],
899 // [d ASC]
900 vec![(col_d, option_asc)],
901 ],
902 ),
903 // ------- TEST CASE 9 ---------
904 // b
905 // a, b, c
906 // d, a, b
907 (
908 // ORDERINGS GIVEN
909 vec![
910 // [b ASC]
911 vec![(col_b, option_asc)],
912 // [a ASC, b ASC, c ASC]
913 vec![
914 (col_a, option_asc),
915 (col_b, option_asc),
916 (col_c, option_asc),
917 ],
918 // [d ASC, a ASC, b ASC]
919 vec![
920 (col_d, option_asc),
921 (col_a, option_asc),
922 (col_b, option_asc),
923 ],
924 ],
925 // EXPECTED orderings that is succinct.
926 vec![
927 // [b ASC]
928 vec![(col_b, option_asc)],
929 // [a ASC, b ASC, c ASC]
930 vec![
931 (col_a, option_asc),
932 (col_b, option_asc),
933 (col_c, option_asc),
934 ],
935 // [d ASC]
936 vec![(col_d, option_asc)],
937 ],
938 ),
939 ];
940 for (orderings, expected) in test_cases {
941 let orderings = convert_to_orderings(&orderings);
942 let expected = convert_to_orderings(&expected);
943 let actual = OrderingEquivalenceClass::from(orderings.clone());
944 let err_msg = format!(
945 "orderings: {orderings:?}, expected: {expected:?}, actual :{actual:?}"
946 );
947 assert_eq!(actual.len(), expected.len(), "{err_msg}");
948 for elem in actual {
949 assert!(expected.contains(&elem), "{}", err_msg);
950 }
951 }
952
953 Ok(())
954 }
955}