Warum ein semantisch ausgerichteter Index?

Was passiert, wenn eine ID Wissen ist, nicht eine Adresse

Eine Adresse weiss nichts

Um Yi Sun-sin in einer Datenbank zu finden, braucht man eine ID.

In Wikidata ist Yi Sun-sins ID Q8492.

Diese Nummer zeigt auf Yi Sun-sin. Aber die Zeichenkette Q8492 selbst weiss nichts.

Sie weiss nicht, ob es sich um eine Person oder ein Gebaeude handelt. Sie weiss nicht, ob es sich um einen Koreaner oder einen franzoesischen Staatsbuerger handelt. Sie weiss nicht, ob es sich um eine Figur des 16. oder des 21. Jahrhunderts handelt. Sie weiss nicht, ob diese Person lebt oder tot ist.

Q8492 ist eine Adresse. Ein Brieftraeger, der Post ausliefert, hat keine Ahnung, was im Umschlag steht. Er schaut einfach auf die Adresse auf dem Umschlag und liefert.

UUID ist dasselbe. 550e8400-e29b-41d4-a716-446655440000. 128 Bit Zufallszahlen. Einzigartig nur um Kollisionen zu vermeiden – es sagt nichts darueber aus, worauf es sich bezieht.

Seit fuenfzig Jahren funktionieren Datenbank-IDs so. Eine ID ist eine Adresse, und um etwas zu erfahren, muss man dieser Adresse folgen und die Daten lesen.

Man muss folgen, um zu wissen

Warum ist das ein Problem?

Angenommen, Sie moechten “einen maennlichen Philosophen deutscher Staatsangehoerigkeit, geboren im 19. Jahrhundert” finden.

In einer traditionellen Datenbank funktioniert das so:

1. Personentabelle filtern, wo gender = 'male'
2. JOIN mit Nationalitaetentabelle und filtern country = 'Germany'
3. JOIN mit Geburtsdatentabelle und filtern year BETWEEN 1800 AND 1899
4. JOIN mit Berufstabelle und filtern occupation = 'philosopher'

Vier JOIN-Operationen. Jeder JOIN vergleicht Zeilen aus zwei Tabellen. Wenn die Tabellen gross sind, durchlaeuft man einen Index; ohne Index erfolgt ein Full Scan. Bei einer Milliarde Datensaetze dauert dieser Prozess Sekunden bis Dutzende von Sekunden.

Warum ist es so komplex?

Weil die ID nichts weiss. Wenn man Q8492 betrachtet, kann man nicht erkennen, ob es sich um einen Deutschen oder einen Koreaner handelt, also muss man eine andere Tabelle aufsuchen, um diese Information abzurufen.

Fuer jede Frage muss man der Adresse der ID folgen. Das sind die Kosten, die Datenbanken seit fuenfzig Jahren zahlen.

Was waere, wenn die ID bereits wuesste?

Kehren wir die Praemisse um.

Was waere, wenn die ID selbst die wesentlichen Informationen enthielte?

Was waere, wenn man allein durch Betrachten der ID erkennen koennte, ob sie sich auf einen Menschen bezieht, aus welchem Land er stammt, welcher Epoche er angehoert und wie er klassifiziert ist?

Um “einen deutschen maennlichen Philosophen des 19. Jahrhunderts” zu finden, werden JOINs ueberfluessig.

Beim Durchscannen einer Milliarde IDs kann man sofort feststellen, ob jede einzelne passt, indem man ihre Bits untersucht.

Das ist die Kernidee hinter dem semantisch ausgerichteten Index.

Bedeutung in die ID einbetten

SIDX (Semantically-Aligned Index) ist ein 64-Bit-Identifikator.

Diese 64 Bits sind keine Zufallszahlen. Jeder Bit-Position ist eine Bedeutung zugewiesen.

Die oberen Bits enthalten die wichtigsten Informationen. Welche Art von Entitaet ist das? Eine Person, ein Ort, ein Ereignis, ein Konzept?

Die naechsten Bits enthalten Klassifikationsinformationen. Wenn es eine Person ist, welche Epoche? Welche Region?

Niedrigere Bits tragen zunehmend spezifische Informationen.

Das Schluesslprinzip ist:

Die Reihenfolge der Bits ist die Reihenfolge der Informationswichtigkeit.

Die grundlegendste Klassifikation oben, die feinsten Unterscheidungen unten.

