pg.ddx.io  pgvector/pgvector GitHub issues and pull requests  
help / color / mirror / Atom feed
From: klenioaraujo (@klenioaraujo) <noreply+klenioaraujo@github.com>
To: pgvector/pgvector <noreply+pgvector-pgvector@github.com>
Subject: Re: [pgvector/pgvector] issue #761: Enhancement: multicolumn vector index design
Date: Fri, 06 Nov 2026 10:10:48 +0000
Message-ID: <gh-pgvector-pgvector-761-c6682406026@github.com> (raw)
In-Reply-To: <gh-pgvector-pgvector-761@github.com>
References: <gh-pgvector-pgvector-761@github.com>

The measurements from @OmkarPalika are the right way to approach this — asserting the plan with EXPLAIN and comparing against an exact scan in the same database removes the ambiguity that usually makes recall numbers incomparable.

I want to add a distinction that this thread touches but does not name: **recall as a measured outcome** versus **exclusion as a proven property**.

Recall@10 = 0.95 tells you that, across your query set, 5% of the true neighbours were missed on average. It does not tell you which queries missed, nor whether the missed document mattered. When the filter column has high cardinality and low correlation with the vector clusters — exactly the cell @IgnazioDS asked about — the misses concentrate in specific queries rather than spreading evenly. An average hides that.

There is an alternative framing that is not a recall improvement but a different guarantee: for each document *not* returned, compute an upper bound on its similarity to the query, and check whether that bound falls below the score of the K-th result. If it does, the document is provably outside the top-K — not probabilistically, arithmetically. The output is per-document and binary rather than an aggregate statistic.

This is tractable with Cauchy–Schwarz over a projection:

  ⟨v,q⟩ ≤ ⟨Pv,Pq⟩ + ‖v−PᵀPv‖ · ‖q−PᵀPq‖

where P is a projection onto a lower-dimensional subspace. The second term is the projection residual. If the bound is below the K-th score, the document is excluded with proof.

**The parameter that decides everything is how P is chosen.** With a random projection the residual stays large and the bound is too loose to exclude anything — in my measurements, 0 of 2,167 documents excluded. Aligning P to the corpus structure (PCA over a sample) tightens the bound sharply: 2,157 of 2,167 excluded, zero bound violations. Same data, same dimension, same query.

That is directly relevant here. A filter-aware index faces the same problem: the pruning structure must align with the data distribution, or it prunes nothing. Choosing the index structure without reference to the corpus is the analogue of choosing P randomly.

Two concrete numbers from a real corpus (2,167 STJ court decisions, 384-dim multilingual embeddings, K=10), for calibration:

| Projection basis | Documents excluded with proof | Query latency |
|---|---|---|
| random | 0 of 2,167 | 0.2 ms |
| PCA, 128 components | 2,153 (99.4%) | 6.6 ms |
| PCA, 256 components | 2,157 (99.5%) | 21.7 ms |

Reproducible notebook, public output, no account needed: https://www.kaggle.com/code/kleniopadilha/winnex-reproduce-the-proof-yourself

The cost is real: computing and verifying the bound costs latency that pure HNSW does not pay. Whether that trade makes sense for pgvector is a question for this thread, not for me — pgvector's users optimise for the planner and the SQL interface, and a per-document proof may be irrelevant to most of them.

But for the subset of users in regulated settings — where the question is not "was recall high enough" but "can you demonstrate that a specific document was not overlooked" — the bound gives an answer that a recall statistic cannot. And that question is the one that shows up in an audit, not in a benchmark.


view thread (18+ messages)

Message-ID: <gh-pgvector-pgvector-761-c6682406026@github.com>
Permalink:  ../gh-pgvector-pgvector-761-c6682406026@github.com/

 · 


This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox