Ускорение метода RUM полнотекстового поиска в PostgreSQL для запросов по индексу с разнородными лексемами

Для текстового поиска в PostgreSQL используется вспомогательный «векторизованный» формат TSvector, который упрощенно описывает текст. Он хранит список отдельных лексем (единиц, совпадающих с любой грамматической формой данного слова) и к каждой лексеме — набор позиций (номеров слов от начала «текста»). С его помощью можно находить записи базы данных, в текстовых полях которых встречаются искомые:

комбинации слов в любых грамматических формах, соединенные логическими операторами & (AND), | (OR) и !(NOT);
фразы: слова, которые стоят в тексте рядом или на заданном расстоянии (по запросу: 'волна <2> перехлест'::tsquery будет найдено «волны с перехлестом»);
логические комбинации фраз и слов.

Выглядит TSvector так:

select to_tsvector('pg_catalog.russian','Джон Донн уснул, уснуло все вокруг. Уснули стены, пол, постель, картины, уснули стол, ковры, засовы, крюк, весь гардероб, буфет, свеча, гардины.');
---------------------------------------------------
 'буфет':19 'ве':17 'вокруг':6 'гардероб':18 'гардин':21 'джон':1 'дон':2 'засов':15 'картин':11 'ковр':14 'крюк':16 'пол':9 'постел':10 'свеч':20 'стен':8 'стол':13 'уснул':3,4,7,12

Ускорение поиска: GIN и RUM

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

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

Если в запросе есть только слова с логическими операторами, GIN и RUM работают одинаково. Если же в запросе есть фразы, то при поиске надо учитывать не только вхождение слов, но и расстояние между ними.

Так как в GIN-индексе есть только лексемы, он выдаст записи, содержащие запрошенные слова, независимо от того, составляют они фразу, или нет. Базе данных придется перепроверить все эти записи, чтобы найти те, где эти слова действительно образуют искомую фразу. Перепроверка может занимать существенное время, если редко употребляемая фраза содержит частые в лексиконе слова. С другой стороны, в таком индексе не тратится место на хранение чего-то, кроме лексем и указателей на записи, в которых встречаются соответствующие слова.

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

Неоднородные лексемы. Метки. Полнотекстовый поиск по нескольким полям и не только

Полнотекстовый поиск PostgreSQL можно использовать при поиске сразу по нескольким полнотекстовым полям. Например, название, аннотация и полный текст книги. И находить слова и фразы или только в названии, или и в названии, и в полном тексте и т.п. — как хотим.

Для этого в лексемах TSvector, кроме слова и позиции, можно (но не обязательно) сохранить четыре метки: A, B, C или D. Они не обязательно должны быть назначены именно по разным полям. Можно как угодно, по частям речи, к примеру, если вдруг мы не хотим считать одинаковыми сходные в написании глаголы и существительные.

В запросе к типу TSVector (он называется TSQuery) можно (но не обязательно) использовать метки, которым должна удовлетворять каждая лексема:

'Рим:a & перехлестом:ab'::TSQuery

Несмотря на кажущуюся широту запроса, кроме «Писем Римскому другу» Бродского, вряд ли много произведений содержат что-то относящееся к перехлесту и одновременно с Рим в названии.

Что происходит с этими метками, если построить индекс?

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

Как обрабатывается запрос к индексу RUM

Упрощенно запрос к индексу (RUM) обрабатывается в два этапа:

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

Второй этап реализован методом consistent (функция rum_tsquery_consistent() — выдает, удовлетворяет ли найденная в индексе запись запросу). Для этого из RUM она вызывает в PostgresSql функцию TS_execute(), которая реализует рекурсивное дерево проверки логической структуре запроса. Узлы этого дерева — операторы, листья — логические результаты определения, удовлетворяет ли запись в индексе операнду, ветви — промежуточные результаты. Листья “проверяются” снова в RUM функцией проверки checkcondition_rum(), которую это дерево вызывает, когда на данной ветви уже нет операторов-узлов, а остался только операнд-лист.

