Fast pagination in SQL

In this article, we will find out why LIMIT and OFFSET cannot be used to implement pagination and how to replace them.

During writing this article, I used PostgreSQL, so some SQL queries will work only for it (for example, a query with generate_series to fill a test table with data). However, all the pagination methods described below should work in any database.

Let's assume, that we have a chat with 1 million messages:

CREATE TABLE messages (id serial primary key, body text);
INSERT INTO messages (body) SELECT md5(random()::text) FROM generate_series(1,1000000);

Now we need to implement pagination so that the user loads messages in batches (100 messages in a batch) as the chat scrolls. This can be implemented in several ways.

Using LIMIT and OFFSET

The most popular way to implement pagination is to use LIMIT and OFFSET.

Let's try to get first 100 messages:

SELECT * FROM messages ORDER BY id ASC LIMIT 100;

 Limit  (cost=0.42..3.86 rows=100 width=37) (actual time=0.059..2.336 rows=100 loops=1)
   ->  Index Scan using messages_pkey on messages  (cost=0.42..34317.43 rows=1000000 width=37) (actual time=0.046..0.794 rows=100 loops=1)
 Planning Time: 0.072 ms
 Execution Time: 3.107 ms

As you can see, the query was executed in 3 ms. In the query plan, you can see that only 100 rows were scanned (Index Scan -> actual time -> rows=100). To execute the query, the B-tree index was used, which PostgreSQL creates automatically for all primary key columns.

Let's get the next 100 messages:

SELECT * FROM messages ORDER BY id ASC LIMIT 100 OFFSET 100;

 Limit  (cost=3.86..7.29 rows=100 width=37) (actual time=1.578..4.078 rows=100 loops=1)
   ->  Index Scan using messages_pkey on messages  (cost=0.42..34317.43 rows=1000000 width=37) (actual time=0.043..1.677 rows=200 loops=1)
 Planning Time: 0.051 ms
 Execution Time: 5.032 ms

The query was executed longer (5 ms). If you look at the query plan, you will notice that 200 rows have already been scanned.

Let's assume that the user scrolleed through 100000 messages (or automatically scrolled to the 100000th message when clicking on the link, which is quite realisctic) and loads the next 100 messages:

SELECT * FROM messages ORDER BY id ASC LIMIT 100 OFFSET 100000;

 Limit  (cost=3432.12..3435.56 rows=100 width=37) (actual time=1377.502..1379.512 rows=100 loops=1)
   ->  Index Scan using messages_pkey on messages  (cost=0.42..34317.43 rows=1000000 width=37) (actual time=0.046..712.494 rows=100100 loops=1)
 Planning Time: 0.127 ms
 Execution Time: 1380.311 ms

The query was executed in 1.3 sec. The number of scanned rows is 100100.

The problem with this approach is that the rows are always scanned from the beginning. At the beginning, we find the first row, scan and skip the OFFSET rows, and then scan and return the LIMIT rows. The larger the OFFSET, the more rows we need to scan, the longer query takes. As a result, each subsequent page will take longer and longer to load, because OFFSET + LIMIT rows will always be scanned to execute the query.

In practice, more complex queries are used, for which even with a small OFFSET, the execution speed becomes unacceptable. As a solution, you can set a limit on the maximum OFFSET (for example, 1000), but in this case the user will not be able to view more than OFFSET + LIMIT records.

Let's look at another problem. Let's get the last 5 messages:

SELECT * FROM messages ORDER BY id DESC LIMIT 5;

   id    |               body               
---------+----------------------------------
 1000000 | b35ebb4db40731d03b8b025cfe7adc19
  999999 | acfd591d18f38692f884d3afc6d5c979
  999998 | b22069d7485b2b4f8bed51a724718fee
  999997 | 17d76b8d7030485413c7458d15d0339d
  999996 | 3ff735c087295f3dc9b4c7323cda9457

