/ Check-in [60a8bde0]
Login

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

Overview
Comment:Another optimization for fts5 prefix (and other) queries.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 60a8bde055a960c5b8cb4e231802c75617c942d8
User & Date: dan 2015-10-19 20:49:10
Context
2015-10-20
15:49
Initialize variables in the fts5 integrity-check code to avoid compiler warnings. check-in: e979e2cc user: dan tags: trunk
2015-10-19
20:49
Another optimization for fts5 prefix (and other) queries. check-in: 60a8bde0 user: dan tags: trunk
17:43
Another tweak to improve performance of fts5 prefix queries. check-in: 69be427c user: dan tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to ext/fts5/fts5Int.h.

220
221
222
223
224
225
226

227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245





246
247
248
249
250
251
252
typedef struct Fts5Buffer Fts5Buffer;
struct Fts5Buffer {
  u8 *p;
  int n;
  int nSpace;
};


int sqlite3Fts5BufferGrow(int*, Fts5Buffer*, int);
void sqlite3Fts5BufferAppendVarint(int*, Fts5Buffer*, i64);
void sqlite3Fts5BufferAppendBlob(int*, Fts5Buffer*, int, const u8*);
void sqlite3Fts5BufferAppendString(int *, Fts5Buffer*, const char*);
void sqlite3Fts5BufferFree(Fts5Buffer*);
void sqlite3Fts5BufferZero(Fts5Buffer*);
void sqlite3Fts5BufferSet(int*, Fts5Buffer*, int, const u8*);
void sqlite3Fts5BufferAppendPrintf(int *, Fts5Buffer*, char *zFmt, ...);
void sqlite3Fts5BufferAppend32(int*, Fts5Buffer*, int);

char *sqlite3Fts5Mprintf(int *pRc, const char *zFmt, ...);

#define fts5BufferZero(x)             sqlite3Fts5BufferZero(x)
#define fts5BufferGrow(a,b,c)         sqlite3Fts5BufferGrow(a,b,c)
#define fts5BufferAppendVarint(a,b,c) sqlite3Fts5BufferAppendVarint(a,b,c)
#define fts5BufferFree(a)             sqlite3Fts5BufferFree(a)
#define fts5BufferAppendBlob(a,b,c,d) sqlite3Fts5BufferAppendBlob(a,b,c,d)
#define fts5BufferSet(a,b,c,d)        sqlite3Fts5BufferSet(a,b,c,d)
#define fts5BufferAppend32(a,b,c)     sqlite3Fts5BufferAppend32(a,b,c)






/* Write and decode big-endian 32-bit integer values */
void sqlite3Fts5Put32(u8*, int);
int sqlite3Fts5Get32(const u8*);

#define FTS5_POS2COLUMN(iPos) (int)(iPos >> 32)
#define FTS5_POS2OFFSET(iPos) (int)(iPos & 0xFFFFFFFF)







>













<





>
>
>
>
>







220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240

241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
typedef struct Fts5Buffer Fts5Buffer;
struct Fts5Buffer {
  u8 *p;
  int n;
  int nSpace;
};

int sqlite3Fts5BufferSize(int*, Fts5Buffer*, int);
int sqlite3Fts5BufferGrow(int*, Fts5Buffer*, int);
void sqlite3Fts5BufferAppendVarint(int*, Fts5Buffer*, i64);
void sqlite3Fts5BufferAppendBlob(int*, Fts5Buffer*, int, const u8*);
void sqlite3Fts5BufferAppendString(int *, Fts5Buffer*, const char*);
void sqlite3Fts5BufferFree(Fts5Buffer*);
void sqlite3Fts5BufferZero(Fts5Buffer*);
void sqlite3Fts5BufferSet(int*, Fts5Buffer*, int, const u8*);
void sqlite3Fts5BufferAppendPrintf(int *, Fts5Buffer*, char *zFmt, ...);
void sqlite3Fts5BufferAppend32(int*, Fts5Buffer*, int);

char *sqlite3Fts5Mprintf(int *pRc, const char *zFmt, ...);

#define fts5BufferZero(x)             sqlite3Fts5BufferZero(x)

