T-SQL Challenges: Replenishing and Depleting Quantities

In this article I discuss two very interesting T-SQL challenges: replenishing quantities and depleting quantities. Both challenges involve ordered transactions that add and remove quantities of some object, and both challenges require you to compute a running state after every transaction. The solution would typically involve a simple running total calculation, but both the challenges I present here have specialized requirements that make it more complex to find an efficient solution.

I'll start with the replenishing quantities puzzle and present a highly efficient solution that makes very interesting use of a number of window functions. I'll then present the depleting quantities puzzle and leave it to you as a challenge to find an efficient solution. I haven't yet found an efficient relational solution for the challenge, but I'm hopeful that one exists.

The Replenishing Quantities Challenge

The replenishing quantities puzzle involves an ordered sequence of transactions that add and remove quantities of an object to the current stock. The object could be a product in a warehouse, for example. A positive quantity represents adding that quantity to the warehouse; a negative quantity represents removing that quantity from the warehouse—for example, to fulfil an order. The code in Listing 1 creates the Transactions table and fills it with a small set of sample data.

SET NOCOUNT ON;USE tempdb;IF OBJECT_ID(N'dbo.Transactions', N'U') IS NOT NULL DROP TABLE dbo.Transactions;CREATE TABLE dbo.Transactions(  txid INT NOT NULL PRIMARY KEY,  val  INT NOT NULL);-- Small set of sample data to check correctnessINSERT INTO dbo.Transactions(txid, val)  VALUES(1,2),(2,-5),(3,4),(4,1),(5,-10),(6,3),(7,1),(8,-2),(9,1),(10,-2),(11,1),(12,-9);GO

A classic calculation involving such transactions is to compute the expected stock level after every transaction. This is done with a basic calculation of the running total quantities (qty column) based on the order of the transactions (txid column). However, our puzzle has an interesting twist that makes it more difficult to solve. If the stock level falls below zero, you replenish the missing quantity from a different source. So in such a case you need to return the stock level 0 instead of the negative value, and return the replenish quantity in a separate column. Figure 1 shows the expected result for the small set of sample data.

txid    val     stocklevel  replenish----------- ----------- ----------- -----------1       2       2       02       -5      0       33       4       4       04       1       5       05       -10     0       56       3       3       07       1       4       08       -2      2       09       1       3       010      -2      1       011      1       2       012      -9      0       713      1       1       014      -1      0       015      0       0       016      1       1       017      -1      0       0

To test the performance of your solution, you'll need a larger set of sample data. Run the code in Listing 2 to create a helper function called GetNums. This function returns a sequence of integers between the @low and @high parameters that you provide as inputs.

IF OBJECT_ID(N'dbo.GetNums', N'IF') IS NOT NULL DROP FUNCTION dbo.GetNums;GOCREATE FUNCTION dbo.GetNums(@low AS BIGINT, @high AS BIGINT) RETURNS TABLEASRETURN  WITH    L0   AS (SELECT c FROM (SELECT 1 UNION ALL SELECT 1) AS D(c)),    L1   AS (SELECT 1 AS c FROM L0 AS A CROSS JOIN L0 AS B),    L2   AS (SELECT 1 AS c FROM L1 AS A CROSS JOIN L1 AS B),    L3   AS (SELECT 1 AS c FROM L2 AS A CROSS JOIN L2 AS B),    L4   AS (SELECT 1 AS c FROM L3 AS A CROSS JOIN L3 AS B),    L5   AS (SELECT 1 AS c FROM L4 AS A CROSS JOIN L4 AS B),    Nums AS (SELECT ROW_NUMBER() OVER(ORDER BY (SELECT NULL)) AS rownum         FROM L5)  SELECT TOP(@high - @low + 1) @low + rownum - 1 AS n  FROM Nums  ORDER BY rownum;GO

Next, run the code in Listing 3 to fill the Transactions table with 1,000,000 rows, using the helper function.

TRUNCATE TABLE dbo.Transactions;INSERT INTO dbo.Transactions(txid, val)  SELECT n, SIGN(1+2*SIGN(CHECKSUM(NEWID())))*(ABS(CHECKSUM(NEWID()))%10+1) AS val  FROM dbo.GetNums(1, 1000000) AS Nums;GO

Feel free to change the numbers if you want to test your solution with different table sizes.

Solution for the Replenishing Quantities Challenge

The most efficient relational solution that I know of for the replenishing quantities puzzle is a beautiful solution that uses window functions in a very interesting way.

The first step in the solution involves two computations. One computation is a simple running total (call it rt) of the quantities, based on the order of the transactions and computed using a window aggregate function. The rt computation represents the current stock level without taking the special replenishing requirement into consideration.

The other computation is the running minimum rt value (call it mn), based on the order of the transactions. Since the computation of mn involves a window function that aggregates the result of another window function, you define a CTE called C1 based on the query that computes rt; you then compute mn in an outer query against C1.

The following code implements the first step:

WITH C1 AS(  SELECT *,    SUM(val) OVER(ORDER BY txid ROWS UNBOUNDED PRECEDING) AS rt  FROM dbo.Transactions)SELECT *,  MIN(rt) OVER(ORDER BY txid ROWS UNBOUNDED PRECEDING) AS mnFROM C1;

Figure 2 shows the output of this code.

txid    val     rt      mn----------- ----------- ----------- -----------1       2       2       22       -5      -3      -33       4       1       -34       1       2       -35       -10     -8      -86       3       -5      -87       1       -4      -88       -2      -6      -89       1       -5      -810      -2      -7      -811      1       -6      -812      -9      -15     -15

