[selective filter 1] Route filtered queries by selectivity, and search allowlists exhaustively - #1871

Purpose of the change

A filtered query on the SQLite store gave its search engine allowed_keys, a container backed by SQL that ran one point query per candidate the approximate search visited: hnswlib asked it through a filter callback, and usearch fetched more and widened until enough candidates passed, up to the whole index. A selective filter made the search visit most of the index, each candidate a round trip, and none of those queries used the declared columns' indexes that [declared schema 1/2] (#1628) adds. _KeyFilter also kept a second, synchronous SQLAlchemy engine for the store.

The query now first selects the row ids the filter admits, through the declared columns' indexes, reading at most one row past selective_filter_limit (default 10,000). A filter admitting at most that many records gives the engine those row ids as an allowlist. A broader one is applied to the best limit * overfetch_factor candidates (default 64) of a search without it, with one SQL query per query vector, so its cost is bounded, and a query returns fewer than limit matches when fewer candidates pass.

search takes allowlist in place of allowed_keys. Every vector stored under one of its keys is scored as it would be scored without one, so none is missed, at a cost proportional to the number of keys; a key with no vector stored is ignored. hnswlib and usearch gather the stored vectors by key and score them exactly, by the engine's metric, with one shared function, exact_search_results; hnswlib refuses a batch with any key it does not hold, so it then gathers key by key. An engine whose index restricts its own search to a list of ids, scoring as it does without one, can answer an allowlist with it. Without an allowlist, hnswlib no longer threads a filter through its fallbacks, and usearch makes one search. _KeyFilter was the only user of the store's synchronous SQLAlchemy engine and its foreign-keys hook, which go with it.

This rebuilds #1602, deferred on speedkick until declared properties were indexed columns, on #1628. It differs from #1602 in three ways:

• Its probe runs over [declared schema 1/2] Make a vector store filter only on the properties it declares #1628's indexed columns, where DEFERRED (until lifecycle/DDL changes): Route filtered queries by selectivity, and score allowlists exactly (speedkick) #1602's ran over the JSON column, a full scan.
• It scores each of the engines' metrics (cosine, dot, and Euclidean) as a search without an allowlist does, where DEFERRED (until lifecycle/DDL changes): Route filtered queries by selectivity, and score allowlists exactly (speedkick) #1602, on cosine-only engines, scaled vectors to unit length when they were added and clamped inner products onto the cosine range.
• A broad filter gets one fetch of limit * overfetch_factor candidates, where DEFERRED (until lifecycle/DDL changes): Route filtered queries by selectivity, and score allowlists exactly (speedkick) #1602 widened four times per round up to that many.

Measurements

100,000 clustered 768-dimensional unit vectors (1,000 clusters, each query near one), cosine, limit 10, 20 queries per row: median latency, and recall@10 against the exact top 10 among the admitted records. A spread filter admits records across all clusters; a far filter admits only clusters away from every query. Before is the per-candidate path, measured under a load average of 13 to 24 from other work, after under 4 to 6, so recall compares like for like and latency only roughly.

                 usearch                        hnswlib
admitted         before        after           before          after
spread 1,000     104 ms 0.93    3.6 ms 1.00    1,509 ms 1.00     25 ms 1.00
spread 10,000     12 ms 0.985    22 ms 1.00      196 ms 1.00    247 ms 1.00
spread 50,000    7.6 ms 0.985    17 ms 1.00       47 ms 1.00     17 ms 1.00
far 1,000        157 ms 0.815   3.1 ms 1.00    1,876 ms 0.995    24 ms 1.00
far 10,000        36 ms 0.635    20 ms 1.00      316 ms 0.875   239 ms 1.00
far 50,000        15 ms 0.615    18 ms 0.875      66 ms 0.775    17 ms 0.855

With limit 20, a broad filter's 1,280 candidates take 26 to 40 ms. hnswlib's allowlist search costs about 25 µs per key, most of it in gathering the stored vectors, which is what its 247 ms at 10,000 admitted is; usearch's costs about 2 µs.

An engine backed by turbovec, as #1599 adds on speedkick, answers an allowlist with its index's own restricted search. Through a minimal adapter of #1599's engine (turbovec 1.0.0, 4-bit) on the same data, every row above took 1.8 to 21 ms, with recall from 0.845 to 1.00 against 0.885 for its search without a filter, which is its quantization's ceiling. Sending every filter through the allowlist instead returned the same results, and took 46 to 49 ms at 100,000 admitted.

Stack

Directly on feat/horizontal-scaling at 0fa52b38b, since [declared schema 1/2] (#1628), which it was stacked on, merged as 5c9d3ae99. This PR is its one commit, 3f0e97373 (8 files).

Verification

At this PR's head 3f0e97373, on 2026-11-02, rebased onto feat/horizontal-scaling at 0fa52b38b, after [sqlite write transactions 1] (#1844) merged. The one conflict was the SQLite store's imports: #1844 moved the store's engine checks into common/sql.py (validate_engine_connections), and this PR removes the imports that only the synchronous engine and _KeyFilter used, so the store imports neither StaticPool nor ConnectionPoolEntry. The commit's message is unchanged, and its patch differs only in those import lines. Checks: ruff check and ruff format --check clean; ty check clean as CI runs it; uv lock --check clean. The unit tests pass, 2398 tests (8 skipped).

Before the rebase onto #1844's merge: At this PR's head 9220a34a8, on 2026-10-30, moved onto feat/horizontal-scaling at 690116e37 (#1628's squash 5c9d3ae99, then #1858) with git rebase --onto: the patch is unchanged (git range-diff reports the commit equal). The base gained #1628's last commits (the declared-property column names built without Column objects, and two contract test commits), #1831, and #1858. Checks: ruff check and ruff format --check clean; ty check clean as CI runs it; uv lock --check clean. The vector store and filter unit tests pass, 592 tests (5 skipped).

Before the move onto feat/horizontal-scaling: At this PR's head 07aae3bea, on 2026-10-28, replayed onto #1628's df716e47b, which reverts the oversized Milvus upsert test's partition deletion: the patch is unchanged (git range-diff reports the commit equal), so the tests at 8e1faae00 stand. Checks: ruff check and ruff format --check clean; ty check clean as CI runs it; uv lock --check clean.

Before the replay onto df716e47b: At this PR's head 8e1faae00, on 2026-10-28: ruff check and ruff format --check clean; ty check clean as CI runs it (uv run --frozen --all-extras ty check --project packages/server); uv lock --check clean. The unit tests pass, 2359 tests (8 skipped). The integration tests did not run here; the change touches only the SQLite store and its search engines.

The filter tests and the declared-schema contract run on both paths. New tests check that a selective filter finds an admitted record however far it is from the query; that a broad filter is applied only to the overfetched candidates and keeps at most limit of them; and that an engine's allowlist search keeps to the allowlist, scores as a search without one does on each metric, ignores keys with no vector, and finds nothing for an empty allowlist. The test of a query overtaken by its partition's deletion covers each path. Each of these fails with its path removed: the store never or always using the allowlist, the broad filter keeping more than limit or fetching the whole index, an engine ignoring the allowlist, and hnswlib's key-by-key gather dropping every key.

🤖 Generated with Claude Code