Пагинация OFFSET и keyset в PostgreSQL 17: как время ответа зависит от глубины страницы

$ cd paginaciya-offset-keyset-postgresql   # папка стенда
$ npm install                              # pg 8.23.1
$ bash run.sh                              # 3 прогона
NOTICE:  table "orders" does not exist, skipping
 1000000 | 48c42fd798489f22b2847d4427ff3f80 | 65 MB      | 30 MB
(1 row)

run 1: 2026-10-12T13:41:31Z
…
run 3: 2026-10-12T13:42:10Z
…
runs=1,2,3; rows measure=330, warmup=60; rows_match=0: 0

docker run --rm -d --name kb-g-research --cpus=2 --memory=2g \
  -e POSTGRES_PASSWORD=bench -e POSTGRES_DB=bench -p 55417:5432 \
  postgres:17-alpine -c jit=off
docker exec kb-g-research pg_isready -U postgres -h 127.0.0.1
docker exec -i kb-g-research psql -U postgres -d bench -v ON_ERROR_STOP=1 < setup.sql
RUN=1 node bench.mjs > raw-1.csv
RUN=1 node bench.mjs --explain
node summarize.mjs raw-1.csv
docker stop kb-g-research

-- R-01 стенд: 1 000 000 синтетических заказов, индекс (created_at, id).
-- Запуск: docker exec -i kb-g-research psql -U postgres -d bench -v ON_ERROR_STOP=1 < setup.sql
-- Схема и формула created_at — как в рецепте recept-sql-paginaciya:
-- по три заказа на каждую минуту, порядок id не совпадает с порядком времени.

DROP TABLE IF EXISTS orders;

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

-- фиксированный seed: random() ниже даёт одинаковые значения при каждом запуске
SELECT setseed(0.42);

INSERT INTO orders (created_at, customer, total)
SELECT timestamptz '2026-01-01 00:00:00+00' + ((g::bigint * 7919) % 333334) * interval '1 minute',
       'customer-' || (floor(random() * 5000))::int,
       round((100 + random() * 30000)::numeric, 2)
FROM generate_series(1, 1000000) AS g;

CREATE INDEX orders_created_at_id_idx ON orders (created_at, id);

VACUUM (ANALYZE) orders;

-- контрольная сумма данных: одинакова при повторной генерации
SELECT count(*) AS rows,
       md5(string_agg(id || '|' || created_at::text || '|' || customer || '|' || total, ',' ORDER BY id)) AS checksum,
       pg_size_pretty(pg_relation_size('orders')) AS table_size,
       pg_size_pretty(pg_relation_size('orders_created_at_id_idx')) AS index_size
FROM orders;

/*
  R-01 bench: OFFSET vs keyset в PostgreSQL 17 — время ответа по глубине страницы.

    npm install                                   # pg из package.json
    RUN=1 node bench.mjs          > raw-1.csv     # замеры одного прогона (прогрев + 10 раундов)
    RUN=1 node bench.mjs --explain                # explain-r1-*.txt для p10000 и p50000
    node bench.mjs --settings                     # версия сервера и настройки (в env.txt)
  Полный цикл из трёх прогонов на свежих контейнерах — run.sh.

  DATABASE_URL по умолчанию: postgres://postgres:bench@localhost:55417/bench
*/
import { writeFileSync } from "node:fs";
import { performance } from "node:perf_hooks";
import pg from "pg";

const DB_URL = process.env.DATABASE_URL ?? "postgres://postgres:bench@localhost:55417/bench";
const PAGE = 20;
const DEPTHS = [1, 100, 1000, 10000, 50000];
const ROUNDS = Number(process.env.ROUNDS ?? 10);
const WARMUP = 2;
const SEED = 20261012;
const RUN = Number(process.env.RUN ?? 1);

// timestamptz (OID 1184) — строкой: Date обрезает микросекунды, граница курсора съехала бы
const types = { getTypeParser: (oid, f) => (oid === 1184 ? (v) => v : pg.types.getTypeParser(oid, f)) };

const COLS = "id, created_at, customer, total";
const ORDER = "ORDER BY created_at DESC, id DESC";
const SQL = {
  offset: `SELECT ${COLS} FROM orders ${ORDER} LIMIT ${PAGE} OFFSET $1`,
  first: `SELECT ${COLS} FROM orders ${ORDER} LIMIT ${PAGE}`,
  keyset: `SELECT ${COLS} FROM orders WHERE (created_at, id) < ($1::timestamptz, $2::bigint) ${ORDER} LIMIT ${PAGE}`,
};

