skip to content

Your exact nearest-neighbour service must serve 50 queries per second over a 2-million-item catalogue on one box — how?

level: seniorimportance: should knowfreq 34%

answer

  1. do the throughput arithmetic first
  2. bytes moved, not asymptotics
  3. read the catalogue once per batch
  4. cache each row's squared norm
  5. per-shard top-k merges exactly

basics

~20 s

Do the arithmetic first: 50 queries over 2 million rows is 100 million row-distances per second, so the work is memory-bound. Batch queries into one pass, store rows contiguously, cache squared norms, shard across cores.

solid answer

~40 s

Start from the budget: 2,000,000 rows * 50 queries per second is 100 million distance computations per second, so the target is bytes moved, not clever structures. Four levers, all exact. **Batch**: score the queries arriving in a short window in one pass, so the catalogue is read once per batch rather than once per query. **Layout**: keep rows contiguous and cache each row's squared norm, since `||q-x||^2 = ||q||^2 - 2*q.x + ||x||^2` and the query term is constant — ranking then needs only a dot product. **Parallelise**: shard the rows across cores and merge per-shard top-k lists, which is exact because a global top-k always sits inside that union. **Pre-filter**: hard constraints applied before scoring shrink n without touching correctness. A partitioning tree is not the lever at these widths.

code

python · 24 lines
python
import random, math

random.seed(0)
D = 8
data = [[random.random() for _ in range(D)] for _ in range(20000)]
q = [random.random() for _ in range(D)]

best_i, best_d = -1, float("inf")
dims_touched = 0
for i, row in enumerate(data):
    acc = 0.0
    for j in range(D):
        diff = q[j] - row[j]
        acc += diff * diff
        dims_touched += 1
        if acc >= best_d:          # this row can no longer win: abandon it
            break
    else:
        best_i, best_d = i, acc

print("nearest row:", best_i, "distance:", round(math.sqrt(best_d), 4))
print("dimensions touched:", dims_touched, "of", len(data) * D)
# nearest row: 5207 distance: 0.2214
# dimensions touched: 37356 of 160000

go deeper

for a junior

Recall that a full scan costs rows times features per query, and that the first move under load is to run it in parallel across cores rather than to invent a new algorithm.

for a middle

Explain the concrete mechanics: contiguous storage, caching each row's squared norm so ranking needs only a dot product, and why one pass over the data can serve a whole batch of queries.

for a senior

An interviewer expects the budget arithmetic up front, the exactness argument for sharded top-k merging, correct filter ordering, and p99 measured with the batching wait included.

for a principal

Own the trade being made: how much latency the batching window may buy, when one box stops being the right unit and the data shards across machines, and what the business is actually paying to keep the results exact.

