从两个多对多列中获取唯一值对

Question

两个来自同一表的列，存在多对多关系。换句话说，ID 1可能与matchID A或B匹配。同时，matchID A可能与ID 1、2或3匹配。

| ID | matchID |
|----|---------|
| 1  | A       |
| 1  | B       |
| 2  | A       |
| 2  | B       |
| 3  | A       |
| 3  | C       |

期望的输出是每个ID仅与一个不同的matchID关联，例如，一旦ID 1与matchID A关联，其他ID就不能再与matchID A关联。

期望得到如下输出：

| ID | matchID |
|----|---------|
| 1  | A       |
| 2  | B       |
| 3  | C       |

Asons · Answer

WITH RankedMatches AS (
  SELECT
    ID,
    matchID,
    ROW_NUMBER() OVER (PARTITION BY matchID ORDER BY ID) AS rn
  FROM
    your_table_name
)
SELECT
  ID,
  matchID
FROM
  RankedMatches
WHERE
  rn = 1;

该查询假定当给定matchID存在多个匹配项时，您希望优先选择ID最小的记录。如果您想根据其他列进行优先级排序，可以在ROW_NUMBER()函数内的ORDER BY子句中相应地调整。

Stephen C · Answer

以下是一个基于递归公共表表达式（Recursive Common Table Expression，CTE）的解决方案，用于探寻可能的分配方案，并找到满足唯一性条件的一种。

查询首先会识别所有唯一的Key1值并按其选项最少的顺序进行排序，以便先处理选项最少的键。它将尝试分配所有可能的映射，然后对于每个额外的Key1值递归重复该过程。在每一级递归中，都会检查可用的Key2值是否已存在于已分配值列表中，若有匹配项则跳过。任何在达到最终Key1值时找到符合条件的Key2映射的递归分支都将被视为一个成功的映射。

使用形如“|Key1=Key2|Key1=Key2|...|”的合并字符串值来存储在递归层级下构建的工作映射。此字符串既用于检查已分配的Key2值，也用于生成成功完成映射后的最终结果。

可能存在多种可能的映射，但只会任意选择其中一个作为最终结果。一旦选定完整的映射，就会解析这些映射并选择为最终结果。

如果找不到成功的映射，此查询将悄悄地返回无结果。

每一级递归都有可能以N倍的方式增加可能性，其中N是当前键可用的选择数。这可能导致资源使用的指数增长。理想情况下，在紧张场景中，深度优先的递归执行计划会有最佳性能（相较于广度优先）。然而，SQL Server并未实现选择这种首选行为的选项。因此，SQL Server可能会使用两种方式中的任意一种。结果是，对于除极小数据集之外的情况，性能可能无法接受。若性能存在问题，建议在更通用的编程环境中执行这项工作。

DECLARE @Delim1 CHAR = '|' -- 选择的字符必须不在数据中出现
DECLARE @Delim2 CHAR = '='

;WITH CTE_Key1List AS (
    -- 获取键的唯一列表，按照拥有选项数量降序排列，
    -- 这样选项最少的键将首先被处理。这样有望在紧张情况下减少回溯。
    SELECT Key1, ROW_NUMBER() OVER(ORDER BY COUNT(*) DESC) AS RowNum
    FROM Data
    GROUP BY Key1
),
CTE_Solver AS (
    -- CTE引导：
    -- 从MAX(RowNum)开始逆向处理，为选定的Key1值选取第一组候选映射
    -- 构建形如"|Key1=Key2|Key1=Key2|...|"的映射列表。
    SELECT
        K.RowNum,
        CAST(CONCAT(@Delim1, D.Key1, @Delim2, D.Key2, @Delim1) AS VARCHAR(MAX)) AS Mapping
    FROM CTE_Key1List K
    JOIN Data D ON D.Key1 = K.Key1
    WHERE K.RowNum = (SELECT MAX(RowNum) FROM CTE_Key1List)
    -- CTE递归：
    -- 对于每一下一个较低的RowNum值直到1，包含下一个Key1值的候选映射。
    -- 排除任何试图重用已分配Key2值的情况。
    UNION ALL
    SELECT
        K.RowNum,
        CONCAT(S.Mapping, D.Key1, @Delim2, D.Key2, @Delim1) AS Mapping
    FROM CTE_Solver S
    JOIN CTE_Key1List K
        ON K.RowNum = S.RowNum - 1 
    JOIN Data D
        ON D.Key1 = K.Key1
        AND CHARINDEX(CONCAT(@Delim2, D.Key2, @Delim1), S.Mapping) = 0 -- 未使用的Key2值
    WHERE S.RowNum > 1
),
CTE_Result AS (
    SELECT R.Key1, R.Key2
    FROM (
        -- 从可能的多个成功映射中获取一个
        SELECT TOP 1 TRIM(@Delim1 FROM S.Mapping) AS TrimmedMapping
        FROM CTE_Solver S
        WHERE S.RowNum = 1
    ) S
    -- 将映射列表分割成单个Key1=Key2对
    CROSS APPLY STRING_SPLIT(S.TrimmedMapping, @Delim1) M
    -- 定位等号分隔符并将两个值分开。
    CROSS APPLY (SELECT CHARINDEX(@Delim2, M.value) SplitPos) P
    CROSS APPLY (
        SELECT
            Key1 = CAST(LEFT(M.value, P.SplitPos - 1) AS INT),
            Key2 = STUFF(M.value, 1, P.SplitPos, '')
    ) R
)
-- 通过适当注释和取消注释最后的SELECT语句，可以查看中间结果。
--SELECT * FROM CTE_Solver S                          -- 所有工作步骤（无序）
--SELECT * FROM CTE_Solver S ORDER BY MapList         -- 所有工作步骤（有序）
--SELECT * FROM CTE_Solver S WHERE S.RowNum = 1       -- 所有解决方案
--SELECT TOP 1 * FROM CTE_Solver S WHERE S.RowNum = 1 -- 一个解决方案
SELECT * FROM CTE_Result ORDER BY Key1                -- 解决方案详细信息

结果：

| Key1 | Key2 |
| ---- | ---- |
| 1    | A    |
| 2    | B    |
| 3    | C    |

请参阅这个db<>fiddle演示示例，其中包含了额外的测试数据。