Почему поиск по триграммам работает так медленно?

Question

[Xaip]

Есть таблица с адресами. Использую GIN индекс для неточного поиска по адресам. Но отклик невероятно медленный при 300к записей поиск по адресу может занимать от 3-6секунд.
База крутится на ssd.

Пример запроса:

EXPLAIN ANALYSE SELECT *, similarity(title, 'г. Санкт-Петербург') FROM addresses
            WHERE title % 'г. Санкт-Петербург' ORDER BY similarity DESC limit 5;

Ответ

Limit  (cost=3114.58..3114.59 rows=5 width=189) (actual time=2952.433..2952.434 rows=5 loops=1)
  ->  Sort  (cost=3114.58..3115.54 rows=383 width=189) (actual time=2952.432..2952.432 rows=5 loops=1)
"        Sort Key: (similarity(title, 'г. Санкт-Петербург'::text)) DESC"
        Sort Method: top-N heapsort  Memory: 26kB
        ->  Bitmap Heap Scan on addresses  (cost=1810.97..3108.22 rows=383 width=189) (actual time=73.699..2911.092 rows=132305 loops=1)
              Recheck Cond: (title % 'г. Санкт-Петербург'::text)
              Rows Removed by Index Recheck: 5930
              Heap Blocks: exact=4599
              ->  Bitmap Index Scan on title_trgm_idx  (cost=0.00..1810.87 rows=383 width=0) (actual time=73.013..73.013 rows=138235 loops=1)
                    Index Cond: (title % 'г. Санкт-Петербург'::text)
Planning time: 0.105 ms
Execution time: 2952.466 ms

Подскажите как оптимизировать запрос.

Comments

[Melkij]

explain (analyze,buffers) при включенном track_io_timing покажите.

[Xaip]

Melkij,

Limit  (cost=3114.58..3114.59 rows=5 width=189) (actual time=2774.437..2774.438 rows=5 loops=1)
  Buffers: shared hit=5708
  ->  Sort  (cost=3114.58..3115.54 rows=383 width=189) (actual time=2774.436..2774.437 rows=5 loops=1)
"        Sort Key: (similarity(title, 'г. Санкт-Петербург'::text)) DESC"
        Sort Method: top-N heapsort  Memory: 26kB
        Buffers: shared hit=5708
        ->  Bitmap Heap Scan on addresses  (cost=1810.97..3108.22 rows=383 width=189) (actual time=81.239..2738.971 rows=130950 loops=1)
              Recheck Cond: (title % 'г. Санкт-Петербург'::text)
              Rows Removed by Index Recheck: 7285
              Heap Blocks: exact=4599
              Buffers: shared hit=5708
              ->  Bitmap Index Scan on title_trgm_idx  (cost=0.00..1810.87 rows=383 width=0) (actual time=80.601..80.601 rows=138235 loops=1)
                    Index Cond: (title % 'г. Санкт-Петербург'::text)
                    Buffers: shared hit=1109
Planning time: 0.118 ms
Execution time: 2774.468 ms

[Melkij]

Энергозатратная штука тут скорее вычисление самого similarity. Попробуйте его убрать из запроса и посмотреть. Вероятно стоит вместо similarity использовать оператор <-> и, возможно, понадобится сделать gist вместо gin индекса.

[Xaip]

Melkij, Такой запрос еще медленнее

SET track_io_timing = ON; explain (analyze,buffers) SELECT title, title <-> 'г. Санкт-Петербург' AS dist
  FROM addresses
  ORDER BY dist LIMIT 5;

Limit  (cost=21431.01..21431.02 rows=5 width=108) (actual time=4501.424..4501.425 rows=5 loops=1)
  Buffers: shared hit=10289
  ->  Sort  (cost=21431.01..22387.91 rows=382760 width=108) (actual time=4501.423..4501.423 rows=5 loops=1)
        Sort Key: ((title <-> 'г. Санкт-Петербург'::text))
        Sort Method: top-N heapsort  Memory: 25kB
        Buffers: shared hit=10289
        ->  Seq Scan on addresses  (cost=0.00..15073.50 rows=382760 width=108) (actual time=0.025..4439.799 rows=382544 loops=1)
              Buffers: shared hit=10289
Planning time: 0.081 ms
Execution time: 4501.442 ms

Он выигрывает по времени если ограничить выборку. Например ограничить поиск определенным регионом. Но для этого нужно знать какой регион выберет пользователь, а это еще лишние запросы.
GIST индексы я тоже пробовал, они еще медленее. В документации postgresql указано, что gin индекс быстрее чем gist

[Melkij]

В документации postgresql указано, что gin индекс быстрее чем gist

Такого в документации однозначно не скажут. gist и gin - названия фреймворков на самом деле. А потому очень сильно зависят от конкретной реализации, т.е. типов данных и операторов.
Например, https://www.postgresql.org/docs/current/pgtrgm.html

A variant of the above query is
SELECT t, t <-> 'word' AS dist
FROM test_trgm
ORDER BY dist LIMIT 10;
This can be implemented quite efficiently by GiST indexes, but not by GIN indexes. It will usually beat the first formulation when only a small number of the closest matches is wanted.

[Xaip]

Melkij,
a GIN index is faster to search than a GiST index, but slower to build or update; so GIN is better suited for static data and GiST for often-updated data.
www.postgresql.cn/docs/9.5/pgtrgm.html