A faster paginator for django

[Saleem Jaffer]

Hi all,

The default paginator that comes with Django is inefficient when dealing with large tables. This is because the final query for fetching pages uses "OFFSET" which is basically a linear scan till the last index of the current page. Does it make sense to have a better paginator which does not use "OFFSET". 

If this sounds like a good idea, I have some ideas on how to do it and with some help from you guys I can implement it.

Saleem

[ludovic coues]

The preferred way for this kind of scenario is to make a third party package. This let you release new version faster than the Django development cycle and it's super easy to install thanks to tools like pip.

Once your solution is stable, if it's popular enough, it could be incorporated into Django.

I'm really curious how you want to do it. I thought there was no other way to skip some row in an SQL query

--
You received this message because you are subscribed to the Google Groups "Django developers (Contributions to Django itself)" group.
To unsubscribe from this group and stop receiving emails from it, send an email to django-develop...@googlegroups.com.
To post to this group, send email to django-d...@googlegroups.com.
Visit this group at https://groups.google.com/group/django-developers.
To view this discussion on the web visit https://groups.google.com/d/msgid/django-developers/020f66e0-ec58-47e2-be0b-00c3f1688c5b%40googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Jason Johns]

https://www.citusdata.com/blog/2016/03/30/five-ways-to-paginate/ has some interesting alternatives.  I believe Django uses the first one. But the others have some tradeoffs that might not apply to all the dbs that django supports.

[Adam Johnson]

There are already some packages on listed on djangopackages that claim to implement different pagination strategies: https://djangopackages.org/grids/g/pagination/

On Wed, 5 Dec 2018 at 12:37, Jason Johns <jjohn...@gmail.com> wrote:

https://www.citusdata.com/blog/2016/03/30/five-ways-to-paginate/ has some interesting alternatives.  I believe Django uses the first one. But the others have some tradeoffs that might not apply to all the dbs that django supports.

--

You received this message because you are subscribed to the Google Groups "Django developers (Contributions to Django itself)" group.
To unsubscribe from this group and stop receiving emails from it, send an email to django-develop...@googlegroups.com.
To post to this group, send email to django-d...@googlegroups.com.
Visit this group at https://groups.google.com/group/django-developers.

To view this discussion on the web visit https://groups.google.com/d/msgid/django-developers/b649819f-80c3-4b12-af07-0914c679287a%40googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--

Adam

[Curtis Maloney]

There are a number of alternatives to this, as well as low-cost
solutions to improve OFFSET / LIMIT pagination.

By adding an index to the sorting field(s), it can drastically improve
the "simple" case.

Beyond that, you start getting into cases with more significant
trade-offs. I know Matthew Schinckel was recently working on a drop-in
replacement paginator that used "keyset pagination"
https://bitbucket.org/schinckel/django-keyset-pagination

There's a lot of published work on this topic, and I'd be very
interested to see, at least, a library implementing some of these
alternatives.

At the very least, we could want to ensure the documentation recommends
indexing on the ORDERing fields, where possible.

--
Curtis

[Josh Smeaton]

I think most people would typically sort/paginate on the primary key field, which still exhibits a linear scan, where 

the first few pages are fast and the last few pages take significantly longer. Just wanted to call that out in case there

were listeners thinking an index solves the problem. Sorting by an unindexed field just makes a bad query a horrible one.

[Kye Russell]

It might also be worth looking at the alternative pagination methods offered by Django REST Framework as a source of inspiration.

[Ivan Anishchuk]

Note: I'm only covering postgres here but the idea is pretty universal.

Good pagination starts with good sorting, so I'd suggest starting with having a good primary key. Integer PK could be enough, could be not quite (custom generator + postgres uuid field would be the next logical choice for me, something timestamp-based but small and fast in any case). I'd supplement that with a secondary id (modification/version id, exactly the same as pk but reset on every save). This way you can cover two most important sorting: by creation order and by modification order (you can even implement some simple data versioning if you use both as a composite pk but that's another story). Then, if you need sorting on other fields it would be extremely wise to create indices for every single sorting option (if the field you sort on is not unique, use index_together and pk and/or version id as the last field).

Now, having that, you can start with the actual pagination. Since you always sort by a unique keyset in this scheme, you should be able to paginate using greater than comparison and to make it generic enough let's assume you always sort/paginate by multiple fields (arbitrary number of them). You have to somehow pass the information about which fields you want to sort on and which keyset you want to compare with from client to server, you can invent your own weird way to do it but the best (I think) would be to use standard query filters and (multiple, if needed) order_by. "Cursor" pagination in Django Rest Framework, for example, is essentially this but supports only a single sorting field (cannot use unique keysets to supplement non-unique primary sorting fields) and for reason unknown encodes the filters to base64 bloating the size enormously. With this proposed scheme everything is transparent and flexible if just slightly verbose (you can always do something similar with base64 encoding or whatnot if you want it to become less transparent and longer). Your url would look kinda like this: /view/?order_by=slug&order_by=-id&slug_lt=some_title&id_lt=123&limit=50 (there could be less verbose options like ?o=-field1+field2-field3&k=+some_title&k=-123&l=50 but more urlsafe if you really care about a few bytes, but mostly just make your param names configurable and you should be fine) -- if you absolutely have to use non-unique keysets you can augment this by adding optional offset (small offset with any gt/lt is better than big offset and no filtering). Next, you need to calculate the next/previous pages from the current, there were some links above that explain it at length but basically to keep it stateless you should always query an extra item and use its value with >= for the next page and with < and reversed order for the previous.

Another beauty of keyset pagination is that it doesn't have to be exact. If an object was removed, comparisons will continue working. You can also trivially construct keysets for getting first and last pages (paginating back from the last would produce different pages but I don't think it matters that much in most real-life scenarios).