// запрос и параметры для варианта и глубины; граница keyset вычислена заранее
function query(variant, page, cursors) {
  if (variant === "offset") return [SQL.offset, [(page - 1) * PAGE]];
  if (page === 1) return [SQL.first, []];
  const c = cursors.get(page);
  return [SQL.keyset, [c.created_at, c.id]];
}

// детерминированный ГПСЧ для перемешивания порядка глубин (seed свой у каждого прогона)
function mulberry32(a) {
  return () => {
    a |= 0; a = (a + 0x6d2b79f5) | 0;
    let t = Math.imul(a ^ (a >>> 15), 1 | a);
    t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t;
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296;
  };
}
function shuffled(arr, rnd) {
  const a = [...arr];
  for (let i = a.length - 1; i > 0; i--) {
    const j = Math.floor(rnd() * (i + 1));
    [a[i], a[j]] = [a[j], a[i]];
  }
  return a;
}

function scanNode(plan) {
  if (/Scan/.test(plan["Node Type"])) return [plan["Node Type"], plan["Scan Direction"], plan["Index Name"]].filter(Boolean).join(" ");
  for (const p of plan.Plans ?? []) {
    const s = scanNode(p);
    if (s) return s;
  }
  return "";
}

const client = new pg.Client({ connectionString: DB_URL, types });
await client.connect();

// граница для keyset: последняя строка страницы N−1; эталонные id страницы N (через OFFSET)
const cursors = new Map();
const reference = new Map();
for (const page of DEPTHS) {
  if (page > 1) {
    const { rows } = await client.query(`SELECT created_at, id FROM orders ${ORDER} LIMIT 1 OFFSET $1`, [(page - 1) * PAGE - 1]);
    cursors.set(page, rows[0]);
  }
  const { rows } = await client.query(SQL.offset, [(page - 1) * PAGE]);
  reference.set(page, rows.map((r) => r.id).join(","));
}

if (process.argv.includes("--settings")) {
  const out = [];
  out.push((await client.query("SELECT version()")).rows[0].version);
  for (const s of ["shared_buffers", "work_mem", "effective_cache_size", "random_page_cost", "jit", "max_parallel_workers_per_gather", "max_worker_processes", "TimeZone"]) {
    out.push(`${s} = ${Object.values((await client.query(`SHOW ${s}`)).rows[0])[0]}`);
  }
  const size = await client.query(`SELECT count(*) AS n, pg_size_pretty(pg_relation_size('orders')) AS t, pg_size_pretty(pg_relation_size('orders_created_at_id_idx')) AS i FROM orders`);
  out.push(`orders: ${size.rows[0].n} rows, table ${size.rows[0].t}, index (created_at, id) ${size.rows[0].i}`);
  for (const [p, c] of cursors) out.push(`keyset cursor for page ${p}: (${c.created_at}, ${c.id})`);
  console.log(out.join("\n"));
  await client.end();
  process.exit(0);
}

if (process.argv.includes("--explain")) {
  for (const page of [10000, 50000]) {
    for (const variant of ["offset", "keyset"]) {
      const [sql, params] = query(variant, page, cursors);
      const { rows } = await client.query(`EXPLAIN (ANALYZE, BUFFERS) ${sql}`, params);
      const text = [`-- ${variant}, page ${page} (page size ${PAGE})`, `-- ${sql}`, `-- params: ${JSON.stringify(params)}`, "", ...rows.map((r) => r["QUERY PLAN"])].join("\n");
      const file = `explain-r${RUN}-${variant}-p${page}.txt`;
      writeFileSync(new URL(file, import.meta.url), `-- run ${RUN}\n${text}\n`);
      console.error(file);
    }
  }
  await client.end();
  process.exit(0);
}

async function measure(variant, page) {
  const [sql, params] = query(variant, page, cursors);
  const ex = await client.query(`EXPLAIN (ANALYZE, BUFFERS, TIMING OFF, FORMAT JSON) ${sql}`, params);
  const plan = ex.rows[0]["QUERY PLAN"][0];
  const t0 = performance.now();
  const res = await client.query(sql, params);
  const clientMs = performance.now() - t0;
  return {
    server_exec_ms: plan["Execution Time"],
    planning_ms: plan["Planning Time"],
    shared_hit: plan.Plan["Shared Hit Blocks"],
    shared_read: plan.Plan["Shared Read Blocks"],
    client_ms: clientMs,
    rows: res.rows.length,
    rows_match: res.rows.map((r) => r.id).join(",") === reference.get(page) ? 1 : 0,
    scan_node: scanNode(plan.Plan),
  };
}

