[
https://issues.apache.org/jira/browse/SPARK-59063?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Uroš Bojanić resolved SPARK-59063.
----------------------------------
Fix Version/s: 4.4.0
Resolution: Fixed
Issue resolved by pull request 58362
[https://github.com/apache/spark/pull/58362]
> Use a byte-length guard in LikeSimplification for 'prefix%suffix'
> -----------------------------------------------------------------
>
> Key: SPARK-59063
> URL: https://issues.apache.org/jira/browse/SPARK-59063
> Project: Spark
> Issue Type: Improvement
> Components: SQL
> Affects Versions: 4.1.0
> Reporter: David Mollitor
> Priority: Minor
> Labels: pull-request-available
> Fix For: 4.4.0
>
>
> h2. Summary
> {{LikeSimplification}} rewrites {{col LIKE 'prefix%suffix'}} into a length
> guard plus {{{}StartsWith{}}}/{{{}EndsWith{}}}:
> {code:none}
> Length(col) >= numChars(prefix) + numChars(suffix)
> && StartsWith(col, prefix) && EndsWith(col, suffix)
> {code}
> The length guard exists only to reject strings too short to hold both the
> prefix and the
> suffix (for example, {{'a'}} must not match {{{}'a%a'{}}}). {{Length}} is
> {{{}numChars{}}}, an
> *O(N)* code-point scan of the input string, evaluated per row in the residual
> filter.
> I propose using {{OctetLength}} (byte length, the stored {{{}numBytes{}}},
> {*}O(1){*}) instead,
> with the threshold expressed in bytes:
> {code:none}
> OctetLength(col) >= numBytes(prefix) + numBytes(suffix)
> && StartsWith(col, prefix) && EndsWith(col, suffix)
> {code}
> h2. Why this is equivalent
> {{StartsWith}} and {{EndsWith}} already pin the prefix and suffix at
> code-point boundaries.
> For any string that already satisfies {{{}StartsWith(prefix) &&
> EndsWith(suffix){}}}, the byte-length floor accepts exactly the same strings
> as the code-point floor:
> {code:none}
> numBytes(s) >= numBytes(prefix) + numBytes(suffix)
> <=> numChars(s) >= numChars(prefix) + numChars(suffix)
> {code}
> so the rewrite is behavior-preserving, it accepts the same rows, while
> replacing an
> O(N) per-row character-count scan with an O(1) byte-length read.
> h2. Change
> In {{LikeSimplification}} (the {{startsAndEndsWith}} branch), emit
> {{OctetLength}} with a byte-count threshold instead of {{Length}} with a
> code-point threshold.
> {code:scala}
> // before
> Some(And(GreaterThanOrEqual(Length(input),
> Literal.create(prefix.codePointCount(0, prefix.length)
> + postfix.codePointCount(0, postfix.length))),
> And(StartsWith(...), EndsWith(...))))
> // after
> Some(And(GreaterThanOrEqual(OctetLength(input),
> Literal.create(UTF8String.fromString(prefix).numBytes
> + UTF8String.fromString(postfix).numBytes)),
> And(StartsWith(...), EndsWith(...))))
> {code}
> h2. User-facing change
> None. The rewrite accepts the same rows; only the internal guard expression
> changes
> ({{{}length{}}} -> {{{}octet_length{}}}).
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
