Co to jest „skanowanie sterty bitmap” w planie kwerend?

113

Chcę poznać zasadę „skanowania sterty bitmap”, wiem, że to się często zdarza, gdy wykonuję zapytanie z ORwarunkiem.

Kto może wyjaśnić zasadę działania „skanowania sterty mapy bitowej”?

franki
źródło

Odpowiedzi:

122

Najlepsze wyjaśnienie pochodzi od Toma Lane'a , który jest autorem algorytmu, chyba że się mylę. Zobacz także artykuł na Wikipedii .

Krótko mówiąc, to trochę jak skanowanie sekwencyjne. Różnica polega na tym, że zamiast odwiedzać każdą stronę dysku, indeks bitmapowy skanuje razem odpowiednie indeksy AND i OR i odwiedza tylko te strony dysku, które są potrzebne.

Różni się to od skanowania indeksu, w którym indeks jest odwiedzany wiersz po wierszu w kolejności - co oznacza, że ​​strona dysku może być odwiedzana wiele razy.


Re: pytanie w twoim komentarzu ... Tak, to jest to.

Skanowanie indeksu przejdzie przez kolejne wiersze, otwierając ponownie strony na dysku tyle razy, ile będzie to konieczne (niektóre oczywiście pozostaną w pamięci, ale o co chodzi).

Skanowanie indeksu mapy bitowej po kolei otworzy krótką listę stron dysku i pobierze każdy odpowiedni wiersz w każdym z nich (stąd tak zwany warunek ponownego sprawdzenia, który widzisz w planach zapytań).

Na marginesie należy zwrócić uwagę, jak grupowanie / kolejność wierszy wpływa na koszty powiązane z każdą z metod. Jeśli wiersze są rozmieszczone w losowej kolejności, indeks bitmapy będzie tańszy. (I faktycznie, jeśli są naprawdę wszędzie , skanowanie sekwencyjne będzie najtańsze, ponieważ skanowanie indeksu mapy bitowej nie jest pozbawione narzutu).

Denis de Bernardy
źródło
Zatem „Skanowanie sterty bitmap”: Strona nie może być odwiedzana więcej niż jeden raz! ale „Index Can”: Stronę można odwiedzać więcej niż jeden raz, ponieważ indeks jest odwiedzany wiersz po wierszu w kolejności.
franki
Prawdopodobnie w przypadku wielokrotnego odwiedzania stron występuje buforowanie: strona zostanie faktycznie załadowana z dysku za pierwszym razem (wolno), a dalszy dostęp dotrze do pamięci podręcznej w pamięci (pamięć podręczna Postgres (szybka) lub pamięć podręczna systemu operacyjnego (szybsza)) .
Matthieu
Istnieje również index-only scansytuacja, w której w zapytaniu jest dostępna tylko indeksowana kolumna. w tym przypadku index-only scannie ma potrzeby dostępu do danych sterty (strony danych): postgresql.org/docs/12/indexes-index-only-scans.html
Alan