Wie Vektordatenbanken funktionieren

Der Beitrag RAG: wann es sich lohnt hat die Vektorsuche als einen Baustein erwähnt und rasch weitergereicht. Hier geht es genau um diesen Baustein: die Vektordatenbank, also den Speicher, der Embeddings ablegt und auf Anfrage die ähnlichsten zurückgibt. Ein Embedding ist dabei die Abbildung eines Textausschnitts auf einen Vektor, sodass semantisch ähnliche Texte nahe beieinanderliegen. Die Frage dieses Artikels ist eng: Was macht eine Datenbank für solche Vektoren anders als eine gewöhnliche, und warum braucht es überhaupt eine eigene Gattung dafür.

Warum klassische Indizes hier versagen

Eine relationale Datenbank ist darauf ausgelegt, exakte oder geordnete Werte schnell zu finden: gleich, größer, kleiner, in einem Bereich. Ihr Werkzeug dafür ist der B-Baum, eine Indexstruktur, die genau von dieser eindimensionalen Ordnung lebt. Bei Vektoren gibt es diese Ordnung nicht. Niemand fragt nach dem Vektor, der exakt gleich ist, denn zwei natürliche Texte erzeugen fast nie denselben Embedding-Vektor. Gefragt ist stattdessen der nächste Nachbar: der gespeicherte Vektor mit dem kleinsten Abstand zur Anfrage.

Diese Nähe lebt in einem hochdimensionalen Raum. Übliche Embeddings haben mehrere Hundert bis wenige Tausend Dimensionen. Ein Index, der auf einer einzigen sortierbaren Achse beruht, hilft dort nicht, denn Nähe entsteht aus allen Dimensionen gleichzeitig. Genau diese Lücke füllt eine Vektordatenbank: Sie ist ein Speicher plus ein Index, der auf Nächste-Nachbarn-Suche in vielen Dimensionen zugeschnitten ist.

Was gespeichert wird, und wie Nähe gemessen wird

Ein Eintrag besteht typischerweise aus drei Teilen: einer Kennung, dem Vektor selbst und einem Satz Metadaten (Quelle, Datum, Sprache, Zugriffsrechte). Die Metadaten werden später wichtig, wenn wir filtern.

Der Kern ist das Abstandsmaß. Drei sind gebräuchlich: die euklidische Distanz (die anschauliche Luftlinie), das Skalarprodukt und die Kosinus-Ähnlichkeit, die nur den Winkel zwischen zwei Vektoren bewertet und ihre Länge ignoriert:

$\cos(u, v) = \frac{u \cdot v}{\lVert u \rVert \, \lVert v \rVert}$

Dass die Wahl des Maßes das Ergebnis verändert, sieht man an einem kleinen Beispiel. Die Anfrage sei $q = (2, 1)$, und es gebe zwei Kandidaten $a = (4, 2)$ und $b = (1, 2)$. Für die Kosinus-Ähnlichkeit rechnen wir:

$\cos(q, a) = \frac{2 \cdot 4 + 1 \cdot 2}{\sqrt{5} \cdot \sqrt{20}} = \frac{10}{\sqrt{100}} = 1{,}0, \qquad \cos(q, b) = \frac{2 \cdot 1 + 1 \cdot 2}{\sqrt{5} \cdot \sqrt{5}} = \frac{4}{5} = 0{,}8$

Nach Kosinus gewinnt also $a$, denn $a$ zeigt in exakt dieselbe Richtung wie $q$, nur doppelt so lang. Messen wir stattdessen die euklidische Distanz, dreht sich das Bild:

$d(q, a) = \sqrt{(4-2)^2 + (2-1)^2} = \sqrt{5} \approx 2{,}24, \qquad d(q, b) = \sqrt{(1-2)^2 + (2-1)^2} = \sqrt{2} \approx 1{,}41$

Nach Luftlinie liegt nun $b$ näher. Beide Antworten sind korrekt, sie beantworten nur verschiedene Fragen. Bei Text-Embeddings ist meist der Winkel aussagekräftig und die Länge eher ein Nebeneffekt von Häufigkeit oder Dokumentlänge. Deshalb ist die Kosinus-Ähnlichkeit dort der übliche Standard. Wichtig ist nur, beim Indexieren und beim Abfragen dasselbe Maß zu verwenden.

Der Preis der exakten Suche

Den exakten nächsten Nachbarn findet man immer, indem man die Anfrage mit jedem gespeicherten Vektor vergleicht. Bei $n$ Vektoren der Dimension $d$ kostet das in der Größenordnung $n \cdot d$ Rechenoperationen pro Anfrage. Für einen kleinen Bestand ist das völlig in Ordnung. Bei zehn Millionen Vektoren mit je 768 Dimensionen sind es aber rund $7{,}7$ Milliarden Multiplikationen für eine einzige Suche. Das ist der Grund, warum reine, exakte Suche jenseits kleiner Bestände nicht mehr trägt.

Eine Minimalversion in Python

Am kürzesten versteht man das an einer kleinen exakten Suche, ganz ohne spezielle Bibliothek. Ein Index ist im Kern nichts weiter als eine Matrix mit einer Zeile pro gespeichertem Vektor. In der Praxis stammen diese Vektoren aus einem Embedding-Modell; damit das Beispiel ohne Modell und ohne Netz läuft, treten hier Zufallsvektoren an ihre Stelle.

import numpy as np

rng = np.random.default_rng(0)
vektoren = rng.standard_normal((100_000, 768)).astype("float32")

def normalisieren(x):
    return x / np.linalg.norm(x, axis=-1, keepdims=True)

index = normalisieren(vektoren)

def suche(anfrage, k=5):
    q = normalisieren(anfrage)
    aehnlichkeit = index @ q
    beste = np.argsort(-aehnlichkeit)[:k]
    return beste, aehnlichkeit[beste]

treffer, werte = suche(vektoren[42])
print(int(treffer[0]), round(float(werte[0]), 3))

Zwei Zeilen tragen den ganzen Gedanken. Weil auf normierten Vektoren das Skalarprodukt genau die Kosinus-Ähnlichkeit ist, berechnet index @ q in einem Schritt die Ähnlichkeit der Anfrage zu jedem der 100000 gespeicherten Vektoren. Das ist wörtlich die $n \cdot d$-Rechnung von oben. Danach liefert np.argsort die Indizes der größten Werte. Sucht man mit einem bereits gespeicherten Vektor (vektoren[42]), findet die Funktion ihn selbst wieder, mit Ähnlichkeit $1{,}0$, die Ausgabe lautet also 42 1.0. Genau das leistet eine Vektordatenbank im Kern; alles Weitere dient nur dazu, dieses Skalarprodukt nicht für jeden einzelnen Vektor ausführen zu müssen.

Approximative Nächste-Nachbarn-Suche

Der Ausweg ist ein Handel: Man gibt die Garantie auf, immer den exakten nächsten Nachbarn zu finden, und erkauft sich dafür einen Bruchteil der Rechenzeit. Solche Verfahren heißen ANN, kurz für Approximate Nearest Neighbor, also approximative Nächste-Nachbarn-Suche. Wie gut sie sind, misst man mit dem Recall: dem Anteil der wahren nächsten Nachbarn, die tatsächlich gefunden werden. Ein Recall von 0,95 heißt, dass im Schnitt 95 von 100 echten Treffern gefunden werden.

Zwei Familien dominieren. Die erste teilt den Raum vorab in Zellen auf, meist mit dem k-means-Verfahren, das Punkte um eine feste Zahl von Schwerpunkten (Zentroiden) gruppiert. Diese Struktur heißt IVF, für Inverted File Index. Bei der Suche bestimmt man erst den nächsten Zentroiden und durchsucht dann nur die wenigen nächstgelegenen Zellen statt des gesamten Bestands.

Die Rechnung dahinter ist überschaubar. Teilt man die zehn Millionen Vektoren in 1000 Zellen, enthält jede im Schnitt 10000 Vektoren. Durchsucht man die zehn nächsten Zellen, vergleicht man rund 100000 Vektoren statt zehn Millionen, dazu die 1000 Zentroiden für die Vorauswahl. Aus dem gesamten Bestand wird so etwa ein Hundertstel, und genau darin liegt die Beschleunigung. Wie viele Zellen man durchsucht, ist ein Stellhebel: mehr Zellen heben den Recall und kosten Zeit, weniger Zellen sind schneller und riskieren, den echten Nachbarn in einer nicht durchsuchten Zelle zu übersehen.

Die zweite Familie baut einen navigierbaren Graphen über die Vektoren, in dem jeder Punkt mit einigen ähnlichen Nachbarn verbunden ist. Das bekannteste Verfahren heißt HNSW, für Hierarchical Navigable Small World. Die Suche startet an einem Einstiegspunkt und hangelt sich gierig immer zum nächstgelegenen Nachbarn weiter, bis es nicht mehr näher geht. Durch mehrere übereinandergelegte Ebenen, oben grob und weitmaschig, unten fein, erreicht man das Ziel in wenigen Schritten. Auch hier gibt es einen Regler, der Suchbreite gegen Recall abwägt. In beiden Familien gilt dieselbe Logik: nicht alles anschauen, sondern schnell in die richtige Nachbarschaft springen.

Ein IVF-Index in Code

Die Minimalversion von oben lässt sich nun um einen echten IVF-Index erweitern. Die verbreitete Bibliothek FAISS bringt genau diese Struktur mit, und die Parameter aus der Rechnung tauchen darin unmittelbar wieder auf. Der Bestand daten ist dieselbe normierte Matrix wie in der Minimalversion, also hunderttausend Vektoren statt der zehn Millionen aus der Rechnung; das hält das Beispiel schnell und ändert am Prinzip nichts.

