# DDIA Ch. 4: LIKE reads every row; an inverted index reads five buffers

## Concept

Finding a word in a text column with `LIKE '%word%'` forces a full table scan —
the leading wildcard defeats an ordinary index, so the database reads every row.
An **inverted index** (the structure behind full-text search) instead stores, for
each distinct word, the list of documents that contain it, so a lookup jumps
straight to the matches. On 5 million short documents you will find a rare word
with `ILIKE` in **~1.25 seconds** reading the whole table, then with a `tsvector`
+ GIN index in **~19 ms** whose index probe touches just **5 buffers** — ~65×
faster. The catch: the inverted index matches *words*, not arbitrary substrings.

## Provenance

*Designing Data-Intensive Applications*, 2nd ed. (Kleppmann & Riccomini,
2025), Chapter 4 — *Storage and Retrieval*, §"Full-Text Search":

> a full-text search index … allows you to search for a word and find all the
> documents … that contain that word.

The book frames full-text search as a specialized inverted index, distinct from
the key-lookup structures earlier in the chapter. Here you measure the gap
against the naive substring scan, and meet the semantic catch that comes with it.

## Prerequisites

The surprise is about which queries an index can serve. These help; each line
notes where it shows up.

1. **`LIKE '%x%'` and the leading wildcard** — a B-tree index orders strings by
   prefix, so it can accelerate `LIKE 'x%'` but not `LIKE '%x%'`; a leading
   wildcard forces a full scan.
2. **Inverted index** — a map from each *term* (word) to a postings list: the
   set of documents containing it. Looking up a word returns its matches
   directly, the way a book's index maps a word to page numbers.
3. **Tokenization / lexemes** — full-text search first splits text into words
   and normalizes them (lowercase, stem), then indexes those *lexemes* — not the
   raw character string.
4. **Postgres `tsvector` / `tsquery` / GIN** — `to_tsvector` turns text into its
   lexemes; a **GIN** (Generalized Inverted iNdex) indexes them; `@@` matches a
   `tsquery` against the `tsvector`.

### Where to learn them

- **Inverted indexes (#2):** DDIA §"Full-Text Search"; any IR (information
  retrieval) intro on inverted indexes and postings lists.
