1. What Are Gap and Island Problems?

In data analysis, we frequently encounter a class of problems known as Gap and Island problems—identifying consecutive ranges within seemingly scattered data. These problems are extremely common in business scenarios:

• User retention analysis: Calculate consecutive login days
• Financial markets: Detect continuous price up/down intervals
• Device monitoring: Identify server online/offline periods
• Order analysis: Recognize active ordering patterns

If you try to solve these with a simple GROUP BY, you’ll quickly hit a wall—because consecutive dates aren’t stored consecutively in the database. They’re scattered across individual rows.

The classic solution uses window functions + the difference method—an elegant, efficient approach that works in any database supporting window functions. DuckDB, as an analytical database, is naturally built for this kind of operation.

2. Core Principle: The Difference Method

The core idea is beautifully simple:

Consecutive dates - Consecutive row numbers = Constant value

Consider a sequence of consecutive dates 2024-01-01, 2024-01-02, 2024-01-03 with row numbers 1, 2, 3. Then date - row_number always equals the same value (2023-12-31). When a gap appears (e.g., 2024-01-05 skips 01-04), the row number keeps incrementing but the date jumps, so the difference changes—naturally forming a new “island.”

This is why subtracting consecutive row numbers from consecutive dates yields a constant—it’s the mathematical foundation for detecting consecutive ranges.

3. Practical Case: User Consecutive Login Days

3.1 Data Setup

Assume we have a user login log table login_log:

CREATE TABLE login_log (
 user_id INTEGER,
 login_date DATE
);

INSERT INTO login_log VALUES
(1, '2024-01-01'),
(1, '2024-01-02'),
(1, '2024-01-03'),
(1, '2024-01-05'),
(1, '2024-01-06'),
(2, '2024-01-01'),
(2, '2024-01-03'),
(2, '2024-01-04'),
(2, '2024-01-05');

User 1 logged in consecutively on Jan 1-3, missed a day, then logged in again on Jan 5-6. User 2 logged in alone on the 1st, then consecutively on Jan 3-5.

3.2 Difference Method Implementation

WITH numbered AS (
 -- Step 1: Number each user's login dates in order
 SELECT user_id, login_date,
 ROW_NUMBER() OVER (
 PARTITION BY user_id 
 ORDER BY login_date
 ) AS rn
 FROM login_log
),
grouped AS (
 -- Step 2: Calculate date - row_number to create group identifiers
 SELECT user_id, login_date,
 login_date - INTERVAL (rn) DAY AS grp
 FROM numbered
)
-- Step 3: Aggregate by (user_id, grp) to get consecutive ranges
SELECT user_id,
 MIN(login_date) AS start_date,
 MAX(login_date) AS end_date,
 COUNT(*) AS consecutive_days
FROM grouped
GROUP BY user_id, grp
ORDER BY user_id, start_date;

3.3 Execution Result

 user_id | start_date | end_date | consecutive_days
---------+------------+------------+------------------
 1 | 2024-01-01 | 2024-01-03 | 3
 1 | 2024-01-05 | 2024-01-06 | 2
 2 | 2024-01-01 | 2024-01-01 | 1
 2 | 2024-01-03 | 2024-01-05 | 3

The result cleanly shows each user’s consecutive login ranges.

3.4 Step-by-Step Breakdown

The key insight: when dates are consecutive, login_date - rn stays constant; when there’s a gap, this value jumps, naturally creating a new group.

4. Advanced Scenarios

4.1 Price Trend Interval Detection

In financial analysis, identifying continuous up/down periods is highly valuable:

WITH price_changes AS (
 SELECT date, price,
 LAG(price) OVER (ORDER BY date) AS prev_price,
 CASE 
 WHEN price > LAG(price) OVER (ORDER BY date) THEN 'UP'
 WHEN price < LAG(price) OVER (ORDER BY date) THEN 'DOWN'
 ELSE 'SAME'
 END AS trend
 FROM stock_prices
),
numbered AS (
 SELECT date, price, trend,
 ROW_NUMBER() OVER (PARTITION BY trend ORDER BY date) AS rn
 FROM price_changes
 WHERE trend != 'SAME'
)
SELECT trend,
 MIN(date) AS start_date,
 MAX(date) AS end_date,
 COUNT(*) AS days
FROM numbered
GROUP BY trend, date - INTERVAL rn DAY
ORDER BY start_date;

4.2 Device Online Status Analysis

WITH numbered AS (
 SELECT device_id, status_time,
 ROW_NUMBER() OVER (PARTITION BY device_id, status ORDER BY status_time) AS rn
 FROM device_events
)
SELECT device_id,
 status,
 MIN(status_time) AS start_time,
 MAX(status_time) AS end_time,
 COUNT(*) AS duration_minutes
FROM numbered
GROUP BY device_id, status, status_time - INTERVAL rn MINUTE
ORDER BY start_time;

4.3 Simplifying with DuckDB’s QUALIFY

DuckDB supports the QUALIFY clause for further simplification:

WITH numbered AS (
 SELECT user_id, login_date,
 ROW_NUMBER() OVER (PARTITION BY user_id ORDER BY login_date) AS rn
 FROM login_log
)
SELECT user_id,
 MIN(login_date) AS start_date,
 MAX(login_date) AS end_date,
 COUNT(*) AS consecutive_days
FROM numbered
GROUP BY user_id, login_date - INTERVAL rn DAY
QUALIFY ROW_NUMBER() OVER (PARTITION BY user_id ORDER BY MIN(login_date)) <= 5;

5. DuckDB vs Traditional Tools Comparison

Conclusion: For analytical queries like Gap/Island problems, DuckDB is the best choice in both development efficiency and runtime performance.

6. Performance Optimization Tips

6.1 Index Strategy

-- Create composite index for login log table
CREATE INDEX idx_login_user_date ON login_log (user_id, login_date);

6.2 Partitioned Tables

For very large datasets, you can partition by date:

-- DuckDB supports external table partitioning
SELECT * FROM read_csv_auto('login_logs/*.csv');

6.3 Parallel Processing

DuckDB automatically leverages multi-core parallelism for window functions, typically responding in seconds for millions of rows.

本文信息

如发现错误，欢迎通过 GitHub Issue 或邮件 [email protected] 反馈。