PostgreSQL Antipatterns: навигация по реестру

    Сегодня не будет никаких сложных кейсов и мудреных алгоритмов на SQL. Все будет очень просто, на уровне Капитана Очевидность — делаем просмотр реестра событий с сортировкой по времени.

    То есть вот лежит в базе табличка events, а у нее поле ts — ровно то самое время, по которому мы хотим эти записи упорядоченно показывать:

    CREATE TABLE events(
      id
        serial
          PRIMARY KEY
    , ts
        timestamp
    , data
        json
    );
    
    CREATE INDEX ON events(ts DESC);

    Понятно, что записей у нас там будет не десяток, поэтому нам потребуется в каком-то виде постраничная навигация.

    #0. «Я у мамы погроммист»


    cur.execute("SELECT * FROM events;")
    rows = cur.fetchall();
    rows.sort(key=lambda row: row.ts, reverse=True);
    limit = 26
    print(rows[offset:offset+limit]);
    

    Даже почти не шутка — редко, но встречается в дикой природе. Иногда после работы с ORM бывает тяжело перестроиться на «прямую» работу с SQL.

    Но давайте перейдем к более распространенным и менее очевидным проблемам.

    #1. OFFSET


    SELECT
      ...
    FROM
      events
    ORDER BY
      ts DESC
    LIMIT 26 OFFSET $1; -- 26 - записей на странице, $1 - начало страницы

    Откуда тут взялось число 26? Это примерное количество записей для заполнения одного экрана. Точнее, 25 отображаемых записей, плюс 1, сигнализирующая, что дальше в выборке хоть что-то еще есть и имеет смысл двигаться дальше.

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

    И пока в интерфейсе приложения просмотр реестра реализован как переключение между визуальными «страницами», никто долго не замечает ничего подозрительного. Ровно до момента, когда в борьбе за удобство UI/UX не решают переделать интерфейс на «бесконечный скролл» — то есть все записи реестра рисуются единым списком, который пользователь может крутить вверх-вниз.

    И вот, при очередном тестировании вас ловят на дублировании записей в реестре. Почему, ведь на таблице есть нормальный индекс (ts), на который опирается ваш запрос?

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

    На самом деле, тут скрыта еще и вторая проблема, которую заметить много сложнее — некоторые записи не будут показаны вовсе! Ведь «сдублировавшиеся» записи заняли чье-то место. Подробное объяснение с красивыми картинками можно прочитать тут.

    Расширяем индекс


    Хитрый разработчик понимает — надо сделать ключ индекса уникальным, а самый простой способ — расширить его заведомо уникальным полем в качестве которого отлично подойдет PK:

    CREATE UNIQUE INDEX ON events(ts DESC, id DESC);

    А запрос мутирует:

    SELECT
      ...
    ORDER BY
      ts DESC, id DESC
    LIMIT 26 OFFSET $1;

    #2. Переход на «курсоры»


    Некоторое время спустя к вам приходит DBA и «радует», что ваши запросы адски грузят сервер своими конскими OFFSET, и вообще, пора бы перейти на навигацию от последнего показанного значения. Ваш запрос мутирует снова:

    SELECT
      ...
    WHERE
      (ts, id) < ($1, $2) -- последние полученные на предыдущем шаге значения
    ORDER BY
      ts DESC, id DESC
    LIMIT 26;

    Вы облегченно вздохнули, пока не наступила…

    #3. Чистка индексов


    Потому что однажды ваш DBA прочитал статью про поиск неэффективных индексов и понял, что «непоследний» timestamp — это нехорошо. И снова пришел к вам — теперь с мыслью, что вот тот индекс должен все-таки превратиться обратно в (ts DESC).

    Но что же делать с первоначальной проблемой «скакания» записей между страницами?.. А все просто — надо выбирать блоки с нефиксированным количеством записей!

    Вообще, кто нам запрещает читать не «ровно 26», а «не менее 26»? Например, так, чтобы в следующем блоке оказались записи с заведомо другими значениями ts — тогда ведь и проблемы с «перепрыгиванием» записей между блоками не будет!

    Вот как этого добиться:

    SELECT
      ...
    WHERE
      ts < $1 AND
      ts >= coalesce((
        SELECT
          ts
        FROM
          events
        WHERE
          ts < $1
        ORDER BY
          ts DESC
        LIMIT 1 OFFSET 25
      ), '-infinity')
    ORDER BY
      ts DESC;

    Что здесь вообще происходит?

    1. Шагаем на 25 записей «вниз» и получаем «граничное» значение ts.
    2. Если там уже ничего нет, то подменяем NULL-значение на -infinity.
    3. Вычитываем весь сегмент значений между полученным значением ts и переданным из интерфейса параметром $1 (предыдущим «последним» отрисованным значением).
    4. Если блок вернулся меньше чем с 26 записями — он последний.

    Или то же самое картинкой:


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

    Замечание


    1. Да, в таком случае мы обращаемся к индексу дважды, но все «чисто по индексу». Поэтому вложенный запрос приведет всего лишь к одному дополнительному Index Only Scan.
    2. Достаточно очевидно, что этой методикой можно пользоваться, только когда у вас значения ts могут пересечься лишь случайно, и их немного. Если же ваш типичный кейс — «миллион записей в 00:00:00.000», так делать не стоит. В смысле, не стоит допускать такого кейса. Но если уж так получилось, используйте вариант с расширенным индексом.
    Тензор
    Разработчик системы СБИС

    Похожие публикации

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

      0
      CREATE UNIQUE INDEX ON events(ts DESC, id DESC);


      Зачем здесь UNIQUE? id, как я понимаю, уже Primary Key, от добавления колонок он не потеряет уникальности. Дополнительная проверка уникальности не даёт лишней нагрузки на базу при INSERT?
        0
        Зачем здесь UNIQUE?
        Исключительно для наглядности — мы ведь тут не ведем речь о производительности вставки в БД.

        Я специально не проверял, но влияние наличия/отсутствия UNIQUE должно иметь микроскопическое влияние на скорость вставки по сравнению с самим фактом наличия дополнительного индекса.
        0
        пора бы перейти на навигацию от последнего показанного значения

        Увы, не поможет если навигация допускается на произвольную страницу (а не только на следущую/предыдущую), без offset/limit тут уже никак (если только не гарантировать сквозную нумерацию в id).

          0
          Тогда возникает вопрос — а нужен ли действительно переход именно «на страницу» или таки достаточно «по координатам». Ну или как-то загодя нумеровать (и перенумеровывать потом) весь набор.
            0
            Загодя нумеровать кажется не получится, если интерфейс позволяет десятки вариантов фильтров и сортировок, до куче в кластере из нескольких серверов.
              0
              Если допустимо оставить крайние «страницы» неполными, то можно ведь разбить на какие-то предметные интервалы — скажем, таймлайн — на минуты, и адресоваться к ним. Тогда на каждой «странице» будет заведомо один интервал, хоть и с непостоянным кол-вом записей
          0
          Было бы интересно почитать про более сложные случаи. Например когда у вас таблица содержит сотни тысяч записей, уникальный ключ и 5-10 полей значений по которым может производиться фильтрация/сортировка. Мы вот как раз живем в таких условиях. B SQL у нас нет (
            0
            Тут надо очень хорошо ориентироваться в предметной области. Например, как часто изменяется/добавляются записи в таблицу, какие возможны комбинации фильтров, все ли из них должны работать «идеально быстро»,…
            И не все из этих вариантов вообще решаются с помощью SQL.
              0
              Ну если брать наши случаи, то есть как раз два варианта:
              1) Записи создаются и не обновляются
              2) Записи создаются и часто изменяются (специфические документы, проходящие разные стадии привязки, дополнения, одобрения и т.п.)

              При этом у нас записи НИКОГДА не удаляются.

              Фильтры и их комбинации по сути комбинаторные, т.е произвольные сочетания произвольного количества фильтров с произвольным порядком сортировки и *ирония ON* конечно же за минимальное время *ирония OFF*.

              Было бы интересно узнать больше о способах решения подобного класса задач. И в том числе о решениях не с помощью SQL, SQL у нас нет.

              Если говорить о наших решениях (которые крайне все таки специфичны ввиду недоступности SQL, хотя СУБД и реляционная), то мы пока остановились на создании индексов покрывающих хотя бы по одному критерию (максимум двум), и проходу с помощью мммм… проблемы терминологического характера… курсора скорее всего. Наша сложность еще в том, что одним из требований является знание об общем числе записей отвечающих этим фильтрам.
                0
                Первый кейс неплохо покрывает clickhouse. Второй кейс тоже, если сможете адаптировать архитектуру под первый кейс — там есть специальные штуки.
                  0
                  Фильтры и их комбинации по сути комбинаторные, т.е произвольные сочетания произвольного количества фильтров с произвольным порядком сортировки
                  В таких условиях лучше всего себя покажет полная материализация всех возможных комбинаций. :)

                  На самом деле, поисковые движки типа Sphinx, ElasticSearch «внутри» ровно это и делают. Только не всегда «полную» материализацию.

                  Пару лет назад читал где-то, что Я.Маркет как раз делает in-memory-материализацию результатов поиска, поэтому все фильтры-поиски идеально быстры, но первичное построение индекса занимает дни. Возможно, что-то уже изменилось.
                    0
                    У меня слишком много комбинаций в такой схеме получается и сильно проседает запись. В пиках запись 500МБ/с при отдельных индексах на всех фильтруемых колонках, если ещё и материализовать — будет совсем треш.
                      0
                      При таком объеме записи не надо давать пользователям хотеть «все возможные комбинации». Как только перестать такое хотеть, можно достаточно несложно «заточить» индексы по конкретные наиболее типовые выборки.
                      Иначе это путь в большие кластеры из много-много серверов.
                        0
                        Если наступает перехотеть — тогда clickhouse начинает лучше выполнять эту задачу… Поэтому пока живём с limit offset и без count всей выборки.
                          0
                          clickhouse начинает лучше выполнять эту задачу

                          А вот это очень сильно зависит от задачи. Как известно, CH плохо относится к UPDATE, поэтому если ваши выборки должны строиться по накапливающимся агрегатам…

                          Конечно, в PG из-за MVCC тоже возникают с этим некоторые проблемы, но таки есть разница для скорости заранее известной выборки — иметь небольшую таблицу результирующих агрегатов с пачкой нужных индексов, или для каждого запроса собирать агрегат, хоть и очень быстро.
              0

              А вариант 3 точно лучше второго?

                0
                Если мы говорим в целом о базе — безусловно. Индекс более компактен (одно поле вместо двух), что положительно сказывается как при Insert/Update, так и при чтении. Да еще и объем меньше на хранилище.

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

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