Query Language Structure

The previous topic built the inverted index and covered how a document enters and leaves it. Every question asked up to that point was a single term: a word was given, the posting list was read, documents came back. Questions asked against a library catalog do not look like that. “Short stories on children’s literature” carries three separate conditions, and how those conditions combine is left unsaid: are all three required, does one suffice, is the word “short” searched in the book’s title or in its summary? A quieter second question follows: in what order will the matching documents come back?

This lesson separates two layers. A leaf query searches a single term in a single field and its answer is a posting list. A compound query combines leaves in a tree; the tree’s root node is a connective, its leaves are terms. The same catalog question can be written as plain text or as a tree — the two return different numbers of documents and read different numbers of posting entries.

Corpus

QR1 (assumption): the corpus is 6,000 book records generated from a library catalog; the seed is 271828 and generation is deterministic. Each record carries a title, a summary, two tags, an author, a year, and a language. title and summary are text fields, tag is a keyword field. QR2 (assumption): query terms are written in the form they take in the index; suffixes and case are the analyzer chain’s job, and the analyzer chain is fixed in this topic.

// corpus.mjs — library catalog corpus and position-aware inverted index.
// Seed 271828, 6000 documents; every measurement in the topic shares this module.
export const SEED = 271828, N = 6000;
let c = SEED;                                        // visible seed, deterministic generator
const r = () => { c = (c + 0x6d2b79f5) | 0; let t = Math.imul(c ^ (c >>> 15), 1 | c);
  t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 4294967296; };
const pick = (d, e = 1) => d[Math.floor(r() ** e * d.length)];  // e>1: early items frequent, late items sparse

const ADJECTIVE = ["critical", "short", "illustrated", "selected", "comparative"];
const GENRE = ["essay", "story", "novel", "study", "anthology"];
const CATEGORY = ["children", "history", "science", "philosophy", "society"];
const SUFFIX = ["selection", "book", "compilation", "series"];
const QUALIFIER = ["comprehensive", "concise", "introductory", "contentious"];
const SUBJECT = ["education", "migration", "city", "memory", "nature", "music", "law", "identity", "labor", "family",
  "war", "tradition", "health", "travel", "architecture", "archaeology", "seafaring", "astronomy"];
const AUTHOR = ["James Miller", "Anna Clarke", "Peter Brooks", "Laura Bennett", "Henry Cole"];
const LANGUAGE = ["english", "german", "french"];

export const CATALOG = [];
for (let i = 1; i <= N; i += 1) {
  const s = pick(ADJECTIVE, 1.5), t = pick(GENRE, 1.5), a = pick(CATEGORY, 2), k = r();
  const pattern = k < 0.18 ? `${s} ${t}` : k < 0.30 ? `${s} meets ${t}`
    : k < 0.40 ? `${s} and theoretical ${t}` : k < 0.50 ? `${t} and ${s} study`
    : k < 0.70 ? `${s} narrative piece` : k < 0.88 ? `a contemporary ${t}` : "review of literature";
  CATALOG.push({ id: `K-${String(i).padStart(4, "0")}`, title: `${a} ${t} ${pick(SUFFIX)}`,
    summary: `${a} field: ${pattern}; readable on ${pick(SUBJECT, 3)} and ${pick(SUBJECT, 3)} as ` +
      `a ${pick(QUALIFIER)} ${pick(GENRE, 1.5)}.`,
    tag: [a, t], author: pick(AUTHOR), year: 1990 + Math.floor(r() * 35), language: pick(LANGUAGE, 2) });
}

export const tokenize = (m) => m.toLocaleLowerCase("en-US").split(/[^\p{L}\p{N}]+/u).filter(Boolean);

// Inverted index: "field|term" -> Map(document index -> positions); length: token count per document field.
export function invertedIndex(fields) {
  const postings = new Map(), length = new Map();
  CATALOG.forEach((b, i) => {
    for (const field of fields) {
      const tk = tokenize(String(b[field]));
      length.set(`${field}|${i}`, tk.length);
      tk.forEach((t, p) => {
        let list = postings.get(`${field}|${t}`); if (!list) postings.set(`${field}|${t}`, (list = new Map()));
        let positions = list.get(i); if (!positions) list.set(i, (positions = [])); positions.push(p);
      });
    }
  });
  return { postings, length };
}

Tree and Evaluation Order

