Filtering and Query Distinction

The previous lesson separated the three condition contexts, but all three shared one thing: all of them passed 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. Part of catalog conditions is wrong for this. “Publication year 2010 or later”, “language is english”, “subject heading mentions education” — conditions like these are either satisfied or not; a book being a 2015 printing does not make it more relevant than a 2011 printing.

This distinction is named filter context and query context. The same condition passes the same documents in both contexts — the set does not change. What changes is whether the condition contributes to score, and that has two consequences: order comes out different, cost comes out different. This lesson runs the same condition in both contexts and compares three numbers: the documents returned, the top ten results, and the entries read.

Corpus and the Scoring Rule

The corpus is the previous lessons’ module: 6,000 book records, seed 271828, deterministic generation. QR7 (assumption): in this lesson score is the sum, over every scored condition, of that condition’s term frequency divided by the token count of that field. There is no rarity multiplier yet; the full model is built in this topic’s fifth lesson. What is measured here is not the size of the score, but the effect on order of a condition entering or not entering scoring.

// 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 Two Contexts

// filter.mjs — the same condition, first in query context, then in filter context. Corpus: corpus.mjs.
// Score here is term frequency divided by field length; the full model is built in the next lesson.
import { CATALOG, SEED, invertedIndex } from "./corpus.mjs";
const { postings, length } = invertedIndex(["title", "summary", "tag", "language"]);
const list = (field, term) => postings.get(`${field}|${term}`) ?? new Map();

function search(scored, filters, s) {
  let candidate = null;
  for (const [field, term] of [...scored, ...filters]) {
    const l = list(field, term); s.scanned += l.size;
    candidate = candidate === null ? [...l.keys()] : candidate.filter((d) => l.has(d));
  }
  const score = new Map();
  for (const d of candidate) {
    let p = 0;
    for (const [field, term] of scored) { s.computed += 1; p += list(field, term).get(d).length / length.get(`${field}|${d}`); }
    score.set(d, p);
  }
  return { set: candidate, score, ranked: [...candidate].sort((x, y) => score.get(y) - score.get(x) || x - y) };
}
const measure = (name, scored, filters) => {
  const s = { scanned: 0, computed: 0 }, c = search(scored, filters, s);
  console.log(`${name.padEnd(40)} ${String(c.set.length).padStart(4)} documents   score computed ${String(s.computed).padStart(4)}` +
    `   entries scanned ${String(s.scanned).padStart(5)}`);
  return c;
};

console.log(`corpus ${CATALOG.length} documents, seed ${SEED}`);
const QUERY = [["summary", "story"]], CONDITION = [["summary", "education"]];
const a = measure("query context: story + education scored", [...QUERY, ...CONDITION], []);
const b = measure("filter context: education only filters", QUERY, CONDITION);
console.log(`same set: ${JSON.stringify(a.set) === JSON.stringify(b.set)}`);
const topTen = (c) => c.ranked.slice(0, 10).map((d) => CATALOG[d].id);
console.log(`top ten, query context ${topTen(a).join(" ")}`);
console.log(`top ten, filter context ${topTen(b).join(" ")}`);
console.log(`changed in top ten ${topTen(a).filter((x) => !topTen(b).includes(x)).length}/10`);
console.log(`distinct score values: query context ${new Set(a.score.values()).size}, ` +
  `filter context ${new Set(b.score.values()).size}`);
const movement = a.set.map((d) => Math.abs(a.ranked.indexOf(d) - b.ranked.indexOf(d)));
console.log(`position movement: average ${Math.round(movement.reduce((x, y) => x + y, 0) / movement.length)}, ` +
  `largest ${Math.max(...movement)}, unchanged ${movement.filter((o) => o === 0).length} documents`);

// Cache: the filter's result is independent of the query, stored as a bit set.
const cache = new Map();
function filterSet(field, term, s) {
  const key = `${field}|${term}`;
  if (cache.has(key)) { s.hits += 1; return cache.get(key); }
  const l = list(field, term); s.scanned += l.size;
  const bits = new Uint8Array(Math.ceil(CATALOG.length / 8));
  for (const d of l.keys()) bits[d >> 3] |= 1 << (d & 7);
  cache.set(key, bits);
  return bits;
}
const FIVE = ["story", "novel", "essay", "study", "anthology"];
for (const cached of [false, true]) {
  cache.clear();
  const s = { scanned: 0, hits: 0 };
  for (const t of FIVE) {
    list("summary", t); s.scanned += list("summary", t).size;
    if (cached) filterSet("summary", "education", s);
    else s.scanned += list("summary", "education").size;
  }
  console.log(`five queries, same filter  ${cached ? "cached    " : "uncached  "}   ` +
    `entries scanned ${String(s.scanned).padStart(6)}   cache hits ${s.hits}`);
}
console.log(`filter bit set ${Math.ceil(CATALOG.length / 8)} bytes; ` +
  `the same condition's score array ${list("summary", "education").size * 8} bytes`);

