viirya commented on code in PR #59879:
URL: https://github.com/apache/spark/pull/59879#discussion_r4428904867
##########
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:
Done, with your `addChoices` helper. The first `|` of a group adds a choice
of two, and the `?`/small-range product shares it. `(a|a)`, `(a|)`, `(?:a|aa)`
and `(\w|\d)` 24 times are now expensive, and `.*(k1|k2|k3|k4|k5|k6|k7|k8).*`
stays cheap. `(a|b)` 24 times, which takes 0 ms, also turns expensive, which
errs on the safe side.
##########
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:
Done as you suggested. `repeats` skips an empty `\Q\E`, and
`^(.*?,)\Q\E{11}P` is now in the test.
##########
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:
Done with your `leadingAnchor` lookahead. `^?.*a.*b`, `\A?.*a.*b` and
`^{0,1}.*a.*b` are now expensive in the test.
##########
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:
Done. `\1` to `\9` and `\k` outside a class count as one quantifier, unless
they end the pattern or an alternative, like a quantifier. So `(.*)\1x`,
`(.+)\1\1x` and `(?<g>.*)\k<g>x` are expensive, while `(.*)\1` and `(\w)\1x`
stay cheap.
##########
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:
Done, a little wider than the suggestion. On JDK 17, with 2000 `a`s,
`.*.{1000}+x` took 467 ms and `.*.{1000,1005}x` took 515 ms, about the same as
`.*.{1000}x` (471 ms). So a repetition with a minimum of 100 or more counts one
whenever it is not already counted as a backtracking range, including the
possessive and small-span cases. A trailing one is still not counted:
`.*.{1000}` on 999 `a`s took 0 ms. `.{1000}x` and `\d{4}-\d{2}-\d{2}.*` stay
cheap.
##########
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:
I'd keep these expensive. Handling them would need per-alternative counting
at every group level, and an all-anchored check that also follows inline `(?m)`
across alternatives. That is a fair amount more scanner for a case that only
keeps a filter higher. The PR description now says they stay expensive on
purpose. If they turn out to matter, they can come with a new estimate version.
--
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]
