Composite Indexes and the Skip Problem

PostgreSQL 18 introduces skip scans, a performance feature that can dramatically speed up queries against composite btree indexes when the leading column has few distinct values. To understand why this matters, consider a table with two columns: one holding a handful of repeated values, and the other holding many unique values. A composite index on both columns resembles a sorted phone book—ordered first by the frequent column, then by the rare one.

This structure creates a familiar challenge. Suppose you need to find all rows where the rare column's value is below a threshold, say 10, but you have no constraint on the frequent column. A straightforward index scan must walk through every entry in the leading column, checking each rare value along the way. In PostgreSQL 17, this means scanning all the frequent entries even when none of their associated rare values meet the condition. The query below completes in 66 milliseconds, but most of that time is spent on unnecessary work:






1
2
3
4
5
6
7
8
9
10
11
12
13



test=> SET enable_seqscan = off;
SET
test=> EXPLAIN (ANALYZE) SELECT * FROM tab WHERE rare < 10;
                                 QUERY PLAN                                                                
═════════════════════════════════════════════════════════════════
 Index Only Scan using tab_frequent_rare_idx on tab  
    (cost=0.42..18481.42 rows=100 width=8) 
    (actual time=0.281..65.923 rows=100 loops=1)
   Index Cond: (rare < 10)
   Heap Fetches: 0
 Planning Time: 0.182 ms
 Execution Time: 66.011 ms
(5 rows)

This pattern is not exotic. Real-world examples include country, phone_number or car_maker, license_plate—situations where the first column is heavily repeated. The cost shows up as CPU usage and, with larger tables, disk I/O.

How Skip Scans Work

The underlying principle is simple: once the database finishes checking all rare values under one frequent value, it can leap directly to the next distinct frequent value instead of walking through every index entry.

Visually, a subset of the index structure looks like this:

How-B tree works

The scan algorithm changes from a linear probe to a skip-based traversal:

  • Find the first entry in the index.
  • Process all matching rare values.
  • Skip ahead to the next frequent entry and repeat.

Instead of exhaustively checking each combination, PostgreSQL can jump over the values that cannot possibly satisfy the query. The improvement is easy to measure in the same test:






1
2
3
4
5
6
7
8
9
10
11
12
13



pg18=> EXPLAIN (ANALYZE) SELECT * FROM tab WHERE rare < 10;
                   QUERY PLAN                                                               
════════════════════════════════════════════════════
 Index Only Scan using tab_frequent_rare_idx on tab  
     (cost=0.42..50.42 rows=100 width=8) 
     (actual time=0.238..0.580 rows=100.00 loops=1)
   Index Cond: (rare < 10)
   Heap Fetches: 0
   Index Searches: 11
   Buffers: shared hit=15 read=22
 Planning Time: 0.202 ms
 Execution Time: 0.648 ms
(7 rows)

Execution time drops from 66 milliseconds to just 0.6 milliseconds. This is a contrived example, but the same order-of-magnitude gains can appear in production when data distribution is favorable.

No Configuration Required

Skip scans are enabled by default in PostgreSQL 18. No user action or query rewrite is needed—the planner simply uses the technique when it detects a beneficial opportunity.

There are no known cases where the feature degrades performance. However, it only pays off when the leading index column has relatively few distinct values; otherwise, there is nothing to skip over. It also applies exclusively to btree indexes—GIN, GiST, and other index types are unaffected.