Performing a running subtraction in T-SQL

Question

I'm sitting with two tables (although they're temp-tables) looking like this:

CREATE TABLE [dbo].[Invoice]
(
    [InvoiceId]     [int] NOT NULL,
    [ReceiverId]    [int] NOT NULL,
    [Amount]        [numeric](19, 2) NOT NULL,
    [Priority]      [int] NOT NULL
);
GO

CREATE TABLE [dbo].[Payment]
(
    [PaymentId] [int] NOT NULL,
    [SenderId]  [int] NOT NULL,
    [Amount]    [numeric](19, 2) NOT NULL
);
GO

The data could look something like this:

Invoice

InvoiceId   ReceiverId    Amount    Priority
        1            1    100.00           1
        2            1    100.00           2
        3            2    100.00           1
        4            2    100.00           2
        5            1    200.00           3

Payment

PaymentId   SenderId      Amount
        1          1        50.00
        2          1        45.00
        3          2        95.00
        4          2       105.00

Incoming payments are stored in Payment. My code's task is distributing the Payment.Amount between the sender's invoices.

The relationship-key between the two is ReceiverId and SenderId.

The Priority column is unique per ReceiverId and the value "1" is of higher priority than "2".

A Payment row with SenderId "1" could be used on an infinite number of invoices with the ReceiverId "1" - if there's not enough in the Payment.Amount column for all of them they'll be paid in accordance with their Priority.

I'm trying to think of a way to program this without using a loop or cursor. Any suggestions? (I'm sitting on SQL Server 2014).

My expected output would be:

1) Payment 1 and 2 would be used to partially pay Invoice 1.
2) Payment 3 would be used to partially pay Invoice 3.
3) Payment 4 would then complete invoice 3.
4) Payment 4 would then completely pay invoice 4.
5) Invoice 2 and 5 would be left completely unpaid.

Answer 1

The main idea

Think of your dollar amounts as intervals on the number line. Place your Invoices and Payments in correct order on the line adjacent to each other.

Invoices, Receiver/Sender ID=1

|----100---|----100---|--------200--------|----------->
0         100        200                 400
ID    1          2              5

Payments, Receiver/Sender ID=1

|-50-|-45|-------------------------------------------->
0   50  95
ID 1   2

Put both sets of intervals together (intersect them):

|----|---|-|----------|-------------------|----------->
0   50  95 100       200                 400

Now you have intervals:

From    To    InvoiceID    PaymentID
------------------------------------
   0    50            1            1
  50    95            1            2
  95   100            1
 100   200            2
 200   400            5

---

Invoices, Receiver/Sender ID=2

|----100---|----100---|------------------------------->
0         100        200                 
ID    3          4

Payments, Receiver/Sender ID=2

|--95----|-----105----|------------------------------->
0       95           200
ID   3          4

Put both sets of intervals together (intersect them):

|--------|-|----------|------------------------------->
0       95 100       200                 

Now you have intervals:

From    To    InvoiceID    PaymentID
------------------------------------
   0    95            3            3
  95   100            3            4
 100   200            4            4

---

For each of these intervals there can be at most one invoice and at most one payment (there can be none as well). Find which invoice and payment correspond to each of these intervals and you've got a mapping between your invoices and payments. Sum up all Payment intervals for each Invoice and you'll know whether invoice was paid in full or partially.

---

Building initial list of intervals separately for Invoices and Payments is done by running total.

SUM(Amount) OVER (PARTITION BY ReceiverId ORDER BY Priority 
    ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS InvoiceInterval

SUM(Amount) OVER (PARTITION BY SenderId ORDER BY PaymentID
    ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS PaymentInterval

Intersecting these two sets is a simple UNION.

For each interval find a corresponding Invoice and Payment. One simple way to do it is subquery in OUTER APPLY.

Let's put all this together.

Sample data

DECLARE @Invoice TABLE
(
    [InvoiceId]     [int] NOT NULL,
    [ReceiverId]    [int] NOT NULL,
    [Amount]        [numeric](19, 2) NOT NULL,
    [Priority]      [int] NOT NULL
);

DECLARE @Payment TABLE
(
    [PaymentId] [int] NOT NULL,
    [SenderId]  [int] NOT NULL,
    [Amount]    [numeric](19, 2) NOT NULL
);

INSERT INTO @Invoice(InvoiceId,ReceiverId,Amount,Priority) VALUES
(1, 1, 100.00, 1),
(2, 1, 100.00, 2),
(3, 2, 100.00, 1),
(4, 2, 100.00, 2),
(5, 1, 200.00, 3);

INSERT INTO @Payment(PaymentId, SenderId, Amount) VALUES
(1, 1,  50.00),
(2, 1,  45.00),
(3, 2,  95.00),
(4, 2, 105.00);

Query

WITH
CTE_InvoiceIntervals
AS
(
    SELECT
        I.InvoiceId
        ,I.ReceiverId AS ClientID
        ,I.Priority
        ,SUM(I.Amount) OVER (PARTITION BY I.ReceiverId ORDER BY I.Priority 
            ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS InvoiceInterval
    FROM @Invoice AS I
)
,CTE_PaymentIntervals
AS
(
    SELECT
        P.PaymentId
        ,P.SenderId AS ClientID
        ,P.PaymentId AS Priority
        ,SUM(P.Amount) OVER (PARTITION BY P.SenderId ORDER BY P.PaymentID
            ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW) AS PaymentInterval
    FROM @Payment AS P
)
,CTE_AllIntervals
AS
(
    SELECT
        ClientID
        ,InvoiceInterval AS Interval
    FROM CTE_InvoiceIntervals

    UNION

    SELECT
        ClientID
        ,PaymentInterval AS Interval
    FROM CTE_PaymentIntervals
)
SELECT *
FROM
    CTE_AllIntervals
    OUTER APPLY
    (
        SELECT TOP(1) CTE_InvoiceIntervals.InvoiceId
        FROM CTE_InvoiceIntervals
        WHERE
            CTE_InvoiceIntervals.ClientID = CTE_AllIntervals.ClientID
            AND CTE_InvoiceIntervals.InvoiceInterval >= CTE_AllIntervals.Interval
        ORDER BY
            CTE_InvoiceIntervals.InvoiceInterval
    ) AS A_Invoices
    OUTER APPLY
    (
        SELECT TOP(1) CTE_PaymentIntervals.PaymentId
        FROM CTE_PaymentIntervals
        WHERE
            CTE_PaymentIntervals.ClientID = CTE_AllIntervals.ClientID
            AND CTE_PaymentIntervals.PaymentInterval >= CTE_AllIntervals.Interval
        ORDER BY
            CTE_PaymentIntervals.PaymentInterval
    ) AS A_Payments
ORDER BY
    ClientID
    ,Interval;

Result

+----------+----------+-----------+-----------+
| ClientID | Interval | InvoiceId | PaymentId |
+----------+----------+-----------+-----------+
|        1 | 50.00    |         1 | 1         |
|        1 | 95.00    |         1 | 2         |
|        1 | 100.00   |         1 | NULL      |
|        1 | 200.00   |         2 | NULL      |
|        1 | 400.00   |         5 | NULL      |
|        2 | 95.00    |         3 | 3         |
|        2 | 100.00   |         3 | 4         |
|        2 | 200.00   |         4 | 4         |
+----------+----------+-----------+-----------+