You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@calcite.apache.org by "silundong (via GitHub)" <gi...@apache.org> on 2025/02/19 11:39:00 UTC
[PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
silundong opened a new pull request, #4204:
URL: https://github.com/apache/calcite/pull/4204
The main enumeration process of dphyp has been implemented. There are two new rules, one for converting Joins into a HyperGraph and the other for triggering the dphyp algorithm
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "rubenada (via GitHub)" <gi...@apache.org>.
rubenada commented on PR #4204:
URL: https://github.com/apache/calcite/pull/4204#issuecomment-2676989615
This is a great contribution @silundong.
Just out of curiosity, have you tested locally what happens if you add the new HyperGraph rules into the "default rules" (e.g. RelOptRules#BASE_RULES, or Programs#RULE_SET) and execute Calcite tests? Do you get any any suspicious error (except for the expected plan changes regarding Join-ordering that the new rules may generate)?
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "rubenada (via GitHub)" <gi...@apache.org>.
rubenada commented on PR #4204:
URL: https://github.com/apache/calcite/pull/4204#issuecomment-2687108194
Thanks for addressing my initial comments @silundong , I'll take another look in the coming days.
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "rubenada (via GitHub)" <gi...@apache.org>.
rubenada commented on PR #4204:
URL: https://github.com/apache/calcite/pull/4204#issuecomment-2697457694
@silundong I have left some remarks , rather generic or Calcite-related, not really dphyp-algo related, which I find I bit hard to follow, but it's good that you provided tests showing the results.
IMO we could consider adding this feature, maybe initially flagging the new classes and rule definitions as `@Experimental` (as it happened in the past with other features). Let's see what other contributors think about it...
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "rubenada (via GitHub)" <gi...@apache.org>.
rubenada commented on code in PR #4204:
URL: https://github.com/apache/calcite/pull/4204#discussion_r1979273034
##########
core/src/main/java/org/apache/calcite/rel/rules/DphypJoinReorderRule.java:
##########
@@ -0,0 +1,86 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to you under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.calcite.rel.rules;
+
+import org.apache.calcite.plan.RelOptRuleCall;
+import org.apache.calcite.plan.RelRule;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.core.Join;
+import org.apache.calcite.rex.RexBuilder;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.tools.RelBuilder;
+
+import org.immutables.value.Value;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/** Rule that re-orders a {@link Join} tree using dphyp algorithm.
+ *
+ * @see CoreRules#HYPER_GRAPH_OPTIMIZE */
+@Value.Enclosing
+public class DphypJoinReorderRule
+ extends RelRule<DphypJoinReorderRule.Config>
+ implements TransformationRule {
+
+ protected DphypJoinReorderRule(Config config) {
+ super(config);
+ }
+
+ @Override public void onMatch(RelOptRuleCall call) {
+ HyperGraph hyperGraph = call.rel(0);
+ RelBuilder relBuilder = call.builder();
+ // make all field name unique and convert the
+ // HyperEdge condition from RexInputRef to RexInputFieldName
+ hyperGraph.convertHyperEdgeCond();
Review Comment:
I think this call over here is a bit weird, what about calling this method inside the DpHyp constructor (to make sure we don't "forget" about this initialization)
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "rubenada (via GitHub)" <gi...@apache.org>.
rubenada commented on code in PR #4204:
URL: https://github.com/apache/calcite/pull/4204#discussion_r1966834279
##########
core/src/main/java/org/apache/calcite/rel/rules/CoreRules.java:
##########
@@ -816,4 +816,14 @@ private CoreRules() {}
WINDOW_REDUCE_EXPRESSIONS =
ReduceExpressionsRule.WindowReduceExpressionsRule.WindowReduceExpressionsRuleConfig
.DEFAULT.toRule();
+ /** Rule that flattens a tree of {@link LogicalJoin}s
Review Comment:
nit: for consistency, could you please keep an empty between the new rule and the previous one?
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "rubenada (via GitHub)" <gi...@apache.org>.
rubenada commented on code in PR #4204:
URL: https://github.com/apache/calcite/pull/4204#discussion_r1979269322
##########
core/src/main/java/org/apache/calcite/rel/rules/DpHyp.java:
##########
@@ -0,0 +1,181 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to you under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.calcite.rel.rules;
+
+import org.apache.calcite.plan.RelOptCost;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.core.JoinRelType;
+import org.apache.calcite.rel.metadata.RelMetadataQuery;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.tools.RelBuilder;
+
+import org.checkerframework.checker.nullness.qual.Nullable;
+
+import java.util.HashMap;
+import java.util.List;
+
+/**
+ * The core process of dphyp enumeration algorithm.
+ */
+public class DpHyp {
+
+ private HyperGraph hyperGraph;
Review Comment:
If the fields in the class (or any new class) can be final, please declare them as final.
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "rubenada (via GitHub)" <gi...@apache.org>.
rubenada commented on code in PR #4204:
URL: https://github.com/apache/calcite/pull/4204#discussion_r1979276175
##########
core/src/main/java/org/apache/calcite/rel/rules/HyperEdge.java:
##########
@@ -0,0 +1,82 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to you under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.calcite.rel.rules;
+
+import org.apache.calcite.rel.core.JoinRelType;
+import org.apache.calcite.rex.RexNode;
+
+/**
+ * Edge in HyperGraph, that represents a join predicate.
+ */
+public class HyperEdge {
+
+ private long leftNodeBits;
+
+ private long rightNodeBits;
+
+ private JoinRelType joinType;
+
+ private RexNode condition;
+
+ public HyperEdge(long leftNodeBits, long rightNodeBits, JoinRelType joinType, RexNode condition) {
+ this.leftNodeBits = leftNodeBits;
+ this.rightNodeBits = rightNodeBits;
+ this.joinType = joinType;
+ this.condition = condition;
+ }
+
+ public long getNodeBitmap() {
+ return leftNodeBits | rightNodeBits;
+ }
+
+ public long getLeftNodeBitmap() {
+ return leftNodeBits;
+ }
+
+ public long getRightNodeBitmap() {
+ return rightNodeBits;
+ }
+
+ // hyperedge (u, v) is simple if |u| = |v| = 1
+ public boolean isSimple() {
+ boolean leftSimple = (leftNodeBits & (leftNodeBits - 1)) == 0;
+ boolean rightSimple = (rightNodeBits & (rightNodeBits - 1)) == 0;
+ return leftSimple && rightSimple;
+ }
+
+ public JoinRelType getJoinType() {
+ return joinType;
+ }
+
+ public RexNode getCondition() {
+ return condition;
+ }
+
+ @Override public String toString() {
+ StringBuilder sb = new StringBuilder();
+ sb.append(LongBitmap.printBitmap(leftNodeBits))
Review Comment:
IMO the string representation should contain also the condition and the joinRelType
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "silundong (via GitHub)" <gi...@apache.org>.
silundong commented on code in PR #4204:
URL: https://github.com/apache/calcite/pull/4204#discussion_r1966971970
##########
core/src/main/java/org/apache/calcite/rel/rules/DphypJoinReorderRule.java:
##########
@@ -0,0 +1,86 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to you under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.calcite.rel.rules;
+
+import org.apache.calcite.plan.RelOptRuleCall;
+import org.apache.calcite.plan.RelRule;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.core.Join;
+import org.apache.calcite.rex.RexBuilder;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.tools.RelBuilder;
+
+import org.immutables.value.Value;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/** Rule that re-orders a {@link Join} tree using dphyp algorithm.
+ *
+ * @see CoreRules#HYPER_GRAPH_OPTIMIZE */
+@Value.Enclosing
+public class DphypJoinReorderRule
+ extends RelRule<DphypJoinReorderRule.Config>
+ implements TransformationRule {
+
+ protected DphypJoinReorderRule(Config config) {
+ super(config);
+ }
+
+ @Override public void onMatch(RelOptRuleCall call) {
+ HyperGraph hyperGraph = call.rel(0);
+ RelBuilder relBuilder = call.builder();
+ // make all field name unique and convert the
+ // HyperEdge condition from RexInputRef to RexInputFieldName
+ hyperGraph.convertHyperEdgeCond();
+
+ // enumerate by Dphyp
+ DpHyp dpHyp = new DpHyp(hyperGraph, relBuilder, call.getMetadataQuery());
+ dpHyp.startEnumerateJoin();
+ RelNode orderedJoin = dpHyp.getBestPlan();
+ if (orderedJoin == null) {
+ return;
Review Comment:
My original intention is that when the query is too complex, even dphyp can be very time-consuming. So, if the execution of `dpHyp.startEnumerateJoin` exceeds a certain time limit, the enumeration process should be forcibly terminated. In this case, the dp table may not have results yet. After returning null, the hypergraph simplification algorithm might be executed.
Alternatively, the rules related to dphyp could be integrated into a single method, with the original Join tree as the input parameter. If the optimization times out, the original Join tree is returned, and other Join reorder algorithms can be called subsequently.
Do you have any suggestions for this? I will update it accordingly.
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "silundong (via GitHub)" <gi...@apache.org>.
silundong commented on code in PR #4204:
URL: https://github.com/apache/calcite/pull/4204#discussion_r1966971970
##########
core/src/main/java/org/apache/calcite/rel/rules/DphypJoinReorderRule.java:
##########
@@ -0,0 +1,86 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to you under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.calcite.rel.rules;
+
+import org.apache.calcite.plan.RelOptRuleCall;
+import org.apache.calcite.plan.RelRule;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.core.Join;
+import org.apache.calcite.rex.RexBuilder;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.tools.RelBuilder;
+
+import org.immutables.value.Value;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/** Rule that re-orders a {@link Join} tree using dphyp algorithm.
+ *
+ * @see CoreRules#HYPER_GRAPH_OPTIMIZE */
+@Value.Enclosing
+public class DphypJoinReorderRule
+ extends RelRule<DphypJoinReorderRule.Config>
+ implements TransformationRule {
+
+ protected DphypJoinReorderRule(Config config) {
+ super(config);
+ }
+
+ @Override public void onMatch(RelOptRuleCall call) {
+ HyperGraph hyperGraph = call.rel(0);
+ RelBuilder relBuilder = call.builder();
+ // make all field name unique and convert the
+ // HyperEdge condition from RexInputRef to RexInputFieldName
+ hyperGraph.convertHyperEdgeCond();
+
+ // enumerate by Dphyp
+ DpHyp dpHyp = new DpHyp(hyperGraph, relBuilder, call.getMetadataQuery());
+ dpHyp.startEnumerateJoin();
+ RelNode orderedJoin = dpHyp.getBestPlan();
+ if (orderedJoin == null) {
+ return;
Review Comment:
My original intention is that when the query is too complex, even dphyp can be very time-consuming. So, if the execution of `dpHyp.startEnumerateJoin` exceeds a certain time limit, the enumeration process should be forcibly terminated. In this case, the dp table may not have results yet. After returning null, the hypergraph simplification algorithm might be executed.
Alternatively, the rules related to dphyp could be integrated into a single method, with the original Join tree as the input parameter. If the optimization times out, the original Join tree is returned, and other Join reorder algorithms can be called subsequently.
Do you have any suggestions for this? I will update it accordingly.
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "silundong (via GitHub)" <gi...@apache.org>.
silundong commented on PR #4204:
URL: https://github.com/apache/calcite/pull/4204#issuecomment-2699479377
> @silundong I have left some remarks , rather generic or Calcite-related, not really dphyp-algo related, which I find I bit hard to follow, but it's good that you provided tests showing the results. IMO we could consider adding this feature, maybe initially flagging the new classes and rule definitions as `@Experimental` (as it happened in the past with other features). Let's see what other contributors think about it...
Thank you very much for your suggestion, I will update 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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "rubenada (via GitHub)" <gi...@apache.org>.
rubenada commented on code in PR #4204:
URL: https://github.com/apache/calcite/pull/4204#discussion_r1979289078
##########
core/src/main/java/org/apache/calcite/rel/rules/JoinToHyperGraphRule.java:
##########
@@ -0,0 +1,192 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to you under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.calcite.rel.rules;
+
+import org.apache.calcite.plan.RelOptRuleCall;
+import org.apache.calcite.plan.RelOptUtil;
+import org.apache.calcite.plan.RelRule;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.core.Join;
+import org.apache.calcite.rel.core.JoinRelType;
+import org.apache.calcite.rel.logical.LogicalJoin;
+import org.apache.calcite.rex.RexInputRef;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.rex.RexShuttle;
+import org.apache.calcite.rex.RexVisitorImpl;
+
+import org.immutables.value.Value;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.stream.Collectors;
+
+/** Rule that flattens a tree of {@link LogicalJoin}s
+ * into a single {@link HyperGraph} with N inputs.
+ *
+ * @see CoreRules#JOIN_TO_HYPER_GRAPH
+ */
+@Value.Enclosing
+public class JoinToHyperGraphRule
+ extends RelRule<JoinToHyperGraphRule.Config>
+ implements TransformationRule {
+
+ protected JoinToHyperGraphRule(Config config) {
+ super(config);
+ }
+
+ @Override public void onMatch(RelOptRuleCall call) {
+ final Join origJoin = call.rel(0);
+ final RelNode left = call.rel(1);
+ final RelNode right = call.rel(2);
+ if (origJoin.getJoinType() != JoinRelType.INNER) {
+ return;
+ }
+
+ HyperGraph result;
+ List<RelNode> inputs = new ArrayList<>();
+ List<HyperEdge> edges = new ArrayList<>();
+ List<RexNode> joinConds = new ArrayList<>();
+
+ if (origJoin.getCondition().isAlwaysTrue()) {
+ joinConds.add(origJoin.getCondition());
+ } else {
+ RelOptUtil.decomposeConjunction(origJoin.getCondition(), joinConds);
+ }
+
+ // when right is HyperGraph, need shift the leftNodeBit, rightNodeBit, condition of HyperEdge
+ int leftNodeCount;
+ int leftFieldCount = left.getRowType().getFieldCount();
+ if (left instanceof HyperGraph && right instanceof HyperGraph) {
+ leftNodeCount = left.getInputs().size();
+ inputs.addAll(left.getInputs());
+ inputs.addAll(right.getInputs());
+
+ edges.addAll(((HyperGraph) left).getEdges());
+ edges.addAll(
+ ((HyperGraph) right).getEdges().stream()
+ .map(hyperEdge -> adjustNodeBit(hyperEdge, leftNodeCount, leftFieldCount))
+ .collect(Collectors.toList()));
+ } else if (left instanceof HyperGraph) {
+ leftNodeCount = left.getInputs().size();
+ inputs.addAll(left.getInputs());
+ inputs.add(right);
+
+ edges.addAll(((HyperGraph) left).getEdges());
+ } else if (right instanceof HyperGraph) {
+ leftNodeCount = 1;
+ inputs.add(left);
+ inputs.addAll(right.getInputs());
+
+ edges.addAll(
+ ((HyperGraph) right).getEdges().stream()
+ .map(hyperEdge -> adjustNodeBit(hyperEdge, leftNodeCount, leftFieldCount))
+ .collect(Collectors.toList()));
+ } else {
+ leftNodeCount = 1;
+ inputs.add(left);
+ inputs.add(right);
+ }
+
+ HashMap<Integer, Integer> fieldIndexToNodeIndexMap = new HashMap<>();
+ int fieldCount = 0;
+ for (int i = 0; i < inputs.size(); i++) {
+ for (int j = 0; j < inputs.get(i).getRowType().getFieldCount(); j++) {
+ fieldIndexToNodeIndexMap.put(fieldCount++, i);
+ }
+ }
+ // convert current join condition to hyper edge condition
+ for (RexNode joinCond : joinConds) {
+ long leftNodeBits;
+ long rightNodeBits;
+ List<Integer> leftRefs = new ArrayList<>();
+ List<Integer> rightRefs = new ArrayList<>();
+
+ RexVisitorImpl visitor = new RexVisitorImpl<Void>(true) {
+ @Override public Void visitInputRef(RexInputRef inputRef) {
+ Integer nodeIndex = fieldIndexToNodeIndexMap.get(inputRef.getIndex());
+ if (nodeIndex == null) {
+ throw new IllegalArgumentException("RexInputRef refers a dummy field: "
+ + inputRef + ", rowType is: " + origJoin.getRowType());
+ }
+ if (nodeIndex < leftNodeCount) {
+ leftRefs.add(nodeIndex);
+ } else {
+ rightRefs.add(nodeIndex);
+ }
+ return null;
+ }
+ };
+ joinCond.accept(visitor);
+
+ // when cartesian product, make it to complex hyper edge
+ if (leftRefs.isEmpty() || rightRefs.isEmpty()) {
+ leftNodeBits = LongBitmap.newBitmapBetween(0, leftNodeCount);
+ rightNodeBits = LongBitmap.newBitmapBetween(leftNodeCount, inputs.size());
+ } else {
+ leftNodeBits = LongBitmap.newBitmapFromList(leftRefs);
+ rightNodeBits = LongBitmap.newBitmapFromList(rightRefs);
+ }
+ edges.add(
+ new HyperEdge(
+ leftNodeBits,
+ rightNodeBits,
+ origJoin.getJoinType(),
+ joinCond));
+ }
+ result =
+ new HyperGraph(
+ origJoin.getCluster(),
+ origJoin.getTraitSet(),
+ inputs,
+ edges,
+ origJoin.getRowType());
+
+ call.transformTo(result);
+ }
+
+ private static HyperEdge adjustNodeBit(HyperEdge hyperEdge, int nodeOffset, int fieldOffset) {
+ RexShuttle shuttle = new RexShuttle() {
Review Comment:
IIANM this shuttle is not needed, you can reuse `RexUtil#shift(RexNode node, final int offset)` method
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "silundong (via GitHub)" <gi...@apache.org>.
silundong commented on code in PR #4204:
URL: https://github.com/apache/calcite/pull/4204#discussion_r1984235656
##########
core/src/main/java/org/apache/calcite/rel/rules/CoreRules.java:
##########
@@ -816,4 +816,15 @@ private CoreRules() {}
WINDOW_REDUCE_EXPRESSIONS =
ReduceExpressionsRule.WindowReduceExpressionsRule.WindowReduceExpressionsRuleConfig
.DEFAULT.toRule();
+
+ /** Rule that flattens a tree of {@link LogicalJoin}s
+ * into a single {@link HyperGraph} with N inputs. */
+ public static final JoinToHyperGraphRule JOIN_TO_HYPER_GRAPH =
Review Comment:
Sure, I will update it
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "rubenada (via GitHub)" <gi...@apache.org>.
rubenada commented on code in PR #4204:
URL: https://github.com/apache/calcite/pull/4204#discussion_r1979275478
##########
core/src/main/java/org/apache/calcite/rel/rules/HyperEdge.java:
##########
@@ -0,0 +1,82 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to you under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.calcite.rel.rules;
+
+import org.apache.calcite.rel.core.JoinRelType;
+import org.apache.calcite.rex.RexNode;
+
+/**
+ * Edge in HyperGraph, that represents a join predicate.
+ */
+public class HyperEdge {
+
+ private long leftNodeBits;
+
+ private long rightNodeBits;
+
+ private JoinRelType joinType;
+
+ private RexNode condition;
+
+ public HyperEdge(long leftNodeBits, long rightNodeBits, JoinRelType joinType, RexNode condition) {
+ this.leftNodeBits = leftNodeBits;
+ this.rightNodeBits = rightNodeBits;
+ this.joinType = joinType;
+ this.condition = condition;
+ }
+
+ public long getNodeBitmap() {
+ return leftNodeBits | rightNodeBits;
+ }
+
+ public long getLeftNodeBitmap() {
+ return leftNodeBits;
+ }
+
+ public long getRightNodeBitmap() {
+ return rightNodeBits;
+ }
+
+ // hyperedge (u, v) is simple if |u| = |v| = 1
+ public boolean isSimple() {
+ boolean leftSimple = (leftNodeBits & (leftNodeBits - 1)) == 0;
Review Comment:
nit: what about having a `isSimple` final boolean field, computed one in the constructor and this method simply returns it?
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "silundong (via GitHub)" <gi...@apache.org>.
silundong closed pull request #4204: [CALCITE-6846] Support basic dphyp join reorder algorithm
URL: https://github.com/apache/calcite/pull/4204
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "silundong (via GitHub)" <gi...@apache.org>.
silundong commented on code in PR #4204:
URL: https://github.com/apache/calcite/pull/4204#discussion_r1966974085
##########
core/src/test/java/org/apache/calcite/test/RelOptRulesTest.java:
##########
@@ -9546,4 +9546,21 @@ private void checkJoinAssociateRuleWithTopAlwaysTrueCondition(boolean allowAlway
.withRule(CoreRules.MULTI_JOIN_OPTIMIZE)
.check();
}
+
+ @Test void testDphypJoinReorder() {
Review Comment:
Sure, I will update it.
##########
core/src/main/java/org/apache/calcite/rel/rules/DpHyp.java:
##########
@@ -0,0 +1,179 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to you under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.calcite.rel.rules;
+
+import org.apache.calcite.plan.RelOptCost;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.core.JoinRelType;
+import org.apache.calcite.rel.metadata.RelMetadataQuery;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.tools.RelBuilder;
+
+import org.checkerframework.checker.nullness.qual.Nullable;
+
+import java.util.HashMap;
+import java.util.List;
+
+/**
+ * The core process of dphyp enumeration algorithm.
+ */
+public class DpHyp {
+
+ private HyperGraph hyperGraph;
+
+ private HashMap<Long, RelNode> dpTable;
+
+ private RelBuilder builder;
+
+ private RelMetadataQuery mq;
+
+ public DpHyp(HyperGraph hyperGraph, RelBuilder builder, RelMetadataQuery relMetadataQuery) {
+ this.hyperGraph = hyperGraph;
+ this.dpTable = new HashMap<>();
+ this.builder = builder;
+ this.mq = relMetadataQuery;
+ }
+
+ public void startEnumerateJoin() {
+ int size = hyperGraph.getInputs().size();
+ for (int i = 0; i < size; i++) {
+ long singleNode = LongBitmap.newBitmap(i);
+ dpTable.put(singleNode, hyperGraph.getInput(i));
+ hyperGraph.initEdgeBitMap(singleNode);
+ }
+
+ // start enumerating from the second to last
+ for (int i = size - 2; i >= 0; i--) {
+ long csg = LongBitmap.newBitmap(i);
+ long forbidden = csg - 1;
+ emitCsg(csg);
+ enumerateCsgRec(csg, forbidden);
+ }
+ }
+
+ private void emitCsg(long csg) {
+ long forbidden = csg | LongBitmap.getBvBitmap(csg);
+ long neighbors = hyperGraph.getNeighborBitmap(csg, forbidden);
+
+ LongBitmap.ReverseIterator reverseIterator = new LongBitmap.ReverseIterator(neighbors);
+ for (long cmp : reverseIterator) {
+ List<HyperEdge> edges = hyperGraph.connectCsgCmp(csg, cmp);
+ if (!edges.isEmpty()) {
+ emitCsgCmp(csg, cmp, edges);
+ }
+ // forbidden the nodes that smaller than current cmp when extend cmp, e.g.
+ // neighbors = {t1, t2}, t1 and t2 are connected.
+ // when extented t2, we will get (t1, t2)
+ // when extented t1, we will get (t1, t2) repeated
+ long newForbidden =
+ (cmp | LongBitmap.getBvBitmap(cmp)) & neighbors;
+ newForbidden = newForbidden | forbidden;
+ enumerateCmpRec(csg, cmp, newForbidden);
+ }
+ }
+
+ private void enumerateCsgRec(long csg, long forbidden) {
+ long neighbors = hyperGraph.getNeighborBitmap(csg, forbidden);
+ LongBitmap.SubsetIterator subsetIterator = new LongBitmap.SubsetIterator(neighbors);
+ for (long subNeighbor : subsetIterator) {
+ hyperGraph.updateEdgesForUnion(csg, subNeighbor);
+ long newCsg = csg | subNeighbor;
+ if (dpTable.containsKey(newCsg)) {
+ emitCsg(newCsg);
+ }
+ }
+ long newForbidden = forbidden | neighbors;
+ subsetIterator.reset();
+ for (long subNeighbor : subsetIterator) {
+ long newCsg = csg | subNeighbor;
+ enumerateCsgRec(newCsg, newForbidden);
+ }
+ }
+
+ private void enumerateCmpRec(long csg, long cmp, long forbidden) {
+ long neighbors = hyperGraph.getNeighborBitmap(cmp, forbidden);
+ LongBitmap.SubsetIterator subsetIterator = new LongBitmap.SubsetIterator(neighbors);
+ for (long subNeighbor : subsetIterator) {
+ long newCmp = cmp | subNeighbor;
+ hyperGraph.updateEdgesForUnion(cmp, subNeighbor);
+ if (dpTable.containsKey(newCmp)) {
+ List<HyperEdge> edges = hyperGraph.connectCsgCmp(csg, newCmp);
+ if (!edges.isEmpty()) {
+ emitCsgCmp(csg, newCmp, edges);
+ }
+ }
+ }
+ long newForbidden = forbidden | neighbors;
+ subsetIterator.reset();
+ for (long subNeighbor : subsetIterator) {
+ long newCmp = cmp | subNeighbor;
+ enumerateCmpRec(csg, newCmp, newForbidden);
+ }
+ }
+
+ private void emitCsgCmp(long csg, long cmp, List<HyperEdge> edges) {
+ RelNode child1 = dpTable.get(csg);
+ RelNode child2 = dpTable.get(cmp);
+ if (child1 == null || child2 == null) {
+ throw new IllegalArgumentException(
+ "csg and cmp were not enumerated in the previous dp process");
+ }
+
+ JoinRelType joinType = hyperGraph.extractJoinType(edges);
+ if (joinType == null) {
+ return;
+ }
+ RexNode joinCond1 = hyperGraph.extractJoinCond(child1, child2, edges);
+ RelNode newPlan1 = builder
+ .push(child1)
+ .push(child2)
+ .join(joinType, joinCond1)
+ .build();
+
+ // swap left and right
+ RexNode joinCond2 = hyperGraph.extractJoinCond(child2, child1, edges);
+ RelNode newPlan2 = builder
+ .push(child2)
+ .push(child1)
+ .join(joinType, joinCond2)
+ .build();
+ RelNode winPlan = chooseBetterPlan(newPlan1, newPlan2);
+
+ RelNode oriPlan = dpTable.get(csg | cmp);
+ if (oriPlan != null) {
+ winPlan = chooseBetterPlan(winPlan, oriPlan);
+ }
+ dpTable.put(csg | cmp, winPlan);
+ }
+
+ public @Nullable RelNode getBestPlan() {
+ int size = hyperGraph.getInputs().size();
+ long wholeGraph = LongBitmap.newBitmapBetween(0, size);
+ return dpTable.get(wholeGraph);
+ }
+
+ private RelNode chooseBetterPlan(RelNode plan1, RelNode plan2) {
+ RelOptCost cost1 = mq.getCumulativeCost(plan1);
+ RelOptCost cost2 = mq.getCumulativeCost(plan2);
+ if (cost1 == null || cost2 == null) {
Review Comment:
I will update it.
##########
core/src/main/java/org/apache/calcite/rel/rules/DphypJoinReorderRule.java:
##########
@@ -0,0 +1,86 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to you under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.calcite.rel.rules;
+
+import org.apache.calcite.plan.RelOptRuleCall;
+import org.apache.calcite.plan.RelRule;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.core.Join;
+import org.apache.calcite.rex.RexBuilder;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.tools.RelBuilder;
+
+import org.immutables.value.Value;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/** Rule that re-orders a {@link Join} tree using dphyp algorithm.
+ *
+ * @see CoreRules#HYPER_GRAPH_OPTIMIZE */
+@Value.Enclosing
+public class DphypJoinReorderRule
+ extends RelRule<DphypJoinReorderRule.Config>
+ implements TransformationRule {
+
+ protected DphypJoinReorderRule(Config config) {
+ super(config);
+ }
+
+ @Override public void onMatch(RelOptRuleCall call) {
+ HyperGraph hyperGraph = call.rel(0);
+ RelBuilder relBuilder = call.builder();
+ // make all field name unique and convert the
+ // HyperEdge condition from RexInputRef to RexInputFieldName
+ hyperGraph.convertHyperEdgeCond();
+
+ // enumerate by Dphyp
+ DpHyp dpHyp = new DpHyp(hyperGraph, relBuilder, call.getMetadataQuery());
+ dpHyp.startEnumerateJoin();
+ RelNode orderedJoin = dpHyp.getBestPlan();
+ if (orderedJoin == null) {
+ return;
Review Comment:
My original intention is that when the query is too complex, even dphyp can be very time-consuming. So, if the execution of `dpHyp.startEnumerateJoin` exceeds a certain time limit, the enumeration process should be forcibly terminated. In this case, the dp table may not have results yet. After returning null, the hypergraph simplification algorithm might be executed.
Alternatively, the rules related to dphyp could be integrated into a single method, with the original Join tree as the input parameter. If the optimization times out, the original Join tree is returned, and other Join reorder algorithms can be called subsequently.
Do you have any suggestions for this? I will update it accordingly.
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "rubenada (via GitHub)" <gi...@apache.org>.
rubenada commented on code in PR #4204:
URL: https://github.com/apache/calcite/pull/4204#discussion_r1970039049
##########
core/src/main/java/org/apache/calcite/rel/rules/DphypJoinReorderRule.java:
##########
@@ -0,0 +1,86 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to you under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.calcite.rel.rules;
+
+import org.apache.calcite.plan.RelOptRuleCall;
+import org.apache.calcite.plan.RelRule;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.core.Join;
+import org.apache.calcite.rex.RexBuilder;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.tools.RelBuilder;
+
+import org.immutables.value.Value;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/** Rule that re-orders a {@link Join} tree using dphyp algorithm.
+ *
+ * @see CoreRules#HYPER_GRAPH_OPTIMIZE */
+@Value.Enclosing
+public class DphypJoinReorderRule
+ extends RelRule<DphypJoinReorderRule.Config>
+ implements TransformationRule {
+
+ protected DphypJoinReorderRule(Config config) {
+ super(config);
+ }
+
+ @Override public void onMatch(RelOptRuleCall call) {
+ HyperGraph hyperGraph = call.rel(0);
+ RelBuilder relBuilder = call.builder();
+ // make all field name unique and convert the
+ // HyperEdge condition from RexInputRef to RexInputFieldName
+ hyperGraph.convertHyperEdgeCond();
+
+ // enumerate by Dphyp
+ DpHyp dpHyp = new DpHyp(hyperGraph, relBuilder, call.getMetadataQuery());
+ dpHyp.startEnumerateJoin();
+ RelNode orderedJoin = dpHyp.getBestPlan();
+ if (orderedJoin == null) {
+ return;
Review Comment:
Thanks for the explanation @silundong . I was worried that this situation could lead to a CannotPlanException (or similar) if these rules are used within HepPlanner. But your explanation makes total sense. Since we won't plan to add the new rules in the "default" Calcite rule set, it's fine. IMO we can keep the code as it is.
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "rubenada (via GitHub)" <gi...@apache.org>.
rubenada commented on code in PR #4204:
URL: https://github.com/apache/calcite/pull/4204#discussion_r1979274485
##########
core/src/main/java/org/apache/calcite/rel/rules/HyperEdge.java:
##########
@@ -0,0 +1,82 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to you under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.calcite.rel.rules;
+
+import org.apache.calcite.rel.core.JoinRelType;
+import org.apache.calcite.rex.RexNode;
+
+/**
+ * Edge in HyperGraph, that represents a join predicate.
+ */
+public class HyperEdge {
+
+ private long leftNodeBits;
Review Comment:
final fields?
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "sonarqubecloud[bot] (via GitHub)" <gi...@apache.org>.
sonarqubecloud[bot] commented on PR #4204:
URL: https://github.com/apache/calcite/pull/4204#issuecomment-2703204122
## [](https://sonarcloud.io/dashboard?id=apache_calcite&pullRequest=4204) **Quality Gate passed**
Issues
 [7 New issues](https://sonarcloud.io/project/issues?id=apache_calcite&pullRequest=4204&issueStatuses=OPEN,CONFIRMED&sinceLeakPeriod=true)
 [0 Accepted issues](https://sonarcloud.io/project/issues?id=apache_calcite&pullRequest=4204&issueStatuses=ACCEPTED)
Measures
 [0 Security Hotspots](https://sonarcloud.io/project/security_hotspots?id=apache_calcite&pullRequest=4204&issueStatuses=OPEN,CONFIRMED&sinceLeakPeriod=true)
 [87.8% Coverage on New Code](https://sonarcloud.io/component_measures?id=apache_calcite&pullRequest=4204&metric=new_coverage&view=list)
 [0.0% Duplication on New Code](https://sonarcloud.io/component_measures?id=apache_calcite&pullRequest=4204&metric=new_duplicated_lines_density&view=list)
[See analysis details on SonarQube Cloud](https://sonarcloud.io/dashboard?id=apache_calcite&pullRequest=4204)
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "sonarqubecloud[bot] (via GitHub)" <gi...@apache.org>.
sonarqubecloud[bot] commented on PR #4204:
URL: https://github.com/apache/calcite/pull/4204#issuecomment-2705288132
## [](https://sonarcloud.io/dashboard?id=apache_calcite&pullRequest=4204) **Quality Gate passed**
Issues
 [7 New issues](https://sonarcloud.io/project/issues?id=apache_calcite&pullRequest=4204&issueStatuses=OPEN,CONFIRMED&sinceLeakPeriod=true)
 [0 Accepted issues](https://sonarcloud.io/project/issues?id=apache_calcite&pullRequest=4204&issueStatuses=ACCEPTED)
Measures
 [0 Security Hotspots](https://sonarcloud.io/project/security_hotspots?id=apache_calcite&pullRequest=4204&issueStatuses=OPEN,CONFIRMED&sinceLeakPeriod=true)
 [87.8% Coverage on New Code](https://sonarcloud.io/component_measures?id=apache_calcite&pullRequest=4204&metric=new_coverage&view=list)
 [0.0% Duplication on New Code](https://sonarcloud.io/component_measures?id=apache_calcite&pullRequest=4204&metric=new_duplicated_lines_density&view=list)
[See analysis details on SonarQube Cloud](https://sonarcloud.io/dashboard?id=apache_calcite&pullRequest=4204)
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "silundong (via GitHub)" <gi...@apache.org>.
silundong commented on PR #4204:
URL: https://github.com/apache/calcite/pull/4204#issuecomment-2673102298
> Is this ready for review? If not, please mark as draft.
Ready, please review.
There are still some checks that are not passed, but I think I have taken care of them in the code. Can you give me some advice on how to pass these checks?
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "NobiGo (via GitHub)" <gi...@apache.org>.
NobiGo commented on PR #4204:
URL: https://github.com/apache/calcite/pull/4204#issuecomment-2673195972
Some parameters might need to be checked whether they are NULL or undergo active type conversion.
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "silundong (via GitHub)" <gi...@apache.org>.
silundong commented on code in PR #4204:
URL: https://github.com/apache/calcite/pull/4204#discussion_r1966951027
##########
core/src/main/java/org/apache/calcite/rel/rules/CoreRules.java:
##########
@@ -816,4 +816,14 @@ private CoreRules() {}
WINDOW_REDUCE_EXPRESSIONS =
ReduceExpressionsRule.WindowReduceExpressionsRule.WindowReduceExpressionsRuleConfig
.DEFAULT.toRule();
+ /** Rule that flattens a tree of {@link LogicalJoin}s
Review Comment:
Sure, I will update it.
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "rubenada (via GitHub)" <gi...@apache.org>.
rubenada commented on code in PR #4204:
URL: https://github.com/apache/calcite/pull/4204#discussion_r1966837330
##########
core/src/test/java/org/apache/calcite/test/RelOptRulesTest.java:
##########
@@ -9546,4 +9546,21 @@ private void checkJoinAssociateRuleWithTopAlwaysTrueCondition(boolean allowAlway
.withRule(CoreRules.MULTI_JOIN_OPTIMIZE)
.check();
}
+
+ @Test void testDphypJoinReorder() {
Review Comment:
I'd be nice to have a few more tests with more variety of scenarios.
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "asolimando (via GitHub)" <gi...@apache.org>.
asolimando commented on PR #4204:
URL: https://github.com/apache/calcite/pull/4204#issuecomment-2709715641
> > @silundong could you please take a look at Alessandro's minor comments in the Jira ticket?
>
> Sure, I will indicate in HyperGraph and HyperEdge that the code is referenced from Apache Doris. Is that ok?
Thanks @silundong, please put a link to the two corresponding files using a fixed release or commit other than master/main, so it stays stable over time.
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "rubenada (via GitHub)" <gi...@apache.org>.
rubenada commented on code in PR #4204:
URL: https://github.com/apache/calcite/pull/4204#discussion_r1966834933
##########
core/src/main/java/org/apache/calcite/rel/rules/DphypJoinReorderRule.java:
##########
@@ -0,0 +1,86 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to you under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.calcite.rel.rules;
+
+import org.apache.calcite.plan.RelOptRuleCall;
+import org.apache.calcite.plan.RelRule;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.core.Join;
+import org.apache.calcite.rex.RexBuilder;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.tools.RelBuilder;
+
+import org.immutables.value.Value;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/** Rule that re-orders a {@link Join} tree using dphyp algorithm.
+ *
+ * @see CoreRules#HYPER_GRAPH_OPTIMIZE */
+@Value.Enclosing
+public class DphypJoinReorderRule
+ extends RelRule<DphypJoinReorderRule.Config>
+ implements TransformationRule {
+
+ protected DphypJoinReorderRule(Config config) {
+ super(config);
+ }
+
+ @Override public void onMatch(RelOptRuleCall call) {
+ HyperGraph hyperGraph = call.rel(0);
+ RelBuilder relBuilder = call.builder();
+ // make all field name unique and convert the
+ // HyperEdge condition from RexInputRef to RexInputFieldName
+ hyperGraph.convertHyperEdgeCond();
+
+ // enumerate by Dphyp
+ DpHyp dpHyp = new DpHyp(hyperGraph, relBuilder, call.getMetadataQuery());
+ dpHyp.startEnumerateJoin();
+ RelNode orderedJoin = dpHyp.getBestPlan();
+ if (orderedJoin == null) {
+ return;
Review Comment:
If we get here, it means something went wrong, doesn't it?
IIANM this would lead to a CannotPlanException (if we cannot decompose the HyperGraph into Joins, the we'll keep the HyperGraph which is a "not implementable" operator). In that case, maybe it would be a good idea to throw an exception (to fail early and with a clearer message) instead of simply returning (and failing later with a more generic and "cryptic" exception)
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "silundong (via GitHub)" <gi...@apache.org>.
silundong commented on code in PR #4204:
URL: https://github.com/apache/calcite/pull/4204#discussion_r1966974165
##########
core/src/main/java/org/apache/calcite/rel/rules/CoreRules.java:
##########
@@ -816,4 +816,14 @@ private CoreRules() {}
WINDOW_REDUCE_EXPRESSIONS =
ReduceExpressionsRule.WindowReduceExpressionsRule.WindowReduceExpressionsRuleConfig
.DEFAULT.toRule();
+ /** Rule that flattens a tree of {@link LogicalJoin}s
Review Comment:
Sure, I will update it.
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "silundong (via GitHub)" <gi...@apache.org>.
silundong commented on PR #4204:
URL: https://github.com/apache/calcite/pull/4204#issuecomment-2673100666
> Is this ready for review? If not, please mark as draft.
Ready, please review.
There are still some checks that are not passed, but I think I have taken care of them in the code. Can you give me some advice on how to pass these checks?
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "rubenada (via GitHub)" <gi...@apache.org>.
rubenada commented on code in PR #4204:
URL: https://github.com/apache/calcite/pull/4204#discussion_r1979294664
##########
core/src/main/java/org/apache/calcite/rel/rules/HyperGraph.java:
##########
@@ -0,0 +1,459 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to you under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.calcite.rel.rules;
+
+import org.apache.calcite.linq4j.Ord;
+import org.apache.calcite.plan.RelOptCluster;
+import org.apache.calcite.plan.RelTraitSet;
+import org.apache.calcite.rel.AbstractRelNode;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.RelWriter;
+import org.apache.calcite.rel.core.JoinRelType;
+import org.apache.calcite.rel.logical.LogicalProject;
+import org.apache.calcite.rel.type.RelDataType;
+import org.apache.calcite.rel.type.RelDataTypeField;
+import org.apache.calcite.rex.RexBiVisitor;
+import org.apache.calcite.rex.RexInputRef;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.rex.RexShuttle;
+import org.apache.calcite.rex.RexUtil;
+import org.apache.calcite.rex.RexVariable;
+import org.apache.calcite.rex.RexVisitor;
+
+import com.google.common.collect.ImmutableList;
+
+import org.checkerframework.checker.nullness.qual.Nullable;
+
+import java.util.ArrayList;
+import java.util.BitSet;
+import java.util.HashMap;
+import java.util.List;
+import java.util.stream.Collectors;
+
+import static com.google.common.base.Preconditions.checkArgument;
+
+/**
+ * HyperGraph represents a join graph.
+ */
+public class HyperGraph extends AbstractRelNode {
Review Comment:
Probably not required at this point, but I think it'll be a good idea (and would avoid potential issues in the future) if this class overrides the `accept(RexShuttle shuttle)` method, which I guess should return a new HyperGraph where the RexShuttle has been applied to the edges conditions?
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "rubenada (via GitHub)" <gi...@apache.org>.
rubenada commented on code in PR #4204:
URL: https://github.com/apache/calcite/pull/4204#discussion_r1979287126
##########
core/src/main/java/org/apache/calcite/rel/rules/HyperGraph.java:
##########
@@ -0,0 +1,459 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to you under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.calcite.rel.rules;
+
+import org.apache.calcite.linq4j.Ord;
+import org.apache.calcite.plan.RelOptCluster;
+import org.apache.calcite.plan.RelTraitSet;
+import org.apache.calcite.rel.AbstractRelNode;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.RelWriter;
+import org.apache.calcite.rel.core.JoinRelType;
+import org.apache.calcite.rel.logical.LogicalProject;
+import org.apache.calcite.rel.type.RelDataType;
+import org.apache.calcite.rel.type.RelDataTypeField;
+import org.apache.calcite.rex.RexBiVisitor;
+import org.apache.calcite.rex.RexInputRef;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.rex.RexShuttle;
+import org.apache.calcite.rex.RexUtil;
+import org.apache.calcite.rex.RexVariable;
+import org.apache.calcite.rex.RexVisitor;
+
+import com.google.common.collect.ImmutableList;
+
+import org.checkerframework.checker.nullness.qual.Nullable;
+
+import java.util.ArrayList;
+import java.util.BitSet;
+import java.util.HashMap;
+import java.util.List;
+import java.util.stream.Collectors;
+
+import static com.google.common.base.Preconditions.checkArgument;
+
+/**
+ * HyperGraph represents a join graph.
+ */
+public class HyperGraph extends AbstractRelNode {
+
+ private final List<RelNode> inputs;
+
+ @SuppressWarnings("HidingField")
+ private final RelDataType rowType;
+
+ private final List<HyperEdge> edges;
+
+ // record the indices of complex hyper edges in the 'edges'
+ private final BitSet complexEdgesBitmap;
+
+ /**
+ * For the HashMap fields, key is the bitmap for inputs,
+ * value is the hyper edge bitmap in edges.
+ */
+ // record which hyper edges have been used by the enumerated csg-cmp pairs
+ private final HashMap<Long, BitSet> ccpUsedEdgesMap;
+
+ private final HashMap<Long, BitSet> simpleEdgesMap;
+
+ private final HashMap<Long, BitSet> complexEdgesMap;
+
+ // node bitmap overlaps edge's leftNodeBits or rightNodeBits, but does not completely cover
+ private final HashMap<Long, BitSet> overlapEdgesMap;
+
+ protected HyperGraph(RelOptCluster cluster,
+ RelTraitSet traitSet,
+ List<RelNode> inputs,
+ List<HyperEdge> edges,
+ RelDataType rowType) {
+ super(cluster, traitSet);
+ this.inputs = inputs;
+ this.edges = edges;
+ this.rowType = rowType;
+ this.complexEdgesBitmap = new BitSet();
+ for (int i = 0; i < edges.size(); i++) {
+ if (!edges.get(i).isSimple()) {
+ complexEdgesBitmap.set(i);
+ }
+ }
+ this.ccpUsedEdgesMap = new HashMap<>();
+ this.simpleEdgesMap = new HashMap<>();
+ this.complexEdgesMap = new HashMap<>();
+ this.overlapEdgesMap = new HashMap<>();
+ }
+
+ protected HyperGraph(RelOptCluster cluster,
+ RelTraitSet traitSet,
+ List<RelNode> inputs,
+ List<HyperEdge> edges,
+ RelDataType rowType,
+ BitSet complexEdgesBitmap,
+ HashMap<Long, BitSet> ccpUsedEdgesMap,
+ HashMap<Long, BitSet> simpleEdgesMap,
+ HashMap<Long, BitSet> complexEdgesMap,
+ HashMap<Long, BitSet> overlapEdgesMap) {
+ super(cluster, traitSet);
+ this.inputs = inputs;
+ this.edges = edges;
+ this.rowType = rowType;
+ this.complexEdgesBitmap = complexEdgesBitmap;
+ this.ccpUsedEdgesMap = ccpUsedEdgesMap;
+ this.simpleEdgesMap = simpleEdgesMap;
+ this.complexEdgesMap = complexEdgesMap;
+ this.overlapEdgesMap = overlapEdgesMap;
+ }
+
+ @Override public RelNode copy(RelTraitSet traitSet, List<RelNode> inputs) {
+ return new HyperGraph(
+ getCluster(),
+ traitSet,
+ inputs,
+ edges,
+ rowType,
+ complexEdgesBitmap,
+ ccpUsedEdgesMap,
+ simpleEdgesMap,
+ complexEdgesMap,
+ overlapEdgesMap);
+ }
+
+ @Override public RelWriter explainTerms(RelWriter pw) {
+ super.explainTerms(pw);
+ for (Ord<RelNode> ord : Ord.zip(inputs)) {
+ pw.input("input#" + ord.i, ord.e);
+ }
+ List<String> hyperEdges = edges.stream()
+ .map(hyperEdge -> hyperEdge.toString())
+ .collect(Collectors.toList());
+ pw.item("edges", String.join(",", hyperEdges));
+ return pw;
+ }
+
+ @Override public List<RelNode> getInputs() {
+ return inputs;
+ }
+
+ @Override public void replaceInput(int ordinalInParent, RelNode p) {
+ inputs.set(ordinalInParent, p);
+ recomputeDigest();
+ }
+
+ @Override public RelDataType deriveRowType() {
+ return rowType;
+ }
+
+ //~ hyper graph method ----------------------------------------------------------
+
+ public List<HyperEdge> getEdges() {
+ return edges;
+ }
+
+ public long getNeighborBitmap(long csg, long forbidden) {
+ long neighbors = 0L;
+ List<HyperEdge> simpleEdges = simpleEdgesMap.getOrDefault(csg, new BitSet()).stream()
+ .mapToObj(edges::get)
+ .collect(Collectors.toList());
+ for (HyperEdge edge : simpleEdges) {
+ neighbors |= edge.getNodeBitmap();
+ }
+
+ forbidden = forbidden | csg;
+ neighbors = neighbors & ~forbidden;
+ forbidden = forbidden | neighbors;
+
+ List<HyperEdge> complexEdges = complexEdgesMap.getOrDefault(csg, new BitSet()).stream()
+ .mapToObj(edges::get)
+ .collect(Collectors.toList());
+ for (HyperEdge edge : complexEdges) {
+ long leftBitmap = edge.getLeftNodeBitmap();
+ long rightBitmap = edge.getRightNodeBitmap();
+ if (LongBitmap.isSubSet(leftBitmap, csg) && !LongBitmap.isOverlap(rightBitmap, forbidden)) {
+ neighbors |= Long.lowestOneBit(rightBitmap);
+ } else if (LongBitmap.isSubSet(rightBitmap, csg)
+ && !LongBitmap.isOverlap(leftBitmap, forbidden)) {
+ neighbors |= Long.lowestOneBit(leftBitmap);
+ }
+ }
+ return neighbors;
+ }
+
+ /**
+ * If csg and cmp are connected, return the edges that connect them.
+ */
+ public List<HyperEdge> connectCsgCmp(long csg, long cmp) {
+ checkArgument(simpleEdgesMap.containsKey(csg));
+ checkArgument(simpleEdgesMap.containsKey(cmp));
+ List<HyperEdge> connectedEdges = new ArrayList<>();
+ BitSet connectedEdgesBitmap = new BitSet();
+ connectedEdgesBitmap.or(simpleEdgesMap.getOrDefault(csg, new BitSet()));
+ connectedEdgesBitmap.or(complexEdgesMap.getOrDefault(csg, new BitSet()));
+
+ BitSet cmpEdgesBitmap = new BitSet();
+ cmpEdgesBitmap.or(simpleEdgesMap.getOrDefault(cmp, new BitSet()));
+ cmpEdgesBitmap.or(complexEdgesMap.getOrDefault(cmp, new BitSet()));
+ connectedEdgesBitmap.and(cmpEdgesBitmap);
+
+ // only consider the records related to csg and cmp in the simpleEdgesMap/complexEdgesMap,
+ // may omit some complex hyper edges. e.g.
+ // csg = {t1, t3}, cmp = {t2}, will omit the edge (t1, t2)——(t3)
+ BitSet mayMissedEdges = new BitSet();
+ mayMissedEdges.or(complexEdgesBitmap);
+ mayMissedEdges.andNot(ccpUsedEdgesMap.getOrDefault(csg, new BitSet()));
+ mayMissedEdges.andNot(ccpUsedEdgesMap.getOrDefault(cmp, new BitSet()));
+ mayMissedEdges.andNot(connectedEdgesBitmap);
+ mayMissedEdges.stream()
+ .forEach(index -> {
+ HyperEdge edge = edges.get(index);
+ if (LongBitmap.isSubSet(edge.getNodeBitmap(), csg | cmp)) {
+ connectedEdgesBitmap.set(index);
+ }
+ });
+
+ // record hyper edges are used by current csg ∪ cmp
+ BitSet curUsedEdges = new BitSet();
+ curUsedEdges.or(connectedEdgesBitmap);
+ curUsedEdges.or(ccpUsedEdgesMap.getOrDefault(csg, new BitSet()));
+ curUsedEdges.or(ccpUsedEdgesMap.getOrDefault(cmp, new BitSet()));
+ if (ccpUsedEdgesMap.containsKey(csg | cmp)) {
+ checkArgument(
+ curUsedEdges.equals(ccpUsedEdgesMap.get(csg | cmp)));
+ }
+ ccpUsedEdgesMap.put(csg | cmp, curUsedEdges);
+
+ connectedEdgesBitmap.stream()
+ .forEach(index -> connectedEdges.add(edges.get(index)));
+ return connectedEdges;
+ }
+
+ public void initEdgeBitMap(long subset) {
+ BitSet simpleBitSet = new BitSet();
+ BitSet complexBitSet = new BitSet();
+ BitSet overlapBitSet = new BitSet();
+ for (int i = 0; i < edges.size(); i++) {
+ HyperEdge edge = edges.get(i);
+ if (isAccurateEdge(edge, subset)) {
+ if (edge.isSimple()) {
+ simpleBitSet.set(i);
+ } else {
+ complexBitSet.set(i);
+ }
+ } else if (isOverlapEdge(edge, subset)) {
+ overlapBitSet.set(i);
+ }
+ }
+ simpleEdgesMap.put(subset, simpleBitSet);
+ complexEdgesMap.put(subset, complexBitSet);
+ overlapEdgesMap.put(subset, overlapBitSet);
+ }
+
+ public void updateEdgesForUnion(long subset1, long subset2) {
+ if (!simpleEdgesMap.containsKey(subset1)) {
+ initEdgeBitMap(subset1);
+ }
+ if (!simpleEdgesMap.containsKey(subset2)) {
+ initEdgeBitMap(subset2);
+ }
+ long unionSet = subset1 | subset2;
+ if (simpleEdgesMap.containsKey(unionSet)) {
+ return;
+ }
+
+ BitSet unionSimpleBitSet = new BitSet();
+ unionSimpleBitSet.or(simpleEdgesMap.getOrDefault(subset1, new BitSet()));
+ unionSimpleBitSet.or(simpleEdgesMap.getOrDefault(subset2, new BitSet()));
+
+ BitSet unionComplexBitSet = new BitSet();
+ unionComplexBitSet.or(complexEdgesMap.getOrDefault(subset1, new BitSet()));
+ unionComplexBitSet.or(complexEdgesMap.getOrDefault(subset2, new BitSet()));
+
+ BitSet unionOverlapBitSet = new BitSet();
+ unionOverlapBitSet.or(overlapEdgesMap.getOrDefault(subset1, new BitSet()));
+ unionOverlapBitSet.or(overlapEdgesMap.getOrDefault(subset2, new BitSet()));
+
+ // the overlaps edge that belongs to subset1/subset2
+ // may be complex edge for subset1 union subset2
+ for (int index : unionOverlapBitSet.stream().toArray()) {
+ HyperEdge edge = edges.get(index);
+ if (isAccurateEdge(edge, unionSet)) {
+ unionComplexBitSet.set(index);
+ unionOverlapBitSet.set(index, false);
+ }
+ }
+
+ // remove cycle in subset1 union subset2
+ for (int index : unionSimpleBitSet.stream().toArray()) {
+ HyperEdge edge = edges.get(index);
+ if (!isAccurateEdge(edge, unionSet)) {
+ unionSimpleBitSet.set(index, false);
+ }
+ }
+ for (int index : unionComplexBitSet.stream().toArray()) {
+ HyperEdge edge = edges.get(index);
+ if (!isAccurateEdge(edge, unionSet)) {
+ unionComplexBitSet.set(index, false);
+ }
+ }
+
+ simpleEdgesMap.put(unionSet, unionSimpleBitSet);
+ complexEdgesMap.put(unionSet, unionComplexBitSet);
+ overlapEdgesMap.put(unionSet, unionOverlapBitSet);
+ }
+
+ private static boolean isAccurateEdge(HyperEdge edge, long subset) {
+ boolean isLeftEnd = LongBitmap.isSubSet(edge.getLeftNodeBitmap(), subset)
+ && !LongBitmap.isOverlap(edge.getRightNodeBitmap(), subset);
+ boolean isRightEnd = LongBitmap.isSubSet(edge.getRightNodeBitmap(), subset)
+ && !LongBitmap.isOverlap(edge.getLeftNodeBitmap(), subset);
+ return isLeftEnd || isRightEnd;
+ }
+
+ private static boolean isOverlapEdge(HyperEdge edge, long subset) {
+ boolean isLeftEnd = LongBitmap.isOverlap(edge.getLeftNodeBitmap(), subset)
+ && !LongBitmap.isOverlap(edge.getRightNodeBitmap(), subset);
+ boolean isRightEnd = LongBitmap.isOverlap(edge.getRightNodeBitmap(), subset)
+ && !LongBitmap.isOverlap(edge.getLeftNodeBitmap(), subset);
+ return isLeftEnd || isRightEnd;
+ }
+
+ public @Nullable JoinRelType extractJoinType(List<HyperEdge> edges) {
+ JoinRelType joinType = edges.get(0).getJoinType();
+ for (int i = 1; i < edges.size(); i++) {
+ if (edges.get(i).getJoinType() != joinType) {
+ return null;
+ }
+ }
+ return joinType;
+ }
+
+ public RexNode extractJoinCond(RelNode left, RelNode right, List<HyperEdge> edges) {
+ List<RexNode> joinConds = new ArrayList<>();
+ List<RelDataTypeField> fieldList = new ArrayList<>(left.getRowType().getFieldList());
+ fieldList.addAll(right.getRowType().getFieldList());
+
+ List<String> names = new ArrayList<>(left.getRowType().getFieldNames());
+ names.addAll(right.getRowType().getFieldNames());
+
+ // convert the HyperEdge's condition from RexInputFieldName to RexInputRef
+ RexShuttle inputName2InputRefShuttle = new RexShuttle() {
+ @Override protected List<RexNode> visitList(
+ List<? extends RexNode> exprs,
+ boolean @Nullable [] update) {
+ ImmutableList.Builder<RexNode> clonedOperands = ImmutableList.builder();
+ for (RexNode operand : exprs) {
+ RexNode clonedOperand;
+ if (operand instanceof RexInputFieldName) {
+ int index = names.indexOf(((RexInputFieldName) operand).getName());
+ clonedOperand = new RexInputRef(index, fieldList.get(index).getType());
+ } else {
+ clonedOperand = operand.accept(this);
+ }
+ if ((clonedOperand != operand) && (update != null)) {
+ update[0] = true;
+ }
+ clonedOperands.add(clonedOperand);
+ }
+ return clonedOperands.build();
+ }
+ };
+
+ for (HyperEdge edge : edges) {
+ RexNode inputRefCond = edge.getCondition().accept(inputName2InputRefShuttle);
+ joinConds.add(inputRefCond);
+ }
+ return RexUtil.composeConjunction(left.getCluster().getRexBuilder(), joinConds);
+ }
+
+ /**
+ * Before starting enumeration, add Project on every input, make all field name unique.
+ * Convert the HyperEdge condition from RexInputRef to RexInputFieldName
+ */
+ public void convertHyperEdgeCond() {
+ int fieldIndex = 0;
+ List<RelDataTypeField> fieldList = rowType.getFieldList();
+ for (int nodeIndex = 0; nodeIndex < inputs.size(); nodeIndex++) {
+ RelNode input = inputs.get(nodeIndex);
+ List<RexNode> projects = new ArrayList<>();
+ List<String> names = new ArrayList<>();
+ for (int i = 0; i < input.getRowType().getFieldCount(); i++) {
+ projects.add(
+ new RexInputRef(
+ i,
+ fieldList.get(fieldIndex).getType()));
+ names.add(fieldList.get(fieldIndex).getName());
+ fieldIndex++;
+ }
+ RelNode renameProject =
+ LogicalProject.create(
Review Comment:
To make things more generic, I think this method should receive a RelBuilder, and instead of creating a new `LogicalProject`, it should do a relBuilder.push(input) + relBuilder.project(...) + relBuilder.build() to construct the new inputs; that would allow users that do not work with logical-convention to get the appropriate Project operator if the use their own RelBuilder
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "rubenada (via GitHub)" <gi...@apache.org>.
rubenada commented on code in PR #4204:
URL: https://github.com/apache/calcite/pull/4204#discussion_r1983506305
##########
core/src/main/java/org/apache/calcite/rel/rules/CoreRules.java:
##########
@@ -816,4 +816,15 @@ private CoreRules() {}
WINDOW_REDUCE_EXPRESSIONS =
ReduceExpressionsRule.WindowReduceExpressionsRule.WindowReduceExpressionsRuleConfig
.DEFAULT.toRule();
+
+ /** Rule that flattens a tree of {@link LogicalJoin}s
+ * into a single {@link HyperGraph} with N inputs. */
+ public static final JoinToHyperGraphRule JOIN_TO_HYPER_GRAPH =
Review Comment:
Could you please annotate also `JOIN_TO_HYPER_GRAPH` and `HYPER_GRAPH_OPTIMIZE` as `@Experimental` ?
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "rubenada (via GitHub)" <gi...@apache.org>.
rubenada commented on code in PR #4204:
URL: https://github.com/apache/calcite/pull/4204#discussion_r1966834933
##########
core/src/main/java/org/apache/calcite/rel/rules/DphypJoinReorderRule.java:
##########
@@ -0,0 +1,86 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to you under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.calcite.rel.rules;
+
+import org.apache.calcite.plan.RelOptRuleCall;
+import org.apache.calcite.plan.RelRule;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.core.Join;
+import org.apache.calcite.rex.RexBuilder;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.tools.RelBuilder;
+
+import org.immutables.value.Value;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/** Rule that re-orders a {@link Join} tree using dphyp algorithm.
+ *
+ * @see CoreRules#HYPER_GRAPH_OPTIMIZE */
+@Value.Enclosing
+public class DphypJoinReorderRule
+ extends RelRule<DphypJoinReorderRule.Config>
+ implements TransformationRule {
+
+ protected DphypJoinReorderRule(Config config) {
+ super(config);
+ }
+
+ @Override public void onMatch(RelOptRuleCall call) {
+ HyperGraph hyperGraph = call.rel(0);
+ RelBuilder relBuilder = call.builder();
+ // make all field name unique and convert the
+ // HyperEdge condition from RexInputRef to RexInputFieldName
+ hyperGraph.convertHyperEdgeCond();
+
+ // enumerate by Dphyp
+ DpHyp dpHyp = new DpHyp(hyperGraph, relBuilder, call.getMetadataQuery());
+ dpHyp.startEnumerateJoin();
+ RelNode orderedJoin = dpHyp.getBestPlan();
+ if (orderedJoin == null) {
+ return;
Review Comment:
If we get here, it means something went wrong, doesn't it? Or is this a valid scenario?
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "silundong (via GitHub)" <gi...@apache.org>.
silundong commented on code in PR #4204:
URL: https://github.com/apache/calcite/pull/4204#discussion_r1966951027
##########
core/src/main/java/org/apache/calcite/rel/rules/CoreRules.java:
##########
@@ -816,4 +816,14 @@ private CoreRules() {}
WINDOW_REDUCE_EXPRESSIONS =
ReduceExpressionsRule.WindowReduceExpressionsRule.WindowReduceExpressionsRuleConfig
.DEFAULT.toRule();
+ /** Rule that flattens a tree of {@link LogicalJoin}s
Review Comment:
Sure, I will update it.
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "zabetak (via GitHub)" <gi...@apache.org>.
zabetak closed pull request #4204: [CALCITE-6846] Support basic dphyp join reorder algorithm
URL: https://github.com/apache/calcite/pull/4204
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "rubenada (via GitHub)" <gi...@apache.org>.
rubenada commented on code in PR #4204:
URL: https://github.com/apache/calcite/pull/4204#discussion_r1979280738
##########
core/src/main/java/org/apache/calcite/rel/rules/HyperGraph.java:
##########
@@ -0,0 +1,459 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to you under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.calcite.rel.rules;
+
+import org.apache.calcite.linq4j.Ord;
+import org.apache.calcite.plan.RelOptCluster;
+import org.apache.calcite.plan.RelTraitSet;
+import org.apache.calcite.rel.AbstractRelNode;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.RelWriter;
+import org.apache.calcite.rel.core.JoinRelType;
+import org.apache.calcite.rel.logical.LogicalProject;
+import org.apache.calcite.rel.type.RelDataType;
+import org.apache.calcite.rel.type.RelDataTypeField;
+import org.apache.calcite.rex.RexBiVisitor;
+import org.apache.calcite.rex.RexInputRef;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.rex.RexShuttle;
+import org.apache.calcite.rex.RexUtil;
+import org.apache.calcite.rex.RexVariable;
+import org.apache.calcite.rex.RexVisitor;
+
+import com.google.common.collect.ImmutableList;
+
+import org.checkerframework.checker.nullness.qual.Nullable;
+
+import java.util.ArrayList;
+import java.util.BitSet;
+import java.util.HashMap;
+import java.util.List;
+import java.util.stream.Collectors;
+
+import static com.google.common.base.Preconditions.checkArgument;
+
+/**
+ * HyperGraph represents a join graph.
+ */
+public class HyperGraph extends AbstractRelNode {
+
+ private final List<RelNode> inputs;
+
+ @SuppressWarnings("HidingField")
+ private final RelDataType rowType;
+
+ private final List<HyperEdge> edges;
+
+ // record the indices of complex hyper edges in the 'edges'
+ private final BitSet complexEdgesBitmap;
+
+ /**
+ * For the HashMap fields, key is the bitmap for inputs,
+ * value is the hyper edge bitmap in edges.
+ */
+ // record which hyper edges have been used by the enumerated csg-cmp pairs
+ private final HashMap<Long, BitSet> ccpUsedEdgesMap;
+
+ private final HashMap<Long, BitSet> simpleEdgesMap;
+
+ private final HashMap<Long, BitSet> complexEdgesMap;
+
+ // node bitmap overlaps edge's leftNodeBits or rightNodeBits, but does not completely cover
+ private final HashMap<Long, BitSet> overlapEdgesMap;
+
+ protected HyperGraph(RelOptCluster cluster,
+ RelTraitSet traitSet,
+ List<RelNode> inputs,
+ List<HyperEdge> edges,
+ RelDataType rowType) {
+ super(cluster, traitSet);
+ this.inputs = inputs;
Review Comment:
Probably it'll be wise to make a defensive copy of the lists of inputs and edges, just in case.
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "rubenada (via GitHub)" <gi...@apache.org>.
rubenada commented on code in PR #4204:
URL: https://github.com/apache/calcite/pull/4204#discussion_r1979273034
##########
core/src/main/java/org/apache/calcite/rel/rules/DphypJoinReorderRule.java:
##########
@@ -0,0 +1,86 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to you under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.calcite.rel.rules;
+
+import org.apache.calcite.plan.RelOptRuleCall;
+import org.apache.calcite.plan.RelRule;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.core.Join;
+import org.apache.calcite.rex.RexBuilder;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.tools.RelBuilder;
+
+import org.immutables.value.Value;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/** Rule that re-orders a {@link Join} tree using dphyp algorithm.
+ *
+ * @see CoreRules#HYPER_GRAPH_OPTIMIZE */
+@Value.Enclosing
+public class DphypJoinReorderRule
+ extends RelRule<DphypJoinReorderRule.Config>
+ implements TransformationRule {
+
+ protected DphypJoinReorderRule(Config config) {
+ super(config);
+ }
+
+ @Override public void onMatch(RelOptRuleCall call) {
+ HyperGraph hyperGraph = call.rel(0);
+ RelBuilder relBuilder = call.builder();
+ // make all field name unique and convert the
+ // HyperEdge condition from RexInputRef to RexInputFieldName
+ hyperGraph.convertHyperEdgeCond();
Review Comment:
I think this call over here is a bit weird (it shouldn't be the rule's responsibility to "initialize" the hyperGraph), what about calling this method inside the DpHyp constructor (to make sure we never about this step)
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "rubenada (via GitHub)" <gi...@apache.org>.
rubenada commented on code in PR #4204:
URL: https://github.com/apache/calcite/pull/4204#discussion_r1979271096
##########
core/src/main/java/org/apache/calcite/rel/rules/DpHyp.java:
##########
@@ -0,0 +1,181 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to you under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.calcite.rel.rules;
+
+import org.apache.calcite.plan.RelOptCost;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.core.JoinRelType;
+import org.apache.calcite.rel.metadata.RelMetadataQuery;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.tools.RelBuilder;
+
+import org.checkerframework.checker.nullness.qual.Nullable;
+
+import java.util.HashMap;
+import java.util.List;
+
+/**
+ * The core process of dphyp enumeration algorithm.
+ */
+public class DpHyp {
+
+ private HyperGraph hyperGraph;
+
+ private HashMap<Long, RelNode> dpTable;
+
+ private RelBuilder builder;
+
+ private RelMetadataQuery mq;
+
+ public DpHyp(HyperGraph hyperGraph, RelBuilder builder, RelMetadataQuery relMetadataQuery) {
+ this.hyperGraph = hyperGraph;
+ this.dpTable = new HashMap<>();
+ this.builder = builder;
+ this.mq = relMetadataQuery;
+ }
+
+ public void startEnumerateJoin() {
Review Comment:
IMO the methods of this class (except the "obvious" ones like `getBestPlan` or `chooseBetterPlan`) should have a javadoc describing their intent.
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "silundong (via GitHub)" <gi...@apache.org>.
silundong commented on PR #4204:
URL: https://github.com/apache/calcite/pull/4204#issuecomment-2673205057
> Some parameters might need to be checked whether they are NULL or undergo active type conversion.
Thank you, I will update it.
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "mihaibudiu (via GitHub)" <gi...@apache.org>.
mihaibudiu commented on PR #4204:
URL: https://github.com/apache/calcite/pull/4204#issuecomment-2672489874
Is this ready for review?
If not, please mark as draft.
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "silundong (via GitHub)" <gi...@apache.org>.
silundong commented on PR #4204:
URL: https://github.com/apache/calcite/pull/4204#issuecomment-2687540002
@rubenada Thank you very much for your review!
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "rubenada (via GitHub)" <gi...@apache.org>.
rubenada commented on code in PR #4204:
URL: https://github.com/apache/calcite/pull/4204#discussion_r1979282835
##########
core/src/main/java/org/apache/calcite/rel/rules/HyperGraph.java:
##########
@@ -0,0 +1,459 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to you under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.calcite.rel.rules;
+
+import org.apache.calcite.linq4j.Ord;
+import org.apache.calcite.plan.RelOptCluster;
+import org.apache.calcite.plan.RelTraitSet;
+import org.apache.calcite.rel.AbstractRelNode;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.RelWriter;
+import org.apache.calcite.rel.core.JoinRelType;
+import org.apache.calcite.rel.logical.LogicalProject;
+import org.apache.calcite.rel.type.RelDataType;
+import org.apache.calcite.rel.type.RelDataTypeField;
+import org.apache.calcite.rex.RexBiVisitor;
+import org.apache.calcite.rex.RexInputRef;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.rex.RexShuttle;
+import org.apache.calcite.rex.RexUtil;
+import org.apache.calcite.rex.RexVariable;
+import org.apache.calcite.rex.RexVisitor;
+
+import com.google.common.collect.ImmutableList;
+
+import org.checkerframework.checker.nullness.qual.Nullable;
+
+import java.util.ArrayList;
+import java.util.BitSet;
+import java.util.HashMap;
+import java.util.List;
+import java.util.stream.Collectors;
+
+import static com.google.common.base.Preconditions.checkArgument;
+
+/**
+ * HyperGraph represents a join graph.
+ */
+public class HyperGraph extends AbstractRelNode {
+
+ private final List<RelNode> inputs;
+
+ @SuppressWarnings("HidingField")
+ private final RelDataType rowType;
+
+ private final List<HyperEdge> edges;
+
+ // record the indices of complex hyper edges in the 'edges'
+ private final BitSet complexEdgesBitmap;
+
+ /**
+ * For the HashMap fields, key is the bitmap for inputs,
+ * value is the hyper edge bitmap in edges.
+ */
+ // record which hyper edges have been used by the enumerated csg-cmp pairs
+ private final HashMap<Long, BitSet> ccpUsedEdgesMap;
+
+ private final HashMap<Long, BitSet> simpleEdgesMap;
+
+ private final HashMap<Long, BitSet> complexEdgesMap;
+
+ // node bitmap overlaps edge's leftNodeBits or rightNodeBits, but does not completely cover
+ private final HashMap<Long, BitSet> overlapEdgesMap;
+
+ protected HyperGraph(RelOptCluster cluster,
+ RelTraitSet traitSet,
+ List<RelNode> inputs,
+ List<HyperEdge> edges,
+ RelDataType rowType) {
+ super(cluster, traitSet);
+ this.inputs = inputs;
+ this.edges = edges;
+ this.rowType = rowType;
+ this.complexEdgesBitmap = new BitSet();
+ for (int i = 0; i < edges.size(); i++) {
+ if (!edges.get(i).isSimple()) {
+ complexEdgesBitmap.set(i);
+ }
+ }
+ this.ccpUsedEdgesMap = new HashMap<>();
+ this.simpleEdgesMap = new HashMap<>();
+ this.complexEdgesMap = new HashMap<>();
+ this.overlapEdgesMap = new HashMap<>();
+ }
+
+ protected HyperGraph(RelOptCluster cluster,
+ RelTraitSet traitSet,
+ List<RelNode> inputs,
+ List<HyperEdge> edges,
+ RelDataType rowType,
+ BitSet complexEdgesBitmap,
+ HashMap<Long, BitSet> ccpUsedEdgesMap,
+ HashMap<Long, BitSet> simpleEdgesMap,
+ HashMap<Long, BitSet> complexEdgesMap,
+ HashMap<Long, BitSet> overlapEdgesMap) {
+ super(cluster, traitSet);
+ this.inputs = inputs;
+ this.edges = edges;
+ this.rowType = rowType;
+ this.complexEdgesBitmap = complexEdgesBitmap;
+ this.ccpUsedEdgesMap = ccpUsedEdgesMap;
+ this.simpleEdgesMap = simpleEdgesMap;
+ this.complexEdgesMap = complexEdgesMap;
+ this.overlapEdgesMap = overlapEdgesMap;
+ }
+
+ @Override public RelNode copy(RelTraitSet traitSet, List<RelNode> inputs) {
+ return new HyperGraph(
+ getCluster(),
+ traitSet,
+ inputs,
+ edges,
+ rowType,
+ complexEdgesBitmap,
Review Comment:
Shouldn't we pass here copies of the maps, instead of the maps themselves?
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "rubenada (via GitHub)" <gi...@apache.org>.
rubenada commented on code in PR #4204:
URL: https://github.com/apache/calcite/pull/4204#discussion_r1979281772
##########
core/src/main/java/org/apache/calcite/rel/rules/HyperGraph.java:
##########
@@ -0,0 +1,459 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to you under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.calcite.rel.rules;
+
+import org.apache.calcite.linq4j.Ord;
+import org.apache.calcite.plan.RelOptCluster;
+import org.apache.calcite.plan.RelTraitSet;
+import org.apache.calcite.rel.AbstractRelNode;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.RelWriter;
+import org.apache.calcite.rel.core.JoinRelType;
+import org.apache.calcite.rel.logical.LogicalProject;
+import org.apache.calcite.rel.type.RelDataType;
+import org.apache.calcite.rel.type.RelDataTypeField;
+import org.apache.calcite.rex.RexBiVisitor;
+import org.apache.calcite.rex.RexInputRef;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.rex.RexShuttle;
+import org.apache.calcite.rex.RexUtil;
+import org.apache.calcite.rex.RexVariable;
+import org.apache.calcite.rex.RexVisitor;
+
+import com.google.common.collect.ImmutableList;
+
+import org.checkerframework.checker.nullness.qual.Nullable;
+
+import java.util.ArrayList;
+import java.util.BitSet;
+import java.util.HashMap;
+import java.util.List;
+import java.util.stream.Collectors;
+
+import static com.google.common.base.Preconditions.checkArgument;
+
+/**
+ * HyperGraph represents a join graph.
+ */
+public class HyperGraph extends AbstractRelNode {
+
+ private final List<RelNode> inputs;
+
+ @SuppressWarnings("HidingField")
+ private final RelDataType rowType;
+
+ private final List<HyperEdge> edges;
+
+ // record the indices of complex hyper edges in the 'edges'
+ private final BitSet complexEdgesBitmap;
Review Comment:
Could this be an ImmutableBitSet (build on the constructor)?
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "rubenada (via GitHub)" <gi...@apache.org>.
rubenada commented on code in PR #4204:
URL: https://github.com/apache/calcite/pull/4204#discussion_r1979278175
##########
core/src/main/java/org/apache/calcite/rel/rules/HyperEdge.java:
##########
@@ -0,0 +1,82 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to you under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.calcite.rel.rules;
+
+import org.apache.calcite.rel.core.JoinRelType;
+import org.apache.calcite.rex.RexNode;
+
+/**
+ * Edge in HyperGraph, that represents a join predicate.
+ */
+public class HyperEdge {
+
+ private long leftNodeBits;
+
+ private long rightNodeBits;
+
+ private JoinRelType joinType;
+
+ private RexNode condition;
+
+ public HyperEdge(long leftNodeBits, long rightNodeBits, JoinRelType joinType, RexNode condition) {
+ this.leftNodeBits = leftNodeBits;
+ this.rightNodeBits = rightNodeBits;
+ this.joinType = joinType;
+ this.condition = condition;
+ }
+
+ public long getNodeBitmap() {
+ return leftNodeBits | rightNodeBits;
+ }
+
+ public long getLeftNodeBitmap() {
+ return leftNodeBits;
+ }
+
+ public long getRightNodeBitmap() {
+ return rightNodeBits;
+ }
+
+ // hyperedge (u, v) is simple if |u| = |v| = 1
+ public boolean isSimple() {
+ boolean leftSimple = (leftNodeBits & (leftNodeBits - 1)) == 0;
+ boolean rightSimple = (rightNodeBits & (rightNodeBits - 1)) == 0;
+ return leftSimple && rightSimple;
+ }
+
+ public JoinRelType getJoinType() {
+ return joinType;
+ }
+
+ public RexNode getCondition() {
+ return condition;
+ }
+
+ @Override public String toString() {
+ StringBuilder sb = new StringBuilder();
+ sb.append(LongBitmap.printBitmap(leftNodeBits))
+ .append("——").append(joinType).append("——")
+ .append(LongBitmap.printBitmap(rightNodeBits));
+ return sb.toString();
+ }
+
+ // before starting dphyp, replace RexInputRef to RexInputFieldName
+ public void replaceCondition(RexNode fieldNameCond) {
Review Comment:
I'm not a fan of this type of manipulations, but I understand it's a pragmatic choice; but I'd suggest to reduce the method's visibility (package-private?)
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "rubenada (via GitHub)" <gi...@apache.org>.
rubenada commented on PR #4204:
URL: https://github.com/apache/calcite/pull/4204#issuecomment-2708379302
@silundong could you please take a look at Alessandro's minor comments in the Jira 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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "silundong (via GitHub)" <gi...@apache.org>.
silundong commented on PR #4204:
URL: https://github.com/apache/calcite/pull/4204#issuecomment-2709342043
> @silundong could you please take a look at Alessandro's minor comments in the Jira ticket?
Sure, I will indicate in HyperGraph and HyperEdge that the code is referenced from Apache Doris. Is that ok?
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "rubenada (via GitHub)" <gi...@apache.org>.
rubenada commented on code in PR #4204:
URL: https://github.com/apache/calcite/pull/4204#discussion_r1966836604
##########
core/src/main/java/org/apache/calcite/rel/rules/DpHyp.java:
##########
@@ -0,0 +1,179 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to you under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.calcite.rel.rules;
+
+import org.apache.calcite.plan.RelOptCost;
+import org.apache.calcite.rel.RelNode;
+import org.apache.calcite.rel.core.JoinRelType;
+import org.apache.calcite.rel.metadata.RelMetadataQuery;
+import org.apache.calcite.rex.RexNode;
+import org.apache.calcite.tools.RelBuilder;
+
+import org.checkerframework.checker.nullness.qual.Nullable;
+
+import java.util.HashMap;
+import java.util.List;
+
+/**
+ * The core process of dphyp enumeration algorithm.
+ */
+public class DpHyp {
+
+ private HyperGraph hyperGraph;
+
+ private HashMap<Long, RelNode> dpTable;
+
+ private RelBuilder builder;
+
+ private RelMetadataQuery mq;
+
+ public DpHyp(HyperGraph hyperGraph, RelBuilder builder, RelMetadataQuery relMetadataQuery) {
+ this.hyperGraph = hyperGraph;
+ this.dpTable = new HashMap<>();
+ this.builder = builder;
+ this.mq = relMetadataQuery;
+ }
+
+ public void startEnumerateJoin() {
+ int size = hyperGraph.getInputs().size();
+ for (int i = 0; i < size; i++) {
+ long singleNode = LongBitmap.newBitmap(i);
+ dpTable.put(singleNode, hyperGraph.getInput(i));
+ hyperGraph.initEdgeBitMap(singleNode);
+ }
+
+ // start enumerating from the second to last
+ for (int i = size - 2; i >= 0; i--) {
+ long csg = LongBitmap.newBitmap(i);
+ long forbidden = csg - 1;
+ emitCsg(csg);
+ enumerateCsgRec(csg, forbidden);
+ }
+ }
+
+ private void emitCsg(long csg) {
+ long forbidden = csg | LongBitmap.getBvBitmap(csg);
+ long neighbors = hyperGraph.getNeighborBitmap(csg, forbidden);
+
+ LongBitmap.ReverseIterator reverseIterator = new LongBitmap.ReverseIterator(neighbors);
+ for (long cmp : reverseIterator) {
+ List<HyperEdge> edges = hyperGraph.connectCsgCmp(csg, cmp);
+ if (!edges.isEmpty()) {
+ emitCsgCmp(csg, cmp, edges);
+ }
+ // forbidden the nodes that smaller than current cmp when extend cmp, e.g.
+ // neighbors = {t1, t2}, t1 and t2 are connected.
+ // when extented t2, we will get (t1, t2)
+ // when extented t1, we will get (t1, t2) repeated
+ long newForbidden =
+ (cmp | LongBitmap.getBvBitmap(cmp)) & neighbors;
+ newForbidden = newForbidden | forbidden;
+ enumerateCmpRec(csg, cmp, newForbidden);
+ }
+ }
+
+ private void enumerateCsgRec(long csg, long forbidden) {
+ long neighbors = hyperGraph.getNeighborBitmap(csg, forbidden);
+ LongBitmap.SubsetIterator subsetIterator = new LongBitmap.SubsetIterator(neighbors);
+ for (long subNeighbor : subsetIterator) {
+ hyperGraph.updateEdgesForUnion(csg, subNeighbor);
+ long newCsg = csg | subNeighbor;
+ if (dpTable.containsKey(newCsg)) {
+ emitCsg(newCsg);
+ }
+ }
+ long newForbidden = forbidden | neighbors;
+ subsetIterator.reset();
+ for (long subNeighbor : subsetIterator) {
+ long newCsg = csg | subNeighbor;
+ enumerateCsgRec(newCsg, newForbidden);
+ }
+ }
+
+ private void enumerateCmpRec(long csg, long cmp, long forbidden) {
+ long neighbors = hyperGraph.getNeighborBitmap(cmp, forbidden);
+ LongBitmap.SubsetIterator subsetIterator = new LongBitmap.SubsetIterator(neighbors);
+ for (long subNeighbor : subsetIterator) {
+ long newCmp = cmp | subNeighbor;
+ hyperGraph.updateEdgesForUnion(cmp, subNeighbor);
+ if (dpTable.containsKey(newCmp)) {
+ List<HyperEdge> edges = hyperGraph.connectCsgCmp(csg, newCmp);
+ if (!edges.isEmpty()) {
+ emitCsgCmp(csg, newCmp, edges);
+ }
+ }
+ }
+ long newForbidden = forbidden | neighbors;
+ subsetIterator.reset();
+ for (long subNeighbor : subsetIterator) {
+ long newCmp = cmp | subNeighbor;
+ enumerateCmpRec(csg, newCmp, newForbidden);
+ }
+ }
+
+ private void emitCsgCmp(long csg, long cmp, List<HyperEdge> edges) {
+ RelNode child1 = dpTable.get(csg);
+ RelNode child2 = dpTable.get(cmp);
+ if (child1 == null || child2 == null) {
+ throw new IllegalArgumentException(
+ "csg and cmp were not enumerated in the previous dp process");
+ }
+
+ JoinRelType joinType = hyperGraph.extractJoinType(edges);
+ if (joinType == null) {
+ return;
+ }
+ RexNode joinCond1 = hyperGraph.extractJoinCond(child1, child2, edges);
+ RelNode newPlan1 = builder
+ .push(child1)
+ .push(child2)
+ .join(joinType, joinCond1)
+ .build();
+
+ // swap left and right
+ RexNode joinCond2 = hyperGraph.extractJoinCond(child2, child1, edges);
+ RelNode newPlan2 = builder
+ .push(child2)
+ .push(child1)
+ .join(joinType, joinCond2)
+ .build();
+ RelNode winPlan = chooseBetterPlan(newPlan1, newPlan2);
+
+ RelNode oriPlan = dpTable.get(csg | cmp);
+ if (oriPlan != null) {
+ winPlan = chooseBetterPlan(winPlan, oriPlan);
+ }
+ dpTable.put(csg | cmp, winPlan);
+ }
+
+ public @Nullable RelNode getBestPlan() {
+ int size = hyperGraph.getInputs().size();
+ long wholeGraph = LongBitmap.newBitmapBetween(0, size);
+ return dpTable.get(wholeGraph);
+ }
+
+ private RelNode chooseBetterPlan(RelNode plan1, RelNode plan2) {
+ RelOptCost cost1 = mq.getCumulativeCost(plan1);
+ RelOptCost cost2 = mq.getCumulativeCost(plan2);
+ if (cost1 == null || cost2 == null) {
Review Comment:
if we have one null cost and one non-null cost, shouldn't we return the non-null one?
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
Re: [PR] [CALCITE-6846] Support basic dphyp join reorder algorithm [calcite]
Posted by "silundong (via GitHub)" <gi...@apache.org>.
silundong commented on PR #4204:
URL: https://github.com/apache/calcite/pull/4204#issuecomment-2677302475
> This is a great contribution @silundong. Just out of curiosity, have you tested locally what happens if you add the new HyperGraph rules into the "default rules" (e.g. RelOptRules#BASE_RULES, or Programs#RULE_SET) and execute Calcite tests? Do you get any any suspicious error (except for the expected plan changes regarding Join-ordering that the new rules may generate)?
Thank you very much for your recognition. I did not add it to the "default rules" (e.g. RelOptRules#BASE_RULES, or Programs#RULE_SET). However, in other projects, I have integrated the Calcite parsing and optimization module and added HyperGraph rules. It has worked without exceptions under TPC-DS.
--
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: commits-unsubscribe@calcite.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org