Оптимизация одного запроса с GROUP BY в PostgreSQL20.12.2016 09:33

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

Сформулируем задачу

Рассмотрим такую схему. У нас есть две таблички

content — документы.
content_keyword_ref — ключевые слова, которые присутствуют в документе.

CREATE TABLE

CREATE TABLE content
(
  id integer NOT NULL DEFAULT nextval('content_id_seq'::regclass),
  some_data character varying(1000) NOT NULL,
  CONSTRAINT content_pkey PRIMARY KEY (id),
);

CREATE TABLE content_keyword_ref
(
  keyword_id integer NOT NULL,
  content_id integer NOT NULL,
  CONSTRAINT content_keyword_ref_pkey PRIMARY KEY (keyword_id, content_id),
  CONSTRAINT content_keyword_ref_content_id_foreign FOREIGN KEY (content_id)
      REFERENCES content (id) MATCH SIMPLE
      ON UPDATE NO ACTION ON DELETE CASCADE,
  CONSTRAINT content_keyword_ref_keyword_id_foreign FOREIGN KEY (keyword_id)
      REFERENCES keywords (id) MATCH SIMPLE
      ON UPDATE NO ACTION ON DELETE CASCADE
);
CREATE INDEX content_keyword_ref_content_id_index
  ON content_keyword_ref
  USING btree
  (content_id);
CREATE INDEX content_keyword_ref_keyword_id_index
  ON content_keyword_ref
  USING btree
  (keyword_id);
CREATE INDEX content_keyword_ref_keyword_content_idx
  ON content_keyword_ref
  USING btree
  (keyword_id, content_id);

Документов у меня локальной в базе примерно 2 млн, а связей с ключевыми словами примерно 15 млн.

Выберем документы, содержащие одно из перечисленных ключевых слов.

Решение классическое

Для этого нам придется написать примерно такой запрос (я сразу буду добавлять EXPLAIN ANALYZE и выводить план):

EXPLAIN ANALYSE
SELECT c.id 
FROM content c
JOIN content_keyword_ref r ON r.content_id = c.id
    AND r.keyword_id IN (4713, 5951)
GROUP BY c.id
LIMIT 1000

GROUP BY нам приходится использовать только для того, чтобы в выводе не дублировались документы для каждого найденного ключевого слова. Что мы видим в плане выполнения запроса:

Limit  (cost=21454.94..34933.16 rows=1000 width=4) (actual time=6.777..199.735 rows=1000 loops=1)
  ->  Group  (cost=21454.94..100235.11 rows=5845 width=4) (actual time=6.775..199.641 rows=1000 loops=1)
        Group Key: c.id
        ->  Merge Join  (cost=21454.94..100220.49 rows=5845 width=4) (actual time=6.774..199.389 rows=1141 loops=1)
              Merge Cond: (c.id = r.content_id)
              ->  Index Only Scan using content_pkey on content c  (cost=0.43..73221.47 rows=2182736 width=4) (actual time=0.013..131.942 rows=1339506 loops=1)
                    Heap Fetches: 0
              ->  Sort  (cost=21454.51..21469.13 rows=5845 width=4) (actual time=6.662..6.792 rows=1141 loops=1)
                    Sort Key: r.content_id
                    Sort Method: quicksort  Memory: 143kB
                    ->  Bitmap Heap Scan on content_keyword_ref r  (cost=118.16..21088.82 rows=5845 width=4) (actual time=0.470..6.273 rows=2007 loops=1)
                          Recheck Cond: (keyword_id = ANY ('{4713,5951}'::integer[]))
                          Heap Blocks: exact=1781
                          ->  Bitmap Index Scan on content_keyword_ref_keyword_content_idx  (cost=0.00..116.70 rows=5845 width=0) (actual time=0.239..0.239 rows=2007 loops=1)
                                Index Cond: (keyword_id = ANY ('{4713,5951}'::integer[]))
Planning time: 0.277 ms
Execution time: 199.805 ms

Аналогичный результат мы получили бы, использовав DISTINCT вместо GROUP BY:

EXPLAIN ANALYSE
SELECT DISTINCT c.id 
FROM content c
JOIN content_keyword_ref r ON r.content_id = c.id
    AND r.keyword_id IN (4713, 5951)
LIMIT 1000

Получаем:

Limit  (cost=21454.94..34933.16 rows=1000 width=4) (actual time=2.824..187.619 rows=1000 loops=1)
  ->  Unique  (cost=21454.94..100235.11 rows=5845 width=4) (actual time=2.824..187.519 rows=1000 loops=1)
        ->  Merge Join  (cost=21454.94..100220.49 rows=5845 width=4) (actual time=2.823..187.351 rows=1141 loops=1)
              Merge Cond: (c.id = r.content_id)
              ->  Index Only Scan using content_pkey on content c  (cost=0.43..73221.47 rows=2182736 width=4) (actual time=0.011..120.481 rows=1339506 loops=1)
                    Heap Fetches: 0
              ->  Sort  (cost=21454.51..21469.13 rows=5845 width=4) (actual time=2.693..2.805 rows=1141 loops=1)
                    Sort Key: r.content_id
                    Sort Method: quicksort  Memory: 143kB
                    ->  Bitmap Heap Scan on content_keyword_ref r  (cost=118.16..21088.82 rows=5845 width=4) (actual time=0.463..2.321 rows=2007 loops=1)
                          Recheck Cond: (keyword_id = ANY ('{4713,5951}'::integer[]))
                          Heap Blocks: exact=1781
                          ->  Bitmap Index Scan on content_keyword_ref_keyword_content_idx  (cost=0.00..116.70 rows=5845 width=0) (actual time=0.235..0.235 rows=2007 loops=1)
                                Index Cond: (keyword_id = ANY ('{4713,5951}'::integer[]))
Planning time: 0.264 ms
Execution time: 187.727 ms

Как видно, группировка приводит к сортировкам и другим накладным расходам. На некоторых данных время выполнения достигает нескольких секунд!

Как быть?

Оптимизация

Мои идеи, как ускорить запрос при имеющейся схеме, закончились. Попробуем перестроить схему. Табличку content оставляем. А вот связи с ключевыми словами будем хранить в массиве. Чтобы быстро выбирать данные по условиям на массиве, создаем также GiST индекс. О том, какие операторы для работы с массивами поддерживаются индексами, можно посмотреть в документации PostgreSQL.

CREATE TABLE document
(
  content_id integer NOT NULL,
  -- Наш массив ключевых слов, взамен таблицы content_keyword_ref
  keyword_ids integer[] NOT NULL
);

-- Наш GiST индекс
CREATE INDEX document_keyword_ids_index ON document USING GiST(keyword_ids  gist__intbig_ops);

И менее интересная часть


CREATE INDEX document_content_id_index
  ON public.document
  USING btree
  (content_id);

-- Копипастим имеющиеся данные
INSERT INTO document (content_id, keyword_ids)
SELECT c.id, ARRAY(
  SELECT r.keyword_id
  FROM content_keyword_ref r 
  WHERE r.content_id = c.id
)
FROM content c
GROUP BY c.id;

Теперь попробуем построить запрос, который будет возвращать такие же данные как и в вариантах выше:

EXPLAIN ANALYZE
SELECT c.id
  FROM content c
  JOIN document d ON d.content_id = c.id 
    AND d.keyword_ids && ARRAY[4713, 5951]
limit 1000

Смотрим план:

Limit  (cost=387.80..7540.27 rows=1000 width=4) (actual time=8.799..12.935 rows=1000 loops=1)
  ->  Nested Loop  (cost=387.80..14177.77 rows=1928 width=4) (actual time=8.799..12.880 rows=1000 loops=1)
        ->  Bitmap Heap Scan on document d  (cost=387.37..6246.79 rows=1930 width=4) (actual time=8.786..10.599 rows=1000 loops=1)
              Recheck Cond: (keyword_ids && '{4713,5951}'::integer[])
              Rows Removed by Index Recheck: 107
              Heap Blocks: exact=1008
              ->  Bitmap Index Scan on document_keyword_ids_index  (cost=0.00..386.89 rows=1930 width=0) (actual time=8.560..8.560 rows=1977 loops=1)
                    Index Cond: (keyword_ids && '{4713,5951}'::integer[])
        ->  Index Only Scan using content_pkey on content c  (cost=0.43..4.10 rows=1 width=4) (actual time=0.002..0.002 rows=1 loops=1000)
              Index Cond: (id = d.content_id)
              Heap Fetches: 0
Planning time: 0.184 ms
Execution time: 12.994 ms

Выгода есть, причем заметная. На выбранных данных оптимизированный вариант запроса выполняется примерно в 14 раз быстрее. Текст запроса остался примерно таким же понятным. Давайте посмотрим, какие еще выгоды мы получили.

Бонус

Допустим, надо выводить найденные документы на странице с пагинацией. Как в этом случае посчитать количество записей в выборке в «классическом» варианте? Вот несколько вариантов:

Считаем количество записей в подзапросе с GROUP BY:

SELECT COUNT(1) FROM (
    SELECT c.id 
    FROM content c
    JOIN content_keyword_ref r ON r.content_id = c.id
        AND r.keyword_id IN (4713, 5951)
    GROUP BY c.id
) t;

Считаем количество записей в подзапросе с DISTINCT:

SELECT COUNT(1) FROM (
    SELECT DISTINCT(c.id)
    FROM content c
    JOIN content_keyword_ref r ON r.content_id = c.id
        AND r.keyword_id IN (4713, 5951)
) t;

Считаем количество записей без подзапроса, но с помощью COUNT (DISTINCT columns):

SELECT COUNT(DISTINCT c.id)
FROM content c
JOIN content_keyword_ref r ON r.content_id = c.id
    AND r.keyword_id IN (4713, 5951)

Или даже так:

SELECT COUNT(1) OVER()
FROM content c
JOIN content_keyword_ref r ON r.content_id = c.id
    AND r.keyword_id IN (4713, 5951)
GROUP BY c.id
LIMIT 1

Во всех этих вариантах минус не только в производительности. Будет ли модуль пагинации в вашем фреймворке автоматически делать один из этих вариантов? Laravel, например, нет. Вместо этого он выберет все записи и посчитает их количество с помощью count() уже на PHP. Поэтому скорее всего вам придется переопределять метод расчета количества записей, чтобы каждый раз не вычитывалась из базы вся выборка.

Как мы посчитаем количество записей в оптимизированном варианте запроса:

SELECT COUNT(1)
FROM document d 
WHERE d.keyword_ids && ARRAY[4713, 5951]

Гораздо лаконичнее и нет проблем с пагинатором.

Еще один бонус

Мы выбирали документы, содержащие хотя бы одно из указанных слов. Что если надо выбрать документы, в которых содержатся все интересующие ключевые слова? В классическом варианте запрос можно построить примерно так:

SELECT c.id 
FROM content c
JOIN content_keyword_ref r1 ON r1.content_id = c.id
    AND r1.keyword_id = 5388
JOIN content_keyword_ref r2 ON r2.content_id = c.id
    AND r2.keyword_id = 5951
LIMIT 1000

То есть сколько ключевых слов ищем, столько JOIN-ов и делаем. Если мы фильтруем записи по массиву, то можем использовать оператор @>. Тогда запрос выглядит более аккуратно:

SELECT c.id
FROM content c
JOIN document d ON d.content_id = c.id 
    AND d.keyword_ids @> ARRAY[5388, 5951]
LIMIT 1000

Да и план выполнения у него оказывается лучше.

В документации по ссылке, которую я оставил выше, можно найти описание и других полезных операторов, поддерживаемых индексами.

Резюме