- **Postgres FTS (#3–#4):** the PostgreSQL manual, "Full Text Search" and the
  GIN index docs.
- **Substring search (#1):** the `pg_trgm` extension docs — the *other* tool,
  for when you genuinely need `LIKE '%…%'` to be fast (a Go-deeper below).

If only one is new, make it #2 — the inverted index is the whole idea.

## Environment

Reproducible plan shapes and row counts (buffer counts and timing vary a little
with cache state):

- macOS 26.5.2 (Darwin 25.5.0), arm64
- Docker 29.6.2 running the official `postgres:16` image → PostgreSQL 16.14
- One `docs` table, 5,000,000 short documents; ~5,000 contain the rare word
  `kestrel`

## Mental model

Five million short documents built from a small vocabulary; about one in a
thousand also contains the rare word `kestrel`. We find those two ways:

- **Substring scan** — `WHERE body ILIKE '%kestrel%'`. No index can help a
  leading wildcard, so Postgres reads and pattern-matches every row.
- **Inverted index** — a generated `tsvector` column (`body` split into lexemes)
  with a **GIN** index, queried as `WHERE body_tsv @@ to_tsquery('kestrel')`. The
  index maps the word `kestrel` straight to the ~5,000 documents that contain it.

We read `EXPLAIN (ANALYZE, BUFFERS)` for each. The whole exercise is one script,
`code/full_text_search.sql`.

## Setup

```
docker run -d --name ddia-ch4 -e POSTGRES_PASSWORD=study -e POSTGRES_DB=study postgres:16
sleep 3
docker cp full_text_search.sql ddia-ch4:/tmp/
docker exec ddia-ch4 psql -U postgres -d study -f /tmp/full_text_search.sql
```

Do **not** read the output yet — make each prediction first.

## Steps

### Step 1 — the substring scan (calibration)

**Predict.** `WHERE body ILIKE '%kestrel%'` over 5,000,000 rows, no full-text
index. How much of the table does Postgres read, and how long does it take?

**Observe.**

```
########## substring scan: WHERE body ILIKE '%kestrel%' (no usable index) ##########
 Finalize Aggregate (actual time=1246.827..1249.060 rows=1 loops=1)
   Buffers: shared hit=16138 read=26380 dirtied=8325 written=7857
   ->  Gather (actual time=1246.555..1249.055 rows=3 loops=1)
         Workers Planned: 2
         ->  Parallel Seq Scan on docs (actual time=1.130..1238.730 rows=1683 loops=3)
               Filter: (body ~~* '%kestrel%'::text)
               Rows Removed by Filter: 1664984
               Buffers: shared hit=16138 read=26380 dirtied=8325 written=7857
```

A **Parallel Seq Scan** over the whole table — ~42,500 buffers, ~**1.25 s** even
with two workers — to find the ~5,000 matches. The leading `%` means every one of
the 5,000,000 rows must be read and tested.

### Step 2 — the inverted index (the surprise)

**Predict.** Add a `tsvector` column and a GIN index, then query the word with
`@@`. How many buffers does the index probe itself read, and how much faster is
the whole query?

**Observe.**

```
########## inverted index: tsvector + GIN, WHERE body_tsv @@ to_tsquery('kestrel') ##########
 Aggregate (actual time=19.443..19.444 rows=1 loops=1)
   Buffers: shared hit=127 read=4791
   ->  Bitmap Heap Scan on docs (actual time=1.556..19.210 rows=5049 loops=1)
         Recheck Cond: (body_tsv @@ '''kestrel'''::tsquery)
         Heap Blocks: exact=4913
         Buffers: shared hit=127 read=4791
         ->  Bitmap Index Scan on docs_gin (actual time=1.117..1.118 rows=5049 loops=1)
               Index Cond: (body_tsv @@ '''kestrel'''::tsquery)
               Buffers: shared hit=5
```

**~19 ms — about 65× faster** — and look at the last line: the **Bitmap Index
Scan** that finds all 5,049 matching documents reads just **5 buffers**. The word
`kestrel` maps directly to its postings list. The remaining ~4,900 buffers are
the heap fetches to count the matched rows; the *search* itself was almost free.

### Step 3 — the catch: words, not substrings

**Predict.** The `ILIKE '%kes%'` version would also match `kestrel`. Can the GIN
index answer `WHERE body ILIKE '%kes%'` too?

**Observe.** No — and this is the semantic price. The inverted index is built on
**lexemes** (whole words), so it answers "which documents contain the *word*
`kestrel`," not "which contain the *substring* `kes`." `to_tsquery('kes')` would
match the token `kes`, which no document has; `ILIKE '%kes%'` (substring) can't
use the GIN index at all and falls back to the seq scan of Step 1. The 65× speedup
comes with a change of question: word/phrase search, not arbitrary substring.

## What you should see

- `ILIKE '%kestrel%'`: **Parallel Seq Scan**, whole table (~42,500 buffers),
  ~**1.25 s**.
- GIN full-text: **Bitmap Index Scan** for the word reads just **~5 buffers**;
  whole query ~**19 ms** (~**65×** faster, ~8–9× fewer buffers total).
- The inverted index matches **words**, not substrings — a different query, not a
  drop-in replacement for `LIKE '%…%'`.

## Why

`LIKE '%kestrel%'` asks whether a pattern appears *anywhere* in each string. A
B-tree orders strings by their prefix, so it can narrow `LIKE 'kestrel%'` but has
nothing to offer once the pattern can start at any position — the planner has no
choice but to read every row and run the matcher, which is the Parallel Seq Scan
over all 5,000,000 rows.

An inverted index turns the question around. When the `tsvector` is built,
Postgres tokenizes each document into lexemes and, in the GIN index, records for
every distinct word the sorted list of rows that contain it (its postings list).
Querying `@@ to_tsquery('kestrel')` is then a lookup of one word in that
dictionary followed by a walk of its postings — the 5-buffer Bitmap Index Scan —
returning the ~5,000 matching row locations directly. The database never looks at
documents that lack the word. That is the same idea as the index at the back of a
book: you don't reread the book to find a term, you look the term up and get the
page numbers.

**The boundary — a different question, and a write-time cost.** An inverted index
is superb at "documents containing this word/phrase" and useless for "strings
containing these characters." A genuine substring query (`LIKE '%kes%'`) needs a
*different* structure — Postgres's `pg_trgm` trigram GIN index, which indexes
3-character grams — because the token-based index simply doesn't contain
substrings. And the speed isn't free: the `tsvector` must be computed and the GIN
index maintained on every insert and update, so full-text search trades write
throughput and storage for read speed. This is exactly the book's point that
full-text search is its own specialized index, not the key-lookup structures used
elsewhere in the chapter.

### Go deeper

1. **Two words.** Query `to_tsquery('kestrel & alpha')` and compare the plan to
   the single-word case. Predict whether the index intersects two postings lists
   or falls back to rechecking rows.
2. **Make substrings fast.** `CREATE EXTENSION pg_trgm; CREATE INDEX … USING gin
   (body gin_trgm_ops);` then re-run `ILIKE '%kes%'`. Predict whether the trigram
   index now serves the substring query the `tsvector` couldn't.
3. **Pay at write time.** Time inserting 1,000,000 more rows with vs. without the
   GIN index present. Predict how much the index maintenance costs the writes —
   the other side of the read speedup.