SQL 服务器：存储过程使用递归 CTE 查找与总数匹配的值

Question

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

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

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

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

当临时文件中只有几条记录时，这工作得相当快 table #t 但是当您删除评论和所有剩余记录（从 id 17 到 id 41）时，查询将永远进行，因为CTE 呈指数级增长。

有没有办法加快代码速度？我只需要第一个匹配的总数（列表锚点数据集是有序的，所以像 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

SQL 服务器：存储过程使用递归 CTE 查找与总数匹配的值

SQL Server: stored procedure using recursive CTE finding values matching a total

sql

sql-server

recursive-query

common-table-expression