company_banner

Почему нужна инструментальная поддержка пагинации на ключах

Автор оригинала: Markus Winand
  • Перевод

Всем привет! Я бэкэнд-разработчик, пишу микросервисы на Java + Spring. Работаю в одной из команд разработки внутренних продуктов в компании Тинькофф.



У нас в команде часто встает вопрос оптимизации запросов в СУБД. Всегда хочется еще чуть-чуть быстрее, но не всегда можно обойтись продуманно выстроенными индексами — приходится искать какие-то обходные пути. Во время одного из таких скитаний по сети в поисках разумных оптимизаций при работе с БД я нашел бесконечно полезный блог Маркуса Винанда, автора книги SQL Performance Explained. Это тот самый редкий вид блогов, в котором можно читать все статьи подряд.


Хочу перевести для вас небольшую статью Маркуса. Ее можно назвать в какой-то степени манифестом, который стремится привлечь внимание к старой, но до сих пор актуальной проблеме производительности операции offset по стандарту SQL.


В некоторых местах я буду дополнять автора пояснениями и замечаниями. Все такие места я буду обозначать как «прим.» для большей ясности


Небольшое введение


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


Итак, ключевое слово offset указывает базе пропустить первые n записей в запросе. Однако база все еще должна прочитать эти первые n записей с диска, причем в заданном порядке (прим.: применить сортировку, если она задана), и только после этого будет возможно вернуть записи начиная с n+1 и далее. Самое интересное, что проблема не в конкретной реализации в СУБД, но в изначальном определении по стандарту:


...the rows are first sorted according to the <order by clause> and then limited by dropping the number of rows specified in the <result offset clause> from the beginning…
-SQL:2016, Part 2, 4.15.3 Derived tables (прим.: cейчас самый используемый стандарт)

Ключевой пункт здесь в том, что offset принимает единственный параметр — количество записей, которые нужно пропустить, и все. Следуя такому определению СУБД может только достать все записи, а затем отбросить ненужные. Очевидно, что такое определение offset’а заставляет проделывать лишнюю работу. И тут даже не важно, SQL это или NoSQL.


Еще немного боли


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



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


Рисунок наглядно изображает такую ситуацию. База читает первые 10 записей, после этого вставляется новая запись, которая смещает все прочитанные записи на 1. Затем база берет новую страницу из 10 следующих записей и начинает не с 11-й, как должна, а с 10-й, дублируя эту запись. Есть и другие аномалии, связанные с использованием этого выражения, но эта — самая распространенная.


Как мы уже выяснили, это не проблемы конкретной СУБД или их реализаций. Проблема — в определении пагинации по стандарту SQL. Мы говорим СУБД, какую страницу нужно достать или как много записей пропустить. База просто не в состоянии оптимизировать такой запрос, так как для этого слишком мало информации.


Стоит также уточнить, что это проблема не конкретного ключевого слова, а скорее семантики запроса. Есть еще несколько идентичных по проблемности синтаксисов:


  • Ключевое слово offset, как говорилось ранее.
  • Конструкция из двух ключевых слов limit [offset] (хотя сам по себе limit не так уж и плох).
  • Фильтрация по нижним границам, построенная на нумерации строк (например, row_number(), rownum и т. д.).

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


Далее в этой статье ключевое слово offset используется как обобщение всех этих вариантов.


Жизнь без OFFSET


А теперь представим, каким был бы наш мир без всех этих проблем. Оказывается, жизнь без offset не так уж и сложна: селектом можно выбирать только те строки, что мы еще не видели (прим.: то есть те, которых не было на прошлой странице), с помощью условия в where.


В этом случае мы отталкиваемся от того факта, что селекты исполняются над упорядоченным множеством (старый добрый order by). Поскольку имеем упорядоченное множество, можем использовать довольно простой фильтр, чтобы доставать только те данные, которые находятся за последней записью предыдущей страницы:


    SELECT ...
    FROM ...
    WHERE ...
    AND id < ?last_seen_id
    ORDER BY id DESC
    FETCH FIRST 10 ROWS ONLY

Вот и весь принцип такого подхода. Конечно, при сортировке по многим столбцам все становится веселее, но идея все та же. Важно заметить, что эта конструкция применима на многих NoSQL-решениях.


Такой подход называется seek method или keyset pagination. Он решает проблему с плавающим результатом (прим.: ситуация с записью между чтениями страниц, описанная ранее) и, конечно, что мы все любим, работает быстрее и стабильнее, чем классический offset. Стабильность заключается в том, что время обработки запроса не увеличивается пропорционально номеру запрашиваемой таблицы (прим.: если хочется подробнее узнать про работу разных подходов к пагинации, можно полистать презентацию автора. Там же можно найти сравнительные бенчмарки по разным методам).


Один из слайдов рассказывает о том, что пагинация по ключам, конечно же, не всемогущая — она имеет свои ограничения. Наиболее значимое — у нее нет возможности читать случайные страницы (прим.: непоследовательно). Однако в эпоху бесконечного скроллинга (прим.: на фронтэнде) это не такая уж и проблема. Указание номера страницы для щелчка — в любом случае плохое решение при разработке UI (прим.: мнение автора статьи).


А что с инструментами?


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


Ситуацию усугубляет то, что описанный метод требует сквозной поддержки в используемых технологиях — начиная от СУБД и заканчивая исполнением AJAX-запроса в браузере при бесконечном скроллинге. Вместо того чтобы указывать только номер страницы, теперь придется указывать набор ключей для всех страниц сразу.


Однако количество фреймворков, поддерживающих пагинацию на ключах, постепенно растет. Вот что есть на данный момент:



(Прим.: некоторые ссылки были убраны ввиду того, что на момент перевода некоторые библиотеки не обновлялись с 2017—2018 года. Если интересно, можно заглянуть в первоисточник.)


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


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


Заключение


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


Как следствие, немногие задумываются о смене подхода к пагинации, а из-за этого и инструментальная поддержка со стороны фреймворков и библиотек развивается слабо. Поэтому, если вам близка идея и цель безофсетной пагинации, — помогите распространить ее!


Источник: https://use-the-index-luke.com/no-offset
Автор: Markus Winand

