Мне сообщили, что при листании списка одна и та же карточка показалась дважды. В логах ничего, запрос обычный. Полдня я потратил на поиск ошибки в приложении. Ошибка в самом способе листать, а драмы с конкурентностью для неё не нужно: хватает одной вставки.
Стенд это таблица на миллион строк с индексом по ключу сортировки, страницы по 20. Первая страница возвращает идентификаторы с 1 по 20. Дальше приходит 1 строка, которая по порядку встаёт раньше всех, а это обычный случай, когда кто-то задним числом добавляет запись. И дальше запрашивается вторая страница обычным способом.
Страница через OFFSET начинается с 20, то есть со строки, которую читатель уже видел. Строка 40 не появляется вообще. Страница по ключу возвращает с 21 по 40. Виноватого нет: запрос с OFFSET честно отдаёт строки с 21 по 40 текущего порядка, а текущий порядок на 1 строку длиннее в начале, чем был, когда рисовалась первая страница.
Именно это и съело мои полдня. Я искал гонку, слой кеширования, неверную сортировку. Искать нечего. У самой схемы есть свойство: всё, что вставили или удалили впереди твоей позиции, сдвигает всё, что позади. Читатель, который листает медленно, видит повторы после вставок и молча пропускает строки после удалений.
Скорость, про которую обычно и говорят вместо этого
В начале списка запрос с OFFSET оказывается быстрее: 1.483 миллисекунды против 1.774. Это стоит сказать вслух, потому что именно поэтому никто ничего не меняет: на тех страницах, которые люди реально открывают, простой вариант выигрывает.
На глубине 100000 он стоит уже 10.8 миллисекунды, а на 900000 стоит 69.5, при том что запрос по ключу так и не сдвинулся с 1.5. План объясняет это одной строкой: чтобы вернуть 20 строк, база читает 900020 и выбрасывает всё, что идёт до смещения. Запрос по ключу читает ровно 20.
Обход всей таблицы делает форму очевидной. Страницами по 20 их выходит 50000. Версия с OFFSET на каждой следующей читает на 20 строк больше, чем на предыдущей. В сумме это около 25 миллиардов прочитанных строк на таблице в миллион. Версия по ключу читает по 20 строк на страницу и заканчивает на миллионе. Это арифметика, а не замер. Ровно та же арифметика, которую план показал на одной странице: цена страницы равна её позиции.
Выгрузка данных устроена именно так. Она проходит все страницы по разу, вежливо, циклом, который кто-то написал за полдня. И превращает обход таблицы в квадратичный, причём ни одна строка того кода не выглядит неправильной.
Чего я не проверял
Листанию по ключу нужен уникальный доводчик. У меня это первичный ключ рядом с отметкой времени. Без него строки с одинаковым значением сортировки лягут по обе стороны границы страницы. Этого я не мерил, хотя жду, что повтор воспроизведётся другим способом.
Зеркало этой ошибки, то есть удаление впереди позиции, из-за которого строка молча пропадёт, я не прогонял, а рассудил. И у листания по ключу есть настоящая цена: перейти сразу на 57 страницу нельзя, только вперёд и назад. Значит любой интерфейс с нумерованными страницами сам просит ту схему, которая ошибается в счёте.
Узкое утверждение про то, что чинить первым. Аргумент про скорость касается глубин, до которых большинство приложений не доходит. Аргумент про корректность работает на второй странице.