/ Check-in [f3789968]
Login

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

Overview
Comment:Further optimizations for fts5 b-tree seeks.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: f37899686c032145f431f81c1072738536c61c7e
User & Date: dan 2015-07-07 08:29:32
Context
2015-07-07
19:07
Add a test case to verify that "PRAGMA data_version" works as expected when an OTA client writes to the database. check-in: 6441f2dc user: dan tags: trunk
08:29
Further optimizations for fts5 b-tree seeks. check-in: f3789968 user: dan tags: trunk
2015-07-06
20:27
Speed up seek operations on fts5 b-tree structures. check-in: 7b7da1eb user: dan tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to ext/fts5/fts5_index.c.

  2128   2128       *pbDlidx = 0;
  2129   2129       pPtr += nNew;
  2130   2130     }
  2131   2131   
  2132   2132     fts5AssertNodeSeekOk(pNode, pTerm, nTerm, iPg, *pbDlidx);
  2133   2133     return iPg;
  2134   2134   }
         2135  +
         2136  +#define fts5IndexGetVarint32(a, iOff, nVal) {     \
         2137  +  nVal = a[iOff++];                               \
         2138  +  if( nVal & 0x80 ){                              \
         2139  +    iOff--;                                       \
         2140  +    iOff += fts5GetVarint32(&a[iOff], nVal);      \
         2141  +  }                                               \
         2142  +}
         2143  +
         2144  +#define fts5IndexSkipVarint(a, iOff) {            \
         2145  +  int iEnd = iOff+9;                              \
         2146  +  while( (a[iOff++] & 0x80) && iOff<iEnd );       \
         2147  +}
  2135   2148   
  2136   2149   /*
  2137   2150   ** The iterator object passed as the second argument currently contains
  2138   2151   ** no valid values except for the Fts5SegIter.pLeaf member variable. This
  2139   2152   ** function searches the leaf page for a term matching (pTerm/nTerm).
  2140   2153   **
         2154  +** If the specified term is found on the page, then the iterator is left
         2155  +** pointing to it. If argument bGe is zero and the term is not found,
         2156  +** the iterator is left pointing at EOF.
         2157  +**
         2158  +** If bGe is non-zero and the specified term is not found, then the
         2159  +** iterator is left pointing to the smallest term in the segment that
         2160  +** is larger than the specified term, even if this term is not on the
         2161  +** current page.
  2141   2162   */
  2142   2163   static void fts5LeafSeek(
  2143   2164     Fts5Index *p,                   /* Leave any error code here */
  2144   2165     int bGe,                        /* True for a >= search */
  2145   2166     Fts5SegIter *pIter,             /* Iterator to seek */
  2146   2167     const u8 *pTerm, int nTerm      /* Term to search for */
  2147   2168   ){
................................................................................
  2164   2185   
  2165   2186     while( 1 ){
  2166   2187       int i;
  2167   2188       int nCmp;
  2168   2189       i64 rowid;
  2169   2190   
  2170   2191       /* Figure out how many new bytes are in this term */
  2171         -
  2172         -    nNew = a[iOff++];
  2173         -    if( nNew & 0x80 ){ 
  2174         -      iOff--;
  2175         -      iOff += fts5GetVarint32(&a[iOff], nNew);
  2176         -    }
         2192  +    fts5IndexGetVarint32(a, iOff, nNew);
  2177   2193   
  2178   2194       if( nKeep<nMatch ){
  2179   2195         goto search_failed;
  2180   2196       }
  2181   2197   
  2182   2198       assert( nKeep>=nMatch );
  2183   2199       if( nKeep==nMatch ){
................................................................................
  2196   2212         }else if( i<nNew && a[iOff+i]>pTerm[nMatch] ){
  2197   2213           goto search_failed;
  2198   2214         }
  2199   2215       }
  2200   2216       iOff += nNew;
  2201   2217   
  2202   2218       /* Skip past the doclist. If the end of the page is reached, bail out. */
  2203         -    iOff += fts5GetVarint(&a[iOff], &rowid);
  2204         -    while( iOff<n ){
         2219  +    while( 1 ){
  2205   2220         int nPos;
  2206   2221   
  2207         -      iOff += fts5GetVarint32(&a[iOff], nPos);
  2208         -      iOff += (nPos / 2);
  2209         -
  2210   2222         /* Skip past docid delta */
  2211         -      iOff += fts5GetVarint(&a[iOff], &rowid);
  2212         -      if( rowid==0 ) break;
         2223  +      fts5IndexSkipVarint(a, iOff);
         2224  +
         2225  +      /* Skip past position list */
         2226  +      fts5IndexGetVarint32(a, iOff, nPos);
         2227  +      iOff += (nPos >> 1);
         2228  +      if( iOff>=n ) goto search_failed;
         2229  +
         2230  +      /* If this is the end of the doclist, break out of the loop */
         2231  +      if( a[iOff]==0x00 ){
         2232  +        iOff++;
         2233  +        break;
         2234  +      }
  2213   2235       };
  2214         -    if( iOff>=n ) goto search_failed;
  2215   2236   
  2216   2237       /* Read the nKeep field of the next term. */
  2217         -    nKeep = a[iOff++];
  2218         -    if( nKeep & 0x80 ){
  2219         -      iOff--;
  2220         -      iOff += fts5GetVarint32(&a[iOff], nKeep);
  2221         -    }
         2238  +    fts5IndexGetVarint32(a, iOff, nKeep);
  2222   2239     }
  2223   2240   
  2224   2241    search_failed:
  2225   2242     if( bGe==0 ){
  2226   2243       fts5DataRelease(pIter->pLeaf);
  2227   2244       pIter->pLeaf = 0;
  2228   2245       return;