Как ускорить сортировку ORDER BY при использовании индекса GIN в PostgreSQL?

13

У меня есть такая таблица:

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

Продукт может принадлежать нескольким категориям. category_idsстолбец содержит список идентификаторов всех категорий продуктов.

Типичный запрос выглядит так (всегда поиск одной категории):

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

Для ускорения я использую следующий индекс:

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

Это очень помогает, если в одной категории слишком много товаров. Он быстро отфильтровывает продукты, относящиеся к этой категории, но затем выполняется операция сортировки, которая должна быть выполнена трудным способом (без индекса).

У меня установлено btree_ginрасширение, позволяющее мне строить многостолбцовый индекс GIN следующим образом:

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

Но Postgres не хочет использовать это для сортировки . Даже когда я удаляю DESCспецификатор в запросе.

Любые альтернативные подходы для оптимизации задачи приветствуются.

Дополнительная информация:

  • PostgreSQL 9.4, с расширением intarray
  • общее количество продуктов в настоящее время составляет 260 тыс., но ожидается значительный рост (до 10 млн., это мультитенантная платформа электронной коммерции)
  • товаров в категории 1..10000 (может вырасти до 100 тыс.), в среднем ниже 100, но те категории с большим количеством товаров имеют тенденцию привлекать гораздо больше запросов

Следующий план запроса был получен из небольшой тестовой системы (4680 товаров в выбранной категории, всего 200 000 товаров в таблице):

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

Примечание # 1 : 82 мс может выглядеть не так страшно, но это потому, что буфер сортировки помещается в память. Как только я выбираю все столбцы из таблицы продуктов ( SELECT * FROM ...а в реальной жизни их около 60), это Sort Method: external merge Disk: 5696kBудваивает время выполнения. И это только для 4680 продуктов.

Точка действия № 1 (из примечания № 1): чтобы уменьшить объем памяти, необходимый для операции сортировки, и, следовательно, немного ускорить ее, было бы целесообразно сначала получить, отсортировать и ограничить идентификаторы продуктов, а затем получить полные записи:

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;

Это возвращает нас к Sort Method: quicksort Memory: 903kB~ 80 мс для 4680 продуктов. Тем не менее может быть медленным, когда количество продуктов увеличивается до 100К.

postgresql index postgresql-performance Ярослав Ставничий
источник
На этой странице: hlinnaka.iki.fi/2014/03/28/… есть комментарий, что btree_gin нельзя использовать для сортировки.
Младен Узелац
ОК, я перефразировал заголовок, чтобы дать больше возможностей.
Ярослав Ставничий
Вы всегда ищете одну категорию? И, пожалуйста, предоставьте более основную информацию: версия Postgres, количество элементов, количество строк в категории (мин. / Ср. / Макс.). рассмотрите инструкции в теге info для postgresql-performance . И: scoreможет быть NULL, но вы все равно сортируете score DESC, нет score DESC NULLS LAST. Один или другой, кажется, не прав ...
Эрвин Брандштеттер
Я добавил дополнительную информацию по запросу. Я всегда ищу одну категорию. И scoreна самом деле это не NULL - я исправил определение таблицы.
Ярослав Ставничий

Ответы:

10

Я много экспериментировал и вот мои выводы.

Джин и сортировка

Индекс GIN в настоящее время (начиная с версии 9.4) не может помочь упорядочению .

Из типов индексов, поддерживаемых в настоящее время PostgreSQL, только B-дерево может производить отсортированный вывод - другие типы индексов возвращают совпадающие строки в неопределенном, зависящем от реализации порядке.

work_mem

Спасибо Крис за указание на этот параметр конфигурации . По умолчанию он равен 4 МБ, и в случае, если ваш набор записей больше, увеличение work_memдо нужного значения (может быть найдено из EXPLAIN ANALYSE) может значительно ускорить операции сортировки.

ALTER SYSTEM SET work_mem TO '32MB';

Перезапустите сервер, чтобы изменения вступили в силу, затем дважды проверьте:

