BigQuery如何按关联对链分组聚合？

问题场景 #

给定如下示例表：

pair0 | pair1
  a      z
  b      a
  c      b
  d      b
  m      n
  z      y

需要将所有连通的节点聚合成数组，最终返回：

matches
[a, z, b, c, d, y]
[m, n]

注：数组内元素顺序无要求。

解决方案代码 #

WITH sample_data AS (
  SELECT 'a' AS pair0, 'z' AS pair1 UNION ALL
  SELECT 'b' AS pair0, 'a' AS pair1 UNION ALL
  SELECT 'c' AS pair0, 'b' AS pair1 UNION ALL
  SELECT 'd' AS pair0, 'b' AS pair1 UNION ALL
  SELECT 'm' AS pair0, 'n' AS pair1 UNION ALL
  SELECT 'z' AS pair0, 'y' AS pair1
),
recursive_cte AS (
  -- 初始化：以每条记录的pair0为起始节点，初始连通集合包含pair0和pair1
  SELECT 
    pair0 AS node,
    ARRAY[pair0, pair1] AS connected_nodes
  FROM sample_data
  UNION ALL
  -- 递归遍历：将现有连通集合与样本表关联，合并新发现的连通节点
  SELECT
    rc.node,
    ARRAY(SELECT DISTINCT val FROM UNNEST(ARRAY_CONCAT(rc.connected_nodes, sd.pair0, sd.pair1)) AS val)
  FROM recursive_cte rc
  JOIN sample_data sd 
    ON sd.pair0 IN UNNEST(rc.connected_nodes) OR sd.pair1 IN UNNEST(rc.connected_nodes)
  -- 过滤已完全包含在当前集合中的pair，避免重复递归
  WHERE NOT (sd.pair0 IN UNNEST(rc.connected_nodes) AND sd.pair1 IN UNNEST(rc.connected_nodes))
)
-- 最终聚合：对同一连通组件去重并输出
SELECT 
  ARRAY_AGG(DISTINCT node ORDER BY node) AS matches
FROM (
  SELECT 
    node,
    -- 用排序后的连通数组作为分组键，确保同一组件的不同起始点归为一组
    ARRAY(SELECT val FROM UNNEST(connected_nodes) AS val ORDER BY val) AS sorted_connected
  FROM recursive_cte
)
GROUP BY sorted_connected
ORDER BY ARRAY_LENGTH(matches) DESC;

关键步骤说明 #

1. 样本数据CTE：替换为你的实际数据表即可，这里仅用于模拟场景。
2. 递归CTE：
   • 初始阶段：将每条关联对的两个节点作为初始连通集合，每个pair0作为遍历起始点。
   • 递归阶段：不断将当前连通集合与原表关联，把未加入集合的新节点合并进去，直到没有新节点可添加。
3. 最终聚合：
   • 通过排序连通数组生成统一的分组键，解决同一组件不同起始点的分组问题。
   • 聚合后去重，得到每个连通组件的完整节点数组。

注意事项 #

• 若数据量较大，可通过OPTIONS(max_recursion_depth=1000)调整递归深度限制（BigQuery默认递归深度为100）。
• 如需调整数组内元素顺序，修改ARRAY_AGG中的ORDER BY即可，也可直接移除该排序逻辑。

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