Database Indexing – Part 1: How Indexes Help Find Data Faster

Recently, I was reading two books: Good Vibes, Good Life and The Mountain Is You.

I usually forget things after some time 😅. So whenever I want to revisit something I've read, I go back to the book.

But I noticed one difference between these two books.

Good Vibes, Good Life has an index at the end of the book. Whenever I want to read about a particular topic, I can look at the index, find the page number, and directly go to that page.

But The Mountain Is You doesn't have that kind of index.

So if I remember a topic but don't remember where I read it, I have to go through the chapters one by one until I find it.

That takes more time, right?

The same thing happens in databases.

Imagine we have a table containing millions of records, and we want to find one particular record.

Without an index, the database may need to scan the entire table, checking rows to find the data we're looking for.

But if we have a suitable index, the database can use it to quickly locate the required record instead of checking every row.

This is why we use indexes in databases.

An index is a separate data structure that helps the database find records efficiently, just like the index in a book helps us find a topic without going through every page.

Before moving forward, check out my previous article, Database Storage Concepts – How Tables Are Stored on Disk, to understand how databases store data internally.

Now, let's see how indexing actually works in PostgreSQL.

Creating a Table with an Index and 10 Million Records

First, let's create an employees table with three columns: id, name, and salary.

Step 1: Create the table

CREATE TABLE employees (
    id INTEGER PRIMARY KEY,
    name TEXT,
    salary INTEGER
);

Here, we defined id as the PRIMARY KEY.

In PostgreSQL, whenever we define a primary key, it automatically creates a unique B-tree index on that column.

In our case, PostgreSQL created an index named employees_pkey on the id column.

Step 2: Insert 10 million records

INSERT INTO employees (id, name, salary)
SELECT
    g,
    'Employee_' || g,
    30000 + (random() * 70000)::INTEGER
FROM generate_series(1, 10000000) AS g;

We now have a table containing 10 million employee records.

Let's understand how PostgreSQL uses indexes when we execute different queries.

Understanding Indexes Through Queries

Query 1: Fetching a Record Using an Indexed Column

Let's find the employee whose id is 20.

EXPLAIN (ANALYZE, BUFFERS)
SELECT id FROM employees WHERE id = 20;

Before looking at the output, let's understand what EXPLAIN, ANALYZE, and BUFFERS mean.

• EXPLAIN: Shows how PostgreSQL plans to execute a query without actually running it.
• ANALYZE: Executes the query and shows what actually happened, including the number of rows returned and execution time.
• BUFFERS: Shows how many data block accesses PostgreSQL made during planning and execution, including blocks already available in memory and blocks that had to be read into memory.

By combining these options, we can understand how PostgreSQL executes our query and how it accesses data.

Output (First Execution):

Now, let's understand each part of the output.

1. Index Only Scan

Index Only Scan using employees_pkey on employees

• PostgreSQL used the employees_pkey index, which was automatically created when we defined id as the primary key.
• We're searching by id and selecting only id.
• Since id is already stored in the index, PostgreSQL can retrieve the required value directly from the index.
• It doesn't need to fetch the full employee record from the table, provided PostgreSQL can confirm that the row is visible without checking the heap.

This is called an Index Only Scan.

2. Cost

cost=0.43..4.45

• 0.43: Estimated startup cost before PostgreSQL can begin returning rows.
• 4.45: Estimated total cost of executing this operation.

These values are PostgreSQL's internal cost estimates, not actual execution times in milliseconds.

3. Rows and Width

rows=1 width=4

• rows=1: PostgreSQL estimates that one row will be returned.
• width=4: The estimated average size of each returned row is 4 bytes.

We're selecting only id, which is an integer occupying 4 bytes.

4. Actual Time, Rows, and Loops

actual time=0.058..0.059 rows=1 loops=1

• 0.058: Time taken until the first row was returned.
• 0.059: Time taken until this scan operation completed.
• rows=1: One row was actually returned.
• loops=1: This operation executed once.

The actual times are measured in milliseconds.

5. Index Condition

Index Cond: (id = 20)

This tells us that PostgreSQL used the condition id = 20 to search the index.

6. Heap Fetches

Heap Fetches: 0

PostgreSQL stores actual table records in heap pages.

An Index Only Scan can avoid visiting heap pages when all the required values are available in the index and PostgreSQL can confirm row visibility using its visibility map.

Here, Heap Fetches: 0 means PostgreSQL didn't need to visit any heap pages to check row visibility.

7. Buffers

Buffers: shared read=4

PostgreSQL stores frequently accessed data pages in memory, in an area called shared buffers.

• shared read=4: PostgreSQL had to read 4 blocks into its shared buffer cache.
• Each PostgreSQL block is typically 8 KB.

