BigQuery中基于ID列关联的递归连接与子图聚合需求

示例表结构与数据 #

以下是表示ID间多对多关联的示例表SQL：

WITH t AS (
  SELECT 1 AS id_1, 'a' AS id_2
  UNION ALL SELECT 2, 'a'
  UNION ALL SELECT 2, 'b'
  UNION ALL SELECT 3, 'b'
  UNION ALL SELECT 4, 'c'
  UNION ALL SELECT 5, 'c'
  UNION ALL SELECT 6, 'd'
  UNION ALL SELECT 6, 'e'
  UNION ALL SELECT 7, 'f'
)
SELECT * FROM t

对应的表数据如下：

需求说明 #

需要通过递归连接并聚合行，找出每个由链接构成的独立子图（即所有相互连通的ID集合）。例如，1虽然没有直接关联到b，但通过路径1 --> a --> 2 --> b可与b连通，因此1、2、3和a、b属于同一个子图。

各ID的连通关系可分为4个独立子图：

• 1、2、3与a、b相互连通
• 4、5与c相互连通
• 6与d、e相互连通
• 7与f相互连通

期望输出 #

最终需要输出每个子图对应的ID集合，格式如下：

解决方案SQL #

WITH t AS (
  SELECT 1 AS id_1, 'a' AS id_2
  UNION ALL SELECT 2, 'a'
  UNION ALL SELECT 2, 'b'
  UNION ALL SELECT 3, 'b'
  UNION ALL SELECT 4, 'c'
  UNION ALL SELECT 5, 'c'
  UNION ALL SELECT 6, 'd'
  UNION ALL SELECT 6, 'e'
  UNION ALL SELECT 7, 'f'
),
-- 统一所有节点格式，区分id_1和id_2类型
nodes AS (
  SELECT CAST(id_1 AS VARCHAR) AS node, 'id1' AS type FROM t
  UNION
  SELECT id_2 AS node, 'id2' AS type FROM t
),
-- 递归遍历所有连通节点
recursive_cte AS (
  -- 初始节点：每个节点作为起始点
  SELECT node, node AS root FROM nodes
  UNION ALL
  -- 递归关联：通过原表的映射关系，找到连通的其他节点
  SELECT r.node, n.node AS root
  FROM recursive_cte r
  -- 关联原表，找到当前节点对应的关联项
  JOIN t 
    ON (r.type = 'id1' AND r.node = CAST(t.id_1 AS VARCHAR)) 
    OR (r.type = 'id2' AND r.node = t.id_2)
  -- 找到关联项对应的另一类节点
  JOIN nodes n 
    ON (n.type = 'id1' AND CAST(t.id_1 AS VARCHAR) = n.node) 
    OR (n.type = 'id2' AND t.id_2 = n.node)
  WHERE n.node <> r.root
),
-- 为每个节点确定所属的子图标识（取最小的根节点作为标识）
component AS (
  SELECT node, MIN(root) AS component_id
  FROM recursive_cte
  GROUP BY node
)
-- 聚合每个子图的id_1和id_2集合
SELECT
  STRING_AGG(DISTINCT CASE WHEN c.type = 'id1' THEN c.node END, ', ') AS id_1_coll,
  STRING_AGG(DISTINCT CASE WHEN c.type = 'id2' THEN c.node END, ', ') AS id_2_coll
FROM component cmp
JOIN nodes c ON cmp.node = c.node
GROUP BY cmp.component_id
ORDER BY id_1_coll;

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