Das ist keine blosse Sortierung. Das ist eine Designphilosophie.

Von einer Milliarde auf zehntausend, in einem Durchlauf

Die praktische Kraft von SIDX zeigt sich in den Zahlen.

WMS haelt eine Milliarde Entitaeten. Der SIDX jeder Entitaet ist 64 Bit. Gesamtgroesse: 1 Milliarde x 8 Bytes = 8 GB.

Diese 8 GB passen vollstaendig in den Arbeitsspeicher.

Sie moechten “Entitaeten finden, die menschlich sind und aus Ostasien stammen.” Die oberen Bits enthalten ein “Mensch”-Flag und einen “Ostasien”-Code, also kann man mit einer einzigen Bitmaske filtern.

mask   = 0xFF00_0000_0000_0000  (obere 8 Bits: Typ + Region)
target = 0x8100_0000_0000_0000  (Mensch + Ostasien)

for each sidx in 1_billion:
    if (sidx & mask) == target:
        add to candidates

Diese Operation laesst sich mit SIMD parallelisieren. Mit AVX-512 vergleicht man 8 SIDXs gleichzeitig in einer einzigen Instruktion. Scannen von 1 Milliarde Eintraegen: etwa 12 Millisekunden.

Auf einer GPU? Unter 1 Millisekunde.

Eine Milliarde Datensaetze auf zehntausend reduziert. Die verbleibenden zehntausend im Detail filtern ist augenblicklich.

Null JOINs. Null Index-Baumdurchlaeufe. Nur ein einziges bitweises AND.

Warum 64 Bit genuegen

Anfangs dachte ich, ein groesserer Raum sei noetig.

32 Bytes (256 Bits). Ein 32-dimensionaler FP16-Vektor. Ich versuchte, jedes Schluesselattribut einer Entitaet in die ID zu pressen. Ob menschlich, Geschlecht, Nationalitaet, Epoche, Beruf, Region, Lebendstatus, Klassifikationspfad…

Aber dann wurde mir etwas klar.

Die ID muss nicht alles wissen.

Sie muss nur eine Milliarde Datensaetze auf zehntausend reduzieren. WMS erledigt den Rest.

Denken Sie an einen Kontrollpunkt. An einer Autobahnmautstelle, um festzustellen, dass “dieses Fahrzeug Richtung Gyeonggi-Provinz faehrt” anhand des Kennzeichens, braucht man nicht zu wissen, was im Kofferraum geladen ist.

64 Bit genuegen. Die oberen Bits fuer Typ und grobe Klassifikation verwenden, die unteren Bits fuer feinere Klassifikation. 64 Bit sind mehr als ausreichend, um eine Milliarde Datensaetze auf zehntausend zu reduzieren.

Und 64 Bit = vier 16-Bit-Woerter. Sie fliessen natuerlich innerhalb eines Streams. Eine 32-Byte-ID wuerde einen Stream schwer machen, aber ein 64-Bit-SIDX ist leicht und schnell.

Graceful Degradation: Bedeutung ueberlebt selbst bei abgeschnittenen Bits

Eine weitere Staerke der semantischen Ausrichtung sind ihre Degradationseigenschaften.

Weil SIDX-Bits von wichtig nach unwichtig geordnet sind, bleibt die Kerninformation in den oberen Bits erhalten, selbst wenn untere Bits beschaedigt oder abgeschnitten werden.

Volle 64 Bits:  "Yi Sun-sin, Flottenkommandant des Joseon des 16. Jahrhunderts"
48 Bits:        "Militaeroffizier des Joseon des 16. Jahrhunderts"
32 Bits:        "Ostasiatischer Mensch des 16. Jahrhunderts"
16 Bits:        "Mensch"
8 Bits:         "Physische Entitaet"

Wenn Information abgeschnitten wird, geht Spezifitaet verloren, aber die grundlegendste Klassifikation ueberlebt bis zum Schluss.

Dies ist eine Bit-Level-Implementierung des “Graceful Degradation”-Prinzips.

Selbst wenn eine Netzwerkunterbrechung nur Teildaten liefert, weiss das System “ich weiss nicht genau, wer das ist, aber es geht mindestens um einen Menschen” und kann weiter denken.

Ein unscharfer Umriss ist besser als voellige Stille. Teilverstaendnis ist besser als totales Versagen.

Eine Abfrage wird zur ID

