WangGuangxin commented on code in PR #12922: URL: https://github.com/apache/gluten/pull/12922#discussion_r4053408440
########## backends-velox/src/main/scala/org/apache/gluten/extension/VeloxBroadcastNestedLoopJoinRewriteRule.scala: ########## @@ -0,0 +1,236 @@ +/* + * 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.gluten.extension + +import org.apache.gluten.config.VeloxConfig + +import org.apache.spark.sql.catalyst.expressions.{Alias, Attribute, AttributeReference, Expression, Literal, Not} +import org.apache.spark.sql.catalyst.optimizer.{BuildLeft, BuildRight} +import org.apache.spark.sql.catalyst.plans.{ExistenceJoin, FullOuter, LeftOuter} +import org.apache.spark.sql.catalyst.plans.logical.Join +import org.apache.spark.sql.catalyst.plans.physical.IdentityBroadcastMode +import org.apache.spark.sql.catalyst.rules.Rule +import org.apache.spark.sql.execution.{FilterExec, ProjectExec, SparkPlan, UnionExec} +import org.apache.spark.sql.execution.adaptive.BroadcastQueryStageExec +import org.apache.spark.sql.execution.exchange.{BroadcastExchangeExec, BroadcastExchangeLike, ReusedExchangeExec} +import org.apache.spark.sql.execution.joins.BroadcastNestedLoopJoinExec +import org.apache.spark.sql.types.BooleanType + +/** + * Rewrites `BroadcastNestedLoopJoinExec(FullOuter)` into a union of two nested-loop joins that + * Velox already supports natively: + * 1. left outer join to produce matches plus unmatched streamed-side rows + * 2. an existence join, with the original broadcast side streamed, to identify its unmatched rows + */ +case class VeloxBroadcastNestedLoopJoinRewriteRule() extends Rule[SparkPlan] { + override def apply(plan: SparkPlan): SparkPlan = { + val threshold = VeloxConfig.get.broadcastNestedLoopJoinFullOuterRewriteThreshold + if (threshold < 0) { + plan + } else { + plan.transformUp { + case bnlj: BroadcastNestedLoopJoinExec + if bnlj.joinType == FullOuter && shouldRewriteFullOuter( + bnlj, + threshold) && conditionOffloadable(bnlj) && broadcastSideRelocatable(bnlj) => + rewriteFullOuter(bnlj) + } + } + } + + /** + * The rewrite reuses the original broadcast side in two roles at once: [[rewriteFullOuter]] keeps + * it as the build (broadcast) side of `branchA`, while [[buildUnmatchedBroadcastSide]] calls + * [[unwrapBroadcast]] on it and consumes the unwrapped subtree as a normal STREAMED input of + * `branchB`. That is only safe when the broadcast side can be cleanly re-materialized as a + * partitioned plan. Reject the rewrite otherwise, e.g. for the MERGE cardinality-check join (`ON + * t.pk > s.pk` with an `autoBroadcastJoinThreshold = -1` broadcast of a reused `Union` source): + * there the broadcast side does not unwrap to a plain partitioned subtree, so after the rewrite a + * `ColumnarBroadcastExchangeExec` ends up in `branchB`'s streamed slot and is executed via + * `ColumnarInputAdapter.doExecuteColumnar -> executeColumnar()`, which the broadcast exchange + * does not support, crashing with `[INTERNAL_ERROR] ... has column support mismatch`. + * + * A broadcast side is considered relocatable only when: + * - it is an exclusively-owned broadcast, i.e. NOT a [[ReusedExchangeExec]] (a reused/shared + * exchange must not be turned into a streamed input); and + * - its unwrapped payload does not itself contain a nested broadcast, which would otherwise + * leak into the streamed position of `branchB`. + */ + private def broadcastSideRelocatable(bnlj: BroadcastNestedLoopJoinExec): Boolean = { + val broadcastSide = bnlj.buildSide match { + case BuildLeft => bnlj.left + case BuildRight => bnlj.right + } + isCleanRelocatableBroadcast(broadcastSide) + } + + private def isCleanRelocatableBroadcast(plan: SparkPlan): Boolean = plan match { + case stage: BroadcastQueryStageExec => isCleanRelocatableBroadcast(stage.plan) + case _: ReusedExchangeExec => false + case exchange: BroadcastExchangeLike => !containsBroadcast(exchange.child) + case _ => false + } + + private def containsBroadcast(plan: SparkPlan): Boolean = + plan.exists { + case _: BroadcastExchangeLike => true + case _: BroadcastQueryStageExec => true + case _: ReusedExchangeExec => true + case _ => false + } + + private def shouldRewriteFullOuter( + bnlj: BroadcastNestedLoopJoinExec, + threshold: Long): Boolean = { + bnlj.logicalLink.collect { + case join: Join => + val leftSize = join.left.stats.sizeInBytes + val rightSize = join.right.stats.sizeInBytes + leftSize >= 0 && rightSize >= 0 && leftSize <= threshold && rightSize <= threshold + }.getOrElse(false) + } + + private def extractChildLogicalSizes( + bnlj: BroadcastNestedLoopJoinExec): Option[(BigInt, BigInt)] = + for { + leftLogical <- bnlj.left.logicalLink + rightLogical <- bnlj.right.logicalLink + } yield (leftLogical.stats.sizeInBytes, rightLogical.stats.sizeInBytes) Review Comment: update PR description with query plan before / after the rule -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
