/ Check-in [3a72af2a]
Login

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

Overview
Comment:Make the MIN() and MAX() macros available in sqliteInt.h. Add TUNING comments to the NGQP and adjust costs slightly.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | nextgen-query-plan-exp
Files: files | file ages | folders
SHA1:3a72af2a95b04b8e195ef17cb3e9d9021a4f0915
User & Date: drh 2013-06-13 15:16:53
Context
2013-06-13
15:50
Restore the ability to do a BETWEEN query on the rowid. Also fix a nearby comment. check-in: 459a7b90 user: drh tags: nextgen-query-plan-exp
15:16
Make the MIN() and MAX() macros available in sqliteInt.h. Add TUNING comments to the NGQP and adjust costs slightly. check-in: 3a72af2a user: drh tags: nextgen-query-plan-exp
14:51
Fix an off-by-one error in the WhereCost to integer conversion. check-in: b5ca80d9 user: drh tags: nextgen-query-plan-exp
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/backup.c.

    11     11   *************************************************************************
    12     12   ** This file contains the implementation of the sqlite3_backup_XXX() 
    13     13   ** API functions and the related features.
    14     14   */
    15     15   #include "sqliteInt.h"
    16     16   #include "btreeInt.h"
    17     17   
    18         -/* Macro to find the minimum of two numeric values.
    19         -*/
    20         -#ifndef MIN
    21         -# define MIN(x,y) ((x)<(y)?(x):(y))
    22         -#endif
    23         -
    24     18   /*
    25     19   ** Structure allocated for each backup operation.
    26     20   */
    27     21   struct sqlite3_backup {
    28     22     sqlite3* pDestDb;        /* Destination database handle */
    29     23     Btree *pDest;            /* Destination b-tree file */
    30     24     u32 iDestSchema;         /* Original schema cookie in destination */

Changes to src/memjournal.c.

    27     27   ** The size chosen is a little less than a power of two.  That way,
    28     28   ** the FileChunk object will have a size that almost exactly fills
    29     29   ** a power-of-two allocation.  This mimimizes wasted space in power-of-two
    30     30   ** memory allocators.
    31     31   */
    32     32   #define JOURNAL_CHUNKSIZE ((int)(1024-sizeof(FileChunk*)))
    33     33   
    34         -/* Macro to find the minimum of two numeric values.
    35         -*/
    36         -#ifndef MIN
    37         -# define MIN(x,y) ((x)<(y)?(x):(y))
    38         -#endif
    39         -
    40     34   /*
    41     35   ** The rollback journal is composed of a linked list of these structures.
    42     36   */
    43     37   struct FileChunk {
    44     38     FileChunk *pNext;               /* Next chunk in the journal */
    45     39     u8 zChunk[JOURNAL_CHUNKSIZE];   /* Content of this chunk */
    46     40   };

Changes to src/os_win.c.

    80     80   
    81     81   /*
    82     82   ** This file mapping API is common to both Win32 and WinRT.
    83     83   */
    84     84   WINBASEAPI BOOL WINAPI UnmapViewOfFile(LPCVOID);
    85     85   #endif /* SQLITE_WIN32_FILEMAPPING_API && !defined(SQLITE_OMIT_WAL) */
    86     86   
    87         -/*
    88         -** Macro to find the minimum of two numeric values.
    89         -*/
    90         -#ifndef MIN
    91         -# define MIN(x,y) ((x)<(y)?(x):(y))
    92         -#endif
    93         -
    94     87   /*
    95     88   ** Some Microsoft compilers lack this definition.
    96     89   */
    97     90   #ifndef INVALID_FILE_ATTRIBUTES
    98     91   # define INVALID_FILE_ATTRIBUTES ((DWORD)-1) 
    99     92   #endif
   100     93   

Changes to src/sqliteInt.h.

   391    391   ** GCC does not define the offsetof() macro so we'll have to do it
   392    392   ** ourselves.
   393    393   */
   394    394   #ifndef offsetof
   395    395   #define offsetof(STRUCTURE,FIELD) ((int)((char*)&((STRUCTURE*)0)->FIELD))
   396    396   #endif
   397    397   
          398  +/*
          399  +** Macros to compute minimum and maximum of two numbers.
          400  +*/
          401  +#define MIN(A,B) ((A)<(B)?(A):(B))
          402  +#define MAX(A,B) ((A)>(B)?(A):(B))
          403  +
   398    404   /*
   399    405   ** Check to see if this machine uses EBCDIC.  (Yes, believe it or
   400    406   ** not, there are still machines out there that use EBCDIC.)
   401    407   */
   402    408   #if 'A' == '\301'
   403    409   # define SQLITE_EBCDIC 1
   404    410   #else

Changes to src/where.c.

    53     53   ** So all costs can be stored in a 16-bit unsigned integer without risk
    54     54   ** of overflow.
    55     55   **
    56     56   ** Costs are estimates, so don't go to the computational trouble to compute
    57     57   ** 10*log2(X) exactly.  Instead, a close estimate is used.  Any value of
    58     58   ** X<=1 is stored as 0.  X=2 is 10.  X=3 is 16.  X=1000 is 99. etc.
    59     59   **
           60  +** The tool/wherecosttest.c source file implements a command-line program
           61  +** that will convert between WhereCost to integers and do addition and
           62  +** multiplication on WhereCost values.  That command-line program is a
           63  +** useful utility to have around when working with this module.
    60     64   */
    61     65   typedef unsigned short int WhereCost;
    62     66   
    63     67   /*
    64     68   ** This object contains information needed to implement a single nestd
    65     69   ** loop in WHERE clause.
    66     70   **
................................................................................
  1897   1901     }
  1898   1902   }
  1899   1903   
  1900   1904   /*
  1901   1905   ** Convert an integer into a WhereCost.  In other words, compute a
  1902   1906   ** good approximatation for 10*log2(x).
  1903   1907   */
  1904         -static WhereCost whereCostFromInt(tRowcnt x){
         1908  +static WhereCost whereCost(tRowcnt x){
  1905   1909     static WhereCost a[] = { 0, 2, 3, 5, 6, 7, 8, 9 };
  1906   1910     WhereCost y = 40;
  1907   1911     if( x<8 ){
  1908   1912       if( x<2 ) return 0;
  1909   1913       while( x<8 ){  y -= 10; x <<= 1; }
  1910   1914     }else{
  1911   1915       while( x>255 ){ y += 40; x >>= 4; }
................................................................................
  1921   1925   ** 10*log2(x).
  1922   1926   */
  1923   1927   static WhereCost whereCostFromDouble(double x){
  1924   1928     u64 a;
  1925   1929     WhereCost e;
  1926   1930     assert( sizeof(x)==8 && sizeof(a)==8 );
  1927   1931     if( x<=1 ) return 0;
  1928         -  if( x<=2000000000 ) return whereCostFromInt((tRowcnt)x);
         1932  +  if( x<=2000000000 ) return whereCost((tRowcnt)x);
  1929   1933     memcpy(&a, &x, 8);
  1930   1934     e = (a>>52) - 1022;
  1931   1935     return e*10;
  1932   1936   }
  1933   1937   #endif /* SQLITE_OMIT_VIRTUALTABLE */
  1934   1938   
  1935   1939   /*
  1936   1940   ** Estimate the logarithm of the input value to base 2.
  1937   1941   */
  1938   1942   static WhereCost estLog(WhereCost N){
  1939         -  WhereCost x = whereCostFromInt(N);
         1943  +  WhereCost x = whereCost(N);
  1940   1944     return x>33 ? x - 33 : 0;
  1941   1945   }
  1942   1946   
  1943   1947   /*
  1944   1948   ** Two routines for printing the content of an sqlite3_index_info
  1945   1949   ** structure.  Used for testing and debugging only.  If neither
  1946   1950   ** SQLITE_TEST or SQLITE_DEBUG are defined, then these routines
................................................................................
  2594   2598         ){
  2595   2599           iUpper = a[0];
  2596   2600           if( (pUpper->eOperator & WO_LE)!=0 ) iUpper += a[1];
  2597   2601         }
  2598   2602         sqlite3ValueFree(pRangeVal);
  2599   2603       }
  2600   2604       if( rc==SQLITE_OK ){
  2601         -      WhereCost iBase = whereCostFromInt(p->aiRowEst[0]);
         2605  +      WhereCost iBase = whereCost(p->aiRowEst[0]);
  2602   2606         if( iUpper>iLower ){
  2603         -        iBase -= whereCostFromInt(iUpper - iLower);
         2607  +        iBase -= whereCost(iUpper - iLower);
  2604   2608         }
  2605   2609         *pRangeDiv = iBase;
  2606   2610         WHERETRACE(0x100, ("range scan regions: %u..%u  div=%d\n",
  2607   2611                            (u32)iLower, (u32)iUpper, *pRangeDiv));
  2608   2612         return SQLITE_OK;
  2609   2613       }
  2610   2614     }
................................................................................
  2611   2615   #else
  2612   2616     UNUSED_PARAMETER(pParse);
  2613   2617     UNUSED_PARAMETER(p);
  2614   2618     UNUSED_PARAMETER(nEq);
  2615   2619   #endif
  2616   2620     assert( pLower || pUpper );
  2617   2621     *pRangeDiv = 0;
         2622  +  /* TUNING:  Each inequality constraint reduces the search space 4-fold.
         2623  +  ** A BETWEEN operator, therefore, reduces the search space 16-fold */
  2618   2624     if( pLower && (pLower->wtFlags & TERM_VNULL)==0 ){
  2619         -    *pRangeDiv += 20;  assert( 20==whereCostFromInt(4) );
         2625  +    *pRangeDiv += 20;  assert( 20==whereCost(4) );
  2620   2626     }
  2621   2627     if( pUpper ){
  2622         -    *pRangeDiv += 20;  assert( 20==whereCostFromInt(4) );
         2628  +    *pRangeDiv += 20;  assert( 20==whereCost(4) );
  2623   2629     }
  2624   2630     return rc;
  2625   2631   }
  2626   2632   
  2627   2633   #ifdef SQLITE_ENABLE_STAT3
  2628   2634   /*
  2629   2635   ** Estimate the number of rows that will be returned based on
................................................................................
  4240   4246     }else{
  4241   4247       opMask = WO_EQ|WO_IN|WO_ISNULL|WO_GT|WO_GE|WO_LT|WO_LE;
  4242   4248     }
  4243   4249     if( pProbe->bUnordered ) opMask &= ~(WO_GT|WO_GE|WO_LT|WO_LE);
  4244   4250   
  4245   4251     if( pNew->u.btree.nEq < pProbe->nColumn ){
  4246   4252       iCol = pProbe->aiColumn[pNew->u.btree.nEq];
  4247         -    nRowEst = whereCostFromInt(pProbe->aiRowEst[pNew->u.btree.nEq+1]);
         4253  +    nRowEst = whereCost(pProbe->aiRowEst[pNew->u.btree.nEq+1]);
  4248   4254     }else{
  4249   4255       iCol = -1;
  4250   4256       nRowEst = 0;
  4251   4257     }
  4252   4258     pTerm = whereScanInit(&scan, pBuilder->pWC, pSrc->iCursor, iCol,
  4253   4259                           opMask, pProbe);
  4254   4260     saved_nEq = pNew->u.btree.nEq;
  4255   4261     saved_nLTerm = pNew->nLTerm;
  4256   4262     saved_wsFlags = pNew->wsFlags;
  4257   4263     saved_prereq = pNew->prereq;
  4258   4264     saved_nOut = pNew->nOut;
  4259   4265     pNew->rSetup = 0;
  4260         -  rLogSize = estLog(whereCostFromInt(pProbe->aiRowEst[0]));
         4266  +  rLogSize = estLog(whereCost(pProbe->aiRowEst[0]));
  4261   4267     for(; rc==SQLITE_OK && pTerm!=0; pTerm = whereScanNext(&scan)){
  4262   4268       int nIn = 0;
  4263   4269       if( pTerm->prereqRight & pNew->maskSelf ) continue;
  4264   4270       pNew->wsFlags = saved_wsFlags;
  4265   4271       pNew->u.btree.nEq = saved_nEq;
  4266   4272       pNew->nLTerm = saved_nLTerm;
  4267   4273       if( whereLoopResize(db, pNew, pNew->nLTerm+1) ) break; /* OOM */
  4268   4274       pNew->aLTerm[pNew->nLTerm++] = pTerm;
  4269   4275       pNew->prereq = (saved_prereq | pTerm->prereqRight) & ~pNew->maskSelf;
  4270         -    pNew->rRun = rLogSize;
         4276  +    pNew->rRun = rLogSize; /* Baseline cost is log2(N).  Adjustments below */
  4271   4277       if( pTerm->eOperator & WO_IN ){
  4272   4278         Expr *pExpr = pTerm->pExpr;
  4273   4279         pNew->wsFlags |= WHERE_COLUMN_IN;
  4274   4280         if( ExprHasProperty(pExpr, EP_xIsSelect) ){
  4275         -        /* "x IN (SELECT ...)":  Assume the SELECT returns 25 rows */
  4276         -        nIn = 46;  assert( 46==whereCostFromInt(25) );
         4281  +        /* "x IN (SELECT ...)":  TUNING: the SELECT returns 25 rows */
         4282  +        nIn = 46;  assert( 46==whereCost(25) );
  4277   4283         }else if( ALWAYS(pExpr->x.pList && pExpr->x.pList->nExpr) ){
  4278   4284           /* "x IN (value, value, ...)" */
  4279         -        nIn = whereCostFromInt(pExpr->x.pList->nExpr);
         4285  +        nIn = whereCost(pExpr->x.pList->nExpr);
  4280   4286         }
  4281   4287         pNew->rRun += nIn;
  4282   4288         pNew->u.btree.nEq++;
  4283   4289         pNew->nOut = nRowEst + nInMul + nIn;
  4284   4290       }else if( pTerm->eOperator & (WO_EQ) ){
  4285   4291         assert( (pNew->wsFlags & (WHERE_COLUMN_NULL|WHERE_COLUMN_IN))!=0
  4286   4292                     || nInMul==0 );
................................................................................
  4293   4299           pNew->wsFlags |= WHERE_ONEROW;
  4294   4300         }
  4295   4301         pNew->u.btree.nEq++;
  4296   4302         pNew->nOut = nRowEst + nInMul;
  4297   4303       }else if( pTerm->eOperator & (WO_ISNULL) ){
  4298   4304         pNew->wsFlags |= WHERE_COLUMN_NULL;
  4299   4305         pNew->u.btree.nEq++;
  4300         -      nIn = 10;  assert( 10==whereCostFromInt(2) );
         4306  +      /* TUNING: IS NULL selects 2 rows */
         4307  +      nIn = 10;  assert( 10==whereCost(2) );
  4301   4308         pNew->nOut = nRowEst + nInMul + nIn;
  4302   4309       }else if( pTerm->eOperator & (WO_GT|WO_GE) ){
  4303   4310         pNew->wsFlags |= WHERE_COLUMN_RANGE|WHERE_BTM_LIMIT;
  4304   4311         pBtm = pTerm;
  4305   4312         pTop = 0;
  4306   4313       }else if( pTerm->eOperator & (WO_LT|WO_LE) ){
  4307   4314         pNew->wsFlags |= WHERE_COLUMN_RANGE|WHERE_TOP_LIMIT;
................................................................................
  4321   4328         tRowcnt nOut = 0;
  4322   4329         if( (pTerm->eOperator & (WO_EQ|WO_ISNULL))!=0 ){
  4323   4330           rc = whereEqualScanEst(pParse, pProbe, pTerm->pExpr->pRight, &nOut);
  4324   4331         }else if( (pTerm->eOperator & WO_IN)
  4325   4332                &&  !ExprHasProperty(pTerm->pExpr, EP_xIsSelect)  ){
  4326   4333           rc = whereInScanEst(pParse, pProbe, pTerm->pExpr->x.pList, &nOut);
  4327   4334         }
  4328         -      pNew->nOut = whereCostFromInt(nOut);
         4335  +      pNew->nOut = whereCost(nOut);
  4329   4336       }
  4330   4337   #endif
  4331   4338       if( (pNew->wsFlags & (WHERE_IDX_ONLY|WHERE_IPK))==0 ){
  4332   4339         /* Each row involves a step of the index, then a binary search of
  4333   4340         ** the main table */
  4334   4341         pNew->rRun =  whereCostAdd(pNew->rRun, rLogSize>27 ? rLogSize-17 : 10);
  4335   4342       }
................................................................................
  4447   4454       if( pSrc->notIndexed==0 ){
  4448   4455         /* The real indices of the table are only considered if the
  4449   4456         ** NOT INDEXED qualifier is omitted from the FROM clause */
  4450   4457         sPk.pNext = pFirst;
  4451   4458       }
  4452   4459       pProbe = &sPk;
  4453   4460     }
  4454         -  rSize = whereCostFromInt(pSrc->pTab->nRowEst);
         4461  +  rSize = whereCost(pSrc->pTab->nRowEst);
  4455   4462     rLogSize = estLog(rSize);
  4456   4463   
  4457   4464     /* Automatic indexes */
  4458   4465     if( !pBuilder->pBest
  4459   4466      && (pWInfo->pParse->db->flags & SQLITE_AutoIndex)!=0
  4460   4467      && pSrc->pIndex==0
  4461   4468      && !pSrc->viaCoroutine
................................................................................
  4469   4476       for(pTerm=pWC->a; rc==SQLITE_OK && pTerm<pWCEnd; pTerm++){
  4470   4477         if( pTerm->prereqRight & pNew->maskSelf ) continue;
  4471   4478         if( termCanDriveIndex(pTerm, pSrc, 0) ){
  4472   4479           pNew->u.btree.nEq = 1;
  4473   4480           pNew->u.btree.pIndex = 0;
  4474   4481           pNew->nLTerm = 1;
  4475   4482           pNew->aLTerm[0] = pTerm;
  4476         -        assert( 43==whereCostFromInt(20) );
  4477         -        pNew->rSetup = 43 + rLogSize + rSize;
  4478         -        pNew->nOut = 33;  assert( 33==whereCostFromInt(10) );
         4483  +        /* TUNING: One-time cost for computing the automatic index is
         4484  +        ** approximately 6*N*log2(N) where N is the number of rows in
         4485  +        ** the table being indexed. */
         4486  +        pNew->rSetup = rLogSize + rSize + 26;  assert( 26==whereCost(6) );
         4487  +        /* TUNING: Each index lookup yields 10 rows in the table */
         4488  +        pNew->nOut = 33;  assert( 33==whereCost(10) );
  4479   4489           pNew->rRun = whereCostAdd(rLogSize,pNew->nOut);
  4480   4490           pNew->wsFlags = WHERE_TEMP_INDEX;
  4481   4491           pNew->prereq = mExtra | pTerm->prereqRight;
  4482   4492           rc = whereLoopInsert(pBuilder, pNew);
  4483   4493         }
  4484   4494       }
  4485   4495     }
................................................................................
  4497   4507       if( pProbe->tnum<=0 ){
  4498   4508         /* Integer primary key index */
  4499   4509         pNew->wsFlags = WHERE_IPK;
  4500   4510   
  4501   4511         /* Full table scan */
  4502   4512         pNew->iSortIdx = b ? iSortIdx : 0;
  4503   4513         pNew->nOut = rSize;
  4504         -      pNew->rRun = whereCostAdd(rSize,rLogSize) + 16 - b;
         4514  +      /* TUNING: Cost of full table scan is 3*(N + log2(N)).
         4515  +      **  +  The extra 3 factor is to encourage the use of indexed lookups
         4516  +      **     over full scans.  A smaller constant 2 is used for covering
         4517  +      **     index scans so that a covering index scan will be favored over
         4518  +      **     a table scan. */
         4519  +      pNew->rRun = whereCostAdd(rSize,rLogSize) + 16;
  4505   4520         rc = whereLoopInsert(pBuilder, pNew);
  4506   4521         if( rc ) break;
  4507   4522       }else{
  4508   4523         Bitmask m = pSrc->colUsed & ~columnsInIndex(pProbe);
  4509   4524         pNew->wsFlags = (m==0) ? (WHERE_IDX_ONLY|WHERE_INDEXED) : WHERE_INDEXED;
  4510   4525   
  4511   4526         /* Full scan via index */
................................................................................
  4513   4528          && pProbe->bUnordered==0
  4514   4529          && (pWInfo->wctrlFlags & WHERE_ONEPASS_DESIRED)==0
  4515   4530          && sqlite3GlobalConfig.bUseCis
  4516   4531          && OptimizationEnabled(pWInfo->pParse->db, SQLITE_CoverIdxScan)
  4517   4532         ){
  4518   4533           pNew->iSortIdx = b ? iSortIdx : 0;
  4519   4534           pNew->nOut = rSize;
  4520         -        pNew->rRun = whereCostAdd(rSize,rLogSize);
  4521         -        pNew->rRun += ((m!=0) ? rLogSize : 10) - b;
         4535  +        if( m==0 ){
         4536  +          /* TUNING: Cost of a covering index scan is 2*(N + log2(N)).
         4537  +          **  +  The extra 2 factor is to encourage the use of indexed lookups
         4538  +          **     over index scans.  A table scan uses a factor of 3 so that
         4539  +          **     index scans are favored over table scans.
         4540  +          **  +  If this covering index might also help satisfy the ORDER BY
         4541  +          **     clause, then the cost is fudged down slightly so that this
         4542  +          **     index is favored above other indices that have no hope of
         4543  +          **     helping with the ORDER BY. */
         4544  +          pNew->rRun = 10 + whereCostAdd(rSize,rLogSize) - b;
         4545  +        }else{
         4546  +          assert( b!=0 ); 
         4547  +          /* TUNING: Cost of scanning a non-covering index is (N+1)*log2(N)
         4548  +          ** which we will simplify to just N*log2(N) */
         4549  +          pNew->rRun = rSize + rLogSize;
         4550  +        }
  4522   4551           rc = whereLoopInsert(pBuilder, pNew);
  4523   4552           if( rc ) break;
  4524   4553         }
  4525   4554       }
  4526   4555       rc = whereLoopAddBtreeIndex(pBuilder, pSrc, pProbe, 0);
  4527   4556   
  4528   4557       /* If there was an INDEXED BY clause, then only that one index is
................................................................................
  4671   4700         pNew->u.vtab.needFree = pIdxInfo->needToFreeIdxStr;
  4672   4701         pIdxInfo->needToFreeIdxStr = 0;
  4673   4702         pNew->u.vtab.idxStr = pIdxInfo->idxStr;
  4674   4703         pNew->u.vtab.isOrdered = (u8)((pIdxInfo->nOrderBy!=0)
  4675   4704                                        && pIdxInfo->orderByConsumed);
  4676   4705         pNew->rSetup = 0;
  4677   4706         pNew->rRun = whereCostFromDouble(pIdxInfo->estimatedCost);
  4678         -      pNew->nOut = 46;  assert( 46 == whereCostFromInt(25) );
         4707  +      /* TUNING: Every virtual table query returns 25 rows */
         4708  +      pNew->nOut = 46;  assert( 46==whereCost(25) );
  4679   4709         whereLoopInsert(pBuilder, pNew);
  4680   4710         if( pNew->u.vtab.needFree ){
  4681   4711           sqlite3_free(pNew->u.vtab.idxStr);
  4682   4712           pNew->u.vtab.needFree = 0;
  4683   4713         }
  4684   4714       }
  4685   4715     }  
