Group by running totals with reset

Question

Sample Data

Expected Data

Need to append trades under an order in a record, was able to do that using string_agg, now I need to split the orders with a maximum value of 10. That is, the quantity for the single order should not exceed 10 , need to combine trades under a single order as much as possible as fewer amended orders are desirable.

For example: I can combine tradeid 11 and 12, the running total is 9 but when I combine tradeid 13 it becomes 12 (exceeds 10) so that needs to be in a separate order.

Am aiming to rank the trades so that I can group by orderid and rank to get the result. Using SQL Server 2016.

Script to create the sample table.

create table #order
(
orderid varchar(100),
tradeid varchar(100),
quantity  int
)

insert into #order (orderid, tradeid, quantity)
values 
('a',    'a1',    5),
('a',    'a2',    4),
('a',    'a3',    3),
('a',    'a4',    12),
('b',    'b1',    9),
('b',    'b2',    8),
('b',    'b3',    7)

Second example

INSERT INTO @Test 
    (OrderID, TradeID, Qty)
VALUES ('a', 11, 5)
    , ('a', 12, 4)
    , ('a', 13, 3)
    , ('a', 14, 5)
    , ('a', 15, 1)
    , ('b', 21, 9)
    , ('b', 22, 8)
    , ('b', 23, 7)

Expected Result

In reality, the maximum would be about 1000 orders at 10 trades per order. A good approximate solution should be good enough.

Answer 1

Assuming you only want to pack the trades in strict trade ID order:

CREATE TABLE #Test
(
    OrderID char(1) NOT NULL,
    TradeID char(2) NOT NULL,
    Qty integer NOT NULL,

    PRIMARY KEY (OrderID, TradeID)
);

INSERT #Test 
    (OrderID, TradeID, Qty)
VALUES 
    ('a', '11', 5),
    ('a', '12', 4),
    ('a', '13', 3),
    ('a', '14', 5),
    ('a', '15', 1),
    ('b', '21', 9),
    ('b', '22', 8),
    ('b', '23', 7);

Recursive CTE solution

WITH R AS
(
    -- Recursive anchor
    -- Start with the lowest numbered trade per order
    SELECT 
        T.OrderID, 
        T.TradeID, 
        T.Qty,
        SumQty = T.Qty,
        TradeRank = 1
    FROM #Test AS T
    WHERE
        T.TradeID =
        (
            SELECT 
                MIN(T2.TradeID)
            FROM #Test AS T2
            WHERE
                T2.OrderID = T.OrderID
        )

    UNION ALL 

    -- Recurive part
    SELECT 
        R.OrderID,
        NextTrade.TradeID,
        Qty = NextTrade.Qty,
        -- Running sum
        SumQty = 
            IIF
            (
                -- Reset condition
                R.SumQty + NextTrade.Qty > 10, 
                -- Yes: Reset to current quantity
                NextTrade.Qty, 
                -- No: Add to running sum
                R.SumQty + NextTrade.Qty
            ),
        TradeRank = 
            R.TradeRank + 
            IIF
            (
                -- Increment rank when
                R.SumQty + NextTrade.Qty > 10, 
                1, 
                0
            )
    FROM R
    CROSS APPLY 
    (
        -- Find later trades for the current order
        SELECT
            T.OrderID, 
            T.TradeID, 
            T.Qty,
            RN = 
                ROW_NUMBER() OVER (
                    ORDER BY T.TradeID)
        FROM #Test AS T
        WHERE 
            T.OrderID = R.OrderID
            AND T.TradeID > R.TradeID
    ) AS NextTrade
    WHERE
        -- Choose the trade next in sequence
        NextTrade.RN = 1
)
SELECT
    R.OrderID, 
    R.TradeID, 
    R.Qty, 
    R.SumQty, 
    R.TradeRank 
FROM R
ORDER BY 
    R.OrderID, 
    R.TradeID
OPTION (MAXRECURSION 0);

Output

OrderID	TradeID	Qty	SumQty	TradeRank
a	11	5	5	1
a	12	4	9	1
a	13	3	3	2
a	14	5	8	2
a	15	1	9	2
b	21	9	9	1
b	22	8	8	2
b	23	7	7	3

With the other sample data set, the output is:

OrderID	TradeID	Qty	SumQty	TradeRank
a	a1	5	5	1
a	a2	4	9	1
a	a3	3	3	2
a	a4	12	12	3
b	b1	9	9	1
b	b2	8	8	2
b	b3	7	7	3

db<>fiddle demo

Execution plan

Answer 2

