SQLite
View Ticket
Not logged in
Ticket UUID: f97c4637102a3ae72b7911167e1d4da12ce60722
Title: Incorrect ordering with ORDER BY and LIMIT
Status: Fixed Type: Code_Defect
Severity: Severe Priority: Immediate
Subsystem: Unknown Resolution: Fixed
Last Modified: 2015-01-20 18:11:18
Version Found In: 3.8.8
User Comments:
drh added on 2015-01-19 15:31:16:

The following SQL outputs rows in the incorrect order for SQLite versions 3.8.7 and 3.8.8:

CREATE TABLE t1(x);
INSERT INTO t1(x) VALUES(1),(5),(3),(4),(2);
SELECT
   x, 01, 02, 03, 04, 05, 06, 07, 08, 09,
  10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
  20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
  30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
  40, 41, 42, 43, 44, 45, 46, 47, 48, 49,
  50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60
FROM t1
ORDER BY x
LIMIT -1;

In order to hit this bug, there must be an ORDER BY clause and a LIMIT clause and the number of columns in the query plus the number of sort keys needs to sum to exactly 62. Adding or removing a single column from the result set yields the correct answer.

This bug first appeared in check-in [b1c0f0bc1bd8a] which is when the multi-threaded sorter was introduced.


drh added on 2015-01-19 15:40:42:

Correction: the total number of columns plus the number of sort terms needs to be 62 or greater, not exactly 62. And, if some of the columns contain large text or blob values that use more than one byte in their type header, then numbers less than 62 will provoke the problem as well.

So a better characterization of the problem:

  • An ORDER BY clause that requires a sort (cannot use an index)
  • A LIMIT clause
  • There are a large number of columns in the result


drh added on 2015-01-20 18:11:18:

The problem was introduced by the sqlite3VdbeRecordCompare() optimizations on 2014-03-04 checkin [3325ad5bdc2f81f63b55] (version 3.8.4). The KeyInfo.nXField value was not always accurate for emphemeral tables and so the sqlite3VdbeFindCompare() function might return one of the short-circuit comparison routines when in fact the generalized comparison routine was required. The problem became more acute with the introduction of multi-threaded sorting on on 2014-09-01 checkin [b1c0f0bc1bd8a347] (version 3.8.7) because the new sorter creates tables with lots of extra fields after the key.

The problem is fixed for version 3.8.8.1 by ensuring that the KeyInfo.nXField is set correctly. Two new assert() statements are added to verify correct KeyInfo.nXField values moving forward.