dongjoon-hyun commented on code in PR #59879:
URL: https://github.com/apache/spark/pull/59879#discussion_r4419220554
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/regexpExpressions.scala:
##########
@@ -84,33 +84,186 @@ 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 ||
+ !SQLConf.get.getConf(SQLConf.ESTIMATE_REGEX_PATTERN_COST) ||
_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 = 1000
+
+ /**
+ * 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. These
+ * quantifiers are not counted:
+ * - a possessive one, which never backtracks;
+ * - one that ends the regex, which a failed match never backtracks into;
+ * - a `{n,m}` that spans fewer than 10, which adds a small factor. The
choices of such ranges
+ * multiply, so they count as one quantifier each time their product
reaches 1000.
+ * 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.
+ */
+ private def scanQuantifiers(regex: String): (Int, Boolean) = {
+ 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
+ }
+ // 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 && i + 1 < regex.length) {
+ 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 (matcherAt(commentsFlag, regex, i).lookingAt()) {
+ return (Int.MaxValue, topLevelAlternation)
+ }
+ 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 else
markGroup()
+ case '*' => quantifier(0, Int.MaxValue)
+ case '+' => quantifier(1, Int.MaxValue)
+ // `?` adds at most a factor of 2 and is not counted.
+ case '?' => quantifier(0, 0)
Review Comment:
**1. [Medium] Two `?` in a repeated group blow up, but `?` is never counted**
The comment above says that "`?` adds at most a factor of 2", and that is
true for one `?`. But the factors of several `?` multiply, like those of the
small ranges. A group that holds two of them can split a run of characters in
exponentially many ways, the same way `(a|aa)` does. These patterns count 0 and
are classed cheap:
| Pattern | Input (no match) | JDK 25 | JDK 17 |
|---|---|---|---|
| `(a?a?){16}b` | 32 `a`s | 8.1 s | 8.4 s |
| `^(a?a?){16}b` | 32 `a`s | 0.62 s | 0.65 s |
| `^(.?.?){16}x` | 32 `a`s | 0.67 s | 0.67 s |
| `^(.?.?){20}x` | 40 `a`s | over 20 s | over 20 s |
| `a?` 24 times, then `b` | 24 `a`s | 1.1 s | 1.2 s |
`a{0,1}` 24 times, then `b`, takes about as long. But it counts 2 and is
classed expensive, because `{0,1}` goes through the small-range product. My
round-3 comment was wrong to say that `?` can stay out. It measured only one
`?` per group, and `(a?){25}a{25}b` does take 0 ms.
Could `?` take the same path as `{0,1}`? The `?` that opens `(?:`, `(?=`,
`(?<name>` or `(?i)` would have to be skipped first:
```scala
case '(' =>
...
groups = false :: groups
// The `?` of `(?:`, `(?=`, `(?<name>` or `(?i)` is not a
quantifier.
if (i + 1 < regex.length && regex.charAt(i + 1) == '?') i += 1
...
case '?' => quantifier(0, 1)
```
`(a?){25}a{25}b` would then be MAX, although it takes 0 ms. That errs on the
same side as round-3 item 8.
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/regexpExpressions.scala:
##########
@@ -84,33 +84,186 @@ 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 ||
Review Comment:
**2. [Low] A LIKE/RLIKE inside another expression keeps the answer of the
first conf value**
`expensive` now reads `estimateRegexPatternCost` on every call. But
`Expression.hasExpensiveChild` is a `lazy val`, so `Not`, `And`, `If` and every
other parent compute their `expensive` only once per instance, under whatever
value the conf had at that time. Analyzed plans share their expression
instances: a DataFrame built on another reuses them, and so does every
streaming query started from it.
For example, take a DataFrame `base` that projects `NOT (s RLIKE '^1') AS p`
over a stream-stream join, and `q = base.where($"p")`. Suppose `q.explain()`
runs, or a query from `q` with a new checkpoint runs a batch, both under the
default `true`. Then `Not.hasExpensiveChild` is cached as `false`. A query from
`q` that restarts from a 4.2 checkpoint gets `false` for the conf, but `NOT (s
RLIKE '^1')` still reports cheap, so its filter is pushed below the join. That
is the placement the offset-log default is there to keep. A bare `s RLIKE '^1'`
reads the conf again and stays above, so the two forms disagree.
Could the conf be checked where the answer is used, instead of inside
`expensive`? For example, in `PushPredicateThroughNonJoin`:
```scala
// `hasExpensiveChild` is cached, so `expensive` itself must not depend on
the conf.
private def isExpensive(e: Expression): Boolean = e.expensive ||
(!conf.getConf(SQLConf.ESTIMATE_REGEX_PATTERN_COST) &&
e.exists(_.isInstanceOf[StringRegexExpression]))
```
This would also save a `SQLConf.get` lookup on every call.
##########
sql/core/src/main/scala/org/apache/spark/sql/execution/streaming/checkpointing/OffsetSeq.scala:
##########
@@ -207,7 +207,8 @@ object OffsetSeqMetadata extends Logging {
ENABLE_STREAMING_SOURCE_EVOLUTION,
STATEFUL_OPERATOR_ALWAYS_NULLABLE_OUTPUT,
DROP_DUPLICATES_DETERMINISTIC_KEY_ORDER,
- ALLOW_EXCEPT_ON_STREAMING_DATAFRAME
+ ALLOW_EXCEPT_ON_STREAMING_DATAFRAME,
+ ESTIMATE_REGEX_PATTERN_COST
Review Comment:
**4. [Low] The offset log pins whether the estimate is on, not which
estimate**
Thanks for adding the conf. It answers the streaming question for
checkpoints written by 4.2.x and 4.3.x. But a checkpoint written with `true`
follows whatever `scanQuantifiers` does in the release that resumes it. Suppose
a later change makes a pattern cheaper, for example by counting each lookaround
(round-3 item 6) or each top-level alternative (item 5 below) on its own. On
restart, the filter on such an alias then moves below a stream-stream join, and
the rows already in the join state are never filtered. That is the problem this
conf fixes, and there would be no value left to pin it.
Could the offset log record a version of the estimate instead? For example,
an int conf where 0 means every LIKE/RLIKE is expensive and 1 means this
scanner. A later change that makes a pattern cheaper would then bump it. If
that is too much for this PR, a comment in `scanQuantifiers` saying that such a
change needs a new pin would still help.
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/internal/SQLConf.scala:
##########
@@ -670,6 +670,18 @@ object SQLConf {
.booleanConf
.createWithDefault(true)
+ val ESTIMATE_REGEX_PATTERN_COST =
+ buildConf("spark.sql.optimizer.estimateRegexPatternCost")
+ .internal()
+ .withBindingPolicy(ConfigBindingPolicy.NOT_APPLICABLE)
+ .doc(s"When true, ${AVOID_DOUBLE_FILTER_EVAL.key} treats a LIKE or RLIKE
expression as " +
+ "expensive only when its pattern is likely to be expensive to match.
When false, every " +
+ "LIKE and RLIKE expression is expensive, as in 4.2.0. A streaming query
keeps the value " +
Review Comment:
**7. [Nit] `as in 4.2.0` does not hold for a literal subject**
4.2.0 decided by `left`. A subject that was not a literal made LIKE/RLIKE
expensive, but a literal one, as in `'abc' RLIKE p`, was cheap. With `false` it
is now expensive. That moves its filter up, not down, so the checkpoint default
stays safe, but the doc could say so:
```scala
.doc(s"When true, ${AVOID_DOUBLE_FILTER_EVAL.key} treats a LIKE or RLIKE
expression as " +
"expensive only when its pattern is likely to be expensive to match.
When false, every " +
"LIKE and RLIKE expression is expensive, as in 4.2.0 for a subject
that is not a " +
"literal. A streaming query keeps the value recorded in its
checkpoint, and one " +
"restarted from a checkpoint without it uses false.")
```
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/regexpExpressions.scala:
##########
@@ -84,33 +84,186 @@ 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 ||
+ !SQLConf.get.getConf(SQLConf.ESTIMATE_REGEX_PATTERN_COST) ||
_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 = 1000
+
+ /**
+ * 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. These
+ * quantifiers are not counted:
+ * - a possessive one, which never backtracks;
+ * - one that ends the regex, which a failed match never backtracks into;
+ * - a `{n,m}` that spans fewer than 10, which adds a small factor. The
choices of such ranges
+ * multiply, so they count as one quantifier each time their product
reaches 1000.
+ * 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.
+ */
+ private def scanQuantifiers(regex: String): (Int, Boolean) = {
+ 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
+ }
+ // 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 && i + 1 < regex.length) {
+ markGroup()
+ if (max - min >= 10) {
+ count += 1
+ } else {
+ smallRanges *= max - min + 1
+ if (smallRanges >= smallRangesLimit) {
Review Comment:
**3. [Low] The small-range product drops what is left at each reset**
Thanks for adding the product. But the reset at 1000 drops the overshoot, so
a product of 9000 counts the same as 1000, and a remainder below 1000 never
counts. So these patterns count 1 and are classed cheap, while `.*a.*b`, which
counts 2, is faster:
| Pattern | Count | Input (no match) | JDK 25 | JDK 17 |
|---|---|---|---|---|
| `.*a.*b` | 2 | 400 `a`s | 42 ms | 41 ms |
| `.{0,9}a.{0,9}a.{0,8}a.*b` | 1 | 400 `a`s | 0.30 s | 0.33 s |
| `.{0,9}a.{0,9}a.{0,8}a.{0,9}a.{0,9}a.{0,8}ab` | 1 | 400 `a`s | 3.0 s | 2.0
s |
| `.*a.*b` | 2 | 2000 `a`s | 5.0 s | 4.9 s |
| `.{0,9}a.{0,9}a.{0,8}a.*b` | 1 | 2000 `a`s | 6.6 s | 6.6 s |
One combination of small ranges costs more than one step of `.*`, so 1000
combinations weigh more than one quantifier on a value of 400 or 2000
characters. With `smallRangesLimit = 100`, both slow patterns count 2, and
every case in the new test keeps its answer: three `.{0,9}` count 1 and stay
cheap, and six count 3. Four `.{0,9}`, which you measured at 15 ms, would
become expensive.
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/regexpExpressions.scala:
##########
@@ -84,33 +84,186 @@ 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 ||
+ !SQLConf.get.getConf(SQLConf.ESTIMATE_REGEX_PATTERN_COST) ||
_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 = 1000
+
+ /**
+ * 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. These
+ * quantifiers are not counted:
+ * - a possessive one, which never backtracks;
+ * - one that ends the regex, which a failed match never backtracks into;
+ * - a `{n,m}` that spans fewer than 10, which adds a small factor. The
choices of such ranges
+ * multiply, so they count as one quantifier each time their product
reaches 1000.
+ * 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.
+ */
+ private def scanQuantifiers(regex: String): (Int, Boolean) = {
+ 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
+ }
+ // 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 && i + 1 < regex.length) {
+ 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 (matcherAt(commentsFlag, regex, i).lookingAt()) {
+ return (Int.MaxValue, topLevelAlternation)
+ }
+ 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 else
markGroup()
Review Comment:
**5. [Low] Quantifiers in different top-level alternatives are added up**
The alternatives of a top-level `|` are tried one after another, so their
quantifiers do not multiply, but the scanner adds them up. Also, only the last
character counts as the end of the pattern. A quantifier that ends an
alternative, or that sits right before the `)` of a group around the whole
pattern, is counted, although a failed match never backtracks into it either.
So common keyword alternations are classed expensive:
| Pattern | Count | Classed | Input (no match) | JDK 25 | JDK 17 |
|---|---|---|---|---|---|
| `a.*b` | 1 | cheap | 2000 `a`s | 7 ms | 7 ms |
| `a.*b\|a.*c` | 2 | expensive | 2000 `a`s | 14 ms | 15 ms |
| `foo.*bar\|baz.*qux` | 2 | expensive | `foobaz` 333 times | 12 ms | 10 ms |
| `foo.*bar.*` | 1 | cheap | `foo` 700 times | 18 ms | 10 ms |
| `(foo.*bar.*)` | 2 | expensive | `foo` 700 times | 12 ms | 9 ms |
| `a.*b.*\|x` | 2 | expensive | 2000 `a`s | 12 ms | 7 ms |
A filter on such an alias stays above the projection and gets no pushdown or
pruning, as in 4.2.0. Like round-3 item 6, this errs on the safe side, but
keyword alternations are much more common in RLIKE filters than lookarounds.
Counting each top-level alternative on its own and taking the largest count
would fix the first two expensive rows. Treating a quantifier that comes right
before a top-level `|`, or before nothing but closing `)`s, as one that ends
the pattern would fix the other two.
##########
sql/core/src/test/scala/org/apache/spark/sql/execution/streaming/OffsetSeqLogSuite.scala:
##########
@@ -52,6 +52,20 @@ class OffsetSeqLogSuite extends SharedSparkSession {
assert(metadata.conf.get(SQLConf.ALLOW_EXCEPT_ON_STREAMING_DATAFRAME.key).contains("false"))
}
+ test("SPARK-60632: regex pattern cost estimate is disabled for old
checkpoints") {
Review Comment:
**8. [Nit] No test restarts a query from a checkpoint without the key**
These two tests check what `readValue` returns and what a new checkpoint
records. Neither checks that a restarted query gets `false` in its session, or
that the filter then stays above the projection. A test could run a batch,
remove the key from the last offset-log entry, restart, and check where the
RLIKE filter lands in `lastExecution.optimizedPlan`. That would cover the whole
path, and with a `NOT (s RLIKE '^1')` alias on the same DataFrame it would also
catch item 2. Checking `OffsetSeqMetadata.setSessionConf` on metadata without
the key would cover the first half.
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/regexpExpressions.scala:
##########
@@ -84,33 +84,186 @@ 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 ||
+ !SQLConf.get.getConf(SQLConf.ESTIMATE_REGEX_PATTERN_COST) ||
_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 = 1000
+
+ /**
+ * 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. These
+ * quantifiers are not counted:
+ * - a possessive one, which never backtracks;
+ * - one that ends the regex, which a failed match never backtracks into;
+ * - a `{n,m}` that spans fewer than 10, which adds a small factor. The
choices of such ranges
+ * multiply, so they count as one quantifier each time their product
reaches 1000.
+ * 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.
+ */
+ private def scanQuantifiers(regex: String): (Int, Boolean) = {
+ 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
+ }
+ // 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 && i + 1 < regex.length) {
+ 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 (matcherAt(commentsFlag, regex, i).lookingAt()) {
Review Comment:
**9. [Nit] A `Matcher` is built at every `(`**
`matcherAt(commentsFlag, regex, i)` allocates a `Matcher` and its group
arrays for every group, although only a `(?` can match. Checking those two
characters first keeps plain groups free:
```suggestion
if (regex.startsWith("(?", i) && matcherAt(commentsFlag, regex,
i).lookingAt()) {
```
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/internal/SQLConf.scala:
##########
@@ -670,6 +670,18 @@ object SQLConf {
.booleanConf
.createWithDefault(true)
+ val ESTIMATE_REGEX_PATTERN_COST =
+ buildConf("spark.sql.optimizer.estimateRegexPatternCost")
+ .internal()
+ .withBindingPolicy(ConfigBindingPolicy.NOT_APPLICABLE)
+ .doc(s"When true, ${AVOID_DOUBLE_FILTER_EVAL.key} treats a LIKE or RLIKE
expression as " +
+ "expensive only when its pattern is likely to be expensive to match.
When false, every " +
+ "LIKE and RLIKE expression is expensive, as in 4.2.0. A streaming query
keeps the value " +
+ "recorded in its checkpoint, and one restarted from a checkpoint without
it uses false.")
+ .version("4.4.0")
Review Comment:
**6. [Low] The version should be the first release that gets the conf**
Your reply on the streaming question says that the fix is safe to backport
to `branch-4.2` and `branch-4.3`. If it goes there, the conf first ships from
`branch-4.2`, so `.version` should be `4.2.2`. If it goes only to `branch-4.3`,
it should be `4.3.0`, which has not been released yet. `4.4.0` is right only if
the change stays on `master` and `branch-4.x`.
--
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]
