0 Data Structures and Algorithms in an ERP

Most of the time the right answer to "how do I make this fast?" is to let Postgres do the work, because a database is a very well-optimized algorithm engine and hand-written loops over fetched rows are one of the most common performance mistakes beginners make. A real apparel ERP still contains a handful of problems no single query will solve for you: forward availability, allocation when there is not enough stock to go round, bill-of-materials explosion (working out the raw materials a production run needs), carton packing, and customer deduplication. This chapter teaches computer science from zero using exactly those problems.

What you need to know first

An algorithm is a recipe: a finite list of unambiguous steps that turns an input into an output. "Take the order lines, add up the quantity on each, report the total" is an algorithm. So is "for each item, find the first carton it fits in, and if none fits, open a new carton." Nothing about the word implies difficulty. If you have written a for loop, you have written an algorithm.

A data structure is a way of arranging information in memory so that particular questions are cheap to answer. That last clause is the point. A SKU — stock-keeping unit — is one sellable variant of a product: one style, in one color, in one size, such as a black quilted jacket in size M.

The same 5,000 SKUs can be a plain list, and then "give me the SKU with code WMN-JKT-001-BLK-M" means walking the list one entry at a time. Or they can be a hash map keyed by code, and the same question is answered in one step. The arrangement is what makes a question cheap or expensive.

Efficient is the third word worth pinning down. "Fast on my laptop" measures one input, on one machine, on one day. Efficiency describes a shape: how much the cost grows when the input grows. A season with 40,000 order lines is eight times a season with 5,000. Does the work go up eight times, or sixty-four times? That difference decides whether a report runs in two seconds or times out.

Memory, disk, and the gap between them

The next pairing to hold onto is memory versus disk. Memory (RAM) is fast, small, and forgotten when the process stops; disk (an SSD) is slower, much larger, and survives restarts. A page is the fixed-size block a database reads and writes at a time; in Postgres it is 8 kB by default.

The gap between the two is enormous: a value already in memory takes on the order of a hundred nanoseconds to read, while a random 8 kB page from an SSD takes tens to a couple of hundred microseconds, hundreds to thousands of times slower, and a row fetched from Supabase over the network adds another factor of ten to a hundred on top.

This explains almost every performance rule you will be given. "Don't query inside a loop" means "don't pay a network round trip 40,000 times." "Add an index" means "don't make the disk read every page."

Why learn this when the database already has it

That raises the objection this section is named for: why learn this when you have a database? Postgres already contains, written in optimized C and refined since 1996, a sort, several join algorithms, a B-tree index, hash tables, a query planner, and a buffer cache. When you write SELECT ... JOIN ... GROUP BY ... ORDER BY, you are commissioning those algorithms; the planner reads your query and its statistics and chooses, changing its mind as your data grows. You will not beat it by hand, because your TypeScript runs after the rows have crossed the network.

So the default really is "push it into SQL." Learn the theory anyway for three reasons:

• First, you cannot use a tool you do not understand: chapter 2 told you to index order_lines(order_id), and until you know what a B-tree is, that advice is superstition.
• Second, several important ERP problems cannot be expressed as one query — forward available-to-promise (the largest quantity you can safely promise a customer for a given future date) is a running minimum over a merged timeline, fair-share allocation has a remainder rule, and carton packing is provably hard.
• Third, recognizing a problem's shape stops you inventing a bad version of a solved one.

Every concept below arrives through a real apparel-ERP task. Complexity claims and published bounds are cited to their source. Every timing quoted in this chapter was measured on one machine — an Apple Silicon Mac running Node 25, in July 2026. Your absolute numbers will differ; the ratios between the fast and slow versions will not.

Cost and growth: Big-O from zero

Fix some sizes in your head for the rest of the book. They are the worked example this book uses throughout, not a survey of the industry:

• a brand carrying four seasons with 5,000 SKUs
• a season of wholesale bookings, the orders stores place in advance, of 40,000 order lines
• and an inventory ledger — every receipt, shipment, adjustment, transfer and count, stored immutably — of 2 million rows after a few years

Your own brand may be an order of magnitude smaller or larger; swap in its numbers and redo the sums. Test your instincts against real counts either way. Fifty rows of seed data — the handful of sample rows you load into a development database — will never tell you anything.

Big-O describes how the number of steps grows as the input grows. We write n for input size. The notation throws away constants and small terms because they stop mattering once n is large: an algorithm taking 3n + 200 steps is written O(n), since at two million rows the 3 and the 200 are noise.

The six shapes you will meet

• O(1), constant. Cost ignores input size — fetching a SKU by primary key, or reading order.total_cents off an object you already hold. Ten rows or ten million, same cost.
• O(log n), logarithmic. Each step discards half the remaining possibilities, so doubling the data adds one step. This is what a B-tree index buys, and why an index on a 2-million-row ledger is barely slower than one on a 5,000-row table: finding a customer by indexed email among 2 million rows takes about 21 comparisons.
• O(n), linear. You touch each item once — summing 40,000 order lines, or a sequential scan. Linear is fine and often correct; a linear pass over 2 million rows inside Postgres is well under a second.
• O(n log n), linearithmic. Sorting. Any sort that works by comparing pairs of items needs about n log n comparisons in the worst case, and mathematicians proved decades ago that no such sort can do better. In practice it is only slightly worse than linear, so never be afraid of a sort.
• O(n²), quadratic. For each item you touch every item. The shape of a nested loop, and the shape that kills ERPs: comparing every customer against every customer, or matching each order line against a SKU array with Array.find. Invisible at small n, fatal at real n.
• O(2ⁿ), exponential. Each extra item doubles the work — for example, testing every possible subset of items to fill the first carton. At n = 25 that is already 33 million combinations; never ship one, and see the packing section for what to do instead.

What those shapes cost at real row counts

This is the table worth memorizing. It counts steps, with logs base 2.

Steps are abstract, so convert them to time. The figures below assume 10 million steps per second, a deliberately conservative rate for a JavaScript loop doing real work per iteration.

Read the O(n²) row across. On 50 seed rows it takes a quarter of a millisecond, which no human perceives and no test flags. On a real season it takes two and a half minutes — nobody waits that long for a web page, and you are within sight of the hard ceiling your hosting puts on a single request. (A serverless function is a piece of your backend that the host starts on demand for one request and then throws away; Vercel gives each one a maximum of 300 seconds, as of July 2026.)

On the ledger it takes four and a half days. The input grew 800×; the work grew 800², or 640,000×.

Quadratic code always passes review and always ships, because only production data reveals it.

Space complexity and the time–space trade-off

Big-O also describes memory, with the same shapes. A running total uses O(1) extra space — one number, whatever the input. A map of all 5,000 SKUs uses O(n). A table pairing every SKU with every warehouse uses O(n × m), which is how people accidentally allocate gigabytes.

Spending memory buys time. The clearest case is the cache for available to promise — ATS — in chapter 8. Computing ATS forward for one SKU means sweeping a merged timeline of its supply and demand events, O(k log k) for k events. Doing that live on a 200-row order screen means 200 sweeps per keystroke. The alternative is to precompute, store the answer keyed by SKU and date bucket, and invalidate on write — turning reads into one indexed lookup at the cost of extra rows and the duty of keeping them correct.

The real price of that trade is correctness rather than memory. A cache is a second copy of a derived truth, and every second copy can drift. The rule that makes it survivable: the cache must be rebuildable from the ledger at any moment by one deterministic function, one that gives the same answer every time it sees the same input, and a scheduled job must rebuild and compare. Any difference between recomputed and cached is a bug you need to see.

The everyday structures: arrays, maps and sets

Arrays and lists

An array is a numbered row of slots in memory. Because the slots are consecutive, the computer jumps straight to slot 7,412 by arithmetic, so reading or writing by index is O(1). Appending is effectively O(1). Inserting into the middle is O(n), because everything after shifts along.

The operation that matters is searching. In an unsorted array you must look at each element until you find the match, which is O(n). find, filter, includes and indexOf are all O(n). One such call over 5,000 SKUs is fine. The problem is putting it inside another loop.

Hash maps and hash sets

A hash map stores key-and-value pairs and retrieves a value by key in constant time. It uses a hash function, which turns a key like "WMN-JKT-001-BLK-M" into a number used directly as a slot position in an internal array. No searching happens — you compute where the value would be and look there. A warehouse works the same way: if your only record of where goods live is a chronological receiving log, finding a SKU means reading the log; if every SKU has a bin whose address is derivable from its code, you walk straight to it.

TypeScript gives you Map (key/value) and Set (keys only, answering "have I seen this?"). Both give O(1) average get, set, has and delete. Prefer them over plain objects for lookup tables: Map takes any key type, keeps insertion order, has a real size, and has no prototype keys to collide with. Two caveats: constant time is an average; and object keys compare by identity, so key by strings and numbers.

The highest-value lesson: replace the nested lookup with a map

The task: you have imported a season of bookings, 40,000 order lines each carrying a SKU code, and 5,000 SKUs each carrying a standard cost. You need the season's total cost of goods. Beginners write the version below, and it works perfectly on the ten rows in the fixture.

type Sku  = { id: string; code: string; cost_cents: number };
type Line = { id: string; sku_code: string; qty: number };

// SLOW: O(lines x skus)
export function totalCostSlow(lines: Line[], skus: Sku[]): number {
  let total = 0;
  for (const line of lines) {
    const sku = skus.find((s) => s.code === line.sku_code);
    if (sku) total += sku.cost_cents * line.qty;
  }
  return total;
}

Line by line. A SKU has an id, a code and a cost in whole cents; an order line has an id, the SKU code it refers to, and a quantity. The outer loop visits each of the 40,000 lines once. Inside, skus.find(...) walks the 5,000-element array comparing codes and stops at the first match, and that inner walk restarts from scratch on every line, so 40,000 lines cost about 100 million comparisons. The function is O(lines × skus), the quadratic shape in disguise, since the inner loop hides inside find.

// FAST: O(skus + lines)
export function totalCostFast(lines: Line[], skus: Sku[]): number {
  // Pass 1 - index the SKUs by code. O(skus), 5,000 steps.
  const byCode = new Map<string, Sku>();
  for (const s of skus) byCode.set(s.code, s);

  // Pass 2 - one constant-time lookup per line. O(lines), 40,000 steps.
  let total = 0;
  for (const line of lines) {
    const sku = byCode.get(line.sku_code);
    if (sku) total += sku.cost_cents * line.qty;
  }
  return total;
}

