Document Data Types

The previous topic closed with selection criteria and left an unfinished decision behind it: the work does not end once an access pattern points to a family. Choosing a family is not choosing a schema. The document model allows very different schemas to be built for the same domain, and that permission is not free.

This topic counts that cost, and the first question starts at the bottom. In a relational table, a field’s name and type are written once in the table definition, and the row holds only the value. The document model has no such definition: every record carries its own field names and types. This lesson’s two measures are exactly that — the space that carrying takes in bytes, and the difference that writing the same field in two different types produces in a range query.

Self-Describing Record

A document is an ordered list of named fields; a field’s value can be a number or text, but it can also be a nested document or an array. Documents sit inside a collection. The store saves this structure as a binary document representation: every field starts with a type tag, writes its name up to a terminating byte, then places the value in the form the type requires. This representation is called self-describing; decoding a record needs no external schema.

The representation follows three rules. Fixed-length types (integer, decimal, boolean, date) carry no length; their size is known from the tag. Variable-length types (text, nested document, array) write their own length with a four-byte prefix, so a reader can skip a field it does not care about without decoding it. An array is an inner document whose field names run "0", "1", and so on — the array’s element count is carried through those names as well.

// binary-document.mjs — self-describing binary document representation.
// Encoding: [4-byte length] (type tag + field name + NUL + value)* [0x00]
export const TAG = { null: 0x0a, int32: 0x10, decimal: 0x01, text: 0x02,
  document: 0x03, array: 0x04, boolean: 0x08, date: 0x09 };
const ORDER = ["null", "int32", "decimal", "text", "document", "array", "boolean", "date"];

export function typeName(d) {
  if (d === null) return "null";
  if (Array.isArray(d)) return "array";
  if (d instanceof Date) return "date";
  if (typeof d === "boolean") return "boolean";
  if (typeof d === "number") return Number.isInteger(d) ? "int32" : "decimal";
  return typeof d === "string" ? "text" : "document";
}

export function encode(doc, s = { name: 0, tag: 0, length: 0, value: 0 }) {
  const parts = [];
  for (const [name, d] of Object.entries(doc)) {
    parts.push(Buffer.from([TAG[typeName(d)]]), Buffer.from(name + "\0", "utf8"), value(d, s));
    s.tag += 1;
    s.name += Buffer.byteLength(name) + 1;
  }
  const body = Buffer.concat([...parts, Buffer.from([0])]);
  const header = Buffer.alloc(4);
  header.writeInt32LE(body.length + 4);
  s.length += 4;
  s.value += 1;                                  // closing NUL
  return Buffer.concat([header, body]);
}

function value(d, s) {
  const t = typeName(d), n = { null: 0, boolean: 1, int32: 4, decimal: 8, date: 8 }[t];
  if (n !== undefined) {
    s.value += n;
    const b = Buffer.alloc(n);
    if (t === "boolean") b[0] = d ? 1 : 0;
    if (t === "int32") b.writeInt32LE(d);
    if (t === "decimal") b.writeDoubleLE(d);
    if (t === "date") b.writeBigInt64LE(BigInt(d.getTime()));
    return b;
  }
  if (t === "text") {
    const m = Buffer.from(d + "\0", "utf8"), b = Buffer.alloc(4);
    b.writeInt32LE(m.length);
    s.length += 4;
    s.value += m.length;
    return Buffer.concat([b, m]);
  }
  return encode(t === "array" ? { ...d } : d, s);   // array: field names "0","1",...
}

export function decode(t, offset = 0) {
  const end = offset + t.readInt32LE(offset), result = {};
  let i = offset + 4;
  while (i < end - 1) {
    const tag = t[i], stop = t.indexOf(0, i + 1), name = t.toString("utf8", i + 1, stop);
    i = stop + 1;
    if (tag === TAG.null) result[name] = null;
    else if (tag === TAG.boolean) result[name] = t[i++] === 1;
    else if (tag === TAG.int32) { result[name] = t.readInt32LE(i); i += 4; }
    else if (tag === TAG.decimal) { result[name] = t.readDoubleLE(i); i += 8; }
    else if (tag === TAG.date) { result[name] = new Date(Number(t.readBigInt64LE(i))); i += 8; }
    else if (tag === TAG.text) {
      const n = t.readInt32LE(i);
      result[name] = t.toString("utf8", i + 4, i + 3 + n);
      i += 4 + n;
    } else {
      const inner = decode(t, i);
      result[name] = tag === TAG.array ? Object.values(inner) : inner;
      i += t.readInt32LE(i);
    }
  }
  return result;
}

