Jakiego indeksu używać z wieloma zduplikowanymi wartościami?

Zróbmy kilka założeń:

Mam stół, który wygląda następująco:

 a | b
---+---
 a | -1
 a | 17
  ...
 a | 21
 c | 17
 c | -3
  ...
 c | 22

Fakty na temat mojego zestawu:

• Rozmiar całego stołu wynosi ~ 10 ¹⁰ rzędów.

• Mam ~ 100 tys. Wierszy z wartością aw kolumnie a, podobnie dla innych wartości (np c.).

• Oznacza to ~ 100 000 różnych wartości w kolumnie „a”.

• Większość moich zapytań odczyta wszystkie lub większość wartości danej wartości w np select sum(b) from t where a = 'c'.

• Tabela jest napisana w taki sposób, że kolejne wartości są fizycznie blisko siebie (albo jest zapisywana w kolejności, albo zakładamy, że CLUSTERzostała użyta w tej tabeli i kolumnie a).

• Tabela jest rzadko aktualizowana, ale zależy nam tylko na prędkości odczytu.

• Tabela jest stosunkowo wąska (powiedzmy ~ 25 bajtów na krotkę, + 23 bajty narzut).

Teraz pytanie brzmi: jakiego rodzaju indeksu powinienem używać? Rozumiem:

• BTree Moim problemem jest to, że indeks BTree będzie ogromny, ponieważ o ile wiem, będzie przechowywać zduplikowane wartości (musi, ponieważ nie może założyć, że tabela jest fizycznie posortowana). Jeśli BTree jest ogromny, w końcu muszę przeczytać zarówno indeks, jak i części tabeli, na które wskazuje indeks. (Możemy użyć, fillfactor = 100aby nieco zmniejszyć rozmiar indeksu.)

• BRIN Rozumiem, że mogę tu mieć mały indeks kosztem czytania bezużytecznych stron. Użycie małej pages_per_rangeoznacza, że ​​indeks jest większy (co jest problemem w BRIN, ponieważ muszę przeczytać cały indeks), posiadanie dużego pages_per_rangeoznacza, że ​​przeczytam wiele bezużytecznych stron. Czy istnieje magiczna formuła, która pozwala znaleźć dobrą wartość pages_per_range, biorąc pod uwagę te kompromisy?

• GIN / GiST Nie jestem pewien, czy są one istotne tutaj, ponieważ są one najczęściej używane do wyszukiwania pełnotekstowego, ale słyszę też, że dobrze radzą sobie z duplikatami kluczy. Czy pomoże tu GINalbo GiSTindeks?

Innym pytaniem jest, czy Postgres wykorzysta fakt, że tabela jest CLUSTERedytowana (przy założeniu braku aktualizacji) w narzędziu do planowania zapytań (np. Przez binarne wyszukiwanie odpowiednich stron początkowych / końcowych)? W jakiś sposób spokrewnione, czy mogę po prostu przechowywać wszystkie moje kolumny w BTree i całkowicie upuścić tabelę (lub osiągnąć coś równoważnego, uważam, że są to indeksy klastrowe na serwerze SQL)? Czy jest jakiś hybrydowy indeks BTree / BRIN, który by tu pomógł?

Wolałbym unikać używania tablic do przechowywania moich wartości, ponieważ moje zapytanie skończy się w ten sposób mniej czytelne (rozumiem, że to zmniejszy koszt 23 bajtów narzut narzuty poprzez zmniejszenie liczby krotek).

BTree

Mój problem polega na tym, że indeks BTree będzie ogromny, ponieważ będzie przechowywał zduplikowane wartości (ma też, ponieważ nie może zakładać, że tabela jest fizycznie posortowana). Jeśli BTree jest ogromny, muszę przeczytać zarówno indeks, jak i te części tabeli, które indeks wskazuje również ...

