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:
This procedure has O(N^2) complexity in total.
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).