datafusion_physical_plan/
sort_pushdown.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
18//! Sort pushdown types for physical execution plans.
19//!
20//! This module provides types used for pushing sort ordering requirements
21//! down through the execution plan tree to data sources.
22
23/// Result of attempting to push down sort ordering to a node.
24///
25/// Used by [`ExecutionPlan::try_pushdown_sort`] to communicate
26/// whether and how sort ordering was successfully pushed down.
27///
28/// [`ExecutionPlan::try_pushdown_sort`]: crate::ExecutionPlan::try_pushdown_sort
29#[derive(Debug, Clone)]
30pub enum SortOrderPushdownResult<T> {
31    /// The source can guarantee exact ordering (data is perfectly sorted).
32    ///
33    /// When this is returned, the optimizer can safely remove the Sort operator
34    /// entirely since the data source guarantees the requested ordering.
35    Exact {
36        /// The optimized node that provides exact ordering
37        inner: T,
38    },
39    /// The source has optimized for the ordering but cannot guarantee perfect sorting.
40    ///
41    /// This indicates the data source has been optimized (e.g., reordered files/row groups
42    /// based on statistics, enabled reverse scanning) but the data may not be perfectly
43    /// sorted. The optimizer should keep the Sort operator but benefits from the
44    /// optimization (e.g., faster TopK queries due to early termination).
45    Inexact {
46        /// The optimized node that provides approximate ordering
47        inner: T,
48    },
49    /// The source cannot optimize for this ordering.
50    ///
51    /// The data source does not support the requested sort ordering and no
52    /// optimization was applied.
53    Unsupported,
54}
55
56impl<T> SortOrderPushdownResult<T> {
57    /// Extract the inner value if present
58    pub fn into_inner(self) -> Option<T> {
59        match self {
60            Self::Exact { inner } | Self::Inexact { inner } => Some(inner),
61            Self::Unsupported => None,
62        }
63    }
64
65    /// Map the inner value to a different type while preserving the variant.
66    pub fn map<U, F: FnOnce(T) -> U>(self, f: F) -> SortOrderPushdownResult<U> {
67        match self {
68            Self::Exact { inner } => SortOrderPushdownResult::Exact { inner: f(inner) },
69            Self::Inexact { inner } => {
70                SortOrderPushdownResult::Inexact { inner: f(inner) }
71            }
72            Self::Unsupported => SortOrderPushdownResult::Unsupported,
73        }
74    }
75
76    /// Try to map the inner value, returning an error if the function fails.
77    pub fn try_map<U, E, F: FnOnce(T) -> Result<U, E>>(
78        self,
79        f: F,
80    ) -> Result<SortOrderPushdownResult<U>, E> {
81        match self {
82            Self::Exact { inner } => {
83                Ok(SortOrderPushdownResult::Exact { inner: f(inner)? })
84            }
85            Self::Inexact { inner } => {
86                Ok(SortOrderPushdownResult::Inexact { inner: f(inner)? })
87            }
88            Self::Unsupported => Ok(SortOrderPushdownResult::Unsupported),
89        }
90    }
91
92    /// Convert this result to `Inexact`, downgrading `Exact` if present.
93    ///
94    /// This is useful when an operation (like merging multiple partitions)
95    /// cannot guarantee exact ordering even if the input provides it.
96    ///
97    /// # Examples
98    ///
99    /// ```
100    /// # use datafusion_physical_plan::SortOrderPushdownResult;
101    /// let exact = SortOrderPushdownResult::Exact { inner: 42 };
102    /// let inexact = exact.into_inexact();
103    /// assert!(matches!(inexact, SortOrderPushdownResult::Inexact { inner: 42 }));
104    ///
105    /// let already_inexact = SortOrderPushdownResult::Inexact { inner: 42 };
106    /// let still_inexact = already_inexact.into_inexact();
107    /// assert!(matches!(still_inexact, SortOrderPushdownResult::Inexact { inner: 42 }));
108    ///
109    /// let unsupported = SortOrderPushdownResult::<i32>::Unsupported;
110    /// let still_unsupported = unsupported.into_inexact();
111    /// assert!(matches!(still_unsupported, SortOrderPushdownResult::Unsupported));
112    /// ```
113    pub fn into_inexact(self) -> Self {
114        match self {
115            Self::Exact { inner } => Self::Inexact { inner },
116            Self::Inexact { inner } => Self::Inexact { inner },
117            Self::Unsupported => Self::Unsupported,
118        }
119    }
120}
datafusion_physical_plan/sort_pushdown.rs

datafusion_physical_plan/
sort_pushdown.rs
