07-keyset-pagination.sql

-- Pattern 07 — Keyset pagination with a composite cursor
-- ============================================================================
--
-- Problem: paginate an activity feed. The default is OFFSET:
--
--     SELECT ... ORDER BY created_at DESC LIMIT 20 OFFSET 10000;
--
-- Two failures, one obvious and one subtle:
--   * cost — OFFSET N reads and discards N rows; page 500 costs 500 pages
--     of work. Every deep page is slower than the last.
--   * correctness — rows inserted while a user pages shift every subsequent
--     page, so they see duplicates or miss rows entirely.
--
-- Keyset pagination fixes both: remember WHERE the last page ended, not how
-- many rows came before. The cursor must be built on a TOTAL ordering —
-- created_at alone ties (batch imports, same-millisecond writes), so pair it
-- with id as a tiebreaker and compare with a ROW comparison:
--
--     (created_at, id) < ($after_ts, $after_id)
--
-- Postgres evaluates row comparison lexicographically and — the part that
-- matters — can drive it straight down the (created_at DESC, id DESC) index.
-- The app encodes the pair opaquely (e.g. base64 "ts|id") as `next_cursor`.
-- ============================================================================

-- Page 1: no cursor. LIMIT n+1 is the look-ahead trick — fetch one extra row;
-- if it arrives, has_more = true and the (n+1)th row is NOT returned, its
-- predecessor becomes the cursor. No COUNT(*) query needed.
SELECT id, node_id, kind, created_at
FROM events
ORDER BY created_at DESC, id DESC
LIMIT 6;                                   -- page_size 5, +1 look-ahead

-- Page 2: resume strictly after the last delivered row. Values below are
-- picked live from the seed (gset stores page 1's boundary into variables).
SELECT created_at AS after_ts, id AS after_id
FROM events
ORDER BY created_at DESC, id DESC
OFFSET 4 LIMIT 1                           -- last row OF the delivered page
\gset

SELECT id, node_id, kind, created_at
FROM events
WHERE (created_at, id) < (:'after_ts', :'after_id')     -- composite keyset
ORDER BY created_at DESC, id DESC
LIMIT 6;

-- ----------------------------------------------------------------------------
-- Correctness check: pages must tile the table — no gaps, no duplicates.
-- Walk the whole events table in 5-row keyset pages and compare the union
-- against a straight ordered scan.
-- ----------------------------------------------------------------------------
CREATE TEMP TABLE paged (id uuid PRIMARY KEY);   -- PK trips on any duplicate

DO $$
DECLARE
    cur_ts timestamptz := 'infinity';
    cur_id uuid        := 'ffffffff-ffff-ffff-ffff-ffffffffffff';
    batch  int;
BEGIN
    LOOP
        INSERT INTO paged
        SELECT id FROM events
        WHERE (created_at, id) < (cur_ts, cur_id)
        ORDER BY created_at DESC, id DESC
        LIMIT 5;
        GET DIAGNOSTICS batch = ROW_COUNT;
        EXIT WHEN batch = 0;
        SELECT e.created_at, e.id INTO cur_ts, cur_id
        FROM events e JOIN paged p ON p.id = e.id
        ORDER BY e.created_at, e.id
        LIMIT 1;                                  -- oldest row seen so far
    END LOOP;
END $$;

SELECT (SELECT count(*) FROM paged)  AS rows_via_pages,
       (SELECT count(*) FROM events) AS rows_in_table,
       (SELECT count(*) FROM paged) = (SELECT count(*) FROM events)
           AS complete_and_duplicate_free;
-- Expected: both counts equal (145 with the stock seed), flag = true.
-- Duplicates would have blown up the temp table's PRIMARY KEY mid-walk.

DROP TABLE paged;

-- ----------------------------------------------------------------------------
-- The plan difference. Keyset: Index Scan that STARTS at the cursor position.
-- OFFSET: the same index scan, but reading and discarding every skipped row.
-- ----------------------------------------------------------------------------
EXPLAIN (COSTS OFF)
SELECT id FROM events
WHERE (created_at, id) < (now() - interval '90 days',
                          '00000000-0000-0000-0000-000000000000')
ORDER BY created_at DESC, id DESC
LIMIT 5;