R3.5 · LESSON 5 OF 6

Disk-based search

Trace IVF and HNSW search and explain how candidate exploration trades latency for recall.

THE IDEA

Disk-based search

When the index does not fit in memory, graph search becomes an I/O problem. Each node visit can mean a random read from storage that costs far more than the arithmetic it feeds. Disk-oriented designs therefore co-locate a node with its neighbours, cache hot blocks, and issue several reads at once so their waits overlap.

distance computations (0.5 µs each)200random reads50reads in flight at once1µs per read100

compute: 100 µs reads: 50 rounds × 100 µs = 5000 µs total 5100 µs share of time spent waiting on storage: 0.98

Plan A: 100 distance computations but 100 random reads takes 10050 µs. Plan B: 1000 computations but only 10 reads takes 1500 µs. Doing fewer calculations does not help if each one waits for the disk. Data layout, caching and read parallelism matter as much as arithmetic.

Change computations, reads and how many reads run in parallel.

Predict first. Can fewer distance calculations still be slower if each needs a costly random read?

Chapter context

An approximate index organizes vectors so a query can avoid most comparisons. Clustering and graph navigation use different mechanisms to choose candidates, and their build settings influence later search quality.

TRY IT YOURSELF

Part 1. Do it hands-on

Cost a search by hand, then write the timing model and an LRU cache.

distance computations (0.5 µs each)200random reads50reads in flight at once1µs per read100

compute: 100 µs reads: 50 rounds × 100 µs = 5000 µs total 5100 µs share of time spent waiting on storage: 0.98

compute µs (200 × 0.5) read µs (50 × 100) share on reads (3 decimals) total µs with 5 reads in flight

To do: A search does 200 distance computations at 0.5 µs each. Compute time in µs?
To do: It also makes 50 random reads one after another at 100 µs each. Read time in µs?
To do: Fraction of the 5100 µs total spent on reads (3 decimals)?
To do: Issuing 5 reads at a time (50 reads in 10 rounds of 100 µs), total time in µs including the 100 µs of compute?

Part 2. Do it in code

compute_us(dists, us_per_dist): time spent on distance computations.
io_us(reads, us_per_read, parallel=1): reads issued `parallel` at a time take ceil(reads / parallel) rounds of us_per_read each.
total_us(plan): plan is a dict with dists, us_per_dist, reads, us_per_read and optionally parallel (default 1); return compute + io time.
io_fraction(plan): the share of total time spent on reads.
lru_hits(accesses, capacity): simulate a least-recently-used cache of that capacity over the list of block ids and return the number of hits (capacity 0 never hits).
faster_plan(a, b): "a" or "b", whichever has the smaller total_us ("a" on ties).

import math

def compute_us(dists, us_per_dist):
    pass

def io_us(reads, us_per_read, parallel=1):
    pass

def total_us(plan):
    pass

def io_fraction(plan):
    pass

def lru_hits(accesses, capacity):
    pass

def faster_plan(a, b):
    pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Can fewer distance calculations still be slow if each needs a costly random read?

AYesBNo

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

Under the simplifying assumption of equally sized IVF lists, N vectors, C cells and p probes produce approximately

N_{candidates}\approx Np/C.

Add coarse scoring, uneven list sizes and any reranking costs separately. HNSW has no equivalent universal fixed candidate-count formula.

Worked example

For 102,400 vectors evenly divided among 1024 cells, a cell has 100 vectors. Probing eight cells scans about 800 candidates, compared with 102,400 in a full scan. This excludes coarse-centroid comparisons and says nothing by itself about recall.

Reference code

The following example uses the Python standard library and does not call a remote service.

total,cells,probes=102400,1024,8
assert total/cells == 100
assert total*probes/cells == 800
assert total/(total*probes/cells) == 128

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

An average candidate count is not an actual worst-case bound. More graph edges consume memory. Approximate search settings must be evaluated against the current corpus and metric.