You are viewing a plain text version of this content. The canonical link for it is here.
Posted to notifications@ignite.apache.org by "korlov42 (via GitHub)" <gi...@apache.org> on 2025/01/11 13:30:31 UTC
[PR] IGNITE-24167 Sql. Introduce heuristics to optimize join order [ignite-3]
korlov42 opened a new pull request, #5026:
URL: https://github.com/apache/ignite-3/pull/5026
https://issues.apache.org/jira/browse/IGNITE-24167
Benchmark results for a few queries on my laptop as follow:
```
Before
Benchmark (fsync) (queryId) Mode Cnt Score Error Units
TpchBenchmark.run false 5 avgt 20 167251.070 ± 7210.703 ms/op
TpchBenchmark.run false 7 avgt 20 11808.586 ± 141.253 ms/op
TpchBenchmark.run false 8 avgt 20 7457.576 ± 140.864 ms/op
TpchBenchmark.run false 9 avgt 20 18017.645 ± 537.820 ms/op
Benchmark (fsync) (queryId) Mode Cnt Score Error Units
TpcdsBenchmark.run false 64 avgt 20 53087.853 ± 853.529 ms/op
After
Benchmark (fsync) (queryId) Mode Cnt Score Error Units
TpchBenchmark.run false 5 avgt 20 3824.434 ± 34.688 ms/op
TpchBenchmark.run false 7 avgt 20 5771.650 ± 19.906 ms/op
TpchBenchmark.run false 8 avgt 20 3844.181 ± 19.312 ms/op
TpchBenchmark.run false 9 avgt 20 9358.626 ± 1251.145 ms/op
Benchmark (fsync) (queryId) Mode Cnt Score Error Units
TpcdsBenchmark.run false 64 avgt 20 4280.076 ± 112.024 ms/op
```
Note: both runs contains changes related to `SqlStatisticManagerImpl` and query texts (i.e. include hints `NO_INDEX` and `DISABLE_RULE('MergeJoinConverter')`), so only order of joins did came into play.
---------------
Thank you for submitting the pull request.
To streamline the review process of the patch and ensure better code quality
we ask both an author and a reviewer to verify the following:
### The Review Checklist
- [ ] **Formal criteria:** TC status, codestyle, mandatory documentation. Also make sure to complete the following:
\- There is a single JIRA ticket related to the pull request.
\- The web-link to the pull request is attached to the JIRA ticket.
\- The JIRA ticket has the Patch Available state.
\- The description of the JIRA ticket explains WHAT was made, WHY and HOW.
\- The pull request title is treated as the final commit message. The following pattern must be used: IGNITE-XXXX Change summary where XXXX - number of JIRA issue.
- [ ] **Design:** new code conforms with the design principles of the components it is added to.
- [ ] **Patch quality:** patch cannot be split into smaller pieces, its size must be reasonable.
- [ ] **Code quality:** code is clean and readable, necessary developer documentation is added if needed.
- [ ] **Tests code quality:** test set covers positive/negative scenarios, happy/edge cases. Tests are effective in terms of execution time and resources.
### Notes
- [Apache Ignite Coding Guidelines](https://cwiki.apache.org/confluence/display/IGNITE/Java+Code+Style+Guide)
--
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-unsubscribe@ignite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] IGNITE-24167 Sql. Introduce heuristics to optimize join order [ignite-3]
Posted by "korlov42 (via GitHub)" <gi...@apache.org>.
korlov42 commented on code in PR #5026:
URL: https://github.com/apache/ignite-3/pull/5026#discussion_r1913347542
##########
modules/sql-engine/src/test/resources/mapping/table_identity.test:
##########
@@ -4,29 +4,30 @@ SELECT * FROM nt1_n1, nt2_n2
Fragment#0 root
executionNodes: [N0]
remoteFragments: [1, 2]
- exchangeSourceNodes: {1=[N1], 2=[N2]}
+ exchangeSourceNodes: {1=[N2], 2=[N1]}
tree:
- NestedLoopJoin
- Receiver(sourceFragment=1, exchange=1, distribution=single)
- Receiver(sourceFragment=2, exchange=2, distribution=single)
+ Project
Review Comment:
https://issues.apache.org/jira/browse/IGNITE-24196
--
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-unsubscribe@ignite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] IGNITE-24167 Sql. Introduce heuristics to optimize join order [ignite-3]
Posted by "AMashenkov (via GitHub)" <gi...@apache.org>.
AMashenkov commented on code in PR #5026:
URL: https://github.com/apache/ignite-3/pull/5026#discussion_r1913061734
##########
modules/sql-engine/src/test/java/org/apache/ignite/internal/sql/engine/planner/TpchQueryPlannerTest.java:
##########
@@ -17,75 +17,44 @@
package org.apache.ignite.internal.sql.engine.planner;
-import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.apache.ignite.internal.sql.engine.planner.AbstractTpcQueryPlannerTest.TpcSuiteInfo;
-import com.google.common.io.CharStreams;
-import java.io.IOException;
-import java.io.InputStream;
-import java.io.InputStreamReader;
-import java.io.UncheckedIOException;
-import java.nio.charset.StandardCharsets;
-import org.apache.calcite.plan.RelOptUtil;
-import org.apache.calcite.sql.SqlExplainLevel;
-import org.apache.ignite.internal.sql.engine.framework.TestBuilders;
-import org.apache.ignite.internal.sql.engine.framework.TestCluster;
-import org.apache.ignite.internal.sql.engine.framework.TestNode;
-import org.apache.ignite.internal.sql.engine.prepare.MultiStepPlan;
-import org.apache.ignite.internal.sql.engine.util.Cloner;
-import org.apache.ignite.internal.sql.engine.util.Commons;
import org.apache.ignite.internal.sql.engine.util.tpch.TpchHelper;
import org.apache.ignite.internal.sql.engine.util.tpch.TpchTables;
-import org.junit.jupiter.api.AfterAll;
-import org.junit.jupiter.api.BeforeAll;
-import org.junit.jupiter.api.Test;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.ValueSource;
/**
* Tests ensures a planner generates optimal plan for TPC-H queries.
*
* @see org.apache.ignite.internal.sql.engine.benchmarks.TpchParseBenchmark
*/
// TODO https://issues.apache.org/jira/browse/IGNITE-21986 validate other query plans and make test parameterized.
-public class TpchQueryPlannerTest extends AbstractPlannerTest {
- private static TestCluster CLUSTER;
-
- @BeforeAll
- static void startCluster() {
- CLUSTER = TestBuilders.cluster().nodes("N1").build();
- CLUSTER.start();
-
- TestNode node = CLUSTER.node("N1");
-
- node.initSchema(TpchTables.LINEITEM.ddlScript());
+@TpcSuiteInfo(
+ tables = TpchTables.class,
+ queryLoader = "getQueryString",
+ planLoader = "getQueryPlan"
+)
+public class TpchQueryPlannerTest extends AbstractTpcQueryPlannerTest {
+ @ParameterizedTest
+ // Query #7 contains disjunctive predicate that switches its part from run to run, making
Review Comment:
I think the reason is we use. HashSet/HashMap somewhere.
E.g. `Set<CorrelationId> correlationIds = new HashSet<>();` in CorrelatedNestedLoopJoinRule
--
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-unsubscribe@ignite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] IGNITE-24167 Sql. Introduce heuristics to optimize join order [ignite-3]
Posted by "AMashenkov (via GitHub)" <gi...@apache.org>.
AMashenkov commented on code in PR #5026:
URL: https://github.com/apache/ignite-3/pull/5026#discussion_r1914805776
##########
modules/sql-engine/src/main/java/org/apache/ignite/internal/sql/engine/rule/logical/IgniteMultiJoinOptimizeBushyRule.java:
##########
@@ -0,0 +1,449 @@
+/*
+ * 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.sql.engine.rule.logical;
+
+import static java.lang.Integer.bitCount;
+
+import it.unimi.dsi.fastutil.ints.Int2ObjectMap;
+import it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap;
+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.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.immutables.value.Value;
+import org.jetbrains.annotations.Nullable;
+
+/**
+ * Transformation rule used for optimizing multi-join queries using a bushy join tree strategy.
+ *
+ * <p>This is an implementation of subset-driven enumeration algorithm (Inspired by G. Moerkotte and T. Neumann.
+ * Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join
+ * Trees without Cross Products. 2.2 Subset-Driven Enumeration). The main loop (which actually consists of two
+ * for-loop) enumerates all subset of relations in a way suitable for dynamic programming: it guarantees,
+ * that for every set {@code S}, any split of the S will produce subsets which have been already processed:
+ * <pre>
+ * For example, for join of 4 relations it will produce following sequence:
+ * 0011
+ * 0101
+ * 0110
+ * ...
+ * 1101
+ * 1110
+ * 1111
+ * </pre>
+ *
+ * <p>The inner while-loop enumerates all possible splits of given subset {@code S} on disjoint subset
+ * {@code lhs} and {@code rhs} such that {@code lhs ∪ rhs = S} (Inspired by B. Vance and D. Maier.
+ * Rapid bushy join-order optimization with cartesian products).
+ *
+ * <p>Finally, if the initial set of relations is not connected, the algorithm composes cartesian join
+ * from best plans, until all relations are joined.
+ *
+ * <p>Current limitations are as follow:<ol>
+ * <li>Only INNER joins are supported</li>
+ * <li>Number of relations to optimize is limited to 20. This is due to time and memory complexity of algorithm chosen.</li>
+ * <li>Disjunctive predicate is not considered as connections.</li>
+ * </ol>
+ */
+@Value.Enclosing
+public class IgniteMultiJoinOptimizeBushyRule
+ extends RelRule<IgniteMultiJoinOptimizeBushyRule.Config>
+ implements TransformationRule {
+
+ private static final int MAX_JOIN_SIZE = 20;
+
+ /**
+ * Comparator that puts better vertexes first.
+ *
+ * <p>Better vertex is the one that incorporate more relations, or costs less.
+ */
+ private static final Comparator<Vertex> VERTEX_COMPARATOR =
+ Comparator.<Vertex>comparingInt(v -> bitCount(v.id))
+ .reversed()
+ .thenComparingDouble(v -> v.cost);
+
+ /** Creates a MultiJoinOptimizeBushyRule. */
+ private IgniteMultiJoinOptimizeBushyRule(Config config) {
+ super(config);
+ }
+
+ @Override
+ public void onMatch(RelOptRuleCall call) {
+ MultiJoin multiJoinRel = call.rel(0);
+
+ int numberOfRelations = multiJoinRel.getInputs().size();
+ if (numberOfRelations > MAX_JOIN_SIZE) {
+ return;
+ }
+
+ // Currently, algorithm below can handle only INNER JOINs
+ if (multiJoinRel.isFullOuterJoin()) {
+ 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 mq = call.getMetadataQuery();
+
+ List<RexNode> unusedConditions = new ArrayList<>();
+
+ Int2ObjectMap<List<Edge>> edges = collectEdges(multiJoin, unusedConditions);
+ Int2ObjectMap<Vertex> bestPlan = new Int2ObjectOpenHashMap<>();
+ BitSet connections = new BitSet(1 << numberOfRelations);
+
+ int id = 0b1;
+ int fieldOffset = 0;
+ for (RelNode input : multiJoinRel.getInputs()) {
+ TargetMapping mapping = Mappings.offsetSource(
+ Mappings.createIdentity(input.getRowType().getFieldCount()),
+ fieldOffset,
+ multiJoin.getNumTotalFields()
+ );
+
+ bestPlan.put(id, new Vertex(id, mq.getRowCount(input), input, mapping));
+ connections.set(id);
+
+ id <<= 1;
+ fieldOffset += input.getRowType().getFieldCount();
+ }
+
+ Vertex bestSoFar = null;
+ for (int k = 2; k <= numberOfRelations; k++) {
+ for (int s = (1 << (k - 1)) + 1; s < 1 << k; s++) {
Review Comment:
```suggestion
// Nested for-loops generates sequence from 0b11 up to (1<< numberOfRelations) - 1 skipping values, which are power of 2.
for (int k = 2; k <= numberOfRelations; k++) {
for (int s = (1 << (k - 1)) + 1; s < 1 << k; s++) {
```
--
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-unsubscribe@ignite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] IGNITE-24167 Sql. Introduce heuristics to optimize join order [ignite-3]
Posted by "zstan (via GitHub)" <gi...@apache.org>.
zstan commented on code in PR #5026:
URL: https://github.com/apache/ignite-3/pull/5026#discussion_r1913041441
##########
modules/sql-engine/src/integrationTest/java/org/apache/ignite/internal/sql/engine/statistic/ItStatisticTest.java:
##########
@@ -51,7 +51,7 @@ public void testStatisticsRowCount() throws Exception {
insertAndUpdateRunQuery(500);
// Minimum row count is 1000, even we have less rows.
Review Comment:
seems this comment is not relevant
##########
modules/sql-engine/src/main/java/org/apache/ignite/internal/sql/engine/prepare/IgnitePlanner.java:
##########
@@ -235,6 +237,22 @@ public RelNode convert(SqlNode sql) {
throw new UnsupportedOperationException();
}
+ /** Derives hints from give relation node, if possible. */
Review Comment:
```suggestion
/** Derives hints from given relation node, if possible. */
```
--
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-unsubscribe@ignite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] IGNITE-24167 Sql. Introduce heuristics to optimize join order [ignite-3]
Posted by "AMashenkov (via GitHub)" <gi...@apache.org>.
AMashenkov commented on code in PR #5026:
URL: https://github.com/apache/ignite-3/pull/5026#discussion_r1914697447
##########
modules/sql-engine/src/main/java/org/apache/ignite/internal/sql/engine/rule/logical/IgniteMultiJoinOptimizeBushyRule.java:
##########
@@ -0,0 +1,425 @@
+/*
+ * 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.sql.engine.rule.logical;
+
+import static java.lang.Integer.bitCount;
+
+import it.unimi.dsi.fastutil.ints.Int2ObjectMap;
+import it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap;
+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.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.immutables.value.Value;
+import org.jetbrains.annotations.Nullable;
+
+/**
+ * Transformation rule used for optimizing multi-join queries using a bushy join tree strategy.
+ *
+ * <p>This is an implementation of subset-driven enumeration algorithm. The main loop (which actually consists
+ * of two for-loop) enumerates all subset of relations in a way suitable for dynamic programming: it guarantees,
+ * that for every set {@code S}, any split of the S will produce subsets which have been already processed:
+ * <pre>
+ * For example, for join of 4 relations it will produce following sequence:
+ * 0011
+ * 0101
+ * 0110
+ * ...
+ * 1101
+ * 1110
+ * 1111
+ * </pre>
+ *
+ * <p>The inner while-loop enumerates all possible splits of given subset {@code S} on disjoint subset
+ * {@code lhs} and {@code rhs} such that {@code lhs ∪ rhs = S}.
+ *
+ * <p>Finally, if the initial set of relations is not connected, the algorithm composes cartesian join
+ * from best plans, until all relations are joined.
+ *
+ * <p>Current limitations are as follow:<ol>
+ * <li>Only INNER joins are supported</li>
+ * <li>Number of relations to optimize is limited to 20. This is due to time and memory complexity of algorithm chosen.</li>
+ * <li>Disjunctive predicate is not considered as connections.</li>
+ * </ol>
+ */
+@Value.Enclosing
+public class IgniteMultiJoinOptimizeBushyRule
+ extends RelRule<IgniteMultiJoinOptimizeBushyRule.Config>
+ implements TransformationRule {
+
+ private static final int MAX_JOIN_SIZE = 20;
+
+ /**
+ * Comparator that puts better vertexes first.
+ *
+ * <p>Better vertex is the one that incorporate more relations, or costs less.
+ */
+ private static final Comparator<Vertex> VERTEX_COMPARATOR =
+ Comparator.<Vertex>comparingInt(v -> bitCount(v.id))
+ .reversed()
+ .thenComparingDouble(v -> v.cost);
+
+ /** Creates a MultiJoinOptimizeBushyRule. */
+ private IgniteMultiJoinOptimizeBushyRule(Config config) {
+ super(config);
+ }
+
+ @Override
+ public void onMatch(RelOptRuleCall call) {
+ MultiJoin multiJoinRel = call.rel(0);
+
+ int numberOfRelations = multiJoinRel.getInputs().size();
+ if (numberOfRelations > MAX_JOIN_SIZE) {
+ return;
+ }
+
+ // Currently, algorithm below can handle only INNER JOINs
+ if (multiJoinRel.isFullOuterJoin()) {
+ 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 mq = call.getMetadataQuery();
+
+ Set<RexNode> unusedConditions = Collections.newSetFromMap(new IdentityHashMap<>());
+ unusedConditions.addAll(multiJoin.getJoinFilters());
+
+ Int2ObjectMap<List<Edge>> edges = collectEdges(multiJoin, unusedConditions);
+ Int2ObjectMap<Vertex> bestPlan = new Int2ObjectOpenHashMap<>();
+ BitSet connections = new BitSet(1 << numberOfRelations);
+
+ int id = 0b1;
+ int fieldOffset = 0;
+ for (RelNode input : multiJoinRel.getInputs()) {
+ TargetMapping mapping = Mappings.offsetSource(
+ Mappings.createIdentity(input.getRowType().getFieldCount()),
+ fieldOffset,
+ multiJoin.getNumTotalFields()
+ );
+
+ bestPlan.put(id, new Vertex(id, mq.getRowCount(input), input, mapping));
+ connections.set(id);
+
+ id <<= 1;
+ fieldOffset += input.getRowType().getFieldCount();
+ }
+
+ Vertex bestSoFar = null;
+ for (int k = 2; k <= numberOfRelations; k++) {
+ for (int s = (1 << (k - 1)) + 1; s < 1 << k; s++) {
+ int lhs = Integer.lowestOneBit(s);
+ while (lhs < (s / 2) + 1) {
+ int rhs = s - lhs;
+
+ List<Edge> edges0;
+ if (connections.get(lhs) && connections.get(rhs)) {
+ edges0 = findEdges(lhs, rhs, edges);
+ } else {
+ edges0 = List.of();
+ }
+
+ if (!edges0.isEmpty()) {
+ connections.set(s);
+
+ Vertex planLhs = bestPlan.get(lhs);
+ Vertex planRhs = bestPlan.get(rhs);
+
+ Vertex newPlan = createJoin(planLhs, planRhs, edges0, mq, relBuilder, rexBuilder);
+ Vertex currentBest = bestPlan.get(s);
+ if (currentBest == null || currentBest.cost > newPlan.cost) {
+ bestPlan.put(s, newPlan);
+
+ bestSoFar = chooseBest(bestSoFar, newPlan);
+ }
+
+ aggregateEdges(edges, lhs, rhs);
+ }
+
+ lhs = s & (lhs - s);
+ }
+ }
+ }
+
+ Vertex best;
+ if (bestSoFar == null || bestSoFar.id != (1 << numberOfRelations) - 1) {
+ best = composeCartesianJoin(bestPlan, edges, bestSoFar, mq, relBuilder, rexBuilder);
+ } else {
+ best = bestSoFar;
+ }
+
+ RelNode result = relBuilder
+ .push(best.rel)
+ .filter(RexUtil.composeConjunction(rexBuilder, unusedConditions)
+ .accept(new RexPermuteInputsShuttle(best.mapping, best.rel)))
+ .project(relBuilder.fields(best.mapping))
+ .build();
+
+ call.transformTo(result);
+ }
+
+ private static void aggregateEdges(Int2ObjectMap<List<Edge>> edges, int lhs, int rhs) {
+ int id = lhs | rhs;
+ if (!edges.containsKey(id)) {
+ Set<Edge> union = Collections.newSetFromMap(new IdentityHashMap<>());
+
+ union.addAll(edges.getOrDefault(lhs, List.of()));
+ union.addAll(edges.getOrDefault(rhs, List.of()));
+
+ edges.put(id, List.copyOf(union));
+ }
+ }
+
+ private static Vertex composeCartesianJoin(
+ Int2ObjectMap<Vertex> bestPlan,
+ Int2ObjectMap<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()) {
+ 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);
+ }
+
+ return bestSoFar;
+ }
+
+ private static Vertex chooseBest(@Nullable Vertex currentBest, Vertex candidate) {
+ if (currentBest == null) {
+ return candidate;
+ }
+
+ if (VERTEX_COMPARATOR.compare(currentBest, candidate) > 0) {
+ return candidate;
+ }
+
+ return currentBest;
+ }
+
+ private static Int2ObjectMap<List<Edge>> collectEdges(LoptMultiJoin multiJoin, Set<RexNode> unusedConditions) {
+ Int2ObjectMap<List<Edge>> edges = new Int2ObjectOpenHashMap<>();
+
+ for (RexNode condition : multiJoin.getJoinFilters()) {
+ int[] inputRefs = multiJoin.getFactorsRefByJoinFilter(condition).toArray();
+
+ if (inputRefs.length < 2 || condition.isA(SqlKind.OR)) {
+ continue;
+ }
+
+ unusedConditions.remove(condition);
Review Comment:
We can fill `unusedConditions` inside the `if-block` instead of removing them.
This will avoid one iteration over join filter, lookups into hasheset, and Set structure can be replaced with a List.
--
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-unsubscribe@ignite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] IGNITE-24167 Sql. Introduce heuristics to optimize join order [ignite-3]
Posted by "ygerzhedovich (via GitHub)" <gi...@apache.org>.
ygerzhedovich commented on code in PR #5026:
URL: https://github.com/apache/ignite-3/pull/5026#discussion_r1916149124
##########
modules/sql-engine/src/main/java/org/apache/ignite/internal/sql/engine/rule/logical/IgniteMultiJoinOptimizeBushyRule.java:
##########
@@ -0,0 +1,453 @@
+/*
+ * 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.sql.engine.rule.logical;
+
+import static java.lang.Integer.bitCount;
+import static org.apache.ignite.internal.util.IgniteUtils.isPow2;
+
+import it.unimi.dsi.fastutil.ints.Int2ObjectMap;
+import it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap;
+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.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.immutables.value.Value;
+import org.jetbrains.annotations.Nullable;
+
+/**
+ * Transformation rule used for optimizing multi-join queries using a bushy join tree strategy.
+ *
+ * <p>This is an implementation of subset-driven enumeration algorithm (Inspired by G. Moerkotte and T. Neumann.
+ * Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join
+ * Trees without Cross Products. 2.2 Subset-Driven Enumeration). The main loop enumerates all subsets of relations
+ * in a way suitable for dynamic programming: it guarantees, that for every emitted set {@code S}, any split of the
+ * {@code S} will produce subsets which have been already processed:
+ * <pre>
+ * For example, for join of 4 relations it will produce following sequence:
+ * 0011
+ * 0101
+ * 0110
+ * ...
+ * 1101
+ * 1110
+ * 1111
+ * </pre>
+ *
+ * <p>The inner while-loop enumerates all possible splits of given subset {@code S} on disjoint subset
+ * {@code lhs} and {@code rhs} such that {@code lhs ∪ rhs = S} (Inspired by B. Vance and D. Maier.
+ * Rapid bushy join-order optimization with cartesian products).
+ *
+ * <p>Finally, if the initial set of relations is not connected, the algorithm composes cartesian join
+ * from best plans, until all relations are joined.
+ *
+ * <p>Current limitations are as follow:<ol>
+ * <li>Only INNER joins are supported</li>
+ * <li>Number of relations to optimize is limited to 20. This is due to time and memory complexity of algorithm chosen.</li>
+ * <li>Disjunctive predicate is not considered as connections.</li>
+ * </ol>
+ */
+@Value.Enclosing
+public class IgniteMultiJoinOptimizeBushyRule
+ extends RelRule<IgniteMultiJoinOptimizeBushyRule.Config>
+ implements TransformationRule {
+
+ private static final int MAX_JOIN_SIZE = 20;
+
+ /**
+ * Comparator that puts better vertexes first.
+ *
+ * <p>Better vertex is the one that incorporate more relations, or costs less.
+ */
+ private static final Comparator<Vertex> VERTEX_COMPARATOR =
+ Comparator.<Vertex>comparingInt(v -> bitCount(v.id))
Review Comment:
bit count can be precomputed during Vertex creation instead of recalculating on every comparison in the comparator
##########
modules/sql-engine/src/main/java/org/apache/ignite/internal/sql/engine/rule/logical/IgniteMultiJoinOptimizeBushyRule.java:
##########
@@ -0,0 +1,453 @@
+/*
+ * 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.sql.engine.rule.logical;
+
+import static java.lang.Integer.bitCount;
+import static org.apache.ignite.internal.util.IgniteUtils.isPow2;
+
+import it.unimi.dsi.fastutil.ints.Int2ObjectMap;
+import it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap;
+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.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.immutables.value.Value;
+import org.jetbrains.annotations.Nullable;
+
+/**
+ * Transformation rule used for optimizing multi-join queries using a bushy join tree strategy.
+ *
+ * <p>This is an implementation of subset-driven enumeration algorithm (Inspired by G. Moerkotte and T. Neumann.
+ * Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join
+ * Trees without Cross Products. 2.2 Subset-Driven Enumeration). The main loop enumerates all subsets of relations
+ * in a way suitable for dynamic programming: it guarantees, that for every emitted set {@code S}, any split of the
+ * {@code S} will produce subsets which have been already processed:
+ * <pre>
+ * For example, for join of 4 relations it will produce following sequence:
+ * 0011
+ * 0101
+ * 0110
+ * ...
+ * 1101
+ * 1110
+ * 1111
+ * </pre>
+ *
+ * <p>The inner while-loop enumerates all possible splits of given subset {@code S} on disjoint subset
+ * {@code lhs} and {@code rhs} such that {@code lhs ∪ rhs = S} (Inspired by B. Vance and D. Maier.
+ * Rapid bushy join-order optimization with cartesian products).
+ *
+ * <p>Finally, if the initial set of relations is not connected, the algorithm composes cartesian join
+ * from best plans, until all relations are joined.
+ *
+ * <p>Current limitations are as follow:<ol>
+ * <li>Only INNER joins are supported</li>
+ * <li>Number of relations to optimize is limited to 20. This is due to time and memory complexity of algorithm chosen.</li>
+ * <li>Disjunctive predicate is not considered as connections.</li>
+ * </ol>
+ */
+@Value.Enclosing
+public class IgniteMultiJoinOptimizeBushyRule
+ extends RelRule<IgniteMultiJoinOptimizeBushyRule.Config>
+ implements TransformationRule {
+
+ private static final int MAX_JOIN_SIZE = 20;
+
+ /**
+ * Comparator that puts better vertexes first.
+ *
+ * <p>Better vertex is the one that incorporate more relations, or costs less.
+ */
+ private static final Comparator<Vertex> VERTEX_COMPARATOR =
+ Comparator.<Vertex>comparingInt(v -> bitCount(v.id))
+ .reversed()
+ .thenComparingDouble(v -> v.cost);
+
+ /** Creates a MultiJoinOptimizeBushyRule. */
+ private IgniteMultiJoinOptimizeBushyRule(Config config) {
+ super(config);
+ }
+
+ @Override
+ public void onMatch(RelOptRuleCall call) {
+ MultiJoin multiJoinRel = call.rel(0);
+
+ int numberOfRelations = multiJoinRel.getInputs().size();
+ if (numberOfRelations > MAX_JOIN_SIZE) {
+ return;
+ }
+
+ // Currently, algorithm below can handle only INNER JOINs
+ if (multiJoinRel.isFullOuterJoin()) {
+ 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 mq = call.getMetadataQuery();
+
+ List<RexNode> unusedConditions = new ArrayList<>();
+
+ Int2ObjectMap<List<Edge>> edges = collectEdges(multiJoin, unusedConditions);
+ Int2ObjectMap<Vertex> bestPlan = new Int2ObjectOpenHashMap<>();
+ BitSet connections = new BitSet(1 << numberOfRelations);
+
+ int id = 0b1;
+ int fieldOffset = 0;
+ for (RelNode input : multiJoinRel.getInputs()) {
+ TargetMapping mapping = Mappings.offsetSource(
+ Mappings.createIdentity(input.getRowType().getFieldCount()),
+ fieldOffset,
+ multiJoin.getNumTotalFields()
+ );
+
+ bestPlan.put(id, new Vertex(id, mq.getRowCount(input), input, mapping));
+ connections.set(id);
+
+ id <<= 1;
+ fieldOffset += input.getRowType().getFieldCount();
+ }
+
+ Vertex bestSoFar = null;
+ for (int s = 0b11; s < 1 << numberOfRelations; s++) {
Review Comment:
let's introduce constant instead of magic number
--
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-unsubscribe@ignite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] IGNITE-24167 Sql. Introduce heuristics to optimize join order [ignite-3]
Posted by "AMashenkov (via GitHub)" <gi...@apache.org>.
AMashenkov commented on code in PR #5026:
URL: https://github.com/apache/ignite-3/pull/5026#discussion_r1913091696
##########
modules/sql-engine/src/test/resources/mapping/test_backup_mapping.test:
##########
Review Comment:
Please revert
--
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-unsubscribe@ignite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] IGNITE-24167 Sql. Introduce heuristics to optimize join order [ignite-3]
Posted by "korlov42 (via GitHub)" <gi...@apache.org>.
korlov42 commented on code in PR #5026:
URL: https://github.com/apache/ignite-3/pull/5026#discussion_r1916427532
##########
modules/sql-engine/src/main/java/org/apache/ignite/internal/sql/engine/rule/logical/IgniteMultiJoinOptimizeBushyRule.java:
##########
@@ -0,0 +1,453 @@
+/*
+ * 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.sql.engine.rule.logical;
+
+import static java.lang.Integer.bitCount;
+import static org.apache.ignite.internal.util.IgniteUtils.isPow2;
+
+import it.unimi.dsi.fastutil.ints.Int2ObjectMap;
+import it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap;
+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.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.immutables.value.Value;
+import org.jetbrains.annotations.Nullable;
+
+/**
+ * Transformation rule used for optimizing multi-join queries using a bushy join tree strategy.
+ *
+ * <p>This is an implementation of subset-driven enumeration algorithm (Inspired by G. Moerkotte and T. Neumann.
+ * Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join
+ * Trees without Cross Products. 2.2 Subset-Driven Enumeration). The main loop enumerates all subsets of relations
+ * in a way suitable for dynamic programming: it guarantees, that for every emitted set {@code S}, any split of the
+ * {@code S} will produce subsets which have been already processed:
+ * <pre>
+ * For example, for join of 4 relations it will produce following sequence:
+ * 0011
+ * 0101
+ * 0110
+ * ...
+ * 1101
+ * 1110
+ * 1111
+ * </pre>
+ *
+ * <p>The inner while-loop enumerates all possible splits of given subset {@code S} on disjoint subset
+ * {@code lhs} and {@code rhs} such that {@code lhs ∪ rhs = S} (Inspired by B. Vance and D. Maier.
+ * Rapid bushy join-order optimization with cartesian products).
+ *
+ * <p>Finally, if the initial set of relations is not connected, the algorithm composes cartesian join
+ * from best plans, until all relations are joined.
+ *
+ * <p>Current limitations are as follow:<ol>
+ * <li>Only INNER joins are supported</li>
+ * <li>Number of relations to optimize is limited to 20. This is due to time and memory complexity of algorithm chosen.</li>
+ * <li>Disjunctive predicate is not considered as connections.</li>
+ * </ol>
+ */
+@Value.Enclosing
+public class IgniteMultiJoinOptimizeBushyRule
+ extends RelRule<IgniteMultiJoinOptimizeBushyRule.Config>
+ implements TransformationRule {
+
+ private static final int MAX_JOIN_SIZE = 20;
+
+ /**
+ * Comparator that puts better vertexes first.
+ *
+ * <p>Better vertex is the one that incorporate more relations, or costs less.
+ */
+ private static final Comparator<Vertex> VERTEX_COMPARATOR =
+ Comparator.<Vertex>comparingInt(v -> bitCount(v.id))
+ .reversed()
+ .thenComparingDouble(v -> v.cost);
+
+ /** Creates a MultiJoinOptimizeBushyRule. */
+ private IgniteMultiJoinOptimizeBushyRule(Config config) {
+ super(config);
+ }
+
+ @Override
+ public void onMatch(RelOptRuleCall call) {
+ MultiJoin multiJoinRel = call.rel(0);
+
+ int numberOfRelations = multiJoinRel.getInputs().size();
+ if (numberOfRelations > MAX_JOIN_SIZE) {
+ return;
+ }
+
+ // Currently, algorithm below can handle only INNER JOINs
+ if (multiJoinRel.isFullOuterJoin()) {
+ 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 mq = call.getMetadataQuery();
+
+ List<RexNode> unusedConditions = new ArrayList<>();
+
+ Int2ObjectMap<List<Edge>> edges = collectEdges(multiJoin, unusedConditions);
+ Int2ObjectMap<Vertex> bestPlan = new Int2ObjectOpenHashMap<>();
+ BitSet connections = new BitSet(1 << numberOfRelations);
+
+ int id = 0b1;
+ int fieldOffset = 0;
+ for (RelNode input : multiJoinRel.getInputs()) {
+ TargetMapping mapping = Mappings.offsetSource(
+ Mappings.createIdentity(input.getRowType().getFieldCount()),
+ fieldOffset,
+ multiJoin.getNumTotalFields()
+ );
+
+ bestPlan.put(id, new Vertex(id, mq.getRowCount(input), input, mapping));
+ connections.set(id);
+
+ id <<= 1;
+ fieldOffset += input.getRowType().getFieldCount();
+ }
+
+ Vertex bestSoFar = null;
+ for (int s = 0b11; s < 1 << numberOfRelations; s++) {
Review Comment:
I believe this "magic number" is self-explanatory: it represents a bit mask with two lowermost bit set to 1
--
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-unsubscribe@ignite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] IGNITE-24167 Sql. Introduce heuristics to optimize join order [ignite-3]
Posted by "korlov42 (via GitHub)" <gi...@apache.org>.
korlov42 commented on code in PR #5026:
URL: https://github.com/apache/ignite-3/pull/5026#discussion_r1916620112
##########
modules/sql-engine/src/main/java/org/apache/ignite/internal/sql/engine/rule/logical/IgniteMultiJoinOptimizeBushyRule.java:
##########
@@ -0,0 +1,453 @@
+/*
+ * 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.sql.engine.rule.logical;
+
+import static java.lang.Integer.bitCount;
+import static org.apache.ignite.internal.util.IgniteUtils.isPow2;
+
+import it.unimi.dsi.fastutil.ints.Int2ObjectMap;
+import it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap;
+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.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.immutables.value.Value;
+import org.jetbrains.annotations.Nullable;
+
+/**
+ * Transformation rule used for optimizing multi-join queries using a bushy join tree strategy.
+ *
+ * <p>This is an implementation of subset-driven enumeration algorithm (Inspired by G. Moerkotte and T. Neumann.
+ * Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join
+ * Trees without Cross Products. 2.2 Subset-Driven Enumeration). The main loop enumerates all subsets of relations
+ * in a way suitable for dynamic programming: it guarantees, that for every emitted set {@code S}, any split of the
+ * {@code S} will produce subsets which have been already processed:
+ * <pre>
+ * For example, for join of 4 relations it will produce following sequence:
+ * 0011
+ * 0101
+ * 0110
+ * ...
+ * 1101
+ * 1110
+ * 1111
+ * </pre>
+ *
+ * <p>The inner while-loop enumerates all possible splits of given subset {@code S} on disjoint subset
+ * {@code lhs} and {@code rhs} such that {@code lhs ∪ rhs = S} (Inspired by B. Vance and D. Maier.
+ * Rapid bushy join-order optimization with cartesian products).
+ *
+ * <p>Finally, if the initial set of relations is not connected, the algorithm composes cartesian join
+ * from best plans, until all relations are joined.
+ *
+ * <p>Current limitations are as follow:<ol>
+ * <li>Only INNER joins are supported</li>
+ * <li>Number of relations to optimize is limited to 20. This is due to time and memory complexity of algorithm chosen.</li>
+ * <li>Disjunctive predicate is not considered as connections.</li>
+ * </ol>
+ */
+@Value.Enclosing
+public class IgniteMultiJoinOptimizeBushyRule
+ extends RelRule<IgniteMultiJoinOptimizeBushyRule.Config>
+ implements TransformationRule {
+
+ private static final int MAX_JOIN_SIZE = 20;
+
+ /**
+ * Comparator that puts better vertexes first.
+ *
+ * <p>Better vertex is the one that incorporate more relations, or costs less.
+ */
+ private static final Comparator<Vertex> VERTEX_COMPARATOR =
+ Comparator.<Vertex>comparingInt(v -> bitCount(v.id))
+ .reversed()
+ .thenComparingDouble(v -> v.cost);
+
+ /** Creates a MultiJoinOptimizeBushyRule. */
+ private IgniteMultiJoinOptimizeBushyRule(Config config) {
+ super(config);
+ }
+
+ @Override
+ public void onMatch(RelOptRuleCall call) {
+ MultiJoin multiJoinRel = call.rel(0);
+
+ int numberOfRelations = multiJoinRel.getInputs().size();
+ if (numberOfRelations > MAX_JOIN_SIZE) {
+ return;
+ }
+
+ // Currently, algorithm below can handle only INNER JOINs
+ if (multiJoinRel.isFullOuterJoin()) {
+ 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 mq = call.getMetadataQuery();
+
+ List<RexNode> unusedConditions = new ArrayList<>();
+
+ Int2ObjectMap<List<Edge>> edges = collectEdges(multiJoin, unusedConditions);
+ Int2ObjectMap<Vertex> bestPlan = new Int2ObjectOpenHashMap<>();
+ BitSet connections = new BitSet(1 << numberOfRelations);
+
+ int id = 0b1;
+ int fieldOffset = 0;
+ for (RelNode input : multiJoinRel.getInputs()) {
+ TargetMapping mapping = Mappings.offsetSource(
+ Mappings.createIdentity(input.getRowType().getFieldCount()),
+ fieldOffset,
+ multiJoin.getNumTotalFields()
+ );
+
+ bestPlan.put(id, new Vertex(id, mq.getRowCount(input), input, mapping));
+ connections.set(id);
+
+ id <<= 1;
+ fieldOffset += input.getRowType().getFieldCount();
+ }
+
+ Vertex bestSoFar = null;
+ for (int s = 0b11; s < 1 << numberOfRelations; s++) {
Review Comment:
could you suggest the name for the new constant then? Also, should we introduce constant for `1` and `null`?
--
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-unsubscribe@ignite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] IGNITE-24167 Sql. Introduce heuristics to optimize join order [ignite-3]
Posted by "korlov42 (via GitHub)" <gi...@apache.org>.
korlov42 commented on code in PR #5026:
URL: https://github.com/apache/ignite-3/pull/5026#discussion_r1913310624
##########
modules/sql-engine/src/test/resources/mapping/test_backup_mapping.test:
##########
Review Comment:
good catch, thanks! Reverted
--
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-unsubscribe@ignite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] IGNITE-24167 Sql. Introduce heuristics to optimize join order [ignite-3]
Posted by "ygerzhedovich (via GitHub)" <gi...@apache.org>.
ygerzhedovich commented on code in PR #5026:
URL: https://github.com/apache/ignite-3/pull/5026#discussion_r1916444577
##########
modules/sql-engine/src/main/java/org/apache/ignite/internal/sql/engine/rule/logical/IgniteMultiJoinOptimizeBushyRule.java:
##########
@@ -0,0 +1,453 @@
+/*
+ * 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.sql.engine.rule.logical;
+
+import static java.lang.Integer.bitCount;
+import static org.apache.ignite.internal.util.IgniteUtils.isPow2;
+
+import it.unimi.dsi.fastutil.ints.Int2ObjectMap;
+import it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap;
+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.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.immutables.value.Value;
+import org.jetbrains.annotations.Nullable;
+
+/**
+ * Transformation rule used for optimizing multi-join queries using a bushy join tree strategy.
+ *
+ * <p>This is an implementation of subset-driven enumeration algorithm (Inspired by G. Moerkotte and T. Neumann.
+ * Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join
+ * Trees without Cross Products. 2.2 Subset-Driven Enumeration). The main loop enumerates all subsets of relations
+ * in a way suitable for dynamic programming: it guarantees, that for every emitted set {@code S}, any split of the
+ * {@code S} will produce subsets which have been already processed:
+ * <pre>
+ * For example, for join of 4 relations it will produce following sequence:
+ * 0011
+ * 0101
+ * 0110
+ * ...
+ * 1101
+ * 1110
+ * 1111
+ * </pre>
+ *
+ * <p>The inner while-loop enumerates all possible splits of given subset {@code S} on disjoint subset
+ * {@code lhs} and {@code rhs} such that {@code lhs ∪ rhs = S} (Inspired by B. Vance and D. Maier.
+ * Rapid bushy join-order optimization with cartesian products).
+ *
+ * <p>Finally, if the initial set of relations is not connected, the algorithm composes cartesian join
+ * from best plans, until all relations are joined.
+ *
+ * <p>Current limitations are as follow:<ol>
+ * <li>Only INNER joins are supported</li>
+ * <li>Number of relations to optimize is limited to 20. This is due to time and memory complexity of algorithm chosen.</li>
+ * <li>Disjunctive predicate is not considered as connections.</li>
+ * </ol>
+ */
+@Value.Enclosing
+public class IgniteMultiJoinOptimizeBushyRule
+ extends RelRule<IgniteMultiJoinOptimizeBushyRule.Config>
+ implements TransformationRule {
+
+ private static final int MAX_JOIN_SIZE = 20;
+
+ /**
+ * Comparator that puts better vertexes first.
+ *
+ * <p>Better vertex is the one that incorporate more relations, or costs less.
+ */
+ private static final Comparator<Vertex> VERTEX_COMPARATOR =
+ Comparator.<Vertex>comparingInt(v -> bitCount(v.id))
+ .reversed()
+ .thenComparingDouble(v -> v.cost);
+
+ /** Creates a MultiJoinOptimizeBushyRule. */
+ private IgniteMultiJoinOptimizeBushyRule(Config config) {
+ super(config);
+ }
+
+ @Override
+ public void onMatch(RelOptRuleCall call) {
+ MultiJoin multiJoinRel = call.rel(0);
+
+ int numberOfRelations = multiJoinRel.getInputs().size();
+ if (numberOfRelations > MAX_JOIN_SIZE) {
+ return;
+ }
+
+ // Currently, algorithm below can handle only INNER JOINs
+ if (multiJoinRel.isFullOuterJoin()) {
+ 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 mq = call.getMetadataQuery();
+
+ List<RexNode> unusedConditions = new ArrayList<>();
+
+ Int2ObjectMap<List<Edge>> edges = collectEdges(multiJoin, unusedConditions);
+ Int2ObjectMap<Vertex> bestPlan = new Int2ObjectOpenHashMap<>();
+ BitSet connections = new BitSet(1 << numberOfRelations);
+
+ int id = 0b1;
+ int fieldOffset = 0;
+ for (RelNode input : multiJoinRel.getInputs()) {
+ TargetMapping mapping = Mappings.offsetSource(
+ Mappings.createIdentity(input.getRowType().getFieldCount()),
+ fieldOffset,
+ multiJoin.getNumTotalFields()
+ );
+
+ bestPlan.put(id, new Vertex(id, mq.getRowCount(input), input, mapping));
+ connections.set(id);
+
+ id <<= 1;
+ fieldOffset += input.getRowType().getFieldCount();
+ }
+
+ Vertex bestSoFar = null;
+ for (int s = 0b11; s < 1 << numberOfRelations; s++) {
Review Comment:
Magic numbers are often self-explanatory, however, best practices are introducing constants for them
--
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-unsubscribe@ignite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] IGNITE-24167 Sql. Introduce heuristics to optimize join order [ignite-3]
Posted by "korlov42 (via GitHub)" <gi...@apache.org>.
korlov42 commented on code in PR #5026:
URL: https://github.com/apache/ignite-3/pull/5026#discussion_r1916648666
##########
modules/sql-engine/src/main/java/org/apache/ignite/internal/sql/engine/rule/logical/IgniteMultiJoinOptimizeBushyRule.java:
##########
@@ -0,0 +1,453 @@
+/*
+ * 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.sql.engine.rule.logical;
+
+import static java.lang.Integer.bitCount;
+import static org.apache.ignite.internal.util.IgniteUtils.isPow2;
+
+import it.unimi.dsi.fastutil.ints.Int2ObjectMap;
+import it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap;
+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.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.immutables.value.Value;
+import org.jetbrains.annotations.Nullable;
+
+/**
+ * Transformation rule used for optimizing multi-join queries using a bushy join tree strategy.
+ *
+ * <p>This is an implementation of subset-driven enumeration algorithm (Inspired by G. Moerkotte and T. Neumann.
+ * Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join
+ * Trees without Cross Products. 2.2 Subset-Driven Enumeration). The main loop enumerates all subsets of relations
+ * in a way suitable for dynamic programming: it guarantees, that for every emitted set {@code S}, any split of the
+ * {@code S} will produce subsets which have been already processed:
+ * <pre>
+ * For example, for join of 4 relations it will produce following sequence:
+ * 0011
+ * 0101
+ * 0110
+ * ...
+ * 1101
+ * 1110
+ * 1111
+ * </pre>
+ *
+ * <p>The inner while-loop enumerates all possible splits of given subset {@code S} on disjoint subset
+ * {@code lhs} and {@code rhs} such that {@code lhs ∪ rhs = S} (Inspired by B. Vance and D. Maier.
+ * Rapid bushy join-order optimization with cartesian products).
+ *
+ * <p>Finally, if the initial set of relations is not connected, the algorithm composes cartesian join
+ * from best plans, until all relations are joined.
+ *
+ * <p>Current limitations are as follow:<ol>
+ * <li>Only INNER joins are supported</li>
+ * <li>Number of relations to optimize is limited to 20. This is due to time and memory complexity of algorithm chosen.</li>
+ * <li>Disjunctive predicate is not considered as connections.</li>
+ * </ol>
+ */
+@Value.Enclosing
+public class IgniteMultiJoinOptimizeBushyRule
+ extends RelRule<IgniteMultiJoinOptimizeBushyRule.Config>
+ implements TransformationRule {
+
+ private static final int MAX_JOIN_SIZE = 20;
+
+ /**
+ * Comparator that puts better vertexes first.
+ *
+ * <p>Better vertex is the one that incorporate more relations, or costs less.
+ */
+ private static final Comparator<Vertex> VERTEX_COMPARATOR =
+ Comparator.<Vertex>comparingInt(v -> bitCount(v.id))
+ .reversed()
+ .thenComparingDouble(v -> v.cost);
+
+ /** Creates a MultiJoinOptimizeBushyRule. */
+ private IgniteMultiJoinOptimizeBushyRule(Config config) {
+ super(config);
+ }
+
+ @Override
+ public void onMatch(RelOptRuleCall call) {
+ MultiJoin multiJoinRel = call.rel(0);
+
+ int numberOfRelations = multiJoinRel.getInputs().size();
+ if (numberOfRelations > MAX_JOIN_SIZE) {
+ return;
+ }
+
+ // Currently, algorithm below can handle only INNER JOINs
+ if (multiJoinRel.isFullOuterJoin()) {
+ 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 mq = call.getMetadataQuery();
+
+ List<RexNode> unusedConditions = new ArrayList<>();
+
+ Int2ObjectMap<List<Edge>> edges = collectEdges(multiJoin, unusedConditions);
+ Int2ObjectMap<Vertex> bestPlan = new Int2ObjectOpenHashMap<>();
+ BitSet connections = new BitSet(1 << numberOfRelations);
+
+ int id = 0b1;
+ int fieldOffset = 0;
+ for (RelNode input : multiJoinRel.getInputs()) {
+ TargetMapping mapping = Mappings.offsetSource(
+ Mappings.createIdentity(input.getRowType().getFieldCount()),
+ fieldOffset,
+ multiJoin.getNumTotalFields()
+ );
+
+ bestPlan.put(id, new Vertex(id, mq.getRowCount(input), input, mapping));
+ connections.set(id);
+
+ id <<= 1;
+ fieldOffset += input.getRowType().getFieldCount();
+ }
+
+ Vertex bestSoFar = null;
+ for (int s = 0b11; s < 1 << numberOfRelations; s++) {
Review Comment:
`MIN_SUBSET` what does it mean? If you refer to the size of subset, then it's not quite correct, because there are several options for subset of size 2: 0b11, 0b101, 0b110, , 0b1010, etc. The crucial part is that we use two least significant bits here
--
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-unsubscribe@ignite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] IGNITE-24167 Sql. Introduce heuristics to optimize join order [ignite-3]
Posted by "korlov42 (via GitHub)" <gi...@apache.org>.
korlov42 commented on code in PR #5026:
URL: https://github.com/apache/ignite-3/pull/5026#discussion_r1914785799
##########
modules/sql-engine/src/main/java/org/apache/ignite/internal/sql/engine/rule/logical/IgniteMultiJoinOptimizeBushyRule.java:
##########
@@ -0,0 +1,425 @@
+/*
+ * 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.sql.engine.rule.logical;
+
+import static java.lang.Integer.bitCount;
+
+import it.unimi.dsi.fastutil.ints.Int2ObjectMap;
+import it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap;
+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.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.immutables.value.Value;
+import org.jetbrains.annotations.Nullable;
+
+/**
+ * Transformation rule used for optimizing multi-join queries using a bushy join tree strategy.
+ *
+ * <p>This is an implementation of subset-driven enumeration algorithm. The main loop (which actually consists
+ * of two for-loop) enumerates all subset of relations in a way suitable for dynamic programming: it guarantees,
+ * that for every set {@code S}, any split of the S will produce subsets which have been already processed:
+ * <pre>
+ * For example, for join of 4 relations it will produce following sequence:
+ * 0011
+ * 0101
+ * 0110
+ * ...
+ * 1101
+ * 1110
+ * 1111
+ * </pre>
+ *
+ * <p>The inner while-loop enumerates all possible splits of given subset {@code S} on disjoint subset
+ * {@code lhs} and {@code rhs} such that {@code lhs ∪ rhs = S}.
+ *
+ * <p>Finally, if the initial set of relations is not connected, the algorithm composes cartesian join
+ * from best plans, until all relations are joined.
+ *
+ * <p>Current limitations are as follow:<ol>
+ * <li>Only INNER joins are supported</li>
+ * <li>Number of relations to optimize is limited to 20. This is due to time and memory complexity of algorithm chosen.</li>
+ * <li>Disjunctive predicate is not considered as connections.</li>
+ * </ol>
+ */
+@Value.Enclosing
+public class IgniteMultiJoinOptimizeBushyRule
+ extends RelRule<IgniteMultiJoinOptimizeBushyRule.Config>
+ implements TransformationRule {
+
+ private static final int MAX_JOIN_SIZE = 20;
+
+ /**
+ * Comparator that puts better vertexes first.
+ *
+ * <p>Better vertex is the one that incorporate more relations, or costs less.
+ */
+ private static final Comparator<Vertex> VERTEX_COMPARATOR =
+ Comparator.<Vertex>comparingInt(v -> bitCount(v.id))
+ .reversed()
+ .thenComparingDouble(v -> v.cost);
+
+ /** Creates a MultiJoinOptimizeBushyRule. */
+ private IgniteMultiJoinOptimizeBushyRule(Config config) {
+ super(config);
+ }
+
+ @Override
+ public void onMatch(RelOptRuleCall call) {
+ MultiJoin multiJoinRel = call.rel(0);
+
+ int numberOfRelations = multiJoinRel.getInputs().size();
+ if (numberOfRelations > MAX_JOIN_SIZE) {
+ return;
+ }
+
+ // Currently, algorithm below can handle only INNER JOINs
+ if (multiJoinRel.isFullOuterJoin()) {
+ 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 mq = call.getMetadataQuery();
+
+ Set<RexNode> unusedConditions = Collections.newSetFromMap(new IdentityHashMap<>());
+ unusedConditions.addAll(multiJoin.getJoinFilters());
+
+ Int2ObjectMap<List<Edge>> edges = collectEdges(multiJoin, unusedConditions);
+ Int2ObjectMap<Vertex> bestPlan = new Int2ObjectOpenHashMap<>();
+ BitSet connections = new BitSet(1 << numberOfRelations);
+
+ int id = 0b1;
+ int fieldOffset = 0;
+ for (RelNode input : multiJoinRel.getInputs()) {
+ TargetMapping mapping = Mappings.offsetSource(
+ Mappings.createIdentity(input.getRowType().getFieldCount()),
+ fieldOffset,
+ multiJoin.getNumTotalFields()
+ );
+
+ bestPlan.put(id, new Vertex(id, mq.getRowCount(input), input, mapping));
+ connections.set(id);
+
+ id <<= 1;
+ fieldOffset += input.getRowType().getFieldCount();
+ }
+
+ Vertex bestSoFar = null;
+ for (int k = 2; k <= numberOfRelations; k++) {
+ for (int s = (1 << (k - 1)) + 1; s < 1 << k; s++) {
+ int lhs = Integer.lowestOneBit(s);
+ while (lhs < (s / 2) + 1) {
+ int rhs = s - lhs;
+
+ List<Edge> edges0;
+ if (connections.get(lhs) && connections.get(rhs)) {
+ edges0 = findEdges(lhs, rhs, edges);
+ } else {
+ edges0 = List.of();
+ }
+
+ if (!edges0.isEmpty()) {
+ connections.set(s);
+
+ Vertex planLhs = bestPlan.get(lhs);
+ Vertex planRhs = bestPlan.get(rhs);
+
+ Vertex newPlan = createJoin(planLhs, planRhs, edges0, mq, relBuilder, rexBuilder);
+ Vertex currentBest = bestPlan.get(s);
+ if (currentBest == null || currentBest.cost > newPlan.cost) {
+ bestPlan.put(s, newPlan);
+
+ bestSoFar = chooseBest(bestSoFar, newPlan);
+ }
+
+ aggregateEdges(edges, lhs, rhs);
+ }
+
+ lhs = s & (lhs - s);
+ }
+ }
+ }
+
+ Vertex best;
+ if (bestSoFar == null || bestSoFar.id != (1 << numberOfRelations) - 1) {
+ best = composeCartesianJoin(bestPlan, edges, bestSoFar, mq, relBuilder, rexBuilder);
+ } else {
+ best = bestSoFar;
+ }
+
+ RelNode result = relBuilder
+ .push(best.rel)
+ .filter(RexUtil.composeConjunction(rexBuilder, unusedConditions)
+ .accept(new RexPermuteInputsShuttle(best.mapping, best.rel)))
+ .project(relBuilder.fields(best.mapping))
+ .build();
+
+ call.transformTo(result);
+ }
+
+ private static void aggregateEdges(Int2ObjectMap<List<Edge>> edges, int lhs, int rhs) {
+ int id = lhs | rhs;
+ if (!edges.containsKey(id)) {
+ Set<Edge> union = Collections.newSetFromMap(new IdentityHashMap<>());
+
+ union.addAll(edges.getOrDefault(lhs, List.of()));
+ union.addAll(edges.getOrDefault(rhs, List.of()));
+
+ edges.put(id, List.copyOf(union));
+ }
+ }
+
+ private static Vertex composeCartesianJoin(
+ Int2ObjectMap<Vertex> bestPlan,
+ Int2ObjectMap<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()) {
+ 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);
+ }
+
+ return bestSoFar;
+ }
+
+ private static Vertex chooseBest(@Nullable Vertex currentBest, Vertex candidate) {
+ if (currentBest == null) {
+ return candidate;
+ }
+
+ if (VERTEX_COMPARATOR.compare(currentBest, candidate) > 0) {
+ return candidate;
+ }
+
+ return currentBest;
+ }
+
+ private static Int2ObjectMap<List<Edge>> collectEdges(LoptMultiJoin multiJoin, Set<RexNode> unusedConditions) {
+ Int2ObjectMap<List<Edge>> edges = new Int2ObjectOpenHashMap<>();
+
+ for (RexNode condition : multiJoin.getJoinFilters()) {
+ int[] inputRefs = multiJoin.getFactorsRefByJoinFilter(condition).toArray();
+
+ if (inputRefs.length < 2 || condition.isA(SqlKind.OR)) {
+ continue;
+ }
+
+ unusedConditions.remove(condition);
Review Comment:
good point! Fixed
--
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-unsubscribe@ignite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] IGNITE-24167 Sql. Introduce heuristics to optimize join order [ignite-3]
Posted by "korlov42 (via GitHub)" <gi...@apache.org>.
korlov42 commented on code in PR #5026:
URL: https://github.com/apache/ignite-3/pull/5026#discussion_r1913310065
##########
modules/sql-engine/src/test/java/org/apache/ignite/internal/sql/engine/planner/TpchQueryPlannerTest.java:
##########
@@ -17,75 +17,44 @@
package org.apache.ignite.internal.sql.engine.planner;
-import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.apache.ignite.internal.sql.engine.planner.AbstractTpcQueryPlannerTest.TpcSuiteInfo;
-import com.google.common.io.CharStreams;
-import java.io.IOException;
-import java.io.InputStream;
-import java.io.InputStreamReader;
-import java.io.UncheckedIOException;
-import java.nio.charset.StandardCharsets;
-import org.apache.calcite.plan.RelOptUtil;
-import org.apache.calcite.sql.SqlExplainLevel;
-import org.apache.ignite.internal.sql.engine.framework.TestBuilders;
-import org.apache.ignite.internal.sql.engine.framework.TestCluster;
-import org.apache.ignite.internal.sql.engine.framework.TestNode;
-import org.apache.ignite.internal.sql.engine.prepare.MultiStepPlan;
-import org.apache.ignite.internal.sql.engine.util.Cloner;
-import org.apache.ignite.internal.sql.engine.util.Commons;
import org.apache.ignite.internal.sql.engine.util.tpch.TpchHelper;
import org.apache.ignite.internal.sql.engine.util.tpch.TpchTables;
-import org.junit.jupiter.api.AfterAll;
-import org.junit.jupiter.api.BeforeAll;
-import org.junit.jupiter.api.Test;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.ValueSource;
/**
* Tests ensures a planner generates optimal plan for TPC-H queries.
*
* @see org.apache.ignite.internal.sql.engine.benchmarks.TpchParseBenchmark
*/
// TODO https://issues.apache.org/jira/browse/IGNITE-21986 validate other query plans and make test parameterized.
-public class TpchQueryPlannerTest extends AbstractPlannerTest {
- private static TestCluster CLUSTER;
-
- @BeforeAll
- static void startCluster() {
- CLUSTER = TestBuilders.cluster().nodes("N1").build();
- CLUSTER.start();
-
- TestNode node = CLUSTER.node("N1");
-
- node.initSchema(TpchTables.LINEITEM.ddlScript());
+@TpcSuiteInfo(
+ tables = TpchTables.class,
+ queryLoader = "getQueryString",
+ planLoader = "getQueryPlan"
+)
+public class TpchQueryPlannerTest extends AbstractTpcQueryPlannerTest {
+ @ParameterizedTest
+ // Query #7 contains disjunctive predicate that switches its part from run to run, making
Review Comment:
https://issues.apache.org/jira/browse/IGNITE-24195
--
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-unsubscribe@ignite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] IGNITE-24167 Sql. Introduce heuristics to optimize join order [ignite-3]
Posted by "ygerzhedovich (via GitHub)" <gi...@apache.org>.
ygerzhedovich commented on code in PR #5026:
URL: https://github.com/apache/ignite-3/pull/5026#discussion_r1916640267
##########
modules/sql-engine/src/main/java/org/apache/ignite/internal/sql/engine/rule/logical/IgniteMultiJoinOptimizeBushyRule.java:
##########
@@ -0,0 +1,453 @@
+/*
+ * 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.sql.engine.rule.logical;
+
+import static java.lang.Integer.bitCount;
+import static org.apache.ignite.internal.util.IgniteUtils.isPow2;
+
+import it.unimi.dsi.fastutil.ints.Int2ObjectMap;
+import it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap;
+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.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.immutables.value.Value;
+import org.jetbrains.annotations.Nullable;
+
+/**
+ * Transformation rule used for optimizing multi-join queries using a bushy join tree strategy.
+ *
+ * <p>This is an implementation of subset-driven enumeration algorithm (Inspired by G. Moerkotte and T. Neumann.
+ * Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join
+ * Trees without Cross Products. 2.2 Subset-Driven Enumeration). The main loop enumerates all subsets of relations
+ * in a way suitable for dynamic programming: it guarantees, that for every emitted set {@code S}, any split of the
+ * {@code S} will produce subsets which have been already processed:
+ * <pre>
+ * For example, for join of 4 relations it will produce following sequence:
+ * 0011
+ * 0101
+ * 0110
+ * ...
+ * 1101
+ * 1110
+ * 1111
+ * </pre>
+ *
+ * <p>The inner while-loop enumerates all possible splits of given subset {@code S} on disjoint subset
+ * {@code lhs} and {@code rhs} such that {@code lhs ∪ rhs = S} (Inspired by B. Vance and D. Maier.
+ * Rapid bushy join-order optimization with cartesian products).
+ *
+ * <p>Finally, if the initial set of relations is not connected, the algorithm composes cartesian join
+ * from best plans, until all relations are joined.
+ *
+ * <p>Current limitations are as follow:<ol>
+ * <li>Only INNER joins are supported</li>
+ * <li>Number of relations to optimize is limited to 20. This is due to time and memory complexity of algorithm chosen.</li>
+ * <li>Disjunctive predicate is not considered as connections.</li>
+ * </ol>
+ */
+@Value.Enclosing
+public class IgniteMultiJoinOptimizeBushyRule
+ extends RelRule<IgniteMultiJoinOptimizeBushyRule.Config>
+ implements TransformationRule {
+
+ private static final int MAX_JOIN_SIZE = 20;
+
+ /**
+ * Comparator that puts better vertexes first.
+ *
+ * <p>Better vertex is the one that incorporate more relations, or costs less.
+ */
+ private static final Comparator<Vertex> VERTEX_COMPARATOR =
+ Comparator.<Vertex>comparingInt(v -> bitCount(v.id))
+ .reversed()
+ .thenComparingDouble(v -> v.cost);
+
+ /** Creates a MultiJoinOptimizeBushyRule. */
+ private IgniteMultiJoinOptimizeBushyRule(Config config) {
+ super(config);
+ }
+
+ @Override
+ public void onMatch(RelOptRuleCall call) {
+ MultiJoin multiJoinRel = call.rel(0);
+
+ int numberOfRelations = multiJoinRel.getInputs().size();
+ if (numberOfRelations > MAX_JOIN_SIZE) {
+ return;
+ }
+
+ // Currently, algorithm below can handle only INNER JOINs
+ if (multiJoinRel.isFullOuterJoin()) {
+ 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 mq = call.getMetadataQuery();
+
+ List<RexNode> unusedConditions = new ArrayList<>();
+
+ Int2ObjectMap<List<Edge>> edges = collectEdges(multiJoin, unusedConditions);
+ Int2ObjectMap<Vertex> bestPlan = new Int2ObjectOpenHashMap<>();
+ BitSet connections = new BitSet(1 << numberOfRelations);
+
+ int id = 0b1;
+ int fieldOffset = 0;
+ for (RelNode input : multiJoinRel.getInputs()) {
+ TargetMapping mapping = Mappings.offsetSource(
+ Mappings.createIdentity(input.getRowType().getFieldCount()),
+ fieldOffset,
+ multiJoin.getNumTotalFields()
+ );
+
+ bestPlan.put(id, new Vertex(id, mq.getRowCount(input), input, mapping));
+ connections.set(id);
+
+ id <<= 1;
+ fieldOffset += input.getRowType().getFieldCount();
+ }
+
+ Vertex bestSoFar = null;
+ for (int s = 0b11; s < 1 << numberOfRelations; s++) {
Review Comment:
MIN_SUBSET_RELATIONS ?
--
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-unsubscribe@ignite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] IGNITE-24167 Sql. Introduce heuristics to optimize join order [ignite-3]
Posted by "AMashenkov (via GitHub)" <gi...@apache.org>.
AMashenkov commented on code in PR #5026:
URL: https://github.com/apache/ignite-3/pull/5026#discussion_r1913138492
##########
modules/sql-engine/src/test/resources/mapping/table_identity.test:
##########
@@ -4,29 +4,30 @@ SELECT * FROM nt1_n1, nt2_n2
Fragment#0 root
executionNodes: [N0]
remoteFragments: [1, 2]
- exchangeSourceNodes: {1=[N1], 2=[N2]}
+ exchangeSourceNodes: {1=[N2], 2=[N1]}
tree:
- NestedLoopJoin
- Receiver(sourceFragment=1, exchange=1, distribution=single)
- Receiver(sourceFragment=2, exchange=2, distribution=single)
+ Project
Review Comment:
This project is a result of changing tables join order.
Seems, it can be pushed into join operator at execution phase.
--
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-unsubscribe@ignite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] IGNITE-24167 Sql. Introduce heuristics to optimize join order [ignite-3]
Posted by "AMashenkov (via GitHub)" <gi...@apache.org>.
AMashenkov commented on code in PR #5026:
URL: https://github.com/apache/ignite-3/pull/5026#discussion_r1914697447
##########
modules/sql-engine/src/main/java/org/apache/ignite/internal/sql/engine/rule/logical/IgniteMultiJoinOptimizeBushyRule.java:
##########
@@ -0,0 +1,425 @@
+/*
+ * 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.sql.engine.rule.logical;
+
+import static java.lang.Integer.bitCount;
+
+import it.unimi.dsi.fastutil.ints.Int2ObjectMap;
+import it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap;
+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.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.immutables.value.Value;
+import org.jetbrains.annotations.Nullable;
+
+/**
+ * Transformation rule used for optimizing multi-join queries using a bushy join tree strategy.
+ *
+ * <p>This is an implementation of subset-driven enumeration algorithm. The main loop (which actually consists
+ * of two for-loop) enumerates all subset of relations in a way suitable for dynamic programming: it guarantees,
+ * that for every set {@code S}, any split of the S will produce subsets which have been already processed:
+ * <pre>
+ * For example, for join of 4 relations it will produce following sequence:
+ * 0011
+ * 0101
+ * 0110
+ * ...
+ * 1101
+ * 1110
+ * 1111
+ * </pre>
+ *
+ * <p>The inner while-loop enumerates all possible splits of given subset {@code S} on disjoint subset
+ * {@code lhs} and {@code rhs} such that {@code lhs ∪ rhs = S}.
+ *
+ * <p>Finally, if the initial set of relations is not connected, the algorithm composes cartesian join
+ * from best plans, until all relations are joined.
+ *
+ * <p>Current limitations are as follow:<ol>
+ * <li>Only INNER joins are supported</li>
+ * <li>Number of relations to optimize is limited to 20. This is due to time and memory complexity of algorithm chosen.</li>
+ * <li>Disjunctive predicate is not considered as connections.</li>
+ * </ol>
+ */
+@Value.Enclosing
+public class IgniteMultiJoinOptimizeBushyRule
+ extends RelRule<IgniteMultiJoinOptimizeBushyRule.Config>
+ implements TransformationRule {
+
+ private static final int MAX_JOIN_SIZE = 20;
+
+ /**
+ * Comparator that puts better vertexes first.
+ *
+ * <p>Better vertex is the one that incorporate more relations, or costs less.
+ */
+ private static final Comparator<Vertex> VERTEX_COMPARATOR =
+ Comparator.<Vertex>comparingInt(v -> bitCount(v.id))
+ .reversed()
+ .thenComparingDouble(v -> v.cost);
+
+ /** Creates a MultiJoinOptimizeBushyRule. */
+ private IgniteMultiJoinOptimizeBushyRule(Config config) {
+ super(config);
+ }
+
+ @Override
+ public void onMatch(RelOptRuleCall call) {
+ MultiJoin multiJoinRel = call.rel(0);
+
+ int numberOfRelations = multiJoinRel.getInputs().size();
+ if (numberOfRelations > MAX_JOIN_SIZE) {
+ return;
+ }
+
+ // Currently, algorithm below can handle only INNER JOINs
+ if (multiJoinRel.isFullOuterJoin()) {
+ 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 mq = call.getMetadataQuery();
+
+ Set<RexNode> unusedConditions = Collections.newSetFromMap(new IdentityHashMap<>());
+ unusedConditions.addAll(multiJoin.getJoinFilters());
+
+ Int2ObjectMap<List<Edge>> edges = collectEdges(multiJoin, unusedConditions);
+ Int2ObjectMap<Vertex> bestPlan = new Int2ObjectOpenHashMap<>();
+ BitSet connections = new BitSet(1 << numberOfRelations);
+
+ int id = 0b1;
+ int fieldOffset = 0;
+ for (RelNode input : multiJoinRel.getInputs()) {
+ TargetMapping mapping = Mappings.offsetSource(
+ Mappings.createIdentity(input.getRowType().getFieldCount()),
+ fieldOffset,
+ multiJoin.getNumTotalFields()
+ );
+
+ bestPlan.put(id, new Vertex(id, mq.getRowCount(input), input, mapping));
+ connections.set(id);
+
+ id <<= 1;
+ fieldOffset += input.getRowType().getFieldCount();
+ }
+
+ Vertex bestSoFar = null;
+ for (int k = 2; k <= numberOfRelations; k++) {
+ for (int s = (1 << (k - 1)) + 1; s < 1 << k; s++) {
+ int lhs = Integer.lowestOneBit(s);
+ while (lhs < (s / 2) + 1) {
+ int rhs = s - lhs;
+
+ List<Edge> edges0;
+ if (connections.get(lhs) && connections.get(rhs)) {
+ edges0 = findEdges(lhs, rhs, edges);
+ } else {
+ edges0 = List.of();
+ }
+
+ if (!edges0.isEmpty()) {
+ connections.set(s);
+
+ Vertex planLhs = bestPlan.get(lhs);
+ Vertex planRhs = bestPlan.get(rhs);
+
+ Vertex newPlan = createJoin(planLhs, planRhs, edges0, mq, relBuilder, rexBuilder);
+ Vertex currentBest = bestPlan.get(s);
+ if (currentBest == null || currentBest.cost > newPlan.cost) {
+ bestPlan.put(s, newPlan);
+
+ bestSoFar = chooseBest(bestSoFar, newPlan);
+ }
+
+ aggregateEdges(edges, lhs, rhs);
+ }
+
+ lhs = s & (lhs - s);
+ }
+ }
+ }
+
+ Vertex best;
+ if (bestSoFar == null || bestSoFar.id != (1 << numberOfRelations) - 1) {
+ best = composeCartesianJoin(bestPlan, edges, bestSoFar, mq, relBuilder, rexBuilder);
+ } else {
+ best = bestSoFar;
+ }
+
+ RelNode result = relBuilder
+ .push(best.rel)
+ .filter(RexUtil.composeConjunction(rexBuilder, unusedConditions)
+ .accept(new RexPermuteInputsShuttle(best.mapping, best.rel)))
+ .project(relBuilder.fields(best.mapping))
+ .build();
+
+ call.transformTo(result);
+ }
+
+ private static void aggregateEdges(Int2ObjectMap<List<Edge>> edges, int lhs, int rhs) {
+ int id = lhs | rhs;
+ if (!edges.containsKey(id)) {
+ Set<Edge> union = Collections.newSetFromMap(new IdentityHashMap<>());
+
+ union.addAll(edges.getOrDefault(lhs, List.of()));
+ union.addAll(edges.getOrDefault(rhs, List.of()));
+
+ edges.put(id, List.copyOf(union));
+ }
+ }
+
+ private static Vertex composeCartesianJoin(
+ Int2ObjectMap<Vertex> bestPlan,
+ Int2ObjectMap<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()) {
+ 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);
+ }
+
+ return bestSoFar;
+ }
+
+ private static Vertex chooseBest(@Nullable Vertex currentBest, Vertex candidate) {
+ if (currentBest == null) {
+ return candidate;
+ }
+
+ if (VERTEX_COMPARATOR.compare(currentBest, candidate) > 0) {
+ return candidate;
+ }
+
+ return currentBest;
+ }
+
+ private static Int2ObjectMap<List<Edge>> collectEdges(LoptMultiJoin multiJoin, Set<RexNode> unusedConditions) {
+ Int2ObjectMap<List<Edge>> edges = new Int2ObjectOpenHashMap<>();
+
+ for (RexNode condition : multiJoin.getJoinFilters()) {
+ int[] inputRefs = multiJoin.getFactorsRefByJoinFilter(condition).toArray();
+
+ if (inputRefs.length < 2 || condition.isA(SqlKind.OR)) {
+ continue;
+ }
+
+ unusedConditions.remove(condition);
Review Comment:
We can fill `unusedConditions` inside the `if-block` instead of removing them.
This will avoid one iteration over join filter, lookups into hashes, and Set can be replaced with a list.
--
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-unsubscribe@ignite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] IGNITE-24167 Sql. Introduce heuristics to optimize join order [ignite-3]
Posted by "korlov42 (via GitHub)" <gi...@apache.org>.
korlov42 merged PR #5026:
URL: https://github.com/apache/ignite-3/pull/5026
--
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-unsubscribe@ignite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] IGNITE-24167 Sql. Introduce heuristics to optimize join order [ignite-3]
Posted by "AMashenkov (via GitHub)" <gi...@apache.org>.
AMashenkov commented on code in PR #5026:
URL: https://github.com/apache/ignite-3/pull/5026#discussion_r1913130708
##########
modules/sql-engine/src/test/java/org/apache/ignite/internal/sql/engine/planner/TpchQueryPlannerTest.java:
##########
@@ -17,75 +17,44 @@
package org.apache.ignite.internal.sql.engine.planner;
-import static org.junit.jupiter.api.Assertions.assertEquals;
+import static org.apache.ignite.internal.sql.engine.planner.AbstractTpcQueryPlannerTest.TpcSuiteInfo;
-import com.google.common.io.CharStreams;
-import java.io.IOException;
-import java.io.InputStream;
-import java.io.InputStreamReader;
-import java.io.UncheckedIOException;
-import java.nio.charset.StandardCharsets;
-import org.apache.calcite.plan.RelOptUtil;
-import org.apache.calcite.sql.SqlExplainLevel;
-import org.apache.ignite.internal.sql.engine.framework.TestBuilders;
-import org.apache.ignite.internal.sql.engine.framework.TestCluster;
-import org.apache.ignite.internal.sql.engine.framework.TestNode;
-import org.apache.ignite.internal.sql.engine.prepare.MultiStepPlan;
-import org.apache.ignite.internal.sql.engine.util.Cloner;
-import org.apache.ignite.internal.sql.engine.util.Commons;
import org.apache.ignite.internal.sql.engine.util.tpch.TpchHelper;
import org.apache.ignite.internal.sql.engine.util.tpch.TpchTables;
-import org.junit.jupiter.api.AfterAll;
-import org.junit.jupiter.api.BeforeAll;
-import org.junit.jupiter.api.Test;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.ValueSource;
/**
* Tests ensures a planner generates optimal plan for TPC-H queries.
*
* @see org.apache.ignite.internal.sql.engine.benchmarks.TpchParseBenchmark
*/
// TODO https://issues.apache.org/jira/browse/IGNITE-21986 validate other query plans and make test parameterized.
-public class TpchQueryPlannerTest extends AbstractPlannerTest {
- private static TestCluster CLUSTER;
-
- @BeforeAll
- static void startCluster() {
- CLUSTER = TestBuilders.cluster().nodes("N1").build();
- CLUSTER.start();
-
- TestNode node = CLUSTER.node("N1");
-
- node.initSchema(TpchTables.LINEITEM.ddlScript());
+@TpcSuiteInfo(
+ tables = TpchTables.class,
+ queryLoader = "getQueryString",
+ planLoader = "getQueryPlan"
+)
+public class TpchQueryPlannerTest extends AbstractTpcQueryPlannerTest {
+ @ParameterizedTest
+ // Query #7 contains disjunctive predicate that switches its part from run to run, making
Review Comment:
Discussed. We agreed the real reason is Calcite RexUtils code generates unstable conditions order.
BWT, on our side, we should use LinkedHashSet/Map to preserve stable digest/plan/toString results.
Let's create a ticket.
--
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-unsubscribe@ignite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] IGNITE-24167 Sql. Introduce heuristics to optimize join order [ignite-3]
Posted by "AMashenkov (via GitHub)" <gi...@apache.org>.
AMashenkov commented on code in PR #5026:
URL: https://github.com/apache/ignite-3/pull/5026#discussion_r1914697447
##########
modules/sql-engine/src/main/java/org/apache/ignite/internal/sql/engine/rule/logical/IgniteMultiJoinOptimizeBushyRule.java:
##########
@@ -0,0 +1,425 @@
+/*
+ * 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.sql.engine.rule.logical;
+
+import static java.lang.Integer.bitCount;
+
+import it.unimi.dsi.fastutil.ints.Int2ObjectMap;
+import it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap;
+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.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.immutables.value.Value;
+import org.jetbrains.annotations.Nullable;
+
+/**
+ * Transformation rule used for optimizing multi-join queries using a bushy join tree strategy.
+ *
+ * <p>This is an implementation of subset-driven enumeration algorithm. The main loop (which actually consists
+ * of two for-loop) enumerates all subset of relations in a way suitable for dynamic programming: it guarantees,
+ * that for every set {@code S}, any split of the S will produce subsets which have been already processed:
+ * <pre>
+ * For example, for join of 4 relations it will produce following sequence:
+ * 0011
+ * 0101
+ * 0110
+ * ...
+ * 1101
+ * 1110
+ * 1111
+ * </pre>
+ *
+ * <p>The inner while-loop enumerates all possible splits of given subset {@code S} on disjoint subset
+ * {@code lhs} and {@code rhs} such that {@code lhs ∪ rhs = S}.
+ *
+ * <p>Finally, if the initial set of relations is not connected, the algorithm composes cartesian join
+ * from best plans, until all relations are joined.
+ *
+ * <p>Current limitations are as follow:<ol>
+ * <li>Only INNER joins are supported</li>
+ * <li>Number of relations to optimize is limited to 20. This is due to time and memory complexity of algorithm chosen.</li>
+ * <li>Disjunctive predicate is not considered as connections.</li>
+ * </ol>
+ */
+@Value.Enclosing
+public class IgniteMultiJoinOptimizeBushyRule
+ extends RelRule<IgniteMultiJoinOptimizeBushyRule.Config>
+ implements TransformationRule {
+
+ private static final int MAX_JOIN_SIZE = 20;
+
+ /**
+ * Comparator that puts better vertexes first.
+ *
+ * <p>Better vertex is the one that incorporate more relations, or costs less.
+ */
+ private static final Comparator<Vertex> VERTEX_COMPARATOR =
+ Comparator.<Vertex>comparingInt(v -> bitCount(v.id))
+ .reversed()
+ .thenComparingDouble(v -> v.cost);
+
+ /** Creates a MultiJoinOptimizeBushyRule. */
+ private IgniteMultiJoinOptimizeBushyRule(Config config) {
+ super(config);
+ }
+
+ @Override
+ public void onMatch(RelOptRuleCall call) {
+ MultiJoin multiJoinRel = call.rel(0);
+
+ int numberOfRelations = multiJoinRel.getInputs().size();
+ if (numberOfRelations > MAX_JOIN_SIZE) {
+ return;
+ }
+
+ // Currently, algorithm below can handle only INNER JOINs
+ if (multiJoinRel.isFullOuterJoin()) {
+ 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 mq = call.getMetadataQuery();
+
+ Set<RexNode> unusedConditions = Collections.newSetFromMap(new IdentityHashMap<>());
+ unusedConditions.addAll(multiJoin.getJoinFilters());
+
+ Int2ObjectMap<List<Edge>> edges = collectEdges(multiJoin, unusedConditions);
+ Int2ObjectMap<Vertex> bestPlan = new Int2ObjectOpenHashMap<>();
+ BitSet connections = new BitSet(1 << numberOfRelations);
+
+ int id = 0b1;
+ int fieldOffset = 0;
+ for (RelNode input : multiJoinRel.getInputs()) {
+ TargetMapping mapping = Mappings.offsetSource(
+ Mappings.createIdentity(input.getRowType().getFieldCount()),
+ fieldOffset,
+ multiJoin.getNumTotalFields()
+ );
+
+ bestPlan.put(id, new Vertex(id, mq.getRowCount(input), input, mapping));
+ connections.set(id);
+
+ id <<= 1;
+ fieldOffset += input.getRowType().getFieldCount();
+ }
+
+ Vertex bestSoFar = null;
+ for (int k = 2; k <= numberOfRelations; k++) {
+ for (int s = (1 << (k - 1)) + 1; s < 1 << k; s++) {
+ int lhs = Integer.lowestOneBit(s);
+ while (lhs < (s / 2) + 1) {
+ int rhs = s - lhs;
+
+ List<Edge> edges0;
+ if (connections.get(lhs) && connections.get(rhs)) {
+ edges0 = findEdges(lhs, rhs, edges);
+ } else {
+ edges0 = List.of();
+ }
+
+ if (!edges0.isEmpty()) {
+ connections.set(s);
+
+ Vertex planLhs = bestPlan.get(lhs);
+ Vertex planRhs = bestPlan.get(rhs);
+
+ Vertex newPlan = createJoin(planLhs, planRhs, edges0, mq, relBuilder, rexBuilder);
+ Vertex currentBest = bestPlan.get(s);
+ if (currentBest == null || currentBest.cost > newPlan.cost) {
+ bestPlan.put(s, newPlan);
+
+ bestSoFar = chooseBest(bestSoFar, newPlan);
+ }
+
+ aggregateEdges(edges, lhs, rhs);
+ }
+
+ lhs = s & (lhs - s);
+ }
+ }
+ }
+
+ Vertex best;
+ if (bestSoFar == null || bestSoFar.id != (1 << numberOfRelations) - 1) {
+ best = composeCartesianJoin(bestPlan, edges, bestSoFar, mq, relBuilder, rexBuilder);
+ } else {
+ best = bestSoFar;
+ }
+
+ RelNode result = relBuilder
+ .push(best.rel)
+ .filter(RexUtil.composeConjunction(rexBuilder, unusedConditions)
+ .accept(new RexPermuteInputsShuttle(best.mapping, best.rel)))
+ .project(relBuilder.fields(best.mapping))
+ .build();
+
+ call.transformTo(result);
+ }
+
+ private static void aggregateEdges(Int2ObjectMap<List<Edge>> edges, int lhs, int rhs) {
+ int id = lhs | rhs;
+ if (!edges.containsKey(id)) {
+ Set<Edge> union = Collections.newSetFromMap(new IdentityHashMap<>());
+
+ union.addAll(edges.getOrDefault(lhs, List.of()));
+ union.addAll(edges.getOrDefault(rhs, List.of()));
+
+ edges.put(id, List.copyOf(union));
+ }
+ }
+
+ private static Vertex composeCartesianJoin(
+ Int2ObjectMap<Vertex> bestPlan,
+ Int2ObjectMap<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()) {
+ 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);
+ }
+
+ return bestSoFar;
+ }
+
+ private static Vertex chooseBest(@Nullable Vertex currentBest, Vertex candidate) {
+ if (currentBest == null) {
+ return candidate;
+ }
+
+ if (VERTEX_COMPARATOR.compare(currentBest, candidate) > 0) {
+ return candidate;
+ }
+
+ return currentBest;
+ }
+
+ private static Int2ObjectMap<List<Edge>> collectEdges(LoptMultiJoin multiJoin, Set<RexNode> unusedConditions) {
+ Int2ObjectMap<List<Edge>> edges = new Int2ObjectOpenHashMap<>();
+
+ for (RexNode condition : multiJoin.getJoinFilters()) {
+ int[] inputRefs = multiJoin.getFactorsRefByJoinFilter(condition).toArray();
+
+ if (inputRefs.length < 2 || condition.isA(SqlKind.OR)) {
+ continue;
+ }
+
+ unusedConditions.remove(condition);
Review Comment:
We can fill `unusedConditions` inside the `if-block` instead of removing them.
This will avoid one iteration over join filter, lookups into hasheset, and Set can be replaced with a list.
--
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-unsubscribe@ignite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] IGNITE-24167 Sql. Introduce heuristics to optimize join order [ignite-3]
Posted by "korlov42 (via GitHub)" <gi...@apache.org>.
korlov42 commented on code in PR #5026:
URL: https://github.com/apache/ignite-3/pull/5026#discussion_r1916057607
##########
modules/sql-engine/src/main/java/org/apache/ignite/internal/sql/engine/rule/logical/IgniteMultiJoinOptimizeBushyRule.java:
##########
@@ -0,0 +1,449 @@
+/*
+ * 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.sql.engine.rule.logical;
+
+import static java.lang.Integer.bitCount;
+
+import it.unimi.dsi.fastutil.ints.Int2ObjectMap;
+import it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap;
+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.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.immutables.value.Value;
+import org.jetbrains.annotations.Nullable;
+
+/**
+ * Transformation rule used for optimizing multi-join queries using a bushy join tree strategy.
+ *
+ * <p>This is an implementation of subset-driven enumeration algorithm (Inspired by G. Moerkotte and T. Neumann.
+ * Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join
+ * Trees without Cross Products. 2.2 Subset-Driven Enumeration). The main loop (which actually consists of two
+ * for-loop) enumerates all subset of relations in a way suitable for dynamic programming: it guarantees,
+ * that for every set {@code S}, any split of the S will produce subsets which have been already processed:
+ * <pre>
+ * For example, for join of 4 relations it will produce following sequence:
+ * 0011
+ * 0101
+ * 0110
+ * ...
+ * 1101
+ * 1110
+ * 1111
+ * </pre>
+ *
+ * <p>The inner while-loop enumerates all possible splits of given subset {@code S} on disjoint subset
+ * {@code lhs} and {@code rhs} such that {@code lhs ∪ rhs = S} (Inspired by B. Vance and D. Maier.
+ * Rapid bushy join-order optimization with cartesian products).
+ *
+ * <p>Finally, if the initial set of relations is not connected, the algorithm composes cartesian join
+ * from best plans, until all relations are joined.
+ *
+ * <p>Current limitations are as follow:<ol>
+ * <li>Only INNER joins are supported</li>
+ * <li>Number of relations to optimize is limited to 20. This is due to time and memory complexity of algorithm chosen.</li>
+ * <li>Disjunctive predicate is not considered as connections.</li>
+ * </ol>
+ */
+@Value.Enclosing
+public class IgniteMultiJoinOptimizeBushyRule
+ extends RelRule<IgniteMultiJoinOptimizeBushyRule.Config>
+ implements TransformationRule {
+
+ private static final int MAX_JOIN_SIZE = 20;
+
+ /**
+ * Comparator that puts better vertexes first.
+ *
+ * <p>Better vertex is the one that incorporate more relations, or costs less.
+ */
+ private static final Comparator<Vertex> VERTEX_COMPARATOR =
+ Comparator.<Vertex>comparingInt(v -> bitCount(v.id))
+ .reversed()
+ .thenComparingDouble(v -> v.cost);
+
+ /** Creates a MultiJoinOptimizeBushyRule. */
+ private IgniteMultiJoinOptimizeBushyRule(Config config) {
+ super(config);
+ }
+
+ @Override
+ public void onMatch(RelOptRuleCall call) {
+ MultiJoin multiJoinRel = call.rel(0);
+
+ int numberOfRelations = multiJoinRel.getInputs().size();
+ if (numberOfRelations > MAX_JOIN_SIZE) {
+ return;
+ }
+
+ // Currently, algorithm below can handle only INNER JOINs
+ if (multiJoinRel.isFullOuterJoin()) {
+ 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 mq = call.getMetadataQuery();
+
+ List<RexNode> unusedConditions = new ArrayList<>();
+
+ Int2ObjectMap<List<Edge>> edges = collectEdges(multiJoin, unusedConditions);
+ Int2ObjectMap<Vertex> bestPlan = new Int2ObjectOpenHashMap<>();
+ BitSet connections = new BitSet(1 << numberOfRelations);
+
+ int id = 0b1;
+ int fieldOffset = 0;
+ for (RelNode input : multiJoinRel.getInputs()) {
+ TargetMapping mapping = Mappings.offsetSource(
+ Mappings.createIdentity(input.getRowType().getFieldCount()),
+ fieldOffset,
+ multiJoin.getNumTotalFields()
+ );
+
+ bestPlan.put(id, new Vertex(id, mq.getRowCount(input), input, mapping));
+ connections.set(id);
+
+ id <<= 1;
+ fieldOffset += input.getRowType().getFieldCount();
+ }
+
+ Vertex bestSoFar = null;
+ for (int k = 2; k <= numberOfRelations; k++) {
+ for (int s = (1 << (k - 1)) + 1; s < 1 << k; s++) {
Review Comment:
Simplified this part a bit: replaced these two for-loops with single loop with condition
--
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-unsubscribe@ignite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] IGNITE-24167 Sql. Introduce heuristics to optimize join order [ignite-3]
Posted by "korlov42 (via GitHub)" <gi...@apache.org>.
korlov42 commented on code in PR #5026:
URL: https://github.com/apache/ignite-3/pull/5026#discussion_r1916057863
##########
modules/sql-engine/src/integrationTest/java/org/apache/ignite/internal/sql/engine/statistic/ItStatisticTest.java:
##########
@@ -51,7 +51,7 @@ public void testStatisticsRowCount() throws Exception {
insertAndUpdateRunQuery(500);
// Minimum row count is 1000, even we have less rows.
Review Comment:
good catch, thanks! Fixed
##########
modules/sql-engine/src/main/java/org/apache/ignite/internal/sql/engine/prepare/IgnitePlanner.java:
##########
@@ -235,6 +237,22 @@ public RelNode convert(SqlNode sql) {
throw new UnsupportedOperationException();
}
+ /** Derives hints from give relation node, if possible. */
Review Comment:
fixed, thanks
--
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-unsubscribe@ignite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] IGNITE-24167 Sql. Introduce heuristics to optimize join order [ignite-3]
Posted by "korlov42 (via GitHub)" <gi...@apache.org>.
korlov42 commented on code in PR #5026:
URL: https://github.com/apache/ignite-3/pull/5026#discussion_r1916424934
##########
modules/sql-engine/src/main/java/org/apache/ignite/internal/sql/engine/rule/logical/IgniteMultiJoinOptimizeBushyRule.java:
##########
@@ -0,0 +1,453 @@
+/*
+ * 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.sql.engine.rule.logical;
+
+import static java.lang.Integer.bitCount;
+import static org.apache.ignite.internal.util.IgniteUtils.isPow2;
+
+import it.unimi.dsi.fastutil.ints.Int2ObjectMap;
+import it.unimi.dsi.fastutil.ints.Int2ObjectOpenHashMap;
+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.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.immutables.value.Value;
+import org.jetbrains.annotations.Nullable;
+
+/**
+ * Transformation rule used for optimizing multi-join queries using a bushy join tree strategy.
+ *
+ * <p>This is an implementation of subset-driven enumeration algorithm (Inspired by G. Moerkotte and T. Neumann.
+ * Analysis of Two Existing and One New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join
+ * Trees without Cross Products. 2.2 Subset-Driven Enumeration). The main loop enumerates all subsets of relations
+ * in a way suitable for dynamic programming: it guarantees, that for every emitted set {@code S}, any split of the
+ * {@code S} will produce subsets which have been already processed:
+ * <pre>
+ * For example, for join of 4 relations it will produce following sequence:
+ * 0011
+ * 0101
+ * 0110
+ * ...
+ * 1101
+ * 1110
+ * 1111
+ * </pre>
+ *
+ * <p>The inner while-loop enumerates all possible splits of given subset {@code S} on disjoint subset
+ * {@code lhs} and {@code rhs} such that {@code lhs ∪ rhs = S} (Inspired by B. Vance and D. Maier.
+ * Rapid bushy join-order optimization with cartesian products).
+ *
+ * <p>Finally, if the initial set of relations is not connected, the algorithm composes cartesian join
+ * from best plans, until all relations are joined.
+ *
+ * <p>Current limitations are as follow:<ol>
+ * <li>Only INNER joins are supported</li>
+ * <li>Number of relations to optimize is limited to 20. This is due to time and memory complexity of algorithm chosen.</li>
+ * <li>Disjunctive predicate is not considered as connections.</li>
+ * </ol>
+ */
+@Value.Enclosing
+public class IgniteMultiJoinOptimizeBushyRule
+ extends RelRule<IgniteMultiJoinOptimizeBushyRule.Config>
+ implements TransformationRule {
+
+ private static final int MAX_JOIN_SIZE = 20;
+
+ /**
+ * Comparator that puts better vertexes first.
+ *
+ * <p>Better vertex is the one that incorporate more relations, or costs less.
+ */
+ private static final Comparator<Vertex> VERTEX_COMPARATOR =
+ Comparator.<Vertex>comparingInt(v -> bitCount(v.id))
Review Comment:
fixed, thanks
--
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-unsubscribe@ignite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org