Keyset has a few disadvantages over page number, mainly no random page access. If you want to have it at the cost of slower queries, you can add optional offset (mentioned above) and run a count(*) query like page number paginator does (or perhaps run some faster estimation). Page number is just a shorter representation of limit-offset pagination when you now the total count, and combined with keyset it would still be much faster on long tables than just limit-offset (or page number).

This is roughly how I plan to implement it although I don't dream of building anything universal, I just want a small reusable module so I don't have to reimplement this in every project that needs it. If you ever release any code, feel free to ping me for review or testing, chances are I like your library and won't have to implement mine :) I have too many library ideas and not enough time to work on them all, collaboration could be much more better.

Ivan.

--

You received this message because you are subscribed to the Google Groups "Django developers (Contributions to Django itself)" group.
To unsubscribe from this group and stop receiving emails from it, send an email to django-develop...@googlegroups.com.
To post to this group, send email to django-d...@googlegroups.com.
Visit this group at https://groups.google.com/group/django-developers.

To view this discussion on the web visit https://groups.google.com/d/msgid/django-developers/020f66e0-ec58-47e2-be0b-00c3f1688c5b%40googlegroups.com.

[Cristiano Coelho]

Let's not forget how the various count calls starts to kill your database when you get over 1 million rows (postgres at least).

So far the only options I have found with postgres are:

- Estimate count for non filtered queries: SELECT reltuples::BIGINT FROM pg_class WHERE relname = '%s';

- If queries are filtered, replace it with a subquery that will first limit the results to a reasonable number (such as 1k), this is silly, and won't allow you to go through all results but at least the count call won't kill your database. This is only useful if the filtered query returns over one million rows as well.

[Tim Allen]

On Friday, December 21, 2018 at 10:18:04 AM UTC-5, Cristiano Coelho wrote:

Let's not forget how the various count calls starts to kill your database when you get over 1 million rows (postgres at least).

So far the only options I have found with postgres are:

- Estimate count for non filtered queries: SELECT reltuples::BIGINT FROM pg_class WHERE relname = '%s';

- If queries are filtered, replace it with a subquery that will first limit the results to a reasonable number (such as 1k), this is silly, and won't allow you to go through all results but at least the count call won't kill your database. This is only useful if the filtered query returns over one million rows as well.

I had this problem with very large tables of data being presented as endpoints through DRF. For filtered queries estimate, we parse the EXPLAIN syntax to get an approximate rowcount, which handles filtered queries. It is by no means perfect, but allows us to have next / previous pagination while using the EXPLAIN approximate count for an estimated total. We then keep showing NEXT until there's a page with no results. More frequent vacuums of PostgreSQL are another option for improving accurance of the estimate count you mention. We subclassed DRF's limit/offset pagination and overrode the count() method to accomplish this. It might be an option to consider for Django pagination as well, especially with EXPLAIN now being available through the ORM in 2.1: https://docs.djangoproject.com/en/2.1/ref/models/querysets/#explain

[Dan Davis]

Also, it can be worse than one count query. When interacting with datables.net serverSide, you will need multiple count queries.

--

You received this message because you are subscribed to the Google Groups "Django developers (Contributions to Django itself)" group.
To unsubscribe from this group and stop receiving emails from it, send an email to django-develop...@googlegroups.com.
To post to this group, send email to django-d...@googlegroups.com.
Visit this group at https://groups.google.com/group/django-developers.

To view this discussion on the web visit https://groups.google.com/d/msgid/django-developers/0f431ffc-5ebf-4703-9e01-91240007c154%40googlegroups.com.

[Tom Forbes]

I would be strongly against misusing EXPLAIN like that inside Django, and I feel keyset/cursor pagination is best if your going down this road.

I've got no concrete evidence for this opinion, but I feel like navigating to an exact page is very rarely used and only then as a proxy for range filtering on a column (i.e "page 5 contains columns within the range I want").

--

You received this message because you are subscribed to the Google Groups "Django developers (Contributions to Django itself)" group.
To unsubscribe from this group and stop receiving emails from it, send an email to django-develop...@googlegroups.com.
To post to this group, send email to django-d...@googlegroups.com.
Visit this group at https://groups.google.com/group/django-developers.

To view this discussion on the web visit https://groups.google.com/d/msgid/django-developers/fb3fd1b6-75ed-454d-85c3-ba0672e5368f%40googlegroups.com.

[Adam Johnson]

(I think you meant https://datatables.net/ ? ) :)

To view this discussion on the web visit https://groups.google.com/d/msgid/django-developers/CAFzonYYvXG7u6AFUKKHULun7H5%2Bv8dzKNqqOAmyrUxwiGDr-4g%40mail.gmail.com.

For more options, visit https://groups.google.com/d/optout.

--

Adam

[Dan Davis]

Yes, https://datatables.net/, often miscalled jquery datatables, it is more like php datatables in its CGI parameters ;)

To view this discussion on the web visit https://groups.google.com/d/msgid/django-developers/CAMyDDM0s1N9%3DiZAdXrHE5UNDzp24wkOcxoW4HwKS5H6Gn2O-cg%40mail.gmail.com.

[Dan Davis]

To be honest, I just entered it as a word, and the client made it a URL because it ends with a top-level domain, and looks like a domain name.