Skip to content

Commit 1433116

Browse files
engleflypull[bot]
authored andcommitted
[runtimefilter](nerieds)support Non equal runtime filter for nested loop join #25193
1 parent 569b3b9 commit 1433116

11 files changed

Lines changed: 350 additions & 106 deletions

File tree

‎fe/fe-core/src/main/java/org/apache/doris/nereids/glue/translator/PhysicalPlanTranslator.java‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -180,6 +180,7 @@
180180
import org.apache.doris.thrift.TFetchOption;
181181
import org.apache.doris.thrift.TPartitionType;
182182
import org.apache.doris.thrift.TPushAggOp;
183+
import org.apache.doris.thrift.TRuntimeFilterType;
183184

184185
import com.google.common.base.Preconditions;
185186
import com.google.common.collect.ImmutableList;
@@ -1392,7 +1393,7 @@ public PlanFragment visitPhysicalNestedLoopJoin(
13921393
.getRuntimeFilterOfHashJoinNode(nestedLoopJoin);
13931394
filters.forEach(filter -> runtimeFilterTranslator
13941395
.createLegacyRuntimeFilter(filter, nestedLoopJoinNode, context));
1395-
if (!filters.isEmpty()) {
1396+
if (filters.stream().anyMatch(filter -> filter.getType() == TRuntimeFilterType.BITMAP)) {
13961397
nestedLoopJoinNode.setOutputLeftSideOnly(true);
13971398
}
13981399
});

