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

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?

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.

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.