DuckDB 图计算：人际关系连通分量三种实现

2026-03-26DuckDB Graph SQL Onager DuckPGQ

社交关系天然是一张图：A 认识 B，B 认识 C，则 A 与 C 虽无直接边，也同属一个圈子。把「能通过认识关系串起来的人」收成一组，本质就是无向图上的连通分量（Connected Components）。

本文用同一套样例数据，对比三种在 DuckDB 内落地的做法：纯 SQL 递归合并、Onager 连通分量、DuckPGQ 弱连通分量。

业务场景

问题描述

两张表：

表	字段	含义
`person`	`person_id`, `display_name`	人员主数据
`knows`	`person_a`, `person_b`, `relationship_type`	认识关系；`friend` 可信，`unknown` 忽略

规则：

每条可信的 knows 记录是一条无向边（A 认识 B 等同于 B 认识 A）。
传递闭包：A→B、B→C 则 A、B、C 同一圈子。
relationship_type = 'unknown' 不参与构图；没有任何可信边的人（孤立点）不输出。
输出：display_name、person_id、group_id、该圈子完整 all_members。

样例数据

DROP TABLE IF EXISTS person;
CREATE TABLE person AS
SELECT * FROM (VALUES
  ('alice', 'Alice'),
  ('bob',   'Bob'),
  ('carol', 'Carol'),
  ('dave',  'Dave'),
  ('eve',   'Eve'),
  ('frank', 'Frank'),
  ('grace', 'Grace')
) AS t(person_id, display_name);

DROP TABLE IF EXISTS knows;
CREATE TABLE knows AS
SELECT * FROM (VALUES
  ('alice', 'bob',   'friend'),
  ('bob',   'carol', 'friend'),
  ('carol', 'dave',  'friend'),
  ('eve',   'frank', 'friend'),
  ('alice', 'grace', 'unknown')  -- 不可信，忽略
) AS t(person_a, person_b, relationship_type);

图结构示意：

alice —— bob —— carol —— dave     → 圈子 1
eve —— frank                      → 圈子 2
grace                             → 仅有 unknown 边，不输出

期望结果（group_id 按 all_members 字典序编号）：

display_name	person_id	group_id	all_members
Alice / Bob / Carol / Dave	alice…dave	1	`[alice, bob, carol, dave]`
Eve / Frank	eve, frank	2	`[eve, frank]`

解决方案

三种方案解决的是同一个图问题，只是「如何求连通分量」不同。

方案一：递归 CTE 列表合并

思路：每条认识关系先变成两人集合，再在递归 CTE 里用 list_has_any 做重叠合并，直到集合不再变大——即「集合相交」语义下的传递闭包。

WITH RECURSIVE
seed AS (
    SELECT list_sort([person_a, person_b]) AS members
    FROM knows
    WHERE relationship_type = 'friend'
      AND person_a IS NOT NULL
      AND person_b IS NOT NULL
      AND person_a != person_b
),
person_groups AS (
    SELECT DISTINCT members, unnest(members) AS person
    FROM seed
),
merged_people AS (
    SELECT
        person,
        members AS all_members,
        len(members) AS member_count
    FROM person_groups
    UNION
    SELECT
        a.person,
        list_sort(list_distinct(flatten(array_agg(a.all_members || b.members)))) AS all_members_a,
        len(list_sort(list_distinct(flatten(array_agg(a.all_members || b.members))))) AS member_count
    FROM merged_people a
    JOIN person_groups b
      ON list_has_any(a.all_members, b.members)
     AND NOT list_has_all(a.all_members, b.members)
     AND a.person != b.person
    GROUP BY a.person, a.member_count
    HAVING len(all_members_a) > a.member_count
),
merged AS (
    SELECT person, all_members
    FROM merged_people
    QUALIFY row_number() OVER (PARTITION BY person ORDER BY member_count DESC) = 1
)
SELECT
    p.display_name,
    a.person AS person_id,
    DENSE_RANK() OVER (ORDER BY a.all_members) AS group_id,
    a.all_members
