Implement Reverse Pagination

[Amit Upadhyay <upadhyay@…>]

Copied from ​http://www.amitu.com/blog/2007/july/reverse-pagination/:

You are all aware of object pagination, search results, your photo on flickr, stories on reddit, all have a next page/previous page paradigm. Django makes it trivially easy to create such pages by providing object_list generic view. There are some problems with the current implementation of pagination that we see around, page no 0/1 is assigned to the latest objects in the list. While in search result this makes little difference, in other cases it has a few consequences.

In reddit for example, you are on the main page, you see 25 stories there, you take 10 minutes to go through all of them, and click next. There is a good chance that 3-5 stories on the first page would have moved to now second page, and you will see them again. Not a good experience, but acceptable. You spend next 3-4 hours working, and click back to see the stories on the first page, you are taken to page 0, and there are good chances you have missed 12 stories that moved from first page to second, as your current page labelled second page became third. This is all quite confusing if you think about it. [I am assuming from this discussion the stories changing their relative rankings for simplicity, you can take example of flickr group photos, they also change rapidly, and order does not change there].

Another problem is, I am page 26 of this flickr group, and I see some fellow has posted 8 nice photos to the group. I bookmark the page, and come back later/email it to a friend, and by the time the page is visited again, 100s of new photos has been added and the content of page 26 is now on page 29 or so.

The last consequence of this is caching difficulty. If a group has 5 thousand pages worth 30 photos each, and one more photo gets added, either the page number of the photos in each page will change for 5 thousand of those pages. This will happen on each photo being added, and there for the page can hardly be ever cached.

I propose a solution to this problem, I call it reverse pagination, and this blog is currently using a patched django to demonstrate it. In reverse pagination, page no 0/1 is assigned to the older page ever. When on reddit home page, and click next, you will not go to page 2, you will jump to page 20566 or something like that. The content of page 20566 will never change, only the content of latest page would be changing while new items are being added. This means all pages other than the main page can be cached for the rest of the life span of the website. And user will not face the other two problems I listed above.

Here is the patch for django. Enjoy!

[Amit Upadhyay <upadhyay@…>]

reverse paginator implementation.

[Amit Upadhyay <upadhyay@…>]

ignore the previous patch.

[Amit Upadhyay <upadhyay@…>]

To use reverse pagination, you will have to reverse the order clause in the queryset passed to it. For example if you were using

    queryset = blog.post_set.filter(is_link=False).order_by("-posted_on")

with object_list() so far, you will have to do

    queryset = blog.post_set.filter(is_link=False).order_by("posted_on")

when using object_list(..., reverse_pagination=True).

[Simon G. <dev@…>]

Discussion is ​here

[Luke Plant]

Your implementation is a huge performance problem -- it requires loading the entire QuerySet into memory, reversing it, and then slicing it. The current implementation only queries the database for the page of data needed.

A much better solution would be along these lines:

• make ObjectPaginator have a property or method called 'defaultpage', which returns 1 for current implementation.
• add a 'paginator' keyword argument to the generic views, which defaults to 'ObjectPaginator'. It's a 'factory function' that has the same signature as the ObjectPaginator constructor (i.e. takes a queryset and the pageinate_by argument) and returns an object used for pagination.
• make a subclass of ObjectPaginator that has the behaviour you want for 'defaultpage', and pass this as the 'paginator' object.

This would have the added advantage that you could use the 'orphans' parameter of ObjectPaginator in generic views:

def mypaginator(queryset, paginate_by):
    return ObjectPaginator(queryset, paginate_by, orphans=3)

...

return object_list(..., paginator=mypaginator)

Alternatively, the 'paginator' keyword argument could be the instantiated object, rather than the class or factory function, in which case it would be mutually exclusive with the paginate_by argument.

[Amit Upadhyay <upadhyay@…>]

Replying to lukeplant:

Your implementation is a huge performance problem -- it requires loading the entire QuerySet into memory, reversing it, and then slicing it. The current implementation only queries the database for the page of data needed.

No it does not. Only objects to be shown on a particular page are loaded in memory and reversed.

[Luke Plant]

Oops, sorry, I misread the patch. Still, it means it now works in a bizarre way. You have to manually reverse the ordering on the query set, *and* tell pagination to work in reverse. The only thing the patch is *really* bringing is the ability to start with the 'other' end of the list when no specific page is requested, and it seems there are better, more explicit ways of doing that.

[anonymous]

Replying to lukeplant:

Oops, sorry, I misread the patch. Still, it means it now works in a bizarre way. You have to manually reverse the ordering on the query set, *and* tell pagination to work in reverse. The only thing the patch is *really* bringing is the ability to start with the 'other' end of the list when no specific page is requested, and it seems there are better, more explicit ways of doing that.

This patch seems like the easiest way to me, can you tell me the other ways.

[anonymous]

The purpose of this patch is to make sure the objects on any given page remain the same throughout the history of that page [other than for latest page], which leads to bookmark-ability and better-cache-ability.

[portland@…]

Another approach to solving this issue: instead of storing references to the next/previous pages (the contents of which change as new objects are added), there could be an option to store references to the next/previous OBJECTS based on what's already on the page. So say you had 372 objects, and you were looking at the first ten (so objects 1-10). Instead of a "previous page" link with a "?page=2" string attached, you'd have a "previous 10" link with a "?object=11" attached, a signal to start the next page with object 11.

Nothing would need to change about how QuerySets are ordered, but it does look like it would require modification of ObjectPaginator. I haven't really thought about implementation details, I just happen to know a site that follows this behavior and it works very well for solving the "creeping updates" problem.

[Amit Upadhyay <upadhyay@…>]

Replying to portland@chrominance.net:

Another approach to solving this issue: instead of storing references to the next/previous pages (the contents of which change as new objects are added), there could be an option to store references to the next/previous OBJECTS based on what's already on the page. So say you had 372 objects, and you were looking at the first ten (so objects 1-10). Instead of a "previous page" link with a "?page=2" string attached, you'd have a "previous 10" link with a "?object=11" attached, a signal to start the next page with object 11.

object==1 is the oldest item or the newest? This will decide the queryset ordering. This will also decide if caching stays or gets invalidated when new items are added. This will also decide if the page is bookmark-able or not.

You are confusing the discussion of "should pagination be forward of backward?" with "should we paginated by using page no. or object index?". They are mutually exclusive discussions, and both will have to be answered. I just assumed the second question is answered, and page number was found to be "better" than object.

[Adrian Holovaty]

I can't wrap my head around this -- it smells like something that is outside the scope of the framework. Marking as a wontfix.

[upadhyay@…]

Here is a nice presentation to explain what I meant: ​https://speakerdeck.com/espylaub/pagination-on-the-internet-and-why-its-weird

[Dylan Young]

+1 This is how pagination should be done (or one way anyways).