/ Check-in [86a06dd0]
Login

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

Overview
Comment:Merge the accidental fork.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 86a06dd0494c2fe83d4fde517557600956cedd9e
User & Date: drh 2009-08-13 15:42:52
References
2010-12-06
16:01 New ticket [80ba2010] Bug involving subqueries and the OR optimization. artifact: 4cebcddb user: dan
Context
2009-08-13
17:14
Add a test case for the affinity problem reported by ticket [93fb9f89d6]. check-in: 149ec24e user: drh tags: trunk
15:42
Merge the accidental fork. check-in: 86a06dd0 user: drh tags: trunk
15:13
Fix a typo on a comment in sqlite3VdbeIntegerAffinity(). check-in: b5a709d3 user: drh tags: trunk
07:09
Changes to the query planner that improve the order in which tables/indexes are scanned in join queries. check-in: 19f799b3 user: dan tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/os_win.c.

   305    305   {
   306    306     static struct tm y;
   307    307     FILETIME uTm, lTm;
   308    308     SYSTEMTIME pTm;
   309    309     sqlite3_int64 t64;
   310    310     t64 = *t;
   311    311     t64 = (t64 + 11644473600)*10000000;
   312         -  uTm.dwLowDateTime = t64 & 0xFFFFFFFF;
   313         -  uTm.dwHighDateTime= t64 >> 32;
          312  +  uTm.dwLowDateTime = (DWORD)(t64 & 0xFFFFFFFF);
          313  +  uTm.dwHighDateTime= (DWORD)(t64 >> 32);
   314    314     FileTimeToLocalFileTime(&uTm,&lTm);
   315    315     FileTimeToSystemTime(&lTm,&pTm);
   316    316     y.tm_year = pTm.wYear - 1900;
   317    317     y.tm_mon = pTm.wMonth - 1;
   318    318     y.tm_wday = pTm.wDayOfWeek;
   319    319     y.tm_mday = pTm.wDay;
   320    320     y.tm_hour = pTm.wHour;
................................................................................
   326    326   /* This will never be called, but defined to make the code compile */
   327    327   #define GetTempPathA(a,b)
   328    328   
   329    329   #define LockFile(a,b,c,d,e)       winceLockFile(&a, b, c, d, e)
   330    330   #define UnlockFile(a,b,c,d,e)     winceUnlockFile(&a, b, c, d, e)
   331    331   #define LockFileEx(a,b,c,d,e,f)   winceLockFileEx(&a, b, c, d, e, f)
   332    332   
   333         -#define HANDLE_TO_WINFILE(a) (winFile*)&((char*)a)[-offsetof(winFile,h)]
          333  +#define HANDLE_TO_WINFILE(a) (winFile*)&((char*)a)[-(int)offsetof(winFile,h)]
   334    334   
   335    335   /*
   336    336   ** Acquire a lock on the handle h
   337    337   */
   338    338   static void winceMutexAcquire(HANDLE h){
   339    339      DWORD dwErr;
   340    340      do {
................................................................................
   465    465     DWORD dwFileOffsetHigh,
   466    466     DWORD nNumberOfBytesToLockLow,
   467    467     DWORD nNumberOfBytesToLockHigh
   468    468   ){
   469    469     winFile *pFile = HANDLE_TO_WINFILE(phFile);
   470    470     BOOL bReturn = FALSE;
   471    471   
          472  +  UNUSED_PARAMETER(dwFileOffsetHigh);
          473  +  UNUSED_PARAMETER(nNumberOfBytesToLockHigh);
          474  +
   472    475     if (!pFile->hMutex) return TRUE;
   473    476     winceMutexAcquire(pFile->hMutex);
   474    477   
   475    478     /* Wanting an exclusive lock? */
   476    479     if (dwFileOffsetLow == SHARED_FIRST
   477    480          && nNumberOfBytesToLockLow == SHARED_SIZE){
   478    481       if (pFile->shared->nReaders == 0 && pFile->shared->bExclusive == 0){
................................................................................
   526    529     DWORD dwFileOffsetHigh,
   527    530     DWORD nNumberOfBytesToUnlockLow,
   528    531     DWORD nNumberOfBytesToUnlockHigh
   529    532   ){
   530    533     winFile *pFile = HANDLE_TO_WINFILE(phFile);
   531    534     BOOL bReturn = FALSE;
   532    535   
          536  +  UNUSED_PARAMETER(dwFileOffsetHigh);
          537  +  UNUSED_PARAMETER(nNumberOfBytesToUnlockHigh);
          538  +
   533    539     if (!pFile->hMutex) return TRUE;
   534    540     winceMutexAcquire(pFile->hMutex);
   535    541   
   536    542     /* Releasing a reader lock or an exclusive lock */
   537         -  if (dwFileOffsetLow >= SHARED_FIRST &&
   538         -       dwFileOffsetLow < SHARED_FIRST + SHARED_SIZE){
          543  +  if (dwFileOffsetLow == SHARED_FIRST){
   539    544       /* Did we have an exclusive lock? */
   540    545       if (pFile->local.bExclusive){
          546  +      assert(nNumberOfBytesToUnlockLow == SHARED_SIZE);
   541    547         pFile->local.bExclusive = FALSE;
   542    548         pFile->shared->bExclusive = FALSE;
   543    549         bReturn = TRUE;
   544    550       }
   545    551   
   546    552       /* Did we just have a reader lock? */
   547    553       else if (pFile->local.nReaders){
          554  +      assert(nNumberOfBytesToUnlockLow == 1);
   548    555         pFile->local.nReaders --;
   549    556         if (pFile->local.nReaders == 0)
   550    557         {
   551    558           pFile->shared->nReaders --;
   552    559         }
   553    560         bReturn = TRUE;
   554    561       }
................................................................................
   582    589     HANDLE *phFile,
   583    590     DWORD dwFlags,
   584    591     DWORD dwReserved,
   585    592     DWORD nNumberOfBytesToLockLow,
   586    593     DWORD nNumberOfBytesToLockHigh,
   587    594     LPOVERLAPPED lpOverlapped
   588    595   ){
          596  +  UNUSED_PARAMETER(dwReserved);
          597  +  UNUSED_PARAMETER(nNumberOfBytesToLockHigh);
          598  +
   589    599     /* If the caller wants a shared read lock, forward this call
   590    600     ** to winceLockFile */
   591    601     if (lpOverlapped->Offset == SHARED_FIRST &&
   592    602         dwFlags == 1 &&
   593    603         nNumberOfBytesToLockLow == SHARED_SIZE){
   594    604       return winceLockFile(phFile, SHARED_FIRST, 0, 1, 0);
   595    605     }
................................................................................
  1588   1598   ** file.
  1589   1599   */
  1590   1600   static int getSectorSize(
  1591   1601       sqlite3_vfs *pVfs,
  1592   1602       const char *zRelative     /* UTF-8 file name */
  1593   1603   ){
  1594   1604     DWORD bytesPerSector = SQLITE_DEFAULT_SECTOR_SIZE;
         1605  +  /* GetDiskFreeSpace is not supported under WINCE */
         1606  +#if SQLITE_OS_WINCE
         1607  +  UNUSED_PARAMETER(pVfs);
         1608  +  UNUSED_PARAMETER(zRelative);
         1609  +#else
  1595   1610     char zFullpath[MAX_PATH+1];
  1596   1611     int rc;
  1597         -  DWORD dwRet = 0, dwDummy;
         1612  +  DWORD dwRet = 0;
         1613  +  DWORD dwDummy;
  1598   1614   
  1599   1615     /*
  1600   1616     ** We need to get the full path name of the file
  1601   1617     ** to get the drive letter to look up the sector
  1602   1618     ** size.
  1603   1619     */
  1604   1620     rc = winFullPathname(pVfs, zRelative, MAX_PATH, zFullpath);
................................................................................
  1616   1632             }
  1617   1633           }
  1618   1634           dwRet = GetDiskFreeSpaceW((WCHAR*)zConverted,
  1619   1635                                     &dwDummy,
  1620   1636                                     &bytesPerSector,
  1621   1637                                     &dwDummy,
  1622   1638                                     &dwDummy);
  1623         -#if SQLITE_OS_WINCE==0
  1624   1639         }else{
  1625   1640           /* trim path to just drive reference */
  1626   1641           CHAR *p = (CHAR *)zConverted;
  1627   1642           for(;*p;p++){
  1628   1643             if( *p == '\\' ){
  1629   1644               *p = '\0';
  1630   1645               break;
................................................................................
  1631   1646             }
  1632   1647           }
  1633   1648           dwRet = GetDiskFreeSpaceA((CHAR*)zConverted,
  1634   1649                                     &dwDummy,
  1635   1650                                     &bytesPerSector,
  1636   1651                                     &dwDummy,
  1637   1652                                     &dwDummy);
  1638         -#endif
  1639   1653         }
  1640   1654         free(zConverted);
  1641   1655       }
  1642   1656       if( !dwRet ){
  1643   1657         bytesPerSector = SQLITE_DEFAULT_SECTOR_SIZE;
  1644   1658       }
  1645   1659     }
         1660  +#endif
  1646   1661     return (int) bytesPerSector; 
  1647   1662   }
  1648   1663   
  1649   1664   #ifndef SQLITE_OMIT_LOAD_EXTENSION
  1650   1665   /*
  1651   1666   ** Interfaces for opening a shared library, finding entry points
  1652   1667   ** within the shared library, and closing the shared library.

Changes to src/sqliteInt.h.

    12     12   ** Internal interface definitions for SQLite.
    13     13   **
    14     14   ** @(#) $Id: sqliteInt.h,v 1.898 2009/08/10 03:57:58 shane Exp $
    15     15   */
    16     16   #ifndef _SQLITEINT_H_
    17     17   #define _SQLITEINT_H_
    18     18   
           19  +/*
           20  +** These #defines should enable >2GB file support on POSIX if the
           21  +** underlying operating system supports it.  If the OS lacks
           22  +** large file support, or if the OS is windows, these should be no-ops.
           23  +**
           24  +** Ticket #2739:  The _LARGEFILE_SOURCE macro must appear before any
           25  +** system #includes.  Hence, this block of code must be the very first
           26  +** code in all source files.
           27  +**
           28  +** Large file support can be disabled using the -DSQLITE_DISABLE_LFS switch
           29  +** on the compiler command line.  This is necessary if you are compiling
           30  +** on a recent machine (ex: Red Hat 7.2) but you want your code to work
           31  +** on an older machine (ex: Red Hat 6.0).  If you compile on Red Hat 7.2
           32  +** without this option, LFS is enable.  But LFS does not exist in the kernel
           33  +** in Red Hat 6.0, so the code won't work.  Hence, for maximum binary
           34  +** portability you should omit LFS.
           35  +**
           36  +** Similar is true for Mac OS X.  LFS is only supported on Mac OS X 9 and later.
           37  +*/
           38  +#ifndef SQLITE_DISABLE_LFS
           39  +# define _LARGE_FILE       1
           40  +# ifndef _FILE_OFFSET_BITS
           41  +#   define _FILE_OFFSET_BITS 64
           42  +# endif
           43  +# define _LARGEFILE_SOURCE 1
           44  +#endif
           45  +
    19     46   /*
    20     47   ** Include the configuration header output by 'configure' if we're using the
    21     48   ** autoconf-based build
    22     49   */
    23     50   #ifdef _HAVE_SQLITE_CONFIG_H
    24     51   #include "config.h"
    25     52   #endif
................................................................................
    78    105   #   define SQLITE_PTR_TO_INT(X)  ((int)(X))
    79    106   # endif
    80    107   #else
    81    108   # define SQLITE_INT_TO_PTR(X)   ((void*)&((char*)0)[X])
    82    109   # define SQLITE_PTR_TO_INT(X)   ((int)(((char*)X)-(char*)0))
    83    110   #endif
    84    111   
    85         -/*
    86         -** These #defines should enable >2GB file support on POSIX if the
    87         -** underlying operating system supports it.  If the OS lacks
    88         -** large file support, or if the OS is windows, these should be no-ops.
    89         -**
    90         -** Ticket #2739:  The _LARGEFILE_SOURCE macro must appear before any
    91         -** system #includes.  Hence, this block of code must be the very first
    92         -** code in all source files.
    93         -**
    94         -** Large file support can be disabled using the -DSQLITE_DISABLE_LFS switch
    95         -** on the compiler command line.  This is necessary if you are compiling
    96         -** on a recent machine (ex: Red Hat 7.2) but you want your code to work
    97         -** on an older machine (ex: Red Hat 6.0).  If you compile on Red Hat 7.2
    98         -** without this option, LFS is enable.  But LFS does not exist in the kernel
    99         -** in Red Hat 6.0, so the code won't work.  Hence, for maximum binary
   100         -** portability you should omit LFS.
   101         -**
   102         -** Similar is true for Mac OS X.  LFS is only supported on Mac OS X 9 and later.
   103         -*/
   104         -#ifndef SQLITE_DISABLE_LFS
   105         -# define _LARGE_FILE       1
   106         -# ifndef _FILE_OFFSET_BITS
   107         -#   define _FILE_OFFSET_BITS 64
   108         -# endif
   109         -# define _LARGEFILE_SOURCE 1
   110         -#endif
   111         -
   112    112   
   113    113   /*
   114    114   ** The SQLITE_THREADSAFE macro must be defined as either 0 or 1.
   115    115   ** Older versions of SQLite used an optional THREADSAFE macro.
   116    116   ** We support that for legacy
   117    117   */
   118    118   #if !defined(SQLITE_THREADSAFE)

Changes to src/where.c.

   191    191   ** A WhereCost object records a lookup strategy and the estimated
   192    192   ** cost of pursuing that strategy.
   193    193   */
   194    194   struct WhereCost {
   195    195     WherePlan plan;    /* The lookup strategy */
   196    196     double rCost;      /* Overall cost of pursuing this search strategy */
   197    197     double nRow;       /* Estimated number of output rows */
          198  +  Bitmask used;      /* Bitmask of cursors used by this plan */
   198    199   };
   199    200   
   200    201   /*
   201    202   ** Bitmasks for the operators that indices are able to exploit.  An
   202    203   ** OR-ed combination of these values can be used when searching for
   203    204   ** terms in the where clause.
   204    205   */
................................................................................
  1334   1335     struct ExprList_item *pTerm;    /* A term of the ORDER BY clause */
  1335   1336     sqlite3 *db = pParse->db;
  1336   1337   
  1337   1338     assert( pOrderBy!=0 );
  1338   1339     nTerm = pOrderBy->nExpr;
  1339   1340     assert( nTerm>0 );
  1340   1341   
         1342  +  /* Argument pIdx must either point to a 'real' named index structure, 
         1343  +  ** or an index structure allocated on the stack by bestBtreeIndex() to
         1344  +  ** represent the rowid index that is part of every table.  */
         1345  +  assert( pIdx->zName || (pIdx->nColumn==1 && pIdx->aiColumn[0]==-1) );
         1346  +
  1341   1347     /* Match terms of the ORDER BY clause against columns of
  1342   1348     ** the index.
  1343   1349     **
  1344   1350     ** Note that indices have pIdx->nColumn regular columns plus
  1345   1351     ** one additional column containing the rowid.  The rowid column
  1346   1352     ** of the index is also allowed to match against the ORDER BY
  1347   1353     ** clause.
................................................................................
  1360   1366         ** left-most table of the FROM clause */
  1361   1367         break;
  1362   1368       }
  1363   1369       pColl = sqlite3ExprCollSeq(pParse, pExpr);
  1364   1370       if( !pColl ){
  1365   1371         pColl = db->pDfltColl;
  1366   1372       }
  1367         -    if( i<pIdx->nColumn ){
         1373  +    if( pIdx->zName && i<pIdx->nColumn ){
  1368   1374         iColumn = pIdx->aiColumn[i];
  1369   1375         if( iColumn==pIdx->pTable->iPKey ){
  1370   1376           iColumn = -1;
  1371   1377         }
  1372   1378         iSortOrder = pIdx->aSortOrder[i];
  1373   1379         zColl = pIdx->azColl[i];
  1374   1380       }else{
................................................................................
  1389   1395         }else{
  1390   1396           /* If an index column fails to match and is not constrained by ==
  1391   1397           ** then the index cannot satisfy the ORDER BY constraint.
  1392   1398           */
  1393   1399           return 0;
  1394   1400         }
  1395   1401       }
  1396         -    assert( pIdx->aSortOrder!=0 );
         1402  +    assert( pIdx->aSortOrder!=0 || iColumn==-1 );
  1397   1403       assert( pTerm->sortOrder==0 || pTerm->sortOrder==1 );
  1398   1404       assert( iSortOrder==0 || iSortOrder==1 );
  1399   1405       termSortOrder = iSortOrder ^ pTerm->sortOrder;
  1400   1406       if( i>nEqCol ){
  1401   1407         if( termSortOrder!=sortOrder ){
  1402   1408           /* Indices can only be used if all ORDER BY terms past the
  1403   1409           ** equality constraints are all either DESC or ASC. */
................................................................................
  1429   1435         && !referencesOtherTables(pOrderBy, pMaskSet, j, base) ){
  1430   1436       /* All terms of this index match some prefix of the ORDER BY clause
  1431   1437       ** and the index is UNIQUE and no terms on the tail of the ORDER BY
  1432   1438       ** clause reference other tables in a join.  If this is all true then
  1433   1439       ** the order by clause is superfluous. */
  1434   1440       return 1;
  1435   1441     }
  1436         -  return 0;
  1437         -}
  1438         -
  1439         -/*
  1440         -** Check table to see if the ORDER BY clause in pOrderBy can be satisfied
  1441         -** by sorting in order of ROWID.  Return true if so and set *pbRev to be
  1442         -** true for reverse ROWID and false for forward ROWID order.
  1443         -*/
  1444         -static int sortableByRowid(
  1445         -  int base,               /* Cursor number for table to be sorted */
  1446         -  ExprList *pOrderBy,     /* The ORDER BY clause */
  1447         -  WhereMaskSet *pMaskSet, /* Mapping from table cursors to bitmaps */
  1448         -  int *pbRev              /* Set to 1 if ORDER BY is DESC */
  1449         -){
  1450         -  Expr *p;
  1451         -
  1452         -  assert( pOrderBy!=0 );
  1453         -  assert( pOrderBy->nExpr>0 );
  1454         -  p = pOrderBy->a[0].pExpr;
  1455         -  if( p->op==TK_COLUMN && p->iTable==base && p->iColumn==-1
  1456         -    && !referencesOtherTables(pOrderBy, pMaskSet, 1, base) ){
  1457         -    *pbRev = pOrderBy->a[0].sortOrder;
  1458         -    return 1;
  1459         -  }
  1460   1442     return 0;
  1461   1443   }
  1462   1444   
  1463   1445   /*
  1464   1446   ** Prepare a crude estimate of the logarithm of the input value.
  1465   1447   ** The results need not be exact.  This is only used for estimating
  1466   1448   ** the total cost of performing operations with O(logN) or O(NlogN)
................................................................................
  1556   1538       ){
  1557   1539         WhereClause * const pOrWC = &pTerm->u.pOrInfo->wc;
  1558   1540         WhereTerm * const pOrWCEnd = &pOrWC->a[pOrWC->nTerm];
  1559   1541         WhereTerm *pOrTerm;
  1560   1542         int flags = WHERE_MULTI_OR;
  1561   1543         double rTotal = 0;
  1562   1544         double nRow = 0;
         1545  +      Bitmask used = 0;
  1563   1546   
  1564   1547         for(pOrTerm=pOrWC->a; pOrTerm<pOrWCEnd; pOrTerm++){
  1565   1548           WhereCost sTermCost;
  1566   1549           WHERETRACE(("... Multi-index OR testing for term %d of %d....\n", 
  1567   1550             (pOrTerm - pOrWC->a), (pTerm - pWC->a)
  1568   1551           ));
  1569   1552           if( pOrTerm->eOperator==WO_AND ){
................................................................................
  1578   1561             tempWC.nTerm = 1;
  1579   1562             bestIndex(pParse, &tempWC, pSrc, notReady, 0, &sTermCost);
  1580   1563           }else{
  1581   1564             continue;
  1582   1565           }
  1583   1566           rTotal += sTermCost.rCost;
  1584   1567           nRow += sTermCost.nRow;
         1568  +        used |= sTermCost.used;
  1585   1569           if( rTotal>=pCost->rCost ) break;
  1586   1570         }
  1587   1571   
  1588   1572         /* If there is an ORDER BY clause, increase the scan cost to account 
  1589   1573         ** for the cost of the sort. */
  1590   1574         if( pOrderBy!=0 ){
  1591   1575           rTotal += nRow*estLog(nRow);
................................................................................
  1595   1579         /* If the cost of scanning using this OR term for optimization is
  1596   1580         ** less than the current cost stored in pCost, replace the contents
  1597   1581         ** of pCost. */
  1598   1582         WHERETRACE(("... multi-index OR cost=%.9g nrow=%.9g\n", rTotal, nRow));
  1599   1583         if( rTotal<pCost->rCost ){
  1600   1584           pCost->rCost = rTotal;
  1601   1585           pCost->nRow = nRow;
         1586  +        pCost->used = used;
  1602   1587           pCost->plan.wsFlags = flags;
  1603   1588           pCost->plan.u.pTerm = pTerm;
  1604   1589         }
  1605   1590       }
  1606   1591     }
  1607   1592   #endif /* SQLITE_OMIT_OR_OPTIMIZATION */
  1608   1593   }