This doesn't necessarily mean 4 physical disk reads, because the operating system may already have those pages cached.

8. Planning Time and Execution Time

Planning:
  Buffers: shared hit=41 read=20
Planning Time: 0.616 ms
Execution Time: 0.097 ms

Before executing a query, PostgreSQL first decides how to execute it.

For example, it checks what indexes are available, estimates how many rows might match, and decides which execution plan would be more efficient.

During this process, PostgreSQL may need to access database pages containing metadata and statistics.

That's why we see:

Planning:
  Buffers: shared hit=41 read=20

• shared hit=41: During planning, PostgreSQL made 41 buffer accesses that found pages already available in shared buffers.
• shared read=20: During planning, PostgreSQL made 20 block reads into shared buffers.
• Planning Time: 0.616 ms: Time taken to prepare the execution plan.
• Execution Time: 0.097 ms: Time taken to execute the plan and retrieve the result.

So, PostgreSQL first decides how to fetch the data (planning) and then actually fetches the data (execution).

What Happens When We Run the Same Query Again?

I executed the exact same query one more time.

Output (Second Execution):

Notice the difference:

Metric	First execution	Second execution
Execution shared reads	4	0
Execution shared hits	0	4
Planning time	0.616 ms	0.059 ms
Execution time	0.097 ms	0.027 ms

In the first execution, PostgreSQL had to read 4 blocks into shared buffers.

But during the second execution, those blocks were already available in PostgreSQL's memory.

That's why we see:

Buffers: shared hit=4

A shared hit means PostgreSQL found the required block in its shared buffer cache without needing to read it into that cache again.

The second execution was faster in our experiment, although execution times can also vary for other reasons.

Testing Without PostgreSQL's Existing Cache

If you want to observe how a query behaves when its pages are not already cached in PostgreSQL's shared buffers, you can restart PostgreSQL on your local test machine.

On Ubuntu:

sudo systemctl restart postgresql

Then execute:

EXPLAIN (ANALYZE, BUFFERS)
SELECT id FROM employees WHERE id = 20;

Restarting PostgreSQL clears its shared buffer cache, but it does not clear the operating system's page cache. Some pages may also be loaded again before your query runs.

So this is useful for observing PostgreSQL's buffer behavior, but it doesn't guarantee a completely cold disk-cache experiment.

Only restart PostgreSQL for this purpose on a local test environment, not on a production or shared database.

Query 2: Fetching a Column That Is Not in the Index

In the previous query, we selected id, which was already available in the primary key index.

Now, let's try fetching name using the same index.

EXPLAIN (ANALYZE, BUFFERS)
SELECT name FROM employees WHERE id = 500;

Output:

Here, PostgreSQL used an Index Scan instead of an Index Only Scan.

Why?

Our employees_pkey index contains id, but not name.

So PostgreSQL:

1. Searches the index to find id = 500.
2. Gets the reference to the corresponding heap row.
3. Visits the heap to fetch the name.

This is called an Index Scan.

Notice the estimated cost:

cost=0.43..8.45 rows=1 width=16

The total estimated cost is 8.45, compared with 4.45 in Query 1, because PostgreSQL also needs to fetch the row from the heap.

The estimated width is now 16 bytes instead of 4, because we're selecting a text column rather than an integer.

Buffers: shared hit=2 read=2

During execution, PostgreSQL made 2 shared-buffer hits and 2 shared-buffer reads, covering the index search and heap access.

The execution took 0.093 ms.

So the difference is simple: an Index Only Scan can return data from the index without visiting the heap when visibility permits, whereas this Index Scan uses the index to find the row and then visits the heap to retrieve name.

Query 3: Searching Using a Column Without an Index

Until now, we've been searching using id, which has an index.

But what happens if we search using a column that doesn't have an index?

Let's try searching using name.

EXPLAIN (ANALYZE, BUFFERS)
SELECT id FROM employees
WHERE name = 'Employee_500';

Output:

Here, PostgreSQL used a Parallel Sequential Scan.

Let's understand what happened.

1. Parallel Sequential Scan

Parallel Seq Scan on employees

Since we haven't created an index on name, PostgreSQL cannot use an index on that column to locate the required employee.

Instead, it scans the table and checks the name of each row against our condition.

But rather than using a single process, PostgreSQL decided to scan the table in parallel.

2. Workers Planned and Launched

Workers Planned: 2
Workers Launched: 2

PostgreSQL planned to use 2 additional worker processes and successfully launched both.

Along with the main process, 3 processes participated in scanning the table.

Each process works on different portions of the table, allowing the scan to finish faster than a single-process scan might.

3. Filter and Rows Removed

Filter: (name = 'Employee_500'::text)
Rows Removed by Filter: 3333333

