Case for Improved Costing for Index Only Scans?

Following is an example table that I’ll be referring to.

-- Creating a very basic table, index and running vacuum analyze
CREATE TABLE index_test AS (SELECT GENERATE_SERIES(1, 10000000)::int id, 'hello world' AS name);
CREATE INDEX on index_test;
VACUUM ANALYZE index_test;

-- SELECT statement
SELECT id FROM index_test WHERE id < [SOME VALUE];

So as a starting point, I wanted to identify when the cost for indexonly exceeds that of a sequential scan. In my case, the number turned out to be 6,243,354 with the table containing 10,000,000 tuples.

When the cost exceeds, the planner should select the more optimum path. However, my concern was why is the indexonly scan cost greater than that of sequential one. Turning on the timing, the expectation was that at the tipping point, indexonly execution time should be greater than that of sequential one. However, I see that indexonly scan’s execution was much much faster than the sequential scan. In terms of timing, this is what I expected. So I turned on the timing in psql and ran EXPLAIN ANALYZE. Following are the outputs.

-- SEQUENTIAL SCAN
EXPLAIN ANALYZE SELECT id FROM index_test WHERE id < 6243354;

                                                      QUERY PLAN                                                      
-----------------------------------------------------------------------------------------------------------------------
 Seq Scan on index_test  (cost=0.00..179053.25 rows=6227030 width=4) (actual time=0.175..993.291 rows=6243353 loops=1)
   Filter: (id < 6243354)
   Rows Removed by Filter: 3756647
 Planning Time: 0.235 ms
 Execution Time: 1149.590 ms
(5 rows)

Time: 1150.798 ms (00:01.151)
postgres=# explain analyze select id from index_test where id < 6243353;


-- INDEXONLY SCAN
EXPLAIN ANALYZE SELECT id FROM index_test WHERE id < 6243353;

                                                                      QUERY PLAN                                                                      
------------------------------------------------------------------------------------------------------------------------------------------------------
 Index Only Scan using index_test_id_idx on index_test  (cost=0.43..177277.44 rows=6227029 width=4) (actual time=0.063..718.390 rows=6243352 loops=1)
   Index Cond: (id < 6243353)
   Heap Fetches: 0
 Planning Time: 0.174 ms
 Execution Time: 873.070 ms
(5 rows)

Time: 874.079 ms

Given that this is a very well packed table, still you can see that the execution time increases from 718ms for indexonly scan to 993ms only with an increase of a single tuple just because the cost of indexonly scan goes beyond that of sequential scan.

I’ve tried this in a docker, my laptop and on a server without virtualization. All have shown similar gains.

Reviewing the costestimate function in cost_size.c, I see that the cost of indexonly differs for min_IO_cost and max_IO_cost. The indexTotalCost cost remains the same whether it’s an indexonly scan or not. I believe that total index cost in case of indexonly scan should also be updated.

I don't think there is a need to modify all amcostestimate functions for indexes, however, perhaps we can pull in another factor that helps make cost for indexonly more realistic.

ISTM, it should be reduced by a factor somewhere around (index size)/(relation size), even perhaps putting together expected index size, actual index size and relation size in some equation.
--