19. Recherche vectorielle : VECTOR INDEX

Une colonne VECTOR(n) (chapitre 4) range des plongements (embeddings) produits par un modèle de langue ou d'image. Chercher les k lignes les plus proches d'un vecteur donné s'écrit ORDER BY distance LIMIT k :

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

Sans index, MIRAJ calcule la distance de chaque ligne et garde les k meilleures : le résultat est exact, mais le coût croît avec la table (environ 90 ms pour 100 000 vecteurs de 128 dimensions). Un index vectoriel ramène cette recherche à une fraction de milliseconde, au prix d'un résultat approché : quelques voisins peuvent manquer, remplacés par des lignes presque aussi proches.

19.1 Créer un index vectoriel#

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 est synonyme de VECTOR INDEX. Sans nom, l'index prend celui de sa colonne.

Règles :

• une seule colonne, de type VECTOR(n) et déclarée NOT NULL (erreur 1252 si elle peut être NULL, 1210 pour un autre type) ; ni préfixe v(2), ni DESC, ni UNIQUE (1064) ;
• un seul index vectoriel par table (1235 pour un second) ;
• un KEY, UNIQUE ou PRIMARY KEY ordinaire sur une colonne VECTOR reste refusé (6133).

Options :

Une option inconnue est refusée (1911). Une option écrite deux fois garde sa dernière valeur. Les options sont restituées telles qu'écrites par SHOW CREATE TABLE :

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

Sans option M ou DISTANCE, l'index prend les valeurs de la session ; si elles diffèrent des valeurs par défaut, elles sont figées dans la définition (`m`=10 `distance`='cosine') : la table se recrée à l'identique quelle que soit la session qui relit le script.

dot (produit scalaire) est une extension de MIRAJ : les plus proches voisins sont ceux de plus grand produit scalaire. Elle convient aux modèles dont les vecteurs ne sont pas normés et dont la similarité est le produit scalaire ; pour des vecteurs normés, elle équivaut à cosine.

SHOW INDEX et information_schema.STATISTICS montrent l'index avec Index_type = VECTOR, Non_unique = 1 et Cardinality NULL ; DESCRIBE marque la colonne MUL.

L'index suit sa colonne dans les ALTER TABLE : MODIFY v VECTOR(4) NOT NULL le garde (le graphe est reconstruit), DROP COLUMN v le retire, MODIFY v VECTOR(4) sans NOT NULL est refusé (1252). TRUNCATE TABLE le vide, CREATE TABLE … LIKE le recopie.

19.2 Requêtes servies par l'index#

L'index sert une requête de la forme :

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

où :

• distance est une fonction ou un opérateur de la métrique de l'index :

• l'un des arguments est la colonne indexée, l'autre un vecteur connu avant l'exécution : un littéral (VEC_FromText('[…]'), '[1,2,3]', x'…'), un paramètre ? d'une requête préparée ou une variable @q, de la dimension de la colonne ; les deux arguments peuvent être inversés ;
• la clé de tri peut être un alias du SELECT : SELECT id, VEC_DISTANCE(v, @q) AS d FROM t ORDER BY d LIMIT 5.

VEC_DISTANCE(a, b) n'a pas de métrique propre : il prend celle de l'index de la colonne qu'il reçoit, y compris hors ORDER BY ; sans index vectoriel sur l'un de ses arguments, il est refusé (erreur 4206). Utilisez alors VEC_DISTANCE_EUCLIDEAN ou VEC_DISTANCE_COSINE.

L'index n'est pas utilisé (calcul exact par balayage) pour :

