SQLite

View Ticket
Login
Ticket Hash: 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.