Median Delivery Time of Each Restaurant — SQL Hard Problem

Problem statement

A food-delivery app records how many minutes each delivered order took. A cancelled order has minutes NULL.

For every restaurant with at least one timed order, return restaurant and median_minutes, the median of its non-NULL minutes. Sort a restaurant's times: with an odd number of them the median is the middle value; with an even number it is the average of the two middle values, so it can end in .5. Equal times count separately (25, 25, 32, 41 has median 28.5). NULL times are ignored entirely, and a restaurant whose orders were all cancelled does not appear. Return the rows in any order.

MySQL has no MEDIAN function — compute it from the sorted positions.

Tables

Table: Delivery

Primary key: order_id.

One row per order; minutes is the delivery time, or NULL for a cancelled order.

Examples

Example 1

Delivery

Output

How to solve Median Delivery Time of Each Restaurant

A median is defined by positions in sorted order, so the plan is to give each value its position and keep the middle one or two.

Drop the NULLs first: a cancelled order has no time and must not count towards the size. Then two window functions over each restaurant do the bookkeeping: ROW_NUMBER() OVER (PARTITION BY restaurant ORDER BY minutes) numbers the sorted times 1…n, and COUNT(*) OVER (PARTITION BY restaurant) puts n on every row. For n values the middle positions are ⌊(n+1)/2⌋ and ⌊(n+2)/2⌋: for n = 5 both are 3, for n = 4 they are 2 and 3. Keeping the rows at those positions and taking AVG(minutes) per restaurant returns the single middle value when n is odd and the mean of the two middles when n is even. Ties in minutes make the order among equal values arbitrary, but they are equal, so the average does not change.

rn BETWEEN n/2 AND n/2 + 1 selects the same positions, because / is decimal division in MySQL.

The window-free version counts instead of numbering: a value v is a middle value when at most n/2 values are below it and at most n/2 above it. With an even count the candidates are exactly the two middle values (possibly equal), so AVG(DISTINCT minutes) over the candidates is the median. That self join compares every pair inside a restaurant — quadratic — while the window version is a sort per restaurant.

Reference solution (MySQL)

WITH ranked AS (
  SELECT restaurant, minutes,
         ROW_NUMBER() OVER (PARTITION BY restaurant ORDER BY minutes) AS rn,
         COUNT(*) OVER (PARTITION BY restaurant) AS cnt
  FROM Delivery
  WHERE minutes IS NOT NULL
)
SELECT restaurant, AVG(minutes) AS median_minutes
FROM ranked
WHERE rn IN (FLOOR((cnt + 1) / 2), FLOOR((cnt + 2) / 2))
GROUP BY restaurant

Another way

SELECT restaurant, AVG(minutes) AS median_minutes
FROM (
  SELECT restaurant, minutes,
         ROW_NUMBER() OVER (PARTITION BY restaurant ORDER BY minutes) AS rn,
         COUNT(minutes) OVER (PARTITION BY restaurant) AS cnt
  FROM Delivery WHERE minutes IS NOT NULL
) t
WHERE rn BETWEEN cnt / 2 AND cnt / 2 + 1
GROUP BY restaurant

Another way

SELECT restaurant, AVG(DISTINCT minutes) AS median_minutes
FROM (
  SELECT a.restaurant, a.minutes
  FROM Delivery a
  JOIN Delivery b ON b.restaurant = a.restaurant AND b.minutes IS NOT NULL
  WHERE a.minutes IS NOT NULL
  GROUP BY a.order_id, a.restaurant, a.minutes
  HAVING SUM(b.minutes < a.minutes) <= COUNT(*) / 2 AND SUM(b.minutes > a.minutes) <= COUNT(*) / 2
) middle
GROUP BY restaurant