Mam taki stół:

CREATE TABLE products (
  id serial PRIMARY KEY, 
  category_ids integer[],
  published boolean NOT NULL,
  score integer NOT NULL,
  title varchar NOT NULL);

Produkt może należeć do wielu kategorii. category_idskolumna zawiera listę identyfikatorów wszystkich kategorii produktów.

Typowe zapytanie wygląda następująco (zawsze szuka pojedynczej kategorii):

SELECT * FROM products WHERE published
  AND category_ids @> ARRAY[23465]
ORDER BY score DESC, title
LIMIT 20 OFFSET 8000;

Aby przyspieszyć, używam następującego indeksu:

CREATE INDEX idx_test1 ON products
  USING GIN (category_ids gin__int_ops) WHERE published;

Ten bardzo pomaga, chyba że w jednej kategorii jest zbyt wiele produktów. Szybko odfiltrowuje produkty należące do tej kategorii, ale następnie istnieje operacja sortowania, która musi zostać wykonana w sposób trudny (bez indeksu).

Zainstalowałem btree_ginrozszerzenie pozwalające mi na zbudowanie wielokolumnowego indeksu GIN w następujący sposób:

CREATE INDEX idx_test2 ON products USING GIN (
  category_ids gin__int_ops, score, title) WHERE published;

Ale Postgres nie chce tego używać do sortowania . Nawet gdy usunę DESCspecyfikator w zapytaniu.

Wszelkie alternatywne podejścia do optymalizacji zadania są bardzo mile widziane.

Dodatkowe informacje:

• PostgreSQL 9.4, z rozszerzeniem intarray
• całkowita liczba produktów wynosi obecnie 260 tys., ale oczekuje się znacznego wzrostu (do 10 mln, jest to platforma e-commerce dla wielu najemców)
• produkty według kategorii 1..10000 (może wzrosnąć do 100 tys.), średnia jest poniżej 100, ale te kategorie z dużą liczbą produktów zwykle przyciągają znacznie więcej zapytań

Poniższy plan zapytań uzyskano z mniejszego systemu testowego (4680 produktów w wybranej kategorii, łącznie 200 000 produktów w tabeli):

Limit  (cost=948.99..948.99 rows=1 width=72) (actual time=82.330..82.341 rows=20 loops=1)
  ->  Sort  (cost=948.37..948.99 rows=245 width=72) (actual time=80.231..81.337 rows=4020 loops=1)
        Sort Key: score, title
        Sort Method: quicksort  Memory: 928kB
        ->  Bitmap Heap Scan on products  (cost=13.90..938.65 rows=245 width=72) (actual time=1.919..16.044 rows=4680 loops=1)
              Recheck Cond: ((category_ids @> '{292844}'::integer[]) AND published)
              Heap Blocks: exact=3441
              ->  Bitmap Index Scan on idx_test2  (cost=0.00..13.84 rows=245 width=0) (actual time=1.185..1.185 rows=4680 loops=1)
                    Index Cond: (category_ids @> '{292844}'::integer[])
Planning time: 0.202 ms
Execution time: 82.404 ms

Uwaga 1 : 82 ms może nie wyglądać tak przerażająco, ale dlatego, że bufor sortowania pasuje do pamięci. Po wybraniu wszystkich kolumn z tabeli produktów ( SELECT * FROM ...w rzeczywistości jest ich około 60), Sort Method: external merge Disk: 5696kBczas wykonania ulega podwojeniu. Dotyczy to tylko 4680 produktów.

Punkt działania nr 1 (pochodzi z uwagi nr 1): Aby zmniejszyć ślad pamięci operacji sortowania, a tym samym nieco ją przyspieszyć, rozsądnie byłoby najpierw pobrać, posortować i ograniczyć identyfikatory produktów, a następnie pobrać pełne rekordy:

SELECT * FROM products WHERE id IN (
  SELECT id FROM products WHERE published AND category_ids @> ARRAY[23465]
  ORDER BY score DESC, title LIMIT 20 OFFSET 8000
) ORDER BY score DESC, title;

