IvanVergiliev commented on a change in pull request #24068: [SPARK-27105][SQL]
Optimize away exponential complexity in ORC predicate conversion
URL: https://github.com/apache/spark/pull/24068#discussion_r288510539
##########
File path:
sql/core/v1.2.1/src/main/scala/org/apache/spark/sql/execution/datasources/orc/OrcFilters.scala
##########
@@ -143,145 +117,244 @@ private[sql] object OrcFilters extends OrcFiltersBase {
case _ => value
}
+ import org.apache.spark.sql.sources._
+ import OrcFilters._
+
+ private[sql] def trimUnconvertibleFilters(expression: Filter):
Option[Filter] = {
+ performFilter(expression, canPartialPushDownConjuncts = true)
+ }
+
/**
- * Build a SearchArgument and return the builder so far.
+ * Builds a SearchArgument for a Filter by first trimming the
non-convertible nodes, and then
+ * only building the remaining convertible nodes.
+ *
+ * Doing the conversion in this way avoids the computational complexity
problems introduced by
+ * checking whether a node is convertible while building it. The approach
implemented here has
+ * complexity that's linear in the size of the Filter tree - O(number of
Filter nodes) - we run
+ * a single pass over the tree to trim it, and then another pass on the
trimmed tree to convert
+ * the remaining nodes.
+ *
+ * The alternative approach of checking-while-building can (and did) result
+ * in exponential complexity in the height of the tree, causing perf
problems with Filters with
+ * as few as ~35 nodes if they were skewed.
*/
- private def buildSearchArgument(
- dataTypeMap: Map[String, DataType],
+ private[sql] def buildSearchArgument(
expression: Filter,
builder: Builder): Option[Builder] = {
- createBuilder(dataTypeMap, expression, builder,
canPartialPushDownConjuncts = true)
+ val filteredExpression: Option[Filter] = performFilter(
+ expression,
+ canPartialPushDownConjuncts = true)
+ filteredExpression.foreach(updateBuilder(_, builder))
+ filteredExpression.map(_ => builder)
}
- /**
- * @param dataTypeMap a map from the attribute name to its data type.
- * @param expression the input filter predicates.
- * @param builder the input SearchArgument.Builder.
- * @param canPartialPushDownConjuncts whether a subset of conjuncts of
predicates can be pushed
- * down safely. Pushing ONLY one side of
AND down is safe to
- * do at the top level or none of its
ancestors is NOT and OR.
- * @return the builder so far.
- */
- private def createBuilder(
- dataTypeMap: Map[String, DataType],
- expression: Filter,
- builder: Builder,
- canPartialPushDownConjuncts: Boolean): Option[Builder] = {
+ sealed trait ActionType
+ case class TrimUnconvertibleFilters(canPartialPushDownConjuncts: Boolean)
extends ActionType
+ case class BuildSearchArgument(builder: Builder) extends ActionType
+
+ // The performAction method can run both the filtering and building
operations for a given
+ // node - we signify which one we want with the `actionType` parameter.
+ //
+ // There are a couple of benefits to coupling the two operations like this:
+ // 1. All the logic for a given predicate is grouped logically in the same
place. You don't
+ // have to scroll across the whole file to see what the filter action for
an And is while
+ // you're looking at the build action.
+ // 2. It's much easier to keep the implementations of the two operations
up-to-date with
+ // each other. If the `filter` and `build` operations are implemented as
separate case-matches
+ // in different methods, it's very easy to change one without
appropriately updating the
+ // other. For example, if we add a new supported node type to `filter`, it
would be very
+ // easy to forget to update `build` to support it too, thus leading to
conversion errors.
+ //
+ // Doing things this way does have some annoying side effects:
+ // - We need to return an `Either`, with one action type always returning a
Left and the other
+ // always returning a Right.
+ // - We always need to pass the canPartialPushDownConjuncts parameter even
though the build
+ // action doesn't need it (because by the time we run the `build`
operation, we know all
+ // remaining nodes are convertible).
+ def performAction(
+ actionType: ActionType,
+ expression: Filter): Either[Option[Filter], Unit] = {
Review comment:
Thanks for the idea - this works! I'm definitely happier with the return
type and the usages now.
I still don't completely understand why the type member version doesn't
work. Reading around, it seems like it would be just a "dependent method type"
which is supported, but somehow the compiler fails to narrow the return type in
the match-case.
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
[email protected]
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
