Total Outage Minutes per Service With Overlaps Merged
Several monitors can open an outage for the same service at once, so a service's outage records often overlap — one can even sit entirely inside another.
- Difficulty: Hard
- Topics: Window Functions, Dates
- Dialect: MySQL
- Problem: #343
Problem statement
Several monitors can open an outage for the same service at once, so a service's outage records often overlap — one can even sit entirely inside another. For the monthly availability report, the outages of a service are merged into windows: two outages belong to the same window when they overlap or touch (one ends at the minute the other starts). Outages still in progress (ended_at NULL) are ignored.
For each service with at least one finished outage, return the columns service, outage_windows (the number of merged windows) and downtime_minutes (the sum of the windows' lengths in minutes, end minus start), ordered by downtime_minutes descending, then service.
Tables
Table: Outage
| Column | Type |
|---|---|
| outage_id | int |
| service | varchar |
| started_at | datetime |
| ended_at | datetime |
Primary key: outage_id.
One row per outage opened by a monitor. Times are whole minutes; a finished outage ends after it starts. ended_at is NULL while it is still open.
Examples
Example 1
Outage
| outage_id | service | started_at | ended_at |
|---|---|---|---|
| 1 | payments-svc | 2025-04-10 10:00:00 | 2025-04-10 10:30:00 |
| 2 | payments-svc | 2025-04-10 10:20:00 | 2025-04-10 11:00:00 |
| 3 | payments-svc | 2025-04-10 10:40:00 | 2025-04-10 10:50:00 |
| 4 | payments-svc | 2025-04-10 14:00:00 | 2025-04-10 14:15:00 |
| 5 | search-svc | 2025-04-10 09:00:00 | 2025-04-10 09:45:00 |
| 6 | search-svc | 2025-04-10 09:45:00 | 2025-04-10 10:00:00 |
| 7 | auth-svc | 2025-04-10 08:00:00 | 2025-04-10 08:20:00 |
| 8 | auth-svc | 2025-04-10 12:00:00 | NULL |
| 9 | notify-worker | 2025-04-10 16:00:00 | NULL |
Output
| service | outage_windows | downtime_minutes |
|---|---|---|
| payments-svc | 2 | 75 |
| search-svc | 1 | 60 |
| auth-svc | 1 | 20 |
How to solve Total Outage Minutes per Service With Overlaps Merged
Summing each outage's length would count overlapping minutes twice, so the outages must first be merged into windows — the classic interval-merging problem. Sort a service's finished outages by started_at (and outage_id, so equal starts have a fixed order). Walking down that list, an outage starts a new window exactly when it begins after every earlier outage has ended; comparing with only the previous row is not enough, because a long outage can cover several later short ones. The running maximum MAX(ended_at) OVER (… ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING) is that "latest end so far", and the test started_at > prev_end uses > so an outage starting at the minute another ends joins it, as the statement says.
A running SUM of those 0/1 flags gives every outage the number of its window, so grouping by it yields each window's MIN(started_at) and MAX(ended_at); TIMESTAMPDIFF(MINUTE, …) measures it, and a final GROUP BY per service counts and sums the windows. In-progress outages are filtered out first and never extend anything.
The alternative finds the window boundaries directly: a start is a window start when no other outage covers it (b.started_at < s <= b.ended_at), an end is a window end when no outage continues past it (b.started_at <= e < b.ended_at). Starts and ends then pair up in order — the k-th start with the k-th end. It is quadratic per service; the window-function version needs one sort.
Reference solution (MySQL)
WITH done AS (
SELECT outage_id, service, started_at, ended_at FROM Outage WHERE ended_at IS NOT NULL
), marked AS (
SELECT outage_id, service, started_at, ended_at,
MAX(ended_at) OVER (PARTITION BY service ORDER BY started_at, outage_id
ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING) AS prev_end
FROM done
), grouped AS (
SELECT service, started_at, ended_at,
SUM(CASE WHEN prev_end IS NULL OR started_at > prev_end THEN 1 ELSE 0 END)
OVER (PARTITION BY service ORDER BY started_at, outage_id
ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS window_no
FROM marked
), windows AS (
SELECT service, window_no, MIN(started_at) AS w_start, MAX(ended_at) AS w_end
FROM grouped
GROUP BY service, window_no
)
SELECT service, COUNT(*) AS outage_windows, SUM(TIMESTAMPDIFF(MINUTE, w_start, w_end)) AS downtime_minutes
FROM windows
GROUP BY service
ORDER BY downtime_minutes DESC, serviceAnother way
WITH done AS (
SELECT service, started_at, ended_at FROM Outage WHERE ended_at IS NOT NULL
), starts AS (
SELECT DISTINCT a.service, a.started_at AS s FROM done a
WHERE NOT EXISTS (SELECT 1 FROM done b WHERE b.service = a.service AND b.started_at < a.started_at AND b.ended_at >= a.started_at)
), ends AS (
SELECT DISTINCT a.service, a.ended_at AS e FROM done a
WHERE NOT EXISTS (SELECT 1 FROM done b WHERE b.service = a.service AND b.started_at <= a.ended_at AND b.ended_at > a.ended_at)
), s2 AS (
SELECT service, s, ROW_NUMBER() OVER (PARTITION BY service ORDER BY s) AS k FROM starts
), e2 AS (
SELECT service, e, ROW_NUMBER() OVER (PARTITION BY service ORDER BY e) AS k FROM ends
)
SELECT s2.service, COUNT(*) AS outage_windows, SUM(TIMESTAMPDIFF(MINUTE, s2.s, e2.e)) AS downtime_minutes
FROM s2 JOIN e2 ON e2.service = s2.service AND e2.k = s2.k
GROUP BY s2.service
ORDER BY downtime_minutes DESC, s2.service← Longest Streak of Clean Deploys per Service · Gaps in the On-Call Rota →