CockroachDB join reordering could discard required predicates

A join optimizer can change the order of operations while preserving the query's meaning. It cannot discard a condition simply because that condition is difficult to place in the new tree. CockroachDB advisory A-76522 describes a failure where logic intended to prevent invalid predicate placement instead caused valid predicates to disappear.

The March 9 advisory says query plans can omit join ON conditions and return incorrect results. The bug has been observed with four or more joins, but the advisory explicitly leaves open the possibility of fewer joins being affected. It identifies the 20.2, 21.1, and 21.2 branches, with repairs in maintenance versions 21.1.16 and 21.2.7.

I value CockroachDB's explicit consistency model. Query optimization still has a separate obligation to preserve the requested relational operation. A serializable execution of a plan missing a filter can produce a consistent execution of the wrong query.

Reordering has to preserve the complete condition

The public issue 76522 supplies a five-table example and an optimized plan. Its source SQL includes equality conditions connecting several tables. The report points out that two conditions disappear from the resulting plan, including an equality on columns deliberately named should_not_be_eliminated.

That name makes the regression easy to identify, but the condition is ordinary SQL. It compares values from two relations and should constrain which joined rows survive. If the plan combines those relations without evaluating that equality or an equivalent condition, it can admit combinations excluded by the original statement.

The issue includes injected statistics to produce the relevant optimizer choice. That does not make the problem an error in cardinality estimation alone. Statistics influence which candidate plan the optimizer selects. Every selectable plan must still preserve the query's conditions, even when the estimated row counts favor a different join order.

This is the distinction between choosing an expensive correct plan and choosing an incorrect plan. Inaccurate estimates can explain performance surprises without changing query meaning. An omitted nonredundant condition changes the operation itself. The advisory concerns the latter failure.

Predicates require their referenced relations

The repair in pull request 76334, merged February 15, explains the join-order-builder logic. It tried to prevent orphaned predicates, meaning predicates that reference a relation absent from the inputs of the join where the predicate would be evaluated.

That is a valid property to enforce. A condition comparing columns from two tables needs access to those columns. Reordering can move the point at which both inputs become available, so the optimizer needs eligibility information that says where the condition can legally appear.

The patch description identifies checks in the associativity and left or right exchange logic. In rare cases, those checks generated invalid conflict rules for join-graph edges. Those rules could then prevent a valid predicate from being added to the reordered tree.

The attempted protection therefore constrained the search incorrectly. Instead of merely rejecting an illegal placement, it could exclude the condition from the final construction. The resulting tree was not equivalent to the original query, despite having a valid-looking arrangement of joins and access paths.

The repair removes duplicate reasoning

The patch removes the problematic conditionals because the underlying algorithm already checks predicate eligibility. Its description names the total eligibility set, which must be a subset of a join's input relations. The existing inner-join and non-inner-join checks already enforced that requirement.

This is a specific case where additional protective logic made the implementation less correct. Two pieces of code attempted to enforce a related condition through different representations. The extra conflict-rule generation did not merely repeat the existing check. It introduced invalid restrictions that changed which filters survived planning.

The repair retains the required eligibility condition through the established checks and removes the inconsistent extra logic. That explanation is more useful than describing the change as a broader search or a smarter optimizer. The issue concerns maintaining a valid mapping between predicates and available inputs.

I find the removal instructive because it preserves a precise invariant. A valid predicate must reach a place where its referenced relations are available. Preventing orphaned predicates cannot mean silently omitting predicates that still belong to the query.

The observed join count is not a safe boundary

The advisory says the bug has only been observed with at least four joins. It immediately qualifies that observation by saying fewer may be affected. A statement with three joins therefore cannot be declared safe solely from the published report's observed size.

Likewise, one plan captured during investigation does not imply that a statement always gets that plan. The original reproduction uses statistics to influence reordering. That evidence supports a dependency on planning choices, rather than a guarantee that a specific SQL text either always fails or always succeeds independently of its planning context.

The affected-version range is broader than the currently named repair versions. The advisory lists deployments through 20.2.19, 21.1.15, and 21.2.6 as exposed. Its repair description says the defect has existed since 20.2. Users need a version containing the fix, rather than assuming that an older major branch avoids the optimizer behavior.

The remedy changes future plans

The published mitigation is upgrading to a maintenance version carrying the repair. The advisory does not direct users to rebuild table indexes. Its subject is the conditions present in a query plan, not persistent corruption of an index representation.

That difference matters for an incident response. Reconstructing data structures cannot establish that a faulty optimizer will retain a predicate when it generates the next plan. The corrected join-order logic addresses the place where the condition disappears.

The regression also shows why an execution plan is useful beyond performance analysis. The issue compares the requested equalities with those actually represented in the optimized tree. A plan can reveal which relational conditions survived transformation, giving the maintainer concrete evidence about a wrong result before investigating storage or transaction scheduling.