Search Engine vs. Database

The In-Memory Stores and Caching Systems course closed on one assumption shared by every access it covered: the key of what was being searched for was known. A session id, a counter name, a sorted set’s name was given, and the store found that name and returned the value. The relational side worked the same way — the index was built on a key, and the query reached that key through an equality, range, or prefix condition.

Questions in a library catalog do not arrive that way. A reader does not remember the book’s identity, only two words that appear in its summary: “books whose summary contains deniz (sea) and çocuk (child).” This question does not reach toward a key, it reaches into the text. This course builds that question, and every lesson counts the same two things: how a decision changed which documents came back, how it changed which order they came back in, and what that decision cost. A more relevant result does not count as a decision in this course.

Going by Word, Not by Key

A relational index is a structure sorted on the entire value. It answers equality, range, and prefix questions through that sort order; once the part being searched for is not at the start of the value, the sort order has nothing left to say. LIKE '%deniz%' is exactly this case: because the match can sit anywhere in the text, the index is skipped and every row is read. Index theory was built in M17/K04; the only point that matters here is that the index cannot help with this question.

The inverted index does the opposite. It does not go from document to its fields, it goes from term to documents: the text is split into words, and for each word the ids of the documents it appears in are stored. When the question arrives, no table is read, only the lists for two terms. The structure’s name and its byte accounting are built in the next lesson; this lesson only compares what the two paths answer to the same question.

The Same Question, Two Paths

The measurement uses a corpus generated from a library catalog, and this corpus stays the same across all three topics in the course. IA1: the corpus carries 600 book records, seed 20250317; each record holds a title, summary, subject tags, author, year, language, and shelf code; the summary averages 25 words and the word pool is limited — this keeps the term count smaller than a real catalog would, without changing the ratios. IA2: on the relational path, the number of rows scanned is the table’s row count; the query plan’s SCAN line confirms this, and the bytes read are the summary field’s total bytes. IA3: an index entry is counted as a 4-byte document id. IA4: the list of inflected forms is given by hand; the classification rests on this ten-form table.

// search/catalog.mjs — corpus shared by three topics: generated from a library catalog,
// 600 book records, seed 20250317. Fields: title, summary, subjects, author, year, language, shelf.
export const SEED = 20250317, DOC_COUNT = 600;
let state = SEED;
const random = () => (state = (state * 1103515245 + 12345) % 2147483648) / 2147483648;
const pick = (d) => d[Math.floor(random() * d.length)];
const pickSkewed = (d) => d[Math.floor(random() ** 2 * d.length)];   // frequency is skewed in real text
const splitBar = (s) => s.split("|");

