[
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]