Недостатки стандартного Paging API
Изначально мы должны понять, почему подход с offset pagination не годится для больших датасетов с помощью следующего примера:
Клиент предоставляет два параметра — LIMIT для ожидаемого максимального количества результатов и OFFSET для смещения страницы. Например, с OFFSET = 400, LIMIT = 20, мы возвращаем из БД 20 items, выбрасывая первых 400.
Использование LIMIT и OFFSET плохо работает на больших датасетах. По мере того, как OFFSET возрастает, БД по-прежнему должна прочитать данные вплоть до OFFSET + нужного кол-ва записей с диска, до того как отбросит OFFSET и вернет только ожидаемое количество записей
Если записи поступают в БД с высокой скоростью, текущее окно становится ненадежным для страничного доступа, потенциально приводя к потере данных или возвращению дубликатов.
Решением этой проблемы может являться Cursor API, после каждого запроса возвращающее курсор, который может использоваться клиентом при запросе следующей/предыдущей порции данных.
Cursor API
Cursor API работает посредством возврата в респонсе некого маркера, ссылающегося на определенный айтем датасета. При последующем реквесте этот маркер используется, чтобы запросить результаты, начиная с записей, следующих за маркером.
Предположим у нас есть следующая GET операция REST-сервиса:
GET /api/v1/items/in/{ns}Для каждого из возвращаемых записей нам необходимо иметь уникальное sequential ID, которое для вновь добавляемых записей будет иметь значение большее всех уже существующих. В некоторых БД это может быть уже существующее поле, например числовой первичный ключ. В случае использования цифробуквенного первичного ключа в качестве такого sequential ID может выступать дополнительное поле, например типа serial / bigserial в PostgreSQL.
Значение этого ID для последней из найденныйх записей будет использоваться для формирования прямого (forward) курсора, значение ID первой из найденных записей — для формирования обратного (backward) курсора.
Запрос первой порции данных клиентом
Когда клиент делает запрос первой порции данных, он использует запрос вида:
GET /api/v1/items/in/{ns}?someParam=...&sortBy={sortingFieldName}&size={count}Здесь мы для усложнения добавили еще сортировку по определенному полю с именем sortingFieldName.
При этом к БД выполняется запрос:
SELECT * FROM items
WHERE ... -- apply search params
ORDER BY :sortingFieldName, :sequentialId
LIMIT :countКлиенту возвращается респонс следующего вида:
{
"elements" : [ {
"sortingFieldName" : "John",
"sequentialId" : 37,
...
}, {
"sortingFieldName" : "John",
"sequentialId" : 38,
...
} ],
"nextCursor" : "eyJmaWVsZE5hbWUiOiJuYW1lIiwiZmllbGRWYWx1ZSI6IkX0="
}где в nextCursor закодировано посредством Base64 следующее содержимое:
{
"fieldName" : "sortingFieldName",
"fieldValue" : "John",
"sequentialId" : 38,
"forward" : true
}Указать просто, что мы остановились на значении sortingFieldName=John в предыдущей странице для формирования следующей — недостаточно, т.к. несколько последующих записей также могут иметь то же значение этого поля. Для этого нам и надо sequential ID.
Поле nextCursor отсутствует в response, если мы нашли меньше чем запрошенных count записей (поэтому точно уверены в отсутствии следующей страницы).
(UPD: либо nextCursor можно возвращать в любом случае, если при последнем запросе найдено любое ненулевое кол-во записей, сохраняя в курсоре информацию о последней записи найденного набора)
Поле prevCursor отсутствует в response после первого запроса (в нем cursor отсутствовал в request)
Запрос следующих порций данных клиентом
Когда клиент делает последующий запрос — ему нужно использовать курсор (прямой или обратный) из предыдущего response.
Прямой курсор:
GET /api/v1/items/in/{ns}?someParam=...&sortBy={sortingFieldName}&size={count}&
cursor=eyJmaWVsZE5hbWUiOiJuYW1lIiwiZmllbGRWYWx1ZSI6IkX0=При этом к БД выполняется запрос:
SELECT * FROM items
WHERE ... -- apply search params
AND ((fieldName = :nextCursor.fieldName AND sequentialId > :nextCursor.sequentialId) OR
fieldName > :nextCursor.fieldName)
ORDER BY :sortingFieldName, :sequentialId
LIMIT :countА клиенту возвращается респонс:
{
"elements" : [ {
"sortingFieldName" : "Zeppelin",
"sequentialId" : 39,
...
} ],
"nextCursor" : "eyJmaWVsZE5JuYW1lIiwiZmllbGRWYhbWUiOiWx1ZSI6IkFUR3Jvd",
"prevCursor" : "eyJmaWVsZE5hbWUiOiJuYW1lIiwiZmllbGRWYWx1ZSI6IkFUR3Jvd"
}Здесь prevCursor также представляет собой закодированный посредством Base64 объект:
{
"fieldName" : "sortingFieldName",
"fieldValue" : "Zeppelin",
"sequentialId" : 39,
"forward" : false
}Обратный курсор:
GET /api/v1/items/in/{ns}?someParam=...&sortBy={sortingFieldName}&size={count}&
cursor=eyJmaWVsZE5hbWUiOiJuYW1lIiwiZmllbGRWYWx1ZSI6IkFUR3JvdПри этом к БД выполняется запрос:
SELECT * from items
WHERE ... -- apply search params
AND ((fieldName = :prevCursor.fieldName AND seq_id < :prevCursor.sequentialId) OR
fieldName < :prevCursor.fieldName)
ORDER BY :sortingFieldName DESC, :sequentialId DESC
LIMIT :countПосле этого нам надо обратить порядок записей в результате, чтобы отдать их клиенту с ожидаемым им ордерингом. Респонс имеет аналогичный вид:
{
"elements": [...],
"nextCursor" : "eyJmaWVsZE5hbWUiOiJuYW1lIiwiZmllbGRWYWx1ZSI6IkFUR3JvdXAtd0ZQ",
"prevCursor" : "eyJmaWVsZE5h4YW1lIiwiZmllbGRWYWx1ZSI6IkFUR3JvdXAtTGFtN0B1aR1l"
}Упаковка параметров запроса в сам курсор
В принципе мы можем упаковать параметры запроса (поля someParam и sortBy) в сам курсор, и тогда последующие запросы клиента будут иметь сходный вид для прямого и обратного курсоров:
GET /api/v1/items/in/{ns}?size={count}&cursor={...}А сам курсор иметь вид:
{
"someParam" : ...,
"sortBy" : ...,
"fieldName" : "sortingFieldName",
"fieldValue" : "Zeppelin",
"sequentialId" : 39,
"forward" : true/false
}Итоги
Мы спроектировали Cursor API, представляющее альтернативу стандартному Paging, лишенное некоторых его недостатков.
UPD: по совету в комментариях — добавляю ссылку на статью, где рассматривается аналогичная проблема.
Комментарии (70)
Imbecile
05.08.2018 02:27Может я чего-то не понял, но почему limit и offset плохо работают на больших dataset? Можно конкретный пример?
Shannon
05.08.2018 03:17Если речь не про выборку из таблицы по индексу, то нельзя просто взять и выбрать 20 записей. Нужно знать где они находятся. А чтобы это узнать, придеться промотать 400 записей и взять следующие 20.
Если выборка идет по индексу, то расположение нужных ключей с нужным смешением в отсортированном индексе известно и можно было бы сначала выбрать нужные id для таблицы, а потом по этим айди извлечь данные.
Но обычно выбираются данные из 2-3 заджоинниных таблиц (комментарий + пользователь + пост)
И соотвественно сначала выполняются условия их сджоивания, и к этой новой выборке уже применяется WHERE. Естественно тут уже нет точного адреса где смешение 400 находится.
И как раз одно из решений проблемы тормозов, не использовать where условие, а сделать сначала выборку нужных айдишников по индексу, а потом заджойнить их:
SELECT * FROM test_table JOIN (SELECT id FROM test_table ORDER BY id LIMIT 100000, 30) as b ON b.id = test_table.id
Можно немного про это тут почитать, хотя эта старая моя статья не содержит особых подробностей
habr.com/post/217521apapacy
05.08.2018 11:47Если идёт выборка не по индексу то любая выборка потребует чтение всехзаписпй
Hardcoin
05.08.2018 13:13Суть решения из задачи — добавить в where условие по полям, на которые есть индекс, что бы выборка была по индексу. Это можно сделать разными способами. А вот offset 200000 легко может быть крайне медленным.
apapacy
05.08.2018 14:31Offset также оптимизируется индексами. Хотя я реально запускал лет десять назад на построена на Винде offset и они судя по всему прокручивались весь набор. Сейчас же на линухе и на новых версиях такого не наблюдал.
Hardcoin
05.08.2018 14:36Если у вас одна таблица и offset по полю с индексом — разумеется. Если у вас join и where по обоим таблицам — то нет.
swelf
05.08.2018 02:32Возьмем за пример хабр. пользователь был на первой странице(id 100 — 91), пока он ее листал появилась новая статья(101). Но за счет курсора пользователь перейдя на вторую страницу увидит записи, как будто новой статьи и не было и ничего не сместилось 90-81, а не 91-82? а когда он нажмет на «prevCursor»: «eyJmaWVsZE5h4YW1lIiwiZmllbGRWYWx1ZSI6IkFUR3JvdXAtTGFtN0B1aR1l» он снова попадет на страницу с записями 100-91 как и было изначально и не узнает о новой статье, которая вроде как есть? В тоже время легко можно представить ситуацию, когда такой «курсор» необходим — лента новостей в какомнить контакте, она подгружается по мере промотки страницы и новая статья собьет смещение, что приведет к задвоению статьи, но это наверно не пагинацию.
VolCh
05.08.2018 15:41Да, не увидит на второй странице намека, что появилась новая статья, но вернувшись на первую увидит, что перед ней появилась новая страница.
kalininmr
06.08.2018 00:11это давний спор — хорошо это или плохо.
но как по мне не особо критичный.
критично то, что непонятно как переходить на страницу номер 100, например.
все их рассчитать — дичайшие тормоза
Leg3nd
05.08.2018 02:45БД по-прежнему должна прочитать данные вплоть до OFFSET
Вы хоть раз с файлами работали? Ничего БД не должна прочитать до OFFSET, если ты знаешь размер каждой записи и количество записей, которые нужно пропустить, то ты просто делаешь сдвиг от начального адреса на количество записей умноженных на размер одной записи — это происходит мгновенно в файловой системе благодаря последовательной адресации, а бд в конечном счете хранит ваши данные как раз в файловой системе и работает в конечно счете именно с ней и я уверен что она оптимизирует данные и старается каждую запись из таблички выравнивать по размеруLeg3nd
05.08.2018 03:27+1Оки, погорячился, бывают сценарии по сложней примитивной выборки (сортировка, джоины таблиц), там такое не прокатит
barbos6
05.08.2018 08:21+1Нормальная БД заранее никогда не знает длину записи, средняя же длина записи (температура по больнице) не может помочь при позиционировании.
БД может и не хранить данные в ФС, посему любые аналогии c ФС тут неуместны.Leg3nd
05.08.2018 09:49Это еще почему заранее никогда не знает? Допустим у вас такая схема таблицы:
CREATE TABLE Persons ( PersonID int, LastName varchar(255), FirstName varchar(255), Address varchar(255), City varchar(255) );
Тут элементарно высчитать размер одной записи, средняя температура по больнице не причем.Rsa97
05.08.2018 09:58+2Varchar хранится в виде (длина_строки)(строка), так что размер записи в данном случае может быть от 8 до 1032 байт.
Кроме того, записи хранятся в файле не последовательно, тем более с учётом сортировки.
kalininmr
06.08.2018 00:14если есть индекс подходящий — то всё вполне реально сходу прочитать.
к сожалению так невсегда.
но тот же постгрес довольно таки успешно большими прыжками перемещается по файлу, а не читает линейно
youROCK
05.08.2018 12:35Вы говорите про сценарий условного MyISAM, когда все данные по заданному условию хранятся в уже отсортированнм виде для конкретного запроса WHERE. В то время как такой случай не является чем-то невозможным, но обычно все-таки данные добавляются в одном порядке, а выбирать их хочется в другом. Поэтому последовательно эти данные хранится не могут даже при использовании LSM структур.
a-tk
05.08.2018 11:38+1При таком подходе stateless microservices накрываются медным тазом и возникает куча вопросов синхронизации состояния клиента и сервера.
Как долго на сервере живёт курсор (и потребляет его ресурсы)? Если клиент долго не активничает, курсор кушает ресурсы.
Если же пользователь после некоторого простоя (на обед, например) решил продолжить листать, а на сервере курсор по таймауту умер?Hardcoin
05.08.2018 13:17Курсор на сервере живёт ноль секунд, вы невнимательно прочитали. Это просто название такое, тут "курсор" — это поле в базе, которое вечное и никакого таймаута не имеет.
VolCh
05.08.2018 15:44Тут описан клиентский курсор, Реального курсора на сервере нет, вся информация о нужных записях передаётся в щапросе, формируясь на основе предыдущего ответа. Всё сервер стейтлесс.
apapacy
05.08.2018 11:51Поле nextCursor отсутствует в response, если мы нашли меньше чем запрошенных count записей (поэтому точно уверены в отсутствии следующей страницы)
Можно ли быть в это уверенным если мы виденной статье рассматриваем динамический быстро изменяемые наборы
С этой точки зрения наименования next/previous не совсем удачные ведььфактияеси это первая и последняя записиandd3dfx Автор
05.08.2018 12:21Да, можно изменить контракт так, что nextCursor возвращать в любом случае, если при последнем запросе найдено любое ненулевое кол-во записей, сохраняя в курсоре информацию о последней записи найденного набора
apapacy
05.08.2018 12:09+1Вцелом описанная проблема с точки зрения программирования вполне понятна и проблемой не является. Это скорее проблема дизайна тк очень часто дизайнер не может отказаться от полоски с номерами страниц. А если такая полоска есть то постраничный классический вывод мы должны обеспечить.
В плане отражения бесконечной ленты встречаются действительно нетривиальные задачи. Например у вас сортировка задана не по дате добавления новостного материала а потпостоянно меняющему рейтингу. При этом вы отразить все позиции но не повторять их при прокрутке вниз если новость тоже съехала вниз по рейтингу.
Или вот другая задача. Возвращать каждому клиенту случайный набор данных, например тот же сайт по аренде жилья если отдавать всегда в одном порядке то жилье попадающее наиперуюьстраницу может иметь меньше шансов чем на второй а на третьей вообще не иметь шансов. И тоже нииоазутнктповториться
slava_k
05.08.2018 12:25В качестве курсора довольно часто используется просто метка времени.
Допустим, у нас есть список элементов (пост/новость/etc), первая порция (страница) которых первоначально отображается при заходе на страницу сайта. Как правило, у нас всегда определено стандартное окно в количестве N элементов на каждую порцию контента. Тогда при запросе на последующие порции контента достаточно передавать время (создания) последнего элемента + параметры сортировки и фильтрации, чего будет в принципе достаточно для сохранения консистентности списка элементов. Единственный накладной расход в плане организации БД — это дополнительный уникальный индекс по времени и немного логики для заполнения поля с таким временем (при создании элемента).
По аналогии, сохраняя время первого в списке элементов контента, можно с некоторой периодичностью (через сокет/просто запрос по таймауту/etc) опрашивать сервер на предмет наличия элементов, моложе того, что сейчас у клиента в качестве начала списка.
Если количество новых элементов контента превышает заданный размер в N штук, то при ответе на запрос также возвращать об этом информацию в виде времени последнего нового элемента, чтобы далее можно было загрузить все оставшиеся элементы.
dem0n3d
05.08.2018 13:02Вообще то это уже всё прекрасно описано: https://habr.com/post/301044/
И под курсорами в данном контекст обычно понимается нечто совершенно другое.
Sabubu
05.08.2018 13:58Хорошая идея, конечно, но давно уже описана в иностранных источниках:
— use-the-index-luke.com/no-offset
— blog.novatec-gmbh.de/art-pagination-offset-vs-value-based-paging
fukkit
05.08.2018 14:04Бред и провокация. Если offset по индексу, ничего лишнего не считывается, если по композитному запросу — на жирном наборе никакие клиентские приблуды не спасут.
Оптимизируйте запросы, кэшируйте запросы, настраивайте индексы, предвыборки, предсказания — вот это всё.
С точки зрения пользователя для большинства задач выборка 20 записей со случайного offset — весьма странное поведение, можно банить бота.
Если задача сложная и действительно требует извращений, на кой пёс там стейтлес? Забабахайте сервер приложения, который будет разруливать и удовлетворять за приемлемое.
lair
05.08.2018 14:23Вот вы озвучили проблему:
Если записи поступают в БД с высокой скоростью, текущее окно становится ненадежным для страничного доступа, потенциально приводя к потере данных или возвращению дубликатов.
И как вы ее решаете?
andd3dfx Автор
05.08.2018 14:57Ну ведь описано же:
— Вернув набор данных клиенту, вместе с ними вручаем ему курсор с меткой внутри на последний (в случае forward) элемент полученного клиентом набора.
— При последующем запросе клиент отправляет курсор в реквесте. Новые записи, появившиеся в БД за это время, имеют значение sequential id поля больше чем эта метка. Клиент получает данные с sequentialId > :nextCursor.sequentialId
Дубликаты исключены, в силу уникальности sequentialId и его возрастающего характера.
Потеря данных исключена в силу относительности выбранного способа нумерации, в отличие от пейджинга, где абсолютная нумерация — надо всегда отсчитать N*Размер страницы от начала, прежде чем вернуть очередную страницу, тогда как часть данных может быть уже удалена.lair
05.08.2018 15:02Новые записи, появившиеся в БД за это время, имеют значение sequential id поля больше чем эта метка.
И как вам это помогает для случая, когда у записи изменилось то поле, по которому была сортировка, и эта запись теперь раньше той, на которую смотрит "курсор"?
И это не говоря о том, что у вас в условии написано "
((fieldName = :nextCursor.fieldName AND sequentialId > :nextCursor.sequentialId) OR fieldName > :nextCursor.fieldName)", поэтому запись, у которойsequentialIdбольше того, который в курсоре, но значение в сортировочном поле меньше того, которое в курсоре, в отбор не попадут.andd3dfx Автор
05.08.2018 15:32И как вам это помогает для случая, когда у записи изменилось то поле, по которому была сортировка, и эта запись теперь раньше той, на которую смотрит «курсор»?
Если эта запись уже получена клиентом, и была изменена после этого, проблемы нет, т.к. на момент выполнения запроса ответ был дан верный. Для пояснения картинка
A 3
A 5
A 8
------ END OF FIRST RESULTS BLOCK
A 12
B 1
...
с двумя столбцами — sortingFieldName и sequentialId.
Вместе с результатами возвращаем курсор с sortingFieldName=A и sequentialId=8. Эти значения потом будут использоваться в
(fieldName = :nextCursor.fieldName AND sequentialId > :nextCursor.sequentialId)
OR fieldName > :nextCursor.fieldName
Рассмотрен случай именно с ордерингом по одному из полей, которое может быть одним и тем же для нескольких записей, в этом случае sequentialId играет вспомогательную роль, страхуя именно в тех ситуациях, когда sortingFieldName одно и то же на границе разрыва страниц. В случае отстутствия необходимости сортировки выражение упрощается до примитивного относительно sequentialId.lair
05.08.2018 15:45Если эта запись уже получена клиентом, и была изменена после этого, проблемы нет, т.к. на момент выполнения запроса ответ был дан верный.
Давайте немного поправим вашу картинку. Вот момент первого запроса:
A 7 A 8 A 9 B 4 --конец страницы, в курсоре лежит B 4 B 5 C 1
И давайте сразу для наглядности развернем ваше условие для получения следующей страницы.
(sortingField = 'B' AND sequentialId > 4) OR sortingField > 'B'
Теперь мы берем и апдейтим последнюю запись с
CнаA, получаетсяA 1. Подставляем в условие выше:('A' = 'B' AND 1 > 4) OR 'A' > 'B'. Все, вы потеряли запись.
Ладно, давайте просто добавим еще одну запись
A, получимA 10. Опять подставляем в условие выше:('A' = 'B' AND 10 > 4) OR 'A' > 'B'. Вы снова потеряли запись.andd3dfx Автор
05.08.2018 16:01Листаете вы картинки котиков (записи А), пролистали. Начали листать собачек (записи B). Будете ли вы считать, что «потеряли запись», если в набор A добавили новую запись? Да, сейчас она уже есть, но когда вы досматривали до конца набор А — вы получили все записи этого набора.
Пример с трансформацией еще не отданной клиенту записи С в запись из набора А — имеет ту же природу, с тем же моим ответом.lair
05.08.2018 16:05Будете ли вы считать, что «потеряли запись», если в набор A добавили новую запись?
На самом деле, буду, потому что иначе вы вместо решения озвученной в моем первом комменте проблемы просто говорите "нас эта проблема не волнует". Нет никакой разницы между тем, в какой набор добавили записи — в тот, который я просматриваю сейчас, или предыдущий, я хочу получить все записи.
Пример с трансформацией еще не отданной клиенту записи в запись из набора А — имеет ту же природу, с тем же моим ответом.
Но нет, потому что если в предыдущем случае еще можно было бы сослаться на некую транзакционную целостность, которая говорит мне "вы получите все данные, которые были у нас на момент первого запроса", но в этом случае нарушается и эта гарантия, потому что некоторых данных я не получу вообще.
При этом да, есть сценарии, когда это не важно — но необходимо понимать и признавать, что ваше решение этих проблем не избегает (вопреки тому, что вы изначально заявляете).
apapacy
05.08.2018 17:31Я ужеьы одном из комментов писал. Пусть набор скиоллится по быстро меняется у рейту в порядке убывания рпйта. То что пропущено в данном случае может и не играет роли но пользователя чаще раздражает другое что он может встретить ту же запись что только что видел на предыдущем экране
swelf
05.08.2018 17:58Вообще конечно интересно
-Решаем проблему смещения окна, дублирования/выпадания данных
-Смотрите, тут не сработает
-В данном случае проигнорируем выпадение данных, нам они не важны.andd3dfx Автор
05.08.2018 18:24Нет, не так. Перечитайте пример с котиками. И определитесь, клиенту важна сортировка по определенному полю? Если да, и ордеринг приоритетен — ведь он будет confused, когда ему начнут позже предлагать котиков опять, при листании вперед.
Если же вам важно именно увидеть все записи — не используйте ордеринг (у вас останется только sequentialId), тогда эта задача — подмножество уже решенной.
Вместо спора попробуйте описать устно API вашей мечты — вот, котиков уже пролистали, пошли собачки, а тут в фоне добавили еще котиков в базу. На какой странице вы ожидаете увидеть новых котиков (при дальнейшей навигации вперед)?
Вы не находите, что когда клиент начнет листать обратно (при помощи backward cursor), либо просто захочет начать серч сначала — он все же увидит все имеющиеся данные?swelf
05.08.2018 19:12Ладно, другой пример, я уже спросил выше. На первой странице статьи 100-91, пока человек их листает, появляется статья 101. Страница 2 за счет курсора покажет записи 90-81. Вернувшись на страницу 1 по курсору я увижу 11 записей 101-91? или все те же 100-91? но если так то я уже на первой странице, откуда мне знать что появилась 101?
Вместо котиков пускай будет интернет магазин/площадка с сортировкой по цене, в данный момент мы долистали по курсору до страницы 10000р и меньше, и тут появляется товар с ценой 11000, мне как покупателю, он был бы так же интересен, но в выборку не попадет.
Если записи поступают в БД с высокой скоростью, текущее окно становится ненадежным для страничного доступа, потенциально приводя к потере данных или возвращению дубликатов.
т.е. изначально поставленная абстрактная задача с высокой динамичностью базы не сильно решается таким курсором. Где-то он поможет, а где-то не является серебряной пулей.
данные теряются? теряются, но когда они теряются из-за offset/limit то надо решать проблему, а когда они теряются и курсор это тоже решить не может «ну оно на самом деле тут и не надо»
lair
05.08.2018 19:41И определитесь, клиенту важна сортировка по определенному полю? Если да, и ордеринг приоритетен — ведь он будет confused, когда ему начнут позже предлагать котиков опять, при листании вперед.
А теперь представьте, что в вашем "примере с котиками" котик в процессе чтения мутировал в собаку. Клиент не будет ли confused, что ему показали одну и ту же (по идентификатору) запись два раза? Люди-то этого могут и не заметить, а вот программные клиенты могут ожидать, что им возвращают уникальные идентификаторы.
Более того, можно легко создать такой кейс, когда объект мутировал в объект той группы, которую вы сейчас показываете, и, значит, его надо пользователю показать — но вот только он уже за границей страницы, и мы его все равно потеряли.
apapacy
05.08.2018 20:20-1Ваши примеры не покрыввют все возможные случаи. Вот вам пример с реального сайта где показывают циклические отрезки видео. Он очень популярен я правда на нем не бываю и не помню его названия. В Вашей ленте должны сказываться самые популярные фрагменты видео. Но рейтинг видео то есть основной ключ сортировки постоянно меняется. И самый негативный случай если вы пароля ленту вдруг получаете уже просмотренное видео ещё один раз
fukkit
05.08.2018 20:56Не оправдывая авторский клиентский курсор, Ваш самый страшный случай как раз легко решается на клиенте хешем айдишек, присутствующих в отображаемом списке.
apapacy
05.08.2018 22:05Как их решает в реальной жизни разработчики была статья даже возможно на хабре. Сложность ведь не в алгоритме. А в том что ресурс мегапопулярный и запросы не дожны положить сервер. Мой самый страшный случай если вы читали комментарии — необходимость отдавать рандомные наборы разным клиентам постранично и не повторяясь. И опять же не положив при этом сервер. Я же не говорю что сижу и бьюсь головой о монитора не знаю как исключить дубли. Я просто пытаюсь показать автору что его предложение не работает в более интересных случаях. А в том самом простом варианте они ни у кого не вызывают вопросов. Это как бы всем и так ясно.
Sayonji
05.08.2018 15:04SELECT * FROM items
WHERE… — apply search params
ORDER BY :sortingFieldName, :sequentialId
LIMIT :count
Если я правильно понимаю синтаксис, здесь sequentialId это переменная, т. к. перед этим токеном стоит двоеточие. Почему? Какие значения бывают у этой переменной? Это не число, такой ORDER BY был бы абсурдным. Подразумевается, что этих sequentialId полей сразу несколько? Об этом нет речи в статье, и в описании курсора нет передачи названия поля с необходимым id.andd3dfx Автор
05.08.2018 15:14Двоеточие используется чтобы показать что запрос параметризован и здесь placeholder для постановки значения извне. Про то, какую колонку использовать в качестве sequentialId сказано — это будет уже существующее поле, имеющее поведение sequential id (уникальность и возрастание с каждой новой записью) или дополнительное поле (для примера указан тип serial). Поле sequentialId — одно из полей курсора.
Sayonji
05.08.2018 15:22Не понял. Пусть у меня таблица людей с колонками (primary int id auto_increment, varchar fullname). Пусть я уже вынул часть данных и хочу следующую порцию размера 10, сортирую по fullname. Можете, пожалуйста, показать, во что преобразится шаблон запроса, данный в статье?
SELECT * FROM people
WHERE 1=1
AND ((fieldName = :nextCursor.fieldName AND sequentialId > :nextCursor.sequentialId) OR
fieldName > :nextCursor.fieldName)
ORDER BY :sortingFieldName, :sequentialId
LIMIT 10andd3dfx Автор
05.08.2018 15:51Первый запрос:
SELECT * FROM people ORDER BY fullname, id LIMIT 10;
Данные из последней возвращенной клиенту записи (fullname, id) попадают в nextCursor
Следующие запросы:
SELECT * FROM people WHERE ((fullname = :nextCursor.fullname AND id > :nextCursor.id) OR fullname > :nextCursor.fullname) ORDER BY fullname, id LIMIT 10;
Данные из последней возвращенной записи должны помещаться в очередной nextCursor и возвращаться клиенту, чтобы он мог сделать следующий requestapapacy
05.08.2018 18:19Если выделить существенное из предложенного варианта то я бы назвал то что среди полей сортировки должен присутствовать неважно на каком месте ключ не обязательно первичный. И он же должен присутствовать в условии со следующим соком больше или меньше. Кажется это вопросов не возникало и не вызывает. То что потом это передавать в base64 кодированном виде это уже такие подробности о которых не имеет смысла даже спорить. Но проблема то совсем в другом заключается. В процессе скролла могут меняться значения в сортируемых полях. И следующий запрос выдаст набор с условно говоря дублями. И как разрулить эту проблему уже задача посложнее и не такая однозначная.
apapacy
05.08.2018 20:11Или пример совсем противоположный. Когда вам как раз нельзя задавать ключ в полях сортировки если нужно иметь случайный набор строк. Поясню более подробно. Вы задаче по поиск квартир под аренду скажем в Москве по гкоклординате места или по району города. Пусть каждый такой запрос порождает сто страниц ответа. Теперь предположим 90% пользователей не пойдут дальше 10 страницы а до 100 страницы не дойдет ни один пользователь. Для того чтобы увеличить шансы всех и сделать их равными необходимо чтобы наборы выдавались случайным образом но для одного и того же клиента не содержали дублей или пропусков.
yleo
05.08.2018 22:30Андрей, ну ерунду вы написали, если разобраться.
Все проблемы давно известны и исследованы, есть масса способов их решения в зависимости от конкретных условий и ограничений. Изучать эти решения/способы лучше начиная с понимания внутренностей СУБД, так как для "больших датасетов" все методы не опирающиеся на этот фундамент становятся неприемлемыми.
При этом возникают две отдельные под-темы:
- обозначенная проблема произвольной сортировки, которую в результате допускают только для ограниченной подвыборки;
- согласованность страничных подвыборок при волатильности данных, включая проблему "распухания" БД при длительной читающей транзакции.
Miron11
05.08.2018 22:55-1Альтернатива… все эти оффсеты были с самого начала, полная туфта. Курсор, хранимый на стороне диспетчера службы запасов цифрового карго, был и будет единственным способом обращения к подаче данных порциями, в случае значительных объемов выборки данных запроса.
Вообще, дурман всех этих оффсетов появился из — за крайне востребованного расширения, получать порцию выборки данных, не прибегая к двум ограничениям, в стиле «TOP». Штука в том, что те, кто эти расширения очень хотел, не были специалистами в выборке данных, или СУБД, как таковых. Они не понимали, что эти расширения использовались в контексте работы отдела ОТК, и перепутали нужды, специфичные для отдела контроля качества с нуждами отдела создателей приложений. Мало того, многие, кого на скорую руку снарядили работать с СУБД, при очень сильно надутых щечках, и быстрых пальчиках, знали как сверстать страничку узла, или форму на Visual Basic, эдакие «чемпионы удовлетворения нужд бизнеса», вот они и довели ситуацию до того, что индустрия 10-й год ищет путей решения небольшой проблемы, и никак не может.
iproger
05.08.2018 23:41С совершенствованием железа и пониманием правильного подхода к бд статья воспринимается странно для обычного разработчика. Не хотелось бы чтобы на волне хайпа подходы с неочевидными преимуществами вошли в употребление для всего подряд.
Вот взять обычную базу и обычный сервер. После простой настройки он сможет держать десятки тысяч запросов. Уверен что профильные админы смогут ещё больше.
Не представляю сервис где возникнет проблема с offset. Это наверное что-то уровня Хабра.
В то же время до сих пор наблюдается полный разброд с api. Это не замечается на сайтах с 10 таблицами и rest, но превращается в боль со сколько-нибудь большими проектами.
Хорошо что начали появляться такие вещи как graph api и swagger. Вот это реальное достижение.andd3dfx Автор
05.08.2018 23:49Вы пробовали замерять, как меняется время, которое тратится на запрос вида
"...ваш запрос..." offset N limit 10
увеличивая N? А именно такие запросы к БД генерируют фреймворки, поддерживающие педжинацию.
В случае же с курсором offset всегда = 0apapacy
06.08.2018 00:19Я пробовал на посгресе. Потому что как уже говорил, на старых версиях и на Винде это работало несколько минут на больших наборах. Сейчас это если запрос простой не виляет так существенно. Все же описанный Вами вариант это не альнернатива offset и дело тутне в програмирование а в изнаально дизайне приложения. Давайте посмотрим конкретно на сайт Хабра. Есть номера страниц и стрелки Туда/Сюда (которые в данном случае работают как текущая страница + 1 и текуща страницы -1) Так вот убрать оффсет это означает убрать страницы прежде всего в дизайне и отсавить только стрелки Туда/Сюда. И при этом если сортировка постов идет в порядке убывания даты публикации коорая не меняется, т о задача становится тривиальной. Она даже не требует ни статей ни обсуждений.
Но вопрос в том готовы ли сейчас дизайнеры, собственники, пользователи вот этого данного конкретного сайта (Хабра) сломать сложившийся стереотип и оставить только две стрелочки Туда/Сюда и полностью убрать футкр с номерами страниц? Возмодно при этом нужно будет добавить что-то вробе каледнаря чтобы модно бвло проматривать статью по датам или еще сдлеать какую-то альтенрнативу.
Но если оставить элеимент дизайна с номерами страниц без оффсета туту меня навскидку не получается что-то придумиать другое нежели оффсет. И никакие закладки на первую и последнюю запись набора тут не помогут.
VolCh
06.08.2018 00:33Классическая пагинация для меня имеет проблемы прежде всего с юзабилити. Например нажимаю ссылку второй страницы на хабре и вижу там половину первой, а то и вообще то, что появилось пока первую читал.
apapacy
06.08.2018 00:47«Бесконечные» ленты типа твиттера или фейсбука также имеют свои неудобства. Например если хочешь найти давний твит (кстати некоторое слишком давние так и не нашел) Но туть имеет место привычка. Пользователи как бы их не раздражало что на следующей станице видят половину предыдущей страницы всеже привыкли к тому что могут интуитивно и быстро отмотать один-два дня и найти то что хотели. Если убрать пагинацию то нужно думать (не программисту — дизайнеру) как сделать чтобы пользователь мог так же легко искать нужный материал. Это же очень опасный вриант когда меняешь что-то в дизайне. Может быть как и взлет та и падение. например недавно читал (возмодно даже на Хабре) что по мнению маркетологов Фейсбука из всзлет начался когда они внедрили кнопочку с лайками. Все кинулись лайкать посты и Фейсбук взлетел.
VolCh
06.08.2018 08:05Как по мне, то клиентские курсоры не исключают пагинацию. Они могут реализовать другое её поведение, но необязательно совершенно иной способ навигации типа бесконечных лент. Собственно и ленты на оффсетах или номерах страниц можно делать. Судя по всему на андроид приложении Хабра именно так и сделано: вроде бесконеная лента по поведению, но иногда посты задваиваются при загрузке следующей порции :)
fukkit
06.08.2018 08:20Имхо, это проблема дырявых абстракций.
Разработчик имеет множество множеств записей в бд, срез которых на конкретно заданный момент времени может быть представлен в виде списка.
В пользовательском интерфейсе же часть контракта относительно времени никак не заявлена. Отсюда ноги всех проблем с "потеряными","повторяющимися","смещающимися" записями.
Пользователю сложно понять (а интерфейс скрывает информацию о том), что на каждый запрос приложение возвращает кусок разных списков.
Таким образом, если вдруг, зачем-то, кто-то втемяшил в интерфейс линейку с номерами страниц, следует крепко подумать, какой именно контракт мы предложили пользователю. И если это таки "случайный доступ к страницам некоего фиксированного списка", придется этот список формировать и хранить целиком (предвыборка).
В иных случаях следует треснуть дизайнера по очумелым ручкам и подумать о замене способа продвижения по (отсутствующему) списку: стрелочки, ползунки, скроллы — тут наши явные бро.VolCh
06.08.2018 10:47В какой-то мере да, дырявые абстракции. Но, по-моему, не в чистом виде, а дырявые абстрации UI «программистов для программистов» переросли уже довольно давно в «у нас так принято». Некоторые современные (ну, может немного отставшие от тренда бесконечных лент) UI/UX-дизайнеры лепят оффсетную пагинацию в интерфейсы просто потому что иных способов не знают, потому что выросли на ней.Ну или сами знают, но свою пользовательскую ЦА относят к тем, кому трудно будет разобраться с иными подходами.
Beholder
06.08.2018 00:03Хоть бы упомянули, что это сделано по мотивам вот этой статьи: "Guys, we’re doing pagination wrong…"
andd3dfx Автор
06.08.2018 00:20Не только этой, но и некоторых других статей. Ок, добавил ссылку, спасибо
Mikluho
06.08.2018 07:49Вот уж и правда, написали бы сначала, какую конкретно проблему решаете и на каких ресурсах.
Потому как и в качестве универсального АПИ ваше решение не годится (о чём уже написали), да и польза от него при работе с MSSQL или Oracle весьма сомнительна. На «больших» СУБД, как уже было замечено, правильные индексы и запросы позволяют движку очень эффективно отбрасывать лишние записи.
И да, на совсем больших датасетах уже приходится строить предвыборки и даже хранить их каким-либо образом, иначе быстро апи не сделать.
vintage
07.08.2018 15:29Вы таким образом не решили исходную проблему, корень которой в изменчивости списка во времени и относительно тяжёлом поисковом запросе на каждую страницу. Подробнее я разбирал тут: https://habr.com/post/413133
Golem765
Что делать в случае не-численных айди записей?
andd3dfx Автор
Как сказано в статье — можно использовать дополнительное sequential id поле (типа serial к примеру), либо, как указали в комментариях — поле имеющее такой смысл, например метки времени