Embedding and Referencing

The previous lesson looked inside a single document: the byte cost of a field name and a type tag was counted, and writing the same field in two types was shown to return 3,491 or 5,991 documents instead of 3,990 in a range query. The catalog, however, is not just one document. Book, copy, member, and loan records are linked to each other, and the document model allows that link to be built in two ways.

Embedding puts the related data inside the document, as a nested document or an array. Referencing keeps the data in a separate collection and carries only its key in the document. Both store the same catalog; where they part ways is how many round trips a read path takes, how many bytes are read, how many documents a single update rewrites, and how large the document grows. This lesson produces those four numbers. The arithmetic of normalization and denormalization was measured in the Data Modeling and Relational Theory and Scaling the Data Layer courses; it is not repeated here — what is measured here is the side that is specific to the document model.

A Store That Counts

A small document store is written for the measurement. The store holds collections, separates key access from full scans, and counts a round trip, the number of documents read, and the bytes read on every access. There is also a document size limit: a write that exceeds it is rejected. The equality map exists only to keep the comparison fair; the index’s own arithmetic is this topic’s fifth lesson’s subject.

// document-store.mjs — a small document store: collections, key access, scans, equality
// mapping, and a document size limit. Every access is counted as a round trip, documents
// read, and bytes read.

// The byte rule from lesson 01's encoding: fixed-length types take their size from the
// tag, variable-length types carry a 4-byte length prefix, every field is 1 byte tag + name + NUL.
export function bytes(d) {
  if (d === null) return 0;
  if (typeof d === "boolean") return 1;
  if (typeof d === "number") return Number.isInteger(d) ? 4 : 8;
  if (d instanceof Date) return 8;
  if (typeof d === "string") return 4 + Buffer.byteLength(d) + 1;
  const item = Array.isArray(d) ? d.map((v, i) => [String(i), v]) : Object.entries(d);
  return 5 + item.reduce((t, [a, v]) => t + 2 + Buffer.byteLength(a) + bytes(v), 0);
}

export class Store {
  constructor(limit = 16384) {
    this.collection = new Map();
    this.index = new Map();
    this.limit = limit;
    this.reset();
  }
  reset() {
    this.o = { roundTrips: 0, documentsRead: 0, bytesRead: 0, documentsWritten: 0, bytesWritten: 0 };
  }
  c(name) {
    if (!this.collection.has(name)) this.collection.set(name, new Map());
    return this.collection.get(name);
  }
  write(name, doc) {
    const n = bytes(doc);
    if (n > this.limit) throw new Error(`document size limit exceeded: ${n} > ${this.limit}`);
    this.c(name).set(doc._k, doc);
    this.o.documentsWritten += 1;
    this.o.bytesWritten += n;
    return n;
  }
  read(b) {
    this.o.documentsRead += 1;
    this.o.bytesRead += bytes(b);
    return b;
  }
  find(name, k) {                                // key access: one round trip, one document
    this.o.roundTrips += 1;
    const b = this.c(name).get(k);
    return b ? this.read(b) : undefined;
  }
  scan(name, condition) {                         // full scan: the whole collection is read
    this.o.roundTrips += 1;
    return [...this.c(name).values()].filter((b) => condition(this.read(b)));
  }
  equalityMap(name, field) {                      // index arithmetic is lesson 05's topic
    const m = new Map();
    for (const b of this.c(name).values()) {
      const v = b[field];
      if (!m.has(v)) m.set(v, []);
      m.get(v).push(b._k);
    }
    this.index.set(`${name}.${field}`, m);
  }
  lookup(name, field, value) {
    this.o.roundTrips += 1;
    const keys = this.index.get(`${name}.${field}`).get(value) ?? [];
    return keys.map((k) => this.read(this.c(name).get(k)));
  }
}

Three Tasks, Two Schemas

NS7 (assumption): the catalog holds 20,000 books, each book has 1–5 copies, and the seed is 424242. NS9 (assumption): the library has three tasks — opening a book page (one book and all of its copies), listing the copies under repair at one branch, and changing one copy’s status. All three run in both schemas.

// embed-reference.mjs — the same catalog is built in two schemas: copies embedded in the
// book, or referenced in a separate collection. Three tasks run in both schemas and the
// difference is counted.
// document-store.mjs is in the same directory.
import { Store, bytes } from "./document-store.mjs";