The magic in the solution is mainly based on the realization that after each transaction, when mn is negative, -mn (read minus mn) is the total quantity that you had to replenish so far (call it replenish_rt). The first time rt falls below zero, -mn is clearly the replenish quantity after that transaction. The next time rt falls below the previous lowest rt marks the next replenish point, and the replenish quantity at that point is the difference between the absolute values of the current rt and the previous lowest rt. So the second step computes the running total replenish quantity (replenish_rt) as -mn when mn is negative and as 0 otherwise. The following code implements the second step in the solution:

WITH C1 AS(  SELECT *,    SUM(val) OVER(ORDER BY txid ROWS UNBOUNDED PRECEDING) AS rt  FROM dbo.Transactions),C2 AS(  SELECT *,    MIN(rt) OVER(ORDER BY txid ROWS UNBOUNDED PRECEDING) AS mn  FROM C1)SELECT txid, val, rt, replenish_rtFROM C2  CROSS APPLY (VALUES(CASE WHEN mn < 0 THEN -mn ELSE 0 END)) AS A(replenish_rt);

The computation of the replenish_rt column is performed using the CROSS APPLY operator in the FROM clause to make the column available throughout the query (FROM is the first clause to be logically evaluated). Figure 3 shows the output of the second step in the solution.

txid    val     rt      replenish_rt----------- ----------- ----------- ------------1       2       2       02       -5      -3      33       4       1       34       1       2       35       -10     -8      86       3       -5      87       1       -4      88       -2      -6      89       1       -5      810      -2      -7      811      1       -6      812      -9      -15     15

The last step in the solution defines a CTE called C2 based on the last query. Then the outer query computes two things: the correct stock level after taking the replenishing from the external source into consideration, and the replenish quantity itself. The correct stock level is the current rt value plus the current replenish_rt value. The current replenish quantity is the current replenish_rt value minus the previous value (or minus zero for the first transaction). You can use the LAG window function to obtain the previous replenish_rt value. The following code contains the complete solution for the challenge:

WITH C1 AS(  SELECT *,    SUM(val) OVER(ORDER BY txid ROWS UNBOUNDED PRECEDING) AS rt  FROM dbo.Transactions),C2 AS(  SELECT *,    MIN(rt) OVER(ORDER BY txid ROWS UNBOUNDED PRECEDING) AS mn  FROM C1)SELECT txid, val,  rt + replenish_rt AS stocklevel,  replenish_rt - LAG(replenish_rt, 1, 0) OVER(ORDER BY txid) AS replenishFROM C2  CROSS APPLY (VALUES(CASE WHEN mn < 0 THEN -mn ELSE 0 END)) AS A(replenish_rt);

Figure 4 shows the plan for this solution.

Plan for Solution for Replenishing Quantities Puzzle

It's amazing to see in the plan that the computation of all three window functions is done relying on the ordered scan of the clustered index (defined on txid as the key). Not even one explicit sort operator was needed. This query took 8 seconds to complete on my system against the large set of sample data.

The Depleting Quantities Challenge

The second puzzle I'll present was given to me by fellow SQL Server MVP Geri Reshef. I haven't yet found a good relational solution for the puzzle, so I'll leave it to you as a challenge (while I keep working on it as well).

Like the previous puzzle, this puzzle involves a sequence of transactions with associated quantities. This time the quantities are always nonnegative. Think about adding quantities of some object to a container. The requirement is to show the total quantity in the container after every transaction but to set it to zero whenever it exceeds 5. Think about a container with limited capacity that needs to be emptied whenever the quantity exceeds the capacity. Use the code in Listing 4 to fill the Transactions table with a small set of sample data to allow you to test the correctness of your solution.

TRUNCATE TABLE dbo.Transactions;INSERT INTO dbo.Transactions(txid, val)  VALUES(1,2),(2,500),(3,4),(4,1),(5,10),(6,3),(7,1),(8,2),(9,1),(10,2),(11,1),(12,9);

Figure 5 shows the desired result for the small set of sample data.

txid    val  newrt----------- ---- -----1       2    22       500  03       4    44       1    55       10   06       3    37       1    48       2    09       1    110      2    311      1    412      9    0

Use the code in Listing 5 to fill the Transactions table with a large set of sample data.

TRUNCATE TABLE dbo.Transactions;INSERT INTO dbo.Transactions(txid, val)  SELECT n, ABS(CHECKSUM(NEWID()))%11 AS val  FROM dbo.GetNums(1, 1000000) AS Nums;

There are straightforward solutions to the puzzle, using a T-SQL cursor, a recursive query, and CLR. However, as I mentioned, I haven't yet found a relational solution that performs well.

Your Mission, Should You Choose to Accept It

In this article I covered two T-SQL puzzles that involve a sequence of transactions with associated quantities, with the need to compute the stock level after every transaction. What makes the puzzles more difficult than classic stock-level puzzles is that both of the puzzles have specialized requirements. In the replenishing quantities puzzle, the stock level is set to zero whenever it falls below zero; in the depleting quantities puzzle, the stock level is set to zero whenever it exceeds 5.

I presented an efficient relational solution for the first puzzle, but I'm still looking for an efficient solution for the second puzzle. If you find an efficient solution, I'd be grateful to see it, and I'd be happy to share it with SQL Server Pro readers.