Skip to content
The Data EngineeringThe Data EngineeringBeta
About
Main content

From how to which

Why does scheduling decide who waits rather than how work runs, and which number does it always lack?

From "how" to "which"

Everything before this mechanism in a data system answers how does this work get done: how a query is executed, how data is stored, how copies are kept consistent. This mechanism answers a different question: which work gets done, and which waits. That is a categorical break. It shows up as three changes at once.

What appears: rivalry. A resource is indivisible in time. Two tasks cannot both hold the same core, the same slot, or the same memory grant at the same instant. Earlier mechanisms could improve things by being cleverer about the work in front of them (a better index, a faster format). A scheduler cannot improve anything in aggregate. It can only decide who is hurt. Scheduling is the first area whose subject matter is other people's jobs.

A scheduler cannot make an answer wrong. It can only change when the answer arrives, or whether it arrives at all. So the quantity that matters is no longer or durability. It is the distribution of waiting time. And waiting time is not a property of a job. It is a property of the interaction between jobs. This is the first area where a system's performance depends on work that did not exist yet when the system made its commitment.

What becomes the governing constraint: information. Queueing theory has optimal policies:

  • SJF (shortest-job-first) minimizes the mean wait.
  • SRPT (shortest-remaining-processing-time) minimizes the mean .

Both need the job's as an input. That is exactly the one number you do not have when the job is admitted. Every real scheduling mechanism here is a workaround for that missing number. You can:

  1. estimate it (cost-based routing);
  2. infer it by watching (multi-level feedback , short-query lanes);
  3. force the user to declare it (deadlines, pools, quotas, limits);
  4. or refuse to need it (, fair share).

A database query optimizer already estimates how expensive a query plan will be, using statistics about the data. Here the same kind of estimate decides whose plan runs first. So a wrong estimate now has a victim: some other job waits.