По различным причинам в web-интерфейсах оказывается предпочтительным ограничение максимального количества данных, отображаемых одновременно, которое достигается через постраничную разбивку этих данных. Этими причинами являются и ограниченная скорость передачи данных через интернет, и скорость отображения в браузере этих данных (которые зачастую представляются в виде достаточно сложной разметки). Но при достижении определенных объемов данных, критичной с точки зрения производительности, становится и сама выборка нужных данных из базы данных. Вопросам оптимизации постраничного вывода данных на стороне БД и будет посвящена эта статья. В ней рассматривается задача постраничного вывода больших объемов данных на примере PostgreSQL. Большая часть написанного справедлива также и для MySQL и для любой реляционной базы. Только нужно учитывать, что в MySQL планировщик запросов несколько слабее.
Для примера создадим табличку, содержащую id и некоторое числовое значение.
CREATE TABLE big_table ( id serial PRIMARY KEY, "value" double precision )
Теперь добавим туда немного данных.
INSERT INTO big_table (value) SELECT random()*100 FROM generate_series(1,1000000)
Предположим, что мы хотим постранично выводить оттуда данные упорядоченные по столбцу value:
SELECT * FROM big_table ORDER BY value LIMIT 20
Посмотрим, какой получился план:
Limit (cost=42015.64..42015.69 rows=20 width=12) (actual time=4047.578..4047.687 rows=20 loops=1)
-> Sort (cost=42015.64..44515.64 rows=1000000 width=12) (actual time=4047.571..4047.607 rows=20 loops=1)
Sort Key: value
Sort Method: top-N heapsort Memory: 17kB
-> Seq Scan on big_table (cost=0.00..15406.00 rows=1000000 width=12) (actual time=0.037..2022.398 rows=1000000 loops=1)
Total runtime: 4047.778 ms
Получилось не очень быстро. Поскольку мы сортируем по столбцу value, то нам может помочь индекс по нему.
CREATE INDEX big_table_value_idx ON big_table(value);
Посмотрим, что произойдет с нашим планом теперь.
Limit (cost=0.00..0.95 rows=20 width=12) (actual time=0.029..0.166 rows=20 loops=1) -> Index Scan using big_table_value_idx on big_table (cost=0.00..47603.17 rows=1000000 width=12) (actual time=0.023..0.087 rows=20 loops=1) Total runtime: 0.240 ms
Стало куда лучше. Но по мере листания
SELECT * FROM big_table ORDER BY value LIMIT 20 OFFSET 100
результат ухудшется
Limit (cost=4.76..5.71 rows=20 width=12) (actual time=0.583..0.716 rows=20 loops=1) -> Index Scan using big_table_value_idx on big_table (cost=0.00..47603.17 rows=1000000 width=12) (actual time=0.022..0.443 rows=120 loops=1) Total runtime: 0.785 ms
А когда дойдём по середины
SELECT * FROM big_table ORDER BY value LIMIT 20 OFFSET 500000
то будет примерно также как и без индекса
Limit (cost=23801.59..23802.54 rows=20 width=12) (actual time=4397.397..4397.591 rows=20 loops=1) -> Index Scan using big_table_value_idx on big_table (cost=0.00..47603.17 rows=1000000 width=12) (actual time=0.022..3409.592 rows=500020 loops=1) Total runtime: 4397.673 ms
Почему так происходит? Дело в том, что когда PostgreSQL оптимизирует запрос с конструкцией вида "LIMIT n OFFSET m" с помощью индекса то ему приходится искать по индексу первые n+m записей а из них первые m пропускать. При больших значениях m это оказывается не лучше, чем сканировать всю таблицу. Выход один - заменить OFFSET на WHERE. Предположим, что мы получили первую страницу данных следующего вида:
id | value --------+---------------------- 880439 | 1.2572854757309e-006 860116 | 6.20726495981216e-005 699877 | 7.89295881986618e-005 345070 | 0.000164657831192017 614704 | 0.000217463821172714 276126 | 0.000326475128531456 225441 | 0.000362470746040344 159893 | 0.000384915620088577 288870 | 0.000771228224039078 660139 | 0.000779842957854271 605310 | 0.000936398282647133 928812 | 0.000983802601695061 276966 | 0.0010006595402956 778343 | 0.0010328833013773 908325 | 0.00132769346237183 463928 | 0.00134636647999287 550207 | 0.00150990672409534 248902 | 0.00154105946421623 556308 | 0.00168662518262863 329455 | 0.00169374980032444 (20 rows)
Мы видим, что последняя из выбранных строк имеет значение 0.00169374980032444 в столбце value. Теперь, можно было бы заменить конструкцию "OFFSET 20" на "WHERE value > 0.00169374980032444".
SELECT * FROM big_table WHERE value > 0.00169374980032444 ORDER BY value LIMIT 20
План в этом случае будет такой:
Limit (cost=0.00..1.00 rows=20 width=12) (actual time=0.047..0.193 rows=20 loops=1)
-> Index Scan using big_table_value_idx on big_table (cost=0.00..50101.42 rows=999900 width=12) (actual time=0.040..0.113 rows=20 loops=1)
Index Cond: (value > 0.00169374980032444::double precision)
Total runtime: 0.269 ms
Но что если значение 0.00169374980032444 не уникально, тогда мы пропустим больше строк, чем нужно. Чтобы это учесть нужно сделать, чтобы упорядочивание было однозначным, например добавить id к ORDER BY: "ORDER BY value, id". Тогда можно будет использовать следующую конструкцию: "WHERE value = 0.00169374980032444 AND id > 329455 OR value > 0.00169374980032444". К счастью, она имеет более удобную запись: "WHERE (value, id) > (0.00169374980032444, 329455)". Т.к. мы упорядочиваем по паре (value, id) то для БД будет более удобно использовать следующий индекс:
CREATE INDEX big_table_value_id_idx ON big_table(value, id);
И запрос на получение второй страницы будет иметь следующий вид:
SELECT * FROM big_table WHERE (value, id) > (0.00169374980032444, 329455) ORDER BY value, id LIMIT 20
и план:
Limit (cost=0.00..1.09 rows=20 width=12) (actual time=0.041..0.178 rows=20 loops=1)
-> Index Scan using big_table_value_id_idx on big_table (cost=0.00..54533.99 rows=999900 width=12) (actual time=0.035..0.099 rows=20 loops=1)
Index Cond: (ROW(value, id) > ROW(0.00169374980032444::double precision, 329455))
Total runtime: 0.249 ms
Как видно, при таком подходе листание будет происходить очень быстро. Однако пролистывание сразу на много страниц вперёд остаётся ресурсоёмкой задачей, поэтому интерфейс высоконагруженного приложения лучше организовать таким образом, чтобы пользователь не мог запросить сразу страницу №10000.
Помимо непосредственно листания, нужно также выводить пользователю общее число строк в таблице. К сожалению, выполнение COUNT потребует сканирования всех строк (даже в простых запросах вида "SELECT COUNT(*) FROM table", если говорить о базах с полноценной реализацией MVCC). Спасает в этом случае одно - выводить не точное число строк, а приблизительное. Его можно оценить с помощью EXPLAIN.
EXPLAIN SELECT * FROM big_table
Seq Scan on big_table (cost=0.00..15406.00 rows=1000000 width=12)
Полученный план можно распарсить regexp'ом и получить из него оценку количества строк. (В PostgreSQL 9.0 обещают возможность вывода плана в форматах JSON, XML и YAML, что устранит необходимость в специальном парсинге плана)
Примечение 1.
Предложенный способ листания лучше чем OFFSET в плане конкурентного доступа. Если кто-то добавил или удалил строку из предыдущей страницы, то не возникнет ситуация что он увидит одну строку дважды или пропустит строку (если, конечно, изменения не затронут столбцы по которым идёт упорядочивание).
Примечание 2
Предложенный способ листания подходит и в тех случаях, когда не нужно выводить всю таблицу целиком. Например, результаты следующего запроса
SELECT * FROM big_table WHERE id % 2 = 0 ORDER BY value, id
тоже можно пролистывать этим способом. Будет происходить аналогичное сканирование индекса, просто строки не удовлетворяющие условию, будут отфильтровываться. Также этот способ будет работать с многостолбцовыми индексами, если по первым столбцам индекса будет идти проверка на равенство, а по последним - сортировка.