B-tree i Hash - najpopularniejsze typy indexów (PostgreSQL)

Pamiętacie może post, w którym opisywałam EXPLAIN plan w PostgreSQLu? Mogliście sie w nim dowiedzieć w jaki sposób czytać informację o tym jak optymalizator odczytuje dane z tabel i jakiego rodzaju indexy wybiera,, aby ta praca była efektywna. Jeśli jednak mamy możliwość zmiany lub utworzenia nowego indexu, dobrze wiedzieć jak one działają i jak są zbudowane.

PostgreSQL ma 4 podstawowe typy indexów:

• B-tree
• Hash
• GiST
• GIN

Dwa pierwsze z nich istnieją także w innych popularnych silnikach bazodanowych i ich zasada działania jest podobna. GiST i GIN postaram się omówić w innym poście. Teraz przestawię tylko dwa najpopularniejsze typy indexów.


Na potrzeby tego posta stworzyłam tabelę test_indexes. Zapisane w niej jest 1000 rekordów:

            Table "public.test_indexes"
+--------+-----------------------------+-----------+
| Column |            Type             | Modifiers |
+--------+-----------------------------+-----------+
| c1     | integer                     |           |
| c2     | character varying(10)       |           |
| c3     | integer                     |           |
| c4     | boolean                     |           |
| c5     | text                        |           |
| c6     | integer                     |           |
| c7     | timestamp without time zone |           |
| c8     | date                        |           |
+--------+-----------------------------+-----------+
Indexes:
    "idx_test_c5" btree (c5)
    "idx_test_c6_c1" btree (c6, c1)
    "idx_test_c7_c6" btree (c7, c6)
    "idx_test_c8_c6" btree (c8, c6)
    "idx_test_hash_c2" hash (c2)

Pamiętajmy, że wybierając dane dla jednej tabeli jest możliwe tylko użycie jednego indexu.

B-tree

Najpopularniejszy z indeksów. Jego strukturą danych jest drzewo zbilansowane, czyli zrównoważone - aby dotrzeć do dowolnego liścia drzewa, musisz przejść ścieżkę o podobnej długości.

Tego typu index współpracuje z następującymi operatorami: =, >, >=, <, <=, dlatego jest najbardziej popularny.
Index działa na danych typu tekst i numerycznych, a także od wersji 8.3 jest używany do znajdowania lub pominięcia wartości NULL w tabelach. Przy wyszukiwaniu rekordów na danych tekstowych możemy użyć LIKE ale tylko pod warunkiem, że szukany fragment jest na początku.

127.0.0.1:7432 postgres@test # explain analyze select * from test_indexes where c5 like '4f2b67f9%';
+--------------------------------------------------------------------------------------------------------+
|                                               QUERY PLAN                                               |
+--------------------------------------------------------------------------------------------------------+
| Seq Scan on test_indexes  (cost=0.00..42.50 rows=1 width=69) (actual time=0.015..0.386 rows=1 loops=1) |
|   Filter: (c5 ~~ '4f2b67f9%'::text)                                                                    |
| Total runtime: 0.413 ms                                                                                |
+--------------------------------------------------------------------------------------------------------+
(3 rows)

Time: 0,862 ms

Mam nadzieję, że zauważyliście iż index nie został wykorzystany i aby wykonać to zapytanie, optymalizator zdecydował o skanowaniu całej tabeli. Ale dlaczego?

Jeśli nasza baza danych nie używa C locale (domyślny przy porównaniach znaków w indexach), to index nie jest wykorzystywany. Jeśli pracujemy na juz istniejącej bazie danych możemy sprawdzić jakie locale jestało zaintalowane dla naszej bazy danych przy pomocy polecenia show lc_collate;

127.0.0.1:7432 postgres@test # show lc_collate;
+-------------+
| lc_collate  |
+-------------+
| pl_PL.UTF-8 |
+-------------+
(1 row)

Time: 0,258 ms

Aby sprawdzić dostępne locale naszego systemu operacyjnego na którym działa nasz serwer bazodanowy, wykonujemy polecenie locale:

[ela:/opt/PostgreSQL/9.1 ]$ locale -a
C
en_AG
en_AU.utf8
en_BW.utf8
en_CA.utf8
en_DK.utf8
en_GB.utf8
en_HK.utf8
en_IE.utf8
en_IN
en_NG
en_NZ.utf8
en_PH.utf8
en_SG.utf8
en_US.utf8
en_ZA.utf8
en_ZW.utf8
pl_PL.utf8
POSIX

