SQL 服务器 : stored procedure using recursive CTE finding values matching a total

Question

我需要根据 valex 的解决方案 recursive query in SQL Server 在存储过程中找到哪些值与所需的总数相匹配

假设 CTE anchor 记录集非常小，以下工作得很好

CREATE TABLE #t ([id] INT, [num] FLOAT);

DECLARE @wanted FLOAT = 100000

INSERT INTO #t ([id], [num])
VALUES (1, 17000), (2, 33000), (3, 53000), (4, 47000), (5, 10000),
       (6, 53000), (7, 7000), (8, 10000), (9, 20000), (10, 5000),
       (11, 40000), (12, 30000), (13, 10000), (14, 8000), (15, 8000),
       (16, 10000), (17, 74000)

 /* when you add more records the query becomes too slow, remove this comment
    to test*/
 /*,(18,10000),(19,78000),(20,10000),(21,10000),(22,80000),(23,19000), 
 (24,8000),(25,5000),(26,10000),(27,4000),(28,46000),(29,48000),(30,20000),
 (31,10000),(32,25000),(33,10000),(34,13000),(35,16000),(36,10000),
 (37,5000), 38,5000),(39,30000),(40,15000),(41,10000)*/
;

CREATE NONCLUSTERED INDEX [idx_id] ON #t ([id]);

WITH CTE AS
(
    SELECT 
        id, num AS CSum, 
        CAST(id AS VARCHAR(MAX)) AS path 
    FROM 
        #t
     WHERE num <= @wanted

    UNION ALL

    SELECT 
        #t.id, #t.num + CTE.CSum AS CSum, 
        CTE.path + ',' + CAST(#t.id AS VARCHAR(MAX)) AS path
    FROM
        #T 
    INNER JOIN 
        CTE ON #T.num + CTE.CSum <= @wanted AND CTE.id < #T.id
    WHERE
        #T.num + CTE.CSum <= @wanted 
)
SELECT TOP 1 Path
FROM CTE  
WHERE CTE.CSum = @wanted 
ORDER BY id

DROP TABLE #t

它将返回 3,4，这是前 2 行，其 [num] 值给出了@wanted 总数。

当临时表 #t 中只有几条记录时，这工作得相当快，但是当您删除评论和所有剩余记录(从 id 17 到 id 41)时，查询将永远持续下去，因为 CTE 呈指数增长。

有没有办法加速代码？我只需要第一个匹配的总数(列表 anchor 数据集是有序的，所以像 3,4 这样的结果比 8,20,22 好)

Answer 1

如果您采用迭代方法会怎么样？如果能够在找到解决方案后立即停止，这将非常简单。

这是快速组合在一起的，因此您可以进一步优化。我测试了您的示例(运行时间不到 1 秒)以及其他几种组合和深度级别。

Result Depth       Total       IdList     NumList
------ ----------- ----------- ---------- -------------
Found  1           100000      3,4        53000,47000

完整代码:

-- Configuration
DECLARE @wanted FLOAT = 100000
DECLARE @MaxDepth INT = 10 -- Customize how many levels you want to look
SET NOCOUNT ON
IF OBJECT_ID('tempdb..#T') IS NOT NULL DROP TABLE #T
IF OBJECT_ID('tempdb..#T') IS NULL BEGIN
    CREATE TABLE #T (Id INT, Num INT)
    INSERT INTO #t ([id], [num])
    VALUES (1, 17000), (2, 33000), (3, 53000), (4, 47000), (5, 10000),
        (6, 53000), (7, 7000), (8, 10000), (9, 20000), (10, 5000),
        (11, 40000), (12, 30000), (13, 10000), (14, 8000), (15, 8000),
        (16, 10000), (17, 74000)
    CREATE NONCLUSTERED INDEX [idx_id] ON #t ([id]);
END

-- Setup processing table
IF OBJECT_ID('tempdb..#U') IS NOT NULL DROP TABLE #U
CREATE TABLE #U (
    MaxId INT,
    Total INT,
    IdList VARCHAR(MAX),
    NumList VARCHAR(MAX)
)

-- Initial population from source table
INSERT #U
    SELECT Id, Num,
        CONVERT(VARCHAR(10), Id), 
        CONVERT(VARCHAR(10), Num)
    FROM #T

-- Iterative approach
DECLARE @Depth INT = 0
WHILE NOT EXISTS (SELECT * FROM #U WHERE Total = @wanted) BEGIN

    -- Increment depth
    SET @Depth = @Depth + 1
    IF @Depth >= @MaxDepth BEGIN
        PRINT 'Max depth reached'
        RETURN -- Stop processing further
    END

    -- Calculate sum for this depth
    IF OBJECT_ID('tempdb..#V') IS NOT NULL
        DROP TABLE #V
    SELECT
        T.Id AS MaxId,
        U.Total + T.Num AS Total,
        U.IdList + ',' + CONVERT(VARCHAR(10), T.Id) AS IdList,
        U.NumList + ',' + CONVERT(VARCHAR(10), T.Num) AS NumList
        INTO #V
    FROM #U U
        INNER JOIN #T T
            ON U.MaxId < T.Id

    -- Replace data for next iteration
    TRUNCATE TABLE #U
    INSERT #U
        SELECT * FROM #V

    -- Check if no more combinations available
    IF @@ROWCOUNT = 0 BEGIN
        PRINT 'All combinations tested'
        RETURN -- Stop processing further
    END

END

-- Return result
SELECT TOP 1 'Found' AS [Result], @Depth AS Depth, Total, IdList, NumList FROM #U WHERE Total = @wanted