Niekoniecznie - posiadanie indeksu btree „zakrywającego” będzie najszybszym czasem odczytu, a jeśli to wszystko, czego chcesz (tj. Jeśli możesz sobie pozwolić na dodatkowe miejsce), to jest to najlepszy wybór.

BRIN

Rozumiem, że mogę mieć tutaj mały indeks kosztem czytania bezużytecznych stron. Użycie małej pages_per_rangeoznacza, że ​​indeks jest większy (co jest problemem w BRIN, ponieważ muszę przeczytać cały indeks), posiadanie dużego pages_per_rangeoznacza, że ​​przeczytam wiele bezużytecznych stron.

Jeśli nie możesz sobie pozwolić na obciążenie magazynu indeksem pokrywającym btree, BRIN jest dla Ciebie idealny, ponieważ masz już klastrowanie ( jest to bardzo ważne, aby BRIN był przydatny). Indeksy BRIN są małe , więc wszystkie strony prawdopodobnie będą w pamięci, jeśli wybierzesz odpowiednią wartość pages_per_range.

Czy istnieje magiczna formuła, aby znaleźć dobrą wartość strony_per_range, która uwzględnia te kompromisy?

Brak magicznej formuły, ale zacznij od pages_per_range nieco mniejszego niż średni rozmiar (w stronach) zajmowany przez średnią awartość. Prawdopodobnie próbujesz zminimalizować: (liczbę zeskanowanych stron BRIN) + (liczbę zeskanowanych stron sterty) dla typowego zapytania. Poszukaj Heap Blocks: lossy=nw planie wykonania pages_per_range=1i porównaj z innymi wartościami pages_per_range- tzn. Sprawdź, ile skanowanych jest niepotrzebnych bloków sterty.

GIN / GiST

Nie jestem pewien, czy są one istotne tutaj, ponieważ są one najczęściej używane do wyszukiwania pełnotekstowego, ale słyszę również, że dobrze radzą sobie z duplikatami kluczy. Czy pomoże tu albo indeks GIN/ GiST?

Warto rozważyć GIN, ale prawdopodobnie nie GiST - jednak jeśli naturalne grupowanie jest naprawdę dobre, to BRIN będzie prawdopodobnie lepszym wyborem.

Oto przykładowe porównanie różnych typów indeksów dla danych fikcyjnych, trochę podobnych do twojego:

tabela i indeksy:

create table foo(a,b,c) as
select *, lpad('',20)
from (select chr(g) a from generate_series(97,122) g) a
     cross join (select generate_series(1,100000) b) b
order by a;
create index foo_btree_covering on foo(a,b);
create index foo_btree on foo(a);
create index foo_gin on foo using gin(a);
create index foo_brin_2 on foo using brin(a) with (pages_per_range=2);
create index foo_brin_4 on foo using brin(a) with (pages_per_range=4);
vacuum analyze;

rozmiary relacji:

select relname "name", pg_size_pretty(siz) "size", siz/8192 pages, (select count(*) from foo)*8192/siz "rows/page"
from( select relname, pg_relation_size(C.oid) siz
      from pg_class c join pg_namespace n on n.oid = c.relnamespace
      where nspname = current_schema ) z;

nazwa | rozmiar | strony | wiersze / strona
: ----------------- | : ------ | ----: | --------:
foo | 149 MB | 19118 | 135
foo_btree_covering | 56 MB | 7132 | 364
foo_btree | 56 MB | 7132 | 364
foo_gin | 2928 kB | 366 | 7103
foo_brin_2 | 264 kB | 33 | 78787
foo_brin_4 | 136 kB | 17 | 152941

obejmujące btree:

explain analyze select sum(b) from foo where a='a';

| PLAN ZAPYTANIA |
| : ------------------------------------------------- -------------------------------------------------- ------------------------------------------- |
| Agregat (koszt = 3282,57..3282,58 wierszy = 1 szerokość = 8) (rzeczywisty czas = 45,942..45,942 wierszy = 1 pętla = 1) |
| -> Skanuj tylko indeks używając foo_btree_covering na foo (koszt = 0,43..3017.80 wierszy = 105907 szerokość = 4) (czas rzeczywisty = 0,038..27.286 wierszy = 100000 pętli = 1) |
| Index Cond: (a = „a” :: text) |
| Sterty pobrania: 0 |
| Czas planowania: 0,099 ms |
| Czas wykonania: 45,968 ms |

zwykły btree:

drop index foo_btree_covering;
explain analyze select sum(b) from foo where a='a';

| PLAN ZAPYTANIA |
| : ------------------------------------------------- -------------------------------------------------- ----------------------------- |
| Agregat (koszt = 4064,57..4064,58 wierszy = 1 szerokość = 8) (rzeczywisty czas = 54.242..54.242 wierszy = 1 pętli = 1) |
| -> Skanowanie indeksu za pomocą foo_btree na foo (koszt = 0,43..3799.80 wierszy = 105907 szerokość = 4) (rzeczywisty czas = 0,037..33,084 wierszy = 100000 pętli = 1) |
| Index Cond: (a = „a” :: text) |
| Czas planowania: 0,135 ms |
| Czas wykonania: 54,280 ms |

BRIN pages_per_range = 4:

drop index foo_btree;
explain analyze select sum(b) from foo where a='a';

| PLAN ZAPYTANIA |
| : ------------------------------------------------- -------------------------------------------------- ----------------------------- |
| Agregat (koszt = 21595.38..21595.39 wierszy = 1 szerokość = 8) (czas rzeczywisty = 52.455..52.455 wierszy = 1 pętla = 1) |
| -> Skanowanie sterty bitmap na foo (koszt = 888,78..21330,61 wierszy = 105907 szerokość = 4) (rzeczywisty czas = 2,738..31,967 wierszy = 100000 pętli = 1) |
| Ponownie sprawdź Cond: (a = 'a' :: text) |
| Wiersze usunięte przez sprawdzenie indeksu: 96 |
| Bloki sterty: straty = 736 |
| -> Skanowanie indeksu bitmap na foo_brin_4 (koszt = 0,00..862,30 wierszy = 105907 szerokość = 0) (rzeczywisty czas = 2,720..2,720 wierszy = 7360 pętli = 1) |
| Index Cond: (a = „a” :: text) |
| Czas planowania: 0,101 ms |
| Czas realizacji: 52,501 ms |

BRIN pages_per_range = 2:

drop index foo_brin_4;
explain analyze select sum(b) from foo where a='a';

| PLAN ZAPYTANIA |
| : ------------------------------------------------- -------------------------------------------------- ----------------------------- |
| Agregat (koszt = 21659,38..21659.39 wierszy = 1 szerokość = 8) (czas rzeczywisty = 53.971..53.971 wierszy = 1 pętla = 1) |
| -> Skanowanie sterty bitmap na foo (koszt = 952,78..21394.61 wierszy = 105907 szerokość = 4) (rzeczywisty czas = 5.286..33.492 wierszy = 100000 pętli = 1) |
| Ponownie sprawdź Cond: (a = 'a' :: text) |
| Wiersze usunięte przez sprawdzenie indeksu: 96 |
| Bloki sterty: straty = 736 |
| -> Skanowanie indeksu bitmap na foo_brin_2 (koszt = 0,00..926,30 wierszy = 105907 szerokość = 0) (rzeczywisty czas = 5,275..5,275 wierszy = 7360 pętli = 1) |
| Index Cond: (a = „a” :: text) |
| Czas planowania: 0,095 ms |
| Czas wykonania: 54,016 ms |

GIN:

drop index foo_brin_2;
explain analyze select sum(b) from foo where a='a';

