Zrozumienie „skanowania stosu bitmap” i „skanowania indeksu bitmapy”

Spróbuję wyjaśnić moje nieporozumienia następującym przykładem.

I nie rozumiem podstaw Spośród Bitmap Heap Scan Node. Rozważ zapytanie, SELECT customerid, username FROM customers WHERE customerid < 1000 AND username <'user100';którego plan jest następujący:

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)

Moje rozumienie tego węzła :

Jak wyjaśniono tam , bitmap heap scanodczytuje bloki tabeli w kolejności sekwencyjnej, więc nie generuje narzutu związanego z dostępem do tabeli losowej, co dzieje się tak, jak w przypadku zwykłego Index Scan.

Po wykonaniu Index Scantej czynności PostgreSQL nie wie, jak optymalnie pobrać wiersze, aby uniknąć niepotrzebnego heap blocks reads(lub hitsjeśli istnieje gorąca pamięć podręczna). Aby to rozgryźć, generuje wywołaną strukturę ( Bitmap Index Scan), bitmapktóra w moim przypadku jest generowana przez wygenerowanie dwóch bitmap indeksów i wykonanie BITWISE AND. Ponieważ bitmapa została wygenerowana, może teraz optymalnie odczytywać tabelę w kolejności sekwencyjnej, unikając niepotrzebnych heap I/O-operations.

To miejsce, gdzie pojawia się wiele pytań.

PYTANIE: Mamy tylko mapę bitową. Skąd PostgreSQL za pomocą mapy bitowej wie cokolwiek o fizycznej kolejności wierszy? Czy generuje mapę bitową, aby każdy jej element można było łatwo mapować na wskaźnik do strony? Jeśli tak, to wszystko wyjaśnia, ale to tylko moje przypuszczenia.

Czy możemy więc powiedzieć po prostu, że bitmap heap scan -> bitmap index scanjest to skanowanie sekwencyjne, ale tylko odpowiedniej części tabeli?

Skąd PostgreSQL za pomocą mapy bitowej wie cokolwiek o fizycznej kolejności wierszy?

Bitmapa to jeden bit na stronę sterty. Skanowanie indeksu bitmap ustawia bity na podstawie adresu strony sterty, na który wskazuje wpis indeksu.

Więc jeśli chodzi o skanowanie stosu bitmap, po prostu wykonuje liniowy skan tabeli, odczytuje mapę bitową, aby zobaczyć, czy powinna zawracać sobie głowę daną stroną, czy ją przeszukiwać.

Czy generuje mapę bitową, aby każdy jej element można było łatwo mapować na wskaźnik do strony?

Nie, mapa bitowa odpowiada stronom 1: 1.

Tutaj napisałem o tym więcej .

OK, wygląda na to, że możesz nie rozumieć, co w tym kontekście oznacza „bitmapa”.

Nie jest to ciąg bitowy, taki jak „101011”, który jest tworzony dla każdej strony sterty, każdego odczytanego indeksu lub cokolwiek innego.

Cała mapa bitowa jest tablicą jednobitową z tyloma bitami, ile jest skanowanych stron stosu.

Jedna bitmapa jest tworzona przez pierwsze skanowanie indeksu, zaczynając od wszystkich wpisów 0 (fałsz). Za każdym razem, gdy zostanie znaleziony wpis indeksu pasujący do warunku wyszukiwania, adres sterty wskazywany przez ten wpis indeksu jest sprawdzany jako przesunięcie w mapie bitowej, a ten bit jest ustawiany na 1 (prawda). Zamiast bezpośrednio patrzeć na stronę sterty, skanowanie indeksu bitmap szuka odpowiedniej pozycji bitu na mapie bitowej.

Drugie i kolejne skany indeksu bitmapowego robią to samo z innymi indeksami i warunkami wyszukiwania na nich.

Następnie każda mapa bitowa jest ANDed razem. Powstała bitmapa ma jeden bit dla każdej strony sterty, przy czym bity są prawdziwe tylko wtedy, gdy były prawdziwe we wszystkich pojedynczych skanach indeksu bitmap, tj. Warunek wyszukiwania dopasowany dla każdego skanu indeksu. To jedyne strony stron, które musimy zawracać sobie głowy ładowaniem i sprawdzaniem. Ponieważ każda strona sterty może zawierać wiele wierszy, musimy następnie sprawdzić każdy wiersz, aby sprawdzić, czy spełnia on wszystkie warunki - na tym właśnie polega część „ponownie sprawdzaj warunek”.

Jedną z kluczowych rzeczy, które należy zrozumieć, jest to, że adres krotki we wpisie indeksu wskazuje na wiersz ctid, który jest kombinacją numeru strony sterty i przesunięcia w obrębie strony sterty. Skanowanie indeksu bitmap ignoruje przesunięcia, ponieważ i tak sprawdzi całą stronę i ustawi bit, jeśli jakikolwiek wiersz na tej stronie spełni warunek.

Przykład graficzny

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
+---------------------------------------------+

Po utworzeniu map bitowych wykonywane jest na nich bitowe AND:

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

Skanowanie sterty map bitowych następnie wyszukuje początek każdej strony i odczytuje stronę:

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

i każda czytana strona jest następnie ponownie sprawdzana pod kątem warunku, ponieważ może istnieć> 1 wiersz na stronie i niekoniecznie wszystkie pasują do warunku.

Zapoznaj się z moim postem na blogu https://rajeevrastogi.blogspot.in/2018/02/bitmap-scan-in-postgresql.html?showComment=1518410565792#c4647352762092142586, aby uzyskać szczegółowe informacje na temat skanowania mapy bitowej w PostgreSQL.

Ogólny szybki przegląd funkcji skanowania bitmapy:

1. Skanowanie stosu bitmap prosi o krotkę ze skanowania indeksu bitmap.

2. Skanowanie indeksu bitmap skanuje indeks zgodnie z warunkami prawie w taki sam sposób, jak w normalnym skanowaniu indeksu. Ale zamiast zwracać TID (składający się z numeru strony i przesunięcia w nim) odpowiadającego danym sterty, dodaje te TID w mapie bitowej. Aby ułatwić zrozumienie, można rozważyć, że ta mapa bitowa zawiera skrót wszystkich stron (skrót w oparciu o nr strony), a każda pozycja strony zawiera tablicę wszystkich przesunięć w obrębie tej strony.

3. Następnie Skan Sterty Bitmap odczytuje mapę bitową, aby uzyskać dane sterty odpowiadające zapisanemu numerowi strony i przesunięciu. Następnie sprawdza widoczność, kwalifikacje itp. I zwraca krotkę na podstawie wyników wszystkich tych kontroli.