The iPhone X bug closest to New Year

Boss · primary-key, binary-search, nearest-neighbor, limit

Given a table bugs(id, token, title, category, device, reported_at, created_at, updated_at)

with about 10 million rows, find the bug from device = 'iPhone X' whose created_at is closest

to '2019-01-01 00:00:00', before or after. If two are equally close, return the earlier one.

Output the columns (id, created_at).

Expected columns

id, created_at

Hints

Hint 1 — find midnight

created_at is not indexed but grows with id, as in 'Count em bugs'. Binary-search with Run (SELECT created_at FROM bugs WHERE id >= <mid> LIMIT 1) until you know the first id created at or after 2019-01-01 00:00:00.

Hint 2 — look both ways

The closest iPhone X bug is either the first one at or after that boundary id or the last one before it. Each is one ordered walk on the primary key: ORDER BY id LIMIT 1 going up, ORDER BY id DESC LIMIT 1 going down.

Hint 3 — how far is the next one?

Look at device on consecutive ids: it cycles through the same 10 devices. So each walk stops after about 10 rows. UNION ALL the two candidates and keep the one with the smaller distance to midnight.