Redis Vector Search Math

RediSearch is an index, not a second database

RediSearch is a secondary index over keys Redis already holds. Documents are ordinary HASH or JSON keys; FT.CREATE declares a schema over a key prefix, and the module maintains inverted, numeric, tag and vector indexes as those keys change. Nothing is copied elsewhere, and nothing spills to disk on the read path. Two consequences you pay for in bytes: your resident set is documents plus index, not documents alone; and indexing is a write amplifier, since every HSET to an indexed key triggers maintenance, so ingest and query compete for one machine.

Posting lists and the memory they cost

Text search rests on the inverted index: for each term t, a posting list of the documents containing it. A naive entry is a 32-bit doc id plus a frequency, so a term in n_t documents costs about n_t × 8 bytes.

RediSearch does better by storing deltas between sorted doc ids and varint-encoding them. The mean gap is N / n_t, and a varint spends ceil(log2(gap)/7) bytes:

N = 1e6 docs, n_t = 20,000  →  mean gap = 50, log2(50) ≈ 5.6 bits
→ 1 varint byte per id;  list ≈ 20,000 × 2 B = 40 KB
vs. 20,000 × 8 B = 160 KB uncompressed  →  ~4× saving

Frequent terms compress best: a longer list means smaller gaps. Rare terms are cheap because the list is short.

BM25: saturation, length, and a worked example

A posting list tells you which documents match; a scorer tells you which ones matter. RediSearch defaults to a classic TF-IDF variant, with BM25 available via SCORER BM25. BM25 is the one worth understanding, because its two constants encode two real assumptions:

score(q, D) = Σ_t IDF(t) · ( f(t,D) · (k1 + 1) )
                          / ( f(t,D) + k1 · (1 - b + b · |D| / avgdl) )

IDF(t) = ln( 1 + (N - n_t + 0.5) / (n_t + 0.5) )
k1 ≈ 1.2   (term-frequency saturation)
b  ≈ 0.75  (length normalisation strength)

k1 makes term frequency saturate — the tenth occurrence says far less than the second — while b penalises long documents, which otherwise win by surface area. Take N = 1e6 documents, the term in n_t = 20,000 of them, avgdl = 200:

IDF = ln(1 + (1e6 - 20,000 + 0.5)/20,000.5) = ln(50.0) = 3.912

A: f=3,  |D|=120   norm = 0.25 + 0.75·(120/200) = 0.70
   tf = 3·2.2 / (3 + 1.2·0.70) = 6.6/3.84 = 1.719  → 6.72
B: f=3,  |D|=400   norm = 0.25 + 1.50 = 1.75
   tf = 6.6 / (3 + 2.1) = 1.294                 → 5.06
C: f=30, |D|=120   tf = 66 / 30.84 = 2.140      → 8.37

Doc B shows length normalisation: identical hits, 75% of the score, because it is twice the average length. Doc C shows saturation — 10× the term frequency buys only 1.24× the score, which is what stops keyword stuffing from dominating a hybrid ranking.

Vector distance: L2, IP and cosine are the same ranking

A vector field declares DISTANCE_METRIC as L2, IP or COSINE; Redis returns a distance, not a similarity, so smaller is better. For unit-normalised embeddings all three induce the same ordering:

|a| = |b| = 1
||a-b||^2 = |a|^2 + |b|^2 - 2(a·b) = 2 - 2(a·b)
cosine_dist = 1 - (a·b)/(|a||b|) = 1 - (a·b) = IP_dist
⇒ L2^2 = 2 · cosine_dist; all three monotone in (a·b)

So normalise once at write time and pick IP, saving the per-query norm. The trap is mixing them: L2 on un-normalised vectors ranks by magnitude as well as direction, quietly favouring embeddings that drift off the unit sphere.

FLAT: exact search is a bandwidth problem

FLAT is brute force — compare the query against every vector. Recall is 1.0 by construction, and the cost is a straight scan:

N = 5,000,000 vectors,  d = 768,  FLOAT32
bytes  = 5e6 × 768 × 4 = 15.36 GB
FLOPs  = 2 × 5e6 × 768 = 7.68 GFLOP per query
arithmetic intensity = 2 flop / 4 bytes = 0.5 flop/byte

Half a FLOP per byte sits far below the ridge point of any modern CPU (tens of flop/byte), so this is memory-bandwidth-bound, not compute-bound: at an effective 100 GB/s, 15.36 / 100 ≈ 154 ms per query, and AVX-512 will not help. FLAT is the right call under roughly a hundred thousand vectors, or for a small filtered subset — not a five-million-doc corpus.

HNSW: the knobs, and where the memory goes

HNSW replaces the scan with a greedy walk over a layered proximity graph, turning O(N · d) into roughly O(ef · M · d) — independent of N except through a log N descent factor. M sets links per node (memory, linear in M), EF_CONSTRUCTION the candidate breadth while building (build time), and EF_RUNTIME the breadth per query (latency, roughly linear). Only EF_RUNTIME is tunable per query, which makes it the recall dial you actually operate: recall rises steeply from ef = k then flattens, so 64 → 128 might buy 0.94 → 0.97 recall for double the latency on a dataset-specific knee.

