CockroachDB 2.1.1 decorrelates EXISTS with generator functions

An array-valued column can make an ordinary existence question difficult for an optimizer. The inner query generates rows from the current outer row's array, then tests whether any generated value qualifies. That dependency is a correlated subquery. CockroachDB 2.1.1 repairs decorrelation for many EXISTS queries containing generator functions, including this pattern.

The November 19 release notes describe broader successful execution of correlated EXISTS queries. The underlying patch makes the scope more precise. It concerns generator functions represented by the optimizer's Zip operator, along with filter placement and preservation of join conditions. The change should not be described as the introduction of all correlated-subquery support.

I value CockroachDB's PostgreSQL-compatible interface because existing application queries have a better chance of remaining usable. Optimizer support is part of that compatibility. A valid expression still needs an executable plan, and a decorrelation error exposes the boundary between recognizing the query and being able to run it.

The inner query depends on the current row

Rebecca Taft's patch in pull request 32026 includes an article table with a string-array tag column. Its regression query uses unnest inside EXISTS to search that array. A reduced version preserves the important dependency:

SELECT a.id
FROM articles AS a
WHERE EXISTS (
  SELECT *
  FROM unnest(a.tag_list) AS tag
  WHERE tag = 'dragons'
);

This assumes an articles table with an id column and a tag_list string-array column, as in the patch's test. The inner input is a.tag_list, so the generated values depend on the outer article. A planner cannot execute the inner expression as one independent relation without accounting for that dependence.

EXISTS also has a particular multiplicity rule. An article qualifies when at least one generated tag matches. Two matching tags must not produce two copies of the article merely because an internal rewrite uses a join. The transformed plan has to preserve the original existence question, including the distinction between no match and one or more matches.

That makes this a useful case for explaining decorrelation. The optimizer is changing the internal expression of the query so its executor can run it. The transformation needs to preserve the result, not just remove an inconvenient reference from the syntax tree. Generated rows make that preservation more involved than moving an independent scalar expression.

The direct SQL remains useful documentation of the application's intent. It asks a yes-or-no question about each article's tags without making the application reconstruct that question as several requests. Broader execution support removes a reason for an application-side workaround. It also keeps the dependency between the outer article and its array visible in one statement, where a reader can assess what the query means.

The rewrite retains the outer row's identity

The patch introduces TryDecorrelateSemiJoinZip. Its comments describe turning a semi-join involving the generated-row operator into a grouping and inner-join form so further rules can decorrelate it. The transformation ensures a key for the outer input and groups by that key. This gives the rewrite a way to retain the original row's identity while processing multiple generated matches.

The execution-builder test shows the resulting sequence of a scan, generated rows and a filter, followed by grouping. Its original query also orders and limits articles. Those later operations depend on receiving the intended article rows after the existence condition, rather than receiving arbitrary duplicates produced by the generator.

The patch additionally prevents filter movement around Zip in the affected rules and ensures InnerJoinApply conditions survive in the execution builder. A missing condition can change which rows qualify. A condition evaluated at the wrong level can likewise change the relationship between generated rows and their outer input. The repair therefore includes correctness details beyond making the planner accept more queries.

My preference is to judge optimizer changes against those preserved semantics. A successful plan is useful only if it still answers the original question. This patch's tests and rule comments make the relevant properties visible, including the outer key and the filter that selects the desired generated values.

A maintenance backport keeps the existing operator

Taft explains that the corresponding development change uses a replacement operator called ProjectSet. Backporting that larger change was considered too costly, so the release-branch patch works with Zip. This is a concrete maintenance tradeoff, retaining the branch's existing representation while supplying the needed transformation and condition handling.

That limits the change without reducing it to a generic promise of improved planning. The user-visible result is support for the documented generator-function EXISTS cases. The implementation strategy is specific to the branch being maintained. Neither fact implies that every possible correlated expression now has a valid decorrelation rule.

For applications using arrays in existence predicates, 2.1.1 removes a particular planning failure. The query can retain its direct expression of an article having a matching tag. Internally, the optimizer now has a transformation that accounts for generated rows, preserves the qualifying condition and returns the outer row with the multiplicity EXISTS requires.