|
23 | 23 | import org.apache.doris.nereids.stats.ExpressionEstimation; |
24 | 24 | import org.apache.doris.nereids.trees.expressions.Alias; |
25 | 25 | import org.apache.doris.nereids.trees.expressions.CTEId; |
| 26 | +import org.apache.doris.nereids.trees.expressions.ComparisonPredicate; |
26 | 27 | import org.apache.doris.nereids.trees.expressions.EqualTo; |
27 | 28 | import org.apache.doris.nereids.trees.expressions.ExprId; |
28 | 29 | 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; |
29 | 34 | import org.apache.doris.nereids.trees.expressions.NamedExpression; |
30 | 35 | import org.apache.doris.nereids.trees.expressions.Not; |
31 | 36 | import org.apache.doris.nereids.trees.expressions.Slot; |
|
53 | 58 | import org.apache.doris.nereids.util.JoinUtils; |
54 | 59 | import org.apache.doris.planner.RuntimeFilterId; |
55 | 60 | import org.apache.doris.statistics.ColumnStatistic; |
| 61 | +import org.apache.doris.thrift.TMinMaxRuntimeFilterType; |
56 | 62 | import org.apache.doris.thrift.TRuntimeFilterType; |
57 | 63 |
|
58 | 64 | import com.google.common.base.Preconditions; |
@@ -113,6 +119,10 @@ public PhysicalPlan visitPhysicalHashJoin(PhysicalHashJoin<? extends Plan, ? ext |
113 | 119 | RuntimeFilterContext ctx = context.getRuntimeFilterContext(); |
114 | 120 | join.right().accept(this, context); |
115 | 121 | 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 | + } |
116 | 126 | collectPushDownCTEInfos(join, context); |
117 | 127 | if (!getPushDownCTECandidates(ctx).isEmpty()) { |
118 | 128 | pushDownRuntimeFilterIntoCTE(ctx); |
@@ -142,29 +152,19 @@ public PhysicalCTEProducer visitPhysicalCTEProducer(PhysicalCTEProducer producer |
142 | 152 | return producer; |
143 | 153 | } |
144 | 154 |
|
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) { |
151 | 157 | if (join.getJoinType() != JoinType.LEFT_SEMI_JOIN && join.getJoinType() != JoinType.CROSS_JOIN) { |
152 | | - return join; |
| 158 | + return; |
153 | 159 | } |
154 | | - RuntimeFilterContext ctx = context.getRuntimeFilterContext(); |
155 | 160 | 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 | | - } |
161 | 161 | List<Slot> leftSlots = join.left().getOutput(); |
162 | 162 | List<Slot> rightSlots = join.right().getOutput(); |
163 | 163 | List<Expression> bitmapRuntimeFilterConditions = JoinUtils.extractBitmapRuntimeFilterConditions(leftSlots, |
164 | 164 | rightSlots, join.getOtherJoinConjuncts()); |
165 | 165 | if (!JoinUtils.extractExpressionForHashTable(leftSlots, rightSlots, join.getOtherJoinConjuncts()) |
166 | 166 | .first.isEmpty()) { |
167 | | - return join; |
| 167 | + return; |
168 | 168 | } |
169 | 169 | int bitmapRFCount = bitmapRuntimeFilterConditions.size(); |
170 | 170 | for (int i = 0; i < bitmapRFCount; i++) { |
@@ -193,6 +193,104 @@ public PhysicalPlan visitPhysicalNestedLoopJoin(PhysicalNestedLoopJoin<? extends |
193 | 193 | join.addBitmapRuntimeFilterCondition(bitmapRuntimeFilterCondition); |
194 | 194 | } |
195 | 195 | } |
| 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 | + |
196 | 294 | return join; |
197 | 295 | } |
198 | 296 |
|
@@ -233,14 +331,16 @@ public PhysicalRelation visitPhysicalRelation(PhysicalRelation relation, Cascade |
233 | 331 | return relation; |
234 | 332 | } |
235 | 333 |
|
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) { |
237 | 337 | AbstractPlan right = (AbstractPlan) join.right(); |
238 | 338 | //make ut test friendly |
239 | 339 | if (right.getStats() == null) { |
240 | 340 | return -1L; |
241 | 341 | } |
242 | 342 | ExpressionEstimation estimator = new ExpressionEstimation(); |
243 | | - ColumnStatistic buildColStats = equalTo.right().accept(estimator, right.getStats()); |
| 343 | + ColumnStatistic buildColStats = compare.right().accept(estimator, right.getStats()); |
244 | 344 | return buildColStats.isUnKnown ? -1 : Math.max(1, (long) buildColStats.ndv); |
245 | 345 | } |
246 | 346 |
|
|
0 commit comments