In den vorherigen Artikeln haben wir die PostgreSQL- Indizierungs-Engine und die Schnittstelle von Zugriffsmethoden sowie Hash-Indizes , B-Bäume , GiST , SP-GiST , GIN , RUM und BRIN erörtert . Aber wir müssen uns noch die Bloom-Indizes ansehen.

Blüte

Allgemeines Konzept

Ein klassischer Bloom-Filter ist eine Datenstruktur, mit der wir die Zugehörigkeit eines Elements zu einer Menge schnell überprüfen können. Der Filter ist sehr kompakt, lässt jedoch falsch positive Ergebnisse zu: Er kann fälschlicherweise ein Element als Mitglied einer Menge betrachten (falsch positiv), aber es ist nicht zulässig, ein Element einer Menge nicht als Mitglied zu betrachten (falsch negativ). .

Der Filter ist ein Array von $$$m$ Bits (auch als Signatur bezeichnet ), die anfänglich mit Nullen gefüllt sind. $$$k$ Es werden verschiedene Hash-Funktionen ausgewählt, die ein beliebiges Element der Menge zuordnen $$$k$ Bits der Signatur. Um der Menge ein Element hinzuzufügen, müssen wir jedes dieser Bits in der Signatur auf eins setzen. Wenn folglich alle einem Element entsprechenden Bits auf eins gesetzt sind, kann das Element ein Mitglied der Menge sein, aber wenn mindestens ein Bit gleich Null ist, ist das Element nicht sicher in der Menge.

Im Falle eines DBMS haben wir tatsächlich $$$N$ Für jede Indexzeile werden separate Filter erstellt. In der Regel sind mehrere Felder im Index enthalten, und die Werte dieser Felder bilden die Elementmenge für jede Zeile.

Durch Auswahl der Länge der Signatur $$$m$ können wir einen Kompromiss zwischen der Indexgröße und der Wahrscheinlichkeit von falsch positiven Ergebnissen finden. Der Anwendungsbereich für den Bloom-Index besteht aus großen, erheblich "breiten" Tabellen, die mithilfe von Filtern für jedes der Felder abgefragt werden müssen. Diese Zugriffsmethode kann wie BRIN als Beschleuniger des sequentiellen Scans betrachtet werden: Alle vom Index gefundenen Übereinstimmungen müssen mit der Tabelle erneut überprüft werden, es besteht jedoch die Möglichkeit, die meisten Zeilen überhaupt nicht zu berücksichtigen.

Struktur

Wir haben bereits Signaturbäume im Zusammenhang mit der GiST- Zugriffsmethode erörtert . Im Gegensatz zu diesen Bäumen ist der Bloom-Index eine flache Struktur. Es besteht aus einer Metapage, gefolgt von regulären Seiten mit Indexzeilen. Jede Indexzeile enthält eine Signatur und einen Verweis auf eine Tabellenzeile (TID), wie in der Abbildung schematisch dargestellt.

Erstellung und Auswahl von Parameterwerten

Beim Erstellen des Bloom-Index wird eine Gesamtgröße der Signatur ("Länge") sowie die Anzahl der Bits angegeben, die für jedes einzelne im Index enthaltene Feld festgelegt werden müssen ("col1" - "col32"):

create index on ... using bloom(...) with (length=..., col1=..., col2=..., ...); 

Die Art und Weise, wie die Anzahl der Bits angegeben wird, sieht seltsam aus: Diese Zahlen müssen Parameter einer Operatorklasse und nicht des Index sein. Die Sache ist, dass Operatorklassen derzeit nicht parametrisiert werden können, obwohl daran gearbeitet wird.

Leider gibt es hier keine weiteren Fortschritte.

Wie können wir geeignete Werte auswählen? Die Theorie besagt, dass angesichts der Wahrscheinlichkeit $$$p$ eines Filters, um ein falsch positives Ergebnis zurückzugeben, kann die optimale Anzahl von Signaturbits als geschätzt werden $$$m = −n \ log_2 p / \ ln 2$ , wo $$$n$ ist die Anzahl der Felder im Index und die Anzahl der zu setzenden Bits $$$k = - \ log_2 p$ .