FROM merged a
LEFT JOIN person p ON a.person = p.person_id
ORDER BY group_id, a.person;

要点：

seed：每条 friend 边 → 排序后的两人列表。
递归步：当前圈子与另一条边集合有交集、但尚未完全包含时，合并扩圈。
QUALIFY ... ORDER BY member_count DESC：每人只保留最大合并结果。
零扩展依赖，适合环境受限、圈子不大的场景。

方案二：Onager 连通分量

Onager 是 DuckDB 社区图算法扩展。节点 ID 需为 BIGINT，因此先把 person_id 映射成数字，再调 onager_cmm_components。

INSTALL onager FROM community;
LOAD onager;

DROP TABLE IF EXISTS person_mapping;
CREATE TEMP TABLE person_mapping AS
SELECT
    ROW_NUMBER() OVER ()::BIGINT AS node_id,
    person_id
FROM (
    SELECT person_a AS person_id FROM knows WHERE relationship_type = 'friend'
    UNION
    SELECT person_b FROM knows WHERE relationship_type = 'friend'
);

DROP TABLE IF EXISTS person_edges;
CREATE TEMP TABLE person_edges AS
SELECT DISTINCT
    m1.node_id AS src,
    m2.node_id AS dst
FROM knows k
JOIN person_mapping m1 ON k.person_a = m1.person_id
JOIN person_mapping m2 ON k.person_b = m2.person_id
WHERE k.relationship_type = 'friend'
  AND k.person_a != k.person_b;

DROP TABLE IF EXISTS person_components;
CREATE TEMP TABLE person_components AS
SELECT node_id, component
FROM onager_cmm_components((SELECT src, dst FROM person_edges));

WITH component_members AS (
    SELECT
        pc.component,
        list_sort(array_agg(DISTINCT pm.person_id)) AS all_members
    FROM person_components pc
    JOIN person_mapping pm ON pc.node_id = pm.node_id
    GROUP BY pc.component
    HAVING len(list_sort(array_agg(DISTINCT pm.person_id))) > 1
),
person_with_groups AS (
    SELECT
        pm.person_id,
        cm.all_members,
        DENSE_RANK() OVER (ORDER BY cm.all_members) AS group_id
    FROM person_components pc
    JOIN person_mapping pm ON pc.node_id = pm.node_id
    JOIN component_members cm ON pc.component = cm.component
)
SELECT
    p.display_name,
    a.person_id,
    a.group_id,
    a.all_members
FROM person_with_groups a
LEFT JOIN person p ON a.person_id = p.person_id
ORDER BY a.group_id, a.person_id;

要点：

边直接来自 knows，无需自连接；Onager 默认按无向处理 src/dst。
HAVING len(...) > 1：过滤单人分量，与方案一对齐。
API：onager_cmm_components((SELECT src, dst FROM edges)) → (node_id, component)。

方案三：DuckPGQ 弱连通分量

DuckPGQ 提供 SQL/PGQ 属性图与图算法。先声明 PROPERTY GRAPH，再调用 weakly_connected_component（弱连通分量，边方向忽略——正适合「认识」这种双向语义）。

DuckPGQ 对 DuckDB 版本有兼容矩阵要求；DuckDB 2.0+ 需 SET active_grammar_extensions = ['duckpgq'] 才能解析 CREATE PROPERTY GRAPH。

INSTALL duckpgq FROM community;
LOAD duckpgq;
SET active_grammar_extensions = ['duckpgq'];

DROP TABLE IF EXISTS PersonNodes;
CREATE TEMP TABLE PersonNodes AS
SELECT person_id AS id
FROM (
    SELECT person_a AS person_id FROM knows WHERE relationship_type = 'friend'
    UNION
    SELECT person_b FROM knows WHERE relationship_type = 'friend'
);

DROP TABLE IF EXISTS KnowsEdges;
CREATE TEMP TABLE KnowsEdges AS
SELECT DISTINCT
    person_a AS src,
    person_b AS dst