Line by line. new Map<string, Sku>() creates an empty hash map with string keys and SKU values. The first loop runs 5,000 times calling set, which hashes the code and stores the SKU at that slot. The second loop runs 40,000 times calling get, which hashes and reads one slot, with no comparisons against other SKUs. Total work is 45,000 steps rather than roughly 100,000,000, so the shape went from O(n × m) to O(n + m). The cost is memory: 5,000 references, a few hundred kilobytes.

40,000 order lines matched against 5,000 SKUs
(measured: Node 25, Apple Silicon, July 2026)
-----------------------------------------------------------
Array.find inside the loop   462.7 ms   ~100,000,000 compares
Map built once, then get       2.3 ms        45,000 steps
-----------------------------------------------------------
speed-up                        203x   (identical result)

Reading the trace: the slow version took 462.7 ms, the fast one 2.3 ms, a 203-fold difference, and the script asserted that both totals matched. Note that the slow version still beats the 10-million-steps-per-second estimate used earlier, because V8, the JavaScript engine inside Node and Chrome, optimizes tight string comparison well. That is the trap. Even heavily optimized, it is 200× slower, and the gap widens with catalog size: double the SKU count and the map version barely moves while the find version doubles again.

The same applies to Set. "Which of these 40,000 imported codes are new?" written as codes.filter(c => !skus.some(s => s.code === c)) is quadratic; written as const known = new Set(skus.map(s => s.code)); codes.filter(c => !known.has(c)) it is linear.

The N+1 query problem

N+1 is the same mistake with a network cable attached. You run one query to fetch a list, then one more query per item in that list.

// N+1: 1 query for orders, then 1 per order. Do not do this.
const { data: orders } = await supabase
  .from('orders')
  .select('id, customer_id, start_ship')
  .eq('season', 'FW26');

for (const order of orders ?? []) {
  const { data: lines } = await supabase      // inside the loop
    .from('order_lines')
    .select('sku_id, qty')
    .eq('order_id', order.id);
  order.lines = lines ?? [];
}

Line by line. The first call fetches every FW26 order, say 800, in one round trip. Then the loop runs 800 times, each iteration awaiting a fresh query. Because of the await they run strictly one after another, and each is a full request: pack the query into a message (serialize it), cross the network, plan, execute, send the rows back, unpack them again. At an optimistic 4 ms per round trip, 800 sequential queries is 3.2 seconds of pure waiting during which the database did almost nothing. Total queries: 1 + N, hence the name.

// Fix 1 - let PostgREST do the join. One round trip.
const { data: orders } = await supabase
  .from('orders')
  .select('id, customer_id, start_ship, order_lines(sku_id, qty)')
  .eq('season', 'FW26');

// Fix 2 - two round trips, then group in memory with a Map.
const { data: heads } = await supabase
  .from('orders').select('id, start_ship').eq('season', 'FW26');

const ids = (heads ?? []).map((o) => o.id);
const { data: allLines } = await supabase
  .from('order_lines').select('order_id, sku_id, qty').in('order_id', ids);

const byOrder = new Map<string, { sku_id: string; qty: number }[]>();
for (const l of allLines ?? []) {
  const bucket = byOrder.get(l.order_id);
  if (bucket) bucket.push(l);
  else byOrder.set(l.order_id, [l]);
}
for (const o of heads ?? []) o.lines = byOrder.get(o.id) ?? [];

Line by line. Fix 1 uses the embedded-resource syntax of PostgREST — the web API layer Supabase runs in front of your database, which is what turns supabase.from(...).select(...) into SQL. Naming the child table inside select makes Postgres perform the join and return nested JSON, so it is one query and one round trip.

Fix 2 applies when an embed will not express it: fetch the parents, collect their ids, fetch every child whose order_id is in that array with a single .in(), then group with the map technique above — two round trips regardless of order count.

A third fix, for complex shapes, is a view (a saved query you can select from as if it were a table) or an RPC (a function you define in the database and call by name), so only the finished answer crosses the wire.

To spot an N+1 you did not write deliberately: look for await inside a for, while or .map(), and count query-log lines per page load — if the count scales with rows on screen you found one. Note that replacing the sequential loop with Promise.all hides latency while still sending 800 queries, moving the load onto your connection pool (the small set of database connections your app shares between requests). Reduce the query count instead of making the queries concurrent.

When to sort, and why sorting once beats searching repeatedly

Sorting costs O(n log n), which looks worse than one O(n) scan. Sort anyway, because sorting is an investment that changes what is cheap afterward. A sorted array can be binary-searched — check the middle, discard half, repeat — at O(log n) per lookup instead of O(n). For pure key lookups a hash map still wins, so the real reason to sort is the next one.

Sorting makes ordered questions answerable in one pass. "Which lines ship in the next 14 days?" on sorted data is a contiguous slice found by two binary searches. "Group the ledger by SKU with running totals" on data sorted by SKU then date is one linear walk: when the SKU changes, emit and reset. That pattern — sort, then sweep — is the backbone of the ATS algorithm below, of allocation, and of every reconciliation report you will write. Two lists that must be matched up can likewise be walked with two pointers in one pass: O(n log n) against O(n × m).

In practice let Postgres sort with ORDER BY: it can often satisfy the ordering straight from an index and skip the sort entirely, and sorting 2 million rows in a Node process will exhaust memory long before it finishes.

Trees

What a tree is

A tree is a set of items where each has exactly one parent, except one, the root, which has none. Items with no children are leaves. An org chart is a tree, a file system is a tree, and a product hierarchy is a tree: department "Womens" contains class "Outerwear", which contains style "WMN-JKT-001" (the design itself, such as the quilted jacket), which contains colorway "Black" (that style in one specific color), which contains the SKUs XS through XL.

The properties that matter: a tree with n items has exactly n − 1 parent links; there is exactly one path between any two items; and depth determines the cost of walking it. A balanced tree keeps branches roughly equal in depth, and where each node has b children that depth is about log_b(n). That logarithm is the reason trees are useful.

Womens                              (department, root)
├── Outerwear                       (class)
│   ├── WMN-JKT-001 Quilted Jacket  (style)
│   │   ├── BLK  Black              (colourway)
│   │   │   ├── WMN-JKT-001-BLK-XS  (SKU, leaf)
│   │   │   ├── WMN-JKT-001-BLK-S
│   │   │   ├── WMN-JKT-001-BLK-M
│   │   │   ├── WMN-JKT-001-BLK-L
│   │   │   └── WMN-JKT-001-BLK-XL
│   │   └── OAT  Oatmeal
│   └── WMN-CT-004  Wool Coat
└── Knitwear
    └── WMN-KNT-011 Merino Crew

Reading the diagram: five levels, root at the left. Every SKU has exactly one path back to the root, and that path is what a merchandising report groups by. With 5,000 SKUs at the leaves and roughly 5 to 10 children per level, the depth stays at 5. The business model fixes that depth; growing the catalog widens the tree instead of deepening it.

The B-tree: why an index is fast, from the inside

Chapter 2 told you to add indexes. Without one, finding rows in a 2-million-row ledger where sku_id = 'x' forces Postgres to read every page and check every row — a sequential scan, O(n). Postgres pages are 8 kB by default, and a narrow ledger row of about 130 bytes packs roughly 60 to a page, so that scan reads about 33,000 pages.

A B-tree index is a separate, sorted, tree-shaped structure over that column. Each node is a full disk page holding hundreds of keys and hundreds of child pointers rather than the two of a binary tree. That high branching factor is deliberate: the expensive operation is reading a page, so each page read should eliminate as much of the search space as possible.

A 2,000,000-row index, ~300 entries per 8 kB page:

Level 0 (root, 1 page)
   [ ... 'K' ... 'S' ... ]      ~23 separator keys in use
        |       |               (the page could hold ~300)
        |       +----------------------+
        v                              v
Level 1 (internal, ~23 pages)
   [ ...'M'... ]                [ ...'V'... ]
        |                            |
        v                            v
Level 2 (leaf, ~6,700 pages)
   [ 'sku_0041' => ctid(1204,7) ]
   [ 'sku_0042' => ctid(0881,3) ]   leaves are chained sideways
   [ 'sku_0043' => ctid(1911,2) ]   so range scans walk along

Reading the diagram. The root page holds separator keys; comparing your search key against them tells you which single child page to read next, and that one read throws away every other branch. Repeat at each level. Leaf pages hold key values paired with a ctid, the physical location (page, slot) of the row in the table, and are chained to their neighbors, so a BETWEEN query walks sideways along the leaf level after finding the first match.

Work the sizes upward. About 300 entries fit in a page, so 2 million rows need roughly 6,700 leaf pages; those need about 23 pages above them; those fit under one root. Three levels. Finding a row by an indexed column costs three or four page reads instead of 33,000 — the difference between O(n) and O(log n), and the same three levels would still cover 27 million rows.

A B-tree index can only answer questions built from five comparisons — <, <=, =, >= and >, which is why it cannot help a "not equal to" (<>) test or a LIKE '%jacket%' search. Postgres also shrinks indexes on repeated values through deduplication, described in the docs as "periodically merging groups of duplicate tuples together".

The write cost of an index

Indexes are not free. Every index is a second structure that must stay consistent with the table. An INSERT writes the row and inserts a key into every index, sometimes splitting a full page in two. An UPDATE touching an indexed column is a delete plus an insert in that index. A DELETE leaves dead entries for VACUUM.

The practical effect: every index you add makes every write on that table slower, and on a wide table the indexes together can occupy more disk than the rows do. For an ERP this bites hardest on the ledger, which is almost all writes. Index for the queries you actually run, check the slow query log rather than trusting your intuition, and accept that a bulk import of 500,000 rows goes faster if you drop non-essential indexes first and rebuild them after.

A composite index covers more than one column, and the order you list those columns decides which queries it can serve. An index on (order_id, sku_id) serves a query filtering on order_id alone, or on both, but not one filtering on sku_id alone, because the tree is sorted by order_id first. A phone book sorted by surname then first name is useless for finding everyone called "Daniel". Put the column you always filter on first.

Storing the product hierarchy in Postgres

Trees are natural in memory and awkward in a relational table. Three classic models exist, each making different questions cheap.

Adjacency list. Every row stores its parent's id. Simple, obviously correct, trivially updated.

create table product_node (
  id          uuid primary key default gen_random_uuid(),
  parent_id   uuid references product_node(id) on delete restrict,
  node_type   text not null
                check (node_type in
                  ('department','class','style','colorway','sku')),
  code        text not null,
  name        text not null,
  unique (parent_id, code)
);

create index on product_node (parent_id);

Line by line. Each node has an id and a nullable parent_id pointing at another row in the same table. A foreign key is a promise the database enforces that a value in one column matches a real row somewhere; here it points back at the same table, which is what makes the data a tree.

