N+1 Query Problem

The transactions topic established the correctness of writing: where the boundary is drawn, what a read sees, how a concurrent update is resolved, why a retry is safe. None of it was about speed.

A data access layer that works correctly can still be slow, and the source of the slowness is usually not the query itself but the query count. This course’s first lesson had a small mapper run ten queries for three loan records. This lesson measures that count, shows how it grows with the record count, and fixes it.

Measurement Data

Measurement requires a dataset of realistic size.

// generate.mjs — generates library data for measurement: 200 books, 60 members, 2000 loans
import { DatabaseSync } from "node:sqlite";
import { rmSync } from "node:fs";

for (const d of ["library.db", "library.db-wal", "library.db-shm"]) {
  rmSync(d, { force: true });
}
const db = new DatabaseSync("library.db");
db.exec(`
CREATE TABLE member (member_id INTEGER PRIMARY KEY, first_name TEXT NOT NULL, last_name TEXT NOT NULL);
CREATE TABLE book (book_id INTEGER PRIMARY KEY, title TEXT NOT NULL, author 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 insertMember = db.prepare("INSERT INTO member VALUES (?,?,?)");
for (let i = 1; i <= 60; i++) insertMember.run(i, `Member${i}`, `Last${i}`);
const insertBook = db.prepare("INSERT INTO book VALUES (?,?,?)");
for (let i = 1; i <= 200; i++) insertBook.run(i, `Book ${i}`, `Author ${(i % 40) + 1}`);
const insertLoan = db.prepare("INSERT INTO loan VALUES (?,?,?,?,?)");
for (let i = 1; i <= 2000; i++) {
  const day = String((i % 28) + 1).padStart(2, "0");
  const month = String((i % 12) + 1).padStart(2, "0");
  insertLoan.run(i, (i % 200) + 1, (i % 60) + 1, `2025-${month}-${day}`, i % 4 === 0 ? null : "2025-12-31");
}
db.exec("COMMIT");
console.log("member:", db.prepare("SELECT count(*) AS n FROM member").get().n,
            " book:", db.prepare("SELECT count(*) AS n FROM book").get().n,
            " 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

member: 60  book: 200  loan: 2000  open: 500

Making the Query Visible

A count that is not measured does not fall. A thin wrapper placed in front of the connection counts the queries run and the rows returned.

// counter.mjs — a thin wrapper that counts the queries it runs
import { DatabaseSync } from "node:sqlite";

export function countingConnection(file) {
  const db = new DatabaseSync(file);
  const counter = { query: 0, row: 0 };
  return {
    counter,
    single(sql, ...d) { counter.query += 1; const r = db.prepare(sql).get(...d);
                        if (r !== undefined) counter.row += 1; return r; },
    many(sql, ...d) { counter.query += 1; const r = db.prepare(sql).all(...d);
                      counter.row += r.length; return r; },
    reset() { counter.query = 0; counter.row = 0; },
  };
}

Three Approaches

The task is the same: list open loans with the book title and the member’s name. Three approaches are tried. One by one loading reads the relations separately for each record; it is the direct, written-out form of the lazy loading built in the first lesson. Batch fetch collects the identifiers and reads them in a single query. Join leaves the work to the database.

// n-plus-1.mjs — three approaches, same list; query and row counts are measured
import { countingConnection } from "./counter.mjs";
const db = countingConnection("library.db");
const ROW_LIMIT = Number(process.argv[2] ?? 100);

function oneByOne() {
  db.reset();
  const t = performance.now();
  const records = db.many(
    "SELECT loan_id, book_id, member_id FROM loan WHERE return_date IS NULL ORDER BY loan_id LIMIT ?", ROW_LIMIT);
  const list = records.map((o) => ({
    id: o.loan_id,
    title: db.single("SELECT title FROM book WHERE book_id = ?", o.book_id).title,
    member: db.single("SELECT first_name FROM member WHERE member_id = ?", o.member_id).first_name,
  }));
  return { name: "one by one", list, ...db.counter, duration: performance.now() - t };
}

function batchFetch() {
  db.reset();
  const t = performance.now();
  const records = db.many(
    "SELECT loan_id, book_id, member_id FROM loan WHERE return_date IS NULL ORDER BY loan_id LIMIT ?", ROW_LIMIT);
  const bookIds = [...new Set(records.map((o) => o.book_id))];
  const memberIds = [...new Set(records.map((o) => o.member_id))];
  const bookLookup = new Map(db.many(
    `SELECT book_id, title FROM book WHERE book_id IN (${bookIds.map(() => "?").join(",")})`,
    ...bookIds).map((k) => [k.book_id, k.title]));
  const memberLookup = new Map(db.many(
    `SELECT member_id, first_name FROM member WHERE member_id IN (${memberIds.map(() => "?").join(",")})`,
    ...memberIds).map((u) => [u.member_id, u.first_name]));
  const list = records.map((o) => ({
    id: o.loan_id, title: bookLookup.get(o.book_id), member: memberLookup.get(o.member_id),
  }));
  return { name: "batch fetch", list, ...db.counter, duration: performance.now() - t };
}

function join() {
  db.reset();
  const t = performance.now();
  const list = db.many(
    `SELECT o.loan_id AS id, k.title, u.first_name AS member
     FROM loan o JOIN book k ON k.book_id = o.book_id JOIN member u ON u.member_id = o.member_id
     WHERE o.return_date IS NULL ORDER BY o.loan_id LIMIT ?`, ROW_LIMIT);
  return { name: "join", list, ...db.counter, duration: performance.now() - t };
}

const results = [oneByOne(), batchFetch(), join()];
const first = JSON.stringify(results[0].list);
for (const s of results) {
  console.log(`${s.name.padEnd(14)} query=${String(s.query).padStart(4)}  ` +
    `returned_rows=${String(s.row).padStart(4)}  duration=${s.duration.toFixed(1).padStart(6)} ms  ` +
    `result_same=${JSON.stringify(s.list) === first}`);
}

node n-plus-1.mjs 100

one by one     query= 201  returned_rows= 300  duration=   1.2 ms  result_same=true
batch fetch    query=   3  returned_rows= 165  duration=   0.2 ms  result_same=true
join           query=   1  returned_rows= 100  duration=   0.1 ms  result_same=true

All three approaches produced the same list; the last column confirms it. The query counts are 201, 3, and 1.

The shape of the first number names it: one query fetches the list, then extra queries run for each record. Two relations are read per record in this example, so the count comes to $1 + 2N$. In its general form, this is the N+1 query problem: one query for the list, one query per item.

The Number’s Growth

The severity of the problem does not show up in a single measurement; it shows up as the record count grows.

for n in 10 50 100 250 500; do echo "--- record count $n ---"; node n-plus-1.mjs $n; done

--- record count 10 ---
one by one     query=  21  returned_rows=  30  duration=   0.3 ms  result_same=true
batch fetch    query=   3  returned_rows=  30  duration=   0.1 ms  result_same=true
join           query=   1  returned_rows=  10  duration=   0.0 ms  result_same=true
--- record count 50 ---
one by one     query= 101  returned_rows= 150  duration=   0.8 ms  result_same=true
batch fetch    query=   3  returned_rows= 115  duration=   0.2 ms  result_same=true
join           query=   1  returned_rows=  50  duration=   0.1 ms  result_same=true
--- record count 100 ---
one by one     query= 201  returned_rows= 300  duration=   1.2 ms  result_same=true
batch fetch    query=   3  returned_rows= 165  duration=   0.2 ms  result_same=true
join           query=   1  returned_rows= 100  duration=   0.1 ms  result_same=true
--- record count 250 ---
one by one     query= 501  returned_rows= 750  duration=   2.6 ms  result_same=true
batch fetch    query=   3  returned_rows= 315  duration=   0.2 ms  result_same=true
join           query=   1  returned_rows= 250  duration=   0.1 ms  result_same=true
--- record count 500 ---
one by one     query=1001  returned_rows=1500  duration=   5.1 ms  result_same=true
batch fetch    query=   3  returned_rows= 565  duration=   0.4 ms  result_same=true
join           query=   1  returned_rows= 500  duration=   0.2 ms  result_same=true

Durations depend on the machine; query counts do not. In one-by-one loading, the count grows linearly with the record count. In batch fetch it stays at three; in join it stays at one. Staying constant is the property being sought: when the record count in a list doubles, the query count should not change.

The returned-row counts show a second distinction. Batch fetch returned 565 rows for five hundred records; join returned 500. In the first, loan records were read once and books and members were read de-duplicated; in the second, every row carries its own book and member columns, so the same book’s title is transferred over and over. This difference is the subject of the next lesson.

What the Local Measurement Hides

In the durations above, one-by-one loading took five milliseconds for five hundred records; that looks acceptable. This is a result of measuring against a local file.

The round trip discussed in the Connection Pool lesson becomes decisive here. If the database sits on a separate server, every query costs a network round trip. Assume just half a millisecond per round trip: 1001 queries come to more than 500 milliseconds, a single query to half a millisecond. This is not a measurement; it is a calculation made from the measured query count. What the calculation says is that query count is a cost that stays hidden in a local environment and surfaces in a real one.

For that reason, the performance metric is set as query count, not duration. Duration changes from environment to environment; query count is a property of the code.

Batch Fetch or Join

The choice between the two solutions depends on the shape of the data.

Join is a single query and returns the fewest rows; it is the right choice when the relations are one-to-one or one-to-few. In one-to-many relations, the result set multiplies: if every loan record has three tags, the row count triples and the loan columns repeat in every row.

Batch fetch adds a fixed number of extra queries but produces no multiplication. Every relation is read once, and the join happens in the application. When there are many one-to-many relations, this approach transfers less data.

Batch fetch has an implementation detail: the identifier list enters the query text as question marks. As the list grows, the text grows with it, and the engine’s bound-variable limit is approached. For that reason, identifiers are requested in chunks; as long as the chunk size stays fixed, the query count grows with a fixed division factor, not with the record count.

Turning the Budget into a Test

A query count that can be measured can be tested. The test below fails if the list goes over a given budget.

// budget.test.mjs — the query budget is written as a test
import { test } from "node:test";
import assert from "node:assert/strict";
import { countingConnection } from "./counter.mjs";

const BUDGET = 5;

function openLoanList(db, limit) {
  const records = db.many(
    "SELECT loan_id, book_id, member_id FROM loan WHERE return_date IS NULL ORDER BY loan_id LIMIT ?", limit);
  const bookIds = [...new Set(records.map((o) => o.book_id))];
  const memberIds = [...new Set(records.map((o) => o.member_id))];
  const bookLookup = new Map(db.many(
    `SELECT book_id, title FROM book WHERE book_id IN (${bookIds.map(() => "?").join(",")})`,
    ...bookIds).map((k) => [k.book_id, k.title]));
  const memberLookup = new Map(db.many(
    `SELECT member_id, first_name FROM member WHERE member_id IN (${memberIds.map(() => "?").join(",")})`,
    ...memberIds).map((u) => [u.member_id, u.first_name]));
  return records.map((o) => ({ id: o.loan_id, title: bookLookup.get(o.book_id), member: memberLookup.get(o.member_id) }));
}

for (const limit of [10, 100, 500]) {
  test(`open loan list for ${limit} records does not exceed the budget`, () => {
    const db = countingConnection("library.db");
    const list = openLoanList(db, limit);
    assert.equal(list.length, limit);
    assert.ok(db.counter.query <= BUDGET, `query count ${db.counter.query} > ${BUDGET}`);
  });
}

node --test budget.test.mjs

✔ open loan list for 10 records does not exceed the budget (0.722292ms)
✔ open loan list for 100 records does not exceed the budget (0.57875ms)
✔ open loan list for 500 records does not exceed the budget (0.475583ms)
ℹ tests 3
ℹ suites 0
ℹ pass 3
ℹ fail 0
ℹ cancelled 0
ℹ skipped 0
ℹ todo 0
ℹ duration_ms 36.655375

The value of the test is that it asks for the same budget at three different record counts. If someone makes a change that reverts to lazy loading, the five-hundred-record test goes over budget and the failure is reported together with the query count. This is the only automatic path that catches the N+1 problem slipping past code review.

Summary

• Once counted with the wrapper, query count became visible: for the same list, one-by-one loading ran 201 queries, batch fetch 3, join 1.
• In one-by-one loading, query count grows linearly with record count, reaching 1001 at five hundred records. It stayed constant in the other two approaches.
• The gap stays in the milliseconds in a local measurement; over a network, every query costs a round trip and the same gap grows into seconds. That is why the metric is query count, not duration.
• Join returns the fewest rows but multiplies the result in one-to-many relations; batch fetch produces no multiplication, in exchange for a fixed number of extra queries.
• Once the query budget is turned into a test, a regression to lazy loading is caught automatically.

Next Step

This lesson brought one number down and let another slip past. Batch fetch returned 565 rows for five hundred records, join 500 — but row count is not the measure of the data transferred. The queries asked only for the needed columns. In real applications, most queries ask for every column, most lists fetch more rows than needed, and the difference stays invisible until it is measured in bytes. The next lesson pulls the same list with different column sets, measures the transferred data in bytes, and shows the payoff of limiting at the field and row level.