OneRangePartitionEvaluator.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.doris.nereids.rules.expression.rules;
import org.apache.doris.analysis.LiteralExpr;
import org.apache.doris.catalog.PartitionKey;
import org.apache.doris.catalog.RangePartitionItem;
import org.apache.doris.catalog.Type;
import org.apache.doris.common.Pair;
import org.apache.doris.nereids.CascadesContext;
import org.apache.doris.nereids.rules.expression.ExpressionRewriteContext;
import org.apache.doris.nereids.rules.expression.rules.OneRangePartitionEvaluator.EvaluateRangeInput;
import org.apache.doris.nereids.rules.expression.rules.OneRangePartitionEvaluator.EvaluateRangeResult;
import org.apache.doris.nereids.rules.expression.rules.PartitionRangeExpander.PartitionSlotType;
import org.apache.doris.nereids.trees.expressions.And;
import org.apache.doris.nereids.trees.expressions.EqualTo;
import org.apache.doris.nereids.trees.expressions.Expression;
import org.apache.doris.nereids.trees.expressions.GreaterThan;
import org.apache.doris.nereids.trees.expressions.GreaterThanEqual;
import org.apache.doris.nereids.trees.expressions.InPredicate;
import org.apache.doris.nereids.trees.expressions.IsNull;
import org.apache.doris.nereids.trees.expressions.LessThan;
import org.apache.doris.nereids.trees.expressions.LessThanEqual;
import org.apache.doris.nereids.trees.expressions.Not;
import org.apache.doris.nereids.trees.expressions.NullSafeEqual;
import org.apache.doris.nereids.trees.expressions.Or;
import org.apache.doris.nereids.trees.expressions.Slot;
import org.apache.doris.nereids.trees.expressions.functions.Monotonic;
import org.apache.doris.nereids.trees.expressions.functions.scalar.NonNullable;
import org.apache.doris.nereids.trees.expressions.functions.scalar.Nullable;
import org.apache.doris.nereids.trees.expressions.literal.BooleanLiteral;
import org.apache.doris.nereids.trees.expressions.literal.Literal;
import org.apache.doris.nereids.trees.expressions.literal.MaxLiteral;
import org.apache.doris.nereids.trees.expressions.literal.NullLiteral;
import org.apache.doris.nereids.trees.expressions.visitor.ExpressionVisitor;
import org.apache.doris.nereids.types.BooleanType;
import org.apache.doris.nereids.util.ExpressionUtils;
import org.apache.doris.nereids.util.Utils;
import org.apache.doris.qe.SessionVariable;
import com.google.common.base.Preconditions;
import com.google.common.collect.ImmutableList;
import com.google.common.collect.ImmutableMap;
import com.google.common.collect.ImmutableMap.Builder;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Lists;
import com.google.common.collect.Maps;
import com.google.common.collect.Range;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Objects;
import java.util.Set;
import java.util.function.BiFunction;
/**
* OneRangePartitionEvaluator.
*
* you can see the process steps in the comment of PartitionSlotInput.columnRanges
*/
public class OneRangePartitionEvaluator<K>
extends ExpressionVisitor<EvaluateRangeResult, EvaluateRangeInput>
implements OnePartitionEvaluator<K> {
private final K partitionIdent;
private final List<Slot> partitionSlots;
private final RangePartitionItem partitionItem;
private final ExpressionRewriteContext expressionRewriteContext;
private final List<PartitionSlotType> partitionSlotTypes;
private final List<Literal> lowers;
private final List<Literal> uppers;
private final List<List<Expression>> inputs;
// whether the Expression in partition range may be null.
private final Map<Expression, Boolean> partitionSlotContainsNull;
private final Map<Slot, PartitionSlotType> slotToType;
// An impossible expander/evaluator state makes pruning unsafe. Production keeps the partition;
// fe_debug throws at the point where the broken invariant is observed.
private boolean disablePruning;
/**
* Create an evaluator for one RANGE partition.
*
* <p>The constructor converts the tuple endpoints to Nereids literals, classifies every
* partition coordinate as {@code CONST}, {@code RANGE}, or {@code OTHER}, and expands the
* enumerable prefix up to {@code expandThreshold}. It also records whether each coordinate can
* contain NULL so expression evaluation can fold null-sensitive predicates safely. An unknown
* coordinate type violates the expander/evaluator contract: fe_debug reports it immediately,
* while production marks this evaluator as non-prunable.
*
* @param partitionIdent identifier returned when this partition must be scanned
* @param partitionSlots partition-key slots in lexicographic order
* @param partitionItem inclusive-lower/exclusive-upper RANGE partition definition
* @param cascadesContext planner context used by expression rewrite rules
* @param expandThreshold maximum number of enumerable values expanded from the partition range
*/
public OneRangePartitionEvaluator(K partitionIdent, List<Slot> partitionSlots,
RangePartitionItem partitionItem, CascadesContext cascadesContext, int expandThreshold) {
this.partitionIdent = partitionIdent;
this.partitionSlots = Objects.requireNonNull(partitionSlots, "partitionSlots cannot be null");
this.partitionItem = Objects.requireNonNull(partitionItem, "partitionItem cannot be null");
this.expressionRewriteContext = new ExpressionRewriteContext(
Objects.requireNonNull(cascadesContext, "cascadesContext cannot be null"));
Range<PartitionKey> range = partitionItem.getItems();
this.lowers = toNereidsLiterals(range.lowerEndpoint());
this.uppers = toNereidsLiterals(range.upperEndpoint());
this.partitionSlotTypes = PartitionRangeExpander.computePartitionSlotTypes(lowers, uppers);
if (partitionSlots.size() == 1) {
// fast path
Slot partSlot = partitionSlots.get(0);
this.slotToType = ImmutableMap.of(partSlot, partitionSlotTypes.get(0));
this.partitionSlotContainsNull = new HashMap<>();
partitionSlotContainsNull.put(partSlot, range.lowerEndpoint().getKeys().get(0).isMinValue());
} else {
// slow path
this.slotToType = Maps.newHashMap();
for (int i = 0; i < partitionSlots.size(); i++) {
slotToType.put(partitionSlots.get(i), partitionSlotTypes.get(i));
}
this.partitionSlotContainsNull = Maps.newHashMap();
for (int i = 0; i < partitionSlots.size(); i++) {
Slot slot = partitionSlots.get(i);
if (!slot.nullable()) {
partitionSlotContainsNull.put(slot, false);
continue;
}
PartitionSlotType partitionSlotType = partitionSlotTypes.get(i);
boolean maybeNull;
switch (partitionSlotType) {
case CONST:
case RANGE:
maybeNull = range.lowerEndpoint().getKeys().get(i).isMinValue();
break;
case OTHER:
maybeNull = true;
break;
default:
disablePruningOnInvalidState(
"Unknown partition slot type while deriving nullability: " + partitionSlotType);
maybeNull = true;
break;
}
partitionSlotContainsNull.put(slot, maybeNull);
}
}
List<List<Expression>> expandInputs = PartitionRangeExpander.tryExpandRange(
partitionSlots, lowers, uppers, partitionSlotTypes, expandThreshold);
// after expand range, we will get 2 dimension list like list:
// part_col1: [1], part_col2:[4, 5, 6], we should combine it to
// [1, 4], [1, 5], [1, 6] as inputs
this.inputs = Utils.allCombinations(expandInputs);
}
@Override
public K getPartitionIdent() {
return partitionIdent;
}
@Override
public List<Map<Slot, PartitionSlotInput>> getOnePartitionInputs() {
if (partitionSlots.size() == 1 && inputs.size() == 1 && inputs.get(0).size() == 1
&& inputs.get(0).get(0) instanceof Literal) {
// fast path
return computeSinglePartitionValueInputs();
} else {
// slow path
return commonComputeOnePartitionInputs();
}
}
/**
* Evaluate a partition predicate under one projected input row.
*
* <p>The projected ranges seed expression evaluation and are then narrowed by the predicate.
* If input construction or range refinement discovers an invalid internal state, returning any
* folded result could incorrectly remove data. In production this method therefore returns the
* original predicate, which {@link PartitionPruner} treats as unknown and keeps the partition.
* In fe_debug the invalid state is thrown before this fallback is reached.
*
* @param expression partition predicate to simplify
* @param currentInputs replacement expression and projected range for every partition slot
* @return the simplified predicate, or {@code expression} when pruning has been disabled
*/
@Override
public Expression evaluate(Expression expression, Map<Slot, PartitionSlotInput> currentInputs) {
if (disablePruning) {
return expression;
}
Map<Expression, ColumnRange> defaultColumnRanges = currentInputs.values().iterator().next().columnRanges;
Map<Expression, ColumnRange> rangeMap = new HashMap<>(defaultColumnRanges);
EvaluateRangeResult result = expression.accept(this, new EvaluateRangeInput(currentInputs, rangeMap));
return disablePruning ? expression : result.result;
}
@Override
public EvaluateRangeResult visit(Expression expr, EvaluateRangeInput context) {
return evaluateChildrenThenThis(expr, context);
}
@Override
public EvaluateRangeResult visitSlot(Slot slot, EvaluateRangeInput context) {
// try to replace partition slot to literal
PartitionSlotInput slotResult = context.slotToInput.get(slot);
Preconditions.checkState(slotResult != null);
Preconditions.checkState(slotResult.columnRanges.containsKey(slot));
return new EvaluateRangeResult(slotResult.result, ImmutableMap.of(slot, slotResult.columnRanges.get(slot)),
ImmutableList.of());
}
@Override
public EvaluateRangeResult visitGreaterThan(GreaterThan greaterThan, EvaluateRangeInput context) {
EvaluateRangeResult result = evaluateChildrenThenThis(greaterThan, context);
if (!(result.result instanceof GreaterThan)) {
return result;
}
greaterThan = (GreaterThan) result.result;
if (!(greaterThan.left() instanceof Literal) && greaterThan.right() instanceof Literal) {
Expression expr = greaterThan.left();
Map<Expression, ColumnRange> leftColumnRanges = result.childrenResult.get(0).columnRanges;
if (leftColumnRanges.containsKey(expr)) {
ColumnRange greaterThenRange = ColumnRange.greaterThan((Literal) greaterThan.right());
result = intersectSlotRange(result, leftColumnRanges, expr, greaterThenRange);
}
} else if (greaterThan.left() instanceof Literal && !(greaterThan.right() instanceof Literal)) {
Expression expr = greaterThan.right();
Map<Expression, ColumnRange> rightColumnRanges = result.childrenResult.get(1).columnRanges;
if (rightColumnRanges.containsKey(expr)) {
ColumnRange lessThenRange = ColumnRange.lessThen((Literal) greaterThan.left());
result = intersectSlotRange(result, rightColumnRanges, expr, lessThenRange);
}
}
return result;
}
@Override
public EvaluateRangeResult visitGreaterThanEqual(GreaterThanEqual greaterThanEqual, EvaluateRangeInput context) {
EvaluateRangeResult result = evaluateChildrenThenThis(greaterThanEqual, context);
if (!(result.result instanceof GreaterThanEqual)) {
return result;
}
greaterThanEqual = (GreaterThanEqual) result.result;
if (!(greaterThanEqual.left() instanceof Literal) && greaterThanEqual.right() instanceof Literal) {
Expression expr = greaterThanEqual.left();
Map<Expression, ColumnRange> leftColumnRanges = result.childrenResult.get(0).columnRanges;
if (leftColumnRanges.containsKey(expr)) {
ColumnRange atLeastRange = ColumnRange.atLeast((Literal) greaterThanEqual.right());
result = intersectSlotRange(result, leftColumnRanges, expr, atLeastRange);
}
} else if (greaterThanEqual.left() instanceof Literal && !(greaterThanEqual.right() instanceof Literal)) {
Expression expr = greaterThanEqual.right();
Map<Expression, ColumnRange> rightColumnRanges = result.childrenResult.get(1).columnRanges;
if (rightColumnRanges.containsKey(expr)) {
ColumnRange atMostRange = ColumnRange.atMost((Literal) greaterThanEqual.left());
result = intersectSlotRange(result, rightColumnRanges, expr, atMostRange);
}
}
return result;
}
@Override
public EvaluateRangeResult visitLessThan(LessThan lessThan, EvaluateRangeInput context) {
EvaluateRangeResult result = evaluateChildrenThenThis(lessThan, context);
if (!(result.result instanceof LessThan)) {
return result;
}
lessThan = (LessThan) result.result;
if (!(lessThan.left() instanceof Literal) && lessThan.right() instanceof Literal) {
Expression expr = lessThan.left();
Map<Expression, ColumnRange> leftColumnRanges = result.childrenResult.get(0).columnRanges;
if (leftColumnRanges.containsKey(expr)) {
ColumnRange greaterThenRange = ColumnRange.lessThen((Literal) lessThan.right());
result = intersectSlotRange(result, leftColumnRanges, expr, greaterThenRange);
}
} else if (lessThan.left() instanceof Literal && !(lessThan.right() instanceof Literal)) {
Expression expr = lessThan.right();
Map<Expression, ColumnRange> rightColumnRanges = result.childrenResult.get(1).columnRanges;
if (rightColumnRanges.containsKey(expr)) {
ColumnRange lessThenRange = ColumnRange.greaterThan((Literal) lessThan.left());
result = intersectSlotRange(result, rightColumnRanges, expr, lessThenRange);
}
}
return result;
}
@Override
public EvaluateRangeResult visitLessThanEqual(LessThanEqual lessThanEqual, EvaluateRangeInput context) {
EvaluateRangeResult result = evaluateChildrenThenThis(lessThanEqual, context);
if (!(result.result instanceof LessThanEqual)) {
return result;
}
lessThanEqual = (LessThanEqual) result.result;
if (!(lessThanEqual.left() instanceof Literal) && lessThanEqual.right() instanceof Literal) {
Expression expr = lessThanEqual.left();
Map<Expression, ColumnRange> leftColumnRanges = result.childrenResult.get(0).columnRanges;
if (leftColumnRanges.containsKey(expr)) {
ColumnRange atLeastRange = ColumnRange.atMost((Literal) lessThanEqual.right());
result = intersectSlotRange(result, leftColumnRanges, expr, atLeastRange);
}
} else if (lessThanEqual.left() instanceof Literal && !(lessThanEqual.right() instanceof Literal)) {
Expression expr = lessThanEqual.right();
Map<Expression, ColumnRange> rightColumnRanges = result.childrenResult.get(1).columnRanges;
if (rightColumnRanges.containsKey(expr)) {
ColumnRange atMostRange = ColumnRange.atLeast((Literal) lessThanEqual.left());
result = intersectSlotRange(result, rightColumnRanges, expr, atMostRange);
}
}
return result;
}
@Override
public EvaluateRangeResult visitEqualTo(EqualTo equalTo, EvaluateRangeInput context) {
EvaluateRangeResult result = evaluateChildrenThenThis(equalTo, context);
if (!(result.result instanceof EqualTo)) {
return result;
}
boolean isRejectNot = false;
if (!(equalTo.left() instanceof Literal) && equalTo.right() instanceof Literal) {
Expression expr = equalTo.left();
Map<Expression, ColumnRange> leftColumnRanges = result.childrenResult.get(0).columnRanges;
if (leftColumnRanges.containsKey(expr)) {
ColumnRange atLeastRange = ColumnRange.singleton((Literal) equalTo.right());
result = intersectSlotRange(result, leftColumnRanges, expr, atLeastRange);
if (leftColumnRanges.get(expr).isSingleton()) {
isRejectNot = true;
}
}
} else if (equalTo.left() instanceof Literal && !(equalTo.right() instanceof Literal)) {
Expression expr = equalTo.right();
Map<Expression, ColumnRange> rightColumnRanges = result.childrenResult.get(1).columnRanges;
if (rightColumnRanges.containsKey(expr)) {
ColumnRange atMostRange = ColumnRange.singleton((Literal) equalTo.left());
result = intersectSlotRange(result, rightColumnRanges, expr, atMostRange);
if (rightColumnRanges.get(expr).isSingleton()) {
isRejectNot = true;
}
}
} else {
isRejectNot = false;
}
if (!isRejectNot) {
result = result.withRejectNot(false);
}
return result;
}
@Override
public EvaluateRangeResult visitNullSafeEqual(NullSafeEqual nullSafeEqual, EvaluateRangeInput context) {
EvaluateRangeResult result = evaluateChildrenThenThis(nullSafeEqual, context);
if (!(result.result instanceof NullSafeEqual)) {
return result;
}
// "A <=> null" has been convert to "A is null" or false by NullSafeEqualToEqual rule
// so we don't consider "A <=> null" here
if (!(nullSafeEqual.left() instanceof Literal) && nullSafeEqual.right() instanceof Literal) {
// A <=> literal -> A = literal and A is not null
return visit(ExpressionUtils.and(new EqualTo(nullSafeEqual.left(), nullSafeEqual.right()),
new Not(new IsNull(nullSafeEqual.left()))), context);
} else if (nullSafeEqual.left() instanceof Literal && !(nullSafeEqual.right() instanceof Slot)) {
// literal <=> A -> literal = A and A is not null
return visit(ExpressionUtils.and(new EqualTo(nullSafeEqual.left(), nullSafeEqual.right()),
new Not(new IsNull(nullSafeEqual.right()))), context);
} else {
return result.withRejectNot(false);
}
}
@Override
public EvaluateRangeResult visitInPredicate(InPredicate inPredicate, EvaluateRangeInput context) {
if (!inPredicate.optionsAreLiterals()) {
EvaluateRangeResult result = evaluateChildrenThenThis(inPredicate, context);
if (!(result.result instanceof InPredicate)) {
return result;
}
result = result.withRejectNot(false);
return result;
}
EvaluateRangeResult leftResult = inPredicate.getCompareExpr().accept(this, context);
Map<Expression, ColumnRange> exprRanges = leftResult.columnRanges;
if (!exprRanges.containsKey(inPredicate.getCompareExpr())) {
EvaluateRangeResult result = evaluateChildrenThenThis(inPredicate, context);
if (!(result.result instanceof InPredicate)) {
return result;
}
result = result.withRejectNot(false);
return result;
}
Expression compareExpr = inPredicate.getCompareExpr();
ColumnRange compareExprRange = exprRanges.get(compareExpr);
ColumnRange optionsRange = inPredicate.getLiteralOptionsRangeSet();
ColumnRange intersect = optionsRange.intersect(compareExprRange);
Map<Expression, ColumnRange> newColumnRanges = replaceExprRange(exprRanges, compareExpr, intersect);
EvaluateRangeResult result;
if (intersect.isEmptyRange()) {
result = new EvaluateRangeResult(BooleanLiteral.FALSE, newColumnRanges, ImmutableList.of(leftResult));
} else {
result = new EvaluateRangeResult(inPredicate, newColumnRanges, ImmutableList.of(leftResult));
}
result = result.withRejectNot(false);
return result;
}
@Override
public EvaluateRangeResult visitIsNull(IsNull isNull, EvaluateRangeInput context) {
EvaluateRangeResult result = evaluateChildrenThenThis(isNull, context);
if (!(result.result instanceof IsNull)) {
return result;
}
result = result.withRejectNot(false);
Expression child = isNull.child();
if (!partitionSlotContainsNull.containsKey(child)) {
return result;
}
if (!partitionSlotContainsNull.get(child)) {
return new EvaluateRangeResult(BooleanLiteral.FALSE,
result.columnRanges, result.childrenResult, false);
}
return result;
}
/**
* Evaluate a conjunction and refine the independent column ranges with the tuple boundary.
*
* <p>The normal child evaluation first intersects the ranges contributed by every conjunct.
* A composite RANGE partition needs one additional pass: a suffix column is constrained by a
* lower or upper endpoint only while every preceding coordinate is still equal to that endpoint.
* Applying this pass after merging the children also recovers prefix coordinates whose equality
* expression was folded to a literal and therefore disappeared from the child range map.
*
* @param and conjunction being evaluated
* @param context replacement values and projected ranges for the current expanded partition input
* @return the folded conjunction together with its lexicographically refined column ranges
*/
@Override
public EvaluateRangeResult visitAnd(And and, EvaluateRangeInput context) {
EvaluateRangeResult result = evaluateChildrenThenThis(and, context);
EvaluateRangeResult andResult = result.childrenResult.get(0);
for (int i = 1; i < result.childrenResult.size(); i++) {
andResult = mergeRanges(result.result, andResult, result.childrenResult.get(i),
context.rangeMap,
(leftRange, rightRange) -> leftRange.intersect(rightRange));
}
andResult = returnFalseIfExistEmptyRange(andResult);
if (andResult.result.equals(BooleanLiteral.FALSE)) {
return andResult;
}
// shrink range and prune the other type: if previous column is literal and equals to the bound
andResult = determinateRangeOfOtherType(andResult, lowers, true, context.rangeMap);
andResult = determinateRangeOfOtherType(andResult, uppers, false, context.rangeMap);
return andResult;
}
@Override
public EvaluateRangeResult visitOr(Or or, EvaluateRangeInput context) {
EvaluateRangeResult result = evaluateChildrenThenThis(or, context);
if (result.result.equals(BooleanLiteral.FALSE)) {
return result;
}
List<EvaluateRangeResult> nonFalseResults = new ArrayList<>();
for (EvaluateRangeResult evaluateRangeResult : result.childrenResult) {
if (!evaluateRangeResult.result.equals(BooleanLiteral.FALSE)) {
nonFalseResults.add(evaluateRangeResult);
}
}
if (nonFalseResults.size() == 1) {
return new EvaluateRangeResult(result.result, nonFalseResults.get(0).columnRanges, result.childrenResult);
}
EvaluateRangeResult orResult = nonFalseResults.get(0);
for (int i = 1; i < nonFalseResults.size(); i++) {
orResult = mergeRanges(result.result, orResult, nonFalseResults.get(i),
context.rangeMap,
(leftRange, rightRange) -> leftRange.union(rightRange));
}
return returnFalseIfExistEmptyRange(orResult);
}
@Override
public EvaluateRangeResult visitNot(Not not, EvaluateRangeInput context) {
EvaluateRangeResult result = evaluateChildrenThenThis(not, context);
if (result.isRejectNot() && !result.result.equals(BooleanLiteral.TRUE)) {
Map<Expression, ColumnRange> newRanges = Maps.newHashMap();
for (Map.Entry<Expression, ColumnRange> entry : result.childrenResult.get(0).columnRanges.entrySet()) {
Expression expr = entry.getKey();
ColumnRange childRange = entry.getValue();
ColumnRange partitionRange = context.rangeMap.containsKey(expr)
? context.rangeMap.get(expr) : ColumnRange.all();
newRanges.put(expr, partitionRange.intersect(childRange.complete()));
}
result = new EvaluateRangeResult(result.result, newRanges, result.childrenResult);
}
return returnFalseIfExistEmptyRange(result);
}
private EvaluateRangeResult evaluateChildrenThenThis(Expression expr, EvaluateRangeInput context) {
// evaluate children
List<Expression> children = expr.children();
ImmutableList.Builder<Expression> newChildren = ImmutableList.builderWithExpectedSize(children.size());
List<EvaluateRangeResult> childrenResults = new ArrayList<>(children.size());
boolean hasNewChildren = false;
for (int i = 0; i < children.size(); i++) {
Expression child = children.get(i);
EvaluateRangeResult childResult;
if (child instanceof Monotonic) {
childResult = visitMonotonic(child, context);
} else {
childResult = child.accept(this, context);
}
if (!childResult.result.equals(child)) {
hasNewChildren = true;
}
childrenResults.add(childResult);
newChildren.add(childResult.result);
}
if (hasNewChildren) {
expr = expr.withChildren(newChildren.build());
}
// evaluate this
expr = FoldConstantRuleOnFE.evaluate(expr, expressionRewriteContext);
return new EvaluateRangeResult(expr, ImmutableMap.of(), childrenResults);
}
private EvaluateRangeResult returnFalseIfExistEmptyRange(EvaluateRangeResult result) {
Expression expr = result.result;
if (expr.getDataType() instanceof BooleanType && !(expr instanceof Literal)
&& result.columnRanges.values().stream().anyMatch(ColumnRange::isEmptyRange)) {
return new EvaluateRangeResult(BooleanLiteral.FALSE, result.columnRanges, result.childrenResult);
}
return result;
}
private EvaluateRangeResult intersectSlotRange(EvaluateRangeResult originResult,
Map<Expression, ColumnRange> columnRanges, Expression expr, ColumnRange otherRange) {
ColumnRange columnRange = columnRanges.get(expr);
ColumnRange intersect = columnRange.intersect(otherRange);
Map<Expression, ColumnRange> newColumnRanges = replaceExprRange(columnRanges, expr, intersect);
if (intersect.isEmptyRange()) {
return new EvaluateRangeResult(BooleanLiteral.FALSE, newColumnRanges, originResult.childrenResult);
} else {
return new EvaluateRangeResult(originResult.result, newColumnRanges, originResult.childrenResult);
}
}
/**
* Refine the first unresolved suffix column against one lexicographic partition endpoint.
*
* <p>Partition slot types have the shape {@code CONST*, RANGE, OTHER*}. The scan proceeds from
* left to right and keeps an endpoint active only while the observed singleton values equal its
* prefix. For the first unresolved {@code OTHER} coordinate, the active lower endpoint contributes
* {@code >= bound}; an active upper endpoint contributes {@code <= bound}, except that the final
* partition column uses {@code < bound} because RANGE partitions are upper-exclusive. The method
* returns immediately after that coordinate because once it may differ from the endpoint, later
* coordinates are lexicographically unconstrained.
*
* <p>Constant folding can remove an expanded {@code RANGE} slot from {@code context.columnRanges}.
* For that slot only, the method reads the singleton from {@code defaultColumnRanges} so the
* omitted equal-prefix coordinate can still participate in prefix comparison. A missing
* {@code OTHER} slot is different: its default range describes only the partition boundary, not
* the predicate. Adding it to the predicate result would let {@code NOT} complement a synthetic
* range and could incorrectly prune the partition, so a missing {@code OTHER} stops refinement.
*
* @param context result of merging all conjunct ranges
* @param partitionBound lower or upper endpoint of the composite partition
* @param isLowerBound whether {@code partitionBound} is the inclusive lower endpoint
* @param defaultColumnRanges projected ranges for the current expanded partition input
* @return {@code context} refined at the first decisive suffix coordinate, or an equivalent
* false result if the refined range is empty
*/
private EvaluateRangeResult determinateRangeOfOtherType(
EvaluateRangeResult context, List<Literal> partitionBound, boolean isLowerBound,
Map<Expression, ColumnRange> defaultColumnRanges) {
if (context.result instanceof Literal) {
return context;
}
LexicographicBoundState boundState = new LexicographicBoundState(
partitionBound, isLowerBound, partitionSlots.size());
for (int i = 0; i < partitionSlotTypes.size(); i++) {
PartitionSlotType partitionSlotType = partitionSlotTypes.get(i);
Slot slot = partitionSlots.get(i);
ColumnRange columnRange = context.columnRanges.get(slot);
switch (partitionSlotType) {
case CONST: continue;
case RANGE:
// Expanded RANGE literals can disappear after constant folding. Recover only this
// equal-prefix coordinate from the partition projection.
if (columnRange == null) {
columnRange = defaultColumnRanges.get(slot);
}
if (columnRange == null || !columnRange.isSingleton()) {
return context;
}
boundState.observeLiteral(columnRange.getLowerBound().getValue(), i);
if (!boundState.hasEqualPrefix()) {
return context;
}
continue;
case OTHER:
// Do not expose a default-only partition range to the predicate tree. In
// particular, visitNot() must never complement a range that the predicate did
// not contribute.
if (columnRange == null) {
return context;
}
if (columnRange.isSingleton()
&& columnRange.getLowerBound().getValue().equals(partitionBound.get(i))
&& i + 1 < partitionSlots.size()) {
continue;
}
ColumnRange newRange = boundState.constrainFirstUnresolvedColumn(columnRange, i);
Map<Expression, ColumnRange> newRanges = replaceExprRange(
context.columnRanges, slot, newRange);
return newRange.isEmptyRange()
? new EvaluateRangeResult(BooleanLiteral.FALSE, newRanges, context.childrenResult)
: new EvaluateRangeResult(context.result, newRanges, context.childrenResult);
default:
disablePruningOnInvalidState(
"Unknown partition slot type while refining a lexicographic bound: "
+ partitionSlotType);
return context;
}
}
return context;
}
private Map<Expression, ColumnRange> replaceExprRange(Map<Expression, ColumnRange> originRange, Expression expr,
ColumnRange range) {
LinkedHashMap<Expression, ColumnRange> newRanges = Maps.newLinkedHashMap(originRange);
newRanges.put(expr, range);
return ImmutableMap.copyOf(newRanges);
}
private EvaluateRangeResult mergeRanges(
Expression originResult, EvaluateRangeResult left, EvaluateRangeResult right,
Map<Expression, ColumnRange> rangeMap,
BiFunction<ColumnRange, ColumnRange, ColumnRange> mergeFunction) {
Map<Expression, ColumnRange> leftRanges = left.columnRanges;
Map<Expression, ColumnRange> rightRanges = right.columnRanges;
if (leftRanges.equals(rightRanges)) {
return new EvaluateRangeResult(originResult, leftRanges, ImmutableList.of(left, right));
}
Set<Expression> exprs = ImmutableSet.<Expression>builder()
.addAll(leftRanges.keySet())
.addAll(rightRanges.keySet())
.build();
Map<Expression, ColumnRange> mergedRange = exprs.stream()
.map(expr -> Pair.of(expr, mergeFunction.apply(
leftRanges.containsKey(expr) ? leftRanges.get(expr) : rangeMap.get(expr),
rightRanges.containsKey(expr) ? rightRanges.get(expr) : rangeMap.get(expr))))
.collect(ImmutableMap.toImmutableMap(Pair::key, Pair::value));
return new EvaluateRangeResult(originResult, mergedRange, ImmutableList.of(left, right));
}
private List<Literal> toNereidsLiterals(PartitionKey partitionKey) {
if (partitionKey.getKeys().size() == 1) {
// fast path
return toSingleNereidsLiteral(partitionKey);
}
// slow path
return toMultiNereidsLiterals(partitionKey);
}
private List<Literal> toSingleNereidsLiteral(PartitionKey partitionKey) {
List<LiteralExpr> keys = partitionKey.getKeys();
LiteralExpr literalExpr = keys.get(0);
Type type = literalExpr.getType();
return ImmutableList.of(Literal.fromLegacyLiteral(literalExpr, type));
}
private List<Literal> toMultiNereidsLiterals(PartitionKey partitionKey) {
List<LiteralExpr> keys = partitionKey.getKeys();
List<Literal> literals = Lists.newArrayListWithCapacity(keys.size());
for (int i = 0; i < keys.size(); i++) {
LiteralExpr literalExpr = keys.get(i);
Type type = literalExpr.getType();
literals.add(Literal.fromLegacyLiteral(literalExpr, type));
}
return literals;
}
private Map<Slot, PartitionSlotInput> fillSlotRangesToInputs(
Map<Slot, PartitionSlotInput> inputs) {
Builder<Expression, ColumnRange> allColumnRangesBuilder =
ImmutableMap.builderWithExpectedSize(16);
for (Entry<Slot, PartitionSlotInput> entry : inputs.entrySet()) {
allColumnRangesBuilder.put(entry.getKey(), entry.getValue().columnRanges.get(entry.getKey()));
}
Map<Expression, ColumnRange> allColumnRanges = allColumnRangesBuilder.build();
Builder<Slot, PartitionSlotInput> partitionSlotInputs =
ImmutableMap.builderWithExpectedSize(16);
for (Slot slot : inputs.keySet()) {
partitionSlotInputs.put(slot, new PartitionSlotInput(inputs.get(slot).result, allColumnRanges));
}
return partitionSlotInputs.build();
}
/** EvaluateRangeInput */
public static class EvaluateRangeInput {
private final Map<Slot, PartitionSlotInput> slotToInput;
private final Map<Expression, ColumnRange> rangeMap;
public EvaluateRangeInput(Map<Slot, PartitionSlotInput> slotToInput, Map<Expression, ColumnRange> rangeMap) {
this.slotToInput = slotToInput;
this.rangeMap = rangeMap;
}
}
/**
* EvaluateRangeResult.
*
* bind expression and ColumnRange, so we can not only compute expression tree, but also compute range.
* if column range is empty range, the predicate should return BooleanLiteral.FALSE, means this partition
* can be pruned.
*/
public static class EvaluateRangeResult {
private final Expression result;
private final Map<Expression, ColumnRange> columnRanges;
// private final Map<Slot, ColumnRange> columnRanges;
private final List<EvaluateRangeResult> childrenResult;
// rejectNot = true, if \exist e \in R, pred(e)=true, then we have \forAll e \in R, !pred(e)=false
// that is, if pred holds true over R, then !pred does not hold true over R.
// example 1. rejectNot=false
// R=(1,10), pred: k = 5. "k = 5" holds true over R, and "NOT k = 5" holds true over R.
// example 2. rejectNot=false
// R=(1,10), pred: k = 11. "k=10" dose not holds over R
// example 3. rejectNot=false
// R=(1,10), pred: k in (4, 5). "k in (4, 5)" holds true over R, and "NOT k in (4, 5)" holds over R
// example 3. rejectNot=true
// R=(1,10), pred: k < 11. "k<11" holds true over R, and "NOT k<11" dose not hold over R
private final boolean rejectNot;
public EvaluateRangeResult(Expression result, Map<Expression, ColumnRange> columnRanges,
List<EvaluateRangeResult> childrenResult, boolean rejectNot) {
this.result = result;
this.columnRanges = columnRanges;
this.childrenResult = childrenResult;
this.rejectNot = rejectNot;
}
public EvaluateRangeResult(Expression result, Map<Expression, ColumnRange> columnRanges,
List<EvaluateRangeResult> childrenResult) {
this(result, columnRanges, childrenResult, allIsRejectNot(childrenResult));
}
public EvaluateRangeResult withRejectNot(boolean rejectNot) {
return new EvaluateRangeResult(result, columnRanges, childrenResult, rejectNot);
}
public boolean isRejectNot() {
return rejectNot;
}
private static boolean allIsRejectNot(List<EvaluateRangeResult> childrenResult) {
for (EvaluateRangeResult evaluateRangeResult : childrenResult) {
if (!evaluateRangeResult.isRejectNot()) {
return false;
}
}
return true;
}
}
@Override
public boolean isDefaultPartition() {
return partitionItem.isDefaultPartition();
}
private List<Map<Slot, PartitionSlotInput>> computeSinglePartitionValueInputs() {
Slot partitionSlot = partitionSlots.get(0);
Literal literal = (Literal) inputs.get(0).get(0);
ColumnRange slotRange = ColumnRange.singleton(literal);
ImmutableMap<Expression, ColumnRange> slotToRange = ImmutableMap.of(partitionSlot, slotRange);
Map<Slot, PartitionSlotInput> slotToInputs =
ImmutableMap.of(partitionSlot, new PartitionSlotInput(literal, slotToRange));
return ImmutableList.of(slotToInputs);
}
/**
* Build evaluator inputs for every expanded representation of this composite RANGE partition.
*
* <p>Range expansion replaces enumerable coordinates with literals and leaves unexpanded
* coordinates as slots. Separate lower- and upper-bound states track whether the literal prefix
* of each generated input still equals the corresponding endpoint. Only the first unresolved
* coordinate while a state is active receives that endpoint's constraint; after it can diverge,
* all suffix coordinates remain unbounded. This preserves tuple ordering instead of incorrectly
* treating each partition column as an independent interval.
*
* <p>The returned {@link PartitionSlotInput}s all contain the complete projected range map for
* their generated input. Expression evaluation can therefore recover ranges for slots that were
* replaced by literals and removed by constant folding.
*
* <p>A {@code CONST} coordinate must have been expanded to a literal. If it is not, the input is
* structurally invalid: fe_debug throws, while production makes the coordinate unbounded and
* disables pruning for the whole evaluator so planning can continue without dropping data.
*
* @return one slot-to-input map for each Cartesian-product row produced by range expansion
*/
private List<Map<Slot, PartitionSlotInput>> commonComputeOnePartitionInputs() {
List<Map<Slot, PartitionSlotInput>> onePartitionInputs = Lists.newArrayListWithCapacity(inputs.size());
for (List<Expression> input : inputs) {
LexicographicBoundState lowerState = new LexicographicBoundState(
lowers, true, partitionSlots.size());
LexicographicBoundState upperState = new LexicographicBoundState(
uppers, false, partitionSlots.size());
Builder<Slot, PartitionSlotInput> slotToInputs = ImmutableMap.builderWithExpectedSize(16);
for (int i = 0; i < partitionSlots.size(); ++i) {
Slot partitionSlot = partitionSlots.get(i);
// partitionSlot will be replaced to this expression
Expression expression = input.get(i);
ColumnRange slotRange;
PartitionSlotType partitionSlotType = partitionSlotTypes.get(i);
if (expression instanceof Literal) {
// const or expanded range
slotRange = ColumnRange.singleton((Literal) expression);
lowerState.observeLiteral(expression, i);
upperState.observeLiteral(expression, i);
} else {
// The first unresolved column carries every still-active lexicographic bound.
// Once that column can diverge, every suffix column must remain unbounded.
switch (partitionSlotType) {
case RANGE:
case OTHER:
slotRange = lowerState.constrainFirstUnresolvedColumn(ColumnRange.all(), i);
slotRange = upperState.constrainFirstUnresolvedColumn(slotRange, i);
break;
case CONST:
disablePruningOnInvalidState("CONST partition input must be a literal: slot="
+ partitionSlot + ", expression=" + expression);
slotRange = ColumnRange.all();
lowerState.diverge();
upperState.diverge();
break;
default:
disablePruningOnInvalidState(
"Unknown partition slot type while building evaluator inputs: "
+ partitionSlotType);
slotRange = ColumnRange.all();
lowerState.diverge();
upperState.diverge();
}
}
ImmutableMap<Expression, ColumnRange> slotToRange = ImmutableMap.of(partitionSlot, slotRange);
slotToInputs.put(partitionSlot, new PartitionSlotInput(expression, slotToRange));
}
Map<Slot, PartitionSlotInput> slotPartitionSlotInputMap = fillSlotRangesToInputs(slotToInputs.build());
onePartitionInputs.add(slotPartitionSlotInputMap);
}
return onePartitionInputs;
}
/**
* Handle a state that violates the contract between {@link PartitionRangeExpander} and this evaluator.
*
* <p>Tests and debugging sessions set {@code fe_debug=true}, so they fail immediately and expose
* the broken invariant. Production planning must remain available: after logging the problem,
* evaluation returns the original predicate for this partition, which conservatively keeps it.
*
* @param message description of the invalid state
*/
private void disablePruningOnInvalidState(String message) {
SessionVariable.throwAnalysisExceptionWhenFeDebug(message);
disablePruning = true;
}
/** Describes whether the coordinates already consumed are still equal to an endpoint prefix. */
private enum BoundPrefixState {
/** No consumed coordinate differs from the tracked lower or upper endpoint. */
EQUAL_PREFIX,
/** An earlier coordinate can differ, so this endpoint cannot constrain any later coordinate. */
DIVERGED
}
/**
* Tracks one lower or upper endpoint while projected ranges are built or refined.
*
* <p>Lexicographic comparison makes an endpoint relevant only as long as all preceding
* coordinates equal its prefix. For example, with lower endpoint {@code (1, 10, 100)}, an input
* whose first coordinate is {@code 1} must constrain the first unresolved coordinate to
* {@code >= 10}. If the first coordinate is {@code 2}, the lower endpoint is already satisfied
* and neither the second nor third coordinate receives a lower constraint.
*
* <p>The state is monotonic: it starts at {@link BoundPrefixState#EQUAL_PREFIX} and can transition
* to {@link BoundPrefixState#DIVERGED} only once.
*/
private static class LexicographicBoundState {
private final List<Literal> bound;
private final boolean lowerBound;
private final int columnCount;
private BoundPrefixState prefixState = BoundPrefixState.EQUAL_PREFIX;
/**
* Create state for one endpoint of a composite partition.
*
* @param bound endpoint values in partition-column order
* @param lowerBound true for the inclusive lower endpoint, false for the exclusive upper endpoint
* @param columnCount total number of partition columns, used to identify the final coordinate
*/
private LexicographicBoundState(List<Literal> bound, boolean lowerBound, int columnCount) {
this.bound = bound;
this.lowerBound = lowerBound;
this.columnCount = columnCount;
}
/**
* Return whether every coordinate observed so far is equal to this endpoint's prefix.
*
* @return true while this endpoint may still constrain the next unresolved coordinate
*/
private boolean hasEqualPrefix() {
return prefixState == BoundPrefixState.EQUAL_PREFIX;
}
/**
* Consume a literal coordinate and deactivate this endpoint if the literal differs from it.
*
* <p>Once a coordinate differs, later values cannot make the tuple equal to the endpoint
* again, so an already-diverged state is intentionally left unchanged.
*
* @param literal literal selected for the current partition coordinate
* @param index zero-based partition-column index of {@code literal}
*/
private void observeLiteral(Expression literal, int index) {
if (hasEqualPrefix() && !literal.equals(bound.get(index))) {
diverge();
}
}
/**
* Intersect an unresolved coordinate with this endpoint when its prefix is still equal.
*
* <p>The lower endpoint is inclusive on every coordinate. The upper endpoint is inclusive on
* non-terminal coordinates because equality there leaves later coordinates to decide tuple
* membership; only the final coordinate is exclusive. Consuming an unresolved coordinate
* always deactivates the endpoint so no suffix coordinate is independently constrained.
*
* @param origin range already inferred for the unresolved coordinate
* @param index zero-based partition-column index of that coordinate
* @return {@code origin} intersected with the active endpoint, or unchanged if an earlier
* coordinate has already diverged
*/
private ColumnRange constrainFirstUnresolvedColumn(ColumnRange origin, int index) {
if (!hasEqualPrefix()) {
return origin;
}
diverge();
Literal boundary = bound.get(index);
ColumnRange boundaryRange;
if (lowerBound) {
boundaryRange = ColumnRange.atLeast(boundary);
} else if (index + 1 == columnCount) {
boundaryRange = ColumnRange.lessThen(boundary);
} else {
boundaryRange = ColumnRange.atMost(boundary);
}
return origin.intersect(boundaryRange);
}
/** Mark this endpoint as satisfied or violated by an earlier decisive coordinate. */
private void diverge() {
prefixState = BoundPrefixState.DIVERGED;
}
}
public EvaluateRangeResult visitMonotonic(Expression monotonic, EvaluateRangeInput context) {
EvaluateRangeResult rangeResult = evaluateChildrenThenThis(monotonic, context);
if (!rangeResult.result.getClass().equals(monotonic.getClass())) {
return rangeResult;
}
return computeMonotonicFunctionRange(rangeResult, context);
}
private EvaluateRangeResult computeMonotonicFunctionRange(EvaluateRangeResult result, EvaluateRangeInput context) {
Monotonic func = (Monotonic) result.result;
if (context.rangeMap.containsKey(func)) {
return new EvaluateRangeResult((Expression) func, ImmutableMap.of((Expression) func,
context.rangeMap.get(func)), result.childrenResult);
}
int childIndex = func.getMonotonicFunctionChildIndex();
Expression funcChild = func.child(childIndex);
boolean isNullable = partitionSlotContainsNull.getOrDefault(funcChild, true);
Expression withNullable = func.withConstantArgs(isNullable ? new Nullable(funcChild)
: new NonNullable(funcChild));
partitionSlotContainsNull.put((Expression) func, withNullable.nullable());
if (!result.childrenResult.get(childIndex).columnRanges.containsKey(funcChild)) {
return result;
}
ColumnRange childRange = result.childrenResult.get(childIndex).columnRanges.get(funcChild);
if (childRange.isEmptyRange() || childRange.asRanges().size() != 1
|| (!childRange.span().hasLowerBound() && !childRange.span().hasUpperBound())) {
return result;
}
Range<ColumnBound> span = childRange.span();
// null means positive infinity or negative infinity
Literal lower = span.hasLowerBound() ? span.lowerEndpoint().getValue() : null;
Literal upper = span.hasUpperBound() && !(span.upperEndpoint().getValue() instanceof MaxLiteral)
? span.upperEndpoint().getValue() : null;
if (!func.isMonotonic(lower, upper)) {
return result;
}
Expression lowerValue = lower != null ? FoldConstantRuleOnFE.evaluate(func.withConstantArgs(lower),
expressionRewriteContext) : null;
Expression upperValue = upper != null ? FoldConstantRuleOnFE.evaluate(func.withConstantArgs(upper),
expressionRewriteContext) : null;
if (!checkFoldConstantValueIsValid(lowerValue, upperValue)) {
return result;
}
if (!func.isPositive()) {
Expression temp = lowerValue;
lowerValue = upperValue;
upperValue = temp;
}
LinkedHashMap<Expression, ColumnRange> newRanges = Maps.newLinkedHashMap();
ColumnRange newRange = ColumnRange.all();
if (lowerValue instanceof Literal && upperValue instanceof Literal && lowerValue.equals(upperValue)) {
newRange = ColumnRange.singleton((Literal) lowerValue);
context.rangeMap.put((Expression) func, newRange);
newRanges.put((Expression) func, newRange);
return new EvaluateRangeResult(lowerValue, newRanges, result.childrenResult);
} else {
if (lowerValue instanceof Literal) {
newRange = newRange.withLowerBound((Literal) lowerValue);
}
if (upperValue instanceof Literal) {
newRange = newRange.withUpperBound((Literal) upperValue);
}
if (newRange.isEmptyRange() || !newRange.span().hasLowerBound() && !newRange.span().hasUpperBound()) {
return result;
}
context.rangeMap.put((Expression) func, newRange);
newRanges.put((Expression) func, newRange);
return new EvaluateRangeResult((Expression) func, newRanges, result.childrenResult);
}
}
// only allow literal(except NullLiteral) and null
private boolean checkFoldConstantValueIsValid(Expression lowerValue, Expression upperValue) {
if (lowerValue instanceof NullLiteral || upperValue instanceof NullLiteral) {
return false;
}
return (lowerValue == null || lowerValue instanceof Literal)
&& (upperValue == null || upperValue instanceof Literal);
}
}