Die Signatur wird im Index als Array von Zwei-Byte-Ganzzahlen gespeichert, also der Wert von $$$m$ kann sicher aufgerundet werden $$$16$ .

Bei der Auswahl der Wahrscheinlichkeit $$$p$ müssen wir die Größe des Index berücksichtigen, die ungefähr gleich ist $$$(m / 8 + 6) N$ , wo $$$N$ ist die Anzahl der Zeilen in der Tabelle und $$$6$ ist die Größe des TID-Zeigers in Bytes.

Einige Punkte zu beachten:

• Die Wahrscheinlichkeit $$$p$ eines falsch positiven bezieht sich auf einen Filter, daher erwarten wir zu bekommen $$$Np$ False Positives während des Tabellenscans (natürlich für eine Abfrage, die nur wenige Zeilen zurückgibt). Beispielsweise können wir für eine Tabelle mit einer Million Zeilen und einer Wahrscheinlichkeit von 0,01 im Abfrageplan im Durchschnitt "Durch Indexüberprüfung entfernte Zeilen: 10000" erwarten.
• Bloom Filter ist eine probabilistische Struktur. Es ist sinnvoll, nur dann von bestimmten Zahlen zu sprechen, wenn ziemlich viele Werte gemittelt werden, während wir in jedem einzelnen Fall alles bekommen können, was wir uns vorstellen können.
• Die obigen Schätzungen basieren auf einem idealisierten mathematischen Modell und einigen Annahmen. In der Praxis ist das Ergebnis wahrscheinlich schlechter. Überschätzen Sie also nicht die Formeln: Sie sind nur ein Mittel, um Anfangswerte für zukünftige Experimente zu wählen.
• Mit der Zugriffsmethode können wir für jedes Feld einzeln die Anzahl der zu setzenden Bits auswählen. Es besteht die begründete Annahme, dass die optimale Anzahl tatsächlich von der Verteilung der Werte in der Spalte abhängt. Um tiefer zu tauchen, können Sie diesen Artikel lesen (Verweise auf andere Forschungen sind willkommen). Lesen Sie jedoch zuerst den vorherigen Artikel erneut.

Aktualisieren

Wenn eine neue Zeile in eine Tabelle eingefügt wird, wird eine Signatur erstellt: Für die Werte aller indizierten Felder werden alle entsprechenden Bits auf eins gesetzt. Theoretisch müssen wir k verschiedene Hash-Funktionen haben, während in der Praxis der Pseudozufallszahlengenerator ausreicht, dessen Startwert jedes Mal mit Hilfe der einzigen Hash-Funktion ausgewählt wird.

Ein regulärer Bloom-Filter unterstützt das Löschen von Elementen nicht, dies ist jedoch für den Bloom-Index nicht erforderlich: Wenn eine Tabellenzeile gelöscht wird, wird die gesamte Signatur zusammen mit der Indexzeile gelöscht.

Wie üblich besteht ein Update aus dem Löschen der veralteten Zeilenversion und dem Einfügen der neuen (die Signatur wird von Grund auf neu berechnet).

Scannen

Da der Bloom-Filter nur die Mitgliedschaft eines Elements in einer Gruppe überprüfen kann, ist die einzige vom Bloom-Index unterstützte Operation eine Gleichheitsprüfung (wie im Hash-Index).

Wie bereits erwähnt, ist der Bloom-Index flach, sodass er im Verlauf des Indexzugriffs immer nacheinander und vollständig gelesen wird. Während des Lesens wird eine Bitmap erstellt, die dann für den Zugriff auf die Tabelle verwendet wird.

