Search: The Inverted Index

Marlow Books is an online bookshop run by four people that exists only in this course, and on the evening of Tuesday 6 October a customer emailed to ask why the shop had stopped selling It.

The shop had not stopped selling It. There were eleven copies of the Stephen King novel in the warehouse, the book's page rendered, the price was right, and the customer's own order from March was sitting in the database with a delivery date and a four star review they had written themselves.

Then the founder typed it into the shop's search box and got nothing back. Not the wrong books. Zero rows, for a word that is the whole title of a book the shop sells one of most weeks.

The explanation is one statement long.

SELECT to_tsvector('english', 'It');

 to_tsvector
-------------

(1 row)

Empty. Postgres read the title, found one word, decided that word carries no meaning, and threw it away before the index ever saw it. The query side runs the same machinery over whatever the customer types, so a search for it is a search for nothing, and nothing matches nothing. No code was wrong that evening. One defensible decision in a dictionary file, made by people who have never seen this catalogue, deleted a book from a shop.

That file is part of the structure lesson 010 pointed at and refused to open: "an inverted index over 1.2 million descriptions is not cheap at all; lesson 045 opens that structure up." Lesson 043 pointed at it again and labelled that section's figures an underestimate because of it. So here it is, including the bill 043 would not write.

A term, a sorted list of documents, and that is the whole idea

Start with the direction you already have. A row holds a title, a description and, for Marlow, the reviews customers have left, and if you have the row you can read its words. That is the forward direction, and it is what a LIKE '%london%' uses: open every row, read the text, look for the string. Over 1.2 million titles that is a sequential pass through everything, and because lesson 043's TOAST moves the big text values out of line, it is a pass through both the table and the side table the text actually lives in. Call it three gigabytes read to answer one query.

Lesson 002's two gigabytes a second makes that a second and a half of pure reading, per search, with sixteen searches a second arriving at the Christmas peak.

It does not survive its own arithmetic.

An inverted index turns the arrow round. Instead of document to words, it stores word to documents. One entry per distinct word, and hanging off each entry a posting list: the identifiers of every document that contains it, in ascending order. The word is the key. The sorted list is the value. Everything below is a consequence of those two sentences.

In Postgres the words are called lexemes, the document's bag of them is a tsvector, and the index over them is a GIN index, which stands for generalised inverted index. Marlow's looks like this, with the counts the shop actually has:

crime    ->   114   2051   2052   8899  ...   (180,000 ids)
fiction  ->    97    114    288   2051  ...   (400,000 ids)
london   ->   114   2051   7310   9004  ...    (95,000 ids)
                |      |
                114 and 2051 are in all three lists

Now ask for books containing all three words. Put a finger at the start of each list and advance whichever finger points at the smallest number. When all three fingers agree, you have a hit. One pass, three fingers, and the work is the sum of the three list lengths rather than their product: 675,000 identifiers inspected, which at two bytes each is 1.35 megabytes of reading.

Sorted order is what buys that. Unsorted lists would force you to build a hash table out of the shortest one and probe it with the others, which costs memory proportional to that list and has to be finished before the first row comes back. Sorted order also buys the compression, because a list of ascending integers can be stored as the gaps between them, and the gaps are small. And it buys skipping: when one finger jumps from 114 to 90,000, the other lists can seek forward instead of walking.

A tokeniser is a deletion

Between the text and the index sits a pipeline that decides what the index can ever be asked. Postgres calls that pipeline a text search configuration, everyone else calls it an analyser, and it does three things worth your attention.

It splits the text into tokens, which is harder than it sounds the moment an ISBN, a hyphenated name or a French title turns up. It stems each token to a root, so running and runs both become run and a search for one finds the other. And it drops stop words, the words so common they cannot narrow anything. Postgres ships a list of them for English, a bit over a hundred words long, and it is on it.

Dropping them is not sentiment. If the were indexed it would have a posting list 1.2 million entries long, two and a half megabytes in one list, and it would never remove a single book from any result. The stop word list is the hundred longest posting lists in the index being deleted on purpose. That is a storage decision that turns out to be a correctness decision, which is the pattern here: every one of the three steps above is lossy, and you cannot query what you threw away.

