dongjoon-hyun commented on code in PR #59143:
URL: https://github.com/apache/spark/pull/59143#discussion_r4328857778
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/predicates.scala:
##########
@@ -185,6 +185,16 @@ trait PredicateHelper extends AliasHelper with Logging {
currentResult.head
}
+ /**
+ * Option-returning form of [[buildBalancedPredicate]]: `None` for an empty
input, otherwise the
+ * combined predicate.
+ */
+ protected def buildBalancedPredicateOption(
+ expressions: Seq[Expression],
+ op: (Expression, Expression) => Expression): Option[Expression] = {
+ if (expressions.isEmpty) None else
Some(buildBalancedPredicate(expressions, op))
Review Comment:
**The first pass of `buildBalancedPredicate` is quadratic on a `List`, and
this wrapper passes its input through unchanged.** HyukjinKwon asked about this
in review 5405036205, and the helper is unchanged at 774871c. At L171-183,
`currentResult` starts as the caller's `Seq`, and the first pass calls
`currentResult.size` in both loop conditions, in the array length and in `i + 1
== currentResult.size`, plus `currentResult(i)` and `currentResult(i + 1)`. On
a `List`, each of these walks the list, so the first pass costs about 1.5 * n^2
node steps, where the replaced `reduceLeft` was O(n).
The `ExpressionSet` callers pass `List`s too. `ExpressionSet` does not
override `toSeq`, so it is `immutable.Seq.from(this)`, which builds a `List`.
That covers `newFilters.toSeq` and `newPredicates.toSeq` in
`InferFiltersFromConstraints` (Optimizer.scala:2255 and :2306), the
`CombineFilters` difference (Optimizer.scala:2407) and `joinConds.toSeq`
(CostBasedJoinReorder.scala:308).
The cost is also paid repeatedly. The `Join` arm of
`PushPredicateThroughJoin` rebuilds every join condition on every fixed-point
iteration, and `ExtractEquiJoinKeys.unapply` (patterns.scala:223-224) builds
both `otherPredicates` and `predicatesOfJoinKeys` on every match, although none
of its 16 match sites in `sql/` reads the latter. Where master re-split a
left-deep tree, its recursive split was already quadratic, so those paths only
move the cost. But a `FullOuter` join condition from SQL, which the parser
builds balanced and `PushPredicateThroughJoin` never rebuilds, now costs O(n^2)
instead of O(n log n) on each `ExtractEquiJoinKeys` match. I traced this by
reading the code and did not measure it.
Could you change L171 to `var currentResult: Seq[Expression] =
expressions.toIndexedSeq`? It is a no-op for an `ArraySeq` or a `Vector`, keeps
the same pairing and tree shape, and makes the helper O(n) for every caller.
--
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]