UPDATE: as macro32 pointed out, this does not actually work for all cases. I'm leaving it here because the bit that identifies all possible combinations that add up to the threshold CTE_RR does work, but I can't think of a way from there of grabbing unique sets (at least not at the moment).

So this answer is only here because it does manage to solve part of the problem.

Here is one possible solution for you that doesn't rely on loops or other cursor based approaches. It may not be the most performant solution but it does provide a list of order combinations that add up to the threshold specified, at least for the sample data provided.

/** DEFINE TestData
    NOTE: I have added an additional value to demonstrate how flexible this solution is
    **/

DECLARE @Test TABLE
    (
    OrderID NCHAR(10) NOT NULL
    , TradeID INT NOT NULL UNIQUE
    , Qty INT NOT NULL
    )

INSERT INTO @Test 
    (OrderID, TradeID, Qty)
VALUES ('a', 11, 5)
    , ('a', 12, 4)
    , ('a', 13, 3)
    , ('a', 14, 12)
    , ('a', 15, 1)
    , ('b', 21, 9)
    , ('b', 22, 8)
    , ('b', 23, 7)

/** OUTPUT TestData **/
SELECT * FROM @Test 

DECLARE @OrderThreshold INT = 10

/** NESTED CTE's for readability.  

    CTE_RR - This is a recursive CTE that will pair up all possible combinations that can equal the order threshold.
    CTE_RN - Adds a row number to the output
    CTE_Filtered - Does an initial pass to decide what needs to be kept.
        Any that is over the order threshold.
        Any combination of trades that equal the threshold (excluding those that are in a prior set).
    CTE_Final 
        Set 1 - Any that were determined to keep in the prior set.
        Set 2 - Any that are left over (not in a combination)

    **/

;WITH CTE_RR AS
    (
    SELECT R.OrderID 
        , R.TradeID
        , R.Qty 
        , Component = CONVERT(NVARCHAR(MAX), R.TradeID)
        , CumulativeQty = R.Qty 
    FROM @Test AS R
    UNION ALL
    SELECT R.OrderID 
        , R.TradeID
        , R.Qty
        , Component = COALESCE(RR.Component, N'') + ',' + CONVERT(NVARCHAR(MAX), R.TradeID)
        , CumulativeQty = RR.CumulativeQty + R.Qty
    FROM @Test AS R
        INNER JOIN CTE_RR AS RR ON RR.OrderID = R.OrderID 
    WHERE RR.CumulativeQty + R.Qty <= @OrderThreshold
        AND R.TradeID <> RR.TradeID
        AND R.TradeID > RR.TradeID 
        AND NOT ( COALESCE(RR.Component, N'') LIKE '%' + CONVERT(NVARCHAR(MAX), R.TradeID) + '%')
    )
, CT_RN AS
    (
    SELECT * 
        , RN = ROW_NUMBER() OVER (PARTITION BY OrderID ORDER BY CumulativeQty DESC)
    FROM CTE_RR
    )
, CTE_Filtered AS
    (
    SELECT F.*
        , IsKeep = CASE WHEN F.Qty >= @OrderThreshold THEN 1
                        WHEN F.CumulativeQty <= @OrderThreshold AND NOT EXISTS (    SELECT TOP (1) 1 
                                                                                    FROM CT_RN AS F2 
                                                                                        OUTER APPLY STRING_SPLIT(F2.Component, ',') AS P 
                                                                                    WHERE F2.OrderID = F.OrderID 
                                                                                        AND F2.RN < F.RN 
                                                                                        AND F2.TradeID <> TRY_CONVERT(INT, P.[value])
                                                                                        ) THEN 1
                        ELSE 0
                        END
    FROM CT_RN AS F
    )
, CTE_Final AS
    (
    SELECT *
    FROM CTE_Filtered AS F
    WHERE F.IsKeep = 1
    UNION ALL
    SELECT *
    FROM CTE_Filtered AS F
    WHERE F.IsKeep = 0
        AND TRY_CONVERT(INT, Component) = F.TradeID
        AND NOT EXISTS (    SELECT TOP (1) 1 
                            FROM CTE_Filtered AS F2
                                OUTER APPLY STRING_SPLIT(F2.Component, ',') AS P 
                            WHERE F2.IsKeep = 1
                                AND F2.OrderID = F.OrderID
                                AND F.TradeID = TRY_CONVERT(INT, P.[value])
                                )
    )
SELECT F.OrderID
    , F.Component AS TradeIDList
    , F.CumulativeQty
FROM CTE_Final AS F
ORDER BY F.OrderID
    , F.CumulativeQty DESC
OPTION (MAXRECURSION 0)