# SQL query for FIFO allocation of items

I have a real world business scenario but for the sake of clarity let me rephrase it as a simpler fictional problem.

We have Buyers and Items.

``````DECLARE @Buyer TABLE
(
BuyerId INT IDENTITY(1,1),
Name NVARCHAR(100),
Budget INT
);

INSERT @Buyer (Name, Budget) VALUES
('Anna', 100),
('Brett', 50),
('Conor', 20)

DECLARE @Item TABLE
(
ItemId INT IDENTITY(1,1),
Cost INT
);

INSERT @Item (Cost) VALUES (50),(30),(20),(40),(10),(40),(30),(10),(5);
``````

The goal is to craft a query (no loops or cursor) which allocates items to buyers, based on their budget. The most expensive items should be allocated in priority.

Expected result:

``````ItemId BuyerName
1  Anna
4  Anna
6  Brett
7  NULL
2  NULL
3  Conor
5  Anna
8  Brett
9, NULL
``````

From a logical perpective, this is what happens. First, the items are sorted by descending cost

``````ItemId Cost
1   50
4   40
6   40
7   30
2   30
3   20
5   10
8   10
9   5
``````

Then we go through each item and try to allocate it to a buyer that has enough budget left.

• Item 1 => Can be assigned to Anna. Anna's remaining budget is 100 - 50 = 50
• Item 4 => Can be assigned to Anna. Anna's remaining budget is 50 - 40 = 10
• Item 6 => Can be assigned to Brett. Brett's remaining budget is 50 - 40 = 10
• Item 7 => No one has enough budget left
• Item 2 => No one has enough budget left
• Item 3 => Can be assigned to Conor. Conor's remaining budget is 20 - 20 = 0
• Item 5 => Can be assigned to Anna. Anna's remaining budget is 10 - 10 = 0
• Item 8 => Can be assigned to Brett. Brett's remaining budget is 10 - 10 = 0
• Item 9 => No one has enough budget left
• Related – mustaccio Oct 7 '20 at 16:18
• I don't see how this is related at all? – Clement Oct 8 '20 at 14:19
• Both are variations of the "knapsack problem". – mustaccio Oct 8 '20 at 14:32
• The first item worth 50 can be assigned to Anna or to Brett. Why did you choose Anna? Does it matter which buyer to choose, as long as his budget allows it? In other words, you have defined an order for processing the items. Do you have any order/preference for processing buyers? The order in which we choose items and buyers affect the overall result. The optimal solution for a knapsack problem may be tricky in SQL. Some variation of the greedy algorithm may be possible to implement in SQL. – Vladimir Baranov Oct 12 '20 at 22:15
• @VladimirBaranov the order for buyer doesn't matter. Can you point me to this greedy algorithm solution you mentioned? – Clement Oct 13 '20 at 6:52

## 4 Answers

Nasty, but will do what you wanted:

``````DECLARE @Out TABLE (BuyerId int, ItemId int);
DECLARE @BuyerId int, @Budget int, @ItemId int, @Cost int;

WHILE EXISTS(SELECT TOP 1 Budget FROM @Buyer WHERE Budget >= (SELECT MIN(Cost) FROM @Item))
BEGIN
SELECT TOP 1 @BuyerId = BuyerId, @Budget = Budget
FROM @Buyer
WHERE Budget >= (SELECT MIN(Cost) FROM @Item)

SELECT TOP 1 @ItemId = ItemId, @Cost = Cost
FROM @Item
WHERE Cost <= @Budget
ORDER BY Cost DESC, ItemId ASC;

DELETE FROM @Item WHERE ItemId = @ItemId;
UPDATE @Buyer SET Budget -= @Cost WHERE BuyerId = @BuyerId;
INSERT INTO @Out VALUES(@BuyerId,@ItemId)
END
SELECT * FROM @Out
``````

UPDATE (2020-10-16):

Based on OPs comment I decided to try to do as much as possible using set based data flow. First of all solution requires to create all possible permutations without duplicates where the order doesn't matter. For that I used a recursive CTE, then out of all possible price sums we needed only these in the Buyers budget, then I ordered them form the most expensive set (as asked by OP) where we want most expensive item first then the most expensive still in the budget and so on. I ended up with having the order column, JSON array for ItemId and all other base data:

``````;WITH totalCostPermutations AS(
SELECT
ItemIndex = CAST(CONCAT('"',ItemId,'') as varchar(max)),
X = CAST(ROW_NUMBER() OVER (ORDER BY Cost DESC, ItemId ASC) as varchar(max)),
ItemId, Cost
FROM @Item
UNION ALL
SELECT
ItemIndex = CAST(CONCAT(i1.ItemIndex,'", "',i2.ItemId) as varchar(max)),
X = CONCAT(i1.X, ROW_NUMBER() OVER (ORDER BY i2.Cost DESC, i2.ItemId ASC)),
i2.ItemId, Cost = (i1.Cost + i2.Cost)
FROM totalCostPermutations i1
JOIN @Item i2 ON 1=1
AND i1.ItemId < i2.ItemId
)
SELECT
RN = ROW_NUMBER() OVER(PARTITION BY b.BuyerId ORDER BY Cost DESC, X ASC),
ItemId_JSON = CONCAT('{"ItemId":[',ItemIndex,'"]}'), TotalCost = Cost,  b.*
FROM totalCostPermutations c
JOIN @Buyer b ON c.Cost <= b.Budget;
``````

