19. Vector search: VECTOR INDEX

A VECTOR(n) column (chapter 4) stores embeddings produced by a language or image model. Finding the k rows closest to a given vector is written ORDER BY distance LIMIT k:

SELECT id, titre
FROM document
ORDER BY VEC_DISTANCE_COSINE(plongement, VEC_FromText('[0.12, -0.03, ...]'))
LIMIT 10;

Without an index, MIRAJ computes the distance of every row and keeps the k best: the result is exact, but the cost grows with the table (about 90 ms for 100,000 vectors of 128 dimensions). A vector index brings this search down to a fraction of a millisecond, at the price of an approximate result: a few neighbours may be missing, replaced by rows that are almost as close.

19.1 Creating a vector index#

CREATE TABLE document (
    id         INT PRIMARY KEY,
    titre      VARCHAR(200),
    plongement VECTOR(768) NOT NULL,
    VECTOR INDEX (plongement) M=16 DISTANCE=cosine
);

CREATE VECTOR INDEX [IF NOT EXISTS] nom ON table (colonne) [M=n] [DISTANCE=métrique] [COMMENT '…'];
ALTER TABLE table ADD VECTOR INDEX [IF NOT EXISTS] [nom] (colonne) [M=n] [DISTANCE=métrique];
ALTER TABLE table DROP INDEX nom;
DROP INDEX nom ON table;

VECTOR KEY is a synonym of VECTOR INDEX. Without a name, the index takes the name of its column.

Rules:

• a single column, of type VECTOR(n) and declared NOT NULL (error 1252 if it can be NULL, 1210 for another type); no prefix v(2), no DESC, no UNIQUE (1064);
• a single vector index per table (1235 for a second one);
• an ordinary KEY, UNIQUE or PRIMARY KEY on a VECTOR column is still rejected (6133).

Options:

An unknown option is rejected (1911). An option written twice keeps its last value. Options are returned as written by SHOW CREATE TABLE:

  VECTOR KEY `plongement` (`plongement`) `M`=16 `DISTANCE`=cosine

Without an M or DISTANCE option, the index takes the session values; if they differ from the defaults, they are frozen in the definition (`m`=10 `distance`='cosine'): the table is recreated identically whichever session replays the script.

dot (inner product) is a MIRAJ extension: the nearest neighbours are those with the largest inner product. It suits models whose vectors are not normalized and whose similarity is the inner product; for normalized vectors, it is equivalent to cosine.

SHOW INDEX and information_schema.STATISTICS show the index with Index_type = VECTOR, Non_unique = 1 and Cardinality NULL; DESCRIBE marks the column MUL.

The index follows its column through ALTER TABLE: MODIFY v VECTOR(4) NOT NULL keeps it (the graph is rebuilt), DROP COLUMN v removes it, MODIFY v VECTOR(4) without NOT NULL is rejected (1252). TRUNCATE TABLE empties it, CREATE TABLE … LIKE copies it.

19.2 Queries served by the index#

The index serves a query of the form:

SELECT … FROM table [WHERE …]
ORDER BY distance(colonne, vecteur) [ASC]
LIMIT k [OFFSET o];

where:

• distance is a function or operator of the index metric:

• one of the arguments is the indexed column, the other a vector known before execution: a literal (VEC_FromText('[…]'), '[1,2,3]', x'…'), a ? parameter of a prepared statement or a @q variable, with the dimension of the column; the two arguments may be swapped;
• the sort key may be a SELECT alias: SELECT id, VEC_DISTANCE(v, @q) AS d FROM t ORDER BY d LIMIT 5.

VEC_DISTANCE(a, b) has no metric of its own: it takes that of the index of the column it receives, even outside ORDER BY; without a vector index on one of its arguments, it is rejected (error 4206). Use VEC_DISTANCE_EUCLIDEAN or VEC_DISTANCE_COSINE instead.

The index is not used (exact computation by scan) for:

• a DESC sort, a query without LIMIT, a composite sort key (ORDER BY d, id) or an expression of the distance (ORDER BY 1 + d);
• a distance of a metric other than that of the index, or DISTANCE(v, q, 'dot') (which returns the inner product itself, ascending: the farthest first);
• a distance between two columns (VEC_DISTANCE(v, v)), a vector of another dimension;
• a join, a GROUP BY or an aggregation, DISTINCT, a union, SELECT … FOR UPDATE;
• UPDATE … ORDER BY … LIMIT and DELETE … ORDER BY … LIMIT.

WHERE filters#

A WHERE applies to the neighbours found. If it discards too many, MIRAJ restarts the search with four times as many neighbours, then, as a last resort, reads the rest of the table: the query always returns LIMIT rows when the table contains enough of them. A very selective filter (a few rows out of millions) is therefore correct but may cost a scan; an ordinary index on the filtered column is then more efficient (WHERE id = 1 goes through the primary key).

EXPLAIN#

