Document Databases

The previous lesson closed with a single question: what would change if the store could see inside the value. The document database is exactly that change. A record is still named by a single key, but the store now recognizes the value’s fields: a condition can be written against a field, an index can be built on a field, and the field itself can be updated in place.

This lesson measures two things. The first is the gain: the difference between a nested book record arriving in a single read and the same record assembled by joining four relational tables. The second is the cost: fields not being enforced by a schema moves the check from write time to read time, and this move has a number attached to it.

The Document and the Collection

In the document model, a record is a document: a tree of named fields whose values may themselves be a document or an array. Documents are gathered into a collection. A collection is not a table, because the documents inside it are not required to carry the same fields; a document is not a row either, because a field is not required to be scalar.

These two relaxations have a direct consequence: multi-valued attributes that the relational model must spread across separate tables — a book’s authors, subjects, copies — stay inside the document. What first normal form forbids is the document model’s definition.

NS1: the catalog carries 50,000 books; book i has between 1 and 3 authors, between 2 and 4 subjects, and between 1 and 5 copies. NS2: the relational side is built with node:sqlite and every join column carries an index; bytes are counted from the same JSON representation on both sides.

// document/nesting.mjs — the same book record read from four relational tables and
// from a single document. The relational side is built with node:sqlite; the numbers
// are independent of the run.
import { DatabaseSync } from "node:sqlite";

const BOOKS = 50_000, AUTHORS = ["Atay", "Saramago", "Tanpinar", "Woolf", "Borges"];
const SUBJECTS = ["novel", "essay", "poetry", "history", "philosophy", "atlas"];
function* books() {                        // book i: 1+(i%3) authors, 2+(i%3) subjects, 1+(i%5) copies
  for (let i = 1; i <= BOOKS; i += 1) yield {
    book_id: i, title: `Book ${i}`,
    publication: { year: 1960 + (i % 65), language: i % 4 === 0 ? "en" : "tr" },
    authors: Array.from({ length: 1 + (i % 3) }, (_, j) => AUTHORS[(i + j) % 5]),
    subjects: Array.from({ length: 2 + (i % 3) }, (_, j) => SUBJECTS[(i * 2 + j) % 6]),
    copies: Array.from({ length: 1 + (i % 5) }, (_, j) => ({
      copy_id: i * 10 + j, branch_id: 1 + ((i + j) % 9), status: j % 3 === 0 ? "on_shelf" : "on_loan" })),
  };
}

const db = new DatabaseSync(":memory:");
db.exec(`CREATE TABLE book (book_id INTEGER PRIMARY KEY, title TEXT NOT NULL,
           publication_year INTEGER NOT NULL, language TEXT NOT NULL);
         CREATE TABLE book_author (book_id INTEGER NOT NULL, position INTEGER NOT NULL, name TEXT NOT NULL);
         CREATE TABLE book_subject (book_id INTEGER NOT NULL, subject TEXT NOT NULL);
         CREATE TABLE copy (copy_id INTEGER PRIMARY KEY, book_id INTEGER NOT NULL,
           branch_id INTEGER NOT NULL, status TEXT NOT NULL);`);
const insertBook = db.prepare("INSERT INTO book VALUES (?,?,?,?)");
const insertAuthor = db.prepare("INSERT INTO book_author VALUES (?,?,?)");
const insertSubject = db.prepare("INSERT INTO book_subject VALUES (?,?)");
const insertCopy = db.prepare("INSERT INTO copy VALUES (?,?,?,?)");
const collection = new Map();              // document collection: book_id -> document
db.exec("BEGIN");
for (const b of books()) {
  insertBook.run(b.book_id, b.title, b.publication.year, b.publication.language);
  b.authors.forEach((a, j) => insertAuthor.run(b.book_id, j, a));
  for (const t of b.subjects) insertSubject.run(b.book_id, t);
  for (const c of b.copies) insertCopy.run(c.copy_id, b.book_id, c.branch_id, c.status);
  collection.set(b.book_id, JSON.stringify(b));
}
db.exec("COMMIT");
db.exec(`CREATE INDEX author_idx ON book_author(book_id); CREATE INDEX subject_idx ON book_subject(book_id);
         CREATE INDEX copy_idx ON copy(book_id);`);