async function ping() {
  const t0 = performance.now();
  await client.query("SELECT 1");
  return performance.now() - t0;
}

const head = ["run", "phase", "round", "seq", "variant", "page", "offset_rows", "server_exec_ms", "planning_ms", "shared_hit", "shared_read", "client_ms", "rows", "rows_match", "scan_node"];
if (!process.env.NO_HEADER) console.log(head.join(","));
let seq = 0;
const emit = (phase, round, variant, page, m) =>
  console.log([RUN, phase, round, ++seq, variant, page, page === 0 ? 0 : (page - 1) * PAGE,
    m.server_exec_ms ?? "", m.planning_ms ?? "", m.shared_hit ?? "", m.shared_read ?? "",
    m.client_ms.toFixed(3), m.rows ?? "", m.rows_match ?? "", m.scan_node ? `"${m.scan_node}"` : ""].join(","));

// прогрев: каждый запрос по WARMUP раз, в медианы не входит
for (let w = 1; w <= WARMUP; w++) {
  for (const page of DEPTHS) for (const variant of ["offset", "keyset"]) emit("warmup", w, variant, page, await measure(variant, page));
}

const rnd = mulberry32(SEED + RUN);
for (let round = 1; round <= ROUNDS; round++) {
  emit("measure", round, "ping", 0, { client_ms: await ping() });
  const variants = round % 2 === 0 ? ["offset", "keyset"] : ["keyset", "offset"];
  for (const page of shuffled(DEPTHS, rnd)) {
    for (const variant of variants) emit("measure", round, variant, page, await measure(variant, page));
  }
}
await client.end();

/*
  Сводка по raw.csv:  node summarize.mjs raw.csv > summary.txt
  Только phase=measure. Перцентили — линейная интерполяция между соседними значениями (p25, p50 = медиана, p75).
*/
import { readFileSync } from "node:fs";

const [header, ...lines] = readFileSync(process.argv[2] ?? "raw.csv", "utf8").trim().split(/\r?\n/);
const keys = header.split(",");
const rows = lines.map((l) => Object.fromEntries(l.split(",").map((v, i) => [keys[i], v.replace(/^"|"$/g, "")])));
const m = rows.filter((r) => r.phase === "measure");

const q = (xs, p) => {
  const s = [...xs].sort((a, b) => a - b);
  const i = (s.length - 1) * p;
  const lo = Math.floor(i);
  return s[lo] + (s[Math.min(lo + 1, s.length - 1)] - s[lo]) * (i - lo);
};
const f = (x) => (x >= 100 ? x.toFixed(1) : x >= 10 ? x.toFixed(2) : x.toFixed(3));
const stat = (xs) => `${f(q(xs, 0.5))} [${f(q(xs, 0.25))}–${f(q(xs, 0.75))}] (${f(Math.min(...xs))}–${f(Math.max(...xs))})`;

const runs = [...new Set(m.map((r) => r.run))];
console.log(`runs=${runs.join(",")}; rows measure=${m.length}, warmup=${rows.length - m.length}; rows_match=0: ${m.filter((r) => r.rows_match === "0").length}`);
console.log("формат: медиана [p25–p75] (min–max), мс; буферы — медиана (min–max)\n");
const pings = m.filter((r) => r.variant === "ping").map((r) => +r.client_ms);
console.log(`ping (SELECT 1), client_ms, n=${pings.length}: ${stat(pings)}\n`);
console.log("variant | page | offset_rows | n | server_exec_ms | client_ms | planning_ms | shared_hit | shared_read | scan_node");
for (const page of [...new Set(m.filter((r) => r.variant !== "ping").map((r) => +r.page))].sort((a, b) => a - b)) {
  for (const variant of ["offset", "keyset"]) {
    const g = m.filter((r) => r.variant === variant && +r.page === page);
    if (!g.length) continue;
    const hit = g.map((r) => +r.shared_hit);
    const read = g.map((r) => +r.shared_read);
    console.log([variant, page, g[0].offset_rows, g.length,
      stat(g.map((r) => +r.server_exec_ms)), stat(g.map((r) => +r.client_ms)), stat(g.map((r) => +r.planning_ms)),
      `${q(hit, 0.5)} (${Math.min(...hit)}–${Math.max(...hit)})`, `${q(read, 0.5)} (${Math.min(...read)}–${Math.max(...read)})`,
      [...new Set(g.map((r) => r.scan_node))].join(" / ")].join(" | "));
  }
}

