Peak parallel batch workers

SQL data engineering interview problem. Difficulty: advanced. Pattern: CTEs. About 18 minutes. Part of the Pro drill bank.

A team runs batch jobs and wants to know how many workers (machines) they need so that no 2 jobs that run at the same time share a worker. That number is the largest number of jobs running at the same moment. Given batch_jobs with job_id, start_time and end_time, return 1 column, peak_workers, the maximum number of jobs that run in parallel at any time. A job counts as running from its start time up to, but not including, its end time. A job that ends at 11:00 and another that starts at 11:00 do not overlap.

Requirements

• Find the highest number of jobs that are active at the same time.
• A job is active from start_time (included) until end_time (not included).
• Return 1 row with the column peak_workers.

Constraints

• The table is batch_jobs.
• A common method: turn each job into 2 events, +1 at its start and -1 at its end, sort the events by time, and take a running sum.
• At the same timestamp, process the -1 (end) before the +1 (start), so a job that ends and another that starts at the same moment do not count as overlapping.

Examples

Input: batch_jobs (morning cluster) job_id | start_time | end_time 1 | 2024-01-01 09:00:00 | 2024-01-01 11:00:00 2 | 2024-01-01 10:00:00 | 2024-01-01 12:00:00 3 | 2024-01-01 10:30:00 | 2024-01-01 11:30:00 Output: peak_workers | 3 | Why this passes: All 3 jobs overlap between 10:30 and 11:00, so peak concurrency is 3.

Topics: lakebench, sql, concurrency, sweep.

More SQL interview questions · All interview problems · Learn data engineering