如何用SQL实现等价ID字符串的分组算法？

现有表input_table包含id1和id2两列，列中存储代表ID的字符串。等价规则如下：

• 同一行中的两个ID互为等价
• 若某ID出现在另一行，则两行中的所有ID彼此等价（传递性）

目标是返回一个包含两列的结果表：一列是所有唯一ID，另一列是该ID所属的等价分组标识。

示例数据 #

create table input_table (
id1 varchar(100),
id2 varchar(100)
)

insert into input_table(id1,id2)
values
('a','b'),
('b','c'),
('d','a'),
('a','b'),
('f','g'),
('f','k'),
('l','m')

预期输出 #

| Id | Grouping |
| a  | 1        |
| b  | 1        |
| c  | 1        |
| d  | 1        |
| f  | 2        |
| g  | 2        |
| k  | 2        |
| l  | 3        |
| m  | 3        |

结果说明 #

• 第1行a与b等价，将二者分配至分组1
• 第2行b与c等价，因b已在分组1中，c归入分组1
• 第3行d与a等价，因a已在分组1中，d归入分组1
• 第4行a与b的关系已存在，无需处理
• 第5行f与g等价，二者均未在现有分组中，分配至分组2
• 第6行f与k等价，因f已在分组2中，k归入分组2
• 第7行l与m等价，二者均未在现有分组中，分配至分组3

解决方案SQL #

WITH all_ids AS (
    -- 收集所有唯一ID
    SELECT id1 AS id FROM input_table
    UNION
    SELECT id2 AS id FROM input_table
),
connected_components AS (
    -- 递归查找连通分量：以每个未访问的ID为起点，遍历所有等价ID
    SELECT 
        id AS root_id,
        id
    FROM all_ids
    WHERE id NOT IN (SELECT root_id FROM connected_components)
    UNION ALL
    SELECT 
        cc.root_id,
        CASE WHEN it.id1 = cc.id THEN it.id2 ELSE it.id1 END AS id
    FROM connected_components cc
    JOIN input_table it ON cc.id IN (it.id1, it.id2)
    WHERE CASE WHEN it.id1 = cc.id THEN it.id2 ELSE it.id1 END NOT IN (SELECT id FROM connected_components WHERE root_id = cc.root_id)
),
grouped_ids AS (
    -- 为每个连通分量分配唯一分组号
    SELECT 
        id,
        DENSE_RANK() OVER (ORDER BY root_id) AS Grouping
    FROM connected_components
)
SELECT id AS Id, Grouping
FROM grouped_ids
ORDER BY Grouping, Id;

逻辑说明 #

1. all_ids：收集表中所有出现过的唯一ID，避免遗漏任何需要分组的ID；
2. connected_components：通过递归CTE遍历每个连通分量，将同一等价组的ID关联到同一个根ID；
3. grouped_ids：使用DENSE_RANK()函数为每个根ID分配连续的分组编号，保证分组号无间隔；
4. 最终输出按分组号和ID排序的结果，与预期格式一致。

内容的提问来源于stack exchange，提问作者Nick Calenti