SQLite

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.

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.