Bei einem regulären Indexzugriff wird davon ausgegangen, dass nur wenige Indexzeilen gelesen werden müssen und außerdem bald wieder benötigt werden können. Daher werden sie in einem Puffercache gespeichert. Das Lesen des Bloom-Index ist jedoch tatsächlich ein sequentieller Scan. Um zu verhindern, dass nützliche Informationen aus dem Cache entfernt werden, erfolgt das Lesen über einen kleinen Pufferring, genau wie beim sequentiellen Scannen von Tabellen.

Wir sollten berücksichtigen, dass je größer der Bloom-Index ist, desto weniger attraktiv erscheint er dem Planer. Diese Abhängigkeit ist im Gegensatz zu baumartigen Indizes linear.

Beispiel

Tabelle

Schauen wir uns den Bloom-Index anhand eines Beispiels einer großen "flights_bi" -Tabelle aus dem vorherigen Artikel an . Zur Erinnerung: Die Größe dieser Tabelle beträgt 4 GB mit ungefähr 30 Millionen Zeilen. Definition der Tabelle:

 demo=# \d flights_bi 

  Table "bookings.flights_bi" Column | Type | Collation | Nullable | Default --------------------+--------------------------+-----------+----------+--------- airport_code | character(3) | | | airport_coord | point | | | airport_utc_offset | interval | | | flight_no | character(6) | | | flight_type | text | | | scheduled_time | timestamp with time zone | | | actual_time | timestamp with time zone | | | aircraft_code | character(3) | | | seat_no | character varying(4) | | | fare_conditions | character varying(10) | | | passenger_id | character varying(20) | | | passenger_name | text | | | 

Lassen Sie uns zunächst die Erweiterung erstellen: Obwohl der Bloom-Index in einer Standardlieferung ab Version 9.6 enthalten ist, ist er standardmäßig nicht verfügbar.

 demo=# create extension bloom; 

Das letzte Mal konnten wir drei Felder mit BRIN indizieren ("Scheduled_time", "Actual_time", "Airport_utc_offset"). Da Bloom-Indizes nicht von der physischen Reihenfolge der Daten abhängen, versuchen wir, fast alle Felder der Tabelle in den Index aufzunehmen. Lassen Sie uns jedoch die Zeitfelder ("geplante_Zeit" und "tatsächliche_Zeit") ausschließen: Die Methode unterstützt nur den Vergleich auf Gleichheit, aber eine Abfrage nach der genauen Zeit ist für niemanden interessant (wir könnten den Index jedoch auf einem Ausdruck aufbauen und den runden Zeit bis zu einem Tag, aber wir werden das nicht tun). Wir müssen auch die geografischen Koordinaten von Flughäfen ausschließen ("Airport_Coord"): Mit Blick auf die Zukunft wird der Typ "Punkt" nicht unterstützt.

Um die Parameterwerte auszuwählen, setzen wir die Wahrscheinlichkeit eines falsch positiven Ergebnisses auf 0,01 (wobei zu berücksichtigen ist, dass wir tatsächlich mehr erhalten). Die obigen Formeln für $$$n = 9$ und $$$N = 30 \, 000 \, $ 00$ Geben Sie die Signaturgröße von 96 Bit an und schlagen Sie vor, 7 Bit pro Element festzulegen. Die geschätzte Größe des Index beträgt 515 MB (ungefähr ein Achtel der Tabelle).

(Bei einer minimalen Signaturgröße von 16 Bit versprechen die Formeln eine Indexgröße, die doppelt so klein ist, erlauben jedoch, sich nur auf die Wahrscheinlichkeit von 0,5 zu verlassen, was sehr schlecht ist.)

Operatorklassen

Versuchen wir also, den Index zu erstellen.

 demo=# create index flights_bi_bloom on flights_bi using bloom(airport_code, airport_utc_offset, flight_no, flight_type, aircraft_code, seat_no, fare_conditions, passenger_id, passenger_name) with (length=96, col1=7, col2=7, col3=7, col4=7, col5=7, col6=7, col7=7, col8=7, col9=7); 

 ERROR: data type character has no default operator class for access method "bloom" HINT: You must specify an operator class for the index or define a default operator class for the data type. 

