求T-SQL实现最少行覆盖所有含1的分类列的方案

核心思路 #

这是典型的集合覆盖NP难问题，针对15000行+35列的规模，精确求解最优解效率极低，因此采用贪心启发式算法：每次选择覆盖最多未覆盖分类的行，直到所有分类都被覆盖。方案完全动态，无需硬编码列名，可直接复用在其他含二进制分类列的表中。

完整实现代码 #

DECLARE @TableName NVARCHAR(128) = 'ProductCategory'; -- 替换为你的目标表名
DECLARE @IdColumn NVARCHAR(128) = 'ProductID'; -- 替换为表的主键/唯一标识列名

-- 1. 动态获取所有二进制分类列（bit类型或存为0/1的int列）
DECLARE @CategoryColumns NVARCHAR(MAX);
SELECT @CategoryColumns = STRING_AGG(QUOTENAME(c.name), ',')
FROM sys.columns c
JOIN sys.tables t ON c.object_id = t.object_id
WHERE t.name = @TableName
  AND c.name != @IdColumn
  AND EXISTS (
    SELECT 1 
    FROM sys.types ty 
    WHERE ty.system_type_id = c.system_type_id 
      AND ty.name IN ('bit', 'int')
  );

-- 2. 创建临时表存储状态：未覆盖的分类、已选中的行
DROP TABLE IF EXISTS #UncoveredCategories;
DROP TABLE IF EXISTS #SelectedRows;

CREATE TABLE #UncoveredCategories (CategoryName NVARCHAR(128) PRIMARY KEY);
INSERT INTO #UncoveredCategories (CategoryName)
SELECT REPLACE(REPLACE(value, '[', ''), ']', '') 
FROM STRING_SPLIT(@CategoryColumns, ',');

CREATE TABLE #SelectedRows (RowId INT PRIMARY KEY); -- 主键类型需与实际表匹配

-- 3. 贪心选择循环：每次选覆盖最多未分类的行
WHILE EXISTS (SELECT 1 FROM #UncoveredCategories)
BEGIN
    DECLARE @BestRowId INT;
    DECLARE @MaxCovered INT = 0;

    -- 动态计算每行覆盖的未分类数量，筛选最优行
    DECLARE @Sql NVARCHAR(MAX) = N'
        SELECT TOP 1 
            @BestRowId = p.' + @IdColumn + ', 
            @MaxCovered = COUNT(DISTINCT uc.CategoryName)
        FROM ' + @TableName + ' p
        UNPIVOT (
            IsActive FOR CategoryName IN (' + @CategoryColumns + ')
        ) up
        JOIN #UncoveredCategories uc ON up.CategoryName = uc.CategoryName
        WHERE up.IsActive = 1
        GROUP BY p.' + @IdColumn + '
        ORDER BY COUNT(DISTINCT uc.CategoryName) DESC';

    EXEC sp_executesql 
        @Sql, 
        N'@BestRowId INT OUTPUT, @MaxCovered INT OUTPUT', 
        @BestRowId OUTPUT, 
        @MaxCovered OUTPUT;

    -- 无可用行覆盖剩余分类时终止（理论上不会触发，前提是所有分类都有1值）
    IF @MaxCovered = 0 BREAK;

    -- 标记选中的行
    INSERT INTO #SelectedRows (RowId) VALUES (@BestRowId);

    -- 移除当前行已覆盖的分类
    SET @Sql = N'
        DELETE uc
        FROM #UncoveredCategories uc
        JOIN (
            SELECT up.CategoryName
            FROM ' + @TableName + ' p
            UNPIVOT (
                IsActive FOR CategoryName IN (' + @CategoryColumns + ')
            ) up
            WHERE p.' + @IdColumn + ' = ' + CAST(@BestRowId AS NVARCHAR) + ' 
              AND up.IsActive = 1
        ) up ON uc.CategoryName = up.CategoryName';

    EXEC sp_executesql @Sql;
END

-- 4. 输出最终选中的行（包含完整产品数据）
SELECT p.* 
FROM #SelectedRows sr
JOIN ' + @TableName + ' p ON sr.RowId = p.' + @IdColumn;

-- 清理临时资源
DROP TABLE IF EXISTS #UncoveredCategories;
DROP TABLE IF EXISTS #SelectedRows;

使用说明 #

1. 参数替换：修改开头的@TableName和@IdColumn为你的实际表名和主键列名
2. 列自动识别：代码会自动筛选非主键的bit/int类型列（默认视为0/1分类列）
3. 冗余控制：贪心算法的结果通常能达到最优解的90%以上，若需允许更多冗余，可在循环中加入终止条件（如剩余分类数<5时直接选中所有相关行）

性能优化建议 #

• 抽样处理：若表数据量极大，可先抽取10-20%的样本数据跑算法，再验证覆盖完整性，大幅提升执行速度
• 存储过程封装：将代码封装为带参数的存储过程，可直接在不同表上调用
• 索引优化：在分类列上创建非聚集索引，或对主键+分类列创建覆盖索引，加快UNPIVOT和分组计算速度

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