Using CTE recursion for STACKING splittable items

2019-08-21 03:11发布

站内文章 / 前沿技术
43 0 0

问题:

I created a minimalistic sample data for the purpose of studying and presenting this interesting task. Bellow is code to setup test tables. The task is to distribute items into pre-set bins, while:

  • we cannot exceed maximum capacity of a bin
  • item can (should) be split, if it exceeds the remaining bin capacity
  • there's a bin (always first), which has "unlimited" (very high) capacity and anything that does not fit into regular bins has to end up here. While it is particular to this example, in broad terms, it demonstrates how to handle conditions in CTE.
  • we start to fill items starting from DueBin and proceeding backwards (in descending order).
  • bins might be used to their full capacity, or only partly, if there's not enough items to stack into

Upper chart shows stacked items, bottom shows matching pre-set bins. Results taken from solution with CURSORS

Bellow is a complete working solution using CURSORS, but this questions is about using CTE recursion to achieve this task. Obviously, I am learning CTE and seeking performance gain, which in my previous applications of CTE recursion was very significant.

Here is incorrect CTE code I created, it's not much of a help I guess. It's far from including all the required logic, such as splitting item or moving to previous bin with available capacity.
I admit having small experience with CTE recursion and struggling to employ it in this task.

DECLARE @MinDate Date
SELECT @MinDate = MIN(BinDateTime) FROM Test_Bins;

WITH CTEfill (DueBinID,BinDate,ItemID,Duration) AS (
    -- Anchor
    SELECT --TI.DueBinID, 
           -- (SELECT DATEADD(MINUTE,TI.Duration,MAX(BI.BinDateTime)) FROM Test_BinItems as BI WHERE BI.BinID = TI.DueBinID) as DueBinID, 
           (SELECT MAX(TB1.BinID) FROM Test_Bins as TB1 WHERE TB1.BinID <= TI.DueBinID AND TB1.BinCapacity - (SELECT SUM(TBI.Duration) FROM Test_BinItems as TBI WHERE TBI.BinID = TB1.BinID) > 0) as DueBinID,
           (SELECT MAX(TB1.BinDateTime) FROM Test_Bins as TB1 WHERE TB1.BinID <= TI.DueBinID AND TB1.BinCapacity - (SELECT SUM(TBI.Duration) FROM Test_BinItems as TBI WHERE TBI.BinID = TB1.BinID) > 0) as BinDate,
           TI.ItemID,
           CASE -- Get remaining (usually whole) item duration if enough capacity in selected bin is available, otherwise space left in selected bin
                WHEN TI.Duration - (SELECT SUM(BI1.Duration) FROM Test_BinItems as BI1)
                   < (SELECT BinCapacity FROM Test_Bins as BI2 WHERE BI2.BinID = TI.DueBinID) - (SELECT SUM(Duration) FROM Test_Items as TI2 WHERE TI2.DueBinID = TI.DueBinID) 
                THEN TI.Duration - (SELECT SUM(BI1.Duration) FROM Test_BinItems as BI1)
                ELSE (SELECT BinCapacity FROM Test_Bins as BI2 WHERE BI2.BinID = TI.DueBinID) - (SELECT SUM(Duration) FROM Test_Items as TI2 WHERE TI2.DueBinID = TI.DueBinID)
           END as Duration
    FROM Test_Items as TI

    UNION ALL   -- Add recursion to the initial elements

    SELECT DueBinID - 1, 
           (SELECT BinDate FROM Test_Bins as TB3 WHERE TB3.BinID = CTE.DueBinID - 1), 
           CTE.ItemID,
    --     CASE -- Get remaining (usually whole) item duration if enough capacity in selected bin is available, otherwise space left in selected bin
    --          WHEN (SELECT Duration FROM Test_Items as TI3 WHERE TI3.ItemID = CTE.ItemID) - (SELECT SUM(BI1.Duration) FROM Test_BinItems as BI1)
    --             < (SELECT BinCapacity FROM Test_Bins as BI2 WHERE BI2.BinID = CTE.DueBinID - 1) - (SELECT SUM(Duration) FROM Test_Items as TI2 WHERE TI2.DueBinID = CTE.DueBinID - 1) 
    --          THEN (SELECT Duration FROM Test_Items as TI3 WHERE TI3.ItemID = CTE.ItemID) - (SELECT SUM(BI1.Duration) FROM Test_BinItems as BI1)
    --          ELSE (SELECT BinCapacity FROM Test_Bins as BI2 WHERE BI2.BinID = CTE.DueBinID - 1) - (SELECT SUM(Duration) FROM Test_Items as TI2 WHERE TI2.DueBinID = CTE.DueBinID - 1)
    --     END as Duration
           CTE.Duration
    FROM CTEfill as CTE
    WHERE BinDate > @MinDate AND DueBinID > 0 -- AND Duration > 0           
)

