Your index is being used. It's still slow.

An index on the right column doesn’t guarantee a fast query. I hit this on a 500k-row users table in Postgres: same index, same query shape, and one search was 700x faster than the other — with the “slow” one still technically using the index the whole time.

What an index actually is

An index is a separate data structure that lives alongside the table. It stores the indexed value(s) plus a pointer to the physical row. The table itself (the “heap”) stays in roughly insertion order — creating an index does not reorder the rows on disk. So there are always two things: the unsorted heap, and one-or-more sorted indexes pointing into it.

The setup

CREATE TABLE users (
  id         bigserial PRIMARY KEY,   -- auto-creates a unique B-tree on id
  last_name  varchar,
  first_name varchar,
  country    varchar,
  created_at timestamp NOT NULL DEFAULT now(),
  updated_at timestamp NOT NULL DEFAULT now()
);

500,000 rows, generated so first_name lands on about 20 distinct values — common names repeating across roughly 5% of the table each:

INSERT INTO users (last_name, first_name, country, created_at, updated_at)
SELECT
  'Last' || floor(random() * 5000)::int,          -- ~5000 distinct -> selective
  (ARRAY['Alice','Bob',/* ...20 names... */])[floor(random()*20)+1],  -- ~20 distinct -> NOT selective
  (ARRAY['US','UK','CA','AU','IE'])[floor(random()*5)+1],
  now(), now()
FROM generate_series(1, 500000);

ANALYZE users;  -- refresh stats so the planner isn't working from an empty-table picture

And the index every query below runs against — a plain, single-column B-tree, nothing composite:

CREATE INDEX index_users_on_first_name ON users (first_name);
-- No ANALYZE needed: plain-column index reuses existing column stats.

What the planner sees

The planner doesn’t count matches before running a query — it works from statistics ANALYZE collects into pg_stats. Here’s what that actually holds for this table:

SELECT attname, n_distinct, null_frac, avg_width,
       most_common_vals, most_common_freqs
FROM pg_stats
WHERE tablename = 'users'
ORDER BY attname;

n_distinct: -1 on id is Postgres’s way of saying “every value is unique, and the count scales with the table” rather than a fixed number. first_name at 20 and last_name at 5009 are the two numbers every row estimate in this post traces back to.

pg_stats also samples the actual most-common values per column. For first_name, all 20 names, each landing close to an even 1-in-20 share (rounded here from the raw fractions to percentages, values unchanged):

Alice — the name the first query below searches for — sits at 4.76%: the same ballpark as the ~25,000 actual matches that query returns.

What buys the win

This B-tree keeps its entries sorted. Because it’s sorted, Postgres can jump straight to matching entries instead of reading every row — but only if there aren’t too many matches to jump to.

For a query with thousands of matches, Postgres builds a Bitmap Heap Scan: read the index once to build a map of which 8 KB table pages hold a match, then visit those pages directly. For a query with a handful of matches, it skips the bitmap step and walks straight to the rows — a plain Index Scan.

Same index, two searches

Searching for a common name:

SELECT * FROM users WHERE first_name = 'Alice';

Bitmap Heap Scan on users (... rows=24367 ...) (actual ... rows=24982 loops=1)
  Heap Blocks: exact=4548        -- 4548 of ~4567 pages = touched 99.6% of the table!
  Execution Time: 19.327 ms      -- vs 29.7 ms seqscan = only ~1.5x

Heap Blocks: exact=4548 means the scan opened 4,548 of the table’s ~4,567 pages — 99.6% of it. The index is being used (that’s what a Bitmap Heap Scan is), but there’s nothing left for it to skip. 19.327 ms against a full sequential scan’s 29.7 ms is barely a win: the index bought about 1.5x on a column it was specifically built for.

Now the same index, same query shape, one rare value:

UPDATE users SET first_name = 'Zzrare' WHERE id <= 5;  -- 5 rows = 0.001%
ANALYZE users;   -- REQUIRED: data changed, and 5 rows is too few to trip autovacuum;
                 -- without it the planner still thinks 'Zzrare' matches ~25k rows

EXPLAIN ANALYZE SELECT * FROM users WHERE first_name = 'Zzrare';

Index Scan using index_users_on_first_name on users
      (cost=0.42..8.43 rows=1 width=40) (actual time=0.015..0.016 rows=5 loops=1)
  Index Cond: ((first_name)::text = 'Zzrare'::text)
  Buffers: shared hit=4           -- read only 4 pages total
  Execution Time: 0.027 ms        -- ~700x faster than the 'Alice' run on the SAME index

Buffers: shared hit=4 — four pages, total, to answer the query. Same index, same table, same column. The only thing that changed between the two runs is how many rows the searched value actually matches: 25,000 versus 5.

Rules of thumb

• Having an index ≠ benefiting from it. Don’t stop at whether the plan says Index Cond — check Heap Blocks or Buffers against the table’s total page count. If the scan is still touching nearly every page, the index isn’t doing much.
• A well-structured index only decides whether it can be used. Selectivity — what fraction of rows match — decides whether using it actually helps. The same index served both queries above; only one of them was fast.
• Re-run ANALYZE after any change to a value’s distribution, even a small one. Five changed rows won’t trip autovacuum’s own threshold, but the planner’s estimate is only as fresh as the last ANALYZE — without it, the planner in the second example would still think 'Zzrare' matches ~25,000 rows and pick the wrong plan for the data that’s actually there now.