How to join two tables but use each row only once

Question

I have two tables. One represents invoices that are still open (table #OPEN) and the other one represents available money (table #overpay). Both have a column USERID by which they can be joined:

CREATE TABLE #OVERPAY(OID INT, USERID CHAR(1), Rest INT)
CREATE TABLE #OPEN(IID INT, USERID CHAR(1), Amt INT, OpenROW INT)

The table #OPEN has a column OpenRow by which the open amounts are ordered (per user). I want to map entries from the table #OVERPAY to entries in the table #OPEN in the following way:

• An entry gets mapped when #OVERPAY.Rest >= #OPEN.AMT
• Smaller values in #OPEN.OpenRow get mapped first
• Each entry in #OVERPAY can only be used once
• Each entry in #OPEN can only be used once

The last two points in that list are what gives me a headache.

This is some mocked data:

OID    USERID   REST
--------------------
1      'A'      10 
2      'A'      15 
3      'F'      5
4      'H'      20 
5      'H'      5

INSERT INTO #OVERPAY(OID, USERID, Rest)
VALUES (1, 'A', 10), (2, 'A', 15), (3, 'F', 5),
       (4, 'H', 20), (5, 'H', 5)

OID    USERID   Amt   OpenRow
-----------------------------
1      'A'      10    1 
2      'A'      10    2
3      'A'      15    3 
4      'F'      5     1
5      'H'      15    1 
6      'H'      10    2
7      'P'      33    1

INSERT INTO #OPEN(IID, USERID, Amt, OpenROW)
VALUES (1, 'A', 10, 1), (2, 'A', 10, 2),
       (3, 'A', 15, 3), (4, 'F', 5, 1),
       (5, 'H', 15, 1), (6, 'H', 10, 2),
       (7, 'P', 33, 1)

The desired result would be:

OID    IID
----------
1      1
2      2
3      4
4      5

I know how I could do it with a CURSOR:

CREATE TABLE #map (OID INT, IID INT)
CREATE TABLE #usedIID(IID INT)

DECLARE @OID INT, @USERID CHAR(1), @Rest INT

DECLARE ov_cursor CURSOR FOR
    SELECT OID, USERID, REST
    FROM #OVERPAY

OPEN ov_cursor
FETCH NEXT FROM ov_cursor INTO @OID, @USERID, @REST

WHILE @@FETCH_STATUS = 0
BEGIN
    DECLARE @IID INT

    INSERT INTO #map (OID, IID)
    OUTPUT inserted.IID INTO #usedIID (IID)
        SELECT TOP 1 @OID, o.IID
        FROM #OPEN o
        LEFT JOIN #usedIID u ON u.IID = o.IID
        WHERE o.USERID = @USERID AND o.Amt <= @REST AND u.IID IS NULL

    FETCH NEXT FROM ov_cursor INTO @OID, @USERID, @REST
END

CLOSE ov_cursor
DEALLOCATE ov_cursor

But since this is horrible in terms of performance (I'm working with a huge set of data) I'm searching for an option to do it without any looping

Answer 1

Try dense_rank

SELECT OID, IID
FROM (
    SELECT op.OID, n.IID, OpenRow
      , dense_rank() over(partition by iid order by oid) rnkIid
      , dense_rank() over(partition by oid order by OpenRow) rnkOid
    FROM #OVERPAY op
    JOIN #OPEN n ON op.USERID = n.USERID AND op.Rest >= n.AMT
) t
WHERE rnkIid = rnkOid
ORDER BY OID, IID