Keyset pagination with alternating sort order within the set of keys?

Question

I have a table called event which has id (uuidv4), name, description, created_at and updated_at columns.

I am trying to understand "keyset pagination". This is what I understand right now:

Base query (first page):

SELECT * 
FROM event 
ORDER BY created_at, id ASC 
LIMIT 3

Second query (second page):

SELECT * 
FROM event 
WHERE (created_at, id)
    > ('2024-02-09 14:21:52+00', '7aa20cad-3a8f-45cb-bee2-2115d4ad1c20') 
ORDER BY created_at, id ASC 
LIMIT 3;

This works perfectly. But I have a few use-cases which I don't understand.

1. What happens when I want to order by created_at DESC or id DESC?

2. How does it work if I want to order by name DESC? SELECT * from event ORDER BY name DESC, created_at, id ASC LIMIT 3. But how does that work when fetching with a cursor? I know that I have to include the name in the cursor but I don't understand how the tuple filter then would look like:

    SELECT * 
    FROM event 
    WHERE (name, created_at, id)
        > ('Name 9', '2024-02-09 14:21:52+00', '7aa20cad-3a8f-45cb-bee2-2115d4ad1c20') 
    ORDER BY created_at, id ASC 
    LIMIT 3;
   

   Like this? But does the < or > operator not correlate to the ordering?

Can someone point to resources explaining it well, or explain it here?

Answer 1

"Keyset pagination" with index support (the only kind that performs well) is based on Row Constructor Comparison. The comparison uses the same operator for every field in the row ("key in the set"). And the index has to agree with that: use the same fields in the same sequence and all with either ascending or descending sort order. You cannot mix ascending and descending order in either the query or the index. See:

• SQL syntax term for 'WHERE (col1, col2) < (val1, val2)'
• Efficient pagination for big tables

Consequently, beware of columns that aren't defined NOT NULL in the row value (the "keyset") used for sorting. NULL sorts last in default ASCENDING sort order (and first ind DESCENDING order), but a row value comparison like:

WHERE (name, created_at, id) > ('Name 9', '...', '...')

... excludes rows with null values in the name completely. The manual:

For the <, <=, > and >= cases, the row elements are compared left-to-right, stopping as soon as an unequal or null pair of elements is found. If either of this pair of elements is null, the result of the row comparison is unknown (null); otherwise comparison of this pair of elements determines the result. For example, ROW(1,2,NULL) < ROW(1,3,0) yields true, not null, because the third pair of elements are not considered.

Answer 2

If you want to mix the ordering then you can't use tuple/row comparison, you need explicit AND/OR conditions. This is not necessarily worse performance-wise (at least on SQL Server, I don't know about Postgres). It's just more verbose. The server should hopefully just use separate index seeks and concatenate them.

SELECT * 
FROM event 
WHERE (
  name = @last_name
  AND created_at = @last_created_at
  AND id > @last_id
) OR (
  name = @last_name
  AND created_at > @last_created_at
) OR (
  name < @last_name
)
ORDER BY
  name DESC, 
  created_at ASC,
  id ASC
LIMIT 3;

You could mix and match, so use AND/OR for some columns and tuple comparison for others.

SELECT * 
FROM event 
WHERE (
  name = @last_name
  AND (created_at, id) > (@last_created_at, @last_id)
) OR (
  name < @last_name
)
ORDER BY
  name DESC, 
  created_at ASC,
  id ASC
LIMIT 3;

Note that three things must align for Keyset Pagination to work properly, they all need to be the same:

• The index, which in this case should be (name DESC, created_at ASC, id ASC)
• The ORDER BY.
• The WHERE clause.

The index could be in reverse order, on DBMSs that support reverse index seeking (are there any that don't?). So you could have an index (name ASC, created_at DESC, id DESC) also.