cockroachdb / cockroachdb/cockroach

sql/vecindex: support post-filtering when using a vector index

Open
#146,145 2 comments 0 reactions 0 assignees View on GitHub
A-vector-index C-enhancement docs-known-limitation T-specialized-indexing
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.