on delete restrict stops you deleting a class that still has styles beneath it, the check constraint pins node type to the five merchandising levels, and unique (parent_id, code) means codes need only be unique among siblings. The index on parent_id turns "give me this node's children" into an index lookup instead of a sequential scan.

with recursive subtree as (
  -- non-recursive term: the starting node
  select id, parent_id, node_type, code, name, 0 as depth
  from product_node
  where code = 'OUTERWEAR' and node_type = 'class'

  union all

  -- recursive term: children of anything already in subtree
  select c.id, c.parent_id, c.node_type, c.code, c.name, s.depth + 1
  from product_node c
  join subtree s on c.parent_id = s.id
)
select code, name, node_type, depth
from subtree
where node_type = 'sku'
order by code;

Line by line. with recursive subtree as (...) declares a common table expression allowed to refer to itself. The first half runs once and seeds the result with the Outerwear row at depth 0. The second half joins the full table against whatever rows the previous iteration produced, picking up their children and incrementing depth; Postgres repeats until an iteration produces nothing new. Cost is O(nodes in the subtree). PostgreSQL 14 and later also offer a cycle id set is_cycle using path clause, which tracks the path already visited and stops when it repeats, so a loop in the data cannot hang the query.

Materialized path. Every row stores its full path from the root as a single value. Postgres has a dedicated type, ltree, whose label paths look like Top.Countries.Europe.Russia.

create extension if not exists ltree;

alter table product_node add column path ltree;
create index product_node_path_gist on product_node using gist (path);

-- a SKU path, e.g. WOMENS.OUTERWEAR.WMN_JKT_001.BLK.WMN_JKT_001_BLK_M

-- every descendant of Outerwear, in ONE indexed query, no recursion
select code, name
from product_node
where path <@ 'WOMENS.OUTERWEAR'::ltree
  and node_type = 'sku';

-- every Black colourway anywhere in the tree, via an lquery pattern
select code from product_node where path ~ '*.BLK.*'::lquery;

Line by line. create extension ltree enables the type; it is one of PostgreSQL's standard contrib modules, so it is present on Supabase and you only have to switch it on. The path column stores dot-separated labels.

From PostgreSQL 16 a label may contain letters, digits, underscores and hyphens; on PostgreSQL 15 and earlier hyphens are not allowed, so a SKU code's dashes have to become underscores. Supabase still offers both 15 and 17, so pick one convention and apply it everywhere.

The GiST index — a general-purpose index type that can answer "contains" and "overlaps" questions rather than only "equals" and "less than" — makes the containment operators fast. <@ means "is a descendant of, or equal to", so the first query returns the whole subtree in one indexed lookup with no recursion, and ~ matches an lquery pattern.

The cost lands on writes: moving a class rewrites the path of every row beneath it.

Nested set. Every row stores a left and a right integer assigned by a depth-first walk, so a node's descendants are exactly the rows whose bounds fall inside its own and the subtree query is a plain BETWEEN on an ordinary B-tree.

The catch is severe: inserting one node shifts the bounds of roughly half the tree, so writes are O(n) and concurrent writes fight each other. Keep nested sets for frozen, read-only reporting snapshots. A live merchandising table will be updated all day, and this model punishes exactly that.

For an apparel ERP: hold the adjacency list as the source of truth, because it is the only model whose data cannot become internally inconsistent. If descendant queries become a measured bottleneck, add an ltree column maintained by a trigger — a function the database runs automatically whenever a row is inserted, updated or deleted, and treat that column strictly as a derived copy. Do not reach for the complicated model before measuring that the simple one is too slow.

Graphs

What a graph is

A graph is a set of items (nodes) connected by links (edges). A tree is a restricted graph: one parent each, no loops. A general graph drops both restrictions, so an item can be reached from several places and you can follow edges in a circle back to where you started.

Two properties describe a graph. Directed means edges have direction: "jacket requires shell fabric" differs from "shell fabric requires jacket". Weighted means edges carry a number — a quantity per unit, a distance, a lead time. A bill of materials is directed and weighted; migration dependencies are directed and unweighted. In code the standard representation is an adjacency list; in Postgres, an edge table with a from column and a to column.

Bill-of-materials explosion

To manufacture 500 units of style WMN-JKT-001 you must know how much of every raw material to buy. The style's bill of materials lists its immediate components, but some components are assemblies with their own bills. "Exploding" the BOM means walking the whole structure and multiplying quantities down each path.

WMN-JKT-001  Quilted Jacket                       (make 500)
├── FAB-SHELL-NYL   shell fabric        1.80 m  => 900.0 m
├── SUB-INSUL-PNL   insulation panel    1.00 ea => 500 ea
│   ├── FAB-WAD-80  wadding             1.20 m  => 600.0 m
│   └── TRM-BIND-10 binding tape        0.50 m  => 250.0 m
├── SUB-ZIP-ASSY    zipper assembly     1.00 ea => 500 ea
│   ├── TRM-ZIP-TAPE zipper tape        0.70 m  => 350.0 m
│   ├── TRM-ZIP-PULL puller             1.00 ea => 500 ea
│   └── TRM-BIND-10  binding tape       0.05 m  =>  25.0 m
├── LBL-MAIN-01     main label          1.00 ea => 500 ea
├── LBL-CARE-01     care label          1.00 ea => 500 ea
└── PKG-POLY-M      poly bag            1.00 ea => 500 ea

TRM-BIND-10 appears TWICE, via two different paths.
Correct total = 250.0 + 25.0 = 275.0 m.

Reading the diagram: left is the component, middle the quantity per parent unit, right the extended quantity for a 500-unit build. Two components are sub-assemblies with their own children. Stare at the last line. Binding tape is reached by two paths and the correct answer is the sum of both. That is why this is a graph rather than a tree: a node can have more than one parent. Code that assumes a tree reports 250 m, you buy 250 m, and production stops 25 m short.

type BomEdge = {
  parent_item: string;
  child_item: string;
  qty_per: number;    // child units per ONE parent unit
  scrap_pct: number;  // 0.03 = 3% expected waste
};

export function explodeBom(
  edges: BomEdge[],
  rootItem: string,
  buildQty: number,
  maxDepth = 32,
): Map<string, number> {
  // adjacency list: parent => its outgoing edges. Built once, O(E).
  const children = new Map<string, BomEdge[]>();
  for (const e of edges) {
    const bucket = children.get(e.parent_item);
    if (bucket) bucket.push(e);
    else children.set(e.parent_item, [e]);
  }

  const totals = new Map<string, number>();
  type Frame = { item: string; qty: number; depth: number; path: string[] };
  const stack: Frame[] =
    [{ item: rootItem, qty: buildQty, depth: 0, path: [rootItem] }];

  while (stack.length > 0) {
    const node = stack.pop()!;
    if (node.depth > maxDepth) {
      throw new Error('BOM deeper than ' + maxDepth);
    }
    for (const e of children.get(node.item) ?? []) {
      if (node.path.includes(e.child_item)) {
        throw new Error('BOM cycle at ' + e.child_item);
      }
      const need = node.qty * e.qty_per * (1 + e.scrap_pct);
      totals.set(e.child_item, (totals.get(e.child_item) ?? 0) + need);
      stack.push({
        item: e.child_item,
        qty: need,
        depth: node.depth + 1,
        path: [...node.path, e.child_item],
      });
    }
  }
  return totals;
}

Line by line. BomEdge is one parent-to-child relationship with a per-unit quantity and expected scrap. The first loop turns the flat edge list into an adjacency list — the map-instead-of-find trick again, making "who are this item's children?" O(1) rather than a scan of every edge. totals accumulates the answer. stack is an explicit to-do pile; using our own stack instead of recursion means a deep BOM cannot blow the JavaScript call stack, and it lets us carry the path taken to reach each node.

The loop pops one item at a time, with maxDepth as a guard. For each outgoing edge we check whether the child already appears on the path that got us here, and throw if so. Then need multiplies the parent's required quantity by the per-unit quantity and inflates it by scrap. We add into totals rather than assigning, which makes binding tape come out at 275 m rather than 25 m. Finally we push the child with its own required quantity, so its children get multiplied correctly in turn.

Complexity: O(E) to build the adjacency list. The traversal visits every path from the root, so the worst case is O(paths), which for a diamond-shaped graph exceeds O(V + E). Real garment BOMs are depth 3 or 4 with tens of components, so this is trivially fast; if path explosion ever mattered, memoize each sub-assembly's per-unit requirements and multiply. One caveat: node.path.includes(...) is a linear scan, so cycle checking costs O(depth) per edge — carry a Set alongside if your BOMs get deep.

Cycle detection at write time

A cycle means item A requires item B which requires item A. It is always a data-entry error, and it is catastrophic, because any traversal without a guard loops forever until the process is killed.

Detecting it at read time prevents the hang, but the damage is done: the bad row is already saved, the nightly MRP run — material requirements planning, the job that works out what to buy and make — throws an error every night, and someone has to hunt the row down. Reject the cycle at write time, in the database, so it can never exist.

create table bom_edge (
  parent_item text not null references item(code),
  child_item  text not null references item(code),
  qty_per     numeric(12,4) not null check (qty_per > 0),
  scrap_pct   numeric(6,4) not null default 0 check (scrap_pct >= 0),
  primary key (parent_item, child_item),
  check (parent_item <> child_item)        -- blocks the 1-step cycle
);

create or replace function bom_no_cycle() returns trigger
language plpgsql as $$
declare found boolean;
begin
  -- Can we already reach NEW.parent_item starting from NEW.child_item?
  -- If so, adding this edge closes a loop.
  with recursive reach as (
    select child_item as item
    from bom_edge where parent_item = new.child_item
    union all
    select e.child_item
    from bom_edge e join reach r on e.parent_item = r.item
  ) cycle item set is_cycle using path
  select exists (
    select 1 from reach where item = new.parent_item
  ) into found;

  if found then
    raise exception 'BOM cycle: % to % closes a loop',
      new.parent_item, new.child_item;
  end if;
  return new;
end $$;

create trigger bom_edge_no_cycle
  before insert or update on bom_edge
  for each row execute function bom_no_cycle();

Line by line. The pair is the primary key, so a component cannot be listed twice under one parent, and check (parent_item <> child_item) catches the trivial self-reference.

The trigger handles the real case: before the row is written, a recursive CTE starts at the proposed child and collects everything it transitively requires; if the proposed parent appears in that set, the new edge closes a loop.

The cycle ... using path clause (PostgreSQL 14 and later) protects the trigger itself against data that is already corrupt, and raise exception aborts the whole transaction so the row is never written. Cost is O(V + E) per insert, where V is items and E is BOM lines.

Topological sort

