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

We switched to cursor-based pagination

moderntreasury.com

Post reply on HN
Print view View original

51–60 of 118 posts

Re: We switched to cursor-based pagination

#51

Post by yrgulation »

jitl wrote: post #41
yrgulation wrote: post #40

Earlier quoted context omitted.

“It makes it near impossible to tune/optimize.” I recommend using elastic search or a nosql database to optimise performance. Relational databases can be slow for this use case.

What kind of NoSQL database are you thinking about? What strategy would you take with that database to optimize this problem?

This is hilarious - i am sharing my knowledge and getting downvoted for it.

Anyway, the gist of it is that you store data in denormalised documents whereby searchable columns become keys of a single entry. The storage is a secondary storage not the main data source. You write data in both - sync in your relational db, async via a queue or what works best for your infrastructure. Searches are then made against it. If you go for es you can rank results assuming filtering is done using free text search. I prefer es, the of flavour of nosql doesn't matter, but es is great for free text search.

Re: We switched to cursor-based pagination

#52

Post by simonw »

hamandcheese wrote: post #31

Cursor based pagination doesn’t actually solve the described pitfalls if your results are ordered by anything mutable, though. A result you haven’t yet seen can be mutated to sort before your current cursor, likewise a result that you’ve already seen can be mutated to sort after the current cursor, causing you to see it twice. Cursor based pagination does minimize the issue somewhat, because only the mutated rows are…

The only approach I can think of which might be able to handle mutability of the rows used for sorting would be to support paginating through a snapshot: provide a mechanism whereby a full snapshot of the query at a specific point in time is captured such that the user can then paginate through that snapshot.

Expensive to implement, so this would only work for situations where you can afford to spend significant storage and computation resources to keep a specific user happy.

Re: We switched to cursor-based pagination

#53

Post by simonw »

erikpukinskis wrote: post #47
simonw wrote: post #32

Earlier quoted context omitted.

My implementation of cursors works by encoding the primary ID of the last row on the page, along with additional information corresponding to the sort order if that's needed. That way it doesn't matter if the record is deleted - I can still return the next page by showing records that come after that provided cursor value. There's an example on this page: https://latest.datasette.io/fixtures/sortable?_sort=sortable S…

Interesting… what happens if new records are added with that 15 value? Do you need an implied secondary sort with the record created time? Also what if there are more than $page_size records with that 15 value?

Yes, if you want to support new records being added it's up to you to include something like a created date as part of your specified sort order.

More than page_size records with that value works fine - that's why the primary key is included as a tie-breaker.

Re: We switched to cursor-based pagination

#54

Post by jlg23 »

simonw wrote: post #36

This post is not about database cursors. It's about the style of pagination where you have a ?_next=xxx link to get to the next page, where the xxx bit encodes details about the last item on the current page such that the next page can show everything that comes after that record. This is also sometimes known as keyset pagination. My favourite technical explanation of that is here: https://use-the-index-luke.com/no-o…

This post is about "database cursors" and "keyset pagination". In practice, these terms refer to the same thing, one seen bottom-up the other seen top-down. Implementation-wise, one saves the state of the cursor in the pagination [parameters] and resumes reading from the DB with an equivalent cursor.

Re: We switched to cursor-based pagination

#55

Post by yrgulation »

nerdponx wrote: post #45
jitl wrote: post #41

Earlier quoted context omitted.

What kind of NoSQL database are you thinking about? What strategy would you take with that database to optimize this problem?

This sounds pretty typical for "analytics" workloads, which relational databases handle just fine. Maybe by "noSQL" they just meant something with column-oriented storage? But even that seems like it might be overkill, compared to setting up a couple of denormalized "analytics tables" to avoid the cost of complicated joins.

Yeah with all due respect but hacks like these are a bit amateurish. I heard of a dude i think at intuit building their queues in a relational db because they work “just fine”. Prompted a giggle or two. Use the right tool for the task at hand, dont do clever hacks as they bite back later on.