// Ordering looks at type first, then value: type order.
export function compare(a, b) {
  const f = ORDER.indexOf(typeName(a)) - ORDER.indexOf(typeName(b));
  if (f !== 0) return f;
  if (a === null) return 0;
  if (a instanceof Date) return a.getTime() - b.getTime();
  return a < b ? -1 : a > b ? 1 : 0;
}

The Byte Cost of a Name

The measurement builds the previous courses’ library catalog in document form. NS7 (assumption): the catalog holds 20,000 book documents; each book has 1–5 copies and 2–4 tags, and the generation seed is 424242. The same data is encoded under three decisions: field names are written out in full, field names are shortened, or the names and types are stripped from the record and moved to a fixed schema. The third is what a relational row does, and it stands here as the comparison baseline.

// field-cost.mjs — the same 20,000 book documents are encoded in two schemas: open field
// names and short field names. The same data is also encoded, as a third decision, in a
// fixed-schema row.
// binary-document.mjs is in the same directory.
import { encode, decode } from "./binary-document.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"];

function books(n) {
  const result = [];
  for (let i = 1; i <= n; i += 1) {
    const copyCount = 1 + Math.floor(random() * 5);
    const copy = [];
    for (let j = 0; j < copyCount; j += 1)
      copy.push({ barcode: `B${String(i * 10 + j).padStart(7, "0")}`,
        branch: BRANCH[Math.floor(random() * BRANCH.length)],
        status: STATUS[Math.floor(random() * STATUS.length)] });
    const tagCount = 2 + Math.floor(random() * 3);
    const tag = [];
    for (let j = 0; j < tagCount; j += 1) tag.push(TAGS[Math.floor(random() * 6)]);
    result.push({ key: `K-${String(i).padStart(5, "0")}`,
      title: `Studies on Book ${i}`, author: `Author ${i % 4000}`,
      publication_year: 1950 + (i % 75), tag, copy });
  }
  return result;
}

const SHORT = { key: "_k", title: "t", author: "a", publication_year: "py",
  tag: "tg", copy: "c", barcode: "bc", branch: "br", status: "st" };
const shorten = (b) => Object.fromEntries(Object.entries(b).map(([a, d]) => [SHORT[a] ?? a,
  Array.isArray(d) ? d.map((x) => (typeof x === "object" ? shorten(x) : x)) : d]));

const RECORDS = books(20000);
const measure = (set) => {
  const s = { tag: 0, name: 0, length: 0, value: 0 };
  let bytes = 0;
  for (const b of set) bytes += encode(b, s).length;
  return { bytes, ...s };
};
const open = measure(RECORDS), short = measure(RECORDS.map(shorten));

// Fixed-schema row: type and field name sit once in the schema, the record carries only the value.
function fixedSchema(set) {
  let bytes = 0;
  for (const b of set) {
    bytes += 4;                                          // publication_year: int32
    for (const field of ["key", "title", "author"]) bytes += 2 + Buffer.byteLength(b[field]);
    bytes += 2 + b.tag.reduce((t, e) => t + 1 + Buffer.byteLength(e), 0);
    bytes += 2;
    for (const c of b.copy)
      bytes += 2 + Buffer.byteLength(c.barcode) + 1 + Buffer.byteLength(c.branch)
        + 1 + Buffer.byteLength(c.status);
  }
  return bytes;
}
const fixed = fixedSchema(RECORDS);
const fields = RECORDS.reduce((t, b) => t + 6 + b.tag.length + b.copy.length * 4, 0);