Stemming has the same shape with a funnier edge. The English snowball stemmer takes both universal and universe to univers, so a customer searching for Universal Studios gets a book about the origins of the universe, and nothing is broken. The founder ran the count that evening and found 206 titles whose entire tokenised form is empty: It, Them, If, To Be or Not to Be, and two hundred others.

The fix is small, and no line of code changes. Add a second vector over the title alone, built with the simple configuration, which lower-cases its tokens and, with no stop word file behind it, throws nothing away, and index that too. Eight lexemes a title over 1.2 million titles is ten million postings, twenty or thirty megabytes depending on how well lists that short compress, which is the same order as the index lesson 010 called cheap. Then route an exact-title lookup at it. The megabytes are not the expensive part. The expensive part is that the search box now has two indexes behind it and somebody has to decide, per query, which one is being asked.

That decision lives in a product conversation rather than in Postgres.

The size of it

Marlow's search document is the title, the description and every review the book has. Take a 450 word average across the catalogue, which after stop words and stemming leaves roughly 200 distinct lexemes a document. That is the one number here no earlier lesson can check for me, and anybody with the database open can settle it in a minute: the index's own size divided by two bytes is the posting count, and that divided by 1.2 million is this figure.

Two hundred lexemes times 1.2 million documents is 240 million postings. Postgres stores a posting list as compressed gaps, which comes to about two bytes a posting on lists this dense, so 480 megabytes of posting data. The entry tree holding the distinct lexemes, maybe 400,000 of them once you count names, typos and ISBNs, adds about twelve megabytes. Call the whole thing five hundred megabytes, sixty thousand pages of lesson 043's eight kilobytes.

Set that against what the shop already has. Lesson 010's composite index is thirty five megabytes over a 240 megabyte table. The inverted index is fourteen times that index and twice the table it describes, and it is the smallest thing in today's budget.

Because the vectors themselves are the big one. Two hundred lexemes with their positions is about 2.4 kilobytes a row, three gigabytes across the catalogue, and a value that size is past the two kilobyte mark where Postgres stops storing a row as it found it. It compresses the vector first, and moves it out of line into the TOAST table lesson 043 named when compressing is not enough. Either way three or four of these rows is all that fits in a page, and reading one is a fetch the index did not do for you.

Lesson 005 and lesson 010 both recorded what search cost Marlow in memory: the working set went from 14 gigabytes to a bit over 40 when full text search arrived, on a machine then holding 32.

Half a gigabyte of that is the index.

The vectors and the raw text behind them account for five or six more, which leaves most of the jump unexplained. My guess is that 450 words is low, because a bestseller with four hundred reviews is a very long document, and the posting side of this sum is countable while the text side is a guess. The shape holds either way, and the shape is the lesson: the structure that answers the query is the cheapest thing in the budget, and the thing it has to touch to rank the answers is six times bigger.

Why the search takes sixty milliseconds

Lesson 010 measured Marlow's searches at about sixty milliseconds each, sixteen a second at the Christmas peak, 0.96 of the database's busy second. Lesson 011 moved them onto the read replica, where they still run. Nobody has ever said where the sixty milliseconds goes, and almost none of it goes where you would guess.

Walk the three word query again. Descending the entry tree for three lexemes is three or four page reads, resident. Merging 675,000 postings is 1.35 megabytes of memory traffic and a few million comparisons, so three to four milliseconds. If the three words were independent, the intersection of 95,000, 180,000 and 400,000 out of 1.2 million is about 4,700 books, and real words are correlated, so take that as a floor.

Then comes the part nobody draws. The index has told you which books match. It has not told you which ones to show first, and it cannot, because ranking needs to know how often each word appears in each document and the GIN index does not store that. So Postgres fetches the tsvector of every candidate and scores it. Resident, that is 4,700 vector fetches and 4,700 small scoring passes, call it ten milliseconds.

Cold, it is 4,700 random reads at lesson 002's hundred microseconds, and you are most of half a second in.

Positions are the other thing the index threw away. london <-> bridge, the phrase query, cannot be answered from posting lists at all, because they record which documents hold both words and not where in a document the words sit. Postgres does the AND and then opens the vector of every candidate to check, so a phrase query is an ordinary query plus a recheck of everything that query matched.

