Matching got slower as supply grew: which stage stopped being linear

Matching is three stages with three different cost curves, and a single latency number tells you nothing about which one gave way. Candidate generation finds the sellers who could plausibly serve this request. Scoring evaluates each of them. Assignment picks who actually gets it, sometimes across several requests at once. Supply growth pushes on all three, but it breaks them at different sizes and in different shapes, and the repair for each is structurally unlike the others — shrink the set, make each candidate cheaper, or change the formulation.

This page is about matching that is slow. If matching is fast and the offers go unanswered, that is a different failure with different evidence — see requests that reach sellers and nobody takes.

Three clocks on one request, then a log-log plot

Emit four numbers per match: the duration of each stage and the size of the candidate set the stage received. Aggregate over a week of real traffic and plot stage duration against candidate count with both axes logarithmic. On those axes a power-law cost draws a straight line, and its slope is the exponent. That single picture usually ends the investigation before anyone opens a profiler, and it is worth building even if you think you already know the answer.

Candidate sets that nothing was ever asked to bound

The most common regression is that candidate generation was written when every seller in the city was a candidate, and that was fine when the city held 200 of them. Nothing in the code caps the set, so it grows exactly as fast as supply, and every downstream stage inherits the growth. Look for the absence of a limit rather than for a slow query.

• Cap the set explicitly. Take the nearest 50 eligible sellers, or the 30 with the earliest availability, and record when the cap binds. A cap that binds on 90% of requests is doing real work; one that never binds is documentation.
• Push eligibility into the index rather than filtering afterwards. A spatial index turns 'within 20 km' into an index scan; computing distance to every seller and filtering in application code is the same answer at a hundred times the cost.
• Order the filters by how much each removes. Hard constraints first, cheapest first — the build order argued in the first ranking function for a thin market, which is also the cheapest one to execute.
• Watch for a cap that silently reintroduces a fairness problem. Nearest-50 in a dense district can exclude the same sellers every time, which is exactly how a performance fix becomes the concentration described in is it the ranker or the market.

One network call per candidate is the single most common fault

A scoring loop that looks innocent in code — fetch the seller's current rating, ask the travel-time service for an estimate, check a fraud flag — becomes three round trips per candidate. At 30 candidates and 8 ms per call that is under a second. At 600 candidates it is fourteen seconds, and the slope on your plot is still 1. The exponent never changed; the constant ate you.

1. Find the loop. Count outbound calls per match request in your tracing tool and divide by the candidate count. Anything above about 1 is a batching opportunity and anything above 3 is the bug.
2. Batch or precompute every signal that is not request-specific. Ratings, verification state, badges and trust flags belong on the seller record, refreshed on write. The trust signals that come out of investigations like what to do with the user who shared a number are exactly this shape — expensive to derive, cheap to store, and disastrous when computed in the hot path.
3. Bound the request-specific ones. Travel time genuinely depends on this request, so ask for it in one batched call for the whole candidate set, and only after the set has been capped.
4. Check what your scoring function actually costs per candidate. A weighted sum over precomputed fields is microseconds; a model inference is milliseconds and may need its own batching. That cost difference is one of the practical arguments in hand-tuned weights or a learned ranker.

The assignment step, where the exponent actually lives

If you are matching one request to one seller, there is no assignment stage — you sort and take the top. The stage appears the moment you batch several requests and solve them together to avoid locally greedy choices. That is usually a good decision, and it is the one made in why waiting two seconds beats nearest-first. It is also the only stage in the pipeline whose cost is genuinely superlinear.

The classical algorithms for optimal assignment run in cubic time in the dimension of the cost matrix. Cubic is forgiving at small sizes and unforgiving at large ones: doubling the matrix multiplies the work by roughly 8, and a tenfold increase multiplies it by roughly 1,000. A batch window that held 20 requests and 40 drivers at launch and now holds 200 and 900 has not grown 10 times harder to solve.

• Shrink the matrix before optimising the solver. Restrict each request to its capped candidate set so the matrix is sparse, and solve the sparse formulation rather than a dense one full of impossible pairings.
• Partition by geography or time slot. Two districts that share no candidate sellers are two independent problems, and solving them separately turns one large cube into several small ones.
• Shorten the batching window. Half the batch size is roughly an eighth of the assignment cost, and the quality lost is usually smaller than teams expect once supply is dense.
• Ask whether you need optimality at all. A greedy pass with a fairness rule is linear, and in thin markets the allocation policy matters far more than the solver — the comparison drawn in auction or round-robin for handing out demand.

Linear stages punish you for growth. The assignment stage punishes you for ambition, and it does it cubically.

The knee: when the data stopped fitting in memory

A fourth pattern is not an algorithm at all. Latency is flat for months, then p99 degrades while p50 stays put, then weeks later p50 follows. That is a working set crossing a memory boundary — a cache that no longer holds the hot sellers, or an index that no longer stays resident — and it looks like an algorithmic regression only because it correlates with growth. The tell is the shape: a knee rather than a curve, and the tail moving first.

Shrink the set, cheapen the candidate, or change the formulation

1. Did candidate-set size grow with supply? If yes, cap it and re-measure everything. Every other fix is worth less until the input stops growing.
2. Is the scoring slope near 1 with a large constant? Count outbound calls per candidate. Precompute what is not request-specific and batch what is.
3. Is the slope near 2? Something compares candidates pairwise. Deduplication and conflict checks are the usual suspects, and both can normally be done with a hash rather than a scan.
4. Is the slope near 3? Do not tune the solver. Sparsify the matrix, partition the problem, or shorten the batch window — in that order, because each is cheaper to ship than the one after it.
5. Is it a knee rather than a slope? This is capacity, not complexity. Find what stopped being resident before rewriting anything.
6. Afterwards, alert on candidate-set size and per-stage p99 rather than on end-to-end latency. The endpoint tells you something is wrong months after the stage told you what.

A matching engine that was correct for 200 sellers and wrong for 2,000 is not a bad build; it is a build whose assumptions were never written down where the next engineer would find them. Recording the bound each stage assumes — and asserting it in a test — is part of what we mean by products built to be handed over. The rest of this silo sits under matching, ranking and dispatch, inside our marketplace and two-sided platform practice.

• matching
• latency
• performance
• dispatch