[
https://issues.apache.org/jira/browse/FLINK-30544?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17654886#comment-17654886
]
Lijie Wang commented on FLINK-30544:
------------------------------------
Done via master d9b8463da4181de48f62b4a551d11672ba313db2
> Speed up finding minimum watermark across all channels by introducing
> heap-based algorithm
> ------------------------------------------------------------------------------------------
>
> Key: FLINK-30544
> URL: https://issues.apache.org/jira/browse/FLINK-30544
> Project: Flink
> Issue Type: Improvement
> Components: Runtime / Task
> Reporter: Lijie Wang
> Assignee: Lijie Wang
> Priority: Major
> Labels: pull-request-available
> Fix For: 1.17.0
>
>
> Currently, every time a task receives a watermark, it tries to update the
> minimum watermark.Currently, we use the traversal algorithm to find the
> minimum watermark across all channels(see
> [StatusWatermarkValue#findAndOutputNewMinWatermarkAcrossAlignedChannels|https://github.com/apache/flink/blob/master/flink-streaming-java/src/main/java/org/apache/flink/streaming/runtime/watermarkstatus/StatusWatermarkValve.java#:~:text=private%20void-,findAndOutputNewMinWatermarkAcrossAlignedChannels,-(DataOutput%3C%3F%3E]
> for details), and the time complexity is O(N), where N is the number of
> channels.
> We can optimize it by introducing a heap-based algorthim, reducing the time
> complexity to O(log(N))
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
