alex-plekhanov commented on code in PR #11935:
URL: https://github.com/apache/ignite/pull/11935#discussion_r2003677465
##########
modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/prepare/PlanningContext.java:
##########
@@ -193,10 +193,12 @@ public RuleSet rules(RuleSet set) {
}
/**
+ * Sets a rule filter. If already exists, enqueues the new one after the
current filter.
+ *
* @param rulesFilter Rules filter.
*/
public void rulesFilter(Function<RuleSet, RuleSet> rulesFilter) {
Review Comment:
Since we now append filter to the old one, perhaps it's worth to rename
method to something like `addRulesFilter` and corresponding method
`setDisabledRules` to something like `addDisabledRules`
##########
modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/prepare/PlannerHelper.java:
##########
@@ -129,6 +152,179 @@ public static IgniteRel optimize(SqlNode sqlNode,
IgnitePlanner planner, IgniteL
}
}
+ /** */
+ private static RelNode actualTopLevelJoinTypeHints(RelNode rel,
List<RelHint> topLevelHints) {
+ assert rel instanceof Hintable;
+
+ List<RelHint> curHints = ((Hintable)rel).getHints();
+
+ List<RelHint> res = new ArrayList<>(topLevelHints.size());
+
+ for (RelHint topHint : topLevelHints) {
+ assert topHint.inheritPath.isEmpty();
+
+ if (!JOIN_TYPE_HINT_NAMES.contains(topHint.hintName))
+ continue;
+
+ if (curHints.isEmpty()) {
+ res.add(topHint);
+
+ continue;
+ }
+
+ for (RelHint curHint : curHints) {
+ // Consider only hints of the join types and which differ by
name or parameters.
+ if (!JOIN_TYPE_HINT_NAMES.contains(curHint.hintName)
Review Comment:
No topHints will be added in case curHint is non-join hint. Let's also add
test case for this.
##########
modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/prepare/PlannerHelper.java:
##########
@@ -292,4 +488,34 @@ private boolean modifyNodeInsertsData() {
return modifyNode.isInsert();
}
}
+
+ /**
+ * @return Found dodes of type {@code nodeType} in the tree. Empty list if
no match found. Single value list if a node
Review Comment:
dodes -> nodes
##########
modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/prepare/PlannerHelper.java:
##########
@@ -129,6 +152,179 @@ public static IgniteRel optimize(SqlNode sqlNode,
IgnitePlanner planner, IgniteL
}
}
+ /** */
+ private static RelNode actualTopLevelJoinTypeHints(RelNode rel,
List<RelHint> topLevelHints) {
+ assert rel instanceof Hintable;
+
+ List<RelHint> curHints = ((Hintable)rel).getHints();
+
+ List<RelHint> res = new ArrayList<>(topLevelHints.size());
+
+ for (RelHint topHint : topLevelHints) {
+ assert topHint.inheritPath.isEmpty();
+
+ if (!JOIN_TYPE_HINT_NAMES.contains(topHint.hintName))
+ continue;
+
+ if (curHints.isEmpty()) {
+ res.add(topHint);
+
+ continue;
+ }
+
+ for (RelHint curHint : curHints) {
+ // Consider only hints of the join types and which differ by
name or parameters.
+ if (!JOIN_TYPE_HINT_NAMES.contains(curHint.hintName)
+ || topHint.equals(curHint.inheritPath.isEmpty() ? curHint
: curHint.copy(Collections.emptyList())))
+ continue;
+
+ res.add(topHint);
+ }
+ }
+
+ if (!res.isEmpty()) {
+ rel = ((Hintable)rel).withHints(res);
+
+ if (!curHints.isEmpty())
+ rel = ((Hintable)rel).attachHints(curHints);
+ }
+
+ 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);
+
+ // No original joins found, nothing to optimize.
+ if (joins.isEmpty())
+ return root;
+
+ int disabledCnt = 0;
+
+ // If all the joins have the forced order, no need to optimize the
joins order at all.
+ for (Join join : joins) {
+ for (RelHint hint : join.getHints()) {
+ if
(HintDefinition.ENFORCE_JOIN_ORDER.name().equals(hint.hintName)) {
+ ++disabledCnt;
+
+ break;
+ }
+ }
+ }
+
+ if (disabledCnt == joins.size())
+ return 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 root;
+
+ // If a new joins order was proposed, no need to launch another join
order optimizations.
+
planner.setDisabledRules(HintDefinition.ENFORCE_JOIN_ORDER.disabledRules().stream().map(RelOptRule::toString)
+ .collect(Collectors.toList()));
+
+ if (!topLevelHints.isEmpty()) {
+ res = actualTopLevelJoinTypeHints(res, topLevelHints);
+
+ restoreJoinTypeHints(res);
+ }
+
+ return res;
+ }
+
+ /**
+ * 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 List<List<RelHint>> hintsStack = new ArrayList<>();
+
+ /** 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 TableScans have 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()) {
+ // Reassing only top-level hints (without the inherit
path).
Review Comment:
reassing -> reasign
##########
modules/calcite/src/test/java/org/apache/ignite/internal/processors/query/calcite/planner/hints/JoinTypeHintPlannerTest.java:
##########
@@ -468,6 +529,50 @@ public void testNestedHintOverrides() throws Exception {
schema, predicateForNestedHintOverrides(true),
CORE_JOIN_REORDER_RULES);
}
+ /** */
+ @Test
+ public void testNestedHintOverridesWithReordering() throws Exception {
Review Comment:
Let's also add case with mixed inner and outer joins.
##########
modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/rule/logical/IgniteMultiJoinOptimizeRule.java:
##########
@@ -0,0 +1,457 @@
+/*
+ * 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.HashMap;
+import java.util.IdentityHashMap;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import org.apache.calcite.plan.RelOptRuleCall;
+import org.apache.calcite.plan.RelOptUtil;
+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.IgniteLogger;
+import org.apache.ignite.internal.processors.query.calcite.hint.HintDefinition;
+import org.apache.ignite.internal.processors.query.calcite.util.Commons;
+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>
+ */
+@Value.Enclosing
+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;
+ }
+
+ IgniteLogger log = Commons.context(multiJoinRel).logger();
+
+ if (log.isDebugEnabled())
+ log.debug("Optimizing multi-join " +
RelOptUtil.toString(multiJoinRel));
+
+ 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.
+ Map<Integer, List<Edge>> edges = collectEdges(multiJoin,
unusedConditions);
+ BitSet connections = new BitSet(1 << relCnt);
+ Map<Integer, Vertex> bestPlan = new HashMap<>();
+
+ 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(Map<Integer, 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.getOrDefault(lhs,
Collections.emptyList()));
+
+ used.addAll(union);
+
+ edges.getOrDefault(rhs, Collections.emptyList()).forEach(edge -> {
+ if (used.add(edge))
+ union.add(edge);
+ });
+
+ if (!union.isEmpty())
+ edges.put(id, union);
+ }
+ }
+
+ /** */
+ private static Vertex composeCartesianJoin(
+ int allRelationsMask,
+ Map<Integer, Vertex> bestPlan,
+ Map<Integer, 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 Map<Integer, List<Edge>> collectEdges(LoptMultiJoin
multiJoin, List<RexNode> unusedConditions) {
+ Map<Integer, List<Edge>> edges = new HashMap<>();
+
+ 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));
+
+ double leftSize = metadataQry.getRowCount(lhs.rel);
+ double rightSize = metadataQry.getRowCount(rhs.rel);
+
+ Vertex majorFactor;
+ Vertex minorFactor;
+
+ // Right side will probably be materialized. Let's put bigger input on
left side.
+ if (leftSize >= rightSize) {
Review Comment:
But it's a bad case for CNLJ
##########
modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/rule/logical/IgniteMultiJoinOptimizeRule.java:
##########
@@ -0,0 +1,457 @@
+/*
+ * 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.HashMap;
+import java.util.IdentityHashMap;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import org.apache.calcite.plan.RelOptRuleCall;
+import org.apache.calcite.plan.RelOptUtil;
+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.IgniteLogger;
+import org.apache.ignite.internal.processors.query.calcite.hint.HintDefinition;
+import org.apache.ignite.internal.processors.query.calcite.util.Commons;
+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>
+ */
+@Value.Enclosing
+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;
+ }
+
+ IgniteLogger log = Commons.context(multiJoinRel).logger();
+
+ if (log.isDebugEnabled())
+ log.debug("Optimizing multi-join " +
RelOptUtil.toString(multiJoinRel));
+
+ 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.
+ Map<Integer, List<Edge>> edges = collectEdges(multiJoin,
unusedConditions);
Review Comment:
IntMap?
##########
modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/prepare/PlannerHelper.java:
##########
@@ -129,6 +152,179 @@ public static IgniteRel optimize(SqlNode sqlNode,
IgnitePlanner planner, IgniteL
}
}
+ /** */
+ private static RelNode actualTopLevelJoinTypeHints(RelNode rel,
List<RelHint> topLevelHints) {
+ assert rel instanceof Hintable;
+
+ List<RelHint> curHints = ((Hintable)rel).getHints();
+
+ List<RelHint> res = new ArrayList<>(topLevelHints.size());
+
+ for (RelHint topHint : topLevelHints) {
+ assert topHint.inheritPath.isEmpty();
+
+ if (!JOIN_TYPE_HINT_NAMES.contains(topHint.hintName))
+ continue;
+
+ if (curHints.isEmpty()) {
+ res.add(topHint);
+
+ continue;
+ }
+
+ for (RelHint curHint : curHints) {
+ // Consider only hints of the join types and which differ by
name or parameters.
+ if (!JOIN_TYPE_HINT_NAMES.contains(curHint.hintName)
+ || topHint.equals(curHint.inheritPath.isEmpty() ? curHint
: curHint.copy(Collections.emptyList())))
+ continue;
+
+ res.add(topHint);
+ }
+ }
+
+ if (!res.isEmpty()) {
+ rel = ((Hintable)rel).withHints(res);
+
+ if (!curHints.isEmpty())
+ rel = ((Hintable)rel).attachHints(curHints);
+ }
+
+ 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);
+
+ // No original joins found, nothing to optimize.
+ if (joins.isEmpty())
+ return root;
+
+ int disabledCnt = 0;
+
+ // If all the joins have the forced order, no need to optimize the
joins order at all.
+ for (Join join : joins) {
+ for (RelHint hint : join.getHints()) {
+ if
(HintDefinition.ENFORCE_JOIN_ORDER.name().equals(hint.hintName)) {
+ ++disabledCnt;
+
+ break;
+ }
+ }
+ }
+
+ if (disabledCnt == joins.size())
+ return 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 root;
+
+ // If a new joins order was proposed, no need to launch another join
order optimizations.
+
planner.setDisabledRules(HintDefinition.ENFORCE_JOIN_ORDER.disabledRules().stream().map(RelOptRule::toString)
+ .collect(Collectors.toList()));
+
+ if (!topLevelHints.isEmpty()) {
+ res = actualTopLevelJoinTypeHints(res, topLevelHints);
+
+ restoreJoinTypeHints(res);
+ }
+
+ return res;
+ }
+
+ /**
+ * 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 List<List<RelHint>> hintsStack = new ArrayList<>();
+
+ /** 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 TableScans have 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()) {
Review Comment:
Why join is skipped? Can join hints be inherited?
##########
modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/prepare/PlannerHelper.java:
##########
@@ -129,6 +152,179 @@ public static IgniteRel optimize(SqlNode sqlNode,
IgnitePlanner planner, IgniteL
}
}
+ /** */
+ private static RelNode actualTopLevelJoinTypeHints(RelNode rel,
List<RelHint> topLevelHints) {
Review Comment:
Please move this method below optimizeJoinsOrder to simplify navigation
##########
modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/prepare/PlannerHelper.java:
##########
@@ -129,6 +152,179 @@ public static IgniteRel optimize(SqlNode sqlNode,
IgnitePlanner planner, IgniteL
}
}
+ /** */
+ private static RelNode actualTopLevelJoinTypeHints(RelNode rel,
List<RelHint> topLevelHints) {
+ assert rel instanceof Hintable;
+
+ List<RelHint> curHints = ((Hintable)rel).getHints();
+
+ List<RelHint> res = new ArrayList<>(topLevelHints.size());
+
+ for (RelHint topHint : topLevelHints) {
+ assert topHint.inheritPath.isEmpty();
+
+ if (!JOIN_TYPE_HINT_NAMES.contains(topHint.hintName))
+ continue;
+
+ if (curHints.isEmpty()) {
+ res.add(topHint);
+
+ continue;
+ }
+
+ for (RelHint curHint : curHints) {
+ // Consider only hints of the join types and which differ by
name or parameters.
+ if (!JOIN_TYPE_HINT_NAMES.contains(curHint.hintName)
+ || topHint.equals(curHint.inheritPath.isEmpty() ? curHint
: curHint.copy(Collections.emptyList())))
+ continue;
+
+ res.add(topHint);
Review Comment:
topHint can be added more than once
##########
modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/prepare/PlannerHelper.java:
##########
@@ -129,6 +152,179 @@ public static IgniteRel optimize(SqlNode sqlNode,
IgnitePlanner planner, IgniteL
}
}
+ /** */
+ private static RelNode actualTopLevelJoinTypeHints(RelNode rel,
List<RelHint> topLevelHints) {
+ assert rel instanceof Hintable;
+
+ List<RelHint> curHints = ((Hintable)rel).getHints();
+
+ List<RelHint> res = new ArrayList<>(topLevelHints.size());
+
+ for (RelHint topHint : topLevelHints) {
+ assert topHint.inheritPath.isEmpty();
+
+ if (!JOIN_TYPE_HINT_NAMES.contains(topHint.hintName))
+ continue;
+
+ if (curHints.isEmpty()) {
+ res.add(topHint);
+
+ continue;
+ }
+
+ for (RelHint curHint : curHints) {
+ // Consider only hints of the join types and which differ by
name or parameters.
+ if (!JOIN_TYPE_HINT_NAMES.contains(curHint.hintName)
+ || topHint.equals(curHint.inheritPath.isEmpty() ? curHint
: curHint.copy(Collections.emptyList())))
+ continue;
+
+ res.add(topHint);
+ }
+ }
+
+ if (!res.isEmpty()) {
+ rel = ((Hintable)rel).withHints(res);
+
+ if (!curHints.isEmpty())
+ rel = ((Hintable)rel).attachHints(curHints);
+ }
+
+ 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);
+
+ // No original joins found, nothing to optimize.
+ if (joins.isEmpty())
+ return root;
+
+ int disabledCnt = 0;
+
+ // If all the joins have the forced order, no need to optimize the
joins order at all.
+ for (Join join : joins) {
+ for (RelHint hint : join.getHints()) {
+ if
(HintDefinition.ENFORCE_JOIN_ORDER.name().equals(hint.hintName)) {
+ ++disabledCnt;
+
+ break;
+ }
+ }
+ }
+
+ if (disabledCnt == joins.size())
+ return 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 root;
+
+ // If a new joins order was proposed, no need to launch another join
order optimizations.
+
planner.setDisabledRules(HintDefinition.ENFORCE_JOIN_ORDER.disabledRules().stream().map(RelOptRule::toString)
+ .collect(Collectors.toList()));
+
+ if (!topLevelHints.isEmpty()) {
+ res = actualTopLevelJoinTypeHints(res, topLevelHints);
+
+ restoreJoinTypeHints(res);
+ }
+
+ return res;
+ }
+
+ /**
+ * 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 List<List<RelHint>> hintsStack = new ArrayList<>();
Review Comment:
Deque?
##########
modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/prepare/PlannerHelper.java:
##########
@@ -129,6 +152,179 @@ public static IgniteRel optimize(SqlNode sqlNode,
IgnitePlanner planner, IgniteL
}
}
+ /** */
+ private static RelNode actualTopLevelJoinTypeHints(RelNode rel,
List<RelHint> topLevelHints) {
+ assert rel instanceof Hintable;
+
+ List<RelHint> curHints = ((Hintable)rel).getHints();
+
+ List<RelHint> res = new ArrayList<>(topLevelHints.size());
+
+ for (RelHint topHint : topLevelHints) {
+ assert topHint.inheritPath.isEmpty();
+
+ if (!JOIN_TYPE_HINT_NAMES.contains(topHint.hintName))
+ continue;
+
+ if (curHints.isEmpty()) {
+ res.add(topHint);
+
+ continue;
+ }
+
+ for (RelHint curHint : curHints) {
+ // Consider only hints of the join types and which differ by
name or parameters.
+ if (!JOIN_TYPE_HINT_NAMES.contains(curHint.hintName)
+ || topHint.equals(curHint.inheritPath.isEmpty() ? curHint
: curHint.copy(Collections.emptyList())))
+ continue;
+
+ res.add(topHint);
+ }
+ }
+
+ if (!res.isEmpty()) {
+ rel = ((Hintable)rel).withHints(res);
+
+ if (!curHints.isEmpty())
+ rel = ((Hintable)rel).attachHints(curHints);
+ }
+
+ 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);
+
+ // No original joins found, nothing to optimize.
+ if (joins.isEmpty())
+ return root;
+
+ int disabledCnt = 0;
+
+ // If all the joins have the forced order, no need to optimize the
joins order at all.
+ for (Join join : joins) {
+ for (RelHint hint : join.getHints()) {
+ if
(HintDefinition.ENFORCE_JOIN_ORDER.name().equals(hint.hintName)) {
+ ++disabledCnt;
+
+ break;
+ }
+ }
+ }
+
+ if (disabledCnt == joins.size())
+ return 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 root;
+
+ // If a new joins order was proposed, no need to launch another join
order optimizations.
+
planner.setDisabledRules(HintDefinition.ENFORCE_JOIN_ORDER.disabledRules().stream().map(RelOptRule::toString)
+ .collect(Collectors.toList()));
Review Comment:
It's better to use `toSet()` since it checked by `contains` in
`setDisabledRules`.
Here we have references to rules and, perhaps, it's better to use references
instead of string presentation (up to you).
##########
modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/rel/agg/IgniteReduceSortAggregate.java:
##########
@@ -111,6 +111,11 @@ public IgniteReduceSortAggregate(RelInput input) {
return super.explainTerms(pw).item("collation", collation);
}
+ /** {@inheritDoc} */
+ @Override public RelCollation collation() {
Review Comment:
Please merge master branch. This conflict is not correctly resolved.
##########
modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/rule/logical/IgniteMultiJoinOptimizeRule.java:
##########
@@ -0,0 +1,457 @@
+/*
+ * 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.HashMap;
+import java.util.IdentityHashMap;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import org.apache.calcite.plan.RelOptRuleCall;
+import org.apache.calcite.plan.RelOptUtil;
+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.IgniteLogger;
+import org.apache.ignite.internal.processors.query.calcite.hint.HintDefinition;
+import org.apache.ignite.internal.processors.query.calcite.util.Commons;
+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
Review Comment:
crates -> creates
##########
modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/prepare/PlannerHelper.java:
##########
@@ -129,6 +152,179 @@ public static IgniteRel optimize(SqlNode sqlNode,
IgnitePlanner planner, IgniteL
}
}
+ /** */
+ private static RelNode actualTopLevelJoinTypeHints(RelNode rel,
List<RelHint> topLevelHints) {
+ assert rel instanceof Hintable;
+
+ List<RelHint> curHints = ((Hintable)rel).getHints();
+
+ List<RelHint> res = new ArrayList<>(topLevelHints.size());
+
+ for (RelHint topHint : topLevelHints) {
+ assert topHint.inheritPath.isEmpty();
+
+ if (!JOIN_TYPE_HINT_NAMES.contains(topHint.hintName))
+ continue;
+
+ if (curHints.isEmpty()) {
+ res.add(topHint);
+
+ continue;
+ }
+
+ for (RelHint curHint : curHints) {
+ // Consider only hints of the join types and which differ by
name or parameters.
+ if (!JOIN_TYPE_HINT_NAMES.contains(curHint.hintName)
+ || topHint.equals(curHint.inheritPath.isEmpty() ? curHint
: curHint.copy(Collections.emptyList())))
+ continue;
+
+ res.add(topHint);
+ }
+ }
+
+ if (!res.isEmpty()) {
+ rel = ((Hintable)rel).withHints(res);
+
+ if (!curHints.isEmpty())
+ rel = ((Hintable)rel).attachHints(curHints);
+ }
+
+ 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);
+
+ // No original joins found, nothing to optimize.
+ if (joins.isEmpty())
+ return root;
+
+ int disabledCnt = 0;
+
+ // If all the joins have the forced order, no need to optimize the
joins order at all.
+ for (Join join : joins) {
+ for (RelHint hint : join.getHints()) {
+ if
(HintDefinition.ENFORCE_JOIN_ORDER.name().equals(hint.hintName)) {
+ ++disabledCnt;
+
+ break;
+ }
+ }
+ }
+
+ if (disabledCnt == joins.size())
Review Comment:
Can we use some theshold to use multi-join optimized. For example, if there
are only 1-2 joins (2-3 tables) which can be permuted (`joins.size() -
disabledCnt <= 2`) it can be planned by CBO planner with better plans, since it
analyzes real costs for each join type, not only rows count.
##########
modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/rule/logical/IgniteMultiJoinOptimizeRule.java:
##########
@@ -0,0 +1,457 @@
+/*
+ * 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.HashMap;
+import java.util.IdentityHashMap;
+import java.util.Iterator;
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
+import org.apache.calcite.plan.RelOptRuleCall;
+import org.apache.calcite.plan.RelOptUtil;
+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.IgniteLogger;
+import org.apache.ignite.internal.processors.query.calcite.hint.HintDefinition;
+import org.apache.ignite.internal.processors.query.calcite.util.Commons;
+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>
+ */
+@Value.Enclosing
+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;
+ }
+
+ IgniteLogger log = Commons.context(multiJoinRel).logger();
+
+ if (log.isDebugEnabled())
+ log.debug("Optimizing multi-join " +
RelOptUtil.toString(multiJoinRel));
+
+ 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.
+ Map<Integer, List<Edge>> edges = collectEdges(multiJoin,
unusedConditions);
+ BitSet connections = new BitSet(1 << relCnt);
+ Map<Integer, Vertex> bestPlan = new HashMap<>();
Review Comment:
IntMap?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: notifications-unsubscr...@ignite.apache.org
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
