Indexes: structure, column order and cost

Time: 60.7 ms against 0.081 ms, median of 7 runs. Pages read predict time better than any other number in a plan.

Without an index Postgres reads every page. With one, it reads a few index pages, then one table page per matching row.

GiST also backs exclusion constraints (sheet T8). Trigram search needs the pg_trgm extension.

I use a B-tree unless the operator needs another type: GIN for arrays and JSONB, GiST for ranges, BRIN for huge append-only tables.

CREATE TABLE orders (
  id          bigint      PRIMARY KEY,
  customer_id int1         NOT NULL,
  status      text        NOT NULL,
  created_at  timestamptz2 NOT NULL,
  total_cents int         NOT NULL,
  email       text        NOT NULL,
  tags        text[]      NOT NULL
) WITH (autovacuum_enabled = off3);

table

1,000,000 rows, 12,508 pages of 8 kB, 98 MB

values

10,000 customers. Status: delivered 80%, shipped 10%, pending 5%, cancelled 4%, refunded 1%. One year of dates, in id order. The gift tag on 1% of rows.

indexes

(customer_id) 871 pages; two columns 3,853; with INCLUDE 4,954

I size an index against the table: here 1 million rows are 98 MB, and one integer index is 7 MB.

An index entry is the key plus a pointer to the row. The entries are sorted, so equal keys and ranges sit together; the rows they point to do not.

Plans, rows and pages are exact and the same on every run. Times are medians of 7 runs on a shared 8-core laptop, shown as bands. Settings: max_parallel_workers_per_gather = 0; jit = off; synchronize_seqscans = off; TimeZone = 'UTC'.

I read the plan: which scan, how many pages, whether it sorts. The right composite index turns a sort and 113 pages into 13 pages and no sort.

index_for(query):
  key = columns compared with =         // any order among them1
  IF the query sorts:
    key += the ORDER BY columns         // rows come out in order2
  key += ONE column compared with a range3
  include = other columns it selects    // an index-only scan4
  IF it always filters one value:
    index only those rows               // a partial index
  IF it wraps a column in a function:
    index the expression, not the column

check it:
  EXPLAIN (ANALYZE, BUFFERS) query
  read the pages, not only the time5

// The claims the sheet makes, checked on the recorded plans.
p := func(set, q string) []Node { return out.Plans[set+"|"+q] }
if s := scan(p("none", "customer")); s.Type != "Seq Scan" || s.Buffers != out.TablePages {
  t.Errorf("no index: %s over %d pages, want a Seq Scan over all %d", s.Type, s.Buffers, out.TablePages)
}
if !slices.ContainsFunc(p("single", "recent"), func(n Node) bool { return n.Type == "Sort" }) {
  t.Error("single-column index: the recent query should still sort")
}
if slices.ContainsFunc(p("composite", "recent"), func(n Node) bool { return n.Type == "Sort" }) {
  t.Error("composite index: the recent query should read in index order, with no sort")
}
if a, b := root(p("composite", "recent")).Buffers, root(p("single", "recent")).Buffers; a*5 > b {
  t.Errorf("composite: %d pages for the recent query, single: %d; want 5 times fewer", a, b)
}
if a, b := root(p("wrong-order", "recent")).Buffers, root(p("composite", "recent")).Buffers; a < 5*b {
  t.Errorf("wrong order: %d pages for the recent query, right order: %d; want 5 times more", a, b)
}
if a, b := root(p("wrong-order", "one-day")).Buffers, root(p("composite", "one-day")).Buffers; a*10 > b {
  t.Errorf("one day: %d pages with created_at first, %d with customer_id first; want 10 times fewer", a, b)
}
cov := scan(p("covering", "recent"))
if cov.Type != "Index Only Scan Backward" || !slices.Contains(cov.Detail, "Heap Fetches: 0") {
  t.Errorf("covering index: %s %v, want an index-only scan with no heap fetches", cov.Type, cov.Detail)
}

I put the equality columns first. Then the column the query sorts by or ranges over. One customer's recent orders become one run of entries, read backward.

Postgres gives me multi-column B-trees with INCLUDE, partial and expression indexes, GIN, GiST and BRIN, and EXPLAIN with page counts to check each one.

• 1% of rows can sit on 55% of the pages. Selectivity is about pages, not rows.
• BRIN stores a minimum and a maximum per 128 pages. It suits append-only tables and reads some extra pages per query.
• Keyset paging needs an index on the sort columns, with a unique column last to break ties.

An index helps when it cuts the pages read. A common value, a function on the column or a deep OFFSET can make it useless.

An index-only scan skips the table only for pages VACUUM marked all-visible. After heavy updates it visits the table again until the next VACUUM.

Each index is another B-tree insert on every write. I keep only the indexes a named query needs, and check idx_scan before I add more.

Queries a second per core is 1,000 divided by the measured time in ms for the "latest 10" query: 1,000 / 0.017 for the composite index. Network and connection costs come on top. Demand example: 500 order-history views a second, 10× at peak.

I start with the primary key and add one index per slow, named query. I move search and analytics to their own stores only when Postgres indexes cannot serve them.