SQL Server: хранимая процедура, использующая рекурсивный CTE-поиск значений, соответствующих общему количеству - PullRequest
Новая
       66

SQL Server: хранимая процедура, использующая рекурсивный CTE-поиск значений, соответствующих общему количеству

0 голосов
/ 17 октября 2018

Мне нужно найти в хранимой процедуре, какие значения соответствуют искомому итоговому значению в соответствии с решением valex рекурсивный запрос в 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

Будет возвращено 3,4, которые являются первыми 2 строками, чьи значения [num] дают итоговое значение @wanted.

Это работает достаточно быстро, когда в записи всего несколько записей.временная таблица #t, но когда вы удаляете комментарий и все оставшиеся записи (от идентификатора 17 до идентификатора 41), запрос выполняется всегда, потому что CTE растет в геометрической прогрессии.

Есть ли способ ускорить код?мне просто нужно первое общее количество (набор данных привязки к списку упорядочен, поэтому результат как 3,4 лучше, чем 8,20,22)

1 Ответ

0 голосов
/ 18 октября 2018

Что если вы выбрали итеративный подход?Было бы довольно просто дать возможность остановиться, как только будет найдено решение.

Это было собрано быстро, так что вы можете оптимизировать дальше.Я протестировал для вашего примера (менее чем за 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
...