Leider bietet uns die Erweiterung nur zwei Operatorklassen:

 demo=# select opcname, opcintype::regtype from pg_opclass where opcmethod = (select oid from pg_am where amname = 'bloom') order by opcintype::regtype::text; 

  opcname | opcintype ----------+----------- int4_ops | integer text_ops | text (2 rows) 

Glücklicherweise ist es ziemlich einfach, ähnliche Klassen auch für andere Datentypen zu erstellen. Eine Operatorklasse für die Bloom-Zugriffsmethode muss genau einen Operator - Gleichheit - und genau ein Hilfsfunktions-Hashing enthalten. Der einfachste Weg, die benötigten Operatoren und Funktionen für einen beliebigen Typ zu finden, besteht darin, im Systemkatalog nach Operatorklassen der "Hash" -Methode zu suchen:

 demo=# select distinct opc.opcintype::regtype::text, amop.amopopr::regoperator, ampr.amproc from pg_am am, pg_opclass opc, pg_amop amop, pg_amproc ampr where am.amname = 'hash' and opc.opcmethod = am.oid and amop.amopfamily = opc.opcfamily and amop.amoplefttype = opc.opcintype and amop.amoprighttype = opc.opcintype and ampr.amprocfamily = opc.opcfamily and ampr.amproclefttype = opc.opcintype order by opc.opcintype::regtype::text; 

  opcintype | amopopr | amproc -----------+----------------------+-------------- abstime | =(abstime,abstime) | hashint4 aclitem | =(aclitem,aclitem) | hash_aclitem anyarray | =(anyarray,anyarray) | hash_array anyenum | =(anyenum,anyenum) | hashenum anyrange | =(anyrange,anyrange) | hash_range ... 

Mit diesen Informationen erstellen wir zwei fehlende Klassen:

 demo=# CREATE OPERATOR CLASS character_ops DEFAULT FOR TYPE character USING bloom AS OPERATOR 1 =(character,character), FUNCTION 1 hashbpchar; demo=# CREATE OPERATOR CLASS interval_ops DEFAULT FOR TYPE interval USING bloom AS OPERATOR 1 =(interval,interval), FUNCTION 1 interval_hash; 

Eine Hash-Funktion ist für Punkte nicht definiert (Typ "Punkt"). Aus diesem Grund können wir keinen Bloom-Index für ein solches Feld erstellen (genau wie wir keinen Hash-Join für Felder dieses Typs durchführen können).

Ich versuche es noch einmal:

 demo=# create index flights_bi_bloom on flights_bi using bloom(airport_code, airport_utc_offset, flight_no, flight_type, aircraft_code, seat_no, fare_conditions, passenger_id, passenger_name) with (length=96, col1=7, col2=7, col3=7, col4=7, col5=7, col6=7, col7=7, col8=7, col9=7); 

 CREATE INDEX 

Die Größe des Index beträgt 526 MB, was etwas größer als erwartet ist. Dies liegt daran, dass die Formel den Seitenaufwand nicht berücksichtigt.

 demo=# select pg_size_pretty(pg_total_relation_size('flights_bi_bloom')); 

  pg_size_pretty ---------------- 526 MB (1 row) 

Abfragen

Wir können jetzt die Suche nach verschiedenen Kriterien durchführen, und der Index wird dies unterstützen.

Wie bereits erwähnt, ist der Bloom-Filter eine probabilistische Struktur, daher hängt die Effizienz stark von jedem Einzelfall ab. Schauen wir uns zum Beispiel die Zeilen an, die sich auf zwei Passagiere beziehen, Miroslav Sidorov:

 demo=# explain(costs off,analyze) select * from flights_bi where passenger_name='MIROSLAV SIDOROV'; 

  QUERY PLAN -------------------------------------------------------------------------------------------------- Bitmap Heap Scan on flights_bi (actual time=2639.010..3010.692 rows=2 loops=1) Recheck Cond: (passenger_name = 'MIROSLAV SIDOROV'::text) Rows Removed by Index Recheck: 38562 Heap Blocks: exact=21726 -> Bitmap Index Scan on flights_bi_bloom (actual time=1065.191..1065.191 rows=38564 loops=1) Index Cond: (passenger_name = 'MIROSLAV SIDOROV'::text) Planning time: 0.109 ms Execution time: 3010.736 ms 

