When Composite-Comparison Keyset Pagination Breaks Down

Keyset pagination generally offers the best performance for paging through large result sets. The standard approach uses composite type comparison (col1, col2, ...) > (last_row_values) in the WHERE clause, which allows an index to seek directly to the start of the next page. That technique works cleanly for ascending sorts, but it fails as soon as you need a mix of ascending and descending sort orders.

Consider a table with a million rows that we want to page through with ORDER BY val3, val1 DESC. Locating the first 50 rows is trivial. The problem emerges on the second page: to compare the tuple (val3, val1, id) against the last row of the previous page, you need > for the first element but < for the second. No single comparison operator can express that mixed condition.

Workaround 1: Negate the Descending Column

The most direct fix is to reverse the descending column's sort order by negating it. For ORDER BY val3, val1 DESC, you can instead compare on -val1, turning the mixed-order problem into a fully ascending one. This requires an index on (val3, -val1, id).

The trick works cleanly for numeric types. For a timestamp with time zone, there is no unary minus, but you can extract the Unix epoch seconds:

EXTRACT(epoch FROM val2)

That expression is unfortunately not considered immutable by PostgreSQL, because EXTRACT on a timestamptz can depend on the current timezone setting. Even though the epoch itself is timezone-independent, you must wrap it in an IMMUTABLE function before it can be used in an index expression, and then use that same function in your queries.

The negation approach has a hard limit: it does not work for types without a sensible unary inverse, such as strings. A text column sorted descending cannot be converted to an ascending comparison this way.

Workaround 2: Split the Predicate into Branches

A type-agnostic alternative is to abandon composite tuple comparison entirely. For an ORDER BY val2, val3 DESC query, the inequality itself is what breaks down, so you can replace it with three mutually exclusive WHERE conditions joined by OR:

  • rows where val2 = last_val2 and val3 < last_val3
  • rows where val2 = last_val2, val3 = last_val3, and id > last_id
  • rows where val2 > last_val2

While logically correct, that query suffers from the well-known performance problems of OR conditions. The effective solution is to rewrite it as a UNION ALL of three subqueries, each of which fetches 50 rows and can use an index on (val2, val3 DESC, id) independently. The plan is uglier than a single index scan, but each branch performs an efficient index seek, making the overall query fast even on large tables.

Workaround 3: Define an Inverted Custom Type

For cases where neither negation nor query splitting is acceptable, PostgreSQL's extensibility offers a third route: define a new base type whose comparison operators are reversed. The idea is to create a type that behaves exactly like text but sorts in descending order, so a mixed-order query becomes uniformly ascending and composite comparison works again.

This requires a shell type declaration first, since the type's input/output functions reference the type and vice versa. The type's text input and output functions are reused from text, and casts to and from text are defined for convenience.

The comparison operators are where the reversal happens: the = operator uses texteq, but the ordering operators such as < are defined as wrappers around PostgreSQL's text_gt, text_ge, and so on. The b-tree operator class then registers a comparison function that feeds the swapped arguments to text_cmp.

With the type in place, the keyset pagination query reads naturally:

WHERE (val2, invtext(val3), id) > (last_val2, invtext(last_val3), last_id)

and is supported by an ordinary b-tree index on the three columns. The cost is significant: defining a base type requires superuser access, which rules out hosted database services, and demands a deep familiarity with PostgreSQL's type machinery.

Choosing a Strategy

Each workaround targets a different constraint. Negating the descending column is the simplest and most efficient, but only works for types with a meaningful inverse. Splitting the query into a union of index-friendly branches works for any data type, at the price of a more complex query structure. Defining a custom inverted type is elegant but carries heavy administrative and conceptual overhead, making it impractical for most real-world deployments.