hhr293 commented on code in PR #12756: URL: https://github.com/apache/gluten/pull/12756#discussion_r3820277363
########## backends-velox/src/main/scala/org/apache/gluten/extension/RewriteSelfJoinInequalityToAggregate.scala: ########## @@ -0,0 +1,722 @@ +/* + * 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.internal.Logging +import org.apache.spark.sql.SparkSession +import org.apache.spark.sql.catalyst.expressions._ +import org.apache.spark.sql.catalyst.expressions.RowOrdering +import org.apache.spark.sql.catalyst.expressions.aggregate._ +import org.apache.spark.sql.catalyst.plans._ +import org.apache.spark.sql.catalyst.plans.logical._ +import org.apache.spark.sql.catalyst.rules.Rule +import org.apache.spark.sql.types.LongType + +/** + * Rewrites self-join with inequality into GROUP BY + HAVING COUNT(DISTINCT) > 1. + * + * Targets three patterns; all require an existence-only context (LeftSemi/LeftAnti join, or + * InSubquery/Exists expression) so that row-count multiplicity from the self-join cross-product + * does not affect semantics. + * + * - Pattern A' (InSubquery/Exists primary): InSubquery/Exists whose subquery top-level join is a + * direct self-join. The primary path for TPC-DS Q95. + * - Pattern A2 (nested): InSubquery/Exists whose subquery contains an outer InnerJoin that has a Review Comment: > since we already address the main issue on q95, could you please clarify what are the typical quereis for the other two patterns? Thanks a lot for the review and the approval! Good question — let me spell out the query shapes for the other two patterns. q95 actually has **two** `IN` subqueries, and they hit different patterns. Both reference the same CTE, so I inlined it below — otherwise the two look identical: ```sql -- ws_wh = self-join: web_sales a, web_sales b -- where a.ws_order_number = b.ws_order_number -- and a.ws_warehouse_sk <> b.ws_warehouse_sk -- Pattern A': the self-join IS the subquery and ws1.ws_order_number in (select ws_order_number from <ws_wh>) -- Pattern A2: the self-join is a child of another InnerJoin and ws1.ws_order_number in (select wr_order_number from web_returns, <ws_wh> where wr_order_number = ws_wh.ws_order_number) ``` A' replaces the whole subquery plan, while A2 replaces only the self-join child and has to preserve the outer join plus its wrapping `Project`'s exprIds — which is why it needs a separate code path. Both subqueries become `LeftSemi` hash builds, and at SF=300 they are the two biggest build sides in the query: | | pattern | build input OFF | ON | share of hash-build cost | |---|---|---|---|---| | first `IN` | A' | 2.35 B rows / 80 GiB | 18 M rows | ~60% | | second `IN` | A2 | 3.08 B rows / 91 GiB | 22 M rows | ~40% | So A2 isn't a speculative generalization — dropping it would leave the larger of the two build sides untouched and give up roughly 40% of the gain. More generally, A2 is the shape you get whenever the "more than one distinct X" set is narrowed by another table before feeding the `IN`. **Pattern A** is just A' with the semi/anti join written explicitly rather than derived from a subquery: ```sql select ws1.ws_order_number from web_sales ws1 left semi join (select ws_order_number from <ws_wh>) x on ws1.ws_order_number = x.ws_order_number ``` Same build side, same reduction, same guards — the two are symmetric. TPC-DS and TPC-H don't match this one only because they write every existence check as `IN` / `EXISTS`, whereas hand-written and BI-generated SQL fairly often uses explicit `LEFT SEMI` / `LEFT ANTI JOIN`. Hope that clarifies it — happy to go into more detail on any of the three if useful. -- 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]
