B-Tree Structure, Operator Classes, Sort Order, Multicolumn Rules, and Skip Scan

Learning outcomes

ServiceHub has reached the point where “add an index” is no longer a useful performance recommendation. Its work-order table supports equality lookups, tenant-scoped time ranges, recent-first queues, and occasional searches that constrain a later column but omit the leading column. A B-tree is PostgreSQL's default index access method because it supports ordered comparisons well, but the useful unit is not “column → index.” The useful unit is query operator + sort contract + data distribution + index key order + planner evidence.

1. Build a deterministic ServiceHub index lab

The lab creates 160,000 work-order observations. tenant_id has only eight distinct values; work_order_id is unique and highly selective; timestamps are monotonic with the generated sequence. This combination lets us reason about both conventional leading-key scans and PostgreSQL 18 skip scans.

DROP TABLE IF EXISTS app.ch10_btree_lab;CREATE TABLE app.ch10_btree_lab (    work_order_id bigint NOT NULL,    tenant_id integer NOT NULL,    status text NOT NULL,    priority smallint NOT NULL,    created_at timestamptz NOT NULL,    due_at timestamptz);INSERT INTO app.ch10_btree_labSELECT g,       (g % 8) + 1,       CASE g % 4 WHEN 0 THEN 'done' WHEN 1 THEN 'queued' WHEN 2 THEN 'assigned' ELSE 'cancelled' END,       (g % 5) + 1,       timestamptz '2026-01-01 00:00+00' + g * interval '20 seconds',       CASE WHEN g % 11 = 0 THEN NULL            ELSE timestamptz '2026-01-01 00:00+00' + g * interval '20 seconds' + interval '2 days' ENDFROM generate_series(1,160000) AS g;ANALYZE app.ch10_btree_lab;

Use ANALYZE before comparing plans. Otherwise you are evaluating the planner with poor cardinality evidence rather than evaluating the index design.

2. B-tree semantics come from operator classes

A PostgreSQL index access method is a framework. An operator class tells that method how one data type behaves for the method's strategies. For B-tree this normally means equality and ordered comparisons. Operator families group compatible classes and can define cross-type behavior. Collation can also change text ordering, so an index's comparison semantics are not merely its column data type.

SELECT am.amname,       opc.opcname,       opc.opcintype::regtype AS input_type,       opc.opcdefaultFROM pg_opclass AS opcJOIN pg_am AS am ON am.oid = opc.opcmethodWHERE am.amname = 'btree'  AND opc.opcintype IN ('text'::regtype, 'int4'::regtype, 'timestamptz'::regtype)ORDER BY input_type::text, opc.opcname;

The catalog query proves which classes are installed on this server; it does not prove which one a particular index uses. Inspect the index definition and attribute metadata too.

CREATE INDEX ch10_btree_tenant_created_idxON app.ch10_btree_lab    (tenant_id ASC, created_at DESC, work_order_id ASC);SELECT pg_get_indexdef('app.ch10_btree_tenant_created_idx'::regclass);

\d+ app.ch10_btree_lab

The \d+ line is a psql meta-command, not SQL. If you automate metadata checks in an application or migration test, use catalog queries such as pg_get_indexdef() rather than parsing psql's human display.

3. Filtering and ordering can be solved by the same index

For a tenant-specific recent-work query, equality on the leading key plus an ordered second key gives a compact index range and an order that can often satisfy ORDER BY directly.

EXPLAIN (ANALYZE, BUFFERS, WAL, SETTINGS)SELECT work_order_id, created_atFROM app.ch10_btree_labWHERE tenant_id = 3  AND created_at >= timestamptz '2026-01-20 00:00+00'ORDER BY created_at DESC, work_order_id ASCLIMIT 40;

On a typical local run, expect an Index Scan or Index Only Scan using ch10_btree_tenant_created_idx, with an Index Cond containing the tenant and timestamp constraints. Do not memorize a cost or elapsed time: cache state, hardware, statistics, visibility-map state, and PostgreSQL settings all affect the chosen plan.

