/ View Ticket
Login
2010-08-05
03:24 Fixed ticket [13f033c8]: Performance regression plus 2 other changes (artifact: c1ac8278 user: drh)
02:52
Fix the query planner so that when it has a choice of full-scan tables to move to the outer loop, it chooses the one that is likely to give the fewest output rows. Ticket [13f033c865f878]. (check-in: 309bbedf user: drh tags: trunk)
2010-08-04
21:17
If the outer loop of a join must be a full table scan, make sure that an incomplete ANALYZE does not trick the planner into use a table that might be indexable in an inner loop. Ticket [13f033c865f878] (check-in: e7a714b5 user: drh tags: trunk)
18:43 New ticket [13f033c8] Performance regression. (artifact: 07edd854 user: drh)

Ticket Hash: 13f033c865f878953fb0412b389dd1d1143d1dce
Title: Performance regression
Status: Fixed Type: Code_Defect
Severity: Important Priority: Immediate
Subsystem: Code_Generator Resolution: Fixed
Last Modified: 2010-08-05 03:24:23
Version Found In: 3.7.0
Description:
Consider the following SQL:
CREATE TABLE t1(a INTEGER PRIMARY KEY,b,c);
CREATE INDEX t1c ON t1(c);
INSERT INTO t1 VALUES(1,2,3);
CREATE TABLE t2(x, y);
ANALYZE;
UPDATE sqlite_stat1 SET stat='20000 100';
explain query plan
SELECT * FROM t2, t1 WHERE t2.x=5 AND t1.a=t2.y;

The SELECT at the end should ideally do a full table scan over table T2 and then use the PRIMARY KEY to look up entries of T1, resulting in an O(NlogN) execution time. However, beginning with SQLite version 3.7.0 (and specifically check-in [defaf0d99a807] on 2010-04-15 01:04:54, the query planner does two full table scans on T1 first and then T2 as the inner loop, resulting an O(N**2) execution time.