At that time PostgreSQL didn't have an Index Skip Scan mechanism. To improve the performance of the original query, I had to rewrite it using a reursive CTE.
PostgreSQL 18, which was relased in 2025, has introduced B-tree Skip Scan into the core optimizer. This is a welcome performance improvement, particulary for queries that need to use a multi-column index without specifying a condition on its leading column.
In this note, I'll demonstrate how Index Skip Scan can improve SQL performance. I'll also revisit the query-rewriting technique that can be useful when you are working with PostgreSQL 17 or earlier versions.
I've used the following script to generate common data to showcase the performance improvement.
drop table if exists employee; create table employee ( empno int not null, ename character varying(10), job character varying(9), mgr int, hiredate timestamp, sal int, comm int, deptno numeric(2,0), sido_nm character varying(100) );
insert into employee select i, chr(65+mod(i,26))||i::text||'nm' ,case when mod(i,10000)=0 then 'president' when mod(i,1000) = 0 then 'manager' when mod(i,3)=0 then 'salesman' when mod(i,3)=1 then 'analyst' when mod(i,3)=2 then 'clerk' end as job ,case when mod(i,10000)= 0 then null when mod(i,1000)= 1 then 10000 when i >= 9000 then 1000 else ceiling((i+1000)/1000)*1000 end as mgr , '20240930'::date - i , trunc(random() * 10000) as sal , trunc(random() * 1000) as com , mod(i,12)+1 as deptno , case when mod(i,3) = 0 then 'jeonbuk' when mod(i,3) = 1 then 'kangwon' else 'chungnam' end as sido_nm from generate_series(1,10000) a(i);
CREATE TABLE sales ( sale_id numeric NOT NULL, employee_id numeric NOT NULL, subsidiary_id numeric NOT NULL, sale_date date NOT NULL, eur_value numeric(17,2) NOT NULL, product_id bigint NOT NULL, quantity integer NOT NULL, channel character varying(4) NOT NULL ); SELECT SETSEED(0);
INSERT INTO sales (sale_id , subsidiary_id, employee_id , sale_date, eur_value , product_id, quantity , CHANNEL) SELECT row_number() OVER (), data.* FROM ( SELECT gen % 100, e.empno , (CURRENT_DATE - CAST(RANDOM()*3650 AS NUMERIC) * INTERVAL '1 DAY') sale_date , CAST(RANDOM()*100000 AS NUMERIC)/100 eur_value , CAST(RANDOM()*25 AS NUMERIC) + 1 product_id , CAST(RANDOM()*5 AS NUMERIC) + 1 quantity , CASE WHEN GEN % 2 = 0 THEN 'ONLI' ELSE 'OFFL' END FROM employee e , GENERATE_SERIES(1, 180) gen ORDER BY sale_date ) data;
--gathering statistics. ANALYZE verbose sales;
--I used the following index to generate a common test case: CREATE INDEX sales_x01 ON sales USING btree (product_id, sale_date, eur_value);
-- Here are the statistics for the sales table and its index: select relname, relpages from pg_class where relname in ('sales','sales_x01'); relname |relpages| ---------+--------+ sales | 18557| sales_x01| 8925|
SELECT tablename, attname, n_distinct FROM PG_STATS WHERE TABLENAME='sales';
Notice that product_id has only 26 distinct values. This will become important later.
Below is the original query we have to investigate:
SELECT SALE_DATE, EUR_VALUE, EMPLOYEE_ID FROM SALES WHERE SALE_DATE = DATE '2021-03-29'
AND EUR_VALUE > 700;
Note that there is no condition on product_id, even though product_id is the leading column of the index we created earlier. This is exactly the type of situation where B-tree Skip Scan can be useful.
First, let's run the query on PostgreSQL 17. Here is the execution plan:
Index Scan using sales_x01 on sales (cost=0.43..27982.06 rows=148 width=15) (actual time=1.405..54.059 rows=161 loops=1) Index Cond: ((sale_date = '2021-03-29'::date) AND (eur_value > '700'::numeric)) Buffers: shared hit=14234 Planning Time: 0.077 ms Execution Time: 54.092 ms The planner chose an Index Scan.
The sales_x01 index contains 8925 blocks according to pg_class.relpages, while the table contains 18,557 blocks. In this particular test, the Index Scan touched 14,234 shared buffers in total. If the planner had chosen a seq scan, the scan would have had to process about 18,557 table pages.
On my server I've set random_page_cost to 1.1.
This relatively low value makes random I/O comparatively inexpensive and is one of the reasons the planner preferred the Index Scan over a Seq Scan(full table scan).
However, there is a significant problem here. PostgreSQL 17 does not have B-tree Skip Scan, so it had to visit all index blocks. It is safe to say that it scanned through 8925 index pages. To avoid this inefficiency, we have to rewrite the query so that PostgreSQL could explicitly supply the leading product_id column to the index scan.
Here is the rewritten query followed by its plan:
WITH RECURSIVE W AS ( SELECT MIN(PRODUCT_ID) AS PRODUCT_ID FROM SALES UNION ALL SELECT (SELECT MIN(PRODUCT_ID) FROM SALES A WHERE A.PRODUCT_ID > W.PRODUCT_ID) FROM W WHERE PRODUCT_ID IS NOT NULL ) SELECT SALE_DATE, EUR_VALUE, EMPLOYEE_ID FROM SALES WHERE PRODUCT_ID IN (SELECT PRODUCT_ID FROM W) AND SALE_DATE = DATE '2021-03-29' AND EUR_VALUE > 700;
Nested Loop (actual time=0.448..0.727 rows=161 loops=1) Buffers: shared hit=318 CTE w -> Recursive Union (actual time=0.038..0.403 rows=27 loops=1) Buffers: shared hit=107 -> Result (actual time=0.037..0.037 rows=1 loops=1) Buffers: shared hit=4 InitPlan 3 (returns $1) -> Limit (actual time=0.034..0.035 rows=1 loops=1) Buffers: shared hit=4 -> Index Only Scan using sales_x01 on sales sales_1 (actual time=0.034..0.034 rows=1 loops=1) Index Cond: (product_id IS NOT NULL) Heap Fetches: 0 Buffers: shared hit=4 -> WorkTable Scan on w w_1 (actual time=0.013..0.013 rows=1 loops=27) Filter: (product_id IS NOT NULL) Rows Removed by Filter: 0 Buffers: shared hit=103 SubPlan 2 -> Result (actual time=0.012..0.013 rows=1 loops=26) Buffers: shared hit=103 InitPlan 1 (returns $3) -> Limit (actual time=0.012..0.012 rows=1 loops=26) Buffers: shared hit=103 -> Index Only Scan using sales_x01 on sales a (actual time=0.011..0.011 rows=1 loops=26) Index Cond: ((product_id IS NOT NULL) AND (product_id > w_1.product_id)) Heap Fetches: 0 Buffers: shared hit=103 -> HashAggregate (actual time=0.433..0.439 rows=27 loops=1) Group Key: w.product_id Batches: 1 Memory Usage: 24kB Buffers: shared hit=107 -> CTE Scan on w (actual time=0.050..0.422 rows=27 loops=1) Buffers: shared hit=107 -> Index Scan using sales_x01 on sales (actual time=0.006..0.009 rows=6 loops=27) Index Cond: ((product_id = w.product_id) AND (sale_date = '2021-03-29'::date) AND (eur_value > '700'::numeric)) Buffers: shared hit=211 Planning: Buffers: shared hit=56 Planning Time: 0.461 ms Execution Time: 0.851 ms Note that the block I/O droppped from 14234 to 318. Here is the important part of the paln:
Nested Loop ├─ HashAggregate │ └─ CTE Scan on w │ └─ Index Scan using sales_x01 Index Cond: product_id = w.product_id AND sale_date = ... AND eur_value > 700 If you take a close look at the Index Scan node, the (product_id, sale_date, eur_value) column was used as its acces condition, which played a critical role in reduing the number of block I/O from 14234 to 318.
Let's run the original query on PostgreSQL 18 without rewriting it. Here is the execution plan:
Bitmap Heap Scan on sales (cost=121.20..679.38 rows=149 width=15) (actual time=0.114..0.136 rows=161.00 loops=1) Recheck Cond: ((sale_date = '2021-03-29'::date) AND (eur_value > '700'::numeric)) Heap Blocks: exact=6 Buffers: shared hit=90 -> Bitmap Index Scan on sales_x01 (cost=0.00..121.16 rows=149 width=0) (actual time=0.104..0.105 rows=161.00 loops=1) Index Cond: ((sale_date = '2021-03-29'::date) AND (eur_value > '700'::numeric)) Index Searches: 28 Buffers: shared hit=84 Planning Time: 0.072 ms
Execution Time: 0.154 ms
There is an interesting detail in the execution plan: Index Searches: 28
This indicates that PostgreSQL 18 performed multiple searches of the B-tree index rather than requiring the leading product_id column to appear explicitly in the query predicate. This is the key idea behind Index Skip Scan. Conceptually, PostgreSQL navigates the index as if it were performing searches such as:
Overall, it accessed only 84 pages on the index, and then it accessed 6 table pages.
Conclusion PostgreSQL 18's B-tree Skip Scan is a useful addtion to the optimizer. Before PostgreSQL 18, if you had an index such as:
(product_id, sale_date, eur_value)
and a query such as:
WHERE sale_date = ... AND eur_value > ...
the leading product_id column could prevent PostgreSQL from efficiently using the index.
One possible workaround was to rewrite the query and explicitly generate the distinct product_id values, as demonstrated with the recursive CTE above. With PostgreSQL 18, the optimizer can perform this kind of index navigation automatically through B-Tree Skip Scan.
Footnote With PostgreSQL 18, we are able to resue a well-designed multi-column index across more access patterns instead of creating a separate companion index for every possible column combination. Of course, the test case above is deliberately constructed, so the exact improvement should not be generalized to every workload.
