@the_unbridled_goose18 мая 2016 в 13:00

Пять способов пагинации в Postgres, от базовых до диковинных

13 мин

108K

PostgreSQL *

Перевод

+28

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

@the_unbridled_goose 18 мая 2016 в 13:19

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

@ZOXEXIVO 18 мая 2016 в 14:03

Раньше думал, что только в MongoDB offset тормозит

@Shannon 18 мая 2016 в 14:04

Если цель просто сделать оптимизацию пагинации, избавиться от оверхеда limit offset, а не изучить возможности postgesql, то достаточно использовать JOIN
Вместо:

SELECT * FROM test_table ORDER BY id LIMIT 100000, 30

Написать:

SELECT * FROM test_table JOIN (SELECT id FROM test_table ORDER BY id LIMIT 100000, 30) as b ON b.id = test_table.id

@Throwable 18 мая 2016 в 14:57

Можете объяснить откуда берутся такие результаты? Что за движок и какие планы выполнения обоих запросов?

@Shannon 18 мая 2016 в 16:29

В общем немного упрощенно, но смысл примерно такой:
Допустим у нас есть нужные (простые или составные) индексы по полям для сортировки

Для первого случая подстава в том, что LIMIT работает не до, а после того как была произведена выборка. Допустим, было бы условие «WHERE id > 100000 AND id < 100030», использовался бы индекс, и в лапы LIMIT уже попали бы только 30 записей (и лимит был бы уже не нужен, но такой простой подход для пагинации обычно не удобен)

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

Для случая с JOIN в запросе всего лишь «SELECT id», то есть выборка id будет производится не из таблицы, а из оптимизированного индекса, и даже если будет какое-то условие, то мы всё равно в результате получим оптимизированную выборку индекса, в которой более менее точно знаем на какой позиции будет находится 100000 запись, поэтому просто перескакиваем туда и берем 30 записей

Соответственно, сначала мы выбрали нужные id для пагинации используя индекс, а потом просто заджойнили нужные id

@Throwable 19 мая 2016 в 08:55

Вообще говоря, странное поведение для планировщика. Обычно запрашиваемые поля никак влияют на план выполнения запроса, а только поля, участвующие в предикатах, сортировках, джоинах, etc… Цель планирования — получить keyset, по которому можно будет сделать fetch — достать все остальные данные из таблицы. То есть по-сути, планировщих должен всегда неявно трансформировать первый запрос во второй.

@kshvakov 19 мая 2016 в 11:01

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

@AxCx 18 мая 2016 в 16:38

habrahabr.ru/post/217521

@kshvakov 18 мая 2016 в 16:38

С join он использует index only scan, что даёт выигрыш на выборку. Больше сложностей с получением общего числа строк в выборке, иногда помогает создание дополнительной таблицы со счетчиками и параметрами, тогда получение общего количества это просто сумма по параметрам, а вот с выборкой по подстроке уже сложности

@LAV45 19 мая 2016 в 05:20

~ $ psql --version
psql (PostgreSQL) 9.5.2

=# EXPLAIN ANALYZE SELECT * FROM medley LIMIT 30 OFFSET 5000000;
Limit (cost=91666.88..91667.43 rows=30 width=37) (actual time=501.497..501.502 rows=30 loops=1)
-> Seq Scan on medley (cost=0.00..183334.29 rows=10000029 width=37) (actual time=0.006..341.246 rows=5000030 loops=1)
Planning time: 0.053 ms
Execution time: 501.523 ms