At this stage our data looks like this: But from this point I can't think of how could this be possible to tell which ItemId have already been "used" and which not, without looping. Still, from this output it won't be hard to either loop it in T-SQL or via the app.

• Thanks but I'm after a set-based solution with no loops. My apologies if that wasn't clear. – Clement Oct 14 '20 at 12:14
• You can probably do a second recursive CTE on top of this, or a join to itself, pseudocode: WHERE C1.RN = C2.RN + 1 AND C2.ItemId_JSON's values are not in C1.ItemId_JSON's values. (Might be better off losing the JSON array, and keeping each item ID in its own row for this purpose.) – J.D. Oct 19 '20 at 11:38
• Agree, that or JOIN driven by dynamic SQL to determinate how many buyers there are. I wanted to do it as far as the solution feels elegant. From this point I can bet that the best performance will be to just simply read it line by line - simply loop through the result, but this is not what the OP wanted. – Bartosz X Oct 19 '20 at 11:51
• I agree on the dynamic SQL as an option, that can be generated in a set based manner. Was thinking about that myself when I was going to tackle this one, but I bet it can be done even without it. I wish I had more time, I knew a recursive CTE was the way to go per my comment on the post, just haven't had the time to sit down and try to tackle this. – J.D. Oct 19 '20 at 12:52

This is incomplete, may be someone can finish it if possible.

``````DECLARE @Buyer TABLE
(
BuyerId INT IDENTITY(1,1),
Name NVARCHAR(100),
Budget INT
);

INSERT @Buyer (Name, Budget) VALUES
('Anna', 100),
('Brett', 50),
('Conor', 20)

DECLARE @Item TABLE
(
ItemId INT IDENTITY(1,1),
Cost INT
);

INSERT @Item (Cost) VALUES (50),(30),(20),(40),(10),(40),(30),(10),(5);

--select *,lag(cost) over(order by cost desc)from @Item
--return
Declare @rn int,@rn1 int
select @rn=count(*) from @Buyer

select @rn1=count(*) from @Item

;with CTE1 as
(
select *,ROW_NUMBER()over(order by cost desc) rownum from  @Item
)
,CTE as
(
select ItemId
, i.Cost
,BuyerId as rn
, rownum rn1
,rownum
,b.Budget,
i.Cost as Totalcost
--,case when i.cost<=b.Budget then b.Name end Buyer,
,1 rn2
,case when b.Budget>=cost then 1 else 0 end Status

from CTE1 I
, @Buyer B
where rownum=1
and b.BuyerId=1

union all

select
i.ItemId
,i.cost

,case when  t1.rn2/@rn1=rn then rn +1 else rn end
,case when I.rownum=@rn1 then 0 else rn1+1 end
,i.rownum
,b.Budget
,case
when t1.rn2/@rn1=rn then i.Cost
when b.Budget>= i.Cost+t1.Totalcost
then i.Cost+t1.Totalcost else t1.Totalcost end   as Totalcost
--,case when i.cost+<=b.Budget then b.Name end Buyer
,rn2+1
,case when t1.rn2/@rn1=rn and b.Budget>=i.cost and t1.cost>0  then 1
when b.Budget>= i.Cost+t1.Totalcost and t1.cost>0   then 1
else 0 end

from CTE1 I
inner join CTE t1 on I.rownum=rn1+1
, @Buyer B
--and rn1<=10
where  b.BuyerId=case when  t1.rn2/@rn1=rn then rn +1 else rn end
and rn<=@rn

)

select * from CTE
``````

Can we know CTE t1 old status when rn>1 ?

I think @mustaccio is right, the problem is a "knapsack problem".

You maybe can attack the problem the other way around using `GROUP BY CUBE`.

``````select coalesce(a, 0) + coalesce(b, 0) + coalesce(c, 0) + coalesce(d, 0) + coalesce(e, 0) + coalesce(f, 0) + coalesce(g, 0) + coalesce(h, 0) + coalesce(i, 0)
from (values (50, 30, 20, 40, 10, 40, 30, 10, 5)) t(a,b,c,d,e,f,g,h,i)
group by cube(a,b,c,d,e,f,g,h,i)
having (case when a is not null then 1 else 0 end +
case when b is not null then 1 else 0 end +
case when c is not null then 1 else 0 end +
case when d is not null then 1 else 0 end +
case when e is not null then 1 else 0 end +
case when f is not null then 1 else 0 end +
case when g is not null then 1 else 0 end +
case when h is not null then 1 else 0 end +
case when i is not null then 1 else 0 end
) = 3;
``````

In this case I'm calculating all possible combinations of the `SUM` of 3 items.

Now that you have all possible totals you can see how those totals fit in your user's budget.

I know is not exactly what you wanted but I hope I might have give you new ideas.

• I see what you've done but then how do go from that to 'you can see how those totals fit in your user's budget'? – Clement Oct 13 '20 at 6:55

aka bin packing

There is a recent article on solving this type of problem here :-

https://www.sqlservercentral.com/articles/a-set-based-solution-for-the-bin-packing-problem

• The linked you shared talks about quite a different problem. Our 'bins' are not of identical size, nor do we have an infinite number of them. – Clement Oct 13 '20 at 6:58