import faiss

dimension, nlist = 768, 1000
quantisierer = faiss.IndexFlatIP(dimension)
index = faiss.IndexIVFFlat(quantisierer, dimension, nlist, faiss.METRIC_INNER_PRODUCT)

index.train(daten)
index.add(daten)
index.nprobe = 10

werte, treffer = index.search(daten[42:43], k=5)
print(int(treffer[0, 0]), round(float(werte[0, 0]), 3))

Jeder Schritt hat sein Gegenstück in der Theorie. nlist = 1000 ist die Zahl der Zellen aus dem Beispiel. IndexFlatIP und der Metrik-Parameter METRIC_INNER_PRODUCT legen fest, dass Nähe über das Skalarprodukt (englisch inner product, IP) gemessen wird, was auf den normierten Vektoren wieder die Kosinus-Ähnlichkeit ist. index.train lässt k-means die 1000 Zentroiden bestimmen, index.add ordnet jeden Vektor seiner Zelle zu, und index.nprobe = 10 legt fest, dass pro Anfrage die zehn nächsten Zellen durchsucht werden, also der Stellhebel zwischen Recall und Geschwindigkeit. Auch hier findet die Suche den Vektor daten[42] als sich selbst wieder. Setzt man nprobe klein, kann es dagegen passieren, dass der wahre Nachbar in einer nicht durchsuchten Zelle liegt und der Treffer ausbleibt, ganz wie oben beschrieben.

Bemerkenswert ist, wie wenig sich gegenüber der exakten Variante ändert: dieselbe Matrix, dieselbe Frage nach den ähnlichsten Zeilen, nur ein Index dazwischen, der die Arbeit auf einen Bruchteil der Vektoren eingrenzt. Diese drei Schritte, Index anlegen, mit Daten trainieren und füllen, mit einstellbarer Suchbreite abfragen, kehren in den meisten Werkzeugen wieder, nur unter anderen Namen.

Filtern nach Metadaten

Selten will man den ähnlichsten Vektor aus allem, meist nur aus einer Teilmenge: nur deutsche Dokumente, nur die letzten zwölf Monate, nur die für diese Nutzer:innen freigegebenen. Hier stoßen die beiden naiven Wege an Grenzen. Filtert man erst und sucht dann (pre-filtering), muss der Index mit der Einschränkung umgehen können, sonst bleibt nur die exakte Suche auf der Teilmenge. Sucht man erst und filtert dann (post-filtering), können nach dem Aussortieren zu wenige Treffer übrig bleiben, weil die besten Kandidaten weggefiltert wurden. Wie gut eine Vektordatenbank gefilterte Suche beherrscht, ist deshalb ein handfestes Auswahlkriterium und nicht bloß ein Detail.

Dedizierte Datenbank, Erweiterung oder Bibliothek?

Für das Ablegen und Durchsuchen von Vektoren gibt es drei Wege, grob nach Aufwand geordnet. Eine Bibliothek wie das oben verwendete FAISS hält den Index im Arbeitsspeicher der Anwendung; das ist schnell und schlank, bringt aber von sich aus keine Persistenz, keine Metadatenverwaltung und kein Betriebsdrumherum mit. Eine Erweiterung einer bestehenden Datenbank, etwa pgvector für PostgreSQL, legt die Vektoren neben die vorhandenen Tabellen; das spart ein zusätzliches System und lässt Vektorsuche und klassische Filter im selben SQL zusammenkommen. Eine dedizierte Vektordatenbank schließlich ist ein eigenständiger Dienst, der auf große Bestände, gefilterte Suche und Betrieb ausgelegt ist, dafür aber als zusätzliches System betrieben werden will.

Die nüchterne Faustregel: Wer schon eine relationale Datenbank betreibt und moderate Mengen hat, kommt mit einer Erweiterung oft am weitesten, weil ein System weniger auch ein Ausfallpunkt weniger ist. Ein dediziertes System lohnt sich, wenn Bestand, Abfragelast oder Anforderungen an gefilterte Suche das Vorhandene sprengen.

Fazit

Eine Vektordatenbank ist kein Zauberspeicher, sondern die Antwort auf eine sehr konkrete Frage: Wie findet man in vielen Dimensionen schnell die nächsten Nachbarn, wenn exakte Suche zu teuer wird. Der Kern sind ein passendes Abstandsmaß und ein approximativer Index, der über Recall und Latenz eingestellt wird. Wer eine solche Datenbank auswählt, sollte weniger auf Schlagworte achten als auf drei Dinge: das gewählte Distanzmaß, den einstellbaren Handel zwischen Recall und Geschwindigkeit und die Frage, wie gut sich nach Metadaten filtern lässt. Für den Einsatz in einer RAG-Anwendung entscheidet gerade Letzteres oft über die Qualität der Treffer.