Gaps and Islands

“The longest streak of consecutive days”, “group these events into sessions”, “merge overlapping bookings” — one pattern. It looks like the hardest thing in SQL and reduces to a subtraction.

The trick

CREATE TEMP TABLE logins (user_id INTEGER, login_date DATE);
INSERT INTO logins VALUES
    (1, DATE '2024-03-01'), (1, DATE '2024-03-02'), (1, DATE '2024-03-03'),
    (1, DATE '2024-03-07'), (1, DATE '2024-03-08'),
    (2, DATE '2024-03-01'), (2, DATE '2024-03-05');

SELECT user_id, login_date,
       row_number() OVER (PARTITION BY user_id ORDER BY login_date)     AS rn,
       login_date - row_number() OVER (PARTITION BY user_id
                                       ORDER BY login_date) * INTERVAL 1 DAY AS grp
FROM logins ORDER BY user_id, login_date;

┌─────────┬────────────┬───────┬─────────────────────┐
│ user_id │ login_date │  rn   │         grp         │
├─────────┼────────────┼───────┼─────────────────────┤
│       1 │ 2024-03-01 │     1 │ 2024-02-29 00:00:00 │
│       1 │ 2024-03-02 │     2 │ 2024-02-29 00:00:00 │
│       1 │ 2024-03-03 │     3 │ 2024-02-29 00:00:00 │
│       1 │ 2024-03-07 │     4 │ 2024-03-03 00:00:00 │
│       1 │ 2024-03-08 │     5 │ 2024-03-03 00:00:00 │
│       2 │ 2024-03-01 │     1 │ 2024-02-29 00:00:00 │
│       2 │ 2024-03-05 │     2 │ 2024-03-03 00:00:00 │
└─────────┴────────────┴───────┴─────────────────────┘

Look at the grp column. The first three rows share 2024-02-29; rows four and five share 2024-03-03. The value is constant inside a streak and changes at every gap.

The reason is one sentence:

“Inside a consecutive run, the date increases by one per row and so does the row number. Their difference is therefore fixed. When a day is skipped the date jumps ahead but the row number does not, so the difference moves — which marks a new island.”

The value itself is meaningless — it is just a group key.

Longest streak

WITH marked AS (
    SELECT user_id, login_date,
           login_date - row_number() OVER (PARTITION BY user_id ORDER BY login_date)
                        * INTERVAL 1 DAY AS grp
    FROM logins
),
islands AS (
    SELECT user_id, grp,
           min(login_date) AS streak_start,
           max(login_date) AS streak_end,
           count(*)        AS streak_length
    FROM marked GROUP BY user_id, grp
)
SELECT user_id, streak_start, streak_end, streak_length
FROM islands ORDER BY user_id, streak_start;

┌─────────┬──────────────┬────────────┬───────────────┐
│ user_id │ streak_start │ streak_end │ streak_length │
├─────────┼──────────────┼────────────┼───────────────┤
│       1 │ 2024-03-01   │ 2024-03-03 │             3 │
│       1 │ 2024-03-07   │ 2024-03-08 │             2 │
│       2 │ 2024-03-01   │ 2024-03-01 │             1 │
│       2 │ 2024-03-05   │ 2024-03-05 │             1 │
└─────────┴──────────────┴────────────┴───────────────┘

The longest per user is then a top-N-per-group on streak_length — the pattern from lesson 5, reused:

WITH islands AS (/* as above */)
SELECT DISTINCT ON (user_id) user_id, streak_start, streak_end, streak_length
FROM islands ORDER BY user_id, streak_length DESC, streak_start;

┌─────────┬──────────────┬────────────┬───────────────┐
│ user_id │ streak_start │ streak_end │ streak_length │
├─────────┼──────────────┼────────────┼───────────────┤
│       1 │ 2024-03-01   │ 2024-03-03 │             3 │
│       2 │ 2024-03-01   │ 2024-03-01 │             1 │
└─────────┴──────────────┴────────────┴───────────────┘

Duplicates break it

INSERT INTO logins VALUES (3, DATE '2024-03-01'), (3, DATE '2024-03-01'), (3, DATE '2024-03-02');

WITH marked AS (
    SELECT user_id, login_date,
           login_date - row_number() OVER (PARTITION BY user_id ORDER BY login_date)
                        * INTERVAL 1 DAY AS grp
    FROM logins WHERE user_id = 3
)
SELECT login_date, grp, count(*) OVER (PARTITION BY grp) AS island_size FROM marked;

