Highlighting and Pagination

Every measurement so far has been done on document identifiers and scores. What the reader actually sees is not an identifier but a short snippet drawn from the book’s title and summary; within that snippet, the word being searched for is marked. There is a second thing too: the list does not end at ten rows — the reader moves to page two, then to page twenty.

These two jobs do not resemble each other. Highlighting touches only the shown documents, and its cost is independent of page depth. Pagination, by contrast, grows more expensive with depth, and that expense is multiplied by how many shards the index is split into. The lesson measures both on the same corpus.

Corpus, Page, and Shard

Code	Assumption	Value	Rationale
QR18	page size and shown fields	10 results; title and summary	highlighting is done only on these two fields
QR19	highlight window	30 characters, around the first match	the snippet must fit on one line
QR20	index shard	4 shards, each shard produces its own ranking	merging happens in the same process
QR21	candidate entry	12 bytes (4 for the id, 8 for the score)	size of the candidate kept by the merger

QR20 is this lesson’s measurement rig: the shards run in the same process, there is no network between them; what is measured is the number of candidates pulled from a shard, not time.

// corpus.mjs — library catalog: seeded corpus, inverted index, and scorer.
export const N = 1200, SEED = 20260801, FIELDS = ["title", "summary", "subject", "author"];
let d = SEED;                                             // 32-bit generator, no overflow
export const random = () => { d = (d + 0x6D2B79F5) | 0; let t = Math.imul(d ^ (d >>> 15), 1 | d);
  t = (t + Math.imul(t ^ (t >>> 7), 61 | t)) ^ t; return ((t ^ (t >>> 14)) >>> 0) / 2 ** 32; };
const pick = (a) => a[Math.floor(random() * a.length)];
const THEMES = [["story|tale", "literature", "short selection collection narrative fiction rural"],
  ["fable", "children's literature", "child illustrated school youth forest sleep"],
  ["history", "history", "ottoman republic archive document chronicle foundation"],
  ["ocean", "travel", "coast fisherman harbor ship island lighthouse"],
  ["mathematics", "science", "geometry number proof theory solution probability"],
  ["poetry", "poetry", "verse collected divan translation selection meter"]]
  .map(([k, subject, a]) => ({ k: k.split("|"), subject, core: a.split(" ") }));
const COMMON = "book volume edition publication review notes introduction glossary".split(" ");
const FIRST_NAMES = "James Emma Simon Nora Kevin Ocean Grace Owen Meredith Blake".split(" ");
const SURNAMES = "Stone Bishop Miller Hayes Reed Frost".split(" ");

export const documents = Array.from({ length: N }, (_, id) => {
  const t = pick(THEMES), draw = t.k[t.k.length > 1 && random() < 0.5 ? 1 : 0], sm = [draw, draw];
  const title = [...new Set([draw, pick(t.core), pick(t.core)])];
  t.core.forEach((s, j) => { if (random() < 1 / (1 + j * 0.42)) sm.push(s); });
  COMMON.forEach((s, j) => { if (random() < 0.55 / (1 + j * 0.28)) sm.push(s); });
  if (random() < 0.5) sm.push(pick(pick(THEMES).core));   // word leaking from another theme
  for (let k = sm.length - 1; k > 0; k -= 1) { const j = Math.floor(random() * (k + 1));
    [sm[k], sm[j]] = [sm[j], sm[k]]; }
  // the subject tag is a publisher decision: a quarter of documents do not match the text's theme
  return { id, title: title.join(" "), summary: sm.join(" "),
    subject: (random() < 0.25 ? pick(THEMES) : t).subject,
    author: `${pick(FIRST_NAMES)} ${pick(SURNAMES)}`, year: 1975 + Math.floor(random() ** 0.6 * 50),
    loans: Math.floor(random() ** 3 * 400) };
});

export const tokenize = (s) => s.toLocaleLowerCase("en-US").match(/[\p{L}\p{N}]+/gu) ?? [];
export function buildIndex(bs) {                          // per-field inverted index
  const idx = {};
  for (const a of FIELDS) {
    const postings = new Map(), lengths = new Float64Array(bs.length);
    for (const b of bs) {
      const ts = tokenize(b[a]), count = new Map();
      lengths[b.id] = ts.length;
      for (const t of ts) count.set(t, (count.get(t) ?? 0) + 1);
      for (const [t, tf] of count) {
        if (!postings.has(t)) postings.set(t, []);
        postings.get(t).push({ id: b.id, tf });
      }
    }
    idx[a] = { postings, lengths, avgLength: lengths.reduce((x, y) => x + y, 0) / bs.length };
  }
  return idx;
}
export function search(idx, query) {      // result list scored with equal field weight
  const terms = tokenize(query), k1 = 1.2, b = 0.75, p = new Map();
  for (const a of FIELDS) for (const t of terms) {
    const g = idx[a].postings.get(t);
    if (!g) continue;
    const idf = Math.log(1 + (N - g.length + 0.5) / (g.length + 0.5));
    for (const e of g) {
      const norm = 1 - b + (b * idx[a].lengths[e.id]) / idx[a].avgLength;
      p.set(e.id, (p.get(e.id) ?? 0) + (idf * e.tf * (k1 + 1)) / (e.tf + k1 * norm));
    }
  }
  return [...p].sort((x, y) => y[1] - x[1] || x[0] - y[0]);
}

