CODEWITHSUNDEEP
pagination
peekolo
peekolo

Reputation: 342

Cursor Based Pagination for search results without sequential unique ids (eg. location)

I am trying to implement cursor based pagination for data which users can search and order by location (lat, lng). A simplified example is let’s say an entity called ‘searchable’. It would have its unique primary key ‘id’ field, and location fields ‘lat’, ‘lng’.

After I have ordered it by distance from a specific point, the ‘id’s will be jumbled up. There does not seem to be a unique sequential id to be used as a cursor. I can’t use the ‘lat’ and ‘lng’ either, since the search and order is by radius/distance which means there is also no order for ‘lat’ and ‘lng’.

Does this mean cursor based pagination is not suited for such queries? Or are there any ways to implement a cursor for this case?

Upvotes: 5

Views: 2703

Answers (1)

Miroslav Šustek
Miroslav Šustek

Reputation: 131

I think that you can implement cursor based pagination even in this case.

First, you say that your results are ordered by distance from a certain point. I assume that it is a distance from a certain starting point that can be specified by user (like asking a map app to "show restaurants near me"). In this situation, the cursor value is not static and cannot be stored in your searchable record. It has to be calculated based on the user input. By calculating the cursor on-the-fly, you lose one of the advantages of cursor pagination [1] - good effectivity with large result sets. That is because you cannot simply use database index to skip records with cursor value "lower" than the specified one.

[1] For more information about pros and cons of cursor pagination see this article from Slack engineers: https://slack.engineering/evolving-api-pagination-at-slack-1c1f644f8e12.

Second, the distance itself may not be sufficient for unambiguous ordering because two different searchables can have the same distance from the starting point. To solve this, you can add ID as a secondary ordering field which will make the order deterministic (or total order in mathematical terms).

The distance and ID together form a value that can be used as a cursor.

As an example, lets say that the last result on the current page has distance of 123.45 kilometers (or whichever unit you use) and has ID 98765.

This translates to the following cursor:

{
    distance: 123.45,
    id: 98765
}

When you want to "go to next page" you simply request 10 (or your page size) searchables after searchable with this cursor.

If you are familiar with SQL, it would translate into a query like this:

SELECT s.*
FROM searchables s
WHERE get_distance(stating_point, s) > 123.45
    OR get_distance(stating_point, s) = 123.45 AND s.id > 98765
LIMIT 10

where get_distance(a, b) function calculates the distance between points a and b.

Practically, if both distance and ID can be bounded in some range, you can use a clever trick and encode the cursor as a single string which lexicographical order will correspond to the order of results - eg. "0000000123.4500-0000098765".

This way the SQL query can be simplified to:

SELECT s.*
FROM searchables s
WHERE get_cursor(get_distance(stating_point, s), s.id) > '0000000123.4500-0000098765'
LIMIT 10

where get_cursor(distance, id) function formats the distance and ID as a string in the proposed format.

Upvotes: 3

Related Questions