Efficient pagination for big tables

Using PostgreSQL 10.5. I'm trying to create a pagination system where the user can go back and forth between various of results.

In an attempt to not use OFFSET, I pass the id from the last row in the previous page in a parameter called p (prevId). I then select the first three rows whose id is higher than the number passed in the p parameter. (as described in this article)

For example, if the id for the last row in the previous page was 5, I'd select the first 3 rows with an id is higher than 5:

SELECT 
  id, 
  firstname, 
  lastname 
FROM 
  people 
WHERE 
  firstname = 'John'
  AND id > 5 
ORDER BY 
  ID ASC 
LIMIT 
  3;

This works great and the timing isn't very bad either:

Limit  (cost=0.00..3.37 rows=3 width=17) (actual time=0.046..0.117 rows=3 loops=1)
   ->  Seq Scan on people  (cost=0.00..4494.15 rows=4000 width=17) (actual time=0.044..0.114 rows=3 loops=1)
         Filter: ((id > 5) AND (firstname = 'John'::text))
         Rows Removed by Filter: 384
 Planning time: 0.148 ms
 Execution time: 0.147 ms

Although, if the user, on the other hand, would like to return to the previous page, things look a bit different:

First, I'd pass the id for the first row and then put minus sign in front of it to indicate that I should select the rows with an id that's less than (a positive) p parameter. Namely, if the id for the first row is 6, the p parameter would be -6. Similarly, my query would look like the following:

SELECT 
  * 
FROM 
  (
    SELECT 
      id, 
      firstname, 
      lastname 
    FROM 
      people 
    WHERE 
      firstname = 'John' 
      AND id < 6 
    ORDER BY 
      id DESC 
    LIMIT 
      3
  ) as d 
ORDER BY 
  id ASC;

In the query above, I first select the last 3 rows with an id that's less than 6 and then reverse them in order to present them in the same way as the first query described in the beginning.

This works as it should, but since the database is going through almost

The key to performance is a matching multicolumn index of the form:

CREATE UNIQUE INDEX ON people (firstname, id);

UNIQUE, since sort order can be ambiguous without it.

A UNIQUE or PRIMARY KEY constraint serves as well.

While the first column is checked for equality like in your example (or sorted in the same direction as the query), this index is good for paging up and down, slightly better for paging up.

With the index in place (and after running ANALYZE on the table), you won't see sequential scans any more (unless your table is small). The database is not "going through almost all your rows" any more.

Read the fine presentation by Markus Winand you are linking to.

If you want paging across more than one firstname, use ROW values. Example for paging down:

SELECT *
FROM  (
   SELECT id, firstname, lastname 
   FROM   people
   WHERE  (firstname, id) < ('John', 6)  -- ROW values!
   ORDER  BY firstname DESC, id DESC 
   LIMIT  3
   ) d 
ORDER BY firstname, id;

Related:

• Optimize query with OFFSET on large table

If the SELECT list only adds lastname like in your example, you might try to add that column to the index to get index-only scans out of it:

CREATE UNIQUE INDEX ON people (firstname, id, lastname);

Index expressions in this order.

In Postgres 11 consider INCLUDE columns instead, making the index slightly smaller and perform better, and applicable in more situations. Like:

CREATE UNIQUE INDEX ON people (firstname, id) INCLUDE (lastname);

StackExchange Database Administrators Q#219782, answer score: 13