|
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 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. | ||||