Large offset optimization and index only scan - Mailing list pgsql-hackers

Use IOS (index only scan) to skip the first OFFSET values than switch to common index scan to fetch LIMIT N values

Usage sample (from real life).. fully cached case:

Simple index-scan:
(postgres@[local]:5432) [hh_data]=# explain analyze select * from vacancy_invitation order by vacancy_invitation_id limit 10 offset 1000000;
                                                                                   QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=6997.98..6998.05 rows=10 width=953) (actual time=883.971..883.978 rows=10 loops=1)
   ->  Index Scan using vacancy_invitation_pkey_dblarge on vacancy_invitation  (cost=0.00..287399.74 rows=41068952 width=953) (actual time=0.011..845.592 rows=1000010 loops=1)
 Total runtime: 884.003 ms

Index only scan... 3x speedup:
(postgres@[local]:5432) [hh_data]=# explain analyze select vacancy_invitation_id from vacancy_invitation order by vacancy_invitation_id limit 10 offset 1000000;
                                                                                    QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=5546.48..5546.54 rows=10 width=4) (actual time=283.851..283.853 rows=10 loops=1)
   ->  Index Only Scan using vacancy_invitation_pkey_dblarge on vacancy_invitation  (cost=0.00..227788.13 rows=41068952 width=4) (actual time=0.013..246.477 rows=1000010 loops=1)
         Heap Fetches: 22
 Total runtime: 283.870 ms



Now lets combine fast IOS for skip first 1M records and simple index scan to fetch the next 10 full entries... still 3x speedup over initial version:
(postgres@[local]:5432) [hh_data]=# explain analyze select * from vacancy_invitation where vacancy_invitation_id>(select vacancy_invitation_id from vacancy_invitation order by vacancy_invitation_id limit 1 offset 1000000) order by vacancy_invitation_id limit 10;
                                                                                        QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=5546.49..5546.58 rows=10 width=953) (actual time=289.674..289.683 rows=10 loops=1)
   InitPlan 1 (returns $0)
     ->  Limit  (cost=5546.48..5546.49 rows=1 width=4) (actual time=289.654..289.654 rows=1 loops=1)
           ->  Index Only Scan using vacancy_invitation_pkey_dblarge on vacancy_invitation  (cost=0.00..227788.13 rows=41068952 width=4) (actual time=0.013..252.358 rows=1000001 loops=1)
                 Heap Fetches: 23
   ->  Index Scan using vacancy_invitation_pkey_dblarge on vacancy_invitation  (cost=0.00..123476.85 rows=13689651 width=953) (actual time=289.673..289.681 rows=10 loops=1)
         Index Cond: (vacancy_invitation_id > $0)
 Total runtime: 289.716 ms

As a result there is possible to have a 3x speedup large offset query if corresponding to order by index present.

In not fully cached case difference could be easy 100x (if index stayed in memory and table data not).