Leçon 12.8 · Temps de lecture : ~7 min

Les trous et îlots (gaps and islands) forment une famille de problèmes sur les séquences : trouver les suites de valeurs consécutives (îlots) et les manques entre elles (trous). Questions typiques : « la plus longue série de connexions de chaque utilisateur », « les périodes où un capteur a envoyé des données », « les numéros de facture manquants ». C'est une question avancée très appréciée en entretien SQL. Dans cette leçon, vous apprendrez l'astuce de ROW_NUMBER qui regroupe les dates consécutives en îlots, trouverez les trous avec LEAD et calculerez la plus longue série de chaque client.

Trous et îlots en SQL

Un îlot est une suite de valeurs sans manque : des jours consécutifs, des nombres consécutifs. Un trou est une suite de valeurs manquantes entre deux îlots. La difficulté : SQL travaille avec des ensembles, alors que « consécutif » est une relation entre lignes. Les fonctions de fenêtrage en font une requête courte.

Les exemples s'exécutent sur la base d'exemple Sakila (MySQL 8.0). Les locations y ont été enregistrées par périodes d'une semaine, ce qui rend les îlots faciles à voir.

L'astuce clé : la date moins le numéro de ligne

Prenez la liste triée des dates distinctes et numérotez-la. Dans une suite de jours consécutifs, la date augmente d'un jour et le numéro de ligne augmente de un : date − numéro de ligne reste donc constant. Quand un jour manque, la date fait un saut alors que le numéro de ligne non, et la différence change. Cette différence est la clé de l'îlot.

Voyons-le sur les jours de location du client 42 avant le 13 juillet 2005 :

WITH customer_days AS (
    SELECT DISTINCT DATE(rental_date) AS rental_day
    FROM rental
    WHERE customer_id = 42
      AND rental_date < '2005-07-13'
)
SELECT rental_day,
       ROW_NUMBER() OVER (ORDER BY rental_day) AS rn,
       DATE_SUB(rental_day, INTERVAL ROW_NUMBER() OVER (ORDER BY rental_day) DAY) AS island_key
FROM customer_days
ORDER BY rental_day;

Résultat : 9 jours formant 4 îlots ; par exemple, les jours du 9 au 12 juillet ont tous la clé 2005-07-03.

La clé elle-même ne signifie rien ; elle doit seulement être identique dans un îlot et différente entre îlots. Le 8 juillet manque, le 7 juillet forme donc son propre îlot.

Îlots : périodes avec des locations

Regroupez maintenant par la clé et prenez le premier et le dernier jour de chaque îlot :

WITH rental_days AS (
    SELECT DISTINCT DATE(rental_date) AS rental_day
    FROM rental
),
grouped AS (
    SELECT rental_day,
           DATE_SUB(rental_day, INTERVAL ROW_NUMBER() OVER (ORDER BY rental_day) DAY) AS island_key
    FROM rental_days
)
SELECT MIN(rental_day) AS island_start,
       MAX(rental_day) AS island_end,
       COUNT(*) AS days
FROM grouped
GROUP BY island_key
ORDER BY island_start;

Résultat : 6 îlots : cinq périodes de 8 jours consécutifs en 2005 et un jour isolé, le 14 février 2006.

Le DISTINCT de la première CTE est indispensable. Si un jour apparaissait deux fois, il recevrait deux numéros de ligne et la différence briserait l'îlot. Pour des suites d'entiers, utilisez value - ROW_NUMBER() de la même façon.

Trous : périodes sans location

Pour les trous, comparez chaque jour au suivant avec LEAD(). Si le jour suivant arrive plus d'un jour plus tard, il y a un trou entre les deux :

WITH rental_days AS (
    SELECT DISTINCT DATE(rental_date) AS rental_day
    FROM rental
),
with_next AS (
    SELECT rental_day,
           LEAD(rental_day) OVER (ORDER BY rental_day) AS next_day
    FROM rental_days
)
SELECT DATE_ADD(rental_day, INTERVAL 1 DAY) AS gap_start,
       DATE_SUB(next_day, INTERVAL 1 DAY) AS gap_end,
       DATEDIFF(next_day, rental_day) - 1 AS missing_days
FROM with_next
WHERE DATEDIFF(next_day, rental_day) > 1
ORDER BY gap_start;

Résultat : 5 trous : quatre de 13 jours entre les périodes de 2005 et un de 174 jours, du 24 août 2005 au 13 février 2006.

La même requête avec des nombres trouve les id manquants, par exemple des numéros de facture sautés : remplacez DATEDIFF(next_day, rental_day) par next_id - id.

Séries par client

La version d'entretien : « trouvez pour chaque client sa plus longue série de jours de location consécutifs ». Ajoutez PARTITION BY customer_id pour que chaque client ait sa propre numérotation, puis agrégez deux fois : les îlots par client, puis l'îlot le plus long :

WITH customer_days AS (
    SELECT DISTINCT customer_id, DATE(rental_date) AS rental_day
    FROM rental
),
grouped AS (
    SELECT customer_id, rental_day,
           DATE_SUB(rental_day, INTERVAL ROW_NUMBER() OVER (
               PARTITION BY customer_id ORDER BY rental_day) DAY) AS island_key
    FROM customer_days
),
streaks AS (
    SELECT customer_id, island_key, COUNT(*) AS streak_days
    FROM grouped
    GROUP BY customer_id, island_key
)
SELECT customer_id, MAX(streak_days) AS longest_streak
FROM streaks
GROUP BY customer_id
ORDER BY longest_streak DESC, customer_id
LIMIT 5;

Résultat : les clients 42, 181, 290, 306 et 373 ont loué 8 jours consécutifs ; au total, 10 clients ont une série de 8 jours.

La plus longue série possible ici est de 8 jours, car le magasin lui-même n'a eu de locations que par périodes de 8 jours. Avec de vraies données d'activité, la même requête trouve des séries de connexions, des jours de travail consécutifs ou des périodes de données continues d'un capteur.

Pratique

• Problème Gap & Islands

Points clés :

• Les îlots sont des suites de valeurs consécutives ; les trous, les suites manquantes entre eux.
• Dans une suite de dates consécutives, date - ROW_NUMBER() est constant : regroupez par cette valeur pour obtenir les îlots.
• Supprimez d'abord les doublons avec DISTINCT, sinon un jour reçoit plusieurs numéros de ligne et les îlots se brisent.
• LEAD() compare chaque valeur à la suivante et trouve les trous.
• PARTITION BY donne à chaque entité ses propres îlots ; une seconde agrégation trouve la plus longue série.

Questions fréquentes

Qu'est-ce que le problème gaps and islands en SQL ?

C'est une classe de problèmes sur les séquences de valeurs : les îlots sont des suites de valeurs consécutives (jours, nombres) sans manque, les trous sont les valeurs manquantes entre eux. Exemples : séries de connexions, périodes d'activité continues, numéros de facture manquants.

Comment trouver des jours consécutifs en SQL ?

Numérotez les dates distinctes avec ROW_NUMBER() OVER (ORDER BY day) et soustrayez ce nombre de jours à la date. Les jours consécutifs obtiennent le même résultat : un GROUP BY sur cette valeur avec MIN(day), MAX(day) et COUNT(*) donne chaque suite.

Comment trouver des dates ou des numéros manquants en SQL ?

Utilisez LEAD(value) OVER (ORDER BY value) pour obtenir la valeur suivante de chaque ligne et gardez les lignes où la différence dépasse un pas. Le trou va de la valeur plus un pas à la valeur suivante moins un pas. Pour lister chaque date manquante, joignez un calendrier généré (leçon 6.6).

Comment trouver la plus longue série de chaque utilisateur ?

Regroupez les jours consécutifs en îlots par utilisateur avec ROW_NUMBER() OVER (PARTITION BY user_id ORDER BY day), comptez les jours de chaque îlot et prenez le MAX de ces comptes par utilisateur.