Select query with offset limit is too much slow

Question

I have read from internet resources that a query will be slow when the offset increases. But in my case I think its too much slow. I am using postgres 9.3

Here is the query (id is primary key):

select * from test_table offset 3900000 limit 100; 

It returns me data in around 10 seconds. And I think its too much slow. I have around 4 million records in table. Overall size of the database is 23GB.

Machine configuration:

RAM: 12 GB CPU: 2.30 GHz Core: 10 

Few values from postgresql.conf file which I have changed are as below. Others are default.

shared_buffers = 2048MB temp_buffers = 512MB work_mem = 1024MB maintenance_work_mem = 256MB dynamic_shared_memory_type = posix default_statistics_target = 10000 autovacuum = on enable_seqscan = off   ## its not making any effect as I can see from Analyze doing seq-scan 

Apart from these I have also tried by changing the values of random_page_cost = 2.0 and cpu_index_tuple_cost = 0.0005 and result is same.

Explain (analyze, buffers) result over the query is as below:

"Limit  (cost=10000443876.02..10000443887.40 rows=100 width=1034) (actual time=12793.975..12794.292 rows=100 loops=1)" "  Buffers: shared hit=26820 read=378984" "  ->  Seq Scan on test_table  (cost=10000000000.00..10000467477.70 rows=4107370 width=1034) (actual time=0.008..9036.776 rows=3900100 loops=1)" "        Buffers: shared hit=26820 read=378984" "Planning time: 0.136 ms" "Execution time: 12794.461 ms" 

How people around the world negotiates with this problem in postgres? Any alternate solution will be helpful for me as well.

UPDATE:: Adding order by id (tried with other indexed column as well) and here is the explain:

"Limit  (cost=506165.06..506178.04 rows=100 width=1034) (actual time=15691.132..15691.494 rows=100 loops=1)" "  Buffers: shared hit=110813 read=415344" "  ->  Index Scan using test_table_pkey on test_table  (cost=0.43..533078.74 rows=4107370 width=1034) (actual time=38.264..11535.005 rows=3900100 loops=1)" "        Buffers: shared hit=110813 read=415344" "Planning time: 0.219 ms" "Execution time: 15691.660 ms" 

Answer 1

It's slow because it needs to locate the top offset rows and scan the next 100. No amounts of optimization will change that when you're dealing with huge offsets.

This is because your query literally instruct the DB engine to visit lots of rows by using offset 3900000 -- that's 3.9M rows. Options to speed this up somewhat aren't many.

Super-fast RAM, SSDs, etc. will help. But you'll only gain by a constant factor in doing so, meaning it's merely kicking the can down the road until you reach a larger enough offset.

Ensuring the table fits in memory, with plenty more to spare will likewise help by a larger constant factor -- except the first time. But this may not be possible with a large enough table or index.

Ensuring you're doing index-only scans will work to an extent. (See velis' answer; it has a lot of merit.) The problem here is that, for all practical purposes, you can think of an index as a table storing a disk location and the indexed fields. (It's more optimized than that, but it's a reasonable first approximation.) With enough rows, you'll still be running into problems with a larger enough offset.

Trying to store and maintain the precise position of the rows is bound to be an expensive approach too.(This is suggested by e.g. benjist.) While technically feasible, it suffers from limitations similar to those that stem from using MPTT with a tree structure: you'll gain significantly on reads but will end up with excessive write times when a node is inserted, updated or removed in such a way that large chunks of the data needs to be updated alongside.

As is hopefully more clear, there isn't any real magic bullet when you're dealing with offsets this large. It's often better to look at alternative approaches.

If you're paginating based on the ID (or a date field, or any other indexable set of fields), a potential trick (used by blogspot, for instance) would be to make your query start at an arbitrary point in the index.

Put another way, instead of:

example.com?page_number=[huge] 

Do something like:

example.com?page_following=[huge] 

That way, you keep a trace of where you are in your index, and the query becomes very fast because it can head straight to the correct starting point without plowing through a gazillion rows:

select * from foo where ID > [huge] order by ID limit 100 

Naturally, you lose the ability to jump to e.g. page 3000. But give this some honest thought: when was the last time you jumped to a huge page number on a site instead of going straight for its monthly archives or using its search box?

If you're paginating but want to keep the page offset by any means, yet another approach is to forbid the use of larger page number. It's not silly: it's what Google is doing with search results. When running a search query, Google gives you an estimate number of results (you can get a reasonable number using explain), and then will allow you to brows the top few thousand results -- nothing more. Among other things, they do so for performance reasons -- precisely the one you're running into.