Pagination Cost

All the queries in the previous lesson asked for the entire result set. Applications show most lists piece by piece; the offset–limit pair introduced in the SQL Fundamentals course is the best-known way to do it.

It is short to write, its plan is simple, and it is fast on early pages. On deep pages, its cost grows together with the number of skipped rows, and that growth is invisible just from looking at the query text. This lesson measures the cost, builds the alternative, and covers the difference the two approaches bring to the interface.

Measurement Data

The measurement uses the fifty-thousand-record dataset from the previous lesson.

// generate.mjs — 50000 loan records
import { DatabaseSync } from "node:sqlite";
import { rmSync } from "node:fs";
rmSync("library.db", { force: true });

const db = new DatabaseSync("library.db");
db.exec(`
CREATE TABLE member (member_id INTEGER PRIMARY KEY, name TEXT NOT NULL);
CREATE TABLE book (book_id INTEGER PRIMARY KEY, title TEXT NOT NULL);
CREATE TABLE loan (loan_id INTEGER PRIMARY KEY, book_id INTEGER NOT NULL,
                   member_id INTEGER NOT NULL, pickup_date TEXT NOT NULL, return_date TEXT);`);
db.exec("BEGIN");
const u = db.prepare("INSERT INTO member VALUES (?,?)");
for (let i = 1; i <= 60; i++) u.run(i, `Member${i}`);
const k = db.prepare("INSERT INTO book VALUES (?,?)");
for (let i = 1; i <= 200; i++) k.run(i, `Book ${i}`);
const o = db.prepare("INSERT INTO loan VALUES (?,?,?,?,?)");
let seed = 20250727;                        // deterministic pseudo-random sequence
const next = (n) => { seed = (seed * 48271) % 2147483647; return seed % n; };
for (let i = 1; i <= 50000; i++) {
  const year = 2022 + next(4);
  const month = String(next(12) + 1).padStart(2, "0");
  const day = String(next(28) + 1).padStart(2, "0");
  o.run(i, next(200) + 1, next(60) + 1, `${year}-${month}-${day}`,
        next(5) === 0 ? null : `${year}-12-31`);
}
db.exec("COMMIT");
db.exec("ANALYZE");
console.log("loan:", db.prepare("SELECT count(*) AS n FROM loan").get().n,
            " open:", db.prepare("SELECT count(*) AS n FROM loan WHERE return_date IS NULL").get().n);

node generate.mjs

loan: 50000  open: 10006

The Cost of Offset

Two queries produce the same page. The first says how many rows to skip; the second continues from the previous page’s last key.

// pagination.mjs — same page size, increasing offset values, and the keyset approach
import { DatabaseSync } from "node:sqlite";
const db = new DatabaseSync("library.db");
const PAGE_SIZE = 20;

const OFFSET_QUERY = `SELECT loan_id, pickup_date FROM loan
                      WHERE return_date IS NOT NULL ORDER BY loan_id LIMIT ? OFFSET ?`;
const KEYSET_QUERY = `SELECT loan_id, pickup_date FROM loan
                      WHERE return_date IS NOT NULL AND loan_id > ? ORDER BY loan_id LIMIT ?`;

const measure = (run, repeat = 20) => {
  run();
  const t = performance.now();
  for (let i = 0; i < repeat; i++) run();
  return (performance.now() - t) / repeat;
};

console.log("offset    offset_ms     keyset_ms     ratio");
for (const offset of [0, 1000, 10000, 30000, 39000]) {
  // The starting key for the same page is found for the keyset approach.
  const boundary = db.prepare(
    `SELECT loan_id FROM loan WHERE return_date IS NOT NULL
     ORDER BY loan_id LIMIT 1 OFFSET ?`).get(Math.max(0, offset - 1));
  const previousKey = offset === 0 ? 0 : boundary.loan_id;

  const a = measure(() => db.prepare(OFFSET_QUERY).all(PAGE_SIZE, offset));
  const b = measure(() => db.prepare(KEYSET_QUERY).all(previousKey, PAGE_SIZE));
  console.log(`${String(offset).padStart(6)}  ${a.toFixed(3).padStart(10)}  ${b.toFixed(3).padStart(12)}  ` +
    `${(a / b).toFixed(1).padStart(6)}x`);
}

