Jungtaek Lim created SPARK-61449:
------------------------------------

             Summary: 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: 5.0.0
            Reporter: Jungtaek Lim


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