Database Indexing – Part 6: How Does PostgreSQL Decide Which Index to Use?

In my previous article, we explored Sequential Scan, Index Scan, and Bitmap Index Scan in PostgreSQL.

We also saw that PostgreSQL doesn't always use an index, even when one is available.

But how does PostgreSQL decide which execution plan to use?

It can use a single index, combine multiple indexes, or scan the entire table.

In this article, we'll understand how PostgreSQL makes these decisions using practical examples.

Understanding Query Planner Decisions with an Example

Let's create a table with two columns, f1 and f2, and separate indexes on both.

We'll use this table to understand when PostgreSQL chooses to use both indexes, only one index, or no index.

1. Creating the Table

CREATE TABLE planner_test (
    id BIGSERIAL PRIMARY KEY,
    f1 INTEGER,
    f2 INTEGER,
    record_name TEXT
);

2. Inserting 1 Million Records

INSERT INTO planner_test (f1, f2, record_name)
SELECT
    (random() * 999)::INTEGER + 1,
    (random() * 999)::INTEGER + 1,
    'Record_' || g
FROM generate_series(1, 1000000) AS g;

Here, f1 and f2 contain randomly generated values from approximately 1 to 1,000.

3. Creating the Indexes

Let's create separate indexes on both columns.

CREATE INDEX idx_planner_f1
ON planner_test (f1);

CREATE INDEX idx_planner_f2
ON planner_test (f2);

Since id is the primary key, PostgreSQL also automatically creates an index on it.

4. Updating Table Statistics

ANALYZE planner_test;

This updates PostgreSQL's statistics about the table and its data distribution, helping the query planner estimate the cost of different execution plans.

Now, we'll run queries with different filtering conditions and observe how PostgreSQL decides which indexes to use.

Case 1: Using Both Indexes

Let's execute a query with two filtering conditions.

EXPLAIN (ANALYZE, BUFFERS)
SELECT record_name
FROM planner_test
WHERE f1 BETWEEN 1 AND 200
  AND f2 BETWEEN 1 AND 200;

Execution Plan:

PostgreSQL chose to use both indexes and combine their results using BitmapAnd.

1. The index on f1 identified 199,631 matching records.
2. The index on f2 identified 200,182 matching records.
3. BitmapAnd combined both bitmaps, keeping only the row locations that matched both conditions.
4. The Bitmap Heap Scan retrieved 39,668 records from the table.

Each condition matched around 200,000 records individually, but only around 40,000 records satisfied both conditions.

PostgreSQL estimated that combining both indexes would be cheaper than using one index and checking the other condition on the retrieved rows.

Case 2: Using Only One Index

Now, let's execute a query where one condition matches very few records.

EXPLAIN (ANALYZE, BUFFERS)
SELECT record_name
FROM planner_test
WHERE f1 = 1
  AND f2 BETWEEN 1 AND 200;

Execution Plan:

PostgreSQL chose to use only the index on f1, followed by a Bitmap Heap Scan.

1. The Bitmap Index Scan on idx_planner_f1 identified 487 records matching f1 = 1.
2. The Bitmap Heap Scan fetched those records from the table.
3. PostgreSQL checked the remaining condition, f2 BETWEEN 1 AND 200, and removed 399 records.
4. Finally, 88 records were returned.

Since the first index identified only 487 records, PostgreSQL estimated that checking the second condition on those rows would be cheaper than scanning another index and combining both results using BitmapAnd.

Case 3: Without Using Any Index

Now, let's execute a query where both conditions match a large number of records.

EXPLAIN (ANALYZE, BUFFERS)
SELECT record_name
FROM planner_test
WHERE f1 BETWEEN 1 AND 900
  AND f2 BETWEEN 1 AND 900;

Execution Plan:

PostgreSQL chose a Sequential Scan, even though separate indexes are available on both f1 and f2.

1. PostgreSQL scanned the entire planner_test table.
2. It checked both filtering conditions on each record.
3. 189,044 records were removed because they didn't satisfy both conditions.
4. Finally, 810,956 records were returned.

The query returned more than 80% of the table's records.

Using indexes would require PostgreSQL to scan the indexes and fetch a large number of records from the heap.

PostgreSQL estimated that scanning the table directly would be cheaper than using either index or combining both indexes.

Importance of Table Statistics

PostgreSQL uses table statistics to estimate how many records might match a query and choose an execution plan with the lowest estimated cost.

After bulk INSERT, UPDATE, or DELETE operations, these statistics may become outdated. PostgreSQL might then choose a less efficient execution plan.

We can run VACUUM (ANALYZE) to clean up the table and update its statistics.

VACUUM (ANALYZE) table_name;

• VACUUM: Cleans up dead tuples created by UPDATE and DELETE operations, making the space available for reuse.
• ANALYZE: Updates table statistics so PostgreSQL can make better decisions when choosing an execution plan.

PostgreSQL also performs these operations automatically, but they may not run immediately after bulk data changes.

If we've only inserted new records, running ANALYZE alone is generally sufficient to update the statistics.

We can also give hints to PostgreSQL to influence which indexes it uses.

We'll explore how these hints work in the next article.