Рецепт: keyset-пагинация в SQL

CREATE TABLE orders (
    id         bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
    created_at timestamptz    NOT NULL DEFAULT now(),
    customer   text           NOT NULL,
    total      numeric(12, 2) NOT NULL
);

-- 1 млн заказов: по три на каждую минуту, порядок id не совпадает с порядком времени
INSERT INTO orders (created_at, customer, total)
SELECT timestamptz '2026-01-01 00:00:00+00' + ((g::bigint * 7919) % 333334) * interval '1 minute',
       'customer-' || (g % 5000),
       100 + (g % 90000) / 3.0
FROM generate_series(1, 1000000) AS g;

ANALYZE orders;

$ psql -d shop -f sql/02-offset.sql
                                                     QUERY PLAN                                                      
---------------------------------------------------------------------------------------------------------------------
 Limit (actual time=191.505..191.520 rows=20 loops=1)
   Buffers: shared hit=503855
   ->  Index Scan Backward using orders_created_at_id_idx on orders (actual time=0.014..181.588 rows=500020 loops=1)
         Buffers: shared hit=503855
 Planning:
   Buffers: shared hit=103
 Planning Time: 0.427 ms
 Execution Time: 191.548 ms

-- один B-tree покрывает и ORDER BY created_at DESC, id DESC (обратный проход), и ASC
CREATE INDEX orders_created_at_id_idx ON orders (created_at, id);

-- та же страница 25 001: всё, что после последней строки страницы 25 000
EXPLAIN (ANALYZE, BUFFERS, COSTS OFF)
SELECT id, created_at, customer, total
FROM orders
WHERE (created_at, id) < ('2026-04-26 17:47:00+00', 166667)
ORDER BY created_at DESC, id DESC
LIMIT 21;

$ psql -d shop -f sql/03-keyset.sql
                                                  QUERY PLAN                                                   
---------------------------------------------------------------------------------------------------------------
 Limit (actual time=0.030..0.150 rows=21 loops=1)
   Buffers: shared hit=24
   ->  Index Scan Backward using orders_created_at_id_idx on orders (actual time=0.029..0.145 rows=21 loops=1)
         Index Cond: (ROW(created_at, id) < ROW('2026-04-26 17:47:00+00'::timestamp with time zone, 166667))
         Buffers: shared hit=24
 Planning:
   Buffers: shared hit=102
 Planning Time: 0.449 ms
 Execution Time: 0.195 ms

-- первая страница
SELECT id, created_at, customer, total FROM orders
ORDER BY created_at DESC, id DESC LIMIT $1;

-- следующая: всё, что ниже последней строки страницы
SELECT id, created_at, customer, total FROM orders
WHERE (created_at, id) < ($1::timestamptz, $2::bigint)
ORDER BY created_at DESC, id DESC LIMIT $3;

-- предыдущая: всё, что выше первой строки страницы; результат развернуть
SELECT id, created_at, customer, total FROM orders
WHERE (created_at, id) > ($1::timestamptz, $2::bigint)
ORDER BY created_at ASC, id ASC LIMIT $3;

import http from "node:http";
import pg from "pg";

const COLUMNS = "id, created_at, customer, total";
const MAX_LIMIT = 100;

// timestamptz (OID 1184) оставляем строкой: в Date пропадут микросекунды, и курсор начнёт терять строки
const types = {
  getTypeParser: (oid, format) => (oid === 1184 ? (value) => value : pg.types.getTypeParser(oid, format)),
};

const TIMESTAMP = /^\d{4}-\d{2}-\d{2} \d{2}:\d{2}:\d{2}(\.\d{1,6})?[+-]\d{2}(:\d{2})?$/;

// курсор — непрозрачная строка: base64url от [created_at, id] граничной строки
export function encodeCursor(row) {
  return Buffer.from(JSON.stringify([row.created_at, row.id])).toString("base64url");
}

export function decodeCursor(cursor) {
  try {
    const [createdAt, id] = JSON.parse(Buffer.from(cursor, "base64url").toString("utf8"));
    if (TIMESTAMP.test(createdAt) && /^\d{1,18}$/.test(id)) return { createdAt, id };
  } catch {
    // не base64url или не JSON — ниже вернём null
  }
  return null;
}

