SQLite

Check-in [f37899686c]
Login

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

Overview
Comment:Further optimizations for fts5 b-tree seeks.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: f37899686c032145f431f81c1072738536c61c7e
User & Date: dan 2015-07-07 08:29:32.749
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: 6441f2dc9e user: dan tags: trunk)
08:29
Further optimizations for fts5 b-tree seeks. (check-in: f37899686c user: dan tags: trunk)
2015-07-06
20:27
Speed up seek operations on fts5 b-tree structures. (check-in: 7b7da1eb43 user: dan tags: trunk)
Changes
Unified Diff Show Whitespace Changes 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
    *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 */
){







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






>
>
>
>
>
>
>
>







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
    *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 */
){
2164
2165
2166
2167
2168
2169
2170
2171
2172
2173
2174
2175
2176
2177
2178
2179
2180
2181
2182
2183

  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 ){







|
<
<
<
<
<







2185
2186
2187
2188
2189
2190
2191
2192





2193
2194
2195
2196
2197
2198
2199

  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 ){
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
      }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;







<
|


>
>
|
>
>
|
>

<
>
|
>
|
>

<


<
<
<
|
<







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
      }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;