5 ms·

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 smal

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.

taeric 5y ago
I was curious how this method avoided the wall you will hit on scanning. Answer appears to be that it doesn't?
- nhoughto 5y ago
  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.
  - branko_d 5y ago
    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
    - nhoughto 5y ago
      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'.
- branko_d 5y ago
  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.
deburo 5y ago
What's the alternative? I hate pagination, nothing feels efficient to me. Fortunately, I've never worked on anything that required scale hehe..
- taeric 5y ago
  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.)
- aarondf 5y ago
  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.
srcreigh 5y ago
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.
- advisedwang 5y ago
  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)
aarondf 5y ago
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.
- TristanBall 5y ago
  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.
  - aarondf 5y ago
    You're welcome! Thanks for reporting back.
aarondf 5y ago
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) > 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. 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 https://twitter.com/mdavis1982/status/1482429071288066054 [2] https://twitter.com/joecampo/status/1483550610028957701 https://twitter.com/joecampo/status/1483550610028957701
- talaketu 5y ago
  > 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.)

taeric 5y ago

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

nhoughto 5y ago
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.
- branko_d 5y ago
  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
  - nhoughto 5y ago
    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'.
branko_d 5y ago
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.

deburo 5y ago

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

taeric 5y ago
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.)
aarondf 5y ago
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.

srcreigh 5y ago

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.

advisedwang 5y ago
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)

aarondf 5y ago

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.

TristanBall 5y ago
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.
- aarondf 5y ago
  You're welcome! Thanks for reporting back.

aarondf 5y ago

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) > 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. 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 https://twitter.com/mdavis1982/status/1482429071288066054 [2] https://twitter.com/joecampo/status/1483550610028957701 https://twitter.com/joecampo/status/1483550610028957701

talaketu 5y ago
> 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.)