viirya commented on code in PR #59879:
URL: https://github.com/apache/spark/pull/59879#discussion_r4405404024
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/regexpExpressions.scala:
##########
@@ -84,33 +84,32 @@ abstract class StringRegexExpression extends
BinaryExpression
}
}
- override def expensive: Boolean = hasExpensiveChild || _expensiveRegex
-
- // Heuristic, not designed to be perfect. Look for things likely to have
- // back tracking.
- private val detectExpensiveRegexPattern = Pattern.compile("\\+\\*\\{")
-
- private lazy val _expensiveRegex = {
- // A quick heuristic for expensive a pattern is.
- left match {
- case StringLiteral(str) =>
- // If we have a clear start limited back tracking required.
- if (str.startsWith("^") || str.startsWith("\\b")) {
- false
- } else if (detectExpensiveRegexPattern.matcher(str).matches()) {
- // Greedy matching can be tricky.
- true
- } else {
- // Default to pushdown for now.
- false
- }
- case _ =>
- true // per row regex compilation.
- }
+ override def expensive: Boolean = hasExpensiveChild || _expensivePattern
+
+ // Heuristic, not designed to be perfect. A pattern that is not foldable is
compiled for every
+ // row; a foldable one is left to `isExpensivePattern`.
+ private lazy val _expensivePattern = if (right.foldable) {
+ val str = right.eval()
Review Comment:
Done in 0048df0. `_expensivePattern` now evaluates
`right.freshCopyIfContainsStatefulExpression()` and treats a pattern that fails
to evaluate as expensive. `RegexpExpressionsSuite` covers `CAST(1/0 AS STRING)`
as the pattern under ANSI. Before this change, `PushPredicateThroughNonJoin`
threw `DIVIDE_BY_ZERO` on your `IF(...)` example.
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/regexpExpressions.scala:
##########
@@ -182,6 +181,9 @@ case class Like(left: Expression, right: Expression,
escapeChar: Char)
override def matches(regex: Pattern, str: String): Boolean =
regex.matcher(str).matches()
+ // A LIKE pattern only has the `%` and `_` wildcards, which do not nest.
+ override protected def isExpensivePattern(str: String): Boolean = false
Review Comment:
Agreed. A LIKE with three or more `%` is now expensive. On JDK 17, one
400-character value took 0.1 ms with two `%`, 18 ms with three and 1.7 s with
four, so two stay cheap. `%a%b%` is now in the expensive cases of the test.
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/regexpExpressions.scala:
##########
@@ -84,33 +84,32 @@ abstract class StringRegexExpression extends
BinaryExpression
}
}
- override def expensive: Boolean = hasExpensiveChild || _expensiveRegex
-
- // Heuristic, not designed to be perfect. Look for things likely to have
- // back tracking.
- private val detectExpensiveRegexPattern = Pattern.compile("\\+\\*\\{")
-
- private lazy val _expensiveRegex = {
- // A quick heuristic for expensive a pattern is.
- left match {
- case StringLiteral(str) =>
- // If we have a clear start limited back tracking required.
- if (str.startsWith("^") || str.startsWith("\\b")) {
- false
- } else if (detectExpensiveRegexPattern.matcher(str).matches()) {
- // Greedy matching can be tricky.
- true
- } else {
- // Default to pushdown for now.
- false
- }
- case _ =>
- true // per row regex compilation.
- }
+ override def expensive: Boolean = hasExpensiveChild || _expensivePattern
+
+ // Heuristic, not designed to be perfect. A pattern that is not foldable is
compiled for every
+ // row; a foldable one is left to `isExpensivePattern`.
+ private lazy val _expensivePattern = if (right.foldable) {
+ val str = right.eval()
+ str != null && isExpensivePattern(str.toString)
+ } else {
+ true
}
+
+ /** Whether matching against the constant pattern `str` is likely to be
expensive. */
+ protected def isExpensivePattern(str: String): Boolean
}
private[catalyst] object StringRegexExpression {
+ // Quantifiers, which are what make a regex backtrack.
+ private val quantifierPattern = Pattern.compile("[+*{]")
+
+ /**
+ * Heuristic for whether a regex is likely to backtrack: one with a clear
start limits the
+ * backtracking, otherwise any quantifier may need it.
+ */
+ def isExpensiveRegex(regex: String): Boolean =
+ !regex.startsWith("^") && !regex.startsWith("\\b") &&
quantifierPattern.matcher(regex).find()
Review Comment:
Agreed, the anchor exemption is gone. I see the same on JDK 17:
`^.*a.*a.*a.*b` and `.*a.*a.*b` both take 2.1 s on 400 characters. RLIKE now
counts repeating quantifiers and treats two or more as expensive, anchored or
not. Two quantifiers took 22 ms there, three took 2.1 s.
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/regexpExpressions.scala:
##########
@@ -84,33 +84,32 @@ abstract class StringRegexExpression extends
BinaryExpression
}
}
- override def expensive: Boolean = hasExpensiveChild || _expensiveRegex
-
- // Heuristic, not designed to be perfect. Look for things likely to have
- // back tracking.
- private val detectExpensiveRegexPattern = Pattern.compile("\\+\\*\\{")
-
- private lazy val _expensiveRegex = {
- // A quick heuristic for expensive a pattern is.
- left match {
- case StringLiteral(str) =>
- // If we have a clear start limited back tracking required.
- if (str.startsWith("^") || str.startsWith("\\b")) {
- false
- } else if (detectExpensiveRegexPattern.matcher(str).matches()) {
- // Greedy matching can be tricky.
- true
- } else {
- // Default to pushdown for now.
- false
- }
- case _ =>
- true // per row regex compilation.
- }
+ override def expensive: Boolean = hasExpensiveChild || _expensivePattern
+
+ // Heuristic, not designed to be perfect. A pattern that is not foldable is
compiled for every
+ // row; a foldable one is left to `isExpensivePattern`.
+ private lazy val _expensivePattern = if (right.foldable) {
+ val str = right.eval()
+ str != null && isExpensivePattern(str.toString)
+ } else {
+ true
}
+
+ /** Whether matching against the constant pattern `str` is likely to be
expensive. */
+ protected def isExpensivePattern(str: String): Boolean
}
private[catalyst] object StringRegexExpression {
+ // Quantifiers, which are what make a regex backtrack.
+ private val quantifierPattern = Pattern.compile("[+*{]")
Review Comment:
The check is now a small scanner that counts `*`, `+` and `{n,m}`. It skips
escaped characters, `\Q...\E`, character classes and the braces of `\p{..}`,
`\x{..}` and `\N{..}`, and does not count again the `+` or `?` that makes a
quantifier possessive or lazy. Because it no longer looks for an anchor, inline
flags do not matter: `(?i)^abc.*` has one quantifier and is cheap, like
`^abc.*`. The test covers `a\+b\*`, `[+*{]x+`, `\p{Lu}+`, `\x{41}.*` and
`\Q.*+\E.*`.
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/regexpExpressions.scala:
##########
@@ -84,33 +84,32 @@ abstract class StringRegexExpression extends
BinaryExpression
}
}
- override def expensive: Boolean = hasExpensiveChild || _expensiveRegex
-
- // Heuristic, not designed to be perfect. Look for things likely to have
- // back tracking.
- private val detectExpensiveRegexPattern = Pattern.compile("\\+\\*\\{")
-
- private lazy val _expensiveRegex = {
- // A quick heuristic for expensive a pattern is.
- left match {
- case StringLiteral(str) =>
- // If we have a clear start limited back tracking required.
- if (str.startsWith("^") || str.startsWith("\\b")) {
- false
- } else if (detectExpensiveRegexPattern.matcher(str).matches()) {
- // Greedy matching can be tricky.
- true
- } else {
- // Default to pushdown for now.
- false
- }
- case _ =>
- true // per row regex compilation.
- }
+ override def expensive: Boolean = hasExpensiveChild || _expensivePattern
+
+ // Heuristic, not designed to be perfect. A pattern that is not foldable is
compiled for every
+ // row; a foldable one is left to `isExpensivePattern`.
+ private lazy val _expensivePattern = if (right.foldable) {
+ val str = right.eval()
+ str != null && isExpensivePattern(str.toString)
+ } else {
+ true
}
+
+ /** Whether matching against the constant pattern `str` is likely to be
expensive. */
+ protected def isExpensivePattern(str: String): Boolean
Review Comment:
Done: `isExpensivePattern` now defaults to `true`, which is what 4.2.0
answers for a column LIKE/RLIKE, and `Like` and `RLike` override it.
##########
sql/core/src/test/scala/org/apache/spark/sql/execution/datasources/FileSourceStrategySuite.scala:
##########
@@ -606,6 +606,30 @@ class FileSourceStrategySuite extends SharedSparkSession {
checkDataFilters(Set.empty)
}
+ test("SPARK-60632: Filters on an aliased LIKE/RLIKE column are pushed into
the file scan") {
+ withTempPath { path =>
+ spark.range(20)
+ .selectExpr("CAST(id AS STRING) AS name", "CAST(id % 4 AS STRING) AS
part")
+ .write.partitionBy("part").parquet(path.getCanonicalPath)
+ val table = spark.read.parquet(path.getCanonicalPath)
+
+ def scanOf(df: DataFrame): FileSourceScanExec =
+ df.queryExecution.sparkPlan.collectFirst { case s: FileSourceScanExec
=> s }.get
+
+ Seq("part RLIKE '^1'", "part LIKE '1_' OR part = '1'").foreach { pred =>
+ withClue(pred) {
+ val df = table.selectExpr("name", s"$pred AS p").where("p")
+ assert(scanOf(df).partitionFilters.nonEmpty)
Review Comment:
Fixed. The partition values are now `v0` to `v3`, so they stay strings, and
the cases are:
- `part RLIKE '^v1'` (1 partition)
- `part RLIKE 'v[12].*'` (2)
- `part LIKE '_1' OR part = 'v2'` (2)
Each asserts that the LIKE/RLIKE reaches `partitionFilters` and checks
`selectedPartitions.partitionCount`. The data filter case asserts that the
RLIKE reaches `dataFilters`.
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/regexpExpressions.scala:
##########
@@ -84,33 +84,32 @@ abstract class StringRegexExpression extends
BinaryExpression
}
}
- override def expensive: Boolean = hasExpensiveChild || _expensiveRegex
-
- // Heuristic, not designed to be perfect. Look for things likely to have
- // back tracking.
- private val detectExpensiveRegexPattern = Pattern.compile("\\+\\*\\{")
-
- private lazy val _expensiveRegex = {
- // A quick heuristic for expensive a pattern is.
- left match {
- case StringLiteral(str) =>
- // If we have a clear start limited back tracking required.
- if (str.startsWith("^") || str.startsWith("\\b")) {
- false
- } else if (detectExpensiveRegexPattern.matcher(str).matches()) {
- // Greedy matching can be tricky.
- true
- } else {
- // Default to pushdown for now.
- false
- }
- case _ =>
- true // per row regex compilation.
- }
+ override def expensive: Boolean = hasExpensiveChild || _expensivePattern
Review Comment:
Agreed that the remaining case is real and is a separate issue, so I'd keep
it out of this PR. With the quantifier count, your `part RLIKE '2024-.*'`
example has one quantifier and is now cheap, so it gets pruned; the `part RLIKE
'v[12].*'` case in `FileSourceStrategySuite` covers that shape. A
partition-only predicate that is still expensive, e.g. a UDF over a partition
column, still loses pruning.
--
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]
