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 02cfb90482 [CALCITE-7657] Apply the absorption law to simplify boolean
expressions
02cfb90482 is described below
commit 02cfb904822e32e39447ed13ba0cba9618203b54
Author: Yu Xu <[email protected]>
AuthorDate: Thu Jul 16 10:06:30 2026 +0800
[CALCITE-7657] Apply the absorption law to simplify boolean expressions
---
.../java/org/apache/calcite/rex/RexSimplify.java | 49 +++++++++++++++
.../org/apache/calcite/rex/RexProgramTest.java | 48 +++++++++++++--
.../org/apache/calcite/test/JdbcAdapterTest.java | 5 +-
.../MaterializedViewSubstitutionVisitorTest.java | 2 +-
.../org/apache/calcite/test/RelBuilderTest.java | 70 ++++++++++++++++++++++
core/src/test/resources/sql/sub-query.iq | 12 ++--
6 files changed, 171 insertions(+), 15 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 58979c0f5c..b275c8b6d9 100644
--- a/core/src/main/java/org/apache/calcite/rex/RexSimplify.java
+++ b/core/src/main/java/org/apache/calcite/rex/RexSimplify.java
@@ -93,6 +93,9 @@ public class RexSimplify {
private static final Strong STRONG = new Strong();
+ /** Maximum number of terms for which to apply the absorption law. */
+ private static final int MAX_TERMS_FOR_ABSORPTION = 20;
+
/**
* Creates a RexSimplify.
*
@@ -1843,6 +1846,9 @@ RexNode simplifyAnd2(List<RexNode> terms, List<RexNode>
notTerms) {
SqlStdOperatorTable.IS_NULL, notSatisfiableNullable),
UNKNOWN));
}
}
+ // Absorption law: a AND (a OR b) => a
+ absorb(terms, SqlKind.OR);
+
// Add the NOT disjunctions back in.
for (RexNode notDisjunction : notTerms) {
terms.add(simplify(not(notDisjunction), UNKNOWN));
@@ -2087,6 +2093,9 @@ private <C extends Comparable<C>> RexNode
simplifyAnd2ForUnknownAsFalse(
if (!Collections.disjoint(nullOperands, strongOperands)) {
return rexBuilder.makeLiteral(false);
}
+ // Absorption law: a AND (a OR b) => a
+ absorb(terms, SqlKind.OR);
+
// Remove not necessary IS NOT NULL expressions.
// Example. IS NOT NULL(x) AND x < 5 : x < 5
for (RexNode operand : notNullOperands) {
@@ -2367,9 +2376,49 @@ private RexNode simplifyOrs(List<RexNode> terms,
RexUnknownAs unknownAs) {
break;
}
}
+
+ // Absorption law: a OR (a AND b) => a
+ absorb(terms, SqlKind.AND);
+
return RexUtil.composeDisjunction(rexBuilder, terms);
}
+ /**
+ * Applies the absorption law to a list of terms, removing any composite term
+ * that is absorbed by a sibling term.
+ *
+ * <p>When {@code compositeKind} is {@link SqlKind#OR}, removes any
+ * {@code (a OR b)} term whose disjunctions contain a sibling {@code a}, so
+ * {@code a AND (a OR b) => a}. When it is {@link SqlKind#AND}, removes any
+ * {@code (a AND b)} term whose conjunctions contain a sibling {@code a}, so
+ * {@code a OR (a AND b) => a}.
+ *
+ * <p>The absorbing sibling {@code a} must be deterministic; otherwise its
two
+ * occurrences might evaluate differently and the rewrite would not be
+ * equivalence-preserving.
+ */
+ private static void absorb(List<RexNode> terms, SqlKind compositeKind) {
+ if (terms.size() > MAX_TERMS_FOR_ABSORPTION) {
+ return;
+ }
+ for (int i = 0; i < terms.size(); i++) {
+ final RexNode term = terms.get(i);
+ if (term.getKind() == compositeKind) {
+ final List<RexNode> components = compositeKind == SqlKind.OR
+ ? RelOptUtil.disjunctions(term)
+ : RelOptUtil.conjunctions(term);
+ for (RexNode other : terms) {
+ if (other != term && components.contains(other)
+ && RexUtil.isDeterministic(other)) {
+ terms.remove(i);
+ i--;
+ break;
+ }
+ }
+ }
+ }
+ }
+
private Pair<Comparable, RuntimeException> evaluate(RexNode e, Map<RexNode,
Comparable> map) {
Comparable c = null;
RuntimeException ex = null;
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 bf506ceb12..5f8b8edfb1 100644
--- a/core/src/test/java/org/apache/calcite/rex/RexProgramTest.java
+++ b/core/src/test/java/org/apache/calcite/rex/RexProgramTest.java
@@ -513,6 +513,45 @@ private RexProgramBuilder createProg(int variant) {
"false");
}
+ /** Test case for
+ * <a
href="https://issues.apache.org/jira/browse/CALCITE-7657";>[CALCITE-7657]
+ * Apply the absorption law to simplify boolean expressions</a>. */
+ @Test void testAbsorptionLaw() {
+ // AND absorption: a AND (a OR b) => a
+ checkSimplify(and(vBool(), or(vBool(), vBool(1))), "?0.bool0");
+ checkSimplify(and(or(vBool(), vBool(1)), vBool()), "?0.bool0");
+
+ // OR absorption: a OR (a AND b) => a
+ checkSimplify(or(vBool(), and(vBool(), vBool(1))), "?0.bool0");
+ checkSimplify(or(and(vBool(), vBool(1)), vBool()), "?0.bool0");
+
+ // with not-null booleans
+ checkSimplify(and(vBoolNotNull(), or(vBoolNotNull(), vBoolNotNull(1))),
"?0.notNullBool0");
+ checkSimplify(or(vBoolNotNull(), and(vBoolNotNull(), vBoolNotNull(1))),
"?0.notNullBool0");
+
+ // filter mode (unknownAsFalse)
+ checkSimplifyFilter(and(vBool(), or(vBool(), vBool(1))), "?0.bool0");
+ checkSimplifyFilter(or(vBool(), and(vBool(), vBool(1))), "?0.bool0");
+ }
+
+ @Test void testAbsorptionLawWithNonDeterministic() {
+ // a is a non-deterministic boolean ("NDC()")
+ final SqlOperator ndc = getNoDeterministicOperator();
+ final RexNode a = rexBuilder.makeCall(ndc);
+ final RexNode b = gt(vInt(1), literal(1));
+
+ // a AND (a OR b) must NOT be simplified to a
+ checkSimplifyUnchanged(and(a, or(a, b)));
+ // a OR (a AND b) must NOT be simplified to a
+ checkSimplifyUnchanged(or(a, and(a, b)));
+
+ // Sanity check: when a is deterministic, absorption does apply.
+ final SqlOperator dc = getDeterministicOperator();
+ final RexNode da = rexBuilder.makeCall(dc);
+ checkSimplify(and(da, or(da, b)), "DC()");
+ checkSimplify(or(da, and(da, b)), "DC()");
+ }
+
@Disabled("CALCITE-3457: AssertionError in RexSimplify.validateStrongPolicy")
@Test void reproducerFor3457() {
// Identified with RexProgramFuzzyTest#testFuzzy, seed=4887662474363391810L
@@ -3064,10 +3103,9 @@ trueLiteral, literal(1),
// ==>
// "A IS NOT NULL"
SqlOperator dc = getDeterministicOperator();
- checkSimplify2(
+ checkSimplify(
and(or(isNotNull(rexBuilder.makeCall(dc)), gt(vInt(2), literal(2))),
isNotNull(rexBuilder.makeCall(dc))),
- "AND(OR(IS NOT NULL(DC()), >(?0.int2, 2)), IS NOT NULL(DC()))",
"IS NOT NULL(DC())");
}
@@ -3962,7 +4000,7 @@ private static String getString(Map<RexNode, RexNode>
map) {
// -> "x = x AND y < y" (treating unknown as unknown)
// -> false (treating unknown as false)
checkSimplify3(and(eq(vInt(1), vInt(1)), not(ge(vInt(2), vInt(2)))),
- "AND(OR(null, IS NOT NULL(?0.int1)), null, IS NULL(?0.int2))",
+ "AND(null, IS NULL(?0.int2))",
"false",
"IS NULL(?0.int2)");
@@ -3970,7 +4008,7 @@ private static String getString(Map<RexNode, RexNode>
map) {
// -> "OR(x <> x, y >= y)" (treating unknown as unknown)
// -> "y IS NOT NULL" (treating unknown as false)
checkSimplify3(not(and(eq(vInt(1), vInt(1)), not(ge(vInt(2), vInt(2))))),
- "OR(AND(null, IS NULL(?0.int1)), null, IS NOT NULL(?0.int2))",
+ "OR(null, IS NOT NULL(?0.int2))",
"IS NOT NULL(?0.int2)",
"true");
}
@@ -4028,7 +4066,7 @@ private static String getString(Map<RexNode, RexNode>
map) {
// -> "AND(x <> x, y >= y)" (treating unknown as unknown)
// -> "FALSE" (treating unknown as false)
checkSimplify3(not(or(eq(vInt(1), vInt(1)), not(ge(vInt(2), vInt(2))))),
- "AND(null, IS NULL(?0.int1), OR(null, IS NOT NULL(?0.int2)))",
+ "AND(null, IS NULL(?0.int1))",
"false",
"IS NULL(?0.int1)");
}
diff --git a/core/src/test/java/org/apache/calcite/test/JdbcAdapterTest.java
b/core/src/test/java/org/apache/calcite/test/JdbcAdapterTest.java
index 5ecf63c5ba..fbf502169d 100644
--- a/core/src/test/java/org/apache/calcite/test/JdbcAdapterTest.java
+++ b/core/src/test/java/org/apache/calcite/test/JdbcAdapterTest.java
@@ -322,9 +322,8 @@ class JdbcAdapterTest {
+ " JdbcProject($f2=[OR(IS NOT NULL($7), IS NOT
NULL($1))])\n"
+ " JdbcTableScan(table=[[SCOTT, EMP]])\n"
+ " JdbcToEnumerableConverter\n"
- + " JdbcAggregate(group=[{0, 1}], i=[LITERAL_AGG(true)],
em=[MAX($2)])\n"
- + " JdbcProject(DEPTNO=[$7], ENAME=[CAST($1):VARCHAR(14)],"
- + " $f2=[AND(IS NOT NULL($7), IS NOT NULL($1))])\n"
+ + " JdbcAggregate(group=[{0, 1}], i=[LITERAL_AGG(true)])\n"
+ + " JdbcProject(DEPTNO=[$7],
ENAME=[CAST($1):VARCHAR(14)])\n"
+ " JdbcFilter(condition=[OR(IS NOT NULL($7), IS NOT
NULL($1))])\n"
+ " JdbcTableScan(table=[[SCOTT, EMP]])\n\n");
}
diff --git
a/core/src/test/java/org/apache/calcite/test/MaterializedViewSubstitutionVisitorTest.java
b/core/src/test/java/org/apache/calcite/test/MaterializedViewSubstitutionVisitorTest.java
index a19cd683d2..285c1cf9a3 100644
---
a/core/src/test/java/org/apache/calcite/test/MaterializedViewSubstitutionVisitorTest.java
+++
b/core/src/test/java/org/apache/calcite/test/MaterializedViewSubstitutionVisitorTest.java
@@ -1653,7 +1653,7 @@ protected final MaterializedViewFixture sql(String
materialize,
SqlStdOperatorTable.NOT,
i4))));
f.checkSatisfiable(e8,
- "AND(=($0, 0), $2, $3, OR(NOT($2), NOT($3), NOT($4)), NOT($4))");
+ "AND(=($0, 0), $2, $3, NOT($4))");
}
@Test void testSplitFilter() {
diff --git a/core/src/test/java/org/apache/calcite/test/RelBuilderTest.java
b/core/src/test/java/org/apache/calcite/test/RelBuilderTest.java
index 30aa2ff77f..7ad9a4d733 100644
--- a/core/src/test/java/org/apache/calcite/test/RelBuilderTest.java
+++ b/core/src/test/java/org/apache/calcite/test/RelBuilderTest.java
@@ -752,6 +752,76 @@ private void
checkSimplify(UnaryOperator<RelBuilder.Config> transform,
assertThat(f.apply(createBuilder()), hasTree(expected));
}
+ /** Test case for
+ * <a
href="https://issues.apache.org/jira/browse/CALCITE-7657";>[CALCITE-7657]
+ * Apply the absorption law to simplify boolean expressions</a>. */
+ @Test void testFilterAndAbsorptionLaw() {
+ // Equivalent SQL:
+ // SELECT *
+ // FROM emp
+ // WHERE deptno = 10 AND (deptno = 10 OR sal > 100)
+ // Should be simplified to:
+ // SELECT *
+ // FROM emp
+ // WHERE deptno = 10
+ final Function<RelBuilder, RelNode> f = b ->
+ b.scan("EMP")
+ .filter(
+ b.and(
+ b.equals(b.field("DEPTNO"), b.literal(10)),
+ b.or(
+ b.equals(b.field("DEPTNO"), b.literal(10)),
+ b.greaterThan(b.field("SAL"), b.literal(100)))))
+ .build();
+
+ final String expected = "LogicalFilter(condition=[=($7, 10)])\n"
+ + " LogicalTableScan(table=[[scott, EMP]])\n";
+ assertThat(f.apply(createBuilder()), hasTree(expected));
+ }
+
+ @Test void testFilterOrAbsorptionLaw() {
+ // Equivalent SQL:
+ // SELECT *
+ // FROM emp
+ // WHERE deptno = 10 OR (deptno = 10 AND sal > 100)
+ // Should be simplified to:
+ // SELECT *
+ // FROM emp
+ // WHERE deptno = 10
+ final Function<RelBuilder, RelNode> f = b ->
+ b.scan("EMP")
+ .filter(
+ b.or(
+ b.equals(b.field("DEPTNO"), b.literal(10)),
+ b.and(
+ b.equals(b.field("DEPTNO"), b.literal(10)),
+ b.greaterThan(b.field("SAL"), b.literal(100)))))
+ .build();
+
+ final String expected = "LogicalFilter(condition=[=($7, 10)])\n"
+ + " LogicalTableScan(table=[[scott, EMP]])\n";
+ assertThat(f.apply(createBuilder()), hasTree(expected));
+ }
+
+ @Test void testFilterAbsorptionLawWithNonDeterministic() {
+ final Function<RelBuilder, RelNode> f = b -> {
+ final RexNode rand =
+ b.greaterThan(
+ b.call(SqlStdOperatorTable.RAND), b.literal(0.5));
+ return b.scan("EMP")
+ .filter(
+ b.and(rand,
+ b.or(rand,
+ b.greaterThan(b.field("SAL"), b.literal(100)))))
+ .build();
+ };
+
+ final String expected = "LogicalFilter(condition=[AND(>(RAND(), 0.5E0),"
+ + " OR(>(RAND(), 0.5E0), >($5, 100)))])\n"
+ + " LogicalTableScan(table=[[scott, EMP]])\n";
+ assertThat(f.apply(createBuilder()), hasTree(expected));
+ }
+
@Test void testBadFieldName() {
final RelBuilder builder = RelBuilder.create(config().build());
try {
diff --git a/core/src/test/resources/sql/sub-query.iq
b/core/src/test/resources/sql/sub-query.iq
index c8719eefe0..847cdb98d9 100644
--- a/core/src/test/resources/sql/sub-query.iq
+++ b/core/src/test/resources/sql/sub-query.iq
@@ -4327,7 +4327,7 @@ select * from "scott".emp where (empno, deptno) not in
((1, 2), (3, null));
!ok
!if (use_old_decorr) {
-EnumerableCalc(expr#0..14=[{inputs}], expr#15=[0], expr#16=[=($t8, $t15)],
expr#17=[IS NULL($t7)], expr#18=[IS NOT NULL($t13)], expr#19=[AND($t14, $t18)],
expr#20=[<($t9, $t8)], expr#21=[OR($t17, $t19, $t18, $t20)], expr#22=[IS NOT
TRUE($t21)], expr#23=[OR($t16, $t22)], proj#0..7=[{exprs}], $condition=[$t23])
+EnumerableCalc(expr#0..13=[{inputs}], expr#14=[0], expr#15=[=($t8, $t14)],
expr#16=[IS NULL($t13)], expr#17=[>=($t9, $t8)], expr#18=[IS NOT NULL($t7)],
expr#19=[AND($t16, $t17, $t18)], expr#20=[OR($t15, $t19)], proj#0..7=[{exprs}],
$condition=[$t20])
EnumerableMergeJoin(condition=[AND(=($10, $11), OR(IS NULL($12),
=(CAST($7):INTEGER, $12)))], joinType=[left])
EnumerableSort(sort0=[$10], dir0=[ASC])
EnumerableCalc(expr#0..9=[{inputs}], expr#10=[CAST($t0):INTEGER NOT
NULL], proj#0..10=[{exprs}])
@@ -4336,7 +4336,7 @@ EnumerableCalc(expr#0..14=[{inputs}], expr#15=[0],
expr#16=[=($t8, $t15)], expr#
EnumerableAggregate(group=[{}], c=[COUNT()], ck=[COUNT() FILTER $0])
EnumerableValues(tuples=[[{ true }, { true }]])
EnumerableSort(sort0=[$0], dir0=[ASC])
- EnumerableCalc(expr#0..1=[{inputs}], expr#2=[true], expr#3=[IS NOT
NULL($t1)], proj#0..3=[{exprs}])
+ EnumerableCalc(expr#0..1=[{inputs}], expr#2=[true], proj#0..2=[{exprs}])
EnumerableValues(tuples=[[{ 3, null }, { 1, 2 }]])
!plan
!}
@@ -4351,14 +4351,14 @@ select * from "scott".emp where (mgr, deptno) not in
((1, 2), (3, null), (cast(n
!ok
!if (use_old_decorr) {
-EnumerableCalc(expr#0..13=[{inputs}], expr#14=[0], expr#15=[=($t8, $t14)],
expr#16=[IS NULL($t3)], expr#17=[IS NULL($t7)], expr#18=[IS NOT NULL($t12)],
expr#19=[AND($t13, $t18)], expr#20=[<($t9, $t8)], expr#21=[OR($t16, $t17, $t19,
$t18, $t20)], expr#22=[IS NOT TRUE($t21)], expr#23=[OR($t15, $t22)],
proj#0..7=[{exprs}], $condition=[$t23])
+EnumerableCalc(expr#0..12=[{inputs}], expr#13=[0], expr#14=[=($t8, $t13)],
expr#15=[IS NULL($t12)], expr#16=[>=($t9, $t8)], expr#17=[IS NOT NULL($t3)],
expr#18=[IS NOT NULL($t7)], expr#19=[AND($t15, $t16, $t17, $t18)],
expr#20=[OR($t14, $t19)], proj#0..7=[{exprs}], $condition=[$t20])
EnumerableNestedLoopJoin(condition=[AND(OR(IS NULL($10), =(CAST($3):INTEGER,
$10)), OR(IS NULL($11), =(CAST($7):INTEGER, $11)))], joinType=[left])
EnumerableNestedLoopJoin(condition=[true], joinType=[inner])
EnumerableTableScan(table=[[scott, EMP]])
EnumerableAggregate(group=[{}], c=[COUNT()], ck=[COUNT() FILTER $0])
EnumerableCalc(expr#0..1=[{inputs}], expr#2=[IS NOT NULL($t0)],
expr#3=[IS NOT NULL($t1)], expr#4=[OR($t2, $t3)], $f2=[$t4])
EnumerableValues(tuples=[[{ 3, null }, { null, null }, { 1, 2 }]])
- EnumerableCalc(expr#0..1=[{inputs}], expr#2=[true], expr#3=[IS NOT
NULL($t0)], expr#4=[IS NOT NULL($t1)], expr#5=[AND($t3, $t4)], expr#6=[OR($t3,
$t4)], proj#0..2=[{exprs}], $f20=[$t5], $condition=[$t6])
+ EnumerableCalc(expr#0..1=[{inputs}], expr#2=[true], expr#3=[IS NOT
NULL($t0)], expr#4=[IS NOT NULL($t1)], expr#5=[OR($t3, $t4)],
proj#0..2=[{exprs}], $condition=[$t5])
EnumerableValues(tuples=[[{ 3, null }, { null, null }, { 1, 2 }]])
!plan
!}
@@ -4393,7 +4393,7 @@ select * from "scott".emp where (empno, deptno) not in
((7369, 20), (7499, 30));
!ok
!if (use_old_decorr) {
-EnumerableCalc(expr#0..15=[{inputs}], expr#16=[0], expr#17=[=($t8, $t16)],
expr#18=[IS NULL($t7)], expr#19=[IS NOT NULL($t14)], expr#20=[AND($t15, $t19)],
expr#21=[<($t9, $t8)], expr#22=[OR($t18, $t20, $t19, $t21)], expr#23=[IS NOT
TRUE($t22)], expr#24=[OR($t17, $t23)], proj#0..7=[{exprs}], $condition=[$t24])
+EnumerableCalc(expr#0..14=[{inputs}], expr#15=[0], expr#16=[=($t8, $t15)],
expr#17=[IS NULL($t14)], expr#18=[>=($t9, $t8)], expr#19=[IS NOT NULL($t7)],
expr#20=[AND($t17, $t18, $t19)], expr#21=[OR($t16, $t20)], proj#0..7=[{exprs}],
$condition=[$t21])
EnumerableMergeJoin(condition=[AND(=($10, $12), =($11, $13))],
joinType=[left])
EnumerableSort(sort0=[$10], sort1=[$11], dir0=[ASC], dir1=[ASC])
EnumerableCalc(expr#0..9=[{inputs}], expr#10=[CAST($t0):INTEGER NOT
NULL], expr#11=[CAST($t7):INTEGER], proj#0..11=[{exprs}])
@@ -4403,7 +4403,7 @@ EnumerableCalc(expr#0..15=[{inputs}], expr#16=[0],
expr#17=[=($t8, $t16)], expr#
EnumerableCalc(expr#0..1=[{inputs}], expr#2=[true], $f2=[$t2])
EnumerableValues(tuples=[[{ 7369, 20 }, { 7499, 30 }]])
EnumerableSort(sort0=[$0], sort1=[$1], dir0=[ASC], dir1=[ASC])
- EnumerableCalc(expr#0..1=[{inputs}], expr#2=[true], proj#0..2=[{exprs}],
$f20=[$t2])
+ EnumerableCalc(expr#0..1=[{inputs}], expr#2=[true], proj#0..2=[{exprs}])
EnumerableValues(tuples=[[{ 7369, 20 }, { 7499, 30 }]])
!plan
!}
