This is an automated email from the ASF dual-hosted git repository.
alexpl pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/ignite.git
The following commit(s) were added to refs/heads/master by this push:
new 5d22d1dd53b IGNITE-24624 SQL Calcite: Add heuristics to optimize join
order - Fixes #11935.
5d22d1dd53b is described below
commit 5d22d1dd53bf8b4b2404e78593eccc800a85e8c6
Author: Vladimir Steshin <[email protected]>
AuthorDate: Tue Apr 8 09:37:07 2025 +0300
IGNITE-24624 SQL Calcite: Add heuristics to optimize join order - Fixes
#11935.
Signed-off-by: Aleksey Plekhanov <[email protected]>
---
.../query/calcite/hint/HintDefinition.java | 8 +-
.../query/calcite/prepare/IgnitePlanner.java | 6 +
.../query/calcite/prepare/IgnitePrograms.java | 12 +-
.../query/calcite/prepare/PlannerHelper.java | 236 ++++++++++-
.../query/calcite/prepare/PlannerPhase.java | 22 +
.../rule/logical/IgniteMultiJoinOptimizeRule.java | 446 +++++++++++++++++++++
.../processors/query/calcite/QueryChecker.java | 32 +-
.../query/calcite/RuleApplyListener.java | 76 ++++
.../integration/AbstractBasicIntegrationTest.java | 28 ++
.../query/calcite/planner/AbstractPlannerTest.java | 60 ++-
.../calcite/planner/JoinCommutePlannerTest.java | 132 +++---
.../planner/hints/JoinTypeHintPlannerTest.java | 168 +++++++-
.../calcite/rules/JoinOrderOptimizationTest.java | 234 +++++++++++
.../ignite/testsuites/IntegrationTestSuite.java | 2 +
14 files changed, 1392 insertions(+), 70 deletions(-)
diff --git
a/modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/hint/HintDefinition.java
b/modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/hint/HintDefinition.java
index 949c2990bbf..a32c028482a 100644
---
a/modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/hint/HintDefinition.java
+++
b/modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/hint/HintDefinition.java
@@ -25,6 +25,7 @@ import org.apache.calcite.rel.hint.HintPredicate;
import org.apache.calcite.rel.hint.HintPredicates;
import org.apache.calcite.rel.rules.CoreRules;
import org.apache.calcite.rel.rules.JoinPushThroughJoinRule;
+import
org.apache.ignite.internal.processors.query.calcite.rule.logical.IgniteMultiJoinOptimizeRule;
/**
* Holds supported SQL hints and their settings.
@@ -67,7 +68,12 @@ public enum HintDefinition {
/** {@inheritDoc} */
@Override public Collection<RelOptRule> disabledRules() {
// CoreRules#JOIN_COMMUTE also disables
CoreRules.JOIN_COMMUTE_OUTER.
- return Arrays.asList(CoreRules.JOIN_COMMUTE,
JoinPushThroughJoinRule.LEFT, JoinPushThroughJoinRule.RIGHT);
+ // Disabling JoinToMultiJoinRule also disables
IgniteMultiJoinOptimizeRule because it won't
+ // receive a MultiJoin. Disabling IgniteMultiJoinOptimizeRule in
this way doesn't actually work because
+ // MultiJoin, unfortunately, is not a Hintable and
HintStrategyTable ignores it. We keep it here as slight
+ // optimization, to remove more unnecessary rules from the
planning.
+ return Arrays.asList(CoreRules.JOIN_COMMUTE,
JoinPushThroughJoinRule.LEFT, JoinPushThroughJoinRule.RIGHT,
+ CoreRules.JOIN_TO_MULTI_JOIN,
IgniteMultiJoinOptimizeRule.INSTANCE);
}
},
diff --git
a/modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/prepare/IgnitePlanner.java
b/modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/prepare/IgnitePlanner.java
index a9f80e7464c..376220ae426 100644
---
a/modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/prepare/IgnitePlanner.java
+++
b/modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/prepare/IgnitePlanner.java
@@ -35,6 +35,7 @@ import org.apache.calcite.plan.RelOptCluster;
import org.apache.calcite.plan.RelOptCost;
import org.apache.calcite.plan.RelOptCostFactory;
import org.apache.calcite.plan.RelOptLattice;
+import org.apache.calcite.plan.RelOptListener;
import org.apache.calcite.plan.RelOptMaterialization;
import org.apache.calcite.plan.RelOptPlanner;
import org.apache.calcite.plan.RelOptRule;
@@ -395,6 +396,11 @@ public class IgnitePlanner implements Planner,
RelOptTable.ViewExpander {
for (RelTraitDef<?> def : traitDefs)
this.planner.addRelTraitDef(def);
+
+ RelOptListener planLsnr = ctx.unwrap(RelOptListener.class);
+
+ if (planLsnr != null)
+ planner.addListener(planLsnr);
}
return planner;
diff --git
a/modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/prepare/IgnitePrograms.java
b/modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/prepare/IgnitePrograms.java
index 838fea05657..c4e81e0f08e 100644
---
a/modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/prepare/IgnitePrograms.java
+++
b/modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/prepare/IgnitePrograms.java
@@ -21,9 +21,11 @@ import java.util.ArrayList;
import java.util.List;
import org.apache.calcite.plan.RelOptLattice;
+import org.apache.calcite.plan.RelOptListener;
import org.apache.calcite.plan.RelOptMaterialization;
import org.apache.calcite.plan.RelOptRule;
import org.apache.calcite.plan.hep.HepPlanner;
+import org.apache.calcite.plan.hep.HepProgram;
import org.apache.calcite.plan.hep.HepProgramBuilder;
import org.apache.calcite.tools.Program;
import org.apache.calcite.tools.Programs;
@@ -40,11 +42,14 @@ public class IgnitePrograms {
* @param rules Rules.
* @return New program.
*/
- public static Program hep(RuleSet rules) {
+ public static Program hep(RuleSet rules, HepProgram... subProgram) {
return (planner, rel, traits, materializations, lattices) -> {
final HepProgramBuilder builder = new HepProgramBuilder();
final List<RelOptRule> ruleList = new ArrayList<>();
+ for (HepProgram sub : subProgram)
+ builder.addSubprogram(sub);
+
for (RelOptRule rule : rules)
ruleList.add(rule);
@@ -53,6 +58,11 @@ public class IgnitePrograms {
final HepPlanner hepPlanner = new HepPlanner(builder.build(),
Commons.context(rel), true,
null, Commons.context(rel).config().getCostFactory());
+ RelOptListener relOptListener =
planner.getContext().unwrap(RelOptListener.class);
+
+ if (relOptListener != null)
+ hepPlanner.addListener(relOptListener);
+
hepPlanner.setExecutor(planner.getExecutor());
for (RelOptMaterialization materialization : materializations)
diff --git
a/modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/prepare/PlannerHelper.java
b/modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/prepare/PlannerHelper.java
index 285c2e43d71..2f3cde82aee 100644
---
a/modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/prepare/PlannerHelper.java
+++
b/modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/prepare/PlannerHelper.java
@@ -17,19 +17,25 @@
package org.apache.ignite.internal.processors.query.calcite.prepare;
+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.List;
import java.util.stream.Collectors;
import java.util.stream.Stream;
import com.google.common.collect.ImmutableSet;
+import org.apache.calcite.plan.RelOptRule;
import org.apache.calcite.plan.RelOptUtil;
import org.apache.calcite.plan.RelTraitSet;
import org.apache.calcite.rel.RelCollations;
+import org.apache.calcite.rel.RelHomogeneousShuttle;
import org.apache.calcite.rel.RelNode;
import org.apache.calcite.rel.RelRoot;
+import org.apache.calcite.rel.RelShuttle;
+import org.apache.calcite.rel.core.Join;
import org.apache.calcite.rel.core.SetOp;
import org.apache.calcite.rel.core.Spool;
import org.apache.calcite.rel.core.TableScan;
@@ -38,11 +44,14 @@ import org.apache.calcite.rel.hint.RelHint;
import org.apache.calcite.rel.rules.CoreRules;
import org.apache.calcite.rel.rules.JoinCommuteRule;
import org.apache.calcite.rel.rules.JoinPushThroughJoinRule;
+import org.apache.calcite.rel.rules.JoinToMultiJoinRule;
+import org.apache.calcite.rel.rules.MultiJoin;
import org.apache.calcite.rex.RexBuilder;
import org.apache.calcite.rex.RexNode;
import org.apache.calcite.sql.SqlKind;
import org.apache.calcite.sql.SqlNode;
import org.apache.calcite.util.Pair;
+import org.apache.calcite.util.Util;
import org.apache.ignite.IgniteLogger;
import org.apache.ignite.internal.processors.query.calcite.hint.HintDefinition;
import org.apache.ignite.internal.processors.query.calcite.hint.HintUtils;
@@ -54,6 +63,7 @@ import
org.apache.ignite.internal.processors.query.calcite.rel.IgniteRel;
import
org.apache.ignite.internal.processors.query.calcite.rel.IgniteTableModify;
import org.apache.ignite.internal.processors.query.calcite.rel.IgniteTableScan;
import
org.apache.ignite.internal.processors.query.calcite.rel.IgniteTableSpool;
+import
org.apache.ignite.internal.processors.query.calcite.rule.logical.IgniteMultiJoinOptimizeRule;
import
org.apache.ignite.internal.processors.query.calcite.schema.ColumnDescriptor;
import org.apache.ignite.internal.processors.query.calcite.schema.IgniteTable;
import
org.apache.ignite.internal.processors.query.calcite.trait.IgniteDistributions;
@@ -74,6 +84,15 @@ public class PlannerHelper {
*/
public static final int MAX_JOINS_TO_COMMUTE_INPUTS = 5;
+ /**
+ * Mininal joins number to launch {@link IgniteMultiJoinOptimizeRule}.
Calcite's default join order optimization rules
+ * like {@link JoinCommuteRule} or {@link JoinPushThroughJoinRule} take
time but can give us better plans. They produce
+ * more join variants. And we estimate their physical costs. While the
joins count is small, let's use the default rules.
+ *
+ * @see #optimizeJoinsOrder(IgnitePlanner, RelNode, List)
+ */
+ public static final int JOINS_COUNT_FOR_HEURISTIC_ORDER = 3;
+
/**
* Default constructor.
*/
@@ -112,9 +131,15 @@ public class PlannerHelper {
rel = planner.transform(PlannerPhase.HEP_FILTER_PUSH_DOWN,
rel.getTraitSet(), rel);
+ // The following pushed down project can erase top-level hints. We
store them to reassign hints for join nodes.
+ // Clear the inherit pathes to consider the hints as not
propogated ones.
+ List<RelHint> topHints = HintUtils.allRelHints(rel).stream().map(h
-> h.inheritPath.isEmpty()
+ ? h
+ :
h.copy(Collections.emptyList())).collect(Collectors.toList());
+
rel = planner.transform(PlannerPhase.HEP_PROJECT_PUSH_DOWN,
rel.getTraitSet(), rel);
- fastenJoinsOrder(planner, rel);
+ rel = optimizeJoinsOrder(planner, rel, topHints);
RelTraitSet desired = rel.getCluster().traitSet()
.replace(IgniteConvention.INSTANCE)
@@ -150,8 +175,10 @@ public class PlannerHelper {
/**
* To prevent long join order planning, disables {@link JoinCommuteRule}
and/or {@link JoinPushThroughJoinRule} rules
* if the joins count reaches the thresholds.
+ *
+ * @return Original {@code rel}.
*/
- private static void fastenJoinsOrder(IgnitePlanner planner, RelNode rel) {
+ private static RelNode checkJoinsCommutes(IgnitePlanner planner, RelNode
rel) {
int joinsCnt = RelOptUtil.countJoins(rel);
if (joinsCnt > MAX_JOINS_TO_COMMUTE)
@@ -161,6 +188,179 @@ public class PlannerHelper {
planner.addDisabledRules(Arrays.asList(JoinPushThroughJoinRule.LEFT.toString(),
JoinPushThroughJoinRule.RIGHT.toString()));
}
+
+ return rel;
+ }
+
+ /**
+ * Tries to optimize joins order.
+ *
+ * @see JoinToMultiJoinRule
+ * @see IgniteMultiJoinOptimizeRule
+ *
+ * @return An node with optimized joins or original {@code root} if didn't
optimize.
+ */
+ private static RelNode optimizeJoinsOrder(IgnitePlanner planner, RelNode
root, List<RelHint> topLevelHints) {
+ List<Join> joins = findNodes(root, Join.class, false);
+
+ if (joins.isEmpty())
+ return checkJoinsCommutes(planner, root);
+
+ int disabledCnt = 0;
+
+ // If all the joins have the forced order, no need to optimize the
joins order at all.
+ for (RelNode join : joins) {
+ for (RelHint hint : ((Hintable)join).getHints()) {
+ if
(HintDefinition.ENFORCE_JOIN_ORDER.name().equals(hint.hintName)) {
+ ++disabledCnt;
+
+ break;
+ }
+ }
+ }
+
+ if (joins.size() - disabledCnt < JOINS_COUNT_FOR_HEURISTIC_ORDER)
+ return checkJoinsCommutes(planner, root);
+
+ RelNode res = planner.transform(PlannerPhase.HEP_OPTIMIZE_JOIN_ORDER,
root.getTraitSet(), root);
+
+ // Still has a MultiJoin, didn't manage to collect one flat join to
optimize.
+ if (!findNodes(res, MultiJoin.class, true).isEmpty())
+ return checkJoinsCommutes(planner, root);
+
+ // If a new joins order was proposed, no need to launch another join
order optimizations.
+
planner.addDisabledRules(HintDefinition.ENFORCE_JOIN_ORDER.disabledRules().stream().map(RelOptRule::toString)
+ .collect(Collectors.toSet()));
+
+ if (!topLevelHints.isEmpty()) {
+ res = actualTopLevelJoinTypeHints(res, topLevelHints,
joins.get(0));
+
+ restoreJoinTypeHints(res);
+ }
+
+ return res;
+ }
+
+ /** */
+ private static RelNode actualTopLevelJoinTypeHints(RelNode rel,
List<RelHint> topLevelHints, Join filterNode) {
+ assert rel instanceof Hintable;
+
+ // Ignore inheritance to compare hints type and options.
+ List<RelHint> filteredRelHints = ((Hintable)rel).getHints().stream()
+ .map(h -> h.inheritPath.isEmpty() ? h :
h.copy(Collections.emptyList())).collect(Collectors.toList());
+
+ List<RelHint> res = new ArrayList<>(topLevelHints.size());
+
+ for (RelHint topHint : topLevelHints) {
+ assert topHint.inheritPath.isEmpty();
+
+ boolean storeHint = true;
+
+ for (RelHint curHint : filteredRelHints) {
+ if (topHint.equals(curHint)) {
+ storeHint = false;
+
+ break;
+ }
+ }
+
+ if (storeHint)
+ res.add(topHint);
+ }
+
+ // Keep hints only for joins.
+ res =
Commons.context(filterNode).config().getSqlToRelConverterConfig().getHintStrategyTable().apply(res,
filterNode);
+
+ if (!res.isEmpty())
+ rel = ((Hintable)rel).attachHints(res);
+
+ return rel;
+ }
+
+ /**
+ * A join type hint might be assigned to a query root (top-level hint) or
to a table. Originally, SELECT-level hints
+ * are propagated and assigned to following Joins and TableScans. We lose
assigned to Join nodes ones
+ * in {@link JoinToMultiJoinRule} and have to reassign them from top-level
hints.
+ */
+ private static void restoreJoinTypeHints(RelNode root) {
+ RelShuttle visitor = new RelHomogeneousShuttle() {
+ /** Hints to assign on current tree level. */
+ private final Deque<List<RelHint>> hintsStack = new ArrayDeque<>();
+
+ /** Current hint inheritance path. It is important for hint
priority. */
+ private final List<Integer> inputsStack = new ArrayList<>();
+
+ /** {@inheritDoc} */
+ @Override public RelNode visit(RelNode rel) {
+ // Leaf scans has no inputs. And we are interrested only in
Joins.
+ if (rel.getInputs().isEmpty())
+ return rel;
+
+ List<RelHint> curHints = Collections.emptyList();
+
+ if ((rel instanceof Hintable) && !(rel instanceof Join) &&
!((Hintable)rel).getHints().isEmpty()) {
+ for (RelHint hint : ((Hintable)rel).getHints()) {
+ // Reassign only top-level hints (without the inherit
path).
+ if (!hint.inheritPath.isEmpty())
+ continue;
+
+ if (curHints == Collections.EMPTY_LIST)
+ curHints = new ArrayList<>();
+
+ curHints.add(hint);
+ }
+ }
+
+ // We may find additional top-level hints in a subquery. From
this point, we need to combine them.
+ if (!stack.isEmpty()) {
+ List<RelHint> prevHints = hintsStack.peekLast();
+
+ if (!curHints.isEmpty() && !prevHints.isEmpty())
+ curHints.addAll(prevHints);
+ else if (curHints.isEmpty())
+ curHints = prevHints;
+
+ assert curHints.size() >= hintsStack.peekLast().size();
+ }
+
+ hintsStack.add(curHints);
+
+ RelNode res = super.visit(rel);
+
+ hintsStack.removeLast();
+
+ return res;
+ }
+
+ /** {@inheritDoc} */
+ @Override protected RelNode visitChild(RelNode parent, int i,
RelNode child) {
+ inputsStack.add(i);
+
+ if (child instanceof Join && !hintsStack.isEmpty()) {
+ List<RelHint> curHints = hintsStack.peekLast();
+
+ if (!curHints.isEmpty()) {
+ assert
Commons.context(child).config().getSqlToRelConverterConfig().getHintStrategyTable()
+ .apply(curHints, child).size() == curHints.size()
: "Not all hints are applicable.";
+
+ curHints = curHints.stream().map(h ->
h.copy(inputsStack)).collect(Collectors.toList());
+
+ // Join is a Hintable.
+ child = ((Hintable)child).attachHints(curHints);
+
+ parent.replaceInput(i, child);
+ }
+ }
+
+ RelNode res = super.visitChild(parent, i, child);
+
+ inputsStack.remove(inputsStack.size() - 1);
+
+ return res;
+ }
+ };
+
+ root.accept(visitor);
}
/**
@@ -326,4 +526,36 @@ public class PlannerHelper {
return modifyNode.isInsert();
}
}
+
+ /**
+ * Searches tree {@code root} for nodes of {@code nodeType}.
+ *
+ * @return Nodes matching {@code nodeType}. An empty list if none matches.
A single value list if a node
+ * found and {@code stopOnFirst} is {@code true}.
+ */
+ public static <T extends RelNode> List<T> findNodes(RelNode root, Class<T>
nodeType, boolean stopOnFirst) {
+ List<T> rels = new ArrayList<>();
+
+ try {
+ RelShuttle visitor = new RelHomogeneousShuttle() {
+ @Override public RelNode visit(RelNode node) {
+ if (nodeType.isAssignableFrom(node.getClass())) {
+ rels.add((T)node);
+
+ if (stopOnFirst)
+ throw Util.FoundOne.NULL;
+ }
+
+ return super.visit(node);
+ }
+ };
+
+ root.accept(visitor);
+ }
+ catch (Util.FoundOne ignored) {
+ // No-op.
+ }
+
+ return rels;
+ }
}
diff --git
a/modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/prepare/PlannerPhase.java
b/modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/prepare/PlannerPhase.java
index 7dc61997a0d..a268f92fc6e 100644
---
a/modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/prepare/PlannerPhase.java
+++
b/modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/prepare/PlannerPhase.java
@@ -18,6 +18,9 @@
package org.apache.ignite.internal.processors.query.calcite.prepare;
import org.apache.calcite.plan.RelRule;
+import org.apache.calcite.plan.hep.HepMatchOrder;
+import org.apache.calcite.plan.hep.HepProgram;
+import org.apache.calcite.plan.hep.HepProgramBuilder;
import org.apache.calcite.rel.core.Aggregate;
import org.apache.calcite.rel.logical.LogicalAggregate;
import org.apache.calcite.rel.logical.LogicalFilter;
@@ -64,6 +67,7 @@ import
org.apache.ignite.internal.processors.query.calcite.rule.UnionConverterRu
import
org.apache.ignite.internal.processors.query.calcite.rule.ValuesConverterRule;
import
org.apache.ignite.internal.processors.query.calcite.rule.logical.ExposeIndexRule;
import
org.apache.ignite.internal.processors.query.calcite.rule.logical.FilterScanMergeRule;
+import
org.apache.ignite.internal.processors.query.calcite.rule.logical.IgniteMultiJoinOptimizeRule;
import
org.apache.ignite.internal.processors.query.calcite.rule.logical.LogicalOrToUnionRule;
import
org.apache.ignite.internal.processors.query.calcite.rule.logical.ProjectScanMergeRule;
@@ -140,6 +144,24 @@ public enum PlannerPhase {
}
},
+ /** */
+ HEP_OPTIMIZE_JOIN_ORDER("Heuristic phase to optimize joins order") {
+ /** {@inheritDoc} */
+ @Override public RuleSet getRules(PlanningContext ctx) {
+ return
ctx.rules(RuleSets.ofList(IgniteMultiJoinOptimizeRule.INSTANCE));
+ }
+
+ /** {@inheritDoc} */
+ @Override public Program getProgram(PlanningContext ctx) {
+ HepProgram sub = new HepProgramBuilder()
+ .addMatchOrder(HepMatchOrder.BOTTOM_UP)
+ .addRuleInstance(CoreRules.JOIN_TO_MULTI_JOIN)
+ .build();
+
+ return hep(getRules(ctx), sub);
+ }
+ },
+
/** */
OPTIMIZATION("Main optimization phase") {
/** {@inheritDoc} */
diff --git
a/modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/rule/logical/IgniteMultiJoinOptimizeRule.java
b/modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/rule/logical/IgniteMultiJoinOptimizeRule.java
new file mode 100644
index 00000000000..d3c717c10f2
--- /dev/null
+++
b/modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/rule/logical/IgniteMultiJoinOptimizeRule.java
@@ -0,0 +1,446 @@
+/*
+ * 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.ignite.internal.processors.query.calcite.rule.logical;
+
+import java.util.ArrayList;
+import java.util.BitSet;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.IdentityHashMap;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Set;
+import org.apache.calcite.plan.RelOptRuleCall;
+import org.apache.calcite.plan.RelRule;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.core.JoinRelType;
+import org.apache.calcite.rel.hint.Hintable;
+import org.apache.calcite.rel.metadata.RelMetadataQuery;
+import org.apache.calcite.rel.rules.LoptMultiJoin;
+import org.apache.calcite.rel.rules.MultiJoin;
+import org.apache.calcite.rel.rules.TransformationRule;
+import org.apache.calcite.rex.RexBuilder;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.rex.RexPermuteInputsShuttle;
+import org.apache.calcite.rex.RexUtil;
+import org.apache.calcite.sql.SqlKind;
+import org.apache.calcite.tools.RelBuilder;
+import org.apache.calcite.util.mapping.Mappings;
+import org.apache.calcite.util.mapping.Mappings.TargetMapping;
+import org.apache.ignite.internal.processors.query.calcite.hint.HintDefinition;
+import org.apache.ignite.internal.util.collection.IntMap;
+import org.apache.ignite.internal.util.collection.IntRWHashMap;
+import org.immutables.value.Value;
+import org.jetbrains.annotations.Nullable;
+
+import static org.apache.ignite.internal.util.IgniteUtils.isPow2;
+
+/**
+ * A rule for optimization of flat multi-join using a bushy trees.
+ *
+ * <p>This is an implementation of subset-driven enumeration algorithm (By T.
Neumann. and G. Moerkotte. Analysis of
+ * Two Existing and One New Dynamic Programming Algorithm for the Generation
of Optimal Bushy Join Trees without Cross Products).
+ *
+ * <p>The main loop enumerates all relations and guarantees that for every
emitted set {@code S} any split of this set
+ * will produce subset which have been already processed.
+ *
+ * <p>The inner loop enumerates all possible splits of given subset {@code S}
on disjoint subset
+ * {@code lhs} and {@code rhs} such that {@code lhs ∪ rhs = S} (B. Vance and
D. Maier. Rapid bushy join-order optimization
+ * with cartesian products).
+ *
+ * <p>Finally, if the initial set is not connected, the algorithm crates
cartesian join from the best plan until
+ * all the relations are connected.
+ *
+ * <p>Limitations:
+ * <ol>
+ * <li>Only INNER joins are supported</li>
+ * <li>Disjunctive predicate (condition) is not considered as
connections.</li>
+ * <li>The maximal number of relations is 20. The value is based on time
and memory consumption.</li>
+ * </ol>
+ */
[email protected]
+public class IgniteMultiJoinOptimizeRule extends
RelRule<IgniteMultiJoinOptimizeRule.Config> implements TransformationRule {
+ /** */
+ public static final IgniteMultiJoinOptimizeRule INSTANCE = new
IgniteMultiJoinOptimizeRule(Config.DEFAULT);
+
+ /** */
+ private static final int MAX_JOIN_SIZE = 20;
+
+ /** Vertexes comparator. Better vertex incorporate more relations or costs
less. */
+ private static final Comparator<Vertex> VERTEX_COMPARATOR =
Comparator.<Vertex>comparingInt(v -> v.size).reversed()
+ .thenComparingDouble(v -> v.cost);
+
+ /** Creates the rule. */
+ private IgniteMultiJoinOptimizeRule(Config cfg) {
+ super(cfg);
+ }
+
+ /** {@inheritDoc} */
+ @Override public void onMatch(RelOptRuleCall call) {
+ MultiJoin multiJoinRel = call.rel(0);
+
+ // Currently, only INNER JOIN is supported.
+ if (multiJoinRel.isFullOuterJoin())
+ return;
+
+ int relCnt = multiJoinRel.getInputs().size();
+
+ if (relCnt > MAX_JOIN_SIZE)
+ return;
+
+ for (JoinRelType joinType : multiJoinRel.getJoinTypes()) {
+ if (joinType != JoinRelType.INNER)
+ return;
+ }
+
+ LoptMultiJoin multiJoin = new LoptMultiJoin(multiJoinRel);
+
+ RexBuilder rexBuilder = multiJoinRel.getCluster().getRexBuilder();
+ RelBuilder relBuilder = call.builder();
+ RelMetadataQuery callMeta = call.getMetadataQuery();
+
+ List<RexNode> unusedConditions = new ArrayList<>();
+
+ // Edges by vertex (rel.) number in pow2 starting.
+ IntMap<List<Edge>> edges = collectEdges(multiJoin, unusedConditions);
+ BitSet connections = new BitSet(1 << relCnt);
+ IntMap<Vertex> bestPlan = new IntRWHashMap<>();
+
+ int fldMappingOffset = 0;
+ int relNumPow2 = 1;
+
+ for (RelNode input : multiJoinRel.getInputs()) {
+ TargetMapping fldMapping = Mappings.offsetSource(
+ Mappings.createIdentity(input.getRowType().getFieldCount()),
+ fldMappingOffset,
+ multiJoin.getNumTotalFields()
+ );
+
+ bestPlan.put(relNumPow2, new Vertex(relNumPow2,
callMeta.getRowCount(input), input, fldMapping));
+
+ connections.set(relNumPow2);
+
+ relNumPow2 <<= 1;
+
+ fldMappingOffset += input.getRowType().getFieldCount();
+ }
+
+ Vertex bestPlanSoFar = null;
+
+ for (int s = 0b11, cnt = 1 << relCnt; s < cnt; ++s) {
+ // Pow2-value refers to an initial relation. They are already
processed at the first phase.
+ if (isPow2(s))
+ continue;
+
+ int lhs = Integer.lowestOneBit(s);
+
+ while (lhs < (s / 2) + 1) {
+ int rhs = s - lhs;
+
+ List<Edge> edges0 = connections.get(lhs) &&
connections.get(rhs)
+ ? findEdges(lhs, rhs, edges)
+ : Collections.emptyList();
+
+ if (!edges0.isEmpty()) {
+ connections.set(s);
+
+ Vertex leftPlan = bestPlan.get(lhs);
+ Vertex rightPlan = bestPlan.get(rhs);
+
+ Vertex newPlan = createJoin(leftPlan, rightPlan, edges0,
callMeta, relBuilder, rexBuilder);
+
+ Vertex curBestPlan = bestPlan.get(s);
+
+ if (curBestPlan == null || curBestPlan.cost >
newPlan.cost) {
+ bestPlan.put(s, newPlan);
+
+ bestPlanSoFar = best(bestPlanSoFar, newPlan);
+ }
+
+ aggregateEdges(edges, lhs, rhs);
+ }
+
+ lhs = s & (lhs - s);
+ }
+ }
+
+ int allRelationsMask = (1 << relCnt) - 1;
+
+ Vertex res;
+
+ if (bestPlanSoFar == null || bestPlanSoFar.id != allRelationsMask)
+ res = composeCartesianJoin(allRelationsMask, bestPlan, edges,
bestPlanSoFar, callMeta, relBuilder, rexBuilder);
+ else
+ res = bestPlanSoFar;
+
+ RelNode result = relBuilder
+ .push(res.rel)
+ .filter(RexUtil.composeConjunction(rexBuilder,
unusedConditions).accept(new RexPermuteInputsShuttle(res.mapping, res.rel)))
+ .project(relBuilder.fields(res.mapping))
+ .build();
+
+ call.transformTo(result);
+ }
+
+ /** */
+ private static void aggregateEdges(IntMap<List<Edge>> edges, int lhs, int
rhs) {
+ int id = lhs | rhs;
+
+ if (!edges.containsKey(id)) {
+ Set<Edge> used = Collections.newSetFromMap(new
IdentityHashMap<>());
+
+ List<Edge> union = new ArrayList<>(edges.computeIfAbsent(lhs, k ->
Collections.emptyList()));
+
+ used.addAll(union);
+
+ edges.computeIfAbsent(rhs, k ->
Collections.emptyList()).forEach(edge -> {
+ if (used.add(edge))
+ union.add(edge);
+ });
+
+ if (!union.isEmpty())
+ edges.put(id, union);
+ }
+ }
+
+ /** */
+ private static Vertex composeCartesianJoin(
+ int allRelationsMask,
+ IntMap<Vertex> bestPlan,
+ IntMap<List<Edge>> edges,
+ @Nullable Vertex bestSoFar,
+ RelMetadataQuery mq,
+ RelBuilder relBuilder,
+ RexBuilder rexBuilder
+ ) {
+ List<Vertex> options;
+
+ if (bestSoFar != null) {
+ options = new ArrayList<>();
+
+ for (Vertex option : bestPlan.values()) {
+ if ((option.id & bestSoFar.id) == 0)
+ options.add(option);
+ }
+ }
+ else
+ options = new ArrayList<>(bestPlan.values());
+
+ options.sort(VERTEX_COMPARATOR);
+
+ Iterator<Vertex> it = options.iterator();
+
+ if (bestSoFar == null)
+ bestSoFar = it.next();
+
+ while (it.hasNext() && bestSoFar.id != allRelationsMask) {
+ Vertex input = it.next();
+
+ if ((bestSoFar.id & input.id) != 0)
+ continue;
+
+ List<Edge> edges0 = findEdges(bestSoFar.id, input.id, edges);
+
+ aggregateEdges(edges, bestSoFar.id, input.id);
+
+ bestSoFar = createJoin(bestSoFar, input, edges0, mq, relBuilder,
rexBuilder);
+ }
+
+ assert bestSoFar.id == allRelationsMask;
+
+ return bestSoFar;
+ }
+
+ /** */
+ private static Vertex best(@Nullable Vertex curBest, Vertex candidate) {
+ return curBest == null || VERTEX_COMPARATOR.compare(curBest,
candidate) > 0
+ ? candidate
+ : curBest;
+ }
+
+ /** */
+ private static IntMap<List<Edge>> collectEdges(LoptMultiJoin multiJoin,
List<RexNode> unusedConditions) {
+ IntMap<List<Edge>> edges = new IntRWHashMap();
+
+ for (RexNode joinCondition : multiJoin.getJoinFilters()) {
+ // Involved rel numbers starting from 0.
+ int[] joinRelNums =
multiJoin.getFactorsRefByJoinFilter(joinCondition).toArray();
+
+ // Skip conditions involving a single table. The main loop looks
only for edges connecting two subsets.
+ // A condition referring to a single table never meet this
requirement. Also, for inner join such conditions must
+ // be pushed down already.
+ if (joinRelNums.length < 2) {
+ unusedConditions.add(joinCondition);
+
+ continue;
+ }
+
+ // TODO: support with adoption of IGNITE-24210
+ if (joinCondition.isA(SqlKind.OR)) {
+ unusedConditions.add(joinCondition);
+
+ continue;
+ }
+
+ int connectedInputs = 0;
+
+ for (int i : joinRelNums)
+ connectedInputs |= 1 << i;
+
+ Edge edge = new Edge(connectedInputs, joinCondition);
+
+ for (int i : joinRelNums)
+ edges.computeIfAbsent(1 << i, k -> new
ArrayList<>()).add(edge);
+ }
+
+ return edges;
+ }
+
+ /** */
+ private static Vertex createJoin(
+ Vertex lhs,
+ Vertex rhs,
+ List<Edge> edges,
+ RelMetadataQuery metadataQry,
+ RelBuilder relBuilder,
+ RexBuilder rexBuilder
+ ) {
+ List<RexNode> conditions = new ArrayList<>();
+
+ edges.forEach(e -> conditions.add(e.condition));
+
+ Vertex majorFactor;
+ Vertex minorFactor;
+
+ // Let's put bigger input on left side, because right side will
probably be materialized.
+ if (metadataQry.getRowCount(lhs.rel) >=
metadataQry.getRowCount(rhs.rel)) {
+ majorFactor = lhs;
+ minorFactor = rhs;
+ }
+ else {
+ majorFactor = rhs;
+ minorFactor = lhs;
+ }
+
+ TargetMapping fldMapping = Mappings.merge(
+ majorFactor.mapping,
+ Mappings.offsetTarget(minorFactor.mapping,
majorFactor.rel.getRowType().getFieldCount())
+ );
+
+ RexNode newCondition = RexUtil.composeConjunction(rexBuilder,
conditions)
+ .accept(new RexPermuteInputsShuttle(fldMapping, majorFactor.rel,
minorFactor.rel));
+
+ RelNode join =
relBuilder.push(majorFactor.rel).push(minorFactor.rel).join(JoinRelType.INNER,
newCondition).build();
+
+ assert ((Hintable)join).getHints().stream().noneMatch(h ->
h.hintName.equals(HintDefinition.ENFORCE_JOIN_ORDER.name()))
+ : "Joins with enforced order must not be optimized.";
+
+ double cost = metadataQry.getRowCount(join) + lhs.cost + rhs.cost;
+
+ return new Vertex(lhs.id | rhs.id, cost, join, fldMapping);
+ }
+
+ /**
+ * Finds all edges which connect given subsets.
+ *
+ * <p>Returned edges will satisfy two conditions:<ol>
+ * <li>At least one relation from each side will be covered by
edge.</li>
+ * <li>No any other relations outside of {@code lhs ∪ rhs} will be
covered by edge.</li>
+ * </ol>
+ *
+ * @param lhs Left subtree.
+ * @param rhs Right subtree.
+ * @param edges All the edges.
+ * @return Edges connecting given subtrees.
+ */
+ private static List<Edge> findEdges(int lhs, int rhs, IntMap<List<Edge>>
edges) {
+ List<Edge> result = new ArrayList<>();
+
+ List<Edge> fromLeft = edges.computeIfAbsent(lhs, k ->
Collections.emptyList());
+
+ for (Edge edge : fromLeft) {
+ int requiredInputs = edge.connectedInputs & ~lhs;
+
+ if (requiredInputs == 0 || edge.connectedInputs == requiredInputs)
+ continue;
+
+ requiredInputs &= ~rhs;
+
+ if (requiredInputs == 0)
+ result.add(edge);
+ }
+
+ return result;
+ }
+
+ /** */
+ private static final class Edge {
+ /** Bitmap of all inputs connected by condition. */
+ private final int connectedInputs;
+
+ /** Join condition. */
+ private final RexNode condition;
+
+ /** */
+ private Edge(int connectedInputs, RexNode condition) {
+ this.connectedInputs = connectedInputs;
+
+ this.condition = condition;
+ }
+ }
+
+ /** Root vertex (rel) of a tree. */
+ private static class Vertex {
+ /** Bitmap of inputs joined together with current vertex. */
+ private final int id;
+
+ /** Number of inputs joined together with current vertex. */
+ private final byte size;
+
+ /** Total cost of this tree. */
+ private final double cost;
+
+ /** Join mapping. */
+ private final TargetMapping mapping;
+
+ /** Node of this vertex. */
+ private final RelNode rel;
+
+ /** */
+ private Vertex(int id, double cost, RelNode rel, TargetMapping
mapping) {
+ this.id = id;
+ this.size = (byte)Integer.bitCount(id);
+ this.cost = cost;
+ this.rel = rel;
+ this.mapping = mapping;
+ }
+ }
+
+ /** Rule configuration. */
+ @Value.Immutable
+ public interface Config extends RelRule.Config {
+ /** */
+ Config DEFAULT = ImmutableIgniteMultiJoinOptimizeRule.Config.of()
+ .withOperandSupplier(b -> b.operand(MultiJoin.class).anyInputs());
+
+ /** {@inheritDoc} */
+ @Override default IgniteMultiJoinOptimizeRule toRule() {
+ return INSTANCE;
+ }
+ }
+}
diff --git
a/modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/QueryChecker.java
b/modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/QueryChecker.java
index 76a12cbe10b..86d789c8159 100644
---
a/modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/QueryChecker.java
+++
b/modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/QueryChecker.java
@@ -25,9 +25,11 @@ import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.Objects;
+import java.util.function.Consumer;
import java.util.regex.Pattern;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
+import org.apache.calcite.plan.RelOptListener;
import org.apache.calcite.tools.FrameworkConfig;
import org.apache.ignite.Ignite;
import org.apache.ignite.cache.query.FieldsQueryCursor;
@@ -308,6 +310,12 @@ public abstract class QueryChecker {
/** */
private FrameworkConfig frameworkCfg;
+ /** */
+ private RelOptListener planLsnr;
+
+ /** */
+ private Consumer<List<List<?>>> resultChecker;
+
/** */
public QueryChecker(String qry) {
this(qry, null, SqlTransactionMode.NONE);
@@ -350,6 +358,20 @@ public abstract class QueryChecker {
return this;
}
+ /** */
+ public QueryChecker withPlannerListener(RelOptListener lsnr) {
+ this.planLsnr = lsnr;
+
+ return this;
+ }
+
+ /** */
+ public QueryChecker withResultChecker(Consumer<List<List<?>>>
resultChecker) {
+ this.resultChecker = resultChecker;
+
+ return this;
+ }
+
/** */
public QueryChecker returns(Object... res) {
if (expectedResult == null)
@@ -402,7 +424,9 @@ public abstract class QueryChecker {
? ((TransactionProxyImpl)tx).tx().xidVersion()
: null;
- QueryContext ctx = (frameworkCfg != null || txVer != null) ?
QueryContext.of(frameworkCfg, txVer) : null;
+ QueryContext ctx = (frameworkCfg != null || txVer != null || planLsnr
!= null)
+ ? QueryContext.of(frameworkCfg, txVer, planLsnr)
+ : null;
List<FieldsQueryCursor<List<?>>> explainCursors =
engine.query(ctx, "PUBLIC", "EXPLAIN PLAN FOR " + qry, params);
@@ -421,8 +445,7 @@ public abstract class QueryChecker {
assertEquals(exactPlan, actualPlan);
// Check result.
- List<FieldsQueryCursor<List<?>>> cursors =
- engine.query(ctx, "PUBLIC", qry, params);
+ List<FieldsQueryCursor<List<?>>> cursors = engine.query(ctx, "PUBLIC",
qry, params);
FieldsQueryCursor<List<?>> cur = cursors.get(0);
@@ -454,6 +477,9 @@ public abstract class QueryChecker {
assertEqualsCollections(expectedResult, res);
}
+
+ if (resultChecker != null)
+ resultChecker.accept(res);
}
/** */
diff --git
a/modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/RuleApplyListener.java
b/modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/RuleApplyListener.java
new file mode 100644
index 00000000000..5b33ffb1016
--- /dev/null
+++
b/modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/RuleApplyListener.java
@@ -0,0 +1,76 @@
+/*
+ * 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.ignite.internal.processors.query.calcite;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.HashSet;
+import org.apache.calcite.plan.RelOptListener;
+import org.apache.calcite.plan.RelOptRule;
+import org.apache.calcite.plan.RelOptRuleCall;
+import org.apache.calcite.plan.RuleEventLogger;
+
+/** Watches appliying of a rule. */
+public class RuleApplyListener extends RuleEventLogger {
+ /** */
+ private final RelOptRule rule;
+
+ /** */
+ public final Collection<RelOptListener.RuleAttemptedEvent> tries = new
ArrayList<>();
+
+ /** */
+ private final Collection<RelOptRuleCall> products = new HashSet<>();
+
+ /** */
+ public RuleApplyListener(RelOptRule rule) {
+ this.rule = rule;
+ }
+
+ /** {@inheritDoc} */
+ @Override public void ruleAttempted(RuleAttemptedEvent evt) {
+ assert evt.getRuleCall().getRule() == rule ||
!rule.getClass().isAssignableFrom(evt.getRuleCall().getRule().getClass());
+
+ if (evt.getRuleCall().getRule() == rule && !evt.isBefore())
+ tries.add(evt);
+
+ super.ruleAttempted(evt);
+ }
+
+ /** {@inheritDoc} */
+ @Override public void ruleProductionSucceeded(RuleProductionEvent evt) {
+ assert evt.getRuleCall().getRule() == rule ||
!rule.getClass().isAssignableFrom(evt.getRuleCall().getRule().getClass());
+
+ if (evt.getRuleCall().getRule() == rule && !evt.isBefore())
+ products.add(evt.getRuleCall());
+
+ super.ruleProductionSucceeded(evt);
+ }
+
+ /**
+ * Checks wheter the rule was sucessfully applied. Resets the listener.
+ *
+ * @return {@code True} if rule has worked and realeased a product.
+ */
+ public boolean ruleSucceeded() {
+ boolean res = !tries.isEmpty() && tries.stream().allMatch(e ->
products.contains(e.getRuleCall()));
+
+ tries.clear();
+ products.clear();
+
+ return res;
+ }
+}
diff --git
a/modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/integration/AbstractBasicIntegrationTest.java
b/modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/integration/AbstractBasicIntegrationTest.java
index be3496844ae..bdf1904609d 100644
---
a/modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/integration/AbstractBasicIntegrationTest.java
+++
b/modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/integration/AbstractBasicIntegrationTest.java
@@ -83,6 +83,8 @@ public class AbstractBasicIntegrationTest extends
GridCommonAbstractTest {
/** {@inheritDoc} */
@Override protected void afterTest() throws Exception {
+ super.afterTest();
+
// Wait for pending queries before destroying caches. If some error
occurs during query execution, client code
// can get control earlier than query leave the running queries
registry (need some time for async message
// exchange), but eventually, all queries should be closed.
@@ -245,6 +247,32 @@ public class AbstractBasicIntegrationTest extends
GridCommonAbstractTest {
}
}
+ /** */
+ protected void gatherStatistics() throws Exception {
+ for (List<?> lst : sql("SELECT TABLE_NAME FROM SYS.TABLES")) {
+ assert lst.size() == 1 : "Single table name expected";
+
+ String tbl = lst.get(0).toString().toUpperCase();
+
+ sql("ANALYZE " + tbl);
+
+ waitForCondition(
+ () -> {
+ for (Ignite node : G.allGrids()) {
+ if (node.configuration().isClientMode())
+ continue;
+
+ if (F.isEmpty(sql((IgniteEx)node, "select * from
sys.statistics_local_data where name = ?", tbl)))
+ return false;
+ }
+
+ return true;
+ },
+ getTestTimeout()
+ );
+ }
+ }
+
/** */
public static class DelegatingIgniteIndex implements IgniteIndex {
/** */
diff --git
a/modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/planner/AbstractPlannerTest.java
b/modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/planner/AbstractPlannerTest.java
index a3cb34dd355..a7b569d2ca4 100644
---
a/modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/planner/AbstractPlannerTest.java
+++
b/modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/planner/AbstractPlannerTest.java
@@ -29,6 +29,8 @@ import java.util.function.Predicate;
import java.util.function.Supplier;
import java.util.stream.Collectors;
import com.google.common.collect.ImmutableSet;
+import org.apache.calcite.plan.Contexts;
+import org.apache.calcite.plan.RelOptListener;
import org.apache.calcite.plan.RelOptTable;
import org.apache.calcite.plan.RelOptUtil;
import org.apache.calcite.plan.RelTraitSet;
@@ -222,13 +224,28 @@ public abstract class AbstractPlannerTest extends
GridCommonAbstractTest {
/** */
protected PlanningContext plannerCtx(String sql, IgniteSchema
publicSchema, String... disabledRules) {
- return plannerCtx(sql, Collections.singleton(publicSchema),
disabledRules);
+ return plannerCtx(sql, publicSchema, null, disabledRules);
}
/** */
- protected PlanningContext plannerCtx(String sql, Collection<IgniteSchema>
schemas, String... disabledRules) {
+ protected PlanningContext plannerCtx(
+ String sql,
+ IgniteSchema publicSchema,
+ @Nullable RelOptListener planLsnr,
+ String... disabledRules
+ ) {
+ return plannerCtx(sql, Collections.singleton(publicSchema), planLsnr,
disabledRules);
+ }
+
+ /** */
+ protected PlanningContext plannerCtx(
+ String sql,
+ Collection<IgniteSchema> schemas,
+ @Nullable RelOptListener planLsnr,
+ String... disabledRules
+ ) {
PlanningContext ctx = PlanningContext.builder()
- .parentContext(baseQueryContext(schemas))
+ .parentContext(Contexts.of(baseQueryContext(schemas), planLsnr))
.query(sql)
.build();
@@ -243,12 +260,17 @@ public abstract class AbstractPlannerTest extends
GridCommonAbstractTest {
/** */
protected IgniteRel physicalPlan(String sql, IgniteSchema publicSchema,
String... disabledRules) throws Exception {
- return physicalPlan(plannerCtx(sql, publicSchema, disabledRules));
+ return physicalPlan(sql, publicSchema, null, disabledRules);
}
/** */
- protected IgniteRel physicalPlan(String sql, Collection<IgniteSchema>
schemas, String... disabledRules) throws Exception {
- return physicalPlan(plannerCtx(sql, schemas, disabledRules));
+ protected IgniteRel physicalPlan(
+ String sql,
+ IgniteSchema publicSchema,
+ @Nullable RelOptListener planLsnr,
+ String... disabledRules
+ ) throws Exception {
+ return physicalPlan(plannerCtx(sql, publicSchema, planLsnr,
disabledRules));
}
/** */
@@ -437,7 +459,7 @@ public abstract class AbstractPlannerTest extends
GridCommonAbstractTest {
Predicate<T> predicate,
String... disabledRules
) throws Exception {
- assertPlan(sql, Collections.singleton(schema), predicate,
disabledRules);
+ assertPlan(sql, schema, null, predicate, disabledRules);
}
/** */
@@ -447,7 +469,18 @@ public abstract class AbstractPlannerTest extends
GridCommonAbstractTest {
Predicate<T> predicate,
String... disabledRules
) throws Exception {
- IgniteRel plan = physicalPlan(sql, schemas, disabledRules);
+ assertPlan(sql, schemas, null, predicate, disabledRules);
+ }
+
+ /** */
+ protected <T extends RelNode> void assertPlan(
+ String sql,
+ Collection<IgniteSchema> schemas,
+ @Nullable RelOptListener planLsnr,
+ Predicate<T> predicate,
+ String... disabledRules
+ ) throws Exception {
+ IgniteRel plan = physicalPlan(plannerCtx(sql, schemas, planLsnr,
disabledRules));
checkSplitAndSerialization(plan, schemas);
@@ -459,6 +492,17 @@ public abstract class AbstractPlannerTest extends
GridCommonAbstractTest {
}
}
+ /** */
+ protected <T extends RelNode> void assertPlan(
+ String sql,
+ IgniteSchema schema,
+ @Nullable RelOptListener planLsnr,
+ Predicate<T> predicate,
+ String... disabledRules
+ ) throws Exception {
+ assertPlan(sql, Collections.singletonList(schema), planLsnr,
predicate, disabledRules);
+ }
+
/**
* Predicate builder for "Instance of class" condition.
*/
diff --git
a/modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/planner/JoinCommutePlannerTest.java
b/modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/planner/JoinCommutePlannerTest.java
index b3f22a9a709..997e4ceaea8 100644
---
a/modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/planner/JoinCommutePlannerTest.java
+++
b/modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/planner/JoinCommutePlannerTest.java
@@ -31,21 +31,20 @@ import org.apache.calcite.rel.core.JoinRelType;
import org.apache.calcite.rel.rules.CoreRules;
import org.apache.calcite.rel.rules.JoinCommuteRule;
import org.apache.calcite.rel.rules.JoinPushThroughJoinRule;
-import org.apache.calcite.rel.type.RelDataTypeFactory;
+import org.apache.ignite.internal.processors.query.calcite.RuleApplyListener;
import
org.apache.ignite.internal.processors.query.calcite.prepare.PlannerHelper;
import
org.apache.ignite.internal.processors.query.calcite.prepare.PlanningContext;
import
org.apache.ignite.internal.processors.query.calcite.rel.IgniteNestedLoopJoin;
import org.apache.ignite.internal.processors.query.calcite.rel.IgniteProject;
import org.apache.ignite.internal.processors.query.calcite.rel.IgniteRel;
import org.apache.ignite.internal.processors.query.calcite.rel.IgniteTableScan;
+import
org.apache.ignite.internal.processors.query.calcite.rule.logical.IgniteMultiJoinOptimizeRule;
import org.apache.ignite.internal.processors.query.calcite.schema.IgniteSchema;
import
org.apache.ignite.internal.processors.query.calcite.trait.IgniteDistribution;
import
org.apache.ignite.internal.processors.query.calcite.trait.IgniteDistributions;
-import
org.apache.ignite.internal.processors.query.calcite.type.IgniteTypeFactory;
-import
org.apache.ignite.internal.processors.query.calcite.type.IgniteTypeSystem;
import org.junit.Test;
-/** Tests correctness applying of JOIN_COMMUTE* rules. */
+/** Tests correctness applying of JOIN_COMMUTE* and {@link
IgniteMultiJoinOptimizeRule} rules. */
public class JoinCommutePlannerTest extends AbstractPlannerTest {
/** */
private static IgniteSchema publicSchema;
@@ -54,34 +53,12 @@ public class JoinCommutePlannerTest extends
AbstractPlannerTest {
@Override protected void beforeTestsStarted() throws Exception {
super.beforeTestsStarted();
- publicSchema = new IgniteSchema("PUBLIC");
+ IgniteDistribution distr = IgniteDistributions.affinity(0, "HUGE",
"hash");
- IgniteTypeFactory f = new IgniteTypeFactory(IgniteTypeSystem.INSTANCE);
-
- publicSchema.addTable(
- "HUGE",
- new TestTable(
- new RelDataTypeFactory.Builder(f)
- .add("ID", f.createJavaType(Integer.class))
- .build(), 1_000) {
-
- @Override public IgniteDistribution distribution() {
- return IgniteDistributions.affinity(0, "HUGE", "hash");
- }
- }
- );
-
- publicSchema.addTable(
- "SMALL",
- new TestTable(
- new RelDataTypeFactory.Builder(f)
- .add("ID", f.createJavaType(Integer.class))
- .build(), 10) {
-
- @Override public IgniteDistribution distribution() {
- return IgniteDistributions.affinity(0, "SMALL", "hash");
- }
- }
+ publicSchema = createSchema(
+ createTable("SMALL", 10, distr, "ID", Integer.class),
+ createTable("AVERAGE", 100, distr, "ID", Integer.class),
+ createTable("HUGE", 1_000, distr, "ID", Integer.class)
);
}
@@ -164,29 +141,36 @@ public class JoinCommutePlannerTest extends
AbstractPlannerTest {
String sql = "SELECT " + select.substring(0, select.length() - 2) +
"\nFROM " + joins;
- PlanningContext ctx = plannerCtx(sql, publicSchema);
+ // The join order optimization should not work. It disables the
default join commute rules too.
+ RuleApplyListener orderOptmzLsnr = new
RuleApplyListener(IgniteMultiJoinOptimizeRule.INSTANCE);
- RuleMatchVisualizer lsnr = new RuleMatchVisualizer() {
+ PlanningContext ctx = plannerCtx(sql, publicSchema, orderOptmzLsnr);
+
+ RuleMatchVisualizer commuteLsnr = new RuleMatchVisualizer() {
@Override public void ruleAttempted(RuleAttemptedEvent evt) {
- if (rules.contains(evt.getRuleCall().getRule()))
+ if (rules.contains(evt.getRuleCall().getRule()) &&
!evt.isBefore())
assertTrue(rulesExpected);
super.ruleAttempted(evt);
}
};
- lsnr.attachTo(ctx.cluster().getPlanner());
+ commuteLsnr.attachTo(ctx.cluster().getPlanner());
+ ctx.cluster().getPlanner().addListener(commuteLsnr);
physicalPlan(ctx);
+
+ assertFalse(orderOptmzLsnr.ruleSucceeded());
}
/** */
@Test
public void testOuterCommute() throws Exception {
+ RuleApplyListener planLsnr = new
RuleApplyListener(IgniteMultiJoinOptimizeRule.INSTANCE);
+
String sql = "SELECT COUNT(*) FROM SMALL s RIGHT JOIN HUGE h on h.id =
s.id";
- IgniteRel phys = physicalPlan(sql, publicSchema,
- "MergeJoinConverter", "CorrelatedNestedLoopJoin");
+ IgniteRel phys = physicalPlan(sql, publicSchema, planLsnr,
"MergeJoinConverter", "CorrelatedNestedLoopJoin");
assertNotNull(phys);
@@ -198,7 +182,7 @@ public class JoinCommutePlannerTest extends
AbstractPlannerTest {
assertEquals(JoinRelType.LEFT, join.getJoinType());
- PlanningContext ctx = plannerCtx(sql, publicSchema,
"MergeJoinConverter",
+ PlanningContext ctx = plannerCtx(sql, publicSchema, planLsnr,
"MergeJoinConverter",
"CorrelatedNestedLoopJoin");
RelOptPlanner pl = ctx.cluster().getPlanner();
@@ -209,8 +193,7 @@ public class JoinCommutePlannerTest extends
AbstractPlannerTest {
assertNotNull(phys);
- phys = physicalPlan(sql, publicSchema,
- "MergeJoinConverter", "CorrelatedNestedLoopJoin",
"JoinCommuteRule");
+ phys = physicalPlan(sql, publicSchema, planLsnr, "MergeJoinConverter",
"CorrelatedNestedLoopJoin", "JoinCommuteRule");
join = findFirstNode(phys, byClass(IgniteNestedLoopJoin.class));
@@ -221,8 +204,7 @@ public class JoinCommutePlannerTest extends
AbstractPlannerTest {
// no commute
assertEquals(JoinRelType.RIGHT, join.getJoinType());
- ctx = plannerCtx(sql, publicSchema,
- "MergeJoinConverter", "CorrelatedNestedLoopJoin",
"JoinCommuteRule");
+ ctx = plannerCtx(sql, publicSchema, planLsnr, "MergeJoinConverter",
"CorrelatedNestedLoopJoin", "JoinCommuteRule");
pl = ctx.cluster().getPlanner();
@@ -231,15 +213,66 @@ public class JoinCommutePlannerTest extends
AbstractPlannerTest {
System.out.println("plan: " + RelOptUtil.toString(phys));
assertTrue(costWithCommute.isLt(costWithoutCommute));
+
+ assertFalse(planLsnr.ruleSucceeded());
+ }
+
+ /** Tests that {@link IgniteMultiJoinOptimizeRule} is enabled if joins
number reaches the threshold. */
+ @Test
+ public void testHeuristicReorderingIsEnabledByJoinsCount() throws
Exception {
+ assert PlannerHelper.JOINS_COUNT_FOR_HEURISTIC_ORDER >= 3;
+
+ String sql = "SELECT COUNT(*) FROM SMALL s JOIN HUGE h on h.id = s.id
JOIN AVERAGE a on a.id = h.id";
+
+ RuleApplyListener planLsnr = new
RuleApplyListener(IgniteMultiJoinOptimizeRule.INSTANCE);
+
+ physicalPlan(sql, publicSchema, planLsnr);
+
+ assertFalse(planLsnr.ruleSucceeded());
+
+ // Joins number is enough. But the optimization is disabled by the
hint.
+ sql = "SELECT /*+ ENFORCE_JOIN_ORDER */ s.id, h.id, a.id FROM SMALL s
JOIN HUGE h on h.id = s.id " +
+ "JOIN AVERAGE a on a.id = h.id JOIN SMALL ss on ss.id = a.id";
+
+ physicalPlan(sql, publicSchema, planLsnr);
+
+ assertFalse(planLsnr.ruleSucceeded());
+
+ // Joins number is enough. But the optimization is disabled by the
hint for some joins.
+ sql = "SELECT s.id, j.b, j.c FROM SMALL s JOIN " +
+ "(SELECT /*+ ENFORCE_JOIN_ORDER */ h.id as a, a.id as b, s2.id as
c FROM HUGE h JOIN AVERAGE a on h.id=a.id " +
+ "JOIN SMALL s2 ON a.id=s2.id) j ON s.id=j.a";
+
+ physicalPlan(sql, publicSchema, planLsnr);
+
+ assertFalse(planLsnr.ruleSucceeded());
+
+ // Joins number is enough and nothing is disabled.
+ sql = "SELECT s.id, j.b, j.c FROM SMALL s JOIN " +
+ "(SELECT h.id as a, a.id as b, s2.id as c FROM HUGE h JOIN AVERAGE
a on h.id=a.id " +
+ "JOIN SMALL s2 ON a.id=s2.id) j ON s.id=j.a";
+
+ physicalPlan(sql, publicSchema, planLsnr);
+
+ assertTrue(planLsnr.ruleSucceeded());
+
+ // Joins number is enough and nothing is disabled.
+ sql = "SELECT s.id, h.id, a.id FROM SMALL s JOIN HUGE h on h.id = s.id
JOIN AVERAGE a on a.id = h.id " +
+ "JOIN SMALL ss on ss.id = a.id";
+
+ physicalPlan(sql, publicSchema, planLsnr);
+
+ assertTrue(planLsnr.ruleSucceeded());
}
/** */
@Test
public void testInnerCommute() throws Exception {
+ RuleApplyListener planLsnr = new
RuleApplyListener(IgniteMultiJoinOptimizeRule.INSTANCE);
+
String sql = "SELECT COUNT(*) FROM SMALL s JOIN HUGE h on h.id = s.id";
- IgniteRel phys = physicalPlan(sql, publicSchema,
- "MergeJoinConverter", "CorrelatedNestedLoopJoin");
+ IgniteRel phys = physicalPlan(sql, publicSchema, planLsnr,
"MergeJoinConverter", "CorrelatedNestedLoopJoin");
assertNotNull(phys);
@@ -266,8 +299,7 @@ public class JoinCommutePlannerTest extends
AbstractPlannerTest {
assertEquals(JoinRelType.INNER, join.getJoinType());
- PlanningContext ctx = plannerCtx(sql, publicSchema,
"MergeJoinConverter",
- "CorrelatedNestedLoopJoin");
+ PlanningContext ctx = plannerCtx(sql, publicSchema, planLsnr,
"MergeJoinConverter", "CorrelatedNestedLoopJoin");
RelOptPlanner pl = ctx.cluster().getPlanner();
@@ -277,8 +309,7 @@ public class JoinCommutePlannerTest extends
AbstractPlannerTest {
assertNotNull(phys);
- phys = physicalPlan(sql, publicSchema,
- "MergeJoinConverter", "CorrelatedNestedLoopJoin",
"JoinCommuteRule");
+ phys = physicalPlan(sql, publicSchema, planLsnr, "MergeJoinConverter",
"CorrelatedNestedLoopJoin", "JoinCommuteRule");
join = findFirstNode(phys, byClass(IgniteNestedLoopJoin.class));
proj = findFirstNode(phys, byClass(IgniteProject.class));
@@ -304,8 +335,7 @@ public class JoinCommutePlannerTest extends
AbstractPlannerTest {
// no commute
assertEquals(JoinRelType.INNER, join.getJoinType());
- ctx = plannerCtx(sql, publicSchema,
- "MergeJoinConverter", "CorrelatedNestedLoopJoin",
"JoinCommuteRule");
+ ctx = plannerCtx(sql, publicSchema, planLsnr, "MergeJoinConverter",
"CorrelatedNestedLoopJoin", "JoinCommuteRule");
pl = ctx.cluster().getPlanner();
@@ -314,5 +344,7 @@ public class JoinCommutePlannerTest extends
AbstractPlannerTest {
System.out.println("plan: " + RelOptUtil.toString(phys));
assertTrue(costWithCommute.isLt(costWithoutCommute));
+
+ assertFalse(planLsnr.ruleSucceeded());
}
}
diff --git
a/modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/planner/hints/JoinTypeHintPlannerTest.java
b/modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/planner/hints/JoinTypeHintPlannerTest.java
index b03ba932e72..66af9f8a106 100644
---
a/modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/planner/hints/JoinTypeHintPlannerTest.java
+++
b/modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/planner/hints/JoinTypeHintPlannerTest.java
@@ -19,15 +19,22 @@ package
org.apache.ignite.internal.processors.query.calcite.planner.hints;
import java.util.Arrays;
import java.util.function.Predicate;
+import java.util.stream.Stream;
+import org.apache.calcite.plan.RelOptRule;
import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.rules.CoreRules;
+import org.apache.calcite.rel.rules.JoinPushThroughJoinRule;
import org.apache.ignite.internal.processors.query.QueryUtils;
+import org.apache.ignite.internal.processors.query.calcite.RuleApplyListener;
import org.apache.ignite.internal.processors.query.calcite.hint.HintDefinition;
import
org.apache.ignite.internal.processors.query.calcite.planner.AbstractPlannerTest;
import org.apache.ignite.internal.processors.query.calcite.planner.TestTable;
+import
org.apache.ignite.internal.processors.query.calcite.prepare.PlannerHelper;
import
org.apache.ignite.internal.processors.query.calcite.rel.AbstractIgniteJoin;
import
org.apache.ignite.internal.processors.query.calcite.rel.IgniteCorrelatedNestedLoopJoin;
import org.apache.ignite.internal.processors.query.calcite.rel.IgniteMergeJoin;
import
org.apache.ignite.internal.processors.query.calcite.rel.IgniteNestedLoopJoin;
+import
org.apache.ignite.internal.processors.query.calcite.rule.logical.IgniteMultiJoinOptimizeRule;
import org.apache.ignite.internal.processors.query.calcite.schema.IgniteSchema;
import
org.apache.ignite.internal.processors.query.calcite.trait.IgniteDistributions;
import org.apache.ignite.testframework.LogListener;
@@ -46,9 +53,12 @@ import static
org.apache.ignite.internal.processors.query.calcite.hint.HintDefin
* Planner test for index hints.
*/
public class JoinTypeHintPlannerTest extends AbstractPlannerTest {
- /** */
- private static final String[] CORE_JOIN_REORDER_RULES =
{"JoinCommuteRule", "JoinPushThroughJoinRule:left",
- "JoinPushThroughJoinRule:right"};
+ /** All the join order optimization rules (not only default/core). Should
be renamed in the future. */
+ private static final String[] CORE_JOIN_REORDER_RULES = Stream.of(
+ CoreRules.JOIN_COMMUTE,
+ JoinPushThroughJoinRule.LEFT, JoinPushThroughJoinRule.RIGHT,
+ CoreRules.JOIN_TO_MULTI_JOIN, IgniteMultiJoinOptimizeRule.INSTANCE
+ ).map(RelOptRule::toString).toArray(String[]::new);
/** */
private IgniteSchema schema;
@@ -76,7 +86,7 @@ public class JoinTypeHintPlannerTest extends
AbstractPlannerTest {
}
/**
- * Tests nested loop join is disabled by hint.
+ * Tests correlated nested loop join is disabled by hint.
*/
@Test
public void testDisableCNLJoin() throws Exception {
@@ -378,7 +388,7 @@ public class JoinTypeHintPlannerTest extends
AbstractPlannerTest {
*/
@Test
public void testTableHints() throws Exception {
- String sqlTpl = "SELECT %s A2.A, T3.V3, T1.V2 FROM (SELECT 1 AS A, 2
AS B) A2 JOIN TBL3 %s T3 ON A2.B=A2.B " +
+ String sqlTpl = "SELECT %s A2.A, T3.V3, T1.V2 FROM (SELECT 1 AS A, 2
AS B) A2 JOIN TBL3 %s T3 ON A2.B=T3.V2 " +
"JOIN TBL1 %s T1 on T3.V3=T1.V1 where T1.V2=5";
assertPlan(String.format(sqlTpl, "", "/*+ " + NL_JOIN + " */", "/*+ "
+ MERGE_JOIN + " */"), schema,
@@ -404,6 +414,65 @@ public class JoinTypeHintPlannerTest extends
AbstractPlannerTest {
.and(input(1, isTableScan("TBL3")))), CORE_JOIN_REORDER_RULES);
}
+ /**
+ * Test table join hints with join reordering.
+ */
+ @Test
+ public void testTableHintsWithReordering() throws Exception {
+ assert PlannerHelper.JOINS_COUNT_FOR_HEURISTIC_ORDER >= 3;
+
+ RuleApplyListener planLsnr = new
RuleApplyListener(IgniteMultiJoinOptimizeRule.INSTANCE);
+
+ // TBL3 leads, gets NL. TBL1 follows, gets MERGE. TBL5 is to keep
joins order enough to launch the optimization.
+ assertPlan("SELECT A2.A, T3.V3, T1.V2, T5.V3 FROM (SELECT 1 AS A, 2 AS
B) A2 JOIN TBL3 /*+ NL_JOIN */ T3 ON A2.B=T3.V2 " +
+ "JOIN TBL1 /*+ MERGE_JOIN */ T1 on T3.V1=T1.V1 JOIN TBL5 t5 on
T1.V1=T5.V1 where T1.V3=5 and T5.V1=1", schema, planLsnr,
+ checkJoinTypeAndInputScan(IgniteNestedLoopJoin.class, "TBL3")
+ .and(checkJoinTypeAndInputScan(IgniteMergeJoin.class, "TBL1"))
+ );
+
+ assertTrue(planLsnr.ruleSucceeded());
+
+ // TBL3 leads, gets top-level NL. TBL1 follows, gets MERGE. TBL5 is to
keep joins order enough to launch the optimization.
+ assertPlan("SELECT /*+ NL_JOIN */ A2.A, T3.V3, T1.V2, T5.V3 FROM
(SELECT 1 AS A, 2 AS B) A2 JOIN TBL3 T3 ON A2.B=T3.V2 " +
+ "JOIN TBL1 /*+ MERGE_JOIN */ T1 on T3.V1=T1.V1 JOIN TBL5 t5 on
T1.V1=T5.V1 where T1.V3=5 and T5.V1=1", schema, planLsnr,
+ checkJoinTypeAndInputScan(IgniteNestedLoopJoin.class, "TBL3")
+ .and(checkJoinTypeAndInputScan(IgniteMergeJoin.class, "TBL1"))
+ );
+
+ assertTrue(planLsnr.ruleSucceeded());
+
+ // TBL1 leads, gets NL. TBL3 follows, gets MERGE. TBL5 is to keep
joins order enough to launch the optimization.
+ assertPlan("SELECT A2.A, T1.V3, T3.V2, T5.V3 FROM (SELECT 1 AS A, 2 AS
B) A2 JOIN TBL1 /*+ NL_JOIN */ T1 ON A2.B=T1.V2 " +
+ "JOIN TBL3 /*+ MERGE_JOIN */ T3 on T1.V1=T3.V1 JOIN TBL5 t5 on
T3.V3=T5.V3 where T3.V3=5 and T5.V1=1", schema, planLsnr,
+ checkJoinTypeAndInputScan(IgniteNestedLoopJoin.class, "TBL1")
+ .and(checkJoinTypeAndInputScan(IgniteMergeJoin.class, "TBL3"))
+ );
+
+ assertTrue(planLsnr.ruleSucceeded());
+
+ // TBL1 leads, gets top-level NL. TBL3 follows, gets MERGE. TBL5 is to
keep joins order enough to launch the optimization.
+ assertPlan("SELECT /*+ NL_JOIN */ A2.A, T1.V3, T3.V2, T5.V1 FROM
(SELECT 1 AS A, 2 AS B) A2 JOIN TBL1 T1 ON A2.B=T1.V2 " +
+ "JOIN TBL3 /*+ MERGE_JOIN */ T3 on T1.V1=T3.V1 JOIN TBL5 t5 on
T3.V3=T5.V3 where T3.V3=5 and T5.V1=1", schema, planLsnr,
+ checkJoinTypeAndInputScan(IgniteNestedLoopJoin.class, "TBL1")
+ .and(checkJoinTypeAndInputScan(IgniteMergeJoin.class, "TBL3"))
+ );
+
+ assertTrue(planLsnr.ruleSucceeded());
+ }
+
+ /**
+ * Searches for a table scan named {@code tblName} in any input of join of
type {@code jType} without other joins
+ * in the middle.
+ */
+ private Predicate<RelNode> checkJoinTypeAndInputScan(Class<? extends
AbstractIgniteJoin> jType, String tblName) {
+ return nodeOrAnyChild(isInstanceOf(jType).and(
+ input(0,
nodeOrAnyChild(isInstanceOf(AbstractIgniteJoin.class)).negate())
+ .and(input(0, nodeOrAnyChild(isTableScan(tblName))))
+ .or(input(1,
nodeOrAnyChild(isInstanceOf(AbstractIgniteJoin.class)).negate())
+ .and(input(1, nodeOrAnyChild(isTableScan(tblName)))))
+ ));
+ }
+
/**
* Tests disable-join-hint works for a sub-query.
*/
@@ -468,6 +537,95 @@ public class JoinTypeHintPlannerTest extends
AbstractPlannerTest {
schema, predicateForNestedHintOverrides(true),
CORE_JOIN_REORDER_RULES);
}
+ /** */
+ @Test
+ public void testNestedHintOverridesWithReordering() throws Exception {
+ assert PlannerHelper.JOINS_COUNT_FOR_HEURISTIC_ORDER >= 3;
+
+ RuleApplyListener planLsnr = new
RuleApplyListener(IgniteMultiJoinOptimizeRule.INSTANCE);
+
+ assertPlan("SELECT /*+ " + MERGE_JOIN + " */ t1.v1, t2.v2 FROM TBL1 t1
JOIN TBL2 t2 on t1.v3=t2.v3 " +
+ "where t2.v1 in (SELECT /*+ " + NL_JOIN + "(TBL1) */ t3.v3
from TBL3 t3 JOIN TBL1 t4 on t3.v2=t4.v2)",
+ schema, planLsnr,
nodeOrAnyChild(isInstanceOf(IgniteMergeJoin.class)
+
.and(hasChildThat(isInstanceOf(IgniteNestedLoopJoin.class).and(hasNestedTableScan("TBL1")))))
+ );
+
+ assertTrue(planLsnr.ruleSucceeded());
+
+ assertPlan("SELECT /*+ " + MERGE_JOIN + " */ t1.v1, t2.v2 FROM TBL1 t1
JOIN TBL2 t2 on t1.v3=t2.v3 " +
+ "where t2.v1 in (SELECT /*+ " + NL_JOIN + "(TBL3) */ t3.v3
from TBL3 t3 JOIN TBL1 t4 on t3.v2=t4.v2)",
+ schema, planLsnr,
nodeOrAnyChild(isInstanceOf(IgniteMergeJoin.class)
+
.and(hasChildThat(isInstanceOf(IgniteNestedLoopJoin.class).and(hasNestedTableScan("TBL3")))))
+ );
+
+ assertTrue(planLsnr.ruleSucceeded());
+
+ assertPlan("SELECT /*+ " + MERGE_JOIN + " */ t1.v1, t2.v2 FROM TBL1 t1
JOIN TBL2 t2 on t1.v3=t2.v3 " +
+ "where t2.v1 in (SELECT /*+ " + NL_JOIN + " */ t3.v3 from TBL3
t3 JOIN TBL1 t4 on t3.v2=t4.v2)",
+ schema, planLsnr,
nodeOrAnyChild(isInstanceOf(IgniteMergeJoin.class)
+ .and(hasChildThat(isInstanceOf(IgniteNestedLoopJoin.class)
+ .and(hasNestedTableScan("TBL1"))
+ .and(hasNestedTableScan("TBL3")))))
+ );
+
+ assertTrue(planLsnr.ruleSucceeded());
+
+ assertPlan("SELECT /*+ " + NL_JOIN + " */ t1.v1, t2.v2 FROM TBL1 t1
JOIN TBL2 t2 on t1.v3=t2.v3 " +
+ "where t2.v1 in (SELECT /*+ " + MERGE_JOIN + "(TBL1) */ t3.v3
from TBL3 t3 JOIN TBL1 t4 on t3.v2=t4.v2)",
+ schema, planLsnr,
nodeOrAnyChild(isInstanceOf(IgniteNestedLoopJoin.class)
+ .and(hasChildThat(isInstanceOf(IgniteMergeJoin.class)
+ .and(hasNestedTableScan("TBL1")))))
+ );
+
+ assertTrue(planLsnr.ruleSucceeded());
+
+ assertPlan("SELECT /*+ " + NL_JOIN + " */ t1.v1, t2.v2 FROM TBL1 t1
JOIN TBL2 t2 on t1.v3=t2.v3 " +
+ "where t2.v1 in (SELECT /*+ " + MERGE_JOIN + "(TBL3) */ t3.v3
from TBL3 t3 JOIN TBL1 t4 on t3.v2=t4.v2)",
+ schema, planLsnr,
nodeOrAnyChild(isInstanceOf(IgniteNestedLoopJoin.class)
+
.and(hasChildThat(isInstanceOf(IgniteMergeJoin.class).and(hasNestedTableScan("TBL3")))))
+ );
+
+ assertTrue(planLsnr.ruleSucceeded());
+
+ assertPlan("SELECT /*+ " + NL_JOIN + " */ t1.v1, t2.v2 FROM TBL1 t1
JOIN TBL2 t2 on t1.v3=t2.v3 " +
+ "where t2.v1 in (SELECT /*+ " + MERGE_JOIN + " */ t3.v3 from
TBL3 t3 JOIN TBL1 t4 on t3.v2=t4.v2)",
+ schema, planLsnr,
nodeOrAnyChild(isInstanceOf(IgniteNestedLoopJoin.class)
+
.and(hasChildThat(isInstanceOf(IgniteMergeJoin.class).and(hasNestedTableScan("TBL1"))
+ .and(hasNestedTableScan("TBL3")))))
+ );
+
+ assertTrue(planLsnr.ruleSucceeded());
+
+ // Produces unsupported left join.
+ assertPlan("SELECT /*+ " + NL_JOIN + " */ t1.v1, t2.v2 FROM TBL1 t1
JOIN TBL2 t2 on t1.v3=t2.v3 " +
+ "where t2.v1 not in (SELECT /*+ " + MERGE_JOIN + " */ t3.v3
from TBL3 t3 JOIN TBL1 t4 on t3.v2=t4.v2)",
+ schema, planLsnr,
nodeOrAnyChild(isInstanceOf(IgniteNestedLoopJoin.class)
+
.and(hasChildThat(isInstanceOf(IgniteMergeJoin.class).and(hasNestedTableScan("TBL1"))
+ .and(hasNestedTableScan("TBL3")))))
+ );
+
+ assertFalse(planLsnr.ruleSucceeded());
+
+ // Produces unsupported outer join.
+ assertPlan("SELECT /*+ " + NL_JOIN + " */ t1.v1, t2.v2 FROM TBL1 t1
FULL OUTER JOIN TBL2 t2 on t1.v3=t2.v3 " +
+ "where t2.v1 in (SELECT /*+ " + MERGE_JOIN + " */ t3.v3 from
TBL3 t3 JOIN TBL1 t4 on t3.v2=t4.v2)",
+ schema, planLsnr,
nodeOrAnyChild(isInstanceOf(IgniteNestedLoopJoin.class)
+
.and(hasChildThat(isInstanceOf(IgniteMergeJoin.class).and(hasNestedTableScan("TBL1"))
+ .and(hasNestedTableScan("TBL3")))))
+ );
+
+ assertFalse(planLsnr.ruleSucceeded());
+
+ // Produces unsupported outer join.
+ assertPlan("SELECT /*+ " + MERGE_JOIN + " */ t1.v1, t2.v2 FROM TBL1 t1
JOIN TBL2 t2 on t1.v3=t2.v3 where " +
+ "t2.v1 in (SELECT /*+ " + NL_JOIN + "(TBL3) */ t3.v3 from TBL3
t3 FULL OUTER JOIN TBL1 t4 on t3.v2=t4.v2)",
+ schema, planLsnr,
nodeOrAnyChild(isInstanceOf(IgniteMergeJoin.class)
+
.and(hasChildThat(isInstanceOf(IgniteNestedLoopJoin.class).and(hasNestedTableScan("TBL3")))))
+ );
+
+ assertFalse(planLsnr.ruleSucceeded());
+ }
+
/**
* @return A {@link Predicate} for {@link #testNestedHintOverrides()}
*/
diff --git
a/modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/rules/JoinOrderOptimizationTest.java
b/modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/rules/JoinOrderOptimizationTest.java
new file mode 100644
index 00000000000..c5396eb3767
--- /dev/null
+++
b/modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/rules/JoinOrderOptimizationTest.java
@@ -0,0 +1,234 @@
+/*
+ * 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.ignite.internal.processors.query.calcite.rules;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.List;
+import org.apache.calcite.rel.rules.JoinToMultiJoinRule;
+import org.apache.ignite.internal.processors.query.calcite.QueryChecker;
+import org.apache.ignite.internal.processors.query.calcite.RuleApplyListener;
+import
org.apache.ignite.internal.processors.query.calcite.integration.AbstractBasicIntegrationTest;
+import
org.apache.ignite.internal.processors.query.calcite.rule.logical.IgniteMultiJoinOptimizeRule;
+import org.apache.ignite.internal.util.typedef.F;
+import org.junit.Test;
+import org.junit.runner.RunWith;
+import org.junit.runners.Parameterized;
+
+import static
org.apache.ignite.internal.processors.query.calcite.hint.HintDefinition.ENFORCE_JOIN_ORDER;
+
+/**
+ * Test of joins order heuristic optimization.
+ *
+ * @see JoinToMultiJoinRule
+ * @see IgniteMultiJoinOptimizeRule
+ */
+@RunWith(Parameterized.class)
+public class JoinOrderOptimizationTest extends AbstractBasicIntegrationTest {
+ /** Test query. */
+ @Parameterized.Parameter
+ public String qry;
+
+ /** Test queries. */
+ @Parameterized.Parameters
+ public static Collection<String> runConfig() {
+ return testQueries();
+ }
+
+ /** {@inheritDoc} */
+ @Override protected void beforeTestsStarted() throws Exception {
+ super.beforeTestsStarted();
+
+ initSchema();
+
+ gatherStatistics();
+ }
+
+ /** {@inheritDoc} */
+ @Override protected boolean destroyCachesAfterTest() {
+ return false;
+ }
+
+ /** */
+ private void initSchema() {
+ int warehsSz = 50;
+ int catgSz = 100;
+ int reviewSz = 50000;
+ int prodSz = 100;
+ int discSz = 2000;
+ int shipSz = 15000;
+ int usrSz = 10000;
+ int ordSz = 20000;
+ int ordDetSz = 100000;
+
+ sql("CREATE TABLE Products (ProdId INT PRIMARY KEY, ProdNm
VARCHAR(100), Price DECIMAL(10, 2)) WITH \"VALUE_TYPE='PROD'\"");
+ sql("INSERT INTO Products SELECT x, 'Product_' || x::VARCHAR, 100.0 +
x % 100.0 FROM system_range(1, ?)",
+ prodSz);
+
+ sql("CREATE TABLE ProductCategories (ProdCatgId INT PRIMARY KEY,
ProdId INT, CatgId INT)");
+ sql("INSERT INTO ProductCategories SELECT x, 1 + RAND_INTEGER(?), 1 +
RAND_INTEGER(?) FROM system_range(1, ?)",
+ prodSz - 1, catgSz - 1, prodSz);
+
+ sql("CREATE TABLE Discounts (DiscId INT PRIMARY KEY, ProdId INT,
DiscPercent DECIMAL(5, 2), ValidUntil DATE)");
+ sql("INSERT INTO Discounts SELECT x, 1 + RAND_INTEGER(?), 1 + x % 15,
date '2025-02-10' + (x % 365)::INTERVAL DAYS " +
+ "FROM system_range(1, ?)", prodSz - 1, discSz);
+
+ sql("CREATE TABLE Shipping (ShippId INT PRIMARY KEY, OrdId INT,
ShippDate DATE, ShippAddrs VARCHAR(255))");
+ sql("INSERT INTO Shipping SELECT x, 1 + RAND_INTEGER(?), date
'2020-01-01' + RAND_INTEGER(365)::INTERVAL DAYS, "
+ + " 'Addrs_' || x::VARCHAR FROM system_range(1, ?)", ordSz - 1,
shipSz);
+
+ sql("CREATE TABLE Users (UsrId INT PRIMARY KEY, UsrNm VARCHAR(100),
Email VARCHAR(100)) WITH \"VALUE_TYPE='USR'\"");
+ sql("INSERT INTO Users SELECT x, 'User_' || x::VARCHAR, 'email_' ||
x::VARCHAR || '@nowhere.xyz' FROM system_range(1, ?)",
+ usrSz);
+
+ sql("CREATE TABLE Orders (OrdId INT PRIMARY KEY, UsrId INT, ProdId
INT, OrdDate DATE, TotalAmount DECIMAL(10, 2)) " +
+ "WITH \"VALUE_TYPE='ORD'\"");
+ sql("INSERT INTO Orders SELECT x, 1 + RAND_INTEGER(?), 1 +
RAND_INTEGER(?), date '2025-02-10' + (x % 365)::INTERVAL DAYS, " +
+ "1 + x % 10 FROM system_range(1, ?)", usrSz - 1, prodSz, ordSz);
+
+ sql("CREATE TABLE OrderDetails (OrdDetId INT PRIMARY KEY, OrdId INT,
ProdId INT, Qnty INT) WITH \"VALUE_TYPE='ORD_DET'\"");
+ sql("INSERT INTO OrderDetails SELECT x, 1 + RAND_INTEGER(?), 1 +
RAND_INTEGER(?), 1 + x % 10 FROM system_range(1, ?)",
+ ordSz - 1, prodSz - 1, ordDetSz);
+
+ sql("CREATE TABLE Warehouses (WrhId INT PRIMARY KEY, WrhNm
VARCHAR(100), LocNm VARCHAR(100))");
+ sql("INSERT INTO Warehouses SELECT x, 'Wrh_' || x::VARCHAR,
'Location_' || x::VARCHAR FROM system_range(1, ?)", warehsSz);
+
+ sql("CREATE TABLE Categories (CatgId INT PRIMARY KEY, CatgName
VARCHAR(100))");
+ sql("INSERT INTO Categories SELECT x, 'Category_' || x::VARCHAR FROM
system_range(1, ?)", catgSz);
+
+ sql("CREATE TABLE Reviews (RevId INT PRIMARY KEY, ProdId INT, usrId
INT, RevTxt VARCHAR, Rating INT)");
+ sql("INSERT INTO Reviews SELECT x, 1 + RAND_INTEGER(?), 1 +
RAND_INTEGER(?), 'Prod. review ' || x::VARCHAR, 1 + RAND_INTEGER(4) " +
+ "FROM system_range(1, ?)", prodSz - 1, usrSz - 1, reviewSz);
+ }
+
+ /** Tests that query result doesn't change with the joins order
optimization. */
+ @Test
+ public void testTheSameResults() {
+ assert !qry.contains(ENFORCE_JOIN_ORDER.name());
+ assert qry.startsWith("SELECT ");
+
+ String qryFixedJoins = qry.replaceAll("SELECT", "SELECT /*+ " +
ENFORCE_JOIN_ORDER + " */");
+
+ RuleApplyListener planLsnr = new
RuleApplyListener(IgniteMultiJoinOptimizeRule.INSTANCE);
+
+ // First, call with fixed join order.
+ List<List<?>> expectedResult = new ArrayList<>();
+
+
assertQuery(qryFixedJoins).withPlannerListener(planLsnr).withResultChecker(expectedResult::addAll).check();
+
+ // Ensure that the optimization rule wasn't fired.
+ assertFalse(planLsnr.ruleSucceeded());
+
+ assertFalse(expectedResult.isEmpty());
+
+ QueryChecker checker = assertQuery(qry).withPlannerListener(planLsnr);
+
+ // Make sure that the optimized query has the same results.
+ expectedResult.forEach(row -> checker.returns(row.toArray()));
+
+ checker.check();
+
+ // Ensure that the optimization rule has worked.
+ assertTrue(planLsnr.ruleSucceeded());
+ }
+
+ /** */
+ private static Collection<String> testQueries() {
+ return F.asList(
+ // User orders with products in multiple categories.
+ "SELECT \n"
+ + " U.UsrNm, O.OrdId, COUNT(DISTINCT C.CatgName) AS
Categories\n"
+ + " FROM Users U, Orders O, OrderDetails OD, Products P,
ProductCategories PC, Categories C\n"
+ + " WHERE U.UsrId = O.UsrId\n"
+ + " AND O.OrdId = OD.OrdId\n"
+ + " AND OD.ProdId = P.ProdId\n"
+ + " AND P.ProdId = PC.ProdId\n"
+ + " AND PC.CatgId = C.CatgId\n"
+ + " GROUP BY U.UsrNm, O.OrdId",
+
+ // Orders with total revenue and shipping details.
+ "SELECT \n"
+ + " O.OrdId, O.OrdDate, S.ShippAddrs, SUM(OD.Qnty *
P.Price) AS TotalOrderValue\n"
+ + " FROM Orders O, Shipping S, OrderDetails OD, Products P\n"
+ + "WHERE O.OrdId = S.OrdId\n"
+ + " AND O.OrdId = OD.OrdId\n"
+ + " AND OD.ProdId = P.ProdId\n"
+ + "GROUP BY O.OrdId, O.OrdDate, S.ShippAddrs",
+
+ // Products in warehouses by category.
+ "SELECT \n"
+ + " W.WrhNm, C.CatgName, P.ProdNm\n"
+ + " FROM Warehouses W, Products P, ProductCategories PC,
Categories C\n"
+ + "WHERE W.WrhId = (P.ProdId % 5 + 1)\n"
+ + " AND P.ProdId = PC.ProdId\n"
+ + " AND PC.CatgId = C.CatgId",
+
+ // Average product rating by category.
+ "SELECT \n"
+ + " C.CatgName, P.ProdNm, AVG(R.Rating) AS AvgRating\n"
+ + " FROM Categories C, ProductCategories PC, Products P,
Reviews R\n"
+ + "WHERE C.CatgId = PC.CatgId\n"
+ + " AND PC.ProdId = P.ProdId\n"
+ + " AND P.ProdId = R.ProdId\n"
+ + "GROUP BY C.CatgName, P.ProdNm",
+
+ // Products ordered by user.
+ "SELECT \n"
+ + " U.UsrNm, P.ProdNm, SUM(OD.Qnty) AS TotalQnty\n"
+ + " FROM Users U, Orders O, OrderDetails OD, Products P\n"
+ + "WHERE U.UsrId = O.UsrId\n"
+ + " AND O.OrdId = OD.OrdId\n"
+ + " AND OD.ProdId = P.ProdId\n"
+ + "GROUP BY U.UsrNm, P.ProdNm",
+
+ // Joining of all the tables.
+ "SELECT \n"
+ + " U.UsrId, U.UsrNm, O.OrdId, O.OrdDate, P.ProdNm,
OD.Qnty, \n"
+ + " C.CatgName, S.ShippAddrs, R.Rating, D.DiscPercent,
W.WrhNm\n"
+ + " FROM Users U, Orders O, OrderDetails OD, Products P,
ProductCategories PC, Categories C, \n"
+ + " Shipping S, Reviews R, Discounts D, Warehouses W\n"
+ + "WHERE U.UsrId = O.UsrId\n"
+ + " AND O.OrdId = OD.OrdId\n"
+ + " AND OD.ProdId = P.ProdId\n"
+ + " AND P.ProdId = PC.ProdId\n"
+ + " AND PC.CatgId = C.CatgId\n"
+ + " AND O.OrdId = S.OrdId\n"
+ + " AND P.ProdId = R.ProdId"
+ + " AND U.UsrId = R.UsrId\n"
+ + " AND P.ProdId = D.ProdId\n"
+ + " AND W.WrhId = (P.ProdId % 5 + 1)",
+
+ // Correlated query.
+ "SELECT OD.OrdDetId, O.OrdId, P.ProdId, U.UsrNm, " +
+ "(SELECT MAX(C.ShippDate) from Shipping C where
C.OrdId=OD.OrdId) as corr " +
+ "from OrderDetails OD " +
+ "JOIN Orders O on O.OrdId = OD.OrdId " +
+ "JOIN Products P on P.ProdId = OD.ProdId " +
+ "JOIN Users U on O.UsrId = U.UsrId",
+
+ // Yet another correlated query.
+ "SELECT S.ShippDate, O.OrdId, P.ProdId, U.UsrNm, " +
+ "(SELECT MAX(C.Qnty) from OrderDetails C where C.OrdId=O.OrdId
and C.ProdId=O.ProdId) as corr, " +
+ "(SELECT AVG(C2.TotalAmount) from Orders C2 where
C2.ProdId=O.ProdId) as corr2 " +
+ "from Shipping S " +
+ "JOIN Orders O on O.OrdId = S.OrdId " +
+ "JOIN Products P on P.ProdId = O.ProdId " +
+ "JOIN Users U on O.UsrId = U.UsrId"
+ );
+ }
+}
diff --git
a/modules/calcite/src/test/java/org/apache/ignite/testsuites/IntegrationTestSuite.java
b/modules/calcite/src/test/java/org/apache/ignite/testsuites/IntegrationTestSuite.java
index f7b3744b789..954d7a4a883 100644
---
a/modules/calcite/src/test/java/org/apache/ignite/testsuites/IntegrationTestSuite.java
+++
b/modules/calcite/src/test/java/org/apache/ignite/testsuites/IntegrationTestSuite.java
@@ -80,6 +80,7 @@ import
org.apache.ignite.internal.processors.query.calcite.integration.tpch.Tpch
import
org.apache.ignite.internal.processors.query.calcite.jdbc.JdbcCrossEngineTest;
import org.apache.ignite.internal.processors.query.calcite.jdbc.JdbcQueryTest;
import
org.apache.ignite.internal.processors.query.calcite.rules.JoinCommuteRulesTest;
+import
org.apache.ignite.internal.processors.query.calcite.rules.JoinOrderOptimizationTest;
import
org.apache.ignite.internal.processors.query.calcite.rules.OrToUnionRuleTest;
import
org.apache.ignite.internal.processors.query.calcite.rules.ProjectScanMergeRuleTest;
import
org.apache.ignite.internal.processors.query.calcite.thin.MultiLineQueryTest;
@@ -125,6 +126,7 @@ import org.junit.runners.Suite;
UnstableTopologyIntegrationTest.class,
PartitionsReservationIntegrationTest.class,
JoinCommuteRulesTest.class,
+ JoinOrderOptimizationTest.class,
ServerStatisticsIntegrationTest.class,
JoinIntegrationTest.class,
IntervalTest.class,