To sprowadza nas z powrotem do Sort Method: quicksort Memory: 903kB~ 80 ms dla 4680 produktów. Nadal może być powolny, gdy liczba produktów wzrośnie do 100 tys.

Przeprowadziłem wiele eksperymentów i oto moje ustalenia.

GIN i sortowanie

Indeks GIN obecnie (od wersji 9.4) nie może pomóc w zamówieniu .

Z typów indeksów obecnie obsługiwanych przez PostgreSQL, tylko B-drzewo może generować posortowane dane wyjściowe - inne typy indeksów zwracają pasujące wiersze w nieokreślonej kolejności zależnej od implementacji.

work_mem

Dzięki Chris za wskazanie tego parametru konfiguracyjnego . Domyślnie wynosi 4 MB, a jeśli Twój zestaw rekordów jest większy, zwiększenie work_memdo odpowiedniej wartości (można ją znaleźć w EXPLAIN ANALYSE) może znacznie przyspieszyć operacje sortowania.

ALTER SYSTEM SET work_mem TO '32MB';

Uruchom ponownie serwer, aby zmiany zaczęły obowiązywać, a następnie sprawdź dwukrotnie:

SHOW work_mem;

Oryginalne zapytanie

Zapełniłem bazę danych 650 000 produktów, a niektóre kategorie zawierały do ​​40 000 produktów. Uprościłem trochę zapytanie, usuwając publishedklauzulę:

SELECT * FROM products WHERE category_ids @> ARRAY [248688]
ORDER BY score DESC, title LIMIT 10 OFFSET 30000;

Limit  (cost=2435.62..2435.62 rows=1 width=1390) (actual time=1141.254..1141.256 rows=10 loops=1)
  ->  Sort  (cost=2434.00..2435.62 rows=646 width=1390) (actual time=1115.706..1140.513 rows=30010 loops=1)
        Sort Key: score, title
        Sort Method: external merge  Disk: 29656kB
        ->  Bitmap Heap Scan on products  (cost=17.01..2403.85 rows=646 width=1390) (actual time=11.831..25.646 rows=41666 loops=1)
              Recheck Cond: (category_ids @> '{248688}'::integer[])
              Heap Blocks: exact=6471
              ->  Bitmap Index Scan on idx_products_category_ids_gin  (cost=0.00..16.85 rows=646 width=0) (actual time=10.140..10.140 rows=41666 loops=1)
                    Index Cond: (category_ids @> '{248688}'::integer[])
Planning time: 0.288 ms
Execution time: 1146.322 ms

Jak widzimy, work_memnie wystarczyło, więc mieliśmy Sort Method: external merge Disk: 29656kB(liczba tutaj jest przybliżona, potrzebuje nieco więcej niż 32 MB na szybkie sortowanie w pamięci).

Zmniejsz ślad pamięci

Nie wybieraj pełnych rekordów do sortowania, używaj identyfikatorów, stosuj sortowanie, przesunięcie i ograniczenie, a następnie załaduj tylko 10 rekordów, których potrzebujemy:

SELECT * FROM products WHERE id in (
  SELECT id FROM products WHERE category_ids @> ARRAY[248688]
  ORDER BY score DESC, title LIMIT 10 OFFSET 30000
) ORDER BY score DESC, title;

Sort  (cost=2444.10..2444.11 rows=1 width=1390) (actual time=707.861..707.862 rows=10 loops=1)
  Sort Key: products.score, products.title
  Sort Method: quicksort  Memory: 35kB
  ->  Nested Loop  (cost=2436.05..2444.09 rows=1 width=1390) (actual time=707.764..707.803 rows=10 loops=1)
        ->  HashAggregate  (cost=2435.63..2435.64 rows=1 width=4) (actual time=707.744..707.746 rows=10 loops=1)
              Group Key: products_1.id
              ->  Limit  (cost=2435.62..2435.62 rows=1 width=72) (actual time=707.732..707.734 rows=10 loops=1)
                    ->  Sort  (cost=2434.00..2435.62 rows=646 width=72) (actual time=704.163..706.955 rows=30010 loops=1)
                          Sort Key: products_1.score, products_1.title
                          Sort Method: quicksort  Memory: 7396kB
                          ->  Bitmap Heap Scan on products products_1  (cost=17.01..2403.85 rows=646 width=72) (actual time=11.587..35.076 rows=41666 loops=1)
                                Recheck Cond: (category_ids @> '{248688}'::integer[])
                                Heap Blocks: exact=6471
                                ->  Bitmap Index Scan on idx_products_category_ids_gin  (cost=0.00..16.85 rows=646 width=0) (actual time=9.883..9.883 rows=41666 loops=1)
                                      Index Cond: (category_ids @> '{248688}'::integer[])
        ->  Index Scan using products_pkey on products  (cost=0.42..8.45 rows=1 width=1390) (actual time=0.004..0.004 rows=1 loops=10)
              Index Cond: (id = products_1.id)
