Группировать по отличиям от начальной точки группы

Question

У меня есть много измерений в таблице базы данных Postgres, и мне нужно разбить этот набор на группы, когда какое-то значение слишком далеко отходит от «начальной» точки текущей группы (более чем порог ). Порядок сортировки определяется по столбцу id.

Пример: разделение на threshold = 1:

id measurements
---------------
1  1.5
2  1.4
3  1.8
4  2.6
5  3.7
6  3.5
7  3.0
8  2.6
9  2.5
10 2.8

Должно быть разбито на группы следующим образом:

id measurements group
---------------------
1  1.5            0     --- start new group 
2  1.4            0
3  1.8            0

4  2.6            1     --- start new group because it too far from 1.5

5  3.7            2     --- start new group because it too far from 2.6
6  3.5            2
7  3.0            2

8  2.6            3     --- start new group because it too far from 3.7
9  2.5            3
10 2.8            3

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

Можно ли достичь цели с помощью PARTITION OVER, CTE или любого другого типа SELECT?

Answer 1

Одним из способов решения этой проблемы является использование рекурсивного CTE. Этот пример написан с использованием синтаксиса SQL Server (потому что я не работаю с postgres). Однако перевод должен быть простым.

--  Table #Test: 
--  sequenceno  measurements
--  ----------- ------------
--  1           1.5
--  2           1.4
--  3           1.8
--  4           2.6
--  5           3.7
--  6           3.5
--  7           3.0
--  8           2.6
--  9           2.5
--  10          2.8

WITH datapoints
AS
(
    SELECT  sequenceno,
            measurements,
            startmeasurement    = measurements,
            groupno             = 0
    FROM    #Test
    WHERE   sequenceno = 1

    UNION ALL

    SELECT  sequenceno          = A.sequenceno + 1,
            measurements        = B.measurements,
            startmeasurement    = 
                CASE 
                WHEN abs(B.measurements - A.startmeasurement) >= 1 THEN B.measurements
                ELSE A.startmeasurement
                END,
            groupno             = 
                A.groupno + 
                CASE 
                WHEN abs(B.measurements - A.startmeasurement) >= 1 THEN 1
                ELSE 0
                END
    FROM    datapoints as A
            INNER JOIN #Test as B
                ON A.sequenceno  + 1 = B.sequenceno
) 
SELECT  sequenceno,
        measurements,
        groupno
FROM    datapoints
ORDER BY
        sequenceno

--  Output:
--  sequenceno  measurements    groupno
--  ----------- --------------- -------
--  1           1.5             0
--  2           1.4             0
--  3           1.8             0
--  4           2.6             1
--  5           3.7             2
--  6           3.5             2
--  7           3.0             2
--  8           2.6             3
--  9           2.5             3
--  10          2.8             3

Обратите внимание, что я добавил столбец " sequenceno " в исходную таблицу, потому что реляционные таблицы считаются неупорядоченными наборами. Кроме того, если количество входных значений слишком велико (более 90–100), возможно, вам придется настроить значение MAXRECURSION (по крайней мере, в SQL Server).

Дополнительные примечания: только что заметил, что в исходном вопросе упоминаетсячто во входных наборах данных есть миллионы записей. Подход CTE будет работать только в том случае, если эти данные можно будет разбить на управляемые куски.

Answer 2

Можно ли достичь цели, используя PARTITION OVER, CTE или любой другой вид SELECT?

Это по своей природе процессуальное проблема . В зависимости от того, с чего вы начнете, все последующие строки могут оказаться в другой группе и / или с другим значением группы. Оконные функции (с использованием предложения PARTITION) не годятся для этого.

Вы можете использовать рекурсивный CTE :

WITH RECURSIVE rcte AS (
   (
   SELECT id
        , measurement
        , measurement - 1 AS grp_min
        , measurement + 1 AS grp_max
        , 1 AS grp
   FROM   tbl
   ORDER  BY id
   LIMIT  1
   )

   UNION ALL
   (
   SELECT t.id
        , t.measurement
        , CASE WHEN t.same_grp THEN r.grp_min ELSE t.measurement - 1 END  -- AS grp_min 
        , CASE WHEN t.same_grp THEN r.grp_max ELSE t.measurement + 1 END  -- AS grp_max
        , CASE WHEN t.same_grp THEN r.grp     ELSE r.grp + 1         END  -- AS grp
   FROM   rcte r 
   CROSS  JOIN LATERAL (
      SELECT *, t.measurement BETWEEN r.grp_min AND r.grp_max AS same_grp
      FROM   tbl t
      WHERE  t.id > r.id
      ORDER  BY t.id
      LIMIT  1
      ) t
   )
   )
SELECT id, measurement, grp
FROM   rcte;

Это элегантно. И прилично быстро. Но только примерно так же быстро или даже медленнее, чем - процедурная языковая функция с одним циклом над множеством - при эффективной реализации:

CREATE OR REPLACE FUNCTION f_measurement_groups(_threshold numeric = 1)
  RETURNS TABLE (id int, grp int, measurement numeric) AS
$func$
DECLARE
   _grp_min numeric;
   _grp_max numeric;
BEGIN
   grp := 0;  -- init

   FOR id, measurement IN
      SELECT * FROM tbl t ORDER BY t.id
   LOOP
      IF measurement BETWEEN _grp_min AND _grp_max THEN
         RETURN NEXT;
      ELSE
         SELECT INTO grp    , _grp_min                , _grp_max
                     grp + 1, measurement - _threshold, measurement + _threshold;
         RETURN NEXT;
      END IF;
   END LOOP;
END
$func$ LANGUAGE plpgsql;

Вызов:

SELECT * FROM f_measurement_groups();  -- optionally supply different threshold

db <> fiddle здесь

Мои деньги идут на процедурную функцию.
Как правило, решения на основе множеств быстрее. Но не при решении изначально процедурной проблемы.

Связанные:

• GROUP BY и агрегированные последовательные числовые значения

Answer 3

Вы, кажется, начинаете группу, когда разница между строками превышает 0,5. Если я предполагаю, что у вас есть столбец заказа, вы можете использовать lag() и совокупную сумму, чтобы получить свои группы:

select t.*,
       count(*) filter (where prev_value < value - 0.5) as grouping
from (select t.*,
             lag(value) over (order by <ordering col>) as prev_value
      from t
     ) t