How PostgreSQL Indexes Work

Heap pages, CTIDs, B-tree index scans, covering indexes, the leftmost prefix rule, and when an index is worth adding.

To see what an index changes, start with how PostgreSQL stores and reads a table without one.

How PostgreSQL stores data internally

1. PostgreSQL stores table data in a heap storage structure.
2. The heap is organized into multiple fixed-size pages (blocks), usually 8 KB each by default.
3. Each page can have multiple tuples, depending on page size.

Tuple is simply the data row itself, but along with some additional metadata like CTID, xmin/xmax, etc. So millions of rows of data from a db table can be termed as tuples divided into multiple pages.

CTID

• Special column that exists in each table, and represents physical location of a row within that table.
• Its format is (block_number, tuple_offset).
• Example: (42, 3) means the tuple is on block/page 42, and at index 3 within that block.
• This ctid can change when a row is updated, so it should not be used as a permanent row identifier.

Table rows stored as tuples across heap pages; each tuple’s (page, offset) is its CTID.

Data Retrieval in PostgreSQL / Sequential Scan

Suppose we have this query:

SELECT *
FROM users
WHERE location = 'Kathmandu';

1. First, PostgreSQL determines the query plan on how to access this data, whether index is present or sequential scan is appropriate, etc.
2. Then, executor requests this table’s pages from PostgreSQL’s buffer manager, which either returns pages present in shared buffers (already cached ones) or simply gets the pages from the heap itself.
3. Now, PostgreSQL will look for each tuple one by one, return the matching tuples, and will continue looking for the matches till it completes scanning all the tuples.
4. So, if a table has 10 million rows, then sequential scan will look for all the rows even if a match was found in the early stage of execution.

Index based Scan

Suppose we have query like this:

SELECT *
FROM employees
WHERE location = 'Kathmandu'
  AND salary > 70000;

And the employees table has many fields like id, name, location, salary, department, etc.

Now we can create index like this:

CREATE INDEX idx_employees_location_salary
ON employees (location, salary);

This will create a separate data structure in PostgreSQL, which can be scanned instead of scanning the whole table.

• This data structure is a B-tree, and it will only have these columns: location, salary and TID (the row’s address in the heap, used to find the full original tuple).
• TID and CTID are the same address: TID is what the index stores, and ctid is the system column you can query to see it.
• Here, the structure is sorted (location first, then salary wise sorting).

Instead of examining every tuple from the original table, PostgreSQL traverses the B-tree to locate matching index entries.

It then uses their TIDs to locate and fetch the corresponding heap tuples when necessary, and the full table scan can be avoided.

Covering Index

An index that includes all columns a query needs, so the database usually doesn’t need to read the actual table. It still checks the table for rows on pages that aren’t yet marked all-visible.

CREATE INDEX idx_orders_covering ON orders (customer_id) INCLUDE (total,
created_at);

Here, a query selecting customer_id, total, and created_at can usually be answered from the index alone (an index-only scan).

Leftmost Prefix Rule for Composite Index

So composite index is built based on order of columns defined in the index. An index (a, b, c) is physically sorted by a, then by b within each a, then by c within that.

Leftmost prefix rule

The index can be used efficiently only if our query condition includes the leftmost column. For index (a,b,c):

Composite index (a, b, c) is only usable when the query filters on a.

So, if column ‘a’ is not even used in a query, then the index itself cannot be used for efficient scanning. (PostgreSQL 18 added skip scan, which can still use the index in some of these cases when a has few distinct values.)

The rule is just that the WHERE clause in our query should include leftmost columns from our index.

• The order of columns used in the query doesn’t matter.
• PostgreSQL optimizer arranges the conditions in the right order itself.

-- index (a, b, c)
WHERE a = 1 AND b = 2 AND c = 3   -- uses the index
WHERE c = 3 AND b = 2 AND a = 1   -- uses the index in exactly the same way
WHERE b = 2 AND a = 1             -- works like WHERE a = 1 AND b = 2

3 main rules for choosing column order in composite index

Suppose, we have a query like this, that gets run frequently:

SELECT *
FROM employees
WHERE department = 'IT'
  AND age BETWEEN 25 AND 35
