PostgreSQL Antipatterns: сказ об итеративной доработке поиска по названию, или «Оптимизация туда и обратно»

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

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

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

    0: чего же хотел пользователь


    [КДПВ отсюда]

    Что вообще обычно подразумевает пользователь, когда говорит про «быстрый» поиск по названию? Почти никогда это не оказывается «честный» поиск по подстроке типа ... LIKE '%роза%' — ведь тогда в результат попадают не только 'Розалия' и 'Магазин Роза', но и роза' и даже 'Дом Деда Мороза'.

    Пользователь же подразумевает на бытовом уровне, что вы ему обеспечите поиск по началу слова в названии и покажете более релевантным то, что начинается на введенное. И сделаете это практически мгновенно — при подстрочном вводе.

    1: ограничиваем задачу


    И уж тем более не будет человек специально вводить 'роз магаз', чтобы каждое слово вам приходилось искать префиксно. Нет, пользователю отреагировать на быструю подсказку для последнего слова гораздо проще, чем целенаправленно «недовводить» предыдущие — посмотрите, как это отрабатывает любой поисковик.

    Вообще, правильно сформулировать требования к задаче — больше половины решения. Иногда внимательный анализ use case может существенно влиять на результат.

    Что же делает абстрактный разработчик?

    1.0: внешний поисковый движок


    Ой, поиск это сложно, что-то вообще им заниматься не хочется — давайте отдадим это devops! Пусть они нам развернут внешнюю относительно БД поисковую систему: Sphinx, ElasticSearch,…

    Рабочий, хоть и трудоемкий в плане синхронизации и оперативности изменений вариант. Но не в нашем случае, поскольку поиск осуществляется для каждого клиента только в рамках данных его аккаунта. А данные имеют достаточно высокую изменчивость — и если сейчас менеджер внес карточку 'Магазин Роза', то через 5-10 секунд он уже может вспомнить, что забыл указать там email и захотеть ее найти и поправить.

    Поэтому — давайте искать «прямо по базе». К счастью, PostgreSQL позволяет нам это делать, и не одним вариантом — их и рассмотрим.

    1.1: «честная» подстрока


    Цепляемся за слово «подстрока». А ведь ровно для индексного поиска по подстроке (и даже по регулярным выражениям!) есть отличный модуль pg_trgm! Только потом надо будет правильно посортировать.

    Давайте попробуем взять для простоты модели такую табличку:

    CREATE TABLE firms(
      id
        serial
          PRIMARY KEY
    , name
        text
    );

    Заливаем туда 7.8 миллионов записей реальных организаций и индексируем:

    CREATE EXTENSION pg_trgm;
    CREATE INDEX ON firms USING gin(lower(name) gin_trgm_ops);

    Поищем для подстрочного поиска первые 10 записей:

    SELECT
      *
    FROM
      firms
    WHERE
      lower(name) ~ ('(^|\s)' || 'роза')
    ORDER BY
      lower(name) ~ ('^' || 'роза') DESC -- сначала "начинающиеся на"
    , lower(name) -- остальное по алфавиту
    LIMIT 10;
    


    [посмотреть на explain.tensor.ru]

    Ну, такое… 26мс, 31MB прочитанных данных и больше 1.7K отфильтрованных записей — для 10 искомых. Накладные расходы слишком велики, нельзя ли как-то поэффективнее?

    1.2: поиск по тексту? это же FTS!


    Действительно, PostgreSQL предоставляет очень мощный механизм полнотекстового поиска (Full Text Search), в том числе с возможностью префиксного поиска. Отличный вариант, даже расширений устанавливать не нужно! Давайте попробуем:

    CREATE INDEX ON firms USING gin(to_tsvector('simple'::regconfig, lower(name)));

    SELECT
      *
    FROM
      firms
    WHERE
      to_tsvector('simple'::regconfig, lower(name)) @@ to_tsquery('simple', 'роза:*')
    ORDER BY
      lower(name) ~ ('^' || 'роза') DESC
    , lower(name)
    LIMIT 10;


    [посмотреть на explain.tensor.ru]

    Тут нам немного помогла параллелизация исполнения запроса, сократив время вдвое до 11мс. Да и прочитать нам пришлось в 1.5 раза меньше — всего 20MB. А тут чем меньше — тем лучше, ведь чем больший объем мы вычитываем, тем выше шансы получить cache miss, и каждая лишняя прочитанная с диска страница данных — потенциальные «тормоза» для запроса.

    1.3: все-таки LIKE?


    Всем предыдущий запрос хорош, да только если его дернуть сотню тысяч раз за сутки, то набежит уже 2TB прочитанных данных. В лучшем случае — из памяти, но если не повезет, то и с диска. Так что давайте попробуем сделать его поменьше.

    Вспомним, что пользователь хочет видеть сначала «которые начинаются на ...». Так ведь это же в чистом виде префиксный поиск с помощью text_pattern_ops! И только если нам «не хватит» до 10 искомых записей, то дочитывать их придется с помощью FTS-поиска:

    CREATE INDEX ON firms(lower(name) text_pattern_ops);

    SELECT
      *
    FROM
      firms
    WHERE
      lower(name) LIKE ('роза' || '%')
    LIMIT 10;


    [посмотреть на explain.tensor.ru]

    Отличные показатели — всего 0.05мс и чуть больше 100KB прочитано! Только мы же забыли сортировку по названию, чтобы пользователь не заблудился в результатах:

    SELECT
      *
    FROM
      firms
    WHERE
      lower(name) LIKE ('роза' || '%')
    ORDER BY
      lower(name)
    LIMIT 10;


    [посмотреть на explain.tensor.ru]

    Ой, что-то уже не так красиво — вроде и индекс есть, но сортировка летит мимо него… Оно, конечно, уже в разы эффективнее, чем предыдущий вариант, но…

    1.4: «доработать напильником»


    Но есть же индекс, который позволяет и по диапазону искать, и сортировку при этом нормально использовать — обычный btree!

    CREATE INDEX ON firms(lower(name));

    Только запрос под него придется «собирать вручную»:

    SELECT
      *
    FROM
      firms
    WHERE
      lower(name) >= 'роза' AND
      lower(name) <= ('роза' || chr(65535)) -- для UTF8, для однобайтовых - chr(255)
    ORDER BY
       lower(name)
    LIMIT 10;


    [посмотреть на explain.tensor.ru]

    Отлично — и сортировка работает, и потребление ресурсов осталось «микроскопическим», в тысячи раз эффективнее «чистого» FTS! Осталось собрать в единый запрос:

    (
      SELECT
        *
      FROM
        firms
      WHERE
        lower(name) >= 'роза' AND
        lower(name) <= ('роза' || chr(65535)) -- для UTF8, для однобайтовых кодировок - chr(255)
      ORDER BY
         lower(name)
      LIMIT 10
    )
    UNION ALL
    (
      SELECT
        *
      FROM
        firms
      WHERE
        to_tsvector('simple'::regconfig, lower(name)) @@ to_tsquery('simple', 'роза:*') AND
        lower(name) NOT LIKE ('роза' || '%') -- "начинающиеся на" мы уже нашли выше
      ORDER BY
        lower(name) ~ ('^' || 'роза') DESC -- используем ту же сортировку, чтобы НЕ пойти по btree-индексу
      , lower(name)
      LIMIT 10
    )
    LIMIT 10;

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

    Таки да, мы теперь имеем на таблице одновременно btree и gin, зато статистически получилось, что меньше 10% запросов доходят до выполнения второго блока. То есть при таких известных заранее типичных ограничениях для задачи мы смогли уменьшить суммарное потребление ресурсов сервера практически в тысячи раз!

    1.5*: обойдемся без напильника


    Выше LIKE нам помешала использовать неправильная сортировка. Но ее можно «наставить на путь истинный» с помощью указания USING-оператора:
    По умолчанию подразумевается ASC. Кроме того, можно задать имя специфического оператора сортировки в предложении USING. Оператор сортировки должен быть членом «меньше» или «больше» некоторого семейства операторов B-дерева. ASC обычно равнозначно USING < и DESC обычно равнозначно USING >.
    В нашем случае «меньше» — это ~<~:

    SELECT
      *
    FROM
      firms
    WHERE
      lower(name) LIKE ('роза' || '%')
    ORDER BY
      lower(name) USING ~<~
    LIMIT 10;


    [посмотреть на explain.tensor.ru]

    2: как «прокисают» запросы


    Теперь оставляем наш запрос «настояться» полгода-год, и с удивлением снова обнаруживаем его «в топе» с показателями суммарного суточного «прокачивания» памяти (buffers shared hit) в 5.5TB — то есть еще больше, чем было исходно.

    Нет, конечно, и бизнес у нас вырос, и нагрузка увеличилась, но не настолько же! Значит, что-то тут нечисто — давайте разбираться.

    2.1: рождение пейджинга


    В какой-то момент другой команде разработчиков захотелось сделать возможность из быстрого подстрочного поиска «прыгнуть» в реестр с теми же, но расширенными результатами. А какой реестр без постраничной навигации? Давайте прикрутим!

    ( ... LIMIT <N> + 10)
    UNION ALL
    ( ... LIMIT <N> + 10)
    LIMIT 10 OFFSET <N>;

    Теперь можно было без напрягов для разработчика показывать реестр результатов поиска с «типа-постраничной» подгрузкой.

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

    2.2: хочется экзотики


    В какой-то момент разработчику захотелось разнообразить результирующую выборку данными из другой таблицы, для чего весь предыдущий запрос был отправлен в CTE:

    WITH q AS (
      ...
      LIMIT <N> + 10
    )
    SELECT
      *
    , (SELECT ...) sub_query -- какой-то запрос к связанной таблице
    FROM
      q
    LIMIT 10 OFFSET <N>;

    И даже так — неплохо, поскольку вложенный запрос вычисляется только для 10 возвращаемых записей, если бы не…

    2.3: DISTINCT бессмысленный и беспощадный


    Где-то в процессе такой эволюции из 2-го подзапроса потерялось NOT LIKE условие. Понятно, что после этого UNION ALL начал возвращать некоторые записи дважды — сначала найденные по началу строки, а потом еще раз — по началу первого слова этой строки. В пределе, все записи 2го подзапроса могли совпасть с записями первого.

    Что делает разработчик вместо поиска причины?.. Не вопрос!

    • расширим вдвое размер исходных выборок
    • наложим DISTINCT, чтобы получились только одинарные экземпляры каждой строки

    WITH q AS (
      ( ... LIMIT <2 * N> + 10)
      UNION ALL
      ( ... LIMIT <2 * N> + 10)
      LIMIT <2 * N> + 10
    )
    SELECT DISTINCT
      *
    , (SELECT ...) sub_query
    FROM
      q
    LIMIT 10 OFFSET <N>;

    То есть понятно, что результат, в итоге, ровно тот же, но шанс «пролететь» во 2-й подзапрос CTE стал сильно выше, да и без этого, читается явно больше.

    Но это не самая печаль. Поскольку разработчик попросил отобрать DISTINCT не по конкретным, а сразу по всем полям записи, то туда автоматом попало и поле sub_query — результат подзапроса. Теперь, для выполнения DISTINCT, базе пришлось выполнить уже не 10 подзапросов, а все <2 * N> + 10!

    2.4: кооперация превыше всего!


    Вот так вот, разработчики жили — не тужили, потому что в реестре «докрутить» до существенных значений N при хроническом замедлении получения каждой следующей «страницы» у пользователя явно не хватало терпения.

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

    В общем, в пойманном экземпляре N достигло значений почти в 17K, а всего за сутки было выполнено «по цепочке» не меньше 4K таких запросов. Последние из них смело сканировали уже по 1GB памяти на каждой итерации

    Итого


    Тензор
    Разработчик системы СБИС

    Комментарии 15

      0
      Картинка неполная. Еще было «как описано в документации» с голым пеньком :-)
        0
        Зря не упомянули, что результирующая сортировка не совсем правильная. В большей части случаев это не заметно, но бывают казусы.

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

        ЗЫ А вообще по моему опыу работы с чужими базами — многим плевать. Ядер вагон, памяти немеряно, диски ssd, а давайте искать лайком без индексов!
          0
          Зря не упомянули, что результирующая сортировка не совсем правильная. В большей части случаев это не заметно, но бывают казусы.
          А можно пример? Сложные кодировки «с умляутами» или что-то более распространенное?
          tsvector у вас дает хорошие результаты потому что на тестах вы ищете целое слово, дела будут обстоять хуже когда будете искать частичное вхождение.
          Так как раз частичное же и ищется, по префиксу:
          to_tsquery('simple', 'роза:*')

            0
            А можно пример?

            Сейчас резко не подберу, но на вскидку
            9 обычных результатов из первой части, выглядят так:
            Железячко Арсен
            Железячко Боб

            И 1 результат из второй выборки
            Анищенко Железко

            Хотя, при сортировке, он должен быть по идее первым. Но если задать сортировку на самом верху, то второй запрос будет выполняться всегда. В большинстве случаев — ничего страшного, но помнить — нужно и не для всех это очевидно.

            Так как раз частичное же и ищется, по префиксу:

            Да, виноват, по диагонали запросы смотрел
              0
              Хотя, при сортировке, он должен быть по идее первым.
              Не совсем понял, почему. Потому что «находимая» часть алфавитно выше?
                0
                Потому что вся строка алфавитно выше. Общей результирующей сортировки не выполняется, для ее выполнения нужен еще один запрос, уровнем выше.

                select * from 
                  (
                   (select --prefix part here order by name asc limit 10)
                   union 
                   (select --ftw/trgm part here order by name asc limit 10)
                   limit 10
                  ) 
                order by name asc
                

                  0
                  А, в этом смысле. Для этого специально в пункте 0 указал:
                  … и покажете более релевантным то, что начинается на введенное

                  То есть не надо пересортировывать «вообще все» по всей строке — там же каша получится просто в результатах.
                    0
                    и покажете более релевантным то, что начинается на введенное

                    Хм, действительно, не заметил

                    там же каша получится просто в результатах.

                    Никакой каши, сами попробуйте.
                    Как раз напротив, если вы не сортируете общие результаты, вы создаете ситуацию, когда результаты отсортированы «хрен пойми как» с точки зрения пользователя. Если вы сознательно на это идете — нет вопросов, но упомянуть — стоит. Просто я довольно часто встречал недоумения по поводу порядка сортировки в случае union limit
                      0
                      Если расширить лимит, то у меня выглядит выборка примерно вот так:
                      "Роза" -- разные ЮЛ, по ИНН, городу и т.п.
                      "Роза"
                      "Роза"
                      "Роза"
                      "Роза"
                      "Роза"
                      "Роза"
                      "Абайдулина Роза Камилевна, ИП"
                      "Абгалимова Роза Абдельгалиммовна, ИП"
                      "Абдразякова Роза Нурихановна, ИП"
                      "Абдрахманова Роза Бахытжановна, ИП"
                      "Абдрахманова Роза Фаритовна, ИП"
                      "Абдулина Роза Абдихаликовна, ИП"
                      "Абдулкеримова Роза Саламбековна, ИП"
                      "Абдулнасырова Роза Камиловна, ИП"
                      "Абдулова Розалия Салихзяновна, ИП"
                      

                      А если пересортировать общий результат, то все эти ИП поедут наверх. И становится банально непонятно, почему на предыдущей строке «Абдулова Розалия Салихзяновна, ИП», а на следующей — уже «Роза».
                        0
                        Если добавить ОКП то имхо все будет вполне логично. У вас контрагенты, у вас довольно специфический случай, тут надо действительно подумать, но как правила навигация среди одинаковых элементов по алфавиту много легче.
                        попробуйте поискать по слову «Розовый»
                          0
                          Если записи равнозначны — все нормально будет:
                          "РОЗОВЫЙ АГАТ, питомник"
                          "Розовый Бегемот, ООО"
                          "Розовый дельфин"
                          "Розовый Дельфин, ООО"
                          "Розовый дождь"
                          "РОЗОВЫЙ ДОЖДЬ, салон красоты, ЗАО"
                          "Розовый Дом, ООО"
                          "Розовый Дом, ТСН"
                          "Розовый Жемчуг, ООО"
                          "Розовый коралл"
                          "Розовый Коралл, ООО"
                          "Розовый крокодил, студия фотообоев"
                          "Розовый кролик"
                          "Розовый Лотос, ООО"
                          "Розовый Лотос, ООО"
                          "Розовый Лотос, ООО"
                          "Розовый Лотос, ООО"
                          "РОЗОВЫЙ ЛОТОС,производственная фирма, ЗАО"
                          "Розовый Мир, ООО"
                          "Розовый Мир, ООО"

                          А вот если их надо показывать в какой-нить иерархии…

                          … тогда это уже не подстрочный поиск.
                            0
                            В первом варианте думалось будет еще нечто вроде Пятачек Розовый ООО (реально название кстати).
                            Скринов сделать забыл но тоже попробовал: география и поиск по имени отчеству хорошо идут если список всегда сортирован по алфавиту, а вот если искать с фамилии то да, ваш вариант с релевантностью удобен. Контрагентов не нашел достаточной выборки.

                            ЗЫ кстати по триграмм и тсвектору зачем вам lower? Триграммы отлично поддерживают ilike (~*) а тс вектору просто плевать
                              +1
                              Просто на едином примере с lower показывал, чтобы частности не отвлекали. А simple regconfig вроде регистрозависим? Сейчас нет базы в доступе проверить.
                                0
                                А simple regconfig вроде регистрозависим

                                нет

                                Просто на едином примере с lower показывал, чтобы частности не отвлекали

                                Уже родилась толпа джунов сующих lower в tsvector и триграммы)

                                ЗЫ вспомнил откуда у меня привычка юзать триграммы а не tsvector. Осталась со времен задачи по поиску нечетких дубликатов: n-граммы, левенштейн, metaphone, soundex вот эти все прелести. но это, вероятно, следующий уровень поиска.

                                ЗЫЗЫ раз уж пошла такая пьянка, когда поиск только на русском, можно еще проверять строку на наличие английских букв и конвертировать раскладку, или увеличить запрос вдвое, это удобно.
                                  0
                                  Уже родилась толпа джунов сующих lower в tsvector и триграммы)
                                  «Дай человеку в руки молоток, и он решит, что весь мир состоит из гвоздей»
                                  можно еще проверять строку на наличие английских букв и конвертировать раскладку, или увеличить запрос вдвое, это удобно.
                                  Ага, у нас такое сделано, но только на уровне интерфейса, а не запроса. То есть поискали сначала в исходной раскладке — если пусто, то и в другой.

        Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

        Самое читаемое