SQLite: DELETE can fail with reverse_unordered_selects = true

DeleteWithReverseUnorderedSelects.md

DELETE can fail with reverse_unordered_selects = true

Under very specific circumstances DELETE FROM x WHERE col = val may fail to delete all rows if PRAGMA reverse_unordered_selects = true; has been executed.

Steps to repro:

Open the test DB (40KB) with SQLite 3.12.1

Run:

pragma reverse_unordered_selects = true;
delete   from ids where fk = 'DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD';
select * from ids where fk = 'DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD';

Expected Behaviour

No rows returned.

Actual Behaviour

SQLite returns the row: 79|DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD

Example:

C:\>sqlite3 test.db
SQLite version 3.12.1 2016-04-08 15:09:49
Enter ".help" for usage hints.
sqlite> pragma reverse_unordered_selects = true;
sqlite> delete   from ids where fk = 'DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD';
sqlite> select * from ids where fk = 'DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD';
79|DDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDD
SQLite>

The bug appears to be harder to reproduce with a larger database page size or smaller keys, so my speculation is that it's related to records for the same key in an index spanning multiple DB pages. (This could happen frequently in an index for a foreign key relationship.)