Оптимизация ORDER BY в полнотекстовом поисковом запросе

У меня есть большая таблица entitiesс ~ 15M записей. Я хочу найти топ-5 строк, соответствующих «хоккею» в их name.

У меня есть полнотекстовый индекс name, который используется:gin_ix_entity_full_text_search_name

Запрос:

 SELECT "entities".*,
         ts_rank(to_tsvector('english', "entities"."name"::text),
         to_tsquery('english', 'hockey'::text)) AS "rank0.48661998202865475"
    FROM "entities" 
         WHERE "entities"."place" = 'f' 
              AND (to_tsvector('english', "entities"."name"::text) @@ to_tsquery('english', 'hockey'::text)) 
         ORDER BY "rank0.48661998202865475" DESC LIMIT 5

Продолжительность 25 623 мс

Объяснить план
1 предел (стоимость = 12666.89..12666.89 строк = 5 ширина = 3116)
2 -> Сортировка (стоимость = 12666.89..12670.18 строк = 6571 ширина = 3116)
3 Ключ сортировки: (ts_rank (to_tsvector ('english' :: regconfig, (name) :: text), '' 'hockey' '' :: tsquery))
4 -> Сканирование кучи растрового изображения на объектах (стоимость = 124.06..12645.06 строк = ширина 6571 = 3116)
5 Перепроверьте Cond: (to_tsvector ('english' :: regconfig, (name) :: text) @@ '' 'hockey' '' :: tsquery)
6 Фильтр: (НЕ место)
7 -> Сканирование индекса растрового изображения для gin_ix_entity_full_text_search_name (стоимость = 0,00..123,74 строки = 6625 ширина = 0)
8 Index Cond: (to_tsvector ('english' :: regconfig, (name) :: text) @@ '' 'hockey' '' :: tsquery)

Я не понимаю, почему он проверяет условие индекса дважды. (Запланируйте шаг 4 и 7). Это из-за моего логического условия ( not place)? Если так, я должен добавить это к своему индексу, чтобы получить очень быстрый запрос? Или условие сортировки делает его медленным?

EXPLAIN ANALYZE вывод:

  Лимит (стоимость = 4447.28..4447.29 строк = 5 ширина = 3116) (фактическое время = 18509.274..18509.282 строк = 5 циклов = 1)
  -> Сортировка (стоимость = 4447.28..4448.41 строк = 2248 ширина = 3116) (фактическое время = 18509.271..18509.273 строк = 5 циклов = 1)
         Ключ сортировки: (ts_rank (to_tsvector ('english' :: regconfig, (name) :: text), '' 'test' '' :: tsquery))
         Метод сортировки: топ-N heapsort Память: 19 КБ
     -> Сканирование кучи растрового изображения на объектах (стоимость = 43.31..4439.82 строки = ширина 2248 = 3116) (фактическое время = 119.003..18491.408 строк = 2533 цикла = 1)
           Перепроверьте Cond: (to_tsvector ('english' :: regconfig, (name) :: text) @@ '' 'test' '' :: tsquery)
           Фильтр: (НЕ место)
           -> Сканирование индекса растрового изображения для gin_ix_entity_full_text_search_name (стоимость = 0,00..43.20 строк = 2266 ширина = 0) (фактическое время = 74.093..74.093 строк = 2593 циклов = 1)
                 Index Cond: (to_tsvector ('english' :: regconfig, (name) :: text) @@ '' 'test' '' :: tsquery)
 Общее время выполнения: 18509,381 мс

Вот мои параметры БД. Он размещен в Heroku на сервисах Amazon. Они описывают его как имеющий 1,7 ГБ ОЗУ, 1 процессор и 1 МБ максимум 1 ТБ.

имя | текущая настройка
------------------------------ + ------------------- -------------------------------------------------- ------------------------------------
 версия | PostgreSQL 9.0.7 на i486-pc-linux-gnu, скомпилированный GCC gcc-4.4.real (Ubuntu 4.4.3-4ubuntu5) 4.4.3, 32-битный
 архив_команда | test -f /etc/postgresql/9.0/main/wal-ed/ARCHIVING_OFF || envdir /etc/postgresql/9.0/resource29857_heroku_com/wal-ed/env wal-e wal-push% p
 архив_режим | на
 archive_timeout | 1 минута
 checkpoint_completion_target | 0.7
 контрольные точки_сегменты | 40
 client_min_messages | уведомление
 cpu_index_tuple_cost | 0,001
 cpu_operator_cost | 0,0005
 cpu_tuple_cost | 0,003
 ffective_cache_size | 1530000kB
 hot_standby | на
 lc_collate | en_US.UTF-8
 lc_ctype | en_US.UTF-8
 listen_addresses | *
 log_checkpoints | на
 log_destination | системный журнал
 log_line_prefix | % u [ЖЕЛТЫЙ]
 log_min_duration_statement | 50мс
 log_min_messages | уведомление
 logging_collector | на
 maintenance_work_mem | 64MB
 max_connections | 500
 max_prepared_transactions | 500
 max_stack_depth | 2MB
 max_standby_archive_delay | -1
 max_standby_streaming_delay | -1
 max_wal_senders | 10
 порт | 
 random_page_cost | 2
 server_encoding | UTF8
 shared_buffers | 415MB
 SSL | на
 syslog_ident | resource29857_heroku_com
 TimeZone | универсальное глобальное время
 wal_buffers | 8MB
 wal_keep_segments | 127
 wal_level | hot_standby
 work_mem | 100MB
 (39 рядов)

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

