Context Queries

The two previous lessons built every condition the same way: a document that failed the condition dropped out of the set. Catalog questions are not this uniform. A reader says: “It should be a children’s book, not in French, and illustrated ones should rank first.” All three requests sit in one sentence, but the three do not do the same job. The first determines the set, the second removes from the set, the third removes no one from the set at all — it only changes what comes first.

A compound query makes this distinction with condition context. A must condition eliminates a document that does not satisfy it. A must-not condition eliminates a document that does satisfy it. A should condition eliminates no document; it adds score to a document that satisfies it. This lesson counts the effect of the three contexts on the set and on order separately, and shows a place where a should condition changes the rule.

Corpus and the Scoring Rule

The corpus is the previous lessons’ module: 6,000 book records, seed 271828, deterministic generation. QR6 (assumption): in this lesson score is the count of satisfied should conditions; ties are broken by document number. The real scoring model built on term frequency and rarity comes in this topic’s fifth lesson — what is measured here is not the size of the score but the fact that a should condition touches order and does not touch the set.

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

Measuring the Three Contexts

// context.mjs — must, must-not, and should conditions. corpus.mjs is in the same directory.
// A should condition eliminates no document; it only produces score. Score here is the
// count of satisfied should conditions; ties are broken by document number.
import { CATALOG, SEED, invertedIndex } from "./corpus.mjs";
const { postings } = invertedIndex(["title", "summary", "tag", "language"]);
const matchSet = (field, term) => new Set(postings.get(`${field}|${term}`)?.keys() ?? []);

function run(query, s) {
  let candidate = null;
  for (const [field, term] of query.must ?? []) {
    const k = matchSet(field, term); s.scanned += k.size;
    candidate = candidate === null ? [...k] : candidate.filter((d) => k.has(d));
  }
  const shouldSets = (query.should ?? []).map(([f, t]) => { const k = matchSet(f, t); s.scanned += k.size; return k; });
  if (candidate === null) {                  // no must condition: should conditions determine the set
    const b = new Set();
    for (const k of shouldSets) for (const d of k) b.add(d);
    candidate = [...b];
  }
  for (const [field, term] of query.mustNot ?? []) {
    const k = matchSet(field, term); s.scanned += k.size;
    candidate = candidate.filter((d) => !k.has(d));
  }
  candidate.sort((x, y) => x - y);
  const score = new Map(candidate.map((d) => [d, shouldSets.filter((k) => k.has(d)).length]));
  const ranked = [...candidate].sort((x, y) => score.get(y) - score.get(x) || x - y);
  return { set: candidate, score, ranked };
}
const measure = (name, query) => {
  const s = { scanned: 0 }, c = run(query, s);
  console.log(`${name.padEnd(38)} ${String(c.set.length).padStart(4)} documents   entries scanned ${String(s.scanned).padStart(5)}`);
  return c;
};

console.log(`corpus ${CATALOG.length} documents, seed ${SEED}`);
const MUST = [["tag", "children"]], SHOULD = [["summary", "illustrated"], ["title", "story"]], MUST_NOT = [["language", "french"]];
const a = measure("must[tag:children]", { must: MUST });
const b = measure("must + mustNot[language:french]", { must: MUST, mustNot: MUST_NOT });
const c = measure("must + should[illustrated, story]", { must: MUST, should: SHOULD });
const d = measure("must + should + mustNot", { must: MUST, should: SHOULD, mustNot: MUST_NOT });
const e = measure("should only[illustrated, story]", { should: SHOULD });
console.log(`documents removed by mustNot ${a.set.length - b.set.length}`);
console.log(`should condition's effect on the set ${c.set.length - a.set.length} documents`);

const topTen = (l) => l.slice(0, 10).map((x) => CATALOG[x].id);
const changed = topTen(c.ranked).filter((x) => !topTen(a.ranked).includes(x)).length;
console.log(`top ten, must only ${topTen(a.ranked).join(" ")}`);
console.log(`top ten, +should ${topTen(c.ranked).join(" ")}   changed ${changed}/10`);
const twoMatches = c.ranked.filter((x) => c.score.get(x) === 2);
console.log(`documents satisfying both should conditions ${twoMatches.length}; ` +
  `the first, ${CATALOG[twoMatches[0]].id}, was at position ${a.set.indexOf(twoMatches[0]) + 1} in the must-only order`);
const movement = twoMatches.map((x) => a.set.indexOf(x) + 1 - (c.ranked.indexOf(x) + 1));
console.log(`these documents gain ${Math.round(movement.reduce((x, y) => x + y, 0) / movement.length)} positions on average, ` +
  `the largest gain ${Math.max(...movement)}`);

