Cursor pagination doesn't work when attempting to paginate on a multiple order by values when the first value is non-unique.

[sonthonaxrk]

Hey, I appreciate I'm sidestepping the discussion phase, but I think this is a fairly clear bug (and there's no test coverage for it).

The CursorPagination class makes two assumptions that don't always hold true: that there will be one ordering parameter; and that ordering parameter will be unique. It's not clear from the documentation that this needs to be enforced, and more importantly, the CursorPagination class defaults to -created which has no reason to be unique.

This is an example of where it fails:

import base64
import itertools
import re
from base64 import b64encode
from urllib import parse

import pytest
from django.db import models
from rest_framework import generics
from rest_framework.pagination import Cursor
from rest_framework.pagination import CursorPagination as BrokenCursorPagination
from rest_framework.permissions import AllowAny
from rest_framework.serializers import ModelSerializer
from rest_framework.test import APIRequestFactory

from rest_framework.pagination import HeaderCursorPagination

factory = APIRequestFactory()


class ExampleModel(models.Model):
    # Don't use an auto field because we can't reset
    # sequences and that's needed for this test
    id = models.IntegerField(primary_key=True)
    field = models.IntegerField()
    timestamp = models.IntegerField()

    class Meta:
        app_label = "test_app"


class SerializerCls(ModelSerializer):
    class Meta:
        model = ExampleModel
        fields = "__all__"


def create_cursor(offset, reverse, position):
    # Taken from rest_framework.pagination
    cursor = Cursor(offset=offset, reverse=reverse, position=position)

    tokens = {}
    if cursor.offset != 0:
        tokens["o"] = str(cursor.offset)
    if cursor.reverse:
        tokens["r"] = "1"
    if cursor.position is not None:
        tokens["p"] = cursor.position

    querystring = parse.urlencode(tokens, doseq=True)
    return b64encode(querystring.encode("ascii")).decode("ascii")


def decode_cursor(response):
    cursors = {}

    for match in re.finditer('<(.*?)>; rel="(.*?)"', response["link"]):
        link = match.group(1)
        rel = match.group(2)
        # Don't hate my laziness - copied from an IPDB prompt
        cursor_dict = dict(
            parse.parse_qsl(
                base64.decodebytes(
                    (parse.parse_qs(parse.urlparse(link).query)["cursor"][0]).encode()
                )
            )
        )

        offset = cursor_dict.get(b"o", 0)
        if offset:
            offset = int(offset)

        reverse = cursor_dict.get(b"r", False)
        if reverse:
            reverse = int(reverse)

        position = cursor_dict.get(b"p", None)

        cursors[rel] = Cursor(
            offset=offset,
            reverse=reverse,
            position=position,
        )

    return type(
        "prev_next_stuct",
        (object,),
        {"next": cursors.get("next"), "prev": cursors.get("previous")},
    )