Planning time: 0.682 ms
Execution time: 707.973 ms

Uwaga Sort Method: quicksort Memory: 7396kB. Wynik jest znacznie lepszy.

DOŁĄCZ i dodatkowy indeks B-drzewa

Zgodnie z radą Chrisa stworzyłem dodatkowy indeks:

CREATE INDEX idx_test7 ON products (score DESC, title);

Najpierw próbowałem dołączyć w ten sposób:

SELECT * FROM products NATURAL JOIN
  (SELECT id FROM products WHERE category_ids @> ARRAY[248688]
  ORDER BY score DESC, title LIMIT 10 OFFSET 30000) c
ORDER BY score DESC, title;

Plan zapytań różni się nieznacznie, ale wynik jest taki sam:

Sort  (cost=2444.10..2444.11 rows=1 width=1390) (actual time=700.747..700.747 rows=10 loops=1)
  Sort Key: products.score, products.title
  Sort Method: quicksort  Memory: 35kB
  ->  Nested Loop  (cost=2436.05..2444.09 rows=1 width=1390) (actual time=700.651..700.690 rows=10 loops=1)
        ->  HashAggregate  (cost=2435.63..2435.64 rows=1 width=4) (actual time=700.630..700.630 rows=10 loops=1)
              Group Key: products_1.id
              ->  Limit  (cost=2435.62..2435.62 rows=1 width=72) (actual time=700.619..700.619 rows=10 loops=1)
                    ->  Sort  (cost=2434.00..2435.62 rows=646 width=72) (actual time=697.304..699.868 rows=30010 loops=1)
                          Sort Key: products_1.score, products_1.title
                          Sort Method: quicksort  Memory: 7396kB
                          ->  Bitmap Heap Scan on products products_1  (cost=17.01..2403.85 rows=646 width=72) (actual time=10.796..32.258 rows=41666 loops=1)
                                Recheck Cond: (category_ids @> '{248688}'::integer[])
                                Heap Blocks: exact=6471
                                ->  Bitmap Index Scan on idx_products_category_ids_gin  (cost=0.00..16.85 rows=646 width=0) (actual time=9.234..9.234 rows=41666 loops=1)
                                      Index Cond: (category_ids @> '{248688}'::integer[])
        ->  Index Scan using products_pkey on products  (cost=0.42..8.45 rows=1 width=1390) (actual time=0.004..0.004 rows=1 loops=10)
              Index Cond: (id = products_1.id)
Planning time: 1.015 ms
Execution time: 700.918 ms

Grając z różnymi przesunięciami i liczbą produktów, nie mogłem zmusić PostgreSQL do korzystania z dodatkowego indeksu B-drzewa.

Więc poszedłem klasycznie i stworzyłem tabelę połączeń :

CREATE TABLE prodcats AS SELECT id AS product_id, unnest(category_ids) AS category_id FROM products;
CREATE INDEX idx_prodcats_cat_prod_id ON prodcats (category_id, product_id);

SELECT p.* FROM products p JOIN prodcats c ON (p.id=c.product_id)
WHERE c.category_id=248688
ORDER BY p.score DESC, p.title LIMIT 10 OFFSET 30000;

