EquivalenceProperties: How DataFusion Knows Its Data Is Already Sorted Before It Sorts It

TL;DR: A query says ORDER BY a. The data might already be sorted by a — or by b, if a and b always hold the same value. DataFusion tracks three things through the plan: which expressions are equal to each other, which are constant, and which orderings the output satisfies. From those it can conclude that ORDER BY a is already satisfied and delete the sort, that a Hash(b) partitioning already satisfies a Hash(a) requirement, and that a GROUP BY a can be a GROUP BY b. The clever part is not the idea but the normalisation: orderings are stored in a canonical form so that “is this sort satisfied?” is a lookup rather than a search.

Sorting is the most expensive thing a query engine does. Eliminating a sort is the most valuable optimisation it can perform. The problem is that “is this data already sorted?” is not a question you can answer by looking at the plan — you have to know the data.

DataFusion’s answer is EquivalenceProperties (datafusion/physical-expr/src/equivalence/), about 5,600 lines across four files. The type’s own documentation is the best summary:

EquivalenceProperties stores information about the output of a plan node that can be used to optimize the plan. Currently, it keeps track of:

• Sort expressions (orderings),
• Equivalent expressions; i.e. expressions known to have the same value.
• Constants expressions; i.e. expressions known to contain a single constant value.

The three examples that matter

The doc comment gives two, and they are the whole idea.

Equivalent sort expressions:

┌-------┐
| a | b |
|---|---|
| 1 | 9 |
| 2 | 8 |
| 3 | 7 |
| 5 | 5 |
└───┴───┘

In this case, both a ASC and b DESC can describe the table ordering. EquivalenceProperties tracks these different valid sort expressions and treat a ASC and b DESC on an equal footing. For example, if the query specifies the output sorted by EITHER a ASC or b DESC, the sort can be avoided.

Equivalent expressions:

┌───────┐
| a | b |
|---|---|
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 5 | 5 |
└───────┘

In this case, columns a and b always have the same value. With this information, Datafusion can optimize various operations. For example, if the partition requirement is Hash(a) and output partitioning is Hash(b), then DataFusion avoids repartitioning the data as the existing partitioning satisfies the requirement.

The second example is the one that makes hash joins fast. If a table is already partitioned by Hash(b) and the join needs Hash(a), and a = b, then no shuffle is needed. That is the difference between a distributed join and a local one.

The equivalence group

The “which expressions are equal” part is an EquivalenceGroup (equivalence/class.rs):

pub struct EquivalenceGroup {
    /// A mapping from expressions to their equivalence class key.
    map: IndexMap<Arc<dyn PhysicalExpr>, usize>,
    /// The equivalence classes in this group.
    classes: Vec<EquivalenceClass>,
}

A union-find over expressions. add_equal_conditions merges two expressions into one class; normalize_sort_exprs maps any expression to its class representative so that a ASC and b ASC become the same thing.

The constant tracking is subtler. A constant is not just “a value” — it is a value and a statement about whether it holds across partitions:

/// Removes constant expressions that may change across partitions.
/// This method should be used when merging data from different partitions.
pub fn clear_per_partition_constants(&mut self) -> bool {

A constant that is uniform across all partitions is a different (and much more useful) fact than one that happens to be constant within one partition. A LIMIT 1 in one partition of a union does not make the result constant.

A comment about conservative comparisons

The best comment in the whole subsystem is on has_same_classes:

/// A cheap, deliberately conservative check that two groups hold the same
/// equivalence classes.
///
/// This is not `PartialEq`, and the distinction is the point. `classes` is a
/// `Vec` whose order carries no meaning -- `remove_class_at_idx` uses
/// `swap_remove` -- so two groups describing exactly the same equalities can
/// hold their classes in different orders and this returns `false` for them.
/// Naming it `PartialEq` would invite callers to read it as semantic equality,
/// which it is not.
///
/// The comparison is positional because it runs on a hot path:
/// `ProjectionExec` consults it every time a rule replaces its child. Set
/// semantics would mean scanning the other group once per class, and that
/// quadratic term costs more than the recomputation the caller is trying to
/// skip, by a margin that widens with the number of classes.
///
/// Only the false direction is reachable: a group can be reported different
/// when it is not, never the same when it is not. Callers using this to skip
/// work must be built so that a `false` merely costs them that work, which is
/// exactly how the projection fast path uses it.

That is a masterclass in documenting a performance-motivated API decision. The key points:

1. It is deliberately not PartialEq, and the doc says so explicitly, so nobody writes assert_eq! and gets confused.
2. The unsound direction is impossible by construction (“only the false direction is reachable”).
3. The caller’s obligation is spelled out: “must be built so that a false merely costs them that work”.
4. The performance reason is quantified: “that quadratic term costs more than the recomputation the caller is trying to skip”.

Most optimizers have a couple of these “fast but conservative” checks. Most do not document them this well.

The ordering equivalence class

The sorting side is more interesting, because the same ordering can be described in many ways. EquivalenceProperties stores a set of orderings in a normal form:

/// This object serves as a cache for storing equivalent sort expressions
/// in normal form, and a map associating leading sort expressions with
/// full lexicographical orderings. With this information, DataFusion can
/// efficiently determine whether a given ordering is satisfied by the
/// existing orderings, and discover new orderings based on the existing
/// equivalence properties.
pub struct OrderingEquivalenceCache {
    /// Equivalent sort expressions in normal form.
    normal_cls: OrderingEquivalenceClass,
    /// Map associating leading sort expressions with full lexicographical
    /// orderings. Values are indices into `normal_cls`.
    leading_map: HashMap<Arc<dyn PhysicalExpr>, Vec<usize>>,
}

The leading_map is the key structure. It maps a leading sort expression to the orderings that start with it. So “is a ASC, c ASC satisfied?” becomes: look up a in the leading_map, get the candidate orderings, and check them.

The normal form is what makes the lookup work. A sort expression normalisation removes constants, removes duplicates, and maps expressions to their equivalence-class representative — so b ASC where a = b normalises to a ASC, and the leading_map lookup finds the right thing.

The dependency graph

Some orderings imply others, and the machinery for that is dependency.rs. The Display impl is the clearest explanation:

/// ```text
/// DependencyMap: {
///   a@0 ASC --> (target: a@0 ASC, dependencies: [[]])
///   b@1 ASC --> (target: b@1 ASC, dependencies: [[a@0 ASC, c@2 ASC]])
///   c@2 ASC --> (target: c@2 ASC, dependencies: [[b@1 ASC, a@0 ASC]])
///   d@3 ASC --> (target: d@3 ASC, dependencies: [[c@2 ASC, b@1 ASC]])
/// }
/// ```

b ASC depends on a ASC, c ASC — meaning that if the data is sorted by a, c, it is also sorted by b. The construct_orderings function expands a dependency into the concrete lexicographic orderings that satisfy it.

The IndexMap choice is explained too, and it is a lovely example of determinism being treated as a feature:

Using IndexMap (which preserves insert order) to ensure consistent results across different executions for the same query. We could have used HashSet and HashMap instead without any loss of functionality.

As an example, if existing orderings are

1. [a ASC, b ASC]
2. [c ASC]

Then both the following output orderings are valid

1. [a ASC, b ASC, c ASC]
2. [c ASC, a ASC, b ASC]

These are both valid as they are concatenated versions of the alternative orderings. Had we used HashSet/HashMap, we couldn’t guarantee to generate the same result among the possible two results in the example above.

Deterministic plans. The same query produces the same plan on every run, which makes plans comparable, cacheable, and testable. Worth a HashMap → IndexMap change across a whole subsystem.

The satisfaction check

ordering_satisfy_requirement is where the reasoning gets subtle. The doc comment gives the algorithm as a worked example:

Case 1: Sort Requirement [a, c]

Existing orderings: [[a, b, c], [a, d]], constants: []

1. The function first checks the leading requirement a, which is satisfied by [a, b, c].first().
2. a is added as a constant for the next iteration.
3. Normal orderings become [[b, c], [d]].
4. The function fails for c in the second iteration, as neither [b, c] nor [d] satisfies c.

Step 2 is the clever one. Once a is known to be satisfied, the remaining requirement only matters within a tie group of a — because in a lexicographic ordering, c only breaks ties among rows with equal a. So a is temporarily treated as a constant, which lets the algorithm drop a from the candidate orderings and compare the rest.

The implementation is careful about the cost of this trick:

// Registering satisfied keys as constants mutates the state, so it
// needs an owned copy -- but only from the second requirement onwards.
// Single-element requirements (the common case) never pay for the clone.
let last_idx = normal_reqs.len() - 1;
let mut owned = None::<Self>;
for (idx, element) in normal_reqs.into_iter().enumerate() {
    let eq_properties = owned.as_ref().unwrap_or(self);
    ...
    if idx == last_idx {
        // Nothing left to check, so no need to update the state:
        break;
    }
    owned
        .get_or_insert_with(|| self.clone())
        .add_satisfied_key_constants(element.expr)?;
}

The Option<Self> starts as None and is only populated when a second requirement needs the mutation. A single-element requirement — by far the common case — never clones the whole equivalence group. That is a very Rust-flavoured performance trick: make the expensive path conditional on the expensive case.

There is one more refinement, and it is the kind of thing that separates a good implementation from a correct one:

In addition to the key itself, this also registers any sub-expressions whose values the key pins down: if an expression is strictly order-preserving, equal outputs imply equal values of its ordered children, so within a tie group of the key those children are constant as well. For example, if data is sorted by [a, b], the requirement [CAST(a AS BIGINT) ASC, b ASC] is satisfied: a is constant within each group of equal CAST(a AS BIGINT) values, and hence b is …

That is a deep inference. CAST(a AS BIGINT) is order-preserving (for the ascending direction), so rows with equal CAST(a AS BIGINT) have equal a, so b is constant within that group, so the requirement [CAST(a AS BIGINT) ASC, b ASC] is satisfied by a sort on [a, b].

The catch

• The facts are only as good as the operators that produce them. A SortExec declares its output ordering. A HashJoinExec declares equivalence classes for its join keys. An operator that lies produces a wrong plan. DataFusion trusts its own operators.
• The normalisation is a canonical form, and canonical forms have corners. normalize_sort_exprs returns None when the expressions do not define a proper lexicographic ordering — e.g. when two equivalent expressions are compared with different directions (a ASC where a = b and b DESC is not a consistent ordering). The code has to detect that and bail.
• Constants are partition-scoped. A constant that is uniform across all partitions is a different fact from one that is constant within a partition, and merging partitions has to clear the latter.
• The bookkeeping is not free. Every operator that produces output has to compute and propagate these properties, and computing them is not free. The optimisation has to pay for itself.
• It is a lot of machinery. 5,600 lines for “which columns are equal and what orderings hold” is a lot, and it is a common source of DataFusion bugs — a plan that is wrong because an ordering was over-claimed is a correctness bug, not a performance one.

Why it matters

Sorting and shuffling are the two operations that dominate the cost of a real analytical query. EquivalenceProperties is the machinery that lets DataFusion delete both when the data does not need them.

And the trick that makes it work is not exotic: it is the observation that “sort by a” and “sort by b” are the same requirement when a and b are equal, and that a lexicographic requirement can be checked one key at a time by temporarily treating the satisfied keys as constants. Both are natural. Neither is obvious. And the difference between an engine that does this and one that does not is the difference between a query that takes 400ms and one that takes 40ms.