let seed = 424242;                                        // visible seed
const random = () => (seed = (seed * 1103515245 + 12345) % 2147483648) / 2147483648;
const BRANCH = ["Central", "Bahcelievler", "Kadikoy", "Beyoglu", "Konak", "Nilufer"];
const STATUS = ["shelved", "checked_out", "in_repair"];
const N = 20000;

const raw = [];
for (let i = 1; i <= N; i += 1) {
  const copy = [];
  for (let j = 0, n = 1 + Math.floor(random() * 5); j < n; j += 1)
    copy.push({ barcode: `B${String(i * 10 + j).padStart(7, "0")}`,
      branch: BRANCH[Math.floor(random() * 6)],
      status: STATUS[Math.floor(random() * 3)] });
  raw.push({ _k: `K-${String(i).padStart(5, "0")}`, title: `Studies on Book ${i}`,
    author: `Author ${i % 4000}`, publication_year: 1950 + (i % 75), copy });
}
const COPY_COUNT = raw.reduce((t, b) => t + b.copy.length, 0);

const embedded = new Store();
for (const b of raw) embedded.write("book", b);
const referenced = new Store();
for (const b of raw) {
  referenced.write("book", { _k: b._k, title: b.title, author: b.author, publication_year: b.publication_year });
  for (const k of b.copy)
    referenced.write("copy", { _k: k.barcode, book: b._k, branch: k.branch, status: k.status });
}
referenced.equalityMap("copy", "book");
referenced.equalityMap("copy", "branch");

const report = (label, o) => console.log(`${label.padEnd(26)} round trips ${String(o.roundTrips).padStart(2)}` +
  `  documents read ${String(o.documentsRead).padStart(6)}  bytes read ${String(o.bytesRead).padStart(8)}`);

console.log(`books ${N}, copies ${COPY_COUNT} (per book ${(COPY_COUNT / N).toFixed(2)})`);
console.log(`collection size: embedded book ${[...embedded.c("book").values()].reduce((t, b) => t + bytes(b), 0)}` +
  `  referenced book+copy ${[...referenced.c("book").values()].reduce((t, b) => t + bytes(b), 0)
  + [...referenced.c("copy").values()].reduce((t, b) => t + bytes(b), 0)}`);

// TASK 1 — book page: one book and all of its copies.
embedded.reset(); referenced.reset();
embedded.find("book", "K-04242");
report("task1 embedded", embedded.o);
referenced.find("book", "K-04242");
referenced.lookup("copy", "book", "K-04242");
report("task1 referenced", referenced.o);

// TASK 2 — copies under repair at one branch.
embedded.reset(); referenced.reset();
const t2e = embedded.scan("book", (b) => b.copy.some((k) => k.branch === "Kadikoy" && k.status === "in_repair"));
report("task2 embedded", embedded.o);
const t2r = referenced.lookup("copy", "branch", "Kadikoy").filter((k) => k.status === "in_repair");
report("task2 referenced", referenced.o);
console.log(`task2 result: embedded ${t2e.length} book documents, referenced ${t2r.length} copy documents`);

// TASK 3 — 5,000 copies change status.
embedded.reset(); referenced.reset();
for (let i = 0; i < 5000; i += 1) {
  const book = raw[(i * 7) % N];
  const target = book.copy[i % book.copy.length];
  const e = embedded.find("book", book._k);
  e.copy.find((k) => k.barcode === target.barcode).status = "shelved";
  embedded.write("book", e);
  const r = referenced.find("copy", target.barcode);
  referenced.write("copy", { ...r, status: "shelved" });
}
console.log(`task3 embedded    documents written ${embedded.o.documentsWritten}  bytes written ${embedded.o.bytesWritten}`);
console.log(`task3 referenced  documents written ${referenced.o.documentsWritten}  bytes written ${referenced.o.bytesWritten}`);

