Module 4 · Indexes and Planning

B-Tree and Multicolumn Indexes

Lesson 10 of 30 14 min read Updated

PostgreSQL B-tree indexes are the default index type because they match common predicates: equality, ordered ranges, sorting, minimum and maximum lookup, uniqueness, and prefix searches with suitable operator classes. A multicolumn B-tree index stores more than one key per index tuple, so it can answer queries that constrain or order by a left-to-right sequence of columns. The outcome of this lesson is practical: given a workload, you should be able to choose a useful column order, predict when the planner can use the index, read the evidence in EXPLAIN, and recognize when an index is extra write cost with little read benefit.

This fits the Indexes and Planning section of the PostgreSQL course because indexes are not hints. They are persistent data structures that the planner may choose when their estimated cost beats alternatives. The important skill is connecting logical query shape to physical access: which rows can be reached directly, which rows still need filtering, and whether the index already delivers the requested order.

B-tree Internals

A PostgreSQL B-tree is a balanced tree of pages. Internal pages guide the search; leaf pages hold sorted index entries that point to table tuples. The index is ordered by the indexed key values according to the operator class for each column. For a simple btree index on customer_id, equal customer IDs are adjacent. For a multicolumn index on (customer_id, created_at), entries are sorted first by customer_id, and within each customer by created_at. That lexicographic ordering is the central rule.

Each leaf entry contains the indexed values and a tuple identifier pointing to the heap table. With multiversion concurrency control, an index entry may point to a tuple version that is invisible to the current transaction, so a normal index scan may visit the heap to check visibility and retrieve non-indexed columns. An index-only scan can avoid heap fetches only when all required columns are in the index and the visibility map says the relevant heap page is all-visible. This is why a query can use an index and still be slow: the scan path may involve many random heap visits.

B-tree pages split as new values are inserted. Sequentially increasing keys, such as timestamps or identity values, tend to insert near the right edge; random keys distribute writes across the tree. PostgreSQL also stores duplicate B-tree entries efficiently in many cases, but duplicate-heavy indexes can still be large and can still make writes more expensive. Every insert, update of indexed columns, and delete must maintain each affected index.

Syntax Anatomy

The basic form is CREATE INDEX name ON table USING btree (column1, column2). Because B-tree is the default, USING btree is often omitted. Each column can include direction and null positioning, such as created_at DESC NULLS LAST. Direction matters mainly when the index is expected to satisfy ORDER BY; PostgreSQL can scan a B-tree forward or backward, but mixed directions across columns may require an index that matches the requested ordering.

Column order is a design decision, not decoration. Equality predicates on leading columns are strongest. A range condition on the first unconstrained column can still use the index, but columns after that range usually cannot narrow the scan in the same direct way. They may be checked in the index, but they do not define a tighter contiguous slice of the tree. This is often called the leftmost-prefix rule.

Useful additions include UNIQUE for enforcing uniqueness, INCLUDE columns for covering queries without making those columns part of the sort key, and partial indexes with a WHERE clause. A partial multicolumn index is especially effective when most queries target a stable subset, such as active orders or unarchived messages.

Example Data

The examples use a small orders table. It is intentionally simple: enough data shape to demonstrate equality, range, order, and covering behavior without hiding the mechanism behind application code.

DROP TABLE IF EXISTS lesson_orders;
CREATE TABLE lesson_orders (
    id bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
    customer_id integer NOT NULL,
    status text NOT NULL,
    created_at timestamptz NOT NULL,
    total_cents integer NOT NULL,
    note text
);

INSERT INTO lesson_orders (customer_id, status, created_at, total_cents, note) VALUES
    (7, 'paid', '2026-01-02 10:00+00', 4200, 'first'),
    (7, 'paid', '2026-01-04 11:00+00', 5100, 'second'),
    (7, 'open', '2026-01-05 09:00+00', 1800, 'cart'),
    (8, 'paid', '2026-01-03 12:00+00', 9900, 'gift'),
    (8, 'cancelled', '2026-01-06 08:00+00', 2500, 'void'),
    (9, 'open', '2026-01-07 14:00+00', 3300, 'new');

ANALYZE lesson_orders;

This setup has six rows. On such a tiny table the planner may prefer a sequential scan because reading the whole table is cheaper than using an index. That is not a failure. The examples teach access rules; the lab later shows how to inspect plans with larger synthetic data.

Example 1: Leading Equality

Create an index whose first column is the most important equality filter. The second column provides useful order within that customer.

CREATE INDEX lesson_orders_customer_created_idx
    ON lesson_orders (customer_id, created_at DESC);

