mihaibudiu commented on code in PR #4392: URL: https://github.com/apache/calcite/pull/4392#discussion_r2110407284
########## core/src/main/java/org/apache/calcite/rel/rules/ConflictDetectionHelper.java: ########## @@ -0,0 +1,216 @@ +/* + * 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 com.google.common.collect.ImmutableMap; + +import java.util.HashMap; +import java.util.List; +import java.util.Map; + +/** + * Conflict detection algorithm based on CD-C. More details are in paper: + * <a href="https://15721.courses.cs.cmu.edu/spring2019/papers/23-optimizer2/p493-moerkotte.pdf";> + * On the correct and complete enumeration of the core search space</a>. + */ +public class ConflictDetectionHelper { + + private ConflictDetectionHelper() { + } + + private static final ImmutableMap<JoinRelType, Integer> INDEX_OF_TABLE = + ImmutableMap.<JoinRelType, Integer>builder() Review Comment: the tables in the paper have 7 operators, but it looks like you are omitting cross-product and group join (first and last). I would add this in the comment above. ########## core/src/main/java/org/apache/calcite/rel/rules/ConflictDetectionHelper.java: ########## @@ -0,0 +1,216 @@ +/* + * 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 com.google.common.collect.ImmutableMap; + +import java.util.HashMap; +import java.util.List; +import java.util.Map; + +/** + * Conflict detection algorithm based on CD-C. More details are in paper: + * <a href="https://15721.courses.cs.cmu.edu/spring2019/papers/23-optimizer2/p493-moerkotte.pdf";> + * On the correct and complete enumeration of the core search space</a>. + */ +public class ConflictDetectionHelper { + + private ConflictDetectionHelper() { + } + + private static final ImmutableMap<JoinRelType, Integer> INDEX_OF_TABLE = + ImmutableMap.<JoinRelType, Integer>builder() + .put(JoinRelType.INNER, 0).put(JoinRelType.SEMI, 1).put(JoinRelType.ANTI, 2) + .put(JoinRelType.LEFT, 3).put(JoinRelType.FULL, 4).build(); + + // TODO: when special attribute is null rejecting, left/full join is + // associative/left_asscom/right_asscom. See table2/3 in paper Review Comment: this is table 2, the next 2 tables are from table 3 in the paper, why not be more explicit in the comment? ########## core/src/main/java/org/apache/calcite/rel/rules/ConflictDetectionHelper.java: ########## @@ -0,0 +1,216 @@ +/* + * 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 com.google.common.collect.ImmutableMap; + +import java.util.HashMap; +import java.util.List; +import java.util.Map; + +/** + * Conflict detection algorithm based on CD-C. More details are in paper: + * <a href="https://15721.courses.cs.cmu.edu/spring2019/papers/23-optimizer2/p493-moerkotte.pdf";> + * On the correct and complete enumeration of the core search space</a>. + */ +public class ConflictDetectionHelper { + + private ConflictDetectionHelper() { + } + + private static final ImmutableMap<JoinRelType, Integer> INDEX_OF_TABLE = + ImmutableMap.<JoinRelType, Integer>builder() + .put(JoinRelType.INNER, 0).put(JoinRelType.SEMI, 1).put(JoinRelType.ANTI, 2) + .put(JoinRelType.LEFT, 3).put(JoinRelType.FULL, 4).build(); + + // TODO: when special attribute is null rejecting, left/full join is + // associative/left_asscom/right_asscom. See table2/3 in paper + private static final boolean[][] ASSOCIATIVE_TABLE = { + // inner-B semi-B anti-B left-B full-B + /* inner-A */ {true, true, true, true, false}, + /* semi-A */ {false, false, false, false, false}, + /* anti-A */ {false, false, false, false, false}, + /* left-A */ {false, false, false, false, false}, + /* full-A */ {false, false, false, false, false}}; + + private static final boolean[][] LEFT_ASSCOM_TABLE = { + // inner-B semi-B anti-B left-B full-B + /* inner-A */ {true, true, true, true, false}, + /* semi-A */ {true, true, true, true, false}, + /* anti-A */ {true, true, true, true, false}, + /* left-A */ {true, true, true, true, false}, + /* full-A */ {false, false, false, false, false}}; + + private static final boolean[][] RIGHT_ASSCOM_TABLE = { + // inner-B semi-B anti-B left-B full-B + /* inner-A */ {true, false, false, false, false}, + /* semi-A */ {false, false, false, false, false}, + /* anti-A */ {false, false, false, false, false}, + /* left-A */ {false, false, false, false, false}, + /* full-A */ {false, false, false, false, false}}; + + /** + * Make conflict rules for join operator based on CD-C. + * + * @param leftSubEdges left sub operators + * @param rightSubEdges right sub operators + * @param joinType current join operator + * @return a map from table set1 to table set2 that if set1 and the tables in the current join + * operator have an intersection, then set2 must be included in the current join operator + */ + public static Map<Long, Long> makeConflictRules( Review Comment: does this method belong to the hypergraph? it could take a join node as an argument. ########## core/src/main/java/org/apache/calcite/rel/rules/ConflictDetectionHelper.java: ########## @@ -0,0 +1,216 @@ +/* + * 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 com.google.common.collect.ImmutableMap; + +import java.util.HashMap; +import java.util.List; +import java.util.Map; + +/** + * Conflict detection algorithm based on CD-C. More details are in paper: + * <a href="https://15721.courses.cs.cmu.edu/spring2019/papers/23-optimizer2/p493-moerkotte.pdf";> + * On the correct and complete enumeration of the core search space</a>. + */ +public class ConflictDetectionHelper { + + private ConflictDetectionHelper() { + } + + private static final ImmutableMap<JoinRelType, Integer> INDEX_OF_TABLE = + ImmutableMap.<JoinRelType, Integer>builder() + .put(JoinRelType.INNER, 0).put(JoinRelType.SEMI, 1).put(JoinRelType.ANTI, 2) + .put(JoinRelType.LEFT, 3).put(JoinRelType.FULL, 4).build(); + + // TODO: when special attribute is null rejecting, left/full join is + // associative/left_asscom/right_asscom. See table2/3 in paper + private static final boolean[][] ASSOCIATIVE_TABLE = { + // inner-B semi-B anti-B left-B full-B + /* inner-A */ {true, true, true, true, false}, + /* semi-A */ {false, false, false, false, false}, + /* anti-A */ {false, false, false, false, false}, + /* left-A */ {false, false, false, false, false}, + /* full-A */ {false, false, false, false, false}}; + + private static final boolean[][] LEFT_ASSCOM_TABLE = { + // inner-B semi-B anti-B left-B full-B + /* inner-A */ {true, true, true, true, false}, + /* semi-A */ {true, true, true, true, false}, + /* anti-A */ {true, true, true, true, false}, + /* left-A */ {true, true, true, true, false}, + /* full-A */ {false, false, false, false, false}}; + + private static final boolean[][] RIGHT_ASSCOM_TABLE = { + // inner-B semi-B anti-B left-B full-B + /* inner-A */ {true, false, false, false, false}, + /* semi-A */ {false, false, false, false, false}, + /* anti-A */ {false, false, false, false, false}, + /* left-A */ {false, false, false, false, false}, + /* full-A */ {false, false, false, false, false}}; + + /** + * Make conflict rules for join operator based on CD-C. + * + * @param leftSubEdges left sub operators + * @param rightSubEdges right sub operators + * @param joinType current join operator + * @return a map from table set1 to table set2 that if set1 and the tables in the current join + * operator have an intersection, then set2 must be included in the current join operator + */ + public static Map<Long, Long> makeConflictRules( + List<HyperEdge> leftSubEdges, + List<HyperEdge> rightSubEdges, + JoinRelType joinType) { + Map<Long, Long> conflictRules = new HashMap<>(); + for (HyperEdge leftSubEdge : leftSubEdges) { + if (!isAssociative(leftSubEdge.getJoinType(), joinType)) { + if (leftSubEdge.getLeftNodeUsedInPredicate() != 0) { + conflictRules.merge( + leftSubEdge.getInitialRightNodeBits(), + leftSubEdge.getLeftNodeUsedInPredicate(), + (oldValue, newValue) -> oldValue | newValue); + } else { + conflictRules.merge( + leftSubEdge.getInitialRightNodeBits(), + leftSubEdge.getInitialLeftNodeBits(), + (oldValue, newValue) -> oldValue | newValue); + } + + } + if (!isLeftAsscom(leftSubEdge.getJoinType(), joinType)) { + if (leftSubEdge.getRightNodeUsedInPredicate() != 0) { + conflictRules.merge( + leftSubEdge.getInitialLeftNodeBits(), + leftSubEdge.getRightNodeUsedInPredicate(), + (oldValue, newValue) -> oldValue | newValue); + } else { + conflictRules.merge( + leftSubEdge.getInitialLeftNodeBits(), + leftSubEdge.getInitialRightNodeBits(), + (oldValue, newValue) -> oldValue | newValue); + } + } + } + + for (HyperEdge rightSubEdge : rightSubEdges) { + if (!isAssociative(joinType, rightSubEdge.getJoinType())) { + if (rightSubEdge.getRightNodeUsedInPredicate() != 0) { + conflictRules.merge( + rightSubEdge.getInitialLeftNodeBits(), + rightSubEdge.getRightNodeUsedInPredicate(), + (oldValue, newValue) -> oldValue | newValue); + } else { + conflictRules.merge( + rightSubEdge.getInitialLeftNodeBits(), + rightSubEdge.getInitialRightNodeBits(), + (oldValue, newValue) -> oldValue | newValue); + } + } + if (!isRightAsscom(joinType, rightSubEdge.getJoinType())) { + if (rightSubEdge.getLeftNodeUsedInPredicate() != 0) { + conflictRules.merge( + rightSubEdge.getInitialRightNodeBits(), + rightSubEdge.getLeftNodeUsedInPredicate(), + (oldValue, newValue) -> oldValue | newValue); + } else { + conflictRules.merge( + rightSubEdge.getInitialRightNodeBits(), + rightSubEdge.getInitialLeftNodeBits(), + (oldValue, newValue) -> oldValue | newValue); + } + } + } + return conflictRules; + } + + /** + * For conflict rule <code>T1 -> T2</code>, if T1 and tes have intersection, we can add T2 + * into tes and remove this rule. See section 5.5 in paper. + * + * @param tes tes + * @param conflictRulesAfterAbsorb conflict rules after absorbing + * @param initialconflictRules conflict rules before absorbing + * @return tes after absorbing conflict rules + */ + public static long absorbConflictRulesIntoTES( + long tes, + Map<Long, Long> conflictRulesAfterAbsorb, + Map<Long, Long> initialconflictRules) { + for (Map.Entry<Long, Long> rule : initialconflictRules.entrySet()) { + if (LongBitmap.isOverlap(tes, rule.getKey())) { + tes |= rule.getValue(); + continue; + } + conflictRulesAfterAbsorb.put(rule.getKey(), rule.getValue()); + } + return tes; + } + + /** + * Check whether the operator is applicable through the conflict rule. + * + * @param subGraph table set of the current join operator Review Comment: there is no "current join operator" in this context, only the caller has it That's why this should also probably be a method of the hypergraph class. ########## core/src/main/java/org/apache/calcite/rel/rules/HyperGraph.java: ########## @@ -401,69 +453,67 @@ public RexNode extractJoinCond(RelNode left, RelNode right, List<HyperEdge> edge }; for (HyperEdge edge : edges) { - RexNode inputRefCond = edge.getCondition().accept(inputName2InputRefShuttle); + RexNode inputRefCond = edge.getCondition().accept(shuttle); joinConds.add(inputRefCond); } - return RexUtil.composeConjunction(left.getCluster().getRexBuilder(), joinConds); + return RexUtil.composeConjunction(getCluster().getRexBuilder(), joinConds); } /** - * Before starting enumeration, add Project on every input, make all field name unique. - * Convert the HyperEdge condition from RexInputRef to RexInputFieldName + * Restore the projection order of the final result to the original plan. + * + * @param resultOrder the node order of the final result + * @param rowTypeList rowType of the final result + * @return list of RexInputRef */ - public void convertHyperEdgeCond(RelBuilder builder) { - 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++; + public List<RexNode> restoreProjectionOrder( + ImmutableList<Integer> resultOrder, + List<RelDataTypeField> rowTypeList) { + Map<Integer, Integer> relativePositionInNode = new HashMap<>(); + int fieldCount = 0; + for (int resultIndex : resultOrder) { + relativePositionInNode.put(resultIndex, fieldCount); + if (!LongBitmap.isOverlap(notProjectInputs, LongBitmap.newBitmap(resultIndex))) { + fieldCount += inputs.get(resultIndex).getRowType().getFieldCount(); } - - builder.push(input) - .project(projects, names, true); - replaceInput(nodeIndex, builder.build()); } - - RexShuttle inputRef2inputNameShuttle = new RexShuttle() { - @Override public RexNode visitInputRef(RexInputRef inputRef) { - int index = inputRef.getIndex(); - return new RexInputFieldName( - fieldList.get(index).getName(), - fieldList.get(index).getType()); + List<RexNode> projects = new ArrayList<>(); + for (int inputIndex = 0; inputIndex < inputs.size(); inputIndex++) { + if (LongBitmap.isOverlap(notProjectInputs, LongBitmap.newBitmap(inputIndex))) { + continue; } - }; - for (int i = 0; i < edges.size(); i++) { - HyperEdge edge = edges.get(i); - RexNode convertCond = edge.getCondition().accept(inputRef2inputNameShuttle); - HyperEdge convertEdge = - new HyperEdge( - edge.getLeftNodeBitmap(), - edge.getRightNodeBitmap(), - edge.getJoinType(), - convertCond); - edges.set(i, convertEdge); + for (int i = 0; i < inputs.get(inputIndex).getRowType().getFieldCount(); i++) { + Integer fieldOffset = relativePositionInNode.get(inputIndex); + if (fieldOffset == null) { + throw new DpHyp.DphypOrHyperGraphException( + "The result order loses the " + inputIndex + "-th input"); Review Comment: looses? is this an assertion failure? Then you should probably use the AssertionFailure exception. ########## core/src/main/java/org/apache/calcite/rel/rules/HyperGraph.java: ########## @@ -369,25 +388,58 @@ private static boolean isOverlapEdge(HyperEdge edge, long subset) { return joinType; } - public RexNode extractJoinCond(RelNode left, RelNode right, List<HyperEdge> edges) { + /** + * Restore join condition from hyper edges. Review Comment: I think that a better description is "build an RexNode expression for the predicate corresponding to a set of hyperedges". ########## core/src/main/java/org/apache/calcite/rel/rules/ConflictDetectionHelper.java: ########## @@ -0,0 +1,215 @@ +/* + * 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 com.google.common.collect.ImmutableMap; + +import java.util.HashMap; +import java.util.List; +import java.util.Map; + +/** + * Conflict detection algorithm based on CD-C. More details are in paper: + * On the correct and complete enumeration of the core search space. + */ +public class ConflictDetectionHelper { + + private ConflictDetectionHelper() { + } + + private static final ImmutableMap<JoinRelType, Integer> INDEX_OF_TABLE = + ImmutableMap.<JoinRelType, Integer>builder() + .put(JoinRelType.INNER, 0).put(JoinRelType.SEMI, 1).put(JoinRelType.ANTI, 2) + .put(JoinRelType.LEFT, 3).put(JoinRelType.FULL, 4).build(); + + // TODO: when special attribute is null rejecting, left/full join is Review Comment: Instead of TODO I would write in the comment that the table here assumes that the predicate are assumed not to be null-rejecting. ########## core/src/main/java/org/apache/calcite/rel/rules/DpHyp.java: ########## @@ -37,7 +40,12 @@ public class DpHyp { private final HyperGraph hyperGraph; - private final HashMap<Long, RelNode> dpTable; + private final Map<Long, RelNode> dpTable; + + // record the node order corresponding to the best subgraph, which is used to convert + // the RexNodeAndFieldIndex in hyperedge to the RexInputRef in join condition, and permute + // final result + private final Map<Long, ImmutableList<Integer>> resultInputOrder; Review Comment: this map can become very large, is that right? is there any mechanism planned to control size explosion? ########## core/src/main/java/org/apache/calcite/rel/rules/HyperEdge.java: ########## @@ -20,42 +20,96 @@ import org.apache.calcite.rel.core.JoinRelType; import org.apache.calcite.rex.RexNode; +import java.util.HashMap; +import java.util.Map; + /** * Edge in HyperGraph, that represents a join predicate. */ @Experimental public class HyperEdge { - private final long leftNodeBits; + // equivalent to the l-tes in CD-C paper + private final long leftEndpoint; Review Comment: if these are all bitmaps, you should use a suitable bitmap class. Calcite already has a BitSet class. On second thought, using a class may be too expensive. ########## core/src/main/java/org/apache/calcite/rel/rules/ConflictDetectionHelper.java: ########## @@ -0,0 +1,216 @@ +/* + * 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 com.google.common.collect.ImmutableMap; + +import java.util.HashMap; +import java.util.List; +import java.util.Map; + +/** + * Conflict detection algorithm based on CD-C. More details are in paper: + * <a href="https://15721.courses.cs.cmu.edu/spring2019/papers/23-optimizer2/p493-moerkotte.pdf";> + * On the correct and complete enumeration of the core search space</a>. + */ +public class ConflictDetectionHelper { + + private ConflictDetectionHelper() { + } + + private static final ImmutableMap<JoinRelType, Integer> INDEX_OF_TABLE = + ImmutableMap.<JoinRelType, Integer>builder() + .put(JoinRelType.INNER, 0).put(JoinRelType.SEMI, 1).put(JoinRelType.ANTI, 2) + .put(JoinRelType.LEFT, 3).put(JoinRelType.FULL, 4).build(); + + // TODO: when special attribute is null rejecting, left/full join is + // associative/left_asscom/right_asscom. See table2/3 in paper + private static final boolean[][] ASSOCIATIVE_TABLE = { + // inner-B semi-B anti-B left-B full-B + /* inner-A */ {true, true, true, true, false}, + /* semi-A */ {false, false, false, false, false}, + /* anti-A */ {false, false, false, false, false}, + /* left-A */ {false, false, false, false, false}, + /* full-A */ {false, false, false, false, false}}; + + private static final boolean[][] LEFT_ASSCOM_TABLE = { + // inner-B semi-B anti-B left-B full-B + /* inner-A */ {true, true, true, true, false}, + /* semi-A */ {true, true, true, true, false}, + /* anti-A */ {true, true, true, true, false}, + /* left-A */ {true, true, true, true, false}, + /* full-A */ {false, false, false, false, false}}; + + private static final boolean[][] RIGHT_ASSCOM_TABLE = { + // inner-B semi-B anti-B left-B full-B + /* inner-A */ {true, false, false, false, false}, + /* semi-A */ {false, false, false, false, false}, + /* anti-A */ {false, false, false, false, false}, + /* left-A */ {false, false, false, false, false}, + /* full-A */ {false, false, false, false, false}}; + + /** + * Make conflict rules for join operator based on CD-C. + * + * @param leftSubEdges left sub operators + * @param rightSubEdges right sub operators + * @param joinType current join operator + * @return a map from table set1 to table set2 that if set1 and the tables in the current join + * operator have an intersection, then set2 must be included in the current join operator + */ + public static Map<Long, Long> makeConflictRules( + List<HyperEdge> leftSubEdges, + List<HyperEdge> rightSubEdges, + JoinRelType joinType) { + Map<Long, Long> conflictRules = new HashMap<>(); Review Comment: Can you define a class for a ConflictRule, even if it only stores a `HashMap<Long,Long>` inside? The documentation and methods of this class will make it much clearer about what about the fact that these Longs are bitmaps. Also, these ConflictRules should point to the hypergraph, and have nice toString() methods which translate indexes in the bitmap into operators in the plan. ########## core/src/main/java/org/apache/calcite/rel/rules/ConflictDetectionHelper.java: ########## @@ -0,0 +1,216 @@ +/* + * 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 com.google.common.collect.ImmutableMap; + +import java.util.HashMap; +import java.util.List; +import java.util.Map; + +/** + * Conflict detection algorithm based on CD-C. More details are in paper: + * <a href="https://15721.courses.cs.cmu.edu/spring2019/papers/23-optimizer2/p493-moerkotte.pdf";> + * On the correct and complete enumeration of the core search space</a>. + */ +public class ConflictDetectionHelper { + + private ConflictDetectionHelper() { + } + + private static final ImmutableMap<JoinRelType, Integer> INDEX_OF_TABLE = + ImmutableMap.<JoinRelType, Integer>builder() + .put(JoinRelType.INNER, 0).put(JoinRelType.SEMI, 1).put(JoinRelType.ANTI, 2) + .put(JoinRelType.LEFT, 3).put(JoinRelType.FULL, 4).build(); + + // TODO: when special attribute is null rejecting, left/full join is + // associative/left_asscom/right_asscom. See table2/3 in paper + private static final boolean[][] ASSOCIATIVE_TABLE = { + // inner-B semi-B anti-B left-B full-B + /* inner-A */ {true, true, true, true, false}, + /* semi-A */ {false, false, false, false, false}, + /* anti-A */ {false, false, false, false, false}, + /* left-A */ {false, false, false, false, false}, + /* full-A */ {false, false, false, false, false}}; + + private static final boolean[][] LEFT_ASSCOM_TABLE = { + // inner-B semi-B anti-B left-B full-B + /* inner-A */ {true, true, true, true, false}, + /* semi-A */ {true, true, true, true, false}, + /* anti-A */ {true, true, true, true, false}, + /* left-A */ {true, true, true, true, false}, + /* full-A */ {false, false, false, false, false}}; + + private static final boolean[][] RIGHT_ASSCOM_TABLE = { + // inner-B semi-B anti-B left-B full-B + /* inner-A */ {true, false, false, false, false}, + /* semi-A */ {false, false, false, false, false}, + /* anti-A */ {false, false, false, false, false}, + /* left-A */ {false, false, false, false, false}, + /* full-A */ {false, false, false, false, false}}; + + /** + * Make conflict rules for join operator based on CD-C. + * + * @param leftSubEdges left sub operators + * @param rightSubEdges right sub operators + * @param joinType current join operator + * @return a map from table set1 to table set2 that if set1 and the tables in the current join + * operator have an intersection, then set2 must be included in the current join operator + */ + public static Map<Long, Long> makeConflictRules( + List<HyperEdge> leftSubEdges, + List<HyperEdge> rightSubEdges, + JoinRelType joinType) { + Map<Long, Long> conflictRules = new HashMap<>(); + for (HyperEdge leftSubEdge : leftSubEdges) { + if (!isAssociative(leftSubEdge.getJoinType(), joinType)) { + if (leftSubEdge.getLeftNodeUsedInPredicate() != 0) { + conflictRules.merge( + leftSubEdge.getInitialRightNodeBits(), + leftSubEdge.getLeftNodeUsedInPredicate(), + (oldValue, newValue) -> oldValue | newValue); + } else { + conflictRules.merge( + leftSubEdge.getInitialRightNodeBits(), + leftSubEdge.getInitialLeftNodeBits(), + (oldValue, newValue) -> oldValue | newValue); + } + + } + if (!isLeftAsscom(leftSubEdge.getJoinType(), joinType)) { + if (leftSubEdge.getRightNodeUsedInPredicate() != 0) { + conflictRules.merge( + leftSubEdge.getInitialLeftNodeBits(), + leftSubEdge.getRightNodeUsedInPredicate(), + (oldValue, newValue) -> oldValue | newValue); + } else { + conflictRules.merge( + leftSubEdge.getInitialLeftNodeBits(), + leftSubEdge.getInitialRightNodeBits(), + (oldValue, newValue) -> oldValue | newValue); + } + } + } + + for (HyperEdge rightSubEdge : rightSubEdges) { + if (!isAssociative(joinType, rightSubEdge.getJoinType())) { + if (rightSubEdge.getRightNodeUsedInPredicate() != 0) { + conflictRules.merge( + rightSubEdge.getInitialLeftNodeBits(), + rightSubEdge.getRightNodeUsedInPredicate(), + (oldValue, newValue) -> oldValue | newValue); + } else { + conflictRules.merge( + rightSubEdge.getInitialLeftNodeBits(), + rightSubEdge.getInitialRightNodeBits(), + (oldValue, newValue) -> oldValue | newValue); + } + } + if (!isRightAsscom(joinType, rightSubEdge.getJoinType())) { + if (rightSubEdge.getLeftNodeUsedInPredicate() != 0) { + conflictRules.merge( + rightSubEdge.getInitialRightNodeBits(), + rightSubEdge.getLeftNodeUsedInPredicate(), + (oldValue, newValue) -> oldValue | newValue); + } else { + conflictRules.merge( + rightSubEdge.getInitialRightNodeBits(), + rightSubEdge.getInitialLeftNodeBits(), + (oldValue, newValue) -> oldValue | newValue); + } + } + } + return conflictRules; + } + + /** + * For conflict rule <code>T1 -> T2</code>, if T1 and tes have intersection, we can add T2 + * into tes and remove this rule. See section 5.5 in paper. + * + * @param tes tes Review Comment: at least here you should spell Total Eligibility Set. ########## core/src/main/java/org/apache/calcite/rel/rules/HyperGraph.java: ########## @@ -401,69 +453,67 @@ public RexNode extractJoinCond(RelNode left, RelNode right, List<HyperEdge> edge }; for (HyperEdge edge : edges) { - RexNode inputRefCond = edge.getCondition().accept(inputName2InputRefShuttle); + RexNode inputRefCond = edge.getCondition().accept(shuttle); joinConds.add(inputRefCond); } - return RexUtil.composeConjunction(left.getCluster().getRexBuilder(), joinConds); + return RexUtil.composeConjunction(getCluster().getRexBuilder(), joinConds); } /** - * Before starting enumeration, add Project on every input, make all field name unique. - * Convert the HyperEdge condition from RexInputRef to RexInputFieldName + * Restore the projection order of the final result to the original plan. + * + * @param resultOrder the node order of the final result + * @param rowTypeList rowType of the final result + * @return list of RexInputRef */ - public void convertHyperEdgeCond(RelBuilder builder) { - 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++; + public List<RexNode> restoreProjectionOrder( + ImmutableList<Integer> resultOrder, + List<RelDataTypeField> rowTypeList) { + Map<Integer, Integer> relativePositionInNode = new HashMap<>(); + int fieldCount = 0; + for (int resultIndex : resultOrder) { + relativePositionInNode.put(resultIndex, fieldCount); + if (!LongBitmap.isOverlap(notProjectInputs, LongBitmap.newBitmap(resultIndex))) { + fieldCount += inputs.get(resultIndex).getRowType().getFieldCount(); } - - builder.push(input) - .project(projects, names, true); - replaceInput(nodeIndex, builder.build()); } - - RexShuttle inputRef2inputNameShuttle = new RexShuttle() { - @Override public RexNode visitInputRef(RexInputRef inputRef) { - int index = inputRef.getIndex(); - return new RexInputFieldName( - fieldList.get(index).getName(), - fieldList.get(index).getType()); + List<RexNode> projects = new ArrayList<>(); + for (int inputIndex = 0; inputIndex < inputs.size(); inputIndex++) { + if (LongBitmap.isOverlap(notProjectInputs, LongBitmap.newBitmap(inputIndex))) { + continue; } - }; - for (int i = 0; i < edges.size(); i++) { - HyperEdge edge = edges.get(i); - RexNode convertCond = edge.getCondition().accept(inputRef2inputNameShuttle); - HyperEdge convertEdge = - new HyperEdge( - edge.getLeftNodeBitmap(), - edge.getRightNodeBitmap(), - edge.getJoinType(), - convertCond); - edges.set(i, convertEdge); + for (int i = 0; i < inputs.get(inputIndex).getRowType().getFieldCount(); i++) { + Integer fieldOffset = relativePositionInNode.get(inputIndex); + if (fieldOffset == null) { + throw new DpHyp.DphypOrHyperGraphException( + "The result order loses the " + inputIndex + "-th input"); + } + int inputRef = i + fieldOffset; + projects.add( + new RexInputRef(inputRef, rowTypeList.get(inputRef).getType())); + } } + return projects; } /** * Adjusting RexInputRef in enumeration process is too complicated, - * so use unique name replace input ref. - * Before starting enumeration, convert RexInputRef to RexInputFieldName. - * When connect csgcmp to Join, convert RexInputFieldName to RexInputRef. + * so use node index and relative position of field in node replace RexInputRef. + * When build hyper graph, convert RexInputRef to RexNodeAndFieldIndex. + * When connect csgcmp to Join, convert RexNodeAndFieldIndex to RexInputRef. */ - private static class RexInputFieldName extends RexVariable { + static class RexNodeAndFieldIndex extends RexVariable { Review Comment: why is this a static class if the nodeIndex depends on the hypergraph? Should be instead an inner class of the HyperGraph? Then you could access the RexNode too. ########## core/src/main/java/org/apache/calcite/rel/rules/DpHyp.java: ########## @@ -173,42 +180,86 @@ private void enumerateCmpRec(long csg, long cmp, long forbidden) { private void emitCsgCmp(long csg, long cmp, List<HyperEdge> edges) { RelNode child1 = dpTable.get(csg); RelNode child2 = dpTable.get(cmp); + ImmutableList csgOrder = resultInputOrder.get(csg); + ImmutableList cmpOrder = resultInputOrder.get(cmp); if (child1 == null || child2 == null) { - throw new IllegalArgumentException( + throw new DphypOrHyperGraphException( "csg and cmp were not enumerated in the previous dp process"); } + if (csgOrder == null || cmpOrder == null) { + throw new DphypOrHyperGraphException("Lost the vertex order of csg or cmp"); + } JoinRelType joinType = hyperGraph.extractJoinType(edges); if (joinType == null) { return; } - RexNode joinCond1 = hyperGraph.extractJoinCond(child1, child2, edges); + if (!ConflictDetectionHelper.applicable(csg | cmp, edges)) { + return; + } + + ImmutableList<Integer> unionOrder = ImmutableList.<Integer>builder() + .addAll(csgOrder) + .addAll(cmpOrder) + .build(); + RexNode joinCond1 = hyperGraph.extractJoinCond(unionOrder, csgOrder.size(), edges); RelNode newPlan1 = builder .push(child1) .push(child2) .join(joinType, joinCond1) .build(); + RelNode winPlan = newPlan1; + ImmutableList<Integer> winOrder = ImmutableList.copyOf(unionOrder); - // 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); + if (ConflictDetectionHelper.isCommutative(joinType)) { + // swap left and right + unionOrder = ImmutableList.<Integer>builder() + .addAll(cmpOrder) + .addAll(csgOrder) + .build(); + RexNode joinCond2 = hyperGraph.extractJoinCond(unionOrder, cmpOrder.size(), edges); + RelNode newPlan2 = builder + .push(child2) + .push(child1) + .join(joinType, joinCond2) + .build(); + winPlan = chooseBetterPlan(winPlan, newPlan2); + if (winPlan.equals(newPlan2)) { + winOrder = ImmutableList.copyOf(unionOrder); + } + } RelNode oriPlan = dpTable.get(csg | cmp); if (oriPlan != null) { winPlan = chooseBetterPlan(winPlan, oriPlan); + if (winPlan.equals(oriPlan)) { + winOrder = resultInputOrder.get(csg | cmp); + } } + assert winOrder != null; dpTable.put(csg | cmp, winPlan); + resultInputOrder.put(csg | cmp, winOrder); } public @Nullable RelNode getBestPlan() { int size = hyperGraph.getInputs().size(); long wholeGraph = LongBitmap.newBitmapBetween(0, size); - return dpTable.get(wholeGraph); + RelNode orderedJoin = dpTable.get(wholeGraph); + if (orderedJoin == null) { + return null; + } + ImmutableList<Integer> resultOrder = resultInputOrder.get(wholeGraph); + if (resultOrder == null) { Review Comment: can this happen for legal programs, or this is essentially an assertion failure? ########## core/src/main/java/org/apache/calcite/rel/rules/JoinToHyperGraphRule.java: ########## @@ -70,106 +75,205 @@ protected JoinToHyperGraphRule(Config config) { RelOptUtil.decomposeConjunction(origJoin.getCondition(), joinConds); } - // when right is HyperGraph, need shift the leftNodeBit, rightNodeBit, condition of HyperEdge + // when right is HyperGraph, need shift fields related to bitmap 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( + notProjectInputs |= ((HyperGraph) left).getNotProjectInputs(); + notProjectInputs |= ((HyperGraph) right).getNotProjectInputs() << leftNodeCount; + + leftSubEdges.addAll(((HyperGraph) left).getEdges()); + rightSubEdges.addAll( ((HyperGraph) right).getEdges().stream() - .map(hyperEdge -> adjustNodeBit(hyperEdge, leftNodeCount, leftFieldCount)) + .map(hyperEdge -> adjustNodeBit(hyperEdge, leftNodeCount)) .collect(Collectors.toList())); } else if (left instanceof HyperGraph) { leftNodeCount = left.getInputs().size(); inputs.addAll(left.getInputs()); inputs.add(right); - edges.addAll(((HyperGraph) left).getEdges()); + notProjectInputs |= ((HyperGraph) left).getNotProjectInputs(); + + leftSubEdges.addAll(((HyperGraph) left).getEdges()); } else if (right instanceof HyperGraph) { leftNodeCount = 1; inputs.add(left); inputs.addAll(right.getInputs()); - edges.addAll( + notProjectInputs |= ((HyperGraph) right).getNotProjectInputs() << leftNodeCount; + + rightSubEdges.addAll( ((HyperGraph) right).getEdges().stream() - .map(hyperEdge -> adjustNodeBit(hyperEdge, leftNodeCount, leftFieldCount)) + .map(hyperEdge -> adjustNodeBit(hyperEdge, leftNodeCount)) .collect(Collectors.toList())); } else { leftNodeCount = 1; inputs.add(left); inputs.add(right); } - HashMap<Integer, Integer> fieldIndexToNodeIndexMap = new HashMap<>(); + // calculate conflict rules + Map<Long, Long> conflictRules = + ConflictDetectionHelper.makeConflictRules( + leftSubEdges, + rightSubEdges, + origJoin.getJoinType()); + leftSubEdges.addAll(rightSubEdges); + + Map<Integer, Integer> fieldIndexToNodeIndexMap = new HashMap<>(); + // the map from input index to the count of fields before it, used to convert RexInputRef to + // RexNodeAndFieldIndex + Map<Integer, Integer> relativePositionInNode = new HashMap<>(); int fieldCount = 0; for (int i = 0; i < inputs.size(); i++) { + if (LongBitmap.isOverlap(notProjectInputs, LongBitmap.newBitmap(i))) { + continue; + } + relativePositionInNode.put(i, fieldCount); 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; + long leftEndpoint; + long rightEndpoint; + long leftNodeUsedInPredicate; + long rightNodeUsedInPredicate; + long initialLeftNodeBits = LongBitmap.newBitmapBetween(0, leftNodeCount); + long initialRightNodeBits = LongBitmap.newBitmapBetween(leftNodeCount, inputs.size()); List<Integer> leftRefs = new ArrayList<>(); List<Integer> rightRefs = new ArrayList<>(); - RexVisitorImpl visitor = new RexVisitorImpl<Void>(true) { - @Override public Void visitInputRef(RexInputRef inputRef) { + RexShuttle shuttle = new RexShuttle() { + @Override public RexNode 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()); + throw new DpHyp.DphypOrHyperGraphException("When build hyper graph, RexInputRef refers " + + "a dummy field: " + inputRef + ", rowType is: " + origJoin.getRowType()); } if (nodeIndex < leftNodeCount) { leftRefs.add(nodeIndex); } else { rightRefs.add(nodeIndex); } - return null; + Integer fieldOffset = relativePositionInNode.get(nodeIndex); + if (fieldOffset == null) { + throw new DpHyp.DphypOrHyperGraphException("When build hyper graph, failed to map " + + "input index to field count before it"); + } + int fieldIndex = inputRef.getIndex() - fieldOffset; + if (fieldIndex < 0) { + throw new DpHyp.DphypOrHyperGraphException("When build hyper graph, failed to convert " + + "the input ref to the relative position of the field in the input"); + } + return new HyperGraph.RexNodeAndFieldIndex( + nodeIndex, + fieldIndex, + inputRef.getName(), + inputRef.getType()); } }; - joinCond.accept(visitor); + RexNode hyperEdgeCondition = joinCond.accept(shuttle); - // when cartesian product, make it to complex hyper edge + Map<Long, Long> conflictRulesAfterAbsorb = new HashMap<>(); + leftNodeUsedInPredicate = LongBitmap.newBitmapFromList(leftRefs); + rightNodeUsedInPredicate = LongBitmap.newBitmapFromList(rightRefs); if (leftRefs.isEmpty() || rightRefs.isEmpty()) { - leftNodeBits = LongBitmap.newBitmapBetween(0, leftNodeCount); - rightNodeBits = LongBitmap.newBitmapBetween(leftNodeCount, inputs.size()); + // when cartesian product or degenerate predicate, a complex hyperedge is generated to fix + // current join operator without exploring more possibilities. See section 6.2 in CD-C paper + leftEndpoint = LongBitmap.newBitmapBetween(0, leftNodeCount); + rightEndpoint = LongBitmap.newBitmapBetween(leftNodeCount, inputs.size()); } else { - leftNodeBits = LongBitmap.newBitmapFromList(leftRefs); - rightNodeBits = LongBitmap.newBitmapFromList(rightRefs); + // simplify conflict rules. See section 5.5 in CD-C paper + long tes = + ConflictDetectionHelper.absorbConflictRulesIntoTES( + leftNodeUsedInPredicate | rightNodeUsedInPredicate, + conflictRulesAfterAbsorb, + conflictRules); + rightEndpoint = tes & initialRightNodeBits; + leftEndpoint = tes & ~rightEndpoint; } - edges.add( + leftSubEdges.add( new HyperEdge( - leftNodeBits, - rightNodeBits, + leftEndpoint, + rightEndpoint, + leftNodeUsedInPredicate, + rightNodeUsedInPredicate, + conflictRulesAfterAbsorb, + initialLeftNodeBits, + initialRightNodeBits, origJoin.getJoinType(), - joinCond)); + hyperEdgeCondition)); + } + + if (!origJoin.getJoinType().projectsRight()) { + notProjectInputs |= LongBitmap.newBitmapBetween(leftNodeCount, inputs.size()); } result = new HyperGraph( origJoin.getCluster(), origJoin.getTraitSet(), inputs, - edges, + notProjectInputs, + leftSubEdges, origJoin.getRowType()); call.transformTo(result); } - private static HyperEdge adjustNodeBit(HyperEdge hyperEdge, int nodeOffset, int fieldOffset) { - RexNode newCondition = RexUtil.shift(hyperEdge.getCondition(), fieldOffset); + private static HyperEdge adjustNodeBit(HyperEdge hyperEdge, int nodeOffset) { Review Comment: should this be a method of the HyperEdge class? ########## core/src/main/java/org/apache/calcite/rel/rules/HyperGraph.java: ########## @@ -401,69 +453,67 @@ public RexNode extractJoinCond(RelNode left, RelNode right, List<HyperEdge> edge }; for (HyperEdge edge : edges) { - RexNode inputRefCond = edge.getCondition().accept(inputName2InputRefShuttle); + RexNode inputRefCond = edge.getCondition().accept(shuttle); joinConds.add(inputRefCond); } - return RexUtil.composeConjunction(left.getCluster().getRexBuilder(), joinConds); + return RexUtil.composeConjunction(getCluster().getRexBuilder(), joinConds); Review Comment: I should have looked at the original hypergraph PR, but I haven't. It seems to me like the shape of predicates in all joins is restricted to be conjunctions of equalities involving simple field accesses. Is this right? ########## core/src/main/java/org/apache/calcite/rel/rules/HyperGraph.java: ########## @@ -401,69 +453,67 @@ public RexNode extractJoinCond(RelNode left, RelNode right, List<HyperEdge> edge }; for (HyperEdge edge : edges) { - RexNode inputRefCond = edge.getCondition().accept(inputName2InputRefShuttle); + RexNode inputRefCond = edge.getCondition().accept(shuttle); joinConds.add(inputRefCond); } - return RexUtil.composeConjunction(left.getCluster().getRexBuilder(), joinConds); + return RexUtil.composeConjunction(getCluster().getRexBuilder(), joinConds); } /** - * Before starting enumeration, add Project on every input, make all field name unique. - * Convert the HyperEdge condition from RexInputRef to RexInputFieldName + * Restore the projection order of the final result to the original plan. Review Comment: ensure that the fields produced by the reordered join are in the same order as in the original plan. ########## core/src/main/java/org/apache/calcite/rel/rules/JoinToHyperGraphRule.java: ########## @@ -70,106 +75,205 @@ protected JoinToHyperGraphRule(Config config) { RelOptUtil.decomposeConjunction(origJoin.getCondition(), joinConds); } - // when right is HyperGraph, need shift the leftNodeBit, rightNodeBit, condition of HyperEdge + // when right is HyperGraph, need shift fields related to bitmap 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( + notProjectInputs |= ((HyperGraph) left).getNotProjectInputs(); + notProjectInputs |= ((HyperGraph) right).getNotProjectInputs() << leftNodeCount; + + leftSubEdges.addAll(((HyperGraph) left).getEdges()); + rightSubEdges.addAll( ((HyperGraph) right).getEdges().stream() - .map(hyperEdge -> adjustNodeBit(hyperEdge, leftNodeCount, leftFieldCount)) + .map(hyperEdge -> adjustNodeBit(hyperEdge, leftNodeCount)) .collect(Collectors.toList())); } else if (left instanceof HyperGraph) { leftNodeCount = left.getInputs().size(); inputs.addAll(left.getInputs()); inputs.add(right); - edges.addAll(((HyperGraph) left).getEdges()); + notProjectInputs |= ((HyperGraph) left).getNotProjectInputs(); + + leftSubEdges.addAll(((HyperGraph) left).getEdges()); } else if (right instanceof HyperGraph) { leftNodeCount = 1; inputs.add(left); inputs.addAll(right.getInputs()); - edges.addAll( + notProjectInputs |= ((HyperGraph) right).getNotProjectInputs() << leftNodeCount; + + rightSubEdges.addAll( ((HyperGraph) right).getEdges().stream() - .map(hyperEdge -> adjustNodeBit(hyperEdge, leftNodeCount, leftFieldCount)) + .map(hyperEdge -> adjustNodeBit(hyperEdge, leftNodeCount)) .collect(Collectors.toList())); } else { leftNodeCount = 1; inputs.add(left); inputs.add(right); } - HashMap<Integer, Integer> fieldIndexToNodeIndexMap = new HashMap<>(); + // calculate conflict rules + Map<Long, Long> conflictRules = + ConflictDetectionHelper.makeConflictRules( + leftSubEdges, + rightSubEdges, + origJoin.getJoinType()); + leftSubEdges.addAll(rightSubEdges); + + Map<Integer, Integer> fieldIndexToNodeIndexMap = new HashMap<>(); + // the map from input index to the count of fields before it, used to convert RexInputRef to + // RexNodeAndFieldIndex + Map<Integer, Integer> relativePositionInNode = new HashMap<>(); int fieldCount = 0; for (int i = 0; i < inputs.size(); i++) { + if (LongBitmap.isOverlap(notProjectInputs, LongBitmap.newBitmap(i))) { + continue; + } + relativePositionInNode.put(i, fieldCount); 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; + long leftEndpoint; + long rightEndpoint; + long leftNodeUsedInPredicate; + long rightNodeUsedInPredicate; + long initialLeftNodeBits = LongBitmap.newBitmapBetween(0, leftNodeCount); + long initialRightNodeBits = LongBitmap.newBitmapBetween(leftNodeCount, inputs.size()); List<Integer> leftRefs = new ArrayList<>(); List<Integer> rightRefs = new ArrayList<>(); - RexVisitorImpl visitor = new RexVisitorImpl<Void>(true) { - @Override public Void visitInputRef(RexInputRef inputRef) { + RexShuttle shuttle = new RexShuttle() { + @Override public RexNode 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()); + throw new DpHyp.DphypOrHyperGraphException("When build hyper graph, RexInputRef refers " + + "a dummy field: " + inputRef + ", rowType is: " + origJoin.getRowType()); } if (nodeIndex < leftNodeCount) { leftRefs.add(nodeIndex); } else { rightRefs.add(nodeIndex); } - return null; + Integer fieldOffset = relativePositionInNode.get(nodeIndex); + if (fieldOffset == null) { + throw new DpHyp.DphypOrHyperGraphException("When build hyper graph, failed to map " + + "input index to field count before it"); + } + int fieldIndex = inputRef.getIndex() - fieldOffset; + if (fieldIndex < 0) { + throw new DpHyp.DphypOrHyperGraphException("When build hyper graph, failed to convert " + + "the input ref to the relative position of the field in the input"); + } + return new HyperGraph.RexNodeAndFieldIndex( + nodeIndex, + fieldIndex, + inputRef.getName(), + inputRef.getType()); } }; - joinCond.accept(visitor); + RexNode hyperEdgeCondition = joinCond.accept(shuttle); - // when cartesian product, make it to complex hyper edge + Map<Long, Long> conflictRulesAfterAbsorb = new HashMap<>(); + leftNodeUsedInPredicate = LongBitmap.newBitmapFromList(leftRefs); + rightNodeUsedInPredicate = LongBitmap.newBitmapFromList(rightRefs); if (leftRefs.isEmpty() || rightRefs.isEmpty()) { - leftNodeBits = LongBitmap.newBitmapBetween(0, leftNodeCount); - rightNodeBits = LongBitmap.newBitmapBetween(leftNodeCount, inputs.size()); + // when cartesian product or degenerate predicate, a complex hyperedge is generated to fix + // current join operator without exploring more possibilities. See section 6.2 in CD-C paper + leftEndpoint = LongBitmap.newBitmapBetween(0, leftNodeCount); + rightEndpoint = LongBitmap.newBitmapBetween(leftNodeCount, inputs.size()); } else { - leftNodeBits = LongBitmap.newBitmapFromList(leftRefs); - rightNodeBits = LongBitmap.newBitmapFromList(rightRefs); + // simplify conflict rules. See section 5.5 in CD-C paper + long tes = + ConflictDetectionHelper.absorbConflictRulesIntoTES( + leftNodeUsedInPredicate | rightNodeUsedInPredicate, + conflictRulesAfterAbsorb, + conflictRules); + rightEndpoint = tes & initialRightNodeBits; + leftEndpoint = tes & ~rightEndpoint; } - edges.add( + leftSubEdges.add( new HyperEdge( - leftNodeBits, - rightNodeBits, + leftEndpoint, + rightEndpoint, + leftNodeUsedInPredicate, + rightNodeUsedInPredicate, + conflictRulesAfterAbsorb, + initialLeftNodeBits, + initialRightNodeBits, origJoin.getJoinType(), - joinCond)); + hyperEdgeCondition)); + } + + if (!origJoin.getJoinType().projectsRight()) { + notProjectInputs |= LongBitmap.newBitmapBetween(leftNodeCount, inputs.size()); } result = new HyperGraph( origJoin.getCluster(), origJoin.getTraitSet(), inputs, - edges, + notProjectInputs, + leftSubEdges, origJoin.getRowType()); call.transformTo(result); } - private static HyperEdge adjustNodeBit(HyperEdge hyperEdge, int nodeOffset, int fieldOffset) { - RexNode newCondition = RexUtil.shift(hyperEdge.getCondition(), fieldOffset); + private static HyperEdge adjustNodeBit(HyperEdge hyperEdge, int nodeOffset) { + RexShuttle shiftNodeIndexShuttle = 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 HyperGraph.RexNodeAndFieldIndex) { + clonedOperand = + new HyperGraph.RexNodeAndFieldIndex( + ((HyperGraph.RexNodeAndFieldIndex) operand).nodeIndex + nodeOffset, Review Comment: you should cast the operand only once ########## core/src/main/java/org/apache/calcite/rel/rules/ConflictDetectionHelper.java: ########## @@ -0,0 +1,216 @@ +/* + * 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 com.google.common.collect.ImmutableMap; + +import java.util.HashMap; +import java.util.List; +import java.util.Map; + +/** + * Conflict detection algorithm based on CD-C. More details are in paper: + * <a href="https://15721.courses.cs.cmu.edu/spring2019/papers/23-optimizer2/p493-moerkotte.pdf";> + * On the correct and complete enumeration of the core search space</a>. + */ +public class ConflictDetectionHelper { + + private ConflictDetectionHelper() { + } + + private static final ImmutableMap<JoinRelType, Integer> INDEX_OF_TABLE = + ImmutableMap.<JoinRelType, Integer>builder() + .put(JoinRelType.INNER, 0).put(JoinRelType.SEMI, 1).put(JoinRelType.ANTI, 2) + .put(JoinRelType.LEFT, 3).put(JoinRelType.FULL, 4).build(); + + // TODO: when special attribute is null rejecting, left/full join is + // associative/left_asscom/right_asscom. See table2/3 in paper + private static final boolean[][] ASSOCIATIVE_TABLE = { + // inner-B semi-B anti-B left-B full-B + /* inner-A */ {true, true, true, true, false}, + /* semi-A */ {false, false, false, false, false}, + /* anti-A */ {false, false, false, false, false}, + /* left-A */ {false, false, false, false, false}, + /* full-A */ {false, false, false, false, false}}; + + private static final boolean[][] LEFT_ASSCOM_TABLE = { + // inner-B semi-B anti-B left-B full-B + /* inner-A */ {true, true, true, true, false}, + /* semi-A */ {true, true, true, true, false}, + /* anti-A */ {true, true, true, true, false}, + /* left-A */ {true, true, true, true, false}, + /* full-A */ {false, false, false, false, false}}; + + private static final boolean[][] RIGHT_ASSCOM_TABLE = { + // inner-B semi-B anti-B left-B full-B + /* inner-A */ {true, false, false, false, false}, + /* semi-A */ {false, false, false, false, false}, + /* anti-A */ {false, false, false, false, false}, + /* left-A */ {false, false, false, false, false}, + /* full-A */ {false, false, false, false, false}}; + + /** + * Make conflict rules for join operator based on CD-C. + * + * @param leftSubEdges left sub operators + * @param rightSubEdges right sub operators + * @param joinType current join operator + * @return a map from table set1 to table set2 that if set1 and the tables in the current join + * operator have an intersection, then set2 must be included in the current join operator + */ + public static Map<Long, Long> makeConflictRules( + List<HyperEdge> leftSubEdges, + List<HyperEdge> rightSubEdges, + JoinRelType joinType) { + Map<Long, Long> conflictRules = new HashMap<>(); + for (HyperEdge leftSubEdge : leftSubEdges) { + if (!isAssociative(leftSubEdge.getJoinType(), joinType)) { + if (leftSubEdge.getLeftNodeUsedInPredicate() != 0) { + conflictRules.merge( + leftSubEdge.getInitialRightNodeBits(), + leftSubEdge.getLeftNodeUsedInPredicate(), + (oldValue, newValue) -> oldValue | newValue); + } else { + conflictRules.merge( + leftSubEdge.getInitialRightNodeBits(), + leftSubEdge.getInitialLeftNodeBits(), + (oldValue, newValue) -> oldValue | newValue); + } + + } + if (!isLeftAsscom(leftSubEdge.getJoinType(), joinType)) { + if (leftSubEdge.getRightNodeUsedInPredicate() != 0) { + conflictRules.merge( + leftSubEdge.getInitialLeftNodeBits(), + leftSubEdge.getRightNodeUsedInPredicate(), + (oldValue, newValue) -> oldValue | newValue); + } else { + conflictRules.merge( + leftSubEdge.getInitialLeftNodeBits(), + leftSubEdge.getInitialRightNodeBits(), + (oldValue, newValue) -> oldValue | newValue); + } + } + } + + for (HyperEdge rightSubEdge : rightSubEdges) { + if (!isAssociative(joinType, rightSubEdge.getJoinType())) { + if (rightSubEdge.getRightNodeUsedInPredicate() != 0) { + conflictRules.merge( + rightSubEdge.getInitialLeftNodeBits(), + rightSubEdge.getRightNodeUsedInPredicate(), + (oldValue, newValue) -> oldValue | newValue); + } else { + conflictRules.merge( + rightSubEdge.getInitialLeftNodeBits(), + rightSubEdge.getInitialRightNodeBits(), + (oldValue, newValue) -> oldValue | newValue); + } + } + if (!isRightAsscom(joinType, rightSubEdge.getJoinType())) { + if (rightSubEdge.getLeftNodeUsedInPredicate() != 0) { + conflictRules.merge( + rightSubEdge.getInitialRightNodeBits(), + rightSubEdge.getLeftNodeUsedInPredicate(), + (oldValue, newValue) -> oldValue | newValue); + } else { + conflictRules.merge( + rightSubEdge.getInitialRightNodeBits(), + rightSubEdge.getInitialLeftNodeBits(), + (oldValue, newValue) -> oldValue | newValue); + } + } + } + return conflictRules; + } + + /** + * For conflict rule <code>T1 -> T2</code>, if T1 and tes have intersection, we can add T2 + * into tes and remove this rule. See section 5.5 in paper. + * + * @param tes tes Review Comment: I would also make a class for TES, this will make it much easier to read the code. This then becomes a method of the TES class. -- 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
