Vector-Similarity-Search-Erweiterung
Die Erweiterung vss ist eine experimentelle DuckDB-Erweiterung. Sie fügt Indexunterstützung hinzu, um Abfragen zur Vektorähnlichkeitssuche über DuckDBs neuen festgroßen Typ ARRAY zu beschleunigen.
Siehe den Ankündigungs-Blogbeitrag und den Beitrag „What’s New in the Vector Similarity Search Extension?“.
Verwendung
Um einen neuen HNSW-Index (Hierarchical Navigable Small Worlds) auf einer Tabelle mit einer ARRAY-Spalte anzulegen, verwenden Sie die Anweisung CREATE INDEX mit der Klausel USING HNSW. Zum Beispiel:
INSTALL vss;LOAD vss;
CREATE TABLE my_vector_table (vec FLOAT[3]);INSERT INTO my_vector_table SELECT array_value(a, b, c) FROM range(1, 10) ra(a), range(1, 10) rb(b), range(1, 10) rc(c);CREATE INDEX my_hnsw_index ON my_vector_table USING HNSW (vec);Der Index wird dann genutzt, um Abfragen zu beschleunigen, die eine ORDER BY-Klausel mit einer der unterstützten Distanzmetrik-Funktionen gegen die indizierten Spalten und einen konstanten Vektor auswerten, gefolgt von einer LIMIT-Klausel. Zum Beispiel:
SELECT *FROM my_vector_tableORDER BY array_distance(vec, [1, 2, 3]::FLOAT[3])LIMIT 3;Zusätzlich kann die überladene Funktion min_by(col, arg, n) ebenfalls mit dem HNSW-Index beschleunigt werden, wenn das Argument arg eine passende Distanzmetrik-Funktion ist. Damit lassen sich schnelle einmalige Nearest-Neighbor-Suchen ausführen. Zum Beispiel die 3 Zeilen mit den nächsten Vektoren zu [1, 2, 3]:
SELECT min_by(my_vector_table, array_distance(vec, [1, 2, 3]::FLOAT[3]), 3 ORDER BY vec) AS resultFROM my_vector_table;[{'vec': [1.0, 2.0, 3.0]}, {'vec': [2.0, 2.0, 3.0]}, {'vec': [1.0, 2.0, 4.0]}]Beachten Sie, dass wir den Tabellennamen als erstes Argument an min_by übergeben, um ein Struct mit der gesamten passenden Zeile zurückzugeben.
Ob der Index verwendet wird, prüfen Sie anhand der EXPLAIN-Ausgabe: Suchen Sie im Plan nach dem Knoten HNSW_INDEX_SCAN:
EXPLAINSELECT *FROM my_vector_tableORDER BY array_distance(vec, [1, 2, 3]::FLOAT[3])LIMIT 3;┌───────────────────────────┐│ PROJECTION ││ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ││ #0 │└─────────────┬─────────────┘┌─────────────┴─────────────┐│ PROJECTION ││ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ││ vec ││array_distance(vec, [1.0, 2││ .0, 3.0]) │└─────────────┬─────────────┘┌─────────────┴─────────────┐│ HNSW_INDEX_SCAN ││ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ││ t1 (HNSW INDEX SCAN : ││ my_idx) ││ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ││ vec ││ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ─ ││ EC: 3 │└───────────────────────────┘Standardmäßig wird der HNSW-Index mit der euklidischen Distanzmetrik l2sq (quadrierte L2-Norm) erzeugt, passend zu DuckDBs Funktion array_distance. Andere Distanzmetriken setzen Sie über die Option metric bei der Indexerzeugung. Zum Beispiel:
CREATE INDEX my_hnsw_cosine_indexON my_vector_tableUSING HNSW (vec)WITH (metric = 'cosine');Die folgende Tabelle zeigt die unterstützten Distanzmetriken und die zugehörigen DuckDB-Funktionen
| Metrik | Funktion | Beschreibung |
|---|---|---|
l2sq |
array_distance |
Euklidische Distanz |
cosine |
array_cosine_distance |
Kosinus-Ähnlichkeitsdistanz |
ip |
array_negative_inner_product |
Negatives Inneres Produkt |
Beachten Sie: Jeder HNSW-Index gilt nur für eine einzelne Spalte, Sie können aber mehrere HNSW-Indizes auf derselben Tabelle anlegen, die jeweils eine andere Spalte indizieren. Außerdem können Sie mehrere HNSW-Indizes auf derselben Spalte anlegen, jeweils mit einer anderen Distanzmetrik.
Index-Optionen
Neben der Option metric unterstützt die HNSW-Indexerzeugung die folgenden Optionen zur Steuerung der Hyperparameter von Aufbau und Suche:
| Option | Standard | Beschreibung |
|---|---|---|
ef_construction |
128 | Die Anzahl der Kandidaten-Knoten, die beim Aufbau des Indexes berücksichtigt werden. Ein höherer Wert ergibt einen genaueren Index, erhöht aber die Aufbauzeit. |
ef_search |
64 | Die Anzahl der Kandidaten-Knoten, die in der Suchphase berücksichtigt werden. Ein höherer Wert ergibt einen genaueren Index, erhöht aber die Suchzeit. |
M |
16 | Die maximale Anzahl Nachbarn, die für jeden Knoten im Graphen gehalten werden. Ein höherer Wert ergibt einen genaueren Index, erhöht aber die Aufbauzeit. |
M0 |
2 * M |
Die Basis-Konnektivität, also die Anzahl Nachbarn, die für jeden Knoten auf Ebene 0 des Graphen gehalten werden. Ein höherer Wert ergibt einen genaueren Index, erhöht aber die Aufbauzeit. |
Zusätzlich können Sie den zur Indexerzeugung gesetzten Parameter ef_search zur Laufzeit mit der Konfigurationsoption SET hnsw_ef_search = ⟨int⟩{:.language-sql .highlight} überschreiben. Das ist nützlich, wenn Sie pro Verbindung Suchleistung gegen Genauigkeit tauschen möchten oder umgekehrt. Die Überschreibung heben Sie mit RESET hnsw_ef_search{:.language-sql .highlight} auf.
Persistenz
Wegen bekannter Probleme bei der Persistenz von Indizes aus Erweiterungen kann der HNSW-Index standardmäßig nur auf Tabellen in In-Memory-Datenbanken angelegt werden, sofern nicht die Konfigurationsoption SET hnsw_enable_experimental_persistence = ⟨bool⟩{:.language-sql .highlight} auf true gesetzt ist.
Diese Funktion steckt hinter einem experimentellen Flag, weil die „WAL“-Wiederherstellung für benutzerdefinierte Indizes noch nicht korrekt implementiert ist. Stürzt DuckDB ab oder wird die Datenbank unerwartet beendet, während es uncommittete Änderungen an einer HNSW-indizierten Tabelle gibt, kann das zu Datenverlust oder einer Beschädigung des Indexes führen.
Wenn Sie diese Option aktivieren und es zu einem unerwarteten Shutdown kommt, können Sie versuchen, den Index wiederherzustellen: Starten Sie DuckDB zunächst getrennt, laden Sie die Erweiterung vss und führen Sie dann ATTACH auf der Datenbankdatei aus. So steht die HNSW-Indexfunktionalität während der WAL-Wiedergabe bereit, und DuckDBs Wiederherstellung kann ohne Probleme weiterlaufen. Wir empfehlen dennoch, diese Funktion nicht in Produktionsumgebungen zu nutzen.
Mit aktivierter Option hnsw_enable_experimental_persistence wird der Index in die DuckDB-Datenbankdatei persistiert (wenn Sie DuckDB mit einer dateibasierten Datenbank betreiben). Nach einem Neustart kann der Index vom Datenträger wieder in den Speicher geladen werden, statt neu erzeugt zu werden. Dabei gibt es keine inkrementellen Updates des persistenten Indexspeichers: Bei jedem Checkpoint serialisiert DuckDB den gesamten Index auf den Datenträger und überschreibt sich selbst. Ebenso wird der Index nach einem Neustart vollständig wieder in den Hauptspeicher deserialisiert. Das geschieht allerdings erst, wenn Sie zum ersten Mal auf die zugehörige Tabelle zugreifen. Je nach Größe des Indexes kann die Deserialisierung etwas dauern, sollte aber immer noch schneller sein, als den Index zu löschen und neu anzulegen.
Einfügen, Aktualisieren, Löschen und Rekompaktierung
Der HNSW-Index unterstützt das Einfügen, Aktualisieren und Löschen von Zeilen nach der Indexerzeugung. Zwei Punkte sind zu beachten:
- Es ist schneller, den Index anzulegen, nachdem die Tabelle bereits mit Daten gefüllt ist, weil der initiale Bulk-Load auf großen Tabellen Parallelität besser nutzen kann.
- Löschungen werden nicht sofort im Index sichtbar, sondern nur als gelöscht „markiert“. Der Index kann dadurch mit der Zeit veralten und Abfragequalität sowie Leistung beeinträchtigen.
Für den letzten Punkt rufen Sie die Pragma-Funktion PRAGMA hnsw_compact_index('⟨index_name⟩'){:.language-sql .highlight} auf, um eine Rekompaktierung auszulösen und gelöschte Einträge zu entfernen, oder legen Sie den Index nach einer größeren Zahl von Updates neu an.
Bonus: Joins für die Vektorsuche
Die Erweiterung vss stellt außerdem einige Tabellenmakros bereit, die das Abgleichen mehrerer Vektoren gegeneinander vereinfachen – sogenannte „Fuzzy Joins“. Das sind:
vss_join(left_table, right_table, left_col, right_col, k, metric := 'l2sq')vss_match(right_table", left_col, right_col, k, metric := 'l2sq')
Diese nutzen den HNSW-Index derzeit nicht, sondern sind Komfortfunktionen für Nutzer, die mit einer Brute-Force-Vektorsuche leben können, ohne die Join-Logik selbst zu schreiben. Künftig könnten sie ebenfalls Ziele für indexbasierte Optimierungen werden.
Die Funktionen lassen sich wie folgt verwenden:
CREATE TABLE haystack (id int, vec FLOAT[3]);CREATE TABLE needle (search_vec FLOAT[3]);
INSERT INTO haystack SELECT row_number() OVER (), array_value(a, b, c) FROM range(1, 10) ra(a), range(1, 10) rb(b), range(1, 10) rc(c);
INSERT INTO needle VALUES ([5, 5, 5]), ([1, 1, 1]);
SELECT *FROM vss_join(needle, haystack, search_vec, vec, 3) res;┌───────┬─────────────────────────────────┬─────────────────────────────────────┐│ score │ left_tbl │ right_tbl ││ float │ struct(search_vec float[3]) │ struct(id integer, vec float[3]) │├───────┼─────────────────────────────────┼─────────────────────────────────────┤│ 0.0 │ {'search_vec': [5.0, 5.0, 5.0]} │ {'id': 365, 'vec': [5.0, 5.0, 5.0]} ││ 1.0 │ {'search_vec': [5.0, 5.0, 5.0]} │ {'id': 364, 'vec': [5.0, 4.0, 5.0]} ││ 1.0 │ {'search_vec': [5.0, 5.0, 5.0]} │ {'id': 356, 'vec': [4.0, 5.0, 5.0]} ││ 0.0 │ {'search_vec': [1.0, 1.0, 1.0]} │ {'id': 1, 'vec': [1.0, 1.0, 1.0]} ││ 1.0 │ {'search_vec': [1.0, 1.0, 1.0]} │ {'id': 10, 'vec': [2.0, 1.0, 1.0]} ││ 1.0 │ {'search_vec': [1.0, 1.0, 1.0]} │ {'id': 2, 'vec': [1.0, 2.0, 1.0]} │└───────┴─────────────────────────────────┴─────────────────────────────────────┘Alternativ nutzen wir das Makro vss_match als „Lateral Join“, um die Treffer bereits nach der linken Tabelle gruppiert zu erhalten.
Dazu müssen wir zuerst die linke Tabelle angeben und dann das Makro vss_match, das die Suchspalte der linken Tabelle referenziert
(in diesem Fall search_vec):
SELECT *FROM needle, vss_match(haystack, search_vec, vec, 3) res;┌─────────────────┬──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┐│ search_vec │ matches ││ float[3] │ struct(score float, "row" struct(id integer, vec float[3]))[] │├─────────────────┼──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┤│ [5.0, 5.0, 5.0] │ [{'score': 0.0, 'row': {'id': 365, 'vec': [5.0, 5.0, 5.0]}}, {'score': 1.0, 'row': {'id': 364, 'vec': [5.0, 4.0, 5.0]}}, {'score': 1.0, 'row': {'id': 356, 'vec': [4.0, 5.0, 5.0]}}] ││ [1.0, 1.0, 1.0] │ [{'score': 0.0, 'row': {'id': 1, 'vec': [1.0, 1.0, 1.0]}}, {'score': 1.0, 'row': {'id': 10, 'vec': [2.0, 1.0, 1.0]}}, {'score': 1.0, 'row': {'id': 2, 'vec': [1.0, 2.0, 1.0]}}] │└─────────────────┴──────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────────┘Einschränkungen
- Derzeit werden nur Vektoren aus
FLOAT-Werten (32 Bit, einfache Genauigkeit) unterstützt. - Der Index selbst wird nicht pufferverwaltet und muss vollständig in den RAM passen.
- Die Größe des Indexes im Speicher zählt nicht zum DuckDB-Konfigurationsparameter
memory_limit. HNSW-Indizes können nur auf Tabellen in In-Memory-Datenbanken angelegt werden, sofern nicht die KonfigurationsoptionSET hnsw_enable_experimental_persistence = ⟨bool⟩{:.language-sql .highlight} auftruegesetzt ist; siehe Persistenz.- Die Tabellenmakros für Vektor-Joins (
vss_joinundvss_match) benötigen denHNSW-Index nicht und nutzen ihn auch nicht.