Keyset pagination

The problem: OFFSET counts every row it skips

Snip's dashboard shows an owner's links, newest first, 50 to a page. The obvious query:

SELECT code, long_url, created_at FROM links_by_owner
WHERE owner_id = $1
ORDER BY created_at DESC
LIMIT 50 OFFSET 8000;  -- page 161

OFFSET 8000 doesn't jump to row 8,001. The database walks the index from the start and reads and throws away 8,000 rows before returning 50. Page 1 is fast; page 161 does about 160 times the work. For Ana's 8,000 links that's tolerable. For a customer with 40 million links exporting them through the API, the last pages each read tens of millions of rows, and the whole export reads trillions.

It also drifts. Ana loads page 1. While she reads, she creates three links. Page 2, computed as "skip 50", now starts three rows earlier, and she sees the last three links of page 1 again. Deletes do the opposite and skip rows she never saw.

Keyset pagination: start after the last row

Instead of "skip N rows", say "rows after the last one I saw". The page remembers the sort key of its last row, and the next query starts there:

SELECT code, long_url, created_at FROM links_by_owner
WHERE owner_id = $1
  AND (created_at, code) < ($2, $3)  -- after the last row of the previous page
ORDER BY created_at DESC, code DESC
LIMIT 51;

With an index on (owner_id, created_at DESC, code DESC), the database seeks straight to the position after the last row and reads 51 rows, whether it's page 2 or page 800,000. And because each page starts from a row rather than a count, new links and deletions elsewhere in the list don't shift it.

Two details make it correct:

• A unique tiebreaker. Two links can share a created_at. Sorting by created_at alone, a page boundary between them would skip or repeat one. Adding code, which is unique, gives every row a distinct position.
• One extra row. Asking for 51 when the page holds 50 tells you whether there's a next page without a separate count.

The cursor

The client shouldn't build that WHERE clause. The API returns an opaque cursor that encodes the last row's key, and the client sends it back for the next page:

type Cursor = { createdAt: string; code: string };

const encode = (c: Cursor) => Buffer.from(JSON.stringify(c)).toString("base64url");
const decode = (s: string): Cursor => JSON.parse(Buffer.from(s, "base64url").toString());

export async function listLinks(db: Db, ownerId: string, cursor?: string, limit = 50) {
  const after = cursor ? decode(cursor) : null;
  const rows = await db.query(
    `SELECT code, long_url, created_at::text AS created_at
       FROM links_by_owner
      WHERE owner_id = $1 ${after ? "AND (created_at, code) < ($3, $4)" : ""}
      ORDER BY created_at DESC, code DESC
      LIMIT $2`,
    after ? [ownerId, limit + 1, after.createdAt, after.code] : [ownerId, limit + 1],
  );
  const page = rows.slice(0, limit);
  const last = page.at(-1);
  return {
    links: page,
    next_cursor: rows.length > limit && last ? encode({ createdAt: last.created_at, code: last.code }) : null,
  };
}

GET /v1/links?limit=50
→ { "links": [...], "next_cursor": "eyJjcmVhdGVkQXQiOiIyMDI2LTExLTA0IDEwOjQy..." }

GET /v1/links?limit=50&cursor=eyJjcmVhdGVkQXQiOiIyMDI2LTExLTA0IDEwOjQy...

Because the cursor is opaque, Snip can change what's inside it later (add a filter, switch to an ID) without breaking clients. The timestamp travels as Postgres's own text (created_at::text), not a JavaScript Date, which would cut microseconds to milliseconds and shift the boundary.

What you give up

For infinite scroll, feeds, API listings and exports, keyset is the right default. For a small admin table where people jump to page 7, OFFSET is fine.

Across shards

If a list spans shards, each shard returns its own next page in the same order, and the service merges them, like merging sorted piles of cards. The cursor then holds one position per shard. Snip avoids this for the dashboard by keeping links_by_owner sharded by owner (05.01 Sharding: range, hash, directory), so one owner's list lives on one shard.

Recap

Interview questions