Indexing

The previous lesson’s three pipelines produced the same answer at three different costs, but shared one thing: all three read the entire collection, 20,000 documents, in their first stage. The stage order changed the records processed and the memory held, not the number of documents read. The only structure that changes that is the index.

The theory of indexing is not built here. The Relational Database Administration course’s Indexes and Partitioning topic measured tree, hash, and inverted indexes, column order, and the gain from a partial index; those numbers still hold here. This lesson’s question is the data the index is built over. A relational row’s indexed column carries a single value; in the document model the same field can be an array, can sit inside a nested document, or can be present in only a portion of the documents. All three cases change the number of index entries, and the entry count determines both size and write cost.

One Document, More Than One Entry

An index entry consists of a key value and a reference to the document carrying that value. In a relational index this relationship is one-to-one: one row produces one entry. When a path descends into an array, the relationship becomes one-to-many — a book with five copies produces five entries in the copy.branch index. This is called a multikey entry, the storage-side counterpart of the existential rule from the previous lesson: if a path reaches more than one value, the index must address every one of them separately.

When the same document produces the same key twice, the index holds a single entry; a book whose three copies are all at Kadikoy appears once in copy.branch. The implementation below carries all three decisions: multikey, compound key, and a partial condition.

// index.mjs — document index. When a path descends into an array, a single document
// produces more than one entry: a multikey entry. Compound keys, element-level keys, and
// a partial condition are all supported. Entry bytes come from lesson 01's encoding rule;
// every entry also carries an 8-byte reference to the document.
const REFERENCE = 8;

export function bytes(d) {
  if (d === null || d === undefined) return 0;
  if (typeof d === "boolean") return 1;
  if (typeof d === "number") return Number.isInteger(d) ? 4 : 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);
}

// Values at the path: if the path meets an array, it descends into its elements.
export function values(root, path) {
  let items = [root];
  for (const name of path.split(".")) {
    const next = [];
    for (const d of items)
      for (const o of Array.isArray(d) ? d : [d])
        if (o && typeof o === "object" && !Array.isArray(o) && name in o) next.push(o[name]);
    items = next;
  }
  return items.flatMap((v) => (Array.isArray(v) ? v : [v]));
}

export class Index {
  // fields: the paths that build the key. element: if given, the key is built over that
  // path's ELEMENT and the fields are relative to the element. condition: if given, only
  // a document or element that satisfies it enters the index -- a partial index.
  constructor(name, { fields, element = null, condition = null }) {
    Object.assign(this, { name, fields, element, condition });
    this.entries = new Map();                        // key -> array of document keys
    this.raw = 0;                                     // entries before deduplication
    this.scanned = 0;
  }
  keys(doc) {                                        // the keys one document generates
    const source = this.element
      ? values(doc, this.element).filter((o) => !this.condition || this.condition(o))
      : !this.condition || this.condition(doc) ? [doc] : [];
    const result = [];
    for (const k of source) {
      let product = [[]];
      for (const field of this.fields) {
        const d = values(k, field);
        product = product.flatMap((prefix) => (d.length ? d : [null]).map((v) => [...prefix, v]));
      }
      result.push(...product);
    }
    return result;
  }
  build(docs) {
    for (const b of docs) {
      const generated = this.keys(b).map((a) => JSON.stringify(a));
      this.raw += generated.length;
      for (const a of new Set(generated)) {           // the same key counts once per document
        if (!this.entries.has(a)) this.entries.set(a, []);
        this.entries.get(a).push(b._k);
      }
    }
    return this;
  }
  get count() {
    return [...this.entries.values()].reduce((t, v) => t + v.length, 0);
  }
  get bytes() {
    let n = 0;
    for (const [a, k] of this.entries)
      n += k.length * (JSON.parse(a).reduce((t, v) => t + bytes(v), 0) + REFERENCE);
    return n;
  }
  lookup(...key) {                                    // exact-key lookup
    const k = this.entries.get(JSON.stringify(key)) ?? [];
    this.scanned += k.length;
    return k;
  }
}