Tinkoff.ru
IT’s Tinkoff.ru — просто о сложном

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

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

    +1
    Как-то я раньше не рассматривал этот вопрос комплексно. Использую пажинацию по ключам в проекте по факту и давно уже подумываю про оптимизацию. Думаю, в ближайшее время попробую сделать библиотеку для golang с поддержкой этого вида пажинации.
      0
      Вы же в курсе, да, что автоинкрементальные ID не обязаны появляться в БД в строгом порядке? И запись под номером 9 может появиться после записи под номером 11?
        +3

        Это не существенно. Если вы знаете, что в вашем конкретном случае они появляются не по порядку, вы можете использовать поле date. Всё абсолютно точно так же, date < ?last_seen, order by date desc

          +2
          date точно так же может не соответствовать порядку появления записей в БД
            +2
            date здесь как пример любого поля по которому отсортирована выборка, т.е. не зависимо от порядка добавления вывод будет верным.
            0
            это не мой конкретный случай. Все БД так работают. Почитайте про изоляцию транзакций в SQL базах. Ваша запись не будет видна, пока транзакция не закомичена. Это фундаментальная проблема, а не вопрос выбора поля.
              0
              И как же изоляция может привести к такому чудесному результату?
              Спойлер
              Да никак.
                0
                TX1                 |    TX2            | TX3
                ---------------------------------------------
                BEGIN               |                   |
                INSERT INTO BOOKS   |                   |
                                    | BEGIN             |
                                    | INSERT INTO BOOKS |
                                    | COMMIT            |
                                    |                   |  BEGIN
                                    |                   |  SELECT * FROM BOOKS ORDER BY ID
                                    |                   |  COMMIT
                COMMIT              |                   |
                                    |                   |  BEGIN
                                    |                   |  SELECT * FROM BOOKS ORDER BY ID
                                    |                   |  COMMIT
                

                  0
                  И? Тут чистая видимость транзакции — и, внезапно, никакого нарушения порядка вставки!
                  Смотрите, ваш пример
                  -- табличка, создаем сразу
                  use tempdb;
                  drop table if exists books;
                  create table books (id int not null identity primary key, val int not null, dt datetime default sysdatetime());
                  


                  -- сессия 1
                  -- вот от этой штуки зависит результат
                  set transaction isolation level read committed;
                  begin tran;
                  insert	into books(val) values (1);
                  waitfor delay '00:00:30';
                  commit;
                  


                  -- сессия 2
                  -- уровень изоляции тот же, что в скрипте 1 для однозначности, например
                  set transaction isolation level read committed;
                  begin tran;
                  insert	into books(val) values (2);
                  commit;
                  


                  -- сессия 3
                  -- уровень изоляции тот же, что в скрипте 1 для однозначности, например
                  set transaction isolation level read committed;
                  select * from books;
                  


                  В зависимости от уровней изоляции законно получаем разные эффекты, но всегда, абсолютно всегда сервером гарантируется, что более ранняя вставка имеет меньший identity. Если какие-то записи чтение/вставку не блокируют (например, при read uncommitted/RCSI), то никакого нарушения нет, а есть только в чистом виде эффекты изоляции. С тем же успехом можно было, например, заблокировать запись и делать широкие выводы вида «таракану оторвали ноги — таракан не слышит».
                    0
                    Здасьте… Для внешнего наблюдателя (txn3) из моего примера сначала появится запись из txn2. и результат select будет (2). После коммита txn1 для внешней транзакции (txn3' ) список будет уже (1, 2). Таким образом, для внешнего наблюдателя запись N2 появляется раньше записи N1. Я не понимаю, о чем тут вообще спорить. это самые базовые вещи.
                      0
                      Для внешнего наблюдателя (txn3) из моего примера сначала появится запись из txn2
                      Во-первых, абсолютно необязательно. Про уровни изоляции я не просто так обращал внимание. Обычный уровень RC и любой выше, как в моем примере, покажет в примере сразу две записи, и только когда завершится вторая сессия. А Read Uncommitted aka грязное чтение — и вовсе по мере появления незакоммиченных записей. А вот с RCSI действительно будет сначала результат второй транзакции, затем — обеих. С верным порядком ключей — сначала более ранняя вставка и никак иначе, ни при каком варианте!
                      Во-вторых, опять же, это ровно никакого отношения к порядку ключей относительно порядка вставки не имеет, могу лишь повторить повторить:
                      Тут чистая видимость транзакции — и, внезапно, никакого нарушения порядка вставки!
                      Вещь эта, конечно, базовая, но базовая вообще безотносительно автоинкремента, уберите автоинкремент — и абсолютно ничего в примере не изменится.

                      А вот выше вы утверждали:
                      Вы же в курсе, да, что автоинкрементальные ID не обязаны появляться в БД в строгом порядке? И запись под номером 9 может появиться после записи под номером 11?
                      Это, простите, просто дичь.
                        0
                        > Обычный уровень RC и любой выше, как в моем примере, покажет в примере сразу две записи

                        Очень интересно. И как же результат txn1, недостигшей еще COMMIT, будет виден другой транзакции с уровнем READ COMMITTED?

                        PS. READ UNCOMMITTED это вообще хак, и далеко не везде он поддерживается
                          0
                          Очень интересно. И как же результат txn1, недостигшей еще COMMIT, будет виден другой транзакции с уровнем READ COMMITTED?
                          У меня вообще-то написано ровно обратное, причем вы еще и окончание предложения снесли. Наверно, случайно так получилось:
                          Обычный уровень RC и любой выше, как в моем примере, покажет в примере сразу две записи, и только когда завершится вторая сессия
                          Еще раз: при read committed результат будет виден извне только сразу для двоих записей. Сразу для двоих, т.е. одной записью из первой сессии выхлопа вообще не будет, понимаете? А случится это только тогда, когда обе транзакции из вашего примера зафиксируются.
                          PS. READ UNCOMMITTED это вообще хак, и далеко не везде он поддерживается
                          Не знаю, что такое хак в лично вашем определении, но то, что грязное чтение поддерживается не везде, опять же ничего не меняет.

                          Вы вообще чрезвычайно легко даете определения, категорически противоречащие общепринятым, чего стоит одно это:
                          Под автоинкрементом обычно подразумевается, что новой транзакции будет выдан номер больший, чем последний, использованный до этого
                          Автоинкремент — это номер транзакции? Да, а номер транзакции — это что такое, вы забыли определить? И выводите из этого дальше сапоги всмятку. На самом деле автоикремент — это значение столбца, автозаполняемого монотонно данными с заданным приращением в порядке вставки. Вот вам, например, по-русски, ознакомьтесь: docs.microsoft.com/ru-ru/sql/t-sql/statements/create-table-transact-sql-identity-property?view=sql-server-ver15
                            0
                            Вы в своем уме вообще? Вы сейчас пишите, что пока есть хоть одна незакомиченная транзакция, не будет виден результат ни одной из них.

                            Час от часу не легче.
                              0
                              А почему вы всегда настолько перевираете мои слова? Опять само так получилось? Я ведь опять ничего подобного не писал. А писал я про ваш пример, который вы срисовали откуда-то, не поняв, что он значит. А значит он, что пока есть хоть одна блокировка, несовместимая по чтению с выбранной на выбранном уровне изоляции (а читать третья сессия хочет всю таблицу, а не диапазон ключей) — читающая на обычном уровне RC будет ждать, именно потому что не закоммичена запись, которую требуется прочитать. Она даже называется Read Committed именно поэтому. Я же вам готовый скрипты дал, просто попробуйте их выполнить. И да, в боевых условиях при этих же вводных будет ровно тот же эффект.
                              Ну прочтите вы хоть что-то по теме, по которой собрались спорить, чтобы понять хоть этот абзац. Ну хотя бы про RC, что ли. Вы же даже логического смысла блокировок не понимаете, зато смело несете в массы свои определения типа
                              Это просто определение того, что значит «появиться раньше/позже» с точки зрения наблюдателя системы
              +2

              А если там несколько записей с одним date, и страница закончилась в середине последовательности?

              +3
              Под автоинкрементом обычно подразумевается, что значения будут монотонно возрастать. Другое дело, что можно самому установить конкретное значение и этот атрибут уже не будет возрастать монотонно (или вообще использовать рандомный uuid), но для этого мы и должны указывать явную сортировку, а наш ключ, покрыть индексом с такой же сортировкой как и в order by. Поправьте, если неправильно понял ваш вопрос
                +1
                Под автоинкрементом обычно подразумевается, что новой транзакции будет выдан номер больший, чем последний, использованный до этого. Но порядок начала транзакций или инсертов в них не совпадает в с порядком окончания транзакций и коммита. Поэтому у вас одна транзакция началась раньше, получила номер 10, потом потупила немного, а когда закончилась, транзакция с номером 11 уже давно вставила запись.

                По этой же причине не работает и таймстэмп, как предложили выше. Он тоже вычисляется на момент начала транзакции или на момент insert. А закончится ваша транзакция через 100 мс, или через 100 сек, никто не знает.
                  0
                  Нет никаких транзакций с номер 10. Есть автоинкрементный ключ вставляемой записи, и он получает значение строго на момент вставки, и при этом строго возрастает. Т.е. ранее вставленная строка всегда имеет значение меньшее, чем вставленная позднее. Это все, что требуется знать для понимания ситуации. Никакие другие факторы, включая время начала транзакции, не меняют вообще ничего. Даже откаченная транзакция просто приведет к пропуску значения, что ничего не меняет в сказанном выше. Так что
                  Вы же в курсе, да, что автоинкрементальные ID не обязаны появляться в БД в строгом порядке? И запись под номером 9 может появиться после записи под номером 11?
                  Оба утверждения ложны: автоинкрементные столбцы появляются всегда в строго монотонном порядке (если исключить зацикливание в некоторых СУБД) и запись со значением 9 не может появиться после записи 11 (в случае положительного приращения и с тем же исключением, что и выше). Ну, или вы имели в виду написать совсем не то, что написали, дав свое определение понятия упорядочивания по времени (что, видимо, следует из комментов).
                    0
                    t1. `SELECT *` => (A); 
                    t2>t1. `SELECT *` => (A, B); 
                    

                    Значит B появился позже A.

                    И в зависимости от времени коммита транзакций может быть A=2, B=1
                      0
                      Значит B появился позже A
                      Не значит.
                      Читайте про изоляцию транзакций — именно там написано, что и почему вышеприведенное значит.
                        0
                        При чем здесь вообще изоляции и транзакции? Это просто определение того, что значит «появиться раньше/позже» с точки зрения наблюдателя системы.
                  0
                  а почему вы просто не используете оставляете открытыми scrollable курсоры раз уж у вас Java? и закрывать их по таймауту. можно же даже двунаправленные.
                    0

                    Курсоры не явы драйвер их создает и "держит" на БД.
                    Кроме то-го что это дорого в плане ресурсов само БД это еще головная боль с закрытием этих курсоров в вашем коде- это то что вы не хотите на самом деле иметь в вашем сервисе.

                  +1
                  А в чём вы тут видите проблему? Если у вас в ТЗ указано условие, что данные надо сортировать по ID или по другому полю (которое укажет пользователь), то какая разница в каком реально порядке эти записи попали в базу? Значение имеет только то, что увидит пользователь. А при использовании сортировки он всегда увидит данные в строгом порядке.
                    0
                    Проблема в динамическом случае. Если таблица статична, то все ок. При листании страниц могут быть дырки если мы листаем от меньших значений к большим.
                    1 — посмотрели. следующая стр
                    2 — посмотрели. следующая стр
                    3 — еще не закоммичена
                    4 — посмотрели. следующая стр. Допустим тут 3 уже закоммитили. нет никакого способа увидеть этоу запись, какое бы поле сортировки/курсора вы не использовали.
                    5 — увидем 5 итд. 3 не будет показана

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

                      Да, разновидность этой проблемы (добавление данных после начала "листания") в статье уже указана. Решать её надо другими методами, которые зависят от критичности этой проблемы. Например можно с каждой страницей возвращать некий ETag, который сможет показать клиенту, что данные, с момента начала листинга, изменились.

                        0
                        Да. без дополнительного UX проблема не решается. Но etag тоже непросто сделать. Наивная имплементация etag = max(id) не будет работать по той же причине. Версия MVCC тоже не подходит, потому что в БД же миллион несвязанных изменений. Надо подумать, но что-то не уверен как можно etag реализовать дешево (очевидно перечисление всех id будет таким тэгом, но не сканить же всю бд ради этого).
                          0

                          Само по себе значение ETag не так важно. Важен факт его изменения. А это несколько проще реализовать. Например хранить в отдельной таблице (или даже в чём-то вроде Redis) некий uuid или просто автоинкремент, генерируемый при каждом изменении данных.

                            0
                            ок, согласен
                              0
                              А что делать предлагается в случае, если etag поменялся? В активной системе новые записи могут постоянно потоком добавляться.
                                0

                                Нуу, тут можно книгу написать по этой теме. Всё зависит от требований к системе и имеющихся ресурсов. Варианты навскидку:


                                • ничего не делаем, продолжаем листать;
                                • перечитываем всё с начала в бесконечном цикле, пока не успеем всё прочитать в промежуток между изменениями;
                                • продолжаем листать дальше, а потом запрашиваем с сервера историю изменений за время пока листали, и с её помощью фиксим полученный список;
                                • и т.д. и т.п
                    0
                    В посте не хватает примеров, как быть, если надо выбирать данные с разной сортировкой. К примеру довольно часто надо выбирать от новых к старым записям и по рейтингу. Если первое не вызывает затруднений, тут опираемся на автокриментируемый индекс, то с рейтингом возникают проблемы — рейтинг не уникален по всей таблице.
                      0
                      Если я вас правильно понял, то составной индекс должен покрыть этот кейс. Статья, как я упомянул, больше обзорная (манифест), описание подхода, его сильных и слабых сторон, без фанатизма. Вообще говоря, автор примерно в 3х статьях описывает общий подход как построить такие запросы, начиная от pipelined order by и взаимодействии с ним запросов top-n, до конкретных реализаций с некоторыми замерами производительности. Если этот перевод многим зайдет, то постараемся выложить переводы оставшихся статей с пояснениями и некоторыми дополнительными замерами
                        0

                        Сосздание индексов на все случаи жизни — так себе решение, тк увеличивает нагрузку на сервер БД при вставке/модификации данных. Палка о 2-х концах, так сказать. К тому же это не сработает а случае join-ов.
                        Как правильно заметил delimer, метод не будет работать в случае сортировки по неуникальному полю, но идея хороша, хоть и для частных случаев.

                      +3
                      И второй момент. Такую pagination можно сделать, если на странице предусмотрены только кнопки назад-вперед. А UX команда, например, хочет чтобы были номера страниц и ссылки на любую страницу. Жизнь – боль.
                        +1
                        Пусть сначала объяснят, зачем это может понадобиться пользователю и чем это удобнее последовательного просмотра
                          +1
                          Пусть для начала объяснят, чем отсутствие произвольного доступа лучше его наличия. Последовательный-то никуда не девается в обоих случаях.

                          Мое лично отношение к тем, кто выдвигает такие идеи — чтоб у вас, умников, книжки были исключительно с инфинити-скролом. Чтобы для того, чтобы продолжить читать с 300-й страницы, нужно было пролистать предыдущие 299.
                            0
                            Веб страница или экран приложения со списком записей, это не книга и ее не читают от корки до корки. Аналогия неуместна.
                              0
                              А элеткронная книга — это не «экран приложения со списком записей»?
                                0
                                А что в электронной книге будет элементом списка записей?
                                  0
                                  Страница текста (например в PDF).
                                  Сразу возражу, то что они выводятся по одной за раз никак не влияет на механику постраничной навигации.
                                    +1
                                    Веб-страницы, выводящие списки с традиционной постраничной навигацией по номерам страниц (например, тут), в подавляющем большинстве случаев не имеют возможности мгновленно перехода к произвольной странице, так как содержат лишь малую часть ссылок: 1, 2, 3 [пробел, многоточние] N. Все ссылки просто на страницу не поместятся. Так что ее работа мало чем отличается от последовательного скроллинга, а проблем с производительностью такой способ создает много.
                                    К тому же содержимое книги постоянно, а списки из БД могут меняться. их элемены могут добавляться/удаляться, поэтому что на какой странице находится не так уж и важно по большому счету. Никто такие списки не просматривает, начиная со страницы M. Аналогия с книгами неуместна, потому что списки на веб-страницах в общем случае не являются книгами, а не наоборот. К ним другие требования и возможности у них другие.

                                      0
                                      Ссылки могут быть вида 1, 2, 10, 11, 100, 400, 509, 510. И это реально удобно в использовании. Но это уже явно не последовательный скроллинг.
                                        0
                                        Могут то могут, но что-то не видел я такого. Хорошо, допустим вам нужна страница 200, как до нее добраться по вашему примеру? А главное зачем? Что такого конкретного может быть на 200 странице, чтобы была необходимость прямого перехода туда?
                                          0
                                          Через сотую, где будет уже 100, 101, 102, 200.

                                          Удобная вещь, когда надо просматривать большое количество данных, но выборочно и не целиком.
                          +1
                          И я бы посмотрел как они предложат уместить ссылки на каждую из 100500 страниц. А вариант с многоточнием посередине чем принципиально отличается от последовательного просмотра с точки зрения UX?
                          +3
                          Указание номера страницы для щелчка — в любом случае плохое решение при разработке UI (прим.: мнение автора статьи).

                          Можно чуть подробнее раскрыть этот момент, почему «плохо»? В итоге мы получаем стрелочки <- -> у которых «под капотом» скрывается id последнего отображенной сущности на странице?
                            0
                            да; Последней и первой (чтобы back тоже можно было сделать)
                              0
                              Эх! Я успел обновить свой первый вопрос. Повторюсь, почему, с точки зрения UI, решение с номерными страницами – плохо?
                                0
                                Почему так считает автор — не знаю. Я так считаю, потому что пока вы шли от 1 страницы до 10 появились новые записи, и если вы пойдете обратно и дойдете до как бы первой страницы, то нужен вменяемый интерфейс, что бы сказать пользователю, что там еще записей навалило.

                                Здесь подразумевается самый распространенный случай, когда новые записи отображаются в начале.
                                0
                                Ну и вообще, если данные постоянно меняются, то что такое «вторая страница» формализовать довольно сложно
                                  0
                                  1. Для получения номера последней страницы нужно выбрать и посчитать все записи. Уже при миллионах записей это работает никак. Для современных СУБД миллиард записей — нормальная ситуация. Даже для того, чтобы убедиться что страниц "очень много" (и можно забить на нумерацию) нужен достаточно тяжёлый запрос.
                                  2. Содержимое N-й страницы зависит от всех предыдущих и потенциально разное при каждом селекте.
                                  3. Ну и как правильно указали в статье — для номерной страницы часто используют offset, который в лучшем случае линейно зависит от номера страницы.
                              0
                              AND id < ?last_seen_id
                              Это для всех типов ID, или строго Integer? А то там может быть и истинно рандомный GUID.
                                0
                                Очевидно, что должен быть ключ, по которому вы будете упорядочивать свои записи. Можно random guid — на статических данных прокатит. )))
                                  0
                                  на статических данных прокатит
                                  Не, ну это не спортивно — на статических проблема внезапного появления записи даже и не возникнет.
                                +5
                                Автор забыл (а может и специально умолчал) про важное ограничение для этого способа. А именно то, что поле (или поля), используемое для паджинации по ключу, должно быть «уникальным» и обязательно указываться на первом месте с списке полей используемых для сортировки.
                                Такие ограничения очень сильно уменьшает возможности использования этого метода.
                                  0
                                  Ну сортировка по этому полю – не так страшно обычно, вам же нужно объяснить БД, что такое ось времени в вашем случае. Реализация навигации без сортировки записей будет странна, потенциально каждый раз возвращая рэндомный результат. Если нужен другой порядок по этому же полю, то можно повторно пересортировать уже данные одной страницы в памяти (на сервере, или на клиенте), или обернуть еще один запрос.

                                  Хуже то, что монотонность не гарантирована. По крайней мере в PG. может есть БД, которые при вставке позволяют поставить «таймстэмп» времени окончания транзакции, но я не знаю таких.
                                    0
                                    Часто «уникальное» поле и поле для сортировки — это разные поля. Например часто сортировать надо по дате создания/обновления записи. И что бы такое поле было ещё и уникальным — это надо заморочится в самом начале разработки (менять старые данные не всегда допустимо).
                                      +1
                                      обычно используют составной атрибут (timestamp, uuid) в таком случае. Разве осались БД, которые не поддерживают составных индексов?
                                        0
                                        Да, индекс по паре (sort_column, unique_column) и использование его для сортировки при паджинации — это подходящее решение. Но надо понимать, что оно увеличивает размер индексов (особенно если надо уметь сортировать по разным полям).
                                          0
                                          Верно, но вообще обычно размер ключа индекса довольно слабо влияет на производительность. Слабее, чем количество индексов. Поэтому довольно часто используют почти забесплатно covering indexes.
                                            0

                                            В MS SQL часто по подходящему уникальному полю есть кластеризованный индекс, а значит его значения есть в каждом некластеризованном. В этом случае на самом деле индекс (sort_column) и (sort_column, unique_column) на уровне движка БД тупо одинаковый.
                                            PS: Для Oracle и PostgeSQL это не так.

                                    0
                                    А зачем постраничная выборка?

                                    Чем сложнее механизмы выборки данных, тем сложнее пользователю понять правила начитки и ориентироваться со списком.
                                    В частности, как замечено в статье, в случае составных индексов, сортировок и фильтров, сложные механизмы механизмы начинают лажаться. Пользователь теряется.

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

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

                                    С переходом на веб-приложения в последние 10 лет в контролах используем исключительно:
                                    1. ограничение на размер возвращаемых записей (200-500)
                                    2. фильтр по всем колонкам (в некоторых колонках multi-select из списка возможных) и сортировку.

                                    Значительно упрощает обращение к базе, понимание пользователем настроек выборки, скорость просмотра записей (грид без постраничной выборки).
                                      +1
                                      А как без нее? Всю базу сразу вываливать?) У бесконечного скроллинга под капотом тоже постраничная выборка
                                        0
                                        А как без нее? Всю базу сразу вываливать?
                                        Ограничивать выборку и делать удобную фильтртацию по клонокам.
                                        Как я писал выше «SELECT TOP 500 ...»
                                        Если программист вываливает пользователю больше 1000 записей одновременно, то нужно пересмотреть дизайн грида.
                                          0
                                          А, то есть весь список никогда не показывать, а показывать всегда, допустим, MAX 500 элементов и выводить общее количество, чтоб пользователь понимал, что это не все и искал нужные ему элементы списка поиском?
                                          P.S. так то почему нет, достойный способ, но не подойдет для краулеров, котороым нужно проиндексировать все данные.
                                            0
                                            Именно.
                                            Вот пример с сортировкой и фильтром при работе с таблицей из 490к записей:
                                            image
                                            ibb.co/6Bs90HB
                                              0
                                              Классно! Спасибо, возьму на заметку.
                                        0
                                        С точки зрения юзабилити например мне нужно посмотреть какую-нибудь прошлую запись, и по моим прикидкам она должна быть где-нибудь на 15-й странице. Скроллом или переходом по одной странице искать замучаюсь, фильтра может и не быть, а если он и есть, то порой проще тыкнуть на страницу 15, если не угадал, то на страницу 14 или 16, чем заморачиваться с уточняющими условиями.
                                        +2

                                        Интересно, что 1С с списками в экранных формах работает именно так — не через offset, а через top N where "записи ниже последней". Это и по причинам прозводительности и по причинам того, что 1С работает с 5 разными СУБД (часто используется общий функциональный минимум).
                                        При этом, кстати, корректно обрабатывается сортировка по нескольким полям при том что первые поля (и комбинации левого "подкортежа" сортировки) не являются уникальными. Там, правда, нюанс — "корректно" не всегда значит "эффективно" — в некоторых пограничных случаях идёт жёсткий пролёт мимо удачного плана, к счастью, это достаточно редкие случаи, которых можно/нужно избегать (а в SQL Server 2005 c SP до четвёртого приводил к падению SQL Server, но это именно бага SQL Server).

                                          0
                                          Это достаточно простой функционал на самом деле.

                                          Кстати, чтобы не пролетать мимо планов есть куда эффективнее способ сначала читать ключи, потом читать колонки. Чуть подробнее в недавней статье.

                                          Ну и еще круче на самом деле отбрасывать сложные фильтры без индексов, находить более широкое «окно» на простых фильтрах для которых есть индексы, а потом добавлять это «окно» в фильтр, чтобы это окно протолкнулось в эти сложные фильтры (чтобы они расчитывались не для всей базы). Но пока так даже lsFusion не умеет, хотя вся инфраструктура для этого есть, возможно в будущих версиях и появится.
                                          +2

                                          В статье как бы смешались все.
                                          Начнем по-порядку.
                                          Сначала надо бы заметить и об этом уже много написано что пагинация есть зло с точки зрния интерфейса (и это не касается эффективноси в базе данных)


                                          Решения пагинанции по ключам просто не существует в природе. Т.к пагинация предполагает произвольный выбор страниц: 3-я, 124-я, 45-я и как в этом случае помогут ключи? Имеется в виду наверное пагинация в стиле next/previous. Но это же как бы совсем другой вид навигации.


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


                                          К тому факту что за момент просмотра страницы пройдут где-то вставки/удаления — некоторые системы это отслеживают в реальном времени. но это же дико грузит и сеть и сервер и приложения. Поэтому уже почти как аксиома кажется что набор является "отсоединенным" от базы данных и иного не моет быть. А еще лет 20 назад все так и было. данные в приложениях менялись мгновенно после изменения их на сервере.

                                            0
                                            Развивая данную идею (OFFSET не нужен, «пляшем» от ключа), можно построить не только пагинацию, но и непрерывный скроллинг — что гораздо интереснее, чем пагинация. Более того, reverse engineering некоторых вещей показывает, что люди давно так его и делают.

                                            Поддержка подобных запросов была бы хороша не только на уровне фреймворков, но и на уровне СУБД.

                                            Уже несколько лет как я пишу по этой проблеме и делал доклад на JPoint, наиболее удачное изложение, на мой взгляд, здесь: dzone.com/articles/hidden-complexity-of-a-routine-task-presenting-tab
                                              0
                                              Да, в статье небольшая заметка есть про это, что бесконечный скроллинг как раз отлично ложится на такой подход.
                                              В целом в статье не только про фреймворки говорится, а что нет комплексных решений для такого подхода. Хотелось бы иметь сквозную технологию, которая упрощала бы все это на всех уровнях, от баз данных до исполнения на фронте
                                                0
                                                Бесконечный скроллинг — это лишь один из возможных подходов, довольно тривиальный. Я же рассказывал про то, как мы сделали честный скроллинг на датасете в несколько млн записей, развивая идею про «пляшем от ключа».
                                                  0

                                                  Не совсем понимаю какие проблемы с реализацией непрерывного скрола в тех же гридах с данными в смысле если отбросить проблемы с интерфейсом. Есть на самом деле интересные задачи. Например на популярном сайте который хостинг которое циклические видео нужно показывать список в порядке убывания рейтинга. Но рейтинг постоянно меняется и уже просмотренное видео может показаться в другом месте и его нужно исключить из показа. Или же в магазине с большой номенклатурой нужно показывать клиентам рандомный список товаров чтобы они равномерно продавались а не только те что в верхней части алфавита или в топе продаж.
                                                  Отдельная тема обновление данных естественно так чтобы не положить сервер. Тут уже были бы в помощь базы данных с подпиской на обновление. Такой функционал есть например у rethinktdb разработка которой к сожалению остановлена вендоргм и перешла в оперативную разработку и наверное уже практически не продвигается.

                                                    0

                                                    Подписка на обновления есть у оракла

                                              0

                                              На самом деле, идеальный вариант это использование одного и того же курсора, которые, кстати, могут быть и двунаправленными, те можно читать и предыдущие строки. Переоткрытие курсора для пагинации в любом случае гораздо более тяжёлая операция, а особенно при отсутствии подходящих ключей. Есть, конечно, некоторая сложность в сохранении открытого курсора при трехзвенке, но вполне решаемая(как будет время, покажу мой вариант). А для двухзвенки, так вообще единственно правильный вариант.

                                                0

                                                Но курсоры это же не у всех без данных. Это же oracle и pervasive и может быть mssql не помню точно

                                                  0

                                                  Oracle, PostgreSql, mssql, db2 точно поддерживают. Вообще поддерживают все, чьи драйвера полноценно поддерживают JDBC

                                                    0

                                                    Я уже лет 15 не работал с java. На тот момент середины нулевых ни один драйвер из мной проверенных не поддерживал динамических курсоров которые менялись бы в случае изменения данных на сервере. Oracle я не проверял ок у них тоже только начался процесс с выходом бесплатной ограниченной версии.

                                                    0
                                                    Курсоры можно эмулировать с помощью SQL и логики на сервере приложений.
                                                    0

                                                    В статье указан тег PostgreSQL, соответственно про долгоиграющие транзакции с открыми курсорами можно забыть. Это связано с особенностями реализации MVCC и возможным распуханием таблиц и индексов. С Ораклом вроде бы должно прокатить, потому что там MVCC работает совсем по другому, через Undo сегменты. Но сейчас мало кто делает монолиты, уж точно не Тинькофф, значит каждый запрос к back-end (дай следующую порцию данных из курсора) направляется балансировщиком к разным нодам/репликам. Получается, никаких долгоживущих курсоров. Но в теории да, курсоры были бы тут очень кстати, особенно вкупе с уровнем изоляции Repeatable Read, чтоб исключить большинство аномалий чтения.

                                                    0
                                                    MyBatis поддерживает mybatis.org/mybatis-dynamic-sql/docs/select.html
                                                      0

                                                      Описанное Маркусом наивное решение подходит лишь для самых простых случаев, когда сортировки прибиты гвоздями в коде. Мне наверное так повезло, но все системы, в разработке которых я участвовал последние лет 20 (финансовая аналитика, страхование, банки и проч.), поддерживали множественные сортировки и фильтры по всем полям в гридах, во всех экранных формах. Юзер может кликать в заголовки колонок в гриде и выбирать одно или сразу несколько полей для сортировки, и менять её направление.
                                                      Это всегда динамический SQL, и значит индексы для чтения с диска "сразу в правильном порядке" тут не работают. Но при грамотном дизайне хранилища эта проблема решается. Идея в том, что индексы должны отработать раньше, еще до сортировок и лимитов, и это обычно какие-то особые хитрые индексы по всяким служебным полям в таблицах/mat. views.
                                                      В первую очередь большую БД хорошо бы распилить на мелкие кусочки и разнести их физически. Это сокращает размеры сегментов таблиц и высоту индексов, повышает степень параллелизма. Сначала оптимизатор выбирает ноду/шард/партицию, потом по комбинации индексов (partial/functional индексы в сочетании с бинарными рулят) получается уже небольшой кусок данных (ну например десятки тысяч строк), и потом только выполняются сортировки этого ограниченного набора — строго в оперативной памяти, это быстро. Иногда можно помочь оптимизатору избежать дисковой сортировки, подкрутив размер рабочей памяти у конкретных запросов. При скроллинге грида следующие порции выдаются повторными запросами быстрее, т.к. данные кешируются в буферах СУБД и ОС.

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

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