The evaluator recognizes three node types: leaf, and, or. Intersection works by galloping — for each entry of the left list, an exponential jump and a binary search run against the right list. QR3 (assumption): the posting list’s length is read from the index dictionary and is known without reading its entries; entries scanned is counted only during the intersection and union walk. This makes the order in which a tree’s children are evaluated a real decision: starting with the short list means only a handful of jumps into the long list.

// query.mjs — leaf and compound query evaluator. corpus.mjs is in the same directory.
// Entries scanned: entries read from posting lists during intersection and union walks.
// List length is known from the dictionary without reading entries.
import { CATALOG, SEED, invertedIndex } from "./corpus.mjs";
const { postings } = invertedIndex(["title", "summary", "tag"]);
const leaf = (field, term) => [...(postings.get(`${field}|${term}`)?.keys() ?? [])];

function gallop(list, target, from, s) {                // exponential jump, then binary search
  let step = 1, i = from;
  while (i + step < list.length && list[i + step] < target) { step *= 2; s.scanned += 1; }
  let lo = i, hi = Math.min(i + step, list.length - 1);
  while (lo <= hi) { const mid = (lo + hi) >> 1; s.scanned += 1;
    if (list[mid] === target) return mid; if (list[mid] < target) lo = mid + 1; else hi = mid - 1; }
  return -lo - 1;
}
function intersect(a, b, s) {                            // a is scanned, b is jumped through
  const c = []; let j = 0;
  for (const d of a) {
    s.scanned += 1;
    const k = gallop(b, d, j, s);
    if (k >= 0) { c.push(d); j = k + 1; } else j = -k - 1;
    if (j >= b.length) break;
  }
  return c;
}
function union(lists, s) {
  const k = new Set();
  for (const l of lists) { s.scanned += l.length; for (const d of l) k.add(d); }
  return [...k].sort((x, y) => x - y);
}
export function evaluate(node, s, optimize = false) {
  if (node.term) return leaf(node.field, node.term);
  if (node.or) return union(node.or.map((d) => evaluate(d, s, optimize)), s);
  const children = node.and.map((d) => evaluate(d, s, optimize));
  if (optimize) children.sort((a, b) => a.length - b.length);
  return children.reduce((acc, l) => intersect(acc, l, s));
}
const measure = (name, node, optimize = false) => {
  const s = { scanned: 0 };
  const k = evaluate(node, s, optimize);
  console.log(`${name.padEnd(34)} ${String(k.length).padStart(4)} documents   entries scanned ${String(s.scanned).padStart(6)}`);
  return k;
};

console.log(`corpus ${CATALOG.length} documents, seed ${SEED}`);
const T = (field, term) => ({ field, term });
const FIELDS = ["title", "summary", "tag"];
const flat = (term) => ({ or: FIELDS.map((f) => T(f, term)) });
measure("plain text, any of them", { or: ["children", "short", "story"].map(flat) });
measure("plain text, all required", { and: ["children", "short", "story"].map(flat) });
measure("structured", { and: [T("tag", "children"), T("summary", "short"), T("title", "story")] });
const tree = { and: [{ or: [T("title", "story"), T("title", "novel")] }, T("summary", "short"), T("tag", "children")] };
const r1 = measure("tree, written order", tree);
const r2 = measure("tree, shortest list first", tree, true);
console.log("same set:", JSON.stringify(r1) === JSON.stringify(r2));
for (const [f, t] of [["tag", "children"], ["summary", "short"], ["title", "story"], ["title", "novel"]])
  console.log(`  posting list ${f}|${t}`.padEnd(30), String(leaf(f, t).length).padStart(5));

// Order: same set, sorted two ways. How many conditions each document satisfies is counted.
const s2 = { scanned: 0 }, tally = new Map();
for (const k of ["children", "short", "story"].map(flat))
  for (const d of evaluate(k, s2)) tally.set(d, (tally.get(d) ?? 0) + 1);
const indexOrder = [...tally.keys()].sort((a, b) => a - b);
const conditionOrder = [...indexOrder].sort((a, b) => tally.get(b) - tally.get(a) || a - b);
const topAllThree = (l) => l.slice(0, 10).filter((d) => tally.get(d) === 3).length;
console.log(`all three conditions in top ten: index order ${topAllThree(indexOrder)}, condition order ${topAllThree(conditionOrder)}`);
const full = conditionOrder.filter((d) => tally.get(d) === 3);
const ranks = full.map((d) => indexOrder.indexOf(d) + 1);
console.log(`${full.length} documents satisfying all three conditions rank ` +
  `${Math.round(ranks.reduce((x, y) => x + y, 0) / ranks.length)} on average in index order, the last at ${Math.max(...ranks)}.`);

