BigQuery中基于发票关联的订单分组实现需求

问题描述 #

现有BigQuery表结构如下：

orders      invoices
2100        [1,3]
1200        [3]
3300        [2]
1100        [1]
4400        [4]
3100        [2]

其中orders为数值类型，invoices为数值数组。需按以下规则分组：

• 若订单共享至少一张发票，或通过其他订单间接关联（如1200与1100通过2100关联），则归为同一组。
• 最终生成带group列的结果表，格式如下：

orders      invoices             group 
2100        [1,3]              A 
1200        [3]                A 
3300        [2]                B 
1100        [1]                A
4400        [4]                C 
3100        [2]                B

实现思路 #

这是典型的**连通分量（Connected Components）**问题：订单与发票构成二分图，需找出所有相互关联（直接/间接）的订单集合。在BigQuery中可通过递归CTE实现，步骤如下：

1. 将发票数组拆分为单行记录，建立订单与发票的一一对应关系；
2. 递归遍历关联关系，为每个连通分量分配唯一根节点；
3. 将根节点映射为A、B、C形式的分组标签。

完整SQL代码 #

假设目标表名为your_table，执行以下SQL：

WITH exploded AS (
  -- 拆分数组，生成订单-发票一对一记录
  SELECT 
    orders,
    invoice,
    invoices AS original_invoices
  FROM your_table, UNNEST(invoices) AS invoice
),
connected_components AS (
  -- 初始化：每个订单作为自身的根节点
  SELECT 
    orders AS node,
    orders AS root,
    invoice
  FROM exploded

  UNION ALL

  -- 递归关联：通过发票找到关联订单，统一根节点为分量中最小的订单号
  SELECT 
    e.orders AS node,
    cc.root,
    e.invoice
  FROM exploded e
  JOIN connected_components cc 
    ON e.invoice = cc.invoice 
    AND e.orders != cc.node
  WHERE e.orders > cc.root -- 避免循环遍历，仅处理根节点更大的订单
),
component_groups AS (
  -- 去重并关联原表，获取原始发票数组
  SELECT 
    DISTINCT node AS orders,
    root,
    original_invoices
  FROM connected_components
  JOIN your_table ON connected_components.node = your_table.orders
),
group_labels AS (
  -- 将根节点转换为A、B、C形式的分组标签
  SELECT 
    orders,
    original_invoices AS invoices,
    CHAR(65 + DENSE_RANK() OVER(ORDER BY root) - 1) AS `group`
  FROM component_groups
)

-- 输出最终结果
SELECT * FROM group_labels ORDER BY `group`, orders;

代码说明 #

• exploded：把每个订单的发票数组拆分为单独行，消除数组结构对关联的影响；
• connected_components：递归遍历所有关联的订单-发票关系，用分量中最小的订单号作为统一根节点，确保同一组的订单拥有相同根；
• component_groups：去重后关联原表，恢复每个订单的原始发票数组；
• group_labels：通过DENSE_RANK()为不同根节点分配序号，再转换为ASCII字母（65对应'A'），生成直观的分组标签。

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