• un tri DESC, une requête sans LIMIT, une clé de tri composée (ORDER BY d, id) ou une expression de la distance (ORDER BY 1 + d) ;
• une distance d'une autre métrique que celle de l'index, ou DISTANCE(v, q, 'dot') (qui rend le produit scalaire lui-même, croissant : les plus éloignés d'abord) ;
• une distance entre deux colonnes (VEC_DISTANCE(v, v)), un vecteur d'une autre dimension ;
• une jointure, un GROUP BY ou une agrégation, DISTINCT, une union, SELECT … FOR UPDATE ;
• UPDATE … ORDER BY … LIMIT et DELETE … ORDER BY … LIMIT.

Filtres WHERE#

Un WHERE s'applique aux voisins trouvés. S'il en écarte trop, MIRAJ relance la recherche avec quatre fois plus de voisins, puis, en dernier recours, lit le reste de la table : la requête rend toujours LIMIT lignes quand la table en contient assez. Un filtre très sélectif (quelques lignes sur des millions) est donc correct mais peut coûter un balayage ; un index ordinaire sur la colonne filtrée est alors plus efficace (WHERE id = 1 passe par la clé primaire).

EXPLAIN#

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

Une lecture par l'index affiche type = index, key = nom de l'index et rows = LIMIT + OFFSET, sans Using filesort. Un k-NN exact affiche type = ALL et Using filesort.

19.3 Approximation et mhnsw_ef_search#

L'index est un graphe HNSW (Hierarchical Navigable Small World) : la recherche part d'un point d'entrée et suit les liens vers des nœuds de plus en plus proches, en gardant une liste des meilleurs candidats. La longueur de cette liste, @@mhnsw_ef_search, règle le compromis :

La liste compte toujours au moins LIMIT + OFFSET candidats. Mesure indicative (100 000 vecteurs de 128 dimensions, M = 16) : 0,4 à 1,1 ms par requête selon ef_search, contre 90 ms pour le calcul exact.

SET mhnsw_ef_search = 64;                                   -- pour la session
SET STATEMENT mhnsw_ef_search = 200 FOR SELECT …;           -- pour une requête

Avec la métrique dot, le graphe se parcourt moins bien (un vecteur n'est pas forcément son propre plus proche voisin) : prévoyez un ef_search de 64 à 100.

Les transactions sont respectées : une ligne insérée ou modifiée par une transaction non validée n'est vue que par elle ; l'index ne rend que des lignes visibles, et la distance affichée est recalculée sur la valeur visible.

19.4 Variables#

19.5 Stockage, mémoire et construction#

Le graphe vit en mémoire, à côté de la table : environ 4 × (2M + 3) octets par ligne, hors vecteurs (qui ne sont pas recopiés : l'index lit la colonne). Pour 1 million de lignes et M = 16, compter environ 150 Mo.

Il est enregistré dans un fichier <table>.vmrj à côté du .mrj, réécrit seulement quand il a changé. Au chargement, le graphe est confronté aux lignes de la table (empreinte de chaque vecteur) puis accordé aux écritures rejouées depuis le journal. S'il est absent, abîmé ou trop en retard, il est reconstruit : ce n'est jamais une erreur, seulement un chargement plus long. CHECK TABLE contrôle le graphe. Une sauvegarde physique (chapitre 18) ne copie pas le .vmrj : le graphe est reconstruit au premier chargement de la base restaurée.

Chaque écriture (INSERT, UPDATE de la colonne, DELETE, annulation) entretient le graphe. Une construction complète (CREATE VECTOR INDEX sur une table remplie, ALTER TABLE qui reconstruit la table, reprise au chargement) procède par lots :

• édition Entreprise : les lots sont traités en parallèle sur les fils du serveur (--parallel-threads) ; 100 000 vecteurs de 128 dimensions, M = 16 : environ 10 s sur 12 fils logiques, contre 49 s en série ;
• édition Express : même algorithme sur un seul fil.

Le graphe obtenu est le même quel que soit le nombre de fils, donc identique d'une édition à l'autre et d'une machine à l'autre.

19.6 Tables partitionnées (édition Cluster)#

Dans l'édition Cluster, une table partitionnée porte un graphe par partition (fichier <table>#p#<partition>.vmrj), entretenu par les écritures routées vers la partition, y compris une ligne qu'un UPDATE déplace d'une partition à l'autre. Les opérations sur les partitions (ADD, DROP, TRUNCATE, REORGANIZE, COALESCE, EXCHANGE PARTITION, PARTITION BY, REMOVE PARTITIONING) reconstruisent les graphes concernés ; EXCHANGE PARTITION exige que les deux tables aient le même index vectoriel (erreur 1736).

Une recherche interroge le graphe de chaque partition retenue par l'élagage, chacune fournissant ses LIMIT + OFFSET meilleurs voisins, puis fusionne les résultats. EXPLAIN affiche index et les partitions lues. Sur un nœud secondaire, les graphes sont reconstruits à l'identique de ceux du primaire.

19.7 Syntaxe CREATE INDEX … USING hnsw#

Pour les applications qui créent leurs index avec des classes d'opérateurs, MIRAJ accepte aussi :

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

C'est un simple synonyme de CREATE VECTOR INDEX ; SHOW CREATE TABLE restitue la forme VECTOR KEY.

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

• Sans nom, l'index prend celui de la colonne.
• m suit les règles de l'option M (3 à 200, 1912 sinon) ; ef_construction est accepté sans effet (la liste de construction est fixée par M : max(100, 2M)) ; une autre option est refusée (1911).
• Une autre classe (vector_l1_ops, halfvec_…, bit_…) ou une autre méthode (USING ivfflat) est refusée (1235). CREATE UNIQUE INDEX … USING hnsw également.
• Les règles de la syntaxe principale s'appliquent : colonne NOT NULL (1252), un seul index vectoriel par table (1235).
• USING hnsw n'est accepté que dans cette forme ; dans CREATE TABLE … VECTOR INDEX (v) USING hnsw, il est refusé (1064).

CREATE INDEX … ON table USING btree (colonne) ou USING hash crée un index ordinaire, comme CREATE INDEX nom USING btree ON table (colonne).

19.8 Voir aussi#

• 4. Types de données : le type VECTOR(n).
• 8.11 Fonctions vectorielles : distances et conversions.
• 16. Limites connues.