viirya commented on code in PR #59879:
URL: https://github.com/apache/spark/pull/59879#discussion_r4408359339
##########
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:
Good catch. Counting the `{n}` after `)` once would not survive item 3,
though: with the anchored threshold of 3, `^(.*?,){11}P` would count 2 and be
cheap again. So a repeated group that holds a counted quantifier now makes the
pattern expensive outright, whatever the anchor, since the repetition
multiplies the factors inside it. This covers `{n}`, `{n,m}` with an upper
bound of at least 2, `*` and `+`, and also `(a+)+b` and `^(a+)+b`. A repeated
group without a quantifier inside, such as `(ab){3}.*`, is not affected.
##########
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:
Done both: the character after `\c` is skipped, and a `[` that is still open
at the end makes the pattern expensive, which covers the `(?x)` comment case.
##########
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:
You're right, and my round-1 reply misread my own numbers: `^.*a.*a.*a.*b`
taking as long as `.*a.*a.*b` shows exactly that the anchor removes one factor.
On JDK 17 I see `^.*a.*a.*b` at 42 ms and `\A.*a.*a.*b` at 41 ms on 400 `a`s,
against 40 ms for LIKE `'%a%a%b'` and 4.2 s for `.*a.*a.*b`.
A pattern that starts with `^` or `\A` now uses the threshold of 3, unless a
leading inline flag mentions `m` or the pattern has a `|` outside any group.
`^v[0-9]+_.*` is now cheap (0.2 ms on 2000 characters), while `^a|.*b.*c` and
`(?m)^.*a.*b` stay expensive. LIKE goes through the same path as a regex that
must match the whole input, so both use 3.
##########
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:
Done. `?` now skips its modifier like the others, a fixed `{n}` is consumed
together with its modifier, and a possessive quantifier is not counted, so
`a?+b?+`, `a{3}+b`, `a*+b*+` and `.*+a.*+b` are cheap (`.*+a.*+b` takes 35 ms
on 2000 characters). A `{n,m}` is counted only when its range is unbounded or
spans at least 10. On 400 characters, three `.{0,9}` took 2.8 ms and three
`.{0,50}` took 120 ms, so `a{1,9}b{1,9}` moved to the cheap cases and
`.{0,50}a.{0,50}b` is in the expensive ones.
##########
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:
Done. `Like` now passes `escape(str)` to the same `isExpensiveRegex` that
`RLike` uses, with `matchesWhole = true`, and `countLikeWildcards` is gone. A
bad escape throws inside the existing `try` and counts as expensive, which the
test now covers. `isExpensivePattern` still defaults to `true` in
`StringRegexExpression`, so a subclass outside Spark keeps the 4.2.0 answer.
##########
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:
Added all of them, plus `^(a+)+b`, `^((.*a)b){2}`, the `(?x)` comment case,
the anchored cases from item 3 and the possessive and range cases from item 4.
`[a-z&&[^b]]+x` is in the cheap list.
--
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]