node pagination.mjs

offset    offset_ms     keyset_ms     ratio
     0       0.012         0.013     1.0x
  1000       0.030         0.012     2.4x
 10000       0.203         0.013    16.2x
 30000       0.616         0.011    57.1x
 39000       0.793         0.011    70.7x

The two approaches are equal on the first page. As the offset grows, the offset query’s duration grows linearly: roughly seventeen-fold at 10000, seventy-fold at 39000. The keyset query’s duration does not change.

The reason lies not in the query plan but in what the plan means. OFFSET is not a “skip” instruction; the database has to produce the skipped rows, then discard them. Fetching the thirty-thousandth page means thirty thousand rows get read and thrown away. In the keyset query, the condition itself gives a starting point in the index; the number of rows read is only the page size.

This matches the previous lesson’s metric: both queries use an index, and both plans say “search.” The difference is in how many rows the plan produces.

Traversal Total

A single deep page takes milliseconds; the real difference shows up when the whole list is scanned. Exports and batch jobs do this constantly.

// full-traversal.mjs — total cost of walking every page from start to end
import { DatabaseSync } from "node:sqlite";
const db = new DatabaseSync("library.db");
const PAGE_SIZE = 100;

function offsetTraversal() {
  const statement = db.prepare(`SELECT loan_id FROM loan WHERE return_date IS NOT NULL
                                ORDER BY loan_id LIMIT ? OFFSET ?`);
  let offset = 0, total = 0, page = 0;
  for (;;) {
    const rows = statement.all(PAGE_SIZE, offset);
    if (rows.length === 0) break;
    total += rows.length; offset += PAGE_SIZE; page += 1;
  }
  return { total, page };
}

function keysetTraversal() {
  const statement = db.prepare(`SELECT loan_id FROM loan WHERE return_date IS NOT NULL
                                AND loan_id > ? ORDER BY loan_id LIMIT ?`);
  let last = 0, total = 0, page = 0;
  for (;;) {
    const rows = statement.all(last, PAGE_SIZE);
    if (rows.length === 0) break;
    last = rows[rows.length - 1].loan_id;
    total += rows.length; page += 1;
  }
  return { total, page };
}

for (const [label, traverse] of [["offset", offsetTraversal], ["keyset", keysetTraversal]]) {
  const t = performance.now();
  const { total, page } = traverse();
  console.log(`${label.padEnd(10)} pages=${page}  rows=${total}  duration=${(performance.now() - t).toFixed(0)} ms`);
}

node full-traversal.mjs

offset     pages=400  rows=39994  duration=170 ms
keyset     pages=400  rows=39994  duration=7 ms

The same four hundred pages, the same thirty-nine thousand rows, a twenty-four-fold difference in duration. In offset traversal, the total number of rows read is proportional to the square of the page count; every page reproduces all of the ones before it. In keyset traversal, every row is read exactly once.

The Shifting Result Set

Alongside the cost, there is a correctness problem. If the result set changes between pages, the offset value no longer points at the same row.

// shifting-page.mjs — when the set changes between pages, offset pagination skips a record
import { DatabaseSync } from "node:sqlite";
import { rmSync } from "node:fs";
rmSync("small.db", { force: true });

const db = new DatabaseSync("small.db");
db.exec(`CREATE TABLE loan (loan_id INTEGER PRIMARY KEY, return_date TEXT);
         INSERT INTO loan (loan_id, return_date)
         VALUES (1,NULL),(2,NULL),(3,NULL),(4,NULL),(5,NULL),
                (6,NULL),(7,NULL),(8,NULL),(9,NULL),(10,NULL);`);

const offsetPage = (offset) => db.prepare(
  "SELECT loan_id FROM loan WHERE return_date IS NULL ORDER BY loan_id LIMIT 5 OFFSET ?")
  .all(offset).map((r) => r.loan_id);
const keysetPage = (lastKey) => db.prepare(
  "SELECT loan_id FROM loan WHERE return_date IS NULL AND loan_id > ? ORDER BY loan_id LIMIT 5")
  .all(lastKey).map((r) => r.loan_id);

const o1 = offsetPage(0);
db.prepare("UPDATE loan SET return_date = '2025-07-20' WHERE loan_id = 2").run();  // the set shrank
const o2 = offsetPage(5);
console.log("offset  page1:", o1.join(","), " page2:", o2.join(","));
console.log("  shown:", [...o1, ...o2].join(","));

db.prepare("UPDATE loan SET return_date = NULL WHERE loan_id = 2").run();          // state is reverted
const k1 = keysetPage(0);
db.prepare("UPDATE loan SET return_date = '2025-07-20' WHERE loan_id = 2").run();
const k2 = keysetPage(k1[k1.length - 1]);
console.log("keyset  page1:", k1.join(","), " page2:", k2.join(","));
console.log("  shown:", [...k1, ...k2].join(","));

node shifting-page.mjs

offset  page1: 1,2,3,4,5  page2: 7,8,9,10
  shown: 1,2,3,4,5,7,8,9,10
keyset  page1: 1,2,3,4,5  page2: 6,7,8,9,10
  shown: 1,2,3,4,5,6,7,8,9,10

When record two leaves the open list, the set shrinks to nine; the second page’s start shifts by one position, and record number six never appears. In the keyset approach, the second page asked for “those greater than five”; the set shrinking did not affect that condition.

The opposite direction is possible too: if the set grows, the same record appears on two pages at once. Both are silent errors; the user sees a list that is missing rows or has duplicates, and no warning is produced. The observation from the Application Impact of Isolation Levels lesson repeats here: two queries that are each correct on their own can be inconsistent together.

Constraints of the Two Approaches

Keyset pagination is not free; it brings two constraints to the interface.

Order cannot be skipped. A “go to page twenty-seven” request cannot be satisfied, because that page’s starting key is not known. Only “next” and — with the sort reversed — “previous” can be offered. The cursor-based pagination introduced in the Web API Design course rests on this constraint; the client is given a cursor instead of a page number.

Sorting must be deterministic. If the sort key is not unique, the order among rows with equal values is undefined, and a record gets skipped or duplicated at the page boundary. For that reason, a unique column is added to the sort key; in a list sorted by pickup date, the condition takes the form “date is greater, or date is equal and the ID is greater.”

Offset pagination has its place too. It is sufficient for lists that stay small in page count, admin screens, and interfaces that need to show the total page count. The criterion is simple: if the offset value has a known upper bound, offset pagination can be used; if the list can grow without limit, the keyset approach is chosen.

A third detail concerns the total count. Showing “1245 records” in an interface requires a separate counting query, and that query produces the entire set; no matter how cheap pagination itself gets, the counting query brings the cost back. For that reason, large lists show “there is more” instead of an exact total; that information is obtained by requesting one more row than the page size.

Summary

• In offset pagination, duration grew linearly with the offset value: 16-fold at 10000, 70-fold at 39000. The keyset query’s duration did not change.
• OFFSET does not keep the database from producing the skipped rows; it reads them and then discards them.
• Walking all four hundred pages took 170 ms with the offset approach and 7 ms with the keyset approach; the cost of offset traversal is proportional to the square of the page count.
• When the result set shrank between pages, offset pagination skipped a record; keyset pagination was unaffected.
• Keyset pagination does not allow skipping order and requires deterministic sorting; offset pagination is sufficient for lists whose offset value has a known upper bound.

Next Step

The Performance Problems topic closed out the measurable side of the data access layer: query count, transferred bytes, statement count, query plan, and pagination cost. All of these metrics were about how the layer works; none of them says what the layer should do. Where does the lending rule live, in which layer does validation happen, is the record returned to the outside the same thing as the domain model? The next topic takes up these questions, and its first lesson separates the responsibilities of the presentation, application, domain, and infrastructure layers and checks the dependency direction through the import graph.