=# EXPLAIN ANALYZE SELECT * FROM medley t1 JOIN (SELECT n FROM medley ORDER BY n LIMIT 30 OFFSET 5000000) as t2 ON t2.n = t1.n;
Nested Loop (cost=129844.71..130099.23 rows=30 width=41) (actual time=600.520..600.580 rows=30 loops=1)
-> Limit (cost=129844.28..129845.06 rows=30 width=4) (actual time=600.506..600.507 rows=30 loops=1)
-> Index Only Scan using medley_n_idx on medley (cost=0.43..259688.87 rows=10000029 width=4) (actual time=0.013..446.107 rows=5000030 loops=1)
Heap Fetches: 0
-> Index Scan using medley_n_idx on medley t1 (cost=0.43..8.45 rows=1 width=37) (actual time=0.001..0.001 rows=1 loops=30)
Index Cond: (n = medley.n)
Planning time: 0.222 ms
Execution time: 600.607 ms

@Shannon 19 мая 2016 в 07:18

В первом запросе забыли ORDER BY n, поэтому seq scan (результат хоть и быстрее, но выборка будет не та, которая нужна)

https://habrahabr.ru/post/301044/#comment_9615682

@nightwolf_du 18 мая 2016 в 16:38

Извините, не подскажете, как вы этого добились? Протестировал ваш пример,
pg 9.3, debian
16GB таблица, primary key на id. Примерно 71кк строк. Нагрузка равномерная, при 100к вне зависимости от смещения 20-21 секунда оба запроса.
При 200к 38-40. Значимой разницы в производительности не замечено.
Строки большие, в кэш базы/диска не влезают.
Результат значительно при повторном прогоне не менялся.
Планы:
1) IndexScan -> Limit
2) IndexOnlyScan -> limit ->NestedLoop
IndexScan->

@Shannon 18 мая 2016 в 17:41

На последнем postgresql для 10кк строк результаты такие:

postgres=# EXPLAIN ANALYZE SELECT * FROM medley ORDER BY n OFFSET 500000 LIMIT 30;
                                                               QUERY PLAN                                                               
-------------------------------------
 Limit  (cost=17258.34..17259.37 rows=30 width=37) (actual time=202.280..202.292 rows=30 loops=1)
   ->  Index Scan using n_idx on medley  (cost=0.43..345158.43 rows=10000000 width=37) 
        (actual time=0.034..176.281 rows=500030 loops=1)
 Planning time: 0.123 ms
 Execution time: 202.323 ms
(4 rows)

postgres=# EXPLAIN ANALYZE SELECT * FROM medley JOIN 
                   (SELECT n FROM medley ORDER BY n OFFSET 500000 LIMIT 30) 
                   as b ON b.n = medley.n;
                                                                        QUERY PLAN                                                                         
------------------------------------------
 Nested Loop  (cost=12985.27..13239.79 rows=30 width=41) (actual time=132.953..133.150 rows=30 loops=1)
   ->  Limit  (cost=12984.83..12985.61 rows=30 width=4) 
        (actual time=132.897..132.912 rows=30 loops=1)
         ->  Index Only Scan using n_idx on medley medley_1  (cost=0.43..259688.43 rows=10000000 width=4) 
              (actual time=0.032..107.005 rows=500030 loops=1)
               Heap Fetches: 0
   ->  Index Scan using n_idx on medley  (cost=0.43..8.45 rows=1 width=37) 
         (actual time=0.007..0.007 rows=1 loops=30)
         Index Cond: (n = medley_1.n)
 Planning time: 0.426 ms
 Execution time: 133.200 ms
(8 rows)

То есть по сути разница хоть и есть, но всё равно результат далек от того, что хотелось бы

@Arkham 20 мая 2016 в 01:29

Есть ещё один трюк, попробуйте его:

WITH temp_rows AS (
        SELECT n 
        FROM medley 
        ORDER BY n OFFSET 500000 
        LIMIT 30
)

SELECT * FROM medley WHERE medley.n = ANY(ARRAY(SELECT n FROM temp_rows)::uuid[])

@Arkham 20 мая 2016 в 01:52

Забыл добавить, вместо «uuid[]» должен быть тип который соответствует массиву типа колонки «n».

Вот результат для моей таблицы, с ~500к записей.

Чистый order: 5338.266 ms