A topological sort takes a directed graph of dependencies and produces a linear order in which every item comes after everything it depends on. It exists if and only if the graph has no cycles. Two ERP uses.

Ordering database migrations. Migration 0005_order_lines creates a table with foreign keys to both orders and skus, so it must run after 0004 and 0003. Numbering files by hand works until two developers on two branches both create 0006.

Sequencing production steps. A garment's route has ordering constraints — cut before sew, sew before wash, wash before press, while other steps are independent, and the existence of several valid orders is exactly the freedom the production planner needs.

The standard algorithm is Kahn's. Its running time is linear in the number of nodes plus the number of edges, O(|V| + |E|), and if any nodes remain unemitted when it finishes, the graph has a cycle.

export function topoSort(
  nodes: string[],
  edges: [string, string][],   // [a, b] means a must come before b
): string[] {
  const indeg = new Map<string, number>(nodes.map((n) => [n, 0]));
  const adj = new Map<string, string[]>(nodes.map((n) => [n, []]));

  for (const [from, to] of edges) {
    adj.get(from)!.push(to);
    indeg.set(to, indeg.get(to)! + 1);
  }

  // ready = everything with nothing left to wait for
  const ready = nodes.filter((n) => indeg.get(n) === 0);
  const out: string[] = [];

  while (ready.length > 0) {
    ready.sort();               // deterministic: same input, same output
    const n = ready.shift()!;
    out.push(n);
    for (const m of adj.get(n)!) {
      indeg.set(m, indeg.get(m)! - 1);
      if (indeg.get(m) === 0) ready.push(m);
    }
  }

  if (out.length !== nodes.length) {
    const done = new Set(out);
    const stuck = nodes.filter((n) => !done.has(n));
    throw new Error('Dependency cycle among: ' + stuck.join(', '));
  }
  return out;
}

Line by line. indeg records how many things each node is still waiting on — its in-degree, and adj maps each node to its dependents. ready starts as every node with in-degree zero. The main loop emits one ready node and decrements the in-degree of everything that depended on it; when a node hits zero it joins the ready list.

The ready.sort() is not required by the algorithm — it makes output deterministic, which for migration ordering is worth paying for. Emitting fewer nodes than we started with is the cycle test. Each node is enqueued once and each edge examined once: O(V + E).

Input (7 migrations, 7 dependency edges):
  0002_styles      => 0003_skus
  0001_customers   => 0004_orders
  0004_orders      => 0005_order_lines
  0003_skus        => 0005_order_lines
  0001_customers   => 0006_price_lists
  0005_order_lines => 0007_allocation
  0003_skus        => 0007_allocation

Output:
  0001_customers, 0002_styles, 0003_skus, 0004_orders,
  0005_order_lines, 0006_price_lists, 0007_allocation

Cycle case, edges a=>b and b=>a:
  Error: Dependency cycle among: a, b

Reading the trace: this is the verified output of the code above, re-run for this edition. Note that 0006_price_lists lands near the end although it only depends on 0001_customers. Any position after 0001 would have been valid, and the alphabetical tie-break put it there. That is correct behavior, because a graph like this usually has several valid orders and a topological sort returns one of them. The cycle case names both trapped nodes.

Shortest path: the warehouse pick walk

A picker has an order with lines in five bin locations and must walk from the dispatch desk, collect all five, and return. Which route is shortest?

Model the warehouse as a weighted undirected graph: nodes are aisle intersections and bin faces, edges are walkable segments, weights are distances in meters. The classic algorithm for "shortest path from one node to every other" is Dijkstra's. Run with a binary-heap priority queue its worst case is Θ((|E| + |V|) log |V|), and it requires every edge weight to be zero or positive — always true of walking distances.

        A1 ---12--- A2 ---12--- A3
        |            |           |
        8            8           8
        |            |           |
PACK --6-- X1 --14-- X2 --14--- X3
        |            |           |
        8            8           8
        |            |           |
        B1 ---12--- B2 ---12--- B3

PACK to B3 via the cross aisle: 6+14+14+8 = 42 m
PACK to B3 cutting down early : 6+8+12+12 = 38 m   <-- shorter

Reading the diagram: PACK is the dispatch desk, X1–X3 are cross-aisle intersections, and the A and B nodes are bin faces, with meters on the links. The two candidate routes show why you cannot eyeball this: the apparently direct cross-aisle route is 42 m and dropping into the B aisle early is 38 m. Dijkstra finds the shorter one by expanding outward from PACK, always extending the cheapest frontier node next.

Now the honest part. Dijkstra gives the shortest path between two points, but the picker needs the shortest route visiting all five bins and returning — the traveling salesman problem, which is NP-hard. Five stops means brute-forcing 5! = 120 orders; twenty stops means 2.4 × 10¹⁸, which is hopeless.

So real warehouse systems do not solve it exactly. They use a serpentine heuristic — a rule of thumb that gives a good answer cheaply: sort pick lines by aisle, then by bin sequence, alternating direction on each aisle so the picker snakes up one and down the next. It is a sort, O(n log n), and it needs no graph at all.

How close it lands to the true optimum depends on the rack layout and on how many picks fall in each aisle, but it is predictable and a picker can follow it without thinking. The work is in the data rather than the code: give every bin an integer pick_sequence reflecting the physical walking order, and the pick list becomes order by pick_sequence.

Intervals and time

The half-open convention, and the off-by-one that will bite you

A price list is valid between two dates. A promotion runs for a window. A purchase order arrives in a window. A wholesale order carries a start-ship date (the earliest the buyer will accept delivery) and a cancel date (after which they will refuse it). Each of these is an interval, and intervals must be compared, overlapped, merged and swept.

Consider a price list valid "1 January to 30 June" and another valid "30 June to 31 December". Do they overlap? With both ends inclusive, yes — they share 30 June, and on that day your pricing engine has two candidate prices and picks one arbitrarily.

The fix is a convention applied everywhere: half-open intervals, written [start, end), start included and end excluded. The two lists become [2026-01-01, 2026-07-01) and [2026-07-01, 2027-01-01), which abut exactly and overlap nowhere.

Postgres agrees. Its documentation says the built-in int4range, int8range and daterange types "all use a canonical form that includes the lower bound and excludes the upper bound; that is, [)".

type Interval = { start: Date; end: Date };   // half-open: [start, end)

export function overlaps(a: Interval, b: Interval): boolean {
  return a.start < b.end && b.start < a.end;
}

export function contains(a: Interval, t: Date): boolean {
  return a.start <= t && t < a.end;           // note <= then <
}

export function intersect(a: Interval, b: Interval): Interval | null {
  const start = a.start > b.start ? a.start : b.start;
  const end   = a.end   < b.end   ? a.end   : b.end;
  return start < end ? { start, end } : null;
}

Line by line. overlaps returns true when a begins strictly before b ends and b begins strictly before a ends. Both comparisons are strict <, which makes touching intervals count as non-overlapping; using <= makes abutting price lists collide. contains is asymmetric on purpose: <= at the start because the start is included, < at the end because the end is excluded. intersect takes the later start and the earlier end, returning null if that is empty. All three are O(1).

Making overlapping price lists impossible

Testing for overlap in application code is fine for computing and displaying an answer. It cannot prevent an overlap, because two requests can run at the same moment, each check the existing rows, each see no conflict, and each insert. Postgres has an exclusion constraint for exactly this. The documentation's own example is a meeting-room booking, which is structurally identical to a price list.

create extension if not exists btree_gist;

create table price_list (
  id           uuid primary key default gen_random_uuid(),
  customer_id  uuid not null references customer(id),
  currency     char(3) not null,
  valid        daterange not null,
  created_at   timestamptz not null default now(),

  -- no two lists for the same customer+currency may overlap in time
  exclude using gist (
    customer_id with =,
    currency    with =,
    valid       with &&
  )
);

insert into price_list (customer_id, currency, valid)
values ('...'::uuid, 'USD', daterange('2026-01-01','2026-07-01','[)'));

-- which price list applies on a given day?
select * from price_list
where customer_id = $1 and currency = $2
  and valid @> date '2026-03-14';

Line by line. btree_gist is another standard contrib extension; it lets a GiST index handle plain equality on ordinary columns alongside range overlap, and without it you cannot mix with = and with && in one constraint. The exclude using gist clause reads: reject a new row if one already exists whose customer id is equal and whose currency is equal and whose date range overlaps. Postgres enforces this with an index, atomically, so the race described above cannot happen. The final query uses @>, "range contains element", served by the same index.

The forward-ATS problem as a timeline sweep

This is the most valuable algorithm in the chapter, so read it slowly.

A rep is on the phone. The customer wants 60 units of WMN-JKT-001-BLK-M shipping in September. Can we promise them? The naive answers are wrong. "We have 120 on hand" ignores that 80 are already committed to an August order. "On hand minus everything allocated" goes negative and ignores 300 units arriving on a September purchase order. The real question is about a timeline: given everything we have, everything coming, and everything promised, what is the largest quantity we can commit on a given date without breaking an existing promise?

The answer is available to promise, defined as: ATS on date d is the minimum of the running inventory balance over all dates from d forward. The minimum is what matters. A balance that looks healthy today but dips to 40 in three weeks means you can promise only 40, because promising more leaves an existing order short when that dip arrives.

Today is 2026-07-25.

SUPPLY                          DEMAND
on hand today        +120       SO-9001  2026-08-20   -80
PO-4471  2026-09-15  +300       SO-9014  2026-09-20  -150
PO-4488  2026-10-20  +240       SO-9027  2026-10-25  -200
                                SO-9033  2026-11-10  -150

SWEEP (forward for balance, then backward for the minimum)

date         change   source     balance   ATS from here
2026-07-25     +120   on hand        120        40
2026-08-20      -80   SO-9001         40        40  <-- binding dip
2026-09-15     +300   PO-4471        340        80
2026-09-20     -150   SO-9014        190        80
2026-10-20     +240   PO-4488        430        80
2026-10-25     -200   SO-9027        230        80
2026-11-10     -150   SO-9033         80        80

Answer to the rep: 40 today, 80 from 15 September.

Reading the trace, the verified output of the code below. PO is a purchase order, stock you have bought and expect to arrive; SO is a sales order, stock a customer has already been promised. balance is a simple running total; ATS is the running minimum of the balance from that row to the end, computed by walking upward.

At 2026-07-25 the balance is 120 but the ATS is 40, because the balance dips to 40 on 20 August and stays there until the PO lands — promising 41 units today would leave SO-9001 short in August. At 2026-09-15 the minimum from there to the end is 80, so the rep can promise 60 for September but not for immediate shipment.

