SQL/BigQuery-如何在不同列中按对链进行分组

Question

我正在尝试聚合成对链上的行。例如，给定的表格：

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

退货：

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

其中对的顺序无关紧要。

我已经尝试过将表本身连接起来，但如果不将连接放入循环中，就无法以这种方式进行聚合，因为可能的组合数量最多。

SELECT
[a.pair0, a.pair1, b.pair0, b.pair1] as matches
FROM pairs a
LEFT JOIN pairs b
ON a.pair0 = b.pair1
GROUP BY
matches

然后将过滤不同的匹配。但是，只有当链被限制为两行时，这个解决方案才有效。在上面的示例中，链延伸了5行。也不允许按数组分组。

Answer 1

BigQuery支持递归查询：耶！有了这个功能，我们可以尝试解决这个图行走问题。

这个想法是从生成所有可能的边开始，然后递归地查询遍历图，同时注意不要访问同一个节点两次。一旦访问了所有路径，我们就可以通过查看其访问节点的聚合列表来确定每个节点属于哪个组。

with recursive 
edges as (
select x.pair0, x.pair1
from pairs p
cross join lateral (
select p.pair0, p.pair1 union all select p.pair1, p.pair0
) x(pair0, pair1)
),
cte as (
select pair0, pair1, [ pair1 ] visited
from edges
union all
select c.pair0, e.pair1, array_concat(c.visited, [ e.pair1 ] )
from cte c
inner join edges e on e.pair0 = c.pair1 and e.pair1 not in unnest(c.visited)
),
res as (
select pair0, array_agg(distinct pair1 order by pair1) grp
from cte
group by pair0
)
select distinct grp from res