books 20000, copies 58595 (per book 2.93)
collection size: embedded book 6450690  referenced book+copy 6816640
task1 embedded             round trips  1  documents read      1  bytes read      478
task1 referenced           round trips  2  documents read      6  bytes read      517
task2 embedded             round trips  1  documents read  20000  bytes read  6450690
task2 referenced           round trips  1  documents read  10066  bytes read   825072
task2 result: embedded 2934 book documents, referenced 3092 copy documents
task3 embedded    documents written 5000  bytes written 1616741
task3 referenced  documents written 5000  bytes written 402224

The three tasks point in three different directions. Embedding wins on the book page: a single round trip reads 478 bytes, while the referenced schema gathers the same information across two round trips and six documents, reading 517 bytes. The difference is small on the byte side (8.2%) and doubled on the round-trip side — and a round trip, for an application connecting to the store remotely, is a more expensive unit than a byte.

The branch query flips the direction. In the embedded schema, the copy is inside the book; finding one branch’s copies reads all 20,000 book documents, 6,450,690 bytes. In the referenced schema, the copy has its own collection and can be mapped by branch: 10,066 documents, 825,072 bytes. The bytes read for the same question fall by a factor of 7.8. The two results carrying different counts is also instructive: the embedded scan returns 2,934 books, the referenced query returns 3,092 copies — the same book can have two copies under repair at the same branch, and in the embedded schema that distinction stays inside the document.

The write path gives the third direction. When a copy’s status changes, the embedded schema rewrites the entire book: 5,000 changes write 1,616,741 bytes, 323 bytes per change. The referenced schema rewrites only the copy document: 402,224 bytes, 80 bytes per change. The ratio is 4.02, and it grows as the book’s field count grows, because every field next to the one that changed gets rewritten too. On the stored-space side the decision runs the other way: the referenced schema takes 6,816,640 bytes, the embedded schema 6,450,690 — the difference is that every copy document carries its own key and the book’s key over again.

An Array That Grows Without Bound

The most expensive form of embedding is embedding an array with no end. Loan history is exactly that: the book stays fixed, the history keeps growing. NS10 (assumption): the store’s document size limit is 16,384 bytes. NS11 (assumption): 1,406,280 loans are issued over three years, and the distribution is Zipf-shaped — the share of the book at rank r is proportional to 1/r.

// growth.mjs — embedding loan history in the book document makes it grow. The decision to
// embed without limit is compared with the decision to embed only the last 20 records and
// leave the rest in a separate collection.
// document-store.mjs is in the same directory.
import { Store, bytes } from "./document-store.mjs";

const LIMIT = 16384, N = 20000, LOANS = 1406280, TAIL = 20;
const base = (i) => ({ _k: `K-${String(i).padStart(5, "0")}`,
  title: `Studies on Book ${i}`, author: `Author ${i % 4000}`,
  publication_year: 1950 + (i % 75), loan: [] });
const record = (n) => ({ member: `U-${String(n % 90000).padStart(5, "0")}`,
  checkedOut: new Date(2023, 0, 1 + (n % 1095)), due: new Date(2023, 0, 15 + (n % 1095)) });

// Zipf distribution: the share of the book at rank r is proportional to 1/r. No randomness.
const H = Array.from({ length: N }, (_, i) => 1 / (i + 1)).reduce((a, b) => a + b);
const share = Array.from({ length: N }, (_, i) => Math.round(LOANS / ((i + 1) * H)));
const emptyDoc = bytes(base(1));
const perRecord = bytes({ ...base(1), loan: [record(1)] }) - emptyDoc;
const collectionBytes = (d) => [...d.values()].reduce((t, b) => t + bytes(b), 0);
console.log(`empty book document ${emptyDoc} bytes, one loan record ${perRecord} bytes`);
console.log(`limit ${LIMIT} bytes, rough estimate: ${Math.floor((LIMIT - emptyDoc) / perRecord)} records`);

// Decision A: the entire history is embedded. Size is tracked incrementally; the nth
// element adds 2 + the length of the index name + the record's bytes to the array.
const storeA = new Store(LIMIT);
let capped = 0, first = null, dropped = 0;
for (let i = 1; i <= N; i += 1) {
  const b = base(i);
  let size = emptyDoc, fit = 0;
  for (let n = 0; n < share[i - 1]; n += 1) {
    const add = String(n).length + perRecord - 1;
    if (size + add > LIMIT) break;
    size += add;
    b.loan.push(record(n));
    fit += 1;
  }
  if (fit < share[i - 1]) {
    capped += 1;
    dropped += share[i - 1] - fit;
    first ??= { rank: i, records: fit, size: bytes(b), wanted: share[i - 1] };
  }
  storeA.write("book", b);
}
console.log(`A unlimited embedding: books hitting the cap ${capped}, loan records that do not fit ${dropped}`);
console.log(`  first capped book, rank ${first.rank}: ${first.records} records ${first.size} bytes, wanted ${first.wanted}`);
console.log(`  book collection ${collectionBytes(storeA.c("book"))} bytes`);