console.log(`document count                 ${RECORDS.length}`);
console.log(`total fields (nested included) ${fields}`);
console.log(`open field names    ${open.bytes} bytes   per document ${(open.bytes / 20000).toFixed(1)}`);
console.log(`short field names   ${short.bytes} bytes   per document ${(short.bytes / 20000).toFixed(1)}`);
console.log(`fixed-schema row    ${fixed} bytes   per document ${(fixed / 20000).toFixed(1)}`);
console.log(`open-schema byte breakdown: name ${open.name}  type tag ${open.tag}  ` +
  `length field ${open.length}  value ${open.value}`);
console.log(`self-description share  open %${(100 * (open.bytes - fixed) / open.bytes).toFixed(1)}` +
  `   short %${(100 * (short.bytes - fixed) / short.bytes).toFixed(1)}`);

const first = encode(RECORDS[0]);
console.log(`first document ${first.length} bytes, decoded first copy: ` +
  JSON.stringify(decode(first).copy[0]));

document count                 20000
total fields (nested included) 417706
open field names    7652469 bytes   per document 382.6
short field names   6319047 bytes   per document 316.0
fixed-schema row    3236623 bytes   per document 161.8
open-schema byte breakdown: name 2407316  type tag 417706  length field 1670824  value 3156623
self-description share  open %57.7   short %48.8
first document 518 bytes, decoded first copy: {"barcode":"B0000010","branch":"Beyoglu","status":"shelved"}

The measurement runs over 417,706 fields — a book document carries 20.9 fields on average, because every copy and every tag is its own field. The open-named representation takes 7,652,469 bytes, the fixed-schema row 3,236,623 bytes. The difference is 4,415,846 bytes, and it is not the data itself but the data describing itself: 2,407,316 bytes go to field names, 417,706 bytes to type tags, 1,670,824 bytes to length prefixes. The arithmetic: of every three bytes stored in the open representation, close to two (57.7%) are not data but definition.

Shortening brings that share down to 48.8%. The 1,333,422-byte difference comes purely from shortening the field names — 66.7 bytes per document, which scales out to around 1.3 MB across 20,000 documents. The flip side of the decision can also be counted: a short-named document, read on its own, does not say that the bc field is the barcode — that information now lives in the application, not the store. Self-description is exactly that information staying in the record, and its cost has now been measured.

The Same Field in Two Types

The counterpart of carrying type in the record is that the same field can be a different type in two documents. A relational schema blocks this at definition time; the document model has no such block, and the absence of one shows up on the query side. NS8 (assumption): in one out of every eight records taken from an external source, the publication year is written as text — "2010" instead of 2010.

What a range query does with these documents depends on the operator’s semantics, and there are two options. Type ordering compares values of different types as well: types are ordered first, and values are ordered only when the type is equal. Type bracketing applies the comparison only to values of the same type as the operator’s right-hand side; every other value fails to match.

// type-mixing.mjs — the same field in two types: publication_year is an integer for part
// of the records, text for another part. The same range is counted under two operator
// semantics.
// binary-document.mjs is in the same directory.
import { compare, typeName, encode } from "./binary-document.mjs";

const N = 20000;
const items = [];
for (let i = 1; i <= N; i += 1) {
  const year = 1950 + (i % 75);
  items.push({ key: `K-${String(i).padStart(5, "0")}`,
    publication_year: i % 8 === 0 ? String(year) : year });    // every eighth document writes text
}
const asText = items.filter((b) => typeName(b.publication_year) === "text").length;

// Decision A: comparison uses type ordering (the total order in sorting).
const A = (b, d, dir) => (dir === "ge" ? compare(b.publication_year, d) >= 0 : compare(b.publication_year, d) < 0);
// Decision B: comparison applies type bracketing, a value of a different type never matches.
const B = (b, d, dir) => typeName(b.publication_year) === typeName(d) && A(b, d, dir);
const count = (f, d, dir) => items.filter((b) => f(b, d, dir)).length;

console.log(`documents ${N}, publication_year as text ${asText} (%${(100 * asText / N).toFixed(1)})`);
console.log(`A type ordering    >= 2010 -> ${count(A, 2010, "ge")}   < 2010 -> ${count(A, 2010, "lt")}` +
  `   total ${count(A, 2010, "ge") + count(A, 2010, "lt")}`);
