Why LIKE '%word%' cannot use a B-tree, and what an inverted index does instead

# /// script
# requires-python = ">=3.10"
# dependencies = ["psycopg[binary]", "numpy"]
# ///
# Copyright (c) 2026 Aayush Sharma · SPDX-License-Identifier: MIT
# https://thedataengineering.com/lab-code/LICENSE.txt
"""Why LIKE '%word%' cannot use a B-tree.

One million short documents in PostgreSQL, words drawn with Zipfian
frequencies. A B-tree on the text and LIKE '%word%' for a rare word; then a
GIN full-text index and the same word with @@; then the most common word with
the GIN index.
Needs the PostgreSQL service from the compose file (port 56001).
"""
import argparse, json, re
import numpy as np, psycopg

p = argparse.ArgumentParser(description=__doc__.splitlines()[0])
p.add_argument("--dsn", default="postgresql://postgres:lab@localhost:56001/postgres", help="Connection string.")
p.add_argument("--docs", type=int, default=1_000_000, help="Documents.")
p.add_argument("--vocab", type=int, default=20_000, help="Vocabulary size.")
p.add_argument("--words", type=int, default=8, help="Words per document.")
p.add_argument("--json", help="Also write the results to this JSON file.")
args = p.parse_args()

rng = np.random.default_rng(0)
vocab = np.array([f"w{i}" for i in range(args.vocab)]); vocab[2000] = "kurta"                    # a rare word with a fixed name
prob = 1 / np.arange(1, args.vocab + 1); prob /= prob.sum()
idx = rng.choice(args.vocab, (args.docs, args.words), p=prob)
c = psycopg.connect(args.dsn, autocommit=True)
c.execute("DROP TABLE IF EXISTS docs"); c.execute("CREATE TABLE docs (id serial PRIMARY KEY, body text)")
with c.cursor().copy("COPY docs (body) FROM STDIN") as cp:
    for row in idx: cp.write_row((" ".join(vocab[row]),))
c.execute("CREATE INDEX docs_btree ON docs (body)"); c.execute("ANALYZE docs")
def run(sql):
    txt = "\n".join(r[0] for r in c.execute("EXPLAIN (ANALYZE) " + sql).fetchall())
    node = "GIN (Bitmap Index Scan)" if "Bitmap Index Scan" in txt else "B-tree index" if "Index" in txt else "sequential scan"
    return node, float(re.search(r"Execution Time: ([\d.]+)", txt).group(1)), c.execute(sql).fetchone()[0]
rows = []
n, t, k = run("SELECT count(*) FROM docs WHERE body LIKE '%kurta%'"); rows.append({"query": "LIKE '%kurta%' with a B-tree", "plan": n, "ms": t, "matches": k})
c.execute("CREATE INDEX docs_gin ON docs USING gin (to_tsvector('simple', body))"); c.execute("ANALYZE docs")
n, t, k = run("SELECT count(*) FROM docs WHERE to_tsvector('simple', body) @@ to_tsquery('simple', 'kurta')"); rows.append({"query": "@@ 'kurta' (rare) with GIN", "plan": n, "ms": t, "matches": k})
n, t, k = run("SELECT count(*) FROM docs WHERE to_tsvector('simple', body) @@ to_tsquery('simple', 'w0')"); rows.append({"query": "@@ 'w0' (most common) with GIN", "plan": n, "ms": t, "matches": k})
for r in rows: print(f"{r['query']:<32} {r['plan']:<25} {r['ms']:9.1f} ms   {r['matches']:>9,} matches")

if args.json:
    with open(args.json, "w") as f:
        json.dump({"tables": {"queries": rows}}, f)

# PostgreSQL for the why-like-word-cannot-use-a lab.
services:
  postgres:
    image: postgres:17.6
    command: ["postgres", "-c", "shared_buffers=512MB", "-c", "work_mem=64MB"]
    environment:
      POSTGRES_PASSWORD: lab
    ports: ["56001:5432"]
    healthcheck:
      test: ["CMD", "pg_isready", "-U", "postgres"]
      interval: 1s
      retries: 30