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: |
f2f0184e9e1c9f121ee2ac864cd28c8c |
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
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];