Database Indexing Isn't Magic. Understand It from Scratch

In my previous post I discussed How databases actually store data on disk. That article was more about data storage, and we talked about some of the fundamental techniques databases use to store data. In this article we are going to focus on “Indexing,” and I’ll try to make it as practical as I can.

I’ll start with an old example. If you had to find a particular topic in a book, what would your searching approach be? Will you search each page one by one? Obviously not; it will take a lot of time. So you will use the “Table Of Contents” available in all books. That “Table Of Contents” keeps a record of which chapter is on which page. You will then figure out the chapter in which that topic might be available and narrow your search to that chapter only.

Now replace this book with a database table that has millions of records. You have to find a particular record from it. Again, you have 2 options: either read each record one by one or use the index. Database indexes work the same as the “Table of Contents” of a book, although they are more complex than simple chapter-to-page mapping.

I’ll be using PostgreSQL for this demonstration. Let’s first start by preparing a database that has a huge number of rows on which we can experiment. I’ll be using the “Postgres Air” dataset for this example. This dataset contains information about airports, bookings, passengers, and more.

1CREATE DATABASE postgres_air;

Once your new database “postgres_air” is created run following command outside psql terminal. Replace username, password and hostname with your credentials.

1pg_restore -d postgresql://<USERNAME>:<PASSWORD>@<HOST>/postgres_air -Fc postgres_air_2023.backup -c -v --no-owner --no-privileges

This command will start inserting data from “postgres_air.backup” file into our database. If you see any error just ignore them and give this process some time to complete.

Once completed you will see following tables. Table named passenger contains 16 million records. We will start exploring it.

Querying Without Index

We will first check if there is any index already implemented on “passengers” tables. Simply use your Postgres GUI client to check this table structure. I’m using Postico2, and here is the output.

This screenshot says that there is a primary key index on this table. Don’t worry about it; we will discuss this later. Expect a primary key index on the column “passenger_id”; there is no other index in this table.

Try to run the following query. We are simply trying to fetch rows with first_name as “JASON” and account_id = 101701.

1SELECT * FROM postgres_air.passenger WHERE first_name = 'JASON' AND account_id = 101701;

Here is the output. Focus on how much time it took to execute this query. It took 5 seconds to return the result on my MacBook Air M1.

Now let’s try to create an index on this table and try to rerun the query. Hence, we are querying for “first_name” and “account_id,” so we will create an index on the “first_name” + “account_id” column using the following command.

1CREATE INDEX "passenger_name_account_id" ON "postgres_air"."passenger"("first_name","account_id");

Let’s rerun this query and see what happens.

This time we got our result in 1 millisecond. Although it will take anywhere from 1 to 10 milliseconds when you run this query for the first time. On my machine it took 6ms to run. But I ran it multiple times, and due to the operating system cache, it is resulting in a 1 ms response time.

Well, this is a huge improvement. A query that was taking 4 seconds to run is now taking less than 10 milliseconds. But why? Because we added an index. Let’s confirm that our boosted speed is because we added an index.

Delete the index and run following query:

1EXPLAIN SELECT * FROM postgres_air.passenger WHERE first_name = 'JASON' AND account_id = 101701;

This query will show us the execution plan for the query. The execution plan contains steps that our database will follow to get the data requested in the query.

1Gather (cost=1000.00..274633.68 rows=1 width=47) 2 Workers Planned: 2 3 -> Parallel Seq Scan on passenger (cost=0.00..273633.58 rows=1 width=47) 4 Filter: ((first_name = 'JASON'::text) AND (account_id = 101701))

Here we can see that Postgres is going to sequentially scan each row in the table and apply the filter to find matching first_name and account_id in each row. It is important to note that in a sequential scan, each row will be traversed and filtered.

1CREATE INDEX "passenger_name_account_id" ON "postgres_air"."passenger"("first_name","account_id");

and rerun the explain query.

1EXPLAIN SELECT * FROM postgres_air.passenger WHERE first_name = 'JASON' AND account_id = 101701;

The explanation query will result in the following output. We can see that after creating the index, our database is not scanning every row sequentially; instead, it is using the index.

1Index Scan using passenger_name_account_id on passenger (cost=0.43..8.46 rows=1 width=47) 2 Index Cond: ((first_name = 'JASON'::text) AND (account_id = 101701))

Cost Difference After Adding Index

The cost of the query determines how much effort the database will need to make to return the result of the query. Without index, our total cost is 274633.68, and with index, the total cost is 8.46, which is 32,462× less than the original cost. So after adding the index, our database needs to make fewer efforts to get results.

But the question is still there: “How does an index lead to faster results?” It’s finally the time to answer this question.

