dongjoon-hyun commented on code in PR #59879:
URL: https://github.com/apache/spark/pull/59879#discussion_r4405059859
##########
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:
**1. [Medium] Evaluating the pattern here can fail the optimizer**
`PushPredicateThroughNonJoin` calls `expensive` (`Optimizer.scala:2628`),
and before this change it never evaluated anything. L92 now evaluates any
foldable pattern. That includes a pattern which `ConstantFolding` deliberately
leaves unfolded because it throws inside a conditional branch
(`expressions.scala:67-72`, `FAILED_TO_EVALUATE`). For example, with ANSI on:
```sql
SELECT * FROM (
SELECT IF(s IS NULL, NULL, s RLIKE CAST(1/0 AS STRING)) AS f FROM t
) WHERE f
```
`If.expensive` goes through `hasExpensiveChild` to `RLike.expensive`, and
L92 throws `DIVIDE_BY_ZERO` inside the optimizer. `PushDownPredicates` also
runs before `ConstantFolding` in each iteration (`Optimizer.scala:108`, `139`),
so the first iteration sees unfolded patterns even outside conditional branches.
The codegen paths at L204 and L548 evaluate the pattern too, so with
whole-stage codegen on, this query already fails at execution. What changes:
- `EXPLAIN` and `queryExecution.optimizedPlan` now fail.
- With `spark.sql.codegen.wholeStage=false`, the expression codegen error
falls back to the interpreter
(`CodeGeneratorWithInterpretedFallback.scala:52-54`). The query used to succeed
when the branch was not taken, and now it fails.
Separately, L92 evaluates the plan's own instance. `ConstantFolding.tryFold`
evaluates `freshCopyIfContainsStatefulExpression()` instead
(`expressions.scala:65`), because a stateful foldable pattern such as
`regexp_replace('a+b', 'x', 'y')` (`RegExpReplace`, L756) mutates its caches
when evaluated.
Could L91-96 evaluate a fresh copy and treat a pattern that fails to
evaluate as expensive?
```scala
private lazy val _expensivePattern = !right.foldable || {
try {
val str = right.freshCopyIfContainsStatefulExpression().eval()
str != null && isExpensivePattern(str.toString)
} catch {
case NonFatal(_) => true
}
}
```
##########
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:
**4. [Low] The `[+*{]` check also matches characters that are not
quantifiers**
`find()` on `[+*{]` also matches:
- escaped literals, e.g. `a\+b`
- characters inside a class, e.g. `[+*]`
- the braces of `\p{...}` and `\x{...}`, e.g. `\p{Lu}`
None of these can backtrack, but all are classed expensive. An inline flag
also hides the anchor: `(?i)^abc.*` is expensive while `^abc.*` is cheap.
For these patterns, a filter on the alias is still not pushed. So the
partition pruning and data filter pushdown that this PR restores are still lost
for them. If the heuristic stays text-based, could it skip escaped characters
and character classes, and allow leading inline flags before `^`?
##########
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:
**5. [Low] The new abstract member breaks subclasses outside Spark**
`StringRegexExpression` is a public, non-sealed abstract class. A subclass
compiled against 4.2.0 does not implement `isExpensivePattern`. It would fail
with `AbstractMethodError` the first time the optimizer reaches L93 for it, and
it no longer compiles against this branch.
Catalyst is not a public API, but this would also reach 4.2.x if it is
backported. Could this have a default instead, e.g. `= true` (what 4.2.0
answers for a column LIKE/RLIKE) or the regex check, with `Like` and `RLike`
overriding it?
##########
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:
**7. [Low] Partition pruning still depends on this per-row cost heuristic**
This narrows the regression but does not remove it. With the defaults,
`SELECT * FROM (SELECT name, part RLIKE '2024-.*' AS p FROM t) WHERE p` still
gets `PartitionFilters: []`, because `.*` is a quantifier. Yet this is where
double evaluation costs least: a predicate on partition columns alone is
evaluated once per partition during listing, not once per row.
As far as I can tell, `ScanOperation` cannot inline the alias either:
- `InferFiltersFromConstraints` adds `isnotnull(p)`
(`QueryPlanConstraints.scala:174`), so `p` is referenced twice.
- The non-cheap producer is therefore kept (`patterns.scala:78`,
`Optimizer.scala:1885`).
This is not a blocker for this PR. Would a separate JIRA be worth it, to let
partition pruning see through the alias for partition-only predicates
regardless of `expensive`?
##########
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 =
Review Comment:
**9. [Nit] A precompiled `Pattern` and a companion method are more than this
needs**
`isExpensiveRegex` has one caller, and the check is a search for three
characters. Could `RLike.isExpensivePattern` hold it directly, with no
`Pattern`?
```scala
override protected def isExpensivePattern(str: String): Boolean =
!str.startsWith("^") && !str.startsWith("\\b") &&
str.exists(c => c == '+' || c == '*' || c == '{')
```
Also, `Like` always answers `false`, so L92 evaluates every foldable LIKE
pattern only to discard the result.
##########
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:
**2. [Medium] Every constant LIKE pattern is classed cheap, including the
slow ones**
`%` and `_` do not nest, but consecutive `%` wildcards still backtrack
polynomially. `StringUtils.escapeLikeRegex` turns `'%a%a%a%b'` into
`(?s).*\Qa\E.*\Qa\E.*\Qa\E.*\Qb\E`, and `Like.matches` uses `matches()`. On JDK
25, matching one value of n `a`s with no `b` took:
| n | time for one value |
|---|---|
| 200 | 0.13 s |
| 400 | 2.0 s |
| 800 | 31 s |
`LikeSimplification` already rewrites the single-`%` shapes (`x%`, `%x`,
`x%y`, `%x%`) into cheap string functions. So the LIKE expressions that are
still `Like` here are mostly the multi-wildcard ones this heuristic should
catch. With this change, a filter on such an alias is pushed below the
`Project` and the LIKE runs twice per row. The new test even asserts that
`%a%b%` is cheap (`RegexpExpressionsSuite.scala:750`).
Could a LIKE pattern with several `%` (say three or more) be classed
expensive? Or could the escaped regex go through the same check as RLIKE?
##########
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:
**6. [Low] The partition test reads `part` back as an INT, and its asserts
are weak**
`part` is written as a string, but partition type inference reads `0` to `3`
back as `IntegerType`. So the RLIKE case runs as `CAST(part AS STRING) RLIKE
'^1'`.
Every value has one digit, so `part LIKE '1_'` matches no partition and only
`part = '1'` returns rows. The LIKE leg's result is never checked.
`partitionFilters.nonEmpty` here, and `dataFilters.nonEmpty` at L628, would
also pass if only an `isnotnull(part)` reached the scan, or if the pushed
predicate pruned nothing.
Could the test do the following?
- Use non-numeric partition values, or turn off
`spark.sql.sources.partitionColumnTypeInference.enabled`.
- Make the LIKE match a partition.
- Assert on the pushed predicate or on the number of selected partitions.
##########
sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/expressions/RegexpExpressionsSuite.scala:
##########
@@ -735,4 +735,28 @@ class RegexpExpressionsSuite extends SparkFunSuite with
ExpressionEvalHelper {
assert(extractAllCopy ne extractAll,
"freshCopyIfContainsStatefulExpression should return a new instance for
RegExpExtractAll")
}
+
+ test("SPARK-60632: LIKE and RLIKE expensive heuristic looks at the pattern")
{
Review Comment:
**8. [Nit] No test checks that an expensive child still wins over a cheap
pattern**
Suppose `hasExpensiveChild ||` were dropped from L87. Then an RLIKE with a
cheap constant pattern over an expensive subject, e.g. `RLike(scalaUdf(col),
Literal("^1"))`, would become cheap. A filter on it would be pushed and the UDF
evaluated twice, and none of the new tests would fail.
Could this test cover that case? `FilterPushdownSuite` could also cover two
more cases:
- an anchored pattern with a quantifier being pushed, e.g. `^a.*b`
- an ILIKE alias, which reaches this code as `Like(Lower(left),
Lower(right))`
##########
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:
**3. [Low] A leading `^` or `\b` does not bound the backtracking**
An anchor only removes the scan over start positions. The backtracking
inside the match is unchanged. `^.*a.*a.*a.*b` is classed cheap here, but on
JDK 25 it took 2.5 s on one 400-character value, about the same as without the
anchor. `\b` is not a start anchor at all: with `find()`, the match is still
tried at every word boundary.
By contrast, the nested-group pattern in the new test, `(a+)+b`, took 0 ms
on the same JDK, which avoids that exponential case. Could the anchor exemption
apply only when the rest of the pattern has at most one quantifier, or be
dropped?
##########
sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/optimizer/FilterPushdownSuite.scala:
##########
@@ -61,6 +61,10 @@ class FilterPushdownSuite extends PlanTest {
val testStringRelation = LocalRelation(attrA, attrB, attrE)
+ // Stands in for an expensive expression: a regex whose pattern is not a
constant is compiled
+ // for every row.
+ private def expensiveRLike(tag: String): Expression =
$"e".rlike(Concat(Seq($"e", Literal(tag))))
Review Comment:
**10. [Nit] This helper splits the test relation definitions**
It sits between `testStringRelation` and `testArrayStringRelation`.
`AGENTS.md` asks that a new member go with the code it belongs to, without
splitting an existing section. Could it go after the block of relation and
predicate `val`s?
--
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]
