/ View Ticket
Login
2016-09-16
17:07 Fixed ticket [0eab1ac7]: O(N*N) behavior where it should be O(N) plus 3 other changes artifact: 8da4f274 user: drh
16:30
Fix a problem causing incorrect code to be generated for IN constraints like "a IN (1, 2, 3)" where column "a" is a rowid column with an extra UNIQUE index created on it. Ticket [0eab1ac759]. check-in: a92aee55 user: dan tags: trunk
15:42
Replace a faulty assert() with a testcase() to assure the condition is tested. Ticket [0eab1ac7591f]. check-in: a49bc0a8 user: drh tags: trunk
14:30 Ticket [0eab1ac7] O(N*N) behavior where it should be O(N) status still Open with 6 other changes artifact: 9aab0ed9 user: drh
13:57 New ticket [0eab1ac7]. artifact: 62ca7f9b user: drh

Ticket UUID: 0eab1ac7591f511dc8f8ed27bd622ac16b31e585
Title: O(N*N) behavior where it should be O(N)
Status: Fixed Type: Code_Defect
Severity: Severe Priority: Immediate
Subsystem: Unknown Resolution: Fixed
Last Modified: 2016-09-16 17:07:43
Version Found In: 3.14.2
User Comments:
drh added on 2016-09-16 13:57:02:

The query at the end of the following SQL exhibits O(N*N) behavior:

CREATE TABLE t1(x INTEGER UNIQUE PRIMARY KEY NOT NULL, a,b,c,d);
CREATE TABLE t2(y INT);
explain query plan SELECT count(*) FROM t1 WHERE x IN t2;

The EXPLAIN QUERY PLAN shows that the subquery against t2 is run twice. One of those two is inside the t1 loop, causing the O(N*N) behavior.

Bisecting shows this problem was introduced by check-in [96ea990942] (2016-03-16, version 3.12.0) and was fixed by check-in [061b800603] (2016-07-26). That fix was later merged to trunk at [ddb5f0558c] but has not yet been released.

In other words, this problem has already been fixed on trunk. This ticket is created to an historical record of the problem, and to allow for study of the root cause, and to make improvements to the test suite to avoid a regression.

This problem was first reported on the sqlite-users mailing list by Takasumi Iwamoto.


drh added on 2016-09-16 14:30:51:

The following query causes an assertion fault on trunk:

CREATE TABLE t1(a INTEGER UNIQUE PRIMARY KEY, b VARCHAR(200));
SELECT count(*) FROM t1 WHERE a IN (1, 2, 3);

The root cause of this failure and the original O(N*N) performance is the redundant UNIQUE constraint on the INTEGER PRIMARY KEY. That extra unique index is confusing the query planner, apparently.