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]