Introducing FastPage: Faster offset pagination for Rails apps

We'd like to introduce FastPage, a new gem for ActiveRecord that applies the MySQL "deferred join" optimization to your offset/limit queries.

Here is a slow pagination query in Rails:

Post.all.order(created_at: :desc).limit(25).offset(100)
# Post Load (1228.7ms)  SELECT `posts`.* FROM `posts` ORDER BY `posts`.`created_at` DESC LIMIT 25 OFFSET 100

We add .fast_page to the query and now it's 2.7x faster!

Post.all.order(created_at: :desc).limit(25).offset(100).fast_page
# Post Pluck (456.9ms)  SELECT `posts`.`id` FROM `posts` ORDER BY `posts`.`created_at` DESC LIMIT 25 OFFSET 100
# Post Load (0.4ms)  SELECT `posts`.* FROM `posts` WHERE `posts`.`id` IN (1271528, 1271527, 1271526, 1271525, 1271524, 1271523, 1271522, 1271521, 1271520, 1271519, 1271518, 1271517, 1271516, 1271515, 1271514, 1271512, 1271513, 1271511, 1271510, 1271509, 1271508, 1271507, 1271506, 1271505, 1271504) ORDER BY `posts`.`created_at` DESC

Benchmark

We wanted to see just how much faster using the deferred join could be. We took a table with about 1 million records in it and benchmarked the standard ActiveRecord offset/limit query vs the query with FastPage.

Here is the query:

AuditLogEvent.page(num).per(100).where(owner: org).order(created_at: :desc)

Both owner and created_at are indexed.

As you can see in the chart above, it's significantly faster the further into the table we paginate.

How this works

The most common form of pagination is implemented using LIMIT and OFFSET.

In this example, each page returns 50 blog posts. For the first page, we grab the first 50 posts. On the 2nd page we grab 100 posts and throw away the first 50. As the OFFSET increases, each additional page becomes more expensive for the database to serve.

-- Page 1
SELECT * FROM posts ORDER BY created_at DESC LIMIT 50;
-- Page 2
SELECT * FROM posts ORDER BY created_at DESC LIMIT 50 OFFSET 50;
-- Page 3
SELECT * FROM posts ORDER BY created_at DESC LIMIT 50 OFFSET 100;

This method of pagination works well until you have a large number of records. The later pages become very expensive to serve. Because of this, applications will often have to limit the maximum number of pages they allow users to view or swap to cursor based pagination.

Deferred join technique

High Performance MySQL recommends using a "deferred join" to increase the efficiency of LIMIT/OFFSET pagination for large tables.

SELECT * FROM posts
INNER JOIN(select id from posts ORDER BY created_at DESC LIMIT 50 OFFSET 10000)
AS lim USING(id);

Notice that we first select the ID of all the rows we want to show, then the data for those rows. This technique works "because it lets the server examine as little data as possible in an index without accessing rows."

The FastPage gem makes it easy to apply this optimization to any ActiveRecord::Relation using offset/limit.

To learn more on how this works, check out this blog post: Efficient Pagination Using Deferred Joins.

When should I use this?

fast_page works best on pagination queries that include an ORDER BY. It becomes more effective as the page number increases. You should test it on your application's data to see how it improves your query times.

Because fast_page runs 2 queries instead of 1, it is very likely a bit slower for early pages. The benefits begin as the user gets into deeper pages. It's worth testing to see at which page your application gets faster from using fast_page and only applying to your queries then.

posts = Post.all.page(params[:page]).per(25)
# Use fast page after page 5, improves query performance
posts = posts.fast_page if params[:page] > 5

Thank you ❤️

This gem was inspired by Hammerstone's fast-paginate for Laravel and @aarondfrancis's excellent blog post: Efficient Pagination Using Deferred Joins. We were so impressed with the results, we had to bring this to Rails as well.