FROM knows
WHERE relationship_type = 'friend'
  AND person_a != person_b
  AND person_a IN (SELECT id FROM PersonNodes)
  AND person_b IN (SELECT id FROM PersonNodes);

DROP PROPERTY GRAPH IF EXISTS social_graph;
CREATE PROPERTY GRAPH social_graph
    VERTEX TABLES (PersonNodes)
    EDGE TABLES (
        KnowsEdges
        SOURCE KEY (src) REFERENCES PersonNodes (id)
        DESTINATION KEY (dst) REFERENCES PersonNodes (id)
        LABEL Knows
    );

DROP TABLE IF EXISTS person_components;
CREATE TEMP TABLE person_components AS
SELECT
    id AS person_id,
    componentId AS component
FROM weakly_connected_component('social_graph', 'PersonNodes', 'Knows');

WITH component_members AS (
    SELECT
        component,
        list_sort(array_agg(DISTINCT person_id)) AS all_members
    FROM person_components
    GROUP BY component
    HAVING len(list_sort(array_agg(DISTINCT person_id))) > 1
),
person_with_groups AS (
    SELECT
        pc.person_id,
        cm.all_members,
        DENSE_RANK() OVER (ORDER BY cm.all_members) AS group_id
    FROM person_components pc
    JOIN component_members cm ON pc.component = cm.component
)
SELECT
    p.display_name,
    a.person_id,
    a.group_id,
    a.all_members
FROM person_with_groups a
LEFT JOIN person p ON a.person_id = p.person_id
ORDER BY a.group_id, a.person_id;

要点：

点表只收录出现在可信边上的人；边端点必须落在点表内。
LABEL Knows 供算法与后续 GRAPH_TABLE 模式匹配复用。
weakly_connected_component 参数为图名、点标签、边标签（字符串）。

对比

三种方案在样例上得到同一组圈子（Alice–Dave 与 Eve–Frank）；差异在依赖、写法与扩展性。

维度	递归 CTE	Onager	DuckPGQ
依赖	仅 DuckDB 内置	`INSTALL onager FROM community`	`INSTALL duckpgq FROM community` + 语法开关
建模	边→两人集合，再相交合并	`BIGINT` 点 + 边表	Property Graph（点/边/`Knows`）
核心算法	手写递归传递闭包	`onager_cmm_components`	`weakly_connected_component`
可读性	SQL 较长，语义偏「集合运算」	构图清晰，算法一行调用	最贴近图论表述，利于「找共同好友 / 最短认识路径」
性能特征	圈子大、重叠多时递归/聚合成本高	专用 CC 实现，中大规模更稳	适合已有 PGQ 管线；建图有约束检查开销
版本约束	宽	社区扩展，跟 DuckDB 版本矩阵	社区扩展；2.0+ 需 `active_grammar_extensions`
后续能力	难扩展到最短路 / PageRank 等	同扩展内有中心性、社区发现等	支持 `GRAPH_TABLE` / 路径模式 / PageRank 等

怎么选

无扩展权限、逻辑一次性：递归 CTE。
只要连通分量、易做成数值边表：Onager，代码最短。
还要写认识路径、共同好友、多算法：DuckPGQ，一次建图多次复用。

实现时注意

无向语义要一致：三种方案都按无向处理「认识」；若业务是单向关注，需改用有向连通 / 强连通，算法与边表都不同。
过滤条件对齐：一律只用 relationship_type = 'friend'，漂移会导致圈子分裂或误并。
孤立点：Grace 仅有 unknown 边，三种写法都不会进入输出。
group_id 稳定性：DENSE_RANK() OVER (ORDER BY all_members) 依赖列表排序；换序会改编号，成员集合不变。

小结

「A 认识 B、B 认识 C」是典型的无向连通分量问题。DuckDB 既可以纯 SQL 递归完成，也可以通过 Onager / DuckPGQ 用标准图算法表达；选型取决于环境约束与是否还要继续做图分析。同一套样例下三种写法结果对齐，可作为换成真实社交边表的对照基线。