Если узел — фразовый оператор, то TS_execute() вызывает другую функцию TS_phrase_execute(), которая проверяет (1) взаимное положение лексем, соединенных фразовым оператором. (2) логические операции, стоящие внутри фразового. Удивительно, что внутри фразового оператора логические операции работают другим образом, чем вне. Так запрос (a & b) <-> c не дает то же самое, что и (a <-> с) & (b <->c). В первом примере накладывается дополнительное ограничение, чтобы позиции a и b в tsvector совпадали, т.е. так как позиции в tsvector уникальны, то a и b не могут быть отдельными словами в поиске, а только разными весами одного слова. Это свойство требуется для фразового поиска в таких языках, как немецкий, где употребляется слияние многих слов в одно. Для фразового поиска оно разделяется на разные корни-лексемы, которые получают один и тот же номер позиции в tsvector. Таким образом, первый из приведенных запросов означает одно составное слово из корней a и b перед одним словом с, а второй — оба этих корня, стоящих перед словом с в тексте, возможно, в двух разных позициях.

В листах дерева (и логического, и фразового) обратно из RUM вызывается функция проверки одиночного операнда checkcondition_rum(). Она выдает единственный результат да/нет в логический оператор, а во фразовый — список позиций для лексемы, в которых она встречается в данной записи.

Между логическим деревом и функцией проверки операнда соблюдается разграничение: первое не знает ничего об операндах, кроме результатов их сравнения с записью в индексе, вторая — ничего не знает о логике, как ее результаты могут быть логически связаны с другими. В случае фразового дерева это разграничение имеет исключение в виде передачи в него правильных позиций для каждого операнда и “сборкой” фразовым оператором результата по совпадению этих позиций с “упрощенным” поведением логических операторов внутри фразового (см. выше).

Проблема проверки отрицательных значений и использование трехпозиционной логики в индексе без весов и с весами

Среди логических операторов в запросе может оказаться ! (NOT). Если есть однозначное соответствие наличия лексемы в индексе и в тексте, то оператор ! полностью определен как над отдельным операндом (лексема не содержится в тексте), так и над логической комбинацией операндов. Это реализуется, если в запросе нет весов (которые требуют селекции только части записей с вхождением лексемы в индекс).

GIN и GiST — неожиданная проблема

Хотя в самих индексах веса отсутствуют, лексемы в запросе они вполне могут содержать выбор по ним. Поэтому запрос A & !B может быть проверен по индексу, а А & !B:d — нет. Отрицание !B:d в последнем запросе может быть положительным, если в тексте содержится, например, B:c (в индексе В в таком случае тоже содержится — без веса).

Раньше в индексе GIN при запросах с весами устанавливался флаг для перепроверки результата по таблице. Однако перепроверка может выбросить ложноположительные значения, которые вернул индекс, но ничего не может поделать с ложноотрицательными, которые уже выброшены при проверке. Так как оператор ! меняет true на false, то для B:d нет бинарного значения, которое гарантированно не сделает его в дереве операндов ложноотрицательным.

Именно такие запросы А & !B:d по индексам GIN и GiST теряли до сих пор ложнотрицательные тексты, содержащие A & B:c — они оказывались выброшенными до перепроверки.