┌────────────┬─────────────────────┬─────────────┐
│ login_date │         grp         │ island_size │
├────────────┼─────────────────────┼─────────────┤
│ 2024-03-01 │ 2024-02-29 00:00:00 │           1 │
│ 2024-03-01 │ 2024-02-28 00:00:00 │           1 │
│ 2024-03-02 │ 2024-02-28 00:00:00 │           1 │
└────────────┴─────────────────────┴─────────────┘

User 3 logged in twice on 1 March and once on 2 March — a two-day streak. The query reports three separate islands, because the row number advanced on the duplicate while the date did not.

The fix is to deduplicate first, and dense_rank() is the alternative that handles it in one step:

WITH marked AS (
    SELECT DISTINCT user_id, login_date,
           login_date - dense_rank() OVER (PARTITION BY user_id ORDER BY login_date)
                        * INTERVAL 1 DAY AS grp
    FROM logins WHERE user_id = 3
)
SELECT min(login_date) AS start, max(login_date) AS finish, count(*) AS days
FROM marked GROUP BY grp;

┌────────────┬────────────┬───────┐
│   start    │   finish   │ days  │
├────────────┼────────────┼───────┤
│ 2024-03-01 │ 2024-03-02 │     2 │
└────────────┴────────────┴───────┘

dense_rank() gives duplicates the same number, so the difference stays constant across them. Knowing why the naive version fails is worth more than knowing the fix.

Sessionisation: the same idea with a threshold

CREATE TEMP TABLE hits (user_id INTEGER, ts TIMESTAMP);
INSERT INTO hits VALUES
    (1, TIMESTAMP '2024-03-01 10:00:00'),
    (1, TIMESTAMP '2024-03-01 10:05:00'),
    (1, TIMESTAMP '2024-03-01 10:20:00'),
    (1, TIMESTAMP '2024-03-01 14:00:00'),
    (1, TIMESTAMP '2024-03-01 14:02:00');

WITH gaps AS (
    SELECT user_id, ts,
           datediff('minute', lag(ts) OVER (PARTITION BY user_id ORDER BY ts), ts) AS gap_min
    FROM hits
),
flagged AS (
    SELECT *, CASE WHEN gap_min IS NULL OR gap_min > 30 THEN 1 ELSE 0 END AS is_new_session
    FROM gaps
),
sessioned AS (
    SELECT *, sum(is_new_session) OVER (PARTITION BY user_id ORDER BY ts
                                        ROWS UNBOUNDED PRECEDING) AS session_id
    FROM flagged
)
SELECT session_id, min(ts) AS started, max(ts) AS ended,
       count(*) AS hits,
       datediff('minute', min(ts), max(ts)) AS duration_min
FROM sessioned GROUP BY user_id, session_id ORDER BY session_id;

┌────────────┬─────────────────────┬─────────────────────┬───────┬──────────────┐
│ session_id │       started       │        ended        │ hits  │ duration_min │
├────────────┼─────────────────────┼─────────────────────┼───────┼──────────────┤
│          1 │ 2024-03-01 10:00:00 │ 2024-03-01 10:20:00 │     3 │           20 │
│          2 │ 2024-03-01 14:00:00 │ 2024-03-01 14:02:00 │     2 │            2 │
└────────────┴─────────────────────┴─────────────────────┴───────┴──────────────┘

Two sessions from five hits: three in the morning, two in the afternoon, split at the 3h40m gap. The 10:00→10:05→10:20 hits are 5 and 15 minutes apart, both under the timeout; the jump to 14:00 is 220 minutes and starts a new session.

The is_new_session flag is 1 on the very first row of each user because lag returns NULL there — gap_min IS NULL handles it, and forgetting that clause gives every user a session 0 containing only their first hit.

The mechanism in one sentence: a running SUM of a 0/1 flag increments only where the flag is 1, so it is a group id. The 30-minute timeout is the standard web analytics definition and is a parameter to ask about — some products use 30 minutes of inactivity, others a fixed daily boundary.

Merging overlapping intervals

CREATE TEMP TABLE bookings (room VARCHAR, start_at DATE, end_at DATE);
INSERT INTO bookings VALUES
    ('A', DATE '2024-03-01', DATE '2024-03-05'),
    ('A', DATE '2024-03-03', DATE '2024-03-08'),   -- overlaps
    ('A', DATE '2024-03-04', DATE '2024-03-06'),   -- fully contained
    ('A', DATE '2024-03-12', DATE '2024-03-15'),   -- separate
    ('B', DATE '2024-03-01', DATE '2024-03-02');

WITH ordered AS (
    SELECT room, start_at, end_at,
           max(end_at) OVER (PARTITION BY room ORDER BY start_at
                             ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING) AS prev_max_end
    FROM bookings
),
flagged AS (
    SELECT *, CASE WHEN prev_max_end IS NULL OR start_at > prev_max_end THEN 1 ELSE 0 END AS is_new
    FROM ordered
),
grouped AS (
    SELECT *, sum(is_new) OVER (PARTITION BY room ORDER BY start_at
                                ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS grp
    FROM flagged
)
SELECT room, grp, min(start_at) AS merged_start, max(end_at) AS merged_end
FROM grouped GROUP BY room, grp ORDER BY room, merged_start;

┌─────────┬───────┬──────────────┬────────────┐
│  room   │  grp  │ merged_start │ merged_end │
├─────────┼───────┼──────────────┼────────────┤
│ A       │     1 │ 2024-03-01   │ 2024-03-08 │
│ A       │     2 │ 2024-03-12   │ 2024-03-15 │
│ B       │     1 │ 2024-03-01   │ 2024-03-02 │
└─────────┴───────┴──────────────┴────────────┘

Room A’s three overlapping bookings merge into 2024-03-01 to 2024-03-08; the March 12 one stays separate. Room B has a single booking and produces a single row.

The critical piece is max(end_at) OVER (... ROWS BETWEEN UNBOUNDED PRECEDING AND 1 PRECEDING) — the running maximum of all previous ends, not just the previous row’s end. Booking three (March 4–6) is entirely inside booking two (March 3–8); comparing only to the immediately previous row would see end_at going backwards and wrongly start a new group.

“The running max is what handles a fully-contained interval. lag(end_at) looks equivalent and breaks on exactly that case — which is why it is usually the test input.”

Recognising it

QUESTION                                        SHAPE
"consecutive days / longest streak"             date - row_number(), group by the difference
"N days in a row"                               same, then filter on count(*) >= N
"group events into sessions"                    gap flag + running SUM
"how many distinct visits"                      sessionise, then count the groups
"merge overlapping ranges"                      running max of end + flag + running SUM
"find the gaps in a sequence"                   the islands query, then lag on the boundaries
duplicates in the source                        dense_rank(), or deduplicate first

Finding the gaps themselves

WITH islands AS (
    SELECT user_id, min(login_date) AS s, max(login_date) AS e
    FROM (SELECT user_id, login_date,
                 login_date - row_number() OVER (PARTITION BY user_id ORDER BY login_date)
                              * INTERVAL 1 DAY AS grp
          FROM logins WHERE user_id = 1) m
    GROUP BY user_id, grp
)
SELECT e + INTERVAL 1 DAY AS gap_start,
       lead(s) OVER (ORDER BY s) - INTERVAL 1 DAY AS gap_end,
       datediff('day', e, lead(s) OVER (ORDER BY s)) - 1 AS gap_days
FROM islands QUALIFY gap_end IS NOT NULL;

┌─────────────────────┬─────────────────────┬──────────┐
│      gap_start      │       gap_end       │ gap_days │
├─────────────────────┼─────────────────────┼──────────┤
│ 2024-03-04 00:00:00 │ 2024-03-06 00:00:00 │        3 │
└─────────────────────┴─────────────────────┴──────────┘

Islands first, then lead across them gives the gaps between. The three missing days are the 4th, 5th and 6th.

QUALIFY filters on a window function without a wrapping CTE — DuckDB, Snowflake, BigQuery and Databricks support it; PostgreSQL and MySQL do not. Another dialect feature to name as one.

Practice

2024-02-29, 2024-02-29, 2024-02-29, 2024-03-03, 2024-03-03

3 islands where there should be 2

session 1: 3 hits, 20 min      session 2: 2 hits, 2 min

A fully contained interval wrongly starts a new group.

Next: query plans and performance — reading EXPLAIN, and the four reasons a query is slow.