Поиск триграмм становится намного медленнее, так как строка поиска становится длиннее

16

В базе данных Postgres 9.1 у меня есть таблица table1с ~ 1,5M строк и столбцом label(упрощенные имена ради этого вопроса).

Имеется функциональный индекс-триграмм lower(unaccent(label))( unaccent()сделан неизменным, чтобы его можно было использовать в индексе).

Следующий запрос довольно быстрый:

SELECT count(*) FROM table1
WHERE (lower(unaccent(label)) like lower(unaccent('%someword%')));
 count 
-------
     1
(1 row)

Time: 394,295 ms

Но следующий запрос медленнее:

SELECT count(*) FROM table1
WHERE (lower(unaccent(label)) like lower(unaccent('%someword and some more%')));
 count 
-------
     1
(1 row)

Time: 1405,749 ms

И добавление большего количества слов еще медленнее, хотя поиск более строгий.

Я попробовал простой трюк для запуска подзапроса для первого слова, а затем для запроса с полной строкой поиска, но (к сожалению) планировщик запросов проследил мои махинации:

EXPLAIN ANALYZE
SELECT * FROM (
   SELECT id, title, label from table1
   WHERE lower(unaccent(label)) like lower(unaccent('%someword%'))
   ) t1
WHERE lower(unaccent(label)) like lower(unaccent('%someword and some more%'));
Сканирование кучи растровых изображений в таблице 1 (стоимость = 16216.01..16220.04 строк = 1 ширина = 212) (фактическое время = 1824.017..1824.019 строк = 1 цикл = 1)
  Перепроверьте Cond: ((lower (unaccent ((label) :: text)) ~~ '% someword%' :: text) AND (Lower (unaccent ((label) :: text))) ~~ '% someword и некоторые другие %'::текст))
  -> Сканирование индекса растрового изображения для table1_label_hun_gin_trgm (стоимость = 0.00..16216.01 строк = 1 ширина = 0) (фактическое время = 1823.900..1823.900 строк = 1 цикл = 1)
        Индекс Cond: ((lower (unaccent ((label) :: text)) ~~ '% someword%' :: text) AND (lower (unaccent ((label) :: text)) ~~ '% someword и некоторые другие %'::текст))
Общее время выполнения: 1824,064 мс

Моя конечная проблема заключается в том, что строка поиска поступает из веб-интерфейса, который может отправлять довольно длинные строки и, следовательно, быть довольно медленным и также может представлять собой вектор DOS.

Итак, мои вопросы:

  • Как ускорить запрос?
  • Есть ли способ разбить его на подзапросы, чтобы он был быстрее?
  • Может быть, более поздняя версия Postgres лучше? (Я попробовал 9.4, и он не кажется быстрее: все тот же эффект. Может быть, более поздняя версия?)
  • Может быть, нужна другая стратегия индексации?
P.Péter
источник
1
Следует отметить, что unaccent()он также предоставляется дополнительным модулем, и Postgres по умолчанию не поддерживает индексы для функции, поскольку это не так IMMUTABLE. Вы, должно быть, что-то изменили, и вы должны упомянуть, что именно сделали в своем вопросе. Мой постоянный совет: stackoverflow.com/a/11007216/939860 . Кроме того, индексы триграммы поддерживают регистронезависимое соответствие из коробки. Вы можете упростить до: WHERE f_unaccent(label) ILIKE f_unaccent('%someword%')- с соответствующим индексом. Подробности: stackoverflow.com/a/28636000/939860 .
Эрвин Брандштеттер
Я просто объявлен unaccentнеизменным. Я добавил это к вопросу.
Петр
Имейте в виду, что хак перезаписывается при обновлении unaccentмодуля. Одна из причин, почему я предлагаю вместо этого функцию-оболочку.
Эрвин Брандштеттер

Ответы:

34

