Индексы в PostgreSQL — 804.12.2017 11:48

Мы уже рассмотрели механизм индексирования PostgreSQL, интерфейс методов доступа и все основные методы доступа, как то: хеш-индексы, B-деревья, GiST, SP-GiST и GIN. А в этой части посмотрим на превращение джина в ром.

RUM
Хоть авторы и утверждают, что джин — могущественный дух, но тема напитков все-таки победила: GIN следующего поколения назвали RUM.

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

Взять пакет yum или apt из репозитория PGDG. Например, если вы ставили PostgreSQL из пакета postgresql-10, то поставьте еще postgresql-10-rum.
Самостоятельно собрать и установить из исходных кодов на github (инструкция там же).
Пользоваться в составе Postgres Pro Enterprise (или хотя бы читать оттуда документацию).

Ограничения GIN

Какие ограничения индекса GIN позволяет преодолеть RUM?

Во-первых, тип данных tsvector, помимо самих лексем, содержит информацию об их позициях внутри документа. В GIN-индексе, как мы видели в прошлый раз, эта информация не сохраняются. Из-за этого операции фразового поиска, появившиеся в версии 9.6, обслуживается GIN-индексом неэффективно и вынуждены обращаться к исходным данным для перепроверки.

Во-вторых, поисковые системы обычно возвращают результаты в порядке релевантности (что бы это ни означало). Для этого можно пользоваться функциями ранжирования ts_rank и ts_rank_cd, но их приходится вычислять для каждой строки результата, что, конечно, медленно.

Метод доступа RUM в первом приближении можно рассматривать как GIN, в который добавлена позиционная информация, и который поддерживает выдачу результата в нужном порядке (аналогично тому, как GiST умеет выдавать ближайших соседей). Пойдем по порядку.

Фразовый поиск

Запрос в полнотекстовом поиске может содержать специальные конструкции, которые учитывают расстояние между лексемами. Например, можно найти документы, в которых бабку от дедки отделяет еще одно слово:

postgres=# select to_tsvector('Бабка за дедку, дедка за репку...') @@ to_tsquery('бабка <2> дедка'); ?column? ---------- t (1 row)
Или указать, что слова должны стоять друг за другом:

postgres=# select to_tsvector('Бабка за дедку, дедка за репку...') @@ to_tsquery('дедка <-> дедка'); ?column? ---------- t (1 row)
Обычный индекс GIN может выдать документы, в которых есть обе лексемы, но проверить расстояние между ними можно, только заглянув в tsvector:

postgres=# select to_tsvector('Бабка за дедку, дедка за репку...'); to_tsvector ------------------------------ 'бабк':1 'дедк':3,4 'репк':6 (1 row)
В индексе RUM каждая лексема не просто ссылается на строки таблицы: вместе с каждым TID-м лежит и список позиций, в которых лексема встречается в документе. Вот как можно представить себе индекс, созданный на уже хорошо знакомой нам таблице с белой березой:

postgres=# create extension rum; CREATE EXTENSION postgres=# create index on ts using rum(doc_tsv); CREATE INDEX

Серые квадраты на рисунке — добавленная позиционная информация:

Чтобы посмотреть, как индекс работает на реальных данных, воспользуемся известным нам архивом рассылки pgsql-hackers.

fts=# alter table mail_messages add column tsv tsvector; ALTER TABLE fts=# set default_text_search_config = default; SET fts=# update mail_messages set tsv = to_tsvector(body_plain); ... UPDATE 356125
Вот как выполняется запрос, использующий фразовый поиск, с индексом GIN:

fts=# create index tsv_gin on mail_messages using gin(tsv); CREATE INDEX fts=# explain (costs off, analyze) select * from mail_messages where tsv @@ to_tsquery('hello <-> hackers'); QUERY PLAN --------------------------------------------------------------------------------- Bitmap Heap Scan on mail_messages (actual time=2.490..18.088 rows=259 loops=1) Recheck Cond: (tsv @@ to_tsquery('hello <-> hackers'::text)) Rows Removed by Index Recheck: 1517 Heap Blocks: exact=1503 -> Bitmap Index Scan on tsv_gin (actual time=2.204..2.204 rows=1776 loops=1) Index Cond: (tsv @@ to_tsquery('hello <-> hackers'::text)) Planning time: 0.266 ms Execution time: 18.151 ms (8 rows)
Как видно из плана, GIN-индекс используется, но возвращает 1776 потенциальных совпадений, из которых остается 259, а 1517 отбрасываются на этапе перепроверки.

