В данной статье мы выясним почему нельзя использовать LIMIT и OFFSET для реализации пагинации и чем их заменить.
При написании этой статьи я использовал PostgreSQL, поэтому часть SQL-запросов будет работать только для нее (напр, запрос с использованием generate_series для наполнения тестовой таблицы данными). Однако, все описанные ниже способы пагинации должны работать в любой базе данных.
Давайте предположим, что у нас есть чат с 1 млн сообщений.
CREATE TABLE messages (id serial primary key, body text);
INSERT INTO messages (body) SELECT md5(random()::text) FROM generate_series(1,1000000);Теперь нам нужно реализовать пагинацию, чтобы у пользователя загружались сообщения по 100 штук по мере прокрутки чата. Это можно реализовать несколькими способами.
Использование LIMIT и OFFSET
Самый популярный способ для реализации пагинации – это использование LIMIT и OFFSET.
Давайте попробуем получить первые 100 сообщений:
SELECT * FROM messages ORDER BY id ASC LIMIT 100; Limit (cost=0.42..3.86 rows=100 width=37) (actual time=0.059..2.336 rows=100 loops=1)
-> Index Scan using messages_pkey on messages (cost=0.42..34317.43 rows=1000000 width=37) (actual time=0.046..0.794 rows=100 loops=1)
Planning Time: 0.072 ms
Execution Time: 3.107 msКак мы видим, запрос выполнился за 3 мс. В плане запроса видно, что просканировалось только 100 строк (Index Scan -> actual time -> rows=100). Для выполнения запроса использовался B-tree индекс, который PostgreSQL создает автоматически для всех primary key колонок.
Давайте получим теперь следующие 100 сообщений:
SELECT * FROM messages ORDER BY id ASC LIMIT 100 OFFSET 100; Limit (cost=3.86..7.29 rows=100 width=37) (actual time=1.578..4.078 rows=100 loops=1)
-> Index Scan using messages_pkey on messages (cost=0.42..34317.43 rows=1000000 width=37) (actual time=0.043..1.677 rows=200 loops=1)
Planning Time: 0.051 ms
Execution Time: 5.032 msНа этот раз запрос выполнялся дольше (5 мс). Если посмотреть на план запроса, то можно заметить, что произошло сканирование уже 200 строк.
Предположим, что пользователь пролистал 100000 сообщений (или автоматически прокрутилось до 100000-го сообщения при нажатии на ссылку, что вполне реалистично) и загружает следующие 100 сообщений:
SELECT * FROM messages ORDER BY id ASC LIMIT 100 OFFSET 100000; Limit (cost=3432.12..3435.56 rows=100 width=37) (actual time=1377.502..1379.512 rows=100 loops=1)
-> Index Scan using messages_pkey on messages (cost=0.42..34317.43 rows=1000000 width=37) (actual time=0.046..712.494 rows=100100 loops=1)
Planning Time: 0.127 ms
Execution Time: 1380.311 msЗапрос выполнялся 1.3 сек. Количество просмотренных строк – 100100.
Проблема данного подхода в том, что строки всегда сканируются с начала. В начале мы находим первую строку, сканируем и пропускаем OFFSET строк, а затем сканируем и возвращаем LIMIT последующих строк. Чем больше OFFSET, тем больше строк нам нужно просканировать, тем дольше выполняется запрос. В итоге каждая последующая страница будет загружаться все дольше и дольше, т.к. для выполнения запроса всегда будет сканироваться OFFSET + LIMIT строк.
На практике используются более сложные запросы, для которых уже при небольшом OFFSET скорость выполнения становится неприемлемой. В качестве решения, можно поставить ограничение на максимальный OFFSET (напр, 1000), но в этом случае пользователь не сможет просмотреть больше, чем OFFSET + LIMIT записей.
Давайте рассмотрим еще одну проблему. Получим на этот раз последние 5 сообщений.
SELECT * FROM messages ORDER BY id DESC LIMIT 5; id | body
---------+----------------------------------
1000000 | b35ebb4db40731d03b8b025cfe7adc19
999999 | acfd591d18f38692f884d3afc6d5c979
999998 | b22069d7485b2b4f8bed51a724718fee
999997 | 17d76b8d7030485413c7458d15d0339d
999996 | 3ff735c087295f3dc9b4c7323cda9457Предположим, что пользователь начал прокручивать этот список и в этот момент кто-то написал новое сообщение:
INSERT INTO messages (body) VALUES (md5(random()::text));и после этого пользователь загружает следующие 5 сообщений:
SELECT * FROM messages ORDER BY id DESC LIMIT 5 OFFSET 5; id | body
--------+----------------------------------
999996 | 3ff735c087295f3dc9b4c7323cda9457
999995 | e41cac0085cacf36e3fa1a3ad845a37d
999994 | 068cbaadc0ab60f99e2284739c1061c8
999993 | c3c53e27b7765ab7aa97268b3ca419e5
999992 | d4d361538e8d1fe89316209c1d5185eaВ итоге пользователь дважды получил одно и то же сообщение (id=999996).
Использование LIMIT и WHERE
Проблема предыдущего подхода состоит в том, что сканирование строк всегда начинается с самого начала. Чтобы решить эту проблему, нам нужно начинать сканирование сразу с нужной строки.
Давайте получим первые 5 сообщений:
SELECT * FROM messages ORDER BY id ASC LIMIT 5; id | body
----+----------------------------------
1 | 7ca7a3f16457f5ec49ebf0cb6fabb52f
2 | 30d67067325190ee3b922793efd7641e
3 | 3e7b041658a1e5e29021c23498e9c870
4 | 985ab7304175eb25a8b577df96baaa1e
5 | a86c097cf8f341e859077f37cc65583bТеперь, при получении следующей страницы со стороны пользователя будет отправляться не номер страницы, а id последней строки. В нашем примере последняя строка имеет id=5.
Запрашиваем следующие 5 сообщений:
SELECT * FROM messages WHERE id > 5 ORDER BY id ASC LIMIT 5; id | body
----+----------------------------------
6 | fba0989cb6b59f81f8b0fc9844710005
7 | 8eacebda19093d998d4a386c0f5e37d7
8 | 456c1d71717ec23e47cf56a490aa77a6
9 | 5c521635cd0ac8610178e4c5626b49d9
10 | d7c4f563b55444499a16c5e675e5af66Пагинация работает. Теперь давайте получим 100 сообщений, которые следуют после 100000-го.
SELECT * FROM messages WHERE id > 100000 ORDER BY id ASC LIMIT 100; Limit (cost=0.42..4.11 rows=100 width=37) (actual time=0.090..2.790 rows=100 loops=1)
-> Index Scan using messages_pkey on messages (cost=0.42..33203.93 rows=901743 width=37) (actual time=0.076..1.085 rows=100 loops=1)
Index Cond: (id > 100000)
Planning Time: 0.076 ms
Execution Time: 3.723 msЗапрос выполнился за 3 мс (примерно столько же занимает получение первой страницы). При использовании OFFSET такой же запрос выполнился за 1,3 сек. В плане запроса видно, что просканировалось только 100 строк (Index Scan -> actual time -> rows=100), вместо 100100 строк при использовании OFFSET.
Т.к. у колонки с id используется b-tree индекс, то первым делом происходит быстрый поиск 100000-й строки, а затем сканируется 100 следующих строк (это происходит за счет того, что в b-tree индексе все листья дерева [в них находятся ссылки на строки] связаны двунаправленным списком).
Теперь рассмотрим проблему, которая у нас возникала при добавлении новой строки. Давайте получим последние 5 сообщений:
SELECT * FROM messages ORDER BY id DESC LIMIT 5; id | body
---------+----------------------------------
1000001 | 1fcaa624f42bc1851516b6f8f4e790cd
1000000 | b35ebb4db40731d03b8b025cfe7adc19
999999 | acfd591d18f38692f884d3afc6d5c979
999998 | b22069d7485b2b4f8bed51a724718fee
999997 | 17d76b8d7030485413c7458d15d0339dдобавим новое сообщение:
INSERT INTO messages (body) VALUES (md5(random()::text));и загрузим следующую страницу:
SELECT * FROM messages WHERE id < 999997 ORDER BY id DESC LIMIT 5; id | body
--------+----------------------------------
999996 | 3ff735c087295f3dc9b4c7323cda9457
999995 | e41cac0085cacf36e3fa1a3ad845a37d
999994 | 068cbaadc0ab60f99e2284739c1061c8
999993 | c3c53e27b7765ab7aa97268b3ca419e5
999992 | d4d361538e8d1fe89316209c1d5185eaНа этот раз строку с id=999997 мы получили только 1 раз.
Сортировка по не уникальным колонкам
Давайте создадим таблицу с товарами и наполним ее:
CREATE TABLE products (id serial primary key, name text, price int);
INSERT INTO products (name, price)
SELECT md5(random()::text), floor(random() * 1000) + 1
FROM generate_series(1,1000000);Предположим, что мы показываем пользователю товары по возрастанию цены. Цена товаров колеблется от 1 до 1000.
В начале посмотрим первые 5 товаров:
SELECT * FROM products ORDER BY price ASC LIMIT 5; id | name | price
------+----------------------------------+-------
3950 | e2af7265e17668e3b325608f3e2a5577 | 1
70 | 3e2cd54660711330325abba843964780 | 1
1561 | cf7deecf27ccfa0bcfff11862f86ac0f | 1
3049 | d3158b4405d05aa8df6d6982eb1ee58e | 1
4046 | 4d0fa7bbfbba435be18922e872e811a4 | 1Но как загрузить следующие 5 товаров? Если сделать так:
SELECT * FROM products WHERE price > 1 ORDER BY price ASC LIMIT 5; id | name | price
------+----------------------------------+-------
2093 | c11ba2e7237336d3e27021ffc4afcbfd | 2
3556 | 4ccd277e9d3fe1493dfa3d451cbe1791 | 2
770 | f5f6661726ae76c377f818fc1a2ea643 | 2
898 | e9b5f5e0eddb4e29c713b30ce8ca001c | 2
4243 | 60fd9a3c1fed481fad896ee3e0858c53 | 2то в этом случае мы пропустим 984 другие строки, у которых price = 1, т.к. общее количество таких строк 989.
SELECT COUNT(*) FROM products WHERE price = 1; -- 989Чтобы решить эту проблему, необходимо сортировать также по какой-нибудь колонке с уникальными значениями, которые поддерживаются b-tree индексом (или другим индексом, который поддерживает операторы больше/меньше). Например, по колонке id.
Создадим новый индекс по 2 колонкам: price и id. Этот индекс нужен, чтобы быстро выполнять запросы, в которых в where используются эти 2 колонки.
CREATE INDEX products_price_id_idx ON products (price, id);Получим первую страницу:
SELECT * FROM products ORDER BY price ASC, id ASC LIMIT 5; id | name | price
------+----------------------------------+-------
70 | 3e2cd54660711330325abba843964780 | 1
1561 | cf7deecf27ccfa0bcfff11862f86ac0f | 1
3049 | d3158b4405d05aa8df6d6982eb1ee58e | 1
3950 | e2af7265e17668e3b325608f3e2a5577 | 1
4046 | 4d0fa7bbfbba435be18922e872e811a4 | 1Последняя строка имеет price = 1 и id = 4046.
Теперь получим следующую страницу:
-- Запрос для PostgreSQL
SELECT * FROM products
WHERE (price, id) > (1, 4046)
ORDER BY price ASC, id ASC
LIMIT 5;
-- Запрос для любых БД
SELECT * FROM products
WHERE price > 1 OR (price = 1 AND id > 4046)
ORDER BY price ASC, id ASC
LIMIT 5; id | name | price
-------+----------------------------------+-------
5820 | 967db515852d6463f845749194f1a6ae | 1
8388 | 2b11088f71918aae6920b6665d3c3544 | 1
8821 | 489e2bfd77ba1f0fd5c37a50dc848e72 | 1
9679 | fbc4f4e0ab73ec8bb05418a44f2a5917 | 1
12252 | 89ab1cf6496e37cb4efa575e5d52d6aa | 1Первые 10 строк выглядят следующие образом:
SELECT * FROM products ORDER BY price ASC, id ASC LIMIT 10; id | name | price
-------+----------------------------------+-------
70 | 3e2cd54660711330325abba843964780 | 1
1561 | cf7deecf27ccfa0bcfff11862f86ac0f | 1
3049 | d3158b4405d05aa8df6d6982eb1ee58e | 1
3950 | e2af7265e17668e3b325608f3e2a5577 | 1
4046 | 4d0fa7bbfbba435be18922e872e811a4 | 1
5820 | 967db515852d6463f845749194f1a6ae | 1
8388 | 2b11088f71918aae6920b6665d3c3544 | 1
8821 | 489e2bfd77ba1f0fd5c37a50dc848e72 | 1
9679 | fbc4f4e0ab73ec8bb05418a44f2a5917 | 1
12252 | 89ab1cf6496e37cb4efa575e5d52d6aa | 1Пагинация работает корректно.
Давайте посмотрим план и скорость выполнения запроса для получения 5 последующих строк после 100000-й. В начале найдем 100000-ю строку:
SELECT * FROM products ORDER BY price ASC, id ASC LIMIT 1 OFFSET 100000; id | name | price
-------+----------------------------------+-------
69113 | 17f845ab71b7cccc46333c2a5c33122d | 101Посмотрим план следующего запроса:
SELECT * FROM products
WHERE (price, id) > (101, 69113)
ORDER BY price ASC, id ASC
LIMIT 5; Limit (cost=0.42..0.78 rows=5 width=41) (actual time=0.060..0.163 rows=5 loops=1)
-> Index Scan using products_price_id_idx on products (cost=0.42..62991.89 rows=899098 width=41) (actual time=0.046..0.083 rows=5 loops=1)
Index Cond: (ROW(price, id) > ROW(101, 69113))
Planning Time: 0.070 ms
Execution Time: 0.249 msЗапрос выполнился за 0.2 мс. Было просканировано 5 строк.
Использование LIMIT + WHERE для пагинации позволяет быстро загружать любую страницу с результатами за одно и то же время, т.к. всегда сканируется только LIMIT строк. Напротив, выборка LIMIT + OFFSET строк с каждой последующей страницей выполняется медленнее, т.к. чем больше OFFSET, тем больше строк нужно просканировать.
Шпаргалка
/* Пагинация с сортировкой по уникальной колонке */
CREATE TABLE messages (id serial primary key, body text);
-- Первые 5 сообщений
SELECT * FROM messages ORDER BY id ASC LIMIT 5;
-- Следующие 5 сообщений
-- (последнее полученное сообщение имеет id = 5)
SELECT * FROM messages WHERE id > 5 ORDER BY id ASC LIMIT 5;/* Пагинация с сортировкой по не уникальной колонке */
CREATE TABLE products (id serial primary key, name text, price int);
CREATE INDEX products_price_id_idx ON products (price, id);
-- Первые 5 товаров
SELECT * FROM products ORDER BY price ASC, id ASC LIMIT 5;
-- Следующие 5 товаров (для PostgreSQL)
-- (последнее полученное сообщение имеет price = 1, id = 4046)
SELECT * FROM products
WHERE (price, id) > (1, 4046)
ORDER BY price ASC, id ASC
LIMIT 5;
-- Следующие 5 товаров (для любой БД)
-- (последнее полученное сообщение имеет price = 1, id = 4046)
SELECT * FROM products
WHERE price > 1 OR (price = 1 AND id > 4046)
ORDER BY price ASC, id ASC
LIMIT 5;