В PostgreSQL 9.6 будет новая версия pg_trgm 1.2, которая будет намного лучше в этом. Приложив немного усилий, вы также можете заставить эту новую версию работать под PostgreSQL 9.4 (вы должны применить исправление, скомпилировать модуль расширения и установить его самостоятельно).

Самая старая версия выполняет поиск каждой триграммы в запросе и объединяет их, а затем применяет фильтр. Новая версия выберет в запросе самую редкую триграмму и произведет поиск именно этой, а затем отфильтрует остальные.

Механизм для этого не существует в 9.1. В 9.4 этот механизм был добавлен, но pg_trgm не был приспособлен для его использования в то время.

У вас все еще может быть потенциальная проблема с DOS, поскольку злоумышленник может создать запрос, имеющий только общие триграммы. как "% and%" или даже "% a%"


Если вы не можете обновиться до pg_trgm 1.2, тогда другой способ обмануть планировщика:

WHERE (lower(unaccent(label)) like lower(unaccent('%someword%'))) 
AND   (lower(unaccent(label||'')) like 
      lower(unaccent('%someword and some more%')));

Объединяя пустую строку с меткой, вы заставляете планировщика думать, что он не может использовать индекс в той части предложения where. Поэтому он использует индекс только для% someword% и применяет фильтр только к этим строкам.


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

jjanes
источник
13
Стоит упомянуть, что именно вы написали патч. И предварительные тесты производительности впечатляют. Это действительно заслуживает большего количества голосов (также для объяснения и обхода текущей версии).
Эрвин Брандштеттер,
Я бы больше интересовался хотя бы ссылкой на механизм, который вы использовали для реализации патча, которого не было в 9.1. Но я согласен с плохим ответом Эрвина.
Эван Кэрролл
3

Я нашел способ мошенничества с планировщиком запросов, это довольно простой взлом:

SELECT *
FROM (
   select id, title, label
   from   table1
   where  lower(unaccent(label)) like lower(unaccent('%someword%'))
   ) t1
WHERE lower(lower(unaccent(label))) like lower(unaccent('%someword and more%'))

EXPLAIN выход:

Сканирование кучи растровых изображений в таблице 1 (стоимость = 6749.11..7332.71 строк = 1 ширина = 212) (фактическое время = 256.607..256.609 строк = 1 цикл = 1)
  Перепроверьте Cond: (нижний (unaccent ((label_hun) :: text)) ~~ '% someword%' :: text)
  Фильтр: (нижний (нижний (unaccent ((label) :: text))) ~~ '% someword и еще несколько%' :: text)
  -> Сканирование индекса растрового изображения для table1_label_hun_gin_trgm (стоимость = 0.00..6749.11 строк = 147 ширина = 0) (фактическое время = 256.499..256.499 строк = 1 петля = 1)
        Индекс Cond: (нижний (unaccent ((label) :: text)) ~~ '% someword%' :: text)
Общее время выполнения: 256,653 мс

Таким образом, поскольку нет индекса для lower(lower(unaccent(label))), это создаст последовательное сканирование, поэтому оно превращается в простой фильтр. Более того, простое И также сделает то же самое:

SELECT id, title, label
FROM table1
WHERE lower(unaccent(label)) like lower(unaccent('%someword%'))
AND   lower(lower(unaccent(label))) like lower(unaccent('%someword and more%'))

Конечно, это эвристика, которая может не сработать, если вырезанная часть, используемая при сканировании индекса, очень распространена. Но в нашей базе данных не так много повторений, если я использую около 10-15 символов.

Осталось два небольших вопроса:

  • Почему postgres не может понять, что что-то подобное будет полезно?
  • Что делает postgres во временном диапазоне 0..256.499 (см. Анализ выходных данных)?
P.Péter
источник
1
В диапазоне времени от 0 до 256,499 он строит растровое изображение. В 256.499 это производит свой первый вывод, который является растровым изображением. Который также является его последним выводом, так как он производит только один вывод - один завершенный битовый массив.
Джанес