Пейджинг страниц в соцсетях

Для пагинации страниц используют смещение (OFFSET) и курсорную пагинацию (по ID), как более быструю. Тем не менее есть ещё один малоизвестный вид пагинации по меткам страниц (MARKS). Она является разновидностью курсорной пагинации, но использует не идентификатор, а ряд полей перечисленных в ORDER BY SQL-запроса.

Всем известен LIMIT в Mysql, OFFSET LIMIT в Postgres и TOP в MSSQL. Именно через них и делают пейджинг страниц. Однако чтобы сместиться к странице с большим смещением, условию (WHERE) придётся поработать и sql-запрос начнёт тормозить.

Давайте бросим взгляд на проблему пагинации по смещению на примере:

SELECT product.id
FROM product
WHERE product.price > 3000
AND product.brand="Love Republic"
AND EXISTS(SELECT 1 
           FROM stock JOIN shop 
           ON stock.shop_id=shop.id
           WHERE stock.product_id=product.id
           AND shop.city_code=7800000000
           LIMIT 1
          )
ORDER BY product.innovation DESC
LIMIT 1000000, 10

Допустим клиент интернет-магазина решил прокрутить каталог товаров сразу на середину. В этом случае придётся применить условия в WHERE к миллионам записей, пока мы дойдём до нужных.

Есть ли способ не использовать OFFSET, а сразу выбрать нужные записи по индексу? Такой способ есть. Правда он требует пожертвовать номерами страниц и использовать вместо них значения полей по которым будет происходить сортировка. Так вместо запроса GET /products/? page=100000&order=innovation, будет запрос GET /products/?order=innovation&page=2021-12-12,5000.

Этот способ называется "Пейджингом через метки начальной записи страницы". Он является расширением курсорной пагинации, когда переход к началу страницы осуществляется не по идентификатору, а по нескольким полям.

SELECT product.id
FROM product
WHERE 
product.innovation < "2021-12-12"
OR product.innovation="2021-12-12"
AND product.id >= 5000
...
ORDER BY product.innovation DESC,
product.id ASC
LIMIT 10

Этот запрос аналогичен предыдущему. Троеточием я сократил условия оставшиеся неизменными. Смещение же было заменено на дополнительные условия: по индексу innovation тут же можно переместиться к товарам нужной страницы. Так как несколько товаров могли появится в одну и ту же дату, то добавлена сортировка по уникальному идентификатору.

Если же сортировка будет осуществляться по нескольким полям, то для каждого поля в сортировке вначале проверяем, что это поле больше своего значения (если направление сортировки ASC и меньше для DESC), а затем через OR, если же поле равно значению, указывающему на страницу, то проверяем следующее поле и так далее. Например, для ORDER BY product.innovation DESC, product.price, product.id:

(product.innovation < 2021-12-12
OR product.innovation = 2021-12-12 AND product.price > 610
OR product.innovation = 2021-12-12 AND product.price = 610 AND product.id >= 5000)

Чтобы автоматизировать построение sql-запроса можно использовать функцию, вроде функции make_query_for_order на perl:

use strict;
use warnings;

# Оборачивает стрки в одинарные кавычки, а числа пропускает
sub quote {
	my ($value) = @_;
  use bytes;
	$value =~ /^-?\d+(\.\d+)?$/? $value: do {
		$value =~ s/[\\']/\\$&/g;
		"'$value'"
	}
}

# Создаёт части sql-запроса для сортировки по условию, а не распространённому лимиту
sub make_query_for_order(@) {
    my ($order, $next) = @_;
 
    my @orders = split /\s*,\s*/, $order;
    my @order_direct;
    my @order_sel = map { my $x=$_; push @order_direct, $x =~ s/\s+(asc|desc)$//i? uc $1: "ASC"; $x } @orders;
    
    my $select = @order_sel==1? $order_sel[0]: join "", "concat(", join(",',',", @order_sel), ")";
 
    return $select, 1 if $next eq "";
    
    my @next = map quote($_), split /,/, $next;
    my @op = map { /^A/? ">": "<" } @order_direct; 
    
    # id -> id >= next[0]
    # id, update -> id > next[0] OR id = next[0] and 
    my @whr;
    for(my $i=0; $i<@orders; $i++) {
        my @opr;
        for(my $j=0; $j<=$i; $j++) {
            my $eq = $j == $#orders? "=": "";
            if($j != $i) {
                push @opr, "$order_sel[$j] = $next[$j]";
            } elsif($j != $#orders) {
                push @opr, "$order_sel[$j] $op[$j] $next[$j]";
            } else {
                push @opr, "$order_sel[$j] $op[$j]= $next[$j]";
            }
        }
        push @whr, join " AND ", @opr;
    }
    my $where = join "\nOR ", map "$_", @whr;
    
    return $select, "($where)", \@order_sel;
}


$\ = "\n";

use Data::Dumper;

print Dumper make_query_for_order "product.innovation DESC, product.price, product.id", "";
print Dumper make_query_for_order "product.innovation DESC, product.price, product.id", "2021-12-12,610,5000";

Функция make_query_for_order принимает два параметра:

1. $order (строка): список столбцов из ORDER BY.

2. $next (строка): параметр page, то есть - значения для столбцов сортировки с которых будет начинаться следующая страница через запятую.

Если $next пуст (нужна первая страница), то будет возвращён массив из двух элементов - для вставки в SELECT и WHERE sql-запроса:

$VAR1 = 'concat(product.innovation,\',\',product.price,\',\',product.id)';
$VAR2 = 1;

То есть sql-запрос будет таким:

SELECT product.id, 
  concat(product.innovation,product.price,product.id) as next
FROM product
WHERE 
1
...
ORDER BY product.innovation DESC,
product.price ASC,
product.id ASC
LIMIT 11

Тут LIMIT 11, а не 10, так как мы выбираем так же следующую строку после страницы и используем next как метку следующей страницы. Допустим она будет 2021-12-12,610,5000, как во втором вызове нашей функции:

$VAR1 = 'concat(product.innovation,\',\',product.price,\',\',product.id)';
$VAR2 = '(product.innovation < 2021-12-12
OR product.innovation = 2021-12-12 AND product.price > 610
OR product.innovation = 2021-12-12 AND product.price = 610 AND product.id >= 5000)';
$VAR3 = [
          'product.innovation',
          'product.price',
          'product.id'
        ];

И мы получаем запрос для страницы с 2021-12-12,610,5000:

SELECT product.id, 
  concat(product.innovation,product.price,product.id) as next
FROM product
WHERE 
(product.innovation < 2021-12-12
OR product.innovation = 2021-12-12 AND product.price > 610
OR product.innovation = 2021-12-12 AND product.price = 610 AND product.id >= 5000)
...
ORDER BY product.innovation DESC,
product.price ASC,
product.id ASC
LIMIT 11

Выводы

Такая схема меток начальной записи страницы, вместо нумерации страниц, подойдёт для последовательных листингов. Таких как новостной листинг в VK, когда нужно прокручивать страницы последовательно. Переместиться к какой-то далёкой странице можно по карте значений (если используются даты, то - календарю). Зато эти неудобства компенсируются мгновенным перемещением к нужной странице по индексу.

Ссылки

1. Пейджинг на метках начальной записи страницы в листинге книг / https://kosmobook.ru/?next=2022-01-30+00:00:00,1567030.

2. Листинг новостей Вконтакте / https://vk.com/feed.

3. Статья о медленном OFFSET, но не раскрывающая решение / https://habr.com/ru/company/ruvds/blog/513766/.