Reservation Holders to Notify After Today's Returns
Each morning the library processes yesterday's returns: every returned copy of a book goes to the next member in that book's reservation queue.
- Difficulty: Hard
- Topics: Window Functions, Joins, Subqueries
- Dialect: MySQL
- Problem: #92
Problem statement
Each morning the library processes yesterday's returns: every returned copy of a book goes to the next member in that book's reservation queue. The queue holds only active holds, in the order they were placed; two holds placed at the same moment are ordered by hold_id. If a book had three copies returned, the first three members in its queue are notified; if it had more returns than holds, everyone in its queue is.
Return book_id, queue_position (1 for the head of that book's active queue) and member_id of every member to notify, ordered by book_id, then queue_position.
Tables
Table: holds
| Column | Type |
|---|---|
| hold_id | int |
| book_id | int |
| member_id | int |
| placed_at | datetime |
| status | enum(active, collected, cancelled) |
Primary key: hold_id.
One row per reservation. Only active holds are still waiting for a copy.
Table: copy_returns
| Column | Type |
|---|---|
| return_id | int |
| book_id | int |
| copy_barcode | varchar |
| returned_at | datetime |
Primary key: return_id.
Yesterday's returns, one row per physical copy handed back.
Examples
Example 1
holds
| hold_id | book_id | member_id | placed_at | status |
|---|---|---|---|---|
| 1 | 10 | 501 | 2025-02-01 10:00:00 | active |
| 2 | 10 | 502 | 2025-02-01 10:00:00 | active |
| 3 | 10 | 503 | 2025-01-30 18:20:00 | collected |
| 4 | 10 | 504 | 2025-02-03 09:15:00 | active |
| 5 | 20 | 505 | 2025-02-02 11:00:00 | cancelled |
| 6 | 20 | 506 | 2025-02-04 12:30:00 | active |
| 7 | 30 | 507 | 2025-02-05 16:45:00 | active |
copy_returns
| return_id | book_id | copy_barcode | returned_at |
|---|---|---|---|
| 1 | 10 | LIB-10-A | 2025-03-09 11:10:00 |
| 2 | 10 | LIB-10-C | 2025-03-09 17:40:00 |
| 3 | 20 | LIB-20-A | 2025-03-09 12:00:00 |
| 4 | 20 | LIB-20-B | 2025-03-09 15:30:00 |
| 5 | 40 | LIB-40-A | 2025-03-09 10:05:00 |
Output
| book_id | queue_position | member_id |
|---|---|---|
| 10 | 1 | 501 |
| 10 | 2 | 502 |
| 20 | 1 | 506 |
How to solve Reservation Holders to Notify After Today's Returns
Two independent facts per book have to meet: its queue and its number of returned copies. The queue is ROW_NUMBER() OVER (PARTITION BY book_id ORDER BY placed_at, hold_id) over the active holds only — collected and cancelled holds must be removed before numbering, or they would occupy positions. The hold_id tie-break matters: holds 1 and 2 in the example were placed in the same second, and the rule puts hold 1 first.
The returns are counted per book, and the join keeps a queued member when queue_position <= copies. A book with returns but no queue (book 40) contributes nothing; a book with more returns than holds (book 20, two copies and one active hold) notifies only the member it has; a book with holds but no returns (30) is absent from the join.
The second alternative makes the pairing literal: number the returned copies too and join copy k to queue position k. The first computes positions with a correlated count of holds ahead, which needs the same tie-break written as a comparison. The window versions sort each book's holds once.
Reference solution (MySQL)
WITH returned AS (
SELECT book_id, COUNT(*) AS copies FROM copy_returns GROUP BY book_id
),
queue AS (
SELECT book_id, member_id,
ROW_NUMBER() OVER (PARTITION BY book_id ORDER BY placed_at, hold_id) AS queue_position
FROM holds
WHERE status = 'active'
)
SELECT q.book_id, q.queue_position, q.member_id
FROM queue q
JOIN returned r ON r.book_id = q.book_id
WHERE q.queue_position <= r.copies
ORDER BY q.book_id, q.queue_positionAnother way
SELECT book_id, queue_position, member_id FROM (
SELECT h.book_id, h.member_id,
(SELECT COUNT(*) FROM holds x WHERE x.book_id = h.book_id AND x.status = 'active'
AND (x.placed_at < h.placed_at OR (x.placed_at = h.placed_at AND x.hold_id <= h.hold_id))) AS queue_position,
(SELECT COUNT(*) FROM copy_returns c WHERE c.book_id = h.book_id) AS copies
FROM holds h WHERE h.status = 'active'
) t WHERE queue_position <= copies
ORDER BY book_id, queue_positionAnother way
SELECT q.book_id, q.queue_position, q.member_id
FROM (SELECT book_id, member_id, ROW_NUMBER() OVER (PARTITION BY book_id ORDER BY placed_at, hold_id) AS queue_position FROM holds WHERE status = 'active') q
JOIN (SELECT book_id, ROW_NUMBER() OVER (PARTITION BY book_id ORDER BY return_id) AS copy_no FROM copy_returns) c
ON c.book_id = q.book_id AND c.copy_no = q.queue_position
ORDER BY q.book_id, q.queue_position← Wards With Complaint Streaks of Three Days or More · First Day a Member's Fine Balance Reached ₹500 →