This is an automated email from the ASF dual-hosted git repository.
xuzifu666 pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/calcite.git
The following commit(s) were added to refs/heads/main by this push:
new 81ec38a191 [CALCITE-5845] Select a very large predicate throw threw
'java.lang.StackOverflowError' exception in SqlNode to RelNode phase
81ec38a191 is described below
commit 81ec38a19198b2e410d3fee443512f0c9142c8f1
Author: Yu Xu <[email protected]>
AuthorDate: Sun Nov 1 12:50:47 2026 +0800
[CALCITE-5845] Select a very large predicate throw threw
'java.lang.StackOverflowError' exception in SqlNode to RelNode phase
---
.../java/org/apache/calcite/plan/RelOptUtil.java | 126 +++++++++++++--------
.../main/java/org/apache/calcite/rex/RexUtil.java | 65 ++++++++---
.../calcite/sql2rel/StandardConvertletTable.java | 75 ++++++++++++
.../org/apache/calcite/plan/RelOptUtilTest.java | 82 ++++++++++++++
.../java/org/apache/calcite/rex/RexUtilTest.java | 92 +++++++++++++++
.../java/org/apache/calcite/test/SmallStack.java | 62 ++++++++++
.../apache/calcite/test/SqlToRelConverterTest.java | 99 ++++++++++++++++
7 files changed, 540 insertions(+), 61 deletions(-)
diff --git a/core/src/main/java/org/apache/calcite/plan/RelOptUtil.java
b/core/src/main/java/org/apache/calcite/plan/RelOptUtil.java
index d92a436595..a9e0db57f6 100644
--- a/core/src/main/java/org/apache/calcite/plan/RelOptUtil.java
+++ b/core/src/main/java/org/apache/calcite/plan/RelOptUtil.java
@@ -2559,15 +2559,27 @@ public static List<RelDataTypeField> deduplicateColumns(
public static void decomposeConjunction(
@Nullable RexNode rexPredicate,
List<RexNode> rexList) {
- if (rexPredicate == null || rexPredicate.isAlwaysTrue()) {
+ // Use an explicit stack to avoid StackOverflowError on deeply nested ANDs
+ // (e.g. CALCITE-5845)
+ if (rexPredicate == null) {
return;
}
- if (rexPredicate.isA(SqlKind.AND)) {
- for (RexNode operand : ((RexCall) rexPredicate).getOperands()) {
- decomposeConjunction(operand, rexList);
+ final Deque<RexNode> stack = new ArrayDeque<>();
+ stack.push(rexPredicate);
+ while (!stack.isEmpty()) {
+ final RexNode node = stack.pop();
+ if (node.isAlwaysTrue()) {
+ continue;
+ }
+ if (node.isA(SqlKind.AND)) {
+ final List<RexNode> operands = ((RexCall) node).getOperands();
+ // Push in reverse order so that the leftmost operand is processed
first
+ for (int i = operands.size() - 1; i >= 0; i--) {
+ stack.push(operands.get(i));
+ }
+ } else {
+ rexList.add(node);
}
- } else {
- rexList.add(rexPredicate);
}
}
@@ -2593,47 +2605,59 @@ public static void decomposeConjunction(
@Nullable RexNode rexPredicate,
List<RexNode> rexList,
List<RexNode> notList) {
- if (rexPredicate == null || rexPredicate.isAlwaysTrue()) {
+ // Use an explicit stack to avoid StackOverflowError on deeply nested
+ // expressions (e.g. CALCITE-5845)
+ if (rexPredicate == null) {
return;
}
- switch (rexPredicate.getKind()) {
- case AND:
- for (RexNode operand : ((RexCall) rexPredicate).getOperands()) {
- decomposeConjunction(operand, rexList, notList);
- }
- break;
- case NOT:
- final RexNode e = ((RexCall) rexPredicate).getOperands().get(0);
- if (e.isAlwaysFalse()) {
- return;
+ final Deque<RexNode> stack = new ArrayDeque<>();
+ stack.push(rexPredicate);
+ while (!stack.isEmpty()) {
+ final RexNode node = stack.pop();
+ if (node.isAlwaysTrue()) {
+ continue;
}
- switch (e.getKind()) {
- case OR:
- final List<RexNode> ors = new ArrayList<>();
- decomposeDisjunction(e, ors);
- for (RexNode or : ors) {
- switch (or.getKind()) {
- case NOT:
- rexList.add(((RexCall) or).operands.get(0));
- break;
- default:
- notList.add(or);
+ switch (node.getKind()) {
+ case AND:
+ final List<RexNode> operands = ((RexCall) node).getOperands();
+ // Push in reverse order so that the leftmost operand is processed
first
+ for (int i = operands.size() - 1; i >= 0; i--) {
+ stack.push(operands.get(i));
+ }
+ break;
+ case NOT:
+ final RexNode e = ((RexCall) node).getOperands().get(0);
+ if (e.isAlwaysFalse()) {
+ break;
+ }
+ switch (e.getKind()) {
+ case OR:
+ final List<RexNode> ors = new ArrayList<>();
+ decomposeDisjunction(e, ors);
+ for (RexNode or : ors) {
+ switch (or.getKind()) {
+ case NOT:
+ rexList.add(((RexCall) or).operands.get(0));
+ break;
+ default:
+ notList.add(or);
+ }
}
+ break;
+ default:
+ notList.add(e);
}
break;
+ case LITERAL:
+ if (!RexLiteral.isNullLiteral(node)
+ && RexLiteral.booleanValue(node)) {
+ break; // ignore TRUE
+ }
+ // fall through
default:
- notList.add(e);
- }
- break;
- case LITERAL:
- if (!RexLiteral.isNullLiteral(rexPredicate)
- && RexLiteral.booleanValue(rexPredicate)) {
- return; // ignore TRUE
+ rexList.add(node);
+ break;
}
- // fall through
- default:
- rexList.add(rexPredicate);
- break;
}
}
@@ -2647,15 +2671,27 @@ public static void decomposeConjunction(
public static void decomposeDisjunction(
@Nullable RexNode rexPredicate,
List<RexNode> rexList) {
- if (rexPredicate == null || rexPredicate.isAlwaysFalse()) {
+ // Use an explicit stack to avoid StackOverflowError on deeply nested ORs
+ // (e.g. CALCITE-5845)
+ if (rexPredicate == null) {
return;
}
- if (rexPredicate.isA(SqlKind.OR)) {
- for (RexNode operand : ((RexCall) rexPredicate).getOperands()) {
- decomposeDisjunction(operand, rexList);
+ final Deque<RexNode> stack = new ArrayDeque<>();
+ stack.push(rexPredicate);
+ while (!stack.isEmpty()) {
+ final RexNode node = stack.pop();
+ if (node.isAlwaysFalse()) {
+ continue;
+ }
+ if (node.isA(SqlKind.OR)) {
+ final List<RexNode> operands = ((RexCall) node).getOperands();
+ // Push in reverse order so that the leftmost operand is processed
first
+ for (int i = operands.size() - 1; i >= 0; i--) {
+ stack.push(operands.get(i));
+ }
+ } else {
+ rexList.add(node);
}
- } else {
- rexList.add(rexPredicate);
}
}
diff --git a/core/src/main/java/org/apache/calcite/rex/RexUtil.java
b/core/src/main/java/org/apache/calcite/rex/RexUtil.java
index 71f4acfef9..b340e1ba78 100644
--- a/core/src/main/java/org/apache/calcite/rex/RexUtil.java
+++ b/core/src/main/java/org/apache/calcite/rex/RexUtil.java
@@ -67,10 +67,12 @@
import java.math.BigDecimal;
import java.math.RoundingMode;
+import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.Collections;
+import java.util.Deque;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Iterator;
@@ -1519,15 +1521,22 @@ public static ImmutableList<RexNode> flattenAnd(
private static void addAnd(ImmutableList.Builder<RexNode> builder,
Set<RexNode> digests, RexNode node) {
- switch (node.getKind()) {
- case AND:
- for (RexNode operand : ((RexCall) node).getOperands()) {
- addAnd(builder, digests, operand);
- }
- return;
- default:
- if (!node.isAlwaysTrue() && digests.add(node)) {
- builder.add(node);
+ // Use an explicit stack to avoid StackOverflowError on deeply nested ANDs
+ // (e.g. CALCITE-5845)
+ final Deque<RexNode> stack = new ArrayDeque<>();
+ stack.push(node);
+ while (!stack.isEmpty()) {
+ final RexNode current = stack.pop();
+ if (current.getKind() == SqlKind.AND) {
+ final List<RexNode> operands = ((RexCall) current).getOperands();
+ // Push in reverse order so that the leftmost operand is processed
first
+ for (int i = operands.size() - 1; i >= 0; i--) {
+ stack.push(operands.get(i));
+ }
+ } else {
+ if (!current.isAlwaysTrue() && digests.add(current)) {
+ builder.add(current);
+ }
}
}
}
@@ -1823,20 +1832,44 @@ private static boolean isFlat(
* calls to an associative operator such as AND and OR.
*/
public static boolean isFlat(RexNode expr) {
- if (!(expr instanceof RexCall)) {
- return true;
+ // Use an explicit stack to avoid StackOverflowError on deeply nested
+ // expressions (e.g. CALCITE-5845)
+ final Deque<RexNode> stack = new ArrayDeque<>();
+ stack.push(expr);
+ while (!stack.isEmpty()) {
+ final RexNode current = stack.pop();
+ if (!(current instanceof RexCall)) {
+ continue;
+ }
+ final RexCall call = (RexCall) current;
+ if (!isFlat(call.getOperands(), call.getOperator())) {
+ return false;
+ }
+ for (RexNode operand : call.getOperands()) {
+ stack.push(operand);
+ }
}
- final RexCall call = (RexCall) expr;
- return isFlat(call.getOperands(), call.getOperator())
- && all(call.getOperands(), RexUtil::isFlat);
+ return true;
}
private static void flattenRecurse(
List<RexNode> list, List<? extends RexNode> exprs, SqlOperator op) {
- for (RexNode expr : exprs) {
+ // Use an explicit stack to avoid StackOverflowError on deeply nested
+ // associative calls (e.g. CALCITE-5845)
+ final Deque<RexNode> stack = new ArrayDeque<>();
+ // Push in reverse order so that the leftmost operand is processed first
+ for (int i = exprs.size() - 1; i >= 0; i--) {
+ stack.push(exprs.get(i));
+ }
+ while (!stack.isEmpty()) {
+ final RexNode expr = stack.pop();
if (expr instanceof RexCall
&& ((RexCall) expr).getOperator() == op) {
- flattenRecurse(list, ((RexCall) expr).getOperands(), op);
+ final List<RexNode> operands = ((RexCall) expr).getOperands();
+ // Push in reverse order so that the leftmost operand is processed
first
+ for (int i = operands.size() - 1; i >= 0; i--) {
+ stack.push(operands.get(i));
+ }
} else {
list.add(expr);
}
diff --git
a/core/src/main/java/org/apache/calcite/sql2rel/StandardConvertletTable.java
b/core/src/main/java/org/apache/calcite/sql2rel/StandardConvertletTable.java
index bff49f3924..05aa63fdf0 100644
--- a/core/src/main/java/org/apache/calcite/sql2rel/StandardConvertletTable.java
+++ b/core/src/main/java/org/apache/calcite/sql2rel/StandardConvertletTable.java
@@ -93,6 +93,7 @@
import java.math.RoundingMode;
import java.util.ArrayDeque;
import java.util.ArrayList;
+import java.util.Deque;
import java.util.List;
import java.util.Objects;
import java.util.function.Function;
@@ -1204,6 +1205,17 @@ public RexNode convertCall(
SqlCall call) {
final SqlOperator op = call.getOperator();
final RexBuilder rexBuilder = cx.getRexBuilder();
+
+ // For associative operators (AND, OR), flatten the SqlNode tree
iteratively
+ // to avoid StackOverflowError on deeply nested expressions.
+ // The parser creates a left-deep binary tree for chains like
+ // "a AND b AND c AND d ...", and the default convertOperands would recurse
+ // into each nested level, causing stack overflow for large operand counts.
+ final SqlKind kind = op.getKind();
+ if (kind == SqlKind.AND || kind == SqlKind.OR) {
+ return convertAssociativeCall(cx, rexBuilder, call, op, kind);
+ }
+
SqlOperandTypeChecker operandTypeChecker = op.getOperandTypeChecker();
final SqlOperandTypeChecker.Consistency consistency =
operandTypeChecker == null
@@ -1276,6 +1288,69 @@ public RexNode convertCall(
return rexBuilder.makeCall(call.getParserPosition(), type, op,
RexUtil.flatten(exprs, op));
}
+ /**
+ * Converts a call to an associative operator (AND, OR) by iteratively
+ * flattening the nested binary SqlNode tree into a flat list of operands,
+ * then converting each operand. This avoids StackOverflowError on deeply
+ * nested expressions.
+ */
+ private static RexNode convertAssociativeCall(
+ SqlRexContext cx,
+ RexBuilder rexBuilder,
+ SqlCall call,
+ SqlOperator op,
+ SqlKind kind) {
+ // Step 1: Iteratively collect all leaf operands from the nested
+ // binary tree. For example, AND(AND(AND(a, b), c), d) becomes [a, b, c,
d].
+ final List<SqlNode> operands = new ArrayList<>();
+ final Deque<SqlNode> stack = new ArrayDeque<>();
+ stack.push(call);
+ while (!stack.isEmpty()) {
+ final SqlNode node = stack.pop();
+ if (node instanceof SqlCall && node.getKind() == kind) {
+ final SqlCall subCall = (SqlCall) node;
+ // Push right operand first, then left, so that left is processed first
+ final List<SqlNode> subOperands = subCall.getOperandList();
+ for (int i = subOperands.size() - 1; i >= 0; i--) {
+ stack.push(subOperands.get(i));
+ }
+ } else {
+ operands.add(node);
+ }
+ }
+
+ // Step 2: Convert each leaf operand.
+ final List<RexNode> exprs = new ArrayList<>();
+ for (SqlNode operand : operands) {
+ exprs.add(cx.convertExpression(operand));
+ }
+
+ // Step 3: Apply type coercion consistent with the original binary call.
+ // The validator has already checked the original binary call's operand
types.
+ // We replicate the same coercion for all operands.
+ final List<RelDataType> operandTypes =
+ cx.getValidator().getValidatedOperandTypes(call);
+ if (operandTypes != null && !operandTypes.isEmpty()) {
+ // Use the first operand's validated type as the template
+ // (both operands of AND/OR have the same validated type)
+ final RelDataType targetType = operandTypes.get(0);
+ final List<RexNode> coercedExprs = new ArrayList<>();
+ for (RexNode expr : exprs) {
+ coercedExprs.add(
+ rexBuilder.ensureType(call.getParserPosition(), targetType, expr,
true));
+ }
+ exprs.clear();
+ exprs.addAll(coercedExprs);
+ }
+
+ // Step 4: Flatten any nested AND/OR RexNodes that may have resulted from
+ // operand conversion (e.g. IN-to-OR expansion), then derive the return
type
+ // and create a flat n-ary RexCall.
+ final List<RexNode> flatExprs = RexUtil.flatten(exprs, op);
+ final RelDataType type = rexBuilder.deriveReturnType(op, flatExprs);
+ return rexBuilder.makeCall(call.getParserPosition(), type, op, flatExprs);
+ }
+
private static List<Integer> elseArgs(int count) {
// If list is odd, e.g. [0, 1, 2, 3, 4] we get [1, 3, 4]
// If list is even, e.g. [0, 1, 2, 3, 4, 5] we get [2, 4, 5]
diff --git a/core/src/test/java/org/apache/calcite/plan/RelOptUtilTest.java
b/core/src/test/java/org/apache/calcite/plan/RelOptUtilTest.java
index 3bdfbd2625..34c11115c8 100644
--- a/core/src/test/java/org/apache/calcite/plan/RelOptUtilTest.java
+++ b/core/src/test/java/org/apache/calcite/plan/RelOptUtilTest.java
@@ -49,6 +49,7 @@
import org.apache.calcite.sql.type.SqlTypeName;
import org.apache.calcite.sql2rel.RexRewritingRelShuttle;
import org.apache.calcite.test.CalciteAssert;
+import org.apache.calcite.test.SmallStack;
import org.apache.calcite.tools.Frameworks;
import org.apache.calcite.tools.RelBuilder;
import org.apache.calcite.util.Pair;
@@ -1122,6 +1123,87 @@ private void splitJoinConditionHelper(RexNode joinCond,
List<Integer> expLeftKey
assertThat(secondVar.getType(), is(empRow));
}
+ /** Test case for
+ * <a
href="https://issues.apache.org/jira/browse/CALCITE-5845";>[CALCITE-5845]
+ * StackOverflowError when SQL has a very large predicate with many ANDs</a>.
+ *
+ * <p>Verifies that {@link RelOptUtil#conjunctions} computes a deeply nested
+ * binary AND tree on a small-stack thread; the previous recursive
+ * implementation overflows. */
+ @Test void testConjunctionsDeeplyNested() {
+ final RexBuilder rexBuilder = relBuilder.getCluster().getRexBuilder();
+ final RelDataType booleanType =
+ relBuilder.getTypeFactory().createSqlType(SqlTypeName.BOOLEAN);
+ final int depth = 20_000;
+ // Build AND(AND(AND(..., $1), $2), $3, ...) as a left-deep binary tree,
+ // iteratively.
+ RexNode node = rexBuilder.makeInputRef(booleanType, 0);
+ for (int i = 1; i < depth; i++) {
+ node =
+ rexBuilder.makeCall(SqlStdOperatorTable.AND, node,
+ rexBuilder.makeInputRef(booleanType, i));
+ }
+ final RexNode deepTree = node;
+ final List<RexNode> conjunctions =
+ SmallStack.run(() -> RelOptUtil.conjunctions(deepTree));
+ assertThat(conjunctions, hasSize(depth));
+ }
+
+ /** Test case for
+ * <a
href="https://issues.apache.org/jira/browse/CALCITE-5845";>[CALCITE-5845]
+ * StackOverflowError when SQL has a very large predicate with many ANDs</a>.
+ *
+ * <p>Verifies that {@link RelOptUtil#decomposeConjunction(RexNode, List,
List)}
+ * computes a deeply nested binary AND tree on a small-stack thread; the
+ * previous recursive implementation overflows. */
+ @Test void testDecomposeConjunctionNotDeeplyNested() {
+ final RexBuilder rexBuilder = relBuilder.getCluster().getRexBuilder();
+ final RelDataType booleanType =
+ relBuilder.getTypeFactory().createSqlType(SqlTypeName.BOOLEAN);
+ final int depth = 20_000;
+ RexNode node = rexBuilder.makeInputRef(booleanType, 0);
+ for (int i = 1; i < depth; i++) {
+ node =
+ rexBuilder.makeCall(SqlStdOperatorTable.AND, node,
+ rexBuilder.makeInputRef(booleanType, i));
+ }
+ final RexNode deepTree = node;
+ final List<RexNode> rexList = new ArrayList<>();
+ final List<RexNode> notList = new ArrayList<>();
+ SmallStack.run(() -> {
+ RelOptUtil.decomposeConjunction(deepTree, rexList, notList);
+ return null;
+ });
+ assertThat(rexList, hasSize(depth));
+ assertThat(notList, hasSize(0));
+ }
+
+ /** Test case for
+ * <a
href="https://issues.apache.org/jira/browse/CALCITE-5845";>[CALCITE-5845]
+ * StackOverflowError when SQL has a very large predicate with many ANDs</a>.
+ *
+ * <p>Verifies that {@link RelOptUtil#disjunctions} computes a deeply nested
+ * binary OR tree on a small-stack thread; the previous recursive
+ * implementation overflows. */
+ @Test void testDisjunctionsDeeplyNested() {
+ final RexBuilder rexBuilder = relBuilder.getCluster().getRexBuilder();
+ final RelDataType booleanType =
+ relBuilder.getTypeFactory().createSqlType(SqlTypeName.BOOLEAN);
+ final int depth = 20_000;
+ // Build OR(OR(OR(..., $1), $2), $3, ...) as a left-deep binary tree,
+ // iteratively.
+ RexNode node = rexBuilder.makeInputRef(booleanType, 0);
+ for (int i = 1; i < depth; i++) {
+ node =
+ rexBuilder.makeCall(SqlStdOperatorTable.OR, node,
+ rexBuilder.makeInputRef(booleanType, i));
+ }
+ final RexNode deepTree = node;
+ final List<RexNode> disjunctions =
+ SmallStack.run(() -> RelOptUtil.disjunctions(deepTree));
+ assertThat(disjunctions, hasSize(depth));
+ }
+
/** Dummy sub-class of ConverterRule, to check whether generated descriptions
* are OK. */
private static class MyConverterRule extends ConverterRule {
diff --git a/core/src/test/java/org/apache/calcite/rex/RexUtilTest.java
b/core/src/test/java/org/apache/calcite/rex/RexUtilTest.java
index 229886f6d0..f4fefa5043 100644
--- a/core/src/test/java/org/apache/calcite/rex/RexUtilTest.java
+++ b/core/src/test/java/org/apache/calcite/rex/RexUtilTest.java
@@ -17,13 +17,23 @@
package org.apache.calcite.rex;
import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.type.RelDataType;
import org.apache.calcite.sql.SqlKind;
import org.apache.calcite.sql.fun.SqlStdOperatorTable;
+import org.apache.calcite.sql.type.SqlTypeName;
+import org.apache.calcite.test.SmallStack;
import org.apache.calcite.tools.Frameworks;
import org.apache.calcite.tools.RelBuilder;
+import com.google.common.collect.ImmutableList;
+
import org.junit.jupiter.api.Test;
+import java.util.List;
+
+import static org.hamcrest.CoreMatchers.is;
+import static org.hamcrest.MatcherAssert.assertThat;
+import static org.hamcrest.Matchers.hasSize;
import static org.junit.jupiter.api.Assertions.assertNull;
import static org.junit.jupiter.api.Assertions.assertSame;
@@ -43,4 +53,86 @@ class RexUtilTest {
RexUtil.SubQueryFinder.find(expression, SqlKind.SCALAR_QUERY));
assertNull(RexUtil.SubQueryFinder.find(expression, SqlKind.EXISTS));
}
+
+ /** Test case for
+ * <a
href="https://issues.apache.org/jira/browse/CALCITE-5845";>[CALCITE-5845]
+ * StackOverflowError when SQL has a very large predicate with many ANDs</a>.
+ *
+ * <p>Verifies that {@link RexUtil#flattenAnd} computes a deeply nested
+ * binary AND tree on a small-stack thread; the previous recursive
+ * implementation overflows. */
+ @Test void testFlattenAndDeeplyNested() {
+ final RelBuilder builder =
+ RelBuilder.create(Frameworks.newConfigBuilder().build());
+ final RexBuilder rexBuilder = builder.getCluster().getRexBuilder();
+ final RelDataType booleanType =
+ builder.getTypeFactory().createSqlType(SqlTypeName.BOOLEAN);
+ final int depth = 20_000;
+ // Build AND(AND(AND(..., $1), $2), $3, ...) as a left-deep binary tree,
+ // iteratively. Hash codes are pre-warmed bottom-up so that the
+ // de-duplication set inside flattenAnd does not itself recurse deeply.
+ RexNode node = rexBuilder.makeInputRef(booleanType, 0);
+ node.hashCode();
+ for (int i = 1; i < depth; i++) {
+ node =
+ rexBuilder.makeCall(SqlStdOperatorTable.AND, node,
+ rexBuilder.makeInputRef(booleanType, i));
+ node.hashCode();
+ }
+ final RexNode deepTree = node;
+ final List<RexNode> flat =
+ SmallStack.run(() -> RexUtil.flattenAnd(ImmutableList.of(deepTree)));
+ assertThat(flat, hasSize(depth));
+ }
+
+ /** Test case for
+ * <a
href="https://issues.apache.org/jira/browse/CALCITE-5845";>[CALCITE-5845]
+ * StackOverflowError when SQL has a very large predicate with many ANDs</a>.
+ *
+ * <p>Verifies that {@link RexUtil#flatten} computes a deeply nested binary
+ * AND tree on a small-stack thread; the previous recursive implementation
+ * overflows. */
+ @Test void testFlattenDeeplyNested() {
+ final RelBuilder builder =
+ RelBuilder.create(Frameworks.newConfigBuilder().build());
+ final RexBuilder rexBuilder = builder.getCluster().getRexBuilder();
+ final RelDataType booleanType =
+ builder.getTypeFactory().createSqlType(SqlTypeName.BOOLEAN);
+ final int depth = 20_000;
+ RexNode node = rexBuilder.makeInputRef(booleanType, 0);
+ for (int i = 1; i < depth; i++) {
+ node =
+ rexBuilder.makeCall(SqlStdOperatorTable.AND, node,
+ rexBuilder.makeInputRef(booleanType, i));
+ }
+ final RexNode deepTree = node;
+ final List<RexNode> flat =
+ SmallStack.run(
+ () -> RexUtil.flatten(ImmutableList.of(deepTree),
+ SqlStdOperatorTable.AND));
+ assertThat(flat, hasSize(depth));
+ }
+
+ /** Test case for
+ * <a
href="https://issues.apache.org/jira/browse/CALCITE-5845";>[CALCITE-5845]
+ * StackOverflowError when SQL has a very large predicate with many ANDs</a>.
+ *
+ * <p>Verifies that {@link RexUtil#isFlat(RexNode)} computes a deeply nested
+ * tree of a non-associative operator (NOT) on a small-stack thread, where
+ * short-circuiting at the top level is not possible; the previous recursive
+ * implementation overflows. */
+ @Test void testIsFlatDeeplyNested() {
+ final RelBuilder builder =
+ RelBuilder.create(Frameworks.newConfigBuilder().build());
+ final RexBuilder rexBuilder = builder.getCluster().getRexBuilder();
+ final RelDataType booleanType =
+ builder.getTypeFactory().createSqlType(SqlTypeName.BOOLEAN);
+ final int depth = 20_000;
+ RexNode node = rexBuilder.makeInputRef(booleanType, 0);
+ for (int i = 0; i < depth; i++) {
+ node = rexBuilder.makeCall(SqlStdOperatorTable.NOT, node);
+ }
+ final RexNode deepTree = node;
+ assertThat(SmallStack.run(() -> RexUtil.isFlat(deepTree)), is(true));
+ }
}
diff --git a/core/src/test/java/org/apache/calcite/test/SmallStack.java
b/core/src/test/java/org/apache/calcite/test/SmallStack.java
new file mode 100644
index 0000000000..4ae950fdfa
--- /dev/null
+++ b/core/src/test/java/org/apache/calcite/test/SmallStack.java
@@ -0,0 +1,62 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to you under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.calcite.test;
+
+import java.util.concurrent.Callable;
+import java.util.concurrent.atomic.AtomicReference;
+
+/** Executes code on a thread with a small stack.
+ *
+ * <p>Useful for verifying that an implementation is iterative: a recursive
+ * implementation overflows quickly, while an iterative one completes. */
+public class SmallStack {
+ private SmallStack() {
+ }
+
+ /** Runs {@code callable} on a thread with a 256KB stack, waits for it to
+ * finish, and returns its result, rethrowing any exception or error that it
+ * threw. */
+ public static <T> T run(Callable<T> callable) {
+ final AtomicReference<T> result = new AtomicReference<>();
+ final AtomicReference<Throwable> error = new AtomicReference<>();
+ final Thread thread = new Thread(null, () -> {
+ try {
+ result.set(callable.call());
+ } catch (Throwable t) {
+ error.set(t);
+ }
+ }, "small-stack", 256 * 1024);
+ thread.start();
+ try {
+ thread.join();
+ } catch (InterruptedException e) {
+ Thread.currentThread().interrupt();
+ throw new RuntimeException(e);
+ }
+ final Throwable t = error.get();
+ if (t == null) {
+ return result.get();
+ }
+ if (t instanceof RuntimeException) {
+ throw (RuntimeException) t;
+ }
+ if (t instanceof Error) {
+ throw (Error) t;
+ }
+ throw new RuntimeException(t);
+ }
+}
diff --git
a/core/src/test/java/org/apache/calcite/test/SqlToRelConverterTest.java
b/core/src/test/java/org/apache/calcite/test/SqlToRelConverterTest.java
index f93370a6b1..ef093bd92f 100644
--- a/core/src/test/java/org/apache/calcite/test/SqlToRelConverterTest.java
+++ b/core/src/test/java/org/apache/calcite/test/SqlToRelConverterTest.java
@@ -51,6 +51,7 @@
import org.apache.calcite.rex.RexNode;
import org.apache.calcite.rex.RexShuttle;
import org.apache.calcite.sql.SqlExplainLevel;
+import org.apache.calcite.sql.SqlKind;
import org.apache.calcite.sql.fun.SqlLibrary;
import org.apache.calcite.sql.type.SqlTypeName;
import org.apache.calcite.sql.validate.SqlConformance;
@@ -7120,4 +7121,102 @@ void checkUserDefinedOrderByOver(NullCollation
nullCollation) {
+ " LIMIT 2) AS t";
sql(sql).withConformance(SqlConformanceEnum.LENIENT).ok();
}
+
+ /** Test case for
+ * <a
href="https://issues.apache.org/jira/browse/CALCITE-5845";>[CALCITE-5845]
+ * StackOverflowError when SQL has a very large predicate with many ANDs</a>.
+ *
+ * <p>Verifies that converting a SQL with many AND-connected predicates
+ * from SqlNode to RelNode does not cause StackOverflowError. */
+ @Test void testLargeAndPredicate() {
+ final int count = 1000;
+ final StringBuilder sb = new StringBuilder();
+ sb.append("SELECT * FROM emp WHERE 1 = 1");
+ for (int i = 0; i < count; i++) {
+ sb.append(" AND 1 = 1");
+ }
+ final String sql = sb.toString();
+ // Should not throw StackOverflowError
+ final RelNode rel = sql(sql).toRel();
+ assertThat(rel, notNullValue());
+ }
+
+ /** Test case for
+ * <a
href="https://issues.apache.org/jira/browse/CALCITE-5845";>[CALCITE-5845]
+ * StackOverflowError when SQL has a very large predicate with many ORs</a>.
+ *
+ * <p>Verifies that converting a SQL with many OR-connected predicates
+ * from SqlNode to RelNode does not cause StackOverflowError. */
+ @Test void testLargeOrPredicate() {
+ final int count = 1000;
+ final StringBuilder sb = new StringBuilder();
+ sb.append("SELECT * FROM emp WHERE 1 = 0");
+ for (int i = 0; i < count; i++) {
+ sb.append(" OR 1 = 0");
+ }
+ final String sql = sb.toString();
+ // Should not throw StackOverflowError
+ final RelNode rel = sql(sql).toRel();
+ assertThat(rel, notNullValue());
+ }
+
+ /** Verifies that a small AND chain produces a flat RexCall with correct
+ * operand count and structure (CALCITE-5845 correctness check). */
+ @Test void testSmallAndChainPlanStructure() {
+ final String sql = "SELECT * FROM emp"
+ + " WHERE deptno = 10 AND sal > 1000 AND empno > 0 AND ename = 'x'";
+ final RelNode rel = sql(sql).toRel();
+ // The filter condition should be a flat AND with 4 operands
+ assertThat(rel, notNullValue());
+ final LogicalFilter filter = (LogicalFilter) rel.getInput(0);
+ final RexNode condition = filter.getCondition();
+ assertThat(condition, notNullValue());
+ // After flattening, the condition should be a single AND call
+ // with all 4 terms as direct operands (not nested ANDs)
+ assertThat(condition, instanceOf(RexCall.class));
+ final RexCall andCall = (RexCall) condition;
+ assertThat(andCall.getKind(), is(SqlKind.AND));
+ assertThat(andCall.getOperands(), hasSize(4));
+ // Verify none of the operands is itself an AND (i.e., it's flat)
+ for (RexNode operand : andCall.getOperands()) {
+ if (operand instanceof RexCall) {
+ assertThat(((RexCall) operand).getKind(), not(is(SqlKind.AND)));
+ }
+ }
+ }
+
+ /** Verifies that mixed AND/OR with IN expansion produces correct flat
+ * structure (CALCITE-5845 correctness check). */
+ @Test void testMixedAndOrWithIn() {
+ final String sql = "SELECT * FROM emp"
+ + " WHERE deptno IN (10, 20) AND sal > 1000 AND empno < 100";
+ final RelNode rel = sql(sql).toRel();
+ assertThat(rel, notNullValue());
+ // Just verify the plan is generated without error and the filter exists
+ final String plan = RelOptUtil.toString(rel);
+ assertThat(plan, notNullValue());
+ assertThat(plan.contains("Filter"), is(true));
+ }
+
+ /** Verifies that a large AND chain with actual column references
+ * produces a correct plan (CALCITE-5845 stress test). */
+ @Test void testLargeAndPredicateWithColumns() {
+ final int count = 500;
+ final StringBuilder sb = new StringBuilder();
+ sb.append("SELECT * FROM emp WHERE deptno > 0");
+ for (int i = 0; i < count; i++) {
+ // Use unique constants to avoid deduplication by simplifyPredicate
+ sb.append(" AND sal > ").append(i);
+ }
+ final String sql = sb.toString();
+ final RelNode rel = sql(sql).toRel();
+ assertThat(rel, notNullValue());
+ final LogicalFilter filter = (LogicalFilter) rel.getInput(0);
+ final RexNode condition = filter.getCondition();
+ assertThat(condition, instanceOf(RexCall.class));
+ final RexCall andCall = (RexCall) condition;
+ assertThat(andCall.getKind(), is(SqlKind.AND));
+ // Should have 501 operands: 1 deptno > 0 + 500 unique sal > i
+ assertThat(andCall.getOperands(), hasSize(501));
+ }
}
