/ Check-in [f2f0184e]
Login

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

Overview
Comment:Improve performance of prefix queries without a prefix index on fts5 tables.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: f2f0184e9e1c9f121ee2ac864cd28c8cd8efecb5
User & Date: dan 2015-10-05 19:41:16
Context
2015-10-06
01:44
Adjustments to sqlite3MemoryBarrier() when compiling with MSVC and/or WinCE. check-in: 3168326e user: mistachkin tags: trunk
2015-10-05
19:41
Improve performance of prefix queries without a prefix index on fts5 tables. check-in: f2f0184e user: dan tags: trunk
15:39
Update fts3 so that expressions to the left and right of a NOT operator are balanced. This prevents relatively small expressions (a dozen terms or so) that are children of NOT operators from triggering the "expression tree is too large" error. check-in: d6b66cd7 user: dan tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Show Whitespace Changes Patch

Changes to ext/fts5/fts5_buffer.c.

   229    229   int sqlite3Fts5PoslistWriterAppend(
   230    230     Fts5Buffer *pBuf, 
   231    231     Fts5PoslistWriter *pWriter,
   232    232     i64 iPos
   233    233   ){
   234    234     static const i64 colmask = ((i64)(0x7FFFFFFF)) << 32;
   235    235     int rc = SQLITE_OK;
          236  +  if( 0==sqlite3Fts5BufferGrow(&rc, pBuf, 5+5+5) ){
   236    237     if( (iPos & colmask) != (pWriter->iPrev & colmask) ){
   237         -    fts5BufferAppendVarint(&rc, pBuf, 1);
   238         -    fts5BufferAppendVarint(&rc, pBuf, (iPos >> 32));
          238  +      pBuf->p[pBuf->n++] = 1;
          239  +      pBuf->n += sqlite3Fts5PutVarint(&pBuf->p[pBuf->n], (iPos>>32));
   239    240       pWriter->iPrev = (iPos & colmask);
   240    241     }
   241         -  fts5BufferAppendVarint(&rc, pBuf, (iPos - pWriter->iPrev) + 2);
          242  +    pBuf->n += sqlite3Fts5PutVarint(&pBuf->p[pBuf->n], (iPos-pWriter->iPrev)+2);
   242    243     pWriter->iPrev = iPos;
          244  +  }
   243    245     return rc;
   244    246   }
   245    247   
   246    248   void *sqlite3Fts5MallocZero(int *pRc, int nByte){
   247    249     void *pRet = 0;
   248    250     if( *pRc==SQLITE_OK ){
   249    251       pRet = sqlite3_malloc(nByte);

Changes to ext/fts5/fts5_index.c.

   303    303     sqlite3_stmt *pIdxWriter;       /* "INSERT ... %_idx VALUES(?,?,?,?)" */
   304    304     sqlite3_stmt *pIdxDeleter;      /* "DELETE FROM %_idx WHERE segid=? */
   305    305     sqlite3_stmt *pIdxSelect;
   306    306     int nRead;                      /* Total number of blocks read */
   307    307   };
   308    308   
   309    309   struct Fts5DoclistIter {
   310         -  u8 *a;
   311         -  int n;
   312         -  int i;
          310  +  u8 *aEof;                       /* Pointer to 1 byte past end of doclist */
   313    311   
   314    312     /* Output variables. aPoslist==0 at EOF */
   315    313     i64 iRowid;
   316    314     u8 *aPoslist;
   317    315     int nPoslist;
   318    316   };
   319    317   
................................................................................
  3703   3701         ret += i;
  3704   3702       }
  3705   3703     }
  3706   3704     return ret;
  3707   3705   }
  3708   3706   
  3709   3707   #define fts5BufferSafeAppendBlob(pBuf, pBlob, nBlob) { \
  3710         -  assert( pBuf->nSpace>=(pBuf->n+nBlob) );             \
  3711         -  memcpy(&pBuf->p[pBuf->n], pBlob, nBlob);             \
  3712         -  pBuf->n += nBlob;                                    \
         3708  +  assert( (pBuf)->nSpace>=((pBuf)->n+nBlob) );             \
         3709  +  memcpy(&(pBuf)->p[(pBuf)->n], pBlob, nBlob);             \
         3710  +  (pBuf)->n += nBlob;                                      \
         3711  +}
         3712  +
         3713  +#define fts5BufferSafeAppendVarint(pBuf, iVal) {                \
         3714  +  (pBuf)->n += sqlite3Fts5PutVarint(&(pBuf)->p[(pBuf)->n], (iVal));  \
         3715  +  assert( (pBuf)->nSpace>=(pBuf)->n );                          \
  3713   3716   }
  3714   3717   
  3715   3718   /*
  3716   3719   ** Flush the contents of in-memory hash table iHash to a new level-0 
  3717   3720   ** segment on disk. Also update the corresponding structure record.
  3718   3721   **
  3719   3722   ** If an error occurs, set the Fts5Index.rc error code. If an error has 
................................................................................
  3985   3988         fts5BufferAppendVarint(&p->rc, pBuf, pSeg->nPos*2);
  3986   3989       }
  3987   3990       fts5SegiterPoslist(p, pSeg, pBuf);
  3988   3991     }
  3989   3992   }
  3990   3993   
  3991   3994   static void fts5DoclistIterNext(Fts5DoclistIter *pIter){
  3992         -  if( pIter->i<pIter->n ){
  3993         -    int bDummy;
  3994         -    if( pIter->i ){
         3995  +  u8 *p = pIter->aPoslist + pIter->nPoslist;
         3996  +
         3997  +  assert( pIter->aPoslist );
         3998  +  if( p>=pIter->aEof ){
         3999  +    pIter->aPoslist = 0;
         4000  +  }else{
  3995   4001         i64 iDelta;
  3996         -      pIter->i += fts5GetVarint(&pIter->a[pIter->i], (u64*)&iDelta);
         4002  +
         4003  +    p += fts5GetVarint(p, (u64*)&iDelta);
  3997   4004         pIter->iRowid += iDelta;
         4005  +
         4006  +    /* Read position list size */
         4007  +    if( p[0] & 0x80 ){
         4008  +      int nPos;
         4009  +      p += fts5GetVarint32(p, nPos);
         4010  +      pIter->nPoslist = (nPos>>1);
  3998   4011       }else{
  3999         -      pIter->i += fts5GetVarint(&pIter->a[pIter->i], (u64*)&pIter->iRowid);
         4012  +      pIter->nPoslist = ((int)(p[0])) >> 1;
         4013  +      p++;
  4000   4014       }
  4001         -    pIter->i += fts5GetPoslistSize(
  4002         -        &pIter->a[pIter->i], &pIter->nPoslist, &bDummy
  4003         -    );
  4004         -    pIter->aPoslist = &pIter->a[pIter->i];
  4005         -    pIter->i += pIter->nPoslist;
  4006         -  }else{
  4007         -    pIter->aPoslist = 0;
         4015  +
         4016  +    pIter->aPoslist = p;
  4008   4017     }
  4009   4018   }
  4010   4019   
  4011   4020   static void fts5DoclistIterInit(
  4012   4021     Fts5Buffer *pBuf, 
  4013   4022     Fts5DoclistIter *pIter
  4014   4023   ){
  4015   4024     memset(pIter, 0, sizeof(*pIter));
  4016         -  pIter->a = pBuf->p;
  4017         -  pIter->n = pBuf->n;
         4025  +  pIter->aPoslist = pBuf->p;
         4026  +  pIter->aEof = &pBuf->p[pBuf->n];
  4018   4027     fts5DoclistIterNext(pIter);
  4019   4028   }
  4020   4029   
         4030  +#if 0
  4021   4031   /*
  4022   4032   ** Append a doclist to buffer pBuf.
         4033  +**
         4034  +** This function assumes that space within the buffer has already been
         4035  +** allocated.
  4023   4036   */
  4024   4037   static void fts5MergeAppendDocid(
  4025         -  int *pRc,                       /* IN/OUT: Error code */
  4026   4038     Fts5Buffer *pBuf,               /* Buffer to write to */
  4027   4039     i64 *piLastRowid,               /* IN/OUT: Previous rowid written (if any) */
  4028   4040     i64 iRowid                      /* Rowid to append */
  4029   4041   ){
  4030         -  if( pBuf->n==0 ){
  4031         -    fts5BufferAppendVarint(pRc, pBuf, iRowid);
  4032         -  }else{
  4033         -    fts5BufferAppendVarint(pRc, pBuf, iRowid - *piLastRowid);
  4034         -  }
         4042  +  assert( pBuf->n!=0 || (*piLastRowid)==0 );
         4043  +  fts5BufferSafeAppendVarint(pBuf, iRowid - *piLastRowid);
  4035   4044     *piLastRowid = iRowid;
  4036   4045   }
         4046  +#endif
         4047  +
         4048  +#define fts5MergeAppendDocid(pBuf, iLastRowid, iRowid) {       \
         4049  +  assert( (pBuf)->n!=0 || (iLastRowid)==0 );                   \
         4050  +  fts5BufferSafeAppendVarint((pBuf), (iRowid) - (iLastRowid)); \
         4051  +  (iLastRowid) = (iRowid);                                     \
         4052  +}
  4037   4053   
  4038   4054   /*
  4039   4055   ** Buffers p1 and p2 contain doclists. This function merges the content
  4040   4056   ** of the two doclists together and sets buffer p1 to the result before
  4041   4057   ** returning.
  4042   4058   **
  4043   4059   ** If an error occurs, an error code is left in p->rc. If an error has
................................................................................
  4053   4069       Fts5DoclistIter i1;
  4054   4070       Fts5DoclistIter i2;
  4055   4071       Fts5Buffer out;
  4056   4072       Fts5Buffer tmp;
  4057   4073       memset(&out, 0, sizeof(out));
  4058   4074       memset(&tmp, 0, sizeof(tmp));
  4059   4075   
         4076  +    sqlite3Fts5BufferGrow(&p->rc, &out, p1->n + p2->n);
  4060   4077       fts5DoclistIterInit(p1, &i1);
  4061   4078       fts5DoclistIterInit(p2, &i2);
  4062   4079       while( p->rc==SQLITE_OK && (i1.aPoslist!=0 || i2.aPoslist!=0) ){
  4063   4080         if( i2.aPoslist==0 || (i1.aPoslist && i1.iRowid<i2.iRowid) ){
  4064   4081           /* Copy entry from i1 */
  4065         -        fts5MergeAppendDocid(&p->rc, &out, &iLastRowid, i1.iRowid);
         4082  +        fts5MergeAppendDocid(&out, iLastRowid, i1.iRowid);
  4066   4083           /* WRITEPOSLISTSIZE */
  4067         -        fts5BufferAppendVarint(&p->rc, &out, i1.nPoslist * 2);
  4068         -        fts5BufferAppendBlob(&p->rc, &out, i1.nPoslist, i1.aPoslist);
         4084  +        fts5BufferSafeAppendVarint(&out, i1.nPoslist * 2);
         4085  +        fts5BufferSafeAppendBlob(&out, i1.aPoslist, i1.nPoslist);
  4069   4086           fts5DoclistIterNext(&i1);
  4070   4087         }
  4071   4088         else if( i1.aPoslist==0 || i2.iRowid!=i1.iRowid ){
  4072   4089           /* Copy entry from i2 */
  4073         -        fts5MergeAppendDocid(&p->rc, &out, &iLastRowid, i2.iRowid);
         4090  +        fts5MergeAppendDocid(&out, iLastRowid, i2.iRowid);
  4074   4091           /* WRITEPOSLISTSIZE */
  4075         -        fts5BufferAppendVarint(&p->rc, &out, i2.nPoslist * 2);
  4076         -        fts5BufferAppendBlob(&p->rc, &out, i2.nPoslist, i2.aPoslist);
         4092  +        fts5BufferSafeAppendVarint(&out, i2.nPoslist * 2);
         4093  +        fts5BufferSafeAppendBlob(&out, i2.aPoslist, i2.nPoslist);
  4077   4094           fts5DoclistIterNext(&i2);
  4078   4095         }
  4079   4096         else{
  4080         -        Fts5PoslistReader r1;
  4081         -        Fts5PoslistReader r2;
         4097  +        i64 iPos1 = 0;
         4098  +        i64 iPos2 = 0;
         4099  +        int iOff1 = 0;
         4100  +        int iOff2 = 0;
         4101  +
  4082   4102           Fts5PoslistWriter writer;
  4083         -
  4084   4103           memset(&writer, 0, sizeof(writer));
  4085   4104   
  4086   4105           /* Merge the two position lists. */ 
  4087         -        fts5MergeAppendDocid(&p->rc, &out, &iLastRowid, i2.iRowid);
         4106  +        fts5MergeAppendDocid(&out, iLastRowid, i2.iRowid);
  4088   4107           fts5BufferZero(&tmp);
  4089         -        sqlite3Fts5PoslistReaderInit(-1, i1.aPoslist, i1.nPoslist, &r1);
  4090         -        sqlite3Fts5PoslistReaderInit(-1, i2.aPoslist, i2.nPoslist, &r2);
  4091         -        while( p->rc==SQLITE_OK && (r1.bEof==0 || r2.bEof==0) ){
         4108  +
         4109  +        sqlite3Fts5PoslistNext64(i1.aPoslist, i1.nPoslist, &iOff1, &iPos1);
         4110  +        sqlite3Fts5PoslistNext64(i2.aPoslist, i2.nPoslist, &iOff2, &iPos2);
         4111  +
         4112  +        while( p->rc==SQLITE_OK && (iPos1>=0 || iPos2>=0) ){
  4092   4113             i64 iNew;
  4093         -          if( r2.bEof || (r1.bEof==0 && r1.iPos<r2.iPos) ){
  4094         -            iNew = r1.iPos;
  4095         -            sqlite3Fts5PoslistReaderNext(&r1);
         4114  +          if( iPos2<0 || (iPos1>=0 && iPos1<iPos2) ){
         4115  +            iNew = iPos1;
         4116  +            sqlite3Fts5PoslistNext64(i1.aPoslist, i1.nPoslist, &iOff1, &iPos1);
  4096   4117             }else{
  4097         -            iNew = r2.iPos;
  4098         -            sqlite3Fts5PoslistReaderNext(&r2);
  4099         -            if( r1.iPos==r2.iPos ) sqlite3Fts5PoslistReaderNext(&r1);
         4118  +            iNew = iPos2;
         4119  +            sqlite3Fts5PoslistNext64(i2.aPoslist, i2.nPoslist, &iOff2, &iPos2);
         4120  +            if( iPos1==iPos2 ){
         4121  +              sqlite3Fts5PoslistNext64(i1.aPoslist, i1.nPoslist, &iOff1,&iPos1);
         4122  +            }
  4100   4123             }
  4101   4124             p->rc = sqlite3Fts5PoslistWriterAppend(&tmp, &writer, iNew);
  4102   4125           }
  4103   4126   
  4104   4127           /* WRITEPOSLISTSIZE */
  4105         -        fts5BufferAppendVarint(&p->rc, &out, tmp.n * 2);
  4106         -        fts5BufferAppendBlob(&p->rc, &out, tmp.n, tmp.p);
         4128  +        fts5BufferSafeAppendVarint(&out, tmp.n * 2);
         4129  +        fts5BufferSafeAppendBlob(&out, tmp.p, tmp.n);
  4107   4130           fts5DoclistIterNext(&i1);
  4108   4131           fts5DoclistIterNext(&i2);
  4109   4132         }
  4110   4133       }
  4111   4134   
  4112   4135       fts5BufferSet(&p->rc, p1, out.n, out.p);
  4113   4136       fts5BufferFree(&tmp);
................................................................................
  4161   4184               fts5BufferSwap(&doclist, &aBuf[i]);
  4162   4185               fts5BufferZero(&doclist);
  4163   4186             }else{
  4164   4187               fts5MergePrefixLists(p, &doclist, &aBuf[i]);
  4165   4188               fts5BufferZero(&aBuf[i]);
  4166   4189             }
  4167   4190           }
         4191  +        iLastRowid = 0;
  4168   4192         }
  4169   4193   
  4170         -      fts5MergeAppendDocid(&p->rc, &doclist, &iLastRowid, iRowid);
         4194  +      if( 0==sqlite3Fts5BufferGrow(&p->rc, &doclist, 9) ){
         4195  +        fts5MergeAppendDocid(&doclist, iLastRowid, iRowid);
  4171   4196         fts5MultiIterPoslist(p, p1, 1, &doclist);
  4172   4197       }
         4198  +    }
  4173   4199   
  4174   4200       for(i=0; i<nBuf; i++){
         4201  +      if( p->rc==SQLITE_OK ){
  4175   4202         fts5MergePrefixLists(p, &doclist, &aBuf[i]);
         4203  +      }
  4176   4204         fts5BufferFree(&aBuf[i]);
  4177   4205       }
  4178   4206       fts5MultiIterFree(p, p1);
  4179   4207   
  4180   4208       pData = fts5IdxMalloc(p, sizeof(Fts5Data) + doclist.n);
  4181   4209       if( pData ){
  4182   4210         pData->p = (u8*)&pData[1];