A B-tree can scan forward or backward. However, mixed sort directions and NULL placement can make an explicitly ordered multicolumn index valuable when the workload requires an exact compound ordering.

CREATE INDEX ch10_btree_due_idxON app.ch10_btree_lab (tenant_id, due_at ASC NULLS LAST, work_order_id);EXPLAIN (ANALYZE, BUFFERS, SETTINGS)SELECT work_order_id, due_atFROM app.ch10_btree_labWHERE tenant_id = 6ORDER BY due_at ASC NULLS LAST, work_order_idLIMIT 30;

4. Multicolumn rules: what actually narrows the scan?

For a multicolumn B-tree, equality constraints on leading columns and an inequality on the first non-equality column reliably constrain the scanned index range. Conditions on later columns can still be applied at the index level and save heap visits, but historically they did not necessarily let PostgreSQL jump over large irrelevant index regions. PostgreSQL 18 adds skip scan, which can perform repeated searches by synthesizing equality constraints for omitted earlier columns when that is cost-effective.

SELECT attname, n_distinct, correlationFROM pg_statsWHERE schemaname = 'app'  AND tablename = 'ch10_btree_lab'  AND attname IN ('tenant_id','work_order_id','created_at')ORDER BY attname;

The leading tenant_id has very low cardinality in this dataset. That makes “repeat one search per tenant group” potentially cheaper than reading the entire index or heap.

5. PostgreSQL 18 skip scan: observe, do not assume

CREATE INDEX ch10_btree_skip_idxON app.ch10_btree_lab (tenant_id, work_order_id);ANALYZE app.ch10_btree_lab;EXPLAIN (ANALYZE, BUFFERS, SETTINGS)SELECT tenant_id, work_order_idFROM app.ch10_btree_labWHERE work_order_id = 98765;

On PostgreSQL 18, this query is a strong skip-scan candidate because the predicate is on the second index column and the first column has only eight values. When skip scan is used, EXPLAIN ANALYZE can report an Index Searches count greater than one. The node is still an index/index-only scan; there is no requirement for a plan node literally named “Skip Scan.”

Skip scan does not convert every poor column order into a good design. If the omitted leading key has thousands or millions of distinct values, repeated searches may approach scanning the whole index, and a dedicated later-column index can be a better portfolio choice.

6. Wrong approach: one wide index for every query

A learner may react to skip scan by creating (tenant_id,status,priority,created_at,work_order_id) and expecting it to replace all narrower indexes. That can increase storage and write work, hurt HOT opportunities when indexed columns are updated, and still fail to match the workload's operators/orderings.

SELECT indexrelid::regclass AS index_name,       pg_size_pretty(pg_relation_size(indexrelid)) AS size,       idx_scan, idx_tup_read, idx_tup_fetchFROM pg_stat_user_indexesWHERE relid = 'app.ch10_btree_lab'::regclassORDER BY pg_relation_size(indexrelid) DESC;

idx_scan = 0 is not a drop command. Statistics can have been reset, a reporting cycle may not have run yet, replicas may serve reads, and constraint indexes may protect correctness even if scans are rare. Lesson 5 turns these signals into an audit discipline.

7. Production judgment and cleanup

Choose B-tree key order from the highest-value query shapes, not from table-column order. Verify operator class/collation semantics, cardinality of leading keys, sort requirements, selectivity, update frequency, visibility conditions for index-only scans, and competing indexes. PostgreSQL 18 skip scan is an optimization opportunity—not a schema-design exemption.

DROP TABLE IF EXISTS app.ch10_btree_lab;

Authoritative references

Index behavior depends on PostgreSQL major version, operator class, collation, statistics, data distribution, visibility, and workload. Use the documentation for the exact major you operate.

• PostgreSQL 18 — Multicolumn Indexes
• PostgreSQL 18 — Indexes and ORDER BY
• PostgreSQL 18 — Operator Classes and Operator Families
• PostgreSQL 18 — Using EXPLAIN
• PostgreSQL 18 — Release Notes / Skip Scan