Inverted indexes

The problem: searching link titles

Snip's team plan adds a search box to the dashboard. A marketing agency with 2 million links types summer shoes and expects, in a fraction of a second, every link whose title, destination, tags or notes mention those words.

The obvious query:

SELECT code, title FROM links
 WHERE owner_id = 4821 AND title ILIKE '%summer%' AND title ILIKE '%shoes%';

A B-tree index can find values by their beginning, but %shoes% can start anywhere, so Postgres reads every one of the owner's 2 million titles. It also misses "Shoe sale" (singular) and "SHOES" written differently, and it can't rank the results. Search needs a different index, built the other way round.

Turn it inside out

A normal index maps a row to its contents. An inverted index maps each term to the documents containing it:

To find documents containing summer and shoe, read two short lists and intersect them: {1}. The cost depends on how many documents contain the terms, not on how many documents exist.

Analysis: deciding what a "term" is

Before text goes into the index, and before a query is looked up, both pass through the same analyzer:

1. Tokenize: split into words. "Kids' shoes: back-to-school" → kids, shoes, back, to, school.
2. Normalize: lowercase, strip accents.
3. Remove stop words: words so common they're useless for searching ("the", "to", "and").
4. Stem: reduce words to a common root, so "shoes" and "shoe" become the same term.

Analysis is where most search quality is won or lost. If the index stems and the query doesn't, nothing matches. Snip analyses titles and tags with an English stemmer, and destination URLs differently: split on /, . and -, no stemming.

A small inverted index

const STOP = new Set(["a", "an", "and", "the", "to", "for", "of", "on"]);

export const analyze = (text: string) =>
  text
    .toLowerCase()
    .split(/[^a-z0-9]+/)
    .filter((t) => t && !STOP.has(t))
    .map((t) => (t.length > 3 && t.endsWith("s") && !t.endsWith("ss") ? t.slice(0, -1) : t)); // a crude stemmer

export class InvertedIndex {
  private postings = new Map<string, number[]>(); // term -> sorted document IDs

  add(docId: number, text: string) {
    for (const term of new Set(analyze(text))) {
      const list = this.postings.get(term) ?? [];
      list.push(docId); // IDs are added in increasing order, so lists stay sorted
      this.postings.set(term, list);
    }
  }

  /** Documents containing every query term: intersect the posting lists, shortest first. */
  search(query: string): number[] {
    const lists = [...new Set(analyze(query))].map((t) => this.postings.get(t) ?? []).sort((a, b) => a.length - b.length);
    if (lists.length === 0) return [];
    return lists.reduce((acc, list) => intersect(acc, list));
  }
}

function intersect(a: number[], b: number[]) {
  const out: number[] = [];
  let i = 0;
  let j = 0;
  while (i < a.length && j < b.length) {
    if (a[i] === b[j]) {
      out.push(a[i]);
      i++;
      j++;
    } else if (a[i] < b[j]) i++;
    else j++;
  }
  return out;
}

Tested on six titles: shoes found four of them (singular and plural alike), shoe sale found the two with both words, and a word not in any title found nothing. On 5,000 random documents, every query returned exactly what a brute-force scan returned. Intersecting the shortest list first keeps the work small: a rare word cuts the candidates down before the common words are checked.

What real engines add

• Positions in each posting, so phrase queries ("summer sale" as adjacent words) and highlighting work.
• Compression: sorted IDs are stored as small gaps between neighbours, packed into few bits.
• Segments: Lucene, the library inside Elasticsearch and OpenSearch, writes new documents into small immutable index segments and merges them in the background, like an LSM-tree's files (09.03 The LSM write and read path). A deleted document is marked deleted and removed at the next merge.
• Scores: finding matches is half the job; ordering them is the other (10.02 Ranking: TF-IDF to BM25).

Postgres can do it too

Postgres has full-text search built in: to_tsvector analyses text into normalized terms (lexemes), and a GIN index, short for Generalized Inverted Index, is an inverted index over them:

ALTER TABLE links ADD COLUMN search tsvector
  GENERATED ALWAYS AS (to_tsvector('english', coalesce(title, '') || ' ' || coalesce(notes, ''))) STORED;
CREATE INDEX links_search ON links USING GIN (search);

SELECT code, title FROM links
 WHERE owner_id = 4821 AND search @@ plainto_tsquery('english', 'summer shoes');

For Snip's first version, this is enough, with no new system to run. A dedicated search engine earns its place when ranking, typo tolerance, facets and scale outgrow it (10.03 Keeping a search index in sync).

Recap

Interview questions