Zhilong Hong created FLINK-21915:
------------------------------------
Summary: Optimize Execution#finishPartitionsAndUpdateConsumers
Key: FLINK-21915
URL: https://issues.apache.org/jira/browse/FLINK-21915
Project: Flink
Issue Type: Sub-task
Components: Runtime / Coordination
Affects Versions: 1.13.0
Reporter: Zhilong Hong
Fix For: 1.13.0
Based on the scheduler benchmark {{PartitionReleaseInBatchJobBenchmark}}
introduced in FLINK-20612, we find that there's another procedure that has
O(N^2) computation complexity:
{{Execution#finishPartitionsAndUpdateConsumers}}.
Once an execution is finished, it will finish all its BLOCKING partitions and
update the partition info to all consumer vertices. The procedure can be
illustrated as the following pseudo code:
{code:java}
for all Execution in ExecutionGraph:
for all produced IntermediateResultPartition of the Execution:
for all consumer ExecutionVertex of the IntermediateResultPartition:
update or cache partition info{code}
This procedure has O(N^2) complexity in total.
Based on FLINK-21326, the consumed partitions are grouped if they are connected
to the same consumer vertices. Therefore, we can update partition info of the
entire ConsumedPartitionGroup in batch, rather than one by one. This will
decrease the complexity from O(N^2) to O(N).
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