A database index is a separate data structure that is mostly built using a B-tree over tables and columns to speed up the data retrieval process. Your database store data in rows and columns. These rows and columns are essentially represented in the heap memory of the computer. But searching in this heap memory is very inefficent because you don’t know where the data you requested is stored. So an index maintains pointers to the data location so that your database can directly go to requested data via pointers.

Let’s visualize what a B-tree-based index would look like. Check the data of the table “aircraft,” and you will find the following rows and columns.

If you look at this index diagram closely, you will notice that this is a kind of binary tree structure where rows have a code column less than the root are on the left, and rows having a code column greater are on the right side.

Although this is not actually a B-tree. Instead, it is a B+ tree. The main difference between both of them is that a B-tree stores keys and pointers to data in all its nodes, including root, internal, and leaf nodes. While the B+ tree stores pointer data only in leaf nodes, the root and internal nodes act as a routing path. So when you have an index database, you can directly traverse this tree and go to requested data quickly instead of sequentially scanning every row.

This is an index that actually reorders the physical storage location of data so that related data is stored together. Every table can have only 1 clustered index. In our example, the clustered index is on the code column, so physical data storage will be according to it.

A clustered index makes range queries and sorting faster. For example, queries like WHERE age BETWEEN 20 AND 30 or ORDER BY code would result in faster execution.

This type of index does not change the actual physical storage location of data. Instead it create a seperate structure that contain the indexed values and pointer to the location of data. For example in our aircraft table you can create another index on velocity column and queries realted to this column will spead up. Because now your database does not need to go scan full table or use inefficient code column index instead it can use velocity index directly.

These indexes are used to make sure that no two rows in a table have the same value in the same column.

Now you might be thinking that if indexes can improve query execution speed, why not index every column and combination of every column? This is completely wrong. Till now you have understood half of the story, the read queries. Let’s understand the whole story, the write queries.

Currently in our aircraft table we have only 1 index in the code column. Every time a new row is added or updated in the table index, reordering takes place. Index reordering is the process of adjusting your index structure (B+ Tree) according to newly written data (rows). As of now for a write command, your database needs to do 2 things:

But if I create 2-3 more indexes on this table than for every write query, my database needs to write data on disk as well as reorder all 3 indexes. Indexing will surely make your read queries faster but at the cost of slower write queries. So you will need to find a right balance between read and write performance to use indexes efficiently. You can’t just blindly create an index on everything.

Now let’s discuss a very interesting scenario. Let’s say you want to find all the users whose first_name is “JASON,” so you will run the following query:

1SELECT * FROM postgres_air.passenger WHERE first_name = 'JASON';

This query is taking around 3 to 4 seconds to execute, and it returns 115895 rows. Your first approach to optimize this will be adding an index on the first_name column.

Let’s add an index to it.

1CREATE INDEX "passenger_name" ON "postgres_air"."passenger"("first_name");

After adding the index, this query is still taking the same amount of time. You were expecting it to respond fast, but it took the same time as an unindexed query. The only difference is that the unindexed query was taking 3.5 seconds and the indexed query is taking 3.2 seconds. Let’s see why there are no performance improvements.

On the unindexed table, we will use EXPLAIN on this query to understand what the database is doing.

1EXPLAIN SELECT * FROM postgres_air.passenger WHERE first_name = 'JASON';

1Gather (cost=1000.00..268842.25 rows=112021 width=47) 2 Workers Planned: 2 3 -> Parallel Seq Scan on passenger (cost=0.00..256640.15 rows=46675 width=47) 4 Filter: (first_name = 'JASON'::text)

On the unindexed table, our database explain commands tell us that the total cost for this query is 268842.25, and you will get approximately 112021 in response. Postgres has planned 2 workers, which means that 2 threads will parallelly process this query and separate work between themselves.

Now let’s try to do EXPLAIN on the indexed table.

1EXPLAIN SELECT * FROM postgres_air.passenger WHERE first_name = 'JASON';

1Gather (cost=2252.60..225803.91 rows=112021 width=47) 2 Workers Planned: 2 3 -> Parallel Bitmap Heap Scan on passenger (cost=1252.60..213601.81 rows=46675 width=47) 4 Recheck Cond: (first_name = 'JASON'::text) 5 -> Bitmap Index Scan on passenger_name (cost=0.00..1224.59 rows=112021 width=0) 6 Index Cond: (first_name = 'JASON'::text)

In this we can see that Postgres will again spin up 2 workers, and the total cost for this query is 225803.91. This cost is around 16% less than the cost of an unindexed query, which justifies why the indexed query took 3.2 seconds and the unindexed query took 3.5 seconds to execute.

But why didn’t this speed improve after indexing?

The problem here is the number of rows. Although the index told our database that here are the rows you requested, our database still needs to go to each memory location of each row and fetch actual data. As a result, we have 115895 rows. These rows must be scattered across a large portion of the table (because physical order is only determined by a single clustered index), and the database needs to go to each location to get