Recomputing only what a price touched

A spreadsheet doesn't recompute every cell when you edit one: it recomputes the cells that depend on it. Build systems do the same with files. STP needed that idea for bills of materials, where inputs change every few seconds and a full computation is expensive.

A BOM is a directed acyclic graph. The root is the vehicle, children are assemblies and parts, and a shared part (a screw) has many parents. Computing cost, weight and CO₂e means walking the graph bottom-up, converting each part's price and multiplying quantities along every path. For 20,000 parts, a full computation takes about 750 ms in the engine alone.

Graphs that stay in memory

At first, every computation reread the BOM from PostgreSQL before checking the cache, even when the answer was already there. Now the backend keeps parsed graphs in memory, identified by BOM and revision, and the UI sends the revision it's displaying, so a request for a known revision needs no database read at all.

That cut a cached request on 20,000 parts by about half at that stage (≈ 440 → 220 ms), and by 70% on 1,000 parts, closer to the size of the cars in the demo.

Dirty nodes

When a part changes price, only the totals of the assemblies containing it are wrong. So each cache entry remembers which parts changed since it was computed, and the next read works in three steps:

1. Select the new offer for the changed parts only.
2. Mark their nodes dirty, and every active ancestor.
3. Recompute the dirty nodes, children before parents. Everything else is reused as it was.

Step 2 is a breadth-first walk up the parents, straight from the engine:

def affected_nodes(self, component_ids: Iterable[str]) -> set[str]:
    """Active nodes of these parts and their active ancestors: the dirty nodes."""
    found = {n for cid in component_ids for n in self.by_component.get(cid, ())}
    queue = deque(found)
    while queue:
        for parent in self.parents.get(queue.popleft(), ()):
            if parent not in found:
                found.add(parent)
                queue.append(parent)
    return found

In the engine, after changing the most shared part of a 20,000-part BOM, that's 45 ms instead of ≈ 750 ms (−94%). At 1,000 parts it's 1 ms instead of 18. Through the API, the read that follows a price change went from ≈ 1.4 s to 310 ms, the rest being the response itself (where the time actually went is about that part).

To recompute partially, each cache entry keeps its plan: the parents of the active subgraph, the nodes of each part, the chosen offers. That added about 17% of memory at 20,000 parts (≈ 545 → 640 MB), and a full computation got about 10% slower, since it now prepares all of it up front. We kept that trade on purpose: a full computation happens once per BOM and configuration, and price changes happen every few seconds.

Same order, same result

A partial recomputation that changed a cost, even by a cent, would be a bug. Decimal arithmetic still rounds once a result passes 28 significant digits, and where it rounds depends on the order of operations, so the partial recomputation adds in exactly the same order as the full one. The results are identical, not just close. Tests check it on generated BOMs with shared parts, after one and then several offer changes, and on the reference fixture: 162 EUR, then 168 EUR once the screw changes price.

When a rate changes

A rate change touches every part priced in that currency, so it isn't worth a partial recomputation: the affected cache entries are dropped and recomputed. The 20,000-node stress test showed that this recomputation ran on the backend's event loop, so the backend stopped answering for as long as it took, at every rate change. It now runs in a worker thread.

Moving it to a thread opened a race: a slow recomputation started with old rates could finish after a newer one and overwrite it. So a result only goes back into the cache if nobody refilled that entry in the meantime and the rates haven't changed again.