und Marfa Soloveva:

 demo=# explain(costs off,analyze) select * from flights_bi where passenger_name='MARFA SOLOVEVA'; 

  QUERY PLAN --------------------------------------------------------------------------------------------------- Bitmap Heap Scan on flights_bi (actual time=9980.884..10142.684 rows=2 loops=1) Recheck Cond: (passenger_name = 'MARFA SOLOVEVA'::text) Rows Removed by Index Recheck: 3950168 Heap Blocks: exact=45757 lossy=67332 -> Bitmap Index Scan on flights_bi_bloom (actual time=1037.588..1037.588 rows=212972 loops=1) Index Cond: (passenger_name = 'MARFA SOLOVEVA'::text) Planning time: 0.157 ms Execution time: 10142.730 ms 

In einem Fall erlaubte der Filter nur 40.000 Fehlalarme und bis zu 4 Millionen davon im anderen Fall ("Durch Indexüberprüfung entfernte Zeilen"). Die Ausführungszeiten der Abfragen unterscheiden sich entsprechend.

Das Folgende sind die Ergebnisse der Suche in denselben Zeilen nach der Passagier-ID und nicht nach dem Namen. Miroslav:

 demo=# explain(costs off,analyze) demo-# select * from flights_bi where passenger_id='5864 006033'; 

  QUERY PLAN ------------------------------------------------------------------------------------------------- Bitmap Heap Scan on flights_bi (actual time=13747.305..16907.387 rows=2 loops=1) Recheck Cond: ((passenger_id)::text = '5864 006033'::text) Rows Removed by Index Recheck: 9620258 Heap Blocks: exact=50510 lossy=165722 -> Bitmap Index Scan on flights_bi_bloom (actual time=937.202..937.202 rows=426474 loops=1) Index Cond: ((passenger_id)::text = '5864 006033'::text) Planning time: 0.110 ms Execution time: 16907.423 ms 

Und Marfa:

 demo=# explain(costs off,analyze) select * from flights_bi where passenger_id='2461 559238'; 

  QUERY PLAN -------------------------------------------------------------------------------------------------- Bitmap Heap Scan on flights_bi (actual time=3881.615..3934.481 rows=2 loops=1) Recheck Cond: ((passenger_id)::text = '2461 559238'::text) Rows Removed by Index Recheck: 30669 Heap Blocks: exact=27513 -> Bitmap Index Scan on flights_bi_bloom (actual time=1084.391..1084.391 rows=30671 loops=1) Index Cond: ((passenger_id)::text = '2461 559238'::text) Planning time: 0.120 ms Execution time: 3934.517 ms 

Die Wirkungsgrade sind wieder sehr unterschiedlich, und diesmal hatte Marfa mehr Glück.

Beachten Sie, dass die Suche nach zwei Feldern gleichzeitig wesentlich effizienter ist, da die Wahrscheinlichkeit eines falschen Positivs besteht $$$p$ verwandelt sich in $$$p ^ 2$ ::

 demo=# explain(costs off,analyze) select * from flights_bi where passenger_name='MIROSLAV SIDOROV' and passenger_id='5864 006033'; 

  QUERY PLAN -------------------------------------------------------------------------------------------------------------------- Bitmap Heap Scan on flights_bi (actual time=872.593..877.915 rows=2 loops=1) Recheck Cond: (((passenger_id)::text = '5864 006033'::text) AND (passenger_name = 'MIROSLAV SIDOROV'::text)) Rows Removed by Index Recheck: 357 Heap Blocks: exact=356 -> Bitmap Index Scan on flights_bi_bloom (actual time=832.041..832.041 rows=359 loops=1) Index Cond: (((passenger_id)::text = '5864 006033'::text) AND (passenger_name = 'MIROSLAV SIDOROV'::text)) Planning time: 0.524 ms Execution time: 877.967 ms 

