/ Check-in [f3789968]
Login
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

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 Unified Diffs Ignore Whitespace Patch

Changes to ext/fts5/fts5_index.c.

2128
2129
2130
2131
2132
2133
2134













2135
2136
2137
2138
2139
2140








2141
2142
2143
2144
2145
2146
2147
....
2164
2165
2166
2167
2168
2169
2170
2171
2172
2173
2174
2175
2176

2177
2178
2179
2180
2181
2182
2183
....
2196
2197
2198
2199
2200
2201
2202
2203
2204
2205
2206
2207
2208
2209
2210
2211
2212
2213
2214
2215
2216
2217
2218
2219
2220
2221

2222
2223
2224
2225
2226
2227
2228
    *pbDlidx = 0;
    pPtr += nNew;
  }

  fts5AssertNodeSeekOk(pNode, pTerm, nTerm, iPg, *pbDlidx);
  return iPg;
}














/*
** The iterator object passed as the second argument currently contains
** no valid values except for the Fts5SegIter.pLeaf member variable. This
** function searches the leaf page for a term matching (pTerm/nTerm).
**








*/
static void fts5LeafSeek(
  Fts5Index *p,                   /* Leave any error code here */
  int bGe,                        /* True for a >= search */
  Fts5SegIter *pIter,             /* Iterator to seek */
  const u8 *pTerm, int nTerm      /* Term to search for */
){
................................................................................

  while( 1 ){
    int i;
    int nCmp;
    i64 rowid;

    /* Figure out how many new bytes are in this term */

    nNew = a[iOff++];
    if( nNew & 0x80 ){ 
      iOff--;
      iOff += fts5GetVarint32(&a[iOff], nNew);
    }


    if( nKeep<nMatch ){
      goto search_failed;
    }

    assert( nKeep>=nMatch );
    if( nKeep==nMatch ){
................................................................................
      }else if( i<nNew && a[iOff+i]>pTerm[nMatch] ){
        goto search_failed;
      }
    }
    iOff += nNew;

    /* Skip past the doclist. If the end of the page is reached, bail out. */
    iOff += fts5GetVarint(&a[iOff], &rowid);
    while( iOff<n ){
      int nPos;

      iOff += fts5GetVarint32(&a[iOff], nPos);
      iOff += (nPos / 2);

      /* Skip past docid delta */
      iOff += fts5GetVarint(&a[iOff], &rowid);
      if( rowid==0 ) break;
    };
    if( iOff>=n ) goto search_failed;

    /* Read the nKeep field of the next term. */
    nKeep = a[iOff++];
    if( nKeep & 0x80 ){
      iOff--;
      iOff += fts5GetVarint32(&a[iOff], nKeep);
    }

  }

 search_failed:
  if( bGe==0 ){
    fts5DataRelease(pIter->pLeaf);
    pIter->pLeaf = 0;
    return;







>
>
>
>
>
>
>
>
>
>
>
>
>






>
>
>
>
>
>
>
>







 







<
<
<
<
<
<
>







 







|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
>







2128
2129
2130
2131
2132
2133
2134
2135
2136
2137
2138
2139
2140
2141
2142
2143
2144
2145
2146
2147
2148
2149
2150
2151
2152
2153
2154
2155
2156
2157
2158
2159
2160
2161
2162
2163
2164
2165
2166
2167
2168
....
2185
2186
2187
2188
2189
2190
2191






2192
2193
2194
2195
2196
2197
2198
2199
....
2212
2213
2214
2215
2216
2217
2218
2219
2220
2221
2222
2223
2224
2225
2226
2227
2228
2229
2230
2231
2232
2233
2234
2235
2236
2237
2238
2239
2240
2241
2242
2243
2244
2245
    *pbDlidx = 0;
    pPtr += nNew;
  }

  fts5AssertNodeSeekOk(pNode, pTerm, nTerm, iPg, *pbDlidx);
  return iPg;
}

#define fts5IndexGetVarint32(a, iOff, nVal) {     \
  nVal = a[iOff++];                               \
  if( nVal & 0x80 ){                              \
    iOff--;                                       \
    iOff += fts5GetVarint32(&a[iOff], nVal);      \
  }                                               \
}

#define fts5IndexSkipVarint(a, iOff) {            \
  int iEnd = iOff+9;                              \
  while( (a[iOff++] & 0x80) && iOff<iEnd );       \
}

/*
** The iterator object passed as the second argument currently contains
** no valid values except for the Fts5SegIter.pLeaf member variable. This
** function searches the leaf page for a term matching (pTerm/nTerm).
**
** If the specified term is found on the page, then the iterator is left
** pointing to it. If argument bGe is zero and the term is not found,
** the iterator is left pointing at EOF.
**
** If bGe is non-zero and the specified term is not found, then the
** iterator is left pointing to the smallest term in the segment that
** is larger than the specified term, even if this term is not on the
** current page.
*/
static void fts5LeafSeek(
  Fts5Index *p,                   /* Leave any error code here */
  int bGe,                        /* True for a >= search */
  Fts5SegIter *pIter,             /* Iterator to seek */
  const u8 *pTerm, int nTerm      /* Term to search for */
){
................................................................................

  while( 1 ){
    int i;
    int nCmp;
    i64 rowid;

    /* Figure out how many new bytes are in this term */






    fts5IndexGetVarint32(a, iOff, nNew);

    if( nKeep<nMatch ){
      goto search_failed;
    }

    assert( nKeep>=nMatch );
    if( nKeep==nMatch ){
................................................................................
      }else if( i<nNew && a[iOff+i]>pTerm[nMatch] ){
        goto search_failed;
      }
    }
    iOff += nNew;

    /* Skip past the doclist. If the end of the page is reached, bail out. */
    while( 1 ){
      int nPos;

      /* Skip past docid delta */
      fts5IndexSkipVarint(a, iOff);

      /* Skip past position list */
      fts5IndexGetVarint32(a, iOff, nPos);
      iOff += (nPos >> 1);
      if( iOff>=n ) goto search_failed;

      /* If this is the end of the doclist, break out of the loop */
      if( a[iOff]==0x00 ){
        iOff++;
        break;
      }
    };

    /* Read the nKeep field of the next term. */
    fts5IndexGetVarint32(a, iOff, nKeep);
  }

 search_failed:
  if( bGe==0 ){
    fts5DataRelease(pIter->pLeaf);
    pIter->pLeaf = 0;
    return;