Re: We switched to cursor-based pagination

#56

Post by MatmaRex »

dinkledunk wrote: post #12
feike wrote: post #5

Reminds me of Markus Winand who hands out stickers on database conferences banning offset. His site is a great resource for anyone wanting to take a deeper dive on SQL performance: https://use-the-index-luke.com/sql/partial-results/fetch-nex...

how to jump to an arbitrary page?

You don't, but instead you can jump to an arbitrary place in the results. For example, you could show results starting from the letter P, or show results starting from 2022-04-02.

Re: We switched to cursor-based pagination

#57

Post by mikedouglas »

simonw wrote: post #52
hamandcheese wrote: post #31

Cursor based pagination doesn’t actually solve the described pitfalls if your results are ordered by anything mutable, though. A result you haven’t yet seen can be mutated to sort before your current cursor, likewise a result that you’ve already seen can be mutated to sort after the current cursor, causing you to see it twice. Cursor based pagination does minimize the issue somewhat, because only the mutated rows are…

The only approach I can think of which might be able to handle mutability of the rows used for sorting would be to support paginating through a snapshot: provide a mechanism whereby a full snapshot of the query at a specific point in time is captured such that the user can then paginate through that snapshot. Expensive to implement, so this would only work for situations where you can afford to spend significant stor…

This theoretically should be possible with MVCC, right? It's not an area I've explored and I could immediately see some issues with resource clean-up, but I could imagine it being possible with most modern DBs.

Re: We switched to cursor-based pagination

#58

Post by imbusy111 »

erikpukinskis wrote: post #44
imbusy111 wrote: post #22

Earlier quoted context omitted.

You probably assume they are talking about database cursors. The cursor is just a record ID in this article. There is no long term storage of database cursors on the server. Assuming you can sort all your data, next query just returns all records after the given record ID, plus the record with that ID. One corner case would be if the cursor record is deleted. I don't see it mentioned how they handle it.

Does that mean you have to scan the entire results set to get the right page? So if I am on page 100, I have to query pages 1-99 and discard them? Or is there a trick here I’m missing?

There are no pages anymore. You fetch a record by ID and next N records.

Re: We switched to cursor-based pagination

#59

Post by robertknight »

nemothekid wrote: post #48
fein wrote: post #18

I have a few main requirements for what I consider easy to use pagination. 1. I can set how many items per page. 2. I can get to an arbitrary page either through a path/ query param or at least close with a pagination row that contains a way to jump around. If an item gets removed, whatever I was looking for should still be in the same vicinity. 3. As a result of #1 and #2, I can go back and find items I saw previous…

> I can get to an arbitrary page either through a path/ query param or at least close with a pagination row that contains a way to jump around I've had quite a few heated discussions on this point. The problem is, once your dataset gets large enough, this use case is incredibly difficult to scale; not impossible (Google does it with millions of search results), but prohibitively expensive compared to how often the ne…

> Google does it with millions of search results

Google cheats, but in a way that very few users will notice. You can only access the first 20 pages of search results. Depending on user behavior, this is one way to offer navigation via page number while limiting worst-case cost.

Re: We switched to cursor-based pagination

#60

Post by jvolkman »

yrgulation wrote: post #55
nerdponx wrote: post #45

Earlier quoted context omitted.

This sounds pretty typical for "analytics" workloads, which relational databases handle just fine. Maybe by "noSQL" they just meant something with column-oriented storage? But even that seems like it might be overkill, compared to setting up a couple of denormalized "analytics tables" to avoid the cost of complicated joins.

Yeah with all due respect but hacks like these are a bit amateurish. I heard of a dude i think at intuit building their queues in a relational db because they work “just fine”. Prompted a giggle or two. Use the right tool for the task at hand, dont do clever hacks as they bite back later on.

"works just fine" might be a perfectly reasonable tradeoff if it avoids adding additional architectural complexity.
Post reply on HN