matrixorigin / matrixorigin/matrixone
[Feature Request]: support filtered vector search for HNSW, IVFPQ, and CAGRA
- Dominant language
- Go
- Stars
- 1.9k
- Forks
- 311
- Avg merge
- 1d 3h
- Merged PRs (30d)
- 768
Description
## Motivation
Filtered vector search currently lacks one consistent capability contract across HNSW, IVFPQ, and CAGRA.
For a query that combines a vector top-k order with a relational predicate, an approximate index may first produce candidates that are later removed by the predicate. A fixed candidate budget can therefore return fewer than `LIMIT` rows even when enough qualifying rows exist. Users also need an explicit way to choose whether filtering happens before or after ANN candidate generation, plus an automatic mode with predictable behavior.
This issue requests a unified filtered-vector-search feature rather than treating one fixed HNSW over-fetch result as an isolated defect.
## Requested capability
Support a common filter strategy contract for HNSW, IVFPQ, and CAGRA:
1. **Pre-filter**
- Apply eligible relational predicates before ANN candidate selection.
- Define supported predicate shapes and the fallback for predicates that cannot be pushed into the vector search path.
2. **Post-filter with adaptive completion**
- Allow ANN candidate generation followed by relational filtering.
- Refill or retry when filtered candidates are insufficient, until `LIMIT` qualifying rows are produced or the searchable set is exhausted.
- Do not rely only on a fixed over-fetch multiplier for result completeness.
3. **Auto/default strategy**
- Select pre-filter, post-filter, or an exact fallback using available cardinality/selectivity information and index capability.
- Expose the selected strategy and candidate budget in `EXPLAIN`.
- Keep literal and prepared-statement execution behavior consistent.
4. **Correctness-preserving fallback**
- If an index or predicate combination cannot guarantee the requested page, use an exact path or another documented completion strategy instead of silently returning a short or empty page while qualifying rows remain.
## Current behavior motivating the request
Environment:
- Branch: `main`
- Commit: `01d60e1c4ded1b0f3fc1a4ecd75ce54e95e23b90`
- Deployment: local 1 Log / 1 TN / 2 CN
```sql
SET experimental_hnsw_index=1;
DROP DATABASE IF EXISTS hnsw_filter_selective;
CREATE DATABASE hnsw_filter_selective;
USE hnsw_filter_selective;
CREATE TABLE t(
id BIGINT PRIMARY KEY,
category INT NOT NULL,
v VECF32(2)
);
INSERT INTO t
SELECT result,
IF(result <= 500, 0, 1),
CAST(CONCAT('[', result, ',0]') AS VECF32(2))
FROM generate_series(1, 1000, 1) g;
CREATE INDEX ix USING hnsw ON t(v)
M=32 EF_CONSTRUCTION=128 EF_SEARCH=128
OP_TYPE 'vector_l2_ops';
SELECT id
FROM t
WHERE category=1
ORDER BY l2_distance(v, '[0,0]')
LIMIT 10;
```
At the fixed commit, the HNSW path requests 20 candidates for `LIMIT 10`. Those nearest candidates all have `category=0`, so the residual predicate removes them and the query returns zero rows. The exact control returns IDs `501..510`:
```sql
SELECT id
FROM t
WHERE category=1
ORDER BY l2_distance(v, '[0,0]')
LIMIT 10 BY RANK WITH OPTION 'mode=force';
```
Observed stability:
- HNSW path: 3/3 on CN1 and 3/3 on CN2 returned 0 rows.
- Exact control: 3/3 on both CNs returned 10 rows, IDs `501..510`.
- No-index control returned the same 10 exact rows.
- A non-selective indexed control (`category=0`) returned IDs `1..10`.
- Reusing a prepared statement reproduced the same selectivity-dependent behavior.
The example is retained as a concrete motivation and acceptance fixture for the requested filtering strategies.
## Acceptance criteria
- HNSW, IVFPQ, and CAGRA have a documented matrix of supported `pre`, `post`, and `auto/default` behavior.
- A selective predicate that rejects more rows than the initial candidate budget does not silently produce an incomplete page while additional qualifying rows exist.
- `EXPLAIN` identifies the chosen filter strategy, candidate limit, retry/completion behavior, and fallback when applicable.
- Literal and prepared `LIMIT` values behave consistently.
- Coverage includes zero-match, fewer-than-k, exactly-k, and more-than-k qualifying sets; highly selective and non-selective predicates; single and combined predicates; and execution through both CN endpoints.
## Related
- Source exploration: #28943
- #26869 covers prepared `LIMIT` over-fetch handling.
- #23551 previously discussed HNSW pre-filter support.
Contributor guide
Assessment
This issue has not been assessed yet.