// новые заказы сверху: ORDER BY created_at DESC, id DESC
export async function listOrders(db, { limit = 20, after = null, before = null } = {}) {
  let query;
  if (after) {
    query = {
      text: `SELECT ${COLUMNS} FROM orders
             WHERE (created_at, id) < ($1::timestamptz, $2::bigint)
             ORDER BY created_at DESC, id DESC LIMIT $3`,
      values: [after.createdAt, after.id, limit + 1],
    };
  } else if (before) {
    // назад: идём от курсора вверх по возрастанию, потом разворачиваем
    query = {
      text: `SELECT ${COLUMNS} FROM orders
             WHERE (created_at, id) > ($1::timestamptz, $2::bigint)
             ORDER BY created_at ASC, id ASC LIMIT $3`,
      values: [before.createdAt, before.id, limit + 1],
    };
  } else {
    query = {
      text: `SELECT ${COLUMNS} FROM orders ORDER BY created_at DESC, id DESC LIMIT $1`,
      values: [limit + 1],
    };
  }

  const { rows } = await db.query({ ...query, types });
  const hasMore = rows.length > limit; // лишняя (limit + 1)-я строка — признак, что дальше есть ещё
  const items = rows.slice(0, limit);
  if (before) items.reverse();

  const hasNext = before ? items.length > 0 : hasMore;
  const hasPrev = before ? hasMore : Boolean(after) && items.length > 0;
  return {
    items,
    next_cursor: hasNext ? encodeCursor(items.at(-1)) : null,
    prev_cursor: hasPrev ? encodeCursor(items[0]) : null,
  };
}

function problem(res, status, detail) {
  res.writeHead(status, { "content-type": "application/problem+json" });
  res.end(JSON.stringify({ title: http.STATUS_CODES[status], status, detail }));
}

export function createServer(db) {
  return http.createServer(async (req, res) => {
    const url = new URL(req.url, "http://localhost");
    if (req.method !== "GET" || url.pathname !== "/api/orders") return problem(res, 404, "Нет такого адреса");

    const params = url.searchParams;
    const limit = Number(params.get("limit") ?? 20);
    if (!Number.isInteger(limit) || limit < 1 || limit > MAX_LIMIT) {
      return problem(res, 400, `limit — целое число от 1 до ${MAX_LIMIT}`);
    }
    if (params.has("after") && params.has("before")) return problem(res, 400, "Передайте after или before, не оба");

    const raw = params.get("after") ?? params.get("before");
    const cursor = raw === null ? null : decodeCursor(raw);
    if (raw !== null && cursor === null) return problem(res, 400, "Курсор повреждён");

    try {
      const page = await listOrders(db, {
        limit,
        after: params.has("after") ? cursor : null,
        before: params.has("before") ? cursor : null,
      });
      res.writeHead(200, { "content-type": "application/json" });
      res.end(JSON.stringify(page));
    } catch (err) {
      console.error(err);
      problem(res, 500, "Внутренняя ошибка сервера");
    }
  });
}

import pg from "pg";
import { createServer } from "./orders-api.js";

// DATABASE_URL=postgres://user:password@localhost:5432/shop node server.js
const pool = new pg.Pool({ connectionString: process.env.DATABASE_URL });
const port = Number(process.env.PORT ?? 3000);

createServer(pool).listen(port, () => console.log(`http://localhost:${port}/api/orders`));

import assert from "node:assert/strict";
import { once } from "node:events";
import { after, before, test } from "node:test";
import pg from "pg";
import { createServer, decodeCursor } from "./orders-api.js";

// отдельная тестовая база: TEST_DATABASE_URL=postgres://postgres:test@localhost:5432/shop_test
const pool = new pg.Pool({ connectionString: process.env.TEST_DATABASE_URL });
let server;
let baseUrl;

before(async () => {
  await pool.query("DROP TABLE IF EXISTS orders");
  await pool.query(`CREATE TABLE orders (
    id         bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
    created_at timestamptz    NOT NULL DEFAULT now(),
    customer   text           NOT NULL,
    total      numeric(12, 2) NOT NULL)`);
  await pool.query("CREATE INDEX orders_created_at_id_idx ON orders (created_at, id)");
  // 45 заказов: по три на одно время, время с микросекундами
  await pool.query(`INSERT INTO orders (created_at, customer, total)
    SELECT timestamptz '2026-10-01 12:00:00.123456+00' + (g % 15) * interval '1.000001 second',
           'customer-' || g, 100 + g
    FROM generate_series(1, 45) AS g`);
  server = createServer(pool).listen(0);
  await once(server, "listening");
  baseUrl = `http://localhost:${server.address().port}/api/orders`;
});

after(async () => {
  server.close();
  await pool.end();
});

async function get(params) {
  const res = await fetch(`${baseUrl}?${new URLSearchParams(params)}`);
  return { status: res.status, body: await res.json() };
}

async function idsInOrder() {
  const { rows } = await pool.query("SELECT id FROM orders ORDER BY created_at DESC, id DESC");
  return rows.map((row) => row.id);
}

const ids = (page) => page.items.map((order) => order.id);

test("вперёд по next_cursor: каждая строка ровно один раз и по порядку", async () => {
  const seen = [];
  let page = (await get({ limit: 10 })).body;
  seen.push(...ids(page));
  while (page.next_cursor) {
    page = (await get({ limit: 10, after: page.next_cursor })).body;
    seen.push(...ids(page));
  }
  assert.deepEqual(seen, await idsInOrder());
  assert.match(decodeCursor((await get({ limit: 10 })).body.next_cursor).createdAt, /\.\d{6}\+00$/);
});

