David Mollitor created SPARK-59354:
--------------------------------------
Summary: Derive a length guard from LIKE patterns with '_'
wildcards
Key: SPARK-59354
URL: https://issues.apache.org/jira/browse/SPARK-59354
Project: Spark
Issue Type: Improvement
Components: SQL
Affects Versions: 4.1.0
Reporter: David Mollitor
h3. What
A {{LIKE}} pattern containing the {{_}} wildcard (which matches exactly one
code point) is not
simplified today – {{LikeSimplification}} leaves it as a full per-row regex.
Since {{_}}
constrains length, this derives a code-point {*}length guard{*}:
* no {{%}} -> exact length: {{col LIKE 'a_c'}} implies {{{}Length(col) = 3{}}};
* with {{%}} -> lower bound: {{col LIKE 'a_b%'}} implies {{{}Length(col) >=
3{}}};
where N is the number of non-{{{}%{}}} code points in the pattern.
When the pattern has no literals (only {{{}_{}}}/{{{}%{}}}) the guard is
exactly equivalent, so it
*replaces* the {{{}LIKE{}}}:
{code:java}
col LIKE '___' ==> Length(col) = 3
col LIKE '_%' ==> Length(col) >= 1
{code}
When the pattern also has literals, the guard is only a necessary condition, so
the exact
{{LIKE}} is kept as the residual:
{code:java}
col LIKE 'a_c' ==> Length(col) = 3 && (col LIKE 'a_c')
col LIKE 'a_b%' ==> Length(col) >= 3 && (col LIKE 'a_b%')
{code}
h3. Why are the changes needed?
{{Length(col)}} is an O(n) check that fails fast before the regex, so short
strings are
rejected (and, for the literal-free cases, the regex is eliminated entirely).
This is a
CPU/short-circuit improvement.
h3. Correctness
* {{Length}} is a *code-point* count – the right measure for {{{}_{}}}, which
matches one code
point regardless of its UTF-8 byte width (so a byte length would be wrong here).
* The rewrite is valid in every context (not just predicates) and needs no
collation gate:
{{Length(col) = N}} agrees with {{col LIKE '...'}} even on {{null}} (both are
null-intolerant),
and for the literal case {{And(guard, LIKE)}} is just the {{LIKE}} conjoined
with one of its necessary conditions, so it is equivalent to the original
{{LIKE}} in all cases.
* Assumes each pattern token consumes exactly one input code point, which
holds for Spark's {{LIKE}} (Java-regex simple, 1:1 case folding). Idempotency
under the fixed-point optimizer batch is maintained via a {{TreeNodeTag}} on
the residual {{{}Like{}}}.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
