David Mollitor created SPARK-59541:
--------------------------------------
Summary: Coalesce OR-connected equality and IN predicates on the
same column into a single IN
Key: SPARK-59541
URL: https://issues.apache.org/jira/browse/SPARK-59541
Project: Spark
Issue Type: Improvement
Components: SQL
Affects Versions: 4.1.0
Reporter: David Mollitor
h2. Background
Spark leaves OR-connected membership tests on the same column un-merged:
* {{x = 1 OR x = 2 OR x = 3}} stays a nested {{Or(EqualTo, ...)}} - it is
never folded to {{{}IN{}}}.
* {{x IN (1, 2) OR x IN (3, 4)}} stays two separate {{In}} nodes.
* {{x = 1 OR x IN (2, 3)}} stays {{{}Or(EqualTo, In){}}}.
{{OptimizeIn}} only processes a single {{In}} node at a time, so none of these
are combined today.
h2. Proposal
A new logical optimizer rule {{CombineDisjunctiveInPredicates}} that coalesces
OR-connected {{EqualTo}} and {{In}} disjuncts on the same deterministic,
non-foldable subject into one {{{}In{}}}, letting the adjacent {{OptimizeIn}}
finish the job (dedup, single-element -> {{{}EqualTo{}}}, large list ->
{{{}InSet{}}}). {{EqualTo(x, c)}} is treated as a one-element membership
{{{}In(x, [c]){}}}. Examples:
* {{x = 1 OR x = 2 OR x = 3}} -> {{x IN (1, 2, 3)}}
* {{x IN (1, 2) OR x IN (3, 4)}} -> {{x IN (1, 2, 3, 4)}}
* {{x = 1 OR x IN (2, 3)}} -> {{x IN (1, 2, 3)}}
The rule runs immediately before {{OptimizeIn}} and is gated by an internal
flag {{spark.sql.optimizer.combineDisjunctiveInPredicates.enabled}} (default
true).
h2. Why are the changes needed
A single {{{}In{}}}/{{{}InSet{}}} is a strictly more optimized representation
than an OR chain of the same predicates:
* Single subject evaluation: {{In.eval}} evaluates the subject expression
once; an {{Or}} of N {{{}EqualTo{}}}/{{{}In{}}} nodes re-evaluates it N times.
* Set dispatch: once merged and above the conversion threshold, {{OptimizeIn}}
turns the {{In}} into {{{}InSet{}}}, which uses a {{switch}} (compact ints) -
dispatch that OR-connected nodes never get.
* Avoids the whole-stage-codegen method-size cliff: a very large OR chain
overflows the generated method-size limit and falls back to interpreted
execution; the merged {{InSet}} stays compact.
Microbenchmark over a {{Long}} column, 10M rows, non-matching values (worst
case), rule off (raw OR) vs rule on:
||N||raw OR (ms)||merged IN/InSet (ms)||
|20|39|40|
|100|148|54|
|500|65142 (interpreted fallback)|82|
Parity at small N and a large win as N grows.
h2. Correctness
* Determinism guard (the sole correctness gate): the subject must be
deterministic - {{In}} evaluates it once, the OR form once per disjunct - so
{{rand() = 1 OR rand() = 2}} is left unchanged.
* Three-valued logic: {{x IN A OR x IN B}} is equivalent to {{x IN (A union
B)}} under nulls (both NULL when the subject is NULL; both FALSE when non-null
and unmatched with no null member; both NULL when unmatched with a null
member), matching {{{}In.eval{}}}.
* Exclusions: {{EqualNullSafe}} (<=>) is never matched; structs are excluded
on subject and members; foldable-only "subjects" are not grouped (avoids the
degenerate {{1 IN (x, y)}} from {{{}x = 1 OR y = 1{}}}).
* Fixed-point safety: fires only on groups with >= 2 candidate disjuncts,
collapsing to one {{In}} that cannot re-match; returns the {{Or}} unchanged
otherwise.
h2. Caveat: Parquet row-group pruning precision
Merging a large (> {{{}spark.sql.optimizer.inSetConversionThreshold{}}})
OR-of-equalities into {{IN}} > {{InSet}} can make Parquet row-group pruning
coarser: a raw OR-of{{{}EqualTo{}}} pushes as {{FilterApi.or(eq, ...)}}
(per-value), whereas the merged form pushes as {{FilterApi.in}} (a min/max
envelope over the set). The internal flag allows disabling the rule where this
matters.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