// stem forms: base, genitive, plural, dative, ablative, locative
export const STEMS = splitBar("deniz denizin denizler denize denizden denizde|kitap kitabın kitaplar kitaba \
kitaptan kitapta|çocuk çocuğun çocuklar çocuğa çocuktan çocukta|şehir şehrin şehirler şehre \
şehirden şehirde|yol yolun yollar yola yoldan yolda|ada adanın adalar adaya adadan adada|bahçe \
bahçenin bahçeler bahçeye bahçeden bahçede|mektup mektubun mektuplar mektuba mektuptan mektupta|\
gemi geminin gemiler gemiye gemiden gemide|köprü köprünün köprüler köprüye köprüden köprüde|\
okul okulun okullar okula okuldan okulda|kuş kuşun kuşlar kuşa kuştan kuşta").map((s) => s.split(" "));
const PATTERNS = splitBar("0 {} ve gündelik hayat üzerine notlar sunar|0 {} bu derlemenin ana izleğidir|\
1 {} tarihine geniş yer ayırır|1 {} çevresinde gelişen olayları anlatır|2 {} üzerine derlenmiş \
yazılar içerir|2 {} hakkında kısa öyküler toplar|3 {} açılan bir yolculuğu izler|4 {} toplanmış \
belgeleri sıralar|5 {} tutulan günlüklerden seçmeler verir|5 {} geçen bölümleri İstanbul'un eski \
mahallelerine bağlar").map((s) => [Number(s[0]), s.slice(2)]);
const PATTERNS2 = splitBar("{Y} kütüphanesinde tutulan {N} üzerine kuruludur|{N} arasından seçilmiş \
örnekler taşır|{Y} ve çevresindeki {N} listesini verir|{Y} basımı bir {N} derlemesine dayanır");
const EXTRA = splitBar("denizci gelenekleri üzerine bir ek bölüm bulunur|Karadeniz kıyısındaki kasabaları \
anlatır|çocukluk anılarına yer verir|kitapçı raflarındaki dağılımı tartışır|yolculuk notlarıyla \
kapanır|adacıklardaki kuş türlerini sayar");
const PLACES = splitBar("Ankara|İzmir|Trabzon|Kars|Bursa|Edirne|Sinop|Antakya");
const OBJECTS = splitBar("harita|fotoğraf|söyleşi|günlük|arşiv belgesi|liman kaydı|kasaba adı|el yazması|gazete kupürü|şarkı sözü");
const PREFIXES = splitBar("Uzak|Kayıp|Sessiz|Eski|Kısa|Büyük|Küçük|Unutulmuş|Beyaz|Yedi");
const SUFFIXES = splitBar("Günleri|Öyküleri|Üzerine Notlar|Anıları|Sözlüğü|Rehberi|Yılları|Defteri");
const SUBJECTS = splitBar("çocuk edebiyatı|roman|kısa öykü|şiir|deniz tarihi|coğrafya|biyografi|gezi yazısı|halk bilimi|mimarlık|müzik|felsefe");
const FIRST_NAMES = splitBar("Ahmet|Ayşe|Zeynep|Cemal|Nuran|Selim|Elif|Kerem|Hatice|Bedri|Sevgi|Nazlı");
const LAST_NAMES = splitBar("Yılmaz|Kaya|Demir|Şahin|Çelik|Aydın|Doğan|Arslan|Koç|Ertem");
const LANGUAGES = splitBar("Türkçe|Türkçe|Türkçe|İngilizce|Almanca|Fransızca");

const capitalize = (s) => s[0].toLocaleUpperCase("tr") + s.slice(1);
function generateSummary() {
  const parts = [];
  for (let i = 0; i < 3; i += 1) { const [d, k] = pickSkewed(PATTERNS); parts.push(k.replace("{}", pickSkewed(STEMS)[d])); }
  parts.push(pick(PATTERNS2).replace("{Y}", pick(PLACES)).replace("{N}", pick(OBJECTS)));
  if (random() < 0.45) parts.push(pick(EXTRA));
  return capitalize(parts.join(", ")) + ".";
}
function generateTitle() {
  const k = pickSkewed(STEMS), o = pick(PREFIXES), s = pick(SUFFIXES), t = random();
  if (t < 0.25) return `${o} ${capitalize(k[2])}`;
  if (t < 0.5) return `${capitalize(k[0])} ${s}`;
  if (t < 0.75) return `${o} ${capitalize(k[0])} ${s}`;
  return `${capitalize(k[1])} ${s}`;
}
export const corpus = [];
for (let i = 1; i <= DOC_COUNT; i += 1) {
  const subjects = [pick(SUBJECTS)];
  if (random() < 0.55) subjects.push(pick(SUBJECTS));
  if (random() < 0.2) subjects.push(pick(SUBJECTS));
  corpus.push({
    id: i, title: generateTitle(), summary: generateSummary(), subjects: [...new Set(subjects)], author: `${pick(FIRST_NAMES)} ${pick(LAST_NAMES)}`,
    year: 1968 + Math.floor(random() * 57), language: pick(LANGUAGES),
    shelf: `${pick(splitBar("TR|EN|DE|FR"))}-${800 + Math.floor(random() * 99)}.${Math.floor(random() * 9)}`,
  });
}

// search/scan.mjs — the same question in two structures: a relational LIKE scan versus an
// inverted index mapping term to document. Scanned unit, returned set, extra and missed docs are counted.
import { DatabaseSync } from "node:sqlite";
import { corpus, DOC_COUNT, SEED } from "./catalog.mjs";

