This is an automated email from the ASF dual-hosted git repository.
viirya pushed a commit to branch branch-4.3
in repository https://gitbox.apache.org/repos/asf/spark.git
The following commit(s) were added to refs/heads/branch-4.3 by this push:
new ae34f771b02e [SPARK-60632][4.3][SQL] Fix the LIKE/RLIKE expensive
heuristic to look at the pattern
ae34f771b02e is described below
commit ae34f771b02ec0d7d4ec976ce374ce3b69a7daa9
Author: Liang-Chi Hsieh <[email protected]>
AuthorDate: Sat Oct 31 17:02:40 2026 -0700
[SPARK-60632][4.3][SQL] Fix the LIKE/RLIKE expensive heuristic to look at
the pattern
### What changes were proposed in this pull request?
This is a backport of #59879 to `branch-4.3`.
It fixes the `expensive` heuristic of LIKE/RLIKE added by SPARK-47672,
which matched on the subject string instead of the pattern and so classed every
LIKE/RLIKE over a column as expensive. A constant pattern is now classed by its
backtracking quantifiers. A new internal config,
`spark.sql.optimizer.regexPatternCostEstimateVersion`, is recorded in the
streaming offset log, so a query resumed from an existing checkpoint keeps its
filter placement. See #59879 for the full description.
Differences from the `master` commit:
- `branch-4.3` does not have SPARK-55014
(`splitProjectForExpensiveConditions`), so `PushPredicateThroughNonJoin` uses
`isExpensive` only in `isCheap`, and the `FilterPushdownSuite` case for
splitting the projection between two LIKE/RLIKE aliases with version `0` is
left out.
- The SPARK-47672 and SPARK-60602 tests in `FilterPushdownSuite` that used
`$"e".rlike("magic")` as their expensive stand-in now use `expensiveRLike`, as
on `master`.
- `StreamingQueryManagerSuite` gets the `rewriteOffsetLogConf` helper,
which `master` has from an earlier change.
### Why are the changes needed?
With the default config, a filter on an alias of a LIKE/RLIKE expression is
not pushed below the Project, which loses partition pruning and data filter
pushdown. This is a regression in 4.2.0.
### Does this PR introduce _any_ user-facing change?
Yes: filters on aliased LIKE/RLIKE expressions with a cheap constant
pattern are pushed down again, as they were before 4.2.0. Query results do not
change. Streaming queries resumed from an existing checkpoint keep their filter
placement.
### How was this patch tested?
`catalyst/testOnly *RegexpExpressionsSuite *FilterPushdownSuite` and
`sql/testOnly *OffsetSeqLogSuite *StreamingQueryManagerSuite
*FileSourceStrategySuite` on JDK 17, and scalastyle.
### Was this patch authored or co-authored using generative AI tooling?
Generated-by: Claude Code (Claude Opus 5.5)
This pull request and its description were written by Isaac.
Closes #59993 from viirya/SPARK-60632-4.3.
Authored-by: Liang-Chi Hsieh <[email protected]>
Signed-off-by: Liang-Chi Hsieh <[email protected]>
---
.../catalyst/expressions/regexpExpressions.scala | 250 +++++++++++++++++++--
.../spark/sql/catalyst/optimizer/Optimizer.scala | 11 +-
.../org/apache/spark/sql/internal/SQLConf.scala | 14 ++
.../expressions/RegexpExpressionsSuite.scala | 77 +++++++
.../catalyst/optimizer/FilterPushdownSuite.scala | 88 ++++++--
.../streaming/checkpointing/OffsetSeq.scala | 6 +-
.../datasources/FileSourceStrategySuite.scala | 33 ++-
.../execution/streaming/OffsetSeqLogSuite.scala | 14 ++
.../sql/streaming/StreamingQueryManagerSuite.scala | 58 +++++
9 files changed, 508 insertions(+), 43 deletions(-)
diff --git
a/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/regexpExpressions.scala
b/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/regexpExpressions.scala
index 07d1d00ec756..779408ee4b02 100644
---
a/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/regexpExpressions.scala
+++
b/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 = 32
+
+ /**
+ * 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 32.
+ * 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 = {
+ smallRanges *= n
+ if (smallRanges >= smallRangesLimit) {
+ count += 1
+ smallRanges = 1
+ }
+ }
+ // 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 = regex.startsWith("+", i + 1)
+ if (possessive || regex.startsWith("?", i + 1)) i += 1
+ if (!endsAlternative(i + 1)) {
+ if (!possessive && max - min >= 10) {
+ markGroup()
+ count += 1
+ } else {
+ if (!possessive && max > min) {
+ markGroup()
+ addChoices(max - min + 1)
+ }
+ if (min >= 100) count += 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 ((c >= '1' && c <= '9') || c == 'k') && classDepth == 0
&&
+ !endsAlternative(i + 1) =>
+ count += 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 '|' =>
+ // A group adds one factor, however many alternatives it has.
+ if (!groups.head) addChoices(2)
+ 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 && {
+ regex.charAt(i) match {
+ case '*' | '+' => true
+ case '{' => bounds(regex, i).exists(_._3 >= 2)
+ // `Pattern` removes an empty quote before it parses the regex.
+ case '\\' if regex.startsWith("\\Q\\E", i) => repeats(regex, i + 4)
+ case _ => false
+ }
+ }
+
+ // A matcher of `p` over `regex` from `start`, which does not copy the rest
of `regex`.
+ private def matcherAt(p: Pattern, regex: String, start: Int): Matcher =
+ p.matcher(regex).region(start, regex.length)
+
+ private val repetition = Pattern.compile("""\{(\d+)(?:,(\d*))?\}""")
+
+ // Parses the `{n}`, `{n,}` or `{n,m}` at `start` into its closing index and
its bounds, with
+ // `Int.MaxValue` as the upper bound of `{n,}`.
+ private def bounds(regex: String, start: Int): Option[(Int, Int, Int)] = {
+ val m = matcherAt(repetition, regex, start)
+ Option.when(m.lookingAt()) {
+ def toInt(s: String): Int = s.toIntOption.getOrElse(Int.MaxValue)
+ val min = toInt(m.group(1))
+ val max = Option(m.group(2)).map(s => if (s.isEmpty) Int.MaxValue else
toInt(s))
+ (m.end - 1, min, max.getOrElse(min))
+ }
+ }
+
def expressionToEscapeChar(e: Expression): Char = e match {
case StringLiteral(v) if v.length == 1 => v.charAt(0)
case _ => throw QueryCompilationErrors.invalidEscapeChar(e)
@@ -182,6 +382,10 @@ case class Like(left: Expression, right: Expression,
escapeChar: Char)
override def matches(regex: Pattern, str: String): Boolean =
regex.matcher(str).matches()
+ // Each `%` becomes a `.*`. `LikeSimplification` rewrites most patterns with
fewer than three.
+ override protected def isExpensivePattern(str: String): Boolean =
+ StringRegexExpression.isExpensiveRegex(escape(str), matchesWhole = true)
+
final override val nodePatterns: Seq[TreePattern] = Seq(LIKE_FAMLIY)
override def toString: String = {
@@ -534,6 +738,8 @@ case class RLike(left: Expression, right: Expression)
extends StringRegexExpress
override def escape(v: String): String = v
override def matches(regex: Pattern, str: String): Boolean =
regex.matcher(str).find(0)
+ override protected def isExpensivePattern(str: String): Boolean =
+ StringRegexExpression.isExpensiveRegex(str, matchesWhole = false)
override def toString: String = s"RLIKE($left, $right)"
override def sql: String =
s"${prettyName.toUpperCase(Locale.ROOT)}(${left.sql}, ${right.sql})"
diff --git
a/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/Optimizer.scala
b/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/Optimizer.scala
index 1a0ee671ab9e..77b730fbcc40 100644
---
a/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/Optimizer.scala
+++
b/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/Optimizer.scala
@@ -2552,7 +2552,7 @@ object PushPredicateThroughNonJoin extends
Rule[LogicalPlan] with PredicateHelpe
// uses nothing at all, or only inexpensive items. Then we can push it
because it might
// eliminate more data quickly and it may also be something which
could be evaluated at
// the storage layer. We may wish to improve this heuristic in the
future.
- def isCheap(used: AttributeMap[Alias]): Boolean =
!used.exists(_._2.child.expensive)
+ def isCheap(used: AttributeMap[Alias]): Boolean = !used.exists(a =>
isExpensive(a._2.child))
// Split the filter's components into cheap and expensive while
keeping track of
// what each references from the projection. The cheap components
written before the
// first expensive one are all pushed. After it, a throwable component
(e.g.
@@ -2743,6 +2743,15 @@ object PushPredicateThroughNonJoin extends
Rule[LogicalPlan] with PredicateHelpe
}
}
+ /**
+ * Whether `e` is expensive. Version 0 of the regex pattern cost estimate
treats every LIKE and
+ * RLIKE as expensive. It is checked here rather than in
`StringRegexExpression.expensive`,
+ * because `hasExpensiveChild` caches the answer of a parent expression.
+ */
+ private def isExpensive(e: Expression): Boolean = e.expensive ||
+ (conf.getConf(SQLConf.REGEX_PATTERN_COST_ESTIMATE_VERSION) == 0 &&
+ e.exists(_.isInstanceOf[StringRegexExpression]))
+
/**
* Check if we can safely push a filter through a projection, by making sure
that predicate
* subqueries in the condition do not contain the same attributes as the
plan they are moved
diff --git
a/sql/catalyst/src/main/scala/org/apache/spark/sql/internal/SQLConf.scala
b/sql/catalyst/src/main/scala/org/apache/spark/sql/internal/SQLConf.scala
index aa3b1858a586..907b2e119d74 100644
--- a/sql/catalyst/src/main/scala/org/apache/spark/sql/internal/SQLConf.scala
+++ b/sql/catalyst/src/main/scala/org/apache/spark/sql/internal/SQLConf.scala
@@ -610,6 +610,20 @@ object SQLConf {
.booleanConf
.createWithDefault(true)
+ val REGEX_PATTERN_COST_ESTIMATE_VERSION =
+ buildConf("spark.sql.optimizer.regexPatternCostEstimateVersion")
+ .internal()
+ .withBindingPolicy(ConfigBindingPolicy.NOT_APPLICABLE)
+ .doc(s"How ${AVOID_DOUBLE_FILTER_EVAL.key} decides whether a LIKE or RLIKE
expression is " +
+ "expensive. 0: every LIKE and RLIKE expression is expensive, as in 4.2.0
for a subject " +
+ "that is not a literal. 1: only one whose pattern is likely to be
expensive to match. A " +
+ "streaming query keeps the version recorded in its checkpoint, and one
restarted from a " +
+ "checkpoint without it uses 0.")
+ .version("4.2.2")
+ .intConf
+ .checkValue(_ >= 0, "The version of the regex pattern cost estimate must
be nonnegative.")
+ .createWithDefault(1)
+
val ATTEMPT_TRANSPILATION_OF_PYTHON_UDFS =
buildConf("spark.sql.experimental.optimizer.transpilePyUDFs")
.withBindingPolicy(ConfigBindingPolicy.SESSION)
diff --git
a/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/expressions/RegexpExpressionsSuite.scala
b/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/expressions/RegexpExpressionsSuite.scala
index 5377b9c7fc0b..0ba9fadd4bba 100644
---
a/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/expressions/RegexpExpressionsSuite.scala
+++
b/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/expressions/RegexpExpressionsSuite.scala
@@ -735,4 +735,81 @@ class RegexpExpressionsSuite extends SparkFunSuite with
ExpressionEvalHelper {
assert(extractAllCopy ne extractAll,
"freshCopyIfContainsStatefulExpression should return a new instance for
RegExpExtractAll")
}
+
+ test("SPARK-60632: LIKE and RLIKE expensive heuristic looks at the pattern")
{
+ val str = $"s".string.at(0)
+ val pattern = $"p".string.at(1)
+
+ // The subject string is irrelevant; a constant pattern is checked. Two or
more repeating
+ // quantifiers that can backtrack make an RLIKE expensive, and three or
more when it is
+ // anchored at the start.
+ // scalastyle:off SingleSpaceBetweenRParenAndLCurlyBrace
+ Seq("^1", "magic", "a.b", "^a.*b", "2024-.*", "\\d{2,}", "a{3}b*",
"(?i)^abc.*",
+ "a\\+b\\*", "[+*{]x+", "\\p{Lu}+", "\\x{41}.*", "\\Q.*+\\E.*",
"[a-z&&[^b]]+x",
+ "\\(?x.*a", "[]a]*x",
+ // Possessive quantifiers and small ranges.
+ "a*+b", "a?+b?+", "a{3}+b", ".*+a.*+b", "a{1,9}b{1,9}", "(ab){3}.*",
+ ".{0,9}a.{0,9}a.{0,9}x",
+ // A quantifier that ends the pattern or an alternative, and
alternatives on their own.
+ "a.*b.*", "a{2,}b+", "\\d+\\s*", "a+?b.*", "(foo.*bar.*)", "a.*b.*|x",
"a.*b|a.*c",
+ "foo.*bar|baz.*qux", "colou?r.*x", "(.*)\\1", ".*.{1000}",
+ // Groups that hold a `|`, a long fixed repetition and a backreference
on their own.
+ ".*(k1|k2|k3|k4|k5|k6|k7|k8).*", ".{1000}x", "\\d{4}-\\d{2}-\\d{2}.*",
"(\\w)\\1x",
+ "^(\\w+)\\s\\1.*", ".*" + "(a|aa)" * 4 + "x",
+ // Anchored.
+ "^.*a.*b", "\\A.*a.*b", "(?i)^.*a.*b", "^v[0-9]+_.*",
"^(a|b).*c.*").foreach { p =>
+ assert(!RLike(str, Literal(p)).expensive, p)
+ }
+ Seq(".*a.*b", "^.*a.*a.*b", "\\b.*a.*b", "a.*b.*$", ".{0,50}a.{0,50}b",
"^a|.*b.*c",
+ "(?m)^.*a.*b", ".{0,9}a.{0,9}a.{0,9}a.{0,9}a.{0,9}a.{0,9}x",
".{0,9}a.{0,9}a.{0,8}a.*b",
+ "a?" * 24 + "b", "(a.*b.*)c", "x|a.*b.*c",
+ // Groups that hold a `|`, which multiply like `?`.
+ "(a|a)" * 24 + "b", "(a|)" * 24 + "b", "(?:a|aa)" * 24 + "b",
"(\\w|\\d)" * 24 + "x",
+ ".*" + "(a|aa)" * 5 + "x", ".*" + "a?" * 5 + "x",
+ // An anchor that a quantifier makes optional.
+ "^?.*a.*b", "\\A?.*a.*b", "^{0,1}.*a.*b",
+ // A backreference, and a long repetition next to a quantifier.
+ "(.*)\\1x", "(.+)\\1\\1x", "(?<g>.*)\\k<g>x", ".*.{1000}x",
".*.{1000}+x",
+ ".*.{1000,1005}x",
+ // A repeated group that holds a quantifier or an alternation.
+ "(a+)+b", "^(a+)+b", "^(.*?,){11}P", "(.*a){3}x", "^((.*a)b){2}",
"(a{1,9}){6}b",
+ "(a|aa){20}b", "^(\\d|\\w){24}x", "(a?a?){16}b", "^(.?.?){16}x",
+ "^(.*?,)\\Q\\E{11}P",
+ // COMMENTS mode.
+ "(?x) ^ (.*?,) {11} P", "(?x)(.*a) {3}x",
+ // A `[` that does not open a class, and a `]` that does not close one.
+ "\\c[.*a.*b", "(?x)a # [\n.*a.*b", "^[](]a|.*b.*c").foreach { p =>
+ assert(RLike(str, Literal(p)).expensive, p)
+ }
+ // scalastyle:on SingleSpaceBetweenRParenAndLCurlyBrace
+ // Three or more `%` that are not at the end make a LIKE expensive, since
it must match the
+ // whole input.
+ Seq("1_", "%magic%", "%a%b", "%a%b%", "%a\\%b%", "a_b_c",
"%a\\\\%b").foreach { p =>
+ assert(!Like(str, Literal(p), '\\').expensive, p)
+ }
+ assert(!Like(str, Literal("%a#%b#%c%"), '#').expensive)
+ Seq("%a%b%c%", "%a%a%a%b", "%(.*)%|%x").foreach { p =>
+ assert(Like(str, Literal(p), '\\').expensive, p)
+ }
+ // A pattern with an invalid escape is expensive rather than failing the
optimizer.
+ assert(Like(str, Literal("a\\b"), '\\').expensive)
+
+ // A foldable pattern that is not yet a literal.
+ assert(!RLike(str, Concat(Seq(Literal("^"), Literal("a.*")))).expensive)
+ assert(RLike(str, Concat(Seq(Literal(".*a"), Literal(".*b")))).expensive)
+ assert(!RLike(str, Literal.create(null, StringType)).expensive)
+ // A foldable pattern that fails to evaluate is expensive rather than
failing the optimizer.
+ withSQLConf(SQLConf.ANSI_ENABLED.key -> "true") {
+ assert(RLike(str, Cast(Divide(Literal(1), Literal(0)),
StringType)).expensive)
+ }
+
+ // A non-foldable pattern is compiled for every row.
+ assert(RLike(str, pattern).expensive)
+ assert(Like(str, pattern, '\\').expensive)
+
+ // An expensive subject wins over a cheap pattern.
+ val udf = ScalaUDF((s: String) => s, StringType, Seq(str), Seq(None))
+ assert(RLike(udf, Literal("^1")).expensive)
+ assert(Like(udf, Literal("1_"), '\\').expensive)
+ }
}
diff --git
a/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/optimizer/FilterPushdownSuite.scala
b/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/optimizer/FilterPushdownSuite.scala
index 832e4fa3a140..e767b06ebba3 100644
---
a/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/optimizer/FilterPushdownSuite.scala
+++
b/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/optimizer/FilterPushdownSuite.scala
@@ -70,6 +70,10 @@ class FilterPushdownSuite extends PlanTest {
&& (("x.a".attr > 3) && ("y.a".attr > 13) || ("x.a".attr > 1) &&
("y.a".attr > 11)))).analyze
}
+ // Stands in for an expensive expression: a regex whose pattern is not a
constant is compiled
+ // for every row.
+ private def expensiveRLike(tag: String): Expression =
$"e".rlike(Concat(Seq($"e", Literal(tag))))
+
// This test already passes.
test("eliminate subqueries") {
val originalQuery =
@@ -173,15 +177,15 @@ class FilterPushdownSuite extends PlanTest {
test("SPARK-47672: Do double evaluation when configured") {
withSQLConf(SQLConf.AVOID_DOUBLE_FILTER_EVAL.key -> "false") {
val originalQuery = testStringRelation
- .select($"a", $"e".rlike("magic") as "f", $"e".rlike("notmagic") as
"j", $"b")
+ .select($"a", expensiveRLike("magic") as "f",
expensiveRLike("notmagic") as "j", $"b")
.where($"a" > 5 && $"f")
.analyze
val optimized = Optimize.execute(originalQuery)
val correctAnswer = testStringRelation
- .where($"a" > 5 && $"e".rlike("magic"))
- .select($"a", $"e".rlike("magic") as "f", $"e".rlike("notmagic") as
"j", $"b")
+ .where($"a" > 5 && expensiveRLike("magic"))
+ .select($"a", expensiveRLike("magic") as "f",
expensiveRLike("notmagic") as "j", $"b")
.analyze
comparePlans(optimized, correctAnswer)
@@ -190,7 +194,7 @@ class FilterPushdownSuite extends PlanTest {
test("SPARK-47672: Make sure that we handle the case where everything is
expensive") {
val originalQuery = testStringRelation
- .select($"e".rlike("magic") as "f")
+ .select(expensiveRLike("magic") as "f")
.where($"f")
.analyze
@@ -205,7 +209,7 @@ class FilterPushdownSuite extends PlanTest {
// Case 1: Multiple filters that don't reference any projection aliases -
all should be pushed
test("SPARK-47672: Case 1 - multiple filters not referencing projection
aliases") {
val originalQuery = testStringRelation
- .select($"a" as "c", $"e".rlike("magic") as "f", $"b" as "d", $"a", $"b")
+ .select($"a" as "c", expensiveRLike("magic") as "f", $"b" as "d", $"a",
$"b")
.where($"a" > 5 && $"b" < 10)
.analyze
@@ -215,7 +219,7 @@ class FilterPushdownSuite extends PlanTest {
// simple aliases (c->a, d->b) which are inexpensive
val correctAnswer = testStringRelation
.where($"a" > 5 && $"b" < 10)
- .select($"a" as "c", $"e".rlike("magic") as "f", $"b" as "d", $"a", $"b")
+ .select($"a" as "c", expensiveRLike("magic") as "f", $"b" as "d", $"a",
$"b")
.analyze
comparePlans(optimized, correctAnswer)
@@ -224,7 +228,7 @@ class FilterPushdownSuite extends PlanTest {
// Case 2: Multiple filters with inexpensive references - all should be
pushed
test("SPARK-47672: Case 2 - multiple filters with inexpensive alias
references") {
val originalQuery = testStringRelation
- .select($"a" + $"b" as "sum", $"a" - $"b" as "diff", $"e".rlike("magic")
as "f")
+ .select($"a" + $"b" as "sum", $"a" - $"b" as "diff",
expensiveRLike("magic") as "f")
.where($"sum" > 10 && $"diff" < 5)
.analyze
@@ -233,7 +237,7 @@ class FilterPushdownSuite extends PlanTest {
// Both sum and diff are inexpensive (arithmetic), so both filters should
be pushed
val correctAnswer = testStringRelation
.where($"a" + $"b" > 10 && $"a" - $"b" < 5)
- .select($"a" + $"b" as "sum", $"a" - $"b" as "diff", $"e".rlike("magic")
as "f")
+ .select($"a" + $"b" as "sum", $"a" - $"b" as "diff",
expensiveRLike("magic") as "f")
.analyze
comparePlans(optimized, correctAnswer)
@@ -242,7 +246,7 @@ class FilterPushdownSuite extends PlanTest {
// Case 3: Filter references expensive to compute references.
test("SPARK-47672: Avoid double evaluation with projections can't push past
certain items") {
val originalQuery = testStringRelation
- .select($"a", $"e".rlike("magic") as "f")
+ .select($"a", expensiveRLike("magic") as "f")
.where($"a" > 5 || $"f")
.analyze
@@ -254,7 +258,7 @@ class FilterPushdownSuite extends PlanTest {
// Combined case 1, 2, and 3 filter pushdown
test("SPARK-47672: Case 1, 2, and 3 make sure we leave up and push down
correctly.") {
val originalQuery = testStringRelation
- .select($"a" + $"b" as "sum", $"a" - $"b" as "diff", $"e".rlike("magic")
as "f")
+ .select($"a" + $"b" as "sum", $"a" - $"b" as "diff",
expensiveRLike("magic") as "f")
.where($"sum" > 10 && $"diff" < 5 && $"f")
.analyze
@@ -264,17 +268,67 @@ class FilterPushdownSuite extends PlanTest {
// rlike magic is expensive so not pushed.
val correctAnswer = testStringRelation
.where($"a" + $"b" > 10 && $"a" - $"b" < 5)
- .select($"a" + $"b" as "sum", $"a" - $"b" as "diff", $"e".rlike("magic")
as "f")
+ .select($"a" + $"b" as "sum", $"a" - $"b" as "diff",
expensiveRLike("magic") as "f")
.where($"f")
.analyze
comparePlans(optimized, correctAnswer)
}
+ test("SPARK-60632: Push a filter on a LIKE/RLIKE alias with a cheap constant
pattern") {
+ Seq(
+ $"e".rlike("^1"),
+ $"e".rlike("magic"),
+ $"e".rlike("^a.*b"),
+ $"e".like("1_"),
+ $"e".like("%magic%"),
+ // ILIKE, as the optimizer sees it after `ReplaceExpressions`.
+ Like(Lower($"e"), Lower(Literal("%Magic%")), '\\')).foreach { pred =>
+ val originalQuery = testStringRelation
+ .select($"a", pred as "f")
+ .where($"f")
+ .analyze
+
+ val correctAnswer = testStringRelation
+ .where(pred)
+ .select($"a", pred as "f")
+ .analyze
+
+ comparePlans(Optimize.execute(originalQuery), correctAnswer)
+ }
+ }
+
+ test("SPARK-60632: Do not push a filter on a LIKE/RLIKE alias with a
backtracking pattern") {
+ Seq($"e".rlike("(a+)+b"), $"e".rlike(".*a.*b"),
$"e".like("%a%b%c")).foreach { pred =>
+ val originalQuery = testStringRelation
+ .select($"a", pred as "f")
+ .where($"f")
+ .analyze
+
+ comparePlans(Optimize.execute(originalQuery), originalQuery)
+ }
+ }
+
+ test("SPARK-60632: Do not push a filter on a LIKE/RLIKE alias with version 0
of the estimate") {
+ Seq($"e".rlike("^1"), $"e".like("1_"), !$"e".rlike("^1")).foreach { pred =>
+ val originalQuery = testStringRelation
+ .select($"a", pred as "f")
+ .where($"f")
+ .analyze
+
+ // A parent expression caches whether its child is expensive, so
optimize the same plan
+ // with version 1 first.
+ Optimize.execute(originalQuery)
+ withSQLConf(SQLConf.REGEX_PATTERN_COST_ESTIMATE_VERSION.key -> "0") {
+ comparePlans(Optimize.execute(originalQuery), originalQuery)
+ }
+ }
+ }
+
test("SPARK-60602: a cheap throwable condition is not pushed ahead of an
expensive one") {
val raiseError = IsNull(RaiseError(Literal("boom")))
val originalQuery = testStringRelation
- .select($"a", $"e".rlike("magic") as "f", $"b")
+ .select($"a", expensiveRLike("magic") as "f", $"b")
.where($"f" && ($"a" > 5 || raiseError) && $"b" > 1)
.analyze
@@ -283,7 +337,7 @@ class FilterPushdownSuite extends PlanTest {
// Only the non-throwable cheap condition moves below the expensive one.
val correctAnswer = testStringRelation
.where($"b" > 1)
- .select($"a", $"e".rlike("magic") as "f", $"b")
+ .select($"a", expensiveRLike("magic") as "f", $"b")
.where($"f" && ($"a" > 5 || raiseError))
.analyze
@@ -291,13 +345,13 @@ class FilterPushdownSuite extends PlanTest {
// Written ahead of every expensive condition, it is pushed as usual.
val throwableFirst = testStringRelation
- .select($"a", $"e".rlike("magic") as "f", $"b")
+ .select($"a", expensiveRLike("magic") as "f", $"b")
.where(($"a" > 5 || raiseError) && $"f")
.analyze
val throwableFirstAnswer = testStringRelation
.where($"a" > 5 || raiseError)
- .select($"a", $"e".rlike("magic") as "f", $"b")
+ .select($"a", expensiveRLike("magic") as "f", $"b")
.where($"f")
.analyze
@@ -308,7 +362,7 @@ class FilterPushdownSuite extends PlanTest {
"expensive one") {
val raiseError = IsNull(RaiseError(Literal("boom")))
val originalQuery = testStringRelation
- .select($"a", $"e".rlike("magic") as "f", If($"a" > 5, Literal(true),
raiseError) as "t",
+ .select($"a", expensiveRLike("magic") as "f", If($"a" > 5,
Literal(true), raiseError) as "t",
$"b")
.where($"f" && $"t" && $"b" > 1)
.analyze
@@ -318,7 +372,7 @@ class FilterPushdownSuite extends PlanTest {
// `t` is cheap, but reading it evaluates the throwable expression behind
it.
val correctAnswer = testStringRelation
.where($"b" > 1)
- .select($"a", $"e".rlike("magic") as "f", If($"a" > 5, Literal(true),
raiseError) as "t",
+ .select($"a", expensiveRLike("magic") as "f", If($"a" > 5,
Literal(true), raiseError) as "t",
$"b")
.where($"f" && $"t")
.analyze
diff --git
a/sql/core/src/main/scala/org/apache/spark/sql/execution/streaming/checkpointing/OffsetSeq.scala
b/sql/core/src/main/scala/org/apache/spark/sql/execution/streaming/checkpointing/OffsetSeq.scala
index 49fbf415e3b3..0d8358520fd7 100644
---
a/sql/core/src/main/scala/org/apache/spark/sql/execution/streaming/checkpointing/OffsetSeq.scala
+++
b/sql/core/src/main/scala/org/apache/spark/sql/execution/streaming/checkpointing/OffsetSeq.scala
@@ -206,7 +206,8 @@ object OffsetSeqMetadata extends Logging {
STATE_STORE_ROW_CHECKSUM_ENABLED, PROTOBUF_EXTENSIONS_SUPPORT_ENABLED,
ENABLE_STREAMING_SOURCE_EVOLUTION,
STATEFUL_OPERATOR_ALWAYS_NULLABLE_OUTPUT,
- DROP_DUPLICATES_DETERMINISTIC_KEY_ORDER
+ DROP_DUPLICATES_DETERMINISTIC_KEY_ORDER,
+ REGEX_PATTERN_COST_ESTIMATE_VERSION
)
/**
@@ -278,7 +279,8 @@ object OffsetSeqMetadata extends Logging {
PROTOBUF_EXTENSIONS_SUPPORT_ENABLED.key -> "false",
ENABLE_STREAMING_SOURCE_EVOLUTION.key -> "false",
STATEFUL_OPERATOR_ALWAYS_NULLABLE_OUTPUT.key -> "false",
- DROP_DUPLICATES_DETERMINISTIC_KEY_ORDER.key -> "false"
+ DROP_DUPLICATES_DETERMINISTIC_KEY_ORDER.key -> "false",
+ REGEX_PATTERN_COST_ESTIMATE_VERSION.key -> "0"
)
def readValue[T](metadataLog: OffsetSeqMetadataBase, confKey:
ConfigEntry[T]): String = {
diff --git
a/sql/core/src/test/scala/org/apache/spark/sql/execution/datasources/FileSourceStrategySuite.scala
b/sql/core/src/test/scala/org/apache/spark/sql/execution/datasources/FileSourceStrategySuite.scala
index f38996adbd99..d5754d34a521 100644
---
a/sql/core/src/test/scala/org/apache/spark/sql/execution/datasources/FileSourceStrategySuite.scala
+++
b/sql/core/src/test/scala/org/apache/spark/sql/execution/datasources/FileSourceStrategySuite.scala
@@ -31,7 +31,7 @@ import org.apache.spark.paths.SparkPath.{fromUrlString => sp}
import org.apache.spark.sql.{execution, DataFrame, Row, SparkSession}
import org.apache.spark.sql.catalyst.InternalRow
import org.apache.spark.sql.catalyst.catalog.BucketSpec
-import org.apache.spark.sql.catalyst.expressions.{Expression, ExpressionSet}
+import org.apache.spark.sql.catalyst.expressions.{Expression, ExpressionSet,
StringRegexExpression}
import org.apache.spark.sql.catalyst.util
import org.apache.spark.sql.classic.Dataset
import org.apache.spark.sql.execution.{DataSourceScanExec, FileSourceScanExec,
SparkPlan}
@@ -606,6 +606,37 @@ class FileSourceStrategySuite extends SharedSparkSession {
checkDataFilters(Set.empty)
}
+ test("SPARK-60632: Filters on an aliased LIKE/RLIKE column are pushed into
the file scan") {
+ withTempPath { path =>
+ spark.range(20)
+ .selectExpr("CAST(id AS STRING) AS name", "CONCAT('v', id % 4) AS
part")
+ .write.partitionBy("part").parquet(path.getCanonicalPath)
+ val table = spark.read.parquet(path.getCanonicalPath)
+
+ def scanOf(df: DataFrame): FileSourceScanExec =
+ df.queryExecution.sparkPlan.collectFirst { case s: FileSourceScanExec
=> s }.get
+ def hasRegex(filters: Seq[Expression]): Boolean =
+ filters.exists(_.exists(_.isInstanceOf[StringRegexExpression]))
+
+ Seq(
+ "part RLIKE '^v1'" -> 1,
+ "part RLIKE 'v[12].*'" -> 2,
+ "part LIKE '_1' OR part = 'v2'" -> 2).foreach { case (pred,
numPartitions) =>
+ withClue(pred) {
+ val df = table.selectExpr("name", s"$pred AS p").where("p")
+ val scan = scanOf(df)
+ assert(hasRegex(scan.partitionFilters))
+ assert(scan.selectedPartitions.partitionCount == numPartitions)
+ checkAnswer(df, table.where(pred).selectExpr("name", "true AS p"))
+ }
+ }
+
+ val df = table.selectExpr("part", "name RLIKE '^1' AS p").where("p")
+ assert(hasRegex(scanOf(df).dataFilters))
+ checkAnswer(df, table.where("name RLIKE '^1'").selectExpr("part", "true
AS p"))
+ }
+ }
+
test(s"SPARK-44021: Test ${SQLConf.FILES_MAX_PARTITION_NUM.key} works as
expected") {
withSQLConf(SQLConf.FILES_MAX_PARTITION_BYTES.key -> "128MB") {
val files =
diff --git
a/sql/core/src/test/scala/org/apache/spark/sql/execution/streaming/OffsetSeqLogSuite.scala
b/sql/core/src/test/scala/org/apache/spark/sql/execution/streaming/OffsetSeqLogSuite.scala
index fd5530471c5c..5e7698c62d16 100644
---
a/sql/core/src/test/scala/org/apache/spark/sql/execution/streaming/OffsetSeqLogSuite.scala
+++
b/sql/core/src/test/scala/org/apache/spark/sql/execution/streaming/OffsetSeqLogSuite.scala
@@ -38,6 +38,20 @@ import org.apache.spark.util.{SerializableConfiguration,
Utils}
class OffsetSeqLogSuite extends SharedSparkSession {
import testImplicits._
+ test("SPARK-60632: regex pattern cost estimate is version 0 for old
checkpoints") {
+ val (_, offsetSeq) = readFromResource("offset-log-version-2.1.0")
+ val metadata = offsetSeq.metadataOpt.get
+
assert(!metadata.conf.contains(SQLConf.REGEX_PATTERN_COST_ESTIMATE_VERSION.key))
+ assert(OffsetSeqMetadata.readValue(
+ metadata, SQLConf.REGEX_PATTERN_COST_ESTIMATE_VERSION) == "0")
+ }
+
+ test("SPARK-60632: regex pattern cost estimate is version 1 for new
checkpoints") {
+ val metadata = OffsetSeqMetadata(
+ batchWatermarkMs = 0, batchTimestampMs = 0, spark.conf)
+
assert(metadata.conf.get(SQLConf.REGEX_PATTERN_COST_ESTIMATE_VERSION.key).contains("1"))
+ }
+
test("SPARK-59919: v1 and v2 metadata persist rebound stateful shuffle
partitions") {
withSQLConf(
SQLConf.SHUFFLE_PARTITIONS.key -> "10",
diff --git
a/sql/core/src/test/scala/org/apache/spark/sql/streaming/StreamingQueryManagerSuite.scala
b/sql/core/src/test/scala/org/apache/spark/sql/streaming/StreamingQueryManagerSuite.scala
index e42050e088a2..d74fadf5f070 100644
---
a/sql/core/src/test/scala/org/apache/spark/sql/streaming/StreamingQueryManagerSuite.scala
+++
b/sql/core/src/test/scala/org/apache/spark/sql/streaming/StreamingQueryManagerSuite.scala
@@ -24,13 +24,17 @@ import scala.concurrent.Future
import scala.util.Random
import scala.util.control.NonFatal
+import org.apache.hadoop.fs.Path
import org.scalatest.concurrent.PatienceConfiguration.Timeout
import org.scalatest.time.Span
import org.scalatest.time.SpanSugar._
import org.apache.spark.SparkException
import org.apache.spark.sql.{Dataset, Encoders}
+import org.apache.spark.sql.catalyst.plans.logical.{Filter, Project}
import
org.apache.spark.sql.execution.datasources.v2.StreamingDataSourceV2ScanRelation
+import org.apache.spark.sql.execution.streaming.checkpointing.{OffsetMap,
OffsetSeq, OffsetSeqLog,
+ OffsetSeqMetadata, OffsetSeqMetadataV2}
import org.apache.spark.sql.execution.streaming.runtime._
import org.apache.spark.sql.internal.SQLConf
import org.apache.spark.sql.streaming.util.BlockingSource
@@ -45,6 +49,29 @@ class StreamingQueryManagerSuite extends StreamTest {
override val streamingTimeout = 20.seconds
+ private def rewriteOffsetLogConf(
+ checkpoint: File)(f: Map[String, String] => Map[String, String]): Unit =
{
+ val offsetsPath = new File(checkpoint, "offsets").getCanonicalPath
+ val offsetLog = new OffsetSeqLog(spark, offsetsPath)
+ val (batchId, offsetSeq) = offsetLog.getLatest().getOrElse {
+ fail("Missing offset log entry")
+ }
+ val updatedMetadata = offsetSeq.metadataOpt.map {
+ case m: OffsetSeqMetadata => m.copy(conf = f(m.conf))
+ case m: OffsetSeqMetadataV2 => m.copy(conf = f(m.conf))
+ }
+ val updatedOffsetSeq = offsetSeq match {
+ case o: OffsetSeq =>
+ o.copy(metadataOpt =
updatedMetadata.map(_.asInstanceOf[OffsetSeqMetadata]))
+ case o: OffsetMap =>
+ o.copy(metadata =
updatedMetadata.map(_.asInstanceOf[OffsetSeqMetadataV2]).get)
+ }
+ val hadoopConf = spark.sessionState.newHadoopConf()
+ val batchFile = new Path(offsetsPath, batchId.toString)
+ assert(batchFile.getFileSystem(hadoopConf).delete(batchFile, false))
+ assert(offsetLog.add(batchId, updatedOffsetSeq))
+ }
+
override def beforeEach(): Unit = {
super.beforeEach()
assert(spark.streams.active.isEmpty)
@@ -60,6 +87,37 @@ class StreamingQueryManagerSuite extends StreamTest {
}
}
+ test("SPARK-60632: regex pattern cost estimate version 0 for old
checkpoints") {
+ withTempDir { checkpointDir =>
+ val input = MemoryStream[String]
+ // `NOT` caches whether its child is expensive, and both queries share
this plan.
+ val result = input.toDF().select($"value", !$"value".rlike("^1") as
"p").where($"p")
+
+ def run(data: String): Boolean = {
+ val query = result.writeStream
+ .format("noop")
+ .option("checkpointLocation", checkpointDir.getCanonicalPath)
+ .start()
+ try {
+ input.addData(data)
+ query.processAllAvailable()
+ // Whether the filter stays above the projection.
+
query.asInstanceOf[StreamingQueryWrapper].streamingQuery.lastExecution.optimizedPlan
+ .exists {
+ case Filter(_, _: Project) => true
+ case _ => false
+ }
+ } finally {
+ query.stop()
+ }
+ }
+
+ assert(!run("a"))
+ rewriteOffsetLogConf(checkpointDir)(_ -
SQLConf.REGEX_PATTERN_COST_ESTIMATE_VERSION.key)
+ assert(run("b"))
+ }
+ }
+
testQuietly("listing") {
val (m1, ds1) = makeDataset
val (m2, ds2) = makeDataset
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]