[FLINK-22773] Optimize the construction of pipelined regions

• Type: Sub-task
• Status: Closed
• Priority: Major
• Resolution: Done
• Affects Version/s: 1.13.0
• Fix Version/s: 1.14.0
• Component/s: Runtime / Coordination
• Labels: pull-request-available
• Assignee: Zhilong Hong
• Reporter: Zhilong Hong
• Created: 25/May/21 11:07
• Updated: 11/Aug/21 10:17
• Resolved: 11/Aug/21 10:17

Description

During the initialization of DefaultExecutionTopology, pipelined regions will be computed for scheduling. Currently the complexity of this procedure is O(N^2):
 

for all vertices in the topology:
  for all consumed results of the vertex:
    if the consumed result is reconnectable:
      merge the current region with its producer region

One possible solution is mentioned in FLINK-17330.

If we can optimize this procedure from O(N^2) to O(N), it will speed up the initialization of SchedulerNG, and accelerate the submission of a new job, especially for OLAP jobs.

Issue Links

• is related to: FLINK-17330 Avoid scheduling deadlocks caused by cyclic input dependencies between regions
• links to: GitHub Pull Request #16688