INSERT INTO [dbo].[Test_BinItems]  -- create new item assignment to bin
            ([BinID]
            ,[BinDateTime]
            ,[ItemID]
            ,[Duration])
SELECT DueBinID, BinDate, ItemID, Duration FROM CTEfill;

SAMPLE DATA

CREATE TABLE Test_Bins(
    BinID INT,
    BinDateTime DateTime, 
    BinCapacity INT
)

-- Sample bins
INSERT INTO Test_Bins(BinID,BinDateTime,BinCapacity) VALUES (1,'2001-01-01 00:00', 9999);    -- **overflow** bin 
INSERT INTO Test_Bins(BinID,BinDateTime,BinCapacity) VALUES (2,'2019-07-15 06:45', 270);     -- new pre-set bin
INSERT INTO Test_Bins(BinID,BinDateTime,BinCapacity) VALUES (3,'2019-07-16 10:00', 540);     -- new pre-set bin
INSERT INTO Test_Bins(BinID,BinDateTime,BinCapacity) VALUES (4,'2019-07-17 00:30', 120);     -- new pre-set bin
INSERT INTO Test_Bins(BinID,BinDateTime,BinCapacity) VALUES (5,'2019-07-19 06:00', 480);     -- new pre-set bin
INSERT INTO Test_Bins(BinID,BinDateTime,BinCapacity) VALUES (6,'2019-07-22 07:15', 270);     -- new pre-set bin


CREATE TABLE Test_Items(
    DueBinID INT,
    ItemID INT,
    DueDate DateTime, 
    Duration INT
);

-- Sample items
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (5,418050,'2019-07-21',23); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (5,418053,'2019-07-19',183); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (5,418066,'2019-07-19',56); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (5,418077,'2019-07-19',32); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (5,418087,'2019-07-19',80); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (5,418091,'2019-07-19',38); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (5,418101,'2019-07-19',101); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (4,418113,'2019-07-18',125); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (4,418116,'2019-07-18',12); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (4,418124,'2019-07-18',6); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (4,418131,'2019-07-18',48); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (4,418134,'2019-07-18',70); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (4,418139,'2019-07-17',20); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (4,418156,'2019-07-17',80); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (4,418158,'2019-07-17',5); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (3,418168,'2019-07-16',18); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (3,418177,'2019-07-16',13); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (3,418179,'2019-07-16',45); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (3,418183,'2019-07-16',20); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (3,418294,'2019-07-16',20); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (2,418296,'2019-07-15',123); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (2,418298,'2019-07-15',242); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (2,418299,'2019-07-15',55); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (2,418301,'2019-07-15',74); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (1,418303,'2019-07-14',145); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (1,418305,'2019-07-13',88); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (1,418313,'2019-07-02',29); 
INSERT INTO Test_Items(DueBinID,ItemID,DueDate,Duration) VALUES (1,418414,'2019-06-21',17); 


CREATE TABLE Test_BinItems(
    BinID INT,
    BinDateTime DateTime, 
    ItemID INT,
    Duration INT
);

SOLUTION WITH CURSORS

DELETE FROM Test_BinItems   -- clear the assignment table

