TL;DR: Optimizer rules can undo each other. PushDownFilter can push a predicate down, and another rule can pull it back up, and if the optimizer just kept looping it would never terminate. DataFusion runs rules in passes and stops when a pass produces a plan it has already seen. The “already seen” test is a LogicalPlanSignature — the plan’s node count plus a hash of its contents — and the seen-plans are kept in a HashSet that grows with each pass.

Termination is the boring half of fixed-point optimization, and it is where most optimizer implementations get sloppy.

The naive approach is a pass counter: “run at most N passes”. That works, but it means every query pays N passes even if the second one changed nothing. And a plan that oscillates between two shapes will happily burn all N passes producing the same answer.

DataFusion’s approach is better: it detects the fixed point.

The loop

The optimizer driver is Optimizer::optimize (datafusion/optimizer/src/optimizer.rs):

let mut previous_plans = HashSet::with_capacity(16);
previous_plans.insert(LogicalPlanSignature::new(&new_plan));

let starting_schema = Arc::clone(new_plan.schema());

let mut i = 0;
while i < options.optimizer.max_passes {
    ...
    for rule in &self.rules {
        ...
    }
    log_plan(&format!("Optimized plan (pass {i})"), &new_plan);

    // HashSet::insert returns, whether the value was newly inserted.
    let plan_is_fresh =
        previous_plans.insert(LogicalPlanSignature::new(&new_plan));
    if !plan_is_fresh {
        // plan did not change, so no need to continue trying to optimize
        debug!("optimizer pass {i} did not make changes");
        break;
    }
    i += 1;
}

Two mechanisms, deliberately separate:

• max_passes is the hard cap — a safety net. If the rules somehow keep producing genuinely new plans forever, the optimizer gives up.
• The previous_plans set is the early exit — the normal case.

The HashSet::with_capacity(16) is a small but revealing detail: the authors expect a typical query to reach its fixed point in a handful of passes, and pre-allocating 16 slots avoids rehashing during the first passes.

The insert returning false means “we have seen this exact plan before”. Note that this is not the same as “the plan is unchanged since the last pass” — it is “the plan is unchanged since any previous pass”, which is exactly what you want for cycle detection. Two rules that push a predicate down and pull it back up produce plan A, plan B, plan A — and the third pass is caught immediately rather than after max_passes iterations.

The signature

LogicalPlanSignature (datafusion/optimizer/src/plan_signature.rs) is the identity used for that comparison:

#[derive(Clone, Copy, PartialEq, Eq, Hash)]
pub struct LogicalPlanSignature {
    node_number: NonZeroUsize,
    plan_hash: u64,
}

Two components. The node count is obtained by a traversal:

/// Get total number of [`LogicalPlan`]s in the plan.
fn get_node_number(plan: &LogicalPlan) -> NonZeroUsize {
    let mut node_number = 0;
    plan.apply_with_subqueries(|_plan| {
        node_number += 1;
        Ok(TreeNodeRecursion::Continue)
    })
    // Closure always return Ok
    .unwrap();
    // Visitor must have at least visited the root,
    // so v.node_number is at least 1.
    NonZeroUsize::new(node_number).unwrap()
}

and the hash is the plan’s own Hash implementation:

pub fn new(plan: &LogicalPlan) -> Self {
    let mut hasher = DefaultHasher::new();
    plan.hash(&mut hasher);

    Self {
        node_number: get_node_number(plan),
        plan_hash: hasher.finish(),
    }
}

The node count is a cheap, structural discriminator that makes hash collisions vanishingly unlikely: two plans with different node counts cannot be confused, so a collision requires two plans with the same node count and the same 64-bit hash.

The doc comment is careful about the guarantees:

If p1 and p2 have a different number of LogicalPlans, then they will have different LogicalPlanSignatures.

If p1 and p2 have a different Hash, then they will have different LogicalPlanSignatures.

Caveats