const db = new DatabaseSync(":memory:");
db.exec("CREATE TABLE book(id INTEGER PRIMARY KEY, title TEXT, summary TEXT)");
const insert = db.prepare("INSERT INTO book VALUES (?, ?, ?)");
for (const b of corpus) insert.run(b.id, b.title, b.summary);
db.exec("CREATE INDEX book_summary ON book(summary)");        // B-tree index: on the summary field
const plan = db.prepare("EXPLAIN QUERY PLAN SELECT id FROM book WHERE summary LIKE ?").all("%deniz%");
const like = (...s) => db.prepare(`SELECT id FROM book WHERE ${s.map(() => "summary LIKE ?").join(" AND ")}`)
  .all(...s.map((x) => `%${x}%`)).map((r) => r.id);

// --- inverted index: tokenization and Turkish lowercasing; stemming is not part of this lesson ---
const tokenize = (s) => s.toLocaleLowerCase("tr").split(/[^\p{L}\p{N}]+/u).filter(Boolean);
const index = new Map();
for (const b of corpus) {
  for (const t of new Set(tokenize(b.summary))) {
    if (!index.has(t)) index.set(t, []);
    index.get(t).push(b.id);
  }
}
const search = (...terms) => {
  const lists = terms.map((t) => index.get(t) ?? []);
  const shortest = lists.reduce((a, l) => (l.length < a.length ? l : a));
  return { results: shortest.filter((id) => lists.every((l) => l.includes(id))),
    postings: lists.reduce((t, l) => t + l.length, 0) };
};

const bytes = corpus.reduce((t, b) => t + Buffer.byteLength(b.summary), 0);
console.log(`seed ${SEED}; corpus ${DOC_COUNT} docs, summary field ${bytes} bytes, ${index.size} terms in index`);
console.log(`query plan: ${plan[0].detail} — every row is still read even with the B-tree index`);

const query = ["deniz", "çocuk"];
const likeIds = like(...query), indexResult = search(...query);
const INFLECTED_FORMS = new Set(["denizin", "denizler", "denize", "denizden", "denizde",
  "çocuğun", "çocuklar", "çocuğa", "çocuktan", "çocukta"]);   // IA4: known inflection table
const extra = likeIds.filter((id) => !indexResult.results.includes(id));
const inflected = extra.filter((id) => tokenize(corpus[id - 1].summary).some((t) => INFLECTED_FORMS.has(t)));
console.log(`\nquery: books with "${query.join('" and "')}" in the summary`);
console.log(`${"path".padEnd(16)}${"scanned unit".padStart(15)}${"bytes read".padStart(13)}` +
  `${"docs returned".padStart(15)}${"first four ids".padStart(20)}`);
console.log("relational LIKE".padEnd(16) + `${DOC_COUNT} rows`.padStart(15) + String(bytes).padStart(13) +
  String(likeIds.length).padStart(15) + likeIds.slice(0, 4).join(",").padStart(20));
console.log("inverted index".padEnd(16) + `${indexResult.postings} postings`.padStart(15) + String(indexResult.postings * 4).padStart(13) +
  String(indexResult.results.length).padStart(15) + indexResult.results.slice(0, 4).join(",").padStart(20));

console.log(`\nLIKE brings back ${extra.length} extra docs, of two kinds:`);
const example = (cond) => extra.find((id) => cond(tokenize(corpus[id - 1].summary)));
for (const [label, id] of [["inflected form (the index misses it)", example((t) => t.some((x) => INFLECTED_FORMS.has(x)))],
  ["match inside another word", example((t) => !t.some((x) => INFLECTED_FORMS.has(x)))]]) {
  const matching = tokenize(corpus[id - 1].summary).filter((t) => t.includes("deniz") || t.includes("çocuk"));
  console.log(`  ${label}: #${id} -> ${[...new Set(matching)].join(", ")}`);
}
console.log(`  ${inflected.length} docs of the first kind, ${extra.length - inflected.length} docs of the second kind`);

for (const variant of ["istanbul", "İstanbul"]) {
  const l = like(variant), d = search(variant.toLocaleLowerCase("tr"));
  console.log(`\nquery "${variant}": LIKE ${l.length} docs (${DOC_COUNT} rows scanned), ` +
    `inverted index ${d.results.length} docs (${d.postings} postings scanned)`);
}

seed 20250317; corpus 600 docs, summary field 124863 bytes, 170 terms in index
query plan: SCAN book USING COVERING INDEX book_summary — every row is still read even with the B-tree index

