Query Operators

The previous lesson built the schema and counted the cost of the embedding decision; the branch query ran through a hand-written condition function. A store does this work itself, with a set of operators: comparison operators, logical connectives, and operators specific to arrays. This lesson does not drill the syntax of that set — syntax already varies from store to store. What does not vary is the semantics, built and measured here in its own evaluator.

The actual question to measure surfaced at the end of the previous lesson. When an embedded copy array is asked two conditions at once, it is ambiguous whether the conditions must be satisfied by the same copy or by any two copies of the document. Both readings are consistent, both are genuinely used, and each returns a different number of documents.

The Path Descending Into the Array

A relational condition looks at a single cell. In the document model, a field path can reach more than one value: the path copy.branch produces three values on a book with three copies. The evaluator behaves existentially in this case — the condition is true when any one of the reached values satisfies it. This single rule is the source of every measurement in the lesson.

The evaluator carries three operator classes. Comparison operators (=, <>, >, >=, <, <=, in) compare a value against a constant. Logical connectives (and, or, not) combine conditions. Array operators (any, all, none) stand apart from the rest: they look not at values but at elements, and apply the sub-condition to each element separately.

// operators.mjs — condition evaluator. A path descends into arrays: a field path can
// reach more than one value, and the condition is true if any one of those values
// satisfies it.
const COMPARE = {
  "=": (a, b) => a === b,
  "<>": (a, b) => a !== b,
  ">": (a, b) => a > b,
  ">=": (a, b) => a >= b,
  "<": (a, b) => a < b,
  "<=": (a, b) => a <= b,
  in: (a, b) => b.includes(a),
};

// Values at the path. An array is a candidate both as itself and through 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] : [v]));
}

// The arrays themselves at the path: element-level operators work on this.
const arrays = (root, path) => values(root, path).filter(Array.isArray);

export function matches(doc, condition, s = { compare: 0, element: 0 }) {
  for (const [name, expected] of Object.entries(condition)) {
    if (name === "and") { if (expected.every((k) => matches(doc, k, s))) continue; return false; }
    if (name === "or") { if (expected.some((k) => matches(doc, k, s))) continue; return false; }
    if (name === "not") { if (matches(doc, expected, s)) return false; continue; }

    const simple = expected === null || typeof expected !== "object" || Array.isArray(expected);
    const conditions = simple ? { "=": expected } : expected;
    for (const [operator, operand] of Object.entries(conditions)) {
      if (operator === "exists") {
        if (values(doc, name).length > 0 !== operand) return false;
        continue;
      }
      if (operator === "any" || operator === "all" || operator === "none") {
        const elements = arrays(doc, name).flat();
        s.element += elements.length;
        const count = elements.filter((o) => matches(o, operand, s)).length;
        const ok = operator === "any" ? count > 0
          : operator === "all" ? count === elements.length && elements.length > 0 : count === 0;
        if (ok) continue;
        return false;
      }
      const candidates = values(doc, name);
      s.compare += candidates.length;
      if (candidates.some((d) => COMPARE[operator](d, operand))) continue;
      return false;
    }
  }
  return true;
}

export const select = (items, condition, s) => items.filter((b) => matches(b, condition, s));

Same Question, Two Semantics

NS7 (assumption): the catalog is 20,000 book documents, each book has 1–5 copies and 2–4 tags, and the seed is 424242. NS12 (assumption): as a result of the flexible schema, one in forty documents has no publication_year field at all. The questions are asked first at the document level, then at the element level; each run prints the number of documents returned, the number of comparisons made, and the number of elements examined.

// operator-measurement.mjs — the same three questions are asked in two operator forms:
// document-level conjunction and element-level matching. The number of documents
// returned and comparisons made are counted.
// operators.mjs is in the same directory.
import { select } from "./operators.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)]);
  const b = { _k: `K-${String(i).padStart(5, "0")}`, author: `Author ${i % 4000}`,
    publication_year: 1950 + (i % 75), tag, copy };
  if (i % 40 === 0) delete b.publication_year;             // flexible schema: a field can be missing
  CATALOG.push(b);
}

function run(name, condition) {
  const s = { compare: 0, element: 0 };
  const result = select(CATALOG, condition, s);
  console.log(`${name.padEnd(34)} ${String(result.length).padStart(5)} documents  ` +
    `comparisons ${String(s.compare).padStart(6)}  elements examined ${String(s.element).padStart(6)}`);
  return result.length;
}

console.log(`catalog ${CATALOG.length} documents`);
const a1 = run("document-level conjunction", { "copy.branch": "Kadikoy", "copy.status": "in_repair" });
const a2 = run("element-level matching", { copy: { any: { branch: "Kadikoy", status: "in_repair" } } });
console.log(`  in ${a1 - a2} documents the conditions are satisfied by separate copies`);

const b1 = run("copy.status <> checked_out", { "copy.status": { "<>": "checked_out" } });
const b2 = run("no copy is checked out", { copy: { none: { status: "checked_out" } } });
console.log(`  in ${b1 - b2} documents at least one copy is checked out`);