const bytes = (x) => Buffer.byteLength(JSON.stringify(x));
const TARGET = 4244;
const target = JSON.parse(collection.get(TARGET));
console.log(`target book ${TARGET}: ${target.authors.length} authors, ${target.subjects.length} subjects, ` +
  `${target.copies.length} copies; product ${target.authors.length * target.subjects.length * target.copies.length}`);

const rows = [];
{ let n = 0, by = 0;
  for (const s of ["SELECT * FROM book WHERE book_id = ?", "SELECT name FROM book_author WHERE book_id = ?",
                   "SELECT subject FROM book_subject WHERE book_id = ?", "SELECT * FROM copy WHERE book_id = ?"]) {
    const r = db.prepare(s).all(TARGET); n += r.length; by += bytes(r); }
  rows.push(["relational, four queries", 4, n, by]); }
{ const r = db.prepare(`SELECT k.title, k.publication_year, k.language, y.name, t.subject, n.branch_id, n.status
    FROM book k JOIN book_author y ON y.book_id = k.book_id
                JOIN book_subject t ON t.book_id = k.book_id
                JOIN copy        n ON n.book_id = k.book_id WHERE k.book_id = ?`).all(TARGET);
  rows.push(["relational, single join", 1, r.length, bytes(r)]); }
{ rows.push(["document, single read", 1, 1, Buffer.byteLength(collection.get(TARGET))]); }

console.log(`\n${"path".padEnd(28)}${"round trip".padStart(11)}${"row/document".padStart(14)}${"byte".padStart(7)}`);
for (const [a, g, k, y] of rows)
  console.log(a.padEnd(28) + String(g).padStart(11) + String(k).padStart(14) + String(y).padStart(7));

// Changing a single field on the same record: copy status "on_shelf" -> "on_loan"
const before = Buffer.byteLength(collection.get(TARGET));
const field = Buffer.byteLength(JSON.stringify({ status: "on_loan" }));
console.log(`\nsingle-field update (copy status)`);
console.log(`${"model".padEnd(28)}${"bytes written".padStart(14)}${"factor".padStart(8)}`);
console.log("relational, single row".padEnd(28) + String(field).padStart(14) + "1.0".padStart(8));
console.log("document, field in place".padEnd(28) + String(field).padStart(14) + "1.0".padStart(8));
console.log("key-value, whole value".padEnd(28) + String(before).padStart(14) +
  (before / field).toFixed(1).padStart(8));

target book 4244: 3 authors, 4 subjects, 5 copies; product 60

path                         round trip  row/document   byte
relational, four queries              4            13    552
relational, single join               1            60   7840
document, single read                 1             1    437

single-field update (copy status)
model                        bytes written  factor
relational, single row                  20     1.0
document, field in place                20     1.0
key-value, whole value                 437    21.9

The numbers are of the measurement class and are deterministic.

The top table shows the relational side’s real dilemma. Four separate queries bring back 13 rows and 552 bytes, but cost four round trips. Writing three joins to bring the round trips down to one produces a result of 60 rows: the product of three authors, four subjects, and five copies. The book’s title, publication year, and language repeat sixty times, and the bytes carried climb from 552 to 7,840 — fourteen times as much.

This is not a flaw in the join but its definition — a relational result set is a flat table, and when three independent multi-valued attributes are brought side by side on the same plane, the product is unavoidable.

On the document side, the same record is a single round trip, a single document, 437 bytes. There is no repetition, because the result is not flattened: authors stay an array, subjects stay an array, copies stay an array of documents. The tree the application wants is the tree that sits on disk.

The bottom table is the document side’s counterpart to the previous lesson’s write amplification measurement. Changing a copy’s status is 20 bytes of information. The relational engine updates a single row. The document database updates the field in place inside the document — because the store recognizes the field, it does not have to write the whole document back. In the key-value store, the same change means rewriting all 437 bytes of the value: a factor of 21.9. The document model keeps one end of the previous lesson’s trade-off — a wide value, a single read — and gets the other end, no write amplification paid, for free.

Schema Moves to the Read Side

This gain has a cost, and the cost is the schema itself. In a relational schema, NOT NULL is a write-time rule: a record without the field is rejected, and the reader never has to check whether the field exists. In a document collection there is no such rule; whether the field exists is asked on every read.