SELECT id, customer_id, created_at::date AS order_date
FROM lesson_orders
WHERE customer_id = 7
ORDER BY created_at DESC;

The deterministic result is customer 7’s three orders, newest first: January 5, January 4, then January 2 of 2026. The index can seek to the contiguous region where customer_id = 7 and scan that region in created_at DESC order. For a large table, this can avoid both scanning unrelated customers and sorting the matching rows.

Example 2: Range Stops the Prefix

Now consider a query with equality on the first column and a range on the second column. This is still a good use of the same index.

SELECT id, customer_id, created_at::date AS order_date
FROM lesson_orders
WHERE customer_id = 7
  AND created_at >= '2026-01-04 00:00+00'
ORDER BY created_at DESC;

The result is two rows for customer 7: January 5 and January 4. The tree can jump to customer 7 and then scan only the portion of that customer’s ordered entries that satisfy the timestamp range. If a third indexed column existed after created_at, for example (customer_id, created_at, status), a predicate on status would usually be a filter after the timestamp range rather than an additional seek boundary. The range condition breaks the simple left-to-right narrowing.

Example 3: Wrong Column Order

Suppose most queries search for a customer first, but the index is defined with status first. That index may help status-heavy reports but is poorly shaped for customer lookup.

CREATE INDEX lesson_orders_status_created_idx
    ON lesson_orders (status, created_at DESC);

EXPLAIN (COSTS OFF)
SELECT id, created_at
FROM lesson_orders
WHERE customer_id = 7
ORDER BY created_at DESC;

The planner cannot use lesson_orders_status_created_idx to directly seek to customer_id = 7, because customer_id is not a leading key. It might still choose another index, sort after scanning, or scan the table. The symptom in a real plan is a large number of rows removed by filter or an explicit Sort node where you expected ordered index access. The correction is to build the index around the query’s leading equality predicates, such as (customer_id, created_at DESC).

Example 4: Covering a Read Path

A B-tree key should not become a dumping ground for every selected column. If a query needs a few extra columns but those columns are not part of search or order semantics, use INCLUDE.

CREATE INDEX lesson_orders_covering_idx
    ON lesson_orders (customer_id, created_at DESC)
    INCLUDE (status, total_cents);

SELECT status, total_cents
FROM lesson_orders
WHERE customer_id = 8
ORDER BY created_at DESC;

The result is customer 8’s rows ordered by date: cancelled with 2500 cents, then paid with 9900 cents. The included columns are stored in the index entry but do not participate in ordering. On a well-vacuumed table where the visibility map allows it, this shape can enable an index-only scan for this query. The trade-off is index size: included columns make each index entry wider and can reduce cache efficiency.

Design Choices and Trade-offs

Start with the workload, not the table. A multicolumn index is good when queries repeatedly constrain the same leading columns and often need the same trailing order. A common pattern is tenant or account ID first, then a timestamp or sequence number. Another is a categorical equality column first only when that category is selective enough or always paired with another selective leading column.

Do not automatically create both (a, b) and (b, a). They support different access paths and each adds write cost, disk use, vacuum work, and planning choices. Prefer one index that matches the most valuable query family. Add a second only when evidence shows a separate high-value access pattern.

Low-cardinality leading columns are often weak. An index on (status, created_at) where status has only open, paid, and cancelled may still scan a large fraction of the table. It can be excellent for WHERE status = 'open' ORDER BY created_at if open rows are a small active queue, but poor if each status contains millions of rows and reports read broad ranges anyway.

Partial indexes can reduce that cost. For example, an application that frequently lists open orders may prefer ON orders (created_at DESC) WHERE status = 'open' over a full (status, created_at) index. The planner can use the partial index only when the query predicate implies the partial predicate.

Troubleshooting

Symptom: the query ignores the new index. Likely causes: the table is small, statistics are stale, the predicate does not match the leading column order, the partial-index predicate is not implied, or the planner estimates too many heap visits. Diagnostics: run ANALYZE, inspect EXPLAIN (ANALYZE, BUFFERS), compare estimated rows with actual rows, and check pg_indexes for the real definition. Correction: update statistics, rewrite the predicate to match the intended condition, or replace the index with one that matches the actual access path.

Symptom: an index scan is chosen but latency is still high. Likely causes: the scan matches too many rows, returns to the heap for many tuple visibility checks, or reads scattered heap pages. Diagnostics: look for high shared read counts, high heap fetches on an index-only scan, and many rows removed by filter. Correction: narrow the leading predicates, add only useful covering columns, vacuum so all-visible pages can be marked, or accept a sequential scan for broad reports.

