Efficient pagination for big amount of data I need to be able to quickly (1-2 seconds) retrieve pages of 50,000 records from table that contains ~3,000,000 records. There's a UNIQUE index on a string primary key which contains values like '57133c4aea332cb17b001a28'.

string_id CHARACTER VARYING(255)

CREATE UNIQUE INDEX index_name ON users USING BTREE (string_id);

I've tried 

SELECT
   customer_id,
   string_id
FROM users
WHERE string_id &gt; '57133c4aea332cb17b001a28'
ORDER BY string_id
LIMIT 50000


but it has a very poor execution time:

Limit  (cost=0.11..48044.67 rows=50000 width=29)
  -&gt;  Index Scan using index_name on users  (cost=0.11..2799915.87 rows=2913874 width=29)
    Index Cond: ((string_id)::text &gt; '57133c4aea332cb17b001a28'::text)

Limit  (cost=0.11..48237.53 rows=50000 width=29) (actual time=0.561..25740.665 rows=50000 loops=1)
  -&gt;  Index Scan using index_name on users  (cost=0.11..2792079.10 rows=2894101 width=29) (actual time=0.560..25730.852 rows=50000 loops=1)
    Index Cond: ((string_id)::text &gt; '57133c4aea332cb17b001a28'::text)
Planning time: 0.364 ms
Execution time: 25747.091 ms


I'm using PostgreSQL 9.5.

Why is it so hard for DB to get 50,000 records using ordered index and what can I do to improve it?
If the 50,000 records are scattered all over the place, and it takes 4ms to fetch each one (15,000 rpm hard drive), it would take 200 seconds.  So 25 seconds is reasonable, since it is unlikely they will be scattered completely at random.

You can CLUSTER users on index_name which will reorder the table to be in the same order as the string_id.  But it won't automatically stay clustered as you do updates and more insertions.

You can add an index on (string_id, customer_id) and see if an index-only scan will solve your problem.