Which also means the cheap query is the long one.

A customer who types crime fiction london is asking for 4,700 documents to be scored. A customer who types london is asking for 95,000, because the whole posting list is now the candidate set, and scoring 95,000 vectors at two microseconds each is 190 milliseconds of work to return twenty rows. Every extra word narrows the candidate set and makes the search cheaper, which inverts the intuition everybody brings to a search box.

It is also why sixty milliseconds is a plausible average over a mix of one word and three word queries rather than a number any single query produces.

The LIMIT 20 does not save you either. To know which twenty are best you have to score all 95,000, so a search costs what matches and not what you show. Core Postgres has no way out of that. An extension called RUM puts enough in the index to answer ranked queries directly, and it buys that with a bigger index and a slower write, which is the section you are about to read.

This is also the mechanism behind a symptom the course has carried since its first lesson without ever explaining it. Lesson 005 gave the catalogue going slow on quiet afternoons as the justification for August's resize, and lesson 010 put it as going slow on a Tuesday with no traffic spike and no code change. That was these fetches falling out of memory: same query, same index, same plan, paying a hundred microseconds a candidate instead of a tenth of one. Lesson 001 called it the working set outgrowing RAM. This is the shape it had.

The write path, which is the bill lesson 043 refused to write

Lesson 043 established the rule that makes an inverted index expensive, and it did not spell out the consequence. An index entry points at a row's location, so an update that cannot be done in place has to rewrite that row's entry in every index on the table, whether or not the indexed column changed.

For a B-tree, one row means one entry. Here, one row means one entry per distinct lexeme. Two hundred of them.

So a customer posting a review on Tuesday evening, adding eleven words to a document that already had four hundred and fifty, moves two hundred postings. Not two. The two hundred have nothing to do with each other, they live in two hundred different places in the index, and which places they are was decided by a publisher's copywriter.

That is the worst case for lesson 043's clustering argument, by construction rather than by accident. In lesson 043's terms, keeping the pages resident saves you the page read, and only keeping your insertions clustered makes the write itself cheap. An inverted index has no clustering available to it at all: its key order is the alphabet, and a document's words are scattered through the alphabet on purpose, because that scatter is the thing that makes a lookup fast.

An inverted index is an index whose key order is designed to spread your writes as widely as it can.

Price Marlow's day. The distributor feed brings about 250 new titles, and with them whatever the publishers revised overnight: a blurb, a subtitle, a series name, a corrected author. Over a catalogue of 1.2 million, each title touched about once a year, that is three thousand documents a day on its own. The reviews customers leave are rounding error beside it, which is the opposite of what everybody assumes: lesson 027 put the shop at one order every fifty seconds, and only a fraction of those buyers come back to write anything. Three thousand changed documents times two hundred lexemes is 600,000 postings landing in an index of sixty thousand pages. Lesson 010's dart model, which lesson 043 wrote out in letters as P times one minus e to the minus M over P, returns all of P once M is ten times P. Every page in the index, dirtied. Four hundred and eighty megabytes of writes and a comparable amount of write ahead log, for three thousand rows.

Put the same three thousand rows through an ordinary B-tree on one column, the way lesson 043 did, and you dirty about two thousand two hundred of its four and a half thousand leaves. Twenty seven times the pages for the same three thousand rows, and the ratio is the whole argument.

The dart model assumes the entries land uniformly, which is not quite true here. Short posting lists share pages, which helps; the lists you are writing into are the common words with the long lists, which does not. Take sixty thousand as the right order of magnitude and not the third digit.

Now the result worth keeping, and it is the one place this course's advice reverses. Thirty thousand changed documents would also touch sixty thousand pages, and cutting the day's churn by a factor of ten, down to three hundred documents, still leaves you dirtying thirty eight thousand of them. The index charges by its own size long before it charges by your change count, so lesson 043's closing advice, do not write what did not change, which cut Marlow's heap and B-tree cost by nearly four fifths, would buy almost nothing here. The only lever that works on an inverted index is doing the writes together, in key order.

Both of the real systems in this area are built around that one idea.

