/ Ticket Change Details
Login
Overview

Artifact ID: 07edd854b59ef3e7ac718f2906c53e0112c3915b
Ticket: 13f033c865f878953fb0412b389dd1d1143d1dce
Performance regression
User & Date: drh 2010-08-04 18:43:50
Changes

  1. comment changed to:
    Consider the following SQL:
    
    <blockquote><pre>
    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;
    </pre></blockquote>
    
    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.
    
  2. Untracked field detected: "Application_Fault"
  3. foundin changed to: "3.7.0"
  4. severity changed to: "Important"
  5. status changed to: "Open"
  6. subsystem changed to: "Code_Generator"
  7. title changed to: "Performance regression"
  8. type changed to: "Code_Defect"