Der Neuaufbau eines HNSW-Index ist einer der ressourcenintensivsten Aspekte bei der Verwendung von HNSW in Produktionsworkloads. Anders als bei herkömmlichen Datenbanken, bei denen Datenlöschungen durch einfaches Löschen einer Zeile in einer Tabelle durchgeführt werden können, erfordert die Verwendung von HNSW in einer Vektordatenbank oft einen vollständigen Neuaufbau, um optimale Leistung und Genauigkeit aufrechtzuerhalten.
Warum ist ein Wiederaufbau notwendig?
Aufgrund seiner mehrschichtigen Graphenstruktur ist HNSW nicht von Natur aus für dynamische Datensätze konzipiert, die sich häufig ändern. Das Hinzufügen neuer Daten oder das Löschen vorhandener Daten ist für die Aufrechterhaltung aktueller Daten unerlässlich, insbesondere für Anwendungsfälle wie RAG, bei denen die Suchrelevanz verbessert werden soll.
Die meisten Datenbanken arbeiten mit einem Konzept namens „hartes“ und „weiches“ Löschen. Hartes Löschen entfernt Daten dauerhaft, während weiches Löschen Daten als „zu löschen“ kennzeichnet und später entfernt. Das Drawback beim weichen Löschen besteht darin, dass die zu löschenden Daten noch immer viel Speicher beanspruchen, bis sie dauerhaft entfernt werden. Dies ist insbesondere bei Vektordatenbanken problematisch, die HNSW verwenden, bei denen der Speicherverbrauch bereits ein erhebliches Drawback darstellt.
HNSW erstellt ein Diagramm, in dem Knoten (Vektoren) auf Grundlage ihrer Nähe im Vektorraum verbunden sind, und das Durchlaufen eines HNSW-Diagramms erfolgt wie bei einer Skip-Liste. Um dies zu unterstützen, sind die Ebenen des Diagramms so gestaltet, dass einige Ebenen nur sehr wenige Knoten aufweisen. Wenn Vektoren gelöscht werden, insbesondere solche auf Ebenen mit sehr wenigen Knoten, die als kritische Verbindungselemente im Diagramm dienen, kann die gesamte HNSW-Struktur fragmentiert werden. Diese Fragmentierung kann dazu führen, dass Knoten (oder Ebenen) vom Hauptdiagramm getrennt werden, was einen Neuaufbau des gesamten Diagramms erforderlich macht oder zumindest zu einer Verschlechterung der Sucheffizienz führt.
HNSW verwendet dann eine Mushy-Delete-Technik, die Vektoren zum Löschen markiert, sie aber nicht sofort entfernt. Dieser Ansatz verringert den Aufwand für häufige vollständige Neuaufbauten, obwohl dennoch eine regelmäßige Rekonstruktion erforderlich ist, um den optimalen Zustand des Graphen aufrechtzuerhalten.