MHNSW: after repeated DELETE/INSERT cycles, ORDER BY VEC_DISTANCE LIMIT N returns fewer rows than the table holds, down to none

Hi,

It took us a while to isolate the vector index issue below. It would be great if you could take a look.

Thanks in advance
Dierk Droth
CEO Unusual Software GmbH

Affects version: 12.3.3 (latest 12.3 release; 13.x not tested)
Environment: Ubuntu 24.04, 12.3.3-MariaDB-ubu2404 from the MariaDB repository, InnoDB, default MHNSW settings (mhnsw_ef_search=20, mhnsw_default_m=6, mhnsw_max_cache_size=16777216), REPEATABLE-READ, autocommit.

Description

A table with a vector index goes through many cycles of "delete every row, insert a few new ones". After some hundreds of cycles, a nearest-neighbour query whose LIMIT is larger than the table returns fewer rows than the table holds, sometimes no row at all. The same query with IGNORE INDEX returns every row.

This is not a recall question: the table holds 6 rows and the query asks for 64, so the result must contain all 6 whatever their order. MDEV-35246 was the same class of wrong result (fewer rows than available) and was fixed in 11.7.1; that case needed identical vectors. Here every vector is distinct.

Single session, autocommit, no explicit transactions, no foreign keys, no concurrent load. The attached script is self-contained: it generates every vector in SQL from Gaussian clusters (20 random centres in 1024 dimensions, each row its centre plus N(0, 0.5) noise per component), so no two vectors are identical and no data file is needed.

How to repeat

mariadb --table < mdev-vector-repro.sql

It creates and uses its own database mdev_vector_repro. Per run:

CREATE TABLE t (id BIGINT PRIMARY KEY, v VECTOR(1024) NOT NULL, VECTOR INDEX vi (v) DISTANCE=cosine M=8) ENGINE=InnoDB;

-- repeated 1500 times:

DELETE FROM t WHERE id > 0;

INSERT INTO t VALUES (<new id>, <new vector>);   -- 5 times

-- every 25 cycles one more row close to the query vector, then:

SELECT COUNT(*) FROM t;                                                                   -- 6

SELECT COUNT(*) FROM (SELECT id FROM t ORDER BY VEC_DISTANCE_COSINE(v, <q>) LIMIT 64) k;   -- expected 6

SELECT COUNT(*) FROM (SELECT id FROM t IGNORE INDEX (vi)

                      ORDER BY VEC_DISTANCE_COSINE(v, <q>) LIMIT 64) k;                    -- 6

EXPLAIN shows the index in use (type=index, key=vi).

Expected

Every check returns 6 rows through the index, as it does with IGNORE INDEX.

Actual

60 checks per run, 6 rows in the table at each:

What brings the rows back, on A's table as the cycles left it (5 rows):

So it is not the shared cache (FLUSH TABLES changes nothing), and OPTIMIZE TABLE reports success without repairing it, as noted in MDEV-41227.

The counts above go through SELECT COUNT FROM (... LIMIT 64) k. The attached confirm-direct.sql rules the wrapper out: a fresh cosine M=8 table through 600 cycles, then the plain query SELECT id FROM t ORDER BY VEC_DISTANCE_COSINE(v, <q>) LIMIT 64 with 20 different query vectors, rows counted with FOUND_ROWS(). Table: 5 rows. Plain query: 18 × 5 rows, once 4, once 0. With IGNORE INDEX: 5 rows all 20 times.

The index keeps growing while the table stays at 6 rows (deleted nodes stay in the graph, MDEV-37010), and the short results begin as it grows.

Related

• MDEV-41227 — rows unreachable through a cosine index after ON DELETE CASCADE; there euclidean and a single plain DELETE were fine. Here the DELETE is plain and repeated, and euclidean fails as well. Possibly the same defect underneath, reached without a cascade.
• MDEV-41321 — stale REPEATABLE READ reader poisoning the shared cache. Not this: one session, no open transaction, and FLUSH TABLES does not help.
• MDEV-37010 — deleted rows stay in the graph.
• MDEV-35246 — fewer rows than available, with identical vectors; fixed in 11.7.1.

How we found it

In production use: a document search in an application whose test account deletes all of its data before each GUI test. The table held one row; ORDER BY VEC_DISTANCE_COSINE(...) LIMIT 64 returned none, with and without a WHERE, while a scan found the row at cosine distance 0.154 and a search from the row's own vector found it. Index size 52 MB for that one row.