skip to content

In a reminder service storing millions of future one-shot jobs, why does a due-time index beat scanning every job to find what is due?

level: juniorimportance: must knowfreq 60%

answer

  1. most jobs are months away
  2. cost per poll versus backlog size
  3. sorted by fire time
  4. range query from the start
  5. poll interval sets lateness

basics

~20 s

A full scan touches every stored job on every poll, though almost all of them are far in the future. An index ordered by due time lets a poller read only rows already due, so cost tracks due work rather than total backlog.

solid answer

~40 s

A 'send later' store is mostly future work: at any moment only a tiny fraction of jobs is due. Scanning the whole table every second costs work proportional to *all* stored jobs on every poll, and it gets slower as the backlog grows even when nothing is due. An index on `due_at` (usually limited to `status = 'pending'`) keeps jobs sorted by fire time, so the poller runs a range query — `due_at <= now`, ordered by `due_at`, with a `LIMIT` — and touches only the due prefix. Cost now scales with the number of due jobs, the poll interval sets how late a job can fire, and fired jobs leave the pending set so the index stays small.

code

sql · 3 lines
sql
CREATE INDEX jobs_pending_due
  ON jobs (due_at)
  WHERE status = 'pending';

go deeper

for a junior

Remember the shape of the data: almost every stored job is in the future. Explain that an index sorted by due time turns 'find due jobs' into reading a short range.

for a middle

Walk through the poll query — pending filter, due_at range, ordering, batch limit — and explain why its cost tracks due work. Mention the write cost the index adds.

for a senior

Talk about the poll interval as a precision contract, catching up after outages in bounded batches, and keeping fired rows out of the hot index.

for a principal

Frame the single index as the first stage: say what breaks at larger scale, such as the hot 'now' end and several pollers, and what you would add next.

## The problem: data that is mostly in the future A **reminder** or **'send later' service** accepts requests such as 'email me at 09:00 next Tuesday' and stores each one as a **one-shot job**: a row with an ID, a payload and a **due time** (`due_at`). Its core loop is simple to state: *find every job whose due time has passed and hand it to a worker.* The difficulty is the shape of the data. At any moment the store may hold hundreds of millions of jobs, yet only a few thousand are due in the current second. Almost everything is waiting for a moment days or months away. The naive loop — read every row, compare its `due_at` with the clock, dispatch the due ones — has a cost proportional to the **total number of stored jobs**, paid on **every poll**. Illustratively, with 500 million pending jobs and a one-second poll, the scan would examine 500 million rows per second to find perhaps 20,000 due ones. It also gets worse as the business succeeds: more scheduled jobs means slower polls, even if the due rate is flat. ## What a due-time index does An **index** is a separate structure the database keeps sorted by one or more columns, typically a **B-tree**. An index on `due_at` keeps all jobs ordered by fire time, so 'every job due before now' is a **contiguous range at the start of the index**. The database can seek to the beginning and read forward until it meets the first row whose `due_at` is later than now, then stop. The cost of a poll now depends on how many jobs are due, plus a small logarithmic seek, instead of on how many jobs exist. In the example above, the poll touches roughly 20,000 index entries rather than 500 million rows. ```sql SELECT job_id, payload FROM jobs WHERE status = 'pending' AND due_at <= :now ORDER BY due_at LIMIT 500; ``` ## The polling loop 1. Read the clock and run the range query above for a bounded batch. 2. Claim the returned jobs so no other poller takes them (a separate topic in its own right). 3. Hand the claimed jobs to workers or a work queue. 4. Mark them fired, or move them out of the pending set. 5. If the batch was full, loop immediately; otherwise sleep until the next poll. The `LIMIT` matters: after an outage thousands of jobs may be overdue, and reading them in bounded batches keeps each transaction short. ## Keeping the index small and fast - **Index only pending work.** A partial index (`WHERE status = 'pending'`) or a separate pending table means fired and cancelled jobs stop costing index space. - **Remove or archive fired jobs.** Leaving billions of completed rows next to pending ones bloats storage and slows maintenance. - **Order by due time, oldest first.** Overdue jobs are served before newer ones, which bounds lateness fairly. - **Mind write cost.** Every insert, reschedule and cancel updates the index; that is the price paid for cheap reads. ## Precision versus cost The index makes each poll cheap, but the **poll interval** still decides how late a job can fire. | Poll interval | Worst-case extra lateness | Polls per poller per day | |---|---|---| | 1 second | about 1 s plus query and dispatch time | 86,400 | | 10 seconds | about 10 s plus query and dispatch time | 8,640 | | 60 seconds | about 60 s plus query and dispatch time | 1,440 | A reminder that appears 30 seconds late is usually acceptable; a one-time-password expiry is not. Choosing the interval is choosing a **precision contract**, and shorter intervals cost more queries even when nothing is due. ## Where this leads A single due-time index is the right first design and works for a long time. At very large scale it develops its own problems — every write and every poll hits the same 'now' end of the index, and several pollers must not dispatch the same job — which is why larger systems add **atomic claiming**, **time-bucketed partitions with sharded pollers**, or an **in-memory timing wheel** in front of the store. A **delay queue**, which releases each item only once its delivery time arrives, is the same idea packaged as a queue: a due-time index is effectively a durable, queryable delay queue.

  • What is a delay queue, and how does it differ from an ordinary FIFO queue?
    A delay queue keeps each item hidden until its delivery time and then releases it, so consumers see items in due-time order. A FIFO queue releases items in arrival order as soon as they are enqueued. A due-time indexed table behaves like a durable delay queue that you can also query, edit and cancel.
  • Why limit the index to pending jobs?
    Fired and cancelled jobs will never be polled again, yet in a full index they still take space and add maintenance cost, and over time they vastly outnumber pending ones. A partial index on `status = 'pending'`, or a separate pending table, keeps the structure the poller reads proportional to live work.
  • Once polling uses the index, what bounds how late a job can fire?
    Mainly the poll interval, plus the time to run the query, claim the batch and dispatch it. Under load, backlog adds more: if more jobs are due than workers can handle, jobs wait in line. Shorter intervals improve precision but cost more queries even when nothing is due.

A due-time index is like a desk calendar: to see what is due today you open today's page, instead of re-reading every note you have ever written.

saying these in an interview costs you the question

  • Scanning the whole jobs table every second is fine; databases are fast.
  • An index on the job ID is enough to find due jobs quickly.
  • With an index, polling every millisecond costs nothing extra.
  • Fired jobs can stay in the pending index forever at no cost.
  • A due-time index makes every job fire exactly at its due time.