PostgreSQL checks each row against the condition name = 'Employee_500'.

Rows that don't match are removed by the filter.

Here, Rows Removed by Filter: 3333333 is the average number of rows rejected per execution of the parallel scan, rounded for display.

Since loops=3, approximately 10 million rows were checked across all three participants.

Even though we wanted only one employee, PostgreSQL had to examine the entire table.

4. Gather

Gather  (cost=1000.00..125620.26 rows=1 width=4)

The Gather operation collects the rows produced by the parallel scan participants and passes them to the main query process.

In our case, only one row matched the condition.

5. Buffer Usage

Buffers: shared hit=1 read=72545

During execution, PostgreSQL made:

• 1 shared-buffer hit.
• 72,545 shared-buffer reads.

With the usual 8 KB page size, those reads represent approximately 567 MB of block-read traffic.

Notice that the Gather and Parallel Seq Scan show the same buffer totals. We shouldn't add them together, because the parent node's statistics include the work of its child node.

6. Execution Time

Execution Time: 374.165 ms

The query took 374.165 ms to execute.

Compare that with Query 2, where we searched using the indexed id column and the execution took 0.093 ms.

The difference is significant in these particular runs.

With the index, PostgreSQL could locate the row directly. Without an index on name, it scanned all 10 million records to find one matching employee.

Query 4: Creating an Index on the Name Column and Comparing Query Performance

In the previous query, PostgreSQL scanned all 10 million records because there was no index on name.

Now, let's create an index on that column.

CREATE INDEX employees_name_idx
ON employees (name);

This creates a B-tree index on name.

Let's execute the query again.

EXPLAIN (ANALYZE, BUFFERS)
SELECT id FROM employees
WHERE name = 'Employee_500';

Output:

This time, PostgreSQL used an Index Scan.

1. Index Scan

Index Scan using employees_name_idx on employees

PostgreSQL searches the new index for Employee_500.

Since we're selecting id, which isn't stored in this index, PostgreSQL then visits the heap to fetch it.

2. Buffer Usage

Buffers: shared hit=1 read=4

During execution, PostgreSQL made just 5 shared-buffer accesses, compared with 72,546 in the previous query.

3. Execution Time

Execution Time: 0.050 ms

Let's compare the results before and after creating the index.

Metric	Without index	With index
Scan type	Parallel Seq Scan	Index Scan
Shared hits	1	1
Shared reads	72,545	4
Execution time	374.165 ms	0.050 ms

The execution time decreased from 374.165 ms to 0.050 ms — approximately 7,483 times faster in these two runs.

Of course, caching and other execution conditions can also affect these timings, so we shouldn't expect exactly the same improvement every time.

But the important difference is how PostgreSQL searches for the record.

Earlier, PostgreSQL had to scan the entire table to find Employee_500.

After creating the index, it searched the B-tree index for that particular name and used the matching entry to fetch the row from the heap.

So even if the execution time varies due to caching, PostgreSQL no longer needs to scan all 10 million table records just to find that employee.

Query 5: Sorting Records Without an Index

So far, we've seen how indexes help PostgreSQL search for records. But indexes can also help when sorting data.

Let's find the top 100 employees with the highest salaries.

EXPLAIN (ANALYZE, BUFFERS)
SELECT id, salary
FROM employees
ORDER BY salary DESC
LIMIT 100;

Output:

Note: When reading an EXPLAIN ANALYZE execution plan, it's usually easier to start from the bottom and move toward the top.

The lower-level operations produce data, which is then passed to their parent operations.

In our query, the data flows through:

1. Parallel Seq Scan – Reads the records from the table.
2. Sort – Finds the highest salaries.
3. Gather Merge – Combines the sorted results from the parallel workers.
4. Limit – Returns only the top 100 records.

This is a useful way to understand execution plans, although some operations can run at the same time.

Now, let's understand each operation.

1. Parallel Sequential Scan

Parallel Seq Scan on employees

Since there is no index on salary, PostgreSQL scans the table to find the highest salaries.

Even though we requested only 100 records, PostgreSQL still needs to examine all 10 million records to determine which employees have the highest salaries.

2. Sort

Sort Key: salary DESC
Sort Method: top-N heapsort  Memory: 31kB

PostgreSQL needs to arrange the results by salary in descending order.

But notice that it used top-N heapsort.

Since we requested only the top 100 records, PostgreSQL doesn't need to fully sort all 10 million records.

Instead, each parallel scan participant keeps track of its best 100 candidates while processing the rows.

This reduces the memory required for sorting, but the table still has to be scanned.

3. Gather Merge

Gather Merge
Workers Planned: 2
Workers Launched: 2

The parallel participants produce sorted results.

