Google BigQuery中大型表行复杂聚类的SQL实现问题

你之前用COALESCE组合多个独立聚类字段的思路是错的——因为那四个规则是传递关联的（比如a1和a2同组，a2和a3同组，那a1、a2、a3必须同组），而COALESCE只是取单个字段的非空值，完全没考虑不同聚类标识之间的连通性，自然会出现本该同组的ID被拆分、无关ID被错误合并的问题。

正确的思路是把所有规则转化为ID之间的关联边，然后用连通分量算法把所有互相连通的ID归为同一组。下面是具体实现步骤：

步骤1：标记ID首次出现时间（用于规则3） #

先预计算每个ID的首次交易时间，判断该ID在某交易中是否是首次出现：

WITH id_first_occurrence AS (
  SELECT
    id,
    MIN(tx_timestamp) AS first_tx_time
  FROM `your_project.your_dataset.your_transaction_table`
  GROUP BY id
)

步骤2：生成所有关联边 #

根据四条规则，生成所有需要关联的ID对（边），避免重复或无效边：

, edges AS (
  -- 规则1：同一tx且is_type_0=TRUE的所有ID两两关联
  SELECT
    t1.id AS id1,
    t2.id AS id2
  FROM `your_project.your_dataset.your_transaction_table` t1
  JOIN `your_project.your_dataset.your_transaction_table` t2
    ON t1.tx_id = t2.tx_id
    AND t1.is_type_0 = TRUE
    AND t2.is_type_0 = TRUE
    AND t1.id < t2.id -- 避免双向重复边（如a1-a2和a2-a1）
  UNION DISTINCT
  -- 规则2：同一tx且is_type_1=FALSE的所有ID两两关联
  SELECT
    t1.id AS id1,
    t2.id AS id2
  FROM `your_project.your_dataset.your_transaction_table` t1
  JOIN `your_project.your_dataset.your_transaction_table` t2
    ON t1.tx_id = t2.tx_id
    AND t1.is_type_1 = FALSE
    AND t2.is_type_1 = FALSE
    AND t1.id < t2.id
  UNION DISTINCT
  -- 规则3：同一tx中is_type_1=TRUE且首次出现的ID，与同tx内其他ID关联
  SELECT
    t1.id AS id1,
    t2.id AS id2
  FROM `your_project.your_dataset.your_transaction_table` t1
  JOIN `your_project.your_dataset.your_transaction_table` t2
    ON t1.tx_id = t2.tx_id
    AND t1.is_type_1 = TRUE
    AND t1.tx_timestamp = (SELECT first_tx_time FROM id_first_occurrence WHERE id = t1.id)
    AND t1.id != t2.id -- 排除自关联
  UNION DISTINCT
  -- 规则4：单个ID自身的关联（确保孤立ID能形成独立组）
  SELECT
    id AS id1,
    id AS id2
  FROM `your_project.your_dataset.your_transaction_table`
)

步骤3：递归计算连通分量 #

用递归CTE遍历所有关联边，把连通的ID归为同一组（用根ID作为聚类标识）：

, recursive_clusters AS (
  -- 初始化：每个ID作为自己的根节点
  SELECT
    id1 AS node,
    id1 AS cluster_root
  FROM edges
  UNION DISTINCT
  -- 递归遍历：合并关联的ID到同一根节点
  SELECT
    e.id2 AS node,
    r.cluster_root AS cluster_root
  FROM recursive_clusters r
  JOIN edges e
    ON r.node = e.id1
  WHERE e.id2 NOT IN (SELECT node FROM recursive_clusters)
)

步骤4：生成最终聚类结果 #

将原始表与聚类结果关联，得到每个ID对应的用户组：

SELECT
  t.id,
  -- 孤立ID（无任何关联）用自身作为聚类标识
  COALESCE(r.cluster_root, t.id) AS user_cluster_id
FROM `your_project.your_dataset.your_transaction_table` t
LEFT JOIN recursive_clusters r
  ON t.id = r.node
GROUP BY t.id, r.cluster_root
ORDER BY user_cluster_id, t.id

大表优化建议 #

如果你的表数据量极大，递归CTE可能遇到性能瓶颈，可以改用CONNECT BY语法实现连通分量（资源消耗更低）：

WITH id_first_occurrence AS (
  SELECT id, MIN(tx_timestamp) AS first_tx_time
  FROM `your_project.your_dataset.your_transaction_table`
  GROUP BY id
),
all_nodes AS (
  SELECT DISTINCT id FROM `your_project.your_dataset.your_transaction_table`
),
edges AS (
  SELECT id1, id2 FROM (
    -- 规则1的边
    SELECT t1.id AS id1, t2.id AS id2
    FROM `your_project.your_dataset.your_transaction_table` t1
    JOIN `your_project.your_dataset.your_transaction_table` t2
      ON t1.tx_id = t2.tx_id AND t1.is_type_0 = TRUE AND t2.is_type_0 = TRUE
    UNION ALL
    -- 规则2的边
    SELECT t1.id AS id1, t2.id AS id2
    FROM `your_project.your_dataset.your_transaction_table` t1
    JOIN `your_project.your_dataset.your_transaction_table` t2
      ON t1.tx_id = t2.tx_id AND t1.is_type_1 = FALSE AND t2.is_type_1 = FALSE
    UNION ALL
    -- 规则3的边
    SELECT t1.id AS id1, t2.id AS id2
    FROM `your_project.your_dataset.your_transaction_table` t1
    JOIN `your_project.your_dataset.your_transaction_table` t2
      ON t1.tx_id = t2.tx_id AND t1.is_type_1 = TRUE AND t1.tx_timestamp = (SELECT first_tx_time FROM id_first_occurrence WHERE id = t1.id)
    UNION ALL
    -- 规则4的自关联边
    SELECT id, id FROM all_nodes
  )
  WHERE id1 != id2
)
SELECT
  id,
  CONNECT_BY_ROOT(id) AS user_cluster_id
FROM all_nodes
CONNECT BY NOCYCLE id = PRIOR id2 OR id = PRIOR id1
GROUP BY id, CONNECT_BY_ROOT(id)

这个方案会正确处理所有规则的传递关联，比如a1、a2、a3会因为a2同时关联a1和a3而被归为同一组，也不会出现无关ID错误聚类的问题。

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