Efficient Pagination Using Deferred Joins | Hacker News Reader

Efficient Pagination Using Deferred Joins

aaronfrancis.com

70 pointsaarondf32 comments

Please don't do this.

1. If you are scanning the (clustered) primary key, this is no better than "normal" offset pagination. You need another index with a smaller record size, without all the ancillary fields of the PK, to make this have a benefit (since it'll read less data than reading the primary key).

2. It's still O(n^2) to page through n rows. Even if it's a constant factor better, it still doesn't scale well. Offset pagination works fine until it doesn't, and it'll fail spectacularly when it does.

3. You still get duplicated/missed elements in your response when things are added/removed with smaller keys than your current page.

I was curious how this method avoided the wall you will hit on scanning. Answer appears to be that it doesn't?

Yeah it doesn’t, the mistake is thinking the “select *” is the expensive bit, for limit 15 it’s cheap, it’s the offset 150000 that is expensive deferred or not.

Assuming a non-clustered index on FOO (and no predicate pushdown by an optimizer smarter than MySQL's), the first query will scan the index on FOO and perform 150000 seeks into clustered index (only to discard 149985 of them):

SELECT * FROM T ORDER BY FOO LIMIT 15 OFFSET 150000

But the following will just scan the index:

SELECT FOO FROM T ORDER BY FOO LIMIT 15 OFFSET 150000

yep its more complicated than my simple statement makes it out =)

i guess the core of the statement was that the net cost to the db is more tied to offset than select, yes they interact and 'select * with offset' is more expensive than 'select foo with offset', but its really the offset that is the problem. If you did keyset style pagination and still did 'select *' you'd be fine and roughly the same cost as 'select foo'.

It still scans the index, but it doesn't fetch those rows that will be discarded. After it reaches the right page, it fetches the rows themselves.

So it doesn't exactly avoid the wall, but it can push it considerably further away.

What's the alternative?

I hate pagination, nothing feels efficient to me. Fortunately, I've never worked on anything that required scale hehe..

I thought best practice was some form of key based pagination. If you must keep things in numbered pages and want to allow skipping to page x of y, then you are backed into a realized view that includes the page numbers in the data, at some level. You either build that on the fly every time you do a query, or you prebuild it.

(Note, I'm not positive my thought here is accurate.)

Cursor based pagination has advantages. You can actually skip records for other pages and you won't miss or duplicate records between pages.

But the drawback is you can't have directly addressable pages. So it's just a tradeoff per app.

Some apps do offset/limit and then simply limit the number of pages to something reasonable, which is a pretty viable solution too.

How is it n^2?

I can see how the DB would need to scan the index from the left side to arrive at the correct offset value O(n). But once it gets there, it should be able to load 15 rows from primary storage.

(FWIW in postgres the primary key index is a secondary index.)

I do agree that "deferred join" is no better than the first option in theory.

How does your point #3 work? It seems to assume the DB tries to guess how many rows are in a single page in order to implement OFFSET. This seems like an obvious bug that would be long fixed.

it's N^2 if the client is scanning through all the records.

With N records and page size P, with p=N/P pages: the client does list?page=1 then list?page=2 ... list?page=p. the server then does scans P records for the first client request, 2P for the second up to pP=N. The total record scanned is (1+2+...N/P)P = (1+N/P)(N/P)1/2*P ~ O(N^2)

It may not work in theory, but it works in practice!

I also mention cursor pagination, but that's not always an option for every app.

For uncached query, I just got a 10x speed improvement on this on an Informix 12.10 instance.

Will I might hesitate to deploy it in an app, because the index scan is still relatively heavy weight, I can certainly see myself using this for ad-hoc stuff, so thankyou.

You're welcome! Thanks for reporting back.

For a little more context, from High Performance MySQL, 3rd Edition (2012)

> This "deferred join" works because it lets the server examine as little data as possible in an index without accessing rows, and then, once the desired rows are found, join them against the full table to retrieve the other columns from the row.

From High Performance MySQL, 4th Edition (2021)

So I mean... it's not a crazy idea. Sometimes you just have to offer directly addressable pages in an application and can't get away with cursors, which are far better in certain circumstances.

I agree that you'll see no benefit if you were paginating PKs in the first place, but most app developers are paginating actual records, right?

This is written from the point of view of application developers. I'm sure that all the DBAs are skeptical right now, but when pages go from 30 seconds to 300 milliseconds [1] or 28 seconds to 2 seconds [2] that's kind of a win right?

[1] https://twitter.com/mdavis1982/status/1482429071288066054

[2] https://twitter.com/joecampo/status/1483550610028957701

> you'll see no benefit if you were paginating PKs in the first place, but most app developers are paginating actual records, right?

You are unclear on this point, but I don't really see how it addresses any of parent's (grogers) counterpoints. Maybe be a critical concept for you to reconsider! (I suspect application developers mainly use OFFSET/LIMIT because it's simple to implement and readily availability in SQL, rather than the optimal way for the user to accomplish their task.)

Putting aside the details of how to make it fast on MySql, I always push back on pagination designs that require direct addressing. Pages don't have any semantic meaning for the person clicking on them. Why would they click on page 17? They're not looking for specifically the 170th-179th results of whatever the query is. There are few cases where this is a useful UX and this is for roughly the same reason the DB is bad at it.

So my playbook here is to ask if direct addressing is really needed and then, when it isn't, switch to using cursors.

I actually agree completely with that!

Yes!

Additionally, it hurts users when the data is changing beneath them. Rows can appear twice or disappear as you move between pages.

As a user, I’d rather live with that possibility than not being able to jump to a page in random-access fashion.

As a user I like paged results when I sort by a key (maybe a timestamp) and want to look at the records around the one I found. However in a large dataset I always use a search filter.

As a developer without a specific requirement if the time is short (it always is) I create a paged navigation using the defaults of the framework I'm using. Then the customer might or might not ask for a search filter. If frameworks defaulted on search filters I'd give customers them first and paged navigation if requested.

OK, but how many pages is too many? I can understand what you're saying for say, 1 to 20 pages, but it doesn't make any sense to me to go to hundreds, or worse, thousands of pages.

What kind of cursor? Will be there any issue if the time the user waits between the first 10 items and the next time items is a couple hours?

Usually a cursor holds some state about the last record shown to a user on a particular page. The next page should always start directly after the previous one, no matter how much time has elapsed.

Most frameworks have some kind of cursor implementation. Laravel's docs do a good job describing theirs: https://laravel.com/docs/8.x/pagination#cursor-pagination

So what's the difference between that and using the id of the row like in the article?

When you use a cursor, the user has to pass a cursor back to the application to see the next page.

So on the first page load, the server will send the records and a cursor that contains the info {'lastId': 32} and when the user requests page two, they'll have to send the cursor {'lastId': 32} so the server knows where to start.

In practice, the cursors are usually encoded and appended to the URLs.

You can never calculate what page 2 should be, you have to know what the last item on page 1 was, because that dictates where to start on page 2.

When I look up something twice, having a “go to page” function is sorely lacking in modern apps. I want to flip to page 300, and they never do that anymore.

As a user, I often do something akin to a binary search when direct addressing is available. It can be annoying when it isn’t available, or when there’s not at least a shortcut to skip 10 or 50 pages, or to jump to the end of the search.

But you’re again, not actually using a page number here. What you really need is a different cursor, e.g. a cursor on created_at, to help perform the binary search more efficiently, right? A cursor doesn’t necessarily have to be an ID.

Well, what I do is to jump to a page at a certain ratio between two pages. Of course the UI could allow entering that ratio instead of selecting a numbered page, but I don’t quite see the benefit in that. The internal navigation can in principle be implemented either way (cursor or offset). One requirement is for the size of the result set to be known, at least as an approximation (e.g. like Google does).

I see people use this method all the time and I use it myself sometimes but it's 100% of the time a hack around the system not having filtering as far as I can tell.

I think this article could have done a better job explaining the underlining data structures, which would have then given the readers much better intuition why this can actually work, and when.

In a nutshell, a table can be:

- Heap-based: the rows are in the unordered "heap", with any number of indexes (B-trees) pointing to them physically (by holding the row's physical address).

- Or clustered (aka. index-organized): the rows are in a primary/clustered index (B-tree), with any number of secondary indexes (also B-trees) pointing to them logically (by holding the copy of the primary key).

Fetching a row through any index in a heap-based table, or any secondary index in a clustered table, requires a separate step: physical heap access in the former case, or a clustered index seek in the later.

So...

- if you are using a heap-based table,

- or using a clustered table where pagination order differs from the clustering order

...then it makes sense to avoid the price of fetching the entire row for those rows that you are going to discard anyway. You just scan the index that matches the pagination order until you reach the correct page, and only then start fetching the rows.

It's still "offset" pagination, but can be much faster in practice than the naive implementation (for later pages).

OTOH, if you are paginating in the clustering order, then there is no separate step for fetching the row, so this method would be unlikely to bring any benefit.

---

A DBMS with a decent query planner should be able to do this kind of optimization automatically, through "predicate pushdown". But it may still be a good idea not to rely on it and make things blindingly obvious to the planner by structuring the SQL as shown in the article.

---

BTW, "cursor pagination" is also known as "keyset pagination" or "seek method". Curiously, actual database cursors can be used for pagination, assuming very tight transactional coordination between client and server (and very nasty consequences if that's lacking), but that's different from the "cursor pagination" as mentioned in the article.

Reply on news.ycombinator.com