Die Suche mit Booleschem "oder" wird jedoch überhaupt nicht unterstützt. Dies ist eher eine Einschränkung eines Planers als der Zugriffsmethode. Natürlich bleibt eine Option, den Index zweimal zu lesen, zwei Bitmaps zu erstellen und diese zu verbinden, aber dies ist höchstwahrscheinlich zu kostspielig, um diesen Plan auszuwählen.

Vergleich mit BRIN und Hash

Die Anwendungsbereiche der Bloom- und BRIN-Indizes überschneiden sich offensichtlich. Dies sind große Tabellen, für die es wünschenswert ist, die Suche nach verschiedenen Feldern sicherzustellen, wobei die Suchgenauigkeit der Kompaktheit geopfert wird.

BRIN-Indizes sind kompakter (in unserem Beispiel beispielsweise um bis zu Dutzende Megabyte) und können die Suche nach Bereich unterstützen, weisen jedoch eine starke Einschränkung in Bezug auf die physische Reihenfolge der Daten in einer Datei auf. Bloom-Indizes sind größer (Hunderte von Megabyte), haben jedoch keine Einschränkungen, außer der Verfügbarkeit einer geeigneten Hash-Funktion.

Wie Bloom-Indizes unterstützen Hash-Indizes die einzige Operation der Gleichheitsprüfung. Der Hash-Index stellt die Suchgenauigkeit sicher, auf die Bloom nicht zugreifen kann, die Indexgröße ist jedoch viel größer (in unserem Beispiel ein Gigabyte für nur ein Feld, und der Hash-Index kann nicht für mehrere Felder erstellt werden).

Eigenschaften

Schauen wir uns wie gewohnt die Eigenschaften von Bloom an (Abfragen wurden bereits bereitgestellt ).

Im Folgenden sind die Eigenschaften der Zugriffsmethode aufgeführt:

  amname | name | pg_indexam_has_property --------+---------------+------------------------- bloom | can_order | f bloom | can_unique | f bloom | can_multi_col | t bloom | can_exclude | f 

Offensichtlich ermöglicht uns die Zugriffsmethode, einen Index für mehrere Spalten zu erstellen. Es ist kaum sinnvoll, einen Bloom-Index für eine Spalte zu erstellen.

Die folgenden Indexschicht-Eigenschaften sind verfügbar:

  name | pg_index_has_property ---------------+----------------------- clusterable | f index_scan | f bitmap_scan | t backward_scan | f 

Die einzige verfügbare Scan-Technik ist der Bitmap-Scan. Da der Index immer vollständig gescannt wird, ist es nicht sinnvoll, einen regulären Indexzugriff zu implementieren, der Zeilen TID für TID zurückgibt.

  name | pg_index_column_has_property --------------------+------------------------------ asc | f desc | f nulls_first | f nulls_last | f orderable | f distance_orderable | f returnable | f search_array | f search_nulls | f 

Hier sind nur Striche; Die Methode kann nicht einmal NULL-Werte manipulieren.

Und zum Schluss:

Es ist nicht unmöglich, dass diese Artikelserie in Zukunft fortgesetzt wird, wenn neue interessante Indexarten auftauchen, aber es ist Zeit, jetzt aufzuhören.

Ich möchte meinen Kollegen von Postgres Professional (einige von ihnen sind die Autoren vieler besprochener Zugriffsmethoden) dafür danken, dass sie die Entwürfe gelesen und ihre Kommentare abgegeben haben. Und ich bin Ihnen natürlich dankbar für Ihre Geduld und Ihre wertvollen Kommentare. Ihre Aufmerksamkeit hat mich ermutigt, diesen Punkt zu erreichen. Danke!