ReduceExpressionsRule.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.RelOptCluster;
import org.apache.calcite.plan.RelOptPredicateList;
import org.apache.calcite.plan.RelOptRuleCall;
import org.apache.calcite.plan.RelOptUtil;
import org.apache.calcite.plan.RelRule;
import org.apache.calcite.rel.RelCollation;
import org.apache.calcite.rel.RelCollations;
import org.apache.calcite.rel.RelFieldCollation;
import org.apache.calcite.rel.RelNode;
import org.apache.calcite.rel.core.Calc;
import org.apache.calcite.rel.core.Filter;
import org.apache.calcite.rel.core.Join;
import org.apache.calcite.rel.core.Project;
import org.apache.calcite.rel.core.Window;
import org.apache.calcite.rel.logical.LogicalCalc;
import org.apache.calcite.rel.logical.LogicalFilter;
import org.apache.calcite.rel.logical.LogicalProject;
import org.apache.calcite.rel.logical.LogicalWindow;
import org.apache.calcite.rel.metadata.RelMetadataQuery;
import org.apache.calcite.rel.type.RelDataType;
import org.apache.calcite.rel.type.RelDataTypeFactory;
import org.apache.calcite.rex.RexBuilder;
import org.apache.calcite.rex.RexCall;
import org.apache.calcite.rex.RexCorrelVariable;
import org.apache.calcite.rex.RexDynamicParam;
import org.apache.calcite.rex.RexExecutor;
import org.apache.calcite.rex.RexFieldAccess;
import org.apache.calcite.rex.RexInputRef;
import org.apache.calcite.rex.RexLambda;
import org.apache.calcite.rex.RexLambdaRef;
import org.apache.calcite.rex.RexLiteral;
import org.apache.calcite.rex.RexLocalRef;
import org.apache.calcite.rex.RexNode;
import org.apache.calcite.rex.RexOver;
import org.apache.calcite.rex.RexProgram;
import org.apache.calcite.rex.RexProgramBuilder;
import org.apache.calcite.rex.RexRangeRef;
import org.apache.calcite.rex.RexShuttle;
import org.apache.calcite.rex.RexSimplify;
import org.apache.calcite.rex.RexSubQuery;
import org.apache.calcite.rex.RexUnknownAs;
import org.apache.calcite.rex.RexUtil;
import org.apache.calcite.rex.RexVisitorImpl;
import org.apache.calcite.rex.RexWindow;
import org.apache.calcite.rex.RexWindowBound;
import org.apache.calcite.sql.SqlAggFunction;
import org.apache.calcite.sql.SqlKind;
import org.apache.calcite.sql.SqlOperator;
import org.apache.calcite.sql.type.SqlTypeName;
import org.apache.calcite.tools.RelBuilder;
import org.apache.calcite.tools.RelBuilderFactory;
import org.apache.calcite.util.ImmutableBitSet;
import org.apache.calcite.util.Pair;
import org.apache.calcite.util.Util;
import com.google.common.collect.ImmutableMap;
import com.google.common.collect.Lists;
import org.checkerframework.checker.nullness.qual.Nullable;
import org.immutables.value.Value;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Deque;
import java.util.List;
import java.util.Map;
import java.util.regex.Pattern;
import java.util.stream.Collectors;
/**
* Collection of planner rules that apply various simplifying transformations on
* RexNode trees. Currently, there are two transformations:
*
* <ul>
* <li>Constant reduction, which evaluates constant subtrees, replacing them
* with a corresponding RexLiteral
* <li>Removal of redundant casts, which occurs when the argument into the cast
* is the same as the type of the resulting cast expression
* </ul>
*
* @param <C> Configuration type
*/
public abstract class ReduceExpressionsRule<C extends ReduceExpressionsRule.Config>
extends RelRule<C>
implements SubstitutionRule {
//~ Static fields/initializers ---------------------------------------------
/**
* Regular expression that matches the description of all instances of this
* rule and {@link ValuesReduceRule} also. Use
* it to prevent the planner from invoking these rules.
*/
public static final Pattern EXCLUSION_PATTERN =
Pattern.compile("Reduce(Expressions|Values)Rule.*");
/**
* Rule that reduces constants inside a {@link org.apache.calcite.rel.core.Filter}.
* If the condition is a constant, the filter is removed (if TRUE) or replaced with
* an empty {@link org.apache.calcite.rel.core.Values} (if FALSE or NULL).
*
* @see CoreRules#FILTER_REDUCE_EXPRESSIONS
*/
public static class FilterReduceExpressionsRule
extends ReduceExpressionsRule<FilterReduceExpressionsRule.FilterReduceExpressionsRuleConfig> {
/** Creates a FilterReduceExpressionsRule. */
protected FilterReduceExpressionsRule(FilterReduceExpressionsRuleConfig config) {
super(config);
}
@Deprecated // to be removed before 2.0
public FilterReduceExpressionsRule(Class<? extends Filter> filterClass,
RelBuilderFactory relBuilderFactory) {
this(FilterReduceExpressionsRuleConfig.DEFAULT.withRelBuilderFactory(relBuilderFactory)
.as(FilterReduceExpressionsRuleConfig.class)
.withOperandFor(filterClass)
.withMatchNullability(true)
.as(FilterReduceExpressionsRuleConfig.class));
}
@Deprecated // to be removed before 2.0
public FilterReduceExpressionsRule(Class<? extends Filter> filterClass,
boolean matchNullability, RelBuilderFactory relBuilderFactory) {
this(FilterReduceExpressionsRuleConfig.DEFAULT.withRelBuilderFactory(relBuilderFactory)
.as(FilterReduceExpressionsRuleConfig.class)
.withOperandFor(filterClass)
.withMatchNullability(matchNullability)
.as(FilterReduceExpressionsRuleConfig.class));
}
@Override public void onMatch(RelOptRuleCall call) {
final Filter filter = call.rel(0);
final List<RexNode> expList =
Lists.newArrayList(filter.getCondition());
RexNode newConditionExp;
boolean reduced;
final RelMetadataQuery mq = call.getMetadataQuery();
final RelOptPredicateList predicates =
mq.getPulledUpPredicates(filter.getInput());
if (reduceExpressions(filter, expList, predicates, true,
config.matchNullability(), config.treatDynamicCallsAsConstant())) {
assert expList.size() == 1;
newConditionExp = expList.get(0);
reduced = true;
} else {
// No reduction, but let's still test the original
// predicate to see if it was already a constant,
// in which case we don't need any runtime decision
// about filtering.
newConditionExp = filter.getCondition();
reduced = false;
}
// Even if no reduction, let's still test the original
// predicate to see if it was already a constant,
// in which case we don't need any runtime decision
// about filtering.
if (newConditionExp.isAlwaysTrue()) {
call.transformTo(
filter.getInput());
} else if (newConditionExp instanceof RexLiteral
|| RexUtil.isNullLiteral(newConditionExp, true)) {
call.transformTo(createEmptyRelOrEquivalent(call, filter));
} else if (reduced) {
call.transformTo(call.builder()
.push(filter.getInput())
.filter(newConditionExp).build());
} else {
if (newConditionExp instanceof RexCall) {
boolean reverse = newConditionExp.getKind() == SqlKind.NOT;
if (reverse) {
newConditionExp = ((RexCall) newConditionExp).getOperands().get(0);
}
reduceNotNullableFilter(call, filter, newConditionExp, reverse);
}
return;
}
// New plan is absolutely better than old plan.
call.getPlanner().prune(filter);
}
/**
* For static schema systems, a filter that is always false or null can be
* replaced by a values operator that produces no rows, as the schema
* information can just be taken from the input Rel. In dynamic schema
* environments, the filter might have an unknown input type, in these cases
* they must define a system specific alternative to a Values operator, such
* as inserting a limit 0 instead of a filter on top of the original input.
*
* <p>The default implementation of this method is to call
* {@link RelBuilder#empty}, which for the static schema will be optimized
* to an empty
* {@link org.apache.calcite.rel.core.Values}.
*
* @param input rel to replace, assumes caller has already determined
* equivalence to Values operation for 0 records or a
* false filter.
* @return equivalent but less expensive replacement rel
*/
protected RelNode createEmptyRelOrEquivalent(RelOptRuleCall call, Filter input) {
return call.builder().push(input).empty().build();
}
private void reduceNotNullableFilter(
RelOptRuleCall call,
Filter filter,
RexNode rexNode,
boolean reverse) {
// If the expression is a IS [NOT] NULL on a non-nullable
// column, then we can either remove the filter or replace
// it with an Empty.
boolean alwaysTrue;
switch (rexNode.getKind()) {
case IS_NULL:
case IS_UNKNOWN:
alwaysTrue = false;
break;
case IS_NOT_NULL:
alwaysTrue = true;
break;
default:
return;
}
if (reverse) {
alwaysTrue = !alwaysTrue;
}
RexNode operand = ((RexCall) rexNode).getOperands().get(0);
if (operand instanceof RexInputRef) {
RexInputRef inputRef = (RexInputRef) operand;
if (!inputRef.getType().isNullable()) {
if (alwaysTrue) {
call.transformTo(filter.getInput());
} else {
call.transformTo(createEmptyRelOrEquivalent(call, filter));
}
// New plan is absolutely better than old plan.
call.getPlanner().prune(filter);
}
}
}
/** Rule configuration. */
@Value.Immutable
public interface FilterReduceExpressionsRuleConfig extends ReduceExpressionsRule.Config {
FilterReduceExpressionsRuleConfig DEFAULT = ImmutableFilterReduceExpressionsRuleConfig.of()
.withMatchNullability(true)
.withOperandFor(LogicalFilter.class)
.withDescription("ReduceExpressionsRule(Filter)")
.as(FilterReduceExpressionsRuleConfig.class);
@Override default FilterReduceExpressionsRule toRule() {
return new FilterReduceExpressionsRule(this);
}
}
}
/** Rule that reduces constants inside a
* {@link org.apache.calcite.rel.core.Project}.
*
* @see CoreRules#PROJECT_REDUCE_EXPRESSIONS */
public static class ProjectReduceExpressionsRule
extends ReduceExpressionsRule<
ProjectReduceExpressionsRule.ProjectReduceExpressionsRuleConfig> {
/** Creates a ProjectReduceExpressionsRule. */
protected ProjectReduceExpressionsRule(ProjectReduceExpressionsRuleConfig config) {
super(config);
}
@Deprecated // to be removed before 2.0
public ProjectReduceExpressionsRule(Class<? extends Project> projectClass,
RelBuilderFactory relBuilderFactory) {
this(ProjectReduceExpressionsRuleConfig.DEFAULT.withRelBuilderFactory(relBuilderFactory)
.as(ProjectReduceExpressionsRuleConfig.class)
.withOperandFor(projectClass)
.as(ProjectReduceExpressionsRuleConfig.class));
}
@Deprecated // to be removed before 2.0
public ProjectReduceExpressionsRule(Class<? extends Project> projectClass,
boolean matchNullability, RelBuilderFactory relBuilderFactory) {
this(ProjectReduceExpressionsRuleConfig.DEFAULT.withRelBuilderFactory(relBuilderFactory)
.as(ProjectReduceExpressionsRuleConfig.class)
.withOperandFor(projectClass)
.withMatchNullability(matchNullability)
.as(ProjectReduceExpressionsRuleConfig.class));
}
@Override public void onMatch(RelOptRuleCall call) {
final Project project = call.rel(0);
final RelMetadataQuery mq = call.getMetadataQuery();
final RelOptPredicateList predicates =
mq.getPulledUpPredicates(project.getInput());
final List<RexNode> expList =
Lists.newArrayList(project.getProjects());
if (reduceExpressions(project, expList, predicates, false,
config.matchNullability(), config.treatDynamicCallsAsConstant())) {
assert !project.getProjects().equals(expList)
: "Reduced expressions should be different from original expressions";
call.transformTo(
call.builder()
.push(project.getInput())
.project(expList, project.getRowType().getFieldNames())
.build());
// New plan is absolutely better than old plan.
call.getPlanner().prune(project);
}
}
/** Rule configuration. */
@Value.Immutable
public interface ProjectReduceExpressionsRuleConfig extends ReduceExpressionsRule.Config {
ProjectReduceExpressionsRuleConfig DEFAULT = ImmutableProjectReduceExpressionsRuleConfig.of()
.withMatchNullability(true)
.withOperandFor(LogicalProject.class)
.withDescription("ReduceExpressionsRule(Project)")
.as(ProjectReduceExpressionsRuleConfig.class);
@Override default ProjectReduceExpressionsRule toRule() {
return new ProjectReduceExpressionsRule(this);
}
}
}
/** Rule that reduces constants inside a {@link Join}.
*
* @see CoreRules#JOIN_REDUCE_EXPRESSIONS */
public static class JoinReduceExpressionsRule
extends ReduceExpressionsRule<JoinReduceExpressionsRule.JoinReduceExpressionsRuleConfig> {
/** Creates a JoinReduceExpressionsRule. */
protected JoinReduceExpressionsRule(JoinReduceExpressionsRuleConfig config) {
super(config);
}
@Deprecated // to be removed before 2.0
public JoinReduceExpressionsRule(Class<? extends Join> joinClass,
RelBuilderFactory relBuilderFactory) {
this(JoinReduceExpressionsRuleConfig.DEFAULT.withRelBuilderFactory(relBuilderFactory)
.as(JoinReduceExpressionsRuleConfig.class)
.withOperandFor(joinClass)
.withMatchNullability(true)
.as(JoinReduceExpressionsRuleConfig.class));
}
@Deprecated // to be removed before 2.0
public JoinReduceExpressionsRule(Class<? extends Join> joinClass,
boolean matchNullability, RelBuilderFactory relBuilderFactory) {
this(JoinReduceExpressionsRuleConfig.DEFAULT.withRelBuilderFactory(relBuilderFactory)
.as(JoinReduceExpressionsRuleConfig.class)
.withOperandFor(joinClass)
.withMatchNullability(matchNullability)
.as(JoinReduceExpressionsRuleConfig.class));
}
@Override public void onMatch(RelOptRuleCall call) {
final Join join = call.rel(0);
final List<RexNode> expList = Lists.newArrayList(join.getCondition());
final int fieldCount = join.getLeft().getRowType().getFieldCount();
final RelMetadataQuery mq = call.getMetadataQuery();
final RelOptPredicateList leftPredicates =
mq.getPulledUpPredicates(join.getLeft());
final RelOptPredicateList rightPredicates =
mq.getPulledUpPredicates(join.getRight());
final RexBuilder rexBuilder = join.getCluster().getRexBuilder();
final RelOptPredicateList predicates =
leftPredicates.union(rexBuilder,
rightPredicates.shift(rexBuilder, fieldCount));
if (!reduceExpressions(join, expList, predicates, true,
config.matchNullability(), config.treatDynamicCallsAsConstant())) {
return;
}
call.transformTo(
join.copy(
join.getTraitSet(),
expList.get(0),
join.getLeft(),
join.getRight(),
join.getJoinType(),
join.isSemiJoinDone()));
// New plan is absolutely better than old plan.
call.getPlanner().prune(join);
}
/** Rule configuration. */
@Value.Immutable
public interface JoinReduceExpressionsRuleConfig extends ReduceExpressionsRule.Config {
JoinReduceExpressionsRuleConfig DEFAULT = ImmutableJoinReduceExpressionsRuleConfig.of()
.withMatchNullability(false)
.withOperandFor(Join.class)
.withDescription("ReduceExpressionsRule(Join)")
.as(JoinReduceExpressionsRuleConfig.class);
@Override default JoinReduceExpressionsRule toRule() {
return new JoinReduceExpressionsRule(this);
}
}
}
/**
* Rule that reduces constants inside a {@link Calc}.
*
* @see CoreRules#CALC_REDUCE_EXPRESSIONS
*/
public static class CalcReduceExpressionsRule
extends ReduceExpressionsRule<CalcReduceExpressionsRule.CalcReduceExpressionsRuleConfig> {
/** Creates a CalcReduceExpressionsRule. */
protected CalcReduceExpressionsRule(CalcReduceExpressionsRuleConfig config) {
super(config);
}
@Deprecated // to be removed before 2.0
public CalcReduceExpressionsRule(Class<? extends Calc> calcClass,
RelBuilderFactory relBuilderFactory) {
this(CalcReduceExpressionsRuleConfig.DEFAULT.withRelBuilderFactory(relBuilderFactory)
.as(CalcReduceExpressionsRuleConfig.class)
.withOperandFor(calcClass)
.withMatchNullability(true)
.as(CalcReduceExpressionsRuleConfig.class));
}
@Deprecated // to be removed before 2.0
public CalcReduceExpressionsRule(Class<? extends Calc> calcClass,
boolean matchNullability, RelBuilderFactory relBuilderFactory) {
this(CalcReduceExpressionsRuleConfig.DEFAULT.withRelBuilderFactory(relBuilderFactory)
.as(CalcReduceExpressionsRuleConfig.class)
.withOperandFor(calcClass)
.withMatchNullability(matchNullability)
.as(CalcReduceExpressionsRuleConfig.class));
}
@Override public void onMatch(RelOptRuleCall call) {
Calc calc = call.rel(0);
RexProgram program = calc.getProgram();
final List<RexNode> exprList = program.getExprList();
// Form a list of expressions with sub-expressions fully expanded.
final List<RexNode> expandedExprList = new ArrayList<>();
final RexShuttle shuttle =
new RexShuttle() {
@Override public RexNode visitLocalRef(RexLocalRef localRef) {
return expandedExprList.get(localRef.getIndex());
}
};
for (RexNode expr : exprList) {
expandedExprList.add(expr.accept(shuttle));
}
final RelOptPredicateList predicates = RelOptPredicateList.EMPTY;
if (reduceExpressions(calc, expandedExprList, predicates, false,
config.matchNullability(), config.treatDynamicCallsAsConstant())) {
final RexProgramBuilder builder =
new RexProgramBuilder(
calc.getInput().getRowType(),
calc.getCluster().getRexBuilder());
final List<RexLocalRef> list = new ArrayList<>();
for (RexNode expr : expandedExprList) {
list.add(builder.registerInput(expr));
}
if (program.getCondition() != null) {
final int conditionIndex =
program.getCondition().getIndex();
final RexNode newConditionExp =
expandedExprList.get(conditionIndex);
if (newConditionExp.isAlwaysTrue()) {
// condition is always TRUE - drop it.
} else if (newConditionExp instanceof RexLiteral
|| RexUtil.isNullLiteral(newConditionExp, true)) {
// condition is always NULL or FALSE - replace calc
// with empty.
call.transformTo(createEmptyRelOrEquivalent(call, calc));
return;
} else {
builder.addCondition(list.get(conditionIndex));
}
}
int k = 0;
for (RexLocalRef projectExpr : program.getProjectList()) {
final int index = projectExpr.getIndex();
builder.addProject(
list.get(index).getIndex(),
program.getOutputRowType().getFieldNames().get(k++));
}
call.transformTo(
calc.copy(calc.getTraitSet(), calc.getInput(), builder.getProgram()));
// New plan is absolutely better than old plan.
call.getPlanner().prune(calc);
}
}
/**
* For static schema systems, a filter that is always false or null can be
* replaced by a values operator that produces no rows, as the schema
* information can just be taken from the input Rel. In dynamic schema
* environments, the filter might have an unknown input type, in these cases
* they must define a system specific alternative to a Values operator, such
* as inserting a limit 0 instead of a filter on top of the original input.
*
* <p>The default implementation of this method is to call
* {@link RelBuilder#empty}, which for the static schema will be optimized
* to an Immutable.Config.of()
* {@link org.apache.calcite.rel.core.Values}.
*
* @param input rel to replace, assumes caller has already determined
* equivalence to Values operation for 0 records or a
* false filter.
* @return equivalent but less expensive replacement rel
*/
protected RelNode createEmptyRelOrEquivalent(RelOptRuleCall call, Calc input) {
return call.builder().push(input).empty().build();
}
/** Rule configuration. */
@Value.Immutable
public interface CalcReduceExpressionsRuleConfig extends ReduceExpressionsRule.Config {
CalcReduceExpressionsRuleConfig DEFAULT = ImmutableCalcReduceExpressionsRuleConfig.of()
.withMatchNullability(true)
.withOperandFor(LogicalCalc.class)
.withDescription("ReduceExpressionsRule(Calc)")
.as(CalcReduceExpressionsRuleConfig.class);
@Override default CalcReduceExpressionsRule toRule() {
return new CalcReduceExpressionsRule(this);
}
}
}
/** Rule that reduces constants inside a {@link Window}.
*
* @see CoreRules#WINDOW_REDUCE_EXPRESSIONS */
public static class WindowReduceExpressionsRule
extends ReduceExpressionsRule<WindowReduceExpressionsRule.WindowReduceExpressionsRuleConfig> {
/** Creates a WindowReduceExpressionsRule. */
protected WindowReduceExpressionsRule(WindowReduceExpressionsRuleConfig config) {
super(config);
}
@Deprecated // to be removed before 2.0
public WindowReduceExpressionsRule(Class<? extends Window> windowClass,
boolean matchNullability, RelBuilderFactory relBuilderFactory) {
this(WindowReduceExpressionsRuleConfig.DEFAULT.withRelBuilderFactory(relBuilderFactory)
.as(WindowReduceExpressionsRuleConfig.class)
.withOperandFor(windowClass)
.withMatchNullability(matchNullability)
.as(WindowReduceExpressionsRuleConfig.class));
}
@Override public void onMatch(RelOptRuleCall call) {
LogicalWindow window = call.rel(0);
RexBuilder rexBuilder = window.getCluster().getRexBuilder();
final RelMetadataQuery mq = call.getMetadataQuery();
final RelOptPredicateList predicates = mq
.getPulledUpPredicates(window.getInput());
boolean reduced = false;
final List<Window.Group> groups = new ArrayList<>();
for (Window.Group group : window.groups) {
List<Window.RexWinAggCall> aggCalls = new ArrayList<>();
for (Window.RexWinAggCall aggCall : group.aggCalls) {
final List<RexNode> expList = new ArrayList<>(aggCall.getOperands());
if (reduceExpressions(window, expList, predicates)) {
aggCall =
new Window.RexWinAggCall((SqlAggFunction) aggCall.getOperator(),
aggCall.type, expList,
aggCall.ordinal, aggCall.distinct, aggCall.ignoreNulls);
reduced = true;
}
aggCalls.add(aggCall);
}
final ImmutableBitSet.Builder keyBuilder = ImmutableBitSet.builder();
for (Integer key : group.keys) {
if (!predicates.constantMap.containsKey(
rexBuilder.makeInputRef(window.getInput(), key))) {
keyBuilder.set(key);
}
}
final ImmutableBitSet keys = keyBuilder.build();
reduced |= keys.cardinality() != group.keys.cardinality();
final List<RelFieldCollation> collationsList = group.orderKeys
.getFieldCollations().stream()
.filter(fc ->
!predicates.constantMap.containsKey(
rexBuilder.makeInputRef(window.getInput(),
fc.getFieldIndex())))
.collect(Collectors.toList());
boolean collationReduced =
group.orderKeys.getFieldCollations().size() != collationsList.size();
reduced |= collationReduced;
RelCollation relCollation = collationReduced
? RelCollations.of(collationsList)
: group.orderKeys;
groups.add(
new Window.Group(keys, group.isRows, group.lowerBound,
group.upperBound, group.exclude, relCollation, aggCalls));
}
if (reduced) {
call.transformTo(LogicalWindow
.create(window.getTraitSet(), window.getInput(),
window.getConstants(), window.getRowType(), groups));
call.getPlanner().prune(window);
}
}
/** Rule configuration. */
@Value.Immutable
public interface WindowReduceExpressionsRuleConfig extends ReduceExpressionsRule.Config {
WindowReduceExpressionsRuleConfig DEFAULT = ImmutableWindowReduceExpressionsRuleConfig.of()
.withMatchNullability(true)
.withOperandFor(LogicalWindow.class)
.withDescription("ReduceExpressionsRule(Window)")
.as(WindowReduceExpressionsRuleConfig.class);
@Override default WindowReduceExpressionsRule toRule() {
return new WindowReduceExpressionsRule(this);
}
}
}
//~ Constructors -----------------------------------------------------------
/** Creates a ReduceExpressionsRule. */
protected ReduceExpressionsRule(C config) {
super(config);
}
//~ Methods ----------------------------------------------------------------
/**
* Reduces a list of expressions.
*
* @param rel Relational expression
* @param expList List of expressions, modified in place
* @param predicates Constraints known to hold on input expressions
* @return whether reduction found something to change, and succeeded
*/
protected static boolean reduceExpressions(RelNode rel, List<RexNode> expList,
RelOptPredicateList predicates) {
return reduceExpressions(rel, expList, predicates, false, true, false);
}
@Deprecated // to be removed before 2.0
protected static boolean reduceExpressions(RelNode rel, List<RexNode> expList,
RelOptPredicateList predicates, boolean unknownAsFalse) {
return reduceExpressions(rel, expList, predicates, unknownAsFalse, true, false);
}
/**
* Reduces a list of expressions.
*
* <p>The {@code matchNullability} flag comes into play when reducing an
* expression whose type is nullable. Suppose we are reducing an expression
* {@code CASE WHEN 'a' = 'a' THEN 1 ELSE NULL END}. Before reduction the
* type is {@code INTEGER} (nullable), but after reduction the literal 1 has
* type {@code INTEGER NOT NULL}.
*
* <p>In some situations it is more important to preserve types; in this
* case you should use {@code matchNullability = true} (which used to be
* the default behavior of this method), and it will cast the literal to
* {@code INTEGER} (nullable).
*
* <p>In other situations, you would rather propagate the new stronger type,
* because it may allow further optimizations later; pass
* {@code matchNullability = false} and no cast will be added, but you may
* need to adjust types elsewhere in the expression tree.
*
* @param rel Relational expression
* @param expList List of expressions, modified in place
* @param predicates Constraints known to hold on input expressions
* @param unknownAsFalse Whether UNKNOWN will be treated as FALSE
* @param matchNullability Whether Calcite should add a CAST to a literal
* resulting from simplification and expression if the
* expression had nullable type and the literal is
* NOT NULL
* @param treatDynamicCallsAsConstant Whether to treat dynamic functions as
* constants
*
* @return whether reduction found something to change, and succeeded
*/
protected static boolean reduceExpressions(RelNode rel, List<RexNode> expList,
RelOptPredicateList predicates, boolean unknownAsFalse,
boolean matchNullability, boolean treatDynamicCallsAsConstant) {
final RelOptCluster cluster = rel.getCluster();
final RexBuilder rexBuilder = cluster.getRexBuilder();
final List<RexNode> originExpList = Lists.newArrayList(expList);
final RexExecutor executor =
Util.first(cluster.getPlanner().getExecutor(), RexUtil.EXECUTOR);
final RexSimplify simplify =
new RexSimplify(rexBuilder, predicates, executor);
// Simplify predicates in place
final RexUnknownAs unknownAs = RexUnknownAs.falseIf(unknownAsFalse);
final boolean reduced =
reduceExpressionsInternal(rel, simplify, unknownAs,
expList, predicates, treatDynamicCallsAsConstant);
boolean simplified = false;
for (int i = 0; i < expList.size(); i++) {
final RexNode expr2 =
simplify.simplifyPreservingType(expList.get(i), unknownAs,
matchNullability);
if (!expr2.equals(expList.get(i))) {
expList.set(i, expr2);
simplified = true;
}
}
if (reduced && simplified) {
return !originExpList.equals(expList);
}
return reduced || simplified;
}
protected static boolean reduceExpressionsInternal(RelNode rel,
RexSimplify simplify, RexUnknownAs unknownAs, List<RexNode> expList,
RelOptPredicateList predicates, boolean treatDynamicCallsAsConstant) {
// Replace predicates on CASE to CASE on predicates.
boolean changed = new CaseShuttle().mutate(expList);
// Find reducible expressions.
final List<RexNode> constExps = new ArrayList<>();
List<Boolean> addCasts = new ArrayList<>();
findReducibleExps(rel.getCluster().getTypeFactory(), expList,
predicates.constantMap, constExps, addCasts, treatDynamicCallsAsConstant);
if (constExps.isEmpty()) {
return changed;
}
final List<RexNode> constExps2 = Lists.newArrayList(constExps);
if (!predicates.constantMap.isEmpty()) {
final List<Map.Entry<RexNode, RexNode>> pairs =
Lists.newArrayList(predicates.constantMap.entrySet());
RexReplacer replacer =
new RexReplacer(simplify, unknownAs, Pair.left(pairs),
Pair.right(pairs), Collections.nCopies(pairs.size(), false));
replacer.mutate(constExps2);
}
// Compute the values they reduce to.
RexExecutor executor = rel.getCluster().getPlanner().getExecutor();
if (executor == null) {
// Cannot reduce expressions: caller has not set an executor in their
// environment. Caller should execute something like the following before
// invoking the planner:
//
// final RexExecutorImpl executor =
// new RexExecutorImpl(Schemas.createDataContext(null));
// rootRel.getCluster().getPlanner().setExecutor(executor);
return changed;
}
final List<RexNode> reducedValues = new ArrayList<>();
executor.reduce(simplify.rexBuilder, constExps2, reducedValues);
// Use RexNode.digest to judge whether each newly generated RexNode
// is equivalent to the original one.
if (RexUtil.strings(constExps).equals(RexUtil.strings(reducedValues))) {
return changed;
}
// For Project, we have to be sure to preserve the result
// types, so always cast regardless of the expression type.
// For other RelNodes like Filter, in general, this isn't necessary,
// and the presence of casts could hinder other rules such as sarg
// analysis, which require bare literals. But there are special cases,
// like when the expression is a UDR argument, that need to be
// handled as special cases.
if (rel instanceof Project) {
addCasts = Collections.nCopies(reducedValues.size(), true);
}
new RexReplacer(simplify, unknownAs, constExps, reducedValues, addCasts)
.mutate(expList);
return true;
}
/**
* Locates expressions that can be reduced to literals or converted to
* expressions with redundant casts removed.
*
* @param typeFactory Type factory
* @param exps list of candidate expressions to be examined for
* reduction
* @param constants List of expressions known to be constant
* @param constExps returns the list of expressions that can be constant
* reduced
* @param addCasts indicator for each expression that can be constant
* reduced, whether a cast of the resulting reduced
* expression is potentially necessary
* @param treatDynamicCallsAsConstant Whether to treat dynamic functions as
* constants
*/
protected static void findReducibleExps(RelDataTypeFactory typeFactory,
List<RexNode> exps, ImmutableMap<RexNode, RexNode> constants,
List<RexNode> constExps, List<Boolean> addCasts, boolean treatDynamicCallsAsConstant) {
ReducibleExprLocator gardener =
new ReducibleExprLocator(typeFactory, constants, constExps,
addCasts, treatDynamicCallsAsConstant);
for (RexNode exp : exps) {
gardener.analyze(exp);
}
assert constExps.size() == addCasts.size();
}
/** Creates a map containing each (e, constant) pair that occurs within
* a predicate list.
*
* @param clazz Class of expression that is considered constant
* @param rexBuilder Rex builder
* @param predicates Predicate list
* @param <C> what to consider a constant: {@link RexLiteral} to use a narrow
* definition of constant, or {@link RexNode} to use
* {@link RexUtil#isConstant(RexNode)}
* @return Map from values to constants
*
* @deprecated Use {@link RelOptPredicateList#constantMap}
*/
@Deprecated // to be removed before 2.0
public static <C extends RexNode> ImmutableMap<RexNode, C> predicateConstants(
Class<C> clazz, RexBuilder rexBuilder, RelOptPredicateList predicates) {
return RexUtil.predicateConstants(clazz, rexBuilder,
predicates.pulledUpPredicates);
}
/** Pushes predicates into a CASE.
*
* <p>We have a loose definition of 'predicate': any boolean expression will
* do, except CASE. For example '(CASE ...) = 5' or '(CASE ...) IS NULL'.
*/
public static RexCall pushPredicateIntoCase(RexCall call) {
if (call.getType().getSqlTypeName() != SqlTypeName.BOOLEAN) {
return call;
}
switch (call.getKind()) {
case CASE:
case AND:
case OR:
return call; // don't push CASE into CASE!
case EQUALS: {
// checks that the EQUALS operands may be split and
// doesn't push EQUALS into CASE
List<RexNode> equalsOperands = call.getOperands();
ImmutableBitSet left = RelOptUtil.InputFinder.bits(equalsOperands.get(0));
ImmutableBitSet right = RelOptUtil.InputFinder.bits(equalsOperands.get(1));
if (!left.isEmpty() && !right.isEmpty() && left.intersect(right).isEmpty()) {
return call;
}
break;
}
default:
break;
}
int caseOrdinal = -1;
final List<RexNode> operands = call.getOperands();
for (int i = 0; i < operands.size(); i++) {
RexNode operand = operands.get(i);
if (operand.getKind() == SqlKind.CASE) {
caseOrdinal = i;
}
}
if (caseOrdinal < 0) {
return call;
}
// Convert
// f(CASE WHEN p1 THEN v1 ... END, arg)
// to
// CASE WHEN p1 THEN f(v1, arg) ... END
final RexCall case_ = (RexCall) operands.get(caseOrdinal);
final List<RexNode> nodes = new ArrayList<>();
for (int i = 0; i < case_.getOperands().size(); i++) {
RexNode node = case_.getOperands().get(i);
if (!RexUtil.isCasePredicate(case_, i)) {
node = substitute(call, caseOrdinal, node);
}
nodes.add(node);
}
return case_.clone(call.getType(), nodes);
}
/** Converts op(arg0, ..., argOrdinal, ..., argN) to op(arg0,..., node, ..., argN). */
protected static RexNode substitute(RexCall call, int ordinal, RexNode node) {
final List<RexNode> newOperands = Lists.newArrayList(call.getOperands());
newOperands.set(ordinal, node);
return call.clone(call.getType(), newOperands);
}
//~ Inner Classes ----------------------------------------------------------
/**
* Replaces expressions with their reductions. Note that we only have to
* look for RexCall, since nothing else is reducible in the first place.
*/
protected static class RexReplacer extends RexShuttle {
private final RexSimplify simplify;
private final List<RexNode> reducibleExps;
private final List<RexNode> reducedValues;
private final List<Boolean> addCasts;
RexReplacer(
RexSimplify simplify,
RexUnknownAs unknownAs,
List<RexNode> reducibleExps,
List<RexNode> reducedValues,
List<Boolean> addCasts) {
this.simplify = simplify;
this.reducibleExps = reducibleExps;
this.reducedValues = reducedValues;
this.addCasts = addCasts;
}
@Override public RexNode visitInputRef(RexInputRef inputRef) {
RexNode node = visit(inputRef);
if (node == null) {
return super.visitInputRef(inputRef);
}
return node;
}
@Override public RexNode visitCall(RexCall call) {
RexNode node = visit(call);
if (node != null) {
return node;
}
node = super.visitCall(call);
return node;
}
private @Nullable RexNode visit(final RexNode call) {
int i = reducibleExps.indexOf(call);
if (i == -1) {
return null;
}
RexNode replacement = reducedValues.get(i);
if (addCasts.get(i)
&& (replacement.getType() != call.getType())) {
// Handle change from nullable to NOT NULL by claiming
// that the result is still nullable, even though
// we know it isn't.
//
// Also, we cannot reduce CAST('abc' AS VARCHAR(4)) to 'abc'.
// If we make 'abc' of type VARCHAR(4), we may later encounter
// the same expression in a Project's digest where it has
// type VARCHAR(3), and that's wrong.
RelDataType type = call.getType();
replacement = simplify.rexBuilder.makeAbstractCast(type, replacement, false);
}
return replacement;
}
}
/**
* Helper class used to locate expressions that either can be reduced to
* literals or contain redundant casts.
*/
protected static class ReducibleExprLocator extends RexVisitorImpl<Void> {
/** Whether an expression is constant, and if so, whether it can be
* reduced to a simpler constant. */
enum Constancy {
NON_CONSTANT, REDUCIBLE_CONSTANT, IRREDUCIBLE_CONSTANT
}
private final boolean treatDynamicCallsAsConstant;
private final List<Constancy> stack = new ArrayList<>();
private final ImmutableMap<RexNode, RexNode> constants;
private final List<RexNode> constExprs;
private final List<Boolean> addCasts;
private final Deque<SqlOperator> parentCallTypeStack = new ArrayDeque<>();
ReducibleExprLocator(RelDataTypeFactory typeFactory,
ImmutableMap<RexNode, RexNode> constants, List<RexNode> constExprs,
List<Boolean> addCasts, boolean treatDynamicCallsAsConstant) {
// go deep
super(true);
this.constants = constants;
this.constExprs = constExprs;
this.addCasts = addCasts;
this.treatDynamicCallsAsConstant = treatDynamicCallsAsConstant;
}
public void analyze(RexNode exp) {
assert stack.isEmpty();
exp.accept(this);
// Deal with top of stack
assert stack.size() == 1;
assert parentCallTypeStack.isEmpty();
Constancy rootConstancy = stack.get(0);
if (rootConstancy == Constancy.REDUCIBLE_CONSTANT) {
// The entire subtree was constant, so add it to the result.
addResult(exp);
}
stack.clear();
}
private Void pushVariable() {
stack.add(Constancy.NON_CONSTANT);
return null;
}
private void addResult(RexNode exp) {
// Cast of literal can't be reduced, so skip those (otherwise we'd
// go into an infinite loop as we add them back).
if (exp.getKind() == SqlKind.CAST) {
RexCall cast = (RexCall) exp;
RexNode operand = cast.getOperands().get(0);
if (operand instanceof RexLiteral) {
return;
}
if (operand instanceof RexCall) {
RexCall opCall = (RexCall) operand;
if (opCall.getKind() == SqlKind.ARRAY_VALUE_CONSTRUCTOR) {
// We can't simplify casts of arrays even if arrays are constant.
return;
}
}
}
constExprs.add(exp);
// In the case where the expression corresponds to a UDR argument,
// we need to preserve casts. Note that this only applies to
// the topmost argument, not expressions nested within the UDR
// call.
//
// REVIEW zfong 6/13/08 - Are there other expressions where we
// also need to preserve casts?
SqlOperator op = parentCallTypeStack.peek();
if (op == null) {
addCasts.add(false);
} else {
addCasts.add(isUdf(op));
}
}
private static Boolean isUdf(@SuppressWarnings("unused") SqlOperator operator) {
// return operator instanceof UserDefinedRoutine
return false;
}
@Override public Void visitInputRef(RexInputRef inputRef) {
final RexNode constant = constants.get(inputRef);
if (constant != null) {
if (constant instanceof RexCall || constant instanceof RexDynamicParam) {
constant.accept(this);
} else {
stack.add(Constancy.REDUCIBLE_CONSTANT);
}
return null;
}
return pushVariable();
}
@Override public Void visitLiteral(RexLiteral literal) {
stack.add(Constancy.IRREDUCIBLE_CONSTANT);
return null;
}
void processWindowBound(RexWindowBound bound) {
RexNode offset = bound.getOffset();
if (offset == null) {
return;
}
bound.accept(this);
Constancy constancy = Util.last(stack);
if (constancy == Constancy.REDUCIBLE_CONSTANT) {
addResult(offset);
}
Util.last(stack, 1).clear();
}
@Override public Void visitOver(RexOver over) {
// assume non-constant (running SUM(1) looks constant but isn't)
analyzeCall(over, Constancy.NON_CONSTANT);
final RexWindow window = over.getWindow();
this.processWindowBound(window.getLowerBound());
this.processWindowBound(window.getUpperBound());
return null;
}
@Override public Void visitCorrelVariable(RexCorrelVariable variable) {
return pushVariable();
}
@Override public Void visitCall(RexCall call) {
// assume REDUCIBLE_CONSTANT until proven otherwise
analyzeCall(call, Constancy.REDUCIBLE_CONSTANT);
return null;
}
@Override public Void visitSubQuery(RexSubQuery subQuery) {
analyzeCall(subQuery, Constancy.REDUCIBLE_CONSTANT);
return null;
}
private void analyzeCall(RexCall call, Constancy callConstancy) {
parentCallTypeStack.push(call.getOperator());
// visit operands, pushing their states onto stack
super.visitCall(call);
// look for NON_CONSTANT operands
int operandCount = call.getOperands().size();
List<Constancy> operandStack = Util.last(stack, operandCount);
for (Constancy operandConstancy : operandStack) {
if (operandConstancy == Constancy.NON_CONSTANT) {
callConstancy = Constancy.NON_CONSTANT;
break;
}
}
// Even if all operands are constant, the call itself may
// be non-deterministic.
if (!call.getOperator().isDeterministic()) {
callConstancy = Constancy.NON_CONSTANT;
} else if (!treatDynamicCallsAsConstant
&& call.getOperator().isDynamicFunction()) {
// In some circumstances, we should avoid caching the plan if we have dynamic functions.
// If desired, treat this situation the same as a non-deterministic function.
callConstancy = Constancy.NON_CONSTANT;
}
if (callConstancy == Constancy.NON_CONSTANT) {
// any REDUCIBLE_CONSTANT children are now known to be maximal
// reducible subtrees, so they can be added to the result
// list
for (int iOperand = 0; iOperand < operandCount; ++iOperand) {
Constancy constancy = operandStack.get(iOperand);
if (constancy == Constancy.REDUCIBLE_CONSTANT) {
addResult(call.getOperands().get(iOperand));
}
}
}
// pop operands off of the stack
operandStack.clear();
// pop this parent call operator off the stack
parentCallTypeStack.pop();
// push constancy result for this call onto stack
stack.add(callConstancy);
}
@Override public Void visitDynamicParam(RexDynamicParam dynamicParam) {
return pushVariable();
}
@Override public Void visitRangeRef(RexRangeRef rangeRef) {
return pushVariable();
}
@Override public Void visitFieldAccess(RexFieldAccess fieldAccess) {
return pushVariable();
}
@Override public Void visitLambda(RexLambda lambda) {
return pushVariable();
}
@Override public Void visitLambdaRef(RexLambdaRef lambda) {
return pushVariable();
}
}
/** Shuttle that pushes predicates into a CASE. */
protected static class CaseShuttle extends RexShuttle {
@Override public RexNode visitCall(RexCall call) {
for (;;) {
call = (RexCall) super.visitCall(call);
final RexCall old = call;
call = pushPredicateIntoCase(call);
if (call == old) {
return call;
}
}
}
}
/** Rule configuration. */
public interface Config extends RelRule.Config {
@Override ReduceExpressionsRule<?> toRule();
/** Whether to add a CAST when a nullable expression
* reduces to a NOT NULL literal. */
@Value.Default default boolean matchNullability() {
return false;
}
/** Sets {@link #matchNullability()}. */
Config withMatchNullability(boolean matchNullability);
/** Whether to treat
* {@link SqlOperator#isDynamicFunction() dynamic functions} as constants.
*
* <p>When false (the default), calls to dynamic functions (e.g.
* {@code USER}) are not reduced. When true, calls to dynamic functions
* are treated as a constant, and reduced. */
@Value.Default default boolean treatDynamicCallsAsConstant() {
return false;
}
/** Sets {@link #treatDynamicCallsAsConstant()}. */
Config withTreatDynamicCallsAsConstant(boolean treatDynamicCallsAsConstant);
/** Defines an operand tree for the given classes. */
default Config withOperandFor(Class<? extends RelNode> relClass) {
return withOperandSupplier(b -> b.operand(relClass).anyInputs())
.as(Config.class);
}
}
}