Database Indexing – Part 3: Understanding Composite Indexes in PostgreSQL

In PostgreSQL, we often come across queries that filter records based on multiple conditions.

Consider an employees table containing information such as employee ID, name, department, and salary.

Suppose we want to find employees working in the Engineering department who earn more than 50,000.

SELECT *
FROM employees
WHERE department = 'Engineering'
  AND salary > 50000;

This query looks simple, but what happens when the table contains millions of employee records?

PostgreSQL needs to identify the rows that satisfy both conditions. As the amount of data grows, finding those records efficiently becomes more important.

How can we optimize queries that filter on multiple columns?

In this article, we'll explore composite indexes in PostgreSQL and understand how they can help with such queries.

What Is a Composite Index?

A composite index, also called a multicolumn index, is an index created on two or more columns of a table.

In PostgreSQL, we can create a composite index using:

CREATE INDEX idx_employees_department_salary
ON employees (department, salary);

Here, we're creating a single index on two columns: department and salary.

Unlike separate indexes on each column, a composite index stores the values together in a specific order.

PostgreSQL organizes the index entries first by department, and then by salary within each department.

For example, consider these employee records:

employee_id	department	salary
1	Engineering	70000
2	HR	45000
3	Engineering	50000
4	Sales	60000
5	HR	55000
6	Engineering	90000

The composite index on (department, salary) organizes its entries in this order:

department	salary	Employee
Engineering	50000	3
Engineering	70000	1
Engineering	90000	6
HR	45000	2
HR	55000	5
Sales	60000	4

Notice that the employees are grouped by department. Within each department, their salaries are arranged in ascending order.

This ordering is important because PostgreSQL can use it to narrow down the records it needs to examine.

Also, column order matters. An index on (department, salary) is not organized in the same way as an index on (salary, department).

Understanding Index Behavior with an Example

Let's use an employees table to understand how PostgreSQL handles queries with multiple filtering conditions.

First, we'll create the table:

CREATE TABLE employees (
    employee_id BIGSERIAL PRIMARY KEY,
    employee_name TEXT,
    department TEXT,
    salary INTEGER
);

Now, let's insert 1 million employee records.

INSERT INTO employees (employee_name, department, salary)
SELECT
    'Employee_' || g,
    (ARRAY['Engineering', 'HR', 'Sales', 'Finance', 'Marketing'])[1 + (g % 5)],
    30000 + (g % 100) * 1000
FROM generate_series(1, 1000000) AS g;

We'll compare three index configurations:

• Case 1: Two separate indexes on department and salary.
• Case 2: A composite index on (department, salary), after removing the separate indexes.
• Case 3: A composite index on (department, salary) along with a separate index on salary.

For each configuration, we'll execute the same four queries and observe the execution plans and performance.

Case 1: Creating Two Separate Indexes

Let's start by creating two individual indexes on the employees table.

CREATE INDEX idx_employees_department
ON employees (department);

CREATE INDEX idx_employees_salary
ON employees (salary);

Now, let's execute a few queries and see how PostgreSQL uses these indexes.

Query 1: Filtering by Department

EXPLAIN (ANALYZE, BUFFERS)
SELECT employee_id
FROM employees
WHERE department = 'Engineering';

Execution Plan:

PostgreSQL used a Bitmap Index Scan on idx_employees_department, followed by a Bitmap Heap Scan.

A Bitmap Index Scan first identifies the locations of matching records using the index. PostgreSQL then uses those locations to access the required heap pages through a Bitmap Heap Scan.

Here, the query returned 200,000 records by accessing 8,161 heap pages.

Execution Time: 123.040 ms

Query 2: Filtering by Salary

EXPLAIN (ANALYZE, BUFFERS)
SELECT employee_id
FROM employees
WHERE salary = 70000;

Execution Plan:

This time, PostgreSQL used idx_employees_salary.

The execution plan again contained a Bitmap Index Scan followed by a Bitmap Heap Scan.

The query returned 10,000 records, accessing 8,161 heap pages.

Execution Time: 130.689 ms

Query 3: Filtering Using AND

Now, let's filter employees using both department and salary.

EXPLAIN (ANALYZE, BUFFERS)
SELECT employee_id
FROM employees
WHERE department = 'Engineering'
  AND salary = 70000;

Execution Plan:

PostgreSQL used two Bitmap Index Scans, combined their results using BitmapAnd, and then performed a Bitmap Heap Scan.