| PLAN ZAPYTANIA |
| : ------------------------------------------------- -------------------------------------------------- ------------------------------ |
| Agregat (koszt = 21687,38..21687.39 wierszy = 1 szerokość = 8) (czas rzeczywisty = 55.331..55.331 wierszy = 1 pętla = 1) |
| -> Skanowanie sterty bitmap na foo (koszt = 980,78..21422,61 wierszy = 105907 szerokość = 4) (rzeczywisty czas = 12,377..33.956 wierszy = 100000 pętli = 1) |
| Ponownie sprawdź Cond: (a = 'a' :: text) |
| Bloki stert: dokładne = 736 |
| -> Skanowanie indeksu bitmap na foo_gin (koszt = 0,00..954,30 wierszy = 105907 szerokość = 0) (rzeczywisty czas = 12.271..12.271 wierszy = 100000 pętli = 1) |
| Index Cond: (a = „a” :: text) |
| Czas planowania: 0,118 ms |
| Czas wykonania: 55,366 ms |

dbfiddle tutaj

Oprócz btree i brin, które wydają się najbardziej sensownymi opcjami, niektóre inne, egzotyczne opcje, które mogą być warte zbadania - mogą być pomocne lub nie w twoim przypadku:

• INCLUDEindeksy . Będą - miejmy nadzieję - w kolejnej głównej wersji (10) Postgres, gdzieś około września 2017 r. Indeks on (a) INCLUDE (b)ma taką samą strukturę jak indeks włączony, (a)ale zawiera na stronach z blistą wszystkie wartości (ale nieuporządkowane). Co oznacza, że ​​nie możesz go użyć na przykład do SELECT * FROM t WHERE a = 'a' AND b = 2 ;. Indeks może być użyty, ale podczas gdy (a,b)indeks znajdzie pasujące wiersze z jednym wyszukiwaniem, indeks uwzględnienia będzie musiał przejść przez (ewentualnie 100K, jak w twoim przypadku) wartości, które pasują a = 'a'i sprawdzić bwartości.
  Z drugiej strony indeks jest nieco mniejszy od (a,b)indeksu i nie jest wymagana kolejność w bcelu obliczenia zapytania SUM(b). Możesz także mieć na przykład(a) INCLUDE (b,c,d) które mogą być używane do zapytań podobnych do twoich, które agregują we wszystkich 3 kolumnach.

• Filtrowane (częściowe) indeksy . Sugestia, która na początku może wydawać się nieco szalona ^* :

  CREATE INDEX flt_a  ON t (b) WHERE (a = 'a') ;
  ---
  CREATE INDEX flt_xy ON t (b) WHERE (a = 'xy') ;

  Jeden indeks dla każdej awartości. W twoim przypadku około 100 000 indeksów. Chociaż brzmi to dużo, należy wziąć pod uwagę, że każdy indeks będzie bardzo mały, zarówno pod względem wielkości (liczby wierszy), jak i szerokości (ponieważ będzie przechowywać tylko bwartości). Jednak we wszystkich innych aspektach (indeksy 100K razem) będzie działał jak indeks b-drzewa (a,b)podczas korzystania z przestrzeni (b)indeksu.
  Wadą jest to, że musisz je tworzyć i utrzymywać samodzielnie, za każdym razem, gdy nowa wartość ajest dodawana do tabeli. Ponieważ twoja tabela jest raczej stabilna, bez wielu (lub jakichkolwiek) wstawek / aktualizacji, nie wydaje się to problemem.

• Tabele podsumowujące. Ponieważ tabela jest raczej stabilna, zawsze możesz utworzyć i wypełnić tabelę podsumowań najczęstszymi agregacjami, których potrzebujesz ( sum(b), sum(c), sum(d), avg(b), count(distinct b)itp.). Będzie mały (tylko 100 000 wierszy) i będzie musiał zostać wypełniony tylko raz i zaktualizowany tylko wtedy, gdy wiersze zostaną wstawione / zaktualizowane / usunięte w głównej tabeli.

^{*: pomysł skopiowany z tej firmy, która prowadzi 10 milionów indeksów w swoim systemie produkcyjnym: The Heap: Uruchamianie 10 milionów indeksów Postgresql w produkcji (i wciąż rośnie) .}