The element option carries the distinction specific to the document model. A compound index built with fields: ["copy.branch", "copy.status"] resolves the two paths separately and takes the product of their values; one built with element: "copy" instead builds the key inside each copy on its own. Both carry the same two fields and answer a different question.

Seven Indexes, One Catalog

NS7 (assumption): the catalog is 20,000 book documents, each book has 1–5 copies and 2–4 tags, and the seed is 424242. NS13 (assumption): an index entry carries, besides the encoded key value, an 8-byte document reference, and node occupancy counts as full. Rationale: reference width and occupancy vary by engine; neither changes the ratio between indexes, they only scale the absolute bytes.

The measured task is the previous two lessons’ question: books with a copy under repair at the Kadikoy branch, retrieved four ways, each counting the index entries scanned and the documents read. Then the second lesson’s third task, 5,000 copy status changes, runs under two index-maintenance decisions.

// index-measurement.mjs — seven indexes are built over the same catalog, the same
// question is answered four ways, and the index maintenance for 5,000 status changes is
// counted under two decisions.
// index.mjs is in the same directory.
import { Index, bytes } from "./index.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 TAGS = ["fiction", "history", "children", "poetry", "science", "reference"];

const CATALOG = [];
for (let i = 1; i <= 20000; i += 1) {
  const copy = [], tag = [];
  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)] });
  for (let j = 0, n = 2 + Math.floor(random() * 3); j < n; j += 1)
    tag.push(TAGS[Math.floor(random() * 6)]);
  CATALOG.push({ _k: `K-${String(i).padStart(5, "0")}`, author: `Author ${i % 4000}`,
    publication_year: 1950 + (i % 75), tag, copy });
}
const BY_KEY = new Map(CATALOG.map((b) => [b._k, b]));
const COLLECTION_BYTES = CATALOG.reduce((t, b) => t + bytes(b), 0);
const COPY_COUNT = CATALOG.reduce((t, b) => t + b.copy.length, 0);
console.log(`catalog ${CATALOG.length} documents, ${COPY_COUNT} copies, collection ${COLLECTION_BYTES} bytes`);

const [authorIdx, tagIdx, branchIdx, statusIdx, productIdx, elementIdx, partialIdx] = [
  new Index("author", { fields: ["author"] }),
  new Index("tag", { fields: ["tag"] }),
  new Index("copy.branch", { fields: ["copy.branch"] }),
  new Index("copy.status", { fields: ["copy.status"] }),
  new Index("tag + copy.branch", { fields: ["tag", "copy.branch"] }),
  new Index("element(branch,status)", { fields: ["branch", "status"], element: "copy" }),
  new Index("partial element(branch)", { fields: ["branch"], element: "copy",
    condition: (o) => o.status === "in_repair" }),
].map((d) => d.build(CATALOG));
const INDEXES = [authorIdx, tagIdx, branchIdx, statusIdx, productIdx, elementIdx, partialIdx];

for (const d of INDEXES)
  console.log(`${d.name.padEnd(23)} raw ${String(d.raw).padStart(6)}` +
    `  entries ${String(d.count).padStart(6)}  per document ${(d.count / 20000).toFixed(2)}` +
    `  ${String(d.bytes).padStart(7)} bytes  %${(100 * d.bytes / COLLECTION_BYTES).toFixed(1)} of collection`);

// Same question: books with a copy under repair at the Kadikoy branch.
const REPAIR = (k) => k.branch === "Kadikoy" && k.status === "in_repair";
const correct = CATALOG.filter((b) => b.copy.some(REPAIR)).length;
const countMatching = (keys) => keys.filter((k) => BY_KEY.get(k).copy.some(REPAIR)).length;
console.log(`copies satisfying the condition ${CATALOG.reduce((t, b) => t + b.copy.filter(REPAIR).length, 0)}` +
  `, documents carrying those copies ${correct}`);

