Navicat Blog

Introduction to Inverse Indexes Jun 25, 2021 by Robert Gravelle

Like most database developers, you've probably written your fair share of queries that search for that proverbial needle in a haystack of text or binary data. I know I have! Perhaps even more important than the SELECT statements that you write against the database are the indexes that it contains. To that end, an inverted index can go a long way towards making mounds of data accessible in an expeditious manner. In today's blog, we'll learn what inverted indexes are, and how to use them in your databases, using MySQL as an example.

Forward Index versus Inverted Index

Inverted indexes were actually invented decades ago, around the same time that much of the first AI and machine learning algorithms were born. However, it wasn't until recent increases in computing power that it became possible to make use of inverted indexes in traditional relational databases. Inverted indexes allows information in relational databases to be found much faster as well as allow queries to be far more complex and specific.

Unlike a regular (forward) index, that maps table rows to a list of keywords, an inverted index maps the keywords to their respective rows. Here's a side-by-side comparison:

Forward IndexInverted Index
RowKeywordsWordRows
row1
row2
row3
hello, sky, morning
tea, coffee, hi
greetings, sky
hello
sky
coffee
hi
greetings
row1
row1, row3
row2
row2
row3

Searching using a forward index is a slower process because the database engine has to look at the entire contents of the index to retrieve all pages related to a word. Meanwhile, searching via an Inverted Index is very fast because there are no duplicate keywords in the index and each word points directly to the relevant row(s).

Inverted Indexes in MySQL

MySQL's InnoDB engine implements Full-text indexes on text-based columns (CHAR, VARCHAR, or TEXT columns) to speed up queries and DML operations on data contained within those columns. Full-text indexes employ an inverted index design so that each keyword in the index points to a list of documents that the word appears in. It also supports proximity searches, whereby two or more words that occur within a certain number of words from each other may also be located, by storing position information for each word.

In Navicat database administration development tools, such as Navicat for MySQL and Navicat Premium, you can view a table's engine in the General Information panel:

table_properties (11K)

Assuming that your table uses the InnoDB engine, you can assign a FULLTEXT index via the Index Type drop-down on the Indexes tab of the Table Designer. Here's an example of the perfect column on which to add a FULLTEXT index - the Description column on the Sakila Sample Database's Film table:

index_type (43K)

Text fields such as this are good candidates for an Inverted Index because there are so many words and phrases to search on:

film_description_column (118K)

Conclusion

Inverted indexes are a great way to speed up your queries while allowing them to be far more complex and specific. Just be aware that the indexing process takes longer than it does for forward indexes.

Interested in Navicat for MySQL or Navicat Premium? You can try both for 14 days completely free of charge for evaluation purposes!



Rob Gravelle resides in Ottawa, Canada, and has been an IT Guru for over 20 years. In that time, Rob has built systems for intelligence-related organizations such as Canada Border Services and various commercial businesses. In his spare time, Rob has become an accomplished music artist with several CDs and digital releases to his credit.

Navicat Blogs
Feed Entries
Blog Archives
Share