Let's assume that the user started scrolling the list, and at that moment someone wrote a new message:

INSERT INTO messages (body) VALUES (md5(random()::text));

and after that, the user loads the next 5 messages:

SELECT * FROM messages ORDER BY id DESC LIMIT 5 OFFSET 5;

   id   |               body               
--------+----------------------------------
 999996 | 3ff735c087295f3dc9b4c7323cda9457
 999995 | e41cac0085cacf36e3fa1a3ad845a37d
 999994 | 068cbaadc0ab60f99e2284739c1061c8
 999993 | c3c53e27b7765ab7aa97268b3ca419e5
 999992 | d4d361538e8d1fe89316209c1d5185ea

As a result, the user received the same message twice (id=999996).

Using LIMIT and WHERE

The problem with the previous approach is that scanning rows always starts from the beginning. To solve this issue, we need to start scanning immediately from the specific row.

Let's get the first 5 messages:

SELECT * FROM messages ORDER BY id ASC LIMIT 5;

 id |               body               
----+----------------------------------
  1 | 7ca7a3f16457f5ec49ebf0cb6fabb52f
  2 | 30d67067325190ee3b922793efd7641e
  3 | 3e7b041658a1e5e29021c23498e9c870
  4 | 985ab7304175eb25a8b577df96baaa1e
  5 | a86c097cf8f341e859077f37cc65583b

When the next page is received by the user, not the page number will be sent, but the ID of the last row. In our example, the last row has id=5.

Let's get the next 5 messages:

SELECT * FROM messages WHERE id > 5 ORDER BY id ASC LIMIT 5;

 id |               body               
----+----------------------------------
  6 | fba0989cb6b59f81f8b0fc9844710005
  7 | 8eacebda19093d998d4a386c0f5e37d7
  8 | 456c1d71717ec23e47cf56a490aa77a6
  9 | 5c521635cd0ac8610178e4c5626b49d9
 10 | d7c4f563b55444499a16c5e675e5af66

The pagination works. Let's get 100 messages that follow after the 100000th.

SELECT * FROM messages WHERE id > 100000 ORDER BY id ASC LIMIT 100;

 Limit  (cost=0.42..4.11 rows=100 width=37) (actual time=0.090..2.790 rows=100 loops=1)
   ->  Index Scan using messages_pkey on messages  (cost=0.42..33203.93 rows=901743 width=37) (actual time=0.076..1.085 rows=100 loops=1)
         Index Cond: (id > 100000)
 Planning Time: 0.076 ms
 Execution Time: 3.723 ms

The query was executed in 3 ms (it takes about the same time to get the first page). When using OFFSET, the same query was executed in 1.3 sec. In the query plan, you can see that only 100 rows were scanned (Index Scan -> actual time -> rows=100), instead of 100100 rows when using OFFSET.

Since the column with id uses b-tree index, the first step is a quick search for the 100000th row, and then 100 next rows are scanned (this is due to the fact that in the b-tree index all the leaves of the tree [they contain references to rows] are connected by a bidirectional list).

Let's look at the problem that we had when adding a new row. Let's get the last 5 messages:

SELECT * FROM messages ORDER BY id DESC LIMIT 5;

   id    |               body               
---------+----------------------------------
 1000001 | 1fcaa624f42bc1851516b6f8f4e790cd
 1000000 | b35ebb4db40731d03b8b025cfe7adc19
  999999 | acfd591d18f38692f884d3afc6d5c979
  999998 | b22069d7485b2b4f8bed51a724718fee
  999997 | 17d76b8d7030485413c7458d15d0339d

add a new message:

INSERT INTO messages (body) VALUES (md5(random()::text));

and load the next page:

SELECT * FROM messages WHERE id < 999997 ORDER BY id DESC LIMIT 5;

   id   |               body               
