[ 
https://issues.apache.org/jira/browse/SPARK-61449?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
 ]

Jungtaek Lim resolved SPARK-61449.
----------------------------------
    Resolution: Won't Do

> Start V4 stream-stream join eviction scans after the previous cutoff when the 
> eviction column is not late-filtered
> ------------------------------------------------------------------------------------------------------------------
>
>                 Key: SPARK-61449
>                 URL: https://issues.apache.org/jira/browse/SPARK-61449
>             Project: Spark
>          Issue Type: Improvement
>          Components: Structured Streaming
>    Affects Versions: 4.3.0, 5.0.0, 4.4.0
>            Reporter: Jungtaek Lim
>            Priority: Major
>
> With state format V4 ({{spark.sql.streaming.join.stateFormatVersion=4}}, 
> opt-in), a stream-stream join keeps a timestamp index for each input and 
> evicts state by scanning that index up to the batch's cutoff. When it can 
> prove that every entry at or below the previous batch's cutoff is already 
> gone, it starts the scan after that cutoff. Otherwise it seeks to the first 
> entry of the index and scans from there, in every batch and partition.
> That proof needs late filtering. A scan may skip entries at or below the 
> previous cutoff only if late filtering keeps every newly admitted row above 
> it. Late filtering checks only an input's own event time. When the input is 
> evicted on any other column, a row admitted in this batch can carry a value 
> at or below the previous cutoff. That row is evictable now, and an outer join 
> must emit it now; a scan that starts at the previous cutoff would skip it for 
> good. So V4 scans from the start for every input whose eviction column is not 
> its own late-filtered event time. The rule exists to keep results correct, 
> and this ticket keeps the results the same.
> h3. Shapes that scan from the start
> - *Today, in 4.3.0 and later.* Take a left outer join on {{lk = rk AND lt = 
> rt}} with a watermark only on {{rt}}. The left state is evicted on {{lt}} by 
> the {{rt}} watermark, but the left input has no watermark, so nothing 
> late-filters {{lt}}. Every batch scans the left index from its first entry.
> - *With the open stream-stream join correctness changes,* more inputs are 
> evicted on columns that late filtering does not check:
>   - SPARK-61344, a range end: for {{leftKey = rightKey AND rightTime BETWEEN 
> leftTime AND expiry}}, the left state is now evicted on {{expiry}}.
>   - SPARK-61345, a crossed equality key: for {{la = ra AND lb = rb}} with 
> watermarks on {{la}} and {{rb}}, the left state is now evicted on {{lb}}.
>   - SPARK-61347, an input without its own watermark that is now evicted 
> through a range bound.
>   Before those changes, these inputs got a bounded scan only because they 
> were evicted on their event time with a cutoff derived from another column or 
> watermark, which could evict a row before its match arrived. Inputs without a 
> watermark were not evicted at all.
> h3. What it costs
> Each batch and partition does one seek to the first entry of the index and 
> iterates up to the cutoff. The live entries it visits are exactly the rows it 
> evicts. The extra work is stepping over the deletions from earlier evictions 
> that RocksDB has not compacted yet. That work grows with the number of 
> deletions since the last compaction of that key range, not with the rows 
> evicted in the batch. It has not been measured.
> h3. What a narrower scan start would need
> A scan can safely start after the lower of two values, and it finds the same 
> rows:
> - the previous cutoff;
> - the smallest timestamp indexed since the previous eviction, minus 1.
> Rows indexed before the previous eviction are above the previous cutoff, 
> because that eviction removed everything at or below it. Rows indexed since 
> then are at or above their own minimum.
> Doing this needs:
> - *Tracking in the state manager.* {{SymmetricHashJoinStateManagerV4}} 
> records the smallest timestamp it adds to the index in the current batch. 
> This can stay in memory: within a task, appends happen before eviction, and a 
> retried task re-appends its rows.
> - *The previous cutoff for these inputs.* Today the eviction predicate 
> carries a scan start only when it is safe on its own. For these inputs it 
> would also have to carry the previous cutoff, which the state manager lowers 
> with its minimum. That is the cutoff at the late-events watermark, without 
> the current check that it is at or below that watermark. The predicate and 
> helper code for range bounds, equality keys and inputs without a watermark 
> all need this.
> - *Restarts that reproduce the previous cutoff exactly.* In a batch where the 
> previous cutoff cannot be recomputed exactly, the scan must start from the 
> beginning. Examples are the first batch after restoring a checkpoint with 
> older join watermark semantics (the open changes already scan from the start 
> there), and a change of session time zone when the bound adds whole days.
> - *No change elsewhere.* The first batch of a query and legacy mode 
> ({{spark.sql.streaming.statefulOperator.allowMultiple=false}}) keep scanning 
> from the start.
> - *Tests:*
>   - for each shape above, a row admitted with a value below the previous 
> cutoff is still evicted, and an outer join emits it;
>   - the scan start is lowered by the smallest indexed timestamp;
>   - a benchmark compares eviction time per batch against the full scan.
> h3. Why this is not part of the correctness changes
> It changes only how much of the index a batch scans, not which rows are 
> evicted or emitted. It touches the eviction predicates for three kinds of 
> bound and the V4 state manager, and its benefit depends on RocksDB 
> compaction, which needs a measurement first. The correctness changes keep the 
> base branch's scan-from-the-start rule for these inputs, so their results are 
> right without it.
> h3. How the affected versions were checked
> I read the code with {{git show <ref>:<path>}}, read-only, at these refs:
> ||Ref||Version||Commit||
> |v3.5.9|3.5.9|7c14a3c28b1|
> |v4.0.5|4.0.5|b472a3aa3c4|
> |v4.1.4|4.1.4|45b9b176e6e|
> |v4.2.1|4.2.1|61761839608|
> |v4.3.0|4.3.0|98bc0212c94|
> |branch-4.x|4.4.0-SNAPSHOT|106f81f8891|
> |master|5.0.0-SNAPSHOT|f35395086c9|
> - *3.5.9, 4.0.5 and 4.1.4* have no V4. {{SQLConf}} accepts only state formats 
> 1 to 3 for {{spark.sql.streaming.join.stateFormatVersion}}, and there is no 
> {{SymmetricHashJoinStateManagerV4}}.
> - *4.2.1* has V4, but its conf documentation says "Version 4 is under 
> development and only available for testing." There, every eviction scan 
> starts at the late-events watermark, and there is no scan-from-the-start 
> rule. So it is excluded both as not a supported feature and as not having 
> this behavior.
> - *4.3.0, branch-4.x and master* document V4 as a state format that 
> "optimizes watermark-based eviction". 
> {{StreamingSymmetricHashJoinHelper.getStateWatermarkPredicates}} sets the 
> previous-scan bound only when the input's own late-filtered event time is the 
> eviction key, or, for value eviction, only when the derived cutoff is at or 
> below the late-events watermark, with the comment "V4 must scan from the 
> beginning". Otherwise the bound is {{None}}, and 
> {{TsWithKeyTypeStore.scanEvictedKeys}} then has no start key and seeks from 
> the first entry of the index. The test "V4 eviction includes newly admitted 
> rows below the previous bound" pins that rule.
> So the from-start scan described above exists in 4.3.0, 4.4.0 and 5.0.0.



--
This message was sent by Atlassian Jira
(v10.3.26#10030026)

---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Reply via email to