The library that couldn’t find its own books
Picture a library. Not a cozy one — tens of millions of books, still growing, and nobody knows ahead of time what shelf a new book will need or how big the library will eventually get. People walk up to the front desk constantly: “find me books matching this, sorted like that, show me page such-and-such.” On a real library of roughly 25 million books, that simple ask could take the librarian 30 minutes — and the front desk just… hung there, waiting.
The obvious guess is “25 million books is just too many for one librarian.” That guess is wrong, and that’s the whole story: a correctly organized catalog answers in single-digit milliseconds and stays that fast no matter how many books get added. Thirty minutes wasn’t a size problem. It was a catalog problem — four of them, actually, all stacked on top of each other:
Problem #1: the catalog was organized by the wrong thing
The library did have a catalog — just not one that matched what people actually asked for. It was filed by “date the book arrived,” because that’s what made receiving new shipments easy. Nobody had filed cards by author or subject — the columns the front desk grid actually filters and sorts by. Ask “books by this author, sorted by title,” and the librarian still has to check every single card, then manually shuffle the matches into order afterward. That’s a full shelf walk plus an improvised sort, on every request.
Problem #2: counting from zero, every single page
Ask for page 500, and someone has to walk past the first 12,475 matching books one at a time just to know where page 500 starts. There’s no shortcut, because nothing kept track of where earlier pages left off:
The fix is almost embarrassingly simple: leave a bookmark. Remember the last book you handed someone, and next time, start exactly there instead of counting from the beginning:
Problem #3: recounting the whole shelf, just in case
Every single request, the librarian also stopped to count the entire matching set from scratch — not because anyone asked “how many books match,” but because the grid always showed that number, whether or not a person was actually looking at it. A second full walk, stacked on top of the first, on every page, every time.
Problem #4: the one where you don’t even know the title
This is the one that actually mattered. Someone remembers the word “dragon” appears somewhere inside a book — could be page one, could be page eight hundred, could be the title or a random sentence in the middle. There’s no catalog card for “contains this word buried anywhere,” so the only honest way to answer is to open every single book and read it, cover to cover:
Fine when “dragon” shows up constantly — the librarian finds one fast and stops. Brutal when it doesn’t show up at all, or when the results also need sorting: 60 to 80 seconds, on exactly the case a person typing a partial search term triggers most often.
Proving it before touching the real library
None of this got fixed by guessing. A throwaway library was built first — 25,000,000 fake books on a spare shelf, shaped like the real thing — and every question was timed with the database’s own stopwatch (its query-plan explainer). That turned “I think this index will help” into real before-and-after numbers, before any of it touched production.
The fix that’s free: reorganize, remember, stop overcounting
Three changes, no new infrastructure, no new anything — just doing the obvious things right:
- A catalog shaped like the actual question — cards filed in the order people search (equality, then sort, then range), instead of the order books arrived.
- A bookmark instead of a head count — resume from the last position seen, never walk the aisle from zero again.
- Stop counting the whole shelf by default — only do it if someone’s actually looking at that number.
That alone took the reported 30-minute case to sub-second for everything except the “contains this word somewhere” question. That one needed an actual trick.
The trick: chop every book into 4-letter pieces
Here’s the idea. Instead of asking “does this book contain ‘dragon’?” — a question with no
shortcut — pre-chop every book’s text into overlapping little pieces, four letters at a time:
drag, rago, agon, and so on. Build a tiny, fast card for every one of those pieces, listing
which books contain it. Now, to find “dragon,” look up the pieces instead of the books, get a
short list of candidates, and only then open those few books to confirm the letters actually
sit next to each other in the right order:
Three approaches got measured side by side at 25 million books:
- Do nothing (read every book): fine when matches are common, 60–80 seconds when they’re not, worse combined with sorting.
- A specialized off-the-shelf chunking service (a vendor-specific native n-gram index): handled plain “contains” fine, but fell to roughly 49 seconds the moment sorting joined in — exactly the combination the real grid needs.
- Chop the books ourselves, on the shelves we already have: no new service, no new license, and it took the worst case from ~80 seconds to about 1 millisecond.
Hiring an entirely separate outside search bureau (a dedicated search engine, evaluated and shelved) was on the table too — the standard answer once fuzzy, faceted search at real scale becomes the actual job. It would mean a whole new service and a live feed keeping it in sync, per library, per site — more than this problem asked for. Parked as the next step if that requirement ever shows up for real, not the answer to today’s problem.
Not every shelf needs the chunk trick, either — small collections answer in milliseconds with no catalog at all, so it only gets built for shelves that actually grow large enough to need it, and it prunes itself based on which chunks people actually search for.
The label taped to the cover
Some books don’t contain the word themselves — they just carry a little card taped to the cover, pointing at something else (“See also: the big book about Bratislava”). People search those taped-on labels too, and the same “read every book” problem applies to them, just as badly: a second benchmark, this time on 8.4 million realistically-shaped books, found a no-match search against one of these labels took about 2.7 seconds — which becomes roughly 16 seconds once the library grows to 50 million. Folding those labels into the same chunk catalog closed the gap the same way: ~2.7 seconds down to ~2 milliseconds for a no-match, and a dense match (hundreds of thousands of hits) from ~900 milliseconds down to ~10.
Two shelves that skip the trick entirely
“Starts with” and “ends with” don’t need chunking at all. Keep one shelf sorted the normal way for “starts with.” Keep a second, imaginary shelf sorted by each book’s last letter first — suddenly “ends with” is exactly the same kind of lookup, just on the reversed shelf. Two cheap, derived shelves, and three of the grid’s most common questions stop needing to open a single book.
The shelf right next to the front desk
The chunk catalog isn’t free — it takes real space. And the honest question at tens of millions of books is whether it fits on the shelf right next to the front desk, where the librarian can reach it instantly, or whether it spills into the back warehouse:
When the catalog starts crowding that shelf, the fixes stack in order of effort:
- Compress the cards — a free setting change, cuts the catalog’s size by 40–50%.
- Only chunk what people actually search that way — not every field needs it, so scoping to the ones flagged searchable roughly halves the coverage.
- Skip small shelves entirely — below a few hundred thousand books, a plain walk is already millisecond-fast, so don’t bother building the catalog at all until a shelf grows large enough to need it.
- Get selective — for the shelves that still don’t fit, chunk only the one or two fields people actually filter on, guided by the database’s own usage stats, and drop the rest.
- Shrink the books themselves — old, versioned history stored inline inside each book padded them out several-fold; moving that history to its own building shrinks every book left on the shelf, which means the front-desk shelf now holds several times more books for the same space.
The one thing this doesn’t fully fix
Ask for “books containing this word, sorted by that column,” and there’s still a wall — the librarian has to gather every possible match before she can even start sorting the pile. That’s not a catalog problem anymore, it’s the same “counting from zero” problem from Problem #2, showing up again in a different shape. The bookmark trick fixes it the same way it did before — it just needs to be applied at that layer too, which means the front desk itself has to ask for “the next page after this bookmark” instead of “page 500.”
Checking the rulebook, not assuming it
This library isn’t a public service someone else rents out — it’s self-hosted, often air-gapped, running entirely behind the application for the people who use it. That distinction matters: the open-source license terms this database ships under only get restrictive once you start offering the database itself as a rented service to others. Verified against the actual license text before committing to this approach, not assumed. The fix adds zero new third-party licenses either way.
How the story ends now
- Filtered search: 30+ minutes → sub-second, flat from small collections all the way to 50 million books.
- Worst-case “contains” search: ~80 seconds → ~1 millisecond. Worst-case label search: ~2.7 seconds → ~2 milliseconds.
- No new infrastructure, no new third-party license, no changes required from the people using the library.
- Shipped in stages — free fixes first, then the self-provisioning catalog, then the chunk trick — so the library got faster in steps, instead of everyone waiting on the whole design at once.