................................................................................
  1847   1832     ** each time.
  1848   1833     */
  1849   1834     pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
  1850   1835     pUsage = pIdxInfo->aConstraintUsage;
  1851   1836     for(i=0; i<pIdxInfo->nConstraint; i++, pIdxCons++){
  1852   1837       j = pIdxCons->iTermOffset;
  1853   1838       pTerm = &pWC->a[j];
  1854         -    pIdxCons->usable =  (pTerm->prereqRight & notReady)==0 ?1:0;
         1839  +    pIdxCons->usable = (pTerm->prereqRight&notReady) ? 0 : 1;
  1855   1840     }
  1856   1841     memset(pUsage, 0, sizeof(pUsage[0])*pIdxInfo->nConstraint);
  1857   1842     if( pIdxInfo->needToFreeIdxStr ){
  1858   1843       sqlite3_free(pIdxInfo->idxStr);
  1859   1844     }
  1860   1845     pIdxInfo->idxStr = 0;
  1861   1846     pIdxInfo->idxNum = 0;
................................................................................
  1867   1852     if( !pOrderBy ){
  1868   1853       pIdxInfo->nOrderBy = 0;
  1869   1854     }
  1870   1855   
  1871   1856     if( vtabBestIndex(pParse, pTab, pIdxInfo) ){
  1872   1857       return;
  1873   1858     }
         1859  +
         1860  +  pIdxCons = *(struct sqlite3_index_constraint**)&pIdxInfo->aConstraint;
         1861  +  for(i=0; i<pIdxInfo->nConstraint; i++){
         1862  +    if( pUsage[i].argvIndex>0 ){
         1863  +      pCost->used |= pWC->a[pIdxCons[i].iTermOffset].prereqRight;
         1864  +    }
         1865  +  }
  1874   1866   
  1875   1867     /* The cost is not allowed to be larger than SQLITE_BIG_DBL (the
  1876   1868     ** inital value of lowestCost in this loop. If it is, then the
  1877   1869     ** (cost<lowestCost) test below will never be true.
  1878   1870     ** 
  1879   1871     ** Use "(double)2" instead of "2.0" in case OMIT_FLOATING_POINT 
  1880   1872     ** is defined.
................................................................................
  1930   1922     Parse *pParse,              /* The parsing context */
  1931   1923     WhereClause *pWC,           /* The WHERE clause */
  1932   1924     struct SrcList_item *pSrc,  /* The FROM clause term to search */
  1933   1925     Bitmask notReady,           /* Mask of cursors that are not available */
  1934   1926     ExprList *pOrderBy,         /* The ORDER BY clause */
  1935   1927     WhereCost *pCost            /* Lowest cost query plan */
  1936   1928   ){
  1937         -  WhereTerm *pTerm;           /* A single term of the WHERE clause */
  1938   1929     int iCur = pSrc->iCursor;   /* The cursor of the table to be accessed */
  1939   1930     Index *pProbe;              /* An index we are evaluating */
  1940         -  int rev;                    /* True to scan in reverse order */
  1941         -  int wsFlags;                /* Flags associated with pProbe */
  1942         -  int nEq;                    /* Number of == or IN constraints */
  1943         -  int eqTermMask;             /* Mask of valid equality operators */
  1944         -  double cost;                /* Cost of using pProbe */
  1945         -  double nRow;                /* Estimated number of rows in result set */
  1946         -  int i;                      /* Loop counter */
         1931  +  Index *pIdx;                /* Copy of pProbe, or zero for IPK index */
         1932  +  int eqTermMask;             /* Current mask of valid equality operators */
         1933  +  int idxEqTermMask;          /* Index mask of valid equality operators */
  1947   1934   
  1948         -  WHERETRACE(("bestIndex: tbl=%s notReady=%llx\n", pSrc->pTab->zName,notReady));
  1949         -  pProbe = pSrc->pTab->pIndex;
  1950         -  if( pSrc->notIndexed ){
  1951         -    pProbe = 0;
  1952         -  }
         1935  +  Index pk;
         1936  +  unsigned int pkint[2] = {1000000, 1};
         1937  +  int pkicol = -1;
         1938  +  int wsFlagMask;
  1953   1939   
  1954         -  /* If the table has no indices and there are no terms in the where
  1955         -  ** clause that refer to the ROWID, then we will never be able to do
  1956         -  ** anything other than a full table scan on this table.  We might as
  1957         -  ** well put it first in the join order.  That way, perhaps it can be
  1958         -  ** referenced by other tables in the join.
  1959         -  */
  1960   1940     memset(pCost, 0, sizeof(*pCost));
  1961         -  if( pProbe==0 &&
  1962         -     findTerm(pWC, iCur, -1, 0, WO_EQ|WO_IN|WO_LT|WO_LE|WO_GT|WO_GE,0)==0 &&
  1963         -     (pOrderBy==0 || !sortableByRowid(iCur, pOrderBy, pWC->pMaskSet, &rev)) ){
  1964         -     if( pParse->db->flags & SQLITE_ReverseOrder ){
  1965         -      /* For application testing, randomly reverse the output order for
  1966         -      ** SELECT statements that omit the ORDER BY clause.  This will help
  1967         -      ** to find cases where
  1968         -      */
  1969         -      pCost->plan.wsFlags |= WHERE_REVERSE;
  1970         -    }
  1971         -    return;
  1972         -  }
  1973   1941     pCost->rCost = SQLITE_BIG_DBL;
  1974   1942   
  1975         -  /* Check for a rowid=EXPR or rowid IN (...) constraints. If there was
  1976         -  ** an INDEXED BY clause attached to this table, skip this step.
  1977         -  */
  1978         -  if( !pSrc->pIndex ){
  1979         -    pTerm = findTerm(pWC, iCur, -1, notReady, WO_EQ|WO_IN, 0);
  1980         -    if( pTerm ){
  1981         -      Expr *pExpr;
  1982         -      pCost->plan.wsFlags = WHERE_ROWID_EQ;
  1983         -      if( pTerm->eOperator & WO_EQ ){
  1984         -        /* Rowid== is always the best pick.  Look no further.  Because only
  1985         -        ** a single row is generated, output is always in sorted order */
  1986         -        pCost->plan.wsFlags = WHERE_ROWID_EQ | WHERE_UNIQUE;
  1987         -        pCost->plan.nEq = 1;
  1988         -        WHERETRACE(("... best is rowid\n"));
  1989         -        pCost->rCost = 0;
  1990         -        pCost->nRow = 1;
  1991         -        return;
  1992         -      }else if( !ExprHasProperty((pExpr = pTerm->pExpr), EP_xIsSelect) 
  1993         -             && pExpr->x.pList 
  1994         -      ){
  1995         -        /* Rowid IN (LIST): cost is NlogN where N is the number of list
  1996         -        ** elements.  */
  1997         -        pCost->rCost = pCost->nRow = pExpr->x.pList->nExpr;
  1998         -        pCost->rCost *= estLog(pCost->rCost);
  1999         -      }else{
  2000         -        /* Rowid IN (SELECT): cost is NlogN where N is the number of rows
  2001         -        ** in the result of the inner select.  We have no way to estimate
  2002         -        ** that value so make a wild guess. */
  2003         -        pCost->nRow = 100;
  2004         -        pCost->rCost = 200;
  2005         -      }
  2006         -      WHERETRACE(("... rowid IN cost: %.9g\n", pCost->rCost));
  2007         -    }
  2008         -  
  2009         -    /* Estimate the cost of a table scan.  If we do not know how many
  2010         -    ** entries are in the table, use 1 million as a guess.
  2011         -    */
  2012         -    cost = pProbe ? pProbe->aiRowEst[0] : 1000000;
  2013         -    WHERETRACE(("... table scan base cost: %.9g\n", cost));
  2014         -    wsFlags = WHERE_ROWID_RANGE;
  2015         -  
  2016         -    /* Check for constraints on a range of rowids in a table scan.
  2017         -    */
  2018         -    pTerm = findTerm(pWC, iCur, -1, notReady, WO_LT|WO_LE|WO_GT|WO_GE, 0);
  2019         -    if( pTerm ){
  2020         -      if( findTerm(pWC, iCur, -1, notReady, WO_LT|WO_LE, 0) ){
  2021         -        wsFlags |= WHERE_TOP_LIMIT;
  2022         -        cost /= 3;  /* Guess that rowid<EXPR eliminates two-thirds of rows */
  2023         -      }
  2024         -      if( findTerm(pWC, iCur, -1, notReady, WO_GT|WO_GE, 0) ){
  2025         -        wsFlags |= WHERE_BTM_LIMIT;
  2026         -        cost /= 3;  /* Guess that rowid>EXPR eliminates two-thirds of rows */
  2027         -      }
  2028         -      WHERETRACE(("... rowid range reduces cost to %.9g\n", cost));
  2029         -    }else{
  2030         -      wsFlags = 0;
  2031         -    }
  2032         -    nRow = cost;
  2033         -  
  2034         -    /* If the table scan does not satisfy the ORDER BY clause, increase
  2035         -    ** the cost by NlogN to cover the expense of sorting. */
  2036         -    if( pOrderBy ){
  2037         -      if( sortableByRowid(iCur, pOrderBy, pWC->pMaskSet, &rev) ){
  2038         -        wsFlags |= WHERE_ORDERBY|WHERE_ROWID_RANGE;
  2039         -        if( rev ){
  2040         -          wsFlags |= WHERE_REVERSE;
  2041         -        }
  2042         -      }else{
  2043         -        cost += cost*estLog(cost);
  2044         -        WHERETRACE(("... sorting increases cost to %.9g\n", cost));
  2045         -      }
  2046         -    }else if( pParse->db->flags & SQLITE_ReverseOrder ){
  2047         -      /* For application testing, randomly reverse the output order for
  2048         -      ** SELECT statements that omit the ORDER BY clause.  This will help
  2049         -      ** to find cases where
  2050         -      */
  2051         -      wsFlags |= WHERE_REVERSE;
  2052         -    }
  2053         -
  2054         -    /* Remember this case if it is the best so far */
  2055         -    if( cost<pCost->rCost ){
  2056         -      pCost->rCost = cost;
  2057         -      pCost->nRow = nRow;
  2058         -      pCost->plan.wsFlags = wsFlags;
  2059         -    }
  2060         -  }
  2061         -
  2062         -  bestOrClauseIndex(pParse, pWC, pSrc, notReady, pOrderBy, pCost);
  2063         -
  2064   1943     /* If the pSrc table is the right table of a LEFT JOIN then we may not
  2065   1944     ** use an index to satisfy IS NULL constraints on that table.  This is
  2066   1945     ** because columns might end up being NULL if the table does not match -
  2067   1946     ** a circumstance which the index cannot help us discover.  Ticket #2177.
  2068   1947     */
  2069         -  if( (pSrc->jointype & JT_LEFT)!=0 ){
  2070         -    eqTermMask = WO_EQ|WO_IN;
         1948  +  if( pSrc->jointype & JT_LEFT ){
         1949  +    idxEqTermMask = WO_EQ|WO_IN;
  2071   1950     }else{
  2072         -    eqTermMask = WO_EQ|WO_IN|WO_ISNULL;
         1951  +    idxEqTermMask = WO_EQ|WO_IN|WO_ISNULL;
  2073   1952     }
  2074   1953   
  2075         -  /* Look at each index.
  2076         -  */
  2077   1954     if( pSrc->pIndex ){
  2078         -    pProbe = pSrc->pIndex;
  2079         -  }
  2080         -  for(; pProbe; pProbe=(pSrc->pIndex ? 0 : pProbe->pNext)){
  2081         -    double inMultiplier = 1;  /* Number of equality look-ups needed */
  2082         -    int inMultIsEst = 0;      /* True if inMultiplier is an estimate */
  2083         -
  2084         -    WHERETRACE(("... index %s:\n", pProbe->zName));
  2085         -
  2086         -    /* Count the number of columns in the index that are satisfied
  2087         -    ** by x=EXPR or x IS NULL constraints or x IN (...) constraints.
  2088         -    ** For a term of the form x=EXPR or x IS NULL we only have to do 
  2089         -    ** a single binary search.  But for x IN (...) we have to do a
  2090         -    ** number of binary searched
  2091         -    ** equal to the number of entries on the RHS of the IN operator.
  2092         -    ** The inMultipler variable with try to estimate the number of
  2093         -    ** binary searches needed.
  2094         -    */
  2095         -    wsFlags = 0;
  2096         -    for(i=0; i<pProbe->nColumn; i++){
  2097         -      int j = pProbe->aiColumn[i];
  2098         -      pTerm = findTerm(pWC, iCur, j, notReady, eqTermMask, pProbe);
         1955  +    pIdx = pProbe = pSrc->pIndex;
         1956  +    wsFlagMask = ~(WHERE_ROWID_EQ|WHERE_ROWID_RANGE);
         1957  +    eqTermMask = idxEqTermMask;
         1958  +  }else{
         1959  +    Index *pFirst = pSrc->pTab->pIndex;
         1960  +    memset(&pk, 0, sizeof(Index));
         1961  +    pk.nColumn = 1;
         1962  +    pk.aiColumn = &pkicol;
         1963  +    pk.aiRowEst = pkint;
         1964  +    pk.onError = OE_Replace;
         1965  +    pk.pTable = pSrc->pTab;
         1966  +    if( pSrc->notIndexed==0 ){
         1967  +      pk.pNext = pFirst;
         1968  +    }
         1969  +    if( pFirst && pFirst->aiRowEst ){
         1970  +      pkint[0] = pFirst->aiRowEst[0];
         1971  +    }
         1972  +    pProbe = &pk;
         1973  +    wsFlagMask = ~(
         1974  +        WHERE_COLUMN_IN|WHERE_COLUMN_EQ|WHERE_COLUMN_NULL|WHERE_COLUMN_RANGE
         1975  +    );
         1976  +    eqTermMask = WO_EQ|WO_IN;
         1977  +    pIdx = 0;
         1978  +  }
         1979  +
         1980  +
         1981  +  for(; pProbe; pIdx=pProbe=pProbe->pNext){
         1982  +    const unsigned int * const aiRowEst = pProbe->aiRowEst;
         1983  +    double cost;                /* Cost of using pProbe */
         1984  +    double nRow;                /* Estimated number of rows in result set */
         1985  +    int rev;                    /* True to scan in reverse order */
         1986  +    int wsFlags = 0;
         1987  +    Bitmask used = 0;
         1988  +
         1989  +    /* The following variables are populated based on the properties of
         1990  +    ** scan being evaluated. They are then used to determine the expected
         1991  +    ** cost and number of rows returned.
         1992  +    **
         1993  +    **  nEq: 
         1994  +    **    Number of equality terms that can be implemented using the index.
         1995  +    **
         1996  +    **  nInMul:  
         1997  +    **    The "in-multiplier". This is an estimate of how many seek operations 
         1998  +    **    SQLite must perform on the index in question. For example, if the 
         1999  +    **    WHERE clause is:
         2000  +    **
         2001  +    **      WHERE a IN (1, 2, 3) AND b IN (4, 5, 6)
         2002  +    **
         2003  +    **    SQLite must perform 9 lookups on an index on (a, b), so nInMul is 
         2004  +    **    set to 9. Given the same schema and either of the following WHERE 
         2005  +    **    clauses:
         2006  +    **
         2007  +    **      WHERE a =  1
         2008  +    **      WHERE a >= 2
         2009  +    **
         2010  +    **    nInMul is set to 1.
         2011  +    **
         2012  +    **    If there exists a WHERE term of the form "x IN (SELECT ...)", then 
         2013  +    **    the sub-select is assumed to return 25 rows for the purposes of 
         2014  +    **    determining nInMul.
         2015  +    **
         2016  +    **  bInEst:  
         2017  +    **    Set to true if there was at least one "x IN (SELECT ...)" term used 
         2018  +    **    in determining the value of nInMul.
         2019  +    **
         2020  +    **  nBound:  
         2021  +    **    Set based on whether or not there is a range constraint on the 
         2022  +    **    (nEq+1)th column of the index. 1 if there is neither an upper or 
         2023  +    **    lower bound, 3 if there is an upper or lower bound, or 9 if there 
         2024  +    **    is both an upper and lower bound.
         2025  +    **
         2026  +    **  bSort:   
         2027  +    **    Boolean. True if there is an ORDER BY clause that will require an 
         2028  +    **    external sort (i.e. scanning the index being evaluated will not 
         2029  +    **    correctly order records).
         2030  +    **
         2031  +    **  bLookup: 
         2032  +    **    Boolean. True if for each index entry visited a lookup on the 
         2033  +    **    corresponding table b-tree is required. This is always false 
         2034  +    **    for the rowid index. For other indexes, it is true unless all the 
         2035  +    **    columns of the table used by the SELECT statement are present in 
         2036  +    **    the index (such an index is sometimes described as a covering index).
         2037  +    **    For example, given the index on (a, b), the second of the following 
         2038  +    **    two queries requires table b-tree lookups, but the first does not.
         2039  +    **
         2040  +    **             SELECT a, b    FROM tbl WHERE a = 1;
         2041  +    **             SELECT a, b, c FROM tbl WHERE a = 1;
         2042  +    */
         2043  +    int nEq;
         2044  +    int bInEst = 0;
         2045  +    int nInMul = 1;
         2046  +    int nBound = 1;
         2047  +    int bSort = 0;
         2048  +    int bLookup = 0;
         2049  +
         2050  +    /* Determine the values of nEq and nInMul */
         2051  +    for(nEq=0; nEq<pProbe->nColumn; nEq++){
         2052  +      WhereTerm *pTerm;           /* A single term of the WHERE clause */
         2053  +      int j = pProbe->aiColumn[nEq];
         2054  +      pTerm = findTerm(pWC, iCur, j, notReady, eqTermMask, pIdx);
  2099   2055         if( pTerm==0 ) break;
  2100         -      wsFlags |= WHERE_COLUMN_EQ;
         2056  +      wsFlags |= (WHERE_COLUMN_EQ|WHERE_ROWID_EQ);
  2101   2057         if( pTerm->eOperator & WO_IN ){
  2102   2058           Expr *pExpr = pTerm->pExpr;
  2103   2059           wsFlags |= WHERE_COLUMN_IN;
  2104   2060           if( ExprHasProperty(pExpr, EP_xIsSelect) ){
  2105         -          inMultiplier *= 25;
  2106         -          inMultIsEst = 1;
         2061  +          nInMul *= 25;
         2062  +          bInEst = 1;
  2107   2063           }else if( pExpr->x.pList ){
  2108         -          inMultiplier *= pExpr->x.pList->nExpr + 1;
         2064  +          nInMul *= pExpr->x.pList->nExpr + 1;
  2109   2065           }
  2110   2066         }else if( pTerm->eOperator & WO_ISNULL ){
  2111   2067           wsFlags |= WHERE_COLUMN_NULL;
  2112   2068         }
         2069  +      used |= pTerm->prereqRight;
  2113   2070       }
  2114         -    nRow = pProbe->aiRowEst[i] * inMultiplier;
  2115         -    /* If inMultiplier is an estimate and that estimate results in an
  2116         -    ** nRow it that is more than half number of rows in the table,
  2117         -    ** then reduce inMultipler */
  2118         -    if( inMultIsEst && nRow*2 > pProbe->aiRowEst[0] ){
  2119         -      nRow = pProbe->aiRowEst[0]/2;
  2120         -      inMultiplier = nRow/pProbe->aiRowEst[i];
  2121         -    }
  2122         -    cost = nRow + inMultiplier*estLog(pProbe->aiRowEst[0]);
  2123         -    nEq = i;
  2124         -    if( pProbe->onError!=OE_None && nEq==pProbe->nColumn ){
         2071  +
         2072  +    /* Determine the value of nBound. */
         2073  +    if( nEq<pProbe->nColumn ){
         2074  +      int j = pProbe->aiColumn[nEq];
         2075  +      if( findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE|WO_GT|WO_GE, pIdx) ){
         2076  +        WhereTerm *pTop = findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE, pIdx);
         2077  +        WhereTerm *pBtm = findTerm(pWC, iCur, j, notReady, WO_GT|WO_GE, pIdx);
         2078  +        if( pTop ){
         2079  +          wsFlags |= WHERE_TOP_LIMIT;
         2080  +          nBound *= 3;
         2081  +          used |= pTop->prereqRight;
         2082  +        }
         2083  +        if( pBtm ){
         2084  +          wsFlags |= WHERE_BTM_LIMIT;
         2085  +          nBound *= 3;
         2086  +          used |= pBtm->prereqRight;
         2087  +        }
         2088  +        wsFlags |= (WHERE_COLUMN_RANGE|WHERE_ROWID_RANGE);
         2089  +      }
         2090  +    }else if( pProbe->onError!=OE_None ){
  2125   2091         testcase( wsFlags & WHERE_COLUMN_IN );
  2126   2092         testcase( wsFlags & WHERE_COLUMN_NULL );
  2127   2093         if( (wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_NULL))==0 ){
  2128   2094           wsFlags |= WHERE_UNIQUE;
  2129   2095         }
  2130   2096       }
  2131         -    WHERETRACE(("...... nEq=%d inMult=%.9g nRow=%.9g cost=%.9g\n",
  2132         -                nEq, inMultiplier, nRow, cost));
  2133   2097   
  2134         -    /* Look for range constraints.  Assume that each range constraint
  2135         -    ** makes the search space 1/3rd smaller.
  2136         -    */
  2137         -    if( nEq<pProbe->nColumn ){
  2138         -      int j = pProbe->aiColumn[nEq];
  2139         -      pTerm = findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE|WO_GT|WO_GE, pProbe);
  2140         -      if( pTerm ){
  2141         -        wsFlags |= WHERE_COLUMN_RANGE;
  2142         -        if( findTerm(pWC, iCur, j, notReady, WO_LT|WO_LE, pProbe) ){
  2143         -          wsFlags |= WHERE_TOP_LIMIT;
  2144         -          cost /= 3;
  2145         -          nRow /= 3;
  2146         -        }
  2147         -        if( findTerm(pWC, iCur, j, notReady, WO_GT|WO_GE, pProbe) ){
  2148         -          wsFlags |= WHERE_BTM_LIMIT;
  2149         -          cost /= 3;
  2150         -          nRow /= 3;
  2151         -        }
  2152         -        WHERETRACE(("...... range reduces nRow to %.9g and cost to %.9g\n",
  2153         -                    nRow, cost));
  2154         -      }
  2155         -    }
  2156         -
  2157         -    /* Add the additional cost of sorting if that is a factor.
  2158         -    */
         2098  +    /* If there is an ORDER BY clause and the index being considered will
         2099  +    ** naturally scan rows in the required order, set the appropriate flags
         2100  +    ** in wsFlags. Otherwise, if there is an ORDER BY clause but the index
         2101  +    ** will scan rows in a different order, set the bSort variable.  */
  2159   2102       if( pOrderBy ){
  2160   2103         if( (wsFlags & (WHERE_COLUMN_IN|WHERE_COLUMN_NULL))==0
  2161         -       && isSortingIndex(pParse,pWC->pMaskSet,pProbe,iCur,pOrderBy,nEq,&rev)
         2104  +        && isSortingIndex(pParse,pWC->pMaskSet,pProbe,iCur,pOrderBy,nEq,&rev)
  2162   2105         ){
  2163         -        if( wsFlags==0 ){
  2164         -          wsFlags = WHERE_COLUMN_RANGE;
  2165         -        }
  2166         -        wsFlags |= WHERE_ORDERBY;
  2167         -        if( rev ){
  2168         -          wsFlags |= WHERE_REVERSE;
  2169         -        }
         2106  +        wsFlags |= WHERE_ROWID_RANGE|WHERE_COLUMN_RANGE|WHERE_ORDERBY;
         2107  +        wsFlags |= (rev ? WHERE_REVERSE : 0);
  2170   2108         }else{
  2171         -        cost += cost*estLog(cost);
  2172         -        WHERETRACE(("...... orderby increases cost to %.9g\n", cost));
         2109  +        bSort = 1;
  2173   2110         }
  2174         -    }else if( wsFlags!=0 && (pParse->db->flags & SQLITE_ReverseOrder)!=0 ){
  2175         -      /* For application testing, randomly reverse the output order for
  2176         -      ** SELECT statements that omit the ORDER BY clause.  This will help
  2177         -      ** to find cases where
  2178         -      */
  2179         -      wsFlags |= WHERE_REVERSE;
  2180   2111       }
  2181   2112   
  2182         -    /* Check to see if we can get away with using just the index without
  2183         -    ** ever reading the table.  If that is the case, then halve the
  2184         -    ** cost of this index.
  2185         -    */
  2186         -    if( wsFlags && pSrc->colUsed < (((Bitmask)1)<<(BMS-1)) ){
         2113  +    /* If currently calculating the cost of using an index (not the IPK
         2114  +    ** index), determine if all required column data may be obtained without 
         2115  +    ** seeking to entries in the main table (i.e. if the index is a covering
         2116  +    ** index for this query). If it is, set the WHERE_IDX_ONLY flag in
         2117  +    ** wsFlags. Otherwise, set the bLookup variable to true.  */
         2118  +    if( pIdx && wsFlags ){
  2187   2119         Bitmask m = pSrc->colUsed;
  2188   2120         int j;
  2189         -      for(j=0; j<pProbe->nColumn; j++){
  2190         -        int x = pProbe->aiColumn[j];
         2121  +      for(j=0; j<pIdx->nColumn; j++){
         2122  +        int x = pIdx->aiColumn[j];
  2191   2123           if( x<BMS-1 ){
  2192   2124             m &= ~(((Bitmask)1)<<x);
  2193   2125           }
  2194   2126         }
  2195   2127         if( m==0 ){
  2196   2128           wsFlags |= WHERE_IDX_ONLY;
  2197         -        cost /= 2;
  2198         -        WHERETRACE(("...... idx-only reduces cost to %.9g\n", cost));
         2129  +      }else{
         2130  +        bLookup = 1;
  2199   2131         }
  2200   2132       }
  2201   2133   
  2202         -    /* If this index has achieved the lowest cost so far, then use it.
  2203         -    */
  2204         -    if( wsFlags!=0 && cost < pCost->rCost ){
         2134  +#if 0
         2135  +    if( bInEst && (nInMul*aiRowEst[nEq])>(aiRowEst[0]/2) ){
         2136  +      nInMul = aiRowEst[0] / (2 * aiRowEst[nEq]);
         2137  +    }
         2138  +    nRow = (double)(aiRowEst[nEq] * nInMul) / nBound;
         2139  +    cost = (nEq>0) * nInMul * estLog(aiRowEst[0])
         2140  +         + nRow
         2141  +         + bSort * nRow * estLog(nRow)
         2142  +         + bLookup * nRow * estLog(aiRowEst[0]);
         2143  +#else
         2144  +
         2145  +    /* The following block calculates nRow and cost for the index scan
         2146  +    ** in the same way as SQLite versions 3.6.17 and earlier. Some elements
         2147  +    ** of this calculation are difficult to justify. But using this strategy
         2148  +    ** works well in practice and causes the test suite to pass.  */
         2149  +    nRow = (double)(aiRowEst[nEq] * nInMul);
         2150  +    if( bInEst && nRow*2>aiRowEst[0] ){
         2151  +      nRow = aiRowEst[0]/2;
         2152  +      nInMul = nRow / aiRowEst[nEq];
         2153  +    }
         2154  +    cost = nRow + nInMul*estLog(aiRowEst[0]);
         2155  +    nRow /= nBound;
         2156  +    cost /= nBound;
         2157  +    if( bSort ){
         2158  +      cost += cost*estLog(cost);
         2159  +    }
         2160  +    if( pIdx && bLookup==0 ){
         2161  +      cost /= 2;
         2162  +    }
         2163  +#endif
         2164  +
         2165  +    WHERETRACE((
         2166  +      "tbl=%s idx=%s nEq=%d nInMul=%d nBound=%d bSort=%d bLookup=%d"
         2167  +      " wsFlags=%d   (nRow=%.2f cost=%.2f)\n",
         2168  +      pSrc->pTab->zName, (pIdx ? pIdx->zName : "ipk"), 
         2169  +      nEq, nInMul, nBound, bSort, bLookup, wsFlags, nRow, cost
         2170  +    ));
         2171  +
         2172  +    if( (!pIdx || wsFlags) && cost<pCost->rCost ){
  2205   2173         pCost->rCost = cost;
  2206   2174         pCost->nRow = nRow;
  2207         -      pCost->plan.wsFlags = wsFlags;
         2175  +      pCost->used = used;
         2176  +      pCost->plan.wsFlags = (wsFlags&wsFlagMask);
  2208   2177         pCost->plan.nEq = nEq;
  2209         -      assert( pCost->plan.wsFlags & WHERE_INDEXED );
  2210         -      pCost->plan.u.pIdx = pProbe;
         2178  +      pCost->plan.u.pIdx = pIdx;
  2211   2179       }
         2180  +
         2181  +    if( pSrc->pIndex ) break;
         2182  +    wsFlagMask = ~(WHERE_ROWID_EQ|WHERE_ROWID_RANGE);
         2183  +    eqTermMask = idxEqTermMask;
  2212   2184     }
  2213   2185   
  2214         -  /* Report the best result
  2215         -  */
         2186  +  /* If there is no ORDER BY clause and the SQLITE_ReverseOrder flag
         2187  +  ** is set, then reverse the order that the index will be scanned
         2188  +  ** in. This is used for application testing, to help find cases
         2189  +  ** where application behaviour depends on the (undefined) order that
         2190  +  ** SQLite outputs rows in in the absence of an ORDER BY clause.  */
         2191  +  if( !pOrderBy && pParse->db->flags & SQLITE_ReverseOrder ){
         2192  +    pCost->plan.wsFlags |= WHERE_REVERSE;
         2193  +  }
         2194  +
         2195  +  assert( pOrderBy || (pCost->plan.wsFlags&WHERE_ORDERBY)==0 );
         2196  +  assert( pCost->plan.u.pIdx==0 || (pCost->plan.wsFlags&WHERE_ROWID_EQ)==0 );
         2197  +  assert( pSrc->pIndex==0 
         2198  +       || pCost->plan.u.pIdx==0 
         2199  +       || pCost->plan.u.pIdx==pSrc->pIndex 
         2200  +  );
         2201  +
         2202  +  WHERETRACE(("best index is: %s\n", 
         2203  +    (pCost->plan.u.pIdx ? pCost->plan.u.pIdx->zName : "ipk")
         2204  +  ));
         2205  +  
         2206  +  bestOrClauseIndex(pParse, pWC, pSrc, notReady, pOrderBy, pCost);
  2216   2207     pCost->plan.wsFlags |= eqTermMask;
  2217         -  WHERETRACE(("best index is %s, nrow=%.9g, cost=%.9g, wsFlags=%x, nEq=%d\n",
  2218         -        (pCost->plan.wsFlags & WHERE_INDEXED)!=0 ?
  2219         -             pCost->plan.u.pIdx->zName : "(none)", pCost->nRow,
  2220         -        pCost->rCost, pCost->plan.wsFlags, pCost->plan.nEq));
  2221   2208   }
  2222   2209   
  2223   2210   /*
  2224   2211   ** Find the query plan for accessing table pSrc->pTab. Write the
  2225   2212   ** best query plan and its cost into the WhereCost object supplied 
  2226   2213   ** as the last parameter. This function may calculate the cost of
  2227   2214   ** both real and virtual table scans.
................................................................................
  3267   3254     pLevel = pWInfo->a;
  3268   3255     andFlags = ~0;
  3269   3256     WHERETRACE(("*** Optimizer Start ***\n"));
  3270   3257     for(i=iFrom=0, pLevel=pWInfo->a; i<pTabList->nSrc; i++, pLevel++){
  3271   3258       WhereCost bestPlan;         /* Most efficient plan seen so far */
  3272   3259       Index *pIdx;                /* Index for FROM table at pTabItem */
  3273   3260       int j;                      /* For looping over FROM tables */
  3274         -    int bestJ = 0;              /* The value of j */
         3261  +    int bestJ = -1;             /* The value of j */
  3275   3262       Bitmask m;                  /* Bitmask value for j or bestJ */
  3276         -    int once = 0;               /* True when first table is seen */
         3263  +    int isOptimal;              /* Iterator for optimal/non-optimal search */
  3277   3264   
  3278   3265       memset(&bestPlan, 0, sizeof(bestPlan));
  3279   3266       bestPlan.rCost = SQLITE_BIG_DBL;
  3280         -    for(j=iFrom, pTabItem=&pTabList->a[j]; j<pTabList->nSrc; j++, pTabItem++){
  3281         -      int doNotReorder;    /* True if this table should not be reordered */
  3282         -      WhereCost sCost;     /* Cost information from best[Virtual]Index() */
  3283         -      ExprList *pOrderBy;  /* ORDER BY clause for index to optimize */
  3284         -
  3285         -      doNotReorder =  (pTabItem->jointype & (JT_LEFT|JT_CROSS))!=0;
  3286         -      if( once && doNotReorder ) break;
  3287         -      m = getMask(pMaskSet, pTabItem->iCursor);
  3288         -      if( (m & notReady)==0 ){
  3289         -        if( j==iFrom ) iFrom++;
  3290         -        continue;
  3291         -      }
  3292         -      pOrderBy = ((i==0 && ppOrderBy )?*ppOrderBy:0);
  3293         -
  3294         -      assert( pTabItem->pTab );
         3267  +
         3268  +    /* Loop through the remaining entries in the FROM clause to find the
         3269  +    ** next nested loop. The FROM clause entries may be iterated through
         3270  +    ** either once or twice. 
         3271  +    **
         3272  +    ** The first iteration, which is always performed, searches for the
         3273  +    ** FROM clause entry that permits the lowest-cost, "optimal" scan. In
         3274  +    ** this context an optimal scan is one that uses the same strategy
         3275  +    ** for the given FROM clause entry as would be selected if the entry
         3276  +    ** were used as the innermost nested loop.
         3277  +    **
         3278  +    ** The second iteration is only performed if no optimal scan strategies
         3279  +    ** were found by the first. This iteration is used to search for the
         3280  +    ** lowest cost scan overall.
         3281  +    **
         3282  +    ** Previous versions of SQLite performed only the second iteration -
         3283  +    ** the next outermost loop was always that with the lowest overall
         3284  +    ** cost. However, this meant that SQLite could select the wrong plan
         3285  +    ** for scripts such as the following:
         3286  +    **   
         3287  +    **   CREATE TABLE t1(a, b); 
         3288  +    **   CREATE TABLE t2(c, d);
         3289  +    **   SELECT * FROM t2, t1 WHERE t2.rowid = t1.a;
         3290  +    **
         3291  +    ** The best strategy is to iterate through table t1 first. However it
         3292  +    ** is not possible to determine this with a simple greedy algorithm.
         3293  +    ** However, since the cost of a linear scan through table t2 is the same 
         3294  +    ** as the cost of a linear scan through table t1, a simple greedy 
         3295  +    ** algorithm may choose to use t2 for the outer loop, which is a much
         3296  +    ** costlier approach.
         3297  +    */
         3298  +    for(isOptimal=1; isOptimal>=0 && bestJ<0; isOptimal--){
         3299  +      Bitmask mask = (isOptimal ? 0 : notReady);
         3300  +      assert( (pTabList->nSrc-iFrom)>1 || isOptimal );
         3301  +      for(j=iFrom, pTabItem=&pTabList->a[j]; j<pTabList->nSrc; j++, pTabItem++){
         3302  +        int doNotReorder;    /* True if this table should not be reordered */
         3303  +        WhereCost sCost;     /* Cost information from best[Virtual]Index() */
         3304  +        ExprList *pOrderBy;  /* ORDER BY clause for index to optimize */
         3305  +  
         3306  +        doNotReorder =  (pTabItem->jointype & (JT_LEFT|JT_CROSS))!=0;
         3307  +        if( j!=iFrom && doNotReorder ) break;
         3308  +        m = getMask(pMaskSet, pTabItem->iCursor);
         3309  +        if( (m & notReady)==0 ){
         3310  +          if( j==iFrom ) iFrom++;
         3311  +          continue;
         3312  +        }
         3313  +        pOrderBy = ((i==0 && ppOrderBy )?*ppOrderBy:0);
         3314  +  
         3315  +        assert( pTabItem->pTab );
  3295   3316   #ifndef SQLITE_OMIT_VIRTUALTABLE
  3296         -      if( IsVirtual(pTabItem->pTab) ){
  3297         -        sqlite3_index_info **pp = &pWInfo->a[j].pIdxInfo;
  3298         -        bestVirtualIndex(pParse, pWC, pTabItem, notReady, pOrderBy, &sCost, pp);
  3299         -      }else 
         3317  +        if( IsVirtual(pTabItem->pTab) ){
         3318  +          sqlite3_index_info **pp = &pWInfo->a[j].pIdxInfo;
         3319  +          bestVirtualIndex(pParse, pWC, pTabItem, mask, pOrderBy, &sCost, pp);
         3320  +        }else 
  3300   3321   #endif
  3301         -      {
  3302         -        bestBtreeIndex(pParse, pWC, pTabItem, notReady, pOrderBy, &sCost);
         3322  +        {
         3323  +          bestBtreeIndex(pParse, pWC, pTabItem, mask, pOrderBy, &sCost);
         3324  +        }
         3325  +        assert( isOptimal || (sCost.used&notReady)==0 );
         3326  +
         3327  +        if( (sCost.used&notReady)==0
         3328  +         && (j==iFrom || sCost.rCost<bestPlan.rCost) 
         3329  +        ){
         3330  +          bestPlan = sCost;
         3331  +          bestJ = j;
         3332  +        }
         3333  +        if( doNotReorder ) break;
  3303   3334         }
  3304         -      if( once==0 || sCost.rCost<bestPlan.rCost ){
  3305         -        once = 1;
  3306         -        bestPlan = sCost;
  3307         -        bestJ = j;
  3308         -      }
  3309         -      if( doNotReorder ) break;
  3310   3335       }
  3311         -    assert( once );
         3336  +    assert( bestJ>=0 );
  3312   3337       assert( notReady & getMask(pMaskSet, pTabList->a[bestJ].iCursor) );
  3313   3338       WHERETRACE(("*** Optimizer selects table %d for loop %d\n", bestJ,
  3314   3339              pLevel-pWInfo->a));
  3315   3340       if( (bestPlan.plan.wsFlags & WHERE_ORDERBY)!=0 ){
  3316   3341         *ppOrderBy = 0;
  3317   3342       }
  3318   3343       andFlags &= bestPlan.plan.wsFlags;

Changes to test/triggerA.test.

    75     75     }
    76     76   } {1 10 2 3 4 5 6 7 8 9 five four three}
    77     77   do_test triggerA-1.6 {
    78     78     db eval {
    79     79        CREATE VIEW v5 AS SELECT x, b FROM t1, t2 WHERE y=c;
    80     80        SELECT * FROM v5;
    81     81     }
    82         -} {1 103 2 203 3 305 4 404 5 504 6 603 7 705 8 805 9 904 10 1003}
           82  +} {10 1003 9 904 8 805 7 705 6 603 5 504 4 404 3 305 2 203 1 103}
    83     83   
    84     84   # Create INSTEAD OF triggers on the views.  Run UPDATE and DELETE statements
    85     85   # using those triggers.  Verify correct operation.
    86     86   #
    87     87   do_test triggerA-2.1 {
    88     88     db eval {
    89     89        CREATE TABLE result2(a,b);

Changes to test/vtab6.test.

   488    488     }
   489    489   } {1 2 3}
   490    490   
   491    491   
   492    492   do_test vtab6-11.2.0 {
   493    493     execsql {
   494    494       CREATE INDEX ab_i ON ab_r(b);
          495  +    CREATE INDEX bc_i ON bc_r(b);
   495    496     }
   496    497   } {}
   497    498   
   498    499   unset ::echo_module_cost
   499    500   
   500    501   do_test vtab6-11.2.1 {
   501    502     execsql {
................................................................................
   556    557   set ::echo_module_ignore_usable 1
   557    558   db cache flush
   558    559   
   559    560   do_test vtab6-11.4.1 {
   560    561     catchsql {
   561    562       SELECT a, b, c FROM ab NATURAL JOIN bc;
   562    563     }
   563         -} {1 {table ab: xBestIndex returned an invalid plan}}
          564  +} {1 {table bc: xBestIndex returned an invalid plan}}
   564    565   do_test vtab6-11.4.2 {
   565    566     catchsql {
   566    567       SELECT a, b, c FROM bc NATURAL JOIN ab;
   567    568     }
   568    569   } {1 {table ab: xBestIndex returned an invalid plan}}
   569    570   
   570    571   unset ::echo_module_ignore_usable
   571    572   
   572    573   finish_test

Changes to test/where8.test.

   283    283   
   284    284   do_test where8-3.15 {
   285    285     execsql_status {
   286    286       SELECT c FROM t1, t2 WHERE a BETWEEN 1 AND 2 OR a = (
   287    287         SELECT sum(e IS NULL) FROM t2 AS inner WHERE t2.d>inner.d
   288    288       )
   289    289     }
   290         -} {I I I I I I I I I I II II II II II II II II II II III III III III III 99 0}
          290  +} {I II I II I II I II I II I II III I II III I II III I II III I II III 9 0}
   291    291   
   292    292   #-----------------------------------------------------------------------
   293    293   # The following tests - where8-4.* - verify that adding or removing 
   294    294   # indexes does not change the results returned by various queries.
   295    295   #
   296    296   do_test where8-4.1 {
   297    297     execsql {