Locale podawane jest przy instalacji bazy danych (initdb) lub przy tworzeniu bazy danych. Jeśli interesuje was ten temat, odsyłam do dokumentacji tutaj.

Aby stworzyć index bez zmian serwerowych i dodatkowych instalacji, przy tworzeniu indexu podajemy operator klasy:

• text_pattern_ops - dla kolumn typu text
• varchar_pattern_ops - dla kolumn typu varchar, 
• bpchar_pattern_ops - dla kolumn typu char

127.0.0.1:7432 postgres@test # create index idx_test_c5_special on test_indexes (c5 text_pattern_ops);
CREATE INDEX
Time: 81,037 ms
127.0.0.1:7432 postgres@test # explain analyze select * from test_indexes where c5 like '4f2b67f9%';
+-----------------------------------------------------------------------------------------------------------------------------------+
|                                                            QUERY PLAN                                                             |
+-----------------------------------------------------------------------------------------------------------------------------------+
| Index Scan using idx_test_c5_special on test_indexes  (cost=0.00..8.27 rows=1 width=69) (actual time=0.082..0.083 rows=1 loops=1) |
|   Index Cond: ((c5 ~>=~ '4f2b67f9'::text) AND (c5 ~<~ '4f2b67f:'::text))                                                          |
|   Filter: (c5 ~~ '4f2b67f9%'::text)                                                                                               |
| Total runtime: 0.115 ms                                                                                                           |
+-----------------------------------------------------------------------------------------------------------------------------------+
(4 rows)

Time: 1,568 ms

Jeśli szukany wzorzec jest w środku lub na końcu, wiązało by się to z przeszukaniem praktycznie całej struktury drzewa indexu, dlatego nie ma to sensu. Pamiętajmy o tym gdy tworzymy nasze zapytania.

Inny przykład dla operatorów mniejszy i większy:

127.0.0.1:7432 postgres@test # explain select count(*) from test_indexes where c1 between 1 and 30;
+---------------------------------------------------------------------------------+
|                                   QUERY PLAN                                    |
+---------------------------------------------------------------------------------+
| Aggregate  (cost=19.08..19.09 rows=1 width=0)                                   |
|   ->  Bitmap Heap Scan on test_indexes  (cost=4.56..19.01 rows=30 width=0)      |
|         Recheck Cond: ((c1 >= 1) AND (c1 <= 30))                                |
|         ->  Bitmap Index Scan on idx_test_c1  (cost=0.00..4.55 rows=30 width=0) |
|               Index Cond: ((c1 >= 1) AND (c1 <= 30))                            |
+---------------------------------------------------------------------------------+
(5 rows)

Time: 0,549 ms

127.0.0.1:7432 postgres@test # explain select * from test_indexes where c6 between 120 and 200 AND c1 = 3;
+------------------------------------------------------------------------------------+
|                                     QUERY PLAN                                     |
+------------------------------------------------------------------------------------+
| Index Scan using idx_test_c6_c1 on test_indexes  (cost=0.00..9.21 rows=1 width=35) |
|   Index Cond: ((c6 >= 120) AND (c6 <= 200) AND (c1 = 3))                           |
+------------------------------------------------------------------------------------+
(2 rows)

Time: 0,475 ms

Hash

W porównaniu do B-tree, hash index jest używany tylko przy operatorze =. Dodatkowo nie pozwala na wartości NULL.

127.0.0.1:7432 postgres@test # explain select * from test_indexes where c2 = 'b2a90e52ed';
+--------------------------------------------------------------------------------------+
|                                      QUERY PLAN                                      |
+--------------------------------------------------------------------------------------+
| Index Scan using idx_test_hash_c2 on test_indexes  (cost=0.00..8.27 rows=1 width=69) |
|   Index Cond: ((c2)::text = 'b2a90e52ed'::text)                                      |
+--------------------------------------------------------------------------------------+
(2 rows)

Time: 75,145 ms

Podsumowanie

	B-tree	Hash
Operatory	>=,=, >, <, <=	=
Wartości NULL	TAK	NIE

Krótko o samym tworzeniu, usuwaniu i zmianie indexów

Tworzenia indexu:

 CREATE INDEX NAZWA_INDEXU ON NAZWA_TABELI USING INDEX_TYPE (NAZWA_KOLUMNY);

Nazwa indexu musi być unikalna w całym schemacie, a nie tabeli tak jak to jest w MySQL-u.

Usuwanie indexu:

DROP INDEX NAZWA_INDEXU;

Aby zmienić index już istniejący, trzeba go najpierw usunąć i utworzyć na nowo ze zmianami.