cockroachdb / cockroachdb/cockroach
sql/vecindex: support post-filtering when using a vector index
- Dominant language
- Go
- Stars
- 32.5k
- Forks
- 4.1k
- PR merge metrics
- PR metrics pending
Description
Currently, a vector index will not be used when there is a `WHERE` clause present, e.g.:
```
root@localhost:26257/defaultdb> CREATE TABLE t (x INT PRIMARY KEY, col INT, v VECTOR(2), VECTOR INDEX (v));
CREATE TABLE
root@localhost:26257/defaultdb> EXPLAIN SELECT * FROM t WHERE col>100 ORDER BY v <-> '[1,2]' LIMIT 1;
info
------------------------------
distribution: local
vectorized: true
• top-k
│ order: +column7
│ k: 1
│
└── • render
│
└── • scan
missing stats
table: t@t_pkey
spans: [/101 - ]
```
We should enhance the vector index to use an iterator when searching, such that it can continue to pull results when too many earlier results have been filtered. This could trigger additional partition search requests (i.e. more KV traffic) to get more vectors. We will need to maintain a "distance threshold" such that the iterator always returns results in increasing distance order even when merging in results from additional partitions (which may contain vectors that are closer to the query vector than what the iterator has already returned).
Note that the optimizer already supports a common, but special case of post-filtering. If the WHERE clause matches the prefix columns of a vector index, then the optimizer can use the vector index, e.g.:
```
root@localhost:26257/defaultdb> CREATE TABLE t (x INT PRIMARY KEY, col INT, v VECTOR(2), VECTOR INDEX (col, v));
CREATE TABLE
root@localhost:26257/defaultdb> EXPLAIN SELECT * FROM t WHERE col = 100 ORDER BY v <-> '[1,2]' LIMIT 1;
info
---------------------------------------------
distribution: local
vectorized: false
• top-k
│ order: +column8
│ k: 1
│
└── • render
│
└── • lookup join
│ table: t@t_pkey
│ equality: (x) = (x)
│ equality cols are key
│
└── • vector search
table: t@t_col_v_idx
target count: 1
prefix spans: [/100 - /100]
```
This also works when there are multiple prefixes: `WHERE col IN (100, 200)`.
Jira issue: CRDB-50405
Contributor guide
Assessment
This issue has not been assessed yet.