recallA retrieval
field guide

Boolean Search and Inverted Indexes

Build this skill

Build an inverted index from analysed text and evaluate Boolean queries as operations on postings lists.

Using the index at the back of a book

Suppose your operating systems textbook has 900 pages and you need every page that mentions "deadlock". You would not read all 900 pages. You would turn to the index at the back, find "deadlock: 212, 215, 340", and go straight to those pages. Someone did the slow work once, so that every reader after them can skip it.

Search engines use exactly the same trick. Reading every document for every search is too slow once a collection grows: an email archive with ten million messages holds gigabytes of text, and scanning all of it for each query would take far too long. Instead, the engine builds an index ahead of time that records, for every word, which documents contain it. A search then only needs to look up its own words.

Building this index has two parts. First, the engine has to decide what counts as a "word" for searching. Second, it stores the words in a structure that answers "which documents contain this word?" instantly. Once that exists, you can combine words with AND, OR and NOT.

Deciding what counts as a word

To a computer, text is just a long string of characters. Before it can index anything, it has to cut that string into pieces and decide which pieces should count as the same. This is called text analysis, and the pieces that end up in the index are called terms.

Here is what happens to one sentence from the hostel handbook, step by step.

Step What it does Result
Split into words (tokenization) Breaks the text at spaces and punctuation Hostel · gates · close · at · 10 · PM · for · first · year · students
Lowercase Makes "Hostel" and "hostel" the same hostel · gates · close · at · 10 · pm · for · first · year · students
Remove stop words Drops very common words such as "at" and "for" hostel · gates · close · 10 · pm · first · year · students
Stem Cuts words down to a shared root hostel · gate · close · 10 · pm · first · year · student

Each step helps the search find more matches. Lowercasing lets a search for "hostel" find "Hostel". Removing stop words shrinks the index a lot, because words like "the" appear in almost every document and tell you nothing about it. Stemming lets "students" match "student" and "fees" match "fee".

Each step can also go wrong. Lowercasing makes "US" (the country) the same as "us". Removing stop words makes the phrase "to be or not to be" impossible to search. Stemmers follow simple rules, so they sometimes merge words that mean different things: a popular stemmer called the Porter stemmer turns both "university" and "universe" into the same stem. There is always a trade-off between finding more pages and finding the wrong ones.

Raw textHostel gatesclose…Splitinto wordsLowercaseHostel → hostelStop wordsdrop at, forStemgates → gate

Documents and queries must go through exactly the same steps, or they will not match.

One rule matters more than any single step: the query must be analysed in exactly the same way as the documents. If the documents are stemmed but the query is not, a search for "students" looks for "students" in an index that only contains "student", and finds nothing.

Decide for yourself where these merges help and where they hurt.

The inverted index

A normal document is a list of words. An inverted index flips this around: for every term, it keeps a list of the documents that contain it. That list is called a postings list. The number of documents in a term's list is its document frequency, often written df.

TermhostelfeemedicalstudentclosePostings list (pages that contain it)D3 · D4 · D5D4D1D1 · D3 · D6D3 · D5

Each term points to the pages that contain it. Looking up a word now means reading one short list, not every page.

Postings lists are kept in sorted order, which makes them quick to combine. Real indexes often store a little more in each entry, such as how many times the word appears on the page (useful for ranking) and where it appears (useful for exact phrases like "medical certificate").

The document frequency is worth noticing. A word like "warden" appears on very few pages, so a page containing it tells you a lot. A word like "student" appears almost everywhere and tells you little. This idea becomes important when results need to be ranked.

The short program below builds an inverted index for five campus pages using a Python dictionary of sets. Run it and read the lists it prints.

python · runs in your browser

Expected output:

text
hostel -> ['D3', 'D4', 'D5']
student -> ['D1', 'D3', 'D6']
close -> ['D3', 'D5']
fee -> ['D4']
Line What it does
re.findall(r"\w+", text.lower()) Lowercases the text and pulls out the words, leaving punctuation behind.
if w not in STOP Drops the stop words.
w[:-1] if w.endswith("s") ... A crude stemmer: it removes a final "s" from longer words.
index.setdefault(term, set()).add(doc_id) Creates the word's list the first time the word is seen, then adds the page to it.

"Hostels" in D5 became "hostel", and "Students" became "student", so each word gathers all of its pages into one list. Large search engines, such as those built on the Lucene library (used by Elasticsearch and OpenSearch), store the same structure in compressed files on disk rather than in memory.

Combining words with AND, OR and NOT

Once every term has a list of pages, answering a query is just combining lists. This is called Boolean retrieval, after the mathematician George Boole, and it uses three operators.

Operator Meaning Example Result
AND Pages that have both words hostel AND fee D4
OR Pages that have either word medical OR fee D1, D4
NOT Leave out pages with this word hostel AND NOT fee D3, D5

AND keeps only the pages that appear in both lists, OR merges the two lists, and NOT removes pages. Because each list is sorted, a computer can combine two lists in one pass, walking down both at the same time like two people comparing sorted attendance registers. A good engine also starts with the rarest word: its short list cuts down the work for everything after it.

Try it below. Pick two words and an operator, then watch which pages light up.

Where Boolean search works well, and where it does not

Boolean search is exact and predictable. Lawyers, patent examiners and librarians still use it because they need to know that every document matching a condition was checked, and they want to explain exactly why a document was included. Email filters work the same way: "from the registrar AND NOT newsletter" is a rule.

For everyday searching, though, it has two big problems. First, it is all or nothing. A page either matches or it does not, so the results come back in no particular order. Too many ANDs return nothing at all, and too many ORs return hundreds of pages that all look equally good. Second, people do not think in AND and OR. A student types "hostel fee late payment", not "hostel AND fee AND (late OR overdue)". What people want is a list with the most useful page at the top, which means giving each page a score.

Follow your curiosity.

↑ ↓ to explore · Enter to open · Escape to close