Эффективно выбрать начало и конец нескольких смежных диапазонов в запросе Postgresql

У меня есть около миллиарда строк данных в таблице с именем и целым числом в диапазоне 1-288. Для данного имени каждое int уникально, и не каждое возможное целое число в диапазоне присутствует - поэтому есть пробелы.

Этот запрос генерирует пример случая:

--what I have:
SELECT *
FROM ( VALUES ('foo', 2),
              ('foo', 3),
              ('foo', 4),
              ('foo', 10),
              ('foo', 11),
              ('foo', 13),
              ('bar', 1),
              ('bar', 2),
              ('bar', 3)
     ) AS baz ("name", "int")

Я хотел бы создать таблицу поиска со строкой для каждого имени и последовательности непрерывных целых чисел. Каждая такая строка будет содержать:

Имя - значение имени столбца
начала - первое целое число в пределах последовательности
конца - конечное значение в непрерывной последовательности
диапазона - конец - старт + 1

Этот запрос генерирует пример вывода для приведенного выше примера:

--what I need:
SELECT * 
FROM ( VALUES ('foo', 2, 4, 3),
              ('foo', 10, 11, 2),
              ('foo', 13, 13, 1),
              ('bar', 1, 3, 3)
     ) AS contiguous_ranges ("name", "start", "end", span)

Потому что у меня так много строк, чем эффективнее, тем лучше. Тем не менее, я должен выполнить этот запрос только один раз, так что это не является абсолютным требованием.

Заранее спасибо!

Редактировать:

Я должен добавить, что решения PL / pgSQL приветствуются (пожалуйста, объясните любые хитрые уловки - я все еще новичок в PL / pgSQL).

Как насчет использования with recursive

тестовый вид:

create view v as 
select *
from ( values ('foo', 2),
              ('foo', 3),
              ('foo', 4),
              ('foo', 10),
              ('foo', 11),
              ('foo', 13),
              ('bar', 1),
              ('bar', 2),
              ('bar', 3)
     ) as baz ("name", "int");

запрос:

with recursive t("name", "int") as ( select "name", "int", 1 as span from v
                                     union all
                                     select "name", v."int", t.span+1 as span
                                     from v join t using ("name")
                                     where v."int"=t."int"+1 )
select "name", "start", "start"+span-1 as "end", span
from( select "name", ("int"-span+1) as "start", max(span) as span
      from ( select "name", "int", max(span) as span 
             from t
             group by "name", "int" ) z
      group by "name", ("int"-span+1) ) z;

результат:

 name | start | end | span
------+-------+-----+------
 foo  |     2 |   4 |    3
 foo  |    13 |  13 |    1
 bar  |     1 |   3 |    3
 foo  |    10 |  11 |    2
(4 rows)

Мне было бы интересно узнать, как это работает с вашей таблицей миллиардов строк.

Вы можете сделать это с помощью оконных функций. Основная идея заключается в том, чтобы использовать leadи lagоконную функцию тянуть строки впереди и позади текущей строки. Тогда мы можем вычислить, если у нас есть начало или конец последовательности:

create temp view temp_view as
    select
        n,
        val,
        (lead <> val + 1 or lead is null) as islast,
        (lag <> val - 1 or lag is null) as isfirst,
        (lead <> val + 1 or lead is null) and (lag <> val - 1 or lag is null) as orphan
    from
    (
        select
            n,
            lead(val, 1) over( partition by n order by n, val),
            lag(val, 1) over(partition by n order by n, val ),
            val
        from test
        order by n, val
    ) as t
;  
select * from temp_view;
 n  | val | islast | isfirst | orphan 
-----+-----+--------+---------+--------
 bar |   1 | f      | t       | f
 bar |   2 | f      | f       | f
 bar |   3 | t      | f       | f
 bar |  24 | t      | t       | t
 bar |  42 | t      | t       | t
 foo |   2 | f      | t       | f
 foo |   3 | f      | f       | f
 foo |   4 | t      | f       | f
 foo |  10 | f      | t       | f
 foo |  11 | t      | f       | f
 foo |  13 | t      | t       | t
(11 rows)

(Я использовал представление, чтобы ниже было легче следовать логике.) Теперь мы знаем, является ли строка началом или концом. Мы должны свернуть это в ряд:

select
    n as "name",
    first,
    coalesce (last, first) as last,
    coalesce (last - first + 1, 1) as span
from
(
    select
    n,
    val as first,
    -- this will not be excellent perf. since were calling the view
    -- for each row sequence found. Changing view into temp table 
    -- will probably help with lots of values.
    (
        select min(val)
        from temp_view as last
        where islast = true
        -- need this since isfirst=true, islast=true on an orphan sequence
        and last.orphan = false
        and first.val < last.val
        and first.n = last.n
    ) as last
    from
        (select * from temp_view where isfirst = true) as first
) as t
;

 name | first | last | span 
