Автор оригинала: Vlad Mihalcea.
Вступление
В этой статье мы рассмотрим, что такое метод поиска SQL или разбиение на страницы набора ключей и почему его следует учитывать при навигации по большим наборам результатов.
Цель разбиения на страницы состоит в том, чтобы избежать извлечения больших объемов данных, поскольку пользовательский интерфейс имеет ограниченное окно просмотра, которое можно использовать для отображения данных.
СМЕЩЕНИЕ Разбиения На Страницы
Прежде чем обсуждать разбиение набора ключей на страницы, давайте посмотрим, как работает разбиение на страницы со смещением по умолчанию в SQL.
Хотя системы реляционных баз данных уже давно предоставляют конкретные способы ограничения набора результатов запроса, начиная с SQL:2008, существует стандартный синтаксис разбиения на страницы.
Таким образом, запрос TOP-N , который ограничивает количество записей данного результирующего набора, может использовать директиву FETCH ТОЛЬКО ДЛЯ ПЕРВЫХ N СТРОК , как показано в следующем примере:
SELECT id FROM post ORDER BY created_on DESC FETCH FIRST 50 ROWS ONLY
И запрос NEXT-N, который пропускает первые M записей и извлекает следующие N записей, выглядит следующим образом:
SELECT id FROM post ORDER BY created_on DESC OFFSET 150 ROWS FETCH NEXT 50 ROWS ONLY
Индексирование со СМЕЩЕНИЕМ по Страницам
Поскольку для разбиения на страницы требуется предложение ORDER BY , чтобы гарантировать согласованный порядок сортировки, обычно индексируют критерии сортировки.
В нашем случае нам нужно создать следующий индекс в столбце created_on :
CREATE INDEX idx_post_created_on ON post (created_on DESC)
При выполнении запроса TOP-N мы видим, что используется idx_post_created_on и сканируется только 50 записей:
SELECT id
FROM post
ORDER BY created_on DESC
FETCH FIRST 50 ROWS ONLY
Limit (cost=0.28..2.51 rows=50 width=16)
(actual time=0.013..0.022 rows=50 loops=1)
-> Index Scan using idx_post_created_on on post p
(cost=0.28..223.28 rows=5000 width=16)
(actual time=0.013..0.019 rows=50 loops=1)
Planning time: 0.113 ms
Execution time: 0.055 ms
Для второй страницы мы видим, что idx_post_created_on должен сканировать 100 записей, потому что ему нужно пропустить первые 50 строк, содержащихся на первой странице, чтобы загрузить следующие 50 записей, которые необходимо вернуть этим запросом:
SELECT id
FROM post
ORDER BY created_on DESC
OFFSET 50 ROWS
FETCH NEXT 50 ROWS ONLY
Limit (cost=2.51..4.74 rows=50 width=16)
(actual time=0.032..0.044 rows=50 loops=1)
-> Index Scan using idx_post_created_on on post p
(cost=0.28..223.28 rows=5000 width=16)
(actual time=0.022..0.040 rows=100 loops=1)
Planning time: 0.198 ms
Execution time: 0.071 ms
Чем дальше мы отойдем от первой страницы, тем больше записей потребуется отсканировать с помощью индекса idx_post_created_on , чтобы пропустить записи, указанные в предложении OFFSET :
SELECT id
FROM post
ORDER BY created_on DESC
OFFSET 4950 ROWS
FETCH NEXT 50 ROWS ONLY
Limit (cost=221.05..223.28 rows=50 width=16)
(actual time=1.154..1.166 rows=50 loops=1)
-> Index Scan using idx_post_created_on on post p
(cost=0.28..223.28 rows=5000 width=16)
(actual time=0.079..1.033 rows=5000 loops=1)
Planning time: 1.629 ms
Execution time: 1.190 ms
Обратите внимание, что сканирование всего индекса idx_post_created_on занимает в 20 раз больше времени, чем сканирование одной страницы, как это было при первоначальном запросе TOP-N.
Метод поиска SQL или Разбиение набора ключей на страницы
Чтобы справиться с этой проблемой сканирования индекса, присущей смещенной разбивке на страницы, мы можем использовать метод поиска или метод разбиения на страницы набора ключей.
Запрос на разбиение на страницы набора ключей TOP-N выглядит следующим образом:
SELECT id, created_on FROM post ORDER BY created_on DESC, id DESC FETCH FIRST 50 ROWS ONLY
Обратите внимание, что нам необходимо включить идентификатор в предложение ORDER BY, поскольку значения столбца created_on не являются уникальными. Следовательно, нам нужно будет передать как последний обработанный created_on , так и идентификатор при загрузке следующей страницы. Поэтому на этот раз проекция запроса также должна загрузить столбец created_on .
Запрос Next-N будет использовать ранее обработанные значения столбцов created_on и id для поиска следующей страницы записей, которые необходимо загрузить.
SELECT id, created_on
FROM post
WHERE
(created_on, id) < ('2019-10-02 21:00:00.0', 4951)
ORDER BY created_on DESC, id DESC
FETCH FIRST 50 ROWS ONLY
(created_on, идентификатор) < ('2019-10-02 21:00:00.0', 4951) выражение значения строки эквивалентно:
created_on < '2019-10-02 21:00:00.0' OR
(
(created_on = '2019-10-02 21:00:00.0') AND
(id < 4951)
)
Метод поиска SQL или Индексирование набора ключей по страницам
Поскольку метод поиска использует как created_on , так и id столбцы в предложении ORDER BY , мы можем создать индекс idx_post_created_on для обоих этих двух столбцов:
CREATE INDEX idx_post_created_on ON post (created_on DESC, id DESC)
Теперь при выполнении запроса на разбиение на страницы набора ключей TOP-N мы видим, что он использует индекс idx_post_created_on , и сканируется всего 50 записей:
SELECT id, created_on
FROM post
ORDER BY created_on DESC, id DESC
FETCH FIRST 50 ROWS ONLY
Limit (cost=0.28..1.91 rows=50 width=16)
(actual time=0.104..0.110 rows=50 loops=1)
-> Index Only Scan using idx_post_created_on_id on post
(cost=0.28..163.28 rows=5000 width=16)
(actual time=0.102..0.107 rows=50 loops=1)
Heap Fetches: 0
Planning Time: 0.882 ms
Execution Time: 0.129 ms
Запрос на разбиение на страницы следующего набора ключей также использует индекс idx_post_created_on , и, в отличие от разбиения на страницы со смещением, на этот раз сканируется только 50 строк:
SELECT id, created_on
FROM post
WHERE
(created_on, id) < ('2019-10-02 21:00:00.0', 4951)
ORDER BY created_on DESC, id DESC
FETCH FIRST 50 ROWS ONLY
Limit (cost=0.28..3.40 rows=50 width=32)
(actual time=0.029..0.063 rows=50 loops=1)
-> Index Scan using idx_post_created_on_id on post
(cost=0.28..308.58 rows=4950 width=32)
(actual time=0.027..0.057 rows=50 loops=1)
Index Cond: (
created_on <=
'2020-04-24 06:00:00'::timestamp without time zone
)
Filter: (
ROW(created_on, (id)::numeric) <
ROW('2020-04-24 06:00:00'::timestamp without time zone, '4951'::numeric)
)
Rows Removed by Filter: 2
Heap Fetches: 52
Planning Time: 0.806 ms
Execution Time: 0.158 ms
И загрузка последней страницы также будет быстрой, так как для разбиения набора ключей на страницы не нужно сканировать весь индекс, чтобы пропустить записи СМЕЩЕНИЯ:
SELECT id, created_on
FROM post
WHERE
(created_on, id) < ('2019-10-03 02:00:00.0', 51)
ORDER BY created_on DESC, id DESC
FETCH FIRST 50 ROWS ONLY
Limit (cost=48.82..48.83 rows=1 width=16)
(actual time=0.168..0.175 rows=50 loops=1)
-> Sort (cost=48.82..48.83 rows=1 width=16)
(actual time=0.166..0.170 rows=50 loops=1)
Sort Key: created_on DESC, id DESC
Sort Method: quicksort Memory: 27kB
-> Bitmap Heap Scan on post
(cost=4.76..48.81 rows=1 width=16)
(actual time=0.071..0.085 rows=50 loops=1)
Recheck Cond: (created_on <= '2019-10-03 02:00:00'::timestamp without time zone)
Filter: (
(created_on < '2019-10-03 02:00:00'::timestamp without time zone) OR
(
(created_on = '2019-10-03 02:00:00'::timestamp without time zone) AND
(id < '51'::bigint)
)
)
Rows Removed by Filter: 2
Heap Blocks: exact=1
-> Bitmap Index Scan on idx_post_created_on_id
(cost=0.00..4.75 rows=63 width=0)
(actual time=0.061..0.062 rows=52 loops=1)
Index Cond: (created_on <= '2019-10-03 02:00:00'::timestamp without time zone)
Planning Time: 0.676 ms
Execution Time: 0.279 ms
Круто, правда?
Вывод
Разбиение набора ключей на страницы позволяет использовать индекс для поиска первой записи любой страницы, по которой необходимо перейти, и по этой причине SQL-запрос может сканировать меньше записей, чем при использовании разбиения на страницы со смещением по умолчанию.