Grundlegendes zu "Bitmap-Heap-Scan" und "Bitmap-Index-Scan"

36

Ich werde versuchen, meine Missverständnisse anhand des folgenden Beispiels zu erklären.

Ich habe die Grundlagen des nicht verstanden Bitmap Heap Scan Node. Betrachten Sie die Abfrage, SELECT customerid, username FROM customers WHERE customerid < 1000 AND username <'user100';deren Plan wie folgt lautet:

Bitmap Heap Scan on customers  (cost=25.76..61.62 rows=10 width=13) (actual time=0.077..0.077 rows=2 loops=1)
  Recheck Cond: (((username)::text < 'user100'::text) AND (customerid < 1000))
  ->  BitmapAnd  (cost=25.76..25.76 rows=10 width=0) (actual time=0.073..0.073 rows=0 loops=1)
        ->  Bitmap Index Scan on ix_cust_username  (cost=0.00..5.75 rows=200 width=0) (actual time=0.006..0.006 rows=2 loops=1)
              Index Cond: ((username)::text < 'user100'::text)
        ->  Bitmap Index Scan on customers_pkey  (cost=0.00..19.75 rows=1000 width=0) (actual time=0.065..0.065 rows=999 loops=1)
              Index Cond: (customerid < 1000)

Mein Verständnis dieses Knotens :

Wie erklärt es , die bitmap heap scanliest Tabellenblöcke in der angegebenen Reihenfolge, so dass es nicht zufällig-table-Zugang Overhead , die genauso tun geschieht produziert Index Scan.

Nachdem Index Scandies geschehen ist, kann PostgreSQL die Zeilen nicht optimal abrufen, um unnötige Zugriffe zu vermeiden heap blocks reads(oder hitswenn ein Hot-Cache vorhanden ist). Um es herauszufinden, generiert es die Bitmap Index Scanaufgerufene Struktur ( ), bitmapdie in meinem Fall durch Generieren von zwei Bitmaps der Indizes und Ausführen generiert wird BITWISE AND. Da die Bitmap generiert wurde, kann sie jetzt die Tabelle in einer sequentiellen Reihenfolge optimal lesen, ohne dass dies unnötig ist heap I/O-operations.

Das ist der Ort, an dem viele Fragen auftauchen.

FRAGE: Wir haben nur eine Bitmap. Woher weiß PostgreSQL anhand einer Bitmap etwas über die physische Reihenfolge der Zeilen? Oder wird die Bitmap so generiert, dass jedes Element auf einfache Weise dem Zeiger auf eine Seite zugeordnet werden kann? Wenn ja, erklärt das alles, aber es ist nur meine Vermutung.

Können wir also einfach sagen, dass das bitmap heap scan -> bitmap index scanwie ein sequentieller Scan ist, aber nur der entsprechende Teil der Tabelle?

St.Antario
quelle
Ich habe hier eine Erklärung dazu geschrieben: stackoverflow.com/q/33100637/398670
Craig Ringer
@CraigRinger Ich habe anscheinend nicht richtig erklärt, was ich nicht verstanden habe. Natürlich haben wir, wie Sie erklärt haben, eine Bitmap, mit der PostgreSQL die Tabelle nacheinander liest. Ich verstehe nicht, wie es den tatsächlichen Block herausfinden kann, der durch eine bestimmte Bitmap gekennzeichnet wird, z 001001010101011010101. Oder spielt es eigentlich keine Rolle und wir müssen nur wissen, dass es einen Block recht schnell anhand seiner Bitmap finden kann ...?
St.Antario
Ah, Sie könnten missverstehen, was "Bitmap" hier bedeutet. Lassen Sie mich in einer Bearbeitung weiterverfolgen.
Craig Ringer
@CraigRinger Vielleicht habe ich die Definition von dort genommen .
St.Antario

Antworten:

52

Woher weiß PostgreSQL anhand einer Bitmap etwas über die physische Reihenfolge der Zeilen?

Die Bitmap ist ein Bit pro Heap-Seite. Der Bitmap-Index-Scan setzt die Bits basierend auf der Adresse der Heap-Seite, auf die der Indexeintrag zeigt.