------+-------+------+------
 bar  |     1 |    3 |    3
 bar  |    24 |   24 |    1
 bar  |    42 |   42 |    1
 foo  |     2 |    4 |    3
 foo  |    10 |   11 |    2
 foo  |    13 |   13 |    1
(6 rows)

Выглядит правильно для меня :)

Другое решение оконной функции. Понятия не имею об эффективности, я добавил план выполнения в конце (хотя с таким небольшим количеством строк он, вероятно, не имеет большого значения). Если вы хотите поиграть: тест SQL-Fiddle

Таблица и данные:

CREATE TABLE baz
( name VARCHAR(10) NOT NULL
, i INT  NOT NULL
, UNIQUE  (name, i)
) ;

INSERT INTO baz
  VALUES 
    ('foo', 2),
    ('foo', 3),
    ('foo', 4),
    ('foo', 10),
    ('foo', 11),
    ('foo', 13),
    ('bar', 1),
    ('bar', 2),
    ('bar', 3)
  ;

Запрос:

SELECT a.name     AS name
     , a.i        AS start
     , b.i        AS "end"
     , b.i-a.i+1  AS span
FROM
      ( SELECT name, i
             , ROW_NUMBER() OVER (PARTITION BY name ORDER BY i) AS rn
        FROM baz AS a
        WHERE NOT EXISTS
              ( SELECT * 
                FROM baz AS prev
                WHERE prev.name = a.name
                  AND prev.i = a.i - 1
              ) 
      ) AS a
    JOIN
      ( SELECT name, i 
             , ROW_NUMBER() OVER (PARTITION BY name ORDER BY i) AS rn
        FROM baz AS a
        WHERE NOT EXISTS
              ( SELECT * 
                FROM baz AS next
                WHERE next.name = a.name
                  AND next.i = a.i + 1
              )
      ) AS b
    ON  b.name = a.name
    AND b.rn  = a.rn
 ; 

План запроса

Merge Join (cost=442.74..558.76 rows=18 width=46)
Merge Cond: ((a.name)::text = (a.name)::text)
Join Filter: ((row_number() OVER (?)) = (row_number() OVER (?)))
-> WindowAgg (cost=221.37..238.33 rows=848 width=42)
-> Sort (cost=221.37..223.49 rows=848 width=42)
Sort Key: a.name, a.i
-> Merge Anti Join (cost=157.21..180.13 rows=848 width=42)
Merge Cond: (((a.name)::text = (prev.name)::text) AND (((a.i - 1)) = prev.i))
-> Sort (cost=78.60..81.43 rows=1130 width=42)
Sort Key: a.name, ((a.i - 1))
-> Seq Scan on baz a (cost=0.00..21.30 rows=1130 width=42)
-> Sort (cost=78.60..81.43 rows=1130 width=42)
Sort Key: prev.name, prev.i
-> Seq Scan on baz prev (cost=0.00..21.30 rows=1130 width=42)
-> Materialize (cost=221.37..248.93 rows=848 width=50)
-> WindowAgg (cost=221.37..238.33 rows=848 width=42)
-> Sort (cost=221.37..223.49 rows=848 width=42)
Sort Key: a.name, a.i
-> Merge Anti Join (cost=157.21..180.13 rows=848 width=42)
Merge Cond: (((a.name)::text = (next.name)::text) AND (((a.i + 1)) = next.i))
-> Sort (cost=78.60..81.43 rows=1130 width=42)
Sort Key: a.name, ((a.i + 1))
-> Seq Scan on baz a (cost=0.00..21.30 rows=1130 width=42)
-> Sort (cost=78.60..81.43 rows=1130 width=42)
Sort Key: next.name, next.i
-> Seq Scan on baz next (cost=0.00..21.30 rows=1130 width=42)

На SQL Server я бы добавил еще один столбец с именем previousInt:

SELECT *
FROM ( VALUES ('foo', 2, NULL),
              ('foo', 3, 2),
              ('foo', 4, 3),
              ('foo', 10, 4),
              ('foo', 11, 10),
              ('foo', 13, 11),
              ('bar', 1, NULL),
              ('bar', 2, 1),
              ('bar', 3, 2)
     ) AS baz ("name", "int", "previousInt")

Я бы использовал ограничение CHECK, чтобы убедиться, что previousInt <int, и ограничение FK (name, previousInt) ссылаются на (name, int) и еще пару ограничений для обеспечения непроницаемости данных. Это сделано, выбор пробелов тривиально:

SELECT NAME, PreviousInt, Int from YourTable WHERE PreviousInt < Int - 1;

Чтобы ускорить это, я мог бы создать фильтрованный индекс, который будет включать только пробелы. Это означает, что все ваши пропуски предварительно вычисляются, поэтому выбор выполняется очень быстро, а ограничения обеспечивают целостность ваших предварительно вычисленных данных. Я часто использую такие решения, они во всей моей системе.

Вы можете посмотреть на метод Табибитозан:

https://community.oracle.com/docs/DOC-915680
http://rwijk.blogspot.com/2014/01/tabibitosan.html
https://www.xaprb.com/blog/2006/03/22/find-contiguous-ranges-with-sql/

