DEV Community

Mayank Srivastava
Mayank Srivastava

Posted on

Why GitHub Cannot Paginate Through Millions of Repositories - Deep Pagination Explained

#webdev #backend #sql #postgres

You've paginated through a big result set before. Page 2 loads fine. Page 200 takes a beat. Nobody stops to ask why — until something like this shows up instead of a slow page:

{
  "message": "Only the first 1000 search results are available.",
  "documentation_url": "https://docs.github.com/v3/search/",
  "status": "422"
}
Enter fullscreen mode Exit fullscreen mode

That's GitHub's own search API. Ask it for page 9 or page 10 of a search and you get real results. Ask for page 11 and you get that, on purpose, every time.

I went and looked at why. Full video below, written breakdown after it for anyone who'd rather read.

Reproducing it

Not a guess — this is live, right now:

curl "https://api.github.com/search/repositories?q=javascript&page=9&per_page=100"
# -> real results

curl "https://api.github.com/search/repositories?q=javascript&page=10&per_page=100"
# -> real results

curl "https://api.github.com/search/repositories?q=javascript&page=11&per_page=100"
# -> 422, the message above
Enter fullscreen mode Exit fullscreen mode

GitHub documents this cap directly — it's not rate limiting, and it's not a bug that slipped through. Once you understand the mechanism it's protecting against, the same wall shows up in a lot of places that don't bother telling you about it — including, probably, a table you've built yourself.

The query behind the page number

Most pagination UIs turn a page number into something like this:

SELECT * FROM videos
ORDER BY id
LIMIT 20 OFFSET 999980;
Enter fullscreen mode Exit fullscreen mode

Twenty rows per page, page 50,000 requested — that's an offset of nearly a million. It's easy to assume the database can jump straight to row 999,980. It can't, and the reason is in how the underlying index is built, not in anything about this specific query.

What an index actually is

A sorted column is backed by a B-tree — a structure built for one thing: walking rows in order, fast. The leaf level is a chain of rows in sorted sequence. That chain is what makes ORDER BY cheap.

It is also the whole problem. There's no operation in a B-tree for "give me whatever's at position 999,980." Only for "give me whatever's next after this value." Position and value are not the same axis, and only one of them has a shortcut.

So OFFSET 999980 does the only thing it can: start at the beginning of the scan, count a row, discard it, count the next, discard it — one at a time, nearly a million times — before it starts collecting the 20 rows you actually asked for.

Cost = O(offset), not O(page size). Page 10 is nearly free. Page 50,000 means walking and throwing away roughly a million rows just to reach the part you wanted.

What actually happens, measured

Theory's cheap. Here's a real table — 5 million rows, local Postgres:

docker run --name pagination-demo -e POSTGRES_PASSWORD=demo -p 5432:5432 -d postgres:16
docker exec -it pagination-demo psql -U postgres
Enter fullscreen mode Exit fullscreen mode 
CREATE TABLE videos (
  id BIGINT PRIMARY KEY,
  title TEXT,
  created_at TIMESTAMP
);

INSERT INTO videos (id, title, created_at)
SELECT g, 'Video ' || g, NOW() - (random() * interval '3 years')
FROM generate_series(1, 5000000) AS g;
Enter fullscreen mode Exit fullscreen mode 
EXPLAIN ANALYZE
SELECT * FROM videos
ORDER BY id
LIMIT 20 OFFSET 999980;
Enter fullscreen mode Exit fullscreen mode 
Limit  (cost=33323.00..33323.67 rows=20 width=29) (actual time=121.583..121.586 rows=20 loops=1)
  ->  Index Scan using videos_pkey on videos  (cost=0.43..166616.30 rows=4999991 width=29)
        (actual time=0.012..94.512 rows=1000000 loops=1)
Planning Time: 0.201 ms
Execution Time: 121.603 ms
Enter fullscreen mode Exit fullscreen mode

rows=1000000 on the scan node isn't an estimate — that's the actual count the engine walked through before it could return anything, exactly matching the mechanism above.

The fix everyone reaches for, and what it actually does

The usual advice is "use cursor pagination instead of OFFSET." Here's the query that advice produces:

EXPLAIN ANALYZE
SELECT * FROM videos
WHERE id < 845923
ORDER BY id DESC
LIMIT 20;
Enter fullscreen mode Exit fullscreen mode 
Limit  (cost=0.43..1.15 rows=20 width=29) (actual time=0.477..0.484 rows=20 loops=1)
  ->  Index Scan Backward using videos_pkey on videos  (cost=0.43..30516.09 rows=851752 width=29)
        (actual time=0.475..0.480 rows=20 loops=1)
        Index Cond: (id < 845923)
Planning Time: 0.129 ms
Execution Time: 0.503 ms
Enter fullscreen mode Exit fullscreen mode

Same table. Same 20 rows back. 121.603 ms → 0.503 ms — roughly 242x, and it's not a rounding error, it's a different cost curve entirely.

What changed underneath: instead of walking the leaf chain from the start, the engine descends the tree directly — root, branch, leaf — to id = 845923, then reads 20 rows backward from there. A seek, not a scan. That's the entire mechanism. Nothing about the table changed, nothing about the index changed — only the shape of the question changed, from "what's at position N" to "what comes after this value."

This is also why Instagram says "load more" and X says "load older posts" instead of showing page numbers. Under the hood, that's a cursor — after=<id> — not a position.

Where this breaks silently

Keyset pagination only holds up if the sort key is unique and strictly ordered — a primary key like id qualifies. The moment you sort by something that can repeat, like created_at, where two rows can land on the exact same millisecond, a single-column cursor can silently skip a row or hand back a duplicate. Nothing errors. It just quietly returns the wrong set.

The fix is comparing a pair of columns, not one:

SELECT * FROM videos
WHERE (created_at, id) < (:last_created_at, :last_id)
ORDER BY created_at DESC, id DESC
LIMIT 20;
Enter fullscreen mode Exit fullscreen mode

That line is the gap between "works in the demo" and "works in production."

What to check before you reach for either

In order:

  1. Does the page number itself need to exist? If users are scrolling a feed, not jumping to "page 4,721," you don't need OFFSET's random access at all — cursor pagination is strictly better here, no tradeoff to weigh.
  2. Do you actually need random access? Admin dashboards, audit tools, support panels — anywhere someone legitimately needs "go to page 42" — OFFSET's random access is the feature, not the bug, and the fix is usually capping how deep it's allowed to go rather than replacing it outright.
  3. If you're building a public API, assume someone will request the deepest possible page. Elasticsearch refuses to paginate past 10,000 results by default and points you at search_after instead — the same fix GitHub ships, in a different system. Capping the depth is cheaper than absorbing the cost of someone finding it by accident.

Not a universal fix

OFFSET isn't wrong. It's the right tool when random access matters more than depth — small tables, internal tools, anywhere nobody's going past page 20 anyway. Cursor pagination isn't strictly "better," it trades away the ability to jump anywhere for a flat cost curve at any depth. The mistake isn't picking one — it's not knowing there's a choice, and finding out which one you picked at the exact moment your table crosses a few million rows.

If this was useful, the video walks through the same benchmark live — GitHub's actual API response, the terminal running both queries against the same 5M-row table, EXPLAIN ANALYZE output as it prints. Drop a comment if you want the follow-up on why COUNT(*) gets slow on the exact same kind of table — different query, same root cause.

Top comments (0)