Статьи

Быстрое разбиение на страницы SQL с наборами ключей, продолжение

Август 13, 2018

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

Пагинация набора ключей наиболее полезна для ленивой загрузки «следующей страницы», гораздо больше, чем, например, для прямого перехода на страницу 235. Хорошим примером, где это полезно, являются социальные сети, такие как Twitter или Facebook с их потоками контента. Когда вы достигнете нижней части страницы, вы просто хотите «следующую пару твитов». Не твиты по смещению 3564.

Если ваши страницы разбиты на страницы, остаются «разумно неизменными» во время разбивки на страницы, вы можете даже выполнить классическую разбивку на OFFSET, предварительно рассчитав (и кэшировав) все границы страницы за один раз. Представьте, у вас есть эти данные (я использую PostgreSQL для примера):

create table t(
  id int,
  value int
);
 
insert into t (id, value)
select id, random() * 100
from generate_series(1, 1000) x(id);

Наши данные содержат 1000 записей со случайными значениями от 0 до 99. Теперь давайте просмотрим эти данные в порядке возрастания, упорядоченного VALUEи затем по ID. Если бы мы хотели попасть на страницу 6 с размерами страницы 5 с нумерацией страниц OFFSET, мы бы написали:

select id, value
from t
order by value, id
limit 5
offset 25

Это тогда даст что-то вроде

|  ID | VALUE |
|-----|-------|
| 640 |     2 |
| 776 |     2 |
| 815 |     2 |
| 947 |     2 |
|  37 |     3 |

Смотрите также этот SQLFiddle

OFFSET эмуляция пагинации с кэшированными границами страницы

The above can be emulated using keyset pagination if we know the page boundaries of every page. In other words, in order to jump to page 6 without an actual OFFSET, we’d have to know the value of the record immediately preceding {"ID":640,"VALUE":2}. Or better, let’s just figure out all the page boundaries with the following query:

select
  t.id,
  t.value,
  case row_number()
       over(order by t.value, t.id) % 5
    when 0 then 1
    else 0
  end page_boundary
from t
order by t.value, t.id

The above query yields

|   ID | VALUE | PAGE_BOUNDARY |
|------|-------|---------------|
|  ... |   ... |           ... |
|  474 |     2 |             0 |
|  533 |     2 |             1 | <-- Before page 6
|  640 |     2 |             0 |
|  776 |     2 |             0 |
|  815 |     2 |             0 |
|  947 |     2 |             0 |
|   37 |     3 |             1 | <-- Last on page 6
|  287 |     3 |             0 |
|  450 |     3 |             0 |
|  ... |   ... |           ... |

See also this SQL Fiddle

As you can see, the record just before {"ID":640,"VALUE":2} is {"ID":533,"VALUE":2}, which is the page boundary that we need to jump to if we want to go to page 6. Page 7 then starts with the record just after {"ID":37,"VALUE":3}.

The above query selects too much data, of course. We’re only interested in those records where PAGE_BOUNDARY = 1. Besides, why not calculate the page numbers already in the database with yet another call to ROW_NUMBER(). Let’s write:

select
  x.value,
  x.id,
  row_number()
    over(order by x.value, x.id) + 1 page_number
from (
  select
    t.id,
    t.value,
    case row_number()
         over(order by t.value, t.id) % 5
      when 0 then 1
      else 0
    end page_boundary
  from t
  order by t.value, t.id
) x
where x.page_boundary = 1

This will then yield:

| VALUE |  ID | PAGE_NUMBER |
|-------|-----|-------------|
|     0 | 786 |           2 |
|     1 | 250 |           3 |
|     1 | 959 |           4 |
|     2 | 229 |           5 |
|     2 | 533 |           6 | <-- Before page 6
|     3 |  37 |           7 |
|     3 | 768 |           8 |

See also this SQLFiddle.

We can now jump to page 6 with this simple query:

select id, value
from t
where (value, id) > (2, 533)
order by value, id
limit 5

… which will yield the same as the previous OFFSET query:

|  ID | VALUE |
|-----|-------|
| 640 |     2 |
| 776 |     2 |
| 815 |     2 |
| 947 |     2 |
|  37 |     3 |

See also this SQLFiddle

If you’re planning on using the upcoming jOOQ 3.3, the same query can be achieved with the following SEEK syntax:

DSL.using(configuration)
   .select(T.ID, T.VALUE)
   .from(T)
   .orderBy(T.VALUE, T.ID)
   .seek(2, 533)
   .limit(5);

The advantage of this is that you don’t have to write out the SEEK predicate explicitly, which adds readability and typesafety, specifically if your ORDER BY clause is a little more complex

If window functions aren’t available

The above queries make use of window functions, which aren’t available in all databases, unfortunately. If you’re using MySQL, for instance, you will have to use a different mechanism to find the PAGE_BOUNDARY. One such example us using a scalar subquery:

select
  t.id,
  t.value,
  case (
      select count(*)
      from t t2
      where (t2.value, t2.id) <= (t.value, t.id)
    ) % 5
    when 0 then 1
    else 0
  end page_boundary
from t
order by t.value, t.id

See also this SQLFiddle

Such a scalar subquery might be quite costly if your database performs poor query optimisation. Your best bet would be to measure things and decide whether caching page boundaries to be able to apply keyset pagination is really faster than classic OFFSET paging.

Conclusion

As explained in our previous blog post about keyset pagination, this technique can bring great performance improvements as pagination can be achieved in constant time, leveraging existing indexes. It is most useful when the underlying data is very stable (no records added / removed while paginating), or when pagination “stability” is desired even if records are added / removed.

Keyset pagination, or the “seek method”, should be part of every SQL developer’s tool set.

40
Share: