Inhaltsverzeichnis
Oracle Datenbank 23ai - Vectoren indizieren – HNSW – Der "Hierarchical Navigable Small World" Index im Detail
Fragestellung:
- Was ist das für ein Index Typ?
- Unterschied zum IVF Index Typ?
- Wie in der Oracle Datenbank einsetzten?
- Was muss beim Anlegen und der Wartung des Index beachtet werden?
- Platzbedarf und Transaktionsverhalten?
Mehr über Vectoren:
Über den Datentyp Vector und den Aufbau einer Testumgebung zu dem Thema siehe ⇒ Oracle Datenbank 23ai - Vector Search - Einen Vector speichern, vergleichen und indizieren und Oracle Datenbank 23ai - Mit Vectoren in der Oracle Datenbank Daten vergleichen - Demo Applikation für die Suche nach Farben
Und über den IVF Index Typ ⇒ Oracle Datenbank 23ai - Vectoren indizieren – IVF - "Inverted File Flat Vector Index" – Index im Detail
Prinzip – Der Hierarchical Navigable Small World Indexes - HNSW
Der Navigable Small World (NSW)-Algorithmus konstruiert einen durchsuchbaren Nachbarschaftsgraphen (Proximity Graph), bei dem jeder Vektor basierend auf drei Schlüsselparametern mit anderen verbunden wird:
- Abstand: Verbindungen werden zwischen Vektoren mit der geringsten Distanz ( euklidischen oder Kosinus basiert) priorisiert.
- Gradbegrenzung - Anzahl der Nachbarn: Die maximale Anzahl direkter Verbindungen pro Vektor.(Verhindert übermäßige Vernetzung und hält den Graphen durchsuchbar.)
- Anzahl der Kandidaten, die in jedem Suchschritt evaluiert werden: Höhere Werte verbessern die Graph Qualität, erhöhen aber den Berechnungsaufwand.
Im HNSW Index werden zwei Konzepte kombiniert:
- Navigable Small Worlds
- Graph von verknüpften Vectoren, Verknüpft nach Ähnlichkeit
- Skip Linked List
- Datenstruktur nach Ebenen
- Auf jeder Ebenen sind die Elemente „näher“ verknüpft, Zwischenwerte entfallen auf den oberen Ebenen
- Auf der untersten Ebene sind alle Elemente enthalten
Vergleich Fulltable Scan zu IVF und HNSW
IFV - Inverted File Flat Vector Index ist ein Index basierend auf Clustern von ähnlichen Vectoren.
Exakte Suche = Full Table Scan
Die exakte Suche vergleicht den Abfragevektor mit jedem Vektor in der Tabelle. Darauf folgt eine Zeitkomplexität von O(n * d) mit n =Anzahl der Datensätze und d = Anzahl der Dimensionen.
HNSW
HNSW hat eine Zeitkomplexität von O(log(n)). D.h. die Anzahl der Datensätze n hat den meisten Einfluss auf das Suchverhalten.
IVF
IVF hat eine Zeitkomplexität von O(((n / k) + k) * d) mit k = Anzahl der Cluster, n =Anzahl der Datensätze und d = Anzahl der Dimensionen.
Vergleich
HNSW bietet im Vergleich zu IVF eine bessere Abfrageleistung allerdings dauert die Erstellung des HNSW-Indexes länger als die Erstellung eines IVF-Indexes.
| Eigenschaft | Full TableScan | HNSW | IVF |
|---|---|---|---|
| Anforderung | Hohe Genauigkeit + Echtzeit | Große Datensätze + begrenzter RAM | |
| Genauigkeit | Exakt | Hohe Wahrscheinlichkeit | Je nach Clusterung Wahrscheinlich |
| Performance | Langsam | performant O(log(n)) | performanter O(((n / k) + k) * d) |
| Platzbedarf | n/a | Mehr Platz für die Navigationsstruktur wird benötigt | Kompakter |
HNSW erreicht höhere Genauigkeit durch dynamische Nachbarschaftssuche in hierarchischen Graphen. IVF leidet unter Cluster-Drift (ungenau, wenn Vektoren nahe Cluster-Grenzen liegen).
Vorbereitung - Datenbank Pool bereitstellen
Für das Verarbeiten der Vectoren wird in der SGA der Datenbank Instance ein neuer Pool Bereich definiert.
siehe auch https://docs.oracle.com/en/database/oracle/oracle-database/23/vecse/size-vector-pool.html
Der benötigt für komplexere Indexe dann auch eine gewisse Größe, nach dem Motto „Nicht zu groß und nicht zu klein, gerade richtig muss es sein“ …. .
Sind große Updates auf den Vector Spalten notwendig erkennt die Datenbank das und legt einen neuen Index im Speicher parallel zum bestehenden Index an.
Daraus folgt dann aber auch ein doppelter Platzbedarf + x an neuen Daten, d.h. der Pool sollte immer auch noch etwas freien Platz enthalten.
Was ist eingestellt:
sqlplus / AS sysdba SHOW parameter vector_memory_size NAME TYPE VALUE ------------------ ----------- ----- vector_memory_size big INTEGER 0 -- mit sqlplus im Container in der CDB anmelden und Parameter ändern podman EXEC -it freeDB bash bash-4.4$ su - oracle export ORACLE_HOME=/opt/oracle/product/23ai/dbhomeFree export ORACLE_SID=FREE export PATH=$ORACLE_HOME/bin:$PATH sqlplus / AS sysdba ALTER system SET vector_memory_size=512M scope=spfile; shutdown IMMEDIATE startup
Der Pool ist notwendig da der Index eine InMemory Struktur ist (static memory-only structure) , die beim ersten Start der Instance in den Speicher geladen wird.
An der Stelle ist die Dokumentation etwas dünn.
Platzverbrauch überprüfen über V$VECTOR_MEMORY_POOL:
-- überprüfen über SELECT * FROM V$VECTOR_MEMORY_POOL;
Anmerkung: die „IVF centroid vectors“ werden alternativ im Shared pool gespeichert, falls der Platz im Vector Pool zu klein ist.
Testtabelle initialisieren
User in der Datenbank anlegen
User mit entsprechenden Rollen für die weitern Test-Cases anlegen als SYS im der PDB:
sqlplus sys@//10.10.10.118:1521/freepdb1 AS sysdba CREATE USER GPI IDENTIFIED BY MYSecretPWD DEFAULT TABLESPACE USERS TEMPORARY TABLESPACE TEMP; ALTER USER GPI QUOTA UNLIMITED ON USERS; -- normal Developer rights GRANT CONNECT TO GPI; GRANT DB_DEVELOPER_ROLE TO GPI; GRANT SELECT_CATALOG_ROLE TO GPI; -- AI Features GRANT CREATE MINING MODEL TO GPI; -- data Exchange for MODEL and Test Data GRANT READ ON DIRECTORY DATA_EXCHANGE TO GPI; GRANT WRITE ON DIRECTORY DATA_EXCHANGE TO GPI; -- Oracle Text Test Case GRANT CTXAPP TO GPI; -- Analyse Vector Indexex GRANT SELECT ON VECSYS.VECTOR$INDEX$BUILD$ TO GPI; GRANT SELECT ON VECSYS.VECTOR$INDEX TO GPI; GRANT SELECT ON V_$VECTOR_MEMORY_POOL TO GPI; ALTER USER GPI DEFAULT ROLE CONNECT, DB_DEVELOPER_ROLE, SELECT_CATALOG_ROLE, CTXAPP;
Testdaten erzeugen
CREATE TABLE elements ( id NUMBER GENERATED BY DEFAULT AS IDENTITY , elem_vector vector(5 , FLOAT32 , DENSE ) ); INSERT INTO elements (elem_vector) VALUES ('[1, 2, 3, 4, 5]'), ('[6, 7, 8, 9, 10]'), ('[11, 12, 13, 14, 15]'), ('[16, 17, 18, 19, 20]'); commit; INSERT INTO elements (elem_vector) SELECT VECTOR( '[' ||DBMS_RANDOM.VALUE(0, 20) ||',' ||DBMS_RANDOM.VALUE(0, 20) ||',' ||DBMS_RANDOM.VALUE(0, 20) ||',' ||DBMS_RANDOM.VALUE(0, 20) ||',' ||DBMS_RANDOM.VALUE(0, 20) || ']' ) FROM TABLE(CAST( MULTISET( SELECT LEVEL FROM DUAL CONNECT BY LEVEL <= 10000 ) AS SYS.ODCINUMBERLIST ) ); SELECT id,JSON_ARRAY(elem_vector returning varchar2) AS elem_vector FROM elements ORDER BY elem_vector;
Auf diesen Daten wird nun der Index angelegt.
Anlegen des Index
Platzbedarf:
#Aus der Doku: #Note:To roughly determine the memory size needed to store an HNSW index, use the following formula: 1.3 * number of #vectors * number of dimensions * size of your vector dimension type (for example, a FLOAT32 is equivalent to #BINARY_FLOAT and is 4 bytes in size).// 1.3*20000*5*4 = 520.000 Byte
Per Advisor als SYS Ermitteln:
SET SERVEROUTPUT ON; DECLARE v_result CLOB; BEGIN DBMS_VECTOR.INDEX_VECTOR_MEMORY_ADVISOR( TABLE_OWNER => 'GPI' , TABLE_NAME => 'ELEMENTS' , COLUMN_NAME => 'ELEM_VECTOR' , INDEX_TYPE => 'HNSW' , RESPONSE_JSON => v_result); END; / USING DEFAULT accuracy: 90% Suggested vector memory pool SIZE: 14.979.657 Bytes
Aus der Doku:
CREATE VECTOR INDEX vector_index_name ON TABLE_NAME (vector_column) [GLOBAL] ORGANIZATION INMEMORY [NEIGHBOR] GRAPH [WITH] [DISTANCE metric name] [WITH TARGET ACCURACY percentage_value] [PARAMETERS (TYPE HNSW , {NEIGHBORS max_closest_vectors_connected | M max_closest_vectors_connected} , EFCONSTRUCTION max_candidates_to_consider)] [PARALLEL degree_of_parallelism]
Werte:
- ACCURACY: > 0 and < = 100
- DISTANCE: EUCLIDEAN, L2_SQUARED (aka EUCLIDEAN_SQUARED), COSINE, DOT, MANHATTAN, HAMMING
- TYPE: HNSW
- NEIGHBORS: > 0 and ⇐ 2048
- EFCONSTRUCTION: > 0 and ⇐ 65535
- EFCONSTRUCTION represents the maximum number of closest vector candidates considered at each step of the search during insertion
Anlegen:
CREATE VECTOR INDEX vidx_elements_elem_vector ON elements (elem_vector) ORGANIZATION INMEMORY NEIGHBOR GRAPH DISTANCE COSINE WITH TARGET ACCURACY 90 PARAMETERS ( TYPE HNSW , neighbors 5 , efconstruction 10);
Was wurde erzeugt?
Speicherbedarf:
-- zuvor als sys ! -- GRANT SELECT ON V_$VECTOR_MEMORY_POOL TO GPI; -- über V$VECTOR_MEMORY_POOL kann geprüft werden wieviel Speicher am Ende wirklich allokiert wurden. SELECT SUM(USED_BYTES) FROM V$VECTOR_MEMORY_POOL; -- vor dem Anlegen abfragen und nun vergleichen .-) -- select 16646144-4128768 from dual; => 12.517.376 Byte wurden im Speicher nach der Anlage reserviert
Da es sich um einem Domain Index handelt werden auch Daten des Indexes in Tabellen abgelegt, vor allen die notwenigen Journale für das Transaktionsverhalten. Der eigentliche Index wird in Speicher abgelegt.
-- Was wurde angelegt: SELECT OBJECT_NAME,OBJECT_TYPE FROM user_objects WHERE object_name LIKE 'V%ELEM%'; OBJECT_NAME OBJECT_TYPE -------------------------------------------------------------------------------------------------------------------------------- ----------------------- VECTOR$VIDX_ELEMENTS_ELEM_VECTOR$79429_79433_0$HNSW_CHECKPOINTS TABLE VECTOR$VIDX_ELEMENTS_ELEM_VECTOR$79429_79433_0$HNSW_ROWID_VID_MAP TABLE VECTOR$VIDX_ELEMENTS_ELEM_VECTOR$79429_79433_0$HNSW_SHARED_JOURNAL_CHANGE_LOG TABLE VECTOR$VIDX_ELEMENTS_ELEM_VECTOR$79429_79433_0$HNSW_SHARED_JOURNAL_CHANGE_LOG TABLE PARTITION -- zuvor als sys ! -- GRANT SELECT ON VECSYS.VECTOR$INDEX$BUILD$ TO GPI; -- GRANT SELECT ON VECSYS.VECTOR$INDEX TO GPI; SET serveroutput ON BEGIN DBMS_VECTOR.GET_INDEX_STATUS ('GPI','VIDX_ELEMENTS_ELEM_VECTOR'); END; / Owner name: GPI INDEX name: VIDX_ELEMENTS_ELEM_VECTOR INDEX objn: 79433 Stage: HNSW INDEX Creation Completed
Aus der Doku: „rowid_vid_map“ stores the mapping between a row ID and vector ID. shared_journal_change_log stores the DML changes that are yet to be incorporated into an HNSW graph
Tabelle abfragen
ORA-22848: cannot use VECTOR type as comparison key
Im ersten Schritt wollen wir genau einen Vector wiederfinden und suchen mit „=“ exakt.
-- wir suchen nach [6, 7, 8, 9, 10] -- SELECT * FROM elements WHERE ELEM_VECTOR = :SEARCH_VECTOR; ORA-22848: cannot USE VECTOR TYPE AS comparison KEY
So geht das aber nicht, eine Vergleich mit „=“ wird nicht unterstützt.
Vector über Funktion suchen
Mit der Cosinus Ähnlichkeit können wir prüfen, ob ein Vector in die gleiche Richtung wie ein anderer Vector zeigt. Zeig der Vector in die gleiche Richtung, ist die Distance = 0;
Wird nun aber auch der Index verwendet?
Test:
-- SEARCH_VECTOR -- [6, 7, 8, 9, 10] EXPLAIN PLAN FOR SELECT id , ELEM_VECTOR FROM elements WHERE vector_distance(ELEM_VECTOR, :SEARCH_VECTOR, COSINE ) = 0; SELECT * FROM TABLE(DBMS_XPLAN.DISPLAY); ------------------------------------------------------------------------------ | Id | Operation | Name | ROWS | Bytes | Cost (%CPU)| TIME | ------------------------------------------------------------------------------ | 0 | SELECT STATEMENT | | 232 | 932K| 107 (1)| 00:00:01 | |* 1 | TABLE ACCESS FULL| ELEMENTS | 232 | 932K| 107 (1)| 00:00:01 | ------------------------------------------------------------------------------ Predicate Information (IDENTIFIED BY operation id): --------------------------------------------------- 1 - FILTER(VECTOR_DISTANCE("ELEM_VECTOR" /*+ LOB_BY_VALUE */ /*+ LOB_INLINE */ , VECTOR(:SEARCH_VECTOR, *, *, * /*+ USEBLOBPCW_QVCGMD */ ), COSINE)=0D)
Ergebnis ist ein Fulltable Scan der Index wird NICHT verwendet! (obwohl der Index COSINUS auch als Ähnlichkeitsmaßstab verwendet!)
Index Verwendung
Der Index wird verwendet, wenn die Vector Ähnlichkeitsfunktion in der Order By Klausel mit dem gleichen Ähnlichkeitsvergleich wie beim Anlegen des Indexes eingesetzt wird.
EXPLAIN PLAN FOR SELECT ID , vector_distance(ELEM_VECTOR, :SEARCH_VECTOR, COSINE ) AS v_COSINE_DISTANCE FROM ELEMENTS ORDER BY vector_distance(ELEM_VECTOR, :SEARCH_VECTOR, COSINE ) FETCH APPROX FIRST 3 ROWS ONLY; SELECT * FROM TABLE(DBMS_XPLAN.DISPLAY); -------------------------------------------------------------------------------------------------------------------- | Id | Operation | Name | ROWS | Bytes |TempSpc| Cost (%CPU)| TIME | -------------------------------------------------------------------------------------------------------------------- | 0 | SELECT STATEMENT | | 3 | 57 | | 19861 (1)| 00:00:01 | |* 1 | COUNT STOPKEY | | | | | | | | 2 | VIEW | | 23180 | 430K| | 19861 (1)| 00:00:01 | |* 3 | SORT ORDER BY STOPKEY | | 23180 | 90M| 181M| 19861 (1)| 00:00:01 | | 4 | TABLE ACCESS BY INDEX ROWID| ELEMENTS | 23180 | 90M| | 1 (0)| 00:00:01 | | 5 | VECTOR INDEX HNSW SCAN | VIDX_ELEMENTS_ELEM_VECTOR | 23180 | 90M| | 1 (0)| 00:00:01 | --------------------------------------------------------------------------------------------------------------------
Filter zusätzlich zum Order by verwenden
Der Index wird verwendet und dann das Ergebnis gefiltert:
SELECT ID , vector_distance(ELEM_VECTOR, :SEARCH_VECTOR, COSINE ) AS v_COSINE_DISTANCE FROM ELEMENTS WHERE vector_distance(ELEM_VECTOR, :SEARCH_VECTOR, COSINE ) = 0 ORDER BY vector_distance(ELEM_VECTOR, :SEARCH_VECTOR, COSINE ) FETCH APPROX FIRST 3 ROWS ONLY; -------------------------------------------------------------------------------------------------------------------------- | Id | Operation | Name | ROWS | Bytes |TempSpc| Cost (%CPU)| TIME | -------------------------------------------------------------------------------------------------------------------------- | 0 | SELECT STATEMENT | | 3 | 57 | | 205 (1)| 00:00:01 | |* 1 | COUNT STOPKEY | | | | | | | | 2 | VIEW | | 232 | 4408 | | 205 (1)| 00:00:01 | |* 3 | SORT ORDER BY STOPKEY | | 232 | 935K| 1864K| 205 (1)| 00:00:01 | |* 4 | TABLE ACCESS BY INDEX ROWID | ELEMENTS | 232 | 935K| | 2 (0)| 00:00:01 | | 5 | VECTOR INDEX HNSW SCAN IN-FILTER| VIDX_ELEMENTS_ELEM_VECTOR | 232 | 935K| | 2 (0)| 00:00:01 | | 6 | VIEW | VW_HIJ_6212B5E8 | 1 | | | 1 (0)| 00:00:01 | |* 7 | TABLE ACCESS BY USER ROWID | ELEMENTS | 1 | 4127 | | 1 (0)| 00:00:01 | -------------------------------------------------------------------------------------------------------------------------- Predicate Information (IDENTIFIED BY operation id): --------------------------------------------------- 1 - FILTER(ROWNUM<=3) 3 - FILTER(ROWNUM<=3) 4 - FILTER(VECTOR_DISTANCE("ELEMENTS"."ELEM_VECTOR" /*+ LOB_BY_VALUE */ /*+ LOB_INLINE */ , VECTOR(:SEARCH_VECTOR, *, *, * /*+ USEBLOBPCW_QVCGMD */ ), COSINE)=0D) 7 - FILTER(VECTOR_DISTANCE("ELEMENTS"."ELEM_VECTOR" /*+ LOB_BY_VALUE */ /*+ LOB_INLINE */ , VECTOR(:SEARCH_VECTOR, *, *, * /*+ USEBLOBPCW_QVCGMD */ ), COSINE)=0D)
Transaktionsverhalten
Der Vector Index ist voll in das normale Transaktionsverhalten der Datenbank eingebunden.
Der Vector Index ist eine „static memory-only structure“.
Diese Struktur muss mit jeder Transaktion gepflegt und aktualisiert werden und wird beim Start der Instance in den Speicher geladen.
Dazu werden zwei Strukturen eingesetzt, ein „private journal“ (im Speicher ) und ein „shared journal“ (über die Tabellen des Domain Indexes ) .
Das private Journal ist als „per-transaction in-memory data structure“ für die laufenden Transaktion in der aktuellen Session zuständig und wird im Vector Memory Pool abgelegt.
Das „shared journal“ enthät die SCN der Commits und die geänderten Zeilen und verwendet dazu die beim Anlegen des Index erzeugten Tabellen. Sobald in einer Session ein Commit erfolgt, werden die Daten aus dem „private journal“ in diese Struktur mit übertragen.
Über einen Check Point Mechanismus und dem Log auf Änderungen wird dafür gesorgt, das bei größeren Änderungen des Index dieser auch neu in den Speicher geladen werden kann.
Doku dazu unter https://docs.oracle.com/en/database/oracle/oracle-database/23/vecse/understand-transaction-support-tables-hnsw-indexes.html
Zu beachten
Bei Verwendung von /*+ APPEND */ Hint wird direkt der Speicher aktualisiert.
Häufige Änderung / Löschungen auf der Vector Spalte hat auch mehr Zugriff auf die Journal Tabellen des Index zur Folge. Zwischen zwei Checkpoints wird über die Tabellen eingelesen werden Daten als „gelöscht“ aus den Ergebnissen gefiltert werden müssen.
Auf genügend Platz im Pool achten, damit parallel auch der Index im Speicher neu aufgebaut werden kann.
Während des Aufbaues kann es bei laufenden Abfragen (die vor dem neu aufbau schon liefen) zu einem „ORA 51815 „INMEMORY NEIGHBOR GRAPH HNSW vector index snapshot is too old.“ kommen, da die „alte“ Speicherstruktur nicht zu 100% in Sync sein können mit dem Journal in den Tabellen in der Datenbank die ja den Aufbau der Daten Struktur im Speicher mit steuern.
Vector Index Qualität
Findet der Index Lauf die gleichen Daten wie ein full Table Scan?
SELECT INDEX_NAME,INDEX_SUBTYPE,TABLE_NAME FROM USER_INDEXES WHERE TABLE_NAME LIKE '%TEXTE%' AND index_type = 'VECTOR'; INDEX_NAME INDEX_SUBTYPE TABLE_NAME -------------------------------------------------------------------------------- IDX_VTEXTE_HNSW_IDX INMEMORY_NEIGHBOR_GRAPH_HNSW VTEXTE
Qualität bewerten:
SET serveroutput ON VARIABLE query_vector CLOB BEGIN :query_vector := '[6, 7, 8, 9, 10]'; END; / DECLARE v_qvector VECTOR; v_report varchar2(128); BEGIN v_qvector := to_vector(:query_vector); v_report := dbms_vector.index_accuracy_query( OWNER_NAME => 'GPI' , INDEX_NAME => 'VIDX_ELEMENTS_ELEM_VECTOR' , qv => v_qvector , top_K =>10 , target_accuracy =>90 ); dbms_output.put_line(v_report); END; / Accuracy achieved (100%) IS 10% higher than the Target Accuracy requested (90%)
View für automatisch erzeugte Informationen „DBA_VECTOR_INDEX_ACCURACY_REPORT“
SELECT * FROM DBA_VECTOR_INDEX_ACCURACY_REPORT;
Fazit
Bei großen Datenmengen ist ein HNSW unerlässlich, um performant abschätzen zu können ob eine ähnlicher Vector wie der gesucht in der Datendatenmenge vorkommt.
D.h. eine Abschätzung der Ähnlichkeit der Treffermenge kann performant erfolgen.
Je performanter allerdings die Suche parametrisiert wird, desto ungenauer kann am Ende auch das Ergebnis werden.
Lokale Optima werden gesucht, es ist aber zu 100% nie ganz sicher, ob es wirklich das optimale Optimum war!
Änderung sich die Daten häufig bzw. kommen vielen Daten hinzu, muss auf ausreichend Platz im Vector Pool geachtet werden, da bei Checkpoints der Index min. kurzfristig zweimal in den Speicher passen muss, um neu aufgebaut werden zu können.