#define fts5BufferAppendVarint(a,b,c) sqlite3Fts5BufferAppendVarint(a,b,c)
#define fts5BufferFree(a)             sqlite3Fts5BufferFree(a)
#define fts5BufferAppendBlob(a,b,c,d) sqlite3Fts5BufferAppendBlob(a,b,c,d)
#define fts5BufferSet(a,b,c,d)        sqlite3Fts5BufferSet(a,b,c,d)
#define fts5BufferAppend32(a,b,c)     sqlite3Fts5BufferAppend32(a,b,c)

#define fts5BufferGrow(pRc,pBuf,nn) ( \
  (pBuf)->n + (nn) <= (pBuf)->nSpace ? 0 : \
    sqlite3Fts5BufferSize((pRc),(pBuf),(nn)+(pBuf)->n) \
)

/* Write and decode big-endian 32-bit integer values */
void sqlite3Fts5Put32(u8*, int);
int sqlite3Fts5Get32(const u8*);

#define FTS5_POS2COLUMN(iPos) (int)(iPos >> 32)
#define FTS5_POS2OFFSET(iPos) (int)(iPos & 0xFFFFFFFF)

Changes to ext/fts5/fts5_buffer.c.

11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

27
28
29
30
31
32
33
34
35
36
37
38
39
40

41
42
43
44
45
46
47
48
49
50
51
52
53
54
..
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
..
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
...
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
******************************************************************************
*/



#include "fts5Int.h"

int sqlite3Fts5BufferGrow(int *pRc, Fts5Buffer *pBuf, int nByte){

  if( (pBuf->n + nByte) > pBuf->nSpace ){
    u8 *pNew;
    int nNew = pBuf->nSpace ? pBuf->nSpace*2 : 64;

    /* A no-op if an error has already occurred */
    if( *pRc ) return 1;


    while( nNew<(pBuf->n + nByte) ){
      nNew = nNew * 2;
    }
    pNew = sqlite3_realloc(pBuf->p, nNew);
    if( pNew==0 ){
      *pRc = SQLITE_NOMEM;
      return 1;
    }else{
      pBuf->nSpace = nNew;
      pBuf->p = pNew;
    }
  }
  return 0;
}


/*
** Encode value iVal as an SQLite varint and append it to the buffer object
** pBuf. If an OOM error occurs, set the error code in p.
*/
void sqlite3Fts5BufferAppendVarint(int *pRc, Fts5Buffer *pBuf, i64 iVal){
  if( sqlite3Fts5BufferGrow(pRc, pBuf, 9) ) return;
  pBuf->n += sqlite3Fts5PutVarint(&pBuf->p[pBuf->n], iVal);
}

void sqlite3Fts5Put32(u8 *aBuf, int iVal){
  aBuf[0] = (iVal>>24) & 0x00FF;
  aBuf[1] = (iVal>>16) & 0x00FF;
  aBuf[2] = (iVal>> 8) & 0x00FF;
................................................................................
}

int sqlite3Fts5Get32(const u8 *aBuf){
  return (aBuf[0] << 24) + (aBuf[1] << 16) + (aBuf[2] << 8) + aBuf[3];
}

void sqlite3Fts5BufferAppend32(int *pRc, Fts5Buffer *pBuf, int iVal){
  if( sqlite3Fts5BufferGrow(pRc, pBuf, 4) ) return;
  sqlite3Fts5Put32(&pBuf->p[pBuf->n], iVal);
  pBuf->n += 4;
}

/*
** Append buffer nData/pData to buffer pBuf. If an OOM error occurs, set 
** the error code in p. If an error has already occurred when this function
................................................................................
void sqlite3Fts5BufferAppendBlob(
  int *pRc,
  Fts5Buffer *pBuf, 
  int nData, 
  const u8 *pData
){
  assert( *pRc || nData>=0 );
  if( sqlite3Fts5BufferGrow(pRc, pBuf, nData) ) return;
  memcpy(&pBuf->p[pBuf->n], pData, nData);
  pBuf->n += nData;
}

/*
** Append the nul-terminated string zStr to the buffer pBuf. This function
** ensures that the byte following the buffer data is set to 0x00, even 
................................................................................
int sqlite3Fts5PoslistWriterAppend(
  Fts5Buffer *pBuf, 
  Fts5PoslistWriter *pWriter,
  i64 iPos
){
  static const i64 colmask = ((i64)(0x7FFFFFFF)) << 32;
  int rc = SQLITE_OK;
  if( 0==sqlite3Fts5BufferGrow(&rc, pBuf, 5+5+5) ){
    if( (iPos & colmask) != (pWriter->iPrev & colmask) ){
      pBuf->p[pBuf->n++] = 1;
      pBuf->n += sqlite3Fts5PutVarint(&pBuf->p[pBuf->n], (iPos>>32));
      pWriter->iPrev = (iPos & colmask);
    }
    pBuf->n += sqlite3Fts5PutVarint(&pBuf->p[pBuf->n], (iPos-pWriter->iPrev)+2);
    pWriter->iPrev = iPos;







|
<
<
<
|
<
<
<
<
>
|
|
|
|
|
|
|
|
|
|
|
<


>






|







 







|







 







|







 







|







11
12
13
14
15
16
17
18



19




20
21
22
23
24
25
26
27
28
29
30
31

32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
..
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
..
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
...
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
******************************************************************************
*/