Похоже, ORDER BYэто медленная часть:

d6ifslbf0ugpu=> EXPLAIN ANALYZE SELECT "entities"."name",
     ts_rank(to_tsvector('english', "entities"."name"::text),
     to_tsquery('english', 'banana'::text)) AS "rank0.48661998202865475"
FROM "entities" 
     WHERE (to_tsvector('english', "entities"."name"::text) @@ to_tsquery('english', 'banana'::text)) 
     LIMIT 5;

QUERY PLAN                                                                         
-----------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=43.31..53.07 rows=5 width=24) (actual time=76.583..103.623 rows=5 loops=1)
->  Bitmap Heap Scan on entities  (cost=43.31..4467.60 rows=2266 width=24) (actual time=76.581..103.613 rows=5 loops=1)
     Recheck Cond: (to_tsvector('english'::regconfig, (name)::text) @@ '''banana'''::tsquery)
     ->  Bitmap Index Scan on gin_ix_entity_full_text_search_name  (cost=0.00..43.20 rows=2266 width=0) (actual time=53.592..53.592 rows=1495 loops=1)
           Index Cond: (to_tsvector('english'::regconfig, (name)::text) @@ '''banana'''::tsquery)
 Total runtime: 103.680 ms

Против с ORDER BY:

d6ifslbf0ugpu=> EXPLAIN ANALYZE SELECT "entities"."name",
     ts_rank(to_tsvector('english', "entities"."name"::text),
     to_tsquery('english', 'banana'::text)) AS "rank0.48661998202865475"
FROM "entities" 
     WHERE (to_tsvector('english', "entities"."name"::text) @@ to_tsquery('english', 'banana'::text)) 
     ORDER BY "rank0.48661998202865475" DESC
     LIMIT 5;

QUERY PLAN                                                                           
---------------------------------------------------------------------------------------------------------------------------------------------------------------
Limit  (cost=4475.12..4475.13 rows=5 width=24) (actual time=15013.735..15013.741 rows=5 loops=1)
->  Sort  (cost=4475.12..4476.26 rows=2266 width=24) (actual time=15013.732..15013.735 rows=5 loops=1)
     Sort Key: (ts_rank(to_tsvector('english'::regconfig, (name)::text), '''banana'''::tsquery))
     Sort Method:  top-N heapsort  Memory: 17kB
     ->  Bitmap Heap Scan on entities  (cost=43.31..4467.60 rows=2266 width=24) (actual time=0.872..15006.763 rows=1495 loops=1)
           Recheck Cond: (to_tsvector('english'::regconfig, (name)::text) @@ '''banana'''::tsquery)
           ->  Bitmap Index Scan on gin_ix_entity_full_text_search_name  (cost=0.00..43.20 rows=2266 width=0) (actual time=0.549..0.549 rows=1495 loops=1)
                 Index Cond: (to_tsvector('english'::regconfig, (name)::text) @@ '''banana'''::tsquery)
 Total runtime: 15013.805 ms

Я все еще не понимаю, почему это медленнее. Похоже, он извлекает такое же количество строк из Bitmap Heap Scan, но это занимает намного больше времени?

То, что я до сих пор не понимаю, почему это медленнее.

То, что сортировка строк будет стоить чего-то , очевидно. Но почему так много?
Без ORDER BY rank0...Postgres можно просто

• выберите первые 5 строк, которые он находит, и прекратите извлекать строки, как только у него будет 5.

  Сканирование кучи растровых изображений на объектах ... rows = 5 ...

• затем вычислите ts_rank()всего 5 строк.

• получить все (1495 в соответствии с вашим планом запроса) подходящие строки.

  Сканирование кучи растровых изображений на объектах ... rows = 1495 ...

• вычислить ts_rank()для всех из них.
• Сортируйте их все, чтобы найти первые 5 согласно вычисленному значению.

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

Сканирование индекса растрового изображения, возможно, должно стать "потерянным", чтобы поместиться в памяти - это снижает его точность от уровня кортежа до уровня страницы. Если вы увеличите work_mem (по крайней мере, для этого одного запроса), вы можете избежать этого. Он не сможет пропустить сканирование кучи растрового изображения в строке 4 или фильтр в строке 6, но может пропустить повторную проверку в строке 5.

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

Возможно, вы захотите рассмотреть индекс KNN - GiST (для K Nearest Neighbor - Generalized Search Tree), который может извлекаться прямо из индекса в порядке сходства, поэтому вам не нужно случайным образом читать все эти кортежи и сортировать их вниз, чтобы найти K лучших матчей.

На сегодняшний день я не думаю, что кто-то реализовал поддержку KNN-GIST для запросов tsearch (хотя я был уверен, что это можно сделать, это просто вопрос, что кто-то нашел время, чтобы сделать это), но, возможно, поддержка триграмм (что это сделано) будет работать для вашего приложения. Основное отличие состоит в том, что при поиске триграмм не используются словари для обозначения и синонимов, как это делает tsearch; вы найдете только точные совпадения слов.

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

CREATE INDEX entities_name_trgm ON entities USING gist (name gist_trgm_ops);

Тогда вы можете искать так:

SELECT
    *,
    name <-> 'banana' AS sim
  FROM entities 
  WHERE name % 'banana'
  ORDER BY sim DESC
  LIMIT 5;

Обратите внимание на используемые операторы и ORDER BYпсевдоним столбца «сходство». Я бы не стал уходить слишком далеко от этого паттерна при его испытании. Индекс по цвету не используется для этого поиска.

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