Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[SQL optimization] Use keyset pagination (a.k.a. seek method) #80

Open
BertrandBordage opened this issue Dec 9, 2014 · 0 comments
Open

Comments

@BertrandBordage
Copy link
Contributor

Current implementation uses QuerySet slicing, which translates into a LIMIT n OFFSET x in SQL.

The problem is that your database has to go through your entire table to select only a small quantity of rows. If your database contains thousands or millions of rows, this leads to far slower queries.

This can be solved using keyset pagination.

That would mean switching from qs[offset:limit] to qs.filter(**kwargs)[:limit] where kwargs is a dict created from the ORDER BY columns and their values in the previous page.

A Django implementation of this solution already exists. But it’s not using the ORM to discover which columns are ordering, and you can only order by one column, so it’s quite useless.

The columns in ORDER BY can be easily fetched using this:

q = qs.query
order_by = q.extra_order_by or (q.get_meta().ordering if q.default_ordering
                                else q.order_by) or []

Of course, the real challenge is to get data from the previous page. Unless we already asked for the previous page, we can’t get these data. In that "first query scenario", nothing special can be done, we have to use OFFSET. Otherwise, there are two solutions in my opinion:

  • pass these data in the template, so that the GET request of the next page contains data from the previous page (easy but less efficient)
  • save these data to the cache for each page, so that it’s saved from a session to another; this implies having to invalidate this cache after each modification (harder but more efficient)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant