Boolean search explained

My mother is taking some online course in order to be a librarian of sorts, in this course they cover boolean searches, so they can search databases efficiently, however, she got a question sounding something like this:

The search "x OR y" will result in 105 000 hits, while a search for only x will result in 80 000 hits, and a search for only y will get 35 000 hits. Why does the search "x OR y" give 105 000 hits, when the combined individual searches gives 115 000 hits?

For me this sounded strange, so I tested this myself, using the words bacon and sandwich.

• Only bacon yielded 179 000 000 results
• Only sandwich yielded 312 000 000 results
• bacon OR sandwich gave 491 000 000 results

But for me it adds up: 179 000 000 (bacon) + 312 000 000 (sandwich) = 491 000 000 (bacon OR sandwich)

Why could an OR query result in fewer hits than both individual queries combined?

• You have a blue dog, blue cat, and red cat. NUMBER OF (BLUE) = 2, NUMBER OF (CAT) = 2, but NUMBER OF (BLUE or CAT) = 3, not 4. – BlueRaja - Danny Pflughoeft May 3 '16 at 22:51
• I tried this, got 184 million results for bacon. Never made it to searching for sandwiches, as I immediately left to fry myself some bacon. – corsiKa May 4 '16 at 0:57
• I think the real problem here is that your database has no bacon sandwiches in it. – MooseBoys May 4 '16 at 6:41
• @MooseBoys yeah, this must be why my numbers add up, since they should not, right? – sch May 4 '16 at 7:27
• @klskl: If you're getting those numbers from google, keep in mind those numbers are very very rough estimates. It could very well be the case that, to get the estimate for "bacon OR sandwich", they just sum the numbers. That only works because the estimate is not required to have any sort of accuracy whatsoever. – BlueRaja - Danny Pflughoeft May 5 '16 at 15:05

Hint: The search x AND y will result in 10 000 hits.

• yes, but that's beside the point, the teachers claim their x OR y search gives fewer hits than combining the hits of individually searching x then y – sch May 3 '16 at 15:31
• No, that's not beside the point. On the contrary, it's the point itself. – Yuval Filmus May 3 '16 at 15:32
• I'm new to this, care to elaborate? From what I understand AND will give results with both words in them, hence fewer results than each individually, but what has that to do with OR? – sch May 3 '16 at 15:36
• When AND is empty OR works like ADD, otherwise it doesn't. @klskl the information of x AND y is crucial. – Evil May 3 '16 at 15:57
• @YuvalFilmus I see now, it is the point! (I was like, hamburger AND sandwich doesn't give 10 000 hits...) thank you – sch May 3 '16 at 16:05

The counting principle that applies here is inclusion-exclusion.

$$\left|X \cup Y\right| = \left|X\right| + \left|Y\right| - \left|X \cap Y \right|$$

To make the numbers work out, $\left|X \cap Y \right|$ must be 10000.

A Venn diagram may be more convincing to someone who may be intimidated by the notation.

• This is really good, will use this to explain to my mother, really clean, thanks! – sch May 4 '16 at 4:51
• I'll expand on your diagram a little and point out that the reason $|X \cup Y| = |X| + |Y| - |X \cap Y|$ is because $|X \cap Y|$ is a part of both $|X|$ and $|Y|$ already, so when you add $|X| + |Y|$, you've counted it twice. You then subtract it out so that it's only counted once. – Devsman May 4 '16 at 20:23
• The math works out, and it makes sense, but it doesn't match the set algebra right above it. – Kevin Brown May 4 '16 at 21:59
• I remember doing Venn Diagrams when I was 4-5. They're really underrated. Thank you John Venn. – Pharap May 5 '16 at 14:29
• @Pharap Indeed, such diagrams deserve our Venn-eration. – Mason Wheeler May 6 '16 at 20:19

Document 1: The cat is on the table
Document 2: My cat is black
Document 3: The dog is under the table
Document 4: What's the name of your cat?
Document 5: This is a black and white photo

Search for cat: returned documents are 1,2,4 (3 documents returned)
Search for black: returned documents are ...
Search for cat OR black: returned documents are ...

:-D :-D

In simple words:

Search for X gives you n answers.
Search for Y gives you m answers.
Search for X AND Y gives you p answers.

In searching for X OR Y, the search breaks off as soon as it finds either X or Y. So if there's an X before a Y, that Y will not be counted in searching for X OR Y. Therefore your search for X OR Y will give you n + m - p answers.

It's important to note that the results will be the same, whether you do 2 searches, or just one. It's just that in summing the two searches, some documents are counted twice.

• "the search breaks off as soon as it finds either X or Y." Doesn't this depend on implementation? An implementation could obtain all results for X, obtain all results for Y, and then combine the results in a way that eliminates duplicates. – jpmc26 May 5 '16 at 0:32
• @ArnabDatta What I described is most definitely not an XOR. "Eliminating duplicates" means eliminating the second copy, not all instances of that element. – jpmc26 May 6 '16 at 8:47
• True. I misunderstood. Removed my comment. – Arnab Datta May 6 '16 at 9:22

Imagine you have only one document. This is Document#1 with this:

X Y


Now imagine you have a search function that can give you all the documents based on one keyword:

search("X") => 1
search("Y") => 1


Notice that the number of documents in both cases is 1. Now if you have a search function that gives you the number of documents that matched one or more of the keywords supplied:

search("X", "Y") => 1


When you add the number of documents containing X to the number of documents containing Y, this causes you to count the same document twice. In your case, this happened 10000 times as pointed out above :)