This is an automated email from the ASF dual-hosted git repository.
morrysnow pushed a commit to branch branch-2.1
in repository https://gitbox.apache.org/repos/asf/doris.git
The following commit(s) were added to refs/heads/branch-2.1 by this push:
new c4a10849d54 branch-2.1: [fix](nereids) fix nereids dead loop due to
simplify range output in-predicate's options in random order #47830 (#47828)
c4a10849d54 is described below
commit c4a10849d543f65c714a2ca7d419a0765cae5590
Author: yujun <[email protected]>
AuthorDate: Thu Feb 13 11:10:22 2025 +0800
branch-2.1: [fix](nereids) fix nereids dead loop due to simplify range
output in-predicate's options in random order #47830 (#47828)
### What problem does this PR solve?
cherry-pick: #47830
#45181 introduce a dead loop for nereids optimizer, then cause error
'Nereids cost too much time'.
simplify range process in-predicate steps as follow:
1. Extract in-predicate's options into a set S1;
2. Use a discrete value desc to hold the value, use a new set S2, and
S2.addAll(S1);
3. Turn discrete value desc back to a new in-predicate, the new
in-predicate's options add all S2.
Before #45181, S2 is an order set(TreeSet)， so the result in-predicate's
options are always order. But this PR change S2 as a unorder
set(HashSet). Then will cause dead loop: in-predicate => S1 => new S2 =>
new in-predicate => new S1 => new S2 => ...
fix:
1. S1 use linked hash set;
2. don't use a new S2, just let S2 = S1;
then the result in-predicate's options' order will be kept.
---
.../rules/expression/rules/SimplifyRange.java | 55 ++++++++++++----------
.../expression/test_simplify_range.groovy | 34 +++++++++++++
2 files changed, 65 insertions(+), 24 deletions(-)
diff --git
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/expression/rules/SimplifyRange.java
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/expression/rules/SimplifyRange.java
index 7931cef1019..d5fd8e24783 100644
---
a/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/expression/rules/SimplifyRange.java
+++
b/fe/fe-core/src/main/java/org/apache/doris/nereids/rules/expression/rules/SimplifyRange.java
@@ -49,7 +49,6 @@ import com.google.common.collect.Range;
import com.google.common.collect.Sets;
import java.util.ArrayList;
-import java.util.Arrays;
import java.util.Collection;
import java.util.Iterator;
import java.util.LinkedHashMap;
@@ -231,10 +230,16 @@ public class SimplifyRange implements
ExpressionPatternRuleFactory {
public abstract ValueDesc intersect(ValueDesc other);
public static ValueDesc intersect(ExpressionRewriteContext context,
RangeValue range, DiscreteValue discrete) {
- DiscreteValue result = new DiscreteValue(context,
discrete.reference, discrete.toExpr);
- discrete.values.stream().filter(x ->
range.range.contains(x)).forEach(result.values::add);
- if (!result.values.isEmpty()) {
- return result;
+ // Since in-predicate's options is a list, the discrete values
need to kept options' order.
+ // If not keep options' order, the result in-predicate's option
list will not equals to
+ // the input in-predicate, later nereids will need to simplify the
new in-predicate,
+ // then cause dead loop.
+ Set<Literal> newValues = discrete.values.stream()
+ .filter(x -> range.range.contains(x))
+ .collect(Collectors.toCollection(
+ () ->
Sets.newLinkedHashSetWithExpectedSize(discrete.values.size())));
+ if (!newValues.isEmpty()) {
+ return new DiscreteValue(context, discrete.reference,
discrete.toExpr, newValues);
}
Expression originExpr = FoldConstantRuleOnFE.evaluate(
ExpressionUtils.and(range.toExpr, discrete.toExpr),
context);
@@ -246,7 +251,7 @@ public class SimplifyRange implements
ExpressionPatternRuleFactory {
public static ValueDesc range(ExpressionRewriteContext context,
ComparisonPredicate predicate) {
Literal value = (Literal) predicate.right();
if (predicate instanceof EqualTo) {
- return new DiscreteValue(context, predicate.left(), predicate,
value);
+ return new DiscreteValue(context, predicate.left(), predicate,
Sets.newHashSet(value));
}
RangeValue rangeValue = new RangeValue(context, predicate.left(),
predicate);
if (predicate instanceof GreaterThanEqual) {
@@ -263,8 +268,15 @@ public class SimplifyRange implements
ExpressionPatternRuleFactory {
}
public static ValueDesc discrete(ExpressionRewriteContext context,
InPredicate in) {
+ // Since in-predicate's options is a list, the discrete values
need to kept options' order.
+ // If not keep options' order, the result in-predicate's option
list will not equals to
+ // the input in-predicate, later nereids will need to simplify the
new in-predicate,
+ // then cause dead loop.
// Set<Literal> literals = (Set)
Utils.fastToImmutableSet(in.getOptions());
- Set<Literal> literals =
in.getOptions().stream().map(Literal.class::cast).collect(Collectors.toSet());
+ Set<Literal> literals = in.getOptions().stream()
+ .map(Literal.class::cast)
+ .collect(Collectors.toCollection(
+ () ->
Sets.newLinkedHashSetWithExpectedSize(in.getOptions().size())));
return new DiscreteValue(context, in.getCompareExpr(), in,
literals);
}
}
@@ -398,17 +410,12 @@ public class SimplifyRange implements
ExpressionPatternRuleFactory {
* a in (1,2,3) => [1,2,3]
*/
private static class DiscreteValue extends ValueDesc {
- Set<Literal> values;
+ final Set<Literal> values;
public DiscreteValue(ExpressionRewriteContext context,
- Expression reference, Expression toExpr, Literal... values) {
- this(context, reference, toExpr, Arrays.asList(values));
- }
-
- public DiscreteValue(ExpressionRewriteContext context,
- Expression reference, Expression toExpr, Collection<Literal>
values) {
+ Expression reference, Expression toExpr, Set<Literal> values) {
super(context, reference, toExpr);
- this.values = Sets.newHashSet(values);
+ this.values = values;
}
@Override
@@ -419,10 +426,11 @@ public class SimplifyRange implements
ExpressionPatternRuleFactory {
if (other instanceof DiscreteValue) {
Expression originExpr = FoldConstantRuleOnFE.evaluate(
ExpressionUtils.or(toExpr, other.toExpr), context);
- DiscreteValue discreteValue = new DiscreteValue(context,
reference, originExpr);
- discreteValue.values.addAll(((DiscreteValue) other).values);
- discreteValue.values.addAll(this.values);
- return discreteValue;
+ Set<Literal> otherValues = ((DiscreteValue) other).values;
+ Set<Literal> newValues =
Sets.newLinkedHashSetWithExpectedSize(values.size() + otherValues.size());
+ newValues.addAll(values);
+ newValues.addAll(otherValues);
+ return new DiscreteValue(context, reference, originExpr,
newValues);
}
if (other instanceof RangeValue) {
return union(context, (RangeValue) other, this, true);
@@ -441,13 +449,12 @@ public class SimplifyRange implements
ExpressionPatternRuleFactory {
if (other instanceof DiscreteValue) {
Expression originExpr = FoldConstantRuleOnFE.evaluate(
ExpressionUtils.and(toExpr, other.toExpr), context);
- DiscreteValue discreteValue = new DiscreteValue(context,
reference, originExpr);
- discreteValue.values.addAll(((DiscreteValue) other).values);
- discreteValue.values.retainAll(this.values);
- if (discreteValue.values.isEmpty()) {
+ Set<Literal> newValues = Sets.newLinkedHashSet(values);
+ newValues.retainAll(((DiscreteValue) other).values);
+ if (newValues.isEmpty()) {
return new EmptyValue(context, reference, originExpr);
} else {
- return discreteValue;
+ return new DiscreteValue(context, reference, originExpr,
newValues);
}
}
if (other instanceof RangeValue) {
diff --git
a/regression-test/suites/nereids_rules_p0/expression/test_simplify_range.groovy
b/regression-test/suites/nereids_rules_p0/expression/test_simplify_range.groovy
index c6d12f3e6bc..945036bcac2 100644
---
a/regression-test/suites/nereids_rules_p0/expression/test_simplify_range.groovy
+++
b/regression-test/suites/nereids_rules_p0/expression/test_simplify_range.groovy
@@ -17,6 +17,8 @@
suite('test_simplify_range') {
def tbl_1 = 'test_simplify_range_tbl_1'
+ sql "set disable_nereids_rules='PRUNE_EMPTY_PARTITION'"
+
sql "DROP TABLE IF EXISTS ${tbl_1} FORCE"
sql "CREATE TABLE ${tbl_1}(a DECIMAL(16,8), b INT) PROPERTIES
('replication_num' = '1')"
sql "INSERT INTO ${tbl_1} VALUES(null, 10)"
@@ -25,4 +27,36 @@ suite('test_simplify_range') {
result([[null]])
}
sql "DROP TABLE IF EXISTS ${tbl_1} FORCE"
+
+ sql """
+ create table ${tbl_1}
+ (
+ pk_id varchar(32) not null,
+ collect_time varchar(16),
+ item_id bigint null,
+ )
+ unique key(pk_id, collect_time)
+ auto partition by list(collect_time)()
+ distributed by hash(pk_id) buckets auto
+ properties (
+ "replication_allocation" = "tag.location.default: 1",
+ "enable_unique_key_merge_on_write" = "true"
+ );
+ """
+
+ // may cause dead loop because simplify range will output new in-predicate
for options in new order.
+ // test the in predicate again.
+ test {
+ sql """SELECT *
+ FROM ${tbl_1}
+ WHERE ITEM_ID IN
+ (1595012731474280448, 1595013220588847104,
1595013220634984448, 1595013220672733184, 1595013220718870528,
+ 1595013220760813568, 1595013220798562304, 1595013220832116736,
1595013220869865472, 1595013220911808512,
+ 1595013220945362944, 1595013220983111680, 1595013221025054720,
1595013221066997760, 1595013221104746496,
+ 1595013221146689536, 1595013221188632576, 1595013221222187008,
1595013221255741440, 1595013221289295872)
+ AND COLLECT_TIME IN ('2025-02-09','2025-02-10','2025-02-11') """
+ result([])
+ }
+
+ sql "DROP TABLE IF EXISTS ${tbl_1} FORCE"
}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
