Hah, interesting - this is almost the same situation as another recent thread¹, which I will borrow on heavily to propose the following:

create temp table some_data(action DATE);

-- First set
insert into temp.some_data VALUES ('2000-01-01');
insert into temp.some_data VALUES ('2000-01-01');
insert into temp.some_data VALUES ('2000-01-02');
insert into temp.some_data VALUES ('2000-01-04');

-- Second set - note this crosses months
insert into temp.some_data VALUES ('2000-01-31');
insert into temp.some_data VALUES ('2000-02-01');
insert into temp.some_data VALUES ('2000-02-02');

--Third set
insert into temp.some_data VALUES ('2000-03-01');
insert into temp.some_data VALUES ('2000-03-02');


WITH
    edge_detect as (
        SELECT action,
            julianday(action)-julianday(lag(action)
                OVER (ORDER BY action)) <= 5 AS ingrp
        FROM some_data
    ),
    build_grouping AS (
        SELECT action, COUNT(*) FILTER (WHERE ingrp IS NOT 1)
                OVER (ORDER BY action,ingrp NULLS FIRST) AS g
        FROM edge_detect
    )
SELECT MIN(action) as Start, MAX(action) AS End
FROM build_grouping
GROUP BY g;

This time I don't think it can be done in a single stage.

Fossil Meta Query: link formatting doesn't seem to work in footnote labels?

1. ^{^} https://sqlite.org/forum/forumpost/e670a1c69e

This version is perhaps slightly more efficient by ordering the first SELECT, if my understanding of a new query optimization in the latest release is correct:

WITH
    edge_detect as (
        SELECT action,
            julianday(action)-julianday(lag(action) OVER ()) <= 5 AS ingrp
        FROM some_data
        ORDER BY action
    ),
    build_grouping AS (
        SELECT action, COUNT(*) FILTER (WHERE ingrp IS NOT 1)
            OVER (ROWS UNBOUNDED PRECEDING) AS g
        FROM edge_detect
    )
SELECT MIN(action) as Start, MAX(action) AS End
FROM build_grouping
GROUP BY g;

Thanks Mark! That works like a charm.

On 3.46.1, against a table with about 20 million records and no index on this field, I can confirm the second (with the ORDER BY) is faster than the first (150s versus ~210s).

A further optimisation is to change the very first SELECT action (line 3 on both) into SELECT DATE(action), as only the date component is required. This saves 10s from the second version (down to 140s) and a big 40s from the first (down to ~170s).

Thanks again!

Bo is right. The first lag needs to operate on sorted rows:

WITH
    edge_detect as (
        SELECT action, julianday(action) - julianday(
            lag(action) OVER ( ORDER BY action)) <= 5 AS ingrp
        FROM some_data
        ORDER BY action
    ),
    build_grouping AS (
        SELECT action, COUNT(*) FILTER (WHERE ingrp IS NOT 1)
            OVER (ROWS UNBOUNDED PRECEDING) AS g
        FROM edge_detect
    )
SELECT MIN(action) as Start, MAX(action) AS End
FROM build_grouping
GROUP BY g;

Honest question to minds less ignorant than mine: should OVER (ROWS UNBOUNDED PROCEDING) also require an explicit ORDER BY to guarantee correct behaviour? Because if not, I don't understand why OVER() in the first doesn't operate on the output row order.

I'm not sure I agree anonymous with your use of date(). I used julianday() to get day values that work with arithmatic. Have you tested arithmatic on dates?

SELECT date('2024-03-05')           - date('2024-03-01') AS Wrong;
SELECT julianday('2024-03-05') - julianday('2024-03-01') AS Right;
-- ┌───────┐
-- │ Wrong │
-- ├───────┤
-- │ 0     │
-- └───────┘
-- ┌───────┐
-- │ Right │
-- ├───────┤
-- │ 4.0   │
-- └───────┘

Please ignore my comments regarding date(). I obvious mistook where you were applying it. Your example data only has dates but presumably your actual data has more resolution.

That version does the wrong thing when dates aren't unique. Try it on a database with the same sample data inserted twice and you'll see.

Edited to add: it also fails in a different way with pragma reverse_unordered_selects=1;

In your example data, all clusters are associated with month breaks. If that holds for the real data as well, things could be done in a single step: just round to the nearest month break rather than the previous one.