/ Check-in [e7a714b5]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment: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]
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: e7a714b52c45af096af74049826d32c647abfe3f
User & Date: drh 2010-08-04 21:17:16
Context
2010-08-05
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
11:34
When opening a write-transaction on a database file that has been appended to or truncated by a pre-3.7.0 client, update the database-size field in the database header. Fix for [51ae9cad31]. check-in: 65b8636a user: dan tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/where.c.

  4060   4060     for(i=iFrom=0, pLevel=pWInfo->a; i<nTabList; i++, pLevel++){
  4061   4061       WhereCost bestPlan;         /* Most efficient plan seen so far */
  4062   4062       Index *pIdx;                /* Index for FROM table at pTabItem */
  4063   4063       int j;                      /* For looping over FROM tables */
  4064   4064       int bestJ = -1;             /* The value of j */
  4065   4065       Bitmask m;                  /* Bitmask value for j or bestJ */
  4066   4066       int isOptimal;              /* Iterator for optimal/non-optimal search */
         4067  +    int nUnconstrained;         /* Number tables without INDEXED BY */
  4067   4068   
  4068   4069       memset(&bestPlan, 0, sizeof(bestPlan));
  4069   4070       bestPlan.rCost = SQLITE_BIG_DBL;
  4070   4071   
  4071   4072       /* Loop through the remaining entries in the FROM clause to find the
  4072   4073       ** next nested loop. The loop tests all FROM clause entries
  4073   4074       ** either once or twice. 
................................................................................
  4101   4102       ** The best strategy is to iterate through table t1 first. However it
  4102   4103       ** is not possible to determine this with a simple greedy algorithm.
  4103   4104       ** However, since the cost of a linear scan through table t2 is the same 
  4104   4105       ** as the cost of a linear scan through table t1, a simple greedy 
  4105   4106       ** algorithm may choose to use t2 for the outer loop, which is a much
  4106   4107       ** costlier approach.
  4107   4108       */
         4109  +    nUnconstrained = 0;
  4108   4110       for(isOptimal=(iFrom<nTabList-1); isOptimal>=0; isOptimal--){
  4109   4111         Bitmask mask;  /* Mask of tables not yet ready */
  4110   4112         for(j=iFrom, pTabItem=&pTabList->a[j]; j<nTabList; j++, pTabItem++){
  4111   4113           int doNotReorder;    /* True if this table should not be reordered */
  4112   4114           WhereCost sCost;     /* Cost information from best[Virtual]Index() */
  4113   4115           ExprList *pOrderBy;  /* ORDER BY clause for index to optimize */
  4114   4116     
................................................................................
  4117   4119           m = getMask(pMaskSet, pTabItem->iCursor);
  4118   4120           if( (m & notReady)==0 ){
  4119   4121             if( j==iFrom ) iFrom++;
  4120   4122             continue;
  4121   4123           }
  4122   4124           mask = (isOptimal ? m : notReady);
  4123   4125           pOrderBy = ((i==0 && ppOrderBy )?*ppOrderBy:0);
         4126  +        if( pTabItem->pIndex==0 ) nUnconstrained++;
  4124   4127     
  4125   4128           assert( pTabItem->pTab );
  4126   4129   #ifndef SQLITE_OMIT_VIRTUALTABLE
  4127   4130           if( IsVirtual(pTabItem->pTab) ){
  4128   4131             sqlite3_index_info **pp = &pWInfo->a[j].pIdxInfo;
  4129   4132             bestVirtualIndex(pParse, pWC, pTabItem, mask, pOrderBy, &sCost, pp);
  4130   4133           }else 
  4131   4134   #endif
  4132   4135           {
  4133   4136             bestBtreeIndex(pParse, pWC, pTabItem, mask, pOrderBy, &sCost);
  4134   4137           }
  4135   4138           assert( isOptimal || (sCost.used&notReady)==0 );
  4136   4139   
  4137         -        if( (sCost.used&notReady)==0
  4138         -         && (bestJ<0 || sCost.rCost<bestPlan.rCost
  4139         -             || (sCost.rCost<=bestPlan.rCost && sCost.nRow<bestPlan.nRow))
         4140  +        /* Conditions under which this table becomes the best so far:
         4141  +        **
         4142  +        **   (1) The table must not depend on other tables that have not
         4143  +        **       yet run.
         4144  +        **
         4145  +        **   (2) A full-table-scan plan cannot supercede another plan unless
         4146  +        **       the full-table-scan is an optimal plan.
         4147  +        **
         4148  +        **   (3) The plan cost must be lower than prior plans or else the
         4149  +        **       cost must be the same and the number of rows must be lower.
         4150  +        **
         4151  +        **   (4) All tables have an INDEXED BY clause or this table lacks an
         4152  +        **       INDEXED BY clause or this table uses the specific
         4153  +        **       index specified by its INDEXED BY clause.
         4154  +        */
         4155  +        if( (sCost.used&notReady)==0                       /* (1) */
         4156  +            && (bestJ<0 || isOptimal                       /* (2) */
         4157  +                || (sCost.plan.wsFlags & WHERE_NOT_FULLSCAN)!=0)
         4158  +            && (bestJ<0 || sCost.rCost<bestPlan.rCost      /* (3) */
         4159  +                || (sCost.rCost<=bestPlan.rCost && sCost.nRow<bestPlan.nRow))
         4160  +            && (nUnconstrained==0 || pTabItem->pIndex==0   /* (4) */
         4161  +                || pTabItem->pIndex==sCost.plan.u.pIdx)
  4140   4162           ){
  4141   4163             WHERETRACE(("... best so far with cost=%g and nRow=%g\n",
  4142   4164                         sCost.rCost, sCost.nRow));
  4143   4165             bestPlan = sCost;
  4144   4166             bestJ = j;
  4145   4167           }
  4146   4168           if( doNotReorder ) break;

Changes to test/indexedby.test.

   119    119   #
   120    120   do_test indexedby-4.1 {
   121    121     EQP { SELECT * FROM t1, t2 WHERE a = c }
   122    122   } {0 0 {TABLE t1} 1 1 {TABLE t2 WITH INDEX i3}}
   123    123   do_test indexedby-4.2 {
   124    124     EQP { SELECT * FROM t1 INDEXED BY i1, t2 WHERE a = c }
   125    125   } {0 1 {TABLE t2} 1 0 {TABLE t1 WITH INDEX i1}}
          126  +do_test indexedby-4.3 {
          127  +  catchsql {
          128  +    SELECT * FROM t1 INDEXED BY i1, t2 INDEXED BY i3 WHERE a=c
          129  +  }
          130  +} {1 {cannot use index: i1}}
          131  +do_test indexedby-4.4 {
          132  +  catchsql {
          133  +    SELECT * FROM t2 INDEXED BY i3, t1 INDEXED BY i1 WHERE a=c
          134  +  }
          135  +} {1 {cannot use index: i3}}
   126    136   
   127    137   # Test embedding an INDEXED BY in a CREATE VIEW statement. This block
   128    138   # also tests that nothing bad happens if an index refered to by
   129    139   # a CREATE VIEW statement is dropped and recreated.
   130    140   #
   131    141   do_test indexedby-5.1 {
   132    142     execsql {

Changes to test/where3.test.

   208    208   do_test where3-2.7 {
   209    209     queryplan {
   210    210       SELECT * FROM tA, tB, tC LEFT JOIN tD ON dpk=cx
   211    211        WHERE cpk=bx AND apk=cx
   212    212     }
   213    213   } {tB {} tC * tA * tD *}
   214    214   
          215  +# Ticket [13f033c865f878953]
          216  +# If the outer loop must be a full table scan, do not let ANALYZE trick
          217  +# the planner into use a table for the outer loop that might be indexable
          218  +# if held until an inner loop.
          219  +# 
          220  +do_test where3-3.0 {
          221  +  execsql {
          222  +    CREATE TABLE t301(a INTEGER PRIMARY KEY,b,c);
          223  +    CREATE INDEX t301c ON t301(c);
          224  +    INSERT INTO t301 VALUES(1,2,3);
          225  +    CREATE TABLE t302(x, y);
          226  +    ANALYZE;
          227  +    explain query plan
          228  +    SELECT * FROM t302, t301 WHERE t302.x=5 AND t301.a=t302.y;
          229  +  }
          230  +} {0 0 {TABLE t302} 1 1 {TABLE t301 USING PRIMARY KEY}}
          231  +do_test where3-3.1 {
          232  +  execsql {
          233  +    explain query plan
          234  +    SELECT * FROM t301, t302 WHERE t302.x=5 AND t301.a=t302.y;
          235  +  }
          236  +} {0 1 {TABLE t302} 1 0 {TABLE t301 USING PRIMARY KEY}}
   215    237   
   216    238   finish_test