#include "fts5Int.h"

int sqlite3Fts5BufferSize(int *pRc, Fts5Buffer *pBuf, int nByte){



  int nNew = pBuf->nSpace ? pBuf->nSpace*2 : 64;




  u8 *pNew;
  while( nNew<nByte ){
    nNew = nNew * 2;
  }
  pNew = sqlite3_realloc(pBuf->p, nNew);
  if( pNew==0 ){
    *pRc = SQLITE_NOMEM;
    return 1;
  }else{
    pBuf->nSpace = nNew;
    pBuf->p = pNew;
  }

  return 0;
}


/*
** Encode value iVal as an SQLite varint and append it to the buffer object
** pBuf. If an OOM error occurs, set the error code in p.
*/
void sqlite3Fts5BufferAppendVarint(int *pRc, Fts5Buffer *pBuf, i64 iVal){
  if( fts5BufferGrow(pRc, pBuf, 9) ) return;
  pBuf->n += sqlite3Fts5PutVarint(&pBuf->p[pBuf->n], iVal);
}

void sqlite3Fts5Put32(u8 *aBuf, int iVal){
  aBuf[0] = (iVal>>24) & 0x00FF;
  aBuf[1] = (iVal>>16) & 0x00FF;
  aBuf[2] = (iVal>> 8) & 0x00FF;
................................................................................
}

int sqlite3Fts5Get32(const u8 *aBuf){
  return (aBuf[0] << 24) + (aBuf[1] << 16) + (aBuf[2] << 8) + aBuf[3];
}

void sqlite3Fts5BufferAppend32(int *pRc, Fts5Buffer *pBuf, int iVal){
  if( fts5BufferGrow(pRc, pBuf, 4) ) return;
  sqlite3Fts5Put32(&pBuf->p[pBuf->n], iVal);
  pBuf->n += 4;
}

