Skip to content
The Data EngineeringThe Data EngineeringBeta
About
Main content

DAG-aware scheduling

Why can no number of machines beat the critical path, and how can adding machines slow a job?

Many jobs are (directed acyclic graphs): tasks with dependencies, where a task can start only after its predecessors finish. The (total time from the first task start to the last finish) is bounded below by the , which is the longest chain of dependent tasks. No number of machines can beat it.

The critical path is 9 minutes. With 2 machines or with 200 machines, the job cannot finish in under 9 minutes. C has 2 minutes of slack (it can start 2 minutes late without delaying D). Tasks A, B and D have zero slack: delaying any of them delays the whole job.

This is Amdahl's law (the serial part of a job limits the speedup, however many workers you add) restated as graph structure, the work-span bound of a query runtime applied to whole jobs. The serial fraction is literally a path through the dependency graph. So the useful priority key is not task size but remaining path length, with slack as its complement.

Two results are worth carrying:

  • Graham's bound. Any greedy list schedule (never leave a machine idle if a task is ready) is within 2× of optimal. The sophistication ceiling is low, and critical-path ordering is close to free.
  • Graham's anomaly. Under list scheduling, adding machines, shortening a task, or relaxing a dependency can lengthen the makespan. This non-monotonicity is real. It is not an implementation bug. It is why "we added nodes and it got slower" is sometimes literally true, not a measurement error.

The same mechanism appears at three scales: operator stages inside one query, tasks inside one job, and jobs inside a pipeline graph. Count it once: critical-path prioritization is scale-free.

Schedule by remaining path, not by task size.