SQL HowTo: курсорный пейджинг с неподходящей сортировкой

    Этот пост родился как расширенный ответ на умозрительную задачу, обозначенную в статье «Хроники пэйджинга».

    Пусть у нас есть реестр документов, с которым работают операторы или бухгалтеры в СБИС, вроде такого:



    Традиционно, при подобном отображении используется или прямая (новые снизу) или обратная (новые сверху) сортировка по дате и порядковому идентификатору, назначаемому при создании документа — ORDER BY dt, id или ORDER BY dt DESC, id DESC.

    Типичные возникающие при этом проблемы я уже рассматривал в статье «PostgreSQL Antipatterns: навигация по реестру». Но что если пользователю зачем-то захотелось «нетипичного» — например, отсортировать одно поле «так», а другое «этак»ORDER BY dt, id DESC? Но второй индекс мы создавать не хотим — ведь это замедление вставки и лишний объем в базе.

    Можно ли решить эту задачу, эффективно используя только индекс (dt, id)?

    Давайте сначала нарисуем, как упорядочен наш индекс:



    Отмечу, что порядок создания записей id не обязательно совпадает с порядком dt, поэтому опираться на него мы не можем, и придется что-то изобретать.

    Теперь предположим, что мы находимся в точке (A, 2) и хотим прочитать «следующие» 6 записей в сортировке ORDER BY dt, id DESC:



    Ага! Мы выбрали какой-то «кусочек» из первого узла A, другой «кусочек» из последнего узла C и все записи из узлов между ними (B). Каждый такой блок вполне успешно ложится на чтение по индексу (dt, id), несмотря на не вполне подходящий порядок.

    Давайте попробуем сконструировать такой запрос:

    • сначала читаем из блока A «влево» от стартовой записи — получаем N записей
    • дальше читаем L - N «вправо» от значения A
    • находим в последнем блоке максимальный ключ C
    • отфильтровываем из предыдущей выборки все записи этим ключом и вычитываем его «справа»

    А теперь попробуем изобразить в коде и проверить на модели:

    CREATE TABLE doc(
      id
        serial
    , dt
        date
    );
    CREATE INDEX ON doc(dt, id); -- наш индекс
    
    -- случайно "раскидаем" документы по последнему году
    INSERT INTO doc(dt)
    SELECT
      now()::date - (random() * 365)::integer
    FROM
      generate_series(1, 10000);

    Чтобы не вычислять количество уже прочитанных записей и разность между ним и целевым количеством, заставим это делать PostgreSQL с помощью «хака» UNION ALL и LIMIT:

    (
      ... LIMIT 100
    )
    UNION ALL
    (
      ... LIMIT 100
    )
    LIMIT 100

    Теперь соберем начитку следующих 100 записей с целевой сортировкой (dt, id DESC) от последнего известного значения:

    WITH src AS (
      SELECT
        '{"dt" : "2019-09-07", "id" : 2331}'::json -- "опорный" ключ
    )
    , pre AS (
      (
        ( -- читаем не более 100 записей "влево" от опорной точки из "левого" значения A
          SELECT
            *
          FROM
            doc
          WHERE
            dt = ((TABLE src) ->> 'dt')::date AND
            id < ((TABLE src) ->> 'id')::integer
          ORDER BY
            dt DESC, id DESC
          LIMIT 100
        )
        UNION ALL
        ( -- дочитываем до 100 записей "вправо" от исходного значения "верхнего" ключа A -> B, C
          SELECT
            *
          FROM
            doc
          WHERE
            dt > ((TABLE src) ->> 'dt')::date
          ORDER BY
            dt, id
          LIMIT 100
        )
      )
      LIMIT 100
    )
    -- находим крайний правый ключ C в том, что прочитали
    , maxdt AS (
      SELECT
        max(dt)
      FROM
        pre
      WHERE
        dt > ((TABLE src) ->> 'dt')::date
    )
    ( -- вычищаем "левые" записи по ключу C
      SELECT
        *
      FROM
        pre
      WHERE
        dt <> (TABLE maxdt)
      ORDER BY
        dt, id DESC -- накладываем целевую сортировку, поскольку записи по B у нас лежат не в том порядке
      LIMIT 100
    )
    UNION ALL
    ( -- дочитываем "правые" записи по ключу C до 100 штук
      SELECT
        *
      FROM
        doc
      WHERE
        dt = (TABLE maxdt)
      ORDER BY
        dt, id DESC
      LIMIT 100
    )
    LIMIT 100;

    Посмотрим, что получилось в плане:


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

    • Итак, по первому ключу A = '2019-09-07' мы прочитали 3 записи.
    • К ним дочитали еще 97 по B и C за счет точного попадания в Index Scan.
    • Среди всех записей отфильтровали 18 по максимальному ключу C.
    • Дочитали 23 записи (вместо 18 искомых из-за Bitmap Scan) по максимальному ключу.
    • Все пересортировали и отсекли целевые 100 записей.
    • … и на все это ушло меньше миллисекунды!

    Метод, безусловно, не универсален и при индексах на большем количестве полей превратится во что-то совсем уж страшное, но если очень хочется дать пользователю «нестандартную» сортировку без «обрушения» базы в Seq Scan по большой таблице — можно осторожно пользоваться.
    Тензор
    Разработчик системы СБИС

    Comments 21

      +1

      Решение прикольное. По сути это эмуляция части логики N-ного уровня на N+1-ом, так как сам движок не догадывается о частном случае использования собственных же средств ускорения доступа.

        0
        Тут научить движок решению в общем случае многоколоночного индекса — та еще задача. Даже с реализацией Incremental Sort больше двух лет бились — а, казалось бы, тоже «все очевидно».
        0

        А как выглядит план там же без хаков?!

          0
          В оригинальной статье есть соответствующий запрос и оба варианта плана — и с BitmapOr, и с деградацией до Seq Scan. Этот вариант не претендует на суперскорость, но гарантирует отсутствие Seq Scan — если не все записи за одну дату, конечно.
            0

            Глянул, грустно. Я надеялся по простоте душевной что слоник умеет выбирать по индексу и досортировывать потом…

        –4

        Из опыта работы.
        Ни одному юзеру никогда не требовался этот самый реестр, особенно с пейджингом.
        Что касается таких учетных систем, как сбис, 1с, axapta, и прочих, прочих
        Юзер всегда ищет конкретный документ! Всегда!
        Юзер, работающий с потоуом звявок Всегда (!!) будет смотреть только первые 5-10 строк и выбирать из них.
        По этому. Все эти реестры документов и "проблемы" сортировки лишь в головах разработчиков.
        Создавать индексы нужно правильно, но нужно.
        Проблемы мутации кортежей надо отслеживать и применять разные техники. Например партицирование и прочее, а не отбрасывать с определением, что вставуа медленная…
        Если она медленная, то это проблема архитектуры БД.
        Иначе прюолучишь проседание по выборкам с фулсканами.
        По мне, так это костыль, для прилуманной проблемы.

          +1
          Ни одному юзеру никогда не требовался этот самый реестр, особенно с пейджингом.

          а, например, покупка авиабилетов? (да и в целом, логистика)

          Что касается учётных систем, то совсем не редкость, когда что-то с чем-то не сходится, и тогда юзер начинает «крыжить» документы.
            0

            В любой системе на любом сайте не зря есть строка поиска. И совмем не поосто так ее стараются унифицировать в плане распознавания семантики запроса.
            Самый простой и очевидный пример — гугл. Много ли людей по статистике при поиске пользуются пэйджингом?

            0
            Юзер всегда ищет конкретный документ! Всегда!

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

              А у вас опыт, простите, юзера или разработчика?


              Юзер всегда ищет конкретный документ!

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

                0

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

                  0
                  Мне кажется, что не нужно обязательно заземлять теоретическое решение на возможность практического его применения, тем более в решении конкретной или типичной бизнес-задачи.

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

                  Поэтому я просто запомнил, что существует прикольный способ — пусть даже 100% как гимнастика ума, ибо в практическом применении действительно а) размер специального индекса будет пренебрежимо мал по сравнению с размером записи в таблице реестров, б) обычно в бизнес-таблицах и так несколько индексов, так что компактный индекс, одна из колонок которого — кластерный, перестроить будет несложно
                  0
                  Есть еще одна интересная задача, на которой слоник валится, а хотелось бы что бы не тупил и полетел.

                  Представьте что у вас есть массив циферок в строчке — разделов. Так вот, если по нему построить составной btree (cats, ctime) — то вы получите все комбинации того, что лежит внутри cats и списки строк отсортированные по ctime, но индекс не будет толком работать при поиске по вхождению в этот индекс: например cats @> array[2] и будет давать full scan, а вот … where cats = array[2] order by ctime даст, через, так называемый sort hint, очень быструю выдачу по вторичному ключу (не забудьте limit).

                  Если сделать индекс gin (с расширением btree_gin) — то запросы @> заработают, но вот незадача, sort hint, увы, на gin по полю ctime уже не заработает.
                  Если кто знает как это решить без доп-таблицы и пачки вариаций btree индексов с where cat @> 1,2,3…, поделитесь плиз )
                    0
                    А если попробовать btree_gist и distance-оператор для k-NN? Что-то вроде WHERE cat @> '{1,2,3}'::int[] ORDER BY point(ctime, ctime) <-> point(0, 0) LIMIT 1, если я правильно понял задачу.
                      0
                      Вот, ровно этот кейс в п.2:
                      www.percona.com/blog/2020/09/10/index-improvements-in-postgresql-13
                      Только PG13 нужен.
                        0
                        я пробовал — не пашет, с circle может быть, но хинт сортировки — все еще никак. Приходится триггерами приводиться в 2ую форму.
                      0
                      чуть голова не лопнула, но запрос курил до понимания, такого в mysql похоже не провернуть.
                        0

                        Не заумно ли тут все написано? Хотя, ту да голый SQL или поздно и я не уловил сути.


                        Я делал подобный финт ушами на linq2db (C#), как-то обходился без CTE и UNION по ненадобности.
                        Главное правило, все что в ORDER BY дожно быть уникальным ключем и тогда такой пейджинг делается с пол пинка. Где-то у меня валялся алгоритм который любой LINQ запрос заворачивал в такой пейджинг. По заявкам откопаю.


                        Принцип простой, есть ORDER BY asc1, asc2, desc1 DESC
                        asc1 + asc2 + desc1 — обязательно уникальный ключ


                        Первый запуск


                        SELECT * FROM table t
                        ORDER BY t.asc1, t.asc2, t.desc1 DESC
                        LIMIT 101

                        Берем на одну запись больше запоминаем asc1, asc2, desc1 последней записи. Также в таком варианте мы уже можем знать что страница последняя, на клиент возвращаем на одну запись меньше.


                        Второй запуск, следующая страница


                        SELECT * FROM table t
                        WHERE t.asc1 >= asc1 AND t.asc2 >= asc2 AND t.desc1 <= desc1
                        ORDER BY t.asc1, t.asc2, t.desc1 DESC
                        LIMIT 101

                        Повторяем запоминание попоследнаей записи.


                        Конечно алгоритм чуток больше еще учитывал, просто передал кратко принцип

                          0
                          Тут тема именно в недопущении Seq Scan, когда в индексе (dt, id), а в запросе ORDER BY dt, id DESC — посмотрите планы в исходной статье.

                        Only users with full accounts can post comments. Log in, please.