如何用Hive SQL或Python按源/目标列分组关联节点？

给定用户连接表结构及数据：

需求是将所有通过src和dst关联的节点归为同一分组，得到如下结果：

下面分别给出Python和Hive SQL的实现方案：

Python实现（并查集算法） #

并查集是处理这类连通分量问题的经典方法，能高效合并关联节点并查询所属组。

# 定义并查集类
class UnionFind:
    def __init__(self):
        self.parent = {}
    
    def find(self, x):
        # 查找根节点，路径压缩优化
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        # 初始化节点
        if x not in self.parent:
            self.parent[x] = x
        if y not in self.parent:
            self.parent[y] = y
        # 合并两个节点的根
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            self.parent[root_y] = root_x

# 模拟输入数据
data = [(1,2), (1,3), (2,4), (4,5), (6,7)]

# 初始化并查集
uf = UnionFind()
for src, dst in data:
    uf.union(src, dst)

# 给每个根节点分配组号
root_to_grp = {}
current_grp = 1
for node in uf.parent:
    root = uf.find(node)
    if root not in root_to_grp:
        root_to_grp[root] = current_grp
        current_grp += 1

# 生成结果
result = []
for src, dst in data:
    grp = root_to_grp[uf.find(src)]
    result.append((src, dst, grp))

# 打印结果
print("| src | dst | grp |")
print("|-----|-----|-----|")
for row in result:
    print(f"| {row[0]}   | {row[1]}   | {row[2]}   |")

运行后就能得到需求的分组结果，逻辑清晰，处理大规模数据也有不错的效率。

Hive SQL实现（递归CTE） #

Hive 2.1.0及以上版本支持递归CTE，可以通过递归遍历找出每个节点的最终根节点，再统一分组编号。

-- 第一步：递归找出所有节点的关联关系
WITH RECURSIVE node_relation AS (
    -- 初始层：所有原始节点对
    SELECT src AS node, dst AS related_node FROM your_table
    UNION ALL
    -- 递归层：遍历所有关联节点，拓展连通链
    SELECT nr.node, t.dst AS related_node
    FROM node_relation nr
    JOIN your_table t ON nr.related_node = t.src
    WHERE nr.node != t.dst -- 避免循环遍历
),
-- 第二步：获取每个节点的最小根节点（用最小节点作为分组标识）
node_root AS (
    SELECT node, MIN(related_node) AS root_node
    FROM node_relation
    GROUP BY node
    UNION ALL
    -- 补充原始表中dst节点的根节点信息
    SELECT dst AS node, MIN(src) AS root_node
    FROM your_table
    GROUP BY dst
),
-- 第三步：去重并确定每个节点的最终根节点
final_root AS (
    SELECT node, MIN(root_node) AS final_root
    FROM node_root
    GROUP BY node
),
-- 第四步：给根节点分配连续的组号
root_group AS (
    SELECT final_root, DENSE_RANK() OVER(ORDER BY final_root) AS grp
    FROM final_root
    GROUP BY final_root
)
-- 关联原表得到最终分组结果
SELECT t.src, t.dst, rg.grp
FROM your_table t
JOIN final_root fr ON t.src = fr.node
JOIN root_group rg ON fr.final_root = rg.final_root
ORDER BY t.src, t.dst;

注意替换your_table为实际的表名。这个SQL通过递归遍历所有关联节点，找到每个节点的最小根节点作为分组标识，再用DENSE_RANK()生成组号，最终得到需求的结果。

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