Budget the graph separately from the payload. Layer 0 allows up to 2M neighbours per node and holds every node, so it dominates the sparse upper layers:

N = 5e6,  d = 768,  M = 16
vectors     = 5e6 × 768 × 4 B          = 15.36 GB
layer-0 links = 5e6 × 32 × 4 B          =  0.64 GB
upper layers  ≈ +10% of layer 0            ≈  0.07 GB
node headers  ≈ 5e6 × 32 B             =  0.16 GB
total       ≈ 16.2 GB   →  vectors are ~94%

The lesson is blunt: tuning M is not a memory strategy. Halving M saves 0.3 GB and costs recall. Switching the field to FLOAT16/BFLOAT16 saves 7.7 GB, and truncating a Matryoshka embedding from 768 to 384 dimensions saves that much again. Precision and dimensionality are the levers.

Filtered KNN: the brute-force crossover

Hybrid queries such as (@tenant:{acme} @year:[2024 2024])=>[KNN 10 @vec $q] cannot post-filter (the graph returns 10 neighbours, the filter deletes 9). Redis pre-filters instead, then chooses between two strategies: ad-hoc brute force over the filtered set, or batches — repeated graph searches with growing ef until k survivors pass the filter.

Let selectivity s = n_f / N. Batches must surface about k/s candidates to find k that match, and each unit of ef costs some constant c distance computations:

cost_bf     ≈ s · N            cost_batches ≈ c · k / s
equal when  s^2 = c · k / N   →  s* = sqrt(c · k / N)
c ≈ 30, k = 10, N = 5e6  →  s* = sqrt(3e2/5e6) ≈ 0.008

Below roughly 0.8% selectivity — here, ~39,000 documents — scanning beats the graph.

Fusing text and vector rankings

BM25 scores and vector distances are not commensurable: one is an unbounded sum of log-odds, the other a bounded distance in [0, 2]. A linear blend α · bm25 + (1-α) · (1 - dist) needs per-query normalisation, and one outlier BM25 score can swamp the vector term.

Reciprocal rank fusion sidesteps the scale problem by using only ranks:

RRF(d) = Σ_i  1 / (k_rrf + rank_i(d)),   k_rrf = 60

doc at rank 1 (text) and rank 12 (vector):
  1/61 + 1/72 = 0.01639 + 0.01389 = 0.03028
doc at rank 4 in both:
  2 · 1/64 = 0.03125   →  the consistent doc wins

k_rrf = 60 damps the top of each list so one confident retriever cannot dictate the result. Run both queries, fuse the ranked lists, and you get a robust hybrid with no score calibration at all.

Sizing the box: the fork spike and Little's Law

Turn the index estimate into a machine — start from the 16.2 GB HNSW figure and add everything else that must be resident:

vector index                     16.2 GB
document hashes (2 KB × 5e6)   10.0 GB
inverted + tag indexes            ~3.0 GB
allocator overhead (~15%)          4.4 GB
subtotal                          33.6 GB
× replica factor 2                67.2 GB total fleet

Then the Redis-specific trap: BGSAVE and replica sync fork the process, and copy-on-write duplicates every page written during the snapshot, so peak RSS under heavy ingest approaches 2× steady state. Provision to ~60% maxmemory utilisation, or drop forking persistence and rely on replicas. Throughput then follows Little’s Law, L = λ · W:

W = 5 ms per KNN query,  8 query threads
λ_max = 8 / 0.005 = 1,600 qps
to sustain 1,600 qps:  L = 1600 × 0.005 = 8 in flight

Push past λ_max and queueing takes over: latency goes vertical rather than degrading gracefully, and raising EF_RUNTIME raises W and lowers the ceiling proportionally. Redis’s command loop is also single-threaded, so a 154 ms FLAT scan is head-of-line blocking for every GET queued behind it. Shard when the working set stops fitting in one machine’s RAM, not for speed: each shard must search for k, not k/S — the global top-10 could all live on one shard — so fan-out costs S × the single-shard work rather than dividing it.

Pitfalls worth pricing in advance

Building HNSW is not free. Insertion costs roughly EF_CONSTRUCTION · M · d work per vector, so five million vectors is a bulk job measured in hours that competes with serving traffic on the same box.

Deletes are tombstones. Removing a node would break its neighbours’ connectivity, so deleted vectors are marked and skipped. A high-churn index accumulates dead nodes that cost RAM and get traversed anyway; periodic rebuilds are maintenance, not optional.

Dimensions and metric are immutable. Changing DIM, TYPE or DISTANCE_METRIC means FT.DROPINDEX and a full rebuild — so plan an alias-swap reindex path before the incident, not during it.