@pytest.mark.django_db
def test_filtered_items_are_paginated():
    class PaginationCls(HeaderCursorPagination):
        page_size = 2
        max_page_size = 20
        offset_cutoff = 6

    example_models = []

    for id_, (field_1, field_2) in enumerate(
        itertools.product(range(1, 11), range(1, 3))
    ):
        # field_1 is a unique range from 1-10 inclusive
        # field_2 is the 'timestamp' field. 1 or 2
        example_models.append(
            ExampleModel(
                # manual primary key
                id=id_ + 1,
                field=field_1,
                timestamp=field_2,
            )
        )

    ExampleModel.objects.bulk_create(example_models)

    view = generics.ListAPIView.as_view(
        serializer_class=SerializerCls,
        queryset=ExampleModel.objects.all(),
        pagination_class=PaginationCls,
        permission_classes=(AllowAny,),
        filter_backends=[OrderingFilter],
    )

    def _request(offset, reverse, position):
        return view(
            factory.get(
                "/",
                {
                    PaginationCls.cursor_query_param: create_cursor(
                        offset, reverse, position
                    ),
                    "ordering": "timestamp",
                },
            )
        )

    # This is the result we would expect
    expected_result = list(
        ExampleModel.objects.order_by("timestamp", "id").values(
            "timestamp",
            "id",
            "field",
        )
    )
    assert expected_result == [
        {"field": 1, "id": 1, "timestamp": 1},
        {"field": 2, "id": 3, "timestamp": 1},
        {"field": 3, "id": 5, "timestamp": 1},
        {"field": 4, "id": 7, "timestamp": 1},
        {"field": 5, "id": 9, "timestamp": 1},
        {"field": 6, "id": 11, "timestamp": 1},
        {"field": 7, "id": 13, "timestamp": 1},
        {"field": 8, "id": 15, "timestamp": 1},
        {"field": 9, "id": 17, "timestamp": 1},
        {"field": 10, "id": 19, "timestamp": 1},
        {"field": 1, "id": 2, "timestamp": 2},
        {"field": 2, "id": 4, "timestamp": 2},
        {"field": 3, "id": 6, "timestamp": 2},
        {"field": 4, "id": 8, "timestamp": 2},
        {"field": 5, "id": 10, "timestamp": 2},
        {"field": 6, "id": 12, "timestamp": 2},
        {"field": 7, "id": 14, "timestamp": 2},
        {"field": 8, "id": 16, "timestamp": 2},
        {"field": 9, "id": 18, "timestamp": 2},
        {"field": 10, "id": 20, "timestamp": 2},
    ]

    response = _request(0, False, None)
    next_cursor = decode_cursor(response).next
    position = 0

    while next_cursor:
        assert (
            expected_result[position : position + len(response.data)] == response.data
        )
        position += len(response.data)
        response = _request(*next_cursor)
        next_cursor = decode_cursor(response).next

    prev_cursor = decode_cursor(response).prev
    position = 20

    while prev_cursor:
        assert (
            expected_result[position - len(response.data) : position] == response.data
        )
        position -= len(response.data)
        response = _request(*prev_cursor)
        prev_cursor = decode_cursor(response).prev

The cursor created by the paginator will create a query like this timestamp>1, which isn't enough information to actually paginate a result like this.

I've written a fix for this, where I create a compound cursor with all of the ordering parameters plus the primary key. I then do something like a tuple comparison between the cursor and the table (using some Q objects). It works fine, and this test passes with the fix.

Let me know if you'd like the patch.

[tomchristie]

If there are any changes to be made here I'd expect them to be around better highlighting aspects of the documentation rather than a required fix.

I think we're fairly clear about the uniqueness requirement with... "Cursor based pagination requires that there is a unique, unchanging ordering of items in the result set." and "Proper use of cursor based pagination requires a little attention to detail. You'll need to think about what ordering you want the scheme to be applied against. [...] Should be unique, or nearly unique. Millisecond precision timestamps are a good example."

I don't fully recall the details of our "position-plus-offset implementation, style that allows it to properly support not-strictly-unique values as the ordering.", but I'd expect any changes in this space to provide a clear example with a case where cursor+offset isn't sufficient.

(Also, using a composite key including the PK may sometimes be suitable, but not neccessarily, since the composite of the two might not neccessarily result in a nicely indexed SQL query.)

[tomchristie]

but the paginator doesn't handle it because it only uses timestamp as the cursor position.

Right, but it does handle it because we don't just use a cursor, we use cursor-plus-offset.

[sonthonaxrk]

@tomchristie

I've created a pull request that should make the problem slightly clearer.

#7889

$ pytest tests/test_cursor_pagination.py -v

tests/test_cursor_pagination.py::test_filtered_items_are_paginated[page_size_divisor_of_offset] FAILED                                             [ 20%]
tests/test_cursor_pagination.py::test_filtered_items_are_paginated[page_size_multiple_of_offset] FAILED                                            [ 40%]
tests/test_cursor_pagination.py::test_filtered_items_are_paginated[page_size_uneven_divisor_of_offset] FAILED                                      [ 60%]
tests/test_cursor_pagination.py::test_filtered_items_are_paginated[page_size_uneven_multiple_of_offset] FAILED                                     [ 80%]
tests/test_cursor_pagination.py::test_filtered_items_are_paginated[page_size_same_as_offset] PASSED                                                [100%]