Limit  (cost=122480.06..122480.09 rows=10 width=1390) (actual time=1290.360..1290.362 rows=10 loops=1)
  ->  Sort  (cost=122405.06..122509.00 rows=41574 width=1390) (actual time=1264.250..1289.575 rows=30010 loops=1)
        Sort Key: p.score, p.title
        Sort Method: external merge  Disk: 29656kB
        ->  Merge Join  (cost=50.46..94061.13 rows=41574 width=1390) (actual time=117.746..182.048 rows=41666 loops=1)
              Merge Cond: (p.id = c.product_id)
              ->  Index Scan using products_pkey on products p  (cost=0.42..90738.43 rows=646067 width=1390) (actual time=0.034..116.313 rows=210283 loops=1)
              ->  Index Only Scan using idx_prodcats_cat_prod_id on prodcats c  (cost=0.43..1187.98 rows=41574 width=4) (actual time=0.022..7.137 rows=41666 loops=1)
                    Index Cond: (category_id = 248688)
                    Heap Fetches: 0
Planning time: 0.873 ms
Execution time: 1294.826 ms

Nadal nie używa indeksu B-drzewa, zestaw wyników nie pasował work_mem, a zatem słabe wyniki.

Ale w niektórych okolicznościach, mając dużą liczbę produktów i mały offset PostgreSQL decyduje się teraz na użycie indeksu B-drzewa:

SELECT p.* FROM products p JOIN prodcats c ON (p.id=c.product_id)
WHERE c.category_id=248688
ORDER BY p.score DESC, p.title LIMIT 10 OFFSET 300;

Limit  (cost=3986.65..4119.51 rows=10 width=1390) (actual time=264.176..264.574 rows=10 loops=1)
  ->  Nested Loop  (cost=0.98..552334.77 rows=41574 width=1390) (actual time=250.378..264.558 rows=310 loops=1)
        ->  Index Scan using idx_test7 on products p  (cost=0.55..194665.62 rows=646067 width=1390) (actual time=0.030..83.026 rows=108037 loops=1)
        ->  Index Only Scan using idx_prodcats_cat_prod_id on prodcats c  (cost=0.43..0.54 rows=1 width=4) (actual time=0.001..0.001 rows=0 loops=108037)
              Index Cond: ((category_id = 248688) AND (product_id = p.id))
              Heap Fetches: 0
Planning time: 0.585 ms
Execution time: 264.664 ms

Jest to w rzeczywistości dość logiczne, ponieważ indeks B-drzewa tutaj nie daje bezpośredniego wyniku, służy jedynie jako przewodnik dla skanowania sekwencyjnego.

Porównajmy z zapytaniem GIN:

SELECT * FROM products WHERE id in (
  SELECT id FROM products WHERE category_ids @> ARRAY[248688]
  ORDER BY score DESC, title LIMIT 10 OFFSET 300
) ORDER BY score DESC, title;

Sort  (cost=2519.53..2519.55 rows=10 width=1390) (actual time=143.809..143.809 rows=10 loops=1)
  Sort Key: products.score, products.title
  Sort Method: quicksort  Memory: 35kB
  ->  Nested Loop  (cost=2435.14..2519.36 rows=10 width=1390) (actual time=143.693..143.736 rows=10 loops=1)
        ->  HashAggregate  (cost=2434.71..2434.81 rows=10 width=4) (actual time=143.678..143.680 rows=10 loops=1)
              Group Key: products_1.id
              ->  Limit  (cost=2434.56..2434.59 rows=10 width=72) (actual time=143.668..143.670 rows=10 loops=1)
                    ->  Sort  (cost=2433.81..2435.43 rows=646 width=72) (actual time=143.642..143.653 rows=310 loops=1)
                          Sort Key: products_1.score, products_1.title
                          Sort Method: top-N heapsort  Memory: 68kB
                          ->  Bitmap Heap Scan on products products_1  (cost=17.01..2403.85 rows=646 width=72) (actual time=11.625..31.868 rows=41666 loops=1)
                                Recheck Cond: (category_ids @> '{248688}'::integer[])
                                Heap Blocks: exact=6471
                                ->  Bitmap Index Scan on idx_products_category_ids_gin  (cost=0.00..16.85 rows=646 width=0) (actual time=9.916..9.916 rows=41666 loops=1)
                                      Index Cond: (category_ids @> '{248688}'::integer[])
        ->  Index Scan using products_pkey on products  (cost=0.42..8.45 rows=1 width=1390) (actual time=0.004..0.004 rows=1 loops=10)
              Index Cond: (id = products_1.id)