SHOW work_mem;

Оригинальный запрос

Я заполнил свою базу данных продуктами из 650 тыс., А некоторые категории содержали до 40 тыс. Товаров. Я немного упростил запрос, удалив publishedпредложение:

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

Как мы видим, этого work_memбыло недостаточно, поэтому мы имели Sort Method: external merge Disk: 29656kBприблизительное число, для быстрой сортировки в памяти требуется чуть больше 32 МБ.

Уменьшить объем памяти

Не выбирайте полные записи для сортировки, используйте идентификаторы, применяйте сортировку, смещение и ограничение, а затем загружайте только 10 нужных нам записей:

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

Примечание Sort Method: quicksort Memory: 7396kB. Результат намного лучше.

JOIN и дополнительный индекс B-дерева

Как советовал Крис, я создал дополнительный индекс:

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

Сначала я попытался присоединиться так:

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;

План запроса немного отличается, но результат тот же:

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

Играя с различными смещениями и количеством продуктов, я не мог заставить PostgreSQL использовать дополнительный индекс B-дерева.

Итак, я пошел классическим путем и создал распределительную таблицу :

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

Все еще не используя индекс B-дерева, набор результатов не соответствовал work_mem, следовательно, плохие результаты.

Но при некоторых обстоятельствах, имея большое количество продуктов и небольшое смещение, PostgreSQL теперь решает использовать индекс B-дерева:

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

Это на самом деле вполне логично, так как индекс B-дерева здесь не дает прямого результата, он используется только как руководство для последовательного сканирования.

Давайте сравним с 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

Результат Джина намного лучше. Я проверил с различными комбинациями количества продуктов и смещения, ни при каких обстоятельствах подход к соединительной таблице не был лучше .

Сила реального индекса

Чтобы PostgreSQL полностью использовал индекс для сортировки, все WHEREпараметры запроса, а также ORDER BYпараметры должны находиться в одном индексе B-дерева. Для этого я скопировал поля сортировки из продукта в таблицу соединений:

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

И это худший сценарий с большим количеством товаров в выбранной категории и большим смещением. При смещении = 300 время выполнения составляет всего 0,5 мс.

К сожалению, поддержание такой соединительной таблицы требует дополнительных усилий. Этого можно добиться с помощью индексированных материализованных представлений, но это полезно только в том случае, если ваши данные обновляются редко, потому что обновление такого материализованного представления является довольно сложной операцией.

Так что я до сих пор остаюсь с индексом GIN, с увеличенным work_memи уменьшенным запросом памяти.

Ярослав Ставничий
источник
Вам не нужно перезапускать для изменения общих work_memнастроек в postgresql.conf. Перезагрузить достаточно. И позвольте мне предостеречь от work_memслишком высокого глобального значения в многопользовательской среде (не слишком низкого). Если у вас есть несколько запросов, требующих большего work_mem, установите его выше для сеанса только с SET- или только для транзакции с SET LOCAL. См .: dba.stackexchange.com/a/48633/3684
Эрвин Брандштеттер,
Какой отличный ответ. Мне очень помогли, особенно с операцией сортировки диска -> в памяти, быстрое изменение для большой победы, спасибо!
Рикардо Вильямиль
4

Вот несколько быстрых советов, которые могут помочь улучшить вашу производительность. Я начну с самого простого совета, который почти без усилий с вашей стороны, и перейду к более сложному совету после первого.

1. work_mem

Итак, я сразу вижу, что сортировка, указанная в вашем плане объяснения, Sort Method: external merge Disk: 5696kBпотребляет менее 6 МБ, но выливается на диск. Вам нужно увеличить work_memнастройки в вашем postgresql.confфайле, чтобы они были достаточно большими, чтобы сортировка помещалась в памяти.