EXPLAIN ANALYZE

SELECT *

FROM product

ORDER BY guid 

OFFSET 200000

LIMIT 10



"Limit (cost=53081.04..53083.70 rows=10 width=427) (actual time=5338.193..5338.218 rows=10 loops=1)"

" -> Index Scan using "pk-product" on product (cost=0.42..107495.58 rows=405026 width=427) (actual time=0.026..5201.130 rows=200010 loops=1)"

"Planning time: 0.679 ms"

"Execution time: 5338.266 ms"

Order + Join: 6361.272 ms

EXPLAIN ANALYZE

SELECT *

FROM product as a

JOIN (SELECT guid FROM product ORDER BY guid OFFSET 200000 LIMIT 30) as b ON b.guid = a.guid;



"Hash Join (cost=6114.90..35463.31 rows=30 width=443) (actual time=246.895..6361.194 rows=30 loops=1)"

" Hash Cond: (a.guid = product.guid)"

" -> Seq Scan on product a (cost=0.00..27829.26 rows=405026 width=427) (actual time=0.004..5820.195 rows=405026 loops=1)"

" -> Hash (cost=6114.53..6114.53 rows=30 width=16) (actual time=243.653..243.653 rows=30 loops=1)"

" Buckets: 1024 Batches: 1 Memory Usage: 2kB"

" -> Limit (cost=6113.31..6114.23 rows=30 width=16) (actual time=243.567..243.618 rows=30 loops=1)"

" -> Index Only Scan using "pk-product" on product (cost=0.42..12379.81 rows=405026 width=16) (actual time=0.011..129.707 rows=200030 loops=1)"

" Heap Fetches: 0"

"Planning time: 0.181 ms"

"Execution time: 6361.272 ms"

Order + CTE: 243.386 ms

EXPLAIN ANALYZE

WITH temp_rows AS (

 SELECT guid 

 FROM product 

 ORDER BY guid OFFSET 200000 

 LIMIT 30

)



SELECT * FROM product WHERE guid = ANY(ARRAY(SELECT guid FROM temp_rows)::uuid[])



"Index Scan using "pk-product" on product (cost=6115.26..6199.24 rows=10 width=427) (actual time=243.227..243.329 rows=30 loops=1)"

" Index Cond: (guid = ANY ($1))"

" CTE temp_rows"

" -> Limit (cost=6113.31..6114.23 rows=30 width=16) (actual time=243.037..243.089 rows=30 loops=1)"

" -> Index Only Scan using "pk-product" on product product_1 (cost=0.42..12379.81 rows=405026 width=16) (actual time=0.015..130.086 rows=200030 loops=1)"

" Heap Fetches: 0"

" InitPlan 2 (returns $1)"

" -> CTE Scan on temp_rows (cost=0.00..0.60 rows=30 width=16) (actual time=243.041..243.133 rows=30 loops=1)"

"Planning time: 0.154 ms"

"Execution time: 243.386 ms"

@Shannon 20 мая 2016 в 08:28

Для Int на той же таблице по сути разницы нет:
Просто OFFSET: Execution time: 202.323 ms
Вариант с WITH: Execution time: 138.158 ms
Вариант с JOIN: Execution time: 133.200 ms

explain

postgres=# EXPLAIN ANALYZE WITH temp_rows AS (
        SELECT n 
        FROM medley 
        ORDER BY n OFFSET 500000 
        LIMIT 30
)
SELECT * FROM medley WHERE medley.n = ANY(ARRAY(SELECT n FROM temp_rows)::Int[]);
                                                                         QUERY PLAN                                                                          