Highlighting’s Per-Document Cost

The inverted index knows which term appears in which document, but not where in the text the term appears: what enters the index is the token, not the token’s character position. Highlighting wants exactly that information. There are two paths: store the position in the index, or re-scan the shown documents at query time.

// highlight.mjs — highlighting cost: re-scan at query time, or keep position in the index.
import { documents, buildIndex, search, tokenize, N, SEED } from "./corpus.mjs";
const idx = buildIndex(documents), QUERY = "ocean ship book";
const terms = new Set(tokenize(QUERY)), results = search(idx, QUERY);
const TOKEN_RE = /[\p{L}\p{N}]+/gu, fmt = (x) => Math.round(x).toLocaleString("en-US");

function scan(text) {                        // re-scan: tokenize, mark positions
  const positions = [];
  let count = 0;
  for (const m of text.matchAll(TOKEN_RE)) {
    count += 1;
    if (terms.has(m[0].toLocaleLowerCase("en-US"))) positions.push([m.index, m[0].length]);
  }
  return { characters: text.length, tokens: count, positions };
}
const WINDOW = 30;
const snippet = (text, positions, width = WINDOW) => {    // window around the first match
  if (positions.length === 0) return "";
  const start = Math.max(0, positions[0][0] - 12), more = start + width < text.length;
  let s = text.slice(start, start + width);
  if (more) s = s.slice(0, s.lastIndexOf(" "));
  return (start > 0 ? "…" : "") + s.replace(TOKEN_RE, (w) =>
    terms.has(w.toLocaleLowerCase("en-US")) ? `[${w}]` : w) + (more ? "…" : "");
};

console.log(`corpus ${N} documents, seed ${SEED}; query "${QUERY}" matched ${results.length} documents`);
console.log("shown".padEnd(12) + "re-scanned characters".padStart(28) +
  "tokens produced".padStart(19) + "matches found".padStart(17) +
  "left outside window".padStart(23));
for (const shown of [10, 50, 100]) {
  let chars = 0, toks = 0, matches = 0, outside = 0;
  for (const [id] of results.slice(0, shown)) {
    const titleScan = scan(documents[id].title), summaryScan = scan(documents[id].summary);
    chars += titleScan.characters + summaryScan.characters; toks += titleScan.tokens + summaryScan.tokens;
    matches += titleScan.positions.length + summaryScan.positions.length;
    const base = summaryScan.positions.length ? Math.max(0, summaryScan.positions[0][0] - 12) : 0;
    outside += summaryScan.positions.filter(([i]) => i < base || i >= base + WINDOW).length;
  }
  console.log(`${shown} documents`.padEnd(12) + fmt(chars).padStart(28) + fmt(toks).padStart(19) +
    fmt(matches).padStart(17) + `${outside}`.padStart(23));
}

let occurrences = 0, totalChars = 0;          // if a position index were built for the whole corpus
for (const b of documents) { occurrences += tokenize(b.title).length + tokenize(b.summary).length;
  totalChars += b.title.length + b.summary.length; }
console.log(`\nif a position index were chosen: ${fmt(occurrences)} token occurrences, 8 bytes per ` +
  `occurrence (start and length) = ${fmt(occurrences * 8)} bytes of permanent overhead`);
console.log(`if the same information is produced at query time there is no permanent overhead: only ` +
  `the shown documents' characters are scanned, out of the corpus's ${fmt(totalChars)} characters`);
for (const [id] of results.slice(0, 3)) {
  const summaryScan = scan(documents[id].summary), titleScan = scan(documents[id].title);
  console.log(`  ${documents[id].title.padEnd(24)} summary snippet: ` +
    `${snippet(documents[id].summary, summaryScan.positions) ||
      "(none, from title field: " + snippet(documents[id].title, titleScan.positions) + ")"}`);
}

corpus 1200 documents, seed 20260801; query "ocean ship book" matched 817 documents
shown              re-scanned characters    tokens produced    matches found    left outside window
10 documents                         656                107               60                     13
50 documents                       3,913                581              263                     65
100 documents                       7,476              1,103              493                    108

