Term and Phrase Queries

The previous lesson built the compound query as a tree and left the relationship between terms at “occurs in the same document.” Part of catalog questions goes further than that. A reader does not remember a book’s full title, but knows two words sit next to each other. “A critical essay” and “critical meets essay” carry the same two terms; in one they are adjacent, in the other a word has come between them. A document-level query cannot tell the two apart — and it also puts documents in the same set where the terms sit at opposite ends of a sentence with no relation between them at all.

A phrase query makes this distinction: it turns not just the presence of terms but their positions into a condition. The position information kept in the inverted index’s posting lists exists exactly for this and has not been used so far. Slop loosens the condition: it allows extra words in between. This lesson measures three numbers together — the set the phrase narrows, the documents slop brings back, and the price position information charges the index.

Corpus and the Slop Definition

The corpus is the previous lesson’s module: 6,000 book records, seed 271828, deterministic generation. QR4 (assumption): slop is the number of extra words between two terms; if the terms match in the order written in the query, it is the word count between them, and if they match in reverse order, two is added to that count — one term crossing to the other side of the other counts as two steps. The measured phrase has two terms; longer phrases are the same rule applied in sequence.

// 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 };
}

Measurement

QR5 (assumption): index size is computed from the variable-length integer encoding of the posting lists: document numbers and positions are written as deltas, each number taking 1–4 bytes by its magnitude, and the dictionary counts the term name plus one byte. The index without positions writes the document delta and term frequency; the index with positions additionally writes the position deltas.

// phrase.mjs — term query versus phrase query. corpus.mjs is in the same directory.
// Slop: the number of extra words allowed between two terms; if the terms match in
// reverse order, two is added to this number. The measured phrase has two terms.
import { CATALOG, SEED, invertedIndex } from "./corpus.mjs";
const { postings } = invertedIndex(["title", "summary", "tag"]);
const list = (field, term) => postings.get(`${field}|${term}`) ?? new Map();

function closest(p1, p2, s) {                      // smallest cost between two position arrays
  let best = Infinity;
  for (const a of p1) for (const b of p2) { s.positions += 1; best = Math.min(best, b > a ? b - a - 1 : a - b + 1); }
  return best;
}
function phraseQuery(field, t1, t2, slop, s) {
  const l2 = list(field, t2), result = [];
  for (const [d, p1] of list(field, t1)) {
    const p2 = l2.get(d);
    if (p2 && closest(p1, p2, s) <= slop) result.push(d);
  }
  return result;
}
const vByte = (n) => (n < 128 ? 1 : n < 16384 ? 2 : n < 2097152 ? 3 : 4);   // variable-length integer
function indexBytes(withPositions) {
  let b = 0;
  for (const [key, l] of postings) {
    b += Buffer.byteLength(key) + 1;
    let previous = 0;
    for (const [d, position] of l) {
      b += vByte(d - previous) + vByte(position.length); previous = d;
      if (withPositions) { let p = 0; for (const k of position) { b += vByte(k - p); p = k; } }
    }
  }
  return b;
}
const report = (name, n, tail) => console.log(`${name.padEnd(30)} ${String(n).padStart(4)} documents   ${tail}`);

console.log(`corpus ${CATALOG.length} documents, seed ${SEED}`);
console.log(`summary|critical ${list("summary", "critical").size} documents, summary|essay ${list("summary", "essay").size} documents`);
const term = [...list("summary", "critical").keys()].filter((d) => list("summary", "essay").has(d));
report("term query, both present", term.length, `${" ".repeat(28)}positions read     0`);
let previous = 0;
for (const slop of [0, 1, 2, 3, 4]) {
  const s = { positions: 0 };
  const k = phraseQuery("summary", "critical", "essay", slop, s);
  report(`phrase query, slop ${slop}`, k.length,
    `in ${String(k.length - previous).padStart(3)}   out ${String(term.length - k.length).padStart(4)}   ` +
    `positions read ${String(s.positions).padStart(5)}`);
  previous = k.length;
}
const noPositions = indexBytes(false), withPositions = indexBytes(true);
console.log(`index bytes   without positions ${noPositions}   with positions ${withPositions}   increase %${((withPositions / noPositions - 1) * 100).toFixed(1)}`);

// Order: same set, two criteria. The term set is sorted by adjacency distance.
const s1 = { positions: 0 }, distance = new Map();
for (const d of term) distance.set(d, closest(list("summary", "critical").get(d), list("summary", "essay").get(d), s1));
const closestOrder = [...term].sort((a, b) => distance.get(a) - distance.get(b) || a - b);
const adjacent = (l) => l.slice(0, 10).filter((d) => distance.get(d) === 0).length;
console.log(`adjacent match in top ten: index order ${adjacent(term)}, by distance ${adjacent(closestOrder)}`);
const farthest = term.find((d) => distance.get(d) > 4);
console.log(`adjacent  ${CATALOG[closestOrder[0]].id}: ${CATALOG[closestOrder[0]].summary}`);
console.log(`farthest  ${CATALOG[farthest].id} (distance ${distance.get(farthest)}): ${CATALOG[farthest].summary}`);