export type Event = {
  date: string;      // ISO 'YYYY-MM-DD'
  qty: number;       // positive = supply, negative = demand
  source: string;    // 'on hand' | 'PO-4471' | 'SO-9001' ...
};

export type AtsPoint = {
  date: string;
  change: number;
  source: string;
  balance: number;   // inventory position after this event
  ats: number;       // promisable ON this date, floored at 0
};

export function forwardAts(events: Event[]): AtsPoint[] {
  // 1. Sort by date. Ties: apply supply before demand on the same day.
  const sorted = [...events].sort((a, b) => {
    if (a.date !== b.date) return a.date < b.date ? -1 : 1;
    return (a.qty >= 0 ? 0 : 1) - (b.qty >= 0 ? 0 : 1);
  });

  // 2. Forward pass: running balance. O(n).
  const points: AtsPoint[] = [];
  let balance = 0;
  for (const e of sorted) {
    balance += e.qty;
    points.push({
      date: e.date, change: e.qty, source: e.source, balance, ats: 0,
    });
  }

  // 3. Backward pass: running minimum of future balance. O(n).
  let minAhead = Number.POSITIVE_INFINITY;
  for (let i = points.length - 1; i >= 0; i--) {
    minAhead = Math.min(minAhead, points[i].balance);
    points[i].ats = Math.max(0, minAhead);
  }

  return points;
}

/** Largest quantity promisable for a requested ship date. */
export function atsOn(points: AtsPoint[], wanted: string): number {
  let answer = 0;
  for (const p of points) {
    if (p.date <= wanted) answer = p.ats;
    else break;
  }
  return answer;
}

Line by line. Event is the unified input: one row per thing that changes inventory, signed to distinguish supply from demand. Merging supply and demand into one signed list is the move that makes the problem easy; keeping them in separate arrays and interleaving them by hand is where people tie themselves in knots.

Step 1 sorts by date. The tie-break matters: when a purchase order lands on the day an order ships, apply supply first, or the balance dips artificially negative for an instant and the backward pass records a phantom shortage. Sorting is O(n log n) and dominates the function. Step 2 walks forward once accumulating balance, so each event's balance is the position immediately after it — O(n) time, O(n) output space.

Step 3 walks backward once. minAhead starts at positive infinity and at each step takes the smaller of itself and the current balance, so after row i it holds the minimum from row i to the end. Floored at zero, that is the ATS, also O(n). Flooring is a business decision: it says "we are oversold, promise nothing" rather than reporting a negative quantity. atsOn keeps the ATS of the latest point at or before the requested date, since ATS does not change between events.

Total complexity: O(n log n), dominated by the sort, where n is the supply and demand events for one SKU — typically a few dozen. Space is O(n). For a whole catalog you run it per SKU, so a full refresh over 5,000 SKUs with 30 events each is a few hundred thousand operations. That is fast enough to run in a background job every few minutes and cache, which is exactly the ATS cache design in chapter 8.

Allocation

Allocation is the core ERP algorithm. You have 100 units. Four accounts have ordered 800 between them. Who gets what?

Several answers are defensible, and the choice between them is a business decision the brand owner must make and must be able to change later. Your job is to implement the policies cleanly, make the choice configurable, and record which policy produced which result so the outcome is auditable when a buyer calls.

Policy one: greedy by order date

type Demand = { id: string; account: string; qty: number;
                ordered_at: string; priority: number };

export function allocateByOrderDate(supply: number, demand: Demand[]) {
  const queue = [...demand].sort((a, b) =>
    a.ordered_at < b.ordered_at ? -1 :
    a.ordered_at > b.ordered_at ?  1 : (a.id < b.id ? -1 : 1));

  let remaining = supply;
  return queue.map((d) => {
    const alloc = Math.min(d.qty, remaining);
    remaining -= alloc;
    return { ...d, alloc, short: d.qty - alloc };
  });
}

Line by line. We copy the array, never sort the caller's array in place, and sort by order date, tie-breaking on id so results are deterministic. Math.min(d.qty, remaining) gives each order everything it wanted or everything left, whichever is smaller: O(n log n) for the sort plus O(n) for the walk.

It is greedy because it makes the locally best choice at each step without looking ahead. With 100 units and orders of 340, 210, 155 and 95, the first account takes 100 and everyone else gets nothing — honest, and it will make three of your four customers angry.

Policy two: by customer priority

Identical code, different sort key: priority descending, then order date. Brands use this to protect strategic accounts, honor a contractual minimum, or reserve capacity for their own direct-to-consumer channel — same greedy shape, same all-or-nothing outcome, different winner. Implement it as one allocation function taking a comparator rather than copying the function.

Policy three: fair-share proration, and the remainder problem

Proration gives everyone the same percentage of what they asked for — with 100 units against 800 of demand, 12.5% each. It is what most brands want when a style sells out, because it keeps every account in the assortment.

And it introduces the problem that makes this section necessary: 12.5% of 340 is 42.5 units, you cannot ship half a jacket, and rounding each share independently stops the total equalling your supply.

CASE A - supply 100, demand 340 / 210 / 155 / 95 (total 800)
  account   demand   exact share   naive round   largest rem
  ACC-1004     340      42.5000            43            43
  ACC-1017     210      26.2500            26            26
  ACC-1032     155      19.3750            19            19
  ACC-1088      95      11.8750            12            12
  TOTAL        800     100.0000           100           100   OK

CASE B - supply 100, demand 210 / 210 / 210 / 170 (total 800)
  A            210      26.2500            26            27
  B            210      26.2500            26            26
  C            210      26.2500            26            26
  D            170      21.2500            21            21
  TOTAL        800     100.0000            99           100
                                        ^ 1 unit LOST

CASE C - supply 7, demand 5 / 5 (total 10)
  A              5       3.5000             4             4
  B              5       3.5000             4             3
  TOTAL         10       7.0000             8             7
                                        ^ 1 unit INVENTED

Reading the trace. Case A is the lucky case where naive rounding happens to work, which is why the bug survives testing. Case B loses a unit: four values that each round down leave one unit assigned to nobody, so it never ships. Case C is worse: two values that each round up allocate eight units when seven exist, so the system promises stock you do not have. Both come from rounding each row independently, and both are silent.

The fix is the largest remainder method, known as Hamilton's method when it is used to apportion legislative seats by vote share. Compute each party's exact entitlement, give everyone the whole-number part, count what is left over, and hand those spare units out one each to the largest fractional remainders.

export type AllocRow = {
  id: string; qty: number;
  exact: number;    // unrounded fair share
  alloc: number;    // whole units allocated
  rem: number;      // fractional remainder, used for the tie-break
};

export function prorate(
  supply: number,
  demand: { id: string; qty: number }[],
): AllocRow[] {
  const total = demand.reduce((s, d) => s + d.qty, 0);

  if (total === 0) {
    return demand.map((d) => ({ ...d, exact: 0, alloc: 0, rem: 0 }));
  }
  if (supply >= total) {                   // no scarcity, everyone whole
    return demand.map((d) =>
      ({ ...d, exact: d.qty, alloc: d.qty, rem: 0 }));
  }

  // 1. exact share, floor it, remember the remainder
  const rows: AllocRow[] = demand.map((d) => {
    const exact = (supply * d.qty) / total;
    const base = Math.floor(exact);
    return { ...d, exact, alloc: base, rem: exact - base };
  });

  // 2. how many whole units are still unassigned?
  const assigned = rows.reduce((s, r) => s + r.alloc, 0);
  const leftover = supply - assigned;      // 0 <= leftover < rows.length

  // 3. one extra unit each, largest remainder first.
  //    Tie-break: bigger remainder, then bigger demand, then id.
  const order = [...rows].sort((a, b) =>
    b.rem - a.rem ||
    b.qty - a.qty ||
    (a.id < b.id ? -1 : 1));

  for (let i = 0; i < leftover; i++) order[i].alloc += 1;

  return rows;
}

Line by line. We total demand first and handle two special cases: zero demand allocates nothing, and supply at or above total demand means nobody is short, which is worth handling explicitly because it is the common case and avoids rounding entirely.

Step 1 computes each exact share as supply × qty / total, multiplying before dividing to keep precision. Math.floor takes the whole part and the difference is the remainder. After this step the allocated total is always at or below supply, never above, which makes over-allocation structurally impossible.

Step 2 counts the shortfall. Because each row lost less than one unit to flooring, the leftover is at least zero and strictly less than the number of rows, so step 3 never runs out of recipients.

Step 3 sorts a copy by remainder descending and gives one extra unit each to the first leftover rows. The chained tie-breaks matter more than they look: without them, two accounts with identical remainders would be ordered by whatever the sort happened to do, and the same input could produce different allocations on different runs. An allocation you cannot reproduce is one you cannot defend to a buyer.

Cost, the Alabama paradox, and splitting money

Complexity: O(n log n), dominated by sorting the remainders. The result sums exactly to supply and every allocation is a whole number, which is the pair of properties naive rounding cannot give you. One documented caveat: the largest remainder method suffers the Alabama paradox, where increasing the total to be shared out can leave one recipient with less than before. The practical defense is to hold confirmed allocations stable and allocate only the new units, instead of recomputing every account from scratch when more stock lands.

The same function allocates money. Chapter 10's problem of splitting a $250.00 freight charge across three $1,000.00 order lines is prorate with units set to cents: exact shares are 8,333.33 each, floors give 8,333 each totalling 24,999, one cent remains, and the tie-break gives it to the first line. Result: $83.34, $83.33, $83.33, summing to exactly $250.00.

Never round each share of a total on its own and hope it adds up. Allocate it.

Build all of these behind one interface, store the chosen policy on the allocation run, and write the policy name and the input snapshot into the audit record. When a buyer calls in three weeks asking why they got 26 units, answer from data rather than memory.

Packing and assortment

Carton packing is bin packing, and bin packing is NP-hard

You are shipping an order. Each carton has a maximum weight — say 15.0 kg, above which the carrier surcharges. You have 21 packs to ship at various weights. How few cartons can you use?

This is the bin packing problem, and it is strongly NP-complete. What that means without jargon: nobody has found an algorithm that solves such problems exactly in a time that grows only polynomially with the input, and if anyone did it would simultaneously solve thousands of other famous problems. Nearly every expert believes no such algorithm exists.

So "NP-hard" is a practical instruction: stop looking for the perfect answer and find a good answer fast. A further result puts a ceiling on the heuristics too — unless P = NP, no polynomial-time algorithm can guarantee an absolute ratio better than 3/2 of the optimal number of bins. (Schemes exist that get arbitrarily close to optimal for very large inputs, at a steep cost in running time.)

First-fit decreasing