EXPLAIN SELECT id FROM document ORDER BY VEC_DISTANCE(plongement, @q) LIMIT 10;

A read through the index shows type = index, key = index name and rows = LIMIT + OFFSET, without Using filesort. An exact k-NN shows type = ALL and Using filesort.

19.3 Approximation and mhnsw_ef_search#

The index is an HNSW graph (Hierarchical Navigable Small World): the search starts from an entry point and follows links towards ever closer nodes, keeping a list of the best candidates. The length of this list, @@mhnsw_ef_search, sets the trade-off:

The list always holds at least LIMIT + OFFSET candidates. Indicative measurement (100,000 vectors of 128 dimensions, M = 16): 0.4 to 1.1 ms per query depending on ef_search, against 90 ms for the exact computation.

SET mhnsw_ef_search = 64;                                   -- for the session
SET STATEMENT mhnsw_ef_search = 200 FOR SELECT …;           -- for one query

With the dot metric, the graph is harder to traverse (a vector is not necessarily its own nearest neighbour): plan for an ef_search of 64 to 100.

Transactions are honoured: a row inserted or modified by an uncommitted transaction is seen only by that transaction; the index returns only visible rows, and the displayed distance is recomputed on the visible value.

19.4 Variables#

19.5 Storage, memory and build#

The graph lives in memory, alongside the table: about 4 × (2M + 3) bytes per row, excluding the vectors (which are not copied: the index reads the column). For 1 million rows and M = 16, allow about 150 MB.

It is saved in a <table>.vmrj file next to the .mrj, rewritten only when it has changed. At load time, the graph is checked against the table rows (fingerprint of each vector) and then brought in line with the writes replayed from the journal. If it is missing, damaged or too far behind, it is rebuilt: this is never an error, only a longer load. CHECK TABLE checks the graph. A physical backup (chapter 18) does not copy the .vmrj: the graph is rebuilt when the restored database is first loaded.

Every write (INSERT, UPDATE of the column, DELETE, rollback) maintains the graph. A full build (CREATE VECTOR INDEX on a populated table, an ALTER TABLE that rebuilds the table, recovery at load) proceeds in batches:

• Enterprise edition: batches are processed in parallel on the server threads (--parallel-threads); 100,000 vectors of 128 dimensions, M = 16: about 10 s on 12 logical threads, against 49 s serially;
• Express edition: same algorithm on a single thread.

The resulting graph is the same whatever the number of threads, hence identical from one edition to another and from one machine to another.

19.6 Partitioned tables (Cluster edition)#

In the Cluster edition, a partitioned table carries one graph per partition (file <table>#p#<partition>.vmrj), maintained by the writes routed to the partition, including a row that an UPDATE moves from one partition to another. Partition operations (ADD, DROP, TRUNCATE, REORGANIZE, COALESCE, EXCHANGE PARTITION, PARTITION BY, REMOVE PARTITIONING) rebuild the graphs concerned; EXCHANGE PARTITION requires both tables to have the same vector index (error 1736).

A search queries the graph of each partition kept by pruning, each returning its LIMIT + OFFSET best neighbours, then merges the results. EXPLAIN shows index and the partitions read. On a secondary node, the graphs are rebuilt identically to those of the primary.

19.7 CREATE INDEX … USING hnsw syntax#

For applications that create their indexes with operator classes, MIRAJ also accepts:

CREATE INDEX [IF NOT EXISTS] [nom] ON table USING hnsw (colonne classe)
  [WITH (m = 16, ef_construction = 64)];

It is a plain synonym of CREATE VECTOR INDEX; SHOW CREATE TABLE returns the VECTOR KEY form.

CREATE INDEX idx_doc ON document USING hnsw (plongement vector_cosine_ops) WITH (m = 16);
SELECT id FROM document ORDER BY plongement <=> '[0.12, -0.03, ...]' LIMIT 10;
-- SHOW CREATE TABLE : VECTOR KEY `idx_doc` (`plongement`) `distance`=cosine `m`=16

• Without a name, the index takes that of the column.
• m follows the rules of the M option (3 to 200, 1912 otherwise); ef_construction is accepted with no effect (the build list is set by M: max(100, 2M)); any other option is rejected (1911).
• Another class (vector_l1_ops, halfvec_…, bit_…) or another method (USING ivfflat) is rejected (1235). So is CREATE UNIQUE INDEX … USING hnsw.
• The rules of the main syntax apply: NOT NULL column (1252), a single vector index per table (1235).
• USING hnsw is accepted only in this form; in CREATE TABLE … VECTOR INDEX (v) USING hnsw, it is rejected (1064).

CREATE INDEX … ON table USING btree (colonne) or USING hash creates an ordinary index, like CREATE INDEX nom USING btree ON table (colonne).

19.8 See also#

• 4. Data Types: the VECTOR(n) type.
• 8.11 Vector functions: distances and conversions.
• 16. Known limitations.