Composite key cursor pagination is broken

[jacob-pro]

Description

The SQL generated by the Cursor struct when using composite keys is incorrect and leads to missed results when paginating. The problem is that the WHERE clause is incorrect, it can only currently work if it just so happens that your two columns naturally followed the exact same ordering.

Example

Lets say you have the following table:

ID	Category
1	B
2	B
3	A
4	C
5	A
6	A
7	C
8	B
9	A

Now lets say you want to paginate by category, category isn't unique so in order to page you need to combine with the ID column into a unique composite key.

The SQL to fetch the first page would look like:

Lets query the first 3 results:

SELECT * FROM example
ORDER BY category ASC, id ASC
LIMIT 3

Which returns:

ID	Category
3	A
5	A
6	A

Now we want to get the next page, according to the current implementation this creates a query like:

SELECT * FROM example
WHERE category > 'A' AND id > 6
ORDER BY category ASC, id ASC
LIMIT 3

But this is wrong - we would end up only getting two more results, missing out many inbetween

ID	Category
8	B
7	C

We need to actually have a query like:

SELECT * FROM example
WHERE (category = 'A' and id > 6) OR category > 'A'
ORDER BY category ASC, id ASC
LIMIT 3

which produces:

ID	Category
9	A
1	B
2	B

Three Columns

Lets say you have 3 columns "x", "y", "z", then the WHERE clause needs to look like:

WHERE ("x"= X AND "y" = Y AND "z" > Z) OR ("x" = X AND "y" > Y) OR "x" > X

Versions

Present in master

Related To

• Cursor Based Pagination #300
• Cursor Pagination #754
• Cursor pagination #822

@tyt2y3 @billy1624 @Sytten @ikrivosheev

[Sytten]

Interestingly this is the same technique used when you have a single column key but you want to order the result set by a column. Having a generic solution could be reused for both use cases.

[tyt2y3]

@billy1624 I am going to give this a try if you are not working on it already

[billy1624]

Hey @tyt2y3, please proceed

[holmofy]

@tyt2y3 @billy1624
composite type comparison is a good solution.

-- Fetch the first page
SELECT * FROM users ORDER BY created_at,id LIMIT 10;

-- Fetch the next page
SELECT * FROM users
WHERE (created_at, id) > ("2022-02-02 01:10:11", 73618361)
ORDER BY created_at,id
LIMIT 10;

I see this method of page turning is called "keyset pagination"
https://docs.gitlab.com/ee/development/database/keyset_pagination.html

[Sytten]

@holmofy This is not enough, you have to deal with the case where the order column is equal and nulls too. The document you link is a good resource though. Cursor pagination is very hard to get right especially multi-column

[holmofy]

Postgresql's Composite Type Comparison can support the case where the field is null, as the documentation says:

The SQL specification requires row-wise comparison to return NULL if the result depends on comparing two NULL values or a NULL and a non-NULL. PostgreSQL does this only when comparing the results of two row constructors (as in Section 9.25.5) or comparing a row constructor to the output of a subquery (as in Section 9.24). In other contexts where two composite-type values are compared, two NULL field values are considered equal, and a NULL is considered larger than a non-NULL. This is necessary in order to have consistent sorting and indexing behavior for composite types.

[holmofy]

In addition, I feel that the KeySetPagination API of ActiveRecord in the gitlab link is very elegant