Indexes in SQL

Introduction

Indexes in databases are used to enhance query performance and speed up data access. They play a crucial role in optimizing query execution and allow for more efficient data retrieval from large datasets.

If you compare a database to a book, indexes are like the table of contents or an index. You could read the entire book to find the information you need, but it's much more convenient to go directly to the desired page.

Application Area

Indexes, like any other tools, should be used wisely. There's no point in placing indexes on fields that won't be searched. However, there are fields and tables where indexes must be set.

For example, we have two tables: Blog and Tag. These tables have a "many-to-many" relationship (ManyToMany), as one blog entry can have different tags, and each tag can belong to multiple entries. Thus, we have a third table, let's call it BlogTag, which has only two columns: blog_id and tag_id referencing entries in the respective tables. In this linking table, both columns should not only be indexed but also have foreign keys referencing entries in the respective tables.

As real practice has shown, even in small tables with about 100,000 records, using several join operations (JOIN), the speed of data selection can increase significantly. In my experience, I achieved a speed increase in processing complex queries almost tenfold, from ~2.7 to ~0.4 seconds, simply by setting the necessary indexes and defining foreign keys.

Types of Indexes

B-tree

This is perhaps the most commonly used type of index, organized as a balanced tree of ordered keys.

Such an index can be used to search not only for exact values but also for relative ones (greater or less).

This type of index is suitable for queries of the following types:

WHERE age = num;
WHERE age > num;
WHERE age < num;
WHERE name LIKE 'John%';

At the same time, this index is not suitable for queries where the substitution of undefined values is at the beginning of the search string, for example:

WHERE name LIKE '%Doe';

Since the B-tree index traverses the tree, in this case, the starting entry point is undefined, and the index will not be considered. Instead, the database will scan the entire table for suitable values.

This limitation can be circumvented by adding a reverse index. In this case, the query will look different:

WHERE reverse(name) LIKE reverse('%Doe');

What can reverse be used for? For example, to search for email addresses of specific servers.

WHERE reverse(email) LIKE reverse('%@gmail.com');

HASH

This type of index involves storing not the values themselves but their hashes, which reduces the size and processing speed of indexes from large fields. Thus, in queries, the hashes of the fields will be compared. This type of index can be compared to selecting an array element by key.

WHERE name = 'John Doe';

Since hashes are compared, this index cannot be used to search for relative values (greater or less). Thus, in the following queries, the index will not be used:

WHERE name LIKE 'John%';
WHERE name LIKE '%Doe';
WHERE age > num;
WHERE age < num;
WHERE name IS NULL;

Moreover, due to the possibility of storing identical values in the database, collision resolution methods are applied for matching hashes.