console.log(`B type bracketing  >= 2010 -> ${count(B, 2010, "ge")}   < 2010 -> ${count(B, 2010, "lt")}` +
  `   total ${count(B, 2010, "ge") + count(B, 2010, "lt")}`);
console.log(`single-typed schema >= 2010 -> ` +
  `${items.filter((b) => Number(b.publication_year) >= 2010).length}`);
console.log(`documents B places in neither side ${N - count(B, 2010, "ge") - count(B, 2010, "lt")}`);
console.log(`B, when the operand is text: >= "2010" -> ${count(B, "2010", "ge")}`);

// Sorting always uses the total order: the result clumps by type.
const sorted = [...items].sort((a, b) => compare(a.publication_year, b.publication_year));
const boundary = sorted.findIndex((b) => typeName(b.publication_year) === "text");
console.log(`first text value at position ${boundary}: ${JSON.stringify(sorted[boundary].publication_year)}` +
  `, previous ${JSON.stringify(sorted[boundary - 1].publication_year)}`);

const bytes = (d) => encode({ publication_year: d }).length;
console.log(`single-field document: integer ${bytes(2010)} bytes, text ${bytes("2010")} bytes`);

documents 20000, publication_year as text 2500 (%12.5)
A type ordering    >= 2010 -> 5991   < 2010 -> 14009   total 20000
B type bracketing  >= 2010 -> 3491   < 2010 -> 14009   total 17500
single-typed schema >= 2010 -> 3990
documents B places in neither side 2500
B, when the operand is text: >= "2010" -> 499
first text value at position 17500: "1950", previous 2024
single-field document: integer 27 bytes, text 32 bytes

The correct answer is 3,990: if the entire field were an integer, this many documents would come back for 2010 and later. Neither semantics gives this number, but they miss it in different ways. Type ordering returns 5,991; the excess of 2,001 documents are records written entirely as text, including some from 1950 — because the text type sits after the integer type in the order, every text value is treated as greater than every integer. Type bracketing returns 3,491; the missing 499 documents are records whose year is written as text and whose real value is 2010 or later.

Type bracketing’s more insidious result shows up in the last line. >= 2010 and < 2010 are the two halves of one range, and their total should be 20,000; the measurement gives 17,500. 2,500 documents fall into neither query. These documents look missing in one report and missing in the reverse query too; because no answer ever shows them, the error goes unnoticed. Sorting, on the other hand, always uses the total order: integers run up through position 17,500, then text values follow, so the value "1950" lands after the value 2024.

The byte side points the same way: a single-field document takes 27 bytes when the year is an integer, 32 when it is text. Across 2,500 documents the difference is 12,500 bytes — a small number, but carrying the type in the document separates not just space but meaning. The lesson’s rule is this: the document model does not bind a field’s type at write time, so the job of binding it falls either to the writing application or to a rule placed afterward. How that rule gets placed, and what it catches and what it misses, is the question of this topic’s sixth lesson.

Summary

• The binary document representation stores every field with a type tag, a field name, and a length prefix where needed; the record is self-describing and decoding it needs no external schema.
• The same 20,000 book documents take 7,652,469 bytes with open names, 6,319,047 with short names, and 3,236,623 bytes in a fixed-schema row; in the open representation, 57.7% of the bytes are not data but definition.
• Shortening field names saves 1,333,422 bytes (66.7 bytes per document) and moves the knowledge of what a field is from the store to the application.
• Writing the same field in two types breaks a range query: type ordering returns 5,991 documents instead of 3,990, type bracketing returns 3,491.
• Under type bracketing, >= 2010 and < 2010 total 17,500, not 20,000; 2,500 documents show up in neither answer.

Next Step

This lesson looked inside a single document and counted the cost of a field’s name and type. 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 different ways — embedding the related data inside the document, or keeping it in a separate collection and pointing to it by key. Both store the same catalog, but they answer the same read with a different number of round trips, rewrite a different number of documents on the same update, and approach the document size limit at a different rate. The next lesson runs both decisions on the same work and counts the difference.