David Mollitor created SPARK-59063:
--------------------------------------
Summary: 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
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]
