Eröffnungsrede
Ich habe diesen Bericht auf Englisch auf der GopherCon Russia 2019-Konferenz in Moskau und auf Russisch bei einem Treffen in Nischni Nowgorod gehalten. Wir sprechen von einem Bitmap-Index – weniger verbreitet als B-Tree, aber nicht weniger interessant. Teilen Reden auf der Konferenz auf Englisch und Texttranskripte auf Russisch.
Wir werden uns ansehen, wie ein Bitmap-Index funktioniert, wann er besser ist, wann schlechter als andere Indizes und in welchen Fällen er deutlich schneller als diese ist; Sehen wir uns an, welche beliebten DBMS bereits über Bitmap-Indizes verfügen. Versuchen wir, unser eigenes in Go zu schreiben. Und „zum Nachtisch“ werden wir vorgefertigte Bibliotheken verwenden, um unsere eigene superschnelle Spezialdatenbank zu erstellen.
Ich hoffe wirklich, dass meine Arbeiten für Sie nützlich und interessant sind. Gehen!
Einführung
Hallo an alle! Es ist sechs Uhr abends und wir sind alle supermüde. Toller Zeitpunkt, um über die langweilige Datenbankindextheorie zu sprechen, oder? Keine Sorge, ich werde hier und da ein paar Zeilen Quellcode haben. 🙂
Spaß beiseite, der Bericht steckt voller Informationen und wir haben nicht viel Zeit. Also lasst uns anfangen.
Heute werde ich über Folgendes sprechen:
- Was sind Indizes?
- Was ist ein Bitmap-Index?
- wo es verwendet wird und wo es NICHT verwendet wird und warum;
- einfache Implementierung in Go und ein wenig Mühe mit dem Compiler;
- etwas weniger einfache, aber viel produktivere Implementierung im Go-Assembler;
- „Probleme“ von Bitmap-Indizes;
- bestehende Implementierungen.
Was sind also Indizes?
Der Index ist eine separate Datenstruktur, die wir zusätzlich zu den Hauptdaten pflegen und aktualisieren. Es wird verwendet, um die Suche zu beschleunigen. Ohne Indizes müssten für die Suche die Daten vollständig durchsucht werden (ein Prozess, der als „vollständiger Scan“ bezeichnet wird), und dieser Prozess weist eine lineare algorithmische Komplexität auf. Aber Datenbanken enthalten normalerweise große Datenmengen und die lineare Komplexität ist zu langsam. Im Idealfall würden wir eine logarithmische oder konstante Zahl erhalten.
Dies ist ein äußerst komplexes Thema voller Feinheiten und Kompromisse, aber nach einem Blick auf jahrzehntelange Datenbankentwicklung und -forschung bin ich bereit zu sagen, dass es nur wenige weit verbreitete Ansätze zum Erstellen von Datenbankindizes gibt.
Der erste Ansatz besteht darin, den Suchraum hierarchisch zu reduzieren und ihn in kleinere Teile zu unterteilen.
Normalerweise machen wir das mit verschiedenen Baumarten. Ein Beispiel wäre eine große Kiste mit Materialien in Ihrem Schrank, die kleinere Kisten mit Materialien enthält, die in verschiedene Themen unterteilt sind. Wenn Sie Materialien benötigen, werden Sie diese wahrscheinlich in einer Box mit der Aufschrift „Materialien“ suchen und nicht in einer mit der Aufschrift „Cookies“, oder?
Der zweite Ansatz besteht darin, das gewünschte Element oder die gewünschte Elementgruppe sofort auszuwählen. Wir tun dies in Hash-Maps oder Reverse-Indizes. Die Verwendung von Hash-Maps ist dem vorherigen Beispiel sehr ähnlich, aber statt einer Kiste voller Kisten haben Sie einen Haufen kleiner Kisten mit endgültigen Gegenständen in Ihrem Schrank.
Der dritte Ansatz besteht darin, die Notwendigkeit einer Suche zu beseitigen. Wir tun dies mit Bloom-Filtern oder Kuckucksfiltern. Die ersten geben sofort eine Antwort und ersparen Ihnen die Suche.
Der letzte Ansatz besteht darin, die gesamte Leistung, die uns moderne Hardware bietet, voll auszunutzen. Genau das machen wir bei Bitmap-Indizes. Ja, wenn wir sie verwenden, müssen wir manchmal den gesamten Index durchgehen, aber wir machen das sehr effizient.
Wie gesagt, das Thema Datenbankindizes ist umfangreich und voller Kompromisse. Das bedeutet, dass wir manchmal mehrere Ansätze gleichzeitig nutzen können: wenn wir die Suche noch weiter beschleunigen müssen oder wenn wir alle möglichen Suchtypen abdecken müssen.
Heute werde ich über den am wenigsten bekannten Ansatz dieser Art sprechen – Bitmap-Indizes.
Wer bin ich, um zu diesem Thema zu sprechen?
Ich arbeite als Teamleiter bei Badoo (vielleicht kennen Sie unser anderes Produkt, Bumble, besser). Wir haben bereits mehr als 400 Millionen Benutzer auf der ganzen Welt und viele Funktionen, die das beste Spiel für sie auswählen. Wir tun dies mithilfe benutzerdefinierter Dienste, einschließlich Bitmap-Indizes.
Was ist also ein Bitmap-Index?
Bitmap-Indizes verwenden, wie der Name schon sagt, Bitmaps oder Bitsets, um einen Suchindex zu implementieren. Aus der Vogelperspektive besteht dieser Index aus einer oder mehreren solchen Bitmaps, die beliebige Entitäten (z. B. Personen) und deren Eigenschaften oder Parameter (Alter, Augenfarbe usw.) darstellen, sowie einem Algorithmus, der Bitoperationen (UND, ODER, NICHT) verwendet ), um die Suchanfrage zu beantworten.
Uns wurde gesagt, dass Bitmap-Indizes am besten geeignet und sehr leistungsfähig sind, wenn es Suchvorgänge gibt, die Abfragen über viele Spalten mit niedriger Kardinalität hinweg kombinieren (denken Sie an „Augenfarbe“ oder „Familienstand“ im Vergleich zu etwas wie „Entfernung vom Stadtzentrum“). Aber ich werde später zeigen, dass sie auch für Spalten mit hoher Kardinalität gut funktionieren.
Schauen wir uns das einfachste Beispiel eines Bitmap-Index an.
Stellen Sie sich vor, wir hätten eine Liste von Moskauer Restaurants mit binären Eigenschaften wie diesen:
- in der Nähe der U-Bahn;
- es gibt einen privaten Parkplatz;
- es gibt eine Veranda (hat eine Terrasse);
- Sie können einen Tisch reservieren (Reservierungen werden entgegengenommen);
- geeignet für Vegetarier (veganfreundlich);
- teuer (teuer).
Geben wir jedem Restaurant eine Sequenznummer beginnend bei 0 und weisen Sie Speicher für 6 Bitmaps zu (eines für jedes Merkmal). Wir werden diese Bitmaps dann füllen, je nachdem, ob das Restaurant über diese Eigenschaft verfügt oder nicht. Wenn Restaurant 4 eine Veranda hat, wird Bit Nr. 4 in der Bitmap „hat eine Veranda“ auf 1 gesetzt (wenn es keine Veranda gibt, dann auf 0).
Jetzt haben wir den einfachsten Bitmap-Index, der möglich ist, und wir können ihn verwenden, um Fragen wie die folgenden zu beantworten:
- „Zeigen Sie mir vegetarische Restaurants“;
- „Zeigen Sie mir preiswerte Restaurants mit einer Veranda, auf der Sie einen Tisch reservieren können.“
Wie? Werfen wir einen Blick darauf. Die erste Anfrage ist sehr einfach. Alles, was wir tun müssen, ist, die „vegetarisch freundliche“ Bitmap in eine Liste von Restaurants umzuwandeln, deren Teile sichtbar sind.
Die zweite Anfrage ist etwas komplizierter. Wir müssen das NOT-Bitmap auf dem „teuren“ Bitmap verwenden, um eine Liste preiswerter Restaurants zu erhalten, dann UND es mit dem „Kann ich einen Tisch reservieren“-Bitmap und UND das Ergebnis mit dem „Es gibt eine Veranda“-Bitmap. Die resultierende Bitmap enthält eine Liste von Betrieben, die alle unsere Kriterien erfüllen. In diesem Beispiel handelt es sich nur um das Restaurant Yunost.
Es steckt viel Theorie dahinter, aber keine Sorge, wir werden den Code sehr bald sehen.
Wo werden Bitmap-Indizes verwendet?
Wenn Sie Bitmap-Indizes von Google verwenden, beziehen sich 90 % der Antworten auf die eine oder andere Weise auf Oracle DB. Aber andere DBMS unterstützen wahrscheinlich auch so eine coole Sache, oder? Nicht wirklich.
Gehen wir die Liste der Hauptverdächtigen durch.
MySQL unterstützt noch keine Bitmap-Indizes, es gibt jedoch einen Vorschlag, der das Hinzufügen dieser Option vorschlägt ().
PostgreSQL unterstützt keine Bitmap-Indizes, sondern verwendet einfache Bitmaps und Bitoperationen, um Suchergebnisse über mehrere andere Indizes hinweg zu kombinieren.
Tarantool verfügt über Bitset-Indizes und unterstützt einfache Suchvorgänge.
Redis hat einfache Bitfelder) ohne die Möglichkeit, danach zu suchen.
MongoDB unterstützt noch keine Bitmap-Indizes, es gibt jedoch auch einen Vorschlag, der die Hinzufügung dieser Option vorschlägt
Elasticsearch verwendet intern Bitmaps).
- Aber ein neuer Nachbar ist in unserem Haus aufgetaucht: Pilosa. Dies ist eine neue nicht relationale Datenbank, die in Go geschrieben wurde. Es enthält nur Bitmap-Indizes und basiert alles auf ihnen. Wir werden etwas später darüber reden.
Implementierung in Go
Aber warum werden Bitmap-Indizes so selten verwendet? Bevor ich diese Frage beantworte, möchte ich Ihnen zeigen, wie Sie einen sehr einfachen Bitmap-Index in Go implementieren.
Bitmaps sind im Wesentlichen nur Datenstücke. In Go verwenden wir hierfür Byte-Slices.
Wir haben eine Bitmap für eine Restauranteigenschaft und jedes Bit in der Bitmap gibt an, ob ein bestimmtes Restaurant über diese Eigenschaft verfügt oder nicht.
Wir benötigen zwei Hilfsfunktionen. Einer wird verwendet, um unsere Bitmaps mit zufälligen Daten zu füllen. Zufällig, aber mit einer gewissen Wahrscheinlichkeit, dass das Restaurant jedes Objekt besitzt. Ich glaube zum Beispiel, dass es in Moskau nur sehr wenige Restaurants gibt, in denen man keinen Tisch reservieren kann, und mir scheint, dass etwa 20 % der Lokale für Vegetarier geeignet sind.
Die zweite Funktion wandelt die Bitmap in eine Liste von Restaurants um.
Um die Frage „Zeigen Sie mir preiswerte Restaurants mit Terrasse und Reservierungsmöglichkeiten“ zu beantworten, benötigen wir zwei Bitoperationen: NICHT und UND.
Wir können unseren Code ein wenig vereinfachen, indem wir den komplexeren AND NOT-Operator verwenden.
Wir haben Funktionen für jede dieser Operationen. Beide gehen die Slices durch, nehmen von jedem die entsprechenden Elemente, kombinieren sie mit einer Bitoperation und fügen das Ergebnis in das resultierende Slice ein.
Und jetzt können wir unsere Bitmaps und Funktionen verwenden, um die Suchanfrage zu beantworten.
Die Leistung ist nicht so hoch, obwohl die Funktionen sehr einfach sind und wir viel Geld gespart haben, indem wir nicht bei jedem Aufruf der Funktion ein neues resultierendes Slice zurückgegeben haben.
Nachdem ich mit pprof ein wenig Profil erstellt hatte, bemerkte ich, dass dem Go-Compiler eine sehr einfache, aber sehr wichtige Optimierung fehlte: Funktions-Inlining.
Tatsache ist, dass der Go-Compiler schreckliche Angst vor Schleifen hat, die Slices durchlaufen, und sich kategorisch weigert, Funktionen zu integrieren, die solche Schleifen enthalten.
Aber ich habe keine Angst und kann den Compiler täuschen, indem ich goto anstelle einer Schleife verwende, wie in den guten alten Zeiten.
Und wie Sie sehen können, integriert der Compiler unsere Funktion jetzt problemlos! Dadurch gelingt es uns, etwa 2 Mikrosekunden einzusparen. Nicht schlecht!
Der zweite Engpass ist leicht zu erkennen, wenn man sich die Assembly-Ausgabe genau ansieht. Der Compiler hat direkt in unserer heißesten Schleife eine Slice-Grenzenprüfung hinzugefügt. Da Go eine sichere Sprache ist, befürchtet der Compiler, dass meine drei Argumente (drei Slices) unterschiedlich groß sind. Denn dann besteht theoretisch die Möglichkeit, dass es zu einem sogenannten Pufferüberlauf kommt.
Beruhigen wir den Compiler, indem wir ihm zeigen, dass alle Slices die gleiche Größe haben. Wir können dies tun, indem wir am Anfang unserer Funktion eine einfache Prüfung hinzufügen.
Als der Compiler dies sieht, überspringt er die Prüfung glücklich und wir sparen am Ende weitere 500 Nanosekunden.
Große Schlächter
Okay, wir haben es geschafft, etwas Leistung aus unserer einfachen Implementierung herauszuholen, aber dieses Ergebnis ist tatsächlich viel schlechter, als es mit aktueller Hardware möglich ist.
Wir machen lediglich grundlegende Bitoperationen, und unsere Prozessoren führen sie sehr effizient aus. Aber leider „füttern“ wir unseren Prozessor mit sehr kleinen Arbeitsstücken. Unsere Funktionen führen Operationen byteweise durch. Mithilfe von UInt8-Slices können wir unseren Code ganz einfach so anpassen, dass er mit 64-Byte-Blöcken funktioniert.
Wie Sie sehen, hat diese kleine Änderung unser Programm um das Achtfache beschleunigt, indem die Chargengröße um das Achtfache erhöht wurde. Der Gewinn kann als linear bezeichnet werden.
Implementierung im Assembler
Aber das ist nicht das Ende. Unsere Prozessoren können mit Blöcken von 16, 32 und sogar 64 Bytes arbeiten. Solche „breiten“ Operationen werden als Single Instruction Multiple Data (SIMD; eine Anweisung, viele Daten) bezeichnet, und der Prozess der Codetransformation, sodass er solche Operationen verwendet, wird als Vektorisierung bezeichnet.
Leider ist der Go-Compiler bei der Vektorisierung alles andere als hervorragend. Derzeit besteht die einzige Möglichkeit, Go-Code zu vektorisieren, darin, diese Operationen manuell mit dem Go-Assembler durchzuführen.
Go Assembler ist ein seltsames Biest. Sie wissen wahrscheinlich, dass die Assemblersprache stark an die Architektur des Computers gebunden ist, für den Sie schreiben, aber das ist in Go nicht der Fall. Go Assembler ähnelt eher einer IRL (Intermediate Representation Language) oder Zwischensprache: Es ist praktisch plattformunabhängig. Rob Pike hat eine hervorragende Leistung gezeigt zu diesem Thema vor einigen Jahren auf der GopherCon in Denver.
Darüber hinaus verwendet Go ein ungewöhnliches Plan-9-Format, das sich von den allgemein akzeptierten AT&T- und Intel-Formaten unterscheidet.
Man kann mit Sicherheit sagen, dass das Schreiben von Go-Assembler von Hand nicht besonders viel Spaß macht.
Aber glücklicherweise gibt es bereits zwei High-Level-Tools, die uns beim Schreiben von Go-Assembler helfen: PeachPy und avo. Beide Dienstprogramme generieren Go-Assembler aus übergeordnetem Code, der in Python bzw. Go geschrieben wurde.
Diese Dienstprogramme vereinfachen Dinge wie die Registerzuweisung und das Schreiben von Schleifen und erleichtern im Allgemeinen den Einstieg in die Welt der Assemblerprogrammierung in Go.
Wir werden avo verwenden, sodass unsere Programme fast normale Go-Programme sein werden.
So sieht das einfachste Beispiel eines Avo-Programms aus. Wir haben eine main()-Funktion, die in sich die Add()-Funktion definiert, deren Bedeutung darin besteht, zwei Zahlen zu addieren. Hier gibt es Hilfsfunktionen, um Parameter anhand des Namens abzurufen und eines der freien und geeigneten Prozessorregister zu erhalten. Jede Prozessoroperation hat eine entsprechende Funktion auf avo, wie in ADDQ zu sehen ist. Schließlich sehen wir eine Hilfsfunktion zum Speichern des resultierenden Werts.
Durch den Aufruf von go generic führen wir das Programm auf avo aus und als Ergebnis werden zwei Dateien generiert:
- add.s mit dem resultierenden Code im Go-Assembler;
- stub.go mit Funktionsheadern, um die beiden Welten zu verbinden: Go und Assembler.
Nachdem wir nun gesehen haben, was avo tut und wie, schauen wir uns unsere Funktionen an. Ich habe sowohl Skalar- als auch Vektorversionen (SIMD) der Funktionen implementiert.
Schauen wir uns zunächst die Skalarversionen an.
Da wir im vorherigen Beispiel nach einem kostenlosen und gültigen Allzweckregister fragen, müssen wir keine Offsets und Größen für die Argumente berechnen. avo erledigt das alles für uns.
Früher haben wir Labels und Goto (oder Sprünge) verwendet, um die Leistung zu verbessern und den Go-Compiler auszutricksen, aber jetzt machen wir es von Anfang an. Der Punkt ist, dass Zyklen ein übergeordnetes Konzept sind. Im Assembler gibt es nur Beschriftungen und Sprünge.
Der restliche Code sollte bereits bekannt und verständlich sein. Wir emulieren eine Schleife mit Beschriftungen und Sprüngen, nehmen ein kleines Datenstück aus unseren beiden Slices, kombinieren sie mit einer Bitoperation (UND NICHT in diesem Fall) und fügen das Ergebnis dann in das resultierende Slice ein. Alle.
So sieht der endgültige Assembler-Code aus. Wir mussten keine Versätze und Größen berechnen (grün hervorgehoben) oder die verwendeten Register im Auge behalten (rot hervorgehoben).
Wenn wir die Leistung der Assembler-Implementierung mit der Leistung der besten Implementierung in Go vergleichen, werden wir feststellen, dass es dasselbe ist. Und das wird erwartet. Schließlich haben wir nichts Besonderes gemacht – wir haben lediglich reproduziert, was ein Go-Compiler tun würde.
Leider können wir den Compiler nicht zwingen, unsere in Assemblersprache geschriebenen Funktionen zu integrieren. Der Go-Compiler verfügt derzeit nicht über eine solche Funktion, obwohl es schon seit einiger Zeit eine Anfrage gibt, sie hinzuzufügen.
Aus diesem Grund ist es unmöglich, aus kleinen Funktionen in Assembler einen Nutzen zu ziehen. Wir müssen entweder große Funktionen schreiben oder das neue Paket math/bits verwenden oder die Assemblersprache umgehen.
Schauen wir uns nun die Vektorversionen unserer Funktionen an.
Für dieses Beispiel habe ich mich für die Verwendung von AVX2 entschieden, daher werden wir Operationen verwenden, die auf 32-Byte-Blöcken arbeiten. Die Struktur des Codes ist der Skalarversion sehr ähnlich: Laden von Parametern, Anfordern eines kostenlosen gemeinsam genutzten Registers usw.
Eine Neuerung besteht darin, dass breitere Vektoroperationen spezielle breite Register verwenden. Bei 32-Byte-Chunks handelt es sich um Register mit dem Präfix Y. Aus diesem Grund sehen Sie im Code die Funktion YMM(). Wenn ich AVX-512 mit 64-Bit-Chunks verwenden würde, wäre das Präfix Z.
Die zweite Neuerung besteht darin, dass ich mich für eine Optimierung namens „Loop Unrolling“ entschieden habe, was bedeutet, dass acht Schleifenoperationen manuell ausgeführt werden, bevor zum Anfang der Schleife gesprungen wird. Diese Optimierung reduziert die Anzahl der Verzweigungen im Code und wird durch die Anzahl der verfügbaren freien Register begrenzt.
Nun, wie sieht es mit der Leistung aus? Sie ist schön! Im Vergleich zur besten Go-Lösung haben wir eine etwa siebenfache Geschwindigkeitssteigerung erreicht. Beeindruckend, oder?
Aber auch diese Implementierung könnte möglicherweise durch die Verwendung von AVX-512, Prefetching oder einem JIT (Just-in-Time-Compiler) für den Abfrageplaner beschleunigt werden. Aber das ist sicherlich ein Thema für einen separaten Bericht.
Probleme mit Bitmap-Indizes
Nachdem wir uns nun bereits eine einfache Implementierung eines Bitmap-Index in Go und eine viel produktivere in Assemblersprache angesehen haben, wollen wir abschließend darüber sprechen, warum Bitmap-Indizes so selten verwendet werden.
In älteren Veröffentlichungen werden drei Probleme mit Bitmap-Indizes erwähnt, aber neuere Veröffentlichungen und ich argumentieren, dass sie nicht mehr relevant sind. Wir werden nicht näher auf jedes dieser Probleme eingehen, sondern sie oberflächlich betrachten.
Das Problem der hohen Kardinalität
Uns wird also gesagt, dass Bitmap-Indizes nur für Felder mit geringer Kardinalität geeignet sind, also solche mit wenigen Werten (z. B. Geschlecht oder Augenfarbe), und der Grund dafür ist, dass die übliche Darstellung solcher Felder (eins Bit pro Wert) wird bei hoher Kardinalität zu viel Platz beanspruchen und außerdem werden diese Bitmap-Indizes schlecht (selten) gefüllt.
Manchmal verwenden wir möglicherweise eine andere Darstellung, beispielsweise die Standarddarstellung, die wir zur Darstellung von Zahlen verwenden. Aber erst das Aufkommen von Komprimierungsalgorithmen hat alles verändert. In den letzten Jahrzehnten haben Wissenschaftler und Forscher eine Vielzahl von Komprimierungsalgorithmen für Bitmaps entwickelt. Ihr Hauptvorteil besteht darin, dass Bitmaps nicht dekomprimiert werden müssen, um Bitoperationen auszuführen – wir können Bitoperationen direkt an komprimierten Bitmaps durchführen.
In letzter Zeit tauchen zunehmend hybride Ansätze auf, beispielsweise Roaring-Bitmaps. Sie verwenden gleichzeitig drei verschiedene Darstellungen für Bitmaps – Bitmaps selbst, Arrays und sogenannte Bitläufe – und balancieren zwischen ihnen, um die Leistung zu maximieren und den Speicherverbrauch zu minimieren.
Brüllende Bitmaps finden Sie in den beliebtesten Anwendungen. Es gibt bereits eine Vielzahl von Implementierungen für die unterschiedlichsten Programmiersprachen, darunter mehr als drei Implementierungen für Go.
Ein weiterer Ansatz, der uns beim Umgang mit hoher Kardinalität helfen kann, ist das sogenannte Binning. Stellen Sie sich vor, Sie haben ein Feld, das die Größe einer Person darstellt. Die Höhe ist eine Gleitkommazahl, aber wir Menschen denken nicht so darüber. Für uns gibt es keinen Unterschied zwischen der Körpergröße 185,2 cm und 185,3 cm.
Es stellt sich heraus, dass wir ähnliche Werte innerhalb von 1 cm in Gruppen einteilen können.
Und wenn wir außerdem wissen, dass sehr wenige Menschen kleiner als 50 cm und größer als 250 cm sind, dann können wir im Wesentlichen ein Feld mit unendlicher Kardinalität in ein Feld mit einer Kardinalität von etwa 200 Werten umwandeln.
Natürlich können wir bei Bedarf im Nachhinein noch eine zusätzliche Filterung durchführen.
Problem mit hoher Bandbreite
Das nächste Problem bei Bitmap-Indizes besteht darin, dass ihre Aktualisierung sehr teuer sein kann.
Datenbanken müssen in der Lage sein, Daten zu aktualisieren, während möglicherweise Hunderte anderer Abfragen die Daten durchsuchen. Wir benötigen Sperren, um Probleme beim gleichzeitigen Datenzugriff oder andere Freigabeprobleme zu vermeiden. Und wo es eine große Sperre gibt, gibt es ein Problem – einen Sperrenkonflikt, wenn diese Sperre zu einem Engpass wird.
Dieses Problem kann durch Sharding oder versionierte Indizes gelöst oder umgangen werden.
Sharding ist eine einfache und bekannte Sache. Sie können einen Bitmap-Index wie alle anderen Daten teilen. Anstelle einer großen Sperre erhalten Sie eine Reihe kleiner Sperren und beseitigen so Sperrenkonflikte.
Die zweite Möglichkeit, das Problem zu lösen, besteht darin, versionierte Indizes zu verwenden. Sie können eine Kopie des Index haben, die Sie zum Suchen oder Lesen verwenden, und eine, die Sie zum Schreiben oder Aktualisieren verwenden. Und einmal in einem bestimmten Zeitraum (z. B. einmal alle 100 ms oder 500 ms) duplizieren Sie sie und tauschen sie aus. Dieser Ansatz ist natürlich nur in Fällen anwendbar, in denen Ihre Anwendung einen leicht verzögerten Suchindex verarbeiten kann.
Diese beiden Ansätze können gleichzeitig verwendet werden: Sie können einen fragmentierten versionierten Index haben.
Komplexere Abfragen
Das letzte Problem bei Bitmap-Indizes besteht darin, dass uns mitgeteilt wird, dass sie für komplexere Abfragetypen, wie z. B. Span-Abfragen, nicht gut geeignet sind.
Tatsächlich sind Bitoperationen wie AND, OR usw., wenn man darüber nachdenkt, für Abfragen à la „Zeigen Sie mir Hotels mit Zimmerpreisen von 200 bis 300 Dollar pro Nacht“ nicht sehr geeignet.
Eine naive und sehr unkluge Lösung wäre, die Ergebnisse für jeden Dollarwert zu nehmen und sie mit einer bitweisen ODER-Operation zu kombinieren.
Eine etwas bessere Lösung wäre die Verwendung von Gruppierungen. Zum Beispiel in Gruppen von 50 Dollar. Dies würde unseren Prozess um das 50-fache beschleunigen.
Das Problem lässt sich aber auch leicht lösen, indem man eine speziell für diese Art von Anfrage erstellte Ansicht verwendet. In wissenschaftlichen Arbeiten spricht man von bereichskodierten Bitmaps.
In dieser Darstellung setzen wir nicht einfach ein Bit für einen Wert (zum Beispiel 200), sondern setzen diesen Wert und alles höher. 200 und mehr. Das Gleiche gilt für 300: 300 und höher. Usw.
Mit dieser Darstellung können wir diese Art von Suchanfrage beantworten, indem wir den Index nur zweimal durchlaufen. Zuerst erhalten wir eine Liste der Hotels, in denen das Zimmer weniger oder 300 US-Dollar kostet, und dann entfernen wir diejenigen, in denen das Zimmer weniger oder 199 US-Dollar kostet. Bereit.
Sie werden überrascht sein, aber auch Geoabfragen sind mithilfe von Bitmap-Indizes möglich. Der Trick besteht darin, eine geometrische Darstellung zu verwenden, die Ihre Koordinate mit einer geometrischen Figur umgibt. Zum Beispiel S2 von Google. Die Figur sollte in Form von drei oder mehr sich schneidenden Linien dargestellt werden können, die nummeriert werden können. Auf diese Weise können wir unsere Geoabfrage in mehrere Abfragen „entlang der Lücke“ (entlang dieser nummerierten Linien) umwandeln.
Bereit Lösungen
Ich hoffe, dass ich Sie ein wenig interessiert habe und Sie nun ein weiteres nützliches Werkzeug in Ihrem Arsenal haben. Wenn Sie jemals so etwas tun müssen, wissen Sie, worauf Sie achten müssen.
Allerdings hat nicht jeder die Zeit, Geduld oder Ressourcen, um Bitmap-Indizes von Grund auf zu erstellen. Vor allem fortgeschrittenere, zum Beispiel mit SIMD.
Glücklicherweise gibt es mehrere vorgefertigte Lösungen, die Ihnen helfen können.
Brüllende Bitmaps
Erstens gibt es dieselbe tolle Bitmap-Bibliothek, über die ich bereits gesprochen habe. Es enthält alle notwendigen Container und Bitoperationen, die Sie zum Erstellen eines vollwertigen Bitmap-Index benötigen.
Leider verwendet derzeit keine der Go-Implementierungen SIMD, was bedeutet, dass Go-Implementierungen beispielsweise weniger performant sind als C-Implementierungen.
Pilosa
Ein weiteres Produkt, das Ihnen helfen kann, ist das Pilosa DBMS, das tatsächlich nur über Bitmap-Indizes verfügt. Dies ist eine relativ neue Lösung, die jedoch schnell die Herzen erobert.
Pilosa verwendet interne Bitmaps und gibt Ihnen die Möglichkeit, sie zu verwenden. Es vereinfacht und erklärt alle Dinge, über die ich oben gesprochen habe: Gruppierung, bereichscodierte Bitmaps, das Konzept eines Felds usw.
Werfen wir einen kurzen Blick auf ein Beispiel für die Verwendung von Pilosa zur Beantwortung einer Frage, mit der Sie bereits vertraut sind.
Das Beispiel ist dem, was Sie zuvor gesehen haben, sehr ähnlich. Wir erstellen einen Client zum Pilosa-Server, erstellen einen Index und die erforderlichen Felder, füllen dann unsere Felder mit Zufallsdaten mit Wahrscheinlichkeiten und führen schließlich die bekannte Abfrage aus.
Danach verwenden wir NOT für das Feld „teuer“ und schneiden dann das Ergebnis (oder UND) mit dem Feld „Terrasse“ und dem Feld „Reservierungen“. Und schließlich erhalten wir das Endergebnis.
Ich hoffe wirklich, dass dieser neue Indextyp in absehbarer Zeit auch in DBMS wie MySQL und PostgreSQL auftauchen wird – Bitmap-Indizes.
Abschluss
Wenn Sie noch nicht eingeschlafen sind, vielen Dank. Aufgrund der begrenzten Zeit musste ich viele Themen kurz ansprechen, aber ich hoffe, dass der Vortrag nützlich und vielleicht sogar motivierend war.
Es ist gut, über Bitmap-Indizes Bescheid zu wissen, auch wenn Sie sie gerade nicht benötigen. Machen Sie sie zu einem weiteren Werkzeug in Ihrem Werkzeugkasten.
Wir haben uns verschiedene Performance-Tricks für Go und Dinge angeschaut, mit denen der Go-Compiler noch nicht so gut zurechtkommt. Aber das ist für jeden Go-Programmierer absolut nützlich.
Das ist alles, was ich dir sagen wollte. Danke!
Source: habr.com