corpus 6000 documents, seed 271828
plain text, any of them            4211 documents   entries scanned  19102
plain text, all required            132 documents   entries scanned  21303
structured                           71 documents   entries scanned   7576
tree, written order                 138 documents   entries scanned   9501
tree, shortest list first           138 documents   entries scanned   7876
same set: true
  posting list tag|children     2678
  posting list summary|short     895
  posting list title|story      1271
  posting list title|novel      1007
all three conditions in top ten: index order 1, condition order 10
132 documents satisfying all three conditions rank 2023 on average in index order, the last at 4185.

Set: Three Readings of the Same Question

Three lines come from the same three words and return three different sets. The “any of them” reading returns 4,211 documents — 70.2% of the corpus. This reading is practically useless in a catalog: the result list is as large as the library itself. The “all required” reading falls to 132 documents; which field a word appears in is still unconstrained, “story” can sit in either the book’s title or its summary. The structured reading ties the three conditions to three separate fields — tagged children, “short” in the summary, “story” in the title — and returns 71 documents.

The 61-document gap in between is not lost; those are books that carry the word “story” only in their summary, meaning they are not a story collection but a book that talks about one. Which set is correct depends on the question itself, and plain text does not say. Plain text is not a query; it is a candidate reading of a query, and the party that picks the reading is the engine. A catalog interface makes that choice, not the user — which is why two users typing the same three words into two different interfaces can see anywhere between 4,211 and 71 results.

Cost: The Tree’s Evaluation Order

The bottom three lines hold the set fixed and measure cost. The compound tree is: books whose title carries “story” or “novel”, whose summary carries “short”, tagged children. Evaluated in written order, the union of the two long lists is taken first (1,271 and 1,007 entries), the result is then carried against the 2,678-entry tag list, and 9,501 entries are read in total. In the same tree, when the children are sorted by length, the intersection starts with the shortest list of 895 entries and the total falls to 7,876 entries — 17.1% less reading. The set returned in both runs is 138 documents; the comparison confirms it.

The same effect is larger in the plain-text readings: “all required” reads 21,303 entries, because for every term the union of three fields is built first and those unions are long. The structured form comes out to 7,576 entries — 64.4% less — because here both the set and the cost fall together, since field separation prunes both unneeded documents and unneeded posting lists. Galloping intersection is what produces this difference: if list walking were linear, either order would have to read the entire long list.

Order: The Set Does Not Give Order

The array the evaluator returns is sorted by ascending document number, and that is not a relevance order — it is index insertion order. The last two lines measure this. Within the 4,211 documents of the “any of them” reading there are 132 documents satisfying all three conditions; in index order, only 1 of the top ten results belongs to that group. Sorted by satisfied-condition count, 10 of the top ten come from that group. The set has not changed, only the order has.

Rank churn makes this difference larger: the 132 documents sit at position 2,023 on average in index order, the furthest at position 4,185. If a reader gives up after the first page, they never see the book they wanted, even though the set was correct all along. Satisfied-condition count is the crudest sort criterion there is; it does not account for how rare the terms are, which field they appear in, or how long that field is. All of that goes into a relevance score, and that score is built in this topic’s fifth lesson. What this lesson leaves behind matters more: deciding the set and deciding the order are separate decisions, and a query form does not fix both at once.

Summary

• A leaf query searches a single term in a single field; a compound query combines leaves in a tree, and the tree’s root determines the connective.
• In a 6,000-document corpus (seed 271828) the same three words return 4,211, 132, and 71 documents across three readings; plain text does not say which reading applies, the engine picks it.
• Field separation both narrows the set and lowers the cost: the structured form reads 7,576 entries, the plain-text “all required” reading reads 21,303.
• When a tree’s children are sorted by length, the set stays the same (138 documents) and entries scanned falls from 9,501 to 7,876.
• The matching set is unordered on its own: the 132 documents satisfying all three conditions sit at position 2,023 on average in index order, but land in the top ten when sorted by satisfied-condition count.

Next Step

The structured query tied terms to fields, but still left the relationship between terms at “occurs in the same document.” Part of what catalog questions ask goes further than that: two words inside a book’s title, whose full title is not known, sit next to each other with nothing in between. “A critical essay” and “a critical and theoretical essay” carry the same two terms; in the first they are adjacent, in the second a word has come between them. The position information kept in the inverted index’s posting lists exists exactly for this distinction, and it has not been used so far. The next lesson builds the phrase query: it turns term order and the distance between terms into a condition, counts how much slop widens the set, and measures how much position information costs the index.