Пробелы и острова, или Gaps and islands. Часть I

Задачи вида "пробелы и острова", или "gaps and islands", возникают, когда в некоторой последовательности нужно найти участки (диапазоны, интервалы) непрерывных данных – "острова" – и/или участки отсутствия данных – "пробелы".

С наступленим эры оконных функций (они же аналитические, они же over-функции) задачи вида "пробелы и острова" решаются с помощью этих функций.

Примеры ниже с таблицей t1 взяты мной из статьи Solving Gaps and Islands with Enhanced Window Functions by Itzik Ben-Gan и адаптированы для выполнения на PostgreSQL.

После примеров с таблицей t1 я разберу более прикладной оригинальный пример с таблицей ежедневных продаж daily_sales.

Итак, в таблице t1 имеется последовательность целых чисел:

create table t1 (
    col1 int not null primary key
);

insert into t1(col1)
values (2),(3),(7),(8),(9),(11),(15),(16),(17),(28)
;

select * from t1;

col1
2
3
7
8
9
11
15
16
17
28

Выделить пробелы в последовательности проще, чем выделить острова. Сделаем это с помощью функции lead():

with c as (
    select col1 cur,
        -- next col1 value in ascending order
        lead(col1) over (order by col1) nxt
    from t1
)
select cur + 1 range_start,
    nxt - 1 range_end
from c
-- detect gaps
where nxt - cur > 1
;

range_start	range_end
4	6
10	10
12	14
18	27

Здесь подзапрос c формирует пары соседних значений столбца col1 в порядке возрастания, а внешний запрос отбирает из них те, у которых разность между соседними значениями больше 1, то есть, пары, представющие "пробелы".

"Симметричный" запрос с lag() вместо lead() дает такой же результат:

with c as (
    select col1 cur,
        lag(col1) over (order by col1) prv
    from t1
)
select prv + 1 range_start,
    cur - 1 range_end
from c
where cur - prv > 1
;

Чтобы выделить из последовательности "острова", потребуется, как минимум, двухходовка. Воспользуемся функциями lag() и lead():

with c1 as (
    select col1,
        case 
            when col1 - lag(col1) over (order by col1) <= 1 then
                0
            else
                1
        end is_start,
        case
            when lead(col1) over (order by col1) - col1 <= 1 then
                0
            else
                1
        end is_end
    from t1
), c2 as (
    select col1 range_start,
        case
            when is_end = 1 then
                col1
            else
                lead(col1, 1) over (order by col1)
        end range_end,
        is_start
    from c1
    where is_start = 1 or is_end = 1
)
select range_start, range_end
from c2
where is_start = 1
order by 1
;

range_start	range_end
2	3
7	9
11	11
15	17
28	28

Здесь подзапрос c1 помечает значения col1 как первые и последние значения неперывного диапазона. Подзапрос c2 работает только с первыми и последними значениями диапазонов, где is_start = 1 or is_end = 1, и формирует последнее значение диапазона (range_end) для всех строк, в результате чего строки с is_start = 1 содержат и первое и последнее значения диапазонов. Внешний запрос выводит эти строки.

Другой подход к выделению "островов" использует фукнции lead() и count():

with c1 as (
    select col1,
    case
        when col1 - lag(col1) over (order by col1) <= 1 then
            null
        else
            1
        end is_start
    from t1
), c2 as (
    select col1,
        -- 1 for all members of the 1st island,
        -- 2 for all members of the 2nd island,
        -- and so on
        count(is_start) over (order by col1) grp
    from c1
)
select min(col1) range_start,
    max(col1) range_end
from c2
group by grp
order by 1
;

Здесь подзапрос c1 помечает первые значения неперывных диапазонов. Но, в отличие от предыдущего примера, для остальных значений col1 столбец is_start получает значение null. Оконная функция count() в подзапросе c2 формирует для членов каждого непрерывного диапазона в стоблце grp номер диапазона, к которому они принадлежат:

col1	grp
2	1
3	1
7	2
8	2
9	2
11	3
15	4
16	4
17	4
28	5

(Такой же реузльтат в данном случае дает оконная функция sum() вместо count().)

А внешний запрос группирует строки по номеру диапазона и выводит минимальное и максимальное значение каждого диапазона:

range_start	range_end
2	3
7	9
11	11
15	17
28	28

Два рассмотренных подхода обладают неочевидным на первый взгляд свойством. Они позволяют выделять не только нормальные острова, где разность между членами диапазона всегда равна 1, но и специальные острова, где разность между членами диапазона не превышает некоторой пороговой величины.

Например, если принять, что значения, разность между которыми не больше 2, принадлежат к одному диапазону, то острова 7 - 9 и 11 - 11 сольются в один:

with c1 as (
    select col1,
    case
        when col1 - lag(col1) over (order by col1) <= 2 then
            null
        else
            1
        end is_start
    from t1
), c2 as (
    select col1,
        -- 1 for all members of the 1st island,
        -- 2 for all members of the 2nd island,
        -- and so on
        count(is_start) over (order by col1) grp
    from c1
)
select min(col1) range_start,
    max(col1) range_end
from c2
group by grp
order by 1
;

range_start	range_end
2	3
7	11
15	17
28	28

Пороговое значение 2 установлено в подзапросе c1.

Для выделения нормальных островов существует популярный подход, использующий оконные функциии dens_rank() или row_number(). Рассмотрим его:

with c as (
    select col1,
        -- the difference between col1 and the dense_rank value
        -- is constant per island and unique per island.
        -- This means that it identifies the island.
        col1 - dense_rank() over (order by col1) grp
    from t1
)
select
    min(col1) as range_start,
    max(col1) as range_end
from c
group by grp
order by 1
;

Здесь подзапрос c формирует для членов каждого непрерывного диапазона в стоблце grp номер диапазона, к которому они принадлежат:

col1	grp
2	1
3	1
7	4
8	4
9	4
11	5
15	8
16	8
17	8
28	18

(Аналогичный результат в данном случае дает оконная функция row_number() вместо dens_rank().)

А внешний запрос группирует строки по номеру диапазона и выводит минимальное и максимальное значение каждого диапазона:

range_start	range_end
2	3
7	9
11	11
15	17
28	28

На этом заканчиваю работу с таблицей t1:

drop table t1;

Были рассмотрены базовые подходы к решению задач вида "пробелы и острова" на последовательности целых чисел. Теперь рассмотрим прикладной пример.

Читайте продолжение Пробелы и острова, или Gaps and islands. Часть II.