--------+----------------------------------
 999996 | 3ff735c087295f3dc9b4c7323cda9457
 999995 | e41cac0085cacf36e3fa1a3ad845a37d
 999994 | 068cbaadc0ab60f99e2284739c1061c8
 999993 | c3c53e27b7765ab7aa97268b3ca419e5
 999992 | d4d361538e8d1fe89316209c1d5185ea

This time we received the row with id=999997 only 1 time.

Sorting by non-unique column

Let's create a table with products and fill it with data:

CREATE TABLE products (id serial primary key, name text, price int);

INSERT INTO products (name, price)
SELECT md5(random()::text), floor(random() * 1000) + 1
FROM generate_series(1,1000000);

Let's assume that we show the user products in ascending order by price. The price of products ranges from 1 to 1000.

At the beginning, let's look at the first 5 products:

SELECT * FROM products ORDER BY price ASC LIMIT 5;

  id  |               name               | price 
------+----------------------------------+-------
 3950 | e2af7265e17668e3b325608f3e2a5577 |     1
   70 | 3e2cd54660711330325abba843964780 |     1
 1561 | cf7deecf27ccfa0bcfff11862f86ac0f |     1
 3049 | d3158b4405d05aa8df6d6982eb1ee58e |     1
 4046 | 4d0fa7bbfbba435be18922e872e811a4 |     1

But how to load the next 5 products? If you do as follow:

SELECT * FROM products WHERE price > 1 ORDER BY price ASC LIMIT 5;

  id  |               name               | price 
------+----------------------------------+-------
 2093 | c11ba2e7237336d3e27021ffc4afcbfd |     2
 3556 | 4ccd277e9d3fe1493dfa3d451cbe1791 |     2
  770 | f5f6661726ae76c377f818fc1a2ea643 |     2
  898 | e9b5f5e0eddb4e29c713b30ce8ca001c |     2
 4243 | 60fd9a3c1fed481fad896ee3e0858c53 |     2

then in this case we will skip 984 other rows, which has price = 1, because the total number of these rows is 989.

SELECT COUNT(*) FROM products WHERE price = 1; -- 989

To solve this problem, it is also necessary to sort by some column with unique values that are supported by a b-tree index (or another index that supports more/less operators). For example, by the id column.

Let's create a new index for 2 columns: price and id. This index is needed to quickly execute queries in which these 2 columns are used in where.

CREATE INDEX products_price_id_idx ON products (price, id);

Let's get the first page:

SELECT * FROM products ORDER BY price ASC, id ASC LIMIT 5;

  id  |               name               | price 
------+----------------------------------+-------
   70 | 3e2cd54660711330325abba843964780 |     1
 1561 | cf7deecf27ccfa0bcfff11862f86ac0f |     1
 3049 | d3158b4405d05aa8df6d6982eb1ee58e |     1
 3950 | e2af7265e17668e3b325608f3e2a5577 |     1
 4046 | 4d0fa7bbfbba435be18922e872e811a4 |     1

The last row has price = 1 and id = 4096.

Let's get the next page:

-- Query for PostgreSQL
SELECT * FROM products
WHERE (price, id) > (1, 4046)
ORDER BY price ASC, id ASC
LIMIT 5;

-- Query for any database
SELECT * FROM products
WHERE price > 1 OR (price = 1 AND id > 4046)
ORDER BY price ASC, id ASC
LIMIT 5;

  id   |               name               | price 
-------+----------------------------------+-------
  5820 | 967db515852d6463f845749194f1a6ae |     1
  8388 | 2b11088f71918aae6920b6665d3c3544 |     1
  8821 | 489e2bfd77ba1f0fd5c37a50dc848e72 |     1
  9679 | fbc4f4e0ab73ec8bb05418a44f2a5917 |     1
 12252 | 89ab1cf6496e37cb4efa575e5d52d6aa |     1

The first 10 rows look like this:

SELECT * FROM products ORDER BY price ASC, id ASC LIMIT 10;

  id   |               name               | price 
