Redenormalisation: Building a search index, the other way
Why unobtanium doesn't go by the textbook when it comes to normalisation in the search index.
Table of Contents
What?
This post is about how the unobtanium search engine handles normalising words so you don't have to worry about weather a document contains the phrase "cat", "cats" or "cat's" (English is pretty tame here, other languages aren't) and simply can search for "cat" content and find all three using a keyword based search index.
This blogpost oversimplifies: Building a search index involves a lot of complexity, to outline this one concpet the rest of the index building is oversimplified here.
Turning documents into a search index
To start with, lets create a bad search index off of some example documents. Too keep it simple I'll spare you the complexity of actual content and reduce everything to a few keywords.
| Name | Keywords |
|---|---|
| A | "cat" "jumps" "silly" |
| B | "cats" "sleeping" "cute" |
| C | "dog" "jumps" "playing" |
| D | "cat" "jumping" "funny" |
In a very simple search index one maps the keywords to the documents:
| Keyword | Documents |
|---|---|
| "cat" | A, D |
| "cats" | B |
| "cute" | B |
| "dog" | C |
| "funny" | D |
| "jumps" | A, C |
| "jumping" | D |
| "playing" | C |
| "silly" | A |
| "sleeping" | B |
Now someone can search for "cat" and … only finds document A. That's not good, they're missing out on the cute cats in document B, and even worse, a search for "cute cat" where one would expect document B as the result would have returned nothing because "cat" is a different string of letters from "cats".
This is why the usual solution is to store normalised forms where "cats" becomes "cat" and "playing" becomes "play", etc. (also known as stemming).
The new index would look like this:
| Keyword | Documents |
|---|---|
| "cat" | A, B, D |
| "cute" | B |
| "dog" | C |
| "funny" | D |
| "jump" | A, C, D |
| "play" | C |
| "silly" | A |
| "sleep" | B |
Note that "cat" and "cats" have merged and all of the example queries from earlier now work.
Searching for "cute cats" requires normalising the search terms to "cute cat" yielding the expected result.
However, storing a normalised index breaks exact matching, as the index can no longer tell "cat" and "cats" apart. This would require a parallel index.
A redenormalising index
To not require two indices for supporting the search modes a redenormalising index works like the naive index, but also stores the normalisations.
The Index would look like the simple normalisation:
| Keyword | Documents |
|---|---|
| "cat" | A, D |
| "cats" | B |
| "cute" | B |
| "dog" | C |
| "funny" | D |
| "jumps" | A, C |
| "jumping" | D |
| "playing" | C |
| "silly" | A |
| "sleeping" | B |
And a separate table storing the normalisation looks like this:
| Keyword | Normalised | Language |
|---|---|---|
| "cats" | "cat" | en |
| "jumps" | "jump" | en |
| "jumping" | "jump" | en |
| "playing" | "play" | en |
| "sleeping" | "sleep" | en |
Exact matching works like before. A normalising query now works by normalising using the query by looking up the normalisations and then looking up the denormalisations and querying for all of them. That's where the name re-denormalisation comes from.
So the query "jumping cat" becomes "jumping|jump cat" after normalising and "jumping|jump|jumps cat|cats" after denormalising. This means that the query matches any document that contains one of "jumping", "jump", "jumps" and one of "cat" or "cats", matching documents A and D which are both about jumping cats.
Normalising across multiple languages
Normalisation isn't universal, what works for English doesn't work for other languages which would require a normalised index for each language.
Noticed how I quietly inserted a language column into the normalisation table? This one can be used to support multiple languages using the same index.
Playing with it
The redenormalisation is what powers the unobtanium search engine after version 3.0.0, you can access the token-playground under /token-playground on any unobtanium instance and see how the words you put in get normalised across different languages for the index behind the search engine.