This is an automated email from the ASF dual-hosted git repository.
mihaibudiu 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 38413ece67 [CALCITE-7783] Speed up deepEquals and deepHashCode for
LogicalUnion, LogicalIntersect and LogicalMinus
38413ece67 is described below
commit 38413ece67fcedcd8c8dc5e6af7bce1efaae1ffc
Author: Michael Braun <[email protected]>
AuthorDate: Wed Sep 16 14:07:28 2026 +0000
[CALCITE-7783] Speed up deepEquals and deepHashCode for LogicalUnion,
LogicalIntersect and LogicalMinus
AbstractRelNode's default deepEquals()/deepHashCode() builds a
RelDigestWriter and a PairList and re-runs explainTerms() on both sides
for every comparison.
LogicalJoin, LogicalFilter and LogicalProject already avoid this: their
abstract core classes expose protected deepEquals0()/deepHashCode0()
helpers that compare fields directly, and the final Logical* subclasses
override deepEquals()/deepHashCode() to call them, per AbstractRelNode's
own javadoc recommendation. LogicalUnion, LogicalIntersect and
LogicalMinus never received the same treatment, despite being equally
eligible: all three are final, and SetOp's explainTerms() output
(inputs, "all") is already their complete identity.
This adds deepEquals0()/deepHashCode0() helpers to SetOp, mirroring
Join's, and overrides deepEquals()/deepHashCode() on LogicalUnion,
LogicalIntersect and LogicalMinus only -- other subclasses
(EnumerableUnion, JdbcUnion, BindableUnion, etc.) are non-final and keep
the safe digest-based default.
deepEquals0() also drops the trailing getRowType() comparison: a SetOp's
row type is derived solely from its inputs' row types, so equal inputs
already imply equal row types, and there is no need to compare them
here.
SetOpDigestBenchmark isolates HepPlanner's digest-based dedup for
UNION/INTERSECT/MINUS trees, separate from rule matching or plan
construction. nodeCount spans 2-10,000 to match realistic plan sizes
(production plans run to tens or a couple hundred nodes, not thousands),
duplicatePercent covers 0/50/100, and branches combine via a balanced
pairwise reduction so duplicates produce SetOp-level deepEquals hits
rather than only leaf-level ones. LargePlanBenchmark also gets an
INTERSECT variant alongside its existing UNION one.
Co-Authored-By: Claude Sonnet 5 <[email protected]>
---
.../java/org/apache/calcite/rel/core/SetOp.java | 40 +++++
.../calcite/rel/logical/LogicalIntersect.java | 10 ++
.../apache/calcite/rel/logical/LogicalMinus.java | 10 ++
.../apache/calcite/rel/logical/LogicalUnion.java | 10 ++
.../calcite/benchmarks/LargePlanBenchmark.java | 18 +-
.../calcite/benchmarks/SetOpDigestBenchmark.java | 181 +++++++++++++++++++++
6 files changed, 266 insertions(+), 3 deletions(-)
diff --git a/core/src/main/java/org/apache/calcite/rel/core/SetOp.java
b/core/src/main/java/org/apache/calcite/rel/core/SetOp.java
index 9af6dd2ca9..3a90404efc 100644
--- a/core/src/main/java/org/apache/calcite/rel/core/SetOp.java
+++ b/core/src/main/java/org/apache/calcite/rel/core/SetOp.java
@@ -32,6 +32,10 @@
import com.google.common.collect.ImmutableList;
+import org.apiguardian.api.API;
+import org.checkerframework.checker.nullness.qual.EnsuresNonNullIf;
+import org.checkerframework.checker.nullness.qual.Nullable;
+
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
@@ -113,6 +117,42 @@ public abstract SetOp copy(
return pw.item("all", all);
}
+ @API(since = "1.43", status = API.Status.INTERNAL)
+ @EnsuresNonNullIf(expression = "#1", result = true)
+ protected boolean deepEquals0(@Nullable Object obj) {
+ if (this == obj) {
+ return true;
+ }
+ if (obj == null || getClass() != obj.getClass()) {
+ return false;
+ }
+ SetOp o = (SetOp) obj;
+ if (all != o.all
+ || !traitSet.equals(o.traitSet)
+ || !hints.equals(o.hints)
+ || inputs.size() != o.inputs.size()) {
+ return false;
+ }
+ for (int i = 0; i < inputs.size(); i++) {
+ if (!inputs.get(i).deepEquals(o.inputs.get(i))) {
+ return false;
+ }
+ }
+ // A SetOp's row type is derived solely from its inputs' row types, so
equal inputs
+ // imply equal row types; there is no need to compare rowType here.
+ return true;
+ }
+
+ @API(since = "1.43", status = API.Status.INTERNAL)
+ protected int deepHashCode0() {
+ int result = 31 + traitSet.hashCode();
+ for (int i = 0; i < inputs.size(); i++) {
+ result = result * 31 + inputs.get(i).deepHashCode();
+ }
+ result = result * 31 + Boolean.hashCode(all);
+ return result * 31 + hints.hashCode();
+ }
+
@Override protected RelDataType deriveRowType() {
return deriveLeastRestrictiveRowType();
}
diff --git
a/core/src/main/java/org/apache/calcite/rel/logical/LogicalIntersect.java
b/core/src/main/java/org/apache/calcite/rel/logical/LogicalIntersect.java
index f31f11292f..927579b619 100644
--- a/core/src/main/java/org/apache/calcite/rel/logical/LogicalIntersect.java
+++ b/core/src/main/java/org/apache/calcite/rel/logical/LogicalIntersect.java
@@ -25,6 +25,8 @@
import org.apache.calcite.rel.core.Intersect;
import org.apache.calcite.rel.hint.RelHint;
+import org.checkerframework.checker.nullness.qual.Nullable;
+
import java.util.Collections;
import java.util.List;
@@ -92,6 +94,14 @@ public static LogicalIntersect create(List<RelNode> inputs,
boolean all) {
return shuttle.visit(this);
}
+ @Override public boolean deepEquals(@Nullable Object obj) {
+ return deepEquals0(obj);
+ }
+
+ @Override public int deepHashCode() {
+ return deepHashCode0();
+ }
+
@Override public RelNode withHints(List<RelHint> hintList) {
return new LogicalIntersect(getCluster(), traitSet, hintList, inputs, all);
}
diff --git
a/core/src/main/java/org/apache/calcite/rel/logical/LogicalMinus.java
b/core/src/main/java/org/apache/calcite/rel/logical/LogicalMinus.java
index 745d2174df..690b2b8c82 100644
--- a/core/src/main/java/org/apache/calcite/rel/logical/LogicalMinus.java
+++ b/core/src/main/java/org/apache/calcite/rel/logical/LogicalMinus.java
@@ -25,6 +25,8 @@
import org.apache.calcite.rel.core.Minus;
import org.apache.calcite.rel.hint.RelHint;
+import org.checkerframework.checker.nullness.qual.Nullable;
+
import java.util.Collections;
import java.util.List;
@@ -88,6 +90,14 @@ public static LogicalMinus create(List<RelNode> inputs,
boolean all) {
return shuttle.visit(this);
}
+ @Override public boolean deepEquals(@Nullable Object obj) {
+ return deepEquals0(obj);
+ }
+
+ @Override public int deepHashCode() {
+ return deepHashCode0();
+ }
+
@Override public RelNode withHints(List<RelHint> hintList) {
return new LogicalMinus(getCluster(), traitSet, hintList, inputs, all);
}
diff --git
a/core/src/main/java/org/apache/calcite/rel/logical/LogicalUnion.java
b/core/src/main/java/org/apache/calcite/rel/logical/LogicalUnion.java
index e8855c6568..7502f48b1c 100644
--- a/core/src/main/java/org/apache/calcite/rel/logical/LogicalUnion.java
+++ b/core/src/main/java/org/apache/calcite/rel/logical/LogicalUnion.java
@@ -25,6 +25,8 @@
import org.apache.calcite.rel.core.Union;
import org.apache.calcite.rel.hint.RelHint;
+import org.checkerframework.checker.nullness.qual.Nullable;
+
import java.util.Collections;
import java.util.List;
@@ -92,6 +94,14 @@ public static LogicalUnion create(List<RelNode> inputs,
boolean all) {
return shuttle.visit(this);
}
+ @Override public boolean deepEquals(@Nullable Object obj) {
+ return deepEquals0(obj);
+ }
+
+ @Override public int deepHashCode() {
+ return deepHashCode0();
+ }
+
@Override public RelNode withHints(List<RelHint> hintList) {
return new LogicalUnion(getCluster(), traitSet, hintList, inputs, all);
}
diff --git
a/ubenchmark/src/jmh/java/org/apache/calcite/benchmarks/LargePlanBenchmark.java
b/ubenchmark/src/jmh/java/org/apache/calcite/benchmarks/LargePlanBenchmark.java
index 91455da172..4393410b68 100644
---
a/ubenchmark/src/jmh/java/org/apache/calcite/benchmarks/LargePlanBenchmark.java
+++
b/ubenchmark/src/jmh/java/org/apache/calcite/benchmarks/LargePlanBenchmark.java
@@ -20,6 +20,7 @@
import org.apache.calcite.plan.hep.HepPlanner;
import org.apache.calcite.plan.hep.HepProgram;
import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.logical.LogicalIntersect;
import org.apache.calcite.rel.logical.LogicalUnion;
import org.apache.calcite.rel.rules.CoreRules;
import org.apache.calcite.rel.type.RelDataType;
@@ -84,6 +85,10 @@ public class LargePlanBenchmark {
@Param({"ARBITRARY"})
String matchOrder;
+ // The set operator used to combine the branches into the plan tree.
+ @Param({"UNION", "INTERSECT"})
+ String setOp;
+
// Enable validation mode to verify rule application counts across different
orders.
boolean enableValidation = false;
@@ -154,14 +159,21 @@ private RelNode makeSelectBranch(int i) {
private RelNode makeUnionTree(int unionNum) {
RelNode union = makeSelectBranch(0);
- for (int i = 1; i < unionNum; i++) {
+ for (int i = 1; i <= unionNum; i++) {
RelNode right = makeSelectBranch(i);
- union = LogicalUnion.create(ImmutableList.of(union, right), true);
+ union = combine(union, right);
}
- union = LogicalUnion.create(ImmutableList.of(union,
makeSelectBranch(unionNum)), true);
return union;
}
+ private RelNode combine(RelNode left, RelNode right) {
+ List<RelNode> inputs = ImmutableList.of(left, right);
+ if ("INTERSECT".equals(setOp)) {
+ return LogicalIntersect.create(inputs, true);
+ }
+ return LogicalUnion.create(inputs, true);
+ }
+
@Benchmark
public void testLargeUnionPlan() {
testLargeUnionPlan(unionNum, matchOrder, false);
diff --git
a/ubenchmark/src/jmh/java/org/apache/calcite/benchmarks/SetOpDigestBenchmark.java
b/ubenchmark/src/jmh/java/org/apache/calcite/benchmarks/SetOpDigestBenchmark.java
new file mode 100644
index 0000000000..1a319ab64f
--- /dev/null
+++
b/ubenchmark/src/jmh/java/org/apache/calcite/benchmarks/SetOpDigestBenchmark.java
@@ -0,0 +1,181 @@
+/*
+ * 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.benchmarks;
+
+import org.apache.calcite.plan.RelOptTable;
+import org.apache.calcite.plan.hep.HepPlanner;
+import org.apache.calcite.plan.hep.HepProgram;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.logical.LogicalIntersect;
+import org.apache.calcite.rel.logical.LogicalMinus;
+import org.apache.calcite.rel.logical.LogicalTableScan;
+import org.apache.calcite.rel.logical.LogicalUnion;
+import org.apache.calcite.rel.type.RelDataType;
+import org.apache.calcite.rel.type.RelDataTypeFactory;
+import org.apache.calcite.schema.SchemaPlus;
+import org.apache.calcite.schema.impl.AbstractTable;
+import org.apache.calcite.sql.type.SqlTypeName;
+import org.apache.calcite.tools.Frameworks;
+import org.apache.calcite.tools.RelBuilder;
+
+import com.google.common.collect.ImmutableList;
+
+import org.openjdk.jmh.annotations.Benchmark;
+import org.openjdk.jmh.annotations.BenchmarkMode;
+import org.openjdk.jmh.annotations.Fork;
+import org.openjdk.jmh.annotations.Level;
+import org.openjdk.jmh.annotations.Measurement;
+import org.openjdk.jmh.annotations.Mode;
+import org.openjdk.jmh.annotations.OutputTimeUnit;
+import org.openjdk.jmh.annotations.Param;
+import org.openjdk.jmh.annotations.Scope;
+import org.openjdk.jmh.annotations.Setup;
+import org.openjdk.jmh.annotations.State;
+import org.openjdk.jmh.annotations.Threads;
+import org.openjdk.jmh.annotations.Warmup;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.concurrent.TimeUnit;
+
+/**
+ * Benchmarks {@code HepPlanner}'s digest-based deduplication for
+ * {@code UNION}/{@code INTERSECT}/{@code MINUS} trees. The rule program is
+ * empty, so no rules run. The benchmark includes {@link HepPlanner}'s own
+ * graph/digest-map bookkeeping on every node insert: a real
+ * {@code deepHashCode} and, on a digest-map hit, a real {@code deepEquals}.
+ */
+@Fork(value = 1, jvmArgsPrepend = {"-Xss200m"})
+@Measurement(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS)
+@Warmup(iterations = 3, time = 1, timeUnit = TimeUnit.SECONDS)
+@BenchmarkMode(Mode.AverageTime)
+@OutputTimeUnit(TimeUnit.MICROSECONDS)
+@State(Scope.Thread)
+@Threads(1)
+public class SetOpDigestBenchmark {
+
+ private static final HepProgram EMPTY_PROGRAM = HepProgram.builder().build();
+
+ @Param({"UNION", "INTERSECT", "MINUS"})
+ String setOp;
+
+ /** Number of {@code SetOp} nodes in the tree. */
+ @Param({"2", "5", "10", "100", "1000", "10000"})
+ int nodeCount;
+
+ /**
+ * 0 = every branch is unique, so every digest lookup misses. 100 = every
+ * branch duplicates one of a handful of templates, so lookups hit and
+ * {@code deepEquals} runs.
+ */
+ @Param({"0", "50", "100"})
+ int duplicatePercent;
+
+ private RelBuilder builder;
+ private List<RelOptTable> templateTables;
+ private RelNode root;
+
+ @Setup(Level.Trial)
+ public void setupCluster() {
+ int templateCount = templateCount();
+ SchemaPlus rootSchema = Frameworks.createRootSchema(true);
+ for (int i = 0; i < templateCount; i++) {
+ rootSchema.add("EMP" + i, new AbstractTable() {
+ @Override public RelDataType getRowType(RelDataTypeFactory
typeFactory) {
+ return typeFactory.builder()
+ .add("EMPNO", SqlTypeName.INTEGER)
+ .build();
+ }
+ });
+ }
+
+ builder =
+ RelBuilder.create(Frameworks.newConfigBuilder()
+ .defaultSchema(rootSchema)
+ .build());
+
+ templateTables = new ArrayList<>(templateCount);
+ for (int i = 0; i < templateCount; i++) {
+ templateTables.add(
+ builder.getRelOptSchema().getTableForMember(ImmutableList.of("EMP" +
i)));
+ }
+ }
+
+ private int templateCount() {
+ int totalBranches = nodeCount + 1;
+ return Math.max(1, totalBranches * (100 - duplicatePercent) / 100);
+ }
+
+ private RelNode makeBranch(int templateIndex) {
+ return LogicalTableScan.create(
+ builder.getCluster(), templateTables.get(templateIndex),
ImmutableList.of());
+ }
+
+ private RelNode combine(RelNode left, RelNode right) {
+ List<RelNode> inputs = ImmutableList.of(left, right);
+ switch (setOp) {
+ case "INTERSECT":
+ return LogicalIntersect.create(inputs, true);
+ case "MINUS":
+ return LogicalMinus.create(inputs, true);
+ default:
+ return LogicalUnion.create(inputs, true);
+ }
+ }
+
+ /** Combines nodes pairwise into a balanced binary tree. */
+ private RelNode balancedReduce(List<RelNode> nodes) {
+ if (nodes.size() == 1) {
+ return nodes.get(0);
+ }
+ List<RelNode> next = new ArrayList<>((nodes.size() + 1) / 2);
+ int i = 0;
+ for (; i + 1 < nodes.size(); i += 2) {
+ next.add(combine(nodes.get(i), nodes.get(i + 1)));
+ }
+ if (i < nodes.size()) {
+ // Odd one out: carried up a level unchanged.
+ next.add(nodes.get(i));
+ }
+ return balancedReduce(next);
+ }
+
+ /** Builds a fresh tree; {@code duplicatePercent} controls the branch
templates used. */
+ private RelNode newTree() {
+ int totalBranches = nodeCount + 1;
+ int templateCount = templateCount();
+ List<RelNode> branches = new ArrayList<>(totalBranches);
+ for (int i = 0; i < totalBranches; i++) {
+ branches.add(makeBranch(i % templateCount));
+ }
+ return balancedReduce(branches);
+ }
+
+ /** Builds a fresh tree so {@link #dedupOnInsert} always sees no cached
digest hash. */
+ @Setup(Level.Invocation)
+ public void prepareInvocation() {
+ root = newTree();
+ }
+
+ @Benchmark
+ public RelNode dedupOnInsert() {
+ HepPlanner planner = new HepPlanner(EMPTY_PROGRAM);
+ planner.setLargePlanMode(true);
+ planner.setRoot(root);
+ return planner.getRoot();
+ }
+}