/*
** Append buffer nData/pData to buffer pBuf. If an OOM error occurs, set 
** the error code in p. If an error has already occurred when this function
................................................................................
void sqlite3Fts5BufferAppendBlob(
  int *pRc,
  Fts5Buffer *pBuf, 
  int nData, 
  const u8 *pData
){
  assert( *pRc || nData>=0 );
  if( fts5BufferGrow(pRc, pBuf, nData) ) return;
  memcpy(&pBuf->p[pBuf->n], pData, nData);
  pBuf->n += nData;
}

/*
** Append the nul-terminated string zStr to the buffer pBuf. This function
** ensures that the byte following the buffer data is set to 0x00, even 
................................................................................
int sqlite3Fts5PoslistWriterAppend(
  Fts5Buffer *pBuf, 
  Fts5PoslistWriter *pWriter,
  i64 iPos
){
  static const i64 colmask = ((i64)(0x7FFFFFFF)) << 32;
  int rc = SQLITE_OK;
  if( 0==fts5BufferGrow(&rc, pBuf, 5+5+5) ){
    if( (iPos & colmask) != (pWriter->iPrev & colmask) ){
      pBuf->p[pBuf->n++] = 1;
      pBuf->n += sqlite3Fts5PutVarint(&pBuf->p[pBuf->n], (iPos>>32));
      pWriter->iPrev = (iPos & colmask);
    }
    pBuf->n += sqlite3Fts5PutVarint(&pBuf->p[pBuf->n], (iPos-pWriter->iPrev)+2);
    pWriter->iPrev = iPos;

Changes to ext/fts5/fts5_index.c.

4103
4104
4105
4106
4107
4108
4109
4110
4111
4112
4113
4114
4115
4116
4117
4118
4119
....
4123
4124
4125
4126
4127
4128
4129




4130
4131
4132
4133
4134
4135
4136
....
4148
4149
4150
4151
4152
4153
4154

4155
4156
4157
4158
4159
4160
4161
....
4236
4237
4238
4239
4240
4241
4242
4243
4244
4245
4246
4247
4248
4249
4250
....
4599
4600
4601
4602
4603
4604
4605
4606
4607
4608
4609
4610
4611
4612
4613
  Fts5Buffer *pBuf
){
  if( p->rc==SQLITE_OK ){
    Fts5SegIter *pSeg = &pMulti->aSeg[ pMulti->aFirst[1].iFirst ];
    assert( fts5MultiIterEof(p, pMulti)==0 );
    assert( pSeg->nPos>0 );
    if( 0==fts5BufferGrow(&p->rc, pBuf, pSeg->nPos+9+9) ){
      int iSv1;
      int iSv2;
      int iData;

      if( pSeg->iLeafOffset+pSeg->nPos<=pSeg->pLeaf->szLeaf 
       && (pColset==0 || pColset->nCol==1)
      ){
        const u8 *pPos = &pSeg->pLeaf->p[pSeg->iLeafOffset];
        int nPos;
        if( pColset ){
................................................................................
          nPos = pSeg->nPos;
        }
        assert( nPos>0 );
        fts5BufferSafeAppendVarint(pBuf, iDelta);
        fts5BufferSafeAppendVarint(pBuf, nPos*2);
        fts5BufferSafeAppendBlob(pBuf, pPos, nPos);
      }else{




        /* Append iDelta */
        iSv1 = pBuf->n;
        fts5BufferSafeAppendVarint(pBuf, iDelta);

        /* WRITEPOSLISTSIZE */
        iSv2 = pBuf->n;
        fts5BufferSafeAppendVarint(pBuf, pSeg->nPos*2);
................................................................................
              int nReq = sqlite3Fts5GetVarintLen((u32)(nActual*2));
              while( iSv2<(iData-nReq) ){ pBuf->p[iSv2++] = 0x80; }
              sqlite3Fts5PutVarint(&pBuf->p[iSv2], nActual*2);
            }
          }
        }
      }

    }
  }

  return 0;
}

static void fts5DoclistIterNext(Fts5DoclistIter *pIter){
................................................................................
    Fts5DoclistIter i1;
    Fts5DoclistIter i2;
    Fts5Buffer out;
    Fts5Buffer tmp;
    memset(&out, 0, sizeof(out));
    memset(&tmp, 0, sizeof(tmp));

    sqlite3Fts5BufferGrow(&p->rc, &out, p1->n + p2->n);
    fts5DoclistIterInit(p1, &i1);
    fts5DoclistIterInit(p2, &i2);
    while( p->rc==SQLITE_OK && (i1.aPoslist!=0 || i2.aPoslist!=0) ){
      if( i2.aPoslist==0 || (i1.aPoslist && i1.iRowid<i2.iRowid) ){
        /* Copy entry from i1 */
        fts5MergeAppendDocid(&out, iLastRowid, i1.iRowid);
        fts5BufferSafeAppendBlob(&out, i1.aPoslist, i1.nPoslist+i1.nSize);
................................................................................
  Fts5IndexIter *pRet = 0;
  int iIdx = 0;
  Fts5Buffer buf = {0, 0, 0};

  /* If the QUERY_SCAN flag is set, all other flags must be clear. */
  assert( (flags & FTS5INDEX_QUERY_SCAN)==0 || flags==FTS5INDEX_QUERY_SCAN );

  if( sqlite3Fts5BufferGrow(&p->rc, &buf, nToken+1)==0 ){
    memcpy(&buf.p[1], pToken, nToken);

#ifdef SQLITE_DEBUG
    /* If the QUERY_TEST_NOIDX flag was specified, then this must be a
    ** prefix-query. Instead of using a prefix-index (if one exists), 
    ** evaluate the prefix query using the main FTS index. This is used
    ** for internal sanity checking by the integrity-check in debug 







<
<
<







 







>
>
>
>







 







>







 







|







 







|







4103
4104
4105
4106
4107
4108
4109



4110
4111
4112
4113
4114
4115
4116
....
4120
4121
4122
4123
4124
4125
4126
4127
4128
4129
4130
4131
4132
4133
4134
4135
4136
4137
....
4149
4150
4151
4152
4153
4154
4155
4156
4157
4158
4159
4160
4161
4162
4163
....
4238
4239
4240
4241
4242
4243
4244
4245
4246
4247
4248
4249
4250
4251
4252
....
4601
4602
4603
4604
4605
4606
4607
4608
4609
4610
4611
4612
4613
4614
4615
  Fts5Buffer *pBuf
){
  if( p->rc==SQLITE_OK ){
    Fts5SegIter *pSeg = &pMulti->aSeg[ pMulti->aFirst[1].iFirst ];
    assert( fts5MultiIterEof(p, pMulti)==0 );
    assert( pSeg->nPos>0 );
    if( 0==fts5BufferGrow(&p->rc, pBuf, pSeg->nPos+9+9) ){




      if( pSeg->iLeafOffset+pSeg->nPos<=pSeg->pLeaf->szLeaf 
       && (pColset==0 || pColset->nCol==1)
      ){
        const u8 *pPos = &pSeg->pLeaf->p[pSeg->iLeafOffset];
        int nPos;
        if( pColset ){
................................................................................
          nPos = pSeg->nPos;
        }
        assert( nPos>0 );
        fts5BufferSafeAppendVarint(pBuf, iDelta);
        fts5BufferSafeAppendVarint(pBuf, nPos*2);
        fts5BufferSafeAppendBlob(pBuf, pPos, nPos);
      }else{
        int iSv1;
        int iSv2;
        int iData;

        /* Append iDelta */
        iSv1 = pBuf->n;
        fts5BufferSafeAppendVarint(pBuf, iDelta);

        /* WRITEPOSLISTSIZE */
        iSv2 = pBuf->n;
        fts5BufferSafeAppendVarint(pBuf, pSeg->nPos*2);
................................................................................
              int nReq = sqlite3Fts5GetVarintLen((u32)(nActual*2));
              while( iSv2<(iData-nReq) ){ pBuf->p[iSv2++] = 0x80; }
              sqlite3Fts5PutVarint(&pBuf->p[iSv2], nActual*2);
            }
          }
        }
      }

    }
  }

  return 0;
}

static void fts5DoclistIterNext(Fts5DoclistIter *pIter){
................................................................................
    Fts5DoclistIter i1;
    Fts5DoclistIter i2;
    Fts5Buffer out;
    Fts5Buffer tmp;
    memset(&out, 0, sizeof(out));
    memset(&tmp, 0, sizeof(tmp));

    fts5BufferGrow(&p->rc, &out, p1->n + p2->n);
    fts5DoclistIterInit(p1, &i1);
    fts5DoclistIterInit(p2, &i2);
    while( p->rc==SQLITE_OK && (i1.aPoslist!=0 || i2.aPoslist!=0) ){
      if( i2.aPoslist==0 || (i1.aPoslist && i1.iRowid<i2.iRowid) ){
        /* Copy entry from i1 */
        fts5MergeAppendDocid(&out, iLastRowid, i1.iRowid);
        fts5BufferSafeAppendBlob(&out, i1.aPoslist, i1.nPoslist+i1.nSize);
................................................................................
  Fts5IndexIter *pRet = 0;
  int iIdx = 0;
  Fts5Buffer buf = {0, 0, 0};

  /* If the QUERY_SCAN flag is set, all other flags must be clear. */
  assert( (flags & FTS5INDEX_QUERY_SCAN)==0 || flags==FTS5INDEX_QUERY_SCAN );

  if( fts5BufferGrow(&p->rc, &buf, nToken+1)==0 ){
    memcpy(&buf.p[1], pToken, nToken);

#ifdef SQLITE_DEBUG
    /* If the QUERY_TEST_NOIDX flag was specified, then this must be a
    ** prefix-query. Instead of using a prefix-index (if one exists), 
    ** evaluate the prefix query using the main FTS index. This is used
    ** for internal sanity checking by the integrity-check in debug