Hotstar: 90th-Percentile Video Start Time by CDN
Averages hide the viewers who wait longest for a stream to start, so Hotstar's video team reports the 90th percentile of start-up time per CDN.
- Difficulty: Hard
- Topics: Window Functions, Aggregation
- Dialect: MySQL
- Problem: #718
Problem statement
Averages hide the viewers who wait longest for a stream to start, so Hotstar's video team reports the 90th percentile of start-up time per CDN. Only successful starts (outcome = ok) with a measured startup_ms count; failed starts are tracked elsewhere.
Use the nearest-rank definition: sort a CDN's n start-up times ascending; the 90th percentile is the value at position ⌈0.9 × n⌉ (positions counted from 1). Return cdn, starts (= n) and p90_ms for every CDN with at least one counted start, ordered by cdn.
A practice scenario set at Hotstar: the tables and data are invented, and this is not a question from, or endorsed by, Hotstar.
Tables
Table: VideoStart
| Column | Type |
|---|---|
| attempt_id | int |
| cdn | varchar |
| startup_ms | int |
| outcome | enum(ok, failed) |
Primary key: attempt_id.
One row per attempt to start a stream. startup_ms is the time to first frame, NULL when it was not measured.
Examples
Example 1
VideoStart
| attempt_id | cdn | startup_ms | outcome |
|---|---|---|---|
| 1 | EdgeNorth | 800 | ok |
| 2 | EdgeNorth | 1200 | ok |
| 3 | EdgeNorth | 900 | ok |
| 4 | EdgeNorth | 1500 | ok |
| 5 | EdgeNorth | 1100 | ok |
| 6 | EdgeNorth | 950 | ok |
| 7 | EdgeNorth | 1000 | ok |
| 8 | EdgeNorth | 1300 | ok |
| 9 | EdgeNorth | 2400 | ok |
| 10 | EdgeNorth | 700 | ok |
| 11 | EdgeNorth | NULL | failed |
| 12 | SkyRelay | 400 | ok |
| 13 | SkyRelay | 600 | ok |
| 14 | SkyRelay | 500 | ok |
| 15 | SkyRelay | NULL | ok |
| 16 | MetroCache | 3000 | failed |
| 17 | EdgeSouth | 900 | ok |
Output
| cdn | starts | p90_ms |
|---|---|---|
| EdgeNorth | 10 | 1500 |
| EdgeSouth | 1 | 900 |
| SkyRelay | 3 | 600 |
How to solve Hotstar: 90th-Percentile Video Start Time by CDN
A percentile is a positional statistic, so the plan is: keep the counted starts, sort each CDN's values, and pick the value at a computed position. ROW_NUMBER() over startup_ms per CDN numbers the values 1…n, and COUNT(*) OVER (PARTITION BY cdn) repeats n on every row so the position can be compared in the same row. The nearest-rank position is ⌈0.9 n⌉, written CEIL(9 * n / 10) so the arithmetic is exact: 10 values → position 9 (EdgeNorth's 1500, not the 2400 outlier), 3 values → position 3, 1 value → position 1.
The filter must happen first: a failed start or an unmeasured one would otherwise take a position and shift the answer, and a CDN with only failures (MetroCache) must vanish. Ties in startup_ms do not matter — equal values are interchangeable at any position — but attempt_id is added to the order so the numbering itself is deterministic.
The first alternative uses the definition directly: the percentile is the smallest value v such that at least 90% of the values are ≤ v (count(≤ v) * 10 >= 9n), found with correlated counts. The second picks the row whose position is the first to reach 90% with integer comparisons. The window version is one sort per CDN; the correlated one is quadratic.
Reference solution (MySQL)
WITH counted AS (
SELECT cdn, startup_ms,
ROW_NUMBER() OVER (PARTITION BY cdn ORDER BY startup_ms, attempt_id) AS pos,
COUNT(*) OVER (PARTITION BY cdn) AS n
FROM VideoStart
WHERE outcome = 'ok' AND startup_ms IS NOT NULL
)
SELECT cdn, n AS starts, startup_ms AS p90_ms
FROM counted
WHERE pos = CEIL(9 * n / 10)
ORDER BY cdnAnother way
WITH ok AS (SELECT cdn, startup_ms FROM VideoStart WHERE outcome = 'ok' AND startup_ms IS NOT NULL),
sizes AS (SELECT cdn, COUNT(*) AS n FROM ok GROUP BY cdn)
SELECT z.cdn, z.n AS starts,
(SELECT MIN(a.startup_ms) FROM ok a
WHERE a.cdn = z.cdn
AND (SELECT COUNT(*) FROM ok b WHERE b.cdn = a.cdn AND b.startup_ms <= a.startup_ms) * 10 >= 9 * z.n) AS p90_ms
FROM sizes z
ORDER BY z.cdnAnother way
WITH counted AS (
SELECT cdn, startup_ms,
ROW_NUMBER() OVER (PARTITION BY cdn ORDER BY startup_ms) AS pos,
COUNT(*) OVER (PARTITION BY cdn) AS n
FROM VideoStart WHERE outcome = 'ok' AND startup_ms IS NOT NULL
)
SELECT cdn, MAX(n) AS starts, MAX(CASE WHEN pos * 10 >= 9 * n AND (pos - 1) * 10 < 9 * n THEN startup_ms END) AS p90_ms
FROM counted
GROUP BY cdn
ORDER BY cdn← Hotstar: Viewers Lost During Each Rain Delay · Hotstar: Commentary Feed Switches and Final Language per Viewer →