## Start with the budget, not the data structure The first thing to say out loud is the arithmetic. Two million stored items, fifty queries per second, means **100 million row-distances per second**. If each item is a 128-value vector, that is roughly 1.3 * 10^10 multiply-adds per second and — more importantly — 2,000,000 * 128 * 4 bytes ≈ 1 GB of data read *per query* if you scan naively. Fifty naive scans a second would need 50 GB/s of memory bandwidth, which is why the naive version fails and why the fixes below are all about reading that gigabyte fewer times. ## Lever 1: batch the queries The single biggest win. Buffer queries for a few milliseconds and score the whole batch in one pass over the catalogue. Fifty queries per second with a 20 ms window means one pass per batch instead of fifty passes: the same total arithmetic, but the catalogue's bytes move once rather than fifty times, and the inner loop becomes one large block of multiply-adds over data already in cache. The cost is the added queue latency, which you set deliberately against the tail-latency target rather than accidentally. ## Lever 2: layout and the norm trick Store the vectors as one flat, contiguous block of 4-byte floats, not as a list of separate objects — a sequential read is several times faster than the same values chased through pointers, and prefetching only works on a predictable stride. Then exploit the algebra. Expanding the squared Euclidean distance: ``` ||q - x||^2 = ||q||^2 - 2*(q . x) + ||x||^2 ``` `||q||^2` is the same for every candidate, so it cannot change the ranking and can be dropped entirely. `||x||^2` depends only on the stored row, so compute it once at load time and keep it beside the data. What remains per row is the dot product `q . x` — the whole scan becomes a matrix-times-vector operation over precomputed quantities. The square root is monotonic and is only taken on the k winners, if at all. ## Lever 3: parallelism, and why merging stays exact Split the two million rows into one shard per core. Each core scans its own shard and returns its own top-k. Merge the shard lists and take the global top-k. This is exact, and it is worth being able to justify: the true global k-th nearest item lives in some shard, and within that shard it is among that shard's k nearest — otherwise k items in that one shard would beat it, and they would beat it globally too. So the union of the per-shard top-k lists always contains the global top-k. Sharding by rows never loses an answer; it does not matter how rows are assigned or whether shards are equal in size. The same argument extends across machines when one box eventually stops being enough. ## Lever 4: exact pre-filters If a query carries hard constraints — in stock, correct region, not the user's own item — apply them before or during the scan. Filtering removes candidates that were never eligible, so the result is still exactly the nearest *eligible* item, and a selective filter cuts `n` far more than any micro-optimisation. Be careful about the reverse order: scoring first and filtering the survivors afterwards can return fewer than k eligible items, which is a correctness bug, not a performance one. ## A fifth lever with a caveat: early abandoning Accumulate a row's squared distance dimension by dimension and stop as soon as the partial sum exceeds the current k-th best — the row cannot win, so the remaining dimensions are wasted work. This is exact and can skip a large fraction of the arithmetic, especially with a good initial best. It works against vectorised block arithmetic, though, because the branch breaks the regular loop, so it pays in scalar implementations and often loses in blocked ones. Measure rather than assume. ## What is not a lever here A space-partitioning tree is the reflex answer and it is the wrong one at catalogue-embedding widths: the pruning bound rarely fires, so the tree visits nearly every node and adds traversal overhead to the same arithmetic. Reducing the number of features is also not an exact-search optimisation — it changes the distance function, so a different item can come back; that is a modelling decision to validate, not a free speed-up. Dropping from 8-byte to 4-byte values halves the bytes moved and rarely changes the ranking, but it is a numerical change and should be stated as one. Everything in this answer keeps the returned neighbour identical to a full-precision full scan; relaxing exactness is a separate design conversation. ## Operating it Measure p99 latency, not the mean, and include the batching wait in the number. Watch memory residency — 2,000,000 * 128 * 4 bytes is about 1 GB of vectors, which fits, but the moment it stops fitting the scan starts touching disk and the latency profile changes character entirely. Keep a brute-force, single-threaded reference implementation around: every optimisation above is supposed to return byte-identical results, so a nightly diff against the reference is a cheap and very effective correctness test.

  • Why is merging per-shard top-k lists guaranteed to give the true global top-k?
    Because the true global k-th nearest item sits in some shard, and inside that shard it must be among the k nearest — if it were not, k items from that shard alone would be closer, and they would also be closer globally. So no member of the global top-k can be missed by its own shard's list, and the union always contains the answer. The row-to-shard assignment is irrelevant.
  • What does batching cost you, and how do you size the window?
    It adds queue wait to every query: with a 20 ms window, a query arriving at the start of the window waits the full 20 ms before scoring begins. Size it against the p99 latency budget, not the mean — pick the largest window whose wait plus scan time still fits, and cap it so a burst does not let batches grow unboundedly.
  • Where would you apply a hard filter such as in-stock, and why does the order matter?
    Apply it before or during the scan, so ineligible rows are never scored. Filtering first is exact — the answer is the nearest eligible item — and a selective filter shrinks n more than any tuning would. Score-then-filter is the buggy order: it can return fewer than k eligible results, or none, when the top of the list is all ineligible.
  • How would you prove the optimised path returns the same answers as a plain scan?
    Keep a naive single-threaded scan as a reference implementation and diff against it on a sampled set of real queries as a scheduled job. Every technique here — batching, norm caching, sharding, early abandoning — is supposed to be exact, so any disagreement beyond floating-point tie-breaking is a real bug and shows up immediately.

saying these in an interview costs you the question

  • Reaches for a partitioning tree without checking the width
  • Suggests dropping features and calls the result exact
  • Scores every candidate first, then applies hard filters
  • Optimises arithmetic while ignoring memory bandwidth
  • Quotes mean latency and never measures the tail

context

resolving links…