-------------------------------------------------------------------------------------------------------------------------------------------------------------
 Index Scan using n_idx on medley  (cost=12986.44..13034.53 rows=10 width=38) (actual time=138.009..138.107 rows=30 loops=1)
   Index Cond: (n = ANY ($1))
   CTE temp_rows
     ->  Limit  (cost=12984.63..12985.41 rows=30 width=4) (actual time=137.945..137.953 rows=30 loops=1)
           ->  Index Only Scan using n_idx on medley medley_1  (cost=0.43..259694.04 rows=10000374 width=4) (actual time=0.038..110.982 rows=500030 loops=1)
                 Heap Fetches: 0
   InitPlan 2 (returns $1)
     ->  CTE Scan on temp_rows  (cost=0.00..0.60 rows=30 width=4) (actual time=137.950..137.968 rows=30 loops=1)
 Planning time: 0.219 ms
 Execution time: 138.158 ms
(10 rows)

Решил так же проверить, как этот вариант будет вести для более частых малых OFFFSET (5000, например), тут уже вариант с WITH стал сильно отставать

Результаты для OFFSET 5000 LIMIT 30:
Просто OFFSET: Execution time: 3.380 ms
Вариант с WITH: Execution time: 8.379 ms
Вариант с JOIN: Execution time: 1.788 ms

@the_unbridled_goose 20 мая 2016 в 08:46

У меня с более сложных подзапросом внутри WITH, с сортировкой по двум полям результаты следующие:

Обычный limit-offset:

cost=725946.11..725946.11 rows=1 width=1147) (actual time=1554.900..1554.915 rows=50 loops=1

JOIN:

cost=725954.67..725962.71 rows=1 width=2041) (actual time=1200.102..1201.138 rows=50 loops=1

WITH:

cost=1654277.66..1654362.74 rows=10 width=2041) (actual time=2729.149..2729.608 rows=50 loops=1

@the_unbridled_goose 20 мая 2016 в 09:08

В общем при различных вариациях одного и того же запроса выигрывает вариант с джоином. With стабильно на втором месте. Но, прошу прощения, запрос с with возвращает неотсортированный список?

@Arkham 20 мая 2016 в 09:11

А можно запрос с эксплейном with'а?

@the_unbridled_goose 20 мая 2016 в 10:01

Это проблематично, так как тестировалось на боевом контуре. В таком виде недостаточно?

Index Scan (cost=1310619.54..1310704.63 rows=10 width=2041) (actual time=1906.651..1907.164 rows=50 loops=1)
  CTE temp_rows
    ->  Limit (cost=1310617.85..1310617.97 rows=50 width=32) (actual time=1906.502..1906.517 rows=50 loops=1)
          ->  Sort (cost=1310542.85..1311220.85 rows=271201 width=32) (actual time=1899.475..1904.427 rows=30050 loops=1)
                ->  Bitmap Heap Scan (cost=399032.63..1289016.16 rows=271201 width=32) (actual time=821.209..1723.774 rows=218436 loops=1)
                      ->  Bitmap Index Scan (cost=0.00..398964.83 rows=305711 width=0) (actual time=705.200..705.200 rows=320530 loops=1)
  InitPlan 2 (returns $1)
    ->  CTE Scan on temp_rows  (cost=0.00..1.00 rows=50 width=16) (actual time=1906.506..1906.544 rows=50 loops=1)
Planning time: 0.966 ms
Execution time: 1911.184 ms

@Arkham 20 мая 2016 в 14:09

Да, тут уже дальше оптимизировать проблематично:
1. Bitmap Heap Scan — постгресу пришлось перепроверять версионность строк, это нормально для таблиц в которых часто происходят update/delete — если же таблица не из таких, то надо проверить когда был последний vacuum/analyze таблицы.
2. Sort — совсем грошёвые cost'ы, максимум что можно сделать — проверить сортировки в индексах, в том ли порядке они, как в запросе.

P.S. Можно попробовать избавиться от Bitmap Index Scan — разбив на несколько CTE, что бы получить Index Only Scan'ы.

@the_unbridled_goose 20 мая 2016 в 14:18

Там вообще все очень непросто, увы. Но спасибо за совет.

Изменения там регулярные, кроме того, долгие хождения по вектору, тяжелому вектору. С вакуумом и статистикой особых проблем нет. Все регулярно, по мере необходимости. Помимо автовакуума, само собой.
Обязательно проверю еще раз что там с индексами.

@the_unbridled_goose 20 мая 2016 в 16:00

Да, индекса не было нужного.

Было:

(cost=1365076.05..1365161.13 rows=10 width=2501) (actual time=2078.275..2078.763 rows=50 loops=1)

Стало:

(cost=2589.09..2674.17 rows=10 width=2501) (actual time=59.720..60.222 rows=50 loops=1)

И сам explain:

Index Scan (cost=2589.09..2674.17 rows=10 width=2501) (actual time=59.720..60.222 rows=50 loops=1)
    ->  Limit  (cost=1294.04..2587.51 rows=50 width=32) (actual time=23.419..59.575 rows=50 loops=1)
          ->  Index Scan (cost=0.56..11409104.75 rows=441025 width=32) (actual time=0.579..59.549 rows=100 loops=1)
    ->  CTE Scan on temp_rows  (cost=0.00..1.00 rows=50 width=16) (actual time=23.423..59.661 rows=50 loops=1)
Planning time: 0.647 ms
Execution time: 60.287 ms

О — оптимизация)