Planning time: 0.630 ms
Execution time: 143.921 ms

Wynik GIN jest znacznie lepszy. Sprawdziłem różne kombinacje liczby produktów i przesunięć, w żadnym wypadku podejście do tabeli połączeń nie było lepsze .

Moc prawdziwego indeksu

Aby PostgreSQL mógł w pełni wykorzystywać indeks do sortowania, wszystkie WHEREparametry zapytania oraz ORDER BYparametry muszą znajdować się w jednym indeksie B-drzewa. Aby to zrobić, skopiowałem pola sortowania z produktu do tabeli połączeń:

CREATE TABLE prodcats AS SELECT id AS product_id, unnest(category_ids) AS category_id, score, title FROM products;
CREATE INDEX idx_prodcats_1 ON prodcats (category_id, score DESC, title, product_id);

SELECT * FROM products WHERE id in (SELECT product_id FROM prodcats WHERE category_id=248688 ORDER BY score DESC, title LIMIT 10 OFFSET 30000) ORDER BY score DESC, title;

Sort  (cost=2149.65..2149.67 rows=10 width=1390) (actual time=7.011..7.011 rows=10 loops=1)
  Sort Key: products.score, products.title
  Sort Method: quicksort  Memory: 35kB
  ->  Nested Loop  (cost=2065.26..2149.48 rows=10 width=1390) (actual time=6.916..6.950 rows=10 loops=1)
        ->  HashAggregate  (cost=2064.83..2064.93 rows=10 width=4) (actual time=6.902..6.904 rows=10 loops=1)
              Group Key: prodcats.product_id
              ->  Limit  (cost=2064.02..2064.71 rows=10 width=74) (actual time=6.893..6.895 rows=10 loops=1)
                    ->  Index Only Scan using idx_prodcats_1 on prodcats  (cost=0.56..2860.10 rows=41574 width=74) (actual time=0.010..6.173 rows=30010 loops=1)
                          Index Cond: (category_id = 248688)
                          Heap Fetches: 0
        ->  Index Scan using products_pkey on products  (cost=0.42..8.45 rows=1 width=1390) (actual time=0.003..0.003 rows=1 loops=10)
              Index Cond: (id = prodcats.product_id)
Planning time: 0.318 ms
Execution time: 7.066 ms

I to jest najgorszy scenariusz z dużą liczbą produktów w wybranej kategorii i dużym offsetem. Gdy offset = 300 czas wykonania wynosi zaledwie 0,5 ms.

Niestety utrzymanie takiej tabeli połączeń wymaga dodatkowego wysiłku. Można to osiągnąć za pomocą indeksowanych widoków zmaterializowanych, ale jest to przydatne tylko wtedy, gdy dane są aktualizowane rzadko, ponieważ odświeżenie takiego zmaterializowanego widoku jest dość ciężką operacją.

Pozostaję więc do tej pory z indeksem GIN, ze zwiększonym work_memi zmniejszonym zapytaniem o wielkość pamięci.

Oto kilka krótkich wskazówek, które mogą pomóc poprawić wydajność. Zacznę od najłatwiejszej wskazówki, która z twojej strony jest prawie bez wysiłku, i przejdę do trudniejszej wskazówki po pierwszej.

1. work_mem

Widzę więc od razu, że rodzaj zgłoszony w twoim planie wyjaśniania Sort Method: external merge Disk: 5696kBzużywa mniej niż 6 MB, ale rozlewa się na dysk. Musisz zwiększyć work_memustawienie w swoim postgresql.confpliku, aby było wystarczająco duże, aby sortowanie mieściło się w pamięci.