if a position index were chosen: 13,529 token occurrences, 8 bytes per occurrence (start and length) = 108,232 bytes of permanent overhead
if the same information is produced at query time there is no permanent overhead: only the shown documents' characters are scanned, out of the corpus's 103,849 characters
  ocean ship               summary snippet: [book] harbor volume coast…
  ocean coast ship         summary snippet: [ocean] [ship] [book] harbor…
  ocean ship harbor        summary snippet: [ocean] notes [ship] fisherman…

Highlighting changes neither the set nor the order: the matched 817 documents and their order are the same whether highlighting is on or off. The only thing that changes is the content of the shown line. Its cost, by contrast, is linear and depends on the number of documents shown: 656 characters and 107 tokens for ten documents, 7,476 characters and 1,103 tokens for a hundred documents. Page depth never appears in this table; highlighting the hundredth page’s ten documents does about as much work as the first page’s ten documents — around 656 characters either way.

The position-index row gives the price of the other path: eight bytes per occurrence for the whole corpus’s 13,529 token occurrences, a total of 108,232 bytes of permanent overhead. This cost is paid for every document, whereas highlighting is done only for the ten shown documents. If the index holds 1,200 documents while a query looks at ten of them, storing position means paying up front for the work of a hundred twenty documents. The decision follows this asymmetry: a position index wins when the text is long and the same documents are highlighted often; when the field is short, as in a catalog record, re-scanning is cheaper.

The last column counts highlighting’s own loss. Of the sixty matches found in ten documents, thirteen fall outside the thirty-character window; the reader never sees those matches at all. Enlarging the window lowers this number but lengthens the line. Highlighting does not show that a match exists; it shows only the surroundings of one of them.

Deep Pagination

Pagination’s cost is talked about as if it were a cursor held in a single sorted list. Once the index is split into shards, that stops being true: because no shard knows the full ranking, which shard the second page’s tenth document will come from can only be found by pulling enough candidates from every shard, starting from the beginning.

// paginate.mjs — deep pagination: candidates pulled per shard, cursor comparison, and drift.
import { documents, buildIndex, search } from "./corpus.mjs";
const idx = buildIndex(documents), QUERY = "ocean ship book", SHARDS = 4, PAGE_SIZE = 10, BYTES = 12;
const full = search(idx, QUERY), before = (a, b) => b[1] - a[1] || a[0] - b[0];
let shards = Array.from({ length: SHARDS }, (_, p) => full.filter(([id]) => id % SHARDS === p));
const BASE = shards.map((pz) => [...pz]);
const fmt = (x) => Math.round(x).toLocaleString("en-US");

const offsetPage = (page) => {                  // each shard returns from+size candidates from the start
  const start = (page - 1) * PAGE_SIZE, requested = start + PAGE_SIZE, pool = [];
  for (const pz of shards) pool.push(...pz.slice(0, requested));
  pool.sort(before);
  return { candidates: requested * SHARDS, page: pool.slice(start, start + PAGE_SIZE) };
};
const cursorPage = (cursor) => {                // each shard returns size candidates after the cursor
  const pool = [];
  for (const pz of shards)
    pool.push(...pz.filter((e) => cursor === null || before(e, cursor) > 0).slice(0, PAGE_SIZE));
  pool.sort(before);
  return pool.slice(0, PAGE_SIZE);
};

console.log(`query "${QUERY}": ${full.length} results, ${SHARDS} shards, page size ${PAGE_SIZE}`);
console.log("page".padEnd(7) + "offset candidates".padStart(19) + "cursor candidates".padStart(19) +
  "ratio".padStart(8) + "merge bytes".padStart(19) + "cumulative offset".padStart(20) +
  "cumulative cursor".padStart(19) + "same page".padStart(12));
let cumulative = 0, cursor = null, cursorResult = [];
for (let pageNum = 1; pageNum <= 20; pageNum += 1) {
  const offsetResult = offsetPage(pageNum);
  cumulative += offsetResult.candidates;
  cursorResult = cursorPage(cursor); cursor = cursorResult[cursorResult.length - 1];
  if (![1, 5, 10, 20].includes(pageNum)) continue;
  const same = offsetResult.page.every(([id], i) => id === cursorResult[i][0]);
  console.log(`${pageNum}`.padEnd(7) + fmt(offsetResult.candidates).padStart(19) +
    fmt(PAGE_SIZE * SHARDS).padStart(19) +
    `${(offsetResult.candidates / (PAGE_SIZE * SHARDS)).toFixed(0)}x`.padStart(8) +
    fmt(offsetResult.candidates * BYTES).padStart(19) + fmt(cumulative).padStart(20) +
    fmt(pageNum * PAGE_SIZE * SHARDS).padStart(19) + (same ? "yes" : "no").padStart(12));
}

