/ Check-in [c71f2359]
Login

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

Overview
Comment:Merge recent trunk changes with this branch.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | exp-window-functions
Files: files | file ages | folders
SHA3-256: c71f23590c25b4cecd27722e6c0fc8e3bf320d399c7d9398b7016dd5cf5b05eb
User & Date: dan 2018-06-09 18:09:44
Context
2018-06-10
07:42
Update Makefile.msc to include window.c in the build. check-in: 16db7384 user: dan tags: exp-window-functions
2018-06-09
18:09
Merge recent trunk changes with this branch. check-in: c71f2359 user: dan tags: exp-window-functions
17:58
Update the amalgamation build script to include window.c. check-in: 21d2f4a6 user: dan tags: exp-window-functions
16:49
Slightly smaller and faster code by encapsulating wal-index hash table location information in a separate WalHashLoc object rather than passing around the various elements as separate variables. check-in: 538a365b user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/btree.c.

  5592   5592         }
  5593   5593         pCur->skipNext = 0;
  5594   5594       }
  5595   5595     }
  5596   5596   
  5597   5597     pPage = pCur->pPage;
  5598   5598     idx = ++pCur->ix;
  5599         -  assert( pPage->isInit );
         5599  +  if( !pPage->isInit ){
         5600  +    /* The only known way for this to happen is for there to be a
         5601  +    ** recursive SQL function that does a DELETE operation as part of a
         5602  +    ** SELECT which deletes content out from under an active cursor
         5603  +    ** in a corrupt database file where the table being DELETE-ed from
         5604  +    ** has pages in common with the table being queried.  See TH3
         5605  +    ** module cov1/btree78.test testcase 220 (2018-06-08) for an
         5606  +    ** example. */
         5607  +    return SQLITE_CORRUPT_BKPT;
         5608  +  }
  5600   5609   
  5601   5610     /* If the database file is corrupt, it is possible for the value of idx 
  5602   5611     ** to be invalid here. This can only occur if a second cursor modifies
  5603   5612     ** the page while cursor pCur is holding a reference to it. Which can
  5604   5613     ** only happen if the database is corrupt in such a way as to link the
  5605   5614     ** page into more than one b-tree structure. */
  5606   5615     testcase( idx>pPage->nCell );

