Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | Further optimizations for fts5 prefix queries without a prefix index. |
|---|---|
| Downloads: | Tarball | ZIP archive | SQL archive |
| Timelines: | family | ancestors | descendants | both | trunk |
| Files: | files | file ages | folders |
| SHA1: |
83dc1ff7fa010715ca7f406a572f4ee4 |
| User & Date: | dan 2015-10-07 19:06:21 |
Context
|
2015-10-08
| ||
| 02:44 | Remove two unused lines of code - discovered by scan-build. (check-in: 77b707b7 user: drh tags: trunk) | |
|
2015-10-07
| ||
| 19:06 | Further optimizations for fts5 prefix queries without a prefix index. (check-in: 83dc1ff7 user: dan tags: trunk) | |
| 17:06 | Fix harmless compiler warning in FTS5. (check-in: 13adcd03 user: mistachkin tags: trunk) | |
Changes
Changes to ext/fts5/fts5_index.c.
309 310 311 312 313 314 315 316 317 318 319 320 321 322 .... 4044 4045 4046 4047 4048 4049 4050 4051 4052 4053 4054 4055 4056 4057 4058 4059 4060 4061 4062 4063 4064 4065 4066 4067 4068 4069 4070 4071 4072 4073 4074 4075 4076 4077 .... 4082 4083 4084 4085 4086 4087 4088 4089 4090 4091 4092 4093 4094 4095 4096 4097 4098 4099 4100 4101 4102 4103 4104 4105 4106 4107 4108 4109 4110 4111 4112 4113 4114 .... 4170 4171 4172 4173 4174 4175 4176 4177 4178 4179 4180 4181 4182 4183 4184 4185 4186 4187 4188 4189 4190 4191 4192 4193 4194 4195 4196 4197 4198 4199 4200 4201 4202 4203 4204 4205 4206 4207 4208 4209 4210 4211 4212 4213 4214 4215 4216 4217 4218 4219 4220 4221 4222 .... 4286 4287 4288 4289 4290 4291 4292 4293 4294 4295 4296 4297 4298 4299 4300 .... 5235 5236 5237 5238 5239 5240 5241 5242 5243 5244 5245 5246 5247 5248 5249 |
struct Fts5DoclistIter {
u8 *aEof; /* Pointer to 1 byte past end of doclist */
/* Output variables. aPoslist==0 at EOF */
i64 iRowid;
u8 *aPoslist;
int nPoslist;
};
/*
** The contents of the "structure" record for each index are represented
** using an Fts5Structure record in memory. Which uses instances of the
** other Fts5StructureXXX types as components.
*/
................................................................................
** If an error occurs, an error code is left in p->rc. It is assumed
** no error has already occurred when this function is called.
*/
static int fts5MultiIterPoslist(
Fts5Index *p,
Fts5IndexIter *pMulti,
Fts5Colset *pColset,
int bSz, /* Append a size field before the data */
Fts5Buffer *pBuf
){
if( p->rc==SQLITE_OK ){
int iSz;
int iData;
Fts5SegIter *pSeg = &pMulti->aSeg[ pMulti->aFirst[1].iFirst ];
assert( fts5MultiIterEof(p, pMulti)==0 );
if( bSz ){
/* WRITEPOSLISTSIZE */
iSz = pBuf->n;
fts5BufferAppendVarint(&p->rc, pBuf, pSeg->nPos*2);
iData = pBuf->n;
}
fts5SegiterPoslist(p, pSeg, pColset, pBuf);
if( bSz && pColset ){
int nActual = pBuf->n - iData;
if( nActual!=pSeg->nPos ){
/* WRITEPOSLISTSIZE */
if( nActual==0 ){
return 1;
}else{
int nReq = sqlite3Fts5GetVarintLen((u32)(nActual*2));
................................................................................
}
}
return 0;
}
static void fts5DoclistIterNext(Fts5DoclistIter *pIter){
u8 *p = pIter->aPoslist + pIter->nPoslist;
assert( pIter->aPoslist );
if( p>=pIter->aEof ){
pIter->aPoslist = 0;
}else{
i64 iDelta;
p += fts5GetVarint(p, (u64*)&iDelta);
pIter->iRowid += iDelta;
/* Read position list size */
if( p[0] & 0x80 ){
int nPos;
p += fts5GetVarint32(p, nPos);
pIter->nPoslist = (nPos>>1);
}else{
pIter->nPoslist = ((int)(p[0])) >> 1;
p++;
}
pIter->aPoslist = p;
}
}
static void fts5DoclistIterInit(
................................................................................
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);
/* WRITEPOSLISTSIZE */
fts5BufferSafeAppendVarint(&out, i1.nPoslist * 2);
fts5BufferSafeAppendBlob(&out, i1.aPoslist, i1.nPoslist);
fts5DoclistIterNext(&i1);
}
else if( i1.aPoslist==0 || i2.iRowid!=i1.iRowid ){
/* Copy entry from i2 */
fts5MergeAppendDocid(&out, iLastRowid, i2.iRowid);
/* WRITEPOSLISTSIZE */
fts5BufferSafeAppendVarint(&out, i2.nPoslist * 2);
fts5BufferSafeAppendBlob(&out, i2.aPoslist, i2.nPoslist);
fts5DoclistIterNext(&i2);
}
else{
i64 iPos1 = 0;
i64 iPos2 = 0;
int iOff1 = 0;
int iOff2 = 0;
Fts5PoslistWriter writer;
memset(&writer, 0, sizeof(writer));
/* Merge the two position lists. */
fts5MergeAppendDocid(&out, iLastRowid, i2.iRowid);
fts5BufferZero(&tmp);
sqlite3Fts5PoslistNext64(i1.aPoslist, i1.nPoslist, &iOff1, &iPos1);
sqlite3Fts5PoslistNext64(i2.aPoslist, i2.nPoslist, &iOff2, &iPos2);
while( p->rc==SQLITE_OK && (iPos1>=0 || iPos2>=0) ){
i64 iNew;
if( iPos2<0 || (iPos1>=0 && iPos1<iPos2) ){
iNew = iPos1;
sqlite3Fts5PoslistNext64(i1.aPoslist, i1.nPoslist, &iOff1, &iPos1);
}else{
iNew = iPos2;
sqlite3Fts5PoslistNext64(i2.aPoslist, i2.nPoslist, &iOff2, &iPos2);
if( iPos1==iPos2 ){
sqlite3Fts5PoslistNext64(i1.aPoslist, i1.nPoslist, &iOff1,&iPos1);
}
}
p->rc = sqlite3Fts5PoslistWriterAppend(&tmp, &writer, iNew);
}
/* WRITEPOSLISTSIZE */
fts5BufferSafeAppendVarint(&out, tmp.n * 2);
................................................................................
iLastRowid = 0;
}
if( 0==sqlite3Fts5BufferGrow(&p->rc, &doclist, 9) ){
int iSave = doclist.n;
assert( doclist.n!=0 || iLastRowid==0 );
fts5BufferSafeAppendVarint(&doclist, iRowid - iLastRowid);
if( fts5MultiIterPoslist(p, p1, pColset, 1, &doclist) ){
doclist.n = iSave;
}else{
iLastRowid = iRowid;
}
}
}
................................................................................
i64 iRowid = fts5MultiIterRowid(pIter);
char *z = (char*)fts5MultiIterTerm(pIter, &n);
/* If this is a new term, query for it. Update cksum3 with the results. */
fts5TestTerm(p, &term, z, n, cksum2, &cksum3);
poslist.n = 0;
fts5MultiIterPoslist(p, pIter, 0, 0, &poslist);
while( 0==sqlite3Fts5PoslistNext64(poslist.p, poslist.n, &iOff, &iPos) ){
int iCol = FTS5_POS2COLUMN(iPos);
int iTokOff = FTS5_POS2OFFSET(iPos);
cksum2 ^= fts5IndexEntryCksum(iRowid, iCol, iTokOff, -1, z, n);
}
}
fts5TestTerm(p, &term, 0, 0, cksum2, &cksum3);
|
> < < | | < > | < | | | | < < | < < | > > | | | | | | | |
309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 .... 4045 4046 4047 4048 4049 4050 4051 4052 4053 4054 4055 4056 4057 4058 4059 4060 4061 4062 4063 4064 4065 4066 4067 4068 4069 4070 4071 4072 4073 4074 4075 .... 4080 4081 4082 4083 4084 4085 4086 4087 4088 4089 4090 4091 4092 4093 4094 4095 4096 4097 4098 4099 4100 4101 4102 4103 4104 4105 4106 4107 4108 4109 4110 4111 4112 .... 4168 4169 4170 4171 4172 4173 4174 4175 4176 4177 4178 4179 4180 4181 4182 4183 4184 4185 4186 4187 4188 4189 4190 4191 4192 4193 4194 4195 4196 4197 4198 4199 4200 4201 4202 4203 4204 4205 4206 4207 4208 4209 4210 4211 4212 4213 4214 4215 4216 4217 4218 .... 4282 4283 4284 4285 4286 4287 4288 4289 4290 4291 4292 4293 4294 4295 4296 .... 5231 5232 5233 5234 5235 5236 5237 5238 5239 5240 5241 5242 5243 5244 5245 |
struct Fts5DoclistIter {
u8 *aEof; /* Pointer to 1 byte past end of doclist */
/* Output variables. aPoslist==0 at EOF */
i64 iRowid;
u8 *aPoslist;
int nPoslist;
int nSize;
};
/*
** The contents of the "structure" record for each index are represented
** using an Fts5Structure record in memory. Which uses instances of the
** other Fts5StructureXXX types as components.
*/
................................................................................
** If an error occurs, an error code is left in p->rc. It is assumed
** no error has already occurred when this function is called.
*/
static int fts5MultiIterPoslist(
Fts5Index *p,
Fts5IndexIter *pMulti,
Fts5Colset *pColset,
Fts5Buffer *pBuf
){
if( p->rc==SQLITE_OK ){
int iSz;
int iData;
Fts5SegIter *pSeg = &pMulti->aSeg[ pMulti->aFirst[1].iFirst ];
assert( fts5MultiIterEof(p, pMulti)==0 );
/* WRITEPOSLISTSIZE */
iSz = pBuf->n;
fts5BufferSafeAppendVarint(pBuf, pSeg->nPos*2);
iData = pBuf->n;
fts5SegiterPoslist(p, pSeg, pColset, pBuf);
if( pColset ){
int nActual = pBuf->n - iData;
if( nActual!=pSeg->nPos ){
/* WRITEPOSLISTSIZE */
if( nActual==0 ){
return 1;
}else{
int nReq = sqlite3Fts5GetVarintLen((u32)(nActual*2));
................................................................................
}
}
return 0;
}
static void fts5DoclistIterNext(Fts5DoclistIter *pIter){
u8 *p = pIter->aPoslist + pIter->nSize + pIter->nPoslist;
assert( pIter->aPoslist );
if( p>=pIter->aEof ){
pIter->aPoslist = 0;
}else{
i64 iDelta;
p += fts5GetVarint(p, (u64*)&iDelta);
pIter->iRowid += iDelta;
/* Read position list size */
if( p[0] & 0x80 ){
int nPos;
pIter->nSize = fts5GetVarint32(p, nPos);
pIter->nPoslist = (nPos>>1);
}else{
pIter->nPoslist = ((int)(p[0])) >> 1;
pIter->nSize = 1;
}
pIter->aPoslist = p;
}
}
static void fts5DoclistIterInit(
................................................................................
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);
fts5DoclistIterNext(&i1);
}
else if( i1.aPoslist==0 || i2.iRowid!=i1.iRowid ){
/* Copy entry from i2 */
fts5MergeAppendDocid(&out, iLastRowid, i2.iRowid);
fts5BufferSafeAppendBlob(&out, i2.aPoslist, i2.nPoslist+i2.nSize);
fts5DoclistIterNext(&i2);
}
else{
i64 iPos1 = 0;
i64 iPos2 = 0;
int iOff1 = 0;
int iOff2 = 0;
u8 *a1 = &i1.aPoslist[i1.nSize];
u8 *a2 = &i2.aPoslist[i2.nSize];
Fts5PoslistWriter writer;
memset(&writer, 0, sizeof(writer));
/* Merge the two position lists. */
fts5MergeAppendDocid(&out, iLastRowid, i2.iRowid);
fts5BufferZero(&tmp);
sqlite3Fts5PoslistNext64(a1, i1.nPoslist, &iOff1, &iPos1);
sqlite3Fts5PoslistNext64(a2, i2.nPoslist, &iOff2, &iPos2);
while( p->rc==SQLITE_OK && (iPos1>=0 || iPos2>=0) ){
i64 iNew;
if( iPos2<0 || (iPos1>=0 && iPos1<iPos2) ){
iNew = iPos1;
sqlite3Fts5PoslistNext64(a1, i1.nPoslist, &iOff1, &iPos1);
}else{
iNew = iPos2;
sqlite3Fts5PoslistNext64(a2, i2.nPoslist, &iOff2, &iPos2);
if( iPos1==iPos2 ){
sqlite3Fts5PoslistNext64(a1, i1.nPoslist, &iOff1,&iPos1);
}
}
p->rc = sqlite3Fts5PoslistWriterAppend(&tmp, &writer, iNew);
}
/* WRITEPOSLISTSIZE */
fts5BufferSafeAppendVarint(&out, tmp.n * 2);
................................................................................
iLastRowid = 0;
}
if( 0==sqlite3Fts5BufferGrow(&p->rc, &doclist, 9) ){
int iSave = doclist.n;
assert( doclist.n!=0 || iLastRowid==0 );
fts5BufferSafeAppendVarint(&doclist, iRowid - iLastRowid);
if( fts5MultiIterPoslist(p, p1, pColset, &doclist) ){
doclist.n = iSave;
}else{
iLastRowid = iRowid;
}
}
}
................................................................................
i64 iRowid = fts5MultiIterRowid(pIter);
char *z = (char*)fts5MultiIterTerm(pIter, &n);
/* If this is a new term, query for it. Update cksum3 with the results. */
fts5TestTerm(p, &term, z, n, cksum2, &cksum3);
poslist.n = 0;
fts5SegiterPoslist(p, &pIter->aSeg[pIter->aFirst[1].iFirst] , 0, &poslist);
while( 0==sqlite3Fts5PoslistNext64(poslist.p, poslist.n, &iOff, &iPos) ){
int iCol = FTS5_POS2COLUMN(iPos);
int iTokOff = FTS5_POS2OFFSET(iPos);
cksum2 ^= fts5IndexEntryCksum(iRowid, iCol, iTokOff, -1, z, n);
}
}
fts5TestTerm(p, &term, 0, 0, cksum2, &cksum3);
|