---
title: 'Query Language Structure'
source: 'https://academia.sh/en/courses/search-engines/query-language-structure'
course: 'Search Engines and Text Retrieval'
language: en
updated: '2026-08-23T07:00:50+00:00'
license: 'CC BY-SA 4.0'
---

# Query Language Structure

The same catalog question is asked in plain text and in structured form: the returned set ranges from 4,211 to 71 documents when how the conditions combine goes unsaid, the compound query is evaluated as a tree, and the tree's evaluation order lowers the entries scanned without changing the set.

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.

```js
// 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.

```js
// 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.