query: books with "deniz" and "çocuk" in the summary
path               scanned unit   bytes read  docs returned      first four ids
relational LIKE        600 rows       124863             68     237,333,364,490
inverted index     269 postings         1076             12        8,77,107,118

LIKE brings back 59 extra docs, of two kinds:
  inflected form (the index misses it): #237 -> denizler, çocuklar
  match inside another word: #14 -> deniz, çocukluk
  43 docs of the first kind, 16 docs of the second kind

query "istanbul": LIKE 0 docs (600 rows scanned), inverted index 73 docs (73 postings scanned)

query "İstanbul": LIKE 73 docs (600 rows scanned), inverted index 73 docs (73 postings scanned)

Where the Set Difference Comes From

The two paths answer the same question differently: LIKE returns 68 documents, the inverted index 12. The 59-document gap does not reduce to one cause — it has two separate sources, and the output counts them separately.

The first source is inflection, and it covers 43 documents. Record #237‘s summary carries the forms “denizler” and “çocuklar”. By the reader’s question this document is relevant; the inverted index misses it, because the index in this lesson stores the word as written, and “denizler” and “deniz” become two separate terms. This is not a shortcoming of the index but a setting — which form a word is stored in is a separate decision made in the third lesson.

The second source is a match inside the stem and it covers 16 documents. Record #14’s summary contains “çocuk”, but the word satisfying the second condition is “çocukluk” (childhood): LIKE '%çocuk%' looks at a character sequence in the middle of the text and does not recognize word boundaries. The same source also matches “denizci”, “Karadeniz”, and “kitapçı”. These documents are brought to the question by mistake and mislead the reader.

The last two lines show the other end of the set. The “İstanbul” query returns 73 documents through LIKE, and the same question written in lowercase returns zero documents. The reason is specific to Turkish: the lowercase of the letter İ is not i, it is a non-ASCII letter, and case folding does not recognize this pair. The inverted index returns 73 documents for both spellings, because the text is put through the same transformation both when it is indexed and when it is queried. This is exactly where a search engine departs from a relational scan: applying the same transformation at write time and at query time.

Order and Cost

The order column makes a third difference visible. LIKE starts with the ids 237, 333, 364, 490; this order is not id order, it is the order of the covering index the query plan chose for itself. The inverted index starts with 8, 77, 107, 118, that is, document id order. What the two orders share is this: neither is a chosen order. Both fall out of the structure’s storage layout. Which document is more relevant is asked for the first time in this course only in the second topic.

The cost side is not symmetric either. LIKE requires no preparation: a record is searchable the moment it is written, but every question reads 600 records and 124,863 bytes. The inverted index answers the question by reading 269 postings, touching roughly 1,076 bytes — a hundred and sixteen times smaller by bytes read. In return, the index must be built and stored; every new document must be processed into the index, and this structure takes up space. What this lesson measures is only the query side; the write side’s accounting is worked out byte by byte in the next lesson.

Summary

• A relational index is sorted on the entire value and cannot help a LIKE '%word%' question; the query plan shows SCAN even with an index present, and all 600 records are read.
• The inverted index goes from term to document: the same question is answered by reading 269 postings, and the bytes touched drop from 124,863 to 1,076.
• The two paths’ sets are not the same: LIKE returns 68, the inverted index 12. Of the 59-document gap, 43 are inflected forms (which the index misses), 16 are matches inside a stem (which LIKE brings back by mistake).
• Case makes the set flip entirely in Turkish: the “istanbul” query returns 0 documents through LIKE, “İstanbul” returns 73; the inverted index puts both spellings through the same rule at write time and query time, so it returns 73 documents for either spelling.
• Neither path’s returned order is a chosen order either: one is the order the query plan’s index uses, the other is document id. The question of relevance is not asked at all in this topic.

Next Step

This lesson used the inverted index as a black box: a term went in, document ids came out. What is inside the structure, how many bytes it holds, and where a document’s count of the same term is stored were not asked. The next lesson builds the index piece by piece: the term list, the document list under each term, the term count per document, and the word’s position in the text. What gets measured is each of these four components’ cost in bytes, and how many times position information makes the index grow.