A pending list. Postgres GIN keeps a small unsorted area inside the index and appends new entries to it, in arrival order, with no attempt to put them where they belong. fastupdate has been on by default for years and gin_pending_list_limit defaults to four megabytes. When the list crosses the limit, the entries are sorted and merged into the index proper in bulk, by whichever unlucky transaction tripped the limit, or by autovacuum, or by gin_clean_pending_list() if you ask. Lesson 043 called this a memtable bolted onto a B-tree, and it is.

What that buys is the seeks. Sixty thousand pages visited in key order cost lesson 010's four microseconds a sequential page instead of a hundred for a random one, twenty five to one, which is the difference between a quarter of a second and six. What it does not buy is the bytes: those pages are still dirtied and still logged in full on the first touch after a checkpoint. Four merges a day log each page four times; scattered writes all day log it rather more.

Batching buys the seek and only some of the bytes.

It also moves the cost somewhere nobody looks for it. A search has to scan the pending list, every time, because the answers in there are real answers that have not been filed yet. Four megabytes is around 150,000 entries, a millisecond or two on top of sixty. Raise the knob to sixty four megabytes, which is standard advice in old blog posts for making GIN inserts faster, and that scan is sixteen times longer, twenty to thirty milliseconds added to the shop's most expensive query to speed up a nightly job.

Marlow would feel that on the replica, where the searches live, where the pending list arrives as replayed pages, and where gin_clean_pending_list() cannot be run at all because it is a write.

Segments. Lucene, and therefore Elasticsearch and OpenSearch, refuses the problem instead. A flush writes a brand new small index, called a segment, and never touches it again. A search queries every segment and merges the results. A delete is a bit flipped in a side file, and an update is a delete plus a complete reindex of the whole document, because a posting list inside a sealed segment cannot be edited. That is lesson 044's no partial write wearing different clothes.

Background merges then combine small segments into large ones, which is lesson 043's LSM tree in a different vocabulary and with the same bet: cheap sequential writes now, read amplification across the levels forever, compaction debt that comes due in the hour that created it. Elasticsearch's refresh_interval, one second by default, decides when a write becomes visible, and the same number decides how many segments a second you are handing the merger to clean up later.

Marlow does not need Lucene. What Marlow needs is to know why it got away with June, and the answer is a decision nobody wrote down. The vectors live in their own table, book_search, keyed by ISBN, because a year ago the founder did not want a two and a half kilobyte column sitting on the table every book page reads.

That is the only reason lesson 043's June arithmetic was honest. Put the vector on books instead and each of that morning's eight thousand stock updates moves two hundred postings rather than one entry in each of four B-trees, so the index pages dirtied go from ten thousand four hundred to about seventy thousand. Two minutes fifty one was the duration that made somebody look, and lesson 043 noted that the clock moves faster than the page count, so the counterfactual is north of a quarter of an hour. Worse, the fix 043 shipped would barely have touched it.

What the index cannot know

Ranking wants two numbers and Postgres keeps them in two places, neither of them handy. How often a term appears in a document is in the vector, which is why the scorer has to go and fetch it. How many documents contain the term at all, the document frequency, is simply the length of the posting list, so the index does know it, and the function that does the scoring never sees it.

The intuition is worth more than the formula. london appears in 95,000 of 1.2 million descriptions and fiction in 400,000, so a book matching london has been narrowed down four times harder than one matching fiction, and the match should be worth more. Inverse document frequency is the log of that ratio: about 2.5 for london against 1.1 for fiction. A rare word is worth more because it told you more.

Lucene's default scoring since version 6 is BM25, which adds the thing raw term frequency gets wrong: saturation. The second occurrence of london in a description is good evidence, the twentieth is not twenty times better, and BM25 flattens out while a linear count does not.

Postgres ts_rank has no document frequency term in it, at all, because it is handed one vector at a time and a vector does not know what the rest of the corpus looks like. That is structural rather than a tuning gap, and it is the honest reason Postgres full text search ranks worse than a search engine while retrieving just as correctly.

For a bookshop it may not matter, and I would not fix it with an index. A shop should mostly rank by what sells, with relevance as a filter, because the customer who typed two words is not asking which description is most textually similar to theirs.

When not to build one

Stagefront is a ticketing service invented for this course, and it has about four thousand event titles. Four thousand rows of sixty bytes is 240 kilobytes, which at lesson 002's two gigabytes a second is a sequential scan taking rather less than a millisecond.

