--- title: 'Highlighting and Pagination' source: 'https://academia.sh/en/courses/search-engines/highlighting-and-pagination' course: 'Search Engines and Text Retrieval' language: en updated: '2026-08-23T07:00:50+00:00' license: 'CC BY-SA 4.0' --- # Highlighting and Pagination The result's face shown to the reader: highlighting's per-document re-scan cost against the permanent byte overhead of storing position in the index, the linear growth with page depth of the candidate count pulled from each shard in deep pagination, cursor-based navigation producing the same page at a fixed cost, and the repeats and skips offset pagination produces when the index changes. 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. ```js // 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. ```js // 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. ```js // 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.