-------+----------------------------------+-------
    70 | 3e2cd54660711330325abba843964780 |     1
  1561 | cf7deecf27ccfa0bcfff11862f86ac0f |     1
  3049 | d3158b4405d05aa8df6d6982eb1ee58e |     1
  3950 | e2af7265e17668e3b325608f3e2a5577 |     1
  4046 | 4d0fa7bbfbba435be18922e872e811a4 |     1
  5820 | 967db515852d6463f845749194f1a6ae |     1
  8388 | 2b11088f71918aae6920b6665d3c3544 |     1
  8821 | 489e2bfd77ba1f0fd5c37a50dc848e72 |     1
  9679 | fbc4f4e0ab73ec8bb05418a44f2a5917 |     1
 12252 | 89ab1cf6496e37cb4efa575e5d52d6aa |     1

Pagination works correctly.

Let's look at the plan and speed of query execution to get 5 next rows after the 100000th. At the beginning we will find the 100000th row:

SELECT * FROM products ORDER BY price ASC, id ASC LIMIT 1 OFFSET 100000;

  id   |               name               | price 
-------+----------------------------------+-------
 69113 | 17f845ab71b7cccc46333c2a5c33122d |   101

Let's look at the plan of the next query:

SELECT * FROM products
WHERE (price, id) > (101, 69113)
ORDER BY price ASC, id ASC
LIMIT 5;

 Limit  (cost=0.42..0.78 rows=5 width=41) (actual time=0.060..0.163 rows=5 loops=1)
   ->  Index Scan using products_price_id_idx on products  (cost=0.42..62991.89 rows=899098 width=41) (actual time=0.046..0.083 rows=5 loops=1)
         Index Cond: (ROW(price, id) > ROW(101, 69113))
 Planning Time: 0.070 ms
 Execution Time: 0.249 ms

The query was executed in 0.2 ms. 5 rows were scanned.

Using LIMIT + WHERE for pagination allows you to quickly load any page with results in the same time, because only LIMIT rows are always scanned. On the contrary, the selection of LIMIT + OFFSET rows with each next page is slower, because the larger the OFFSET, the more rows need to be scanned.

Cheat sheet

/* Pagination with sorting by unique column */

CREATE TABLE messages (id serial primary key, body text);

-- First 5 messages
SELECT * FROM messages ORDER BY id ASC LIMIT 5;

-- Next 5 messages
-- (the last message received has id = 5)
SELECT * FROM messages WHERE id > 5 ORDER BY id ASC LIMIT 5;

/* Pagination with sorting by non-unique column */

CREATE TABLE products (id serial primary key, name text, price int);
CREATE INDEX products_price_id_idx ON products (price, id);

-- First 5 products
SELECT * FROM products ORDER BY price ASC, id ASC LIMIT 5;

-- Next 5 products (for PostgreSQL)
-- (the last message received has price = 1, id = 4046)
SELECT * FROM products
WHERE (price, id) > (1, 4046)
ORDER BY price ASC, id ASC
LIMIT 5;

-- Next 5 products (for any database)
-- (the last message received has price = 1, id = 4046)
SELECT * FROM products
WHERE price > 1 OR (price = 1 AND id > 4046)
ORDER BY price ASC, id ASC
LIMIT 5; Limit  (cost=0.42..4.11 rows=100 width=37) (actual time=0.090..2.790 rows=100 loops=1)
   ->  Index Scan using messages_pkey on messages  (cost=0.42..33203.93 rows=901743 width=37) (actual time=0.076..1.085 rows=100 loops=1)
         Index Cond: (id > 100000)
 Planning Time: 0.076 ms
 Execution Time: 3.723 msINSERT INTO messages (body) VALUES (md5(random()::text));SELECT * FROM messages WHERE id < 999997 ORDER BY id DESC LIMIT 5;SELECT * FROM products ORDER BY price ASC LIMIT 5;SELECT * FROM products WHERE price > 1 ORDER BY price ASC LIMIT 5;