More efficient FIFO inventory calculation?

Question

I am implementing a basic ledger system for which I want to calculate costs based on the FIFO system. Is there a more clever method than an O(n) search?

Example

Suppose I have two lists of transactions:

Incoming Inventory:

Date	Batch	Quantity	Price
Jan 1	A	3	5.00
Jan 15	B	5	7.00

Inventory Sold:

Order	Date	Quantity
X	Jan 1	2
Y	Jan 2	3
Z	Jan 3	1

I want to calculate that the items in order X cost $5 each, there was one item in order Y which was $5 and two that were $7, and order Z's items were $7.

My current solution

Naively, I would have to iterate through every single sale and inventory batch since the beginning of time:

inventory = [
    {"quantity": 3, "price": 5},
    {"quantity": 5, "price": 7},
]

sold = [
    {"order": "X", "quantity": 2},
    {"order": "Y", "quantity": 3},
    {"order": "Z", "quantity": 1},
]

i = 0
for s in sold:
    for sold_item in range(0, s['quantity']):
        if inventory[i]['quantity'] == 0:
            i += 1

        print(f'Order {s["order"]} price {inventory[i]["price"]}')
        inventory[i]['quantity'] -= 1

This outputs the following:

Order X price 5
Order X price 5
Order Y price 5
Order Y price 7
Order Y price 7
Order Z price 7

If I want to ask "for order Y, what were my prices?" then I have to compute this from the very beginning of my order history. Furthermore, if the orders are input out of order, then this changes the cost basis for every other subsequent order.

More details about the question

I am wondering if there is a more clever way to do this. It seems that if I could keep a cumulative sum, then it would be easier for me to find the exact bucket in which my inventory belongs. I haven't been able to come up with anything.

If it helps, I am storing this data in a SQL database (though open to using pretty much any kind of disk-based datastore.) However, regardless of the database being used, I'm interested to know if there is a technique (for pre-computing, or aggregating, or a different structure all together) which would be useful for solving this problem.

Answer 1

In short

The main challenge in your requirement is the uncertain sequence of outgoing orders, which could arbitrarily change the price. Several financial constraints forbid this to happen in some circumstances, and requires the prices to be frozen at some time.

If the sequence of the outgoing items can be frozen, you could think of a solution based on remaining inventory for each batch. The solution will depend on whether the inventory holds a sales price, or a cost of goods sold.

More details

If it's about sales price, you need to freeze it at latest once the invoicing is done, since the sequence of registration shall in no way retroactively change an invoice. One solution would be to issue stock reservations when the orders are registered, with some more challenges when orders are cancelled. Another is to record the stock movement at the moment of delivery or invoicing whatever is first:

• You'd maintain a remaining quantity for each incoming batch
• For the outgoing movements, you'd keep a flag on whether price is frozen or not.
• You'd store the sales price in the outgoing movement.
• When the price is frozen, you'd read the items with remaining quantity in the FIFO sequence, updating the remaining quantity and update the price (btw. the price would be a weighted average of the prices of the involved batches). This is almost O(1) operation.
• Unfortunately, you'd have to recalculate the outgoing movements not yet confirmed (in the same way as today) in O(n).
• If you can delay the outgoing inventory movement to the moment the price is frozen, you'd skip the unfortunate update and directly record the price in almost O(1) without the need for a frozen flag.

Remark: Where I mention almost O(1) above, it is in reality O(k) where k is the number of batches having remaining inventory, which is small compared to the total number of lines, and where in practice k tends to be small since you'd read only the first few. This allows to consider it as constant compared to the ever-growing n of stock movements.

If you're in an industry working with batches and traceability requirements, you'll have to refer to batches anyway in every business transaction. If it's about sales price, you'd need to refer to the batches in the sales order. If it's about cost of goods sold, you'd probably have to record batches sent for each delivery, in the sequence of deliveries:

• You'd maintain a remaining quantity for each incoming batch
• Every outgoing movement would necessarily by design refer to a precise batch, determined in LIFO manner, and would not be changed retroactively. Outgoing movements crossing several available batches would have to be split to ensure that mapping to one unique incoming batch is possible.
• The direct mapping of every movement to a single batch, and the synchronous update of remaining batch quantity, ensure together a real O(1) operation.

If it's about cost of goods sold and if you don't work in a batch-oriented industry, you could either use the technique above behind the scene and achieve O(1), or use a similar technique that for the very first case in O(1) if you can make the sequence of outgoing elements unchanged, which is generally the case if the ordering is based on the delivery. In all other cases, you'll get O(n) as you'll have to perform the calculation on demand (in general at account closing at the end of the month or the end of the year). You'll then have to deal with another regulatory constraint: you cannot change the accounting figures (sum of cost of goods sold in the month or in the year) after the closing of the financial period or the official reports. You must therefore persist the situation at latest at account closing. This would mean that you would never reacalculate all prices since the beginning of times in your ledger, but only since the end of the last closed period (if it's O(n), where n is the the number of movements in an open accounting period).

Disclaimer: This is not legal advice. I'm not a lawyer, check regulatory aspects with a qualified legal advisor or chartered accountant in your jurisdiction

Answer 2

You can't beat O(n)

You can record the results so you don't keep counting from the start each time.

I guess if you are doing this in sql, your problems are

1. When to pull data from the database.
2. Avoiding concurrency issues.
3. Ordering the data

You could assign stock when the order is created, which would allow you to only pull {number of items in order} TOP rows from inventory.

You could have a single worker process which gets batches of inventory and orders to work through, pulling a new batch when either list is used up.

Add an OrderId col to Inventory, or separate Order-Inventory linking table and fill it in as stock is assigned to orders

Don't do

1. Putting the loop in a sproc

2. Making a report with joins

3. making a 'clever' select with row number

You want to keep this logic out of the data layer at all costs.