Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Add the 'merge=?,?' command to fts4. This still needs some work. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | fts4-incr-merge |
Files: | files | file ages | folders |
SHA1: |
741b8f897750eac3c9774fd65de7e40b |
User & Date: | dan 2012-03-08 18:39:03.077 |
Context
2012-03-09
| ||
12:52 | Minor commenting and stylistic changes only. (check-in: a1747086c5 user: drh tags: fts4-incr-merge) | |
2012-03-08
| ||
18:39 | Add the 'merge=?,?' command to fts4. This still needs some work. (check-in: 741b8f8977 user: dan tags: fts4-incr-merge) | |
2012-03-05
| ||
16:24 | Fix a problem compiling the test code in fts3_test.c when SQLITE_ENABLE_FTS3 is not defined. (check-in: b00ccda307 user: dan tags: trunk) | |
Changes
Changes to ext/fts3/fts3Int.h.
︙ | ︙ | |||
63 64 65 66 67 68 69 70 71 72 73 74 75 76 | */ #define SizeofArray(X) ((int)(sizeof(X)/sizeof(X[0]))) #ifndef MIN # define MIN(x,y) ((x)<(y)?(x):(y)) #endif /* ** Maximum length of a varint encoded integer. The varint format is different ** from that used by SQLite, so the maximum length is 10, not 9. */ #define FTS3_VARINT_MAX 10 | > > > | 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 | */ #define SizeofArray(X) ((int)(sizeof(X)/sizeof(X[0]))) #ifndef MIN # define MIN(x,y) ((x)<(y)?(x):(y)) #endif #ifndef MAX # define MAX(x,y) ((x)>(y)?(x):(y)) #endif /* ** Maximum length of a varint encoded integer. The varint format is different ** from that used by SQLite, so the maximum length is 10, not 9. */ #define FTS3_VARINT_MAX 10 |
︙ | ︙ | |||
193 194 195 196 197 198 199 | sqlite3_tokenizer *pTokenizer; /* tokenizer for inserts and queries */ char *zContentTbl; /* content=xxx option, or NULL */ char *zLanguageid; /* languageid=xxx option, or NULL */ /* Precompiled statements used by the implementation. Each of these ** statements is run and reset within a single virtual table API call. */ | | | 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 | sqlite3_tokenizer *pTokenizer; /* tokenizer for inserts and queries */ char *zContentTbl; /* content=xxx option, or NULL */ char *zLanguageid; /* languageid=xxx option, or NULL */ /* Precompiled statements used by the implementation. Each of these ** statements is run and reset within a single virtual table API call. */ sqlite3_stmt *aStmt[35]; char *zReadExprlist; char *zWriteExprlist; int nNodeSize; /* Soft limit for node size */ u8 bHasStat; /* True if %_stat table exists */ u8 bHasDocsize; /* True if %_docsize table exists */ |
︙ | ︙ |
Changes to ext/fts3/fts3_write.c.
︙ | ︙ | |||
20 21 22 23 24 25 26 27 28 29 30 31 32 33 | #include "fts3Int.h" #if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS3) #include <string.h> #include <assert.h> #include <stdlib.h> /* ** When full-text index nodes are loaded from disk, the buffer that they ** are loaded into has the following number of bytes of padding at the end ** of it. i.e. if a full-text index node is 900 bytes in size, then a buffer ** of 920 bytes is allocated for it. ** ** This means that if we have a pointer into a buffer containing node data, | > > > | 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | #include "fts3Int.h" #if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS3) #include <string.h> #include <assert.h> #include <stdlib.h> #define FTS_MAX_APPENDABLE_HEIGHT 10 /* ** When full-text index nodes are loaded from disk, the buffer that they ** are loaded into has the following number of bytes of padding at the end ** of it. i.e. if a full-text index node is 900 bytes in size, then a buffer ** of 920 bytes is allocated for it. ** ** This means that if we have a pointer into a buffer containing node data, |
︙ | ︙ | |||
225 226 227 228 229 230 231 | #define SQL_REPLACE_DOCSIZE 20 #define SQL_SELECT_DOCSIZE 21 #define SQL_SELECT_DOCTOTAL 22 #define SQL_REPLACE_DOCTOTAL 23 #define SQL_SELECT_ALL_PREFIX_LEVEL 24 #define SQL_DELETE_ALL_TERMS_SEGDIR 25 | | > > > | | | > > | 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 | #define SQL_REPLACE_DOCSIZE 20 #define SQL_SELECT_DOCSIZE 21 #define SQL_SELECT_DOCTOTAL 22 #define SQL_REPLACE_DOCTOTAL 23 #define SQL_SELECT_ALL_PREFIX_LEVEL 24 #define SQL_DELETE_ALL_TERMS_SEGDIR 25 #define SQL_DELETE_SEGDIR_RANGE 26 #define SQL_SELECT_ALL_LANGID 27 #define SQL_FIND_MERGE_LEVEL 28 #define SQL_MAX_LEAF_NODE_ESTIMATE 29 #define SQL_DELETE_SEGDIR_ENTRY 30 #define SQL_SHIFT_SEGDIR_ENTRIES 31 #define SQL_SELECT_SEGDIR 32 #define SQL_CHOMP_SEGDIR 33 #define SQL_SEGMENT_IS_APPENDABLE 34 /* ** This function is used to obtain an SQLite prepared statement handle ** for the statement identified by the second argument. If successful, ** *pp is set to the requested statement handle and SQLITE_OK returned. ** Otherwise, an SQLite error code is returned and *pp is set to 0. ** |
︙ | ︙ | |||
257 258 259 260 261 262 263 | /* 2 */ "DELETE FROM %Q.'%q_content'", /* 3 */ "DELETE FROM %Q.'%q_segments'", /* 4 */ "DELETE FROM %Q.'%q_segdir'", /* 5 */ "DELETE FROM %Q.'%q_docsize'", /* 6 */ "DELETE FROM %Q.'%q_stat'", /* 7 */ "SELECT %s WHERE rowid=?", /* 8 */ "SELECT (SELECT max(idx) FROM %Q.'%q_segdir' WHERE level = ?) + 1", | | | | 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 | /* 2 */ "DELETE FROM %Q.'%q_content'", /* 3 */ "DELETE FROM %Q.'%q_segments'", /* 4 */ "DELETE FROM %Q.'%q_segdir'", /* 5 */ "DELETE FROM %Q.'%q_docsize'", /* 6 */ "DELETE FROM %Q.'%q_stat'", /* 7 */ "SELECT %s WHERE rowid=?", /* 8 */ "SELECT (SELECT max(idx) FROM %Q.'%q_segdir' WHERE level = ?) + 1", /* 9 */ "REPLACE INTO %Q.'%q_segments'(blockid, block) VALUES(?, ?)", /* 10 */ "SELECT coalesce((SELECT max(blockid) FROM %Q.'%q_segments') + 1, 1)", /* 11 */ "REPLACE INTO %Q.'%q_segdir' VALUES(?,?,?,?,?,?)", /* Return segments in order from oldest to newest.*/ /* 12 */ "SELECT idx, start_block, leaves_end_block, end_block, root " "FROM %Q.'%q_segdir' WHERE level = ? ORDER BY idx ASC", /* 13 */ "SELECT idx, start_block, leaves_end_block, end_block, root " "FROM %Q.'%q_segdir' WHERE level BETWEEN ? AND ?" "ORDER BY level DESC, idx ASC", |
︙ | ︙ | |||
285 286 287 288 289 290 291 292 293 294 295 296 297 298 | /* 23 */ "REPLACE INTO %Q.'%q_stat' VALUES(0,?)", /* 24 */ "", /* 25 */ "", /* 26 */ "DELETE FROM %Q.'%q_segdir' WHERE level BETWEEN ? AND ?", /* 27 */ "SELECT DISTINCT level / (1024 * ?) FROM %Q.'%q_segdir'", }; int rc = SQLITE_OK; sqlite3_stmt *pStmt; assert( SizeofArray(azSql)==SizeofArray(p->aStmt) ); assert( eStmt<SizeofArray(azSql) && eStmt>=0 ); | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 | /* 23 */ "REPLACE INTO %Q.'%q_stat' VALUES(0,?)", /* 24 */ "", /* 25 */ "", /* 26 */ "DELETE FROM %Q.'%q_segdir' WHERE level BETWEEN ? AND ?", /* 27 */ "SELECT DISTINCT level / (1024 * ?) FROM %Q.'%q_segdir'", /* This statement is used to determine which level to read the input from ** when performing an incremental merge. It returns the absolute level number ** of the oldest level in the db that contains at least ? segments. Or, ** if no level in the FTS index contains more than ? segments, the statement ** returns zero rows. */ /* 28 */ "SELECT level FROM %Q.'%q_segdir' GROUP BY level HAVING count(*)>?" " ORDER BY (level %% 1024) DESC LIMIT 1", /* Estimate the upper limit on the number of leaf nodes in a new segment ** created by merging the two segments with idx=0 and idx=1 from absolute ** level ?. See function fts3Incrmerge() for details. */ /* 29 */ "SELECT 2 * total(1 + leaves_end_block - start_block) " " FROM %Q.'%q_segdir' WHERE level = ? AND idx BETWEEN 0 AND 1", /* SQL_DELETE_SEGDIR_ENTRY ** Delete the %_segdir entry on absolute level :1 with index :2. */ /* 30 */ "DELETE FROM %Q.'%q_segdir' WHERE level = ? AND idx = ?", /* SQL_SHIFT_SEGDIR_ENTRIES ** Reduce by one the idx values of all segments on absolute level :1 with ** an index greater than :2. */ /* 31 */ "UPDATE %Q.'%q_segdir' SET idx = idx - 1 WHERE level = ? AND idx>:2", /* SQL_SELECT_SEGDIR ** Read a single entry from the %_segdir table. The entry from absolute ** level :1 with index value :2. */ /* 32 */ "SELECT idx, start_block, leaves_end_block, end_block, root " "FROM %Q.'%q_segdir' WHERE level = ? AND idx = ?", /* SQL_CHOMP_SEGDIR ** Update the start_block (:1) and root (:2) fields of the %_segdir ** entry located on absolute level :3 with index :4. */ /* 33 */ "UPDATE %Q.'%q_segdir' SET start_block = ?, root = ?" "WHERE level = ? AND idx = ?", /* SQL_SEGMENT_IS_APPENDABLE ** Return a single row if the segment with end_block=? is appendable. Or ** no rows otherwise. */ /* 34 */ "SELECT 1 FROM %Q.'%q_segments' WHERE blockid=? AND block IS NULL" }; int rc = SQLITE_OK; sqlite3_stmt *pStmt; assert( SizeofArray(azSql)==SizeofArray(p->aStmt) ); assert( eStmt<SizeofArray(azSql) && eStmt>=0 ); |
︙ | ︙ | |||
441 442 443 444 445 446 447 448 449 450 451 452 453 454 | int iLevel ){ assert( iLangid>=0 ); assert( p->nIndex>0 ); assert( iIndex>=0 && iIndex<p->nIndex ); return (iLangid * p->nIndex + iIndex) * FTS3_SEGDIR_MAXLEVEL + iLevel; } /* ** Set *ppStmt to a statement handle that may be used to iterate through ** all rows in the %_segdir table, from oldest to newest. If successful, ** return SQLITE_OK. If an error occurs while preparing the statement, ** return an SQLite error code. | > > > > > > > > > > > > > > > > > > | 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 | int iLevel ){ assert( iLangid>=0 ); assert( p->nIndex>0 ); assert( iIndex>=0 && iIndex<p->nIndex ); return (iLangid * p->nIndex + iIndex) * FTS3_SEGDIR_MAXLEVEL + iLevel; } /* ** Given an absolute level number, determine the langauge-id, index ** and relative level that it corresponds to. ** ** The return value is the relative level. The language-id and index ** are returned via output variables. */ static int getRelativeLevel( Fts3Table *p, /* FTS table handle */ sqlite3_int64 iAbsLevel, /* Absolute level */ int *piLangid, /* OUT: Language id */ int *piIndex /* OUT: Index in p->aIndex[] */ ){ if( piLangid ) *piLangid = (iAbsLevel / FTS3_SEGDIR_MAXLEVEL) / p->nIndex; if( piIndex ) *piIndex = (iAbsLevel / FTS3_SEGDIR_MAXLEVEL) % p->nIndex; return iAbsLevel % FTS3_SEGDIR_MAXLEVEL; } /* ** Set *ppStmt to a statement handle that may be used to iterate through ** all rows in the %_segdir table, from oldest to newest. If successful, ** return SQLITE_OK. If an error occurs while preparing the statement, ** return an SQLite error code. |
︙ | ︙ | |||
1055 1056 1057 1058 1059 1060 1061 | char **paBlob, /* OUT: Blob data in malloc'd buffer */ int *pnBlob, /* OUT: Size of blob data */ int *pnLoad /* OUT: Bytes actually loaded */ ){ int rc; /* Return code */ /* pnBlob must be non-NULL. paBlob may be NULL or non-NULL. */ | | | 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 | char **paBlob, /* OUT: Blob data in malloc'd buffer */ int *pnBlob, /* OUT: Size of blob data */ int *pnLoad /* OUT: Bytes actually loaded */ ){ int rc; /* Return code */ /* pnBlob must be non-NULL. paBlob may be NULL or non-NULL. */ assert( pnBlob ); if( p->pSegments ){ rc = sqlite3_blob_reopen(p->pSegments, iBlockid); }else{ if( 0==p->zSegmentsTbl ){ p->zSegmentsTbl = sqlite3_mprintf("%s_segments", p->zName); if( 0==p->zSegmentsTbl ) return SQLITE_NOMEM; |
︙ | ︙ | |||
2258 2259 2260 2261 2262 2263 2264 2265 2266 2267 2268 2269 2270 2271 | getAbsoluteLevel(p, iLangid, iIndex, FTS3_SEGDIR_MAXLEVEL-1) ); if( SQLITE_ROW==sqlite3_step(pStmt) ){ *pnMax = sqlite3_column_int(pStmt, 0); } return sqlite3_reset(pStmt); } /* ** This function is used after merging multiple segments into a single large ** segment to delete the old, now redundant, segment b-trees. Specifically, ** it: ** ** 1) Deletes all %_segments entries for the segments associated with | > > > > > > > > > > > > > > > > > > > > > > > | 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 2356 2357 2358 2359 | getAbsoluteLevel(p, iLangid, iIndex, FTS3_SEGDIR_MAXLEVEL-1) ); if( SQLITE_ROW==sqlite3_step(pStmt) ){ *pnMax = sqlite3_column_int(pStmt, 0); } return sqlite3_reset(pStmt); } /* ** Delete all entries in the %_segments table associated with the segment ** opened with seg-reader pSeg. This function does not affect the contents ** of the %_segdir table. */ static int fts3DeleteSegment( Fts3Table *p, /* FTS table handle */ Fts3SegReader *pSeg /* Segment to delete */ ){ int rc = SQLITE_OK; /* Return code */ if( pSeg->iStartBlock ){ sqlite3_stmt *pDelete; /* SQL statement to delete rows */ rc = fts3SqlStmt(p, SQL_DELETE_SEGMENTS_RANGE, &pDelete, 0); if( rc==SQLITE_OK ){ sqlite3_bind_int64(pDelete, 1, pSeg->iStartBlock); sqlite3_bind_int64(pDelete, 2, pSeg->iEndBlock); sqlite3_step(pDelete); rc = sqlite3_reset(pDelete); } } return rc; } /* ** This function is used after merging multiple segments into a single large ** segment to delete the old, now redundant, segment b-trees. Specifically, ** it: ** ** 1) Deletes all %_segments entries for the segments associated with |
︙ | ︙ | |||
2281 2282 2283 2284 2285 2286 2287 | Fts3Table *p, /* Virtual table handle */ int iLangid, /* Language id */ int iIndex, /* Index for p->aIndex */ int iLevel, /* Level of %_segdir entries to delete */ Fts3SegReader **apSegment, /* Array of SegReader objects */ int nReader /* Size of array apSegment */ ){ | | | < | < < < < < < | 2369 2370 2371 2372 2373 2374 2375 2376 2377 2378 2379 2380 2381 2382 2383 2384 2385 2386 2387 2388 | Fts3Table *p, /* Virtual table handle */ int iLangid, /* Language id */ int iIndex, /* Index for p->aIndex */ int iLevel, /* Level of %_segdir entries to delete */ Fts3SegReader **apSegment, /* Array of SegReader objects */ int nReader /* Size of array apSegment */ ){ int rc = SQLITE_OK; /* Return Code */ int i; /* Iterator variable */ sqlite3_stmt *pDelete = 0; /* SQL statement to delete rows */ for(i=0; rc==SQLITE_OK && i<nReader; i++){ rc = fts3DeleteSegment(p, apSegment[i]); } if( rc!=SQLITE_OK ){ return rc; } assert( iLevel>=0 || iLevel==FTS3_SEGCURSOR_ALL ); if( iLevel==FTS3_SEGCURSOR_ALL ){ |
︙ | ︙ | |||
3138 3139 3140 3141 3142 3143 3144 3145 3146 3147 3148 3149 3150 3151 3152 3153 3154 3155 3156 3157 3158 3159 3160 3161 3162 3163 3164 3165 3166 3167 3168 3169 3170 | } } } return rc; } /* ** Handle a 'special' INSERT of the form: ** ** "INSERT INTO tbl(tbl) VALUES(<expr>)" ** ** Argument pVal contains the result of <expr>. Currently the only ** meaningful value to insert is the text 'optimize'. */ static int fts3SpecialInsert(Fts3Table *p, sqlite3_value *pVal){ int rc; /* Return Code */ const char *zVal = (const char *)sqlite3_value_text(pVal); int nVal = sqlite3_value_bytes(pVal); if( !zVal ){ return SQLITE_NOMEM; }else if( nVal==8 && 0==sqlite3_strnicmp(zVal, "optimize", 8) ){ rc = fts3DoOptimize(p, 0); }else if( nVal==7 && 0==sqlite3_strnicmp(zVal, "rebuild", 7) ){ rc = fts3DoRebuild(p); #ifdef SQLITE_TEST }else if( nVal>9 && 0==sqlite3_strnicmp(zVal, "nodesize=", 9) ){ p->nNodeSize = atoi(&zVal[9]); rc = SQLITE_OK; }else if( nVal>11 && 0==sqlite3_strnicmp(zVal, "maxpending=", 9) ){ p->nMaxPendingData = atoi(&zVal[11]); rc = SQLITE_OK; | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 3219 3220 3221 3222 3223 3224 3225 3226 3227 3228 3229 3230 3231 3232 3233 3234 3235 3236 3237 3238 3239 3240 3241 3242 3243 3244 3245 3246 3247 3248 3249 3250 3251 3252 3253 3254 3255 3256 3257 3258 3259 3260 3261 3262 3263 3264 3265 3266 3267 3268 3269 3270 3271 3272 3273 3274 3275 3276 3277 3278 3279 3280 3281 3282 3283 3284 3285 3286 3287 3288 3289 3290 3291 3292 3293 3294 3295 3296 3297 3298 3299 3300 3301 3302 3303 3304 3305 3306 3307 3308 3309 3310 3311 3312 3313 3314 3315 3316 3317 3318 3319 3320 3321 3322 3323 3324 3325 3326 3327 3328 3329 3330 3331 3332 3333 3334 3335 3336 3337 3338 3339 3340 3341 3342 3343 3344 3345 3346 3347 3348 3349 3350 3351 3352 3353 3354 3355 3356 3357 3358 3359 3360 3361 3362 3363 3364 3365 3366 3367 3368 3369 3370 3371 3372 3373 3374 3375 3376 3377 3378 3379 3380 3381 3382 3383 3384 3385 3386 3387 3388 3389 3390 3391 3392 3393 3394 3395 3396 3397 3398 3399 3400 3401 3402 3403 3404 3405 3406 3407 3408 3409 3410 3411 3412 3413 3414 3415 3416 3417 3418 3419 3420 3421 3422 3423 3424 3425 3426 3427 3428 3429 3430 3431 3432 3433 3434 3435 3436 3437 3438 3439 3440 3441 3442 3443 3444 3445 3446 3447 3448 3449 3450 3451 3452 3453 3454 3455 3456 3457 3458 3459 3460 3461 3462 3463 3464 3465 3466 3467 3468 3469 3470 3471 3472 3473 3474 3475 3476 3477 3478 3479 3480 3481 3482 3483 3484 3485 3486 3487 3488 3489 3490 3491 3492 3493 3494 3495 3496 3497 3498 3499 3500 3501 3502 3503 3504 3505 3506 3507 3508 3509 3510 3511 3512 3513 3514 3515 3516 3517 3518 3519 3520 3521 3522 3523 3524 3525 3526 3527 3528 3529 3530 3531 3532 3533 3534 3535 3536 3537 3538 3539 3540 3541 3542 3543 3544 3545 3546 3547 3548 3549 3550 3551 3552 3553 3554 3555 3556 3557 3558 3559 3560 3561 3562 3563 3564 3565 3566 3567 3568 3569 3570 3571 3572 3573 3574 3575 3576 3577 3578 3579 3580 3581 3582 3583 3584 3585 3586 3587 3588 3589 3590 3591 3592 3593 3594 3595 3596 3597 3598 3599 3600 3601 3602 3603 3604 3605 3606 3607 3608 3609 3610 3611 3612 3613 3614 3615 3616 3617 3618 3619 3620 3621 3622 3623 3624 3625 3626 3627 3628 3629 3630 3631 3632 3633 3634 3635 3636 3637 3638 3639 3640 3641 3642 3643 3644 3645 3646 3647 3648 3649 3650 3651 3652 3653 3654 3655 3656 3657 3658 3659 3660 3661 3662 3663 3664 3665 3666 3667 3668 3669 3670 3671 3672 3673 3674 3675 3676 3677 3678 3679 3680 3681 3682 3683 3684 3685 3686 3687 3688 3689 3690 3691 3692 3693 3694 3695 3696 3697 3698 3699 3700 3701 3702 3703 3704 3705 3706 3707 3708 3709 3710 3711 3712 3713 3714 3715 3716 3717 3718 3719 3720 3721 3722 3723 3724 3725 3726 3727 3728 3729 3730 3731 3732 3733 3734 3735 3736 3737 3738 3739 3740 3741 3742 3743 3744 3745 3746 3747 3748 3749 3750 3751 3752 3753 3754 3755 3756 3757 3758 3759 3760 3761 3762 3763 3764 3765 3766 3767 3768 3769 3770 3771 3772 3773 3774 3775 3776 3777 3778 3779 3780 3781 3782 3783 3784 3785 3786 3787 3788 3789 3790 3791 3792 3793 3794 3795 3796 3797 3798 3799 3800 3801 3802 3803 3804 3805 3806 3807 3808 3809 3810 3811 3812 3813 3814 3815 3816 3817 3818 3819 3820 3821 3822 3823 3824 3825 3826 3827 3828 3829 3830 3831 3832 3833 3834 3835 3836 3837 3838 3839 3840 3841 3842 3843 3844 3845 3846 3847 3848 3849 3850 3851 3852 3853 3854 3855 3856 3857 3858 3859 3860 3861 3862 3863 3864 3865 3866 3867 3868 3869 3870 3871 3872 3873 3874 3875 3876 3877 3878 3879 3880 3881 3882 3883 3884 3885 3886 3887 3888 3889 3890 3891 3892 3893 3894 3895 3896 3897 3898 3899 3900 3901 3902 3903 3904 3905 3906 3907 3908 3909 3910 3911 3912 3913 3914 3915 3916 3917 3918 3919 3920 3921 3922 3923 3924 3925 3926 3927 3928 3929 3930 3931 3932 3933 3934 3935 3936 3937 3938 3939 3940 3941 3942 3943 3944 3945 3946 3947 3948 3949 3950 3951 3952 3953 3954 3955 3956 3957 3958 3959 3960 3961 3962 3963 3964 3965 3966 3967 3968 3969 3970 3971 3972 3973 3974 3975 3976 3977 3978 3979 3980 3981 3982 3983 3984 3985 3986 3987 3988 3989 3990 3991 3992 3993 3994 3995 3996 3997 3998 3999 4000 4001 4002 4003 4004 4005 4006 4007 4008 4009 4010 4011 4012 4013 4014 4015 4016 4017 4018 4019 4020 4021 4022 4023 4024 4025 4026 4027 4028 4029 4030 4031 4032 4033 4034 4035 4036 4037 4038 4039 4040 4041 4042 4043 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 4078 4079 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 4113 4114 4115 4116 4117 4118 4119 4120 4121 4122 4123 4124 4125 4126 4127 4128 4129 4130 4131 4132 4133 4134 4135 4136 4137 4138 4139 4140 4141 4142 4143 4144 4145 4146 4147 4148 4149 4150 4151 4152 4153 4154 4155 4156 4157 4158 4159 4160 4161 4162 4163 4164 4165 4166 4167 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 4219 4220 4221 4222 4223 4224 4225 4226 4227 4228 4229 4230 4231 4232 4233 4234 4235 4236 4237 4238 4239 4240 4241 4242 4243 4244 4245 4246 4247 4248 4249 4250 4251 4252 4253 4254 4255 4256 4257 4258 4259 4260 4261 | } } } return rc; } /* ** This function opens a cursor used to read the input data for an ** incremental merge operation. Specifically, it opens a cursor to scan ** the oldest two segments (idx=0 and idx=1) in absolute level iAbsLevel. */ static int fts3IncrmergeCsr( Fts3Table *p, /* FTS3 table handle */ sqlite3_int64 iAbsLevel, /* Absolute level to open */ Fts3MultiSegReader *pCsr /* Cursor object to populate */ ){ int rc; /* Return Code */ sqlite3_stmt *pStmt = 0; memset(pCsr, 0, sizeof(*pCsr)); pCsr->apSegment = (Fts3SegReader **)sqlite3_malloc(sizeof(Fts3SegReader *)*2); if( pCsr->apSegment==0 ){ rc = SQLITE_NOMEM; }else{ memset(pCsr->apSegment, 0, sizeof(Fts3SegReader *)*2); pCsr->nSegment = 2; rc = fts3SqlStmt(p, SQL_SELECT_LEVEL, &pStmt, 0); } if( rc==SQLITE_OK ){ int i; int rc2; sqlite3_bind_int64(pStmt, 1, iAbsLevel); for(i=0; rc==SQLITE_OK && sqlite3_step(pStmt)==SQLITE_ROW && i<2; i++){ rc = sqlite3Fts3SegReaderNew(i, 0, sqlite3_column_int64(pStmt, 1), /* segdir.start_block */ sqlite3_column_int64(pStmt, 2), /* segdir.leaves_end_block */ sqlite3_column_int64(pStmt, 3), /* segdir.end_block */ sqlite3_column_blob(pStmt, 4), /* segdir.root */ sqlite3_column_bytes(pStmt, 4), /* segdir.root */ &pCsr->apSegment[i] ); } rc2 = sqlite3_reset(pStmt); if( rc==SQLITE_OK ) rc = rc2; } return rc; } typedef struct IncrmergeWriter IncrmergeWriter; typedef struct LayerWriter LayerWriter; typedef struct Blob Blob; typedef struct NodeReader NodeReader; struct Blob { char *a; int n; int nAlloc; }; struct LayerWriter { sqlite3_int64 iBlock; /* Current block id */ Blob key; /* Last key written to the current block */ Blob block; /* Current block image */ }; struct IncrmergeWriter { int nLeafEst; /* Space allocated for leaf blocks */ int nWork; /* Number of leaf pages flushed */ sqlite3_int64 iAbsLevel; /* Absolute level of input segments */ int iIdx; /* Index of *output* segment in iAbsLevel+1 */ sqlite3_int64 iStart; /* Block number of first allocated block */ sqlite3_int64 iEnd; /* Block number of last allocated block */ LayerWriter aLayer[FTS_MAX_APPENDABLE_HEIGHT]; }; /* ** An object of the following type is used to read data from a single ** FTS segment node. See the following functions: ** ** nodeReaderInit() ** nodeReaderNext() ** nodeReaderRelease() */ struct NodeReader { const char *aNode; int nNode; int iOff; /* Current offset within aNode[] */ /* Output variables. Containing the current node entry. */ sqlite3_int64 iChild; /* Pointer to child node */ Blob term; /* Current term */ const char *aDoclist; /* Pointer to doclist */ int nDoclist; /* Size of doclist in bytes */ }; static void blobGrowBuffer(Blob *pBlob, int nMin, int *pRc){ if( *pRc==SQLITE_OK && nMin>pBlob->nAlloc ){ int nAlloc = nMin; char *a = (char *)sqlite3_realloc(pBlob->a, nAlloc); if( a ){ pBlob->nAlloc = nAlloc; pBlob->a = a; }else{ *pRc = SQLITE_NOMEM; } } } static int nodeReaderNext(NodeReader *p){ int bFirst = (p->term.n==0); /* True for first term on the node */ int nPrefix = 0; /* Bytes to copy from previous term */ int nSuffix = 0; /* Bytes to append to the prefix */ int rc = SQLITE_OK; /* Return code */ assert( p->aNode ); if( p->iChild && bFirst==0 ) p->iChild++; if( p->iOff>=p->nNode ){ /* EOF */ p->aNode = 0; }else{ if( bFirst==0 ){ p->iOff += sqlite3Fts3GetVarint32(&p->aNode[p->iOff], &nPrefix); } p->iOff += sqlite3Fts3GetVarint32(&p->aNode[p->iOff], &nSuffix); blobGrowBuffer(&p->term, nPrefix+nSuffix, &rc); if( rc==SQLITE_OK ){ memcpy(&p->term.a[nPrefix], &p->aNode[p->iOff], nSuffix); p->term.n = nPrefix+nSuffix; p->iOff += nSuffix; if( p->iChild==0 ){ p->iOff += sqlite3Fts3GetVarint32(&p->aNode[p->iOff], &p->nDoclist); p->aDoclist = &p->aNode[p->iOff]; p->iOff += p->nDoclist; } } } assert( p->iOff<=p->nNode ); return rc; } static void nodeReaderRelease(NodeReader *p){ sqlite3_free(p->term.a); } /* ** Initialize a node-reader object. */ static int nodeReaderInit(NodeReader *p, const char *aNode, int nNode){ memset(p, 0, sizeof(NodeReader)); p->aNode = aNode; p->nNode = nNode; /* Figure out if this is a leaf or an internal node. */ if( p->aNode[0] ){ /* An internal node. */ p->iOff = 1 + sqlite3Fts3GetVarint(&p->aNode[1], &p->iChild); }else{ p->iOff = 1; } return nodeReaderNext(p); } /* ** This function is called while writing an FTS segment each time a leaf o ** node is finished and written to disk. The key (zTerm/nTerm) is guaranteed ** to be greater than the largest key on the node just written, but smaller ** than or equal to the first key that will be written to the next leaf ** node. ** ** The block id of the leaf node just written to disk may be found in ** (pWriter->aLayer[0].iBlock) when this function is called. */ static int fts3IncrmergePush( Fts3Table *p, /* Fts3 table handle */ IncrmergeWriter *pWriter, /* Writer object */ const char *zTerm, /* Term to write to internal node */ int nTerm /* Bytes at zTerm */ ){ sqlite3_int64 iPtr = pWriter->aLayer[0].iBlock; int iLayer; assert( nTerm>0 ); for(iLayer=1; iLayer<FTS_MAX_APPENDABLE_HEIGHT; iLayer++){ sqlite3_int64 iNextPtr = 0; LayerWriter *pLayer = &pWriter->aLayer[iLayer]; int rc = SQLITE_OK; int nPrefix; int nSuffix; int nSpace; /* Figure out how much space the key will consume if it is written to ** the current node of layer iLayer. Due to the prefix compression, ** the space required changes depending on which node the key is to ** be added to. */ nPrefix = fts3PrefixCompress(pLayer->key.a, pLayer->key.n, zTerm, nTerm); nSuffix = nTerm - nPrefix; nSpace = sqlite3Fts3VarintLen(nPrefix); nSpace += sqlite3Fts3VarintLen(nSuffix) + nSuffix; if( pLayer->key.n==0 || (pLayer->block.n + nSpace)<=p->nNodeSize ){ /* If the current node of layer iLayer contains zero keys, or if adding ** the key to it will not cause it to grow to larger than nNodeSize ** bytes in size, write the key here. */ Blob *pBlk = &pLayer->block; if( pBlk->n==0 ){ blobGrowBuffer(pBlk, p->nNodeSize, &rc); if( rc==SQLITE_OK ){ pBlk->a[0] = (char)iLayer; pBlk->n = 1 + sqlite3Fts3PutVarint(&pBlk->a[1], iPtr); } } blobGrowBuffer(pBlk, pBlk->n + nSpace, &rc); blobGrowBuffer(&pLayer->key, nTerm, &rc); if( rc==SQLITE_OK ){ if( pLayer->key.n ){ pBlk->n += sqlite3Fts3PutVarint(&pBlk->a[pBlk->n], nPrefix); } pBlk->n += sqlite3Fts3PutVarint(&pBlk->a[pBlk->n], nSuffix); memcpy(&pBlk->a[pBlk->n], &zTerm[nPrefix], nSuffix); pBlk->n += nSuffix; memcpy(pLayer->key.a, zTerm, nTerm); pLayer->key.n = nTerm; } }else{ /* Otherwise, flush the the current node of layer iLayer to disk. ** Then allocate a new, empty sibling node. The key will be written ** into the parent of this node. */ rc = fts3WriteSegment(p, pLayer->iBlock, pLayer->block.a,pLayer->block.n); assert( pLayer->block.nAlloc>=p->nNodeSize ); pLayer->block.a[0] = (char)iLayer; pLayer->block.n = 1 + sqlite3Fts3PutVarint(&pLayer->block.a[1], iPtr+1); iNextPtr = pLayer->iBlock; pLayer->iBlock++; pLayer->key.n = 0; } if( rc!=SQLITE_OK || iNextPtr==0 ) return rc; iPtr = iNextPtr; } assert( 0 ); } static int fts3IncrmergeAppend( Fts3Table *p, /* Fts3 table handle */ IncrmergeWriter *pWriter, /* Writer object */ Fts3MultiSegReader *pCsr /* Cursor containing term and doclist */ ){ const char *zTerm = pCsr->zTerm; int nTerm = pCsr->nTerm; const char *aDoclist = pCsr->aDoclist; int nDoclist = pCsr->nDoclist; int rc = SQLITE_OK; /* Return code */ int nSpace; /* Total space in bytes required on leaf */ int nPrefix; int nSuffix; LayerWriter *pLayer; Blob *pPg; pLayer = &pWriter->aLayer[0]; nPrefix = fts3PrefixCompress(pLayer->key.a, pLayer->key.n, zTerm, nTerm); nSuffix = nTerm - nPrefix; nSpace = sqlite3Fts3VarintLen(nPrefix); nSpace += sqlite3Fts3VarintLen(nSuffix) + nSuffix; nSpace += sqlite3Fts3VarintLen(nDoclist) + nDoclist; /* If the current block is not empty, and if adding this term/doclist ** to the current block would make it larger than Fts3Table.nNodeSize ** bytes, write this block out to the database. */ if( pLayer->block.n>0 && (pLayer->block.n + nSpace)>p->nNodeSize ){ rc = fts3WriteSegment(p, pLayer->iBlock, pLayer->block.a, pLayer->block.n); pWriter->nWork++; /* Add the current term to the parent node. The term added to the ** parent must: ** ** a) be greater than the largest term on the leaf node just written ** to the database (still available in pLayer->key), and ** ** b) be less than or equal to the term about to be added to the new ** leaf node (zTerm/nTerm). ** ** In other words, it must be the prefix of zTerm 1 byte longer than ** the common prefix (if any) of zTerm and pWriter->zTerm. */ if( rc==SQLITE_OK ){ rc = fts3IncrmergePush(p, pWriter, zTerm, nPrefix+1); } /* Advance to the next output block */ pLayer->iBlock++; pLayer->key.n = 0; pLayer->block.n = 0; nPrefix = 0; nSuffix = nTerm; nSpace = 1; nSpace += sqlite3Fts3VarintLen(nSuffix) + nSuffix; nSpace += sqlite3Fts3VarintLen(nDoclist) + nDoclist; } blobGrowBuffer(&pLayer->key, nTerm, &rc); blobGrowBuffer(&pLayer->block, pLayer->block.n + nSpace, &rc); if( rc==SQLITE_OK ){ /* Update the block image with the new entry */ pPg = &pLayer->block; pPg->n += sqlite3Fts3PutVarint(&pPg->a[pPg->n], nPrefix); pPg->n += sqlite3Fts3PutVarint(&pPg->a[pPg->n], nSuffix); memcpy(&pPg->a[pPg->n], &zTerm[nPrefix], nSuffix); pPg->n += nSuffix; pPg->n += sqlite3Fts3PutVarint(&pPg->a[pPg->n], nDoclist); memcpy(&pPg->a[pPg->n], aDoclist, nDoclist); pPg->n += nDoclist; /* Take a copy of the key just written */ memcpy(pLayer->key.a, zTerm, nTerm); pLayer->key.n = nTerm; } return rc; } static void fts3IncrmergeRelease( Fts3Table *p, IncrmergeWriter *pWriter, int *pRc ){ int i; /* Used to iterate through non-root layers */ int iRoot; LayerWriter *pRoot; int rc = *pRc; /* Find the root node */ for(iRoot=FTS_MAX_APPENDABLE_HEIGHT-1; iRoot>=0; iRoot--){ if( pWriter->aLayer[iRoot].block.n>0 ) break; assert( pWriter->aLayer[iRoot].block.nAlloc==0 ); assert( pWriter->aLayer[iRoot].key.nAlloc==0 ); } /* Empty output segment. This is a no-op. */ if( iRoot<0 ) return; /* The entire output segment fits on the root node. This is not allowed. */ if( iRoot==0 ){ Blob *pBlock = &pWriter->aLayer[1].block; blobGrowBuffer(pBlock, 1 + FTS3_VARINT_MAX, &rc); if( rc==SQLITE_OK ){ pBlock->a[0] = 0x01; pBlock->n = 1 + sqlite3Fts3PutVarint( &pBlock->a[1], pWriter->aLayer[0].iBlock ); } iRoot = 1; } pRoot = &pWriter->aLayer[iRoot]; for(i=0; i<iRoot; i++){ LayerWriter *pLayer = &pWriter->aLayer[i]; if( pLayer->block.n>0 && rc==SQLITE_OK ){ rc = fts3WriteSegment(p, pLayer->iBlock, pLayer->block.a,pLayer->block.n); } sqlite3_free(pLayer->block.a); sqlite3_free(pLayer->key.a); } /* Write the %_segdir record. */ if( rc==SQLITE_OK ){ rc = fts3WriteSegdir(p, pWriter->iAbsLevel+1, /* level */ pWriter->iIdx, /* idx */ pWriter->iStart, /* start_block */ pWriter->aLayer[0].iBlock, /* leaves_end_block */ pWriter->iEnd, /* end_block */ pRoot->block.a, pRoot->block.n /* root */ ); } sqlite3_free(pRoot->block.a); sqlite3_free(pRoot->key.a); *pRc = rc; } static int fts3TermCmp( const char *zLhs, int nLhs, /* LHS of comparison */ const char *zRhs, int nRhs /* RHS of comparison */ ){ int nCmp = MIN(nLhs, nRhs); int res; res = memcmp(zLhs, zRhs, nCmp); if( res==0 ) res = nLhs - nRhs; return res; } static int fts3IsAppendable(Fts3Table *p, sqlite3_int64 iEnd, int *pRc){ int bRes = 0; if( *pRc==SQLITE_OK ){ sqlite3_stmt *pCheck = 0; int rc; rc = fts3SqlStmt(p, SQL_SEGMENT_IS_APPENDABLE, &pCheck, 0); if( rc==SQLITE_OK ){ sqlite3_bind_int64(pCheck, 1, iEnd); if( SQLITE_ROW==sqlite3_step(pCheck) ) bRes = 1; rc = sqlite3_reset(pCheck); } *pRc = rc; } return bRes; } /* ** */ static int fts3IncrmergeLoad( Fts3Table *p, /* Fts3 table handle */ sqlite3_int64 iAbsLevel, /* Absolute level of input segments */ int iIdx, /* Index of candidate output segment */ const char *zKey, /* First key to write */ int nKey, /* Number of bytes in nKey */ IncrmergeWriter *pWriter /* Populate this object */ ){ sqlite3_int64 iStart = 0; sqlite3_int64 iLeafEnd = 0; sqlite3_int64 iEnd = 0; const char *aRoot = 0; int nRoot = 0; int rc; sqlite3_stmt *pSelect = 0; rc = fts3SqlStmt(p, SQL_SELECT_SEGDIR, &pSelect, 0); if( rc==SQLITE_OK ){ int rc2; int bAppendable = 0; sqlite3_bind_int64(pSelect, 1, iAbsLevel+1); sqlite3_bind_int(pSelect, 2, iIdx); if( sqlite3_step(pSelect)==SQLITE_ROW ){ iStart = sqlite3_column_int64(pSelect, 1); iLeafEnd = sqlite3_column_int64(pSelect, 2); iEnd = sqlite3_column_int64(pSelect, 3); nRoot = sqlite3_column_bytes(pSelect, 4); aRoot = sqlite3_column_blob(pSelect, 4); }else{ return sqlite3_reset(pSelect); } /* Check for the zero-length marker in the %_segments table */ bAppendable = fts3IsAppendable(p, iEnd, &rc); /* Check that zKey/nKey is larger than the largest key the candidate */ if( rc==SQLITE_OK && bAppendable ){ char *aLeaf = (char *)aRoot; int nLeaf = nRoot; if( aRoot[0] ){ rc = sqlite3Fts3ReadBlock(p, iLeafEnd, &aLeaf, &nLeaf, 0); } if( rc==SQLITE_OK ){ NodeReader reader; for(rc = nodeReaderInit(&reader, aLeaf, nLeaf); rc==SQLITE_OK && reader.aNode; rc = nodeReaderNext(&reader) ){ assert( reader.aNode ); } if( fts3TermCmp(zKey, nKey, reader.term.a, reader.term.n)<=0 ){ bAppendable = 0; } nodeReaderRelease(&reader); } if( aLeaf!=aRoot ) sqlite3_free(aLeaf); } if( rc==SQLITE_OK && bAppendable ){ /* It is possible to append to this segment. Set up the IncrmergeWriter ** object to do so. */ int i; int nHeight = (int)aRoot[0]; LayerWriter *pLayer; pWriter->nLeafEst = ((iEnd - iStart) + 1) / FTS_MAX_APPENDABLE_HEIGHT; pWriter->iStart = iStart; pWriter->iEnd = iEnd; pWriter->iAbsLevel = iAbsLevel; pWriter->iIdx = iIdx; pLayer = &pWriter->aLayer[nHeight]; pLayer->iBlock = pWriter->iStart + nHeight*FTS_MAX_APPENDABLE_HEIGHT; blobGrowBuffer(&pLayer->block, MAX(nRoot, p->nNodeSize), &rc); if( rc==SQLITE_OK ){ memcpy(pLayer->block.a, aRoot, nRoot); pLayer->block.n = nRoot; } for(i=(int)aRoot[0]; i>=0 && rc==SQLITE_OK; i--){ pLayer = &pWriter->aLayer[i]; NodeReader reader; rc = nodeReaderInit(&reader, pLayer->block.a, pLayer->block.n); while( reader.aNode && rc==SQLITE_OK ) rc = nodeReaderNext(&reader); blobGrowBuffer(&pLayer->key, reader.term.n, &rc); if( rc==SQLITE_OK ){ memcpy(pLayer->key.a, reader.term.a, reader.term.n); pLayer->key.n = reader.term.n; if( i>0 ){ char *aBlock = 0; int nBlock = 0; pLayer = &pWriter->aLayer[i-1]; pLayer->iBlock = reader.iChild; rc = sqlite3Fts3ReadBlock(p, reader.iChild, &aBlock, &nBlock, 0); blobGrowBuffer(&pLayer->block, nBlock, &rc); if( rc==SQLITE_OK ){ memcpy(pLayer->block.a, aBlock, nBlock); pLayer->block.n = nBlock; } sqlite3_free(aBlock); } } nodeReaderRelease(&reader); } } rc2 = sqlite3_reset(pSelect); if( rc==SQLITE_OK ) rc = rc2; } return rc; } /* ** Either allocate an output segment or locate an existing appendable ** output segment to append to. And "appendable" output segment is ** slightly different to a normal one, as the required range of keys in ** the %_segments table must be allocated up front. This requires some ** assumptions: ** ** * It is expected that due to the short-keys used, and the prefix and ** suffix compression, the fanout of segment b-trees will be very high. ** With a conservative assumption of 32 bytes per key and 1024 byte ** pages, say 32 (2^5). Since SQLite database files are limited to ** a total of 2^31 pages in size, it seems very likely that no segment ** b-tree will have more than ten layers of nodes (including the ** leaves). ** ** * Since each interior node has a pointer to at least two child nodes, ** each layer of interior nodes must be smaller than the layer of ** leaf nodes. ** ** In the %_segdir table, a segment is defined by the values in three ** columns: ** ** start_block ** leaves_end_block ** end_block ** ** When an appendable segment is allocated, it is estimated that the ** maximum number of leaf blocks that may be required is the sum of the ** number of leaf blocks consumed by the two input segments multiplied ** by three. If an input segment consists of a root node only, treat it ** as if it has a single leaf node for the purposes of this estimate. ** This value is stored in stack variable nLeafEst. ** ** A total of 10*nLeafEst blocks are allocated when an appendable segment ** is created ((1 + end_block - start_block)==10*nLeafEst). The contiguous ** array of leaf nodes starts at the first block allocated. The array ** of interior nodes that are parents of the leaf nodes start at block ** (start_block + (1 + end_block - start_block) / 10). And so on. ** ** In the actual code below, the value "10" is replaced with the ** pre-processor macro FTS_MAX_APPENDABLE_HEIGHT. */ static int fts3IncrmergeWriter( Fts3Table *p, /* Fts3 table handle */ sqlite3_int64 iAbsLevel, /* Absolute level of input segments */ const char *zKey, /* First key to write */ int nKey, /* Number of bytes in nKey */ IncrmergeWriter *pWriter /* Populate this object */ ){ int rc; /* Return Code */ int i; /* Iterator variable */ int nLeafEst; /* Blocks allocated for leaf nodes */ int iIdx; /* Index of output segment */ sqlite3_stmt *pLeafEst = 0; /* SQL used to determine nLeafEst */ sqlite3_stmt *pFirstBlock = 0; /* SQL used to determine first block */ sqlite3_stmt *pOutputIdx = 0; /* SQL used to find output index */ rc = fts3SqlStmt(p, SQL_NEXT_SEGMENT_INDEX, &pOutputIdx, 0); if( rc==SQLITE_OK ){ sqlite3_bind_int(pOutputIdx, 1, iAbsLevel+1); sqlite3_step(pOutputIdx); iIdx = sqlite3_column_int(pOutputIdx, 0) - 1; rc = sqlite3_reset(pOutputIdx); } if( rc!=SQLITE_OK ) return rc; assert( zKey ); assert( pWriter->nLeafEst==0 ); rc = fts3IncrmergeLoad(p, iAbsLevel, iIdx, zKey, nKey, pWriter); if( rc!=SQLITE_OK || pWriter->nLeafEst ) return rc; iIdx++; /* Calculate nLeafEst. */ rc = fts3SqlStmt(p, SQL_MAX_LEAF_NODE_ESTIMATE, &pLeafEst, 0); if( rc==SQLITE_OK ){ sqlite3_bind_int64(pLeafEst, 1, iAbsLevel); if( SQLITE_ROW==sqlite3_step(pLeafEst) ){ nLeafEst = sqlite3_column_int(pLeafEst, 0); } rc = sqlite3_reset(pLeafEst); } if( rc!=SQLITE_OK ) return rc; /* Calculate the first block to use in the output segment */ rc = fts3SqlStmt(p, SQL_NEXT_SEGMENTS_ID, &pFirstBlock, 0); if( rc==SQLITE_OK ){ if( SQLITE_ROW==sqlite3_step(pFirstBlock) ){ pWriter->iStart = sqlite3_column_int64(pFirstBlock, 0); pWriter->iEnd = pWriter->iStart - 1; pWriter->iEnd += nLeafEst * FTS_MAX_APPENDABLE_HEIGHT; } rc = sqlite3_reset(pFirstBlock); } if( rc!=SQLITE_OK ) return rc; /* Insert the marker in the %_segments table to make sure nobody tries ** to steal the space just allocated. This is also used to identify ** appendable segments. */ if( rc==SQLITE_OK ){ rc = fts3WriteSegment(p, pWriter->iEnd, 0, 0); } /* Set up the array of LayerWriter objects */ for(i=0; i<FTS_MAX_APPENDABLE_HEIGHT; i++){ pWriter->aLayer[i].iBlock = pWriter->iStart + i*pWriter->nLeafEst; } pWriter->iAbsLevel = iAbsLevel; pWriter->nLeafEst = nLeafEst; pWriter->iIdx = iIdx; return SQLITE_OK; } /* ** Remove an entry from the %_segdir table. This involves running the ** following two statements: ** ** DELETE FROM %_segdir WHERE level = :iAbsLevel AND idx = :iIdx ** UPDATE %_segdir SET idx = idx - 1 WHERE level = :iAbsLevel AND idx > :iIdx */ static int fts3RemoveSegdirEntry( Fts3Table *p, sqlite3_int64 iAbsLevel, int iIdx ){ int rc; sqlite3_stmt *pDelete = 0; sqlite3_stmt *pUpdate = 0; rc = fts3SqlStmt(p, SQL_DELETE_SEGDIR_ENTRY, &pDelete, 0); if( rc==SQLITE_OK ){ sqlite3_bind_int64(pDelete, 1, iAbsLevel); sqlite3_bind_int(pDelete, 2, iIdx); sqlite3_step(pDelete); rc = sqlite3_reset(pDelete); } if( rc==SQLITE_OK ){ rc = fts3SqlStmt(p, SQL_SHIFT_SEGDIR_ENTRIES, &pUpdate, 0); } if( rc==SQLITE_OK ){ sqlite3_bind_int64(pUpdate, 1, iAbsLevel); sqlite3_bind_int(pUpdate, 2, iIdx); sqlite3_step(pUpdate); rc = sqlite3_reset(pUpdate); } return rc; } static int fts3AppendToNode( Blob *pNode, Blob *pPrev, const char *zTerm, int nTerm, const char *aDoclist, int nDoclist ){ int rc = SQLITE_OK; int bFirst = (pPrev->n==0); int nPrefix; int nSuffix; blobGrowBuffer(pPrev, nTerm, &rc); if( rc!=SQLITE_OK ) return rc; nPrefix = fts3PrefixCompress(pPrev->a, pPrev->n, zTerm, nTerm); nSuffix = nTerm - nPrefix; memcpy(pPrev->a, zTerm, nTerm); pPrev->n = nTerm; if( bFirst==0 ){ pNode->n += sqlite3Fts3PutVarint(&pNode->a[pNode->n], nPrefix); } pNode->n += sqlite3Fts3PutVarint(&pNode->a[pNode->n], nSuffix); memcpy(&pNode->a[pNode->n], &zTerm[nPrefix], nSuffix); pNode->n += nSuffix; if( aDoclist ){ pNode->n += sqlite3Fts3PutVarint(&pNode->a[pNode->n], nDoclist); memcpy(&pNode->a[pNode->n], aDoclist, nDoclist); pNode->n += nDoclist; } return SQLITE_OK; } static void fts3StartNode(Blob *pNode, int iHeight, sqlite3_int64 iChild){ pNode->a[0] = (char)iHeight; if( iChild ){ assert( pNode->nAlloc>=1+sqlite3Fts3VarintLen(iChild) ); pNode->n = 1 + sqlite3Fts3PutVarint(&pNode->a[1], iChild); }else{ assert( pNode->nAlloc>=1 ); pNode->n = 1; } } static int fts3TruncateNode( const char *aNode, /* Current node image */ int nNode, /* Size of aNode in bytes */ Blob *pNew, /* OUT: Write new node image here */ const char *zTerm, /* Omit all terms smaller than this */ int nTerm, /* Size of zTerm in bytes */ sqlite3_int64 *piBlock /* OUT: Block number in next layer down */ ){ NodeReader reader; /* Reader object */ Blob prev = {0, 0, 0}; int rc = SQLITE_OK; int bStarted = 0; /* Allocate required output space */ blobGrowBuffer(pNew, nNode, &rc); if( rc!=SQLITE_OK ) return rc; pNew->n = 0; /* Populate new node buffer */ for(rc = nodeReaderInit(&reader, aNode, nNode); rc==SQLITE_OK && reader.aNode; rc = nodeReaderNext(&reader) ){ if( bStarted==0 ){ if( fts3TermCmp(reader.term.a, reader.term.n, zTerm, nTerm)<0 ) continue; pNew->a[0] = aNode[0]; fts3StartNode(pNew, (int)aNode[0], reader.iChild); *piBlock = reader.iChild; bStarted = 1; } rc = fts3AppendToNode( pNew, &prev, reader.term.a, reader.term.n, reader.aDoclist, reader.nDoclist ); } if( bStarted==0 ){ fts3StartNode(pNew, (int)aNode[0], reader.iChild); *piBlock = reader.iChild; } assert( pNew->n<=pNew->nAlloc ); nodeReaderRelease(&reader); sqlite3_free(prev.a); return rc; } static int fts3TruncateSegment( Fts3Table *p, /* FTS3 table handle */ sqlite3_int64 iAbsLevel, /* Absolute level of segment to modify */ int iIdx, /* Index within level of segment to modify */ const char *zTerm, /* Remove terms smaller than this */ int nTerm /* Number of bytes in buffer zTerm */ ){ int rc; /* Return code */ Blob root = {0,0,0}; /* New root page image */ Blob block = {0,0,0}; /* Buffer used for any other block */ sqlite3_stmt *pFetch = 0; /* Statement used to fetch segdir */ rc = fts3SqlStmt(p, SQL_SELECT_SEGDIR, &pFetch, 0); if( rc==SQLITE_OK ){ sqlite3_int64 iBlock = 0; /* Block id */ sqlite3_int64 iNewStart = 0; sqlite3_int64 iOldStart = 0; int rc2; /* sqlite3_reset() return code */ sqlite3_bind_int64(pFetch, 1, iAbsLevel); sqlite3_bind_int(pFetch, 2, iIdx); if( SQLITE_ROW==sqlite3_step(pFetch) ){ const char *aRoot = sqlite3_column_blob(pFetch, 4); int nRoot = sqlite3_column_bytes(pFetch, 4); iOldStart = sqlite3_column_int64(pFetch, 1); rc = fts3TruncateNode(aRoot, nRoot, &root, zTerm, nTerm, &iBlock); } rc2 = sqlite3_reset(pFetch); if( rc==SQLITE_OK ) rc = rc2; while( rc==SQLITE_OK && iBlock ){ char *aBlock = 0; int nBlock = 0; iNewStart = iBlock; rc = sqlite3Fts3ReadBlock(p, iBlock, &aBlock, &nBlock, 0); if( rc==SQLITE_OK ){ rc = fts3TruncateNode(aBlock, nBlock, &block, zTerm, nTerm, &iBlock); } if( rc==SQLITE_OK ){ rc = fts3WriteSegment(p, iNewStart, block.a, block.n); } sqlite3_free(aBlock); } /* Variable iNewStart now contains the first valid leaf node. */ if( rc==SQLITE_OK && iNewStart ){ sqlite3_stmt *pDel = 0; rc = fts3SqlStmt(p, SQL_DELETE_SEGMENTS_RANGE, &pDel, 0); if( rc==SQLITE_OK ){ sqlite3_bind_int64(pDel, 1, iOldStart); sqlite3_bind_int64(pDel, 2, iNewStart-1); sqlite3_step(pDel); rc = sqlite3_reset(pDel); } } if( rc==SQLITE_OK ){ sqlite3_stmt *pChomp = 0; rc = fts3SqlStmt(p, SQL_CHOMP_SEGDIR, &pChomp, 0); if( rc==SQLITE_OK ){ sqlite3_bind_int64(pChomp, 1, iNewStart); sqlite3_bind_blob(pChomp, 2, root.a, root.n, SQLITE_STATIC); sqlite3_bind_int64(pChomp, 3, iAbsLevel); sqlite3_bind_int(pChomp, 4, iIdx); sqlite3_step(pChomp); rc = sqlite3_reset(pChomp); } } } sqlite3_free(root.a); sqlite3_free(block.a); return rc; } /* ** This function is called after an incrmental-merge operation has run to ** merge (or partially merge) two or more segments from absolute level ** iAbsLevel. ** ** Each input segment is either removed from the db completely (if all of ** its data was copied to the output segment by the incrmerge operation) ** or modified in place so that it no longer contains those entries that ** have been duplicated in the output segment. */ static int fts3IncrmergeChomp( Fts3Table *p, sqlite3_int64 iAbsLevel, Fts3MultiSegReader *pCsr ){ int i; int rc = SQLITE_OK; assert( pCsr->nSegment==2 ); assert( (pCsr->apSegment[0]->iIdx==0 && pCsr->apSegment[1]->iIdx==1) || (pCsr->apSegment[1]->iIdx==0 && pCsr->apSegment[0]->iIdx==1) ); for(i=1; i>=0; i--){ Fts3SegReader *pSeg = pCsr->apSegment[0]; if( pSeg->iIdx!=i ) pSeg = pCsr->apSegment[1]; assert( pSeg->iIdx==i ); if( pSeg->aNode==0 ){ /* Seg-reader is at EOF. Remove the entire input segment. */ rc = fts3DeleteSegment(p, pSeg); if( rc==SQLITE_OK ){ rc = fts3RemoveSegdirEntry(p, iAbsLevel, pSeg->iIdx); } }else{ /* The incremental merge did not copy all the data from this ** segment to the upper level. The segment is modified in place ** so that it contains no keys smaller than zTerm/nTerm. */ const char *zTerm = pSeg->zTerm; int nTerm = pSeg->nTerm; rc = fts3TruncateSegment(p, iAbsLevel, pSeg->iIdx, zTerm, nTerm); } } return rc; } static int fts3Incrmerge(Fts3Table *p, int nMerge, int nMin){ int rc = SQLITE_OK; /* Return code */ int nRem = nMerge; assert( nMin>=2 ); while( rc==SQLITE_OK && nRem>0 ){ sqlite3_int64 iAbsLevel; /* Absolute level number to work on */ sqlite3_stmt *pFindLevel = 0; /* SQL used to determine iAbsLevel */ Fts3MultiSegReader csr; /* Cursor used to read input data */ Fts3SegFilter filter; /* Filter used with cursor csr */ IncrmergeWriter writer; /* Writer object */ memset(&writer, 0, sizeof(IncrmergeWriter)); /* Determine which level to merge segments from. Any level, from any ** prefix or language index may be selected. Stack variable iAbsLevel ** is set to the absolute level number of the level to merge from. */ rc = fts3SqlStmt(p, SQL_FIND_MERGE_LEVEL, &pFindLevel, 0); if( rc!=SQLITE_OK ) return rc; sqlite3_bind_int(pFindLevel, 1, nMin); if( sqlite3_step(pFindLevel)!=SQLITE_ROW ){ return sqlite3_reset(pFindLevel); } iAbsLevel = sqlite3_column_int64(pFindLevel, 0); rc = sqlite3_reset(pFindLevel); if( rc!=SQLITE_OK ) return rc; /* Open a cursor to iterate through the contents of indexes 0 and 1 of ** the selected absolute level. */ rc = fts3IncrmergeCsr(p, iAbsLevel, &csr); if( rc!=SQLITE_OK ) return rc; memset(&filter, 0, sizeof(Fts3SegFilter)); filter.flags = FTS3_SEGMENT_REQUIRE_POS; rc = sqlite3Fts3SegReaderStart(p, &csr, &filter); assert( rc!=SQLITE_ABORT ); if( SQLITE_ROW==(rc = sqlite3Fts3SegReaderStep(p, &csr)) ){ rc = fts3IncrmergeWriter(p, iAbsLevel, csr.zTerm, csr.nTerm, &writer); assert( rc!=SQLITE_ABORT ); if( rc==SQLITE_OK ){ do { rc = fts3IncrmergeAppend(p, &writer, &csr); assert( rc!=SQLITE_ABORT ); if( rc==SQLITE_OK ) rc = sqlite3Fts3SegReaderStep(p, &csr); assert( rc!=SQLITE_ABORT ); if( writer.nWork>=nRem && rc==SQLITE_ROW ) rc = SQLITE_OK; }while( rc==SQLITE_ROW ); } } assert( rc!=SQLITE_ABORT ); fts3IncrmergeRelease(p, &writer, &rc); nRem -= (1 + writer.nWork); /* Update or delete the input segments */ if( rc==SQLITE_OK ){ rc = fts3IncrmergeChomp(p, iAbsLevel, &csr); } sqlite3Fts3SegReaderFinish(&csr); } return rc; } static int fts3_isdigit(char c){ return (c>='0' && c<='9'); } static int fts3DoIncrmerge(Fts3Table *p, const char *zParam){ int rc; int nMin = (FTS3_MERGE_COUNT / 2); int nMerge = 0; const char *z = zParam; /* Read the first integer value */ for(z=zParam; fts3_isdigit(z[0]); z++){ nMerge = nMerge * 10 + (z[0] - '0'); } /* If the first integer value is followed by a ',', read the second ** integer value. */ if( z[0]==',' && z[1]!='\0' ){ z++; nMin = 0; while( fts3_isdigit(z[0]) ){ nMin = nMin * 10 + (z[0] - '0'); z++; } } if( z[0]!='\0' ) return SQLITE_ERROR; if( nMin<2 ) nMin = 2; rc = fts3Incrmerge(p, nMerge, nMin); sqlite3Fts3SegmentsClose(p); return rc; } /* ** Handle a 'special' INSERT of the form: ** ** "INSERT INTO tbl(tbl) VALUES(<expr>)" ** ** Argument pVal contains the result of <expr>. Currently the only ** meaningful value to insert is the text 'optimize'. */ static int fts3SpecialInsert(Fts3Table *p, sqlite3_value *pVal){ int rc; /* Return Code */ const char *zVal = (const char *)sqlite3_value_text(pVal); int nVal = sqlite3_value_bytes(pVal); if( !zVal ){ return SQLITE_NOMEM; }else if( nVal==8 && 0==sqlite3_strnicmp(zVal, "optimize", 8) ){ rc = fts3DoOptimize(p, 0); }else if( nVal==7 && 0==sqlite3_strnicmp(zVal, "rebuild", 7) ){ rc = fts3DoRebuild(p); }else if( nVal>6 && 0==sqlite3_strnicmp(zVal, "merge=", 6) ){ rc = fts3DoIncrmerge(p, &zVal[6]); #ifdef SQLITE_TEST }else if( nVal>9 && 0==sqlite3_strnicmp(zVal, "nodesize=", 9) ){ p->nNodeSize = atoi(&zVal[9]); rc = SQLITE_OK; }else if( nVal>11 && 0==sqlite3_strnicmp(zVal, "maxpending=", 9) ){ p->nMaxPendingData = atoi(&zVal[11]); rc = SQLITE_OK; |
︙ | ︙ |
Changes to test/fts3_common.tcl.
︙ | ︙ | |||
42 43 44 45 46 47 48 49 50 51 52 53 54 55 | # # proc fts3_integrity_check {tbl} { fts3_read2 $tbl 1 A foreach zTerm [array names A] { foreach doclist $A($zTerm) { set docid 0 while {[string length $doclist]>0} { set iCol 0 set iPos 0 set lPos [list] set lCol [list] | > | 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 | # # proc fts3_integrity_check {tbl} { fts3_read2 $tbl 1 A foreach zTerm [array names A] { #puts $zTerm foreach doclist $A($zTerm) { set docid 0 while {[string length $doclist]>0} { set iCol 0 set iPos 0 set lPos [list] set lCol [list] |
︙ | ︙ | |||
229 230 231 232 233 234 235 | while {[string length $blob] > 0} { set nPrefix [gobble_varint blob] set nSuffix [gobble_varint blob] set zTerm [string range $zPrev 0 [expr $nPrefix-1]] append zTerm [gobble_string blob $nSuffix] | > | > > | < | 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 258 259 260 261 262 263 264 265 266 267 268 269 270 271 | while {[string length $blob] > 0} { set nPrefix [gobble_varint blob] set nSuffix [gobble_varint blob] set zTerm [string range $zPrev 0 [expr $nPrefix-1]] append zTerm [gobble_string blob $nSuffix] set nDoclist [gobble_varint blob] set doclist [gobble_string blob $nDoclist] lappend terms $zTerm $doclist set zPrev $zTerm } return $terms } proc fts3_read2 {tbl where varname} { upvar $varname a array unset a db eval " SELECT start_block, leaves_end_block, root FROM ${tbl}_segdir WHERE $where ORDER BY level ASC, idx DESC " { set c 0 binary scan $root c c if {$c==0} { foreach {t d} [fts3_readleaf $root] { lappend a($t) $d } } else { db eval " SELECT block FROM ${tbl}_segments WHERE blockid>=$start_block AND blockid<=$leaves_end_block ORDER BY blockid " { foreach {t d} [fts3_readleaf $block] { lappend a($t) $d } } } } } proc fts3_read {tbl where varname} { upvar $varname a |
︙ | ︙ |
Added test/fts4merge.test.
> > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 1 2 3 4 5 6 7 8 9 10 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 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 | # 2012 March 06 # # The author disclaims copyright to this source code. In place of # a legal notice, here is a blessing: # # May you do good and not evil. # May you find forgiveness for yourself and forgive others. # May you share freely, never taking more than you give. # #************************************************************************* # This file implements regression tests for SQLite library. The # focus of this script is testing the incremental merge function. # set testdir [file dirname $argv0] source $testdir/tester.tcl source $testdir/fts3_common.tcl set ::testprefix fts4merge # If SQLITE_ENABLE_FTS3 is defined, omit this file. ifcapable !fts3 { finish_test return } proc fts3_build_db_1 {n} { if {$n > 10000} {error "n must be <= 10000"} db eval { CREATE VIRTUAL TABLE t1 USING fts4(x, y) } set xwords [list zero one two three four five six seven eight nine ten] set ywords [list alpha beta gamma delta epsilon zeta eta theta iota kappa] for {set i 0} {$i < $n} {incr i} { set x "" set y "" set x [list] lappend x [lindex $xwords [expr ($i / 1000) % 10]] lappend x [lindex $xwords [expr ($i / 100) % 10]] lappend x [lindex $xwords [expr ($i / 10) % 10]] lappend x [lindex $xwords [expr ($i / 1) % 10]] set y [list] lappend y [lindex $ywords [expr ($i / 1000) % 10]] lappend y [lindex $ywords [expr ($i / 100) % 10]] lappend y [lindex $ywords [expr ($i / 10) % 10]] lappend y [lindex $ywords [expr ($i / 1) % 10]] db eval { INSERT INTO t1(docid, x, y) VALUES($i, $x, $y) } } } #------------------------------------------------------------------------- # Test cases 1.* # do_test 1.0 { fts3_build_db_1 1004 } {} do_test 1.1 { fts3_integrity_check t1 } {ok} do_execsql_test 1.1 { SELECT level, group_concat(idx, ' ') FROM t1_segdir GROUP BY level } { 0 {0 1 2 3 4 5 6 7 8 9 10 11} 1 {0 1 2 3 4 5 6 7 8 9 10 11 12 13} 2 {0 1 2} } for {set i 0} {$i<20} {incr i} { do_execsql_test 1.2.$i.1 { INSERT INTO t1(t1) VALUES('merge=1') } do_test 1.2.$i.2 { fts3_integrity_check t1 } ok do_execsql_test 1.2.$i.3 { SELECT docid FROM t1 WHERE t1 MATCH 'zero one two three' } {123 132 213 231 312 321} } do_execsql_test 1.3 { SELECT level, group_concat(idx, ' ') FROM t1_segdir GROUP BY level } { 0 {0 1 2 3 4 5 6 7} 1 {0 1 2 3 4 5 6 7} 2 {0 1 2 3 4 5 6} } for {set i 0} {$i<100} {incr i} { do_execsql_test 1.4.$i { INSERT INTO t1(t1) VALUES('merge=1,4') } do_test 1.4.$i.2 { fts3_integrity_check t1 } ok do_execsql_test 1.4.$i.3 { SELECT docid FROM t1 WHERE t1 MATCH 'zero one two three' } {123 132 213 231 312 321} } do_execsql_test 1.5 { SELECT level, group_concat(idx, ' ') FROM t1_segdir GROUP BY level } { 0 {0 1 2 3} 1 {0 1 2 3} 2 {0 1 2 3} 3 {0 1 2} } finish_test |