corpus 6000 documents, seed 271828
must[tag:children]                     2678 documents   entries scanned  2678
must + mustNot[language:french]        2166 documents   entries scanned  3800
must + should[illustrated, story]      2678 documents   entries scanned  4638
must + should + mustNot                2166 documents   entries scanned  5760
should only[illustrated, story]        1802 documents   entries scanned  1960
documents removed by mustNot 512
should condition's effect on the set 0 documents
top ten, must only K-0004 K-0008 K-0016 K-0018 K-0020 K-0023 K-0024 K-0026 K-0033 K-0037
top ten, +should K-0037 K-0072 K-0078 K-0080 K-0216 K-0345 K-0371 K-0518 K-0615 K-0712   changed 9/10
documents satisfying both should conditions 82; the first, K-0037, was at position 10 in the must-only order
these documents gain 1263 positions on average, the largest gain 2574

Set: Two Kinds of Condition Eliminate, One Does Not

The must condition alone returns 2,678 documents — the tagged-children books. Once the must-not condition is added, the set falls to 2,166: 512 documents drop out, all of them French-language records. The number a must-not condition produces is always a subtraction; it never adds a document to the set, and used alone its meaning is unclear, because “not French” does not say from which set it should be subtracted.

The third row is this lesson’s core. The same must condition gained two should conditions and the set stayed at 2,678 documents: nothing entered, nothing left, the difference is zero. A book that is not illustrated and does not carry “story” in its title did not drop out of the result list; only its score stayed at zero. The fourth row puts the must-not condition back on the same query and the set falls to 2,166 again — because what changes the set is not the should condition, it is the must-not condition.

The fifth row shows the boundary of the rule, and it is the point most often misunderstood in practice. Once the must condition is removed, the same two should conditions bring the set down to 1,802 documents. The should conditions have not suddenly started eliminating; what happens is this: once no condition remains to determine the set, at least one should condition must be satisfied, or the query would return the entire corpus. So the sentence “a should condition does not change the set” is not unconditionally true; the correct statement is: as long as some other condition determines the set, a should condition does not touch it. When an interface adds a condition for weighting purposes and the must condition is later removed, that condition dropping the result from 6,000 to 1,802 comes from this rule.

Order and Cost: What the Non-Eliminating Condition Charges

The set stays the same, yet the list becomes unrecognizable. The top ten results the must condition alone gives start with K-0004; once the should conditions are added, nine of the top ten change. The one document that survives is K-0037, and it climbs from tenth position to first. There are 82 documents that satisfy both should conditions; these documents climb 1,263 positions on average, the largest climbing 2,574 positions. In a 2,678-document list, a 2,574-position jump means the document moves from the very end of the list to the very front.

The cost side shows that a non-eliminating condition is not free either. The must condition alone reads 2,678 entries. Once the two should conditions are added, reading rises to 4,638 entries: a 73.2% increase, without eliminating a single document. The reason is plain — computing a should condition’s contribution to score requires reading the entire posting list, while a must condition does less work as the candidate set shrinks. With all three contexts together, reading reaches 5,760 entries; 1,122 of that is the must-not condition’s list, read only to remove 512 documents.

The operating rule that follows from this is: whether a condition is cheap or not is decided not by how many documents it eliminates, but by how many entries it makes you read. A condition that changes the set not at all can be the most expensive condition of all.

Summary

• A must condition determines the set, a must-not condition removes from it, a should condition only produces score; in a 6,000-document corpus (seed 271828) the must-not condition removes 512 documents, the should condition removes 0.
• The should condition’s neutrality toward the set is conditional: if no other condition determines the set, at least one should condition must be satisfied, and the set becomes 1,802 documents instead of 6,000.
• Order is rewritten while the set stays fixed: nine of the top ten results change, the 82 documents satisfying both should conditions climb 1,263 positions on average, the largest climbing 2,574 positions.
• A non-eliminating condition does not run for free: the two should conditions raise entries scanned from 2,678 to 4,638 without eliminating a single document.
• A condition’s cost is measured by the posting entries it makes you read, not by how many documents it eliminates.

Next Step

All three contexts meet at one point: every one of them passes in front of the scorer. The must condition both determines the set and contributes to score at the same time; the should condition exists for scoring alone. Yet part of catalog conditions should never enter the score at all. “Publication year 2010 or later” or “language is english” is a condition that is either satisfied or not; a book being a 2015 printing does not make it more relevant than a 2011 printing. These conditions are evaluated in a separate context, and that context has two consequences: the score computation shortens, and the result becomes reusable, because the same condition returns the same documents on every query. The next lesson runs the same condition in two contexts, shows that the set stays the same while the order changes, and counts how many entries the cached condition reads on its second run.