Here’s a Google search for a famous phrase, to be or not to be; give it a try and see what happens. When you look at word frequencies, it appears that there are a few words that appear unreasonably often and carry unreasonably little information. They are called “stopwords,” and this (brief) eighth bead in the On Search necklace considers them.

What many search engines have done with stopwords is, well, nothing. That is to say, they don’t get indexed, and you can’t search for them. The theory is that they’re expensive to index because there are so many of them, and they carry little useful information.

The Numbers · Let’s start with some numbers. Just before I started writing this, a collection of ad-hoc Perl and sed and sort alleged that ongoing as of then contained 169,908 words of text, comprising 15,370 unique words. Here are the most common twenty-six in decreasing order of frequency. The column labels are a bit short to keep the table from spreading, so to amplify: “Count” means the number of times this word appears, “Running” means the total occurrence of this word and all those above it, and “%” is “Running” as a percentage of all 169,908 words in ongoing.

WordCountRunning%
the888688865.2
and5499143858.5
a45761896111.2
to44662342713.8
of44062783316.4
in28213065418.0
i25003315419.5
is24233557720.9
that23543793122.3
it19433987423.5
on15774145124.4
you15054295625.3
this14994445526.2
for14694592427.0
but11264705027.7
with11114816128.3
are10774923829.0
have9215015929.5
be9095106830.1
at8365190430.5
or8335273731.0
as7935353031.5
was7895431932.0
so7635508232.4
if6995578132.8
out6865646733.2
not6795714633.6

Why Stop? · The numbers tell the story. By leaving out the 26 most common words, we account for a third of all word occurrences. (If you haven’t read the write-up on how search indices work, you might want to take a side-trip there now.) Each word occurrence requires that you create, store, and search one posting. Most of the space-cost of search is in postings, and most of the compute time is reading and merging postings lists. Consider that occurrences of “the” comprise almost 5% of the total. If you’re running something like Google, with billions of documents and hundreds of billions of words, you’re looking at many billions of postings you can get rid of by discarding stopwords. Consider the task of doing a set intersection on the billions of matches to “to,” “be,” “or,” and so on. It’s no surprise, really, that you get that polite little note from Google about all of Hamlet’s words except “not” being too common to be useful.

Why Not Stop? · Of course, skipping the stopwords comes at a cost; for example, “to be or not to be.” Another amusing example is the well-known retail chain “The Limited,” which is going to be pretty hard to find in a database that doesn't index “the.”

And as we’ve come to expect from Google, they’re not stupid. They do in fact index the stopwords, and you can search for "to be or not to be" just fine. See the quotes around the string? This is a phrase search. I won’t go into the details, but the cost of combining huge lists of common-word postings is immensely cheaper for a phrase search than doing a simple AND or OR. You can find The Limited just fine, too.

In fact, by putting + characters in front of each of the words, you can make Google claim to do a search for each of the words separately, although when I do the arithmetic in my head, I find it hard to believe they’re actually processing that many billions of postings.

Interestingly, I note that in the first Google search in the article, to be or not to be with no quotes or pluses, the one word it’s willing to search on is “not,” the least common of the most common (in ongoing anyhow).

The bottom line: refusing, by default, to search for common words is good usability practice; when I search for “Lord of the Rings,” nobody misses the two words in the middle. But simply leaving words out of your index because they’re common is a bug, not a feature.


author · Dad · software · colophon · rights
picture of the day
July 11, 2003
· Technology (77 fragments)
· · Search (66 more)

By .

I am an employee
of Amazon.com, but
the opinions expressed here
are my own, and no other party
necessarily agrees with them.

A full disclosure of my
professional interests is
on the author page.