How does BitmapAnd work?

1. PostgreSQL searches idx_employees_department and identifies 200,000 matching records.
2. It searches idx_employees_salary and identifies 10,000 matching records.
3. BitmapAnd combines the two bitmaps, keeping only the row locations that satisfy both conditions.
4. The Bitmap Heap Scan uses the resulting bitmap to fetch matching rows from the table.

For example, suppose the two indexes identify these employee IDs:

Department = Engineering → 1, 3, 5, 7
Salary = 70000          → 2, 3, 5, 8

BitmapAnd                 → 3, 5

These IDs are just an example to illustrate the intersection. PostgreSQL's bitmaps represent heap tuple locations, not employee IDs directly.

In our actual execution:

• Rows returned: 10,000
• Heap pages accessed: 8,161
• Execution time: 117.610 ms

Notice that PostgreSQL scanned both indexes separately before combining their results. We will compare this behavior with a composite index in the next case.

Query 4: Filtering Using OR

Now, let's find employees who belong to the Engineering department or have a salary of 70,000.

EXPLAIN (ANALYZE, BUFFERS)
SELECT employee_id
FROM employees
WHERE department = 'Engineering'
   OR salary = 70000;

Execution Plan:

PostgreSQL used two Bitmap Index Scans, combined their results using BitmapOr, and then performed a Bitmap Heap Scan.

How does BitmapOr work?

1. PostgreSQL searches idx_employees_department and identifies 200,000 matching records.
2. It searches idx_employees_salary and identifies 10,000 matching records.
3. BitmapOr combines the two bitmaps, keeping row locations that match either condition.
4. The Bitmap Heap Scan visits the corresponding heap pages and retrieves the matching employee IDs.

For example:

Department = Engineering → 1, 3, 5, 7
Salary = 70000          → 2, 3, 5, 8

BitmapOr                  → 1, 2, 3, 5, 7, 8

PostgreSQL combines heap tuple locations rather than employee IDs directly.

Actual Results:

• Rows returned: 200,000
• Heap pages accessed: 8,161
• Execution time: 126.784 ms

Notice that the query returned 200,000 records, not 210,000. In our generated dataset, all employees earning 70,000 belong to the Engineering department, so those records already satisfy the first condition.

PostgreSQL used both indexes and combined their results without returning duplicate rows.

Case 2: Creating a Composite Index

Now, let's remove the two separate indexes and create a composite index on department and salary.

DROP INDEX idx_employees_department;
DROP INDEX idx_employees_salary;

Create the composite index:

CREATE INDEX idx_employees_department_salary
ON employees (department, salary);

Let's run the same four queries and observe how PostgreSQL uses this index.

Query 1: Filtering by Department

EXPLAIN (ANALYZE, BUFFERS)
SELECT employee_id
FROM employees
WHERE department = 'Engineering';

Execution Plan:

PostgreSQL used a Bitmap Index Scan on idx_employees_department_salary, followed by a Bitmap Heap Scan.

Here's how it works:

1. PostgreSQL searches the composite index using department = 'Engineering'.
2. Since department is the first column in the index, PostgreSQL can directly locate the matching index entries without requiring a condition on salary.
3. The Bitmap Index Scan collects the matching heap tuple locations into a bitmap.
4. The Bitmap Heap Scan visits the corresponding heap pages, checks tuple visibility, and retrieves the employee IDs.

Results:

• Rows returned: 200,000
• Heap pages accessed: 8,161
• Execution time: 130.189 ms

Even though the index contains two columns, PostgreSQL was able to use it with a condition on the first column alone.

Query 2: Filtering by Salary

Now, let's filter employees using only salary, which is the second column in our composite index (department, salary).

EXPLAIN (ANALYZE, BUFFERS)
SELECT employee_id
FROM employees
WHERE salary = 70000;

Execution Plan:

This time, PostgreSQL chose a Parallel Sequential Scan instead of using the composite index.

• Rows returned: 10,000
• Heap pages read: 8,161
• Workers launched: 2
• Execution time: 98.216 ms

PostgreSQL scanned the table using three processes (the main process and two parallel workers), checking the salary condition against the rows.

Why didn't PostgreSQL use the composite index?

Our composite index is created on:

CREATE INDEX idx_employees_department_salary
ON employees (department, salary);

PostgreSQL organizes the index entries first by department, then by salary within each department.

For example:

Department	Salary
Engineering	50000
Engineering	70000
Engineering	90000
Finance	60000
Finance	70000
HR	45000
HR	70000
Sales	55000
Sales	70000

Notice that employees earning 70,000 are spread across different departments in the index.

When we filter by department, PostgreSQL can directly locate the corresponding entries because it is the first indexed column.

But when we filter only by salary, the matching values are scattered across different departments. PostgreSQL cannot retrieve all matching entries through a single continuous range of the index.

This behavior is commonly described by the leftmost prefix rule.

• An index on (department, salary) efficiently supports filtering by department.
• It also supports filtering by both department and salary.
• Filtering only by salary is generally less efficient because the leading column is missing.

PostgreSQL can sometimes use a composite index even without a condition on its first column, but whether that is worthwhile depends on the data and estimated query cost.

In our execution, PostgreSQL chose a Parallel Sequential Scan rather than using the composite index.

Query 3: Filtering Using AND

Now, let's filter employees using both department and salary.

EXPLAIN (ANALYZE, BUFFERS)
SELECT employee_id
FROM employees
WHERE department = 'Engineering'
  AND salary = 70000;

Execution Plan:

PostgreSQL used a Bitmap Index Scan on idx_employees_department_salary, followed by a Bitmap Heap Scan.

Unlike Case 1, where PostgreSQL used two separate indexes and combined their results using BitmapAnd, this time it used a single composite index.

Here's how it works:

1. PostgreSQL searches the composite index for entries where department = 'Engineering'.
2. Since salary values are ordered within each department, PostgreSQL can further narrow the search to entries where salary = 70000.
3. The Bitmap Index Scan collects the matching heap tuple locations into a bitmap.
4. The Bitmap Heap Scan visits the corresponding heap pages, checks tuple visibility, and retrieves the matching employee IDs.

Results:

• Rows returned: 10,000
• Heap pages accessed: 8,161
• Execution time: 115.172 ms

PostgreSQL was able to use both filtering conditions directly within a single composite index.

Query 4: Filtering Using OR

Now, let's filter employees using either department or salary.

EXPLAIN (ANALYZE, BUFFERS)
SELECT employee_id
FROM employees
WHERE department = 'Engineering'
   OR salary = 70000;

Execution Plan:

This time, PostgreSQL chose a Sequential Scan instead of using the composite index.

Here's why:

1. Our composite index is created on (department, salary), where department is the first column.
2. PostgreSQL can efficiently search using department, but the OR condition also requires finding employees with salary = 70000, regardless of their department.
3. Since salary is the second column, its matching values are spread across different departments in the index.
4. PostgreSQL estimated that scanning the table and checking both conditions would be cheaper than using the composite index.

Results:

• Rows returned: 200,000
• Rows removed by filter: 800,000
• Heap pages read: 8,161
• Execution time: 138.981 ms

Unlike Case 1, where PostgreSQL combined two separate indexes using BitmapOr, here it performed a Sequential Scan because there was no separate index on salary.

Case 3: Composite Index with a Separate Salary Index

We have kept the composite index on (department, salary) and created an additional index on salary.

CREATE INDEX idx_employees_salary
ON employees (salary);

Now, let's run the same four queries again.

Query 1: Filtering by Department

EXPLAIN (ANALYZE, BUFFERS)
SELECT employee_id
FROM employees
WHERE department = 'Engineering';

Execution Plan:

PostgreSQL used a Bitmap Index Scan on idx_employees_department_salary, followed by a Bitmap Heap Scan.

Here's how it works:

1. PostgreSQL searches the composite index using department = 'Engineering'.
2. Since department is the first column in the index, PostgreSQL can locate the matching entries without requiring a condition on salary.
3. The Bitmap Index Scan collects the matching heap tuple locations.
4. The Bitmap Heap Scan visits the corresponding heap pages, checks tuple visibility, and retrieves the employee IDs.

Results:

• Rows returned: 200,000
• Heap pages accessed: 8,161
• Execution time: 127.859 ms

PostgreSQL continued to use the composite index for this query. The separate salary index was not needed because the query filtered only on department.

Query 2: Filtering by Salary

Now, let's filter employees using only salary.

EXPLAIN (ANALYZE, BUFFERS)
SELECT employee_id
FROM employees
WHERE salary = 70000;

Execution Plan:

PostgreSQL used a Bitmap Index Scan on idx_employees_salary, followed by a Bitmap Heap Scan.

Here's how it works:

1. PostgreSQL searches the separate salary index for entries where salary = 70000.
2. The Bitmap Index Scan collects the matching heap tuple locations into a bitmap.
3. The Bitmap Heap Scan visits the corresponding heap pages, checks tuple visibility, and retrieves the matching employee IDs.

Results:

• Rows returned: 10,000
• Heap pages accessed: 8,161
• Execution time: 12.315 ms

In Case 2, PostgreSQL chose a Parallel Sequential Scan because only the composite index (department, salary) was available.

Now that we have a separate index on salary, PostgreSQL can directly search for matching salary values without depending on the leading department column.

Query 3: Filtering Using AND

Now, let's filter employees using both department and salary.

EXPLAIN (ANALYZE, BUFFERS)
SELECT employee_id
FROM employees
WHERE department = 'Engineering'
  AND salary = 70000;

Execution Plan:

PostgreSQL used a Bitmap Index Scan on idx_employees_department_salary, followed by a Bitmap Heap Scan.

Even though we have a separate index on salary, PostgreSQL chose to use only the composite index.

Here's how it works:

1. PostgreSQL searches the composite index for entries where department = 'Engineering'.
2. Since salary values are ordered within each department, PostgreSQL can further narrow the search using salary = 70000.
3. The Bitmap Index Scan collects the matching heap tuple locations into a bitmap.
4. The Bitmap Heap Scan visits the corresponding heap pages, checks tuple visibility, and retrieves the matching employee IDs.

Results:

• Rows returned: 10,000
• Heap pages accessed: 8,161
• Execution time: 94.164 ms

Unlike Case 1, where PostgreSQL combined two separate indexes using BitmapAnd, here it used a single composite index to apply both filtering conditions.

The separate salary index was not needed for this query.

Query 4: Filtering Using OR

Now, let's filter employees using either department or salary.

EXPLAIN (ANALYZE, BUFFERS)
SELECT employee_id
FROM employees
WHERE department = 'Engineering'
   OR salary = 70000;

Execution Plan:

PostgreSQL used two Bitmap Index Scans, combined their results using BitmapOr, and then performed a Bitmap Heap Scan.

This time, PostgreSQL used both the composite index idx_employees_department_salary and the separate index idx_employees_salary.

Here's how it works:

1. PostgreSQL searches the composite index using department = 'Engineering' and identifies 200,000 matching records.
2. It searches the separate salary index using salary = 70000 and identifies 10,000 matching records.
3. BitmapOr combines both bitmaps, keeping the heap tuple locations that match either condition.
4. The Bitmap Heap Scan visits the corresponding heap pages, checks tuple visibility, and retrieves the matching employee IDs.

Results:

• Rows returned: 200,000
• Heap pages accessed: 8,161
• Execution time: 63.308 ms

In Case 2, PostgreSQL performed a Sequential Scan for the same OR query because only the composite index was available.

With the additional salary index, PostgreSQL was able to use BitmapOr to combine both indexes and retrieve the matching records.

Comparing the Three Index Configurations

We executed the same four queries using different index configurations.

Query	Separate Indexes	Composite Index	Composite + Salary Index
Department	Bitmap Index Scan	Bitmap Index Scan	Bitmap Index Scan
Salary	Bitmap Index Scan	Parallel Seq Scan	Bitmap Index Scan
Department AND Salary	BitmapAnd	Bitmap Index Scan	Bitmap Index Scan
Department OR Salary	BitmapOr	Seq Scan	BitmapOr

Conclusion

Composite indexes are useful when queries frequently filter or sort using multiple columns.

• Column order matters: The order of columns in a composite index determines how efficiently PostgreSQL can use it for searching and sorting.
• Leftmost prefix rule: PostgreSQL generally uses composite indexes most efficiently when queries filter using the leading indexed columns. Filtering only by a non-leading column may be less efficient.
• AND conditions: A composite index can use multiple filtering conditions in a single index scan, avoiding the need to combine separate indexes.
• OR conditions: PostgreSQL can combine multiple indexes using BitmapOr when suitable indexes are available. Otherwise, it may choose a Sequential Scan.
• Separate indexes: A composite index may not replace the need for individual indexes, especially when non-leading columns are frequently filtered independently.

Composite indexes can improve query performance when columns are indexed in the right order. However, no single index works best for every query, so choose indexes based on your most frequently used filtering and sorting conditions.