Typy indeksów w PostgreSQL. Bloom – kontra dla B-tree?

Dobrze zaprojektowana baza oparta o relacyjny system zarządzania powinna w jakimś (i to raczej w większym) stopniu uwzględniać postulaty Edgara F. Codda – także te dotyczące postaci normalnych. Respektowanie tych założeń powoduje powstanie w strukturze tabel przechowujących klucze główne do wielu innych tabel. Tabele te są bardzo często przeszukiwane – np. podczas filtrowania. Warto zatem zadbać o ich optymalizację pod tym kątem. Artykuł ten porównuje wydajność dwóch indeksów: b-tree oraz bloom na silniku PostgreSQL w wersji 10.

Dobrze zaprojektowana baza oparta o relacyjny system zarządzania powinna w jakimś (i to raczej w większym) stopniu uwzględniać postulaty Edgara F. Codda – także te dotyczące postaci normalnych. Respektowanie tych założeń powoduje powstanie w strukturze tabel przechowujących klucze główne do wielu innych tabel. Tabele te są bardzo często przeszukiwane – np. podczas filtrowania. Warto zatem zadbać o ich optymalizację pod tym kątem. Artykuł ten porównuje wydajność dwóch indeksów: b-tree oraz bloom na silniku PostgreSQL w wersji 10.

Zarys technologiczny

Bloom index (od PostgreSQL 9.6) jest implementacją filtru stworzonego przez Burtona H. Blooma w 1970 roku w ramach rodzącej się koncepcji matematycznego podejścia do danych. Jest tablicą m bitów przewidującą istnienie n elementów, które to elementy zostały zakodowane k funkcjami haszującymi. Jest to wydajna struktura, jednak ryzykiem jest pojawienie się wyników false postive – innymi słowy dla danego elementu jesteśmy w stanie z całkowitą pewnością stwierdzić, że nie istnieje on w zadanym zbiorze lub że prawdopodobnie istnieje (ale to z kolei pewne nie jest). Stopień ryzyka jest zależny od m, czyli ilości bitów, na których przechowujemy informację – im więcej dedykujemy przestrzeni, tym mniejszy margines błędów.
Indeks ten w PostgreSQL jest dedykowany jako indeks wielokolumnowy, stosowany przy typach danych int4 oraz text. Jedynym operatorem wspieranym przez ten typ indeksu jest =.

B-tree (B-drzewo, drzewiasta struktura danych) od dawna znajduje zastosowanie w bazach danych, a w wielu silnikach (w tym w PostgreSQL) stanowi domyślny rodzaj indeksu. Centralnym ośrodkiem koncepcji jest struktura wewnętrznego węzła. Każdy z węzłów może posiadać od M+1 do 2*M+1 węzłów potomnych (gdzie M to rząd B-drzewa) co rzutuje na stosunkowo niską wysokość drzewa (rzędu logMn) oraz bezpośrednio powoduje, że liczba węzłów, które trzeba odczytać lub zapisać jest niewielka. Cecha ta odróżnia B-tree od binary search tree oraz stanowi optymalizację pod operacje I/O. Naturalną konsekwencją utworzenia indeksu B-tree jest to, że nasze dane są posortowane według zaindeksowanej kolumny.

Implementacja w PostgreSQL dotyczy danych każdego typu. Indeks obsługuje operatory porównania (<, <=, =, >=, >), odpowiedniki składniowe będące ich połączeniem (BETWEEN, IN) i klauzule IS NULL or IS NOT NULL. Proces optimizer będzie używać tego indeksu także przy zapytaniach zawierających polecenie LIKE, ale tylko w wypadku gdy poszukiwany wzorzec posiada na sztywno zakotwiczony początek (np. LIKE 'foo%'). Indeks może być indeksem wielokolumnowym.

Metryka testów

Na potrzeby testów powstały 4 tabele, każda posiadająca 8 kolumn o typie danych int. Każdą zaindeksowaną w inny sposób:

CREATE TABLE t_bloom_default (
    c1 serial 
    , c2 int
    , c3 int
    , c4 int
    , c5 int
    , c6 int
    , c7 int
    , c8 int
);
CREATE INDEX idx_bloom_default 
    ON t_bloom_default
    USING bloom (c2, c3, c4, c5, c6, c7, c8);

Indeks bloom utworzono z domyślnymi parametrami

CREATE TABLE t_bloom_optimized (
    c1 serial 
    , c2 int
    , c3 int
    , c4 int
    , c5 int
    , c6 int
    , c7 int
    , c8 int
);
CREATE INDEX idx_bloom_optimized
    ON t_bloom_optimized
    USING bloom (c2, c3, c4, c5, c6, c7, c8) 
    WITH (length=200,col2=10,col3=10,col4=10,col5=10,col6=10,col7=10,col8=10);

Indeks bloom utworzono ze zwiększonym rozmiarem sygnatury oraz ilością bitów dla kolumn

CREATE TABLE t_btree_multicol (
    c1 serial 
    , c2 int
    , c3 int
    , c4 int
    , c5 int
    , c6 int
    , c7 int
    , c8 int
);
CREATE INDEX idx_btree_multicol
    ON t_btree_multicol (c2, c3, c4, c5, c6, c7, c8);

Artykuł ten porównujeIndeks b-tree został utworzony dla wszystkich kolumn jednym zapytaniem

CREATE TABLE t_btree_separated (
    c1 serial 
    , c2 int
    , c3 int
    , c4 int
    , c5 int
    , c6 int
    , c7 int
    , c8 int
);
CREATE INDEX idx_btree_separated_c2 
    ON t_btree_separated(c2);
CREATE INDEX idx_btree_separated_c3 
    ON t_btree_separated(c3);
CREATE INDEX idx_btree_separated_c4 
    ON t_btree_separated(c4);
CREATE INDEX idx_btree_separated_c5 
    ON t_btree_separated(c5);
CREATE INDEX idx_btree_separated_c6 
    ON t_btree_separated(c6);
CREATE INDEX idx_btree_separated_c7 
    ON t_btree_separated(c7);
CREATE INDEX idx_btree_separated_c8 
    ON t_btree_separated(c8);

Dla każdej kolumny indeks b-tree został utworzony osobno

Tabele zostały zasilone takim samym zestawem danych, wygenerowanych za pomocą euro-datagenerator. Badanie następowało za pomocą zapytania:

SELECT * FROM [nazwa_tabeli] where c3 = 462299 AND c5 = 384328;

Zapytanie wykonano 30 razy dla każdej tabeli. Przed każdym zapytaniem testowym następował restart silnika, a następnie zapytanie:

ANALYZE [nazwa_tabeli];

Aby wymusić używanie indeksów, parametr enable_seqscan ustawiono na false (jest to szczególnie istotne przy zoptymalizowanym indeksie bloom – prawdopodobnie ze względu na jego wielkość silnik „uznaje”, że skan sekwencyjny okaże się szybszy).

Wyniki:

TABELA t_btree_separated t_bloom_optimized t_bloom_default t_btree_multicol
ŚREDNI CZAS [ms] 1.54 14.33 16.55 63.50
MAKSYMALNY CZAS [ms] 2.68 22.24 27.22 77.69
MINIMALNY CZAS [ms] 1.16 12.46 14.96 58.46
MEDIANA CZASU [ms] 1.50 13.95 16.23 62.29
(SUMARYCZNY) ROZMIAR INDEKSÓW [MB] (7 * ~28) = 196 31 15 48

 

Na wynik indeksu b-tree, zakładanego na każdą kolumnę osobno, niewątpliwie wpływ ma fakt, że rekordy z warunkiem c3 = 462299 były w zestawie danych zaledwie dwa. Mechanizm polegał bowiem na użyciu tylko indeksu założonego na tę właśnie kolumnę, a następnie sekwencyjnym odfiltrowaniu rekordów niepasujących do drugiego warunku logicznego:

QUERY PLAN
Index Scan using idx_btree_separated_c5 on t_btree_separated
(cost=0.42..12.46 rows=1 width=32)
(actual time=0.066..0.066 rows=0 loops=1)
Index Cond: (c5 = 384328)
Filter: (c3 = 462299)Metryka testów
Rows Removed by Filter: 2
Planning time: 0.274 ms
Execution time: 0.085 ms

To, co spowalnia dość mocno indeks bloom przy domyślnych ustawieniach, to konieczność usunięcia rekordów false positive:

QUERY PLAN
Bitmap Heap Scan on t_bloom_default
(cost=17848.00..17852.02 rows=1 width=32)
(actual time=16.012..16.012 rows=0 loops=1)
Recheck Cond: ((c3 = 462299) AND (c5 = 384328))
Rows Removed by Index Recheck: 790
Heap Blocks: exact=748
-> Bitmap Index Scan on idx_bloom_default
(cost=0.00..17848.00 rows=1 width=0)
(actual time=9.839..9.839 rows=790 loops=1)
Index Cond: ((c3 = 462299) AND (c5 = 384328))
Planning time: 0.296 ms
Execution time: 16.058 ms

Optymalizacja indeksu sprawia jednak, że tego typu błędy się nie pojawiają:

QUERY PLAN
Bitmap Heap Scan on t_bloom_optimized
(cost=25692.00..25696.02 rows=1 width=32)
(actual time=12.460..12.460 rows=0 loops=1)
Recheck Cond: ((c3 = 462299) AND (c5 = 384328))
-> Bitmap Index Scan on idx_bloom_optimized
(cost=0.00..25692.00 rows=1 width=0)
(actual time=12.456..12.456 rows=0 loops=1)
Index Cond: ((c3 = 462299) AND (c5 = 384328))
Planning time: 0.166 ms
Execution time: 12.511 ms

To, co wydaje się równie istotnym wynikiem testów, to bardzo niska wydajność indeksu b-tree przy założeniu go na wielu kolumnach:

QUERY PLAN
Index Only Scan using idx_btree_multicol on t_btree_multicol
(cost=0.42..34608.44 rows=1 width=32)
(actual time=63.501..63.501 rows=0 loops=1)
Index Cond: ((c3 = 462299) AND (c5 = 384328))
Heap Fetches: 0
Planning time: 0.285 ms
Execution time: 63.526 ms

Podsumowanie

Oczekiwanym i oczywistym zwycięzcą testów jest indeks b-tree w przypadku zakładania go na każdej kolumnie osobno. Warto jednak zwrócić uwagę, że suma rozmiarów tych indeksów jest równie spektakularna – jest to 196 MB, podczas gdy sama tabela ma rozmiar 57 MB. Tymczasem zoptymalizowany indeks bloom, zajmując 6 razy mniej powierzchni dyskowej, posiada wcale niezłe wyniki – i znacząco lepsze niż (również większy) wielokolumnowy b-tree.

Źródła:
http://ksmigiel.com/2016/06/bloom-filters/
https://en.wikipedia.org/wiki/Bloom_filter
https://en.wikipedia.org/wiki/B-tree
https://www.postgresql.org/docs/10/static/bloom.html
https://www.depesz.com/2016/04/11/waiting-for-9-6-bloom-index-contrib-module/

blank Autorzy

Artykuły na blogu są pisane przez osoby z zespołu EuroLinux. 80% treści zawdzięczamy naszym developerom, pozostałą część przygotowuje dział sprzedaży lub marketingu. Dokładamy starań, żeby treści były jak najlepsze merytorycznie i językowo, ale nie jesteśmy nieomylni. Jeśli zauważysz coś wartego poprawienia lub wyjaśnienia, będziemy wdzięczni za wiadomość.