SemiJoinJoinTransposeRule.java
/*
* 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.rel.type.RelDataTypeField;
import org.apache.calcite.rex.RexNode;
import org.apache.calcite.tools.RelBuilderFactory;
import org.apache.calcite.util.ImmutableIntList;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableSet;
import org.immutables.value.Value;
import java.util.ArrayList;
import java.util.List;
/**
* Planner rule that pushes a {@link Join#isSemiJoin semi-join}
* down in a tree past a {@link org.apache.calcite.rel.core.Join}
* in order to trigger other rules that will convert {@code SemiJoin}s.
*
* <ul>
* <li>SemiJoin(LogicalJoin(X, Y), Z) → LogicalJoin(SemiJoin(X, Z), Y)
* <li>SemiJoin(LogicalJoin(X, Y), Z) → LogicalJoin(X, SemiJoin(Y, Z))
* </ul>
*
* <p>Whether this
* first or second conversion is applied depends on which operands actually
* participate in the semi-join.
*
* @see CoreRules#SEMI_JOIN_JOIN_TRANSPOSE
*/
@Value.Enclosing
public class SemiJoinJoinTransposeRule
extends RelRule<SemiJoinJoinTransposeRule.Config>
implements TransformationRule {
/** Creates a SemiJoinJoinTransposeRule. */
protected SemiJoinJoinTransposeRule(Config config) {
super(config);
}
@Deprecated // to be removed before 2.0
public SemiJoinJoinTransposeRule(RelBuilderFactory relBuilderFactory) {
this(Config.DEFAULT.withRelBuilderFactory(relBuilderFactory)
.as(Config.class));
}
//~ Methods ----------------------------------------------------------------
@Override public void onMatch(RelOptRuleCall call) {
final Join semiJoin = call.rel(0);
final Join join = call.rel(1);
if (join.isSemiJoin()) {
return;
}
// X is the left child of the join below the semi-join
// Y is the right child of the join below the semi-join
// Z is the right child of the semi-join
final int nFieldsX = join.getLeft().getRowType().getFieldList().size();
final int nFieldsY = join.getRight().getRowType().getFieldList().size();
final int nFieldsZ = semiJoin.getRight().getRowType().getFieldList().size();
final int nTotalFields = nFieldsX + nFieldsY + nFieldsZ;
final List<RelDataTypeField> fields = new ArrayList<>();
// create a list of fields for the full join result; note that
// we can't simply use the fields from the semi-join because the
// row-type of a semi-join only includes the left hand side fields
List<RelDataTypeField> joinFields =
semiJoin.getRowType().getFieldList();
for (int i = 0; i < (nFieldsX + nFieldsY); i++) {
fields.add(joinFields.get(i));
}
joinFields = semiJoin.getRight().getRowType().getFieldList();
for (int i = 0; i < nFieldsZ; i++) {
fields.add(joinFields.get(i));
}
// determine which operands below the semi-join are the actual
// Rels that participate in the semi-join
final ImmutableIntList leftKeys = semiJoin.analyzeCondition().leftKeys;
int nKeysFromX = 0;
for (int leftKey : leftKeys) {
if (leftKey < nFieldsX) {
nKeysFromX++;
}
}
if (nKeysFromX != 0 && nKeysFromX != leftKeys.size()) {
// We can not push semi-join down if it has keys from both tables of the bottom join
return;
}
// join type needs to allow pushing predicate (represented as semi-join in our case)
// to the corresponding input
if (nKeysFromX > 0) {
if (!join.getJoinType().canPushLeftFromAbove()) {
return;
}
} else {
if (!join.getJoinType().canPushRightFromAbove()) {
return;
}
}
// need to convert the semi-join condition and possibly the keys
final RexNode newSemiJoinFilter;
int[] adjustments = new int[nTotalFields];
if (nKeysFromX > 0) {
// (X, Y, Z) --> (X, Z, Y)
// semiJoin(X, Z)
// pass 0 as Y's adjustment because there shouldn't be any
// references to Y in the semi-join filter
setJoinAdjustments(
adjustments,
nFieldsX,
nFieldsY,
nFieldsZ,
0,
-nFieldsY);
newSemiJoinFilter =
semiJoin.getCondition().accept(
new RelOptUtil.RexInputConverter(
semiJoin.getCluster().getRexBuilder(),
fields,
adjustments));
} else {
// (X, Y, Z) --> (X, Y, Z)
// semiJoin(Y, Z)
setJoinAdjustments(
adjustments,
nFieldsX,
nFieldsY,
nFieldsZ,
-nFieldsX,
-nFieldsX);
newSemiJoinFilter =
semiJoin.getCondition().accept(
new RelOptUtil.RexInputConverter(
semiJoin.getCluster().getRexBuilder(),
fields,
adjustments));
}
// create the new join
final RelNode leftSemiJoinOp;
if (nKeysFromX > 0) {
leftSemiJoinOp = join.getLeft();
} else {
leftSemiJoinOp = join.getRight();
}
final LogicalJoin newSemiJoin =
LogicalJoin.create(leftSemiJoinOp,
semiJoin.getRight(),
// No need to copy the hints, the framework would try to do that.
ImmutableList.of(),
newSemiJoinFilter,
ImmutableSet.of(),
JoinRelType.SEMI);
final RelNode left;
final RelNode right;
if (nKeysFromX > 0) {
left = newSemiJoin;
right = join.getRight();
} else {
left = join.getLeft();
right = newSemiJoin;
}
final RelNode newJoin =
join.copy(
join.getTraitSet(),
join.getCondition(),
left,
right,
join.getJoinType(),
join.isSemiJoinDone());
call.transformTo(newJoin);
}
/**
* Sets an array to reflect how much each index corresponding to a field
* needs to be adjusted. The array corresponds to fields in a 3-way join
* between (X, Y, and Z). X remains unchanged, but Y and Z need to be
* adjusted by some fixed amount as determined by the input.
*
* @param adjustments array to be filled out
* @param nFieldsX number of fields in X
* @param nFieldsY number of fields in Y
* @param nFieldsZ number of fields in Z
* @param adjustY the amount to adjust Y by
* @param adjustZ the amount to adjust Z by
*/
private static void setJoinAdjustments(
int[] adjustments,
int nFieldsX,
int nFieldsY,
int nFieldsZ,
int adjustY,
int adjustZ) {
for (int i = 0; i < nFieldsX; i++) {
adjustments[i] = 0;
}
for (int i = nFieldsX; i < (nFieldsX + nFieldsY); i++) {
adjustments[i] = adjustY;
}
for (int i = nFieldsX + nFieldsY;
i < (nFieldsX + nFieldsY + nFieldsZ);
i++) {
adjustments[i] = adjustZ;
}
}
/** Rule configuration. */
@Value.Immutable
public interface Config extends RelRule.Config {
Config DEFAULT = ImmutableSemiJoinJoinTransposeRule.Config.of()
.withOperandFor(LogicalJoin.class, Join.class);
@Override default SemiJoinJoinTransposeRule toRule() {
return new SemiJoinJoinTransposeRule(this);
}
/** Defines an operand tree for the given classes. */
default Config withOperandFor(Class<? extends Join> joinClass,
Class<? extends Join> join2Class) {
return withOperandSupplier(b0 ->
b0.operand(joinClass).predicate(Join::isSemiJoin).inputs(b1 ->
b1.operand(join2Class).anyInputs()))
.as(Config.class);
}
}
}