The standard practical heuristic sorts items heaviest first, then places each into the first carton it fits in, opening a new carton only when none fits. Its tight bound, proved by György Dósa in 2007, is FFD(S,C) ≤ (11/9)·OPT(S,C) + 6/9: never more than about 22% more cartons than the theoretical best, plus a fraction of a carton. Dósa also gave an example that hits the bound exactly, so it cannot be improved.

export type PackItem = { sku: string; weight_kg: number };
export type Carton = { items: PackItem[]; used_kg: number };

export function firstFitDecreasing(
  items: PackItem[],
  capacityKg: number,
): Carton[] {
  // reject anything that can never fit - fail loudly, never drop silently
  const over = items.filter((i) => i.weight_kg > capacityKg);
  if (over.length > 0) {
    throw new Error('Over capacity: ' + over.map((i) => i.sku).join(', '));
  }

  const sorted = [...items].sort((a, b) => b.weight_kg - a.weight_kg);
  const cartons: Carton[] = [];

  for (const item of sorted) {
    let placed = false;
    for (const c of cartons) {
      if (c.used_kg + item.weight_kg <= capacityKg + 1e-9) {
        c.items.push(item);
        c.used_kg += item.weight_kg;
        placed = true;
        break;                    // FIRST fit, so stop looking
      }
    }
    if (!placed) {
      cartons.push({ items: [item], used_kg: item.weight_kg });
    }
  }
  return cartons;
}

Line by line. The guard rejects any single item heavier than a whole carton; without it the loop opens an over-capacity carton and the bug surfaces at the shipping desk. The sort is descending by weight — that "decreasing" is the entire difference from plain first-fit. The inner loop scans open cartons from the first and stops at the first with room; the break is what makes it first fit rather than best fit. The + 1e-9 is a floating-point tolerance so 14.9 + 0.1 does not fail to fit in 15.0. Complexity is O(n log n) plus O(n × cartons), and n here is tens of items.

21 packs, carton capacity 15.0 kg, total 60.3 kg
Lower bound = ceil(60.3 / 15.0) = 5 cartons

FFD result (verified output):
  carton 1  14.8 kg   7.4 + 7.4
  carton 2  14.8 kg   4.2 + 4.2 + 4.2 + 1.1 + 1.1
  carton 3  14.8 kg   4.2 + 4.2 + 4.2 + 1.1 + 1.1
  carton 4  14.8 kg   2.6 + 2.6 + 2.6 + 2.6 + 1.1 x 4
  carton 5   1.1 kg   1.1
  => 5 cartons, equal to the lower bound, so optimal here.
  (proven worst case at OPT=5 is 11/9 x 5 + 6/9 = 6.78, i.e. 6)

Where the sort earns its keep - weights
  [5.9, 1.9, 0.7, 2.0, 5.5, 5.2, 4.8, 2.9], capacity 15.0:
  first-fit in arrival order : 3 cartons  (13.4, 10.7, 4.8)
  first-fit DECREASING       : 2 cartons  (15.0, 13.9)

Reading the trace. Both blocks are verified program output, re-run for this edition. In the first, FFD found five cartons and the arithmetic lower bound is also five, so here the heuristic happened to be optimal — the proven bound only promised at most six.

The second block is the one to remember: on that eight-item list, arrival order needs three cartons and sorting first needs two, so one sort call removed a third of the cartons.

Two caveats. Real carton packing is multi-dimensional: weight, volume and the box's length, width and height all constrain it at once, and this code models weight alone. And most wholesale shipments use a standard pack configuration per style anyway, so ask the warehouse whether they want a packer at all before you build one.

Prepacks and size runs

Wholesale apparel often ships in prepacks: a sealed carton with a fixed size ratio such as 1 XS, 2 S, 3 M, 2 L, 1 XL — a "1-2-3-2-1" pack of nine units. Retailers order whole packs, which cuts picking cost and stops them cherry-picking the middle sizes. Two questions follow: given a ratio, how many packs cover demand, and what ratio should you choose?

Season demand by size for WMN-JKT-001-BLK:
  XS  40    S  95    M 160    L 110    XL  45      total 450

Q1 - how many 1-2-3-2-1 packs cover all demand?
  XS  40/1 = 40.0    S  95/2 = 47.5    M 160/3 = 53.3
  L  110/2 = 55.0   XL  45/1 = 45.0
  Need max = 55 packs.
  Ships XS 55, S 110, M 165, L 110, XL 55 = 495 units.
  Overship 45 units (10%): XS +15, S +15, XL +10, M +5, L +0.

Q2 - derive the ratio FROM the demand (pack of 9):
  size   demand   share    x9 exact   floor   remainder
  XS        40    8.89%      0.80        0       0.80
  S         95   21.11%      1.90        1       0.90
  M        160   35.56%      3.20        3       0.20
  L        110   24.44%      2.20        2       0.20
  XL        45   10.00%      0.90        0       0.90
                             9.00        6    need 3 more
  Largest remainders: S (.90), XL (.90), XS (.80)
  => 1 - 2 - 3 - 2 - 1    exactly the classic curve.

Reading the trace. Question 1 divides each size's demand by its count in the pack; the largest quotient is how many packs satisfy every size, because you cannot open a sealed pack. Covering L's 110 units at 2 per pack forces 55 packs, which overships the sizes that are thin in the ratio. The alternative, 45 packs, undershoots M and L and leaves a residual to fill with loose units, which is what most brands actually do.

Question 2 is the pleasing part. Convert demand to percentages, multiply by the pack size, and you get fractional size counts that must become whole numbers summing to exactly 9. That is the same problem as allocation proration, and it has the same solution: floor everything, count the shortfall, give the extras to the largest remainders. Running prorate on this demand with a supply of 9 produces 1-2-3-2-1, the same curve the trade reaches for by habit, this time derived from the brand's own demand.

Matching and deduplication

Chapter 7 gave you the customer import problem. A rep hands you a spreadsheet of 20,000 accounts from a badge scanner, and some already exist under a slightly different spelling. "Nordstrom Inc", "NORDSTROM, INC." and "Nordstrum Inc" are one customer, and a naive exact-match import creates three.

Edit distance

The standard measure of string difference is Levenshtein edit distance: the minimum number of single-character insertions, deletions or substitutions needed to turn one string into the other.

export function levenshtein(a: string, b: string): number {
  if (a === b) return 0;
  if (a.length === 0) return b.length;
  if (b.length === 0) return a.length;

  // Two rows are enough. Full grid O(m*n) space is unnecessary.
  let prev = new Array<number>(b.length + 1);
  let cur  = new Array<number>(b.length + 1);

  // cost of building b from an empty string
  for (let j = 0; j <= b.length; j++) prev[j] = j;

  for (let i = 1; i <= a.length; i++) {
    cur[0] = i;                    // cost of deleting all of a so far
    for (let j = 1; j <= b.length; j++) {
      const cost = a[i - 1] === b[j - 1] ? 0 : 1;
      cur[j] = Math.min(
        cur[j - 1] + 1,            // insert a character into a
        prev[j] + 1,               // delete a character from a
        prev[j - 1] + cost,        // substitute, or match at cost 0
      );
    }
    [prev, cur] = [cur, prev];     // swap buffers, no allocation
  }
  return prev[b.length];
}

Line by line. The algorithm is dynamic programming: it builds the answer out of answers to smaller sub-problems. Conceptually there is a grid where cell (i, j) holds the edit distance between the first i characters of a and the first j of b.

Each cell depends only on the cell above, the cell to the left, and the cell diagonally up-left, so only the previous row is ever needed — hence two arrays instead of a full grid. The three-way Math.min picks the cheapest way to reach the cell. Time is O(m × n). Space is one row of length b.length + 1, so pass the shorter string as b and it becomes O(min(m, n)).

levenshtein, verified output:
  "kitten"            "sitting"              => 3
  "nordstrom"         "nordstrum"            => 1
  "saks fifth avenue" "saks 5th avenue"      => 3
  "revolve clothing"  "revolve clothing llc" => 4
  "bloomingdales"     "bloomingdale's"       => 1

Reading the trace: real outputs. Note the last three. A legal-suffix difference scores 4 and a punctuation difference scores 1, which shows why you must normalize before comparing — lowercase, strip punctuation, strip inc/llc/ltd/co, collapse whitespace — or your distances measure boilerplate instead of identity.

Why the naive approach is impossible

To find duplicates you must compare pairs, and the number of unordered pairs among n records is n(n − 1)/2.

Reading the table: the 2,000-record row was measured — 1,999,000 pairs of company-name strings took 1,845 ms on Node 25, about 0.92 microseconds per pair, and the other rows are that rate multiplied out. Twenty thousand records is 200 million comparisons and three minutes during which that function computes nothing else; a hundred thousand records is well over the 300-second ceiling Vercel puts on a single function (as of July 2026). Longer names cost more per pair, so treat these as the optimistic case. Note the shape: five times the data costs twenty-five times the work.

The fix: blocking

Almost every pair is obviously not a match, and you should not spend a Levenshtein computation discovering that "Nordstrom" is unlike "Zebra Trading Co". Blocking groups records by a cheap key and compares only within groups. The arithmetic is decisive: split n records into b blocks of size n/b, and total pairs become b × (n/b)²/2 = n²/(2b). Blocking into b blocks divides the work by b.

const normalise = (s: string) => s
  .toLowerCase()
  .replace(/\b(inc|llc|ltd|co|corp|company|the)\b/g, '')
  .replace(/[^a-z0-9]+/g, ' ')
  .trim();

// cheap key: first 4 letters of the name + postcode prefix
const blockKey = (r: { name: string; postcode: string }) =>
  normalise(r.name).replace(/ /g, '').slice(0, 4)
  + '|' + r.postcode.slice(0, 3);

export function findDuplicates(
  records: { id: string; name: string; postcode: string }[],
  maxDistance = 3,
) {
  const blocks = new Map<string, typeof records>();
  for (const r of records) {
    const k = blockKey(r);
    const bucket = blocks.get(k);
    if (bucket) bucket.push(r);
    else blocks.set(k, [r]);
  }

  const pairs: { a: string; b: string; distance: number }[] = [];
  for (const bucket of blocks.values()) {
    for (let i = 0; i < bucket.length; i++) {
      for (let j = i + 1; j < bucket.length; j++) {
        const d = levenshtein(normalise(bucket[i].name),
                              normalise(bucket[j].name));
        if (d <= maxDistance) {
          pairs.push({ a: bucket[i].id, b: bucket[j].id, distance: d });
        }
      }
    }
  }
  return pairs;
}