DECLARE @i INT
DECLARE @iDuration INT
DECLARE @iBinCapacity INT
DECLARE @iDueDate DATE
DECLARE @iItemID INT
DECLARE @iBinID INT
DECLARE @BinAvailableCapacity INT
DECLARE ItemCursor CURSOR FOR SELECT TI.ItemID FROM Test_Items as TI ORDER BY DueDate DESC -- create cursor

SET @i = 0

OPEN ItemCursor
FETCH NEXT FROM ItemCursor INTO @iItemID   -- get first item

PRINT CONCAT('STARTING @iItemID=',@iItemID)

WHILE @@FETCH_STATUS = 0
BEGIN
    SELECT @iDuration = Duration,   -- start with whole duration of an item
           @iDueDate = DueDate,     -- set due date of iterated item
           @iBinID = DueBinID       -- set starting bin as the due bin of iterated item
    FROM Test_Items WHERE ItemID = @iItemID   -- set variables for iterated item
    PRINT CONCAT('iITEM:   @iDuration=',@iDuration,'    @iDueDate=',@iDueDate,'    @iBinID=',@iBinID)

    WHILE @iDuration > 0  AND @i < 500           -- until we allocate whole duration of iterated item to bins (with safety limit of 500 iterations)
    BEGIN
        SET @BinAvailableCapacity = 
              (SELECT BinCapacity FROM Test_Bins WHERE BinID = @iBinID)                   -- whole bin capcacity
            - ISNULL((SELECT SUM(Duration) FROM Test_BinItems WHERE BinID = @iBinID),0)   -- minus already filled capacity
        PRINT CONCAT('INSETING @BinAvailableCapacity=',@BinAvailableCapacity)
        IF @BinAvailableCapacity > 0 -- if there is capacity to be used
        BEGIN
            -- Used duration in this iteration
            DECLARE @iUsedDuration INT
            IF @iDuration < @BinAvailableCapacity  -- if the item fits remaining bin capacity
            BEGIN 
                SET @iUsedDuration = @iDuration
                SET @iDuration = 0
            END
            ELSE  -- if the item does not fit remaining bin capacity, put only part of the item in
            BEGIN
                SET @iUsedDuration = @BinAvailableCapacity
                SET @iDuration = @iDuration - @iUsedDuration
            END

            -- Item date-time assigned in the bin
            DECLARE @iItemBinDateTime DateTime        -- stack date-TIME - where the item will start
            DECLARE @LastBinItemDTInBin DateTime      -- where the last inserted item starts
            SET @LastBinItemDTInBin = (SELECT MAX(BinDateTime) FROM Test_BinItems WHERE BinID = @iBinID)
            SET @iItemBinDateTime = ISNULL(DATEADD(MINUTE,(SELECT Duration FROM Test_BinItems WHERE BinDateTime = @LastBinItemDTInBin),@LastBinItemDTInBin),(SELECT BinDateTime FROM Test_Bins WHERE BinID = @iBinID))

            INSERT INTO [dbo].[Test_BinItems]  -- create new item assignment to bin
                       ([BinID]
                       ,[BinDateTime]
                       ,[ItemID]
                       ,[Duration])
                 VALUES
                       (@iBinID
                       ,@iItemBinDateTime
                       ,@iItemID
                       ,@iUsedDuration)
            PRINT CONCAT('INSETING @iBinID=',@iBinID,'    @iItemBinDateTime=',@iItemBinDateTime,'    @iItemID=',@iItemID,'    @iUsedDuration=',@iUsedDuration)

        END
        ELSE    -- if there's no capacity to be used, move to previous bin
        BEGIN 
            SET @iBinID = @iBinID - 1 
        END
    SET @i = @i + 1
    END

FETCH NEXT FROM ItemCursor INTO @iItemID
END

CLOSE ItemCursor
DEALLOCATE ItemCursor
标签： recursion cursor common-table-expression
举报

收藏的人(0)

Ta的文章 更多文章
登录 后发表评论
0条评论
还没有人评论过~