dongjoon-hyun commented on code in PR #59879:
URL: https://github.com/apache/spark/pull/59879#discussion_r4413332231
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/regexpExpressions.scala:
##########
@@ -84,33 +84,152 @@ 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 {
+ /**
+ * Whether matching `regex` is likely to be expensive. A failed match tries
every combination of
+ * the lengths that its repeating quantifiers take, so each one costs a
factor of the input
+ * length. `find` also tries every start position, which costs one more
factor unless the regex
+ * is anchored at the start. So two quantifiers are expensive, and three
when the regex is
+ * anchored or must match the whole input, as the one a LIKE pattern
becomes. Repeating a group
+ * that holds a quantifier multiplies the factors, so it is always expensive.
+ *
+ * @param matchesWhole whether `regex` must match the whole input rather
than be found in it.
+ */
+ def isExpensiveRegex(regex: String, matchesWhole: Boolean): Boolean = {
+ val (quantifiers, topLevelAlternation) = scanQuantifiers(regex)
+ val anchored = matchesWhole || (!topLevelAlternation &&
startsWithAnchor(regex))
+ quantifiers >= (if (anchored) 3 else 2)
+ }
+
+ // Leading inline flags, e.g. `(?i)` or `(?s-m)`.
+ private val leadingFlags = """(?:\(\?[a-zA-Z]*(?:-[a-zA-Z]*)?\))*""".r
+
+ // Whether `regex` starts with `^` or `\A`. A leading flag that mentions
MULTILINE, under which
+ // `^` also matches after every line terminator, makes it not anchored.
+ private def startsWithAnchor(regex: String): Boolean = {
+ val flags = leadingFlags.findPrefixOf(regex).getOrElse("")
+ val rest = regex.substring(flags.length)
+ !flags.contains('m') && (rest.startsWith("^") || rest.startsWith("\\A"))
+ }
+
+ /**
+ * Counts the repeating quantifiers (`*`, `+` and `{n,m}`) in a regex that
can backtrack, and
+ * tells whether the regex has a `|` outside any group. Escaped characters,
quoted text,
+ * character classes and the braces of `\p{..}`, `\x{..}` and `\N{..}` are
skipped. A possessive
+ * quantifier never backtracks and a `{n,m}` with a small range adds a small
factor, so neither
+ * is counted. The count is `Int.MaxValue` for a repeated group that holds a
counted quantifier,
+ * and for a `[` that is never closed, which may hide quantifiers.
+ */
+ private def scanQuantifiers(regex: String): (Int, Boolean) = {
+ var count = 0
+ var classDepth = 0
+ var topLevelAlternation = false
+ // Whether each open group holds a counted quantifier, innermost first.
+ var groups = List.empty[Boolean]
+ var i = 0
+ def possessive: Boolean = i + 1 < regex.length && regex.charAt(i + 1) ==
'+'
+ // 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
+ }
+ }
+ def markGroup(): Unit = groups = groups match {
+ case _ :: outer => true :: outer
+ case Nil => Nil
+ }
+ while (i < regex.length) {
+ regex.charAt(i) match {
+ case '\\' if i + 1 < regex.length =>
+ i += 1
+ regex.charAt(i) match {
+ case 'Q' =>
+ val end = regex.indexOf("\\E", i)
+ i = if (end < 0) regex.length else end + 1
+ // `\cX` is a control character, and `X` may be `[`.
+ case 'c' => i += 1
+ case c if "pPxN".indexOf(c) >= 0 &&
+ i + 1 < regex.length && regex.charAt(i + 1) == '{' =>
+ val end = regex.indexOf('}', i)
+ i = if (end < 0) regex.length else end
+ case _ =>
+ }
+ case '[' => classDepth += 1
+ case ']' if classDepth > 0 => classDepth -= 1
+ case _ if classDepth > 0 =>
+ case '(' => groups = false :: groups
+ case ')' if groups.nonEmpty =>
+ val holdsQuantifier = groups.head
+ groups = groups.tail
+ if (holdsQuantifier) {
+ if (repeats(regex, i + 1)) return (Int.MaxValue,
topLevelAlternation)
+ markGroup()
+ }
+ case '|' if groups.isEmpty => topLevelAlternation = true
+ case '*' | '+' =>
+ if (!possessive) {
+ count += 1
+ markGroup()
+ }
+ skipModifier()
+ case '?' => skipModifier()
+ case '{' =>
+ bounds(regex, i).foreach { case (end, min, max) =>
+ i = end
+ if (!possessive && max - min >= 10) {
+ count += 1
+ markGroup()
+ }
+ skipModifier()
+ }
+ case _ =>
+ }
+ i += 1
+ }
+ (if (classDepth > 0) Int.MaxValue else count, topLevelAlternation)
+ }
+
+ // Whether a quantifier that can repeat its operand more than once starts at
`i`.
+ private def repeats(regex: String, i: Int): Boolean = i < regex.length && {
Review Comment:
**2. [Medium] Under `(?x)`, whitespace before a group's quantifier hides the
repeat**
`repeats(regex, i + 1)` looks only at the character right after `)`. In
`(?x)` mode, Java skips whitespace before a quantifier, so `(...) {11}` still
repeats the group. The scanner reads the `{11}` as a fixed count on its own
instead:
| Pattern | Count | Input (no match) | JDK 25 | JDK 17 |
|---|---|---|---|---|
| `(?x) ^ (.*?,){11} P` | MAX | 30 comma-separated numbers, 80 chars | 1.3 s
| 1.3 s |
| `(?x) ^ (.*?,) {11} P` | 1 | the same line | 1.4 s | 1.3 s |
| `(?x)(.*a) {3}x` | 1 | 200 `a`s | 0.55 s | 0.45 s |
The `[` inside a `(?x)` comment is already handled, but the scanner would
need to follow comments mode in more places to get this right. Since `(?x)` is
rare in a LIKE/RLIKE filter, could a pattern that turns on `x` in an inline
flag just be expensive? For example:
```scala
// Comments mode lets whitespace and comments separate a group from its
quantifier.
private val commentsFlag = """\(\?[a-zA-Z]*x""".r
def isExpensiveRegex(regex: String, matchesWhole: Boolean): Boolean =
commentsFlag.findFirstIn(regex).nonEmpty || {
val (quantifiers, topLevelAlternation) = scanQuantifiers(regex)
val anchored = matchesWhole || (!topLevelAlternation &&
startsWithAnchor(regex))
quantifiers >= (if (anchored) 3 else 2)
}
```
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/regexpExpressions.scala:
##########
@@ -182,6 +301,10 @@ case class Like(left: Expression, right: Expression,
escapeChar: Char)
override def matches(regex: Pattern, str: String): Boolean =
regex.matcher(str).matches()
+ // Each `%` becomes a `.*`. `LikeSimplification` rewrites most patterns with
fewer than three.
+ override protected def isExpensivePattern(str: String): Boolean =
Review Comment:
**4. [Low] A quantifier at the end of the pattern is counted, though a
failed match never backtracks into it**
Once matching reaches the last token, the match succeeds: the trailing `.*`
of a LIKE pattern runs to the end under `(?s)`, and `find` stops at the first
match. So the last quantifier never multiplies the cost of a failed match. It
is counted anyway. That makes the common `LIKE '%foo%bar%'` expensive while
`LIKE '%foo%bar'` is cheap, and `LikeSimplification` rewrites neither.
| Pattern | Count | Classed | JDK 25 | JDK 17 |
|---|---|---|---|---|
| LIKE `'%a%b'` | 2 | cheap | 11 ms | 14 ms |
| LIKE `'%a%b%'` | 3 | expensive | 4 ms | 3 ms |
| RLIKE `'a.*b'` | 1 | cheap | 4 ms | 4 ms |
| RLIKE `'a.*b.*'` | 2 | expensive | 4 ms | 3 ms |
| RLIKE `'a+?b.*'` | 2 | expensive | 15 ms | 16 ms |
| RLIKE `'\d+\s*'` | 2 | expensive | 0 ms | 0 ms |
Each input is one value of 2000 `a`s, or 2000 `x`s for the last row, and
none of them matches.
The new test pins three of these as expensive: `"%a%b%"` at
`RegexpExpressionsSuite.scala:769`, and `"\\d+\\s*"` and `"a+?b.*"` at
`RegexpExpressionsSuite.scala:755`. Could the scanner leave out a quantifier
that ends the pattern?
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/regexpExpressions.scala:
##########
@@ -84,33 +84,152 @@ 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 {
+ /**
+ * Whether matching `regex` is likely to be expensive. A failed match tries
every combination of
+ * the lengths that its repeating quantifiers take, so each one costs a
factor of the input
+ * length. `find` also tries every start position, which costs one more
factor unless the regex
+ * is anchored at the start. So two quantifiers are expensive, and three
when the regex is
+ * anchored or must match the whole input, as the one a LIKE pattern
becomes. Repeating a group
+ * that holds a quantifier multiplies the factors, so it is always expensive.
+ *
+ * @param matchesWhole whether `regex` must match the whole input rather
than be found in it.
+ */
+ def isExpensiveRegex(regex: String, matchesWhole: Boolean): Boolean = {
+ val (quantifiers, topLevelAlternation) = scanQuantifiers(regex)
+ val anchored = matchesWhole || (!topLevelAlternation &&
startsWithAnchor(regex))
+ quantifiers >= (if (anchored) 3 else 2)
+ }
+
+ // Leading inline flags, e.g. `(?i)` or `(?s-m)`.
+ private val leadingFlags = """(?:\(\?[a-zA-Z]*(?:-[a-zA-Z]*)?\))*""".r
+
+ // Whether `regex` starts with `^` or `\A`. A leading flag that mentions
MULTILINE, under which
+ // `^` also matches after every line terminator, makes it not anchored.
+ private def startsWithAnchor(regex: String): Boolean = {
+ val flags = leadingFlags.findPrefixOf(regex).getOrElse("")
+ val rest = regex.substring(flags.length)
+ !flags.contains('m') && (rest.startsWith("^") || rest.startsWith("\\A"))
+ }
+
+ /**
+ * Counts the repeating quantifiers (`*`, `+` and `{n,m}`) in a regex that
can backtrack, and
+ * tells whether the regex has a `|` outside any group. Escaped characters,
quoted text,
+ * character classes and the braces of `\p{..}`, `\x{..}` and `\N{..}` are
skipped. A possessive
+ * quantifier never backtracks and a `{n,m}` with a small range adds a small
factor, so neither
+ * is counted. The count is `Int.MaxValue` for a repeated group that holds a
counted quantifier,
+ * and for a `[` that is never closed, which may hide quantifiers.
+ */
+ private def scanQuantifiers(regex: String): (Int, Boolean) = {
+ var count = 0
+ var classDepth = 0
+ var topLevelAlternation = false
+ // Whether each open group holds a counted quantifier, innermost first.
Review Comment:
**1. [Medium] A repeated group that holds a small range or an alternation is
not caught**
Making a repeated group with a quantifier inside expensive outright fixes
`^(.*?,){11}P`, thanks. But the group is marked only next to `count += 1`, so a
group whose choices come from an uncounted `{n,m}` or from a `|` stays
unmarked. Each repetition multiplies those choices too. These patterns count 0
and are classed cheap:
| Pattern | Input (no match) | JDK 25 | JDK 17 |
|---|---|---|---|
| `(a{1,9}){6}b` | 400 `a`s | 1.6 s | 1.8 s |
| `^(a{1,9}){8}b` | 400 `a`s | 0.32 s | 0.41 s |
| `(a\|aa){20}b` | 100 `a`s | 1.4 s | 1.3 s |
| `^(\d\|\w){24}x` | 60 `1`s | 0.33 s | 0.35 s |
The anchored ones try only one start position, and each extra repetition of
`(\d|\w)` doubles the time. `?` is different: `^(a?){25}a{25}` and `^(.?){30}x`
take 0 ms on both JDKs, so it can stay out.
Could a group also be marked when it holds an uncounted `{n,m}` or a `|`?
`(a|b){3}` would then be expensive too, which errs on the same side as the rest
of the rule.
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/regexpExpressions.scala:
##########
@@ -84,33 +84,152 @@ 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 {
+ /**
+ * Whether matching `regex` is likely to be expensive. A failed match tries
every combination of
+ * the lengths that its repeating quantifiers take, so each one costs a
factor of the input
+ * length. `find` also tries every start position, which costs one more
factor unless the regex
+ * is anchored at the start. So two quantifiers are expensive, and three
when the regex is
+ * anchored or must match the whole input, as the one a LIKE pattern
becomes. Repeating a group
+ * that holds a quantifier multiplies the factors, so it is always expensive.
+ *
+ * @param matchesWhole whether `regex` must match the whole input rather
than be found in it.
+ */
+ def isExpensiveRegex(regex: String, matchesWhole: Boolean): Boolean = {
+ val (quantifiers, topLevelAlternation) = scanQuantifiers(regex)
+ val anchored = matchesWhole || (!topLevelAlternation &&
startsWithAnchor(regex))
+ quantifiers >= (if (anchored) 3 else 2)
+ }
+
+ // Leading inline flags, e.g. `(?i)` or `(?s-m)`.
+ private val leadingFlags = """(?:\(\?[a-zA-Z]*(?:-[a-zA-Z]*)?\))*""".r
+
+ // Whether `regex` starts with `^` or `\A`. A leading flag that mentions
MULTILINE, under which
+ // `^` also matches after every line terminator, makes it not anchored.
+ private def startsWithAnchor(regex: String): Boolean = {
+ val flags = leadingFlags.findPrefixOf(regex).getOrElse("")
+ val rest = regex.substring(flags.length)
+ !flags.contains('m') && (rest.startsWith("^") || rest.startsWith("\\A"))
+ }
+
+ /**
+ * Counts the repeating quantifiers (`*`, `+` and `{n,m}`) in a regex that
can backtrack, and
+ * tells whether the regex has a `|` outside any group. Escaped characters,
quoted text,
+ * character classes and the braces of `\p{..}`, `\x{..}` and `\N{..}` are
skipped. A possessive
+ * quantifier never backtracks and a `{n,m}` with a small range adds a small
factor, so neither
+ * is counted. The count is `Int.MaxValue` for a repeated group that holds a
counted quantifier,
+ * and for a `[` that is never closed, which may hide quantifiers.
+ */
+ private def scanQuantifiers(regex: String): (Int, Boolean) = {
+ var count = 0
+ var classDepth = 0
+ var topLevelAlternation = false
+ // Whether each open group holds a counted quantifier, innermost first.
+ var groups = List.empty[Boolean]
+ var i = 0
+ def possessive: Boolean = i + 1 < regex.length && regex.charAt(i + 1) ==
'+'
+ // 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
+ }
+ }
+ def markGroup(): Unit = groups = groups match {
+ case _ :: outer => true :: outer
+ case Nil => Nil
+ }
+ while (i < regex.length) {
+ regex.charAt(i) match {
+ case '\\' if i + 1 < regex.length =>
+ i += 1
+ regex.charAt(i) match {
+ case 'Q' =>
+ val end = regex.indexOf("\\E", i)
+ i = if (end < 0) regex.length else end + 1
+ // `\cX` is a control character, and `X` may be `[`.
+ case 'c' => i += 1
+ case c if "pPxN".indexOf(c) >= 0 &&
+ i + 1 < regex.length && regex.charAt(i + 1) == '{' =>
+ val end = regex.indexOf('}', i)
+ i = if (end < 0) regex.length else end
+ case _ =>
+ }
+ case '[' => classDepth += 1
+ case ']' if classDepth > 0 => classDepth -= 1
+ case _ if classDepth > 0 =>
+ case '(' => groups = false :: groups
+ case ')' if groups.nonEmpty =>
+ val holdsQuantifier = groups.head
+ groups = groups.tail
+ if (holdsQuantifier) {
+ if (repeats(regex, i + 1)) return (Int.MaxValue,
topLevelAlternation)
+ markGroup()
+ }
+ case '|' if groups.isEmpty => topLevelAlternation = true
+ case '*' | '+' =>
+ if (!possessive) {
+ count += 1
+ markGroup()
+ }
+ skipModifier()
+ case '?' => skipModifier()
+ case '{' =>
+ bounds(regex, i).foreach { case (end, min, max) =>
+ i = end
+ if (!possessive && max - min >= 10) {
Review Comment:
**3. [Low] Small ranges in sequence multiply, but none of them is counted**
A `{n,m}` that spans fewer than 10 is left out because one of them adds only
a small factor. Several in a row multiply, like any other quantifiers.
`.{0,9}a.{0,9}a.{0,9}a.{0,9}a.{0,9}a.{0,9}x` counts 0 and is classed cheap, yet
one value of 400 `a`s takes 0.90 s on JDK 25 and 0.81 s on JDK 17.
Could the scanner multiply the `max - min + 1` of the small ranges, and
count them as one quantifier once the product passes, say, 1000? Three
`.{0,9}`, which you measured at 2.8 ms, would stay cheap.
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/regexpExpressions.scala:
##########
@@ -84,33 +84,152 @@ 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 {
+ /**
+ * Whether matching `regex` is likely to be expensive. A failed match tries
every combination of
+ * the lengths that its repeating quantifiers take, so each one costs a
factor of the input
+ * length. `find` also tries every start position, which costs one more
factor unless the regex
+ * is anchored at the start. So two quantifiers are expensive, and three
when the regex is
+ * anchored or must match the whole input, as the one a LIKE pattern
becomes. Repeating a group
+ * that holds a quantifier multiplies the factors, so it is always expensive.
+ *
+ * @param matchesWhole whether `regex` must match the whole input rather
than be found in it.
+ */
+ def isExpensiveRegex(regex: String, matchesWhole: Boolean): Boolean = {
+ val (quantifiers, topLevelAlternation) = scanQuantifiers(regex)
+ val anchored = matchesWhole || (!topLevelAlternation &&
startsWithAnchor(regex))
+ quantifiers >= (if (anchored) 3 else 2)
+ }
+
+ // Leading inline flags, e.g. `(?i)` or `(?s-m)`.
+ private val leadingFlags = """(?:\(\?[a-zA-Z]*(?:-[a-zA-Z]*)?\))*""".r
+
+ // Whether `regex` starts with `^` or `\A`. A leading flag that mentions
MULTILINE, under which
+ // `^` also matches after every line terminator, makes it not anchored.
+ private def startsWithAnchor(regex: String): Boolean = {
+ val flags = leadingFlags.findPrefixOf(regex).getOrElse("")
+ val rest = regex.substring(flags.length)
+ !flags.contains('m') && (rest.startsWith("^") || rest.startsWith("\\A"))
+ }
+
+ /**
+ * Counts the repeating quantifiers (`*`, `+` and `{n,m}`) in a regex that
can backtrack, and
+ * tells whether the regex has a `|` outside any group. Escaped characters,
quoted text,
+ * character classes and the braces of `\p{..}`, `\x{..}` and `\N{..}` are
skipped. A possessive
+ * quantifier never backtracks and a `{n,m}` with a small range adds a small
factor, so neither
+ * is counted. The count is `Int.MaxValue` for a repeated group that holds a
counted quantifier,
+ * and for a `[` that is never closed, which may hide quantifiers.
+ */
+ private def scanQuantifiers(regex: String): (Int, Boolean) = {
+ var count = 0
+ var classDepth = 0
+ var topLevelAlternation = false
+ // Whether each open group holds a counted quantifier, innermost first.
+ var groups = List.empty[Boolean]
+ var i = 0
+ def possessive: Boolean = i + 1 < regex.length && regex.charAt(i + 1) ==
'+'
+ // 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
+ }
+ }
+ def markGroup(): Unit = groups = groups match {
+ case _ :: outer => true :: outer
+ case Nil => Nil
+ }
+ while (i < regex.length) {
+ regex.charAt(i) match {
+ case '\\' if i + 1 < regex.length =>
+ i += 1
+ regex.charAt(i) match {
+ case 'Q' =>
+ val end = regex.indexOf("\\E", i)
+ i = if (end < 0) regex.length else end + 1
+ // `\cX` is a control character, and `X` may be `[`.
+ case 'c' => i += 1
+ case c if "pPxN".indexOf(c) >= 0 &&
+ i + 1 < regex.length && regex.charAt(i + 1) == '{' =>
+ val end = regex.indexOf('}', i)
+ i = if (end < 0) regex.length else end
+ case _ =>
+ }
+ case '[' => classDepth += 1
+ case ']' if classDepth > 0 => classDepth -= 1
+ case _ if classDepth > 0 =>
+ case '(' => groups = false :: groups
+ case ')' if groups.nonEmpty =>
+ val holdsQuantifier = groups.head
+ groups = groups.tail
+ if (holdsQuantifier) {
+ if (repeats(regex, i + 1)) return (Int.MaxValue,
topLevelAlternation)
Review Comment:
**8. [Nit] A repeated group between distinct delimiters is always expensive**
This follows from my round-2 item 1, so it is a trade-off rather than a bug.
`^(\d+\.){3}\d+$` (an IPv4 check) and `^([a-z]+_)*[a-z]+$` (a snake_case check)
are now MAX, although `\d+` cannot run past the `.` that follows it.
`^(\d+\.){3}\d+$` takes 0 ms on JDK 25 and JDK 17 for `1.2.3.` followed by 2000
digits and an `x`. A filter on such a validation alias stays above the
projection, as in 4.2.0.
One possible exception: leave a group unmarked when each quantified token in
it is a class or an escape that the next literal cannot match. If that is not
worth the extra code, I'm fine with keeping the simple rule.
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/regexpExpressions.scala:
##########
@@ -84,33 +84,152 @@ 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 {
+ /**
+ * Whether matching `regex` is likely to be expensive. A failed match tries
every combination of
+ * the lengths that its repeating quantifiers take, so each one costs a
factor of the input
+ * length. `find` also tries every start position, which costs one more
factor unless the regex
+ * is anchored at the start. So two quantifiers are expensive, and three
when the regex is
+ * anchored or must match the whole input, as the one a LIKE pattern
becomes. Repeating a group
+ * that holds a quantifier multiplies the factors, so it is always expensive.
+ *
+ * @param matchesWhole whether `regex` must match the whole input rather
than be found in it.
+ */
+ def isExpensiveRegex(regex: String, matchesWhole: Boolean): Boolean = {
+ val (quantifiers, topLevelAlternation) = scanQuantifiers(regex)
+ val anchored = matchesWhole || (!topLevelAlternation &&
startsWithAnchor(regex))
+ quantifiers >= (if (anchored) 3 else 2)
+ }
+
+ // Leading inline flags, e.g. `(?i)` or `(?s-m)`.
+ private val leadingFlags = """(?:\(\?[a-zA-Z]*(?:-[a-zA-Z]*)?\))*""".r
+
+ // Whether `regex` starts with `^` or `\A`. A leading flag that mentions
MULTILINE, under which
+ // `^` also matches after every line terminator, makes it not anchored.
+ private def startsWithAnchor(regex: String): Boolean = {
+ val flags = leadingFlags.findPrefixOf(regex).getOrElse("")
+ val rest = regex.substring(flags.length)
+ !flags.contains('m') && (rest.startsWith("^") || rest.startsWith("\\A"))
+ }
+
+ /**
+ * Counts the repeating quantifiers (`*`, `+` and `{n,m}`) in a regex that
can backtrack, and
+ * tells whether the regex has a `|` outside any group. Escaped characters,
quoted text,
+ * character classes and the braces of `\p{..}`, `\x{..}` and `\N{..}` are
skipped. A possessive
+ * quantifier never backtracks and a `{n,m}` with a small range adds a small
factor, so neither
+ * is counted. The count is `Int.MaxValue` for a repeated group that holds a
counted quantifier,
+ * and for a `[` that is never closed, which may hide quantifiers.
+ */
+ private def scanQuantifiers(regex: String): (Int, Boolean) = {
+ var count = 0
+ var classDepth = 0
+ var topLevelAlternation = false
+ // Whether each open group holds a counted quantifier, innermost first.
+ var groups = List.empty[Boolean]
+ var i = 0
+ def possessive: Boolean = i + 1 < regex.length && regex.charAt(i + 1) ==
'+'
+ // 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
+ }
+ }
+ def markGroup(): Unit = groups = groups match {
+ case _ :: outer => true :: outer
+ case Nil => Nil
+ }
+ while (i < regex.length) {
+ regex.charAt(i) match {
+ case '\\' if i + 1 < regex.length =>
+ i += 1
+ regex.charAt(i) match {
+ case 'Q' =>
+ val end = regex.indexOf("\\E", i)
+ i = if (end < 0) regex.length else end + 1
+ // `\cX` is a control character, and `X` may be `[`.
+ case 'c' => i += 1
+ case c if "pPxN".indexOf(c) >= 0 &&
+ i + 1 < regex.length && regex.charAt(i + 1) == '{' =>
+ val end = regex.indexOf('}', i)
+ i = if (end < 0) regex.length else end
+ case _ =>
+ }
+ case '[' => classDepth += 1
+ case ']' if classDepth > 0 => classDepth -= 1
+ case _ if classDepth > 0 =>
+ case '(' => groups = false :: groups
+ case ')' if groups.nonEmpty =>
+ val holdsQuantifier = groups.head
+ groups = groups.tail
+ if (holdsQuantifier) {
+ if (repeats(regex, i + 1)) return (Int.MaxValue,
topLevelAlternation)
+ markGroup()
+ }
+ case '|' if groups.isEmpty => topLevelAlternation = true
+ case '*' | '+' =>
Review Comment:
**9. [Nit] The three quantifier cases repeat the same steps**
The `*`/`+`, `?` and `{` cases each check `possessive`, count, mark the
group and skip the modifier. A local helper would keep them in step when the
counting rule changes again, as in items 1 and 3:
```scala
// Counts the quantifier that ends at `i` unless it is possessive, then
skips its modifier.
def quantifier(counted: Boolean): Unit = {
if (counted && !possessive) {
count += 1
markGroup()
}
skipModifier()
}
...
case '*' | '+' => quantifier(counted = true)
case '?' => quantifier(counted = false)
case '{' =>
bounds(regex, i).foreach { case (end, min, max) =>
i = end
quantifier(counted = max - min >= 10)
}
```
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/regexpExpressions.scala:
##########
@@ -84,33 +84,152 @@ 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 {
+ /**
+ * Whether matching `regex` is likely to be expensive. A failed match tries
every combination of
+ * the lengths that its repeating quantifiers take, so each one costs a
factor of the input
+ * length. `find` also tries every start position, which costs one more
factor unless the regex
+ * is anchored at the start. So two quantifiers are expensive, and three
when the regex is
+ * anchored or must match the whole input, as the one a LIKE pattern
becomes. Repeating a group
+ * that holds a quantifier multiplies the factors, so it is always expensive.
+ *
+ * @param matchesWhole whether `regex` must match the whole input rather
than be found in it.
+ */
+ def isExpensiveRegex(regex: String, matchesWhole: Boolean): Boolean = {
+ val (quantifiers, topLevelAlternation) = scanQuantifiers(regex)
+ val anchored = matchesWhole || (!topLevelAlternation &&
startsWithAnchor(regex))
+ quantifiers >= (if (anchored) 3 else 2)
+ }
+
+ // Leading inline flags, e.g. `(?i)` or `(?s-m)`.
+ private val leadingFlags = """(?:\(\?[a-zA-Z]*(?:-[a-zA-Z]*)?\))*""".r
+
+ // Whether `regex` starts with `^` or `\A`. A leading flag that mentions
MULTILINE, under which
+ // `^` also matches after every line terminator, makes it not anchored.
+ private def startsWithAnchor(regex: String): Boolean = {
+ val flags = leadingFlags.findPrefixOf(regex).getOrElse("")
+ val rest = regex.substring(flags.length)
+ !flags.contains('m') && (rest.startsWith("^") || rest.startsWith("\\A"))
+ }
+
+ /**
+ * Counts the repeating quantifiers (`*`, `+` and `{n,m}`) in a regex that
can backtrack, and
+ * tells whether the regex has a `|` outside any group. Escaped characters,
quoted text,
+ * character classes and the braces of `\p{..}`, `\x{..}` and `\N{..}` are
skipped. A possessive
+ * quantifier never backtracks and a `{n,m}` with a small range adds a small
factor, so neither
+ * is counted. The count is `Int.MaxValue` for a repeated group that holds a
counted quantifier,
+ * and for a `[` that is never closed, which may hide quantifiers.
+ */
+ private def scanQuantifiers(regex: String): (Int, Boolean) = {
+ var count = 0
+ var classDepth = 0
+ var topLevelAlternation = false
+ // Whether each open group holds a counted quantifier, innermost first.
+ var groups = List.empty[Boolean]
+ var i = 0
+ def possessive: Boolean = i + 1 < regex.length && regex.charAt(i + 1) ==
'+'
+ // 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
+ }
+ }
+ def markGroup(): Unit = groups = groups match {
+ case _ :: outer => true :: outer
+ case Nil => Nil
+ }
+ while (i < regex.length) {
+ regex.charAt(i) match {
+ case '\\' if i + 1 < regex.length =>
+ i += 1
+ regex.charAt(i) match {
+ case 'Q' =>
+ val end = regex.indexOf("\\E", i)
+ i = if (end < 0) regex.length else end + 1
+ // `\cX` is a control character, and `X` may be `[`.
+ case 'c' => i += 1
+ case c if "pPxN".indexOf(c) >= 0 &&
+ i + 1 < regex.length && regex.charAt(i + 1) == '{' =>
+ val end = regex.indexOf('}', i)
+ i = if (end < 0) regex.length else end
+ case _ =>
+ }
+ case '[' => classDepth += 1
+ case ']' if classDepth > 0 => classDepth -= 1
Review Comment:
**5. [Low] A `]` right after `[` closes the class too early**
Java reads a `]` that comes right after `[` or `[^` as a literal, so `[]a]`
is one class. L177 closes the class there instead, and the rest of the class is
read as regex syntax. A `(` in it opens a group that never closes. That group
hides a later top-level `|`, so an unanchored pattern looks anchored:
| Pattern | Count | Classed | JDK 25 | JDK 17 |
|---|---|---|---|---|
| `^a\|.*b.*c` | 2 | expensive | 2.9 s | 2.9 s |
| `^[](]a\|.*b.*c` | 2 | cheap | 2.9 s | 2.9 s |
The input is one value of 2000 `b`s. The pattern is contrived, but the fix
is small: skip a `]` that comes right after `[` or `[^`.
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/regexpExpressions.scala:
##########
@@ -84,33 +84,152 @@ 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 {
+ /**
+ * Whether matching `regex` is likely to be expensive. A failed match tries
every combination of
+ * the lengths that its repeating quantifiers take, so each one costs a
factor of the input
+ * length. `find` also tries every start position, which costs one more
factor unless the regex
+ * is anchored at the start. So two quantifiers are expensive, and three
when the regex is
+ * anchored or must match the whole input, as the one a LIKE pattern
becomes. Repeating a group
+ * that holds a quantifier multiplies the factors, so it is always expensive.
+ *
+ * @param matchesWhole whether `regex` must match the whole input rather
than be found in it.
+ */
+ def isExpensiveRegex(regex: String, matchesWhole: Boolean): Boolean = {
+ val (quantifiers, topLevelAlternation) = scanQuantifiers(regex)
+ val anchored = matchesWhole || (!topLevelAlternation &&
startsWithAnchor(regex))
+ quantifiers >= (if (anchored) 3 else 2)
+ }
+
+ // Leading inline flags, e.g. `(?i)` or `(?s-m)`.
+ private val leadingFlags = """(?:\(\?[a-zA-Z]*(?:-[a-zA-Z]*)?\))*""".r
+
+ // Whether `regex` starts with `^` or `\A`. A leading flag that mentions
MULTILINE, under which
+ // `^` also matches after every line terminator, makes it not anchored.
+ private def startsWithAnchor(regex: String): Boolean = {
+ val flags = leadingFlags.findPrefixOf(regex).getOrElse("")
+ val rest = regex.substring(flags.length)
+ !flags.contains('m') && (rest.startsWith("^") || rest.startsWith("\\A"))
+ }
+
+ /**
+ * Counts the repeating quantifiers (`*`, `+` and `{n,m}`) in a regex that
can backtrack, and
+ * tells whether the regex has a `|` outside any group. Escaped characters,
quoted text,
+ * character classes and the braces of `\p{..}`, `\x{..}` and `\N{..}` are
skipped. A possessive
+ * quantifier never backtracks and a `{n,m}` with a small range adds a small
factor, so neither
+ * is counted. The count is `Int.MaxValue` for a repeated group that holds a
counted quantifier,
+ * and for a `[` that is never closed, which may hide quantifiers.
+ */
+ private def scanQuantifiers(regex: String): (Int, Boolean) = {
+ var count = 0
+ var classDepth = 0
+ var topLevelAlternation = false
+ // Whether each open group holds a counted quantifier, innermost first.
+ var groups = List.empty[Boolean]
+ var i = 0
+ def possessive: Boolean = i + 1 < regex.length && regex.charAt(i + 1) ==
'+'
+ // 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
+ }
+ }
+ def markGroup(): Unit = groups = groups match {
+ case _ :: outer => true :: outer
+ case Nil => Nil
+ }
+ while (i < regex.length) {
+ regex.charAt(i) match {
+ case '\\' if i + 1 < regex.length =>
+ i += 1
+ regex.charAt(i) match {
+ case 'Q' =>
+ val end = regex.indexOf("\\E", i)
+ i = if (end < 0) regex.length else end + 1
+ // `\cX` is a control character, and `X` may be `[`.
+ case 'c' => i += 1
+ case c if "pPxN".indexOf(c) >= 0 &&
+ i + 1 < regex.length && regex.charAt(i + 1) == '{' =>
+ val end = regex.indexOf('}', i)
+ i = if (end < 0) regex.length else end
+ case _ =>
+ }
+ case '[' => classDepth += 1
+ case ']' if classDepth > 0 => classDepth -= 1
+ case _ if classDepth > 0 =>
+ case '(' => groups = false :: groups
Review Comment:
**6. [Low] Quantifiers in different lookarounds or atomic groups are added
up, though they do not multiply**
Java never backtracks into a lookaround or an atomic group once it has
matched. So the quantifiers in two such groups do not multiply each other the
way the two in `.*a.*b` do. The scanner adds them up anyway, and a common
password check is classed expensive:
| Pattern | Count | Classed | JDK 25 | JDK 17 |
|---|---|---|---|---|
| `^(?=.*[A-Z])(?=.*\d).{8,}$` | 3 | expensive | 0 ms | 0 ms |
| `(?>.*a)(?>.*b)` | 2 | expensive | 9 ms | 9 ms |
| `.*a.*b` | 2 | expensive | 3.1 s | 3.0 s |
The input is one value of 2000 `a`s. Quantifiers inside one such group still
multiply each other. So each `(?=`, `(?!` and `(?>` group could be counted on
its own, and the pattern classed by the largest count, with the quantifiers
outside these groups as one more count. If that is more than this heuristic
needs, I'm fine with leaving it.
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/regexpExpressions.scala:
##########
@@ -84,33 +84,152 @@ 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 {
+ /**
+ * Whether matching `regex` is likely to be expensive. A failed match tries
every combination of
+ * the lengths that its repeating quantifiers take, so each one costs a
factor of the input
+ * length. `find` also tries every start position, which costs one more
factor unless the regex
+ * is anchored at the start. So two quantifiers are expensive, and three
when the regex is
+ * anchored or must match the whole input, as the one a LIKE pattern
becomes. Repeating a group
+ * that holds a quantifier multiplies the factors, so it is always expensive.
+ *
+ * @param matchesWhole whether `regex` must match the whole input rather
than be found in it.
+ */
+ def isExpensiveRegex(regex: String, matchesWhole: Boolean): Boolean = {
+ val (quantifiers, topLevelAlternation) = scanQuantifiers(regex)
+ val anchored = matchesWhole || (!topLevelAlternation &&
startsWithAnchor(regex))
+ quantifiers >= (if (anchored) 3 else 2)
+ }
+
+ // Leading inline flags, e.g. `(?i)` or `(?s-m)`.
+ private val leadingFlags = """(?:\(\?[a-zA-Z]*(?:-[a-zA-Z]*)?\))*""".r
+
+ // Whether `regex` starts with `^` or `\A`. A leading flag that mentions
MULTILINE, under which
+ // `^` also matches after every line terminator, makes it not anchored.
+ private def startsWithAnchor(regex: String): Boolean = {
+ val flags = leadingFlags.findPrefixOf(regex).getOrElse("")
+ val rest = regex.substring(flags.length)
+ !flags.contains('m') && (rest.startsWith("^") || rest.startsWith("\\A"))
+ }
+
+ /**
+ * Counts the repeating quantifiers (`*`, `+` and `{n,m}`) in a regex that
can backtrack, and
+ * tells whether the regex has a `|` outside any group. Escaped characters,
quoted text,
+ * character classes and the braces of `\p{..}`, `\x{..}` and `\N{..}` are
skipped. A possessive
+ * quantifier never backtracks and a `{n,m}` with a small range adds a small
factor, so neither
+ * is counted. The count is `Int.MaxValue` for a repeated group that holds a
counted quantifier,
+ * and for a `[` that is never closed, which may hide quantifiers.
+ */
+ private def scanQuantifiers(regex: String): (Int, Boolean) = {
+ var count = 0
+ var classDepth = 0
+ var topLevelAlternation = false
+ // Whether each open group holds a counted quantifier, innermost first.
+ var groups = List.empty[Boolean]
+ var i = 0
+ def possessive: Boolean = i + 1 < regex.length && regex.charAt(i + 1) ==
'+'
+ // 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
+ }
+ }
+ def markGroup(): Unit = groups = groups match {
+ case _ :: outer => true :: outer
+ case Nil => Nil
+ }
+ while (i < regex.length) {
+ regex.charAt(i) match {
+ case '\\' if i + 1 < regex.length =>
+ i += 1
+ regex.charAt(i) match {
+ case 'Q' =>
+ val end = regex.indexOf("\\E", i)
+ i = if (end < 0) regex.length else end + 1
+ // `\cX` is a control character, and `X` may be `[`.
+ case 'c' => i += 1
+ case c if "pPxN".indexOf(c) >= 0 &&
+ i + 1 < regex.length && regex.charAt(i + 1) == '{' =>
+ val end = regex.indexOf('}', i)
+ i = if (end < 0) regex.length else end
+ case _ =>
+ }
+ case '[' => classDepth += 1
+ case ']' if classDepth > 0 => classDepth -= 1
+ case _ if classDepth > 0 =>
+ case '(' => groups = false :: groups
+ case ')' if groups.nonEmpty =>
+ val holdsQuantifier = groups.head
+ groups = groups.tail
+ if (holdsQuantifier) {
+ if (repeats(regex, i + 1)) return (Int.MaxValue,
topLevelAlternation)
+ markGroup()
+ }
+ case '|' if groups.isEmpty => topLevelAlternation = true
+ case '*' | '+' =>
+ if (!possessive) {
+ count += 1
+ markGroup()
+ }
+ skipModifier()
+ case '?' => skipModifier()
+ case '{' =>
+ bounds(regex, i).foreach { case (end, min, max) =>
+ i = end
+ if (!possessive && max - min >= 10) {
+ count += 1
+ markGroup()
+ }
+ skipModifier()
+ }
+ case _ =>
+ }
+ i += 1
+ }
+ (if (classDepth > 0) Int.MaxValue else count, topLevelAlternation)
+ }
+
+ // Whether a quantifier that can repeat its operand more than once starts at
`i`.
+ private def repeats(regex: String, i: Int): Boolean = i < regex.length && {
+ regex.charAt(i) match {
+ case '*' | '+' => true
+ case '{' => bounds(regex, i).exists(_._3 >= 2)
+ case _ => false
+ }
+ }
+
+ private val repetition = """\{(\d+)(?:,(\d*))?\}""".r
+
+ // Parses the `{n}`, `{n,}` or `{n,m}` at `start` into its closing index and
its bounds, with
+ // `Int.MaxValue` as the upper bound of `{n,}`.
+ private def bounds(regex: String, start: Int): Option[(Int, Int, Int)] = {
+ repetition.findPrefixMatchOf(regex.substring(start)).map { m =>
Review Comment:
**7. [Low] `bounds` copies the rest of the pattern for every `{`**
`regex.substring(start)` copies everything after the `{`, and `repeats`
makes one more copy after a `)`. So the scan is quadratic in the pattern
length, and it runs inside the optimizer. In a port of the scanner, a pattern
of `\d{3}-` repeated 50,000 times (300 KB) took 266 ms on JDK 25 and 313 ms on
JDK 17. Repeated 100,000 times (600 KB), it took 700 ms and 760 ms. Generated
patterns that large are unusual but possible. Matching in place avoids the copy:
```scala
private def bounds(regex: String, start: Int): Option[(Int, Int, Int)] = {
val m = repetition.pattern.matcher(regex).region(start, regex.length)
Option.when(m.lookingAt()) {
def toInt(s: String): Int = s.toIntOption.getOrElse(Int.MaxValue)
val min = toInt(m.group(1))
val max = Option(m.group(2)).map(s => if (s.isEmpty) Int.MaxValue else
toInt(s))
(m.end - 1, min, max.getOrElse(min))
}
}
```
--
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]