Symptom: writes slow down after adding indexes. Likely cause: each write now maintains more B-tree pages, and updates to indexed columns create new index entries. Diagnostics: compare insert or update timing before and after, inspect index sizes with pg_relation_size, and review unused indexes with statistics views over a representative period. Correction: drop redundant indexes, consolidate overlapping indexes only when semantics match, and avoid indexing columns that are not part of valuable predicates, joins, uniqueness, or ordering.

Performance and Reliability Implications

Indexes improve read paths by reducing scanned rows or avoiding sorts, but they are not free. Large indexes compete for cache with table pages and other indexes. Extra indexes increase write amplification and can lengthen maintenance operations. Use CREATE INDEX CONCURRENTLY for live systems when avoiding a blocking table write lock matters, but remember it takes longer, performs more work, and cannot run inside a transaction block. If a concurrent build fails, a leftover invalid index may need to be dropped.

Security is indirect but real. An index does not bypass row-level security or privileges, but it can change timing and resource usage. Avoid creating broad indexes that encourage unbounded exploratory queries on sensitive tables. For multi-tenant tables, tenant-leading indexes such as (tenant_id, created_at) often support both performance and operational isolation because ordinary tenant queries stay inside a smaller key range.

Hands-on Lab

Prerequisites: a PostgreSQL database where you can create and drop a table, plus permission to run EXPLAIN. Use a scratch schema, not production. The lab builds enough rows for the planner to have a meaningful choice.

  1. Create the lab table and populate it with generated orders.
  2. Run the baseline query with EXPLAIN (ANALYZE, BUFFERS) and note whether it sorts or scans the table.
  3. Create the multicolumn index and run ANALYZE.
  4. Run the same query again and verify that the plan can use the index for the customer filter and requested order.
  5. Clean up by dropping the table.
DROP TABLE IF EXISTS btree_lab_orders;
CREATE TABLE btree_lab_orders AS
SELECT
    gs AS id,
    (gs % 1000) AS customer_id,
    CASE WHEN gs % 5 = 0 THEN 'open' ELSE 'paid' END AS status,
    timestamptz '2026-01-01 00:00+00' + (gs || ' minutes')::interval AS created_at,
    (1000 + (gs % 9000)) AS total_cents
FROM generate_series(1, 200000) AS gs;

ANALYZE btree_lab_orders;

EXPLAIN (ANALYZE, BUFFERS)
SELECT id, created_at, total_cents
FROM btree_lab_orders
WHERE customer_id = 42
ORDER BY created_at DESC
LIMIT 10;

CREATE INDEX btree_lab_customer_created_idx
    ON btree_lab_orders (customer_id, created_at DESC)
    INCLUDE (total_cents);

ANALYZE btree_lab_orders;

EXPLAIN (ANALYZE, BUFFERS)
SELECT id, created_at, total_cents
FROM btree_lab_orders
WHERE customer_id = 42
ORDER BY created_at DESC
LIMIT 10;

DROP TABLE btree_lab_orders;

Verification is plan-based, not exact timing-based. Before the index, expect a plan that reads many rows and may sort the matching rows. After the index, expect an index scan or index-only scan using btree_lab_customer_created_idx, with the LIMIT satisfied from the newest entries for customer 42. If the table is cached, timing may vary; the important evidence is fewer rows scanned, no separate sort for the requested order, and buffers consistent with a narrower access path.

Assessment

  1. A table has queries shaped as WHERE tenant_id = ? AND status = ? ORDER BY created_at DESC LIMIT 50. Propose a multicolumn index and explain which predicates define the seek range and which column provides order.
  2. Why might (created_at, customer_id) be poor for WHERE customer_id = ? AND created_at > ?, even though both columns appear in the index?
  3. You added INCLUDE (payload) to support an index-only scan, but the index became much larger and plans did not improve. What diagnostics would you check before keeping or dropping it?
  4. A partial index on open orders is ignored by a query that uses WHERE status IN ('open', 'paid'). Explain why the planner cannot use that partial index as a complete substitute.
  5. Design a test that proves a new index removes a sort without relying on a specific execution time.

Summary

A PostgreSQL multicolumn B-tree index is a sorted, persistent access path over a left-to-right key. Equality on leading columns narrows the tree most effectively; a range condition narrows the next ordered slice; trailing columns are most valuable for ordering, covering, or filtering after the scan has been bounded. Good index design is therefore workload-specific. Choose column order from predicates and ORDER BY, measure with representative data, watch write and storage cost, and keep only indexes whose plans show real benefit.

Progress is saved in this browser.