Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | If a prefix index of size N is not present, use a prefix index of size N+1 along with the terms index for queries for prefixes of length N. |
|---|---|
| Downloads: | Tarball | ZIP archive | SQL archive |
| Timelines: | family | ancestors | descendants | both | fts3-prefix-search |
| Files: | files | file ages | folders |
| SHA1: |
cc83991caae7c7d647432d5711b6cd80 |
| User & Date: | dan 2011-05-25 19:17:32 |
Context
|
2011-05-28
| ||
| 15:57 | Minor changes made while planning a larger change. check-in: 84097a4c user: dan tags: fts3-prefix-search | |
|
2011-05-25
| ||
| 19:17 | If a prefix index of size N is not present, use a prefix index of size N+1 along with the terms index for queries for prefixes of length N. check-in: cc83991c user: dan tags: fts3-prefix-search | |
| 18:47 | Merge trunk changes into experimental fts3-prefix-search branch. check-in: f0f0a03d user: dan tags: fts3-prefix-search | |
Changes
Changes to ext/fts3/fts3.c.
2233 2234 2235 2236 2237 2238 2239 2240 2241 2242 2243 2244 2245 2246 2247 2248 2249 2250 2251 2252 2253 2254 2255 2256 2257 2258 2259 2260 2261 2262 2263 2264 2265 2266 2267 2268 2269 2270 2271 2272 2273 2274 2275 2276 2277 2278 2279 2280 2281 .... 2306 2307 2308 2309 2310 2311 2312 2313 2314 2315 2316 2317 2318 2319 2320 2321 2322 2323 2324 2325 2326 2327 2328 2329 2330 2331 2332 2333 2334 .... 2341 2342 2343 2344 2345 2346 2347 2348 2349 2350 2351 2352 2353 2354 2355 2356 2357 2358 2359 2360 |
}
pCsr->apSegment = apNew;
}
pCsr->apSegment[pCsr->nSegment++] = pNew;
return SQLITE_OK;
}
/*
** Set up a cursor object for iterating through a full-text index or a
** single level therein.
*/
int sqlite3Fts3SegReaderCursor(
Fts3Table *p, /* FTS3 table handle */
int iIndex, /* Index to search (from 0 to p->nIndex-1) */
int iLevel, /* Level of segments to scan */
const char *zTerm, /* Term to query for */
int nTerm, /* Size of zTerm in bytes */
int isPrefix, /* True for a prefix search */
int isScan, /* True to scan from zTerm to EOF */
Fts3SegReaderCursor *pCsr /* Cursor object to populate */
){
int rc = SQLITE_OK;
int rc2;
int iAge = 0;
sqlite3_stmt *pStmt = 0;
assert( iIndex>=0 && iIndex<p->nIndex );
assert( iLevel==FTS3_SEGCURSOR_ALL
|| iLevel==FTS3_SEGCURSOR_PENDING
|| iLevel>=0
);
assert( iLevel<FTS3_SEGDIR_MAXLEVEL );
assert( FTS3_SEGCURSOR_ALL<0 && FTS3_SEGCURSOR_PENDING<0 );
assert( iLevel==FTS3_SEGCURSOR_ALL || (zTerm==0 && isPrefix==1) );
assert( isPrefix==0 || isScan==0 );
/* "isScan" is only set to true by the ft4aux module, an ordinary
** full-text tables. */
assert( isScan==0 || p->aIndex==0 );
memset(pCsr, 0, sizeof(Fts3SegReaderCursor));
/* If iLevel is less than 0 and this is not a scan, include a seg-reader
** for the pending-terms. If this is a scan, then this call must be being
** made by an fts4aux module, not an FTS table. In this case calling
** Fts3SegReaderPending might segfault, as the data structures used by
** fts4aux are not completely populated. So it's easiest to filter these
** calls out here. */
if( iLevel<0 && p->aIndex ){
................................................................................
if( iStartBlock && zTerm ){
sqlite3_int64 *pi = (isPrefix ? &iLeavesEndBlock : 0);
rc = fts3SelectLeaf(p, zTerm, nTerm, zRoot, nRoot, &iStartBlock, pi);
if( rc!=SQLITE_OK ) goto finished;
if( isPrefix==0 && isScan==0 ) iLeavesEndBlock = iStartBlock;
}
rc = sqlite3Fts3SegReaderNew(iAge, iStartBlock, iLeavesEndBlock,
iEndBlock, zRoot, nRoot, &pSeg
);
if( rc!=SQLITE_OK ) goto finished;
rc = fts3SegReaderCursorAppend(pCsr, pSeg);
iAge++;
}
}
finished:
rc2 = sqlite3_reset(pStmt);
if( rc==SQLITE_DONE ) rc = rc2;
return rc;
}
static int fts3TermSegReaderCursor(
Fts3Cursor *pCsr, /* Virtual table cursor handle */
const char *zTerm, /* Term to query for */
int nTerm, /* Size of zTerm in bytes */
int isPrefix, /* True for a prefix search */
................................................................................
if( pSegcsr ){
int i;
int nCost = 0;
int bFound = 0; /* True once an index has been found */
Fts3Table *p = (Fts3Table *)pCsr->base.pVtab;
if( isPrefix ){
for(i=1; i<p->nIndex; i++){
if( p->aIndex[i].nPrefix==nTerm ){
bFound = 1;
rc = sqlite3Fts3SegReaderCursor(
p, i, FTS3_SEGCURSOR_ALL, zTerm, nTerm, 0, 0, pSegcsr);
break;
}
}
}
if( bFound==0 ){
rc = sqlite3Fts3SegReaderCursor(
p, 0, FTS3_SEGCURSOR_ALL, zTerm, nTerm, isPrefix, 0, pSegcsr
|
< < < < | < < < < < < < < < < < < < < < < < | | < > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | < > > > > > > > > > > > > |
2233 2234 2235 2236 2237 2238 2239 2240 2241 2242 2243 2244 2245 2246 2247 2248 2249 2250 2251 2252 2253 2254 2255 2256 2257 2258 2259 2260 .... 2285 2286 2287 2288 2289 2290 2291 2292 2293 2294 2295 2296 2297 2298 2299 2300 2301 2302 2303 2304 2305 2306 2307 2308 2309 2310 2311 2312 2313 2314 2315 2316 2317 2318 2319 2320 2321 2322 2323 2324 2325 2326 2327 2328 2329 2330 2331 2332 2333 2334 2335 2336 2337 2338 2339 2340 2341 2342 2343 2344 2345 2346 2347 2348 2349 2350 2351 2352 2353 2354 2355 .... 2362 2363 2364 2365 2366 2367 2368 2369 2370 2371 2372 2373 2374 2375 2376 2377 2378 2379 2380 2381 2382 2383 2384 2385 2386 2387 2388 2389 2390 2391 2392 |
}
pCsr->apSegment = apNew;
}
pCsr->apSegment[pCsr->nSegment++] = pNew;
return SQLITE_OK;
}
static int fts3SegReaderCursor(
Fts3Table *p, /* FTS3 table handle */
int iIndex, /* Index to search (from 0 to p->nIndex-1) */
int iLevel, /* Level of segments to scan */
const char *zTerm, /* Term to query for */
int nTerm, /* Size of zTerm in bytes */
int isPrefix, /* True for a prefix search */
int isScan, /* True to scan from zTerm to EOF */
Fts3SegReaderCursor *pCsr /* Cursor object to populate */
){
int rc = SQLITE_OK;
int rc2;
sqlite3_stmt *pStmt = 0;
/* If iLevel is less than 0 and this is not a scan, include a seg-reader
** for the pending-terms. If this is a scan, then this call must be being
** made by an fts4aux module, not an FTS table. In this case calling
** Fts3SegReaderPending might segfault, as the data structures used by
** fts4aux are not completely populated. So it's easiest to filter these
** calls out here. */
if( iLevel<0 && p->aIndex ){
................................................................................
if( iStartBlock && zTerm ){
sqlite3_int64 *pi = (isPrefix ? &iLeavesEndBlock : 0);
rc = fts3SelectLeaf(p, zTerm, nTerm, zRoot, nRoot, &iStartBlock, pi);
if( rc!=SQLITE_OK ) goto finished;
if( isPrefix==0 && isScan==0 ) iLeavesEndBlock = iStartBlock;
}
rc = sqlite3Fts3SegReaderNew(pCsr->nSegment+1,
iStartBlock, iLeavesEndBlock, iEndBlock, zRoot, nRoot, &pSeg
);
if( rc!=SQLITE_OK ) goto finished;
rc = fts3SegReaderCursorAppend(pCsr, pSeg);
}
}
finished:
rc2 = sqlite3_reset(pStmt);
if( rc==SQLITE_DONE ) rc = rc2;
return rc;
}
/*
** Set up a cursor object for iterating through a full-text index or a
** single level therein.
*/
int sqlite3Fts3SegReaderCursor(
Fts3Table *p, /* FTS3 table handle */
int iIndex, /* Index to search (from 0 to p->nIndex-1) */
int iLevel, /* Level of segments to scan */
const char *zTerm, /* Term to query for */
int nTerm, /* Size of zTerm in bytes */
int isPrefix, /* True for a prefix search */
int isScan, /* True to scan from zTerm to EOF */
Fts3SegReaderCursor *pCsr /* Cursor object to populate */
){
assert( iIndex>=0 && iIndex<p->nIndex );
assert( iLevel==FTS3_SEGCURSOR_ALL
|| iLevel==FTS3_SEGCURSOR_PENDING
|| iLevel>=0
);
assert( iLevel<FTS3_SEGDIR_MAXLEVEL );
assert( FTS3_SEGCURSOR_ALL<0 && FTS3_SEGCURSOR_PENDING<0 );
assert( isPrefix==0 || isScan==0 );
/* "isScan" is only set to true by the ft4aux module, an ordinary
** full-text tables. */
assert( isScan==0 || p->aIndex==0 );
memset(pCsr, 0, sizeof(Fts3SegReaderCursor));
return fts3SegReaderCursor(
p, iIndex, iLevel, zTerm, nTerm, isPrefix, isScan, pCsr
);
}
static int fts3SegReaderCursorAddZero(
Fts3Table *p,
const char *zTerm,
int nTerm,
Fts3SegReaderCursor *pCsr
){
return fts3SegReaderCursor(p, 0, FTS3_SEGCURSOR_ALL, zTerm, nTerm, 0, 0,pCsr);
}
static int fts3TermSegReaderCursor(
Fts3Cursor *pCsr, /* Virtual table cursor handle */
const char *zTerm, /* Term to query for */
int nTerm, /* Size of zTerm in bytes */
int isPrefix, /* True for a prefix search */
................................................................................
if( pSegcsr ){
int i;
int nCost = 0;
int bFound = 0; /* True once an index has been found */
Fts3Table *p = (Fts3Table *)pCsr->base.pVtab;
if( isPrefix ){
for(i=1; bFound==0 && i<p->nIndex; i++){
if( p->aIndex[i].nPrefix==nTerm ){
bFound = 1;
rc = sqlite3Fts3SegReaderCursor(
p, i, FTS3_SEGCURSOR_ALL, zTerm, nTerm, 0, 0, pSegcsr);
}
}
for(i=1; bFound==0 && i<p->nIndex; i++){
if( p->aIndex[i].nPrefix==nTerm+1 ){
bFound = 1;
rc = sqlite3Fts3SegReaderCursor(
p, i, FTS3_SEGCURSOR_ALL, zTerm, nTerm, 1, 0, pSegcsr
);
if( rc==SQLITE_OK ){
rc = fts3SegReaderCursorAddZero(p, zTerm, nTerm, pSegcsr);
}
}
}
}
if( bFound==0 ){
rc = sqlite3Fts3SegReaderCursor(
p, 0, FTS3_SEGCURSOR_ALL, zTerm, nTerm, isPrefix, 0, pSegcsr
|
Changes to ext/fts3/fts3_write.c.
418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 |
int rc;
sqlite3_stmt *pStmt = 0;
assert( iLevel==FTS3_SEGCURSOR_ALL || iLevel>=0 );
assert( iLevel<FTS3_SEGDIR_MAXLEVEL );
assert( iIndex>=0 && iIndex<p->nIndex );
if( iLevel==FTS3_SEGCURSOR_ALL ){
/* "SELECT * FROM %_segdir WHERE level BETWEEN ? AND ? ORDER BY ..." */
rc = fts3SqlStmt(p, SQL_SELECT_LEVEL_RANGE, &pStmt, 0);
if( rc==SQLITE_OK ){
sqlite3_bind_int(pStmt, 1, iIndex*FTS3_SEGDIR_MAXLEVEL);
sqlite3_bind_int(pStmt, 2, (iIndex+1)*FTS3_SEGDIR_MAXLEVEL-1);
}
}else{
|
| |
418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 |
int rc;
sqlite3_stmt *pStmt = 0;
assert( iLevel==FTS3_SEGCURSOR_ALL || iLevel>=0 );
assert( iLevel<FTS3_SEGDIR_MAXLEVEL );
assert( iIndex>=0 && iIndex<p->nIndex );
if( iLevel<0 ){
/* "SELECT * FROM %_segdir WHERE level BETWEEN ? AND ? ORDER BY ..." */
rc = fts3SqlStmt(p, SQL_SELECT_LEVEL_RANGE, &pStmt, 0);
if( rc==SQLITE_OK ){
sqlite3_bind_int(pStmt, 1, iIndex*FTS3_SEGDIR_MAXLEVEL);
sqlite3_bind_int(pStmt, 2, (iIndex+1)*FTS3_SEGDIR_MAXLEVEL-1);
}
}else{
|
Changes to test/fts3prefix.test.
189 190 191 192 193 194 195 196 197 |
} {{four five six}}
do_execsql_test 4.3 {
SELECT * FROM t3 WHERE t3 MATCH 'four*'
} {{four five six}}
do_execsql_test 4.4 {
SELECT * FROM t3 WHERE t3 MATCH 's*'
} {{four five six} {seven eight nine}}
finish_test
|
> > > > > > |
189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 |
} {{four five six}}
do_execsql_test 4.3 {
SELECT * FROM t3 WHERE t3 MATCH 'four*'
} {{four five six}}
do_execsql_test 4.4 {
SELECT * FROM t3 WHERE t3 MATCH 's*'
} {{four five six} {seven eight nine}}
do_execsql_test 4.5 {
SELECT * FROM t3 WHERE t3 MATCH 'sev*'
} {{seven eight nine}}
do_execsql_test 4.6 {
SELECT * FROM t3 WHERE t3 MATCH 'one*'
} {{one two three}}
finish_test
|