dongjoon-hyun commented on code in PR #59879:
URL: https://github.com/apache/spark/pull/59879#discussion_r4405703484
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/regexpExpressions.scala:
##########
@@ -84,33 +84,92 @@ 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`. Like
`ConstantFolding`, evaluate a fresh
+ // copy so that a stateful pattern keeps its state.
+ private lazy val _expensivePattern = !right.foldable || {
+ try {
+ val str = right.freshCopyIfContainsStatefulExpression().eval()
+ str != null && isExpensivePattern(str.toString)
+ } catch {
+ // E.g. a pattern that `ConstantFolding` left in a conditional branch
because it throws.
+ case NonFatal(_) => true
}
}
+
+ /** Whether matching against the constant pattern `str` is likely to be
expensive. */
+ protected def isExpensivePattern(str: String): Boolean = true
}
private[catalyst] object StringRegexExpression {
+ /**
+ * Counts the `%` wildcards in a LIKE pattern, skipping escaped characters.
Each one becomes a
+ * `.*`, and a failed match tries every combination of their lengths.
+ */
+ def countLikeWildcards(pattern: String, escapeChar: Char): Int = {
+ var count = 0
+ var i = 0
+ while (i < pattern.length) {
+ val c = pattern.charAt(i)
+ if (c == escapeChar) {
+ i += 1
+ } else if (c == '%') {
+ count += 1
+ }
+ i += 1
+ }
+ count
+ }
+
+ /**
+ * Counts the repeating quantifiers (`*`, `+` and `{n,m}`) in a regex, which
are what make a
+ * failed match backtrack. Escaped characters, quoted text, character
classes and the braces of
+ * `\p{..}`, `\x{..}` and `\N{..}` are skipped, and the `+` or `?` that
makes a quantifier
+ * possessive or lazy is not counted again.
+ */
+ def countRegexQuantifiers(regex: String): Int = {
+ var count = 0
+ var classDepth = 0
+ var i = 0
+ // Moves `i` past a `+` or `?` that modifies the quantifier ending at `i`.
+ def skipModifier(): Unit = {
+ if (i + 1 < regex.length && (regex.charAt(i + 1) == '+' ||
regex.charAt(i + 1) == '?')) {
+ i += 1
+ }
+ }
+ while (i < regex.length) {
+ regex.charAt(i) match {
+ case '\\' if i + 1 < regex.length =>
+ i += 1
+ if (regex.charAt(i) == 'Q') {
+ val end = regex.indexOf("\\E", i)
+ i = if (end < 0) regex.length else end + 1
+ } else if ("pPxN".indexOf(regex.charAt(i)) >= 0 &&
+ i + 1 < regex.length && regex.charAt(i + 1) == '{') {
+ val end = regex.indexOf('}', i)
+ i = if (end < 0) regex.length else end
+ }
+ case '[' => classDepth += 1
Review Comment:
**2. [Low] A `[` that does not open a class hides every later quantifier**
The scanner treats every `[` it does not skip as the start of a class, and
it counts nothing while `classDepth > 0`. Java does not read two kinds of `[`
as a class:
- `\c[` is a control-character escape (ESC). The `'\\'` case consumes only
the `c`, so the `[` opens a class here.
- In a `(?x)` pattern, `#` starts a comment, and the comment may contain a
`[`.
Both `"\\c[.*a.*b"` and `"(?x)a # [\n.*a.*b"` compile in Java. Both count 0
here, although each has the two `.*`s that make `.*a.*b` expensive (4.3 s on
2000 chars on JDK 25).
These patterns are rare. A cheap guard would be to treat a pattern whose
`classDepth` is still positive at the end as expensive, since the stray `[` is
never closed. Skipping the character after `\c` would also fix the first case.
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/regexpExpressions.scala:
##########
@@ -84,33 +84,92 @@ 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`. Like
`ConstantFolding`, evaluate a fresh
+ // copy so that a stateful pattern keeps its state.
+ private lazy val _expensivePattern = !right.foldable || {
+ try {
+ val str = right.freshCopyIfContainsStatefulExpression().eval()
+ str != null && isExpensivePattern(str.toString)
+ } catch {
+ // E.g. a pattern that `ConstantFolding` left in a conditional branch
because it throws.
+ case NonFatal(_) => true
}
}
+
+ /** Whether matching against the constant pattern `str` is likely to be
expensive. */
+ protected def isExpensivePattern(str: String): Boolean = true
}
private[catalyst] object StringRegexExpression {
+ /**
+ * Counts the `%` wildcards in a LIKE pattern, skipping escaped characters.
Each one becomes a
+ * `.*`, and a failed match tries every combination of their lengths.
+ */
+ def countLikeWildcards(pattern: String, escapeChar: Char): Int = {
+ var count = 0
+ var i = 0
+ while (i < pattern.length) {
+ val c = pattern.charAt(i)
+ if (c == escapeChar) {
+ i += 1
+ } else if (c == '%') {
+ count += 1
+ }
+ i += 1
+ }
+ count
+ }
+
+ /**
+ * Counts the repeating quantifiers (`*`, `+` and `{n,m}`) in a regex, which
are what make a
+ * failed match backtrack. Escaped characters, quoted text, character
classes and the braces of
+ * `\p{..}`, `\x{..}` and `\N{..}` are skipped, and the `+` or `?` that
makes a quantifier
+ * possessive or lazy is not counted again.
+ */
+ def countRegexQuantifiers(regex: String): Int = {
+ var count = 0
+ var classDepth = 0
+ var i = 0
+ // Moves `i` past a `+` or `?` that modifies the quantifier ending at `i`.
+ def skipModifier(): Unit = {
+ if (i + 1 < regex.length && (regex.charAt(i + 1) == '+' ||
regex.charAt(i + 1) == '?')) {
+ i += 1
+ }
+ }
+ while (i < regex.length) {
+ regex.charAt(i) match {
+ case '\\' if i + 1 < regex.length =>
+ i += 1
+ if (regex.charAt(i) == 'Q') {
+ val end = regex.indexOf("\\E", i)
+ i = if (end < 0) regex.length else end + 1
+ } else if ("pPxN".indexOf(regex.charAt(i)) >= 0 &&
+ i + 1 < regex.length && regex.charAt(i + 1) == '{') {
+ val end = regex.indexOf('}', i)
+ i = if (end < 0) regex.length else end
+ }
+ case '[' => classDepth += 1
+ case ']' if classDepth > 0 => classDepth -= 1
+ case '*' | '+' if classDepth == 0 =>
+ count += 1
+ skipModifier()
+ case '{' if classDepth == 0 =>
Review Comment:
**1. [Medium] A fixed `{n}` on a group that holds a quantifier is not
counted**
Skipping a `{n}` without a comma is right for `\d{4}`. But on a group, `{n}`
repeats everything inside it, so `(.*a){3}` backtracks like `.*a.*a.*a` and
still counts as one quantifier. The textbook catastrophic-backtracking pattern
is classed cheap:
| Pattern | Count | Input (no match) | JDK 25 | JDK 17 |
|---|---|---|---|---|
| `^(.*?,){11}P` | 1 | one line of 30 comma-separated numbers, 82 chars |
1.9 s | 2.1 s |
| `^(.*?,){13}P` | 1 | the same line | 6.1 s | 6.3 s |
| `(.*a){3}x` | 1 | 400 `a`s | 14.4 s | 7.4 s |
| `.*a.*a.*ax` | 3 | 400 `a`s | 10.2 s | 4.3 s |
So a filter on `col RLIKE '^(.*?,){11}P' AS p` is pushed below the
projection and evaluated twice. Meanwhile the faster `.*a.*a.*ax` stays above
it.
Could a quantifier that follows `)` be counted even when it is a fixed
`{n}`? That gives 2 for both patterns above, and `\d{4}` is still not counted.
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/regexpExpressions.scala:
##########
@@ -84,33 +84,92 @@ 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`. Like
`ConstantFolding`, evaluate a fresh
+ // copy so that a stateful pattern keeps its state.
+ private lazy val _expensivePattern = !right.foldable || {
+ try {
+ val str = right.freshCopyIfContainsStatefulExpression().eval()
+ str != null && isExpensivePattern(str.toString)
+ } catch {
+ // E.g. a pattern that `ConstantFolding` left in a conditional branch
because it throws.
+ case NonFatal(_) => true
}
}
+
+ /** Whether matching against the constant pattern `str` is likely to be
expensive. */
+ protected def isExpensivePattern(str: String): Boolean = true
}
private[catalyst] object StringRegexExpression {
+ /**
+ * Counts the `%` wildcards in a LIKE pattern, skipping escaped characters.
Each one becomes a
+ * `.*`, and a failed match tries every combination of their lengths.
+ */
+ def countLikeWildcards(pattern: String, escapeChar: Char): Int = {
+ var count = 0
+ var i = 0
+ while (i < pattern.length) {
+ val c = pattern.charAt(i)
+ if (c == escapeChar) {
+ i += 1
+ } else if (c == '%') {
+ count += 1
+ }
+ i += 1
+ }
+ count
+ }
+
+ /**
+ * Counts the repeating quantifiers (`*`, `+` and `{n,m}`) in a regex, which
are what make a
+ * failed match backtrack. Escaped characters, quoted text, character
classes and the braces of
+ * `\p{..}`, `\x{..}` and `\N{..}` are skipped, and the `+` or `?` that
makes a quantifier
+ * possessive or lazy is not counted again.
+ */
+ def countRegexQuantifiers(regex: String): Int = {
+ var count = 0
+ var classDepth = 0
+ var i = 0
+ // Moves `i` past a `+` or `?` that modifies the quantifier ending at `i`.
+ def skipModifier(): Unit = {
Review Comment:
**4. [Low] `?+` and `{n}+` are counted, and so are quantifiers that cannot
backtrack**
`skipModifier()` runs only after `*`, `+` and `{n,m}`. After `?` or a fixed
`{n}`, the possessive `+` reaches the `case '*' | '+'` branch and is counted as
a new quantifier:
- `a?+b?+` counts 2.
- `a{3}+b` counts 1.
Neither pattern has a quantifier that can backtrack. The possessive `*+` and
`++` cannot backtrack either, yet each is counted once, so `a*+b*+` is
expensive. A small bounded range is counted like `*` too. The test asserts that
`a{1,9}b{1,9}` is expensive, although each range adds a factor of at most 9,
not a factor of the input length.
All of these err on the expensive side, so nothing regresses from 4.2.0. But
they lose the pushdown and pruning that this PR restores. They also disagree
with the scaladoc, which counts quantifiers because they are "what make a
failed match backtrack". Could the modifier after `?` and `{n}` be skipped too,
and could possessive quantifiers be left uncounted?
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/regexpExpressions.scala:
##########
@@ -534,6 +598,10 @@ case class RLike(left: Expression, right: Expression)
extends StringRegexExpress
override def escape(v: String): String = v
override def matches(regex: Pattern, str: String): Boolean =
regex.matcher(str).find(0)
+ // Like the `%` of LIKE, but `find` also tries every start position, which
costs one more
+ // factor of the input length. An anchor does not bound the backtracking
within a match.
+ override protected def isExpensivePattern(str: String): Boolean =
+ StringRegexExpression.countRegexQuantifiers(str) >= 2
Review Comment:
**3. [Low] An anchored RLIKE gets a lower threshold than the LIKE with the
same cost**
This reopens part of my [round-1 comment
3](https://github.com/apache/spark/pull/59879#discussion_r4405059885). As I
wrote there, an anchor does not bound the backtracking inside a match. But it
does remove the extra factor that the comment above uses to justify 2 instead
of 3. With `^`, `find()` fails at once at every start position after the first.
So a `^`-anchored RLIKE costs about the same as the LIKE with the same
number of `.*`s, yet the two are classed differently:
| Pattern | Count | Classed | 2000 `a`s, JDK 25 | JDK 17 |
|---|---|---|---|---|
| LIKE `'%a%b'` | 2 | cheap | 15 ms | 21 ms |
| RLIKE `'^.*a.*b'` | 2 | expensive | 9 ms | 16 ms |
| RLIKE `'.*a.*b'` | 2 | expensive | 4.3 s | 4.8 s |
With three wildcards on 400 `a`s, LIKE `'%a%a%b'` took 31 ms and RLIKE
`'^.*a.*a.*b'` took 35 ms on JDK 25. Without the anchor, `'.*a.*a.*b'` took 3.7
s.
This costs the pruning that this PR restores. For example, a filter on `part
RLIKE '^v[0-9]+_.*' AS p` still stays above the projection. Could a pattern
that starts with `^` or `\A` use the LIKE threshold of 3, when it has no `(?m)`
flag and no top-level `|`?
##########
sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/expressions/RegexpExpressionsSuite.scala:
##########
@@ -735,4 +735,46 @@ 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")
{
+ val str = $"s".string.at(0)
+ val pattern = $"p".string.at(1)
+
+ // The subject string is irrelevant; a constant pattern is checked. Two or
more repeating
+ // quantifiers make an RLIKE expensive, anchored or not.
+ Seq("^1", "magic", "a.b", "^a.*b", "2024-.*", "\\d{2,}", "a{3}b*", "a*+b",
"(?i)^abc.*",
+ "a\\+b\\*", "[+*{]x+", "\\p{Lu}+", "\\x{41}.*", "\\Q.*+\\E.*").foreach {
p =>
+ assert(!RLike(str, Literal(p)).expensive, p)
+ }
+ Seq(".*a.*b", "^.*a.*a.*a.*b", "\\b.*a.*b", "(a+)+b", "a{2,}b+",
"\\d+\\s*", "a+?b.*",
+ "a{1,9}b{1,9}").foreach { p =>
Review Comment:
**6. [Nit] No case covers a quantified group or a `[` that is not a class**
All the new RLIKE cases are flat. Could the expensive list also have
`"^(.*?,){11}P"`, `"(.*a){3}x"` and `"\\c[.*a.*b"`? All three fail today, which
is items 1 and 2. A nested or intersected class such as `"[a-z&&[^b]]+x"` in
the cheap list would also pin down the `classDepth` handling.
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/regexpExpressions.scala:
##########
@@ -84,33 +84,92 @@ 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`. Like
`ConstantFolding`, evaluate a fresh
+ // copy so that a stateful pattern keeps its state.
+ private lazy val _expensivePattern = !right.foldable || {
+ try {
+ val str = right.freshCopyIfContainsStatefulExpression().eval()
+ str != null && isExpensivePattern(str.toString)
+ } catch {
+ // E.g. a pattern that `ConstantFolding` left in a conditional branch
because it throws.
+ case NonFatal(_) => true
}
}
+
+ /** Whether matching against the constant pattern `str` is likely to be
expensive. */
+ protected def isExpensivePattern(str: String): Boolean = true
}
private[catalyst] object StringRegexExpression {
+ /**
+ * Counts the `%` wildcards in a LIKE pattern, skipping escaped characters.
Each one becomes a
+ * `.*`, and a failed match tries every combination of their lengths.
+ */
+ def countLikeWildcards(pattern: String, escapeChar: Char): Int = {
Review Comment:
**5. [Nit] `countLikeWildcards` can be `countRegexQuantifiers(escape(str))`**
`escape` turns each unescaped `%` into `.*` and quotes every other character
with `\Q..\E`, which `countRegexQuantifiers` skips. So
`countRegexQuantifiers(escape(str))` gives the same count. I checked the LIKE
patterns in the new test, plus `%a\\%b%` (an escaped backslash, then a
wildcard) and `50\%%off%%`, and the counts match for all of them.
That would leave one parser of the LIKE escape rules instead of two.
`escapeLikeRegex` walks code points and throws on a bad escape, while this loop
walks chars and skips a bad escape silently. With the change, a bad escape
would throw inside the existing `try` and count as expensive.
`isExpensivePattern` could then live in `StringRegexExpression`, and `Like` and
`RLike` would give only their thresholds.
--
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]