const allIds = () => shards.flat().sort(before).map(([id]) => id);
const page1 = offsetPage(1).page, shown1 = new Set(page1.map(([id]) => id)), cursor1 = page1[page1.length - 1];
console.log("\nwhat happens on page 2 if the index changes after page 1 is shown");
console.log("change".padEnd(24) + "offset repeat".padStart(18) + "skipped".padStart(9) +
  "cursor repeat".padStart(16) + "skipped".padStart(9));
for (const [label, change] of [
  ["new document at the top", () => shards[0].unshift([-1, full[0][1] + 1])],
  ["delete from first page", () => { const x = page1[2][0];
    shards[x % SHARDS] = shards[x % SHARDS].filter(([id]) => id !== x); }]]) {
  shards = BASE.map((pz) => [...pz]);
  change();
  const updated = allIds();                     // skipped: those left before where page 2 now starts
  const counts = (p2) => [p2.filter((id) => shown1.has(id)).length,
    updated.slice(0, updated.indexOf(p2[0])).filter((id) => id >= 0 && !shown1.has(id)).length];
  const offsetCounts = counts(offsetPage(2).page.map(([id]) => id));
  const cursorCounts = counts(cursorPage(cursor1).map(([id]) => id));
  console.log(label.padEnd(24) + `${offsetCounts[0]}`.padStart(18) + `${offsetCounts[1]}`.padStart(9) +
    `${cursorCounts[0]}`.padStart(16) + `${cursorCounts[1]}`.padStart(9));
}

query "ocean ship book": 817 results, 4 shards, page size 10
page     offset candidates  cursor candidates   ratio        merge bytes   cumulative offset  cumulative cursor   same page
1                       40                 40      1x                480                  40                 40         yes
5                      200                 40      5x              2,400                 600                200         yes
10                     400                 40     10x              4,800               2,200                400         yes
20                     800                 40     20x              9,600               8,400                800         yes

what happens on page 2 if the index changes after page 1 is shown
change                       offset repeat  skipped   cursor repeat  skipped
new document at the top                  1        0               0        0
delete from first page                   0        1               0        0

The last column is the basis of the whole comparison: both paths produce the same page. The documents, and their order, are identical. The only thing that changes is the cost.

In offset pagination, the candidates pulled per shard equal the number skipped plus the page size; with four shards, page twenty means 800 candidates, of which 790 are discarded. The cost grows linearly with page depth and is multiplied by the shard count: the same page would want 1,600 candidates in an eight-shard index. In cursor-based navigation the number is fixed: 40 candidates on every page, because each shard is asked “the first ten documents after this score and this id,” and no counting from the start is needed.

The cumulative columns show the reader’s whole journey. A reader who visits twenty pages in sequence generates 8,400 candidates on the offset path and 800 on the cursor path. The offset path’s cumulative total grows quadratically, the cursor path’s grows linearly; at page twenty the difference is ten and a half times. Cursor navigation, however, cannot do one thing: it cannot jump straight to page twenty, because the cursor is not a rank number but the score and id of the last shown document. If navigation by page number is required, the offset path’s cost will be paid.

The lower table measures a third difference. If a document that will land at the very top is added to the index after page one is shown, a document the reader has already seen reappears on page two in the offset path. If a document on page one is deleted, a document that should have opened page two is never shown to the reader at all. On the cursor path both numbers are zero, because the cursor is not a counter but a value; whatever happens at the start of the list does not shift the window to the right of the cursor. Here, pagination style stops being a display preference and becomes a decision that determines the set the reader sees.

Summary

• Highlighting changes neither the set nor the order; its cost grows only with the number of documents shown: 656 characters and 107 tokens for ten documents, 7,476 characters and 1,103 tokens for a hundred documents.
• Keeping position in the index wants 108,232 bytes of permanent overhead for 13,529 token occurrences, and that cost is paid for every document; re-scanning works only for the ones shown.
• Highlighting hides matches that do not fit the window: thirteen of the sixty matches in ten documents fell outside the thirty-character window.
• In offset pagination, candidates per shard grow linearly with page depth and are multiplied by the shard count: page twenty wants 800 candidates across four shards, 9,600 bytes of merge overhead.
• Cursor navigation produces the same page at a fixed 40 candidates and gives no repeats or skips even when the index changes; in exchange, it gives up jumping by page number.

Next Step

The result page is now complete: the matching set has been determined, ranked, tuned, reduced to numbers, and put into the form shown to the reader. All of this work rests on a single assumption: the word in the query is the same word as the word in the document. In the catalog, this assumption often does not hold. A reader searching “tale” cannot see books titled “story”; for the inverted index there is no link at all between these two strings, and no adjustment so far can build that link, because both weight and function-based scoring only change the score of a term that has already matched. The next lesson builds an access method that compares not the word itself but the context the word appears in, and measures the set and order the two paths return, side by side.