This is not a design flaw but the natural consequence of an application changing over time. Three schema versions written at different times sit side by side in the same collection: in the first version, the publication year is a top-level year field; in the second, it has moved into a publication subdocument; in the third, a digital field has been added as well. The question does not change — which books were published after 2000.

// document/schema.mjs — the load schema flexibility shifts onto the read side. Three
// schema versions coexist in the same collection; the same question is asked four
// ways. The relational side is built with node:sqlite.
import { DatabaseSync } from "node:sqlite";

const BOOKS = 50_000, THRESHOLD = 2000;
function version(i) { return i <= 20_000 ? 1 : i <= 40_000 ? 2 : 3; }
function document(i) {                     // v1: year at top level; v2: publication.year; v3: + digital
  const year = 1960 + (i % 65), common = { book_id: i, title: `Book ${i}` };
  if (version(i) === 1) return { ...common, year, language: i % 4 === 0 ? "en" : "tr" };
  const b = { ...common, publication: { year, language: i % 4 === 0 ? "en" : "tr" } };
  return version(i) === 3 ? { ...b, digital: i % 2 === 0 } : b;
}

class DocumentStore {
  #documents = []; #index = new Map();
  roundTrips = 0; scanned = 0;
  add(b) { this.#documents.push(b); }
  get(b, path) { return path.split(".").reduce((o, k) => (o == null ? undefined : o[k]), b); }
  buildIndex(path) { const entries = [];
    for (const b of this.#documents) { const v = this.get(b, path);
      if (v === undefined) continue;       // a document without the field never enters the index
      for (const x of Array.isArray(v) ? v : [v]) entries.push([x, b.book_id]); }
    this.#index.set(path, entries.sort((p, q) => p[0] - q[0])); return entries.length; }
  indexedGreaterThan(path, threshold) {     // in a sorted index, the suffix above the threshold is read
    this.roundTrips += 1; const entries = this.#index.get(path);
    let a = 0, u = entries.length;
    while (a < u) { const o = (a + u) >> 1; if (entries[o][0] <= threshold) a = o + 1; else u = o; }
    this.scanned += entries.length - a; return entries.slice(a).map(([, id]) => id); }
  scanGreaterThan(predicate) {              // no index: every document is checked one by one
    this.roundTrips += 1; const c = [];
    for (const b of this.#documents) { this.scanned += 1; if (predicate(b)) c.push(b.book_id); }
    return c; }
  reset() { this.roundTrips = 0; this.scanned = 0; }
}

const db = new DatabaseSync(":memory:");
db.exec(`CREATE TABLE book (book_id INTEGER PRIMARY KEY, title TEXT NOT NULL,
           publication_year INTEGER NOT NULL, language TEXT NOT NULL);`);
const insert = db.prepare("INSERT INTO book VALUES (?,?,?,?)");
const store = new DocumentStore();
db.exec("BEGIN");
for (let i = 1; i <= BOOKS; i += 1) {
  const b = document(i);
  insert.run(i, b.title, b.year ?? b.publication.year, b.language ?? b.publication.language);
  store.add(b);
}
db.exec("COMMIT");
db.exec("CREATE INDEX book_year ON book(publication_year);");
const idxPubYear = store.buildIndex("publication.year"), idxYear = store.buildIndex("year");
console.log(`${BOOKS} books, threshold ${THRESHOLD}; version distribution 1:20000 2:20000 3:10000`);
console.log(`index entry count — publication.year: ${idxPubYear}, year: ${idxYear}`);

const correct = db.prepare("SELECT book_id FROM book WHERE publication_year > ?").all(THRESHOLD).map((r) => r.book_id);
const rows = [];
rows.push(["relational, publication_year index", 1, correct.length, correct.length]);
store.reset(); let r = store.indexedGreaterThan("publication.year", THRESHOLD);
rows.push(["document, publication.year index", store.roundTrips, store.scanned, r.length]);
store.reset(); r = [...store.indexedGreaterThan("publication.year", THRESHOLD), ...store.indexedGreaterThan("year", THRESHOLD)];
rows.push(["document, union of two indexes", store.roundTrips, store.scanned, r.length]);
store.reset(); r = store.scanGreaterThan((b) => (b.publication?.year ?? b.year) > THRESHOLD);
rows.push(["document, defensive scan", store.roundTrips, store.scanned, r.length]);

console.log(`\n${"path".padEnd(37)}${"round trip".padStart(11)}${"entries scanned".padStart(16)}` +
  `${"result".padStart(8)}${"missing".padStart(9)}`);
for (const [a, g, t, n] of rows)
  console.log(a.padEnd(37) + String(g).padStart(11) + String(t).padStart(16) +
    String(n).padStart(8) + String(correct.length - n).padStart(9));

let rejected = 0, accepted = 0;            // 500 records without a year field
for (let i = BOOKS + 1; i <= BOOKS + 500; i += 1) {
  try { insert.run(i, `Book ${i}`, null, "tr"); } catch { rejected += 1; }
  store.add({ book_id: i, title: `Book ${i}` }); accepted += 1;
}
console.log(`\n500 records without a year field — relational rejected: ${rejected}, document collection accepted: ${accepted}`);
store.reset(); const after = store.scanGreaterThan((b) => (b.publication?.year ?? b.year) > THRESHOLD);
console.log(`defensive scan now visits ${store.scanned} documents, result ${after.length}`);

50000 books, threshold 2000; version distribution 1:20000 2:20000 3:10000
index entry count — publication.year: 30000, year: 20000

path                                  round trip entries scanned  result  missing
relational, publication_year index             1           18456   18456        0
document, publication.year index               1           11083   11083     7373
document, union of two indexes                 2           18456   18456        0
document, defensive scan                       1           50000   18456        0

500 records without a year field — relational rejected: 500, document collection accepted: 500
defensive scan now visits 50500 documents, result 18456

The second row is this lesson’s most expensive number. The query does not error, does not return empty, does not run slowly: it returns 11,083 results in a single round trip, and 7,373 books silently disappear. The reason lies in the definition of the index itself — a document without the publication.year field never enters the index, so for a query answered from the index, those documents do not exist. This cannot happen in a relational schema, because the absence of the field is rejected at write time; the last row confirms it: the same 500 incomplete records were rejected on the relational side and accepted into the document collection.

There are two paths to the correct result, and each has a cost. The union of two indexes gives the correct 18,456 records, but the round trips double, and it requires keeping a separate index for every schema version and the query author knowing every version. A defensive scan gives the correct answer in a single round trip, but it cannot use any index: because the condition chooses between two separate paths, it is not an indexable expression. Entries scanned climb from 18,456 to 50,000 — 2.7 times the result. After the 500 records with a missing field are added, the scan stretches to 50,500 documents; the result does not change.

The trade-off fits in one sentence: the document model does not remove schema checking, it moves it from write time to read time. The flexibility gained on the write side comes back on the read side as either a correctness gap, an index multiplication, or a scan. For this load to disappear entirely, the schema has to be put back into the collection; how that is done and what it costs is a later topic in this course.

Summary

• In the document model, a record is a tree whose fields may themselves be documents or arrays; a collection does not require documents to carry the same fields.
• The nested book record is 1 round trip and 437 bytes on the document side; on the relational side it is either 4 round trips and 552 bytes, or, with a single join, 60 rows and 7,840 bytes — the product of three multi-valued attributes.
• Updating the field in place writes 20 bytes; the same change in the key-value model means rewriting the whole value, a factor of 21.9.
• Schema flexibility moves the check to read time: in a three-version collection, a query answered from the publication.year index silently misses 7,373 records, while the relational schema rejects the same 500 incomplete records at write time.
• Both paths to the correct answer exact a cost: the union of two indexes raises the round trips to 2, and a defensive scan, unable to use an index, raises entries scanned from 18,456 to 50,000.

Next Step

So far, both families have treated the record as a single whole: the key-value store treated the value as an opaque whole, and the document database recognized the tree but still kept the whole document in one place. In both, all of a record’s fields sit side by side on disk, so a read for a single field also reads the location where the whole record lives. If a catalog record has forty fields and a query wants only two, the remaining thirty-eight pass through disk as well. The next lesson takes up the family that splits layout by field, and measures three things: the bytes the same query reads under column-family layout, what it means for thousands of columns to gather under a single key, and the cost an append-only write path — in place of in-place modification — exacts on deletion.