Я поэкспериментировал с разными данными. Как правило, оптимизированный вариант дает выигрыш в скорости от 2 до 10 раз. Но мне удалось-таки подобрать примеры, когда запросы на вычисление количества записей в выдаче работают в 1.5–2 раза медленнее в случае «оптимизированного» варианта.

То есть в целом эксперимент можно назвать удачным. Но если решитесь на подобные хитрости, то перед запуском изменений в продакшн стоит проверить эффективность на ваших данных.

Комментарии (10)

zlukfo

20 декабря 2016 в 07:54

0

↑

↓

Раз уж Вы оптимизируете не только поисковый запрос, но и структуру исходных таблиц, постановка задачи подсказывает использование инструментов fts
- mnv
  
  20 декабря 2016 в 09:03
  
  0
  
  ↑
  
  ↓
  
  Иногда действительно удобно полностью положиться на полнотекстовый поиск, но не всегда. Если нужно определять объекты в документе более аккуратно, то на мой взгляд лучше это делать более тонкими механизмами.
  - zlukfo
    
    20 декабря 2016 в 09:07
    
    0
    
    ↑
    
    ↓
    
    Не совсем понял «более аккуратно». Можно пример.
genew

20 декабря 2016 в 07:54

+1

↑

↓
Что если сделать так?
```
CREATE INDEX i_content_keyword_ref ON content_keyword_ref(keyword_id, content_id);

SELECT distinct r.id FROM content_keyword_ref r where r.keyword_id IN (4713, 5951);
```
- mnv
  
  20 декабря 2016 в 08:01
  
  0
  
  ↑
  
  ↓
  
  Такой индекс я добавлял, он называется content_keyword_ref_keyword_content_idx. В EXPLAIN он есть, а в листинг я его почему-то не добавил. Спасибо, что заметили, добавлю его в текст.
- mnv
  
  20 декабря 2016 в 08:29
  
  0
  
  ↑
  
  ↓
  На этой паре айдишников ваш запрос отрабатывает примерно в 3 раза быстрее, чем вариант с фильтрацией массива. Причем не важно — с JOIN или без, главное — без LIMIT. Попробовал другую пару айдишников, для которых в базе больше данных — там наоборот вариант с фильтрацией массива получается в 2 раза быстрее.
  План для вашего варианта
  HashAggregate (cost=21103.43..21160.44 rows=5701 width=4) (actual time=3.280..3.447 rows=1786 loops=1) Group Key: content_id -> Bitmap Heap Scan on content_keyword_ref r (cost=118.16..21088.82 rows=5845 width=4) (actual time=0.785..2.754 rows=2007 loops=1) Recheck Cond: (keyword_id = ANY ('{4713,5951}'::integer[])) Heap Blocks: exact=1781 -> Bitmap Index Scan on content_keyword_ref_keyword_content_idx (cost=0.00..116.70 rows=5845 width=0) (actual time=0.403..0.403 rows=2007 loops=1) Index Cond: (keyword_id = ANY ('{4713,5951}'::integer[])) Planning time: 0.138 ms Execution time: 3.542 ms
  - genew
    
    20 декабря 2016 в 09:16 (комментарий был изменён)
    
    0
    
    ↑
    
    ↓
    
    Айдишники должны быть в одном индексе. Тогда запрос работает только по индексу, не считывая данные из таблиц, что гораздо быстрее.
    - mnv
      
      20 декабря 2016 в 09:29
      
      0
      
      ↑
      
      ↓
      
      Понял вашу идею. Так и есть. Жаль, что не всегда можно обойтись чтением только айдишников.
erwins22

20 декабря 2016 в 09:20

0

↑

↓

А если использовать method hash?
CREATE INDEX i_content_keyword_ref ON content_keyword_ref (keyword_id, content_id) USING HASH
- mnv
  
  20 декабря 2016 в 09:28
  
  0
  
  ↑
  
  ↓
  PostgreSQL 9.6:
  
  CREATE INDEX i_content_keyword_ref ON content_keyword_ref USING HASH(keyword_id, content_id)
```
ОШИБКА:  метод доступа "hash" не поддерживает индексы по многим столбцам
```