Bug: Sort by column with NULL in next_page URL

[earthboundkid]

Copy-pasting from #189 (comment), since that issue is closed:

I think I found a bug. I tried to sort by middle initial in my salaries set, and many middle initials are null. The next_url gets set by Datasette to:

http://localhost:8001/salaries-d3a5631/2017+Maryland+state+salaries?_next=None%2C391&_sort=middle_initial

But then None is interpreted literally and it tries to find a name with the middle initial "None" and ends up skipping ahead to O on page 2.

[simonw]

Yikes, definitely a bug.

[simonw]

So there are two tricky problems to solve here:

• I need a way of encoding null into that _next= that is unambiguous from the string None or null. This means introducing some kind of escaping mechanism in those strings. I already use URL encoding as part of the construction of those components here, maybe that can help here?
• I need to figure out what the SQL should be for the "next" set of results if the previous value was null. Thankfully we use the primary key as a tie-breaker so this shouldn't be impossible.

[simonw]

Relevant code:

datasette/datasette/app.py

Lines 828 to 832 in 904f1c7

	if (sort or sort_desc) and not is_view:
	prefix = str(rows[-2][sort or sort_desc])
	next_value = '{},{}'.format(
	urllib.parse.quote_plus(prefix), next_value
	)

[simonw]

I could use $null as a magic value that means None. Since I'm applying quote_plus() to actual values, any legit strings that look like this will be encoded as %24null:

>>> urllib.parse.quote_plus('$null')
'%24null'

[simonw]

I think the correct SQL is this: https://datasette-issue-189-demo-3.now.sh/salaries-7859114-7859114?sql=select+rowid%2C+*+from+%5B2017+Maryland+state+salaries%5D%0D%0Awhere+%28middle_initial+is+not+null+or+%28middle_initial+is+null+and+rowid+%3E+%3Ap0%29%29%0D%0Aorder+by+middle_initial+limit+101&p0=391

select rowid, * from [2017 Maryland state salaries]
where (middle_initial is not null or (middle_initial is null and rowid > :p0))
order by middle_initial limit 101

Though this will also need to be taken into account for #198

[simonw]

But what would that SQL look like for _sort_desc?

[simonw]

Here's where that SQL gets constructed at the moment:

datasette/datasette/app.py

Lines 761 to 771 in 10a34f9

	# Now add the sort SQL, which may incorporate next_by_pk_clauses
	if sort or sort_desc:
	where_clauses.append(
	'({column} {op} :p{p} or ({column} = :p{p} and {next_clauses}))'.format(
	column=escape_sqlite(sort or sort_desc),
	op='>' if sort else '<',
	p=len(params),
	next_clauses=' and '.join(next_by_pk_clauses),
	)
	)
	params['p{}'.format(len(params))] = sort_value

[simonw]

Weird... tests are failing in Travis, despite passing on my local machine. https://travis-ci.org/simonw/datasette/builds/367423706

[simonw]

Still failing. This is very odd.

[simonw]

I'm reverting this out of master until I can figure out why the tests are failing.

[simonw]

Here's the test that's failing:

datasette/tests/test_api.py

Lines 437 to 470 in 59a3aa8

	(
	'_sort_desc=sortable_with_nulls',
	lambda row: (
	1 if row['sortable_with_nulls'] is None else 0,
	-row['sortable_with_nulls'] if row['sortable_with_nulls'] is not None else 0,
	row['content']
	),
	'sorted by sortable_with_nulls descending'
	),
	# text column contains '$null' - ensure it doesn't confuse pagination:
	('_sort=text', lambda row: row['text'], 'sorted by text'),
	])
	def test_sortable(app_client, query_string, sort_key, human_description_en):
	path = '/test_tables/sortable.json?_shape=objects&{}'.format(query_string)
	fetched = []
	page = 0
	while path:
	page += 1
	assert page < 100
	response = app_client.get(path, gather_request=False)
	assert human_description_en == response.json['human_description_en']
	fetched.extend(response.json['rows'])
	path = response.json['next_url']
	assert 5 == page
	expected = list(generate_sortable_rows(201))
	expected.sort(key=sort_key)
	import json
	print('expected = {}'.format(json.dumps(expected)))
	print('fetched = {}'.format(json.dumps(fetched)))
	assert [
	r['content'] for r in expected
	] == [
	r['content'] for r in fetched
	]

I got Travis to spit out the fetched and expected variables.

expected has 201 items in it and is identical to what I get on my local laptop.

fetched has 250 items in it, so it's clearly different from my local environment.

I've managed to replicate the bug in production! I created a test database like this:

python tests/fixtures.py sortable.db

Then deployed that database like so:

datasette publish now sortable.db \
    --extra-options="--page_size=50" --branch=debug-travis-issue-216

And... if you click "next" on this page https://datasette-issue-216-pagination.now.sh/sortable-5679797/sortable?_sort_desc=sortable_with_nulls five times you get back 250 results, when you should only get back 201.

[simonw]

The version that I deployed which exhibits the bug is running SQLite 3.8.7.1 - https://datasette-issue-216-pagination.now.sh/sortable-5679797?sql=select+sqlite_version%28%29

The version that I have running locally which does NOT exhibit the bug is running SQLite 3.23.0

[simonw]

... which is VERY surprising, because 3.23.0 only came out on 2nd April this year: https://www.sqlite.org/changes.html - I have no idea how I came to be running that version on my laptop.

[simonw]

This is the SQL that returns differing results in production and on my laptop: https://datasette-issue-216-pagination.now.sh/sortable-5679797?sql=select+%2A+from+sortable+where+%28sortable_with_nulls+is+null+and+%28%28pk1+%3E+%3Ap0%29%0A++or%0A%28pk1+%3D+%3Ap0+and+pk2+%3E+%3Ap1%29%29%29+order+by+sortable_with_nulls+desc+limit+51&p0=b&p1=t

select * from sortable where (sortable_with_nulls is null and ((pk1 > :p0)
  or
(pk1 = :p0 and pk2 > :p1))) order by sortable_with_nulls desc limit 51

I think that order by sortable_with_nulls desc bit is at fault - the primary keys should be included in that order by as well.

Sure enough, changing the query to this one returns the same results across both environments:

select * from sortable where (sortable_with_nulls is null and ((pk1 > :p0)
  or
(pk1 = :p0 and pk2 > :p1))) order by sortable_with_nulls desc, pk1, pk2 limit 51

[simonw]

Fixed!