Удалим теперь GIN-индекс и построим RUM.

fts=# drop index tsv_gin; DROP INDEX fts=# create index tsv_rum on mail_messages using rum(tsv); CREATE INDEX
Теперь в индексе есть вся необходимая информация и поиск выполняется точно:

fts=# explain (costs off, analyze) select * from mail_messages where tsv @@ to_tsquery('hello <-> hackers'); QUERY PLAN -------------------------------------------------------------------------------- Bitmap Heap Scan on mail_messages (actual time=2.798..3.015 rows=259 loops=1) Recheck Cond: (tsv @@ to_tsquery('hello <-> hackers'::text)) Heap Blocks: exact=250 -> Bitmap Index Scan on tsv_rum (actual time=2.768..2.768 rows=259 loops=1) Index Cond: (tsv @@ to_tsquery('hello <-> hackers'::text)) Planning time: 0.245 ms Execution time: 3.053 ms (7 rows)

Сортировка по релевантности

Для того, чтобы выдавать документы сразу в нужном порядке, индекс RUM поддерживает упорядочивающие операторы, о которых у нас шла речь в части про GiST. Расширение rum определяет такой оператор <=>, возвращающий некое расстояние между документом (tsvector) и запросом (tsquery). Например:

fts=# select to_tsvector('Бабка за дедку, дедка за репку...') <=> to_tsquery('репка'); ?column? ---------- 16.4493 (1 row)

fts=# select to_tsvector ('Бабка за дедку, дедка за репку…') <=> to_tsquery ('дедка');
? column?
----------
13.1595
(1 row)

Документ оказался более релевантен первому запросу, чем второму: чем чаще в документе встречается слово, тем менее оно «ценно».

Снова попробуем сравнить GIN и RUM на относительно большом объеме данных: выберем десять наиболее релевантных документов, содержащих «hello» и «hackers».

fts=# explain (costs off, analyze) select * from mail_messages where tsv @@ to_tsquery('hello & hackers') order by ts_rank(tsv,to_tsquery('hello & hackers')) limit 10; QUERY PLAN --------------------------------------------------------------------------------------------- Limit (actual time=27.076..27.078 rows=10 loops=1) -> Sort (actual time=27.075..27.076 rows=10 loops=1) Sort Key: (ts_rank(tsv, to_tsquery('hello & hackers'::text))) Sort Method: top-N heapsort Memory: 29kB -> Bitmap Heap Scan on mail_messages (actual ... rows=1776 loops=1) Recheck Cond: (tsv @@ to_tsquery('hello & hackers'::text)) Heap Blocks: exact=1503 -> Bitmap Index Scan on tsv_gin (actual ... rows=1776 loops=1) Index Cond: (tsv @@ to_tsquery('hello & hackers'::text)) Planning time: 0.276 ms Execution time: 27.121 ms (11 rows)
GIN-индекс возвращает 1776 совпадений, которые затем отдельно сортируются для выборки десяти наиболее подходящих.

С индексом RUM запрос выполняется простым индексным сканированием: никакие лишние документы не просматриваются, никакой отдельной сортировки не требуется:

fts=# explain (costs off, analyze) select * from mail_messages where tsv @@ to_tsquery('hello & hackers') order by tsv <=> to_tsquery('hello & hackers') limit 10; QUERY PLAN -------------------------------------------------------------------------------------------- Limit (actual time=5.083..5.171 rows=10 loops=1) -> Index Scan using tsv_rum on mail_messages (actual ... rows=10 loops=1) Index Cond: (tsv @@ to_tsquery('hello & hackers'::text)) Order By: (tsv <=> to_tsquery('hello & hackers'::text)) Planning time: 0.244 ms Execution time: 5.207 ms (6 rows)

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

Индекс RUM, как и GIN, можно построить по нескольким полям. Но если в GIN лексемы разных столбцов хранятся независимо друг от друга, то RUM позволяет «связать» основное поле (tsvector в нашем случае) с дополнительным. Для этого надо воспользоваться специальным классом операторов rum_tsvector_addon_ops:

fts=# create index on mail_messages using rum(tsv rum_tsvector_addon_ops, sent) with (attach='sent', to='tsv'); CREATE INDEX
Такой индекс можно использовать, чтобы выдавать результаты в порядке сортировки по дополнительному полю:

fts=# select id, sent, sent <=> '2017-01-01 15:00:00' from mail_messages where tsv @@ to_tsquery('hello') order by sent <=> '2017-01-01 15:00:00' limit 10; id | sent | ?column? ---------+---------------------+---------- 2298548 | 2017-01-01 15:03:22 | 202 2298547 | 2017-01-01 14:53:13 | 407 2298545 | 2017-01-01 13:28:12 | 5508 2298554 | 2017-01-01 18:30:45 | 12645 2298530 | 2016-12-31 20:28:48 | 66672 2298587 | 2017-01-02 12:39:26 | 77966 2298588 | 2017-01-02 12:43:22 | 78202 2298597 | 2017-01-02 13:48:02 | 82082 2298606 | 2017-01-02 15:50:50 | 89450 2298628 | 2017-01-02 18:55:49 | 100549 (10 rows)
Здесь мы ищем подходящие строки, расположенные как можно ближе к указанной дате, не важно, раньше или позже. Чтобы получить результаты, строго предшествующие дате (или следующие за ней), надо воспользоваться операцией <=| (или |=>).

Запрос, как мы и ожидаем, выполняется простым индексным сканированием:

ts=# explain (costs off) select id, sent, sent <=> '2017-01-01 15:00:00' from mail_messages where tsv @@ to_tsquery('hello') order by sent <=> '2017-01-01 15:00:00' limit 10; QUERY PLAN --------------------------------------------------------------------------------- Limit -> Index Scan using mail_messages_tsv_sent_idx on mail_messages Index Cond: (tsv @@ to_tsquery('hello'::text)) Order By: (sent <=> '2017-01-01 15:00:00'::timestamp without time zone) (4 rows)
Если бы мы создали индекс без дополнительной информации о связи полей, то для аналогичного запроса пришлось бы выполнять сортировку всех полученных от индекса результатов.

Конечно, кроме даты в RUM-индекс можно добавить поля и других типов данных — поддерживаются практически все базовые типы. Например, интернет-магазин может быстро показывать товары по новизне (дата), цене (numeric), популярности или размеру скидки (целое или плавающая точка).

Другие классы операторов

Для полноты картины стоит сказать и про другие доступные классы операторов.

Начнем с rum_tsvector_hash_ops и rum_tsvector_hash_addon_ops. Они во всем аналогичны уже рассмотренным выше rum_tsvector_ops и rum_tsvector_addon_ops, но в индексе сохраняется не сама лексема, а ее хеш-код. Это может уменьшить размер индекса, но, разумеется, делает поиск менее точным и требующим перепроверки. Кроме того, индекс перестает поддерживать поиск частичных совпадений.

Любопытен класс операторов rum_tsquery_ops. Он позволяет решать «обратную» задачу: находить запросы, которые соответствуют документу. Зачем это может понадобиться? Например, подписать пользователя на новые товары по его фильтру. Или автоматически классифицировать новые документы. Вот простой пример:

fts=# create table categories(query tsquery, category text); CREATE TABLE fts=# insert into categories values (to_tsquery('vacuum | autovacuum | freeze'), 'vacuum'), (to_tsquery('xmin | xmax | snapshot | isolation'), 'mvcc'), (to_tsquery('wal | (write & ahead & log) | durability'), 'wal'); INSERT 0 3 fts=# create index on categories using rum(query); CREATE INDEX

fts=# select array_agg (category)
from categories
where to_tsvector (
  'Hello hackers, the attached patch greatly improves performance of tuple
   freezing and also reduces size of generated write-ahead logs.'
) @@ query;
  array_agg
--------------
{vacuum, wal}
(1 row)

Остаются классы операторов rum_anyarray_ops и rum_anyarray_addon_ops — они предназначены для работы не с tsvector, а с массивами. Для GIN это уже рассматривалось в прошлый раз, так что нет резона повторяться.

Размер индекса и журнала предзаписи

Понятно, что, раз RUM содержит больше информации, чем GIN, то и места он будет занимать больше. В прошлый раз мы сравнивали размеры разных индексов; добавим в эту таблицу и RUM:

rum | gin | gist | btree --------+--------+--------+-------- 457 MB | 179 MB | 125 MB | 546 MB
Как видно, объем вырос довольно существенно — такова плата за быстрый поиск.

Еще один неочевидный момент, на который стоит обратить внимание, связан с тем, что RUM является расширением, то есть его можно устанавливать, не внося никаких изменений в ядро системы. Это стало возможным в версии 9.6 благодаря патчу, который сделал Александр Коротков. Одна из задач, которые при этом пришлось решить — генерация журнальных записей. Механизм журналирования обязан быть абсолютно надежным, поэтому расширение нельзя пускать в эту кухню. Вместо того, чтобы позволять расширению создавать свои собственные типы журнальных записей, сделано так: код расширения сообщает о намерении изменить страницу, вносит в нее любые изменения и сигнализирует о завершении, а уже ядро системы сравнивает старую и новую версии страницы и само генерирует необходимые унифицированные журнальные записи.

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

Из-за этого активно изменяющийся RUM-индекс может генерировать журнальные записи существенно большего размера, чем GIN (который, будучи не расширением, а частью ядра, управляет журналом сам). Степень этого неприятного эффекта сильно зависит от реальной нагрузки, но, чтобы как-то почувствовать проблему, давайте попробуем несколько раз удалить и добавить некоторое количество строк, перемежая эти действия очисткой (vacuum). Оценить размер журнальных записей можно так: в начале и в конце запомнить позицию в журнале функцией pg_current_wal_location (до десятой верcии — pg_current_xlog_location) и затем посмотреть на их разность.

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

fts=# select pg_current_wal_location() as start_lsn \gset

fts=# insert into mail_messages (parent_id, sent, subject, author, body_plain, tsv)
select parent_id, sent, subject, author, body_plain, tsv
from mail_messages where id % 100 = 0;
INSERT 0 3576
fts=# delete from mail_messages where id % 100 = 99;
DELETE 3590
fts=# vacuum mail_messages;
VACUUM

fts=# insert into mail_messages (parent_id, sent, subject, author, body_plain, tsv)
select parent_id, sent, subject, author, body_plain, tsv
from mail_messages where id % 100 = 1;
INSERT 0 3605
fts=# delete from mail_messages where id % 100 = 98;
DELETE 3637
fts=# vacuum mail_messages;
VACUUM

fts=# insert into mail_messages (parent_id, sent, subject, author, body_plain, tsv)
select parent_id, sent, subject, author, body_plain, tsv from mail_messages
where id % 100 = 2;
INSERT 0 3625
fts=# delete from mail_messages where id % 100 = 97;
DELETE 3668
fts=# vacuum mail_messages;
VACUUM

fts=# select pg_current_wal_location () as end_lsn \gset
fts=# select pg_size_pretty (:'end_lsn':: pg_lsn — :'start_lsn':: pg_lsn);
pg_size_pretty
----------------
3114 MB
(1 row)

Итак, получилось около 3 ГБ. А если тот же эксперимент повторить с индексом GIN, будет всего около 700 МБ.

Поэтому хотелось бы иметь другой алгоритм, находящий минимальное количество операций вставки и удаления, с помощью которых одно состояние страницы можно привести к другому — аналогично тому, как работает утилита diff. Такой алгоритм уже реализовал Олег Иванов, его патч обсуждается. В приведенном примере этот патч, ценой небольшого замедления, позволяет сократить объем журнальных записей в полтора раза, до 1900 МБ.

Свойства

Традиционно посмотрим на свойства метода доступа rum (запросы приводились ранее), обратив внимание на отличия от gin.

Свойства метода:

name | pg_index_has_property ---------------+----------------------- clusterable | f index_scan | t -- f для gin bitmap_scan | t backward_scan | f
Отметим, что RUM, в отличие от GIN, поддерживает индексное сканирование — иначе нельзя было бы получить ровно необходимое количество результатов в запросах с фразой limit. Соответственно, нет необходимости и в аналоге параметра gin_fuzzy_search_limit. Ну и, как следствие, индекс использоваться для поддержки ограничений исключения.

Свойства уровня столбца:

Здесь отличие в том, что RUM поддерживает упорядочивающие операторы. Хотя и не для всех классов операторов: например, для tsquery_ops будет false.

Продолжение следует.