Why Standard Indexes Fail: The Architecture of the Covering Index

In my last article, I broke down how and why to use indexes wisely for efficient lookups and data retrieval by identifying fields to index and which not to index. Can read that here.

But adding a standard index in some cases is half the battle.

Adding an index to a column creates a separate, organized B-Tree for that column. And at the bottom of the tree (leaf node) is the pointer. That pointer tells the database engine where the full row lives on the heap. The heap is the main table where the full rows live. It is unsorted, massive, and slow to search as it forces a full-table scan. Indexes help to make data retrieval faster.

Standard indexes make searching fast, but they introduce a hidden bottleneck. Let’s look at a real-world example to see how and when to use a Covering Index to fix it.

Spotify “Recently Played” Screen

The Problem: The “Recently Played” Feed

Think of any music streaming platform like Spotify or Apple Music. Every time you open the app, it instantly fetches your most recently played tracks, around 10 tracks initially.

The query looks like this:

SELECT track_id, played_at 
FROM listen_history 
WHERE user_id = '018dc336-1234...' 
ORDER BY played_at DESC 
LIMIT 10;

Method 1: No Index

Without an index, the query is forced to do a full-table scan. Let’s say Spotify has 100 million records on its listen_history table, which means for each query.

1. 100 million rows will be scanned just to isolate this single user’s history
2. Then it is sorted in memory.
3. And then the top 10 i s returned. At scale, this doesn’t just increase response times. This manual RAM sort will choke your disk I/O, exhaust your connection pool, and eventually bring down your application with 500 server errors.

Execution Time roughly 217ms with no index as a result of the Parallel Sequential Scan with 1,000,000 rows scanned. (Nano Banana for sharpening text in the terminal)

Method 2: Using Standard Index

CREATE INDEX idx_user_history ON listen_history (user_id);

SELECT track_id, played_at 
FROM listen_history 
WHERE user_id = '018dc336-1234...' 
ORDER BY played_at DESC 
LIMIT 10;

Here, an index is added on user_id, and the database engine creates a new B-Tree for this column. So let's say a user has played 5000 different tracks after signing up. No need for a 100 million row scan. It takes O(log n) time to traverse through the B-Tree to get the records and their pointers (where n is the number of tracks played by the user).

Is it faster, right? But here is the hidden catch.

But the index only contains user_id. The query is asking for track_id and played_at. Because these columns are missing from the index, the database engine must use the pointers to jump from the B-Tree to the main heap to get the missing data.

You know what that means? 5000 physical jump to the Heap. And after the jump, sorting is done in the memory using the played_at column, and then it returns the top 10. This physical jump is what’s called the Heap Fetch, and this destroys I/O performance.

The standard index eliminates the Sequential Scan, but introduces a new bottleneck, which are the implicit Heap Fetch and heap sort in RAM. (Nano Banana for sharpening text in the terminal)

Method 3: Covering Index

CREATE INDEX idx_user_recent_plays 
ON listen_history (user_id, played_at DESC) 
INCLUDE (track_id);

SELECT track_id, played_at 
FROM listen_history 
WHERE user_id = '018dc336-1234...' 
ORDER BY played_at DESC 
LIMIT 10;

Look closely at this query:

1. The user_id and the played_at DESC are used to build the core structure of the B-Tree. With this, the data is sorted by user_id and then by played_at in descending order
2. The INCLUDE keyword bolts the track_id to the leaf nodes of the B-Tree

So when the SELECT query is run:

1. The database engine jumps to the user_id in the B-Tree.
2. And because the tree is pre-sorted using the played_at, no need to take all tracks and sorting; all the database engine does is to fetch the first 10 rows as it is exactly the 10 newest tracks.
3. It grabs the track_id from the leaf node, and returns the data to the user. It never jumps to the Heap. It never sorts data in memory. That is why it is called an Index-Only Scan, and it executes at the speed of memory.

The Covering Index doesn’t require the Heap Fetch and in-memory sorting isn’t required, reducing execution time to a blistering 0.106ms.
The magic. From a 217ms execution time to a 0.106ms execution time

NOTE: If you run this exact experiment locally immediately after doing a 1-million-row bulk insert, your initial Index-Only Scan might show a small number of Heap Fetches (e.g., Heap Fetches: 10). This is not a failure of the index. This happens because PostgreSQL hasn't had time to update its Visibility Map. The database checks the heap to ensure that another transaction hasn't deleted those specific 10 rows. Running a manual VACUUM on the table updates the map and instantly drops the Heap Fetches back down to zero.

WHEN TO USE COVERING INDEX:

Covering indexes are powerful, but if misused, they can slow down write speeds. They should not be abused.

Use them strictly for:

1. Highly critical, high-frequency read queries (endpoints hit thousands of times a second).
2. Queries that return a small, lightweight columns (Integers, UUIDs, Timestamps, Booleans) . Never INCLUDE massive text blocks or JSON data.