Repository navigation
Two correlated EXISTS over UNNEST do not plan under top-down decorrelation: Unknown join type LEFT_MARK #163
Description
With topDownGeneralDecorrelationEnabled=true, a statement carrying two correlated EXISTS over UNNEST does not plan. One is fine. The second one arrives as a LogicalConditionalCorrelate still in the NONE convention, and planning fails:
java.lang.IllegalStateException: Unknown join type LEFT_MARK for correlate relation
rel#571:LogicalConditionalCorrelate.NONE.[](left=LogicalUnion#561, right=LogicalFilter#569,
correlation=$cor0, joinType=left_mark, requiredColumns={1})
Reproduction
No adapter, no EF — VALUES and UNNEST only, so the whole plan is ClrEnumerable*.
Plans (one quantifier):
SELECT t."id" FROM (VALUES (1, ARRAY['a','b']), (2, ARRAY['c'])) AS t("id", "tags")
WHERE EXISTS (SELECT 1 FROM UNNEST(t."tags") AS x WHERE x = 'a')ClrEnumerableCalc(expr#0..2=[{inputs}], id=[$t0], $condition=[$t2])
ClrEnumerableConditionalCorrelate(correlation=[$cor0], joinType=[left_mark], requiredColumns=[{1}])
ClrEnumerableUnion(all=[true])
...
Fails (two quantifiers): add a second EXISTS over the same array —
SELECT t."id" FROM (VALUES (1, ARRAY['a','b']), (2, ARRAY['c'])) AS t("id", "tags")
WHERE EXISTS (SELECT 1 FROM UNNEST(t."tags") AS x WHERE x = 'a')
AND EXISTS (SELECT 1 FROM UNNEST(t."tags") AS y WHERE y = 'b')OR instead of AND fails identically.
As a test, in Apache.Calcite.Data.Tests. One_quantifier passes; Two_quantifiers fails.
using System;
using Xunit;
namespace Apache.Calcite.Data.Tests
{
public class Issue163Tests
{
const string ConnectionString =
"Model=inline:{\"version\":\"1.0\",\"defaultSchema\":\"adhoc\",\"schemas\":[{\"name\":\"adhoc\"}]};Schema=adhoc";
static object? Scalar(string sql)
{
var b = new CalciteConnectionStringBuilder(ConnectionString)
{
TopDownGeneralDecorrelationEnabled = true,
};
using var c = new CalciteConnection(b);
c.Open();
using var cmd = c.CreateCommand();
cmd.CommandText = sql;
return cmd.ExecuteScalar();
}
[Fact]
public void One_quantifier()
{
Assert.Equal(1, Convert.ToInt32(Scalar(
"SELECT t.\"id\" FROM (VALUES (1, ARRAY['a','b']), (2, ARRAY['c'])) AS t(\"id\", \"tags\") " +
"WHERE EXISTS (SELECT 1 FROM UNNEST(t.\"tags\") AS x WHERE x = 'a')")));
}
[Fact]
public void Two_quantifiers()
{
Assert.Equal(1, Convert.ToInt32(Scalar(
"SELECT t.\"id\" FROM (VALUES (1, ARRAY['a','b']), (2, ARRAY['c'])) AS t(\"id\", \"tags\") " +
"WHERE EXISTS (SELECT 1 FROM UNNEST(t.\"tags\") AS x WHERE x = 'a') " +
"AND EXISTS (SELECT 1 FROM UNNEST(t.\"tags\") AS y WHERE y = 'b')")));
}
}
}src\Apache.Calcite.Data.Tests\bin\Debug\net10.0\Apache.Calcite.Data.Tests.exe -class Apache.Calcite.Data.Tests.Issue163Tests
Apache.Calcite.Data.Tests.Issue163Tests.Two_quantifiers [FAIL]
Apache.Calcite.Data.CalciteException : Failed to execute Calcite statement.
---- java.lang.IllegalStateException : Unknown join type LEFT_MARK for correlate relation rel#571:LogicalConditionalCorrelate.NONE.[](left=LogicalUnion#561,right=LogicalFilter#569,correlation=$cor0,joinType=left_mark,requiredColumns={1})
----- Inner Stack Trace -----
RelMdColumnUniqueness.java(223,0): at org.apache.calcite.rel.metadata.RelMdColumnUniqueness.areColumnsUnique(Correlate rel, RelMetadataQuery mq, ImmutableBitSet columns, Boolean ignoreNulls)
at GeneratedMetadata_ColumnUniqueness_5.areColumnsUnique(RelNode, RelMetadataQuery, ImmutableBitSet, Boolean)
RelMetadataQuery.java(619,0): at org.apache.calcite.rel.metadata.RelMetadataQuery.areColumnsUnique(RelNode rel, ImmutableBitSet columns, Boolean ignoreNulls)
RelMdColumnUniqueness.java(111,0): at org.apache.calcite.rel.metadata.RelMdColumnUniqueness.areColumnsUnique(Filter rel, RelMetadataQuery mq, ImmutableBitSet columns, Boolean ignoreNulls)
at GeneratedMetadata_ColumnUniqueness_5.areColumnsUnique(RelNode, RelMetadataQuery, ImmutableBitSet, Boolean)
RelMetadataQuery.java(619,0): at org.apache.calcite.rel.metadata.RelMetadataQuery.areColumnsUnique(RelNode rel, ImmutableBitSet columns, Boolean ignoreNulls)
RelMdColumnUniqueness.java(290,0): at org.apache.calcite.rel.metadata.RelMdColumnUniqueness.areProjectColumnsUnique(SingleRel rel, RelMetadataQuery mq, ImmutableBitSet columns, Boolean ignoreNulls, List projExprs)
RelMdColumnUniqueness.java(239,0): at org.apache.calcite.rel.metadata.RelMdColumnUniqueness.areColumnsUnique(Project rel, RelMetadataQuery mq, ImmutableBitSet columns, Boolean ignoreNulls)
at GeneratedMetadata_ColumnUniqueness_5.areColumnsUnique(RelNode, RelMetadataQuery, ImmutableBitSet, Boolean)
RelMetadataQuery.java(619,0): at org.apache.calcite.rel.metadata.RelMetadataQuery.areColumnsUnique(RelNode rel, ImmutableBitSet columns, Boolean ignoreNulls)
RelMetadataQuery.java(599,0): at org.apache.calcite.rel.metadata.RelMetadataQuery.areColumnsUnique(RelNode rel, ImmutableBitSet columns)
RelBuilder.java(2766,0): at org.apache.calcite.tools.RelBuilder.alreadyUnique(List aggCallList, GroupKeyImpl groupKey, ImmutableBitSet groupSet, List extraNodes)
RelBuilder.java(2551,0): at org.apache.calcite.tools.RelBuilder.aggregate_(GroupKeyImpl groupKey, ImmutableList aggCalls)
RelBuilder.java(2497,0): at org.apache.calcite.tools.RelBuilder.distinct()
TopDownGeneralDecorrelator.java(1243,0): at org.apache.calcite.sql2rel.TopDownGeneralDecorrelator.DedupFreeVarsNode.create(RelNode newLeft, UnnestedQuery leftInfo, NavigableSet corDefs, RelBuilder builder)
TopDownGeneralDecorrelator.java(329,0): at org.apache.calcite.sql2rel.TopDownGeneralDecorrelator.correlateElimination(RelNode rel, Boolean allowEmptyOutputFromRewrite)
TopDownGeneralDecorrelator.java(294,0): at org.apache.calcite.sql2rel.TopDownGeneralDecorrelator.correlateElimination(RelNode rel, Boolean allowEmptyOutputFromRewrite)
TopDownGeneralDecorrelator.java(294,0): at org.apache.calcite.sql2rel.TopDownGeneralDecorrelator.correlateElimination(RelNode rel, Boolean allowEmptyOutputFromRewrite)
TopDownGeneralDecorrelator.java(294,0): at org.apache.calcite.sql2rel.TopDownGeneralDecorrelator.correlateElimination(RelNode rel, Boolean allowEmptyOutputFromRewrite)
TopDownGeneralDecorrelator.java(240,0): at org.apache.calcite.sql2rel.TopDownGeneralDecorrelator.decorrelateQuery(RelNode rel, RelBuilder builder)
Programs.java(458,0): at org.apache.calcite.tools.Programs.DecorrelateProgram.run(RelOptPlanner planner, RelNode rel, RelTraitSet requiredOutputTraits, List materializations, List lattices)
...
What does and does not trigger it
| case | top-down | default |
|---|---|---|
one EXISTS over UNNEST |
plans | plans |
two EXISTS over UNNEST, AND |
fails | plans |
two EXISTS over UNNEST, OR |
fails | plans |
two EXISTS over ordinary subqueries (no UNNEST) |
plans | plans |
one EXISTS over UNNEST OR a scalar predicate |
plans | plans |
Two things narrow it:
- It needs both
UNNESTand more than one quantifier. Two correlatedEXISTSover ordinaryVALUESsubqueries plan fine, and becomeClrEnumerableHashJoin(joinType=[semi])over aClrEnumerableHashJoin(joinType=[left_mark])— soleft_markis implemented on a hash join; it is theConditionalCorrelatethat has no implementation for it. - With
topDownGeneralDecorrelationEnabledunset (defaultRelDecorrelator) both forms plan, as nestedClrEnumerableCorrelate(joinType=[inner]).
Impact
It is not an exotic shape. Any filter that asks two questions of arrays on the same row hits it — "in this city or that state", or a locality filter that also projects the array it filtered on. In a service built on this it forced a schema change: two arrays merged into one column so the search could be a single quantifier, and the values re-exposed as scalars so a filtered query could still return them.
Versions
Apache.Calcite.Data / Apache.Calcite.Adapter.AdoNet / Apache.Calcite.Extensions 2.0.1-pre.188, .NET 10, win-x64. Deterministic — every run, both AND and OR.
Related
- Flaky: correlated EXISTS over UNCOLLECT with top-down decorrelation trips a HepPlanner assertion on arm64 #150 is a different failure on a neighbouring shape: flaky, arm64-only, a single
EXISTSoverUNCOLLECT, tripping aHepPlannerassertion. This one is deterministic on x64 and needs two. - Correlated EXISTS over an unnest does not decorrelate: $cor1 unbound at execution (the 'correlate over uncollect' half of #47 survives) #125 is the reason
topDownGeneralDecorrelationEnabledwas turned on in the first place. Worth noting there: theEXISTS-over-UNNESTshape that used to raiseCorrelation variable $cor1 should be definednow answers under the default decorrelator on pre.188, so the workaround that leads into this bug may no longer be needed.
Activity
wasabii commentedon Sep 19, 2026
Worth adding context on why this matters beyond the shapes above: the top-down general decorrelator is the better decorrelator and is expected to become the default. So this is not a defect in an opt-in path that callers can simply decline — it is a defect in the path everything will take, and today it is the thing standing between a caller and adopting it.
We have pinned to
RelDecorrelatorto get the two shapes back, and marked the pin in the code as temporary rather than as a preference. That pin only holds because #125's shape stopped reproducing under the default on pre.188; it is not a position we can keep once the default changes.