ILIKE '%hamlet%' is the correct answer here, and buying a search cluster is the mistake.

The crossover is worth carrying: fifty milliseconds of scan budget at that rate buys a hundred megabytes, which is over a million rows of that size, so Stagefront has a factor of four hundred in hand and "just scan it" stays right for far longer than people assume. What takes the scan away is not the row count. It is the day Stagefront wants typo tolerance over three hundred thousand past events, because a sequential pass cannot do that at any size.

Galewatch, which collects a reading every two seconds from each of its wind turbines, has no text at all. Its queries are one turbine over one hour, which is a range over a sorted key, which is the B-tree lesson 043 spent a whole section on. The company should never acquire an inverted index. The only text it owns is in its logs, and searching those is a different problem with a different structure under it.

Recap

A term, a sorted list of document ids, and that is the whole idea. Sorted order turns an AND into one merge costing the sum of the posting lists rather than their product, and it is also what makes the lists compressible and skippable.

A tokeniser is a deletion. Stop words, stemming and whatever the splitter does to a hyphen all remove information before the index exists, and you cannot query what you threw away. Marlow has 206 titles it cannot find by name, and the cure is a second index over raw titles rather than a change to any line of code.

The index is the small part. Five hundred megabytes of index over 1.2 million documents, against three gigabytes of vectors sitting behind them, and it is the vectors a ranked query has to read. Lesson 005's working set went from fourteen gigabytes to past forty when search arrived, and the index is barely a fiftieth of that difference.

A search costs what matches, not what you show. Ranking has to score every candidate before it can pick twenty, so a one word query is the expensive one and every word the customer adds makes their search cheaper. The sixty milliseconds lesson 010 measured is an average over that spread and not a property of any query.

One word changes and two hundred entries move. An index entry points at a location, and a document's lexemes are scattered across the key space on purpose, so an inverted index is the structure that spreads your writes as widely as it possibly can. It charges by its own size before it charges by your change count, which is why lesson 043's best advice does almost nothing here.

Batching buys the seek and only some of the bytes. GIN's pending list and Lucene's segments are the same move at different scales, and both of them pay for the write path out of the read path: a search has to look in the buffer, and on a replica you cannot even clean it.

And the one to carry out of today, which has nothing to do with scale. The index knows every word in 1.2 million descriptions and it does not know the title of the book in the hook, because somebody put it on a stop word list long before this shop existed and nobody at Marlow has ever opened that file. A surprising number of search bugs are that shape: not a failure of the structure, but a decision taken for you, upstream, by a default.

Check your understanding

1. A colleague wants product search ordered by relevance with an infinite scroll, twenty results a page, over eight million documents. Say which part of that request is the expensive one, what you would measure before agreeing, and what you would offer instead if the measurement comes back badly.

2. Your team's search index takes 300 milliseconds a query at the ninety fifth percentile and the index is 2 gigabytes on a machine with 64. A colleague proposes more memory. Say what you would check first, and give the two different causes that would each produce that latency with the whole index resident.

3. A nightly job reindexes every document whose updated_at moved, about 0.2 percent of a 50 million document corpus. The job takes four hours and the search latency doubles while it runs. Say what you expect the cause to be in each of the two structures this lesson described, and which single number you would ask for first.

4. Somebody proposes a full text index so Galewatch's engineers can search their fault messages, and today's lesson says the company has no text. Say where text does accumulate in a system shaped like that, what you would build for it, and why none of it belongs in an index over the readings.

5. A product manager asks why searching for the exact name of a product returns three other products above it. Explain what is happening in terms of document frequency and term frequency, and say which of the two fixes available to you is a product decision rather than an engineering one.

6. You inherit a service where gin_pending_list_limit has been raised to 128 megabytes and the insert path is fast. Say what you expect to find in the read path's percentiles, what you would do before changing the setting back, and what breaks if you simply turn fastupdate off.

Next lesson

046 Caching Patterns: Cache-Aside, Write-Through, Write-Behind. Today's pending list is a write-behind buffer hiding inside an index, with the classic write-behind bargain already visible: the writer gets its latency back and somebody else pays, in a place that does not appear in the writer's own graphs.