dongjoon-hyun commented on code in PR #59879:
URL: https://github.com/apache/spark/pull/59879#discussion_r4424294972
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/regexpExpressions.scala:
##########
@@ -84,33 +84,212 @@ 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 or an alternation 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"))
+ }
+
+ // An inline flag, e.g. `(?x)` or `(?ix:`, that turns on COMMENTS mode,
which lets whitespace
+ // and comments separate a group from its quantifier.
+ private val commentsFlag = Pattern.compile("""\(\?[a-zA-Z]*x""")
+
+ // The product of the choices of the uncounted ranges that makes them count
as one quantifier.
+ private val smallRangesLimit = 100
+
+ /**
+ * 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. The
+ * alternatives of a `|` outside any group are tried one after another, so
each is counted on its
+ * own and the largest count is returned. These quantifiers are not counted:
+ * - a possessive one, which never backtracks;
+ * - one that ends the regex or an alternative of it, possibly inside
groups that end there too,
+ * which a failed match never backtracks into;
+ * - `?` and a `{n,m}` that spans fewer than 10, which add a small factor.
The choices of such
+ * quantifiers multiply, so they count as one quantifier each time their
product reaches 100.
+ * The count is `Int.MaxValue` for a repeated group that holds a quantifier
that can backtrack or
+ * a `|`, for a regex in COMMENTS mode, and for a `[` that is never closed,
since the scan cannot
+ * follow them.
+ *
+ * A streaming query pins `SQLConf.REGEX_PATTERN_COST_ESTIMATE_VERSION` in
its checkpoint, since
+ * a pattern that turns cheap can move a filter below a stateful operator.
So a change that makes
+ * any pattern cheaper needs a new version of the estimate, and the old one
has to be kept.
+ */
+ private def scanQuantifiers(regex: String): (Int, Boolean) = {
+ // The largest count of the alternatives before the current one.
+ var maxCount = 0
+ var count = 0
+ var smallRanges = 1
+ var classDepth = 0
+ var topLevelAlternation = false
+ // Whether each open group holds a choice that a repetition of it would
multiply, innermost
+ // first.
+ var groups = List.empty[Boolean]
+ var i = 0
+ def markGroup(): Unit = groups = groups match {
+ case _ :: outer => true :: outer
+ case Nil => Nil
+ }
+ // Whether nothing but the closing `)` of open groups comes between `j`
and the end of the
+ // regex or a `|` outside any group.
+ def endsAlternative(j: Int): Boolean = {
+ var end = j
+ var depth = groups.length
+ while (end < regex.length && depth > 0 && regex.charAt(end) == ')') {
+ end += 1
+ depth -= 1
+ }
+ end == regex.length || (depth == 0 && regex.charAt(end) == '|')
+ }
+ // Handles the quantifier that ends at `i`, which repeats its operand
`min` to `max` times,
+ // and moves `i` past its modifier.
+ def quantifier(min: Int, max: Int): Unit = {
+ val possessive = i + 1 < regex.length && regex.charAt(i + 1) == '+'
+ if (i + 1 < regex.length && (regex.charAt(i + 1) == '+' ||
regex.charAt(i + 1) == '?')) {
+ i += 1
+ }
+ if (!possessive && max > min && !endsAlternative(i + 1)) {
+ markGroup()
+ if (max - min >= 10) {
+ count += 1
+ } else {
+ smallRanges *= max - min + 1
+ if (smallRanges >= smallRangesLimit) {
+ count += 1
+ smallRanges = 1
+ }
+ }
+ }
+ }
+ 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
+ // A `]` right after `[` or `[^` is a literal.
+ if (i + 1 < regex.length && regex.charAt(i + 1) == '^') i += 1
+ if (i + 1 < regex.length && regex.charAt(i + 1) == ']') i += 1
+ case ']' if classDepth > 0 => classDepth -= 1
+ case _ if classDepth > 0 =>
+ case '(' =>
+ if (regex.startsWith("(?", i)) {
+ if (matcherAt(commentsFlag, regex, i).lookingAt()) {
+ return (Int.MaxValue, topLevelAlternation)
+ }
+ // The `?` of `(?:`, `(?=`, `(?<name>` or `(?i)` is not a
quantifier.
+ i += 1
+ }
+ groups = false :: groups
+ case ')' if groups.nonEmpty =>
+ val holdsChoice = groups.head
+ groups = groups.tail
+ if (holdsChoice) {
+ if (repeats(regex, i + 1)) return (Int.MaxValue,
topLevelAlternation)
+ markGroup()
+ }
+ case '|' if groups.isEmpty =>
+ topLevelAlternation = true
+ maxCount = math.max(maxCount, count)
+ count = 0
+ smallRanges = 1
+ case '|' => markGroup()
Review Comment:
**1. [Low] Alternations outside a repeated group are not in the choice
product**
Thanks for taking `?` through `quantifier(0, 1)`. A `|` adds the same kind
of choice, but it only marks its group, so a sequence of groups with
overlapping alternatives multiplies without being counted. These patterns count
0 and are classed cheap, while `a?` 24 times, which costs about the same, is
classed expensive:
| Pattern | Count | Input (no match) | JDK 25 | JDK 17 |
|---|---|---|---|---|
| `a?` 24 times, then `b` | 3 | 30 `a`s | 1.81 s | 2.04 s |
| `(a\|a)` 24 times, then `b` | 0 | 30 `a`s | 2.22 s | 2.20 s |
| `(a\|)` 24 times, then `b` | 0 | 30 `a`s | 5.18 s | 5.25 s |
| `(\w\|\d)` 24 times, then `x` | 0 | 30 `1`s | 2.25 s | 2.69 s |
| `(?:a\|aa)` 24 times, then `b` | 0 | 60 `a`s | 9.36 s | 9.86 s |
Could a group's first `|` feed the same product? It would need the product
step of `quantifier` as a helper:
```scala
// Adds a choice among `n` to the product, which counts as one
quantifier when it gets large.
def addChoices(n: Int): Unit = {
smallRanges *= n
if (smallRanges >= smallRangesLimit) {
count += 1
smallRanges = 1
}
}
...
case '|' =>
// A group adds one factor, however many alternatives it has.
if (!groups.head) addChoices(2)
markGroup()
```
All five patterns above then count 3. Because a group adds only one factor,
`.*(k1|k2|k3|k4|k5|k6|k7|k8).*` still counts 1 and stays cheap. I checked this
on a Java port of the scanner, and every constant pattern in your new test
keeps its answer.
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/regexpExpressions.scala:
##########
@@ -84,33 +84,212 @@ 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 or an alternation 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"))
+ }
+
+ // An inline flag, e.g. `(?x)` or `(?ix:`, that turns on COMMENTS mode,
which lets whitespace
+ // and comments separate a group from its quantifier.
+ private val commentsFlag = Pattern.compile("""\(\?[a-zA-Z]*x""")
+
+ // The product of the choices of the uncounted ranges that makes them count
as one quantifier.
+ private val smallRangesLimit = 100
+
+ /**
+ * 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. The
+ * alternatives of a `|` outside any group are tried one after another, so
each is counted on its
+ * own and the largest count is returned. These quantifiers are not counted:
+ * - a possessive one, which never backtracks;
+ * - one that ends the regex or an alternative of it, possibly inside
groups that end there too,
+ * which a failed match never backtracks into;
+ * - `?` and a `{n,m}` that spans fewer than 10, which add a small factor.
The choices of such
+ * quantifiers multiply, so they count as one quantifier each time their
product reaches 100.
+ * The count is `Int.MaxValue` for a repeated group that holds a quantifier
that can backtrack or
+ * a `|`, for a regex in COMMENTS mode, and for a `[` that is never closed,
since the scan cannot
+ * follow them.
+ *
+ * A streaming query pins `SQLConf.REGEX_PATTERN_COST_ESTIMATE_VERSION` in
its checkpoint, since
+ * a pattern that turns cheap can move a filter below a stateful operator.
So a change that makes
+ * any pattern cheaper needs a new version of the estimate, and the old one
has to be kept.
+ */
+ private def scanQuantifiers(regex: String): (Int, Boolean) = {
+ // The largest count of the alternatives before the current one.
+ var maxCount = 0
+ var count = 0
+ var smallRanges = 1
+ var classDepth = 0
+ var topLevelAlternation = false
+ // Whether each open group holds a choice that a repetition of it would
multiply, innermost
+ // first.
+ var groups = List.empty[Boolean]
+ var i = 0
+ def markGroup(): Unit = groups = groups match {
+ case _ :: outer => true :: outer
+ case Nil => Nil
+ }
+ // Whether nothing but the closing `)` of open groups comes between `j`
and the end of the
+ // regex or a `|` outside any group.
+ def endsAlternative(j: Int): Boolean = {
+ var end = j
+ var depth = groups.length
+ while (end < regex.length && depth > 0 && regex.charAt(end) == ')') {
+ end += 1
+ depth -= 1
+ }
+ end == regex.length || (depth == 0 && regex.charAt(end) == '|')
+ }
+ // Handles the quantifier that ends at `i`, which repeats its operand
`min` to `max` times,
+ // and moves `i` past its modifier.
+ def quantifier(min: Int, max: Int): Unit = {
+ val possessive = i + 1 < regex.length && regex.charAt(i + 1) == '+'
+ if (i + 1 < regex.length && (regex.charAt(i + 1) == '+' ||
regex.charAt(i + 1) == '?')) {
+ i += 1
+ }
+ if (!possessive && max > min && !endsAlternative(i + 1)) {
+ markGroup()
+ if (max - min >= 10) {
+ count += 1
+ } else {
+ smallRanges *= max - min + 1
+ if (smallRanges >= smallRangesLimit) {
+ count += 1
+ smallRanges = 1
+ }
+ }
+ }
+ }
+ 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
+ // A `]` right after `[` or `[^` is a literal.
+ if (i + 1 < regex.length && regex.charAt(i + 1) == '^') i += 1
+ if (i + 1 < regex.length && regex.charAt(i + 1) == ']') i += 1
+ case ']' if classDepth > 0 => classDepth -= 1
+ case _ if classDepth > 0 =>
+ case '(' =>
+ if (regex.startsWith("(?", i)) {
+ if (matcherAt(commentsFlag, regex, i).lookingAt()) {
+ return (Int.MaxValue, topLevelAlternation)
+ }
+ // The `?` of `(?:`, `(?=`, `(?<name>` or `(?i)` is not a
quantifier.
+ i += 1
+ }
+ groups = false :: groups
+ case ')' if groups.nonEmpty =>
+ val holdsChoice = groups.head
+ groups = groups.tail
+ if (holdsChoice) {
+ if (repeats(regex, i + 1)) return (Int.MaxValue,
topLevelAlternation)
+ markGroup()
+ }
+ case '|' if groups.isEmpty =>
+ topLevelAlternation = true
+ maxCount = math.max(maxCount, count)
+ count = 0
+ smallRanges = 1
+ case '|' => markGroup()
+ case '*' => quantifier(0, Int.MaxValue)
+ case '+' => quantifier(1, Int.MaxValue)
+ case '?' => quantifier(0, 1)
+ case '{' =>
+ bounds(regex, i).foreach { case (end, min, max) =>
+ i = end
+ quantifier(min, max)
+ }
+ case _ =>
+ }
+ i += 1
+ }
+ (if (classDepth > 0) Int.MaxValue else math.max(maxCount, 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. [Low] An empty `\Q\E` hides a repeated group**
`repeats` looks only at the character right after the `)`. But `Pattern`
removes the quoting before it parses the regex, so an empty quote between a
group and its quantifier leaves a repeated group. `Pattern.quote("")` returns
exactly `\Q\E`, so a pattern built from parts can contain one, although it is
unusual.
| Pattern | Count | Classed | Input (no match) | JDK 25 | JDK 17 |
|---|---|---|---|---|---|
| `^(.*?,){11}P` | MAX | expensive | 40 `,`s, then 42 `x`s | over 20 s |
over 20 s |
| `^(.*?,)\Q\E{11}P` | 1 | cheap | 40 `,`s, then 42 `x`s | over 20 s | over
20 s |
Whitespace under `(?x)` was the other way to separate a group from its
quantifier, and that one is already MAX. Skipping the empty quote closes this
one:
```scala
case '{' => bounds(regex, i).exists(_._3 >= 2)
// `Pattern` removes an empty quote before it parses the regex.
case '\\' if regex.startsWith("\\Q\\E", i) => repeats(regex, i + 4)
```
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/regexpExpressions.scala:
##########
@@ -84,33 +84,212 @@ 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 or an alternation 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))
Review Comment:
**6. [Low] Some cheap alternations are still classed expensive**
Thanks for counting the top-level alternatives on their own. Two close
relatives of those patterns stay expensive: one wrapped in a group, where the
`|` is no longer at the top level, and one whose alternatives are all anchored,
where any top-level `|` turns the threshold of 3 off:
| Pattern | Count | Classed | Input (no match) | JDK 25 | JDK 17 |
|---|---|---|---|---|---|
| `a.*b\|c.*d` | 1 | cheap | 2000 `a`s | 19 ms | 7.5 ms |
| `(a.*b\|c.*d)` | 2 | expensive | 2000 `a`s | 20 ms | 7.5 ms |
| `^a.*a.*b` | 2 | cheap | 2000 `a`s | 19 ms | 7.5 ms |
| `^a.*a.*b\|^c.*c.*d` | 2 | expensive | 2000 `a`s | 19 ms | 7.5 ms |
A filter on such an alias gets no pushdown or pruning. This errs on the safe
side, like round-3 items 6 and 8, so I'm fine if you keep it. What makes it
worth deciding now is your new scaladoc: once this ships, a change that makes
these patterns cheaper needs a new estimate version, and the old scanner has to
stay. So could you either handle them before the first release, or say in the
PR description that they stay expensive on purpose?
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/regexpExpressions.scala:
##########
@@ -84,33 +84,212 @@ 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 or an alternation 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 = {
Review Comment:
**3. [Low] A quantified anchor counts as an anchor**
`Pattern` accepts a quantifier on `^` and `\A`, and `^?` or `\A?` does not
pin the match to the start of the input. `startsWithAnchor` does not look at
what follows the anchor, so these patterns get the threshold of 3, although
they cost the same as `.*a.*b`:
| Pattern | Count | Classed | Input (no match) | JDK 25 | JDK 17 |
|---|---|---|---|---|---|
| `.*a.*b` | 2 | expensive | 2000 `a`s | 4.95 s | 3.75 s |
| `^?.*a.*b` | 2 | cheap | 2000 `a`s | 4.87 s | 3.67 s |
| `\A?.*a.*b` | 2 | cheap | 2000 `a`s | 4.88 s | 3.66 s |
| `^{0,1}.*a.*b` | 2 | cheap | 2000 `a`s | 4.89 s | 3.75 s |
Nobody is likely to write these by hand, and the fix is small. A lookahead
could replace the two `startsWith` calls:
```scala
// `^` or `\A`, unless a quantifier may make it optional.
private val leadingAnchor = """(?:\^|\\A)(?![?*{])""".r
...
!flags.contains('m') && leadingAnchor.findPrefixOf(rest).isDefined
```
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/Optimizer.scala:
##########
@@ -2897,11 +2897,11 @@ object PushPredicateThroughNonJoin extends
Rule[LogicalPlan] with PredicateHelpe
expensiveConds: Seq[(Expression, AttributeMap[Alias])])
: (LogicalPlan, AttributeSet, Seq[Expression]) = {
val expensiveAliases = AttributeSet(
- aliasMap.collect { case (attr, alias) if alias.child.expensive => attr })
+ aliasMap.collect { case (attr, alias) if isExpensive(alias.child) =>
attr })
// Expensive sub-expressions behind each expensive alias, to spot when two
aliases are the
// same piece of work. Cheap aliases have none, so we skip the (possibly
wide) cheap rest.
val expensivePartsOf = AttributeMap(expensiveAliases.toSeq.map { attr =>
- attr -> aliasMap(attr).child.collect { case e if e.expensive =>
e.canonicalized }.toSet
+ attr -> aliasMap(attr).child.collect { case e if isExpensive(e) =>
e.canonicalized }.toSet
Review Comment:
**9. [Nit] Version 0 walks the alias tree once per node**
`collect` calls `isExpensive` on every node of the alias, and at version 0
each call runs `e.exists` over that node's subtree and reads the conf again. So
the work is quadratic in the size of the alias, for example a `CASE WHEN` with
many branches, and it repeats for each batch of a query resumed from an old
checkpoint. Version 1 does not reach `exists`, so this only affects those
queries.
Two aliases share work exactly when they share a regex, so the regex nodes
are enough here, without their ancestors:
```scala
val regexIsExpensive =
conf.getConf(SQLConf.REGEX_PATTERN_COST_ESTIMATE_VERSION) == 0
...
attr -> aliasMap(attr).child.collect {
case e if e.expensive || (regexIsExpensive &&
e.isInstanceOf[StringRegexExpression]) =>
e.canonicalized
}.toSet
```
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/regexpExpressions.scala:
##########
@@ -84,33 +84,212 @@ 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 or an alternation 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"))
+ }
+
+ // An inline flag, e.g. `(?x)` or `(?ix:`, that turns on COMMENTS mode,
which lets whitespace
+ // and comments separate a group from its quantifier.
+ private val commentsFlag = Pattern.compile("""\(\?[a-zA-Z]*x""")
+
+ // The product of the choices of the uncounted ranges that makes them count
as one quantifier.
+ private val smallRangesLimit = 100
+
+ /**
+ * 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. The
+ * alternatives of a `|` outside any group are tried one after another, so
each is counted on its
+ * own and the largest count is returned. These quantifiers are not counted:
+ * - a possessive one, which never backtracks;
+ * - one that ends the regex or an alternative of it, possibly inside
groups that end there too,
+ * which a failed match never backtracks into;
+ * - `?` and a `{n,m}` that spans fewer than 10, which add a small factor.
The choices of such
+ * quantifiers multiply, so they count as one quantifier each time their
product reaches 100.
+ * The count is `Int.MaxValue` for a repeated group that holds a quantifier
that can backtrack or
+ * a `|`, for a regex in COMMENTS mode, and for a `[` that is never closed,
since the scan cannot
+ * follow them.
+ *
+ * A streaming query pins `SQLConf.REGEX_PATTERN_COST_ESTIMATE_VERSION` in
its checkpoint, since
+ * a pattern that turns cheap can move a filter below a stateful operator.
So a change that makes
+ * any pattern cheaper needs a new version of the estimate, and the old one
has to be kept.
+ */
+ private def scanQuantifiers(regex: String): (Int, Boolean) = {
+ // The largest count of the alternatives before the current one.
+ var maxCount = 0
+ var count = 0
+ var smallRanges = 1
+ var classDepth = 0
+ var topLevelAlternation = false
+ // Whether each open group holds a choice that a repetition of it would
multiply, innermost
+ // first.
+ var groups = List.empty[Boolean]
+ var i = 0
+ def markGroup(): Unit = groups = groups match {
+ case _ :: outer => true :: outer
+ case Nil => Nil
+ }
+ // Whether nothing but the closing `)` of open groups comes between `j`
and the end of the
+ // regex or a `|` outside any group.
+ def endsAlternative(j: Int): Boolean = {
+ var end = j
+ var depth = groups.length
+ while (end < regex.length && depth > 0 && regex.charAt(end) == ')') {
+ end += 1
+ depth -= 1
+ }
+ end == regex.length || (depth == 0 && regex.charAt(end) == '|')
+ }
+ // Handles the quantifier that ends at `i`, which repeats its operand
`min` to `max` times,
+ // and moves `i` past its modifier.
+ def quantifier(min: Int, max: Int): Unit = {
+ val possessive = i + 1 < regex.length && regex.charAt(i + 1) == '+'
+ if (i + 1 < regex.length && (regex.charAt(i + 1) == '+' ||
regex.charAt(i + 1) == '?')) {
+ i += 1
+ }
+ if (!possessive && max > min && !endsAlternative(i + 1)) {
Review Comment:
**5. [Low] A large fixed repetition adds a factor, but is not counted**
`max > min` leaves out every fixed `{n}`. It cannot backtrack, but with a
large `n` it adds up to `n` steps to each attempt, and those attempts multiply
with the rest of the pattern. Next to a `.*` it weighs about as much as a
second quantifier:
| Pattern | Count | Classed | Input (no match) | JDK 25 | JDK 17 |
|---|---|---|---|---|---|
| `.{1000}x` | 0 | cheap | 2000 `a`s | 2.9 ms | 2.4 ms |
| `.*a.*b` | 2 | expensive | 2000 `a`s | 4.95 s | 3.75 s |
| `.*.{1000}x` | 1 | cheap | 2000 `a`s | 2.93 s | 2.47 s |
| `.*.{2000}x` | 1 | cheap | 4000 `a`s | over 20 s | 19.7 s |
Counting a fixed repetition of 100 or more as one quantifier would cover
these, and it leaves common ones such as `\d{4}-\d{2}-\d{2}` alone:
```scala
if (!possessive && !endsAlternative(i + 1)) {
if (max > min) {
...
} else if (min >= 100) {
// A long fixed repetition adds its length to every attempt.
count += 1
}
}
```
`.*.{1000}x` then counts 2, and `.{1000}x` counts 1 and stays cheap. Every
constant pattern in your new test keeps its answer.
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/regexpExpressions.scala:
##########
@@ -84,33 +84,212 @@ 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 or an alternation 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"))
+ }
+
+ // An inline flag, e.g. `(?x)` or `(?ix:`, that turns on COMMENTS mode,
which lets whitespace
+ // and comments separate a group from its quantifier.
+ private val commentsFlag = Pattern.compile("""\(\?[a-zA-Z]*x""")
+
+ // The product of the choices of the uncounted ranges that makes them count
as one quantifier.
+ private val smallRangesLimit = 100
+
+ /**
+ * 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. The
+ * alternatives of a `|` outside any group are tried one after another, so
each is counted on its
+ * own and the largest count is returned. These quantifiers are not counted:
+ * - a possessive one, which never backtracks;
+ * - one that ends the regex or an alternative of it, possibly inside
groups that end there too,
+ * which a failed match never backtracks into;
+ * - `?` and a `{n,m}` that spans fewer than 10, which add a small factor.
The choices of such
+ * quantifiers multiply, so they count as one quantifier each time their
product reaches 100.
+ * The count is `Int.MaxValue` for a repeated group that holds a quantifier
that can backtrack or
+ * a `|`, for a regex in COMMENTS mode, and for a `[` that is never closed,
since the scan cannot
+ * follow them.
+ *
+ * A streaming query pins `SQLConf.REGEX_PATTERN_COST_ESTIMATE_VERSION` in
its checkpoint, since
+ * a pattern that turns cheap can move a filter below a stateful operator.
So a change that makes
+ * any pattern cheaper needs a new version of the estimate, and the old one
has to be kept.
+ */
+ private def scanQuantifiers(regex: String): (Int, Boolean) = {
+ // The largest count of the alternatives before the current one.
+ var maxCount = 0
+ var count = 0
+ var smallRanges = 1
+ var classDepth = 0
+ var topLevelAlternation = false
+ // Whether each open group holds a choice that a repetition of it would
multiply, innermost
+ // first.
+ var groups = List.empty[Boolean]
+ var i = 0
+ def markGroup(): Unit = groups = groups match {
+ case _ :: outer => true :: outer
+ case Nil => Nil
+ }
+ // Whether nothing but the closing `)` of open groups comes between `j`
and the end of the
+ // regex or a `|` outside any group.
+ def endsAlternative(j: Int): Boolean = {
+ var end = j
+ var depth = groups.length
+ while (end < regex.length && depth > 0 && regex.charAt(end) == ')') {
+ end += 1
+ depth -= 1
+ }
+ end == regex.length || (depth == 0 && regex.charAt(end) == '|')
+ }
+ // Handles the quantifier that ends at `i`, which repeats its operand
`min` to `max` times,
+ // and moves `i` past its modifier.
+ def quantifier(min: Int, max: Int): Unit = {
+ val possessive = i + 1 < regex.length && regex.charAt(i + 1) == '+'
+ if (i + 1 < regex.length && (regex.charAt(i + 1) == '+' ||
regex.charAt(i + 1) == '?')) {
+ i += 1
+ }
+ if (!possessive && max > min && !endsAlternative(i + 1)) {
+ markGroup()
+ if (max - min >= 10) {
+ count += 1
+ } else {
+ smallRanges *= max - min + 1
+ if (smallRanges >= smallRangesLimit) {
+ count += 1
+ smallRanges = 1
+ }
+ }
+ }
+ }
+ 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 _ =>
Review Comment:
**4. [Low] A backreference adds a factor, but is not counted**
A backreference compares as many characters as its group holds, so it costs
a factor of the input length, like a quantifier. The scanner passes over `\1`
and `\k` as plain escapes. `(.*)\1x` counts 1, the same as `a.*b`, but it grows
much faster:
| Pattern | Count | Input (no match) | JDK 25 | JDK 17 |
|---|---|---|---|---|
| `a.*b` | 1 | 2000 `a`s | 7 ms | 7 ms |
| `(.*)\1x` | 1 | 400 `a`s | 5.3 ms | 15 ms |
| `(.*)\1x` | 1 | 2000 `a`s | 458 ms | 270 ms |
| `(.*)\1x` | 1 | 4000 `a`s | 3.62 s | 2.09 s |
| `(.+)\1\1x` | 1 | 2000 `a`s | 666 ms | 458 ms |
Could a backreference count as one quantifier?
```scala
// A backreference compares as many characters as its group
holds.
case c if (c >= '1' && c <= '9') || c == 'k' => count += 1
```
`(.*)\1x` then counts 2 and `(.+)\1\1x` counts 3, and every constant pattern
in your new test keeps its answer. `^(.+)\1+$`, which takes 2 ms on 2000 `a`s
and a `b`, would also count 3 and turn expensive, which errs on the safe side.
##########
sql/core/src/test/scala/org/apache/spark/sql/streaming/StreamingQueryManagerSuite.scala:
##########
@@ -168,6 +169,36 @@ class StreamingQueryManagerSuite extends StreamTest {
}
}
+ test("SPARK-60632: regex pattern cost estimate version 0 for old
checkpoints") {
+ withTempDir { checkpointDir =>
+ val input = MemoryStream[String]
+ // `NOT` caches whether its child is expensive, and both queries share
this plan.
+ val result = input.toDF().select($"value", !$"value".rlike("^1") as
"p").where($"p")
+
+ def run(data: String): Boolean = {
+ val query = result.writeStream
+ .format("noop")
+ .option("checkpointLocation", checkpointDir.getCanonicalPath)
+ .start()
+ try {
+ input.addData(data)
+ query.processAllAvailable()
+ // Whether the filter stays above the projection.
+
query.asInstanceOf[StreamingQueryWrapper].streamingQuery.lastExecution.optimizedPlan
+ .exists {
+ case Filter(_, _: Project) => true
+ case _ => false
+ }
+ } finally {
+ query.stop()
+ }
+ }
+
+ assert(!run("a"))
+ rewriteOffsetLogConf(checkpointDir)(_ -
SQLConf.REGEX_PATTERN_COST_ESTIMATE_VERSION.key)
+ assert(run("b"))
+ }
+ }
Review Comment:
**12. [Nit] A blank line is missing after the new test**
The next test starts on the line right after this `}`, while the other tests
in this file are separated by a blank line.
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/regexpExpressions.scala:
##########
@@ -84,33 +84,212 @@ 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 or an alternation 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"))
+ }
+
+ // An inline flag, e.g. `(?x)` or `(?ix:`, that turns on COMMENTS mode,
which lets whitespace
+ // and comments separate a group from its quantifier.
+ private val commentsFlag = Pattern.compile("""\(\?[a-zA-Z]*x""")
+
+ // The product of the choices of the uncounted ranges that makes them count
as one quantifier.
+ private val smallRangesLimit = 100
+
+ /**
+ * 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. The
+ * alternatives of a `|` outside any group are tried one after another, so
each is counted on its
+ * own and the largest count is returned. These quantifiers are not counted:
+ * - a possessive one, which never backtracks;
+ * - one that ends the regex or an alternative of it, possibly inside
groups that end there too,
+ * which a failed match never backtracks into;
+ * - `?` and a `{n,m}` that spans fewer than 10, which add a small factor.
The choices of such
+ * quantifiers multiply, so they count as one quantifier each time their
product reaches 100.
+ * The count is `Int.MaxValue` for a repeated group that holds a quantifier
that can backtrack or
+ * a `|`, for a regex in COMMENTS mode, and for a `[` that is never closed,
since the scan cannot
+ * follow them.
+ *
+ * A streaming query pins `SQLConf.REGEX_PATTERN_COST_ESTIMATE_VERSION` in
its checkpoint, since
+ * a pattern that turns cheap can move a filter below a stateful operator.
So a change that makes
+ * any pattern cheaper needs a new version of the estimate, and the old one
has to be kept.
+ */
+ private def scanQuantifiers(regex: String): (Int, Boolean) = {
+ // The largest count of the alternatives before the current one.
+ var maxCount = 0
+ var count = 0
+ var smallRanges = 1
+ var classDepth = 0
+ var topLevelAlternation = false
+ // Whether each open group holds a choice that a repetition of it would
multiply, innermost
+ // first.
+ var groups = List.empty[Boolean]
+ var i = 0
+ def markGroup(): Unit = groups = groups match {
+ case _ :: outer => true :: outer
+ case Nil => Nil
+ }
+ // Whether nothing but the closing `)` of open groups comes between `j`
and the end of the
+ // regex or a `|` outside any group.
+ def endsAlternative(j: Int): Boolean = {
+ var end = j
+ var depth = groups.length
Review Comment:
**10. [Nit] `endsAlternative` computes `groups.length` for each quantifier**
`groups` is a `List`, so `length` walks all the open groups, and this runs
for every quantifier. Only a very large pattern with deep nesting would notice,
but walking the list needs no length at all and is no longer:
```scala
def endsAlternative(j: Int): Boolean = {
var end = j
var open = groups
while (end < regex.length && open.nonEmpty && regex.charAt(end) ==
')') {
end += 1
open = open.tail
}
end == regex.length || (open.isEmpty && regex.charAt(end) == '|')
}
```
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/internal/SQLConf.scala:
##########
@@ -670,6 +670,20 @@ object SQLConf {
.booleanConf
.createWithDefault(true)
+ val REGEX_PATTERN_COST_ESTIMATE_VERSION =
+ buildConf("spark.sql.optimizer.regexPatternCostEstimateVersion")
+ .internal()
+ .withBindingPolicy(ConfigBindingPolicy.NOT_APPLICABLE)
+ .doc(s"How ${AVOID_DOUBLE_FILTER_EVAL.key} decides whether a LIKE or RLIKE
expression is " +
+ "expensive. 0: every LIKE and RLIKE expression is expensive, as in 4.2.0
for a subject " +
+ "that is not a literal. 1: only one whose pattern is likely to be
expensive to match. A " +
+ "streaming query keeps the version recorded in its checkpoint, and one
restarted from a " +
+ "checkpoint without it uses 0.")
+ .version("4.2.2")
+ .intConf
+ .checkValues(Set(0, 1))
Review Comment:
**7. [Nit] `checkValues` rejects a later version in a checkpoint**
The scaladoc of `scanQuantifiers` plans for new versions. Suppose a later
release records `2`. If the user then goes back to a release that has this
code, `OffsetSeqMetadata.setSessionConf` calls `setConfString`, `checkValues`
throws, and the query does not start. The comment on
`rebindSQLConfsSessionToOffsetLog` in `OffsetSeq.scala` lists that kind of
downgrade as a case it cares about.
The state format versions use `checkValues` for a good reason, since an old
release cannot read a newer format. This conf only decides filter placement,
and `isExpensive` only tests for `0`, so a higher value already means the
current estimate:
```scala
.checkValue(_ >= 0, "The version of the regex pattern cost estimate must
be nonnegative.")
```
Going back would then run the older estimate. That is a placement change,
but it is much better than a query that cannot start. If you'd rather fail
loudly here, that's fine too.
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/regexpExpressions.scala:
##########
@@ -84,33 +84,212 @@ 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 or an alternation 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"))
+ }
+
+ // An inline flag, e.g. `(?x)` or `(?ix:`, that turns on COMMENTS mode,
which lets whitespace
+ // and comments separate a group from its quantifier.
+ private val commentsFlag = Pattern.compile("""\(\?[a-zA-Z]*x""")
+
+ // The product of the choices of the uncounted ranges that makes them count
as one quantifier.
+ private val smallRangesLimit = 100
+
+ /**
+ * 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. The
+ * alternatives of a `|` outside any group are tried one after another, so
each is counted on its
+ * own and the largest count is returned. These quantifiers are not counted:
+ * - a possessive one, which never backtracks;
+ * - one that ends the regex or an alternative of it, possibly inside
groups that end there too,
+ * which a failed match never backtracks into;
+ * - `?` and a `{n,m}` that spans fewer than 10, which add a small factor.
The choices of such
+ * quantifiers multiply, so they count as one quantifier each time their
product reaches 100.
+ * The count is `Int.MaxValue` for a repeated group that holds a quantifier
that can backtrack or
+ * a `|`, for a regex in COMMENTS mode, and for a `[` that is never closed,
since the scan cannot
+ * follow them.
+ *
+ * A streaming query pins `SQLConf.REGEX_PATTERN_COST_ESTIMATE_VERSION` in
its checkpoint, since
+ * a pattern that turns cheap can move a filter below a stateful operator.
So a change that makes
+ * any pattern cheaper needs a new version of the estimate, and the old one
has to be kept.
+ */
+ private def scanQuantifiers(regex: String): (Int, Boolean) = {
+ // The largest count of the alternatives before the current one.
+ var maxCount = 0
+ var count = 0
+ var smallRanges = 1
+ var classDepth = 0
+ var topLevelAlternation = false
+ // Whether each open group holds a choice that a repetition of it would
multiply, innermost
+ // first.
+ var groups = List.empty[Boolean]
+ var i = 0
+ def markGroup(): Unit = groups = groups match {
+ case _ :: outer => true :: outer
+ case Nil => Nil
+ }
+ // Whether nothing but the closing `)` of open groups comes between `j`
and the end of the
+ // regex or a `|` outside any group.
+ def endsAlternative(j: Int): Boolean = {
+ var end = j
+ var depth = groups.length
+ while (end < regex.length && depth > 0 && regex.charAt(end) == ')') {
+ end += 1
+ depth -= 1
+ }
+ end == regex.length || (depth == 0 && regex.charAt(end) == '|')
+ }
+ // Handles the quantifier that ends at `i`, which repeats its operand
`min` to `max` times,
+ // and moves `i` past its modifier.
+ def quantifier(min: Int, max: Int): Unit = {
+ val possessive = i + 1 < regex.length && regex.charAt(i + 1) == '+'
Review Comment:
**11. [Nit] `quantifier` reads its modifier three times**
`String.startsWith` with an offset already handles the end of the string,
and the scanner uses it at `(?`. So these lines could lose their bounds checks:
```scala
val possessive = regex.startsWith("+", i + 1)
if (possessive || regex.startsWith("?", i + 1)) i += 1
```
##########
sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/optimizer/FilterPushdownSuite.scala:
##########
@@ -328,16 +332,66 @@ class FilterPushdownSuite extends PlanTest {
// rlike magic is expensive so not pushed.
val correctAnswer = testStringRelation
.where($"a" + $"b" > 10 && $"a" - $"b" < 5)
- .select($"a" + $"b" as "sum", $"a" - $"b" as "diff", $"e".rlike("magic")
as "f")
+ .select($"a" + $"b" as "sum", $"a" - $"b" as "diff",
expensiveRLike("magic") as "f")
.where($"f")
.analyze
comparePlans(optimized, correctAnswer)
}
+ test("SPARK-60632: Push a filter on a LIKE/RLIKE alias with a cheap constant
pattern") {
+ Seq(
+ $"e".rlike("^1"),
+ $"e".rlike("magic"),
+ $"e".rlike("^a.*b"),
+ $"e".like("1_"),
+ $"e".like("%magic%"),
+ // ILIKE, as the optimizer sees it after `ReplaceExpressions`.
+ Like(Lower($"e"), Lower(Literal("%Magic%")), '\\')).foreach { pred =>
+ val originalQuery = testStringRelation
+ .select($"a", pred as "f")
+ .where($"f")
+ .analyze
+
+ val correctAnswer = testStringRelation
+ .where(pred)
+ .select($"a", pred as "f")
+ .analyze
+
+ comparePlans(Optimize.execute(originalQuery), correctAnswer)
+ }
+ }
+
+ test("SPARK-60632: Do not push a filter on a LIKE/RLIKE alias with a
backtracking pattern") {
+ Seq($"e".rlike("(a+)+b"), $"e".rlike(".*a.*b"),
$"e".like("%a%b%c")).foreach { pred =>
+ val originalQuery = testStringRelation
+ .select($"a", pred as "f")
+ .where($"f")
+ .analyze
+
+ comparePlans(Optimize.execute(originalQuery), originalQuery)
+ }
+ }
+
+ test("SPARK-60632: Do not push a filter on a LIKE/RLIKE alias with version 0
of the estimate") {
Review Comment:
**8. [Nit] The version-0 test does not reach the split path**
This test and the restart test use one alias, and one alias never splits.
With `isExpensive`, `stillToCompute` is `{f}`, which is a subset of `used`.
With plain `expensive`, it is empty, which is also a subset. So as far as I can
tell, changing the two `isExpensive` calls in
`splitProjectForExpensiveConditions` back to `.expensive` would leave every
test green, and a query resumed from a 4.3 checkpoint would no longer get the
split it had on 4.3.
Two aliases would tell them apart. By analogy with the first SPARK-55014
test:
```scala
withSQLConf(SQLConf.REGEX_PATTERN_COST_ESTIMATE_VERSION.key -> "0") {
val originalQuery = testStringRelation
.select($"a", $"e".rlike("^1") as "f", $"e".rlike("^2") as "g", $"b")
.where($"f" && $"g")
.analyze
val correctAnswer = testStringRelation
.select($"a", $"b", $"e", $"e".rlike("^1") as "f")
.where($"f")
.select($"a", $"f", $"e".rlike("^2") as "g", $"b")
.where($"g")
.analyze
comparePlans(Optimize.execute(originalQuery), correctAnswer)
}
```
--
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]