// Decision B: the last 20 records are embedded, the rest stay in the loan collection.
const storeB = new Store(LIMIT);
for (let i = 1; i <= N; i += 1) {
  const b = base(i);
  for (let n = Math.max(0, share[i - 1] - TAIL); n < share[i - 1]; n += 1) b.loan.push(record(n));
  storeB.write("book", b);
}
const largest = Math.max(...[...storeB.c("book").values()].map(bytes));
console.log(`B last ${TAIL} records embedded: largest document ${largest} bytes, distance to limit ${LIMIT - largest}`);
console.log(`  book collection ${collectionBytes(storeB.c("book"))} bytes, records remaining in the separate collection ` +
  `${share.reduce((t, p) => t + Math.max(0, p - TAIL), 0)}`);

empty book document 104 bytes, one loan record 61 bytes
limit 16384 bytes, rough estimate: 266 records
A unlimited embedding: books hitting the cap 515, loan records that do not fit 781509
  first capped book, rank 1: 260 records 16374 bytes, wanted 134178
  book collection 40880034 bytes
B last 20 records embedded: largest document 1340 bytes, distance to limit 15044
  book collection 19422356 bytes, records remaining in the separate collection 1125534

The rough estimate says 266 records, but only 260 actually fit. The gap of 6 records comes from the array’s own field names: past the tenth element the index name grows by a digit, and every element beyond that point costs one byte more. This is a consequence of the previous lesson’s finding — even inside an array, the field name is stored.

The real number is in the second line. 515 of the 20,000 books hit the limit within three years, and 781,509 loan records cannot be written into the document. The most-borrowed book wants 134,178 records and can hold only 260 of them. The limit is not a performance problem, it is a data-loss problem: the embedding decision quietly runs into an irreversible limit here. The second decision removes the limit — the last 20 records are embedded, and the rest stay in a separate collection. The largest book document drops to 1,340 bytes, leaving 15,044 bytes of distance to the limit, and 1,125,534 records move to the separate collection. The book page still shows the last 20 loans in a single round trip; a screen that wants the full history pays for a second round trip.

The rule for the decision follows from these three measurements: data that is read together and changed together is embedded; data that is queried separately or grows without bound is kept by reference. Sentences like “more flexible” or “more natural” do not carry this decision; what carries it is the round-trip count, the bytes read, the bytes rewritten, and the distance to the limit.

Summary

• Embedding puts the related data inside the document, referencing keeps it in a separate collection and carries its key; both store the same catalog at a different access cost.
• The book page takes 1 round trip and 478 bytes in the embedded schema, 2 round trips and 517 bytes in the referenced schema; the gain is in round trips, not bytes.
• The branch query reads 20,000 documents and 6,450,690 bytes in the embedded schema, 10,066 documents and 825,072 bytes in the referenced schema; the ratio is 7.8×.
• A copy’s status change rewrites the entire book in the embedded schema: 5,000 changes write 1,616,741 bytes, versus 402,224 bytes in the referenced schema (a ratio of 4.02).
• An array that grows without bound runs into the document size limit: 515 of 20,000 books exceed it and 781,509 loan records cannot be written; embedding only the last 20 records brings the largest document down to 1,340 bytes.

Next Step

The two decisions that build the schema have been counted; next comes asking questions of that schema. In this lesson, the branch query ran through a hand-written condition function, but a store evaluates the condition itself, using a set of operators: comparison, logical connectives, and array operators. Array operators carry an ambiguity that surfaced in this lesson — when an embedded copy array is asked two conditions at once, whether the conditions must be satisfied by the same element or by any two elements of the document is two different answers to the same query. The next lesson builds the operators in their own evaluator and counts that difference.