SQL分组interescting/overlapping行

Question

我在 Postgres 中有下表，在 a_sno 和 b_sno 两列中有重叠数据。

create table data
( a_sno integer not null,  
  b_sno integer not null,
  PRIMARY KEY (a_sno,b_sno)
);

insert into data (a_sno,b_sno) values
  ( 4, 5 )
, ( 5, 4 )
, ( 5, 6 )
, ( 6, 5 )
, ( 6, 7 )
, ( 7, 6 )
, ( 9, 10)
, ( 9, 13)
, (10, 9 )
, (13, 9 )
, (10, 13)
, (13, 10)
, (10, 14)
, (14, 10)
, (13, 14)
, (14, 13)
, (11, 15)
, (15, 11);

从前 6 行可以看出，两列中的数据值 4、5、6 和 7 相交/重叠，需要划分到一个组中。第 7-16 行和第 17-18 行也是如此，它们将分别标记为第 2 组和第 3 组。

结果输出应该是这样的:

group | value
------+------
1     | 4
1     | 5
1     | 6
1     | 7
2     | 9
2     | 10
2     | 13
2     | 14
3     | 11
3     | 15

Answer 1

假设所有对都存在于它们的镜像组合中，还有 (4,5) 和 (5,4)。但以下解决方案在没有镜像复制的情况下也能正常工作。

简单案例

所有连接都可以按单个升序排列，并且像我在 fiddle 中添加的那样复杂是不可能的，我们可以在 rCTE 中使用没有重复的解决方案:

我首先获取每个组的最小 a_sno，以及最小关联的 b_sno:

SELECT row_number() OVER (ORDER BY a_sno) AS grp
     , a_sno, min(b_sno) AS b_sno
FROM   data d
WHERE  a_sno < b_sno
AND    NOT EXISTS (
   SELECT 1 FROM data
   WHERE  b_sno = d.a_sno
   AND    a_sno < b_sno
   )
GROUP  BY a_sno;

这只需要一个查询级别，因为可以在聚合上构建窗口函数:

• Get the distinct sum of a joined table column

结果:

grp  a_sno  b_sno
1    4      5
2    9      10
3    11     15

我避免分支和重复(多行)行 - 长链可能多更昂贵。我在相关子查询中使用 ORDER BY b_sno LIMIT 1 来实现递归 CTE。

• Create a unique index on a non-unique column

性能的关键是匹配索引，它已经由 PK 约束 PRIMARY KEY (a_sno,b_sno) 提供:不是相反 (b_sno, a_sno ):

• Is a composite index also good for queries on the first field?

WITH RECURSIVE t AS (
   SELECT row_number() OVER (ORDER BY d.a_sno) AS grp
        , a_sno, min(b_sno) AS b_sno  -- the smallest one
   FROM   data d
   WHERE  a_sno < b_sno
   AND    NOT EXISTS (
      SELECT 1 FROM data
      WHERE  b_sno = d.a_sno
      AND    a_sno < b_sno
      )
   GROUP  BY a_sno
   )

, cte AS (
   SELECT grp, b_sno AS sno FROM t

   UNION ALL
   SELECT c.grp
       , (SELECT b_sno  -- correlated subquery
          FROM   data
          WHERE  a_sno = c.sno
          AND    a_sno < b_sno
          ORDER  BY b_sno
          LIMIT  1)
   FROM   cte  c
   WHERE  c.sno IS NOT NULL
   )
SELECT * FROM cte
WHERE  sno IS NOT NULL   -- eliminate row with NULL
UNION  ALL               -- no duplicates
SELECT grp, a_sno FROM t
ORDER  BY grp, sno;

不太简单的情况

所有节点都可以从根(最小的sno)开始按升序到达一个或多个分支。

这一次，获取所有更大的sno并在最后用UNION去重可能被多次访问的节点:

WITH RECURSIVE t AS (
   SELECT rank() OVER (ORDER BY d.a_sno) AS grp
        , a_sno, b_sno  -- get all rows for smallest a_sno
   FROM   data d
   WHERE  a_sno < b_sno
   AND    NOT EXISTS (
      SELECT 1 FROM data
      WHERE  b_sno = d.a_sno
      AND    a_sno < b_sno
      )
   )   
, cte AS (
   SELECT grp, b_sno AS sno FROM t

   UNION ALL
   SELECT c.grp, d.b_sno
   FROM   cte  c
   JOIN   data d ON d.a_sno = c.sno
                AND d.a_sno < d.b_sno  -- join to all connected rows
   )
SELECT grp, sno FROM cte
UNION                     -- eliminate duplicates
SELECT grp, a_sno FROM t  -- add first rows
ORDER  BY grp, sno;

与第一个解决方案不同，我们在这里没有得到最后一行 NULL(由相关子查询引起)。

两者都应该表现得很好 - 特别是对于长链/许多分支。结果如愿:

SQL Fiddle (添加行以展示难度)。

无向图

如果存在升序遍历无法从根到达的局部极小值，上述解决方案将不起作用。考虑 Farhęg's solution在这种情况下。