viirya commented on code in PR #59879:
URL: https://github.com/apache/spark/pull/59879#discussion_r4421485100
##########
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:
Changed to `4.2.2`, since the plan is to backport this to `branch-4.2` and
`branch-4.3`.
##########
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:
Right, a literal subject was cheap in 4.2.0. The doc now says "as in 4.2.0
for a subject that is not a literal".
##########
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:
Added `SPARK-60632: regex pattern cost estimate version 0 for old
checkpoints` to `StreamingQueryManagerSuite`. It runs a batch of a query with a
`NOT (value RLIKE '^1')` alias and checks that the filter is pushed below the
projection. Then it removes the key from the latest offset-log entry, restarts
the query from the same DataFrame and checks that the filter stays above the
projection. Because both queries share the plan, this also covers item 2.
##########
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:
Done. The check now runs only after `regex.startsWith("(?", i)`, which is
also where the `?` from item 1 is skipped.
--
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]
