BigQuery无向环图遍历实现：递归查询报错求解决方案

问题背景 #

我在BigQuery中有一张edges表，存储有向环图的边，包含node_from和node_to两个字段。需要从指定初始节点出发，以无向方式遍历整个连通图，返回所有可达节点。比如下图：

(a->b)
(c->b)
(c->d)

无论初始节点是a、b、c还是d，最终都要返回[a, b, c, d]。

我参考PostgreSQL的递归查询方案转换为BigQuery代码，但执行报错：

Query error: An unsupported query pattern using WITH RECURSIVE was detected (such as using IN or EXISTS within the recursive term). Please rewrite the query.

原转换代码如下：

CREATE temp TABLE edges (
`from` STRING,
`to` STRING
);

INSERT INTO edges (`from`, `to`) VALUES
('initial_node', 'a'), ('a', 'b'), ('a', 'c'), ('c', 'd');

WITH RECURSIVE graph AS (
SELECT ARRAY(SELECT DISTINCT `to` FROM `edges` WHERE `from` = 'initial_node') AS points
UNION ALL
SELECT points || ARRAY(SELECT DISTINCT `to` 
          FROM `edges` 
          WHERE `from` IN UNNEST(g.points) 
            AND `to` NOT IN UNNEST(g.points) 
            AND `to` != 'initial_node') AS points
FROM graph g
WHERE ARRAY_LENGTH(g.points) > 0
)
SELECT DISTINCT point
FROM graph
CROSS JOIN UNNEST(points) AS point
ORDER BY 1;

解决方案：BigQuery支持无向图遍历，需调整递归逻辑 #

BigQuery支持递归CTE，但对递归子句中的IN UNNEST()这类嵌套查询模式有限制，需要换一种方式跟踪已访问节点，避免不符合要求的语法结构。

正确实现代码 #

-- 模拟测试用的edges表（实际使用时替换为你的真实表）
CREATE TEMP TABLE edges (
  node_from STRING,
  node_to STRING
);

INSERT INTO edges (node_from, node_to) VALUES
('initial_node', 'a'), ('a', 'b'), ('a', 'c'), ('c', 'd');

-- 定义初始节点
DECLARE initial_node STRING DEFAULT 'initial_node';

WITH RECURSIVE traversal AS (
  -- 初始步骤：获取初始节点的直接邻居，同时记录已访问节点集合
  SELECT 
    node_to AS current_node,
    ARRAY_CONCAT([initial_node], [node_to]) AS visited_nodes
  FROM edges
  WHERE node_from = initial_node
  
  UNION ALL
  
  -- 递归步骤：遍历未访问过的节点，扩展已访问集合
  SELECT
    next_node,
    ARRAY_CONCAT(t.visited_nodes, [next_node]) AS visited_nodes
  FROM traversal t
  -- 无向遍历：同时检查出边和入边
  CROSS JOIN (
    SELECT node_to AS next_node FROM edges WHERE node_from = t.current_node
    UNION ALL
    SELECT node_from AS next_node FROM edges WHERE node_to = t.current_node
  ) neighbors
  -- 过滤已访问过的节点，避免循环
  WHERE NOT next_node IN UNNEST(t.visited_nodes)
)
-- 汇总所有可达节点，包含初始节点
SELECT DISTINCT node
FROM (
  -- 取出初始节点
  SELECT initial_node AS node
  UNION ALL
  -- 取出遍历过程中所有访问过的节点
  SELECT current_node AS node FROM traversal
)
ORDER BY node;

关键调整说明 #

• 无向遍历处理：通过UNION ALL同时查询node_from = current_node（出边）和node_to = current_node（入边），实现无向图的双向遍历逻辑。
• 规避递归子句限制：将邻居节点查询改为CROSS JOIN的形式，替代原代码中嵌套的ARRAY(SELECT ...)结构，符合BigQuery递归CTE的语法要求。
• 防止循环遍历：用数组visited_nodes记录所有已访问的节点，每次递归时过滤掉已在数组中的节点，避免重复遍历和死循环。
• 结果完整汇总：最终将初始节点和遍历到的所有节点合并，去重后按顺序返回。

内容的提问来源于stack exchange，提问作者Yung-Wen Lan