
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/