Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Building APIs: A Comparison Between Cursor and Offset Pagination?

news.ycombinator.com

Post reply on HN
Print view View original

21–27 of 27 posts

Re: Building APIs: A Comparison Between Cursor and Offset Pagination?

#21

Post by slver »

inshadows wrote: post #18
slver wrote: post #7

Earlier quoted context omitted.

We can technically offer the users Nth page with cursors+offset hybrid, if we're fine with the computational demands (smaller than pure offset, but bigger than just prev|next|last). Let's say we want to offer the user 5 pages, 100 records per page: prev (7) | next (9) | 10 | 11 | 12 | 13 | 14 | ... | last If you click "13", you'd need to query with cursor for page 9 (i.e. id > last rec of page 8) , and offset 400 lim…

You can also just query 5*100 IDs (keysets actually) and insert them into temporary table, all in a single SQL query, retrieve 100 full records in 2nd query, and get cursors for next/prev pages in third query (I'm not sure about this part, would need some windowing query I guess). It may seem wasteful, but in my experience it's fast (though I don't really have "Big Data" to test on). I do something similar to check i…

It may be fast on its own, but I doubt it's faster than cursor+offset. Your idea is to materialize a slice starting from the cursor and offsetting within it. This means we still do offset, but without the cursor.

The thing is, the cursor is a lookup on an indexed sorted index, it's O(log N), it's effectively free already. And we add the cost of materializing the slice (if even just in memory), and introducing the potential of DoS-ing our server with this temporary state if we're not careful.

Re: Building APIs: A Comparison Between Cursor and Offset Pagination?

#22

Post by inshadows »

slver wrote: post #21
inshadows wrote: post #18

Earlier quoted context omitted.

You can also just query 5*100 IDs (keysets actually) and insert them into temporary table, all in a single SQL query, retrieve 100 full records in 2nd query, and get cursors for next/prev pages in third query (I'm not sure about this part, would need some windowing query I guess). It may seem wasteful, but in my experience it's fast (though I don't really have "Big Data" to test on). I do something similar to check i…

It may be fast on its own, but I doubt it's faster than cursor+offset. Your idea is to materialize a slice starting from the cursor and offsetting within it. This means we still do offset, but without the cursor. The thing is, the cursor is a lookup on an indexed sorted index, it's O(log N), it's effectively free already. And we add the cost of materializing the slice (if even just in memory), and introducing the pot…

I don't understand your point. I don't do any offset. I just pick 500 keys by cursor.

insert into temp select id, date from tbl where id >= c_id and date >= c_date order by date desc, id desc limit 500

I don't see doing any offset over the whole dataset.

> And we add the cost of materializing the slice (if even just in memory)

The alternative is to transfer 400 full rows of data that will be used just to compute pages.

> and introducing the potential of DoS-ing our server with this temporary state if we're not careful.

I don't see any DoS vector specific to this but I'd be thrilled to learn of one.

Re: Building APIs: A Comparison Between Cursor and Offset Pagination?

#23

Post by slver »

inshadows wrote: post #22
slver wrote: post #21

Earlier quoted context omitted.

It may be fast on its own, but I doubt it's faster than cursor+offset. Your idea is to materialize a slice starting from the cursor and offsetting within it. This means we still do offset, but without the cursor. The thing is, the cursor is a lookup on an indexed sorted index, it's O(log N), it's effectively free already. And we add the cost of materializing the slice (if even just in memory), and introducing the pot…

I don't understand your point. I don't do any offset. I just pick 500 keys by cursor. insert into temp select id, date from tbl where id >= c_id and date >= c_date order by date desc, id desc limit 500 I don't see doing any offset over the whole dataset. > And we add the cost of materializing the slice (if even just in memory) The alternative is to transfer 400 full rows of data that will be used just to compute page…

> I don't understand your point. I don't do any offset. I just pick 500 keys by cursor

So you pick 500 keys and put them into a temp table. Then what? You still have to show a page that's 100 of those 500 keys.

> The alternative is to transfer 400 full rows of data that will be used just to compute pages.

The alternative is the hybrid cursor+offset approach, which doesn't transfer 400 full rows of anything.

> I don't see any DoS vector specific to this but I'd be thrilled to learn of one.

I generate enough sessions to fill your RAM with temp tables.

Re: Building APIs: A Comparison Between Cursor and Offset Pagination?

#24

Post by inshadows »

slver wrote: post #23
inshadows wrote: post #22

Earlier quoted context omitted.

I don't understand your point. I don't do any offset. I just pick 500 keys by cursor. insert into temp select id, date from tbl where id >= c_id and date >= c_date order by date desc, id desc limit 500 I don't see doing any offset over the whole dataset. > And we add the cost of materializing the slice (if even just in memory) The alternative is to transfer 400 full rows of data that will be used just to compute page…

> I don't understand your point. I don't do any offset. I just pick 500 keys by cursor So you pick 500 keys and put them into a temp table. Then what? You still have to show a page that's 100 of those 500 keys. > The alternative is to transfer 400 full rows of data that will be used just to compute pages. The alternative is the hybrid cursor+offset approach, which doesn't transfer 400 full rows of anything. > I don't…

> Then what? You still have to show a page that's 100 of those 500 keys.

I don't need to use offset. I can use limit. And also, offset in 500 rows dataset never was a problem.

> I generate enough sessions to fill your RAM with temp tables.

o_O These tables contain only keys. In your approach you're going to have 500 keys in memory as well. Moreover, I'm not wasting resources by transferring them in my application. I'm in fact saving resources. You're making things up.

EDIT: Are you arguing about performance impact of scanning 500 rows vs 100 rows (though I don't understand your approach either, you're skipping - scanning - 400 rows as well)? The problem of paging is scanning whole dataset.

Re: Building APIs: A Comparison Between Cursor and Offset Pagination?

#25

Post by [deleted] »

inshadows wrote: post #24
slver wrote: post #23

Earlier quoted context omitted.

> I don't understand your point. I don't do any offset. I just pick 500 keys by cursor So you pick 500 keys and put them into a temp table. Then what? You still have to show a page that's 100 of those 500 keys. > The alternative is to transfer 400 full rows of data that will be used just to compute pages. The alternative is the hybrid cursor+offset approach, which doesn't transfer 400 full rows of anything. > I don't…

> Then what? You still have to show a page that's 100 of those 500 keys. I don't need to use offset. I can use limit. And also, offset in 500 rows dataset never was a problem. > I generate enough sessions to fill your RAM with temp tables. o_O These tables contain only keys. In your approach you're going to have 500 keys in memory as well. Moreover, I'm not wasting resources by transferring them in my application. I'…

[deleted]

Re: Building APIs: A Comparison Between Cursor and Offset Pagination?

#26

Post by slver »

inshadows wrote: post #24
slver wrote: post #23

Earlier quoted context omitted.

> I don't understand your point. I don't do any offset. I just pick 500 keys by cursor So you pick 500 keys and put them into a temp table. Then what? You still have to show a page that's 100 of those 500 keys. > The alternative is to transfer 400 full rows of data that will be used just to compute pages. The alternative is the hybrid cursor+offset approach, which doesn't transfer 400 full rows of anything. > I don't…

> Then what? You still have to show a page that's 100 of those 500 keys. I don't need to use offset. I can use limit. And also, offset in 500 rows dataset never was a problem. > I generate enough sessions to fill your RAM with temp tables. o_O These tables contain only keys. In your approach you're going to have 500 keys in memory as well. Moreover, I'm not wasting resources by transferring them in my application. I'…

I wrote a longer reply, but it buried the lead.

So let's focus on the main issue I spotted:

> In your approach you're going to have 500 keys in memory as well.

That's not true at all. At no point I have 500 of anything in memory. So there's some big misunderstanding here about what I propose (and hence how it compares with your alternative).

If you want to go over my original comments again and ask questions to understand the concept, I'm at your service.

Re: Building APIs: A Comparison Between Cursor and Offset Pagination?

#27

Post by slver »

inshadows wrote: post #24
slver wrote: post #23

Earlier quoted context omitted.

> I don't understand your point. I don't do any offset. I just pick 500 keys by cursor So you pick 500 keys and put them into a temp table. Then what? You still have to show a page that's 100 of those 500 keys. > The alternative is to transfer 400 full rows of data that will be used just to compute pages. The alternative is the hybrid cursor+offset approach, which doesn't transfer 400 full rows of anything. > I don't…

> Then what? You still have to show a page that's 100 of those 500 keys. I don't need to use offset. I can use limit. And also, offset in 500 rows dataset never was a problem. > I generate enough sessions to fill your RAM with temp tables. o_O These tables contain only keys. In your approach you're going to have 500 keys in memory as well. Moreover, I'm not wasting resources by transferring them in my application. I'…

> EDIT: Are you arguing about performance impact of scanning 500 rows vs 100 rows (though I don't understand your approach either, you're skipping - scanning - 400 rows as well)? The problem of paging is scanning whole dataset.

Cursor+offset doesn't scan the whole dataset, and saving subsets in temp tables doesn't improve on it (i.e. temp tables make things slower). But I'm not sure where we misunderstand each other.

1. You start at the cursor.

2. You offset at most 400 records from the cursor.

3. You read 100 records.

The first point means you don't scan the whole dataset. The second point means for the next 5 pages you offset max 400 records. The third point means you read nothing, except what you want to display immediately.

Post reply on HN