console.log("\nмедианы по прогонам (каждый прогон — свежий контейнер и свежая генерация), мс");
console.log("variant | page | " + runs.map((r) => `run ${r} server`).join(" | ") + " | " + runs.map((r) => `run ${r} client`).join(" | ") + " | scan_node по прогонам");
for (const page of [...new Set(m.filter((r) => r.variant !== "ping").map((r) => +r.page))].sort((a, b) => a - b)) {
  for (const variant of ["offset", "keyset"]) {
    const by = (run) => m.filter((r) => r.variant === variant && +r.page === page && r.run === run);
    console.log([variant, page,
      ...runs.map((run) => f(q(by(run).map((r) => +r.server_exec_ms), 0.5))),
      ...runs.map((run) => f(q(by(run).map((r) => +r.client_ms), 0.5))),
      runs.map((run) => [...new Set(by(run).map((r) => r.scan_node))].join("+")).join(" / ")].join(" | "));
  }
}

#!/usr/bin/env bash
# R-01: три независимых прогона, каждый — на свежем контейнере со свежей генерацией данных.
# Запуск из папки исследования (Linux, macOS или Git Bash на Windows):  bash run.sh
# Нужны Docker и Node.js; перед первым запуском — npm install.
set -euo pipefail
cd "$(dirname "$0")"

IMAGE=postgres:17-alpine
NAME=kb-g-research
PORT=55417
RUNS=${RUNS:-3}

host_info() {
  if command -v powershell.exe > /dev/null; then
    powershell.exe -NoProfile -Command '[Console]::OutputEncoding = [Text.Encoding]::UTF8; $c = Get-CimInstance Win32_Processor; $s = Get-CimInstance Win32_ComputerSystem; $o = Get-CimInstance Win32_OperatingSystem; "CPU " + $c.Name + ", cores " + $c.NumberOfCores + ", logical " + $c.NumberOfLogicalProcessors; "RAM " + [math]::Round($s.TotalPhysicalMemory / 1GB, 1) + " GB"; $o.Caption + " " + $o.Version' | tr -d '\r'
  elif command -v lscpu > /dev/null; then
    lscpu | grep 'Model name'; free -g | head -2
  else
    sysctl -n machdep.cpu.brand_string hw.memsize
  fi
}

: > raw.csv
for RUN in $(seq 1 "$RUNS"); do
  docker run --rm -d --name "$NAME" --cpus=2 --memory=2g \
    -e POSTGRES_PASSWORD=bench -e POSTGRES_DB=bench -p "$PORT:5432" \
    "$IMAGE" -c jit=off > /dev/null
  # ждём финальный сервер (временный сервер инициализации слушает только сокет)
  for _ in $(seq 1 60); do
    docker exec "$NAME" pg_isready -U postgres -h 127.0.0.1 > /dev/null 2>&1 && break
    sleep 1
  done
  docker exec -i "$NAME" psql -U postgres -d bench -v ON_ERROR_STOP=1 < setup.sql | tail -n 3
  echo "run $RUN: $(date -u +%FT%TZ)" >&2
  if [ "$RUN" -eq 1 ]; then RUN=$RUN node bench.mjs >> raw.csv; else RUN=$RUN NO_HEADER=1 node bench.mjs >> raw.csv; fi
  RUN=$RUN node bench.mjs --explain
  if [ "$RUN" -eq 1 ]; then
    {
      echo "# R-01 environment, recorded $(date -u +%FT%TZ)"
      echo "## host"
      uname -a
      host_info
      echo "## runtime"
      echo "node $(node -v)"
      echo "pg $(node -p "require('./node_modules/pg/package.json').version")"
      docker version --format 'docker client {{.Client.Version}}, server {{.Server.Version}} ({{.Server.Os}}/{{.Server.Arch}})'
      docker info --format 'docker VM: {{.OperatingSystem}}, kernel {{.KernelVersion}}, {{.NCPU}} CPU, {{.MemTotal}} bytes'
      docker image inspect "$IMAGE" --format 'image {{index .RepoTags 0}} {{.Id}}'
      echo "container limits: --cpus=2 --memory=2g; server flag: -c jit=off"
      echo "## postgres"
      node bench.mjs --settings
    } > env.txt
  fi
  docker stop "$NAME" > /dev/null
done
node summarize.mjs raw.csv > summary.txt
cat summary.txt