Lição 12.8 · Tempo de leitura: ~7 min

As lacunas e ilhas (gaps and islands) são uma família de tarefas sobre sequências: encontrar trechos de valores consecutivos (ilhas) e os buracos entre eles (lacunas). Perguntas típicas: "a maior sequência de logins de cada utilizador", "os períodos em que um sensor enviou dados", "os números de fatura em falta". É uma pergunta avançada muito apreciada em entrevistas de SQL. Nesta lição, você vai aprender o truque do ROW_NUMBER que agrupa datas consecutivas em ilhas, encontrar lacunas com LEAD e calcular a maior sequência de cada cliente.

Lacunas e Ilhas em SQL

Uma ilha é um trecho de valores sem buracos: dias consecutivos, números consecutivos. Uma lacuna é um trecho de valores em falta entre duas ilhas. A dificuldade é que o SQL trabalha com conjuntos, e "consecutivo" é uma relação entre linhas. As funções de janela transformam isto numa consulta curta.

Os exemplos são executados no banco de exemplo Sakila (MySQL 8.0). Os aluguéis no Sakila foram registados em períodos de uma semana, o que torna as ilhas fáceis de ver.

O Truque Principal: Data Menos Número da Linha

Pegue na lista ordenada de datas distintas e numere-a. Dentro de um trecho de dias consecutivos, a data cresce um dia e o número da linha cresce um, por isso data − número da linha fica constante. Quando falta um dia, a data salta para a frente e o número da linha não, e a diferença muda. Essa diferença é a chave da ilha.

Vejamos nos dias de aluguel do cliente 42 antes de 13 de julho de 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;

Resultado: 9 dias que formam 4 ilhas; por exemplo, os dias de 9 a 12 de julho têm todos a chave 2005-07-03.

A chave em si não significa nada; só tem de ser igual dentro de uma ilha e diferente entre ilhas. Falta o dia 8 de julho, por isso o dia 7 forma a sua própria ilha.

Ilhas: Períodos com Aluguéis

Agora agrupe pela chave e pegue no primeiro e no último dia de cada ilha:

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;

Resultado: 6 ilhas: cinco períodos de 8 dias consecutivos em 2005 e um único dia, 14 de fevereiro de 2006.

O DISTINCT na primeira CTE é essencial. Se um dia aparecesse duas vezes, receberia dois números de linha e a diferença partiria a ilha. Para sequências de inteiros, use value - ROW_NUMBER() da mesma forma.

Lacunas: Períodos sem Aluguéis

Para as lacunas, compare cada dia com o seguinte usando LEAD(). Se o dia seguinte for mais de um dia depois, há um buraco entre eles:

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;

Resultado: 5 lacunas: quatro de 13 dias entre os períodos de 2005 e uma de 174 dias, de 24 de agosto de 2005 a 13 de fevereiro de 2006.

A mesma consulta com números encontra ids em falta, por exemplo números de fatura saltados: substitua DATEDIFF(next_day, rental_day) por next_id - id.

Sequências por Cliente

A versão de entrevista: "encontre a maior sequência de dias consecutivos com aluguéis de cada cliente". Acrescente PARTITION BY customer_id para que cada cliente tenha a sua própria numeração e depois agregue duas vezes: ilhas por cliente e, a seguir, a maior ilha:

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;

Resultado: os clientes 42, 181, 290, 306 e 373 alugaram filmes em 8 dias consecutivos; no total, 10 clientes têm uma sequência de 8 dias.

A maior sequência possível aqui é de 8 dias, porque a própria loja só teve aluguéis em períodos de 8 dias. Com dados reais de atividade, a mesma consulta encontra sequências de logins, dias de trabalho consecutivos ou períodos de dados contínuos de um sensor.

Prática

• Problema Gap & Islands

Principais conclusões:

• As ilhas são trechos de valores consecutivos; as lacunas são os trechos em falta entre elas.
• Num trecho de datas consecutivas, date - ROW_NUMBER() é constante: agrupe por esse valor para obter as ilhas.
• Remova primeiro os repetidos com DISTINCT, ou um dia recebe vários números de linha e as ilhas partem-se.
• LEAD() compara cada valor com o seguinte e encontra as lacunas.
• PARTITION BY dá a cada entidade as suas próprias ilhas; uma segunda agregação encontra a maior sequência.

Perguntas Frequentes

O que é o problema gaps and islands em SQL?

É uma classe de tarefas sobre sequências de valores: as ilhas são trechos de valores consecutivos (dias, números) sem buracos, as lacunas são os valores em falta entre elas. Exemplos: sequências de logins, períodos contínuos de atividade, números de fatura em falta.

Como encontrar dias consecutivos em SQL?

Numere as datas distintas com ROW_NUMBER() OVER (ORDER BY day) e subtraia esse número de dias à data. Os dias consecutivos obtêm o mesmo resultado, por isso um GROUP BY por esse valor com MIN(day), MAX(day) e COUNT(*) dá cada trecho.

Como encontrar datas ou números em falta em SQL?

Use LEAD(value) OVER (ORDER BY value) para obter o valor seguinte de cada linha e mantenha as linhas em que a diferença é maior do que um passo. A lacuna vai do valor mais um passo até ao valor seguinte menos um passo. Para listar cada data em falta, junte um calendário gerado (Lição 6.6).

Como encontrar a maior sequência de cada utilizador?

Agrupe os dias consecutivos em ilhas por utilizador com ROW_NUMBER() OVER (PARTITION BY user_id ORDER BY day), conte os dias de cada ilha e pegue no MAX dessas contagens por utilizador.