В принципе:

SQL> create table mytable (nr)
  2  as
  3  select 1 from dual union all
  4  select 2 from dual union all
  5  select 3 from dual union all
  6  select 6 from dual union all
  7  select 7 from dual union all
  8  select 11 from dual union all
  9  select 18 from dual union all
 10  select 19 from dual union all
 11  select 20 from dual union all
 12  select 21 from dual union all
 13  select 22 from dual union all
 14  select 25 from dual
 15  /

 Table created.

 SQL> with tabibitosan as
 2  ( select nr
 3         , nr - row_number() over (order by nr) grp
 4      from mytable
 5  )
 6  select min(nr)
 7       , max(nr)
 8    from tabibitosan
 9   group by grp
10   order by grp
11  /

   MIN(NR)    MAX(NR)
---------- ----------
         1          3
         6          7
        11         11
        18         22
        25         25

5 rows selected.

Я думаю, что это представление лучше:

SQL> r
  1  select min(nr) as range_start
  2    ,max(nr) as range_end
  3  from (-- our previous query
  4    select nr
  5      ,rownum
  6      ,nr - rownum grp
  7    from  (select nr
  8       from   mytable
  9       order by 1
 10      )
 11   )
 12  group by grp
 13* order by 1

RANGE_START  RANGE_END
----------- ----------
      1      3
      6      7
     11     11
     18     22
     25     25

примерный план:

• Выберите минимум для каждого имени (группа по имени)
• Выберите минимум2 для каждого имени, где min2> min1 и не существует (подзапрос: SEL min2-1).
• Sel max val1> min val1, где max val1 <min val2.

Повторяйте от 2. до тех пор, пока больше не произойдет обновление. Оттуда это становится сложным, Гордианом, с группировкой по максимуму мин и мин максимум. Я думаю, я бы пошел на язык программирования.

PS: Хорошая таблица примеров с несколькими значениями выборок была бы хороша, которая могла бы использоваться всеми, поэтому не каждый создает свои тестовые данные с нуля.

Это решение основано на ответе nate c с использованием оконных функций и предложения OVER. Интересно, что этот ответ возвращается к подзапросам с внешними ссылками. Можно завершить консолидацию строк, используя другой уровень функций управления окнами. Это может выглядеть не слишком красиво, но я предполагаю, что это более эффективно, поскольку оно использует встроенную логику мощных оконных функций.

Из решения Нейта я понял, что начальный набор строк уже содержит необходимые флаги для 1) выбора значений начального и конечного диапазона И 2) для устранения лишних строк между ними. Запрос имеет вложенные два подзапроса только из-за ограничений оконных функций, которые ограничивают использование псевдонимов столбцов. Логически я мог бы получить результаты только с одним вложенным подзапросом.

Несколько других замечаний : Ниже приведен код для SQLite3. Диалект SQLite является производным от postgresql, поэтому он очень похож и может даже работать без изменений. Я добавил ограничение на кадрирование в предложения OVER, поскольку функции lag()и lead()нужны только в одном окне, до и после соответственно (поэтому не нужно было сохранять набор по умолчанию для всех предыдущих строк). Я также выбрал имена firstи lastтак как слово endзарезервировано.

create temp view test as 
with cte(name, int) AS (
select * from ( values ('foo', 2),
              ('foo', 3),
              ('foo', 4),
              ('foo', 10),
              ('foo', 11),
              ('foo', 13),
              ('bar', 1),
              ('bar', 2),
              ('bar', 3) ))
select * from cte;


SELECT name,
       int AS first, 
       endpoint AS last,
       (endpoint - int + 1) AS span
FROM ( SELECT name, 
             int, 
             CASE WHEN prev <> 1 AND next <> -1 -- orphan
                  THEN int
                WHEN next = -1 -- start of range
                  THEN lead(int) OVER (PARTITION BY name 
                                       ORDER BY int 
                                       ROWS BETWEEN CURRENT ROW AND 1 FOLLOWING)
                ELSE null END
             AS endpoint
        FROM ( SELECT name, 
                   int,
                   coalesce(int - lag(int) OVER (PARTITION BY name 
                                                 ORDER BY int 
                                                 ROWS BETWEEN 1 PRECEDING AND CURRENT ROW), 
                            0) AS prev,
                   coalesce(int - lead(int) OVER (PARTITION BY name 
                                                  ORDER BY int 
                                                  ROWS BETWEEN CURRENT ROW AND 1 FOLLOWING),
                            0) AS next
              FROM test
            ) AS mark_boundaries
        WHERE NOT (prev = 1 AND next = -1) -- discard values within range
      ) as raw_ranges
WHERE endpoint IS NOT null
ORDER BY name, first

Результаты так же, как и другие ответы, как и ожидалось:

 name | first | last | span
------+-------+------+------
 bar  |     1 |    3 |   3
 foo  |     2 |    4 |   3
 foo  |    10 |   11 |   2
 foo  |    13 |   13 |   1