РЕДАКТИРОВАТЬ: Кроме того, при дальнейшей проверке, я вижу, что после использования индекса, чтобы проверить, catgory_idsкоторый соответствует вашим критериям, сканирование индекса растрового изображения вынуждено стать «с потерями» и должен перепроверить условие при чтении строк из соответствующих страниц кучи , Обратитесь к этому сообщению на postgresql.org для объяснения лучше, чем я дал. : P Суть в том, что вы work_memслишком низко. Если вы не настроили параметры по умолчанию на вашем сервере, он не будет работать хорошо.

Это исправление не займет у вас практически никакого времени. Одно изменение postgresql.conf, и вы выключены! Обратитесь к этой странице настройки производительности для получения дополнительных советов.

2. Изменение схемы

Итак, вы приняли решение в своем проекте схемы денормализовать category_idsв массив целых чисел, который затем заставляет вас использовать индекс GIN или GIST для получения быстрого доступа. По моему опыту, ваш выбор индекса GIN будет быстрее для чтения, чем GIST, поэтому в этом случае вы сделали правильный выбор. Тем не менее, GIN является несортированным индексом; думать о нем , как ключ-значение, где предикаты равенства являются легко проверить, но такие операции, как WHERE >, WHERE <или ORDER BYне облегчило индексом.

Достойным подходом было бы нормализовать ваш дизайн с помощью таблицы мостов / соединительных таблиц , используемых для указания отношений «многие ко многим» в базах данных.

В этом случае у вас есть много категорий и набор соответствующих целых чисел category_id, и у вас есть много продуктов и соответствующих им product_id. Вместо столбца в таблице продуктов, представляющего собой целочисленный массив category_ids, удалите этот столбец массива из схемы и создайте таблицу как

CREATE TABLE join_products_categories (product_id int, category_id int);

Затем вы можете генерировать индексы B-дерева в двух столбцах таблицы мостов,

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);

Просто мое скромное мнение, но эти изменения могут иметь большое значение для вас. Попробуйте это work_memизменение первым делом, по крайней мере.

Удачи!

РЕДАКТИРОВАТЬ:

Создайте дополнительный индекс, чтобы помочь сортировке

Таким образом, если со временем ваша линейка продуктов расширяется, определенные запросы могут возвращать много результатов (тысячи, десятки тысяч?), Но которые все еще могут быть лишь небольшим подмножеством вашей общей линейки продуктов. В этих случаях сортировка может даже быть довольно дорогой, если она выполняется в памяти, но для содействия сортировке может использоваться соответствующий индекс.

Смотрите официальную документацию PostgreSQL, описывающую индексы и ORDER BY .

Если вы создаете индекс вашего ORDER BYreqirements

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

Затем Postgres оптимизирует и решит, будет ли использование индекса или явная сортировка более экономически эффективным. Имейте в виду, что нет никаких гарантий, что Postgres будет использовать индекс; он будет стремиться оптимизировать производительность и выбирать между использованием индекса или явной сортировкой. Если вы создаете этот индекс, следите за ним, чтобы увидеть, достаточно ли он используется, чтобы оправдать его создание, и отбросьте его, если большинство ваших сортировок выполняются явно.

Тем не менее, на данный момент ваш «самый большой удар по доллару», вероятно, будет использовать больше work_mem, но в некоторых случаях индекс может поддерживать сортировку.

Крис
источник
Я также думал об использовании соединительной таблицы, чтобы избежать GIN. Но вы не указали, как это поможет с сортировкой. Я думаю, что это не поможет. Я попытался объединить таблицу продуктов с набором идентификаторов продуктов, собранных с помощью запроса GIN, который, я считаю, очень похож на предложение, которое вы предлагаете, и эта операция не могла использовать индекс b-дерева для оценки и заголовка. Возможно я построил неправильный индекс. Не могли бы вы пояснить это?
Ярослав Ставничий
Извинения, возможно, я не объяснил достаточно ясно. Изменение вашей work_memконфигурации было задумано как исправление вашей проблемы «сортировки на диске», а также вашей проблемы с перепроверкой. По мере роста количества продуктов может потребоваться дополнительный индекс для сортировки. Пожалуйста, смотрите мои правки выше для уточнения.
Крис