................................................................................
  5062   5092   **
  5063   5093   ** Return SQLITE_OK on success or SQLITE_NOMEM of a memory allocation
  5064   5094   ** error occurs.
  5065   5095   */
  5066   5096   static int wherePathSolver(WhereInfo *pWInfo, WhereCost nRowEst){
  5067   5097     int mxChoice;             /* Maximum number of simultaneous paths tracked */
  5068   5098     int nLoop;                /* Number of terms in the join */
         5099  +  Parse *pParse;            /* Parsing context */
  5069   5100     sqlite3 *db;              /* The database connection */
  5070   5101     int iLoop;                /* Loop counter over the terms of the join */
  5071   5102     int ii, jj;               /* Loop counters */
  5072   5103     WhereCost rCost;             /* Cost of a path */
  5073   5104     WhereCost mxCost;            /* Maximum cost of a set of paths */
  5074   5105     WhereCost rSortCost;         /* Cost to do a sort */
  5075   5106     int nTo, nFrom;           /* Number of valid entries in aTo[] and aFrom[] */
................................................................................
  5077   5108     WherePath *aTo;           /* The nTo best paths at the current level */
  5078   5109     WherePath *pFrom;         /* An element of aFrom[] that we are working on */
  5079   5110     WherePath *pTo;           /* An element of aTo[] that we are working on */
  5080   5111     WhereLoop *pWLoop;        /* One of the WhereLoop objects */
  5081   5112     WhereLoop **pX;           /* Used to divy up the pSpace memory */
  5082   5113     char *pSpace;             /* Temporary memory used by this routine */
  5083   5114   
  5084         -  db = pWInfo->pParse->db;
         5115  +  pParse = pWInfo->pParse;
         5116  +  db = pParse->db;
  5085   5117     nLoop = pWInfo->nLevel;
         5118  +  /* TUNING: For simple queries, only the best path is tracked.
         5119  +  ** For 2-way joins, the 5 best paths are followed.
         5120  +  ** For joins of 3 or more tables, track the 10 best paths */
  5086   5121     mxChoice = (nLoop==1) ? 1 : (nLoop==2 ? 5 : 10);
  5087   5122     assert( nLoop<=pWInfo->pTabList->nSrc );
  5088   5123     WHERETRACE(0x002, ("---- begin solver\n"));
  5089   5124   
  5090   5125     /* Allocate and initialize space for aTo and aFrom */
  5091   5126     ii = (sizeof(WherePath)+sizeof(WhereLoop*)*nLoop)*mxChoice*2;
  5092   5127     pSpace = sqlite3DbMallocRaw(db, ii);
................................................................................
  5095   5130     aFrom = aTo+mxChoice;
  5096   5131     memset(aFrom, 0, sizeof(aFrom[0]));
  5097   5132     pX = (WhereLoop**)(aFrom+mxChoice);
  5098   5133     for(ii=mxChoice*2, pFrom=aTo; ii>0; ii--, pFrom++, pX += nLoop){
  5099   5134       pFrom->aLoop = pX;
  5100   5135     }
  5101   5136   
  5102         -  /* Seed the search with a single WherePath containing zero WhereLoops */
  5103         -  aFrom[0].nRow = pWInfo->pParse->nQueryLoop;
         5137  +  /* Seed the search with a single WherePath containing zero WhereLoops.
         5138  +  **
         5139  +  ** TUNING: Do not let the number of iterations go above 25.  If the cost
         5140  +  ** of computing an automatic index is not paid back within the first 25
         5141  +  ** rows, then do not use the automatic index. */
         5142  +  aFrom[0].nRow = MIN(pParse->nQueryLoop, 46);  assert( 46==whereCost(25) );
  5104   5143     nFrom = 1;
  5105   5144   
  5106   5145     /* Precompute the cost of sorting the final result set, if the caller
  5107   5146     ** to sqlite3WhereBegin() was concerned about sorting */
  5108   5147     rSortCost = 0;
  5109   5148     if( pWInfo->pOrderBy==0 || nRowEst==0 ){
  5110   5149       aFrom[0].isOrderedValid = 1;
  5111   5150     }else{
  5112         -    /* Compute an estimate on the cost to sort the entire result set */
         5151  +    /* TUNING: Estimated cost of sorting is N*log2(N) where N is the
         5152  +    ** number of output rows. */
  5113   5153       rSortCost = nRowEst + estLog(nRowEst);
  5114   5154       WHERETRACE(0x002,("---- sort cost=%-3d\n", rSortCost));
  5115   5155     }
  5116   5156   
  5117   5157     /* Compute successively longer WherePaths using the previous generation
  5118   5158     ** of WherePaths as the basis for the next.  Keep track of the mxChoice
  5119   5159     ** best paths at each generation */
................................................................................
  5250   5290       pFrom = aTo;
  5251   5291       aTo = aFrom;
  5252   5292       aFrom = pFrom;
  5253   5293       nFrom = nTo;
  5254   5294     }
  5255   5295   
  5256   5296     if( nFrom==0 ){
  5257         -    sqlite3ErrorMsg(pWInfo->pParse, "no query solution");
         5297  +    sqlite3ErrorMsg(pParse, "no query solution");
  5258   5298       sqlite3DbFree(db, pSpace);
  5259   5299       return SQLITE_ERROR;
  5260   5300     }
  5261   5301     
  5262   5302     /* Find the lowest cost path.  pFrom will be left pointing to that path */
  5263   5303     pFrom = aFrom;
  5264   5304     for(ii=1; ii<nFrom; ii++){
................................................................................
  5331   5371     pLoop->wsFlags = 0;
  5332   5372     pTerm = findTerm(pWC, iCur, -1, 0, WO_EQ, 0);
  5333   5373     if( pTerm ){
  5334   5374       pLoop->wsFlags = WHERE_COLUMN_EQ|WHERE_IPK|WHERE_ONEROW;
  5335   5375       pLoop->aLTerm[0] = pTerm;
  5336   5376       pLoop->nLTerm = 1;
  5337   5377       pLoop->u.btree.nEq = 1;
  5338         -    pLoop->rRun = 33;  /* 33 == whereCostFromInt(10) */
         5378  +    /* TUNING: Cost of a rowid lookup is 10 */
         5379  +    pLoop->rRun = 33;  /* 33==whereCost(10) */
  5339   5380     }else{
  5340   5381       for(pIdx=pTab->pIndex; pIdx; pIdx=pIdx->pNext){
  5341   5382         if( pIdx->onError==OE_None ) continue;
  5342   5383         for(j=0; j<pIdx->nColumn; j++){
  5343   5384           pTerm = findTerm(pWC, iCur, pIdx->aiColumn[j], 0, WO_EQ, pIdx);
  5344   5385           if( pTerm==0 ) break;
  5345   5386           whereLoopResize(pWInfo->pParse->db, pLoop, j);
................................................................................
  5349   5390         pLoop->wsFlags = WHERE_COLUMN_EQ|WHERE_ONEROW|WHERE_INDEXED;
  5350   5391         if( (pItem->colUsed & ~columnsInIndex(pIdx))==0 ){
  5351   5392           pLoop->wsFlags |= WHERE_IDX_ONLY;
  5352   5393         }
  5353   5394         pLoop->nLTerm = j;
  5354   5395         pLoop->u.btree.nEq = j;
  5355   5396         pLoop->u.btree.pIndex = pIdx;
  5356         -      pLoop->rRun = 39;  /* 39 == whereCostFromInt(15) */
         5397  +      /* TUNING: Cost of a unique index lookup is 15 */
         5398  +      pLoop->rRun = 39;  /* 39==whereCost(15) */
  5357   5399         break;
  5358   5400       }
  5359   5401     }
  5360   5402     if( pLoop->wsFlags ){
  5361   5403       pLoop->nOut = (WhereCost)1;
  5362   5404       pWInfo->a[0].pWLoop = pLoop;
  5363   5405       pLoop->maskSelf = getMask(&pWInfo->sMaskSet, iCur);

Changes to test/autoindex1.test.

    74     74   } {35}
    75     75   do_test autoindex1-202 {
    76     76     db status autoindex
    77     77   } {0}
    78     78   do_test autoindex1-210 {
    79     79     db eval {
    80     80       PRAGMA automatic_index=ON;
           81  +    ANALYZE;
           82  +    UPDATE sqlite_stat1 SET stat='10000' WHERE tbl='t1';
           83  +    ANALYZE sqlite_master;
    81     84       SELECT b, (SELECT d FROM t2 WHERE c=a) FROM t1;
    82     85     }
    83     86   } {11 911 22 922 33 933 44 944 55 955 66 966 77 977 88 988}
    84     87   do_test autoindex1-211 {
    85     88     db status step
    86     89   } {7}
    87     90   do_test autoindex1-212 {
................................................................................
   139    142   # Ticket [8011086c85c6c404014c947fcf3eb9f42b184a0d] from 2010-07-08
   140    143   # Make sure automatic indices are not created for the RHS of an IN expression
   141    144   # that is not a correlated subquery.
   142    145   #
   143    146   do_execsql_test autoindex1-500 {
   144    147     CREATE TABLE t501(a INTEGER PRIMARY KEY, b);
   145    148     CREATE TABLE t502(x INTEGER PRIMARY KEY, y);
          149  +  INSERT INTO sqlite_stat1(tbl,idx,stat) VALUES('t501',null,'1000000');
          150  +  INSERT INTO sqlite_stat1(tbl,idx,stat) VALUES('t502',null,'1000');
          151  +  ANALYZE sqlite_master;
   146    152     EXPLAIN QUERY PLAN
   147    153     SELECT b FROM t501
   148    154      WHERE t501.a IN (SELECT x FROM t502 WHERE y=?);
   149    155   } {
   150    156     0 0 0 {SEARCH TABLE t501 USING INTEGER PRIMARY KEY (rowid=?)} 
   151    157     0 0 0 {EXECUTE LIST SUBQUERY 1} 
   152    158     1 0 0 {SCAN TABLE t502}