SQLite

View Ticket
Login
2015-01-20
18:11 Fixed ticket [f97c463710]: Incorrect ordering with ORDER BY and LIMIT plus 4 other changes (artifact: ac59934aff user: drh)
03:04
Fix another instance of an incorrect value for KeyInfo.nXField on a sorting index. Ticket [f97c4637102a3ae72b79]. (check-in: 0077f64510 user: drh tags: trunk)
02:50
Fix another instance of an incorrect value for KeyInfo.nXField on a sorting index. More changes for ticket [f97c4637102a3ae72b79]. (check-in: dc711db44e user: drh tags: branch-3.8.8)
2015-01-19
21:38
Ensure that the KeyInfo.nXField value for ephemeral tables used to implement ORDER BY or GROUP BY clauses is set correctly, so that the sqlite3VdbeFindCompare() routine can choose the correct comparison function. Add assert() statements to the high-speed comparison functions to detect cases where they are inappropriately chosen. Fix for ticket [f97c4637102a3ae72b7911]. (check-in: 59e592f67f user: drh tags: branch-3.8.8)
21:36
Ensure that the KeyInfo.nXField value for ephemeral tables used to implement ORDER BY or GROUP BY clauses is set correctly, so that the sqlite3VdbeFindCompare() routine can choose the correct comparison function. Add assert() statements to the high-speed comparison functions to detect cases where they are inappropriately chosen. Fix for ticket [f97c4637102a3ae72b7911]. (check-in: f7201bb0cd user: drh tags: trunk)
21:10
There are asserts in place now that will prevent a recurrence of ticket [f97c4637102a3ae7]. Nevertheless, it is good to add some test cases as well. (Closed-Leaf check-in: e02959b9a0 user: drh tags: tkt-f97c4637)
19:21
An alternative way of fixing the key comparison bug of ticket [f97c4637102a3ae72b]. (Closed-Leaf check-in: e41376cf08 user: drh tags: alt1-tkt-f97c4637)
17:28
Add an assert() to verify that the nField+nXField values of a KeyInfo object are never less then the number of columns in a row for a non-corrupt database. This assert() currently fails, which is the root of the problem with ticket [f97c4637102a3ae72b]. (check-in: 083f523d2f user: drh tags: tkt-f97c4637)
15:40 Ticket [f97c463710] Incorrect ordering with ORDER BY and LIMIT status still Open with 6 other changes (artifact: 0c9d51dfc8 user: drh)
15:31 New ticket [f97c463710]. (artifact: fc35a8b205 user: drh)

Ticket Hash: 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
10.25 years ago
Created: 2015-01-19 15:31:16
10.25 years ago
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:

<blockquote><verbatim>
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;
</verbatim></blockquote>

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.