@Arkham 21 мая 2016 в 02:19

Отличный результат!

@Shannon 18 мая 2016 в 19:24

Проверил на mysql для таблицы 6кк строк, разница примерно такая же

@Shannon 18 мая 2016 в 19:29

Всмысле хоть с join намного легче запрос, но это просто потому что без join намного тяжелее чем тут

@Shannon 18 мая 2016 в 20:52

Окончательный вердикт. Эта информация немного преувеличена. Этот трюк работает редко и только с mysql, так как в индексе хранится видимость, и можно легко перепрыгнуть. В psql видимость хранится по другому, поэтому подобный трюк с JOIN не сработает так же хорошо, как для mysql, но при этом обычный LIMIT OFFSET будет оптимизирован и сработает намного лучше, чем в mysql.

При этом добавляя условие в JOIN (без чего пагинация редко обходится), и добавляя составной индекс, в обоих случаях результат становится схожим и для mysql и для postgresql

Разница в том, что для psql лучше не использовать join, а для mysql без join тяжеловато выходит

@franzose 18 мая 2016 в 23:05

На MySQL подобный выигрыш по производительности тоже можно получить?

@kshvakov 19 мая 2016 в 04:50

В MySql подобный выигрыш ощутимие и стабильнее по причине того, что даже при index only scan постгрес может «бегать» на диск что в explain будет показано в heap fetches, тут все дело в visibility map и такие «фокусы» в постгресе будут работать не на всех таблицах/данных особенно у тех кто «сознательно отключает autovacuum», хотя, стоит сказать, что с «глубокими» limit/offset постгрес справляется вполне достойно

@Tatikoma 18 мая 2016 в 18:43

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

@asm0dey 18 мая 2016 в 20:31

Ну, учитывая что в БД хранятся не массивы, а гомогенные мультимножества — это логично для любой БД, как мне кажется.

@kshvakov 19 мая 2016 в 04:55

Крайне не рекомендуется использовать LIMIT без ORDER BY т.к. это может помешать в выборе правильного плана оптимизатором. В отличии от MySql у постгреса первичный ключ не кластер и он не «выравнивает» данные по индексу постоянно, отсюда и «неожиданный» результат т.к. при последовательном вычитывании данные будут расположены в порядке изменения (mvcc)

@kuzin_mv 19 мая 2016 в 05:20

Хорошая презентация, с более сложным примером для случая «Пагинация по набору ключей» www.slideshare.net/MarkusWinand/p2d2-pagination-done-the-postgresql-way.

Зарегистрируйтесь на Хабре, чтобы оставить комментарий