‎fe/fe-core/src/main/java/org/apache/doris/nereids/glue/translator/RuntimeFilterTranslator.java‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -152,8 +152,8 @@ public void createLegacyRuntimeFilter(RuntimeFilter filter, JoinNodeBase node, P
152152
if (!hasInvalidTarget) {
153153
org.apache.doris.planner.RuntimeFilter origFilter
154154
= org.apache.doris.planner.RuntimeFilter.fromNereidsRuntimeFilter(
155-
filter.getId(), node, src, filter.getExprOrder(), targetExprList,
156-
targetTupleIdMapList, filter.getType(), context.getLimits(), filter.getBuildSideNdv());
155+
filter, node, src, targetExprList,
156+
targetTupleIdMapList, context.getLimits());
157157
if (node instanceof HashJoinNode) {
158158
origFilter.setIsBroadcast(((HashJoinNode) node).getDistributionMode() == DistributionMode.BROADCAST);
159159
} else {

‎fe/fe-core/src/main/java/org/apache/doris/nereids/processor/post/RuntimeFilterGenerator.java‎

Lines changed: 116 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -23,9 +23,14 @@
2323
import org.apache.doris.nereids.stats.ExpressionEstimation;
2424
import org.apache.doris.nereids.trees.expressions.Alias;
2525
import org.apache.doris.nereids.trees.expressions.CTEId;
26+
import org.apache.doris.nereids.trees.expressions.ComparisonPredicate;
2627
import org.apache.doris.nereids.trees.expressions.EqualTo;
2728
import org.apache.doris.nereids.trees.expressions.ExprId;
2829
import org.apache.doris.nereids.trees.expressions.Expression;
30+
import org.apache.doris.nereids.trees.expressions.GreaterThan;
31+
import org.apache.doris.nereids.trees.expressions.GreaterThanEqual;
32+
import org.apache.doris.nereids.trees.expressions.LessThan;
33+
import org.apache.doris.nereids.trees.expressions.LessThanEqual;
2934
import org.apache.doris.nereids.trees.expressions.NamedExpression;
3035
import org.apache.doris.nereids.trees.expressions.Not;
3136
import org.apache.doris.nereids.trees.expressions.Slot;
@@ -53,6 +58,7 @@
5358
import org.apache.doris.nereids.util.JoinUtils;
5459
import org.apache.doris.planner.RuntimeFilterId;
5560
import org.apache.doris.statistics.ColumnStatistic;
61+
import org.apache.doris.thrift.TMinMaxRuntimeFilterType;
5662
import org.apache.doris.thrift.TRuntimeFilterType;
5763

5864
import com.google.common.base.Preconditions;
@@ -113,6 +119,10 @@ public PhysicalPlan visitPhysicalHashJoin(PhysicalHashJoin<? extends Plan, ? ext
113119
RuntimeFilterContext ctx = context.getRuntimeFilterContext();
114120
join.right().accept(this, context);
115121
join.left().accept(this, context);
122+
if (RuntimeFilterGenerator.DENIED_JOIN_TYPES.contains(join.getJoinType()) || join.isMarkJoin()) {
123+
join.right().getOutput().forEach(slot ->
124+
context.getRuntimeFilterContext().getAliasTransferMap().remove(slot));
125+
}
116126
collectPushDownCTEInfos(join, context);
117127
if (!getPushDownCTECandidates(ctx).isEmpty()) {
118128
pushDownRuntimeFilterIntoCTE(ctx);
@@ -142,29 +152,19 @@ public PhysicalCTEProducer visitPhysicalCTEProducer(PhysicalCTEProducer producer
142152
return producer;
143153
}
144154

145-
@Override
146-
public PhysicalPlan visitPhysicalNestedLoopJoin(PhysicalNestedLoopJoin<? extends Plan, ? extends Plan> join,
147-
CascadesContext context) {
148-
// TODO: we need to support all type join
149-
join.right().accept(this, context);
150-
join.left().accept(this, context);
155+
private void generateBitMapRuntimeFilterForNLJ(PhysicalNestedLoopJoin<? extends Plan, ? extends Plan> join,
156+
RuntimeFilterContext ctx) {
151157
if (join.getJoinType() != JoinType.LEFT_SEMI_JOIN && join.getJoinType() != JoinType.CROSS_JOIN) {
152-
return join;
158+
return;
153159
}
154-
RuntimeFilterContext ctx = context.getRuntimeFilterContext();
155160
Map<NamedExpression, Pair<PhysicalRelation, Slot>> aliasTransferMap = ctx.getAliasTransferMap();
156-
157-
if ((ctx.getSessionVariable().getRuntimeFilterType() & TRuntimeFilterType.BITMAP.getValue()) == 0) {
158-
//only generate BITMAP filter for nested loop join
159-
return join;
160-
}
161161
List<Slot> leftSlots = join.left().getOutput();
162162
List<Slot> rightSlots = join.right().getOutput();
163163
List<Expression> bitmapRuntimeFilterConditions = JoinUtils.extractBitmapRuntimeFilterConditions(leftSlots,
164164
rightSlots, join.getOtherJoinConjuncts());
165165
if (!JoinUtils.extractExpressionForHashTable(leftSlots, rightSlots, join.getOtherJoinConjuncts())
166166
.first.isEmpty()) {
167-
return join;
167+
return;
168168
}
169169
int bitmapRFCount = bitmapRuntimeFilterConditions.size();
170170
for (int i = 0; i < bitmapRFCount; i++) {
@@ -193,6 +193,104 @@ public PhysicalPlan visitPhysicalNestedLoopJoin(PhysicalNestedLoopJoin<? extends
193193
join.addBitmapRuntimeFilterCondition(bitmapRuntimeFilterCondition);
194194
}
195195
}
196+
}
197+
198+
/**
199+
* A join B on B.x < A.x
200+
* transform B.x < A.x to A.x > B.x,
201+
* otherwise return null
202+
*/
203+
private ComparisonPredicate normalizeNonEqual(AbstractPhysicalJoin<? extends Plan, ? extends Plan> join,
204+
Expression expr) {
205+
if (!(expr instanceof ComparisonPredicate)) {
206+
return null;
207+
}
208+
if (!(expr.child(0) instanceof SlotReference)) {
209+
return null;
210+
}
211+
if (!(expr.child(1) instanceof SlotReference)) {
212+
return null;
213+
}
214+
if (! join.left().getOutput().contains(expr.child(0))
215+
|| ! join.right().getOutput().contains(expr.child(1))) {
216+
if (join.left().getOutput().contains(expr.child(1))
217+
&& join.right().getOutput().contains(expr.child(0))) {
218+
return ((ComparisonPredicate) expr).commute();
219+
}
220+
} else {
221+
return (ComparisonPredicate) expr;
222+
}
223+
return null;
224+
}
225+
226+
private TMinMaxRuntimeFilterType getMinMaxType(ComparisonPredicate compare) {
227+
if (compare instanceof LessThan || compare instanceof LessThanEqual) {
228+
return TMinMaxRuntimeFilterType.MAX;
229+
}
230+
if (compare instanceof GreaterThan || compare instanceof GreaterThanEqual) {
231+
return TMinMaxRuntimeFilterType.MIN;
232+
}
233+
return TMinMaxRuntimeFilterType.MIN_MAX;
234+
}
235+
236+
/**
237+
* A join B on A.x < B.y
238+
* min-max filter (A.x < N, N=max(B.y)) could be applied to A.x
239+
*/
240+
private void generateMinMaxRuntimeFilter(AbstractPhysicalJoin<? extends Plan, ? extends Plan> join,
241+
RuntimeFilterContext ctx) {
242+
Map<NamedExpression, Pair<PhysicalRelation, Slot>> aliasTransferMap = ctx.getAliasTransferMap();
243+
int hashCondionSize = join.getHashJoinConjuncts().size();
244+
for (int idx = 0; idx < join.getOtherJoinConjuncts().size(); idx++) {
245+
int exprOrder = idx + hashCondionSize;
246+
Expression expr = join.getOtherJoinConjuncts().get(exprOrder);
247+
ComparisonPredicate compare = normalizeNonEqual(join, expr);
248+
if (compare != null) {
249+
Slot unwrappedSlot = checkTargetChild(compare.child(0));
250+
if (unwrappedSlot == null) {
251+
continue;
252+
}
253+
Pair<PhysicalRelation, Slot> pair = aliasTransferMap.get(unwrappedSlot);
254+
if (pair == null) {
255+
continue;
256+
}
257+
Slot olapScanSlot = pair.second;
258+
PhysicalRelation scan = pair.first;
259+
Preconditions.checkState(olapScanSlot != null && scan != null);
260+
long buildSideNdv = getBuildSideNdv(join, compare);
261+
RuntimeFilter filter = new RuntimeFilter(generator.getNextId(),
262+
compare.child(1), ImmutableList.of(olapScanSlot), ImmutableList.of(olapScanSlot),
263+
TRuntimeFilterType.MIN_MAX, exprOrder, join, true, buildSideNdv,
264+
getMinMaxType(compare));
265+
ctx.addJoinToTargetMap(join, olapScanSlot.getExprId());
266+
ctx.setTargetExprIdToFilter(olapScanSlot.getExprId(), filter);
267+
ctx.setTargetsOnScanNode(scan.getRelationId(), olapScanSlot);
268+
}
269+
}
270+
}
271+
272+
@Override
273+
public PhysicalPlan visitPhysicalNestedLoopJoin(PhysicalNestedLoopJoin<? extends Plan, ? extends Plan> join,
274+
CascadesContext context) {
275+
// TODO: we need to support all type join
276+
join.right().accept(this, context);
277+
join.left().accept(this, context);
278+
279+
if (RuntimeFilterGenerator.DENIED_JOIN_TYPES.contains(join.getJoinType()) || join.isMarkJoin()) {
280+
join.right().getOutput().forEach(slot ->
281+
context.getRuntimeFilterContext().getAliasTransferMap().remove(slot));
282+
return join;
283+
}
284+
RuntimeFilterContext ctx = context.getRuntimeFilterContext();
285+
286+
if ((ctx.getSessionVariable().getRuntimeFilterType() & TRuntimeFilterType.BITMAP.getValue()) != 0) {
287+
generateBitMapRuntimeFilterForNLJ(join, ctx);
288+
}
289+
290+
if ((ctx.getSessionVariable().getRuntimeFilterType() & TRuntimeFilterType.MIN_MAX.getValue()) != 0) {
291+
generateMinMaxRuntimeFilter(join, ctx);
292+
}
293+
196294
return join;
197295
}
198296

@@ -233,14 +331,16 @@ public PhysicalRelation visitPhysicalRelation(PhysicalRelation relation, Cascade
233331
return relation;
234332
}
235333

236-
private long getBuildSideNdv(PhysicalHashJoin<? extends Plan, ? extends Plan> join, EqualTo equalTo) {
334+
// runtime filter build side ndv
335+
private long getBuildSideNdv(AbstractPhysicalJoin<? extends Plan, ? extends Plan> join,
336+
ComparisonPredicate compare) {
237337
AbstractPlan right = (AbstractPlan) join.right();
238338
//make ut test friendly
239339
if (right.getStats() == null) {
240340
return -1L;
241341
}
242342
ExpressionEstimation estimator = new ExpressionEstimation();
243-
ColumnStatistic buildColStats = equalTo.right().accept(estimator, right.getStats());
343+
ColumnStatistic buildColStats = compare.right().accept(estimator, right.getStats());
244344
return buildColStats.isUnKnown ? -1 : Math.max(1, (long) buildColStats.ndv);
245345
}
246346

‎fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/physical/AbstractPhysicalJoin.java‎

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -30,6 +30,7 @@
3030
import org.apache.doris.nereids.trees.plans.algebra.Join;
3131
import org.apache.doris.nereids.util.ExpressionUtils;
3232
import org.apache.doris.nereids.util.JoinUtils;
33+
import org.apache.doris.nereids.util.Utils;
3334
import org.apache.doris.statistics.Statistics;
3435

3536
import com.google.common.collect.ImmutableList;
@@ -41,6 +42,7 @@
4142
import java.util.List;
4243
import java.util.Objects;
4344
import java.util.Optional;
45+
import java.util.stream.Collectors;
4446

4547
/**
4648
* Abstract class for all physical join node.
@@ -214,4 +216,30 @@ public List<Slot> computeOutput() {
214216
? ImmutableList.of(markJoinSlotReference.get()) : ImmutableList.of())
215217
.build();
216218
}
219+
220+
@Override
221+
public String toString() {
222+
List<Object> args = Lists.newArrayList("type", joinType,
223+
"hashCondition", hashJoinConjuncts,
224+
"otherCondition", otherJoinConjuncts,
225+
"stats", statistics);
226+
if (markJoinSlotReference.isPresent()) {
227+
args.add("isMarkJoin");
228+
args.add("true");
229+
}
230+
if (markJoinSlotReference.isPresent()) {
231+
args.add("MarkJoinSlotReference");
232+
args.add(markJoinSlotReference.get());
233+
}
234+
if (hint != JoinHint.NONE) {
235+
args.add("hint");
236+
args.add(hint);
237+
}
238+
if (!runtimeFilters.isEmpty()) {
239+
args.add("runtimeFilters");
240+
args.add(runtimeFilters.stream().map(rf -> rf.toString() + " ").collect(Collectors.toList()));
241+
}
242+
return Utils.toSqlString(this.getClass().getName() + "[" + id.asInt() + "]" + getGroupIdWithPrefix(),
243+
args.toArray());
244+
}
217245
}

‎fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/physical/PhysicalHashJoin.java‎

Lines changed: 0 additions & 29 deletions
Original file line numberDiff line numberDiff line change
@@ -31,14 +31,12 @@
3131
import org.apache.doris.nereids.trees.expressions.MarkJoinSlotReference;
3232
import org.apache.doris.nereids.trees.expressions.NamedExpression;
3333
import org.apache.doris.nereids.trees.expressions.Slot;
34-
import org.apache.doris.nereids.trees.plans.AbstractPlan;
3534
import org.apache.doris.nereids.trees.plans.JoinHint;
3635
import org.apache.doris.nereids.trees.plans.JoinType;
3736
import org.apache.doris.nereids.trees.plans.Plan;
3837
import org.apache.doris.nereids.trees.plans.PlanType;
3938
import org.apache.doris.nereids.trees.plans.visitor.PlanVisitor;
4039
import org.apache.doris.nereids.util.MutableState;
41-
import org.apache.doris.nereids.util.Utils;
4240
import org.apache.doris.planner.RuntimeFilterId;
4341
import org.apache.doris.qe.ConnectContext;
4442
import org.apache.doris.statistics.Statistics;
@@ -140,33 +138,6 @@ public <R, C> R accept(PlanVisitor<R, C> visitor, C context) {
140138
return visitor.visitPhysicalHashJoin(this, context);
141139
}
142140

143-
@Override
144-
public String toString() {
145-
List<Object> args = Lists.newArrayList("type", joinType,
146-
"hashJoinCondition", hashJoinConjuncts,
147-
"otherJoinCondition", otherJoinConjuncts,
148-
"stats", statistics,
149-
"fr", getMutableState(AbstractPlan.FRAGMENT_ID));
150-
if (markJoinSlotReference.isPresent()) {
151-
args.add("isMarkJoin");
152-
args.add("true");
153-
}
154-
if (markJoinSlotReference.isPresent()) {
155-
args.add("MarkJoinSlotReference");
156-
args.add(markJoinSlotReference.get());
157-
}
158-
if (hint != JoinHint.NONE) {
159-
args.add("hint");
160-
args.add(hint);
161-
}
162-
if (!runtimeFilters.isEmpty()) {
163-
args.add("runtimeFilters");
164-
args.add(runtimeFilters.stream().map(rf -> rf.toString() + " ").collect(Collectors.toList()));
165-
}
166-
return Utils.toSqlString("PhysicalHashJoin[" + id.asInt() + "]" + getGroupIdWithPrefix(),
167-
args.toArray());
168-
}
169-
170141
@Override
171142
public PhysicalHashJoin<Plan, Plan> withChildren(List<Plan> children) {
172143
Preconditions.checkArgument(children.size() == 2);

‎fe/fe-core/src/main/java/org/apache/doris/nereids/trees/plans/physical/PhysicalNestedLoopJoin.java‎

Lines changed: 11 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -28,7 +28,6 @@
2828
import org.apache.doris.nereids.trees.plans.PlanType;
2929
import org.apache.doris.nereids.trees.plans.visitor.PlanVisitor;
3030
import org.apache.doris.nereids.util.MutableState;
31-
import org.apache.doris.nereids.util.Utils;
3231
import org.apache.doris.statistics.Statistics;
3332

3433
import com.google.common.base.Preconditions;
@@ -113,17 +112,17 @@ public <R, C> R accept(PlanVisitor<R, C> visitor, C context) {
113112
return visitor.visitPhysicalNestedLoopJoin(this, context);
114113
}
115114

116-
@Override
117-
public String toString() {
118-
// TODO: Maybe we could pull up this to the abstract class in the future.
119-
return Utils.toSqlString("PhysicalNestedLoopJoin[" + id.asInt() + "]" + getGroupIdWithPrefix(),
120-
"type", joinType,
121-
"otherJoinCondition", otherJoinConjuncts,
122-
"isMarkJoin", markJoinSlotReference.isPresent(),
123-
"markJoinSlotReference", markJoinSlotReference.isPresent() ? markJoinSlotReference.get() : "empty",
124-
"stats", statistics
125-
);
126-
}
115+
// @Override
116+
// public String toString() {
117+
// // TODO: Maybe we could pull up this to the abstract class in the future.
118+
// return Utils.toSqlString("PhysicalNestedLoopJoin[" + id.asInt() + "]" + getGroupIdWithPrefix(),
119+
// "type", joinType,
120+
// "otherJoinCondition", otherJoinConjuncts,
121+
// "isMarkJoin", markJoinSlotReference.isPresent(),
122+
// "markJoinSlotReference", markJoinSlotReference.isPresent() ? markJoinSlotReference.get() : "empty",
123+
// "stats", statistics
124+
// );
125+
// }
127126

128127
@Override
129128
public PhysicalNestedLoopJoin<Plan, Plan> withChildren(List<Plan> children) {

0 commit comments

Comments
 (0)