/ View Ticket
Login
2018-09-17
15:25
Disable the ORDER BY LIMIT optimization in queries using window functions. This fixes a problem that was introduced by check-in [206720129ed2fa8875a286] which attempted to fix ticket [9936b2fa443fec03ff25f9]. This changes is a fix for the follow-in tocket [510cde277783b5fb5de628]. (check-in: 36c75fd5 user: drh tags: branch-3.25)
15:19
Disable the ORDER BY LIMIT optimization in queries using window functions. This fixes a problem that was introduced by check-in [206720129ed2fa8875a286] which attempted to fix ticket [9936b2fa443fec03ff25f9]. This changes is a fix for the follow-in tocket [510cde277783b5fb5de628]. (check-in: c6c9585f user: drh tags: trunk)
14:28 New ticket [510cde27] Endless loop on a query with window functions, ORDER BY, and LIMIT. (artifact: 614870a8 user: drh)
2018-09-10
14:49 Fixed ticket [9936b2fa]: Infinite loop due to the ORDER BY LIMIT optimization plus 3 other changes (artifact: 7fafa41f user: drh)
2018-09-08
20:09
Fix multiple issues with the ORDER BY LIMIT optimization. This is the proposed resolution to ticket [9936b2fa443fec03ff25]. (check-in: 20672012 user: drh tags: trunk)
17:43 Ticket [9936b2fa] Infinite loop due to the ORDER BY LIMIT optimization status still Open with 6 other changes (artifact: 959f3745 user: dan)
03:22 New ticket [9936b2fa]. (artifact: 9b89fdd3 user: drh)

Ticket UUID: 9936b2fa443fec03ff25f9b822528c20a2200a49
Title: Infinite loop due to the ORDER BY LIMIT optimization
Status: Fixed Type: Code_Defect
Severity: Critical Priority: Immediate
Subsystem: Unknown Resolution: Fixed
Last Modified: 2018-09-10 14:49:04
Version Found In: 3.24.0
User Comments:
drh added on 2018-09-08 03:22:02:

A confluence of multiple defects in the code generator associated with the ORDER BY LIMIT optimization causes the prepared statement to enter an infinite loop while running the final query in the following SQL:

CREATE TABLE t1(aa VARCHAR PRIMARY KEY NOT NULL,bb,cc,x VARCHAR(400));
INSERT INTO t1(aa,bb,cc) VALUES('maroon','meal','lecture');
INSERT INTO t1(aa,bb,cc) VALUES('reality','meal','catsear');
CREATE TABLE t2(aa VARCHAR PRIMARY KEY, dd INT DEFAULT 1, ee, x VARCHAR(100));
INSERT INTO t2(aa,dd,ee) VALUES('maroon',0,'travel'),('reality',0,'hour');
CREATE INDEX t2x1 ON t2(dd,ee);
ANALYZE;
DROP TABLE IF EXISTS sqlite_stat4;
DELETE FROM sqlite_stat1;
INSERT INTO sqlite_stat1 VALUES
  ('t2','t2x1','3 3 3'),
  ('t2','sqlite_autoindex_t2_1','3 1'),
  ('t1','sqlite_autoindex_t1_1','2 1');
ANALYZE sqlite_master;
PRAGMA vdbe_trace=on;
SELECT *
  FROM t1 LEFT JOIN t2 ON t1.aa=t2.aa
 WHERE t1.bb='meal'
 ORDER BY t2.dd DESC
 LIMIT 1;

The infinite loop is only entered if the command-line shell is compiled without -DSQLITE_DEBUG or without -DSQLITE_ENABLE_MODULE_COMMENTS. If both of those compile-time options are enabled, then another bug in the code generator causes the ORDER BY LIMIT optimization to be disabled, and so the infinite loop does not occur.

This problem was originally reported on the SQLite users mailing list. It took considerable effort to reproduce the problem and then boil it down to the repro script shown above.

The script above first began failing with check-in [02ba8a7ba7ba71cd7abd5d] which added the omit-left-join optimization. That optimization does not seem to be the root cause, but merely a changed that allowed it to be expressed with the current script. The ORDER BY LIMIT optimization that probably is the root cause was introduced in version 3.14 (2016-08-08) by check-in [559733b09e9630fac9d].


dan added on 2018-09-08 17:43:12:

Different manifestation of one of the same problems causes SQLite to return incorrect data:

CREATE TABLE t1(aa, bb);
INSERT INTO t1 VALUES('maroon','meal');

CREATE TABLE t2(cc, dd, ee, x VARCHAR(100));
INSERT INTO t2(cc,dd,ee) VALUES('maroon',1,'one');
INSERT INTO t2(cc,dd,ee) VALUES('maroon',2,'two');
INSERT INTO t2(cc,dd,ee) VALUES('maroon',0,'zero');

CREATE INDEX t2ddee ON t2(dd,ee);
CREATE INDEX t2cc ON t2(cc);

ANALYZE;

---------- returns "maroon|0|zero" (correct)
SELECT t2.cc, t2.dd, t2.ee FROM t1 CROSS JOIN t2 ON t1.aa=t2.cc
ORDER BY t2.dd LIMIT 1;

---------- returns "maroon|1|one" (incorrect)
SELECT t2.cc, t2.dd, t2.ee FROM t1 CROSS JOIN t2 ON t1.aa=t2.cc
WHERE t1.bb='meal'
ORDER BY t2.dd LIMIT 1;