This is an automated email from the ASF dual-hosted git repository.
asolimando 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 6ff13eaccd [CALCITE-7867] RexSimplify takes cubic time on long IN and
NOT IN lists
6ff13eaccd is described below
commit 6ff13eaccd9c70bd399f0e43ed88884f182a2091
Author: Iurii Gerzhedovich <[email protected]>
AuthorDate: Tue Oct 20 14:57:42 2026 +0300
[CALCITE-7867] RexSimplify takes cubic time on long IN and NOT IN lists
---
.../java/org/apache/calcite/rex/RexSimplify.java | 20 ++++++------
.../org/apache/calcite/rex/RexProgramTest.java | 37 ++++++++++++++++++++++
2 files changed, 48 insertions(+), 9 deletions(-)
diff --git a/core/src/main/java/org/apache/calcite/rex/RexSimplify.java
b/core/src/main/java/org/apache/calcite/rex/RexSimplify.java
index 3bbfa92916..0f5174a219 100644
--- a/core/src/main/java/org/apache/calcite/rex/RexSimplify.java
+++ b/core/src/main/java/org/apache/calcite/rex/RexSimplify.java
@@ -2305,7 +2305,11 @@ private <C extends Comparable<C>> RexNode
simplifyUsingPredicates(RexNode e,
*/
private static <C extends Comparable<C>> RangeSet<C> residue(RexNode ref,
RangeSet<C> r0, List<RexNode> predicates, Class<C> clazz) {
- RangeSet<C> result = r0;
+ // Narrow a single mutable range set in place. Copying the range set for
+ // every predicate is quadratic per call, and cubic over a large OR or AND,
+ // because simplifyOrTerms and simplifyAndTerms pass one predicate per
+ // preceding term.
+ final TreeRangeSet<C> result = TreeRangeSet.create(r0);
for (RexNode predicate : predicates) {
switch (predicate.getKind()) {
case EQUALS:
@@ -2330,23 +2334,21 @@ private static <C extends Comparable<C>> RangeSet<C>
residue(RexNode ref,
final RangeSet<C> notEqualsRangeSet =
ImmutableRangeSet.of(pointRange).complement();
if (result.enclosesAll(notEqualsRangeSet)) {
- result = RangeSets.rangeSetAll();
- continue;
+ return RangeSets.rangeSetAll();
}
- result = RangeSets.minus(result, pointRange);
+ result.remove(pointRange);
break;
default:
final Range<C> r1 = range(comparison.kind, c1);
if (result.encloses(r1)) {
// Given these predicates, term is always satisfied.
// e.g. r0 is "$0 < 10", r1 is "$0 < 5"
- result = RangeSets.rangeSetAll();
- continue;
+ return RangeSets.rangeSetAll();
}
- result = result.subRangeSet(r1);
+ result.removeAll(ImmutableRangeSet.of(r1).complement());
}
if (result.isEmpty()) {
- break; // short-cut
+ return ImmutableRangeSet.of(); // short-cut
}
}
break;
@@ -2354,7 +2356,7 @@ private static <C extends Comparable<C>> RangeSet<C>
residue(RexNode ref,
break;
}
}
- return result;
+ return ImmutableRangeSet.copyOf(result);
}
/** Simplifies OR(x, x) into x, and similar.
diff --git a/core/src/test/java/org/apache/calcite/rex/RexProgramTest.java
b/core/src/test/java/org/apache/calcite/rex/RexProgramTest.java
index 4b5283451c..fe1fd1c241 100644
--- a/core/src/test/java/org/apache/calcite/rex/RexProgramTest.java
+++ b/core/src/test/java/org/apache/calcite/rex/RexProgramTest.java
@@ -1894,6 +1894,43 @@ private void checkExponentialCnf(int n) {
"true");
}
+ /** Test case for
+ * <a
href="https://issues.apache.org/jira/browse/CALCITE-7867";>[CALCITE-7867]
+ * RexSimplify takes cubic time on long IN and NOT IN lists</a>. An IN list
+ * on a NOT NULL operand turns into a large OR of equalities. */
+ @Test void testSimplifyLargeOrOfEqualitiesOnNotNullOperand() {
+ final int n = 2_000;
+ final List<RexNode> terms = new ArrayList<>();
+ for (int i = 0; i < n; i++) {
+ terms.add(eq(vIntNotNull(), literal(i)));
+ }
+ final RexNode simplified = simplify.simplifyPreservingType(or(terms));
+ assertThat(simplified.getKind(), is(SqlKind.SEARCH));
+ final Sarg<?> sarg =
+ ((RexLiteral) ((RexCall) simplified).getOperands().get(1))
+ .getValueAs(Sarg.class);
+ assertThat(sarg.pointCount, is(n));
+ }
+
+ /** Test case for
+ * <a
href="https://issues.apache.org/jira/browse/CALCITE-7867";>[CALCITE-7867]
+ * RexSimplify takes cubic time on long IN and NOT IN lists</a>. A NOT IN
+ * list in a filter turns into a large AND of inequalities, even on a
+ * nullable operand. */
+ @Test void testSimplifyLargeAndOfNotEqualsAsFilter() {
+ final int n = 2_000;
+ final List<RexNode> terms = new ArrayList<>();
+ for (int i = 0; i < n; i++) {
+ terms.add(ne(vInt(), literal(i)));
+ }
+ final RexNode simplified = simplify.simplifyUnknownAsFalse(and(terms));
+ assertThat(simplified.getKind(), is(SqlKind.SEARCH));
+ final Sarg<?> sarg =
+ ((RexLiteral) ((RexCall) simplified).getOperands().get(1))
+ .getValueAs(Sarg.class);
+ assertThat(sarg.isComplementedPoints(), is(true));
+ }
+
/** Unit test for
* <a
href="https://issues.apache.org/jira/browse/CALCITE-7032";>[CALCITE-7032]
* Simplify 'NULL > ALL (ARRAY[1,2,NULL])' to 'NULL'</a>. */