Line by line. normalise lowercases, removes legal suffixes and the definite article, collapses runs of non-alphanumerics to a single space, and trims. blockKey builds a cheap grouping key from the first four letters of the squashed name plus the first three characters of the postcode, so two records are compared only if both agree. The first loop bins every record in one linear pass. The triple-nested loop then does the expensive comparison within each bucket, with j = i + 1 generating each unordered pair exactly once.

Complexity: O(n) to block, plus the pairwise cost inside each block. With 20,000 records in 500 blocks averaging 40 records each, that is 500 × 780 = 390,000 pairs instead of 199,990,000 — a 512-fold reduction, and at the measured 0.92 microseconds per pair about a third of a second instead of three minutes. The trade-off is honest: blocking misses a true duplicate whose block key differs, so the standard mitigation is several blocking passes with different keys — name prefix, postcode plus city, normalized phone number, and taking the union of the candidates each pass finds.

Letting Postgres do it instead

create extension if not exists pg_trgm;
create extension if not exists fuzzystrmatch;

create index customer_name_trgm
  on customer using gin (lower(name) gin_trgm_ops);

-- indexed fuzzy match; similarity_threshold defaults to 0.3
select id, name, similarity(lower(name), lower($1)) as score
from customer
where lower(name) % lower($1)
order by score desc
limit 10;

-- candidate pairs for a whole import, entirely in the database
select a.id, b.id, similarity(lower(a.name), lower(b.name)) as score
from staging_customer a
join customer b
  on lower(a.name) % lower(b.name)
where a.postcode = b.postcode
  and levenshtein(lower(a.name), lower(b.name)) <= 3;

Line by line. pg_trgm breaks strings into overlapping three-character sequences called trigrams and supplies similarity() plus the % operator, which returns true when the similarity of its two arguments is greater than pg_trgm.similarity_threshold — documented as defaulting to 0.3, and adjustable per session. The GIN index with gin_trgm_ops makes % index-backed; GIN is an inverted index, explained in the next section.

The second query finds candidate pairs for a whole import in one statement: the trigram operator does the indexed blocking, postcode equality narrows it further, and levenshtein from fuzzystrmatch scores the survivors. Note that the documentation limits each levenshtein argument to 255 characters, so normalize and truncate long names before you pass them in.

Search

A rep at a trade show types WMN-JK into a phone and expects matching styles instantly. That is prefix search, and it is the one text search a plain B-tree handles beautifully: because a B-tree stores keys in sorted order, every string starting with WMN-JK occupies one contiguous run of leaf entries, found by descending once and walking sideways.

-- prefix search: uses a plain B-tree
create index style_code_prefix_idx
  on style (upper(code) text_pattern_ops);

select code, name from style
where upper(code) like upper($1) || '%'
order by code
limit 20;

-- NOT prefix search: leading wildcard, no B-tree can help
-- select * from style where code like '%JK%';   -- sequential scan

Line by line. text_pattern_ops tells the index to compare values character by character instead of by the database's collation — the locale-specific rules that decide sort order for text. That makes LIKE 'prefix%' index-usable in any locale; without it, a database not running the plain "C" locale will ignore the index for pattern matching.

Upper-casing on both the index expression and the query keeps the search case-insensitive and still index-backed — the index is built on the expression upper(code), so the query must use the identical expression. The commented query is the contrast: a leading % means matches can start anywhere, so Postgres scans every row. O(n) against O(log n).

The inverted index and full-text search

For descriptive text, "black quilted jacket" against style names and descriptions, the structure is an inverted index. A normal index maps a row to its content; an inverted index maps each word to the rows containing it, and the name comes from that inversion.

Forward (the table):
  style 101 => "Womens Quilted Jacket Black"
  style 102 => "Womens Wool Coat Black"
  style 103 => "Mens Quilted Vest Navy"

Inverted index (word => rows):
  black   => [101, 102]        men    => [103]
  coat    => [102]             navy   => [103]
  jacket  => [101]             quilt  => [101, 103]
  vest    => [103]             women  => [101, 102]
  wool    => [102]

Query "quilted black":
  quilt => [101, 103]
  black => [101, 102]
  intersect  => [101]        one row, nothing scanned

Reading the diagram: the forward view is the table as you think of it; the inverted view lists each distinct word once with the rows it appears in. Note that quilted became quilt and womens became women — that is stemming, folding grammatical variants together so a search for one finds the others. A two-word query becomes two list lookups plus a set intersection, and the cost depends on how many rows contain those words, not on how many rows exist.

alter table style add column search_doc tsvector
  generated always as (
    setweight(to_tsvector('english', coalesce(code, '')),        'A') ||
    setweight(to_tsvector('english', coalesce(name, '')),        'B') ||
    setweight(to_tsvector('english', coalesce(description, '')), 'C')
  ) stored;

create index style_search_idx on style using gin (search_doc);

select code, name, ts_rank(search_doc, q) as rank
from style, websearch_to_tsquery('english', $1) q
where search_doc @@ q
order by rank desc
limit 20;

Line by line. tsvector is the preprocessed document, normalized lexemes with positions, and tsquery the preprocessed query, combining terms with & (and), | (or) and ! (not). The generated column builds the tsvector from three columns and keeps it in sync on every write, stored meaning it is materialized rather than recomputed, while setweight makes a code hit rank above a description hit. The docs are explicit that GIN is preferred: as inverted indexes "they contain an index entry for each word (lexeme), with a compressed list of matching locations", and are not lossy, whereas GiST "might produce false matches".

Queues and scheduling

Chapter 9 built the background job system:

• import a CSV
• recalculate ATS
• render a pick ticket (the sheet a warehouse worker carries to collect an order)
• push an order to the 3PL (a third-party logistics provider — the outside company that stores and ships your stock)

Those jobs go in a queue.

FIFO queues and the priority heap

A FIFO queue is first-in, first-out, like a line at a counter — push to the back, pop from the front, both O(1) with the right structure. Using a JavaScript array with push and shift makes the pop O(n), because shift has to move every remaining element down one slot, which is quadratic over the whole queue.

Measured on Node 25, draining an array of 50,000 numbers with shift took 143 ms; 200,000 took 2.3 seconds; 800,000 took 37.7 seconds — four times the data, sixteen times the work, exactly the quadratic shape. Reading the same arrays with a head index that only moves forward took under half a millisecond in every case. Keep a head index.

A priority queue pops the most important item rather than the oldest, so a rush order jumps ahead of a nightly report rebuild. The structure that implements it efficiently is a heap: a tree kept in an array where every parent is at least as important as its children. It does not keep everything sorted, which would be expensive; it guarantees only that the most important item sits at the root. Push and pop are O(log n), and peeking is O(1).

/** Min-heap keyed by score. Lower score pops first. */
export class PriorityQueue<T> {
  private heap: { score: number; value: T }[] = [];

  get size() { return this.heap.length; }

  push(score: number, value: T): void {
    this.heap.push({ score, value });
    let i = this.heap.length - 1;
    while (i > 0) {                          // bubble up: O(log n)
      const p = (i - 1) >> 1;                // parent index
      if (this.heap[p].score <= this.heap[i].score) break;
      [this.heap[p], this.heap[i]] = [this.heap[i], this.heap[p]];
      i = p;
    }
  }

  pop(): T | undefined {
    if (this.heap.length === 0) return undefined;
    const top = this.heap[0];
    const last = this.heap.pop()!;
    if (this.heap.length > 0) {
      this.heap[0] = last;
      let i = 0;
      for (;;) {                             // sink down: O(log n)
        const l = 2 * i + 1, r = 2 * i + 2;
        let small = i;
        const h = this.heap;
        if (l < h.length && h[l].score < h[small].score) small = l;
        if (r < h.length && h[r].score < h[small].score) small = r;
        if (small === i) break;
        [h[i], h[small]] = [h[small], h[i]];
        i = small;
      }
    }
    return top.value;
  }
}

Line by line. The heap lives in a flat array and the tree structure is implicit in the indices: the children of i are at 2i+1 and 2i+2, and the parent of i is at (i−1)/2 rounded down, which >> 1 computes quickly. push appends and then swaps the new item with its parent while it is more important, running at most log n times. pop takes the root, moves the last element into the root to keep the array dense, then sinks it until the heap property holds. Both are O(log n).

SKIP LOCKED is a concurrent queue pop

An in-memory heap works inside one process. Your job system runs several workers at once, and two workers must never claim the same job. Doing that correctly with locks and retries in application code is genuinely difficult, and Postgres already solves it.

create table job (
  id           bigserial primary key,
  kind         text not null,
  payload      jsonb not null,
  priority     int not null default 100,   -- lower = more urgent
  run_after    timestamptz not null default now(),
  status       text not null default 'queued',
  attempts     int not null default 0,
  locked_at    timestamptz
);

create index job_claim_idx on job (priority, run_after)
  where status = 'queued';

-- claim exactly one job, atomically, with many workers running this
update job
set status = 'running', locked_at = now(), attempts = attempts + 1
where id = (
  select id from job
  where status = 'queued' and run_after <= now()
  order by priority, run_after
  for update skip locked
  limit 1
)
returning id, kind, payload;

Line by line. The table is the queue, and priority plus run_after gives a priority queue with delayed execution in one ordering. The partial index — note the where status = 'queued' clause — indexes only claimable rows, so it stays small even when the table holds millions of completed jobs, which is the difference between a queue that stays fast and one that degrades over months.

The claim statement is the important part. The inner select orders queued, due jobs and picks one, and for update takes a row lock. skip locked is the key phrase: the documentation states that with it, "any selected rows that cannot be immediately locked are skipped", and notes this suits multiple consumers on a queue-like table. Worker A locks job 1; worker B running the identical statement at the identical moment neither blocks nor fails — it skips job 1 and takes job 2. The outer update marks the row and returns the payload in the same round trip.

pgmq is a mature Postgres-native queue extension — v1.12.0 as of July 2026, supported on Postgres 14 through 18, and the engine behind Supabase Queues. It gives you a visibility timeout (a claimed message becomes visible to other workers again if the worker does not finish in time) and archiving instead of deletion. Reach for it before writing your own retry logic.

Either way you need a reaper: a scheduled statement that returns jobs to queued when locked_at is older than the maximum expected runtime, and moves them to a dead-letter table, a parking place for jobs that failed too many times, after N attempts. Without one, a worker that dies mid-job leaves its row stuck in running forever.

Streaming and bounded memory

Chapter 7's import problem, at scale. A 3PL sends a 500,000-row inventory snapshot as CSV. The obvious code reads the file, parses it, and iterates the array. Measured on Node 25, that costs the following:

Parsed CSV rows held in a JavaScript array, 12 fields each:

  rows       CSV size    heap used    process RSS   bytes/row
  500,000       49 MB     175.7 MB        349 MB         368
  2,000,000    200 MB     699.0 MB        879 MB         366

  Node default heap limit on this machine:  4,288 MB
  Vercel Function memory, July 2026:        2 GB default,
                                            4 GB max on Pro

Repeated values V8 can share are cheaper: the same 500,000
rows with only a handful of distinct strings cost 76 MB of
heap. Unique lot numbers and free-text notes cost the most.
Add a Map keyed by SKU on top and you have doubled it.

Reading the trace: 176 MB of heap and 349 MB of RSS — resident set size, the total memory the operating system has handed the process — for 49 MB of CSV on disk, because every parsed row becomes a JavaScript object and every property carries overhead.

Multiply the file by four and everything scales with it: 2 million rows need 699 MB of heap and 879 MB resident, which is uncomfortably close to a 2 GB function once a lookup map and the parser's own buffers are added. The ratio is the part to remember: parsed objects here cost roughly two to four times the size of the raw file, and more when every field is unique.

Streaming the import with chunked writes

import { createReadStream } from 'node:fs';
import { parse } from 'csv-parse';
import type { SupabaseClient } from '@supabase/supabase-js';

type Row = { sku: string; warehouse: string; qty: string };

export async function importSnapshot(
  path: string,
  supabase: SupabaseClient,
) {
  const parser = createReadStream(path).pipe(
    parse({ columns: true, skip_empty_lines: true, trim: true }),
  );

  const BATCH = 1_000;
  let batch: { sku: string; warehouse: string; qty: number }[] = [];

  // O(1) accumulators - these do NOT grow with the input
  let rows = 0, totalQty = 0, rejected = 0;
  let minQty = Infinity, maxQty = -Infinity;

  const flush = async () => {
    if (batch.length === 0) return;
    const { error } = await supabase
      .from('stock_snapshot')
      .upsert(batch, { onConflict: 'sku,warehouse' });
    if (error) throw error;
    batch = [];                    // release the references
  };

  for await (const row of parser as AsyncIterable<Row>) {
    rows++;
    const qty = Number.parseInt(row.qty, 10);
    if (!Number.isFinite(qty) || !row.sku) { rejected++; continue; }

    totalQty += qty;
    if (qty < minQty) minQty = qty;
    if (qty > maxQty) maxQty = qty;

    batch.push({ sku: row.sku, warehouse: row.warehouse, qty });
    if (batch.length >= BATCH) await flush();
  }
  await flush();

  return { rows, rejected, totalQty, minQty, maxQty,
           meanQty: rows ? totalQty / rows : 0 };
}

Line by line. createReadStream opens the file without reading it, and .pipe(parse(...)) feeds chunks through a streaming CSV parser emitting one row at a time, with columns: true using the header line for named fields.

BATCH and batch implement chunking: we do not write one row per query, which would be 500,000 round trips, and we do not write all of them at once, which would be the memory problem again. An upsert inserts a row, or updates the existing one when the key already exists — here the pair of sku and warehouse.

Somewhere between 500 and 2,000 rows per upsert is a sensible starting point; time your own and adjust, because the best size depends on row width and network latency.

flush sends the batch then reassigns batch to a fresh empty array, dropping the references so the collector can reclaim those objects. for await (const row of parser) is the streaming loop — it pulls one row at a time and applies backpressure, so the parser cannot race ahead of the database writes and pile rows in memory. A bad row increments a counter and is skipped rather than aborting the import.

The accumulators are the part to study. rows, totalQty, rejected, minQty and maxQty are five numbers, O(1) space: 500,000 rows or 50 million, the memory is identical. The mean is derived at the end from the sum and count rather than stored. That is a running aggregate, computed in one pass with constant memory. Peak memory here is one CSV chunk plus 1,000 row objects — on the order of a megabyte, whatever the file size.

Correctness of numbers

An ERP that is fast and wrong is worthless. Two numeric failures cause almost all money bugs.

Floating point and the toFixed trap

Floating point. JavaScript's number is an IEEE 754 double, a binary fraction. Binary cannot represent 0.1 exactly, just as decimal cannot represent 1/3 exactly.

Verified in Node:
  0.1 + 0.2               => 0.30000000000000004
  0.1 * 3                 => 0.30000000000000004
  (1.005).toFixed(2)      => "1.00"     (expected "1.01")
  (0.615).toFixed(2)      => "0.61"     (expected "0.62")
  Number.MAX_SAFE_INTEGER => 9007199254740991

Reading the trace: these are real outputs, copied from a Node session. The toFixed results are the dangerous ones, because toFixed looks like a rounding function and gets used as one everywhere. 1.005 is stored as very slightly less than 1.005, so it rounds down and your invoice is a cent short — a cent that will not reconcile and that costs someone a day to find.

The rule: store money as integers. Work in minor units — the smallest unit of the currency, so cents for dollars and pence for pounds. In Postgres use bigint cents or numeric(14,2), never float, real or double precision. In TypeScript carry cents as number, which is exact up to 9,007,199,254,740,991 — about $90 trillion. Where you genuinely need fractions, as in unit costs and BOM consumption, use numeric.

Watch how your client hands those values back: the node-postgres driver returns numeric and bigint as JavaScript strings, because it has no parser that could convert them without risking precision. Do not "fix" that with Number(). Parse them into a decimal library or into integer minor units.

Rounding once, in one place

Rounding strategy. Once you have integers, decide how to round and apply it consistently. Half-up (0.5 rounds away from zero) is what most people expect and what most tax authorities specify. Half-even, or banker's rounding, rounds 0.5 to the nearest even number and avoids the systematic upward drift of always rounding half up across millions of rows. Pick one, put it in a single shared function, and never round in more than one place.

/** Round to whole minor units (cents), half away from zero. */
export const roundHalfUp = (x: number): number =>
  x >= 0 ? Math.round(x) : -Math.round(-x);

/** Extend a line: qty x unit price, both minor units, ONE rounding. */
export function extendLine(
  qty: number,
  unitPriceCents: number,
  discountPct: number,
): number {
  const gross = qty * unitPriceCents;            // exact: both integers
  return roundHalfUp(gross * (1 - discountPct)); // round once, at the end
}

Line by line. Math.round rounds half toward positive infinity, so Math.round(-0.5) is -0 rather than -1; for symmetric behavior on credits and returns you must negate, round and negate back, which is what roundHalfUp does. extendLine shows the other half of the rule: multiply the two integers first, which is exact, apply the discount, and round exactly once at the end. Rounding after each intermediate step compounds error, and on a 40-line order it will visibly disagree with the customer's own arithmetic.

Distributing a rounded total is the allocation problem again. A $250.00 freight charge across three $1,000.00 lines gives exact shares of 8,333.33 cents; round each independently and you get 24,999 cents, one short, and the invoice does not foot. Run prorate(25000, lines) instead and the verified result is 8,334 / 8,333 / 8,333 = exactly 25,000. Any time you split a total, put it through the allocator. Plain division will not add back up.

When not to write an algorithm

Apply this decision rule every time, in order, stopping at the first "yes".

1. Can Postgres express it? Push it into SQL. Aggregation, grouping, joining, sorting, filtering, ranking, running totals, percentiles, date bucketing, deduplication by key, top-N-per-group — each is one query, executed by optimized C over data that is often already in the database's own memory cache.

Window functions (row_number(), lag(), sum() over (order by ...)) let one row's result depend on its neighbors without a self-join, and they cover an enormous share of what people write loops for. If the query is slow, run it with EXPLAIN (ANALYZE, BUFFERS) in front, that prints the plan Postgres chose and what it actually cost, before you write a line of TypeScript.

2. Does a well-maintained library do it? Use the library:

• Date arithmetic across time zones and daylight saving is a swamp — use date-fns today. (The Temporal API is the standard replacement for JavaScript's Date, but as of July 2026 it is still marked limited availability by MDN and is absent from Node 25, so it needs a polyfill.)
• Decimal arithmetic: decimal.js, or integer minor units.
• CSV parsing, where quoted fields contain commas and newlines: csv-parse.
• Checking that incoming data has the shape you expect: zod.
• Job queues: pgmq.

Each of these has been bitten by edge cases you have not thought of yet.

3. Is it one of the genuinely ERP-specific problems? Write it yourself, carefully, with tests. The list is short and this chapter covered most of it:

• forward ATS as a timeline sweep
• allocation with largest-remainder proration
• BOM explosion with cycle rejection
• carton packing by first-fit decreasing
• prepack ratio construction
• dependency ordering by topological sort

These encode your business rules. Make them deterministic, unit-tested against the awkward cases — empty input, zero demand, ties, one unit left over, and write them as pure functions where you can: functions that read only their arguments and touch nothing else, which makes them trivial to test.

A hand-rolled loop is usually a missing query

The honest closing advice: a hand-rolled algorithm in application code is usually the symptom of a missing index or a missing query. When you find yourself looping over fetched rows, ask what the loop is really doing:

• Filtering is a WHERE.
• Summing by group is GROUP BY.
• Looking things up is a JOIN.
• Taking the newest per SKU is DISTINCT ON or a window function.

Only when the answer is genuinely "SQL cannot express this" should you reach for code.

Field notes & further reading

• PostgreSQL: Range Types — the canonical [) convention, the && overlap operator, and the exclusion-constraint example adapted here for price lists.
• PostgreSQL: WITH Queries — recursive CTE structure plus the CYCLE and SEARCH clauses that make graph traversal safe in SQL.
• PostgreSQL: B-Tree Indexes — the five supported operators, and how deduplication shrinks indexes on low-cardinality columns.
• PostgreSQL: SELECT, the locking clause — the exact wording on FOR UPDATE SKIP LOCKED and why it suits queue-like tables.
• PostgreSQL: pg_trgm — similarity(), the % operator, the 0.3 default threshold, and gin_trgm_ops.
• PostgreSQL: GIN and GiST Index Types for Full Text Search — why GIN is preferred and what "lossy" costs you.
• PostgreSQL: ltree — materialized-path storage for the product hierarchy, with @>, <@ and lquery, plus the label rules (hyphens allowed from PostgreSQL 16).
• PostgreSQL: fuzzystrmatch — the in-database levenshtein() function and its 255-character limit per argument.
• First-fit-decreasing bin packing — Dósa's 2007 tight bound of (11/9)·OPT + 6/9, with the example that attains it.
• Bin packing problem — why it is strongly NP-complete, and the proof that no polynomial algorithm beats an absolute ratio of 3/2 unless P = NP.
• Largest remainder method — the apportionment rule behind prorate, including the Alabama paradox it inherits.
• pgmq — the Postgres-native queue behind Supabase Queues; check the releases page for the current version before pinning one.