viirya commented on code in PR #59879:
URL: https://github.com/apache/spark/pull/59879#discussion_r4430934604
##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/regexpExpressions.scala:
##########
@@ -84,33 +84,233 @@ 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
+
+ // `^` or `\A`, unless a quantifier may make it optional.
+ private val leadingAnchor = """(?:\^|\\A)(?![?*{])""".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') && leadingAnchor.findPrefixOf(rest).isDefined
+ }
+
+ // 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, and of groups that hold a `|`, multiply, so they count as
one quantifier each
+ * time their product reaches 100.
+ * A repetition of at least 100, which adds its length to every attempt even
when it cannot
+ * backtrack, and a backreference, which compares as many characters as its
group holds, count
+ * as one quantifier each, unless they end the regex or an alternative of it.
+ * 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 open = groups
+ while (end < regex.length && open.nonEmpty && regex.charAt(end) == ')') {
+ end += 1
+ open = open.tail
+ }
+ end == regex.length || (open.isEmpty && regex.charAt(end) == '|')
+ }
+ // Adds a choice among `n` to the product, which counts as one quantifier
when it gets large.
+ def addChoices(n: Int): Unit = {
Review Comment:
Thanks, I lowered the limit to 32. On JDK 17, with 1000 `a`s and no match,
`.*a.*b` took 331 ms. `.*` followed by `(a|aa)` repeated 4, 5 and 6 times took
153 ms, 325 ms and 638 ms. So a product of 32 next to a `.*` costs about as
much as a second `.*`. `.*` with 4 `(a|aa)` stays cheap, and with 5 `(a|aa)` or
5 `a?` it is now expensive. Every other constant pattern in the test keeps its
answer. Since the conf has not shipped yet, no new estimate version is needed.
--
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]
