Hacker News new | ask | show | jobs
by huem0n 672 days ago
Good article, I do wish it would talked about big-O and arbitrary sort orders.

Let's say there's lots of columns/fields to sort by. Not quite an arbitrary sort (e.g. can't sort by area when given a width and height column) but its still pretty flexible. Is is possible to get a O(1) pagination while avoiding the rolling-shutter problem and deleted-anchor problem?

Getting around the deleted-anchor problem with ordered-ID's seems like just using ID's as a index. Not a bad trick, but seems like it isn't generalizable for all different kinds of sorts.
2 comments
JadedBlueEyes 672 days ago
Author here! This might be a case for one of the methods I missed, mentioned on the Reddit thread [0]. I've heard it called Cursor-based pagination or searchID-based pagination. The basic idea is you sort everything once and take a snapshot of the result. The user then gets an ID that refers to this snapshot. This often means that `next_page`/`previous_page` are opaque identifiers.

The tradeoff here is now you've got to keep that copy around - your server has to maintain some kind of state, you've got to garbage collect unused snapshots and it's impractical to scale this to millions of items.

[0]: https://old.reddit.com/r/programming/comments/1ev9hha/the_po...

link
kreig 672 days ago
One solution that we've been implementing in our APIs is the Seek Method (https://use-the-index-luke.com/sql/partial-results/fetch-nex...) which scales very well with large data sets in postgres, while avoiding some of the mentioned problems.
link