Чтобы это исправить, надо в таких “сомнительных” случаях передавать от функции проверки операнда в дерево запроса третий результат — maybe (ни да, ни нет), который гарантированно дойдет до корня логического дерева, независимо на отрицания и инициирует перепроверку. Изменение передаваемого результата с двоичного на трехзначный решило описанную проблему в индексах GIN и GiST (после этого коммита в PostgreSQL https://github.com/postgres/postgres/commit/2f2007fbb255be178aca586780967f43885203a7 )

RUM — как получить точный результат без перепроверки

В индексе RUM веса есть, поэтому при запросе A:b он может выдавать:

1. в случае логического запроса только те записи, где слово A встречается хотя бы в одной позиции с весом b

2. в случае фразового запроса — номера позиций слова A с весом b

Отрицательный оператор при этом определен как двойной: !B:d = B:abc | !B

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

Таким образом, чтобы отрицательный оператор в индексе RUM работал корректно, есть две возможности:

1. Аналогично GIN: все операнды с весами должны выдавать неопределенный результат сравнения — maybe, который в корне дерева вызовет функцию перепроверки.

Это позволило избавиться от потери результатов как в GIN/GiST (см. выше). Но если результат запроса с весами в любом случае неопределенный и требует перепроверки, то и селекция весов в функции проверки операнда не нужна: она может ускорить поиск, избавив нас от перепроверки результатов с весами.

2. Отрицательный оператор не должен инвертировать yes на no, если в листьях выше узла есть операнды с весами.

Во этом случае можно выбирать операнды входящие с правильными весами, если ближе к корню дерева от операндов с весами не будет оператора ! (например C:d & ! (A & B) ). Совершенно корректным будет передавать от операнда до корня дерева yes, если хотя бы в одной позиции внутри лексемы вес соответствует операнду из запроса и no: если лексема отсутствует или ни одна из позиций не входит с правильным весом. Такие запросы с весами, но без отрицаний выдают точный результат, который не требуют перепроверки, что ускоряет поиск.

Оператор ! должен выдавать maybe, если хотя бы один из операндов внутри него содержат веса, а если нет — то можно обычным образом инвертировать результат. Проверка в промежуточном узле дерева, есть ли веса в операндах ближе к листьям, выглядит некоторым превышением полномочий функции логического перебора только операторов (которая по умолчанию не знает ничего об операндах). Но технически это не сложно и позволяет не замедлять перепроверками запросы, содержащими оператор !, но не содержащими весов в операндах ближе него к листьям (например, запросы вида C:d & !(A & B) )

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

Таким образом, получилось существенное ускорение в положительных запросах с весами из-за того, что они не требуют перепроверки. Все запросы без весов имеют такую же скорость, как и раньше. Запросы, в которых операнд с весом стоит “внутри” оператора ! должны быть перепроверены аналогично GIN (новому, корректному поведению, которое не теряет результаты).

(Правильное поведение RUM никак не зависит от того, внесено ли изменение в PostgreSQL https://github.com/postgres/postgres/commit/2f2007fbb255be178aca586780967f43885203a7, он будет правильно работать и с более ранними и с новыми версиями)

Что стало. Лучше или хуже? Тест

Тесты я делал на обыкновенном ноутбуке (i7 2300Mhz 16Mb RAM, HDD) по базе рассылок постгрес-разработчиков с 1998 по 2016 годы http://www.sai.msu.su/~megera/postgres/files/pglist-28-04-16.dump.gz построив по ним три индекса: GIN, RUM до изменений (https://github.com/postgrespro/rum/commit/bc917c9f0d667432412df998a3fe6b6c935b3053) и RUM после изменений (самый свежий коммит на сегодня, совместимый с 13 версией Постгрес https://github.com/postgrespro/rum/commit/3d331aa8faaff06e48172084201f1907d6eed471 )

Импортируем базу данных

psql -d postgres -c '\i ~/Downloads/pglist-28-04-16.dump.gz'

Удалим старый(если есть), соберем новый модуль RUM и подключим его:

psql -d postgres -c 'DROP EXTENSION RUM CASCADE;'

cd ~/rum

make USE_PGXS=1 distclean

make USE_PGXS=1

make USE_PGXS=1 install

psql -d postgres -c 'CREATE EXTENSION RUM;'

Построим индексы:

CREATE INDEX pglist_fts_idx ON pglist USING gin (fts);

CREATE INDEX pglist_rum_idx ON pglist USING rum (fts rum_tsvector_ops);

SET enable_seqscan=off;

(Если мы хотим отключить все индексы кроме одного, чтобы протестировать выборку именно по нему, а не как решит планировщие Постгрес, удобно использовать такую команду для отключения индекса update pg_index set indisvalid = false where indexrelid = 'pglist_rum_idx'::regclass; )

Сделаем запрос с примерно 50% селективностью по меткам.

explain analyse SELECT * FROM pglist WHERE fts @@ to_tsquery('pg_catalog.english', 'Bartunov:bc & Oleg:c');

GIN ----------
Bitmap Heap Scan on pglist  (cost=44.20..143.59 rows=25 width=1242) (actual time=2.735..90.144 rows=2567 loops=1)
   Recheck Cond: (fts @@ '''bartunov'':BC & ''oleg'':C'::tsquery)
   Rows Removed by Index Recheck: 2111
   Heap Blocks: exact=3750
   ->  Bitmap Index Scan on pglist_fts_idx  (cost=0.00..44.19 rows=25 width=0) (actual time=1.954..1.954 rows=4678 loops=1)
         Index Cond: (fts @@ '''bartunov'':BC & ''oleg'':C'::tsquery)
 Planning Time: 4.533 ms
 Execution Time: 90.686 ms

RUM(orig) ----------
 Index Scan using pglist_rum_idx on pglist  (cost=48.00..152.44 rows=25 width=1242) (actual time=3.143..95.514 rows=2567 loops=1)
   Index Cond: (fts @@ '''bartunov'':BC & ''oleg'':C'::tsquery)
   Rows Removed by Index Recheck: 2111
 Planning Time: 3.158 ms
 Execution Time: 96.090 ms
RUM(mod) ----------
Index Scan using pglist_rum_idx on pglist  (cost=48.00..152.44 rows=25 width=1242) (actual time=3.541..21.324 rows=2567 loops=1)
   Index Cond: (fts @@ '''bartunov'':BC & ''oleg'':C'::tsquery)
 Planning Time: 3.076 ms
 Execution Time: 21.736 ms

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

Попробуем сделать хуже: более многопозиционный по количеству меток в каждой лексеме из запроса. Селективность по результатам прежняя — около 50%.

explain analyse SELECT * FROM pglist WHERE fts @@ to_tsquery('pg_catalog.english', 'Tom:b & lane:c');

GIN -----------
Bitmap Heap Scan on pglist  (cost=527.41..111288.90 rows=52569 width=1242) (actual time=84.123..1792.180 rows=103610 loops=1)
   Recheck Cond: (fts @@ '''tom'':B & ''lane'':C'::tsquery)
   Rows Removed by Index Recheck: 119203
   Heap Blocks: exact=105992
   ->  Bitmap Index Scan on pglist_fts_idx  (cost=0.00..514.27 rows=52569 width=0) (actual time=61.065..61.065 rows=222813 loops=1)
         Index Cond: (fts @@ '''tom'':B & ''lane'':C'::tsquery)
 Planning Time: 3.210 ms
 Execution Time: 1808.157 ms

RUM(orig) ----------
Bitmap Heap Scan on pglist  (cost=535.41..111296.90 rows=52569 width=1242) (actual time=156.136..1870.167 rows=103610 loops=1)
   Recheck Cond: (fts @@ '''tom'':B & ''lane'':C'::tsquery)
   Rows Removed by Index Recheck: 119203
   Heap Blocks: exact=105992
   ->  Bitmap Index Scan on pglist_rum_idx  (cost=0.00..522.27 rows=52569 width=0) (actual time=132.542..132.542 rows=222813 loops=1)
         Index Cond: (fts @@ '''tom'':B & ''lane'':C'::tsquery)
 Planning Time: 3.135 ms
 Execution Time: 1887.881 ms
RUM(mod) ----------
Bitmap Heap Scan on pglist  (cost=535.41..111296.90 rows=52569 width=1242) (actual time=151.851..486.524 rows=103610 loops=1)
   Recheck Cond: (fts @@ '''tom'':B & ''lane'':C'::tsquery)
   Heap Blocks: exact=71165
   ->  Bitmap Index Scan on pglist_rum_idx  (cost=0.00..522.27 rows=52569 width=0) (actual time=137.607..137.607 rows=103610 loops=1)
         Index Cond: (fts @@ '''tom'':B & ''lane'':C'::tsquery)
 Planning Time: 3.203 ms
 Execution Time: 498.604 ms

Выигрыш времени в 3.5 раза.

Фразовый поиск с низкой селективностью. Почти 100% выбранных в индексе данных удовлетворяют запросу.

explain analyse SELECT * FROM pglist WHERE fts @@ to_tsquery('pg_catalog.english', 'Tom <-> lane');

GIN -----------
 Bitmap Heap Scan on pglist  (cost=527.41..111288.90 rows=52569 width=1242) (actual time=85.355..1857.377 rows=222777 loops=1)
   Recheck Cond: (fts @@ '''tom'' <-> ''lane'''::tsquery)
   Rows Removed by Index Recheck: 36
   Heap Blocks: exact=105992
   ->  Bitmap Index Scan on pglist_fts_idx  (cost=0.00..514.27 rows=52569 width=0) (actual time=61.188..61.188 rows=222813 loops=1)
         Index Cond: (fts @@ '''tom'' <-> ''lane'''::tsquery)
 Planning Time: 3.256 ms
 Execution Time: 1887.208 ms

RUM (orig) ----------
BBitmap Heap Scan on pglist  (cost=535.41..111296.90 rows=52569 width=1242) (actual time=186.795..716.592 rows=222777 loops=1)
   Recheck Cond: (fts @@ '''tom'' <-> ''lane'''::tsquery)
   Heap Blocks: exact=105978
   ->  Bitmap Index Scan on pglist_rum_idx  (cost=0.00..522.27 rows=52569 width=0) (actual time=163.717..163.717 rows=222777 loops=1)
         Index Cond: (fts @@ '''tom'' <-> ''lane'''::tsquery)
 Planning Time: 4.075 ms
 Execution Time: 740.540 ms
RUM (mod) ----------
Bitmap Heap Scan on pglist  (cost=535.41..111296.90 rows=52569 width=1242) (actual time=187.515..699.380 rows=222777 loops=1)
   Recheck Cond: (fts @@ '''tom'' <-> ''lane'''::tsquery)
   Heap Blocks: exact=105978
   ->  Bitmap Index Scan on pglist_rum_idx  (cost=0.00..522.27 rows=52569 width=0) (actual time=162.768..162.768 rows=222777 loops=1)
         Index Cond: (fts @@ '''tom'' <-> ''lane'''::tsquery)
 Planning Time: 3.187 ms
 Execution Time: 723.066 ms

Потеря времени в GIN идет на перепроверку. Она зависит от абсолютного числа перепроверяемых запросов, а от селективности не зависит (это видно из сравнения с предыдущим результатом). Так как этот запрос не содержит весов, он одинаково выполняется и в модифицированном, и в немодифицированном RUM.

Контрольный запрос: чисто логический без меток. C ним перепроверка не нужна ни одному из трех методов. GIN показывает немного лучший результат за счет меньшего размера индекса.

explain analyse SELECT * FROM pglist WHERE fts @@ to_tsquery('pg_catalog.english', 'Tom & lane');

GIN -----------
Bitmap Heap Scan on pglist  (cost=527.41..111288.90 rows=52569 width=1242) (actual time=88.311..615.489 rows=222813 loops=1)
   Recheck Cond: (fts @@ '''tom'' & ''lane'''::tsquery)
   Heap Blocks: exact=105992
   ->  Bitmap Index Scan on pglist_fts_idx  (cost=0.00..514.27 rows=52569 width=0) (actual time=65.490..65.490 rows=222813 loops=1)
         Index Cond: (fts @@ '''tom'' & ''lane'''::tsquery)
 Planning Time: 2.989 ms
 Execution Time: 634.919 ms

RUM(orig) -----------
Bitmap Heap Scan on pglist  (cost=535.41..111296.90 rows=52569 width=1242) (actual time=162.540..683.670 rows=222813 loops=1)
   Recheck Cond: (fts @@ '''tom'' & ''lane'''::tsquery)
   Heap Blocks: exact=105992
   ->  Bitmap Index Scan on pglist_rum_idx  (cost=0.00..522.27 rows=52569 width=0) (actual time=134.477..134.477 rows=222813 loops=1)
         Index Cond: (fts @@ '''tom'' & ''lane'''::tsquery)
 Planning Time: 3.116 ms
 Execution Time: 705.019 ms
RUM(mod) -----------
Bitmap Heap Scan on pglist  (cost=535.41..111296.90 rows=52569 width=1242) (actual time=173.801..682.293 rows=222813 loops=1)
   Recheck Cond: (fts @@ '''tom'' & ''lane'''::tsquery)
   Heap Blocks: exact=105992
   ->  Bitmap Index Scan on pglist_rum_idx  (cost=0.00..522.27 rows=52569 width=0) (actual time=150.079..150.079 rows=222813 loops=1)
         Index Cond: (fts @@ '''tom'' & ''lane'''::tsquery)
 Planning Time: 2.926 ms
 Execution Time: 704.734 ms

Мы помним, что отрицательный оператор, внутри которого есть операнды с весами обязан быть перепроверен. Оригинальный RUM справился быстрее всех, но нашел всего половину результатов! Ниже результат перепроверки последовательным поиском из которого убеждаемся, что именно старое поведение было неправильным, а новое — правильное.

explain analyse SELECT * FROM pglist WHERE fts @@ to_tsquery('pg_catalog.english', 'Oleg & !Bartunov:c');

GIN -----------
Bitmap Heap Scan on pglist  (cost=87.09..17440.24 rows=5044 width=1242) (actual time=3.171..120.598 rows=3961 loops=1)
   Recheck Cond: (fts @@ '''oleg'' & !''bartunov'':C'::tsquery)
   Rows Removed by Index Recheck: 2563
   Heap Blocks: exact=5110
   ->  Bitmap Index Scan on pglist_fts_idx  (cost=0.00..85.83 rows=5044 width=0) (actual time=2.398..2.398 rows=6524 loops=1)
         Index Cond: (fts @@ '''oleg'' & !''bartunov'':C'::tsquery)
 Planning Time: 3.100 ms
 Execution Time: 121.402 ms

RUM(orig) -----------
Bitmap Heap Scan on pglist  (cost=95.09..17448.24 rows=5044 width=1242) (actual time=3.341..38.289 rows=1846 loops=1)
   Recheck Cond: (fts @@ '''oleg'' & !''bartunov'':C'::tsquery)
   Heap Blocks: exact=1485
   ->  Bitmap Index Scan on pglist_rum_idx  (cost=0.00..93.83 rows=5044 width=0) (actual time=3.123..3.123 rows=1846 loops=1)
         Index Cond: (fts @@ '''oleg'' & !''bartunov'':C'::tsquery)
 Planning Time: 4.012 ms
 Execution Time: 38.774 ms
RUM(mod) -----------
Bitmap Heap Scan on pglist  (cost=95.09..17448.24 rows=5044 width=1242) (actual time=4.802..113.275 rows=3961 loops=1)
   Recheck Cond: (fts @@ '''oleg'' & !''bartunov'':C'::tsquery)
   Rows Removed by Index Recheck: 2563
   Heap Blocks: exact=5110
   ->  Bitmap Index Scan on pglist_rum_idx  (cost=0.00..93.83 rows=5044 width=0) (actual time=4.016..4.016 rows=6524 loops=1)
         Index Cond: (fts @@ '''oleg'' & !''bartunov'':C'::tsquery)
 Planning Time: 2.971 ms
 Execution Time: 114.117 ms

SET enable_seqscan=on;
SET enable_indexscan=off;
SET enable_indexonlyscan=off;

Gather  (cost=1000.00..171915.45 rows=5044 width=1242) (actual time=1.023..2141.792 rows=3961 loops=1)
   Workers Planned: 2
   Workers Launched: 2
   ->  Parallel Seq Scan on pglist  (cost=0.00..170411.05 rows=2102 width=1242) (actual time=0.777..2057.403 rows=1320 loops=3)
         Filter: (fts @@ '''oleg'' & !''bartunov'':C'::tsquery)
         Rows Removed by Filter: 336603
 Planning Time: 3.030 ms
 Execution Time: 2142.293 ms

Отрицательный оператор, внутри которого нет операндов с весами перепроверки не требует. Выигрыш времени по сравнению со старым RUM — в три раза. Cелективность этого запроса по весам около 30%.

explain analyse SELECT * FROM pglist WHERE fts @@ to_tsquery('pg_catalog.english', 'Oleg:c & !Bartunov');

GIN -----------
Bitmap Heap Scan on pglist  (cost=87.09..17440.24 rows=5044 width=1242) (actual time=1.333..35.188 rows=547 loops=1)
   Recheck Cond: (fts @@ '''oleg'':C & !''bartunov'''::tsquery)
   Rows Removed by Index Recheck: 1299
   Heap Blocks: exact=1485
   ->  Bitmap Index Scan on pglist_fts_idx  (cost=0.00..85.83 rows=5044 width=0) (actual time=1.139..1.139 rows=1846 loops=1)
         Index Cond: (fts @@ '''oleg'':C & !''bartunov'''::tsquery)
 Planning Time: 2.902 ms
 Execution Time: 35.359 ms

RUM(orig) -----------
 Bitmap Heap Scan on pglist  (cost=95.09..17448.24 rows=5044 width=1242) (actual time=3.055..37.500 rows=547 loops=1)
   Recheck Cond: (fts @@ '''oleg'':C & !''bartunov'''::tsquery)
   Rows Removed by Index Recheck: 1299
   Heap Blocks: exact=1485
   ->  Bitmap Index Scan on pglist_rum_idx  (cost=0.00..93.83 rows=5044 width=0) (actual time=2.861..2.861 rows=1846 loops=1)
         Index Cond: (fts @@ '''oleg'':C & !''bartunov'''::tsquery)
 Planning Time: 2.951 ms
 Execution Time: 37.808 ms
RUM(mod) -----------
 Bitmap Heap Scan on pglist  (cost=95.09..17448.24 rows=5044 width=1242) (actual time=5.921..12.629 rows=547 loops=1)
   Recheck Cond: (fts @@ '''oleg'':C & !''bartunov'''::tsquery)
   Heap Blocks: exact=476
   ->  Bitmap Index Scan on pglist_rum_idx  (cost=0.00..93.83 rows=5044 width=0) (actual time=5.770..5.770 rows=547 loops=1)
         Index Cond: (fts @@ '''oleg'':C & !''bartunov'''::tsquery)
 Planning Time: 3.126 ms
 Execution Time: 12.947 ms

И, наконец, запрос с фразовым поиском, с метками и селективностью около 10%. Новый RUM обрабатывает его в 8 раз быстрее старого!

explain analyse SELECT * FROM pglist WHERE fts @@ to_tsquery('pg_catalog.english', 'Oleg:c <-> !Bartunov');

GIN -----------
Bitmap Heap Scan on pglist  (cost=87.09..17440.24 rows=5044 width=1242) (actual time=2.635..116.817 rows=551 loops=1)
   Recheck Cond: (fts @@ '''oleg'':C <-> !''bartunov'''::tsquery)
   Rows Removed by Index Recheck: 5973
   Heap Blocks: exact=5110
   ->  Bitmap Index Scan on pglist_fts_idx  (cost=0.00..85.83 rows=5044 width=0) (actual time=1.935..1.935 rows=6524 loops=1)
         Index Cond: (fts @@ '''oleg'':C <-> !''bartunov'''::tsquery)
 Planning Time: 3.706 ms
 Execution Time: 117.020 ms

RUM(orig) -----------
Bitmap Heap Scan on pglist  (cost=95.09..17448.24 rows=5044 width=1242) (actual time=5.585..103.667 rows=551 loops=1)
   Recheck Cond: (fts @@ '''oleg'':C <-> !''bartunov'''::tsquery)
   Rows Removed by Index Recheck: 4447
   Heap Blocks: exact=4081
   ->  Bitmap Index Scan on pglist_rum_idx  (cost=0.00..93.83 rows=5044 width=0) (actual time=4.965..4.965 rows=4998 loops=1)
         Index Cond: (fts @@ '''oleg'':C <-> !''bartunov'''::tsquery)
 Planning Time: 3.306 ms
 Execution Time: 103.998 ms
RUM(mod) -----------
Bitmap Heap Scan on pglist  (cost=95.09..17448.24 rows=5044 width=1242) (actual time=4.116..8.386 rows=551 loops=1)
   Recheck Cond: (fts @@ '''oleg'':C <-> !''bartunov'''::tsquery)
   Heap Blocks: exact=480
   ->  Bitmap Index Scan on pglist_rum_idx  (cost=0.00..93.83 rows=5044 width=0) (actual time=4.034..4.034 rows=551 loops=1)
         Index Cond: (fts @@ '''oleg'':C <-> !''bartunov'''::tsquery)
 Planning Time: 3.062 ms
 Execution Time: 8.693 ms

Результат

Обработка меток лексем внутри индекса RUM позволяет избежать существенной потери времени на перепроверку результатов. Полнотекстовый поиск с разнородными лексемами в одном индексе в результате модификации ускоряется в несколько раз. Чем выше селективность запроса по меткам, тем больше будет выигрыш времени. На запросах без меток или в случае, когда операнд с меткой стоит внутри отрицания и должен быть перепроверен модификация работает так же, как оригинальный метод RUM: в случае фразового оператора — в разы быстрее, чем GIN, в случае чисто логических операторов — примерно на 10% медленнее.

Кроме того новое поведение индексов RUM и GIN в отличие от старого корректно выдает результаты при использовании оператора ! с операндами, которые содержат отбор по весам.