Die faszinierendste Moeglichkeit, die semantisch ausgerichtete Indexierung eroeffnet, ist diese: Eine natuerlichsprachliche Abfrage kann in einen temporaeren SIDX umgewandelt werden.

Ein Benutzer fragt: “Wer war der General, der die japanische Flotte waehrend des Imjin-Krieges besiegte?”

Der Encoder analysiert diese Frage. Mensch. Ostasien. 16. Jahrhundert. Militaerbezogen. Das Zusammensetzen dieser Attribute in Bits ergibt einen temporaeren SIDX.

Dieser temporaere SIDX scannt die Milliarden SIDXs im WMS. Entitaeten, deren Bitmuster am aehnlichsten sind, steigen als Kandidaten auf. Yi Sun-sin, Won Gyun, Gwon Yul, Yi Eok-gi…

Der Abgleich detaillierter Informationen mit diesen Kandidaten ergibt die endgueltige Antwort.

Das vereint Suche und Entity-Linking in einem einzigen Mechanismus. Keine separate Suchmaschine erforderlich. Keine separate NER-Pipeline (Named Entity Recognition) erforderlich. Ein einziger SIDX-Vergleich genuegt.

Warum kein B-Tree?

Traditionelle Datenbanken verwenden B-Tree-Indizes.

B-Trees eignen sich hervorragend dafuer, einen bestimmten Wert in sortierten Daten in O(log n) zu finden. Fuer “finde Q8492” sind sie optimal.

Aber fuer “finde alle Entitaeten, die menschlich sind und aus Ostasien stammen” sind sie schwach. Suchen mit zusammengesetzten Bedingungen erfordern die Schnittmenge mehrerer Indizes, und die Kosten der Schnittmenge wachsen stark mit der Datengroesse.

SIDX + SIMD-Exhaustivscan verfolgt einen grundlegend anderen Ansatz.

Wenn ein B-Tree ein Telefonbuch ist, das schnell beantwortet “wer wohnt an dieser Adresse”, ist ein SIDX-Scan ein Profiling, das schnell beantwortet “wer hat diese Eigenschaften”.

Die Art der Frage unterscheidet sich, und damit auch die optimale Datenstruktur.

WMS verwendet keine B-Trees. Es laedt eine Milliarde SIDXs in den Arbeitsspeicher und fuehrt einen Exhaustivscan mit SIMD-Bitmasken durch.

Einfach. Brute-Force. Schnell.

Huffmans Weisheit

Die Bit-Allokationsstruktur von SIDX folgt dem Prinzip der Huffman-Kodierung.

Bei der Huffman-Kodierung erhalten haeufig vorkommende Symbole kuerzere Codes, und selten vorkommende Symbole laengere Codes.

Bei SIDX belegen die am haeufigsten benoetigten Klassifikationsinformationen die oberen Bits, und selten benoetigte Details belegen die unteren Bits.

Dasselbe Prinzip bestimmt die Pakettyppraeifxe dieser Sprache. Der hochfrequente Tiny Verb Edge bekommt das kuerzeste Praefix. Der niederfrequente Event6 Edge bekommt ein laengeres Praefix.

Huffmans Weisheit durchzieht jede Schicht dieses Designs. Kein einziges Bit wird verschwendet. Die niedrigsten Kosten fuer das Wichtigste.

Zusammenfassung

Eine traditionelle ID ist eine Adresse. Eine Adresse weiss nichts.

1. Wenn die ID keine Bedeutung traegt, muss man jedes Mal den Daten folgen. Das ist ein JOIN.
2. Vier JOINs ueber eine Milliarde Datensaetze sind langsam.
3. SIDX kodiert Bedeutung direkt in die ID durch semantische Ausrichtung.
4. Ein einziges Bitmasken-AND reduziert eine Milliarde Datensaetze auf zehntausend. Null JOINs.
5. 64 Bit genuegen. Die ID muss nicht alles wissen – sie muss nur die Kandidaten eingrenzen.
6. Weil die wichtigste Information die oberen Bits belegt, ueberlebt die Kernbedeutung selbst bei abgeschnittenen Bits.
7. Die Umwandlung einer natuerlichsprachlichen Abfrage in einen temporaeren SIDX verwandelt Suche in eine Vektoroperation.

In dem Moment, in dem eine ID aufhoert eine Adresse zu sein und zu Wissen wird, aendern sich die Regeln der Datenbank.