corpus 6000 documents, seed 271828
summary|critical 1487 documents, summary|essay 2983 documents
term query, both present        757 documents                               positions read     0
phrase query, slop 0            144 documents   in 144   out  613   positions read   869
phrase query, slop 1            230 documents   in  86   out  527   positions read   869
phrase query, slop 2            303 documents   in  73   out  454   positions read   869
phrase query, slop 3            377 documents   in  74   out  380   positions read   869
phrase query, slop 4            377 documents   in   0   out  380   positions read   869
index bytes   without positions 220626   with positions 334724   increase %51.7
adjacent match in top ten: index order 1, by distance 10
adjacent  K-0069: history field: critical essay; readable on memory and education as a contentious study.
farthest  K-0002 (distance 10): science field: critical narrative piece; readable on music and war as a comprehensive essay.

Set: The Phrase Leaves a Fifth of the Term Query Behind

“Critical” occurs in 1,487 summaries, “essay” in 2,983; the count of documents carrying both is 757. The adjacent-phrase condition brings this set down to 144 documents — 19.0% of the term query. The 613 documents left out carry both terms, but not side by side. The output’s last line shows one of them: in K-0002’s summary “critical” qualifies a narrative, and “essay” names an entirely different genre at the other end of the sentence; the distance between the two terms is 10 and there is no meaning connecting them. The term query brought this document back wrongly; the phrase query does not.

Slop loosens this condition step by step. One unit of slop lets in the “critical meets essay” shape and 86 documents enter; two units let in “critical and theoretical essay”, 73 more enter; three units let in the reverse-order match — “essay and critical study” — and 74 more enter. At the fourth step, no document enters. This shows that raising slop does not have a constant effect: which distances exist is decided by the corpus’s sentence shapes, slop only opens those steps one at a time. In a catalog interface, raising slop from 0 to 3 grows the set here from 144 to 377 — 2.6 times — while raising it to 4 changes nothing.

Cost: Position Information Is Charged Against Every Document

The cost at query time is small. The phrase condition reads positions only in the documents the two posting lists share: 757 candidate documents draw 869 position comparisons, because most documents carry each term once and only a single pair is compared. This number does not change when slop changes — slop is a threshold; it does not decide how many positions are read, only how many documents clear the threshold.

The real cost sits in the index. The index without positions is 220,626 bytes, the index with positions is 334,724 bytes: a 51.7% increase, a 114,098-byte difference, roughly 19 bytes per document. The nature of this cost matters — it is paid per document, not per query. Position information is kept in every document whether or not a phrase query is ever asked, written at every indexing pass, carried through every segment merge. The decision is this: in a field where phrase queries are never needed, position information can be turned off and the index shrinks by roughly a third; in exchange, phrase queries can no longer be asked on that field, only an approximate result comes back from a term query — and that approximation’s error is measured right here: 757 against 144.

Order: Distance Is a Sort Criterion

When the phrase condition is used as a threshold, the set splits sharply: 144 inside, 613 outside. The same distance can also be used as a sort criterion instead of a threshold, and then the set does not narrow at all. The last measurement shows this: when the 757-document term set is given in index order, only 1 of the top ten results is an adjacent match; when the same set is sorted by inter-term distance, all ten of the top ten are adjacent matches.

The difference between the two approaches is the plainest example of this course’s core distinction. The phrase condition used as a threshold changes the set and makes 613 documents entirely invisible; distance used as a sort criterion changes the order and leaves those 613 documents at the bottom of the list. In the first case, missing a document has no way back; in the second, the user finds it by scrolling down. Which is correct depends on how certain the question is: a threshold suits a book whose title is fully known, a sort criterion suits a topic search.

Summary

• A phrase query turns term positions, not just their presence, into a condition; in a 6,000-document corpus (seed 271828) it narrows the term query’s 757 documents to 144.
• Slop loosens the condition step by step: 1 unit adds 86 documents, 2 units add 73, 3 units add 74, 4 units add none.
• A reverse-order match counts as two steps, which is why the “essay and critical study” shape only enters the set once slop reaches 3.
• Position information is cheap at query time (869 position comparisons for 757 candidates) and expensive in the index: from 220,626 bytes to 334,724 bytes, a 51.7% increase.
• The same distance measure splits the set when used as a threshold and only reorders it when used as a sort criterion: adjacent matches in the top ten rise from 1 to 10.

Next Step

Every condition built so far was the same kind: a document that fails the condition drops out of the set. Catalog questions are not this uniform. “It should be tagged children” is a required condition; “it should not be in French” is a condition that narrows the set but works in reverse; “summaries mentioning ‘illustrated’ should rank higher” is a request that eliminates no document at all, it only affects order. All three sit side by side inside a single compound query, and their effect on the set is entirely different from one another. The next lesson separates these three condition types and counts how an optional condition rewrites the top ten results without changing a single document in the set.