Feature Request: Seek/Keyset Pagination

JetFault commented 9 years ago

This is a feature request to add keyset/seek pagination. So instead of Offsets, which are slower and face problems with duplicates (if you add a new row) or missing items (if you delete a row), provide an 'after' criteria.

Similar to Reddit and Product Hunt

Relevant Threads:

In article [1], they mention some libs that implement this.

dmarcelino commented 9 years ago

The first article is a good reading source for this feature and the feature sounds reasonable. :+1:

@JetFault, would you like to volunteer to implement this? :smiley:

randallmeeker commented 9 years ago

It is important to note that Limit & Skip simply transpose those values to specific arguments on the adapter. This SEEK method (and I think it is a very, very good one) is more complicated in that it has to work on a set of sort criteria and needs to have advance knowledge of a specific values in order to jump to a specific page. Meaning you can't just say, {seek: 10} in order to go to page 10, but you would need to specify the criteria of the row that came on the last line of page 9. It would require a new complex object specified on find(), something like

seek:{
   page:10,
   criteria:[
   {field: 'id', order: 'desc', lastValue:55}
   ]
}

This would then have to override anything in the sort and extend any criteria sent to the find method with the criteria in the seek method. Without the criteria specified then the system would/could still have to have to fallback on offset. This would happen if someones initial visit to the data request was for page 10.

I think this would require a pagination library that can be implemented based on a trigger in the find and then passed back with the array returned by FindAll so that I can be attached to local scope or passed back with an AJAX call. Which, although an interesting idea, is way different from how Sails/Waterline works. Currently waterline is very decoupled and it would be hard to have it passback anything other than an array or object.

Since this this is more of a methodology and less of a transposition of actual database features, this might be a better candidate to write into BluePrints which is why you have seen the same thing when it comes to basic pagination. Basic pagination helpers have been written by different people (including myself) into custom blueprints.

Currently there is nothing stopping anyone from using this method currently in waterline. It just requires understanding how it works and then implementing the correct search, sort and limit procedures. However I think it would require a lot of discussion how it would make it into waterline.

Thank you @JetFault for the articles as I'm easily going to start using this methodology!!!

JetFault commented 9 years ago

@dmarcelino Unfortunately, I have negative time right now :( I looked a bit at how waterline does where queries as this is just an extension of where queries, but resorted to native queries (it would be nice if these had a more knex-like binding but that's another topic).

And as @randallmeeker said, these can be done using Waterline right now by just adding to the where. The only reason I chose to go with raw queries is to take advantage of Postgres' SQL Row Values: WHERE (sale_date, sale_id) < (?, ?) ORDER BY sale_date DESC, sale_id DESC, which is faster than the workaround needed for other SQL DBs WHERE sale_date <= ? AND NOT (sale_date = ? AND sale_id >= ?) ORDER BY sale_date DESC, sale_id DESC. Which I think the Postgres adapter should handle if this ever gets in.

Options for how it should look

JOOQ

JOOQ adds a new keyword, seek, that lets you pass in the previous values and relates them to the orderBy.

DSL.using(configuration)
   .select(PLAYERS.PLAYER_ID,
           PLAYERS.FIRST_NAME,
           PLAYERS.LAST_NAME,
           PLAYERS.SCORE)
   .from(PLAYERS)
   .where(PLAYERS.GAME_ID.eq(42))
   .orderBy(PLAYERS.SCORE.desc(),
            PLAYERS.PLAYER_ID.asc())
   .seek(949, 15) // (!)
   .limit(10)
   .fetch();

It does some checking to make sure # arguments in seek === # args in orderBy and same types.

This seems like the easiest approach as all this would do is take the args from the seek and add a new where clause.

ActiveRecord Order_Query

This approach is closer to adding Model attributes and creating different sorting ways. So something this might look like on the Model:

seekOrder: {
  recentlyCreated: [
    'createdAt': 'desc',
    'id': 'desc'
  ],
  recentlyUpdated: [
    'updatedAt': 'desc'
  ] // If no unique key was used, auto add the primary key to this sort
}

A way to use it might look like this:

User.find({blah: 1}).seek('2015-03-31 16:40:38', 15).limit(10);

Where the two values passed in can be passed from query params.

@randallmeeker Regarding paging, I don't think this method should be used if you need arbitrary pages and is best used in infinite-scroll scenarios and cases where you need more "stable" pagination (e.g. lots of removes/creates or reshuffles of the sort). It even requires a bit more work to make it work for previous page (reversing the Order By and Where).

In regards if this should be in Sails vs Waterline, I think I agree that this should most likely be in sails. It can be similar to the paginate helper that just adds limit and skip. Seek can add orderBy (removing the previous one if there is one) and where. Although, I don't know if its possible right now to have two where clauses. So maybe some additions to check if there is a previous where and add an and where clause with the seeking method.

EDIT: You guys want me to make an Issue on Sails as well, or just keep it here for now?

randallmeeker commented 9 years ago

I like it. I think here is where the conversation should continue.

mikermcneil commented 9 years ago

Thanks for posting, @JetFault. I'm a repo bot-- nice to meet you!

It has been 60 days since there have been any updates or new comments on this page. If this issue has been resolved, feel free to disregard the rest of this message. On the other hand, if you are still waiting on a patch, please:

review our contribution guide to make sure this submission meets our criteria (only verified bugs with documented features, please; no questions, commentary, or bug reports about undocumented features or unofficial plugins)
create a new issue with the latest information, including updated version details with error messages, failing tests, and a link back to [the original issue](). This allows GitHub to automatically create a back-reference for future visitors arriving from search engines.

Thanks so much for your help!

balderdashy / sails