const intersection = new Set(branchIdx.lookup("Kadikoy"));
const B = statusIdx.lookup("in_repair").filter((k) => intersection.has(k));
const C = elementIdx.lookup("Kadikoy", "in_repair");
const D = partialIdx.lookup("Kadikoy");
const paths = [
  ["A scan", 0, CATALOG.map((b) => b._k)],
  ["B two single-field indexes", branchIdx.scanned + statusIdx.scanned, B],
  ["C element-level compound", elementIdx.scanned, C],
  ["D partial element index", partialIdx.scanned, D],
];
for (const [label, scanned, keys] of paths)
  console.log(`${label.padEnd(28)} entries scanned ${String(scanned).padStart(6)}` +
    `  documents read ${String(keys.length).padStart(5)}  result ${countMatching(keys)}`);

// 5,000 copies change status: index maintenance counted under two decisions.
const keySet = (d, b) => [...new Set(d.keys(b).map((a) => JSON.stringify(a)))];
const diff = (a, b) => a.filter((v) => !b.includes(v)).length
  + b.filter((v) => !a.includes(v)).length;
let different = 0, full = 0, real = 0;
for (let i = 0; i < 5000; i += 1) {
  const book = CATALOG[(i * 7) % CATALOG.length];
  const target = book.copy[i % book.copy.length];
  const before = INDEXES.map((d) => keySet(d, book));
  if (target.status !== "shelved") real += 1;
  target.status = "shelved";
  const after = INDEXES.map((d) => keySet(d, book));
  for (let j = 0; j < INDEXES.length; j += 1) {
    different += diff(before[j], after[j]);
    full += before[j].length + after[j].length;
  }
}
console.log(`of 5,000 status changes, ${real} actually change the value`);
console.log(`  diff-based maintenance   ${different} entry writes`);
console.log(`  full document reindexing ${full} entry writes, ${(full / different).toFixed(1)}x`);

catalog 20000 documents, 59494 copies, collection 6983575 bytes
author                  raw  20000  entries  20000  per document 1.00   474450 bytes  %6.8 of collection
tag                     raw  59730  entries  50179  per document 2.51  1020851 bytes  %14.6 of collection
copy.branch             raw  59494  entries  47982  per document 2.40   984197 bytes  %14.1 of collection
copy.status             raw  59494  entries  38997  per document 1.95   857376 bytes  %12.3 of collection
tag + copy.branch       raw 177480  entries 120042  per document 6.00  3945348 bytes  %56.5 of collection
element(branch,status)  raw  59494  entries  55516  per document 2.78  1914334 bytes  %27.4 of collection
partial element(branch) raw  20021  entries  18752  per document 0.94   385051 bytes  %5.5 of collection
copies satisfying the condition 3508, documents carrying those copies 3340
A scan                       entries scanned      0  documents read 20000  result 3340
B two single-field indexes   entries scanned  21248  documents read  6033  result 3340
C element-level compound     entries scanned   3340  documents read  3340  result 3340
D partial element index      entries scanned   3340  documents read  3340  result 3340
of 5,000 status changes, 3311 actually change the value
  diff-based maintenance   10840 entry writes
  full document reindexing 173994 entry writes, 16.1x

The Cost of the Entry Count

The first lines give the source of index size. The author index produces exactly one entry per document and takes up 6.8% of the collection — the ratio of a relational index. The tag index produces 59,730 raw entries, and after deduplication 50,179 remain — 2.51 per document. The 9,551 entries in between come from the same tag being written twice in one book, collapsed to a single entry. Deduplication is even stronger in the copy.status index: 59,494 raw entries drop to 38,997, because on a three-valued field it is ordinary for several copies of one book to share the same status.

The fifth line is the lesson’s harshest number. When tag and copy.branch are combined into a single compound index, the entry count is not a sum but a product: 177,480 raw entries, 120,042 unique entries, six per document. The index takes 3,945,348 bytes, 56.5% of the collection. This is why engines block two array fields from sharing a compound index — the block prevents this product, it is not a convenience. Kept in two separate indexes, the same two fields total 98,161 entries and 2,005,048 bytes — just over half.

The Same-Element Condition

All four paths return the same 3,340 documents; where they differ is the documents read to reach that answer. The scan reads 20,000 documents. The intersection of the two single-field indexes scans 21,248 entries and reads 6,033 documents — exactly the third lesson’s document-level conjunction count. It intersects the set “has a copy at Kadikoy” with the set “has a copy under repair,” and it cannot confirm the conditions are satisfied by the same copy; that confirmation has to come from reading the document, which is why the 2,693 extra documents are read.

The element-level compound index does this work inside the index itself. Because the key is built from each copy’s own branch and status, the lookup ("Kadikoy", "in_repair") returns 3,340 document references directly, and entries scanned is also 3,340. Copies satisfying the condition number 3,508 — the 168 in between are a second copy under repair at the same branch of the same book, collapsed by the index to a single entry. Documents read drop to a sixth of the scan and to 1.8 times less than the index intersection, and every document read stays in the result.

Its cost is size: this index takes 1,914,334 bytes, 27.4% of the collection. The partial index gives the same answer far more cheaply. Copies with status equal to in_repair are 20,021 of the 59,494; an index covering only those takes 18,752 entries and 385,051 bytes, 5.5% of the collection, returning the same 3,340 documents by scanning the same number of entries. Its limit is that the condition it covers must appear in the query: this index says nothing about “shelved copies at Kadikoy,” because those copies are not in it.

The Cost of Writing

The last three lines are the other side of the index. 3,311 of the 5,000 copy status changes actually change the value. Maintenance that computes the changed keys and writes only those makes 10,840 entry writes across seven indexes — 2.17 per attempted change. Maintenance that does the same job by dropping and regenerating all of a document’s entries makes 173,994 entry writes, 16.1 times as many. The difference shares its root with the second lesson’s finding: in the embedded schema, changing one copy’s status rewrites the entire book, and regenerating every index entry of a rewritten document is the easiest implementation. A store that knows which field changed avoids the full 16-fold cost; one that does not sees the write cost grow linearly with the index count.

Looking at the share per index, the decision is clear: the seven indexes together take 9,581,607 bytes, 1.4 times the collection. In the document model, an index is charged not per field but per entry, and the schema itself determines that count.

Summary

• A path descending into an array makes a single document produce more than one index entry; copy.branch produces 59,494 raw entries from 20,000 documents, 47,982 after deduplication.
• Combining two array fields into one compound index does not add the entries, it multiplies them: 120,042 entries and 56.5% of the collection’s space.
• The intersection of two single-field indexes cannot confirm that the conditions are satisfied by the same element; it reads 6,033 documents, and 2,693 of them do not stay in the result.
• The element-level compound index gives the same answer by scanning 3,340 entries and reading 3,340 documents; the partial index gives the same answer while taking up 5.5% of the collection instead of 27.4%.
• Maintenance that computes the changed key spends 10,840 entry writes on 5,000 updates; maintenance that fully reindexes the document spends 173,994 (16.1×).

Next Step

Every index in this lesson was built over fields that already existed, and none of them looked at what those fields carry. The copy.status index would just as quietly index a copy written as repair instead of in_repair; the publication years written as text that the first lesson measured also enter the publication_year index under their own type. A flexible schema does not bind whether a field is present, or its type, at write time — the first lesson counted this returning 5,991 or 3,491 documents instead of 3,990 in a range query, and left the question of how to place a rule to this topic. The next lesson writes that rule and measures two numbers: the broken-document classes it catches versus the ones it misses, and the violation count on an already-full collection against the documents a backfill touches.