Gather Merge combines these results while maintaining the salary order.

4. Limit

Limit

Finally, PostgreSQL returns only the first 100 records from the sorted results.

5. Buffer Usage and Execution Time

Buffers: shared hit=273 read=72385
Execution Time: 575.346 ms

During execution, PostgreSQL made 273 shared-buffer hits and 72,385 shared-buffer reads.

The query took 575.346 ms to execute.

Even though we requested just 100 records, PostgreSQL had to examine all 10 million records to identify the highest salaries.

Query 6: Sorting Records After Creating an Index on Salary

In the previous query, PostgreSQL scanned all 10 million records and performed sorting to find the top 100 highest salaries.

Now, let's create an index on salary.

CREATE INDEX employees_salary_idx
ON employees (salary);

This creates a B-tree index on the salary column, where the index entries are maintained in sorted order.

Let's run the same query again.

EXPLAIN (ANALYZE, BUFFERS)
SELECT id, salary
FROM employees
ORDER BY salary DESC
LIMIT 100;

Output:

Notice that PostgreSQL used an Index Scan Backward instead of a Parallel Sequential Scan followed by sorting.

1. Index Scan Backward

Index Scan Backward using employees_salary_idx on employees

A B-tree index keeps its entries in sorted order.

Since our query uses ORDER BY salary DESC, PostgreSQL can scan the index backward, starting from the highest salary values.

It doesn't need to sort all 10 million records separately.

And because we're also selecting id, which isn't stored in the salary index, PostgreSQL visits the heap to fetch it.

2. Limit

Limit (cost=0.43..5.17 rows=100 width=8)

This is where the LIMIT 100 makes a big difference.

PostgreSQL starts reading the index from the highest salary and stops after returning 100 records.

Even though the index contains entries for 10 million records, PostgreSQL doesn't need to scan all of them.

3. Buffer Usage

Buffers: shared read=103

PostgreSQL made only 103 shared-buffer reads during execution.

Compare that with the previous query, which required 72,658 buffer accesses.

4. Execution Time

Execution Time: 1.123 ms

Let's compare both executions.

Metric	Without salary index	With salary index
Execution plan	Parallel Seq Scan + Sort	Index Scan Backward
Shared hits	273	0
Shared reads	72,385	103
Execution time	575.346 ms	1.123 ms

The execution time decreased from 575.346 ms to 1.123 ms, approximately 512 times faster in these runs.

Although caching can affect execution times, the important difference is that PostgreSQL no longer needs to scan the entire table and sort the results.

It can simply scan the index backward, retrieve the highest salary records, and stop after finding 100 rows.

Query 7: Why Doesn't PostgreSQL Always Use an Index?

Until now, we've seen how indexes improved query performance.

But does PostgreSQL always use an index whenever one is available?

Let's try searching for employees whose salary is greater than 40000.

Remember, we already created an index on the salary column.

EXPLAIN (ANALYZE, BUFFERS)
SELECT id, salary
FROM employees
WHERE salary > 40000;

Output:

Interesting! PostgreSQL chose a Sequential Scan, even though an index exists on salary.

Why?

1. Sequential Scan

Seq Scan on employees

Our condition is:

WHERE salary > 40000

This matches a large number of employees.

In our case, PostgreSQL found 8,572,502 matching records out of 10 million, which is approximately 85.7% of the table.

If PostgreSQL used the salary index, it would need to find all matching index entries and then visit the heap to fetch id, since id isn't stored in that index.

For so many matching records, accessing the heap through the index could require more work than simply scanning the table.

So PostgreSQL estimated that a Sequential Scan would be cheaper.

2. Rows Removed by Filter

Filter: (salary > 40000)
Rows Removed by Filter: 1427498

PostgreSQL scanned all 10 million records.

Of those:

• 8,572,502 records matched the condition.
• 1,427,498 records were removed by the filter.

3. Buffer Usage

Buffers: shared hit=16247 read=56299

PostgreSQL accessed 72,546 shared-buffer blocks while scanning the table.

Some pages were already cached, while others had to be read into shared buffers.

4. Execution Time

Execution Time: 1123.251 ms

The query took approximately 1.12 seconds to execute and return over 8.5 million rows to the query executor.

Here, the important thing is that having an index doesn't mean PostgreSQL will always use it.

PostgreSQL's query planner estimates the cost of different execution plans and chooses the one it expects to be cheaper.

When a query returns a small number of records, an index can be very useful. But when most of the table matches, a sequential scan may be more efficient.

What's Next?

In this article, we focused on understanding indexing through practical queries and execution plans.

In Part 2, we'll explore different types of index scans, when PostgreSQL chooses each one, and how we can design indexes more efficiently.

That's it for now! 😊

Thanks for reading!