The intention of LogicalPlanSignature is to have a lower chance of hash collisions.

There exist different LogicalPlans with the same LogicalPlanSignature.

When two LogicalPlans differ only in metadata, then they will have the same LogicalPlanSignatures (due to hash implementation in LogicalPlan).

That last caveat is worth dwelling on. The signature is a heuristic identity, not a true one. Two different plans that differ only in metadata hash the same and have the same node count, so they share a signature. The consequence is benign in this context: the optimizer will stop one pass earlier than it theoretically could. The alternative — a true structural equality — would require comparing every node of every plan on every pass, which is exactly the cost this design is trying to avoid.

Why not just compare the plans?

Because comparing two LogicalPlans structurally is O(size of plan), and the optimizer does it after every pass. For a plan of a few dozen nodes that is not free, but it is not free repeatedly either.

The hash is computed with DefaultHasher, which is SipHash-1-3 — a seeded hasher whose seed is fixed per-process (zero-initialised DefaultHasher). That gives a strong guarantee against adversarial collisions for hash-map use, and it is fast enough for a plan-sized input.

The traversal for the node count is a second walk of the plan, on top of the hash. That sounds wasteful, but the hash itself has to walk the tree anyway, and the count is a counter increment in the same closure shape. Two walks of a 50-node tree is microseconds.

Actually — it is not the same walk. get_node_number uses apply_with_subqueries, which visits nested plans inside expressions. The hash walks the plan’s own Hash implementation. They are different traversals, but both are O(plan size), and both are dwarfed by the 26 rule rewrites that follow.

The cap

max_passes is a config option:

pub fn with_max_passes(mut self, v: u8) -> Self {
    Arc::make_mut(&mut self.options).optimizer.max_passes = v as usize;
    self
}

The default is a small number (three, in the shipped configuration), which tells you how much the DataFusion developers trust the fixed-point detection to do the real work. If the detection were unreliable, the cap would need to be large enough to cover the worst case; a small default means the detection is expected to fire quickly.

There is even a test for the pathological case — a rule that rotates a projection, which is a classic way to make an optimizer oscillate:

fn optimizer_detects_plan_equal_to_the_initial() -> Result<()> {
    let opt = Optimizer::with_rules(vec![Arc::new(RotateProjectionRule::new(false))]);
    let config = OptimizerContext::new().with_max_passes(16);
    ...

Note with_max_passes(16) in the test: the test gives the optimizer a generous cap precisely so that it is the detection that terminates the loop, not the cap. If the detection were broken, the test would run 16 passes instead of 2 and the assertions would catch it.

The catch

• A hash collision terminates the optimizer early. The probability with a 64-bit hash is negligible, but it is not zero, and the failure mode is silent: you get a slightly less-optimised plan, not an error.
• Metadata-only differences are invisible. Two plans that differ only in metadata are considered “the same plan”. This is documented, and the consequences are mild.
• The previous_plans set grows with the number of passes. It is bounded by max_passes, so it is bounded by a small constant, but it is not free: each pass computes a fresh signature, which is a full plan hash.
• Detection requires a complete pass. The check happens after all 26 rules have run, not after each rule. A plan that oscillates within a pass (rule A undoes rule B, rule C undoes rule A) will not be detected until the pass completes — but it will be detected, because the signature is compared against all previous passes, not just the previous one.

The broader idea

Fixed-point detection by plan identity is a general technique. Compilers use it (hash-consing, “seen this IR before” caches). Query planners use it. What DataFusion does well here is the specificity of the signature: the node count is a structural discriminator that makes the cheap 64-bit hash safe to use as an identity for termination purposes.

The alternative — comparing plans structurally — would be correct in all cases and would cost O(plan) per pass instead of O(plan) per pass plus a hash. Same order of magnitude, honestly. The real win is the early exit: the fixed point is usually reached in pass two, and the set-based check lets the optimizer skip the remaining rules entirely rather than running them and discovering they are no-ops.