Changes to src/build.c.

  1690   1690   
  1691   1691   /* Return true if value x is found any of the first nCol entries of aiCol[]
  1692   1692   */
  1693   1693   static int hasColumn(const i16 *aiCol, int nCol, int x){
  1694   1694     while( nCol-- > 0 ) if( x==*(aiCol++) ) return 1;
  1695   1695     return 0;
  1696   1696   }
         1697  +
         1698  +/* Recompute the colNotIdxed field of the Index.
         1699  +**
         1700  +** colNotIdxed is a bitmask that has a 0 bit representing each indexed
         1701  +** columns that are within the first 63 columns of the table.  The
         1702  +** high-order bit of colNotIdxed is always 1.  All unindexed columns
         1703  +** of the table have a 1.
         1704  +**
         1705  +** The colNotIdxed mask is AND-ed with the SrcList.a[].colUsed mask
         1706  +** to determine if the index is covering index.
         1707  +*/
         1708  +static void recomputeColumnsNotIndexed(Index *pIdx){
         1709  +  Bitmask m = 0;
         1710  +  int j;
         1711  +  for(j=pIdx->nColumn-1; j>=0; j--){
         1712  +    int x = pIdx->aiColumn[j];
         1713  +    if( x>=0 ){
         1714  +      testcase( x==BMS-1 );
         1715  +      testcase( x==BMS-2 );
         1716  +      if( x<BMS-1 ) m |= MASKBIT(x);
         1717  +    }
         1718  +  }
         1719  +  pIdx->colNotIdxed = ~m;
         1720  +  assert( (pIdx->colNotIdxed>>63)==1 );
         1721  +}
  1697   1722   
  1698   1723   /*
  1699   1724   ** This routine runs at the end of parsing a CREATE TABLE statement that
  1700   1725   ** has a WITHOUT ROWID clause.  The job of this routine is to convert both
  1701   1726   ** internal schema data structures and the generated VDBE code so that they
  1702   1727   ** are appropriate for a WITHOUT ROWID table instead of a rowid table.
  1703   1728   ** Changes include:
................................................................................
  1839   1864         }
  1840   1865       }
  1841   1866       assert( pPk->nColumn==j );
  1842   1867       assert( pTab->nCol==j );
  1843   1868     }else{
  1844   1869       pPk->nColumn = pTab->nCol;
  1845   1870     }
         1871  +  recomputeColumnsNotIndexed(pPk);
  1846   1872   }
  1847   1873   
  1848   1874   /*
  1849   1875   ** This routine is called to report the final ")" that terminates
  1850   1876   ** a CREATE TABLE statement.
  1851   1877   **
  1852   1878   ** The table structure that other action routines have been building
................................................................................
  3272   3298     sqlite3DefaultRowEst(pIndex);
  3273   3299     if( pParse->pNewTable==0 ) estimateIndexWidth(pIndex);
  3274   3300   
  3275   3301     /* If this index contains every column of its table, then mark
  3276   3302     ** it as a covering index */
  3277   3303     assert( HasRowid(pTab) 
  3278   3304         || pTab->iPKey<0 || sqlite3ColumnOfIndex(pIndex, pTab->iPKey)>=0 );
         3305  +  recomputeColumnsNotIndexed(pIndex);
  3279   3306     if( pTblName!=0 && pIndex->nColumn>=pTab->nCol ){
  3280   3307       pIndex->isCovering = 1;
  3281   3308       for(j=0; j<pTab->nCol; j++){
  3282   3309         if( j==pTab->iPKey ) continue;
  3283   3310         if( sqlite3ColumnOfIndex(pIndex,j)>=0 ) continue;
  3284   3311         pIndex->isCovering = 0;
  3285   3312         break;

Changes to src/sqliteInt.h.

  1106   1106   typedef struct VTable VTable;
  1107   1107   typedef struct VtabCtx VtabCtx;
  1108   1108   typedef struct Walker Walker;
  1109   1109   typedef struct WhereInfo WhereInfo;
  1110   1110   typedef struct Window Window;
  1111   1111   typedef struct With With;
  1112   1112   
         1113  +
         1114  +/*
         1115  +** The bitmask datatype defined below is used for various optimizations.
         1116  +**
         1117  +** Changing this from a 64-bit to a 32-bit type limits the number of
         1118  +** tables in a join to 32 instead of 64.  But it also reduces the size
         1119  +** of the library by 738 bytes on ix86.
         1120  +*/
         1121  +#ifdef SQLITE_BITMASK_TYPE
         1122  +  typedef SQLITE_BITMASK_TYPE Bitmask;
         1123  +#else
         1124  +  typedef u64 Bitmask;
         1125  +#endif
         1126  +
         1127  +/*
         1128  +** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
         1129  +*/
         1130  +#define BMS  ((int)(sizeof(Bitmask)*8))
         1131  +
         1132  +/*
         1133  +** A bit in a Bitmask
         1134  +*/
         1135  +#define MASKBIT(n)   (((Bitmask)1)<<(n))
         1136  +#define MASKBIT32(n) (((unsigned int)1)<<(n))
         1137  +#define ALLBITS      ((Bitmask)-1)
         1138  +
  1113   1139   /* A VList object records a mapping between parameters/variables/wildcards
  1114   1140   ** in the SQL statement (such as $abc, @pqr, or :xyz) and the integer
  1115   1141   ** variable number associated with that parameter.  See the format description
  1116   1142   ** on the sqlite3VListAdd() routine for more information.  A VList is really
  1117   1143   ** just an array of integers.
  1118   1144   */
  1119   1145   typedef int VList;
................................................................................
  2209   2235     int nSample;             /* Number of elements in aSample[] */
  2210   2236     int nSampleCol;          /* Size of IndexSample.anEq[] and so on */
  2211   2237     tRowcnt *aAvgEq;         /* Average nEq values for keys not in aSample */
  2212   2238     IndexSample *aSample;    /* Samples of the left-most key */
  2213   2239     tRowcnt *aiRowEst;       /* Non-logarithmic stat1 data for this index */
  2214   2240     tRowcnt nRowEst0;        /* Non-logarithmic number of rows in the index */
  2215   2241   #endif
         2242  +  Bitmask colNotIdxed;     /* 0 for unindexed columns in pTab */
  2216   2243   };
  2217   2244   
  2218   2245   /*
  2219   2246   ** Allowed values for Index.idxType
  2220   2247   */
  2221   2248   #define SQLITE_IDXTYPE_APPDEF      0   /* Created using CREATE INDEX */
  2222   2249   #define SQLITE_IDXTYPE_UNIQUE      1   /* Implements a UNIQUE constraint */
................................................................................
  2555   2582     struct IdList_item {
  2556   2583       char *zName;      /* Name of the identifier */
  2557   2584       int idx;          /* Index in some Table.aCol[] of a column named zName */
  2558   2585     } *a;
  2559   2586     int nId;         /* Number of identifiers on the list */
  2560   2587   };
  2561   2588   
  2562         -/*
  2563         -** The bitmask datatype defined below is used for various optimizations.
  2564         -**
  2565         -** Changing this from a 64-bit to a 32-bit type limits the number of
  2566         -** tables in a join to 32 instead of 64.  But it also reduces the size
  2567         -** of the library by 738 bytes on ix86.
  2568         -*/
  2569         -#ifdef SQLITE_BITMASK_TYPE
  2570         -  typedef SQLITE_BITMASK_TYPE Bitmask;
  2571         -#else
  2572         -  typedef u64 Bitmask;
  2573         -#endif
  2574         -
  2575         -/*
  2576         -** The number of bits in a Bitmask.  "BMS" means "BitMask Size".
  2577         -*/
  2578         -#define BMS  ((int)(sizeof(Bitmask)*8))
  2579         -
  2580         -/*
  2581         -** A bit in a Bitmask
  2582         -*/
  2583         -#define MASKBIT(n)   (((Bitmask)1)<<(n))
  2584         -#define MASKBIT32(n) (((unsigned int)1)<<(n))
  2585         -#define ALLBITS      ((Bitmask)-1)
  2586         -
  2587   2589   /*
  2588   2590   ** The following structure describes the FROM clause of a SELECT statement.
  2589   2591   ** Each table or subquery in the FROM clause is a separate element of
  2590   2592   ** the SrcList.a[] array.
  2591   2593   **
  2592   2594   ** With the addition of multiple database support, the following structure
  2593   2595   ** can also be used to describe a particular table such as the table that

Changes to src/wal.c.

   875    875     assert( iPage>0 );
   876    876     assert( (HASHTABLE_NSLOT & (HASHTABLE_NSLOT-1))==0 );
   877    877     return (iPage*HASHTABLE_HASH_1) & (HASHTABLE_NSLOT-1);
   878    878   }
   879    879   static int walNextHash(int iPriorHash){
   880    880     return (iPriorHash+1)&(HASHTABLE_NSLOT-1);
   881    881   }
          882  +
          883  +/*
          884  +** An instance of the WalHashLoc object is used to describe the location
          885  +** of a page hash table in the wal-index.  This becomes the return value
          886  +** from walHashGet().
          887  +*/
          888  +typedef struct WalHashLoc WalHashLoc;
          889  +struct WalHashLoc {
          890  +  volatile ht_slot *aHash;  /* Start of the wal-index hash table */
          891  +  volatile u32 *aPgno;      /* aPgno[1] is the page of first frame indexed */
          892  +  u32 iZero;                /* One less than the frame number of first indexed*/
          893  +};
   882    894   
   883    895   /* 
   884    896   ** Return pointers to the hash table and page number array stored on
   885    897   ** page iHash of the wal-index. The wal-index is broken into 32KB pages
   886    898   ** numbered starting from 0.
   887    899   **
   888         -** Set output variable *paHash to point to the start of the hash table
   889         -** in the wal-index file. Set *piZero to one less than the frame 
          900  +** Set output variable pLoc->aHash to point to the start of the hash table
          901  +** in the wal-index file. Set pLoc->iZero to one less than the frame 
   890    902   ** number of the first frame indexed by this hash table. If a
   891    903   ** slot in the hash table is set to N, it refers to frame number 
   892         -** (*piZero+N) in the log.
          904  +** (pLoc->iZero+N) in the log.
   893    905   **
   894         -** Finally, set *paPgno so that *paPgno[1] is the page number of the
   895         -** first frame indexed by the hash table, frame (*piZero+1).
          906  +** Finally, set pLoc->aPgno so that pLoc->aPgno[1] is the page number of the
          907  +** first frame indexed by the hash table, frame (pLoc->iZero+1).
   896    908   */
   897    909   static int walHashGet(
   898    910     Wal *pWal,                      /* WAL handle */
   899    911     int iHash,                      /* Find the iHash'th table */
   900         -  volatile ht_slot **paHash,      /* OUT: Pointer to hash index */
   901         -  volatile u32 **paPgno,          /* OUT: Pointer to page number array */
   902         -  u32 *piZero                     /* OUT: Frame associated with *paPgno[0] */
          912  +  WalHashLoc *pLoc                /* OUT: Hash table location */
   903    913   ){
   904    914     int rc;                         /* Return code */
   905         -  volatile u32 *aPgno;
   906    915   
   907         -  rc = walIndexPage(pWal, iHash, &aPgno);
          916  +  rc = walIndexPage(pWal, iHash, &pLoc->aPgno);
   908    917     assert( rc==SQLITE_OK || iHash>0 );
   909    918   
   910    919     if( rc==SQLITE_OK ){
   911         -    u32 iZero;
   912         -    volatile ht_slot *aHash;
   913         -
   914         -    aHash = (volatile ht_slot *)&aPgno[HASHTABLE_NPAGE];
          920  +    pLoc->aHash = (volatile ht_slot *)&pLoc->aPgno[HASHTABLE_NPAGE];
   915    921       if( iHash==0 ){
   916         -      aPgno = &aPgno[WALINDEX_HDR_SIZE/sizeof(u32)];
   917         -      iZero = 0;
          922  +      pLoc->aPgno = &pLoc->aPgno[WALINDEX_HDR_SIZE/sizeof(u32)];
          923  +      pLoc->iZero = 0;
   918    924       }else{
   919         -      iZero = HASHTABLE_NPAGE_ONE + (iHash-1)*HASHTABLE_NPAGE;
          925  +      pLoc->iZero = HASHTABLE_NPAGE_ONE + (iHash-1)*HASHTABLE_NPAGE;
   920    926       }
   921         -  
   922         -    *paPgno = &aPgno[-1];
   923         -    *paHash = aHash;
   924         -    *piZero = iZero;
          927  +    pLoc->aPgno = &pLoc->aPgno[-1];
   925    928     }
   926    929     return rc;
   927    930   }
   928    931   
   929    932   /*
   930    933   ** Return the number of the wal-index page that contains the hash-table
   931    934   ** and page-number array that contain entries corresponding to WAL frame
................................................................................
   963    966   **
   964    967   ** At most only the hash table containing pWal->hdr.mxFrame needs to be
   965    968   ** updated.  Any later hash tables will be automatically cleared when
   966    969   ** pWal->hdr.mxFrame advances to the point where those hash tables are
   967    970   ** actually needed.
   968    971   */
   969    972   static void walCleanupHash(Wal *pWal){
   970         -  volatile ht_slot *aHash = 0;    /* Pointer to hash table to clear */
   971         -  volatile u32 *aPgno = 0;        /* Page number array for hash table */
   972         -  u32 iZero = 0;                  /* frame == (aHash[x]+iZero) */
          973  +  WalHashLoc sLoc;                /* Hash table location */
   973    974     int iLimit = 0;                 /* Zero values greater than this */
   974    975     int nByte;                      /* Number of bytes to zero in aPgno[] */
   975    976     int i;                          /* Used to iterate through aHash[] */
   976    977   
   977    978     assert( pWal->writeLock );
   978    979     testcase( pWal->hdr.mxFrame==HASHTABLE_NPAGE_ONE-1 );
   979    980     testcase( pWal->hdr.mxFrame==HASHTABLE_NPAGE_ONE );
................................................................................
   983    984   
   984    985     /* Obtain pointers to the hash-table and page-number array containing 
   985    986     ** the entry that corresponds to frame pWal->hdr.mxFrame. It is guaranteed
   986    987     ** that the page said hash-table and array reside on is already mapped.
   987    988     */
   988    989     assert( pWal->nWiData>walFramePage(pWal->hdr.mxFrame) );
   989    990     assert( pWal->apWiData[walFramePage(pWal->hdr.mxFrame)] );
   990         -  walHashGet(pWal, walFramePage(pWal->hdr.mxFrame), &aHash, &aPgno, &iZero);
          991  +  walHashGet(pWal, walFramePage(pWal->hdr.mxFrame), &sLoc);
   991    992   
   992    993     /* Zero all hash-table entries that correspond to frame numbers greater
   993    994     ** than pWal->hdr.mxFrame.
   994    995     */
   995         -  iLimit = pWal->hdr.mxFrame - iZero;
          996  +  iLimit = pWal->hdr.mxFrame - sLoc.iZero;
   996    997     assert( iLimit>0 );
   997    998     for(i=0; i<HASHTABLE_NSLOT; i++){
   998         -    if( aHash[i]>iLimit ){
   999         -      aHash[i] = 0;
          999  +    if( sLoc.aHash[i]>iLimit ){
         1000  +      sLoc.aHash[i] = 0;
  1000   1001       }
  1001   1002     }
  1002   1003     
  1003   1004     /* Zero the entries in the aPgno array that correspond to frames with
  1004   1005     ** frame numbers greater than pWal->hdr.mxFrame. 
  1005   1006     */
  1006         -  nByte = (int)((char *)aHash - (char *)&aPgno[iLimit+1]);
  1007         -  memset((void *)&aPgno[iLimit+1], 0, nByte);
         1007  +  nByte = (int)((char *)sLoc.aHash - (char *)&sLoc.aPgno[iLimit+1]);
         1008  +  memset((void *)&sLoc.aPgno[iLimit+1], 0, nByte);
  1008   1009   
  1009   1010   #ifdef SQLITE_ENABLE_EXPENSIVE_ASSERT
  1010   1011     /* Verify that the every entry in the mapping region is still reachable
  1011   1012     ** via the hash table even after the cleanup.
  1012   1013     */
  1013   1014     if( iLimit ){
  1014   1015       int j;           /* Loop counter */
  1015   1016       int iKey;        /* Hash key */
  1016   1017       for(j=1; j<=iLimit; j++){
  1017         -      for(iKey=walHash(aPgno[j]); aHash[iKey]; iKey=walNextHash(iKey)){
  1018         -        if( aHash[iKey]==j ) break;
         1018  +      for(iKey=walHash(sLoc.aPgno[j]);sLoc.aHash[iKey];iKey=walNextHash(iKey)){
         1019  +        if( sLoc.aHash[iKey]==j ) break;
  1019   1020         }
  1020         -      assert( aHash[iKey]==j );
         1021  +      assert( sLoc.aHash[iKey]==j );
  1021   1022       }
  1022   1023     }
  1023   1024   #endif /* SQLITE_ENABLE_EXPENSIVE_ASSERT */
  1024   1025   }
  1025   1026   
  1026   1027   
  1027   1028   /*
  1028   1029   ** Set an entry in the wal-index that will map database page number
  1029   1030   ** pPage into WAL frame iFrame.
  1030   1031   */
  1031   1032   static int walIndexAppend(Wal *pWal, u32 iFrame, u32 iPage){
  1032   1033     int rc;                         /* Return code */
  1033         -  u32 iZero = 0;                  /* One less than frame number of aPgno[1] */
  1034         -  volatile u32 *aPgno = 0;        /* Page number array */
  1035         -  volatile ht_slot *aHash = 0;    /* Hash table */
         1034  +  WalHashLoc sLoc;                /* Wal-index hash table location */
  1036   1035   
  1037         -  rc = walHashGet(pWal, walFramePage(iFrame), &aHash, &aPgno, &iZero);
         1036  +  rc = walHashGet(pWal, walFramePage(iFrame), &sLoc);
  1038   1037   
  1039   1038     /* Assuming the wal-index file was successfully mapped, populate the
  1040   1039     ** page number array and hash table entry.
  1041   1040     */
  1042   1041     if( rc==SQLITE_OK ){
  1043   1042       int iKey;                     /* Hash table key */
  1044   1043       int idx;                      /* Value to write to hash-table slot */
  1045   1044       int nCollide;                 /* Number of hash collisions */
  1046   1045   
  1047         -    idx = iFrame - iZero;
         1046  +    idx = iFrame - sLoc.iZero;
  1048   1047       assert( idx <= HASHTABLE_NSLOT/2 + 1 );
  1049   1048       
  1050   1049       /* If this is the first entry to be added to this hash-table, zero the
  1051   1050       ** entire hash table and aPgno[] array before proceeding. 
  1052   1051       */
  1053   1052       if( idx==1 ){
  1054         -      int nByte = (int)((u8 *)&aHash[HASHTABLE_NSLOT] - (u8 *)&aPgno[1]);
  1055         -      memset((void*)&aPgno[1], 0, nByte);
         1053  +      int nByte = (int)((u8 *)&sLoc.aHash[HASHTABLE_NSLOT]
         1054  +                               - (u8 *)&sLoc.aPgno[1]);
         1055  +      memset((void*)&sLoc.aPgno[1], 0, nByte);
  1056   1056       }
  1057   1057   
  1058   1058       /* If the entry in aPgno[] is already set, then the previous writer
  1059   1059       ** must have exited unexpectedly in the middle of a transaction (after
  1060   1060       ** writing one or more dirty pages to the WAL to free up memory). 
  1061   1061       ** Remove the remnants of that writers uncommitted transaction from 
  1062   1062       ** the hash-table before writing any new entries.
  1063   1063       */
  1064         -    if( aPgno[idx] ){
         1064  +    if( sLoc.aPgno[idx] ){
  1065   1065         walCleanupHash(pWal);
  1066         -      assert( !aPgno[idx] );
         1066  +      assert( !sLoc.aPgno[idx] );
  1067   1067       }
  1068   1068   
  1069   1069       /* Write the aPgno[] array entry and the hash-table slot. */
  1070   1070       nCollide = idx;
  1071         -    for(iKey=walHash(iPage); aHash[iKey]; iKey=walNextHash(iKey)){
         1071  +    for(iKey=walHash(iPage); sLoc.aHash[iKey]; iKey=walNextHash(iKey)){
  1072   1072         if( (nCollide--)==0 ) return SQLITE_CORRUPT_BKPT;
  1073   1073       }
  1074         -    aPgno[idx] = iPage;
  1075         -    aHash[iKey] = (ht_slot)idx;
         1074  +    sLoc.aPgno[idx] = iPage;
         1075  +    sLoc.aHash[iKey] = (ht_slot)idx;
  1076   1076   
  1077   1077   #ifdef SQLITE_ENABLE_EXPENSIVE_ASSERT
  1078   1078       /* Verify that the number of entries in the hash table exactly equals
  1079   1079       ** the number of entries in the mapping region.
  1080   1080       */
  1081   1081       {
  1082   1082         int i;           /* Loop counter */
  1083   1083         int nEntry = 0;  /* Number of entries in the hash table */
  1084         -      for(i=0; i<HASHTABLE_NSLOT; i++){ if( aHash[i] ) nEntry++; }
         1084  +      for(i=0; i<HASHTABLE_NSLOT; i++){ if( sLoc.aHash[i] ) nEntry++; }
  1085   1085         assert( nEntry==idx );
  1086   1086       }
  1087   1087   
  1088   1088       /* Verify that the every entry in the mapping region is reachable
  1089   1089       ** via the hash table.  This turns out to be a really, really expensive
  1090   1090       ** thing to check, so only do this occasionally - not on every
  1091   1091       ** iteration.
  1092   1092       */
  1093   1093       if( (idx&0x3ff)==0 ){
  1094   1094         int i;           /* Loop counter */
  1095   1095         for(i=1; i<=idx; i++){
  1096         -        for(iKey=walHash(aPgno[i]); aHash[iKey]; iKey=walNextHash(iKey)){
  1097         -          if( aHash[iKey]==i ) break;
         1096  +        for(iKey=walHash(sLoc.aPgno[i]);
         1097  +            sLoc.aHash[iKey];
         1098  +            iKey=walNextHash(iKey)){
         1099  +          if( sLoc.aHash[iKey]==i ) break;
  1098   1100           }
  1099         -        assert( aHash[iKey]==i );
         1101  +        assert( sLoc.aHash[iKey]==i );
  1100   1102         }
  1101   1103       }
  1102   1104   #endif /* SQLITE_ENABLE_EXPENSIVE_ASSERT */
  1103   1105     }
  1104   1106   
  1105   1107   
  1106   1108     return rc;
................................................................................
  1630   1632         sizeof(ht_slot) * (iLast>HASHTABLE_NPAGE?HASHTABLE_NPAGE:iLast)
  1631   1633     );
  1632   1634     if( !aTmp ){
  1633   1635       rc = SQLITE_NOMEM_BKPT;
  1634   1636     }
  1635   1637   
  1636   1638     for(i=walFramePage(nBackfill+1); rc==SQLITE_OK && i<nSegment; i++){
  1637         -    volatile ht_slot *aHash;
  1638         -    u32 iZero;
  1639         -    volatile u32 *aPgno;
         1639  +    WalHashLoc sLoc;
  1640   1640   
  1641         -    rc = walHashGet(pWal, i, &aHash, &aPgno, &iZero);
         1641  +    rc = walHashGet(pWal, i, &sLoc);
  1642   1642       if( rc==SQLITE_OK ){
  1643   1643         int j;                      /* Counter variable */
  1644   1644         int nEntry;                 /* Number of entries in this segment */
  1645   1645         ht_slot *aIndex;            /* Sorted index for this segment */
  1646   1646   
  1647         -      aPgno++;
         1647  +      sLoc.aPgno++;
  1648   1648         if( (i+1)==nSegment ){
  1649         -        nEntry = (int)(iLast - iZero);
         1649  +        nEntry = (int)(iLast - sLoc.iZero);
  1650   1650         }else{
  1651         -        nEntry = (int)((u32*)aHash - (u32*)aPgno);
         1651  +        nEntry = (int)((u32*)sLoc.aHash - (u32*)sLoc.aPgno);
  1652   1652         }
  1653         -      aIndex = &((ht_slot *)&p->aSegment[p->nSegment])[iZero];
  1654         -      iZero++;
         1653  +      aIndex = &((ht_slot *)&p->aSegment[p->nSegment])[sLoc.iZero];
         1654  +      sLoc.iZero++;
  1655   1655     
  1656   1656         for(j=0; j<nEntry; j++){
  1657   1657           aIndex[j] = (ht_slot)j;
  1658   1658         }
  1659         -      walMergesort((u32 *)aPgno, aTmp, aIndex, &nEntry);
  1660         -      p->aSegment[i].iZero = iZero;
         1659  +      walMergesort((u32 *)sLoc.aPgno, aTmp, aIndex, &nEntry);
         1660  +      p->aSegment[i].iZero = sLoc.iZero;
  1661   1661         p->aSegment[i].nEntry = nEntry;
  1662   1662         p->aSegment[i].aIndex = aIndex;
  1663         -      p->aSegment[i].aPgno = (u32 *)aPgno;
         1663  +      p->aSegment[i].aPgno = (u32 *)sLoc.aPgno;
  1664   1664       }
  1665   1665     }
  1666   1666     sqlite3_free(aTmp);
  1667   1667   
  1668   1668     if( rc!=SQLITE_OK ){
  1669   1669       walIteratorFree(p);
  1670   1670       p = 0;
................................................................................
  2669   2669         void *pBuf1 = sqlite3_malloc(szPage);
  2670   2670         void *pBuf2 = sqlite3_malloc(szPage);
  2671   2671         if( pBuf1==0 || pBuf2==0 ){
  2672   2672           rc = SQLITE_NOMEM;
  2673   2673         }else{
  2674   2674           u32 i = pInfo->nBackfillAttempted;
  2675   2675           for(i=pInfo->nBackfillAttempted; i>pInfo->nBackfill; i--){
  2676         -          volatile ht_slot *dummy;
  2677         -          volatile u32 *aPgno;      /* Array of page numbers */
  2678         -          u32 iZero;                /* Frame corresponding to aPgno[0] */
         2676  +          WalHashLoc sLoc;          /* Hash table location */
  2679   2677             u32 pgno;                 /* Page number in db file */
  2680   2678             i64 iDbOff;               /* Offset of db file entry */
  2681   2679             i64 iWalOff;              /* Offset of wal file entry */
  2682   2680   
  2683         -          rc = walHashGet(pWal, walFramePage(i), &dummy, &aPgno, &iZero);
         2681  +          rc = walHashGet(pWal, walFramePage(i), &sLoc);
  2684   2682             if( rc!=SQLITE_OK ) break;
  2685         -          pgno = aPgno[i-iZero];
         2683  +          pgno = sLoc.aPgno[i-sLoc.iZero];
  2686   2684             iDbOff = (i64)(pgno-1) * szPage;
  2687   2685   
  2688   2686             if( iDbOff+szPage<=szDb ){
  2689   2687               iWalOff = walFrameOffset(i, szPage) + WAL_FRAME_HDRSIZE;
  2690   2688               rc = sqlite3OsRead(pWal->pWalFd, pBuf1, szPage, iWalOff);
  2691   2689   
  2692   2690               if( rc==SQLITE_OK ){
................................................................................
  2879   2877     **
  2880   2878     **   (iFrame<=iLast): 
  2881   2879     **     This condition filters out entries that were added to the hash
  2882   2880     **     table after the current read-transaction had started.
  2883   2881     */
  2884   2882     iMinHash = walFramePage(pWal->minFrame);
  2885   2883     for(iHash=walFramePage(iLast); iHash>=iMinHash; iHash--){
  2886         -    volatile ht_slot *aHash;      /* Pointer to hash table */
  2887         -    volatile u32 *aPgno;          /* Pointer to array of page numbers */
  2888         -    u32 iZero;                    /* Frame number corresponding to aPgno[0] */
         2884  +    WalHashLoc sLoc;              /* Hash table location */
  2889   2885       int iKey;                     /* Hash slot index */
  2890   2886       int nCollide;                 /* Number of hash collisions remaining */
  2891   2887       int rc;                       /* Error code */
  2892   2888   
  2893         -    rc = walHashGet(pWal, iHash, &aHash, &aPgno, &iZero);
         2889  +    rc = walHashGet(pWal, iHash, &sLoc);
  2894   2890       if( rc!=SQLITE_OK ){
  2895   2891         return rc;
  2896   2892       }
  2897   2893       nCollide = HASHTABLE_NSLOT;
  2898         -    for(iKey=walHash(pgno); aHash[iKey]; iKey=walNextHash(iKey)){
  2899         -      u32 iFrame = aHash[iKey] + iZero;
  2900         -      if( iFrame<=iLast && iFrame>=pWal->minFrame && aPgno[aHash[iKey]]==pgno ){
         2894  +    for(iKey=walHash(pgno); sLoc.aHash[iKey]; iKey=walNextHash(iKey)){
         2895  +      u32 iFrame = sLoc.aHash[iKey] + sLoc.iZero;
         2896  +      if( iFrame<=iLast && iFrame>=pWal->minFrame
         2897  +       && sLoc.aPgno[sLoc.aHash[iKey]]==pgno ){
  2901   2898           assert( iFrame>iRead || CORRUPT_DB );
  2902   2899           iRead = iFrame;
  2903   2900         }
  2904   2901         if( (nCollide--)==0 ){
  2905   2902           return SQLITE_CORRUPT_BKPT;
  2906   2903         }
  2907   2904       }

Changes to src/where.c.

  2447   2447           || (pNew->wsFlags & WHERE_COLUMN_NULL)!=0 
  2448   2448           || (pNew->wsFlags & WHERE_COLUMN_IN)!=0 
  2449   2449           || (pNew->wsFlags & WHERE_SKIPSCAN)!=0 
  2450   2450       );
  2451   2451   
  2452   2452       if( eOp & WO_IN ){
  2453   2453         Expr *pExpr = pTerm->pExpr;
  2454         -      pNew->wsFlags |= WHERE_COLUMN_IN;
  2455   2454         if( ExprHasProperty(pExpr, EP_xIsSelect) ){
  2456   2455           /* "x IN (SELECT ...)":  TUNING: the SELECT returns 25 rows */
  2457   2456           int i;
  2458   2457           nIn = 46;  assert( 46==sqlite3LogEst(25) );
  2459   2458   
  2460   2459           /* The expression may actually be of the form (x, y) IN (SELECT...).
  2461   2460           ** In this case there is a separate term for each of (x) and (y).
................................................................................
  2467   2466           }
  2468   2467         }else if( ALWAYS(pExpr->x.pList && pExpr->x.pList->nExpr) ){
  2469   2468           /* "x IN (value, value, ...)" */
  2470   2469           nIn = sqlite3LogEst(pExpr->x.pList->nExpr);
  2471   2470           assert( nIn>0 );  /* RHS always has 2 or more terms...  The parser
  2472   2471                             ** changes "x IN (?)" into "x=?". */
  2473   2472         }
         2473  +      if( pProbe->hasStat1 ){
         2474  +        LogEst M, logK, safetyMargin;
         2475  +        /* Let:
         2476  +        **   N = the total number of rows in the table
         2477  +        **   K = the number of entries on the RHS of the IN operator
         2478  +        **   M = the number of rows in the table that match terms to the 
         2479  +        **       to the left in the same index.  If the IN operator is on
         2480  +        **       the left-most index column, M==N.
         2481  +        **
         2482  +        ** Given the definitions above, it is better to omit the IN operator
         2483  +        ** from the index lookup and instead do a scan of the M elements,
         2484  +        ** testing each scanned row against the IN operator separately, if:
         2485  +        **
         2486  +        **        M*log(K) < K*log(N)
         2487  +        **
         2488  +        ** Our estimates for M, K, and N might be inaccurate, so we build in
         2489  +        ** a safety margin of 2 (LogEst: 10) that favors using the IN operator
         2490  +        ** with the index, as using an index has better worst-case behavior.
         2491  +        ** If we do not have real sqlite_stat1 data, always prefer to use
         2492  +        ** the index.
         2493  +        */
         2494  +        M = pProbe->aiRowLogEst[saved_nEq];
         2495  +        logK = estLog(nIn);
         2496  +        safetyMargin = 10;  /* TUNING: extra weight for indexed IN */
         2497  +        if( M + logK + safetyMargin < nIn + rLogSize ){
         2498  +          WHERETRACE(0x40,
         2499  +            ("Scan preferred over IN operator on column %d of \"%s\" (%d<%d)\n",
         2500  +             saved_nEq, pProbe->zName, M+logK+10, nIn+rLogSize));
         2501  +          continue;
         2502  +        }else{
         2503  +          WHERETRACE(0x40,
         2504  +            ("IN operator preferred on column %d of \"%s\" (%d>=%d)\n",
         2505  +             saved_nEq, pProbe->zName, M+logK+10, nIn+rLogSize));
         2506  +        }
         2507  +      }
         2508  +      pNew->wsFlags |= WHERE_COLUMN_IN;
  2474   2509       }else if( eOp & (WO_EQ|WO_IS) ){
  2475   2510         int iCol = pProbe->aiColumn[saved_nEq];
  2476   2511         pNew->wsFlags |= WHERE_COLUMN_EQ;
  2477   2512         assert( saved_nEq==pNew->u.btree.nEq );
  2478   2513         if( iCol==XN_ROWID 
  2479   2514          || (iCol>=0 && nInMul==0 && saved_nEq==pProbe->nKeyCol-1)
  2480   2515         ){
................................................................................
  2696   2731           }
  2697   2732         }
  2698   2733       }
  2699   2734     }
  2700   2735     return 0;
  2701   2736   }
  2702   2737   
  2703         -/*
  2704         -** Return a bitmask where 1s indicate that the corresponding column of
  2705         -** the table is used by an index.  Only the first 63 columns are considered.
  2706         -*/
  2707         -static Bitmask columnsInIndex(Index *pIdx){
  2708         -  Bitmask m = 0;
  2709         -  int j;
  2710         -  for(j=pIdx->nColumn-1; j>=0; j--){
  2711         -    int x = pIdx->aiColumn[j];
  2712         -    if( x>=0 ){
  2713         -      testcase( x==BMS-1 );
  2714         -      testcase( x==BMS-2 );
  2715         -      if( x<BMS-1 ) m |= MASKBIT(x);
  2716         -    }
  2717         -  }
  2718         -  return m;
  2719         -}
  2720         -
  2721   2738   /* Check to see if a partial index with pPartIndexWhere can be used
  2722   2739   ** in the current query.  Return true if it can be and false if not.
  2723   2740   */
  2724   2741   static int whereUsablePartialIndex(int iTab, WhereClause *pWC, Expr *pWhere){
  2725   2742     int i;
  2726   2743     WhereTerm *pTerm;
  2727   2744     Parse *pParse = pWC->pWInfo->pParse;
................................................................................
  2929   2946         if( rc ) break;
  2930   2947       }else{
  2931   2948         Bitmask m;
  2932   2949         if( pProbe->isCovering ){
  2933   2950           pNew->wsFlags = WHERE_IDX_ONLY | WHERE_INDEXED;
  2934   2951           m = 0;
  2935   2952         }else{
  2936         -        m = pSrc->colUsed & ~columnsInIndex(pProbe);
         2953  +        m = pSrc->colUsed & pProbe->colNotIdxed;
  2937   2954           pNew->wsFlags = (m==0) ? (WHERE_IDX_ONLY|WHERE_INDEXED) : WHERE_INDEXED;
  2938   2955         }
  2939   2956   
  2940   2957         /* Full scan via index */
  2941   2958         if( b
  2942   2959          || !HasRowid(pTab)
  2943   2960          || pProbe->pPartIdxWhere!=0
................................................................................
  3496   3513         }
  3497   3514         rc = whereLoopAddVirtual(pBuilder, mPrereq, mUnusable);
  3498   3515       }else
  3499   3516   #endif /* SQLITE_OMIT_VIRTUALTABLE */
  3500   3517       {
  3501   3518         rc = whereLoopAddBtree(pBuilder, mPrereq);
  3502   3519       }
  3503         -    if( rc==SQLITE_OK ){
         3520  +    if( rc==SQLITE_OK && pBuilder->pWC->hasOr ){
  3504   3521         rc = whereLoopAddOr(pBuilder, mPrereq, mUnusable);
  3505   3522       }
  3506   3523       mPrior |= pNew->maskSelf;
  3507   3524       if( rc || db->mallocFailed ) break;
  3508   3525     }
  3509   3526   
  3510   3527     whereLoopClear(db, pNew);
................................................................................
  4332   4349           pTerm = sqlite3WhereFindTerm(pWC, iCur, j, 0, opMask, pIdx);
  4333   4350           if( pTerm==0 ) break;
  4334   4351           testcase( pTerm->eOperator & WO_IS );
  4335   4352           pLoop->aLTerm[j] = pTerm;
  4336   4353         }
  4337   4354         if( j!=pIdx->nKeyCol ) continue;
  4338   4355         pLoop->wsFlags = WHERE_COLUMN_EQ|WHERE_ONEROW|WHERE_INDEXED;
  4339         -      if( pIdx->isCovering || (pItem->colUsed & ~columnsInIndex(pIdx))==0 ){
         4356  +      if( pIdx->isCovering || (pItem->colUsed & pIdx->colNotIdxed)==0 ){
  4340   4357           pLoop->wsFlags |= WHERE_IDX_ONLY;
  4341   4358         }
  4342   4359         pLoop->nLTerm = j;
  4343   4360         pLoop->u.btree.nEq = j;
  4344   4361         pLoop->u.btree.pIndex = pIdx;
  4345   4362         /* TUNING: Cost of a unique index lookup is 15 */
  4346   4363         pLoop->rRun = 39;  /* 39==sqlite3LogEst(15) */

Changes to src/whereInt.h.

   318    318   ** the subclauses "(b AND c)" and "(d AND e)".  The pOuter field of the
   319    319   ** subclauses points to the WhereClause object for the whole clause.
   320    320   */
   321    321   struct WhereClause {
   322    322     WhereInfo *pWInfo;       /* WHERE clause processing context */
   323    323     WhereClause *pOuter;     /* Outer conjunction */
   324    324     u8 op;                   /* Split operator.  TK_AND or TK_OR */
          325  +  u8 hasOr;                /* True if any a[].eOperator is WO_OR */
   325    326     int nTerm;               /* Number of terms */
   326    327     int nSlot;               /* Number of entries in a[] */
   327    328     WhereTerm *a;            /* Each a[] describes a term of the WHERE cluase */
   328    329   #if defined(SQLITE_SMALL_STACK)
   329    330     WhereTerm aStatic[1];    /* Initial static space for a[] */
   330    331   #else
   331    332     WhereTerm aStatic[8];    /* Initial static space for a[] */
................................................................................
   491    492   );
   492    493   
   493    494   /* whereexpr.c: */
   494    495   void sqlite3WhereClauseInit(WhereClause*,WhereInfo*);
   495    496   void sqlite3WhereClauseClear(WhereClause*);
   496    497   void sqlite3WhereSplit(WhereClause*,Expr*,u8);
   497    498   Bitmask sqlite3WhereExprUsage(WhereMaskSet*, Expr*);
          499  +Bitmask sqlite3WhereExprUsageNN(WhereMaskSet*, Expr*);
   498    500   Bitmask sqlite3WhereExprListUsage(WhereMaskSet*, ExprList*);
   499    501   void sqlite3WhereExprAnalyze(SrcList*, WhereClause*);
   500    502   void sqlite3WhereTabFuncArgs(Parse*, struct SrcList_item*, WhereClause*);
   501    503   
   502    504   
   503    505   
   504    506   

Changes to src/whereexpr.c.

   668    668     }
   669    669   
   670    670     /*
   671    671     ** Record the set of tables that satisfy case 3.  The set might be
   672    672     ** empty.
   673    673     */
   674    674     pOrInfo->indexable = indexable;
   675         -  pTerm->eOperator = indexable==0 ? 0 : WO_OR;
          675  +  if( indexable ){
          676  +    pTerm->eOperator = WO_OR;
          677  +    pWC->hasOr = 1;
          678  +  }else{
          679  +    pTerm->eOperator = WO_OR;
          680  +  }
   676    681   
   677    682     /* For a two-way OR, attempt to implementation case 2.
   678    683     */
   679    684     if( indexable && pOrWc->nTerm==2 ){
   680    685       int iOne = 0;
   681    686       WhereTerm *pOne;
   682    687       while( (pOne = whereNthSubterm(&pOrWc->a[0],iOne++))!=0 ){
................................................................................
  1007   1012       }
  1008   1013     }else if( op==TK_ISNULL ){
  1009   1014       pTerm->prereqRight = 0;
  1010   1015     }else{
  1011   1016       pTerm->prereqRight = sqlite3WhereExprUsage(pMaskSet, pExpr->pRight);
  1012   1017     }
  1013   1018     pMaskSet->bVarSelect = 0;
  1014         -  prereqAll = sqlite3WhereExprUsage(pMaskSet, pExpr);
         1019  +  prereqAll = sqlite3WhereExprUsageNN(pMaskSet, pExpr);
  1015   1020     if( pMaskSet->bVarSelect ) pTerm->wtFlags |= TERM_VARSELECT;
  1016   1021     if( ExprHasProperty(pExpr, EP_FromJoin) ){
  1017   1022       Bitmask x = sqlite3WhereGetMask(pMaskSet, pExpr->iRightJoinTable);
  1018   1023       prereqAll |= x;
  1019   1024       extraRight = x-1;  /* ON clause terms may not be used with an index
  1020   1025                          ** on left table of a LEFT JOIN.  Ticket #3015 */
  1021   1026       if( (prereqAll>>1)>=x ){
................................................................................
  1436   1441   
  1437   1442   
  1438   1443   /*
  1439   1444   ** These routines walk (recursively) an expression tree and generate
  1440   1445   ** a bitmask indicating which tables are used in that expression
  1441   1446   ** tree.
  1442   1447   */
  1443         -Bitmask sqlite3WhereExprUsage(WhereMaskSet *pMaskSet, Expr *p){
         1448  +Bitmask sqlite3WhereExprUsageNN(WhereMaskSet *pMaskSet, Expr *p){
  1444   1449     Bitmask mask;
  1445         -  if( p==0 ) return 0;
  1446   1450     if( p->op==TK_COLUMN ){
  1447   1451       return sqlite3WhereGetMask(pMaskSet, p->iTable);
         1452  +  }else if( ExprHasProperty(p, EP_TokenOnly|EP_Leaf) ){
         1453  +    assert( p->op!=TK_IF_NULL_ROW );
         1454  +    return 0;
  1448   1455     }
  1449   1456     mask = (p->op==TK_IF_NULL_ROW) ? sqlite3WhereGetMask(pMaskSet, p->iTable) : 0;
  1450         -  assert( !ExprHasProperty(p, EP_TokenOnly) );
  1451         -  if( p->pLeft ) mask |= sqlite3WhereExprUsage(pMaskSet, p->pLeft);
         1457  +  if( p->pLeft ) mask |= sqlite3WhereExprUsageNN(pMaskSet, p->pLeft);
  1452   1458     if( p->pRight ){
  1453         -    mask |= sqlite3WhereExprUsage(pMaskSet, p->pRight);
         1459  +    mask |= sqlite3WhereExprUsageNN(pMaskSet, p->pRight);
  1454   1460       assert( p->x.pList==0 );
  1455   1461     }else if( ExprHasProperty(p, EP_xIsSelect) ){
  1456   1462       if( ExprHasProperty(p, EP_VarSelect) ) pMaskSet->bVarSelect = 1;
  1457   1463       mask |= exprSelectUsage(pMaskSet, p->x.pSelect);
  1458   1464     }else if( p->x.pList ){
  1459   1465       mask |= sqlite3WhereExprListUsage(pMaskSet, p->x.pList);
  1460   1466     }
  1461   1467     return mask;
         1468  +}
         1469  +Bitmask sqlite3WhereExprUsage(WhereMaskSet *pMaskSet, Expr *p){
         1470  +  return p ? sqlite3WhereExprUsageNN(pMaskSet,p) : 0;
  1462   1471   }
  1463   1472   Bitmask sqlite3WhereExprListUsage(WhereMaskSet *pMaskSet, ExprList *pList){
  1464   1473     int i;
  1465   1474     Bitmask mask = 0;
  1466   1475     if( pList ){
  1467   1476       for(i=0; i<pList->nExpr; i++){
  1468   1477         mask |= sqlite3WhereExprUsage(pMaskSet, pList->a[i].pExpr);

Changes to test/in6.test.

    24     24   do_test in6-1.1 {
    25     25     db eval {
    26     26       CREATE TABLE t1(a,b,c,d);
    27     27       WITH RECURSIVE c(x) AS (VALUES(1) UNION ALL SELECT x+1 FROM c WHERE x<100)
    28     28         INSERT INTO t1(a,b,c,d)
    29     29           SELECT 100, 200+x/2, 300+x/5, x FROM c;
    30     30       CREATE INDEX t1abc ON t1(a,b,c);
           31  +    ANALYZE;
           32  +    UPDATE sqlite_stat1 SET stat='1000000 500000 500 50';
           33  +    ANALYZE sqlite_master;
    31     34     }
    32     35     set ::sqlite_search_count 0
    33     36     db eval {
    34     37       SELECT d FROM t1
    35     38        WHERE a=99
    36     39          AND b IN (200,205,201,204)
    37     40          AND c IN (304,302,309,308);

Changes to test/rowvalue4.test.

   220    220     CREATE TABLE d2(a, b, c);
   221    221     CREATE INDEX d2ab ON d2(a, b);
   222    222     CREATE INDEX d2c ON d2(c);
   223    223   
   224    224     WITH i(i) AS (
   225    225       VALUES(1) UNION ALL SELECT i+1 FROM i WHERE i<1000
   226    226     )
   227         -  INSERT INTO d2 SELECT i/3, i%3, i/3 FROM i;
          227  +  INSERT INTO d2 SELECT i/100, i%100, i/100 FROM i;
   228    228     ANALYZE;
   229    229   }
   230    230   
   231    231   do_eqp_test 5.1 {
   232    232     SELECT * FROM d2 WHERE 
   233    233       (a, b) IN (SELECT x, y FROM d1) AND
   234    234       (c) IN (SELECT y FROM d1)