It doesn't handle it unless the offset_cutoff is the same as the page_size. But that can't hold because the the page size is adjustable by the request. Either way, it's not what I'd expect.

I have a fix for this, it's pretty simple to get this to work for the universal case.

[carltongibson]

Should be unique, or nearly unique. Millisecond precision timestamps are a good example.

In a lot of cases, you'll have objects created in a single transaction that will share the value created field. This is a problem because it's the default sorting order (a sane default would be to use the primary key).

I'm not understanding the complaint here?

If you're creating objects one at a time, then timestamps will be fine, even though not strictly unique. No problem.

On the other hand, if you're bulk creating, you know this doesn't apply, and so know you can't use the timestamp to order by.

This seems like a usage issue — I tried to order on a field I knew wasn't (sufficiently) unique 🤔

[sonthonaxrk]

Take a look at the test, it's pretty clear what passes and fails. This kind of request will fail:

http://testserver/example_model?ordering=created,id

That's a consistent and unchanging sort order. I'm not ordering on a non-unique field created, I am ordering on created,id.

In fact, the behaviour is pretty inconsistent across Pagination classes. If you use the CursorPaginator it ignores all of the ordering parameters after created (I can write a test case to show how additional order-bys are implicitly ignored as well). This contrasts to the LimitOffsetPaginator which will respect all of the ordering parameters.

It's pretty clear how the CursorPaginator will just silently ignore all the other sort parameters (when the other classes don't):

https://github.com/encode/django-rest-framework/blob/master/rest_framework/pagination.py#L627

I highly doubt that's intended behaviour because it turns a 'unique, unchanging ordering of items in the result set' to a non-unique one.

[sonthonaxrk]

This demonstrates the broken behaviour:

2375f6c

This demonstrates the fix:

9408b43

[sonthonaxrk]

@carltongibson

If you're creating objects one at a time, then timestamps will be fine, even though not strictly unique. No problem.

On the other hand, if you're bulk creating, you know this doesn't apply, and so know you can't use the timestamp to order by.

Right, but then the typical solution is that you order by timestamp and id, which creates a deterministic ordering of the result set. Having multiple ordering parameters is a feature supported by the ordering filter, and is used as an example in the documentation.

https://www.django-rest-framework.org/api-guide/filtering/#orderingfilter

However, this doesn't work reliably with the CursorPaginator. This class makes an assumption about ordering that does not work in a large number of cases. It only uses the first parameter (note self.ordering[0]).

# https://github.com/encode/django-rest-framework/blob/master/rest_framework/pagination.py#L627

        if current_position is not None:
            # This can be list like ['group', 'username'].  This is usually set by the client
            # making results like this: http://example.com/api/users?ordering=group,username

            order = self.ordering[0]
            is_reversed = order.startswith('-')
            order_attr = order.lstrip('-')

            # Test for: (cursor reversed) XOR (queryset reversed)
            if self.cursor.reverse != is_reversed:
                kwargs = {order_attr + '__lt': current_position}
            else:
                kwargs = {order_attr + '__gt': current_position}

            queryset = queryset.filter(**kwargs)

And like I said, the query that you would use to support multiple parameters is very simple, and does not result in any additional computation because the queryset has already been sorted (but not limited) by those parameters.

---

If this is the correct behaviour. There should be an additional constraint listed here:

https://www.django-rest-framework.org/api-guide/pagination/#details-and-limitations

Perhaps you could add to that list:

CursorPagination might not work reliably with the OrderingFilter. It can only reliably use the first parameter of an ordering parameter list. For example, this request will return http://example.com/api/users?ordering=group,username a list of users sorted by their group membership and username. Although the first page will be sorted deterministically, the cursor will only include enough data to paginate by group and not username and group.

In order to paginate the first element of ordering=<parameter list> MUST be unique. For example, http://example.com/api/users?ordering=group,user_id will not paginate, but http://example.com/api/users?ordering=user_id,group will paginate.

Be sure to constrain ordering_fields in the view only to unique values.

---

@tomchristie

Right, but it does handle it because we don't just use a cursor, we use cursor-plus-offset.