const c1 = run("tag in [history, science]", { tag: { in: ["history", "science"] } });
const c2 = run("both history and science", { and: [{ tag: "history" }, { tag: "science" }] });
const c3 = run("all copies shelved", { copy: { all: { status: "shelved" } } });
console.log(`  difference between in and the two-condition conjunction ${c1 - c2} documents`);

run("publication_year field missing", { publication_year: { exists: false } });
run("publication_year >= 2010", { publication_year: { ">=": 2010 } });
run("not publication_year < 2010", { not: { publication_year: { "<": 2010 } } });

catalog 20000 documents
document-level conjunction          6033 documents  comparisons  88749  elements examined      0
element-level matching              3340 documents  comparisons  70018  elements examined  59494
  in 2693 documents the conditions are satisfied by separate copies
copy.status <> checked_out         17787 documents  comparisons  59494  elements examined      0
no copy is checked out              7111 documents  comparisons  59494  elements examined  59494
  in 10676 documents at least one copy is checked out
tag in [history, science]          14033 documents  comparisons  79730  elements examined      0
both history and science            2777 documents  comparisons 115287  elements examined      0
all copies shelved                  1919 documents  comparisons  59494  elements examined  59494
  difference between in and the two-condition conjunction 11256 documents
publication_year field missing       500 documents  comparisons      0  elements examined      0
publication_year >= 2010            3891 documents  comparisons  19500  elements examined      0
not publication_year < 2010         4391 documents  comparisons  19500  elements examined      0

What the Numbers Say

The first pair is the lesson’s core finding. The question “book with a copy under repair at the Kadikoy branch” returns 6,033 documents when asked at the document level, 3,340 when asked at the element level. In the 2,693 documents in between, there is a copy at Kadikoy and a copy under repair, but they are different copies — the one at Kadikoy is shelved, the one under repair is at a different branch. The document-level conjunction is not wrong; it asks a different question. What is wrong is asking an element-level question at the document level, and the result is 80.6% too many documents. The measurement produces this difference silently: both queries run, neither raises an error.

The second pair shows how negation behaves on an array. The condition copy.status <> "checked_out" returns 17,787 documents; the intent here is almost always “book with no copy checked out,” and the correct answer to that question is 7,111. The difference of 10,676 documents is books that have at least one copy checked out but also at least one copy that is not, and the existential rule makes the condition true. Negation on an array runs, against intuition, inclusively: “is not” does not mean “none of them is.” The correct expression is the none operator, and because it works at the element level, it examines all 59,494 elements.

The third pair shows the reverse direction of the same mistake. The in operator, applied to an array, means “any one of the listed values” and returns 14,033 documents; the question “book tagged with both history and science” is a two-condition conjunction and returns 2,777 documents. The difference is 11,256. Here the document-level conjunction is the right tool, because the tags are separate elements and the conditions are not meant to be satisfied by the same element. The two measurements together give the rule: what decides whether a conjunction should be built at the document level or the element level is the question itself, not the presence of an array.

The all operator returns 1,919 documents: books whose every copy is shelved. This operator’s definition in the evaluator carries a detail — count === elements.length && elements.length > 0. Without the second condition, a book with no copies at all would answer “yes” to “all copies shelved,” because every proposition is true over an empty set. This behavior of the empty array creates, alongside a field being absent altogether in the document model, two separate kinds of emptiness, and each silently changes the query’s answer.

The last three lines are the flexible schema’s trace on the query side. 500 documents have no publication_year field. publication_year >= 2010 does not return these documents (3,891), but the same condition wrapped in not does (4,391): no comparison ever comes true over a missing field, so its negation comes true. The difference is exactly 500 — the number of documents without the field. A report’s “books not from before 2010” line ends up including the 500 books that have no field at all.

The comparison counts give the cost. Element-level matching makes 70,018 comparisons and examines 59,494 elements, the document-level conjunction makes 88,749 comparisons. Both read the entire collection: 20,000 documents. This means the choice of operator does not change how many documents are read — what changes that number is the index, and that is this topic’s fifth lesson’s subject.

Summary

• A field path descends into an array and reaches more than one value; the condition is true when any one of the reached values satisfies it.
• The question “copy under repair at Kadikoy” returns 6,033 documents at the document level, 3,340 at the element level; in 2,693 documents the two conditions are satisfied by separate copies.
• Negation on an array is inclusive: copy.status <> "checked_out" returns 17,787 documents, “no copy is checked out” returns 7,111; the difference is 10,676.
• The in operator applied to an array means “any one” (14,033 documents); the “all” question is built as a two-condition document-level conjunction (2,777 documents).
• A missing field satisfies no comparison, so its negation comes true: the 500 documents with no publication_year field fall into the negated form of the condition.

Next Step

Operators are enough to filter a question, but most of the library’s questions do not end with filtering: “how many copies are under repair at each branch,” “the five most-borrowed books,” “the average copy count per author.” All of these need grouping, counting, and sorting after the filtering, and it is not possible to state them in a single condition expression. The document model does this work with a pipeline made of stages: each stage takes a stream of records, transforms it, and hands it to the next. The order of the stages determines the length of the stream — depending on whether filtering comes first or last, the number of records the later stages process changes. The next lesson builds that pipeline and counts the effect of the ordering decision on the number of records processed.