Wenn der Bitmap-Heap-Scan ausgeführt wird, wird lediglich ein linearer Tabellenscan ausgeführt, bei dem die Bitmap gelesen wird, um festzustellen, ob sie sich mit einer bestimmten Seite befassen oder darüber suchen soll.

Oder wird die Bitmap so generiert, dass jedes Element auf einfache Weise dem Zeiger auf eine Seite zugeordnet werden kann?

Nein, die Bitmap entspricht 1: 1 Heap-Seiten.

Ich schrieb etwas mehr dazu hier .


OK, es sieht so aus, als ob Sie falsch verstehen, was "Bitmap" in diesem Kontext bedeutet.

Es ist keine Bitfolge wie "101011", die für jede Heap-Seite oder jeden gelesenen Index oder was auch immer erstellt wird.

Die gesamte Bitmap ist ein einzelnes Bit-Array mit so vielen Bits, wie Heap-Seiten in der Beziehung vorhanden sind, die gescannt werden.

Beim ersten Index-Scan wird eine Bitmap erstellt, beginnend mit allen Einträgen 0 (false). Immer wenn ein Indexeintrag gefunden wird, der der Suchbedingung entspricht, wird die Heap-Adresse, auf die dieser Indexeintrag verweist, als Offset in der Bitmap nachgeschlagen und dieses Bit auf 1 (wahr) gesetzt. Anstatt die Heap-Seite direkt nachzuschlagen, sucht der Bitmap-Index-Scan die entsprechende Bitposition in der Bitmap.

Der zweite und weitere Bitmap-Index-Scan machen dasselbe mit den anderen Indizes und den Suchbedingungen für sie.

Dann wird jede Bitmap UND-verknüpft. Die resultierende Bitmap enthält ein Bit für jede Heap-Seite, wobei die Bits nur dann wahr sind, wenn sie in allen einzelnen Bitmap-Index-Scans wahr waren, dh die Suchbedingung für jeden Index-Scan erfüllt ist. Dies sind die einzigen Heap-Seiten, die wir zum Laden und Untersuchen benötigen. Da jede Heap-Seite mehrere Zeilen enthalten kann, müssen wir jede Zeile überprüfen, um festzustellen, ob sie allen Bedingungen entspricht. Darum geht es im Abschnitt "Erneutes Überprüfen von Konditionen".

Bei alledem ist es wichtig zu verstehen, dass die Tupeladresse in einem Indexeintrag auf die Zeilen verweist ctid, die eine Kombination aus der Heap-Seitennummer und dem Versatz innerhalb der Heap-Seite sind. Bei einem Bitmap-Index-Scan werden die Offsets ignoriert, da ohnehin die gesamte Seite überprüft und das Bit gesetzt wird, wenn eine Zeile auf dieser Seite der Bedingung entspricht.


Grafisches Beispiel

Heap, one square = one page:
+---------------------------------------------+
|c____u_____X___u___X_________u___cXcc______u_|
+---------------------------------------------+
Rows marked c match customers pkey condition.
Rows marked u match username condition.
Rows marked X match both conditions.


Bitmap scan from customers_pkey:
+---------------------------------------------+
|100000000001000000010000000000000111100000000| bitmap 1
+---------------------------------------------+
One bit per heap page, in the same order as the heap
Bits 1 when condition matches, 0 if not

Bitmap scan from ix_cust_username:
+---------------------------------------------+
|000001000001000100010000000001000010000000010| bitmap 2
+---------------------------------------------+

Sobald die Bitmaps erstellt sind, wird ein bitweises UND für sie ausgeführt:

+---------------------------------------------+
|100000000001000000010000000000000111100000000| bitmap 1
|000001000001000100010000000001000010000000010| bitmap 2
 &&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
|000000000001000000010000000000000010000000000| Combined bitmap
+-----------+-------+--------------+----------+
            |       |              |
            v       v              v
Used to scan the heap only for matching pages:
+---------------------------------------------+
|___________X_______X______________X__________|
+---------------------------------------------+

Der Bitmap-Heap-Scan sucht dann zum Anfang jeder Seite und liest die Seite:

+---------------------------------------------+
|___________X_______X______________X__________|
+---------------------------------------------+
seek------->^seek-->^seek--------->^
            |       |              |
            ------------------------
            only these pages read

und jede gelesene Seite wird dann erneut gegen die Bedingung geprüft, da es> 1 Zeile pro Seite geben kann und nicht alle notwendigerweise mit der Bedingung übereinstimmen.

Craig Ringer
quelle
Ah, das ist , was sie gemeint bevölkern die Bitmap.
St.Antario
@ St.Antario Ich habe Grafiken hinzugefügt, um zu erklären
Craig Ringer
Lassen Sie mich noch etwas zum Bitmap-Scan sagen. Sie sagten, wir hätten eine 1: 1-Bitmap, um Seiten zu heapen, und wir könnten eine Heap-Seite anhand eines Bitindex in der Bitmap bestimmen. Da die Relation möglicherweise Seiten auf einem Datenträger in einer nicht sequenziellen Reihenfolge enthält (nicht gruppiert), ist nicht ganz klar, wie die Adresse einer Seite durch einfaches Versetzen in einer Bitmap ermittelt werden kann. Ich nehme an, der Planer weiß, wie man eine Seitenadresse für eine gegebene Beziehung durch Offset berechnet . Ist das wahr?
St.Antario
1
Also müssen wir alle Seiten, die sich auf einem Laufwerk befinden, ablegen. Darüber hinaus können die Daten einer Beziehung auf zwei oder mehr Laufwerke verteilt sein (daher ist kaum eine lineare Reihenfolge der Beziehungsseiten vorstellbar ), sodass es schwierig ist, den tatsächlichen Versatz der nächsten Seite zu bestimmen. Weil ich glaube, dass Sie mit "Versatz" den tatsächlichen physischen Versatz gemeint haben, der einer physischen Position auf einem Laufwerk entspricht.
St.Antario
2
PostgreSQL interessiert sich nicht im geringsten für Laufwerke. Es kümmert sich nur um Dateien im Dateisystem . Die logische Datei für die Beziehung ist linear und zusammenhängend, und genau das ist die Bitmap. (Möglicherweise enthält die Datei mehrere Bereiche, diese werden jedoch so behandelt, als würden sie fortlaufend angehängt, und die Bitmap überschreibt alle Bereiche.) Sie suchen auf der falschen Abstraktionsebene. (Nebenbei bemerkt, die Bitmap in einem Bitmap-Index-Scan wird auch nicht vom Planer berechnet, sondern ist Teil der Btree-Index-Zugriffsmethode und eher mit dem Ausführenden als mit dem Planer verbunden.)
Craig Ringer
3

Weitere Informationen zum Bitmap-Scan in PostgreSQL finden Sie in meinem Blog-Beitrag https://rajeevrastogi.blogspot.in/2018/02/bitmap-scan-in-postgresql.html?showComment=1518410565792#c4647352762092142586 .

Allgemeine schnelle Funktionsübersicht des Bitmap-Scans:

  1. Bitmap-Heap-Scan: Fordern Sie ein Tupel von Bitmap Index Scan an.

  2. Bitmap-Index-Scan scannt den Index gemäß der Bedingung fast auf die gleiche Weise wie beim normalen Index-Scan. Anstatt jedoch eine TID (bestehend aus Seitennummer und Offset innerhalb dieser) zurückzugeben, die den Heap-Daten entspricht, werden diese TIDs in eine Bitmap eingefügt. Zum einfacheren Verständnis können Sie davon ausgehen, dass diese Bitmap einen Hash aller Seiten enthält (basierend auf der Seitennummer gehasht) und jeder Seiteneintrag ein Array aller Offsets innerhalb dieser Seite enthält.

  3. Dann liest der Bitmap-Heap-Scan die Bitmap durch, um Heap-Daten zu erhalten, die der gespeicherten Seitenzahl und dem Offset entsprechen. Dann prüft es die Sichtbarkeit, Qualifikation usw. und gibt das Tupel basierend auf dem Ergebnis all dieser Prüfungen zurück.

Rajeev Rastogi
quelle