EDYCJA: Ponadto, po dalszej inspekcji, widzę, że po użyciu indeksu do sprawdzenia, catgory_idsktóre pasują do twoich kryteriów, skanowanie indeksu bitmap jest zmuszone stać się „stratne” i musi ponownie sprawdzić stan podczas odczytywania wierszy z odpowiednich stron stosu . Zapoznaj się z tym postem na postgresql.org w celu uzyskania lepszego wyjaśnienia niż ja. : P Najważniejsze jest to, że twój poziom work_memjest zdecydowanie za niski. Jeśli nie dostroiłeś ustawień domyślnych na serwerze, nie będzie on działał dobrze.

Ta poprawka nie zajmie Ci dużo czasu. Jedna zmiana na postgresql.confi już nie ma! Więcej wskazówek znajdziesz na tej stronie dostrajania wydajności .

2. Zmiana schematu

Tak więc w projekcie schematu podjąłeś decyzję o denormalizacji category_idstablicy na liczbę całkowitą, co następnie zmusza cię do użycia indeksu GIN lub GIST w celu uzyskania szybkiego dostępu. Z mojego doświadczenia wynika, że ​​wybór indeksu GIN będzie szybszy dla odczytów niż GIST, więc w takim przypadku dokonałeś właściwego wyboru. Jednak GIN jest nieposortowanym indeksem; myśleć bardziej jak klucz-wartość, gdzie predykaty równość to łatwe do sprawdzenia, ale operacji, takich jak WHERE >, WHERE <lub ORDER BYnie są ułatwione przez indeks.

Przyzwoite podejście polegałoby na znormalizowaniu projektu przy użyciu tabeli mostów / tabeli połączeń , służącej do określania relacji wiele do wielu w bazach danych.

W takim przypadku masz wiele kategorii i zestaw odpowiednich liczb całkowitych category_idoraz wiele produktów i odpowiadających im liczb całkowitych product_id. Zamiast kolumny w tabeli produktów, która jest tablicą liczb całkowitych category_ids, usuń tę kolumnę tablicy ze schematu i utwórz tabelę jako

CREATE TABLE join_products_categories (product_id int, category_id int);

Następnie możesz wygenerować indeksy B-drzewa na dwóch kolumnach tabeli mostu,

CREATE INDEX idx_products_in_join_table ON join_products_categories (product_id);
CREATE INDEX idx_products_in_join_table ON join_products_categories (category_id);

Tylko moja skromna opinia, ale te zmiany mogą mieć dla ciebie dużą różnicę. work_memPrzynajmniej wypróbuj tę zmianę.

Powodzenia!

EDYTOWAĆ:

Zbuduj dodatkowy indeks ułatwiający sortowanie

Tak więc, jeśli z czasem Twoja linia produktów się rozszerzy, niektóre zapytania mogą zwrócić wiele wyników (tysiące, dziesiątki tysięcy?), Ale które nadal mogą być tylko niewielkim podzbiorem całej linii produktów. W takich przypadkach sortowanie może być nawet dość kosztowne, jeśli jest wykonywane w pamięci, ale do ułatwienia sortowania można użyć odpowiednio zaprojektowanego indeksu.

Zobacz oficjalną dokumentację PostgreSQL opisującą indeksy i ORDER BY .

Jeśli utworzysz indeks pasujący do twoich ORDER BYwymagań

CREATE INDEX idx_product_sort ON products (score DESC, title);

następnie Postgres zoptymalizuje i zdecyduje, czy użycie indeksu lub wykonanie jawnego sortowania będzie bardziej opłacalne. Pamiętaj, że nie ma gwarancji, że Postgres będzie korzystać z indeksu; będzie dążyć do optymalizacji wydajności i wybierać między użyciem indeksu lub jawnym sortowaniem. Jeśli utworzysz ten indeks, monitoruj go, aby sprawdzić, czy jest on wystarczająco używany, aby uzasadnić jego utworzenie, i upuść go, jeśli większość twoich działań jest wykonywana jawnie.

Nadal jednak w tym momencie Twoje zaangażowanie w „największy huk za grosze” będzie prawdopodobnie zużywać więcej work_mem, ale są przypadki, w których indeks mógłby wspierać sortowanie.