ORDER BY salary DESC;

Rule 1:

• Put equality columns first (operators like =, or IN).
• This is done so that equality lets the database narrow down to specific values early in the index.

Rule 2:

• Put range columns after equality columns. (operators like <, >, <=, >=, BETWEEN, LIKE).
• Since, we have department as equality and age as range in above example, our index will be:

CREATE INDEX idx_emp ON employees (department, age);

Rule 3:

Get Suyan Shrestha’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Include order itself in the index when that order based queries are used often.

If we have a query like this:

SELECT *
FROM employees
WHERE department = 'IT'
ORDER BY salary DESC;

Then, we can have index like this:

CREATE INDEX idx_emp ON employees (department, salary DESC);

This is not generally required, since PostgreSQL can walk the index backwards (Index Scan Backward), which is about as fast. Explicit DESC matters when a query sorts columns in different directions, like ORDER BY department ASC, salary DESC.

When to add/skip an index?

Add when:

1. A column appears frequently in WHERE, JOIN, or ORDER BY clauses.
2. For foreign keys, since this can speed up joins.

InnoDB (MySQL’s storage engine) automatically adds indexes on FK, but PostgreSQL doesn’t.

Suppose, we have two tables, employees and departments, where departments is the parent table, and employees is the child table with FK department_id.

Parent table departments (PK id) and child table employees (FK department_id).

Here, departments.id is PK, so is indexed automatically, but employees.department_id is not.

• Without an index on FK, deleting or updating a row from the departments table might be very slow here, since all affected rows of the employees table should be scanned first.

But, we shouldn’t be adding index on all FK:

• Don’t add for small tables.
• Don’t add when FK are rarely used as query, like queries with “WHERE department_id = 1”.

Skip when:

1. The table is small (as a rough rule of thumb, under 10k rows), since sequential scans are fast enough.
2. The column has low selectivity (e.g., a boolean is_active column with only two values).
3. Write-heavy tables, since managing writes on both the actual table as well as maintaining the indexes with updated writes will make it even more slow.
4. The query returns a large percentage of the table’s rows. At some point, a sequential scan is faster than thousands of random index lookups.

How do I know if my index is used?

Step 1: Run the query with EXPLAIN ANALYZE and read the plan:

EXPLAIN ANALYZE
SELECT *
FROM employees
WHERE location = 'Kathmandu'
  AND salary > 70000;

• Index Scan, Index Only Scan, or Bitmap Index Scan using idx_employees_location_salary means the index was used.
• Seq Scan on employees means it wasn't. On a small table this is expected, since a sequential scan is cheaper there.

Step 2: Check index usage in PostgreSQL via pg_stat_user_indexes. This shows, how often that index is used, and if the index is nothing but a dead weight.

SELECT relname AS table_name,
       indexrelname AS index_name,
       idx_scan
FROM pg_stat_user_indexes
ORDER BY idx_scan;

• idx_scan counts how many times the index has been scanned since statistics were last reset.
• An index that stays at 0 over a long period isn't helping any query, but it still slows down every write.

Summary

• PostgreSQL stores rows as tuples in 8 KB heap pages. Without an index, a query has to scan every one of them.
• A B-tree index keeps the indexed columns sorted, with a TID pointing to each row, so PostgreSQL can jump straight to the matching rows.
• A composite index is used efficiently only when the query includes its leftmost column. Put equality columns first, then range columns.
• Indexes speed up reads but cost something on every write. Add them for frequent filters, joins, and foreign keys, and use EXPLAIN ANALYZE and pg_stat_user_indexes to confirm they’re used.

References

YouTube

• Engineering Digest
• Smart Postgres: Fundamentals of Selects
• Laiture: Database Indexing for Dumb Developers

Articles

• Medium: Understanding PostgreSQL’s “ctid”: A Hidden Gem for Efficient Row Updates 💎
• Postgres CTID Scanning for Faster Backfills
• Database Indexing: How It Works, Types, and When to Use It
• Vikulin-va: PostgreSQL Composite Indexes and the Leftmost Prefix Rule
• Medium: How SQL Composite Indexes Work: The Leftmost Prefix Rule and B-Tree Insights