Opensource internals

DataFusion Checks Its Own Optimizer: Plan Invariants as a Debugging and Correctness Net

8 min read Jay Hubbert

Every optimizer rule's output is validated against a set of plan invariants, with a two-level system that runs the expensive checks only in debug builds.

TL;DR: A query optimizer is a program that rewrites a program, and the rewrites are supposed to preserve meaning. Nothing in the type system enforces that. DataFusion’s answer is a set of plan invariants — properties that must hold of any valid LogicalPlan — checked after every optimizer rule, with a two-level system: the cheap structural checks always run, and the expensive semantic checks run only in debug builds. A rule that breaks an invariant is caught immediately, with the rule’s name in the error message.

There is a specific kind of bug that only query optimizers have. The optimizer rewrites SELECT ... WHERE a > 5 AND b < 3 into a form that pushes the filter down a join, and the pushed-down form is subtly wrong because a NULL on the null-extended side of an outer join behaves differently. The plan is structurally valid. It is type-correct. It produces the wrong answer.

Nothing about the type system catches this. The only defence is to state the properties explicitly and check them.

DataFusion does this in datafusion/expr/src/logical_plan/invariants.rs (508 lines) and, more importantly, in the optimizer driver, which runs the checks after every single rule.

Two levels

rust 
#[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Hash)]
pub enum InvariantLevel {
    /// Invariants that are always true in DataFusion `LogicalPlan`s
    /// such as the number of expected children and no duplicated output fields
    Always,
    /// Invariants that must hold true for the plan to be "executable"
    /// such as the type and number of function arguments are correct and
    /// that wildcards have been expanded
    ///
    /// To ensure a LogicalPlan satisfies the `Executable` invariants, run the
    /// `Analyzer`
    Executable,
}

Always — the structural invariants. The right number of children, no duplicated output field names, and so on. These are cheap and hold for every plan DataFusion ever builds.

Executable — the semantic invariants. Function argument counts and types are right, wildcards are expanded, subqueries are in legal places. These are more expensive, and they can be restored by running the Analyzer.

The two-level design is what makes it affordable to check invariants after every rule rather than only at the end of optimisation.

The checks

The Always level is, essentially, one function:

rust 
/// Apply the [`InvariantLevel::Always`] check at the current plan node only.
///
/// This does not recurs to any child nodes.
pub fn assert_always_invariants_at_current_node(plan: &LogicalPlan) -> Result<()> {
    // Refer to <https://datafusion.apache.org/contributor-guide/specification/invariants.html#relation-name-tuples-in-logical-fields-and-logical-columns-are-unique>
    assert_unique_field_names(plan)?;

    Ok(())
}

which is a schema check:

rust 
/// Returns an error if plan, and subplans, do not have unique fields.
///
/// This invariant is subject to change.
/// refer: <https://github.com/apache/datafusion/issues/13525#issuecomment-2494046463>
fn assert_unique_field_names(plan: &LogicalPlan) -> Result<()> {
    plan.schema().check_names()
}

Note the honesty: “This invariant is subject to change.” DataFusion is still deciding what the rules are, and the doc says so rather than pretending otherwise.

The Executable level adds the subquery checks, which are the meatiest part:

rust 
/// Do necessary check on subqueries and fail the invalid plan
/// 1) Check whether the outer plan is in the allowed outer plans list to use subquery expressions,
///    the allowed while list: [Projection, Filter, Window, Aggregate, Join].
/// 2) Check whether the inner plan is in the allowed inner plans list to use correlated(outer) expressions.
/// 3) Check and validate unsupported cases to use the correlated(outer) expressions inside the subquery(inner) plans/inner expressions.
///    For example, we do not want to support to use correlated expressions as the Join conditions in the subquery plan when the Join
///    is a Full Out Join
pub fn check_subquery_expr(

This is a semantic rule, not a structural one: a correlated subquery may appear in a projection, a filter, a window, an aggregate or a join — but not, say, in the LIMIT of a subquery. And a correlated reference may not be a join condition in a full outer join inside the subquery, because the null-extension makes the correlation meaningless.

These are exactly the kinds of rules that a hand-written optimiser violates by accident.

The check in the optimizer

The interesting part is where the check runs. In datafusion/optimizer/src/optimizer.rs:

rust 
.and_then(|tnr| {
    // run checks optimizer invariant checks, per optimizer rule applied
    assert_valid_optimization(&tnr.data, &starting_schema)
        .map_err(|e| e.context(format!("Check optimizer-specific invariants after optimizer rule: {}", rule.name())))?;

    // run LP invariant checks only in debug mode for performance reasons
    #[cfg(debug_assertions)]
    tnr.data.check_invariants(InvariantLevel::Executable)
        .map_err(|e| e.context(format!("Invalid (non-executable) plan after Optimizer rule: {}", rule.name())))?;

    Ok(tnr)
});

Two different checks, with two different cost profiles.

assert_valid_optimization always runs. It is the schema invariant — the rule must not change the plan’s output schema in a way that is not expressible as a cast:

rust 
/// These are invariants which should hold true before and after [`LogicalPlan`] optimization.
///
/// This differs from [`LogicalPlan::check_invariants`], which addresses if a singular
/// LogicalPlan is valid. Instead, this address if the optimization was valid based upon permitted changes.
fn assert_valid_optimization(
    plan: &LogicalPlan,
    prev_schema: &Arc<DFSchema>,
) -> Result<()> {
    // verify invariant: optimizer passes should not change the schema if the schema can't be cast from the previous schema.
    // Refer to <https://datafusion.apache.org/contributor-guide/specification/invariants.html#logical-schema-is-invariant-under-logical-optimization>
    assert_expected_schema(prev_schema, plan)?;

    Ok(())
}

This one is cheap — comparing two schemas — and it catches the most common class of optimiser bug: a rule that renames a column or drops one by accident.

The full check_invariants(Executable) is #[cfg(debug_assertions)]. In release builds it does not run at all. The comment says why: “run LP invariant checks only in debug mode for performance reasons”.

This is a really good trade-off, and it is worth dwelling on. The expensive checks are exactly the ones that catch the expensive bugs. The bugs they catch are, almost by definition, bugs in code paths that are hard to reach — so they are worth catching in debug builds (where the overhead does not matter and the developer is running the test suite) and not worth paying for in production (where the overhead is real and the bugs would have been caught already).

The error messages name the rule, which is exactly what you want when debugging:

rust 
.map_err(|e| e.context(format!("Check optimizer-specific invariants after optimizer rule: {}", rule.name())))?;

The check before the first pass

There is also a check on the input:

rust 
// verify LP is valid, before the first LP optimizer pass.
plan.check_invariants(InvariantLevel::Executable)
    .map_err(|e| e.context("Invalid input plan before LP Optimizers"))?;

Note that this one is not gated on debug_assertions — it runs in release too. The reasoning is sound: if the input plan is invalid, the optimizer’s output will be invalid too, and there is no point paying for 26 rules to produce garbage. Failing fast at the entrance is free; failing fast at the exit of every rule is not.

And a final check after the last pass:

rust 
// verify LP is valid, after the last optimizer pass.
new_plan
    .check_invariants(InvariantLevel::Executable)
    .map_err(|e| {
        e.context("Invalid (non-executable) plan after LP Optimizers")
    })?;

So the scheme is: check the input (always), check after every rule (schema only, always; full checks in debug), check the output (always).

The catch

  • The invariants are only as complete as the specification. DataFusion documents its invariants at contributor-guide/specification/invariants.html, and the code links to that document. But the specification is a work in progress — one of the checks explicitly says “This invariant is subject to change.”

  • The debug_assertions gate means release builds have weaker guarantees. That is a deliberate trade, but it means a bug that only the Executable invariants would catch can reach production. The mitigation is that the test suite runs in debug mode.

  • The checks are not free even at the Always level. The schema check runs after every rule, on every pass, on every plan. For a large plan with 26 rules and 3 passes, that is 78 schema comparisons. The comparison is logically_equivalent_names_and_types, which ignores metadata and nullability — deliberately looser than equality, and therefore cheaper.

  • Extension nodes can add their own invariants, which is how third-party operators participate:

    rust 
    fn assert_valid_extension_nodes(plan: &LogicalPlan, check: InvariantLevel) -> Result<()> {
    plan.apply_with_subqueries(|plan: &LogicalPlan| {
        if let LogicalPlan::Extension(Extension { node }) = plan {
            node.check_invariants(check)?;
        }
        ...

    and the traversal recurses into subqueries inside expressions, which is the fiddly part:

    rust 
    plan.apply_expressions(|expr| {
    // recursively look for subqueries
    expr.apply(|expr| {
        match expr {
            Expr::Exists(Exists { subquery, .. })
            | Expr::InSubquery(InSubquery { subquery, .. })
            | Expr::SetComparison(SetComparison { subquery, .. })
            | Expr::ScalarSubquery(subquery) => {
                assert_valid_extension_nodes(&subquery.subquery, check)?;
            }
            _ => {}
        }
        Ok(TreeNodeRecursion::Continue)
    })
})

    Note that apply_with_subqueries is used for the plan traversal, and additionally a manual expression traversal for subqueries — because subquery plans live inside expressions, not in the plan’s child slots.

Why it matters

The value of invariant checking is not that it prevents bugs. It is that it turns “the optimiser produced a wrong answer” into “the optimiser produced a plan that violates rule X, in rule Y”. The first is a data-correctness incident; the second is a five-minute fix.

And the two-level design is the part that makes it viable: a system that checked everything after every rule would be too slow to ship, and a system that checked nothing would be too fragile to maintain. Checking the cheap thing always, the expensive thing in debug, and naming the offending rule in the error — that is the engineering.

DatafusionOptimizerCorrectnessInternalsDesign