求PostgreSQL实现双向唯一匹配且保留最多记录的SQL查询

问题描述 #

现有如下数据表：

# |                column1                |            column2
--------------------------------------------------------------------------------
1 |  3ed28be1-92a0-4cf0-a258-a0e248f9a15c | 8bc73931-fc5a-488e-9fa3-60fce65cf427
2 |  3ed28be1-92a0-4cf0-a258-a0e248f9a15c | b5861526-1ed2-4030-9064-333abb902da7
3 |  4c300c60-b4c0-4c9c-9d7d-081a503786ed | 5f04a419-fc0d-4683-a2f9-06abc2c18218
4 |  61ffe19a-91be-4649-8c31-607523798b39 | 8bc73931-fc5a-488e-9fa3-60fce65cf427
5 |  61ffe19a-91be-4649-8c31-607523798b39 | b5861526-1ed2-4030-9064-333abb902da7
6 |  67c28846-e602-4f44-aba4-f9372a38101f | 5f04a419-fc0d-4683-a2f9-06abc2c18218
7 |  7b3b0d03-b81b-4202-9ef4-39eafd99d176 | 8bc73931-fc5a-488e-9fa3-60fce65cf427
8 |  7b3b0d03-b81b-4202-9ef4-39eafd99d176 | b5861526-1ed2-4030-9064-333abb902da7

需要编写PostgreSQL查询，实现双向唯一匹配：column1和column2的每个值仅能出现一次，同时保留尽可能多的记录。例如合法结果可以是以下两种之一：

结果示例一 #

# |                column1                |            column2
--------------------------------------------------------------------------------
1 |  3ed28be1-92a0-4cf0-a258-a0e248f9a15c | 8bc73931-fc5a-488e-9fa3-60fce65cf427
3 |  4c300c60-b4c0-4c9c-9d7d-081a503786ed | 5f04a419-fc0d-4683-a2f9-06abc2c18218
5 |  61ffe19a-91be-4649-8c31-607523798b39 | b5861526-1ed2-4030-9064-333abb902da7

结果示例二 #

# |                column1                |            column2
--------------------------------------------------------------------------------
2 |  3ed28be1-92a0-4cf0-a258-a0e248f9a15c | b5861526-1ed2-4030-9064-333abb902da7
3 |  4c300c60-b4c0-4c9c-9d7d-081a503786ed | 5f04a419-fc0d-4683-a2f9-06abc2c18218
4 |  61ffe19a-91be-4649-8c31-607523798b39 | 8bc73931-fc5a-488e-9fa3-60fce65cf427

解决方案 #

这个问题本质是求二分图的最大匹配，在PostgreSQL中可以用递归CTE结合贪心策略实现，以下是两种可行的写法：

方法一：基于窗口函数的贪心匹配 #

WITH ranked_pairs AS (
    -- 给每个column1、column2的配对排序，random()保证随机选取，也可替换为按主键ID排序
    SELECT 
        column1,
        column2,
        ROW_NUMBER() OVER (PARTITION BY column1 ORDER BY random()) AS rn_col1,
        ROW_NUMBER() OVER (PARTITION BY column2 ORDER BY random()) AS rn_col2
    FROM your_table_name  -- 替换为你的实际表名
),
selected AS (
    -- 先选取每个column1和column2的首个可用配对
    SELECT 
        column1,
        column2,
        rn_col1,
        rn_col2
    FROM ranked_pairs
    WHERE rn_col1 = 1 AND rn_col2 = 1
    UNION ALL
    -- 递归选取下一个未被占用的配对
    SELECT 
        rp.column1,
        rp.column2,
        rp.rn_col1,
        rp.rn_col2
    FROM ranked_pairs rp
    JOIN selected s 
        ON (rp.column1 = s.column1 AND rp.rn_col1 = s.rn_col1 + 1)
        OR (rp.column2 = s.column2 AND rp.rn_col2 = s.rn_col2 + 1)
    WHERE rp.column1 NOT IN (SELECT column1 FROM selected)
        AND rp.column2 NOT IN (SELECT column2 FROM selected)
)
SELECT DISTINCT column1, column2 FROM selected;

方法二：递归逐步选取未使用的配对 #

WITH RECURSIVE match AS (
    -- 随机选取一条初始记录作为起点
    SELECT 
        t.column1,
        t.column2,
        ARRAY[t.column1] AS used_col1,
        ARRAY[t.column2] AS used_col2
    FROM your_table_name t
    ORDER BY random()
    LIMIT 1
    UNION ALL
    -- 每次选取一条column1和column2都未被使用过的记录
    SELECT 
        t.column1,
        t.column2,
        m.used_col1 || t.column1,
        m.used_col2 || t.column2
    FROM match m
    JOIN your_table_name t 
        ON t.column1 <> ALL(m.used_col1) 
        AND t.column2 <> ALL(m.used_col2)
    ORDER BY random()
    LIMIT 1
)
SELECT column1, column2 FROM match;

注意事项 #

• 替换代码中的your_table_name为你实际的数据表名称。
• 如果不需要随机匹配结果，将ORDER BY random()替换为你需要的排序规则（比如按原表的主键ID排序）。
• 两种方法均基于贪心算法，能保证column1和column2的每个值仅出现一次，且尽可能保留最多的记录。

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