In response to that specific comment, I double checked my work. I added tests, and I don't think it does.

$ pytest tests/test_cursor_pagination.py -v

tests/test_cursor_pagination.py::test_filtered_items_are_paginated[page_size_divisor_of_offset] FAILED [ 20%]
tests/test_cursor_pagination.py::test_filtered_items_are_paginated[page_size_multiple_of_offset] FAILED [ 40%]
tests/test_cursor_pagination.py::test_filtered_items_are_paginated[page_size_uneven_divisor_of_offset] FAILED [ 60%]
tests/test_cursor_pagination.py::test_filtered_items_are_paginated[page_size_uneven_multiple_of_offset] FAILED [ 80%]
tests/test_cursor_pagination.py::test_filtered_items_are_paginated[page_size_same_as_offset] PASSED [100%]

---

Again, it's pretty simple to get working with a query that adds no additional complexity :)

[rollue]

Right, but then the typical solution is that you order by timestamp and id, which creates a deterministic ordering of the result set. Having multiple ordering parameters is a feature supported by the ordering filter, and is used as an example in the documentation.

I'm having exactly the same problem here. I had to use limitoffsetpagination on the specific view that required ordering by timestamp & id.

[amegianeg]

@sonthonaxrk great post! we've hit the same issue. Would you mind sharing your compound cursor solution?

Is there a reason why this it not getting implemented in DRF?

[sonthonaxrk]

@amegianeg @rubendura feel free to use the patch I linked.

I think the reason this is a no fix is just an ego thing, since I spent more time failing to convince the maintainers of this project it was a problem than it took to fix it.

[kavdev]

@sonthonaxrk how do you feel about releasing this multi-column cursor pagination implementation as a third-party package? I think that would solve the problem and would relieve the pressure on the drf devs to merge this in.

[sonthonaxrk]

Sure I could do. I'd rather people just copy and paste the patch wholesale into their project just because I don't have time to maintain any API breakages.

I'm a little bit annoyed that this is just being ignored as an ego thing. Like I get people have priorities, but this is silly. Either have some integrity and label it as a nofix, or put a todo on it. Enough people have this same issue and are complaining about it, and there's silence from the maintainers.

Even the tests in master are wrong!

• https://github.com/encode/django-rest-framework/blob/master/tests/test_pagination.py#L655
• https://github.com/encode/django-rest-framework/blob/master/tests/test_pagination.py#L681
• https://github.com/encode/django-rest-framework/blob/master/tests/test_pagination.py#L794
• https://github.com/encode/django-rest-framework/blob/master/tests/test_pagination.py#L820
• https://github.com/encode/django-rest-framework/blob/master/tests/test_pagination.py#L861
• https://github.com/encode/django-rest-framework/blob/master/tests/test_pagination.py#L887

My patch literally fixes deliberately broken tests.

Also one of the maintainers of DRF worked at my company years ago (and was hired because of his contribution) introduced this pagination into our project, and I ended up fixing it because our clients complained about pagination is broken.

[Hassan-Elseoudy]

I do have the same exact problem, and I think maintainers should really work on this instead of blaming not understanding documentation.

[sonthonaxrk]

@Hassan-Elseoudy @rollue @amegianeg I've got better things to do than write a package that just fixes a bug. It's a waste of time to do so because the package will be obsolete as soon as the bug is fixed.

I think your best best if you want this fixed is to just copy my new pagination.py file into your project.

Then wait a few months and raise the issue yourself because I've obviously annoyed the DRF maintainers too much (which is fair enough, no one likes being told their wrong for free).

[joshorr]

I have a situation where the user can decide the ordering (dynamic), but I always add the id to the end of the ordering to ensure the ordering is stable/unique.

I then thought that I better make sure the CursorPaginator handles multiple ordering fields, so I stepped though the code and discovered it only used the first ordering field!

I then searched for cursor paginator django rest framework multiple ordering fields and found this discussion. I do agree that it would be nice if the built-in CursorPaginator handled multiple ordering fields. But for now I'll just make a custom pagination subclass with your changes in it.

@sonthonaxrk Thank you for your time on providing a patch and creating this discussion.