Support reverse pagination (previous page, has-previous-items)

[simonw]

I need this for datasette-graphql for full compatibility with the way Relay likes to paginate - using cursors for paginating backwards as well as for paginating forwards.

This may be the kick I need to get Datasette pagination to work in reverse too.
Originally posted by @simonw in simonw/datasette-graphql#2 (comment)

[jungle-boogie]

Yes, this would be nice!

I using Datasette v0.56 and don't see a previous page button.

[simonw]

I found one example of an implementation of reversed keyset pagination here: https://github.com/tvainika/objection-keyset-pagination/blob/cb21a493c96daa6e63c302efae6718d09aa11661/index.js#L74-L79

[simonw]

I think my ideal implementation for this would be to reverse the order, grab the previous page-size-plus-one items, then return a ?_next=x token that would provide the previous page sorted back in the expected default order.

The alternative would be to have a ?_previous=x token which can be used to paginate backwards in reverse order, but I think this would be confusing as it would result in "hit next page, then hit previous page" returning you to a new state which features rows in the reverse order.

[simonw]

Let's figure out the SQL for this. The most complex case is probably this one: https://latest.datasette.io/fixtures/compound_three_primary_keys?_next=a%2Ch%2Cr

Here's the SQL for that page: https://latest.datasette.io/fixtures?sql=select+pk1%2C+pk2%2C+pk3%2C+content+from+compound_three_primary_keys+where+%28%28pk1+%3E+%3Ap0%29%0A++or%0A%28pk1+%3D+%3Ap0+and+pk2+%3E+%3Ap1%29%0A++or%0A%28pk1+%3D+%3Ap0+and+pk2+%3D+%3Ap1+and+pk3+%3E+%3Ap2%29%29+order+by+pk1%2C+pk2%2C+pk3+limit+101&p0=a&p1=h&p2=r

select pk1, pk2, pk3, content from compound_three_primary_keys where ((pk1 > :p0)
  or
(pk1 = :p0 and pk2 > :p1)
  or
(pk1 = :p0 and pk2 = :p1 and pk3 > :p2)) order by pk1, pk2, pk3 limit 101

Where p0 is a, p1 is h and p2 is r.

Given the above, how would I figure out the correct previous link? It should be https://latest.datasette.io/fixtures/compound_three_primary_keys?_next=a%2Cd%2Cv - a, d, v.

[simonw]

I tried flipping the direction of the sort and the comparison operators and got this: https://latest.datasette.io/fixtures?sql=select+pk1%2C+pk2%2C+pk3%2C+content+from+compound_three_primary_keys+where+%28%28pk1+%3C+%3Ap0%29%0D%0A++or%0D%0A%28pk1+%3D+%3Ap0+and+pk2+%3C+%3Ap1%29%0D%0A++or%0D%0A%28pk1+%3D+%3Ap0+and+pk2+%3D+%3Ap1+and+pk3+%3C+%3Ap2%29%29+order+by+pk1+desc%2C+pk2+desc%2C+pk3+desc+limit+1+offset+99&p0=a&p1=h&p2=r

select pk1, pk2, pk3, content from compound_three_primary_keys where ((pk1 < :p0)
  or
(pk1 = :p0 and pk2 < :p1)
  or
(pk1 = :p0 and pk2 = :p1 and pk3 < :p2)) order by pk1 desc, pk2 desc, pk3 desc limit 1 offset 99

Which returned a-d-v as desired. I messed around with it to find the limit 1 offset 99 values.

[simonw]

Same query again with a, d, v returns 0 results, which is also as we would want: it signifies that we are back to the very first page: https://latest.datasette.io/fixtures?sql=select+pk1%2C+pk2%2C+pk3%2C+content+from+compound_three_primary_keys+where+%28%28pk1+%3C+%3Ap0%29%0D%0A++or%0D%0A%28pk1+%3D+%3Ap0+and+pk2+%3C+%3Ap1%29%0D%0A++or%0D%0A%28pk1+%3D+%3Ap0+and+pk2+%3D+%3Ap1+and+pk3+%3C+%3Ap2%29%29+order+by+pk1+desc%2C+pk2+desc%2C+pk3+desc+limit+1+offset+99&p0=a&p1=d&p2=v

[simonw]

Relevant code is some of the most complex in all of Datasette.

datasette/datasette/views/table.py

Lines 530 to 594 in 0a7621f

	if _next:
	if is_view:
	# _next is an offset
	offset = f" offset {int(_next)}"
	else:
	components = urlsafe_components(_next)
	# If a sort order is applied, the first of these is the sort value
	if sort or sort_desc:
	sort_value = components[0]
	# Special case for if non-urlencoded first token was $null
	if _next.split(",")[0] == "$null":
	sort_value = None
	components = components[1:]
	# Figure out the SQL for next-based-on-primary-key first
	next_by_pk_clauses = []
	if use_rowid:
	next_by_pk_clauses.append(f"rowid > :p{len(params)}")
	params[f"p{len(params)}"] = components[0]
	else:
	# Apply the tie-breaker based on primary keys
	if len(components) == len(pks):
	param_len = len(params)
	next_by_pk_clauses.append(
	compound_keys_after_sql(pks, param_len)
	)
	for i, pk_value in enumerate(components):
	params[f"p{param_len + i}"] = pk_value
	# Now add the sort SQL, which may incorporate next_by_pk_clauses
	if sort or sort_desc:
	if sort_value is None:
	if sort_desc:
	# Just items where column is null ordered by pk
	where_clauses.append(
	"({column} is null and {next_clauses})".format(
	column=escape_sqlite(sort_desc),
	next_clauses=" and ".join(next_by_pk_clauses),
	)
	)
	else:
	where_clauses.append(
	"({column} is not null or ({column} is null and {next_clauses}))".format(
	column=escape_sqlite(sort),
	next_clauses=" and ".join(next_by_pk_clauses),
	)
	)
	else:
	where_clauses.append(
	"({column} {op} :p{p}{extra_desc_only} or ({column} = :p{p} and {next_clauses}))".format(
	column=escape_sqlite(sort or sort_desc),
	op=">" if sort else "<",
	p=len(params),
	extra_desc_only=""
	if sort
	else " or {column2} is null".format(
	column2=escape_sqlite(sort or sort_desc)
	),
	next_clauses=" and ".join(next_by_pk_clauses),
	)
	)
	params[f"p{len(params)}"] = sort_value
	order_by = f"{order_by}, {order_by_pks}"
	else:
	where_clauses.extend(next_by_pk_clauses)

And

datasette/datasette/views/table.py

Lines 743 to 771 in 0a7621f

	# Pagination next link
	next_value = None
	next_url = None
	if 0 < page_size < len(rows):
	if is_view:
	next_value = int(_next or 0) + page_size
	else:
	next_value = path_from_row_pks(rows[-2], pks, use_rowid)
	# If there's a sort or sort_desc, add that value as a prefix
	if (sort or sort_desc) and not is_view:
	prefix = rows[-2][sort or sort_desc]
	if isinstance(prefix, dict) and "value" in prefix:
	prefix = prefix["value"]
	if prefix is None:
	prefix = "$null"
	else:
	prefix = urllib.parse.quote_plus(str(prefix))
	next_value = f"{prefix},{next_value}"
	added_args = {"_next": next_value}
	if sort:
	added_args["_sort"] = sort
	else:
	added_args["_sort_desc"] = sort_desc
	else:
	added_args = {"_next": next_value}
	next_url = self.ds.absolute_url(
	request, path_with_replaced_args(request, added_args)
	)
	rows = rows[:page_size]

I'll need to think hard about how to refactor this out into something more understandable before implementing previous links.