1. Introduction

In this tutorial, we’ll study the lookup tables in databases.

Lookup tables are frequently used in computer vision and graphic programming where they save a lot of heavy computations.

2. Lookup Table

A lookup table or LUT maps keys to values. Keys are unique and no value appears more than once.

For example, a table connecting author names to their ids is a lookup table:

Rendered by QuickLaTeX.com

The data we save in a lookup table can be anything. For example, they can be categorical such as country names, currencies, colors, etc., or numerical.

More so, a lookup table can store one-dimensional and multidimensional keys. Most of the time, we use lookup keys in other tables. For instance, instead of saving the author’s name as a field in the table of articles published, we use the author’s id as the foreign key. This gives us more flexibility if we want to change an author’s name to a pseudonym at one point as we only need to change 1 row in the lookup table instead of many rows in the article table.

In most cases, we create a lookup table once. Thereafter, we do a large number of read operations on it. We can also insert new records and update the existing ones. However, we execute these two operations very infrequently as compared to the read operation.

3. Benefits of Lookup Table

The lookup table can replace complex runtime calculations with simple lookup operations.

For example, we can pre-calculate and store the output values of a complex math function in a lookup table, using the input arguments as keys. Then, we query the table instead of calculating values. Additionally, we can load the table or a part of it in memory at the time of initialization of our app. Thus, we get a good amount of savings in terms of processing time.

We use lookup tables to maintain data integrity in our application.

The lookup tables make our database design simple and scalable. We can store all static key-value pairs in a single lookup table for all modules of the application.  This saves space and promotes data integrity since all the modules of our application can use the same simple key to refer to a potentially more space-consuming value. For instance, all modules can refer to the user gender as user\_gender only and store the numerical id corresponding to the gender instead of repeating the gender string all the time.

Additionally, if we need to change the value of a key-value pair, we change only that particular row in the lookup table.

4. Lookup Table vs Hashing

A lookup table and a hash table are very similar data structures. Both store data as key-value pairs but aren’t the same.

4.1. Lookup Table Internals

Unless indexed, the lookup table does a read operation by looking into the entire table to select the relevant entry (or entries). There is no specific mathematical function that maps an input value to its corresponding output value. This is inefficient when the table becomes very large as the reading complexity is O(N).

4.2. Hash Table Internals

On the other hand, the hash table allows us to insert and retrieve a value in the amortized O(1) time. To achieve this, we use a hash function that transforms a key value to a specific index in the table. Then, we use that index to get our value.

The efficiency of a hash table depends upon the strength of the hash function to map input value to a unique index as well as its processing overhead. If the hash function maps two different keys to the same index, then we have a collision and need more work to get the value corresponding to the search key.

4.3. Differences

Let’s summarize two key differences between a lookup table and a hash table.

First, a hash table uses a mapping function called a hash function that is applied to each key to get a unique index value in the table. Lookup tables use no hash.

Second, a hash function can map multiple keys to the same index value. So, we need extra logic to resolve collisions. In contrast, a lookup table represents a one-to-one mapping, so nothing except the search key is needed to get the associated value.

5. Conclusion

In this article, we talked about lookup tables in databases.

Comments are open for 30 days after publishing a post. For any issues past this date, use the Contact form on the site.