corpus 6000 documents, seed 271828
query context: story + education scored  1138 documents   score computed 2276   entries scanned  5513
filter context: education only filters   1138 documents   score computed 1138   entries scanned  5513
same set: true
top ten, query context K-0836 K-2188 K-4924 K-5913 K-1025 K-1207 K-2800 K-3095 K-3253 K-3683
top ten, filter context K-0171 K-0360 K-0417 K-0709 K-0836 K-0958 K-1185 K-1325 K-1520 K-1670
changed in top ten 9/10
distinct score values: query context 9, filter context 6
position movement: average 173, largest 791, unchanged 4 documents
five queries, same filter  uncached     entries scanned  27836   cache hits 0
five queries, same filter  cached       entries scanned  13260   cache hits 4
filter bit set 750 bytes; the same condition's score array 29152 bytes

Set Stays, Order Does Not

Both runs return 1,138 documents, and the comparison confirms the sets are literally identical. This is the expected result: in both contexts the condition is required, the documents it passes are the same. On the set side, filter context has no effect at all.

On the order side, the effect is large. Nine of the top ten results change; the only record surviving between the two lists is K-0836. Only four of the 1,138 documents stay in place, the average position movement is 173, the largest is 791. The source of the difference is score resolution: in filter context, score comes from a single condition and takes 6 distinct values; in query context, score comes from two conditions and takes 9 distinct values. As the number of distinct values grows, ties get broken and the list gets reshuffled.

The decision that follows is clear. “It should be about education” is not a relevance measure, it is a scope restriction; left in query context, a book with a short summary or one that mentions “education” twice climbs to the top of the list. This ordering has nothing to do with what the user asked — the user is not asking how many times the word education occurs, they are looking for a story book. Filter context leaves ordering to the user’s actual question.

Cost: Computation, Reading, and Cache

Score computation is cut in half: from 2,276 to 1,138. For every candidate document, one multiplication and one division are done instead of two, and this saving grows in proportion to the candidate count. Entries scanned does not change on the first run (5,513) — a filter still reads a posting list in the end.

The real gain shows up on the second run. The filter’s result is independent of the query: whatever free-text query is asked, the set “summaries mentioning education” is the same. This means the result can be stored as a bit set, and later queries never touch the posting list again. When five different queries share the same filter, an uncached run reads 27,836 entries; a cached run reads 13,260 entries — 52.4% less, with four cache hits.

The cache’s size makes this decision easy. For a 6,000-document corpus, the bit set is 750 bytes. Storing the same condition’s score contribution instead would need an eight-byte decimal for each of 3,644 documents, which is 29,152 bytes — thirty-nine times as much. Storing the score is also pointless besides, because the final score is computed together with the query’s other conditions and comes out different on every query. The filter owes its cacheability entirely to the fact that it does not enter scoring: the result of a condition that does not enter scoring is a boolean value, and a boolean value does not change from query to query.

The filter is not free of cost. The cache consumes memory and invalidates on every document insert or delete; keeping a rarely asked condition in the cache wastes memory for nothing. The measure is simple: how many separate queries repeat the same condition. The language and subject restrictions in a library interface repeat on every query, the free text the user types does not.

Summary

• The same required condition returns the same set in both contexts: in a 6,000-document corpus (seed 271828), both runs return 1,138 documents.
• Order changes entirely: nine of the top ten results differ, only four of the 1,138 documents stay in place, average position movement is 173, the largest is 791.
• The source of the difference is score resolution: filter context produces 6 distinct score values, query context produces 9.
• Filter context cuts score computation in half (2,276 to 1,138) and, by making the result independent of the query, makes it cacheable: 13,260 entries instead of 27,836 across five queries.
• The filter cache is 750 bytes, the same condition’s score array is 29,152 bytes; storing the score is pointless besides, because the final score comes out different on every query.

Next Step

Up to this point score was always computed with a placeholder formula: first satisfied-condition count, then term frequency divided by field length. Both produced an ordering, but both skipped the real other half of the question. A term occurring in a document carries no meaning without knowing how rare that term is across the corpus: the word “and” occurs in every one of the 6,000 documents and distinguishes nothing, while “astronomy” occurs in about two hundred documents and nearly determines the document by itself. The next lesson splits score into three components — term frequency, inverse document frequency, and field length — shows which component a document’s position comes from, and defines precision and recall to measure how much of the result is correct.