test("назад по prev_cursor: те же страницы в обратном порядке", async () => {
  const forward = [];
  let page = (await get({ limit: 10 })).body;
  forward.push(ids(page));
  while (page.next_cursor) {
    page = (await get({ limit: 10, after: page.next_cursor })).body;
    forward.push(ids(page));
  }
  const backward = [];
  while (page.prev_cursor) {
    page = (await get({ limit: 10, before: page.prev_cursor })).body;
    backward.unshift(ids(page));
  }
  assert.deepEqual(backward, forward.slice(0, -1));
  assert.equal(page.prev_cursor, null); // дошли до первой страницы
});

test("новые заказы не сдвигают следующую страницу, а OFFSET даёт дубли", async () => {
  const expected = await idsInOrder();
  const first = (await get({ limit: 10 })).body;

  await pool.query("INSERT INTO orders (customer, total) SELECT 'customer-new', 500 FROM generate_series(1, 5)");

  const second = (await get({ limit: 10, after: first.next_cursor })).body;
  assert.deepEqual(ids(second), expected.slice(10, 20));

  const { rows } = await pool.query("SELECT id FROM orders ORDER BY created_at DESC, id DESC LIMIT 10 OFFSET 10");
  const onFirstPage = new Set(ids(first));
  assert.equal(rows.filter((row) => onFirstPage.has(row.id)).length, 5);
});

test("битый курсор и неверный limit — 400", async () => {
  const forged = Buffer.from(JSON.stringify(["2026-10-01", "1; DROP TABLE orders"])).toString("base64url");
  for (const params of [{ after: "abc" }, { before: forged }, { limit: 1000 }, { after: "a", before: "b" }]) {
    const { status, body } = await get(params);
    assert.equal(status, 400, JSON.stringify(params));
    assert.equal(body.title, "Bad Request");
  }
});

$ TEST_DATABASE_URL=postgres://postgres:test@localhost:5432/shop_test node --test
✔ вперёд по next_cursor: каждая строка ровно один раз и по порядку (97.8309ms)
✔ назад по prev_cursor: те же страницы в обратном порядке (122.9019ms)
✔ новые заказы не сдвигают следующую страницу, а OFFSET даёт дубли (31.1297ms)
✔ битый курсор и неверный limit — 400 (60.7639ms)
ℹ tests 4
ℹ suites 0
ℹ pass 4
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 475.9961

$ curl -s "localhost:3000/api/orders?limit=2"
{"items":[{"id":"964223","created_at":"2026-08-20 11:33:00+00","customer":"customer-4223","total":"21507.67"},{"id":"630889","created_at":"2026-08-20 11:33:00+00","customer":"customer-889","total":"396.33"}],"next_cursor":"WyIyMDI2LTA4LTIwIDExOjMzOjAwKzAwIiwiNjMwODg5Il0","prev_cursor":null}

$ curl -s "localhost:3000/api/orders?limit=2&after=WyIyMDI2LTA4LTIwIDExOjMzOjAwKzAwIiwiNjMwODg5Il0"
{"items":[{"id":"297555","created_at":"2026-08-20 11:33:00+00","customer":"customer-2555","total":"9285.00"},{"id":"928444","created_at":"2026-08-20 11:32:00+00","customer":"customer-3444","total":"9581.33"}],"next_cursor":"WyIyMDI2LTA4LTIwIDExOjMyOjAwKzAwIiwiOTI4NDQ0Il0","prev_cursor":"WyIyMDI2LTA4LTIwIDExOjMzOjAwKzAwIiwiMjk3NTU1Il0"}

$ curl -s -i "localhost:3000/api/orders?after=oops"
HTTP/1.1 400 Bad Request
content-type: application/problem+json
…
Transfer-Encoding: chunked

{"title":"Bad Request","status":400,"detail":"Курсор повреждён"}

BEGIN;
-- страница 1, которую видит пользователь
CREATE TEMP TABLE page1 AS
SELECT id, created_at FROM orders ORDER BY created_at DESC, id DESC LIMIT 20;

-- пока он читает, появились 5 новых заказов
INSERT INTO orders (customer, total)
SELECT 'customer-new', 500 FROM generate_series(1, 5);

-- страница 2 через OFFSET: сколько строк повторяют страницу 1
SELECT count(*) AS offset_duplicates
FROM (SELECT id FROM orders ORDER BY created_at DESC, id DESC LIMIT 20 OFFSET 20) AS page2
WHERE id IN (SELECT id FROM page1);

-- страница 2 через keyset от последней строки страницы 1
SELECT count(*) AS keyset_duplicates
FROM (SELECT id FROM orders
      WHERE (created_at, id) < (SELECT created_at, id FROM page1 ORDER BY created_at, id LIMIT 1)
      ORDER BY created_at DESC, id DESC LIMIT 20) AS page2
WHERE id IN (SELECT id FROM page1);
ROLLBACK;

$ psql -d shop -f sql/05-stability.sql
BEGIN
SELECT 20
INSERT 0 5
 offset_duplicates 
-------------------
                 5
(1 row)

 keyset_duplicates 
-------------------
                 0
(1 row)

ROLLBACK