Pattern: Gaps and Islands

## The construction ```sql SELECT reading_no, reading_no - ROW_NUMBER() OVER (ORDER BY reading_no) AS island_key FROM sensor_readings; ``` For `reading_no` values 1, 2, 3, 7, 8, 11 the row numbers are 1…6 and `island_key` comes out as 0, 0, 0, 3, 3, 5. Three distinct keys, one per island. ## Why it works Walk two adjacent rows of the same island. The row number always increases by exactly one — that is what `ROW_NUMBER()` does over an ordered set. Inside an island the value also increases by exactly one, by the definition of consecutive. Two quantities that both increase by one keep a constant difference, so every row of a run carries the same `island_key`. At a gap the value jumps by more than one while the row number still advances by one, so the difference grows by exactly the size of the gap. That guarantees the new island's key differs from the previous one. It also guarantees keys never repeat: the difference is non-decreasing as you scan forward and strictly increases at each break, so two different islands can never collide on the same key. The number itself carries no meaning — do not present it to users; it is scaffolding for `GROUP BY`. ## Turning it into an answer ```sql WITH marked AS ( SELECT reading_no, reading_no - ROW_NUMBER() OVER (ORDER BY reading_no) AS island_key FROM sensor_readings ) SELECT MIN(reading_no) AS island_start, MAX(reading_no) AS island_end, COUNT(*) AS island_length FROM marked GROUP BY island_key ORDER BY island_start; ``` The window function must be computed in an inner query: window functions are evaluated after `WHERE` and `GROUP BY`, so you cannot group by a window expression in the same query block. A CTE or derived table is the standard way to stage it. ## The three preconditions **Step of exactly one.** The trick relies on the value advancing at the same rate as the row number. Values that step by 2, or ids drawn from a sequence with caching holes, break it — every real hole becomes an island boundary whether or not it is one. If the step is a constant *k*, divide the value by *k* first, or switch to the `LAG()`-based construction where you spell out the break condition explicitly. **Uniqueness.** Duplicates are the classic trap. With values 4, 4, 5, 6 the row numbers are 1, 2, 3, 4 and the differences are 3, 2, 2, 2 — the duplicate splits what should be a single island. Two fixes: deduplicate first with `SELECT DISTINCT`, or use `DENSE_RANK() OVER (ORDER BY v)` instead of `ROW_NUMBER()`, which assigns the same rank to equal values and yields 3, 3, 3, 3. `DENSE_RANK()` is the safer default whenever duplicates are possible. **Deterministic ordering.** The `ORDER BY` inside `OVER` must order by the value that defines consecutiveness. Ordering by anything else produces row numbers unrelated to the sequence and the differences become noise. ## Per-entity islands Streaks are almost always per user, per device, per account. Add the partition key in both places: ```sql ROW_NUMBER() OVER (PARTITION BY user_id ORDER BY reading_no) ... GROUP BY user_id, island_key ``` Forgetting the key in the `GROUP BY` is a real bug rather than a style issue: two different users can produce the same difference and their rows would be merged into one bogus island. ## Filtered sets are a feature The row numbers are assigned over the rows that survive `WHERE`, not over the whole table. That is usually exactly what you want — "runs of days where the balance was negative" means numbering only the negative-balance days, so the positive days genuinely become gaps. It is worth stating out loud in an interview, because it shows you understand that the sequence is defined by the query's result set, not by the physical table. ## When to reach for the other construction The difference trick is compact and cheap but it can only express "the next value is exactly one step away". As soon as the break condition involves a tolerance ("a new run if more than 30 minutes elapsed"), a value change ("a new run when the status changes"), or an irregular step, you want `LAG()` to flag the break and a running `SUM()` of that flag as the run id. Both produce a run id; only the second lets you define the break yourself.