按组起点的差异分组

Question

我在 Postgres 数据库 table 中有很多测量值，当某些值与当前组的 "starting" 点相距太远时，我需要将这个集合分成几组（超过一些阈值）。排序顺序由 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 编写一个函数来做到这一点，但我正在寻找一种更有效的方法。性能非常重要，因为实际 table 包含数百万行。

是否可以通过使用 PARTITION OVER、CTE 或任何其他类型的 SELECT 来实现目标？

Answer 1

当行之间的差异超过 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

Answer 2

解决此问题的一种方法是使用递归 CTE。这个例子是使用 SQL 服务器语法编写的（因为我不使用 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

请注意，我在起始 table 中添加了一个“sequenceno”列，因为关系 table 被认为是无序集。此外，如果输入值的数量太大（超过 90-100），您可能需要调整 MAXRECURSION 值（至少在 SQL 服务器中）。

补充说明：刚刚注意到原题中提到输入数据集中有数百万条记录。 CTE 方法只有在数据可以分解为可管理的块时才有效。

Answer 3

Is it possible to achieve the goal by using PARTITION OVER, CTE or any other kind of SELECT?

这是一个固有的程序问题。根据您开始的位置，所有后面的行都可以在不同的组中结束和/或具有不同的组值。 Window functions（使用 PARTITION 子句）对此没有好处。

您可以使用recursive 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 here

我的钱在程序功能上。
通常，基于集合的解决方案更快。但在解决固有的程序问题时不会。

按组起点的差异分组

Group by difference from starting point of group

sql

postgresql

gaps-and-islands