Le bug iPhone X le plus proche du Nouvel An

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

Étant donnée une table bugs(id, token, title, category, device, reported_at, created_at, updated_at)

d'environ 10 millions de lignes, trouvez le bug de l'appareil device = 'iPhone X' dont created_at

est le plus proche de '2019-01-01 00:00:00', avant ou après. Si deux sont aussi proches, renvoyez

le plus ancien. Renvoyez les colonnes (id, created_at).

Colonnes attendues

id, created_at

Indices

Indice 1 : trouvez minuit

created_at n'est pas indexé mais croît avec id, comme dans « Comptez ces bugs ». Faites une recherche dichotomique avec Run (SELECT created_at FROM bugs WHERE id >= <mid> LIMIT 1) jusqu'à connaître le premier id créé à partir de 2019-01-01 00:00:00.

Indice 2 : regardez des deux côtés

Le bug iPhone X le plus proche est soit le premier à partir de cet id frontière, soit le dernier avant lui. Chacun est un parcours ordonné de la clé primaire : ORDER BY id LIMIT 1 vers le haut, ORDER BY id DESC LIMIT 1 vers le bas.

Indice 3 : à quelle distance est le suivant ?

Regardez device sur des ids consécutifs : il parcourt toujours les mêmes 10 appareils. Chaque parcours s'arrête donc après une dizaine de lignes. Réunissez les deux candidats avec UNION ALL et gardez celui dont la distance à minuit est la plus faible.