From 4ab6f2b9c1fba9d2a40d7b15c4c8b1742bf16dcb Mon Sep 17 00:00:00 2001 From: dan Date: Thu, 15 Mar 2012 17:45:50 +0000 Subject: [PATCH] Modify incremental merge code to merge nMin segments at a time. FossilOrigin-Name: cd34bc1af4ba608ea3b52bab55bcfe0086711900 --- ext/fts3/fts3_write.c | 58 +++++++++++++++++++++++++++---------------- manifest | 16 ++++++------ manifest.uuid | 2 +- test/fts3_common.tcl | 8 +++--- test/fts4merge.test | 18 +++++++------- 5 files changed, 59 insertions(+), 43 deletions(-) diff --git a/ext/fts3/fts3_write.c b/ext/fts3/fts3_write.c index 08f07c10b2..a6ee1f6919 100644 --- a/ext/fts3/fts3_write.c +++ b/ext/fts3/fts3_write.c @@ -306,10 +306,10 @@ static int fts3SqlStmt( " 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. */ +** created by merging the oldest :2 segments from absolute level :1. 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", + " FROM %Q.'%q_segdir' WHERE level = ? AND idx < ?", /* SQL_DELETE_SEGDIR_ENTRY ** Delete the %_segdir entry on absolute level :1 with index :2. */ @@ -1077,6 +1077,9 @@ static int fts3AllocateSegdirIdx( ** if iNext is less than FTS3_MERGE_COUNT, allocate index iNext. */ if( iNext>=FTS3_MERGE_COUNT ){ +sqlite3_log(SQLITE_OK, + "16-way merge at level=%d langid=%d index=%d", iLevel, iLangid, iIndex +); rc = fts3SegmentMerge(p, iLangid, iIndex, iLevel); *piIdx = 0; }else{ @@ -3232,25 +3235,30 @@ static int fts3DoRebuild(Fts3Table *p){ static int fts3IncrmergeCsr( Fts3Table *p, /* FTS3 table handle */ sqlite3_int64 iAbsLevel, /* Absolute level to open */ + int nSeg, /* Number of segments to merge */ Fts3MultiSegReader *pCsr /* Cursor object to populate */ ){ int rc; /* Return Code */ - sqlite3_stmt *pStmt = 0; + sqlite3_stmt *pStmt = 0; /* Statement used to read %_segdir entry */ + int nByte; /* Bytes allocated at pCsr->apSegment[] */ + assert( nSeg>=2 ); memset(pCsr, 0, sizeof(*pCsr)); - pCsr->apSegment = (Fts3SegReader **)sqlite3_malloc(sizeof(Fts3SegReader *)*2); + nByte = sizeof(Fts3SegReader *) * nSeg; + + pCsr->apSegment = (Fts3SegReader **)sqlite3_malloc(nByte); if( pCsr->apSegment==0 ){ rc = SQLITE_NOMEM; }else{ - memset(pCsr->apSegment, 0, sizeof(Fts3SegReader *)*2); - pCsr->nSegment = 2; + memset(pCsr->apSegment, 0, nByte); + pCsr->nSegment = nSeg; 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++){ + for(i=0; rc==SQLITE_OK && sqlite3_step(pStmt)==SQLITE_ROW && izTerm; + int nKey = pCsr->nTerm; rc = fts3SqlStmt(p, SQL_NEXT_SEGMENT_INDEX, &pOutputIdx, 0); if( rc==SQLITE_OK ){ @@ -3849,6 +3858,7 @@ static int fts3IncrmergeWriter( rc = fts3SqlStmt(p, SQL_MAX_LEAF_NODE_ESTIMATE, &pLeafEst, 0); if( rc==SQLITE_OK ){ sqlite3_bind_int64(pLeafEst, 1, iAbsLevel); + sqlite3_bind_int64(pLeafEst, 2, pCsr->nSegment); if( SQLITE_ROW==sqlite3_step(pLeafEst) ){ nLeafEst = sqlite3_column_int(pLeafEst, 0); } @@ -4120,15 +4130,17 @@ static int fts3IncrmergeChomp( 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=pCsr->nSegment-1; i>=0 && rc==SQLITE_OK; i--){ + Fts3SegReader *pSeg = 0; + int j; - for(i=1; i>=0 && rc==SQLITE_OK; i--){ - Fts3SegReader *pSeg = pCsr->apSegment[0]; - if( pSeg->iIdx!=i ) pSeg = pCsr->apSegment[1]; - assert( pSeg->iIdx==i ); + /* Find the Fts3SegReader object with Fts3SegReader.iIdx==i. It is hiding + ** somewhere in the pCsr->apSegment[] array. */ + for(j=0; ALWAYS(jnSegment); j++){ + pSeg = pCsr->apSegment[j]; + if( pSeg->iIdx==i ) break; + } + assert( jnSegment && pSeg->iIdx==i ); if( pSeg->aNode==0 ){ /* Seg-reader is at EOF. Remove the entire input segment. */ @@ -4178,6 +4190,8 @@ static int fts3Incrmerge(Fts3Table *p, int nMerge, int nMin){ rc = fts3SqlStmt(p, SQL_FIND_MERGE_LEVEL, &pFindLevel, 0); sqlite3_bind_int(pFindLevel, 1, nMin); if( sqlite3_step(pFindLevel)!=SQLITE_ROW ){ + /* There are no levels with nMin or more segments. Or an error has + ** occurred. Either way, exit early. */ return sqlite3_reset(pFindLevel); } iAbsLevel = sqlite3_column_int64(pFindLevel, 0); @@ -4193,14 +4207,16 @@ static int fts3Incrmerge(Fts3Table *p, int nMerge, int nMin){ /* Open a cursor to iterate through the contents of indexes 0 and 1 of ** the selected absolute level. */ pFilter->flags = FTS3_SEGMENT_REQUIRE_POS; - rc = fts3IncrmergeCsr(p, iAbsLevel, pCsr); - + rc = fts3IncrmergeCsr(p, iAbsLevel, nMin, pCsr); +sqlite3_log(SQLITE_OK, "%d-way merge from level=%d to level=%d", + nMin, (int)iAbsLevel, (int)iAbsLevel+1 +); if( rc==SQLITE_OK ){ rc = sqlite3Fts3SegReaderStart(p, pCsr, pFilter); } if( rc==SQLITE_OK ){ if( SQLITE_ROW==(rc = sqlite3Fts3SegReaderStep(p, pCsr)) ){ - rc = fts3IncrmergeWriter(p, iAbsLevel, pCsr->zTerm,pCsr->nTerm,pWriter); + rc = fts3IncrmergeWriter(p, iAbsLevel, pCsr, pWriter); if( rc==SQLITE_OK ){ do { rc = fts3IncrmergeAppend(p, pWriter, pCsr); diff --git a/manifest b/manifest index 06d7ae13ce..88b357ba30 100644 --- a/manifest +++ b/manifest @@ -1,5 +1,5 @@ -C Add\stests\sfor\sincremental\smerge\scode. -D 2012-03-14T20:01:52.250 +C Modify\sincremental\smerge\scode\sto\smerge\snMin\ssegments\sat\sa\stime. +D 2012-03-15T17:45:50.857 F Makefile.arm-wince-mingw32ce-gcc d6df77f1f48d690bd73162294bbba7f59507c72f F Makefile.in 3f79a373e57c3b92dabf76f40b065e719d31ac34 F Makefile.linux-gcc 91d710bdc4998cb015f39edf3cb314ec4f4d7e23 @@ -78,7 +78,7 @@ F ext/fts3/fts3_test.c 6b7cc68aef4efb084e1449f7d20c4b20d3bdf6b4 F ext/fts3/fts3_tokenizer.c 3da7254a9881f7e270ab28e2004e0d22b3212bce F ext/fts3/fts3_tokenizer.h 66dec98e365854b6cd2d54f1a96bb6d428fc5a68 F ext/fts3/fts3_tokenizer1.c 0dde8f307b8045565cf63797ba9acfaff1c50c68 -F ext/fts3/fts3_write.c 355121666034ece7d2472caa3f322d0cb61b0f0d +F ext/fts3/fts3_write.c be60aaf4a887a68aaf0d7541bc78413e7ba66291 F ext/fts3/fts3speed.tcl b54caf6a18d38174f1a6e84219950d85e98bb1e9 F ext/fts3/mkfts3amal.tcl 252ecb7fe6467854f2aa237bf2c390b74e71f100 F ext/icu/README.txt bf8461d8cdc6b8f514c080e4e10dc3b2bbdfefa9 @@ -448,7 +448,7 @@ F test/fts2q.test b2fbbe038b7a31a52a6079b215e71226d8c6a682 F test/fts2r.test b154c30b63061d8725e320fba1a39e2201cadd5e F test/fts2token.test d8070b241a15ff13592a9ae4a8b7c171af6f445a F test/fts3.test 672a040ea57036fb4b6fdc09027c18d7d24ab654 -F test/fts3_common.tcl 1b2e522476236a018c1a4b8ae4f7599ce29b7be0 +F test/fts3_common.tcl d65de7e21c2b933bf17152830eb924356f197c8f F test/fts3aa.test 909d5f530d30a8e36b9328d67285eae6537c79c0 F test/fts3ab.test 09aeaa162aee6513d9ff336b6932211008b9d1f9 F test/fts3ac.test 636ed7486043055d4f126a0e385f2d5a82ebbf63 @@ -497,7 +497,7 @@ F test/fts3sort.test 95be0b19d7e41c44b29014f13ea8bddd495fd659 F test/fts4aa.test 6e7f90420b837b2c685f3bcbe84c868492d40a68 F test/fts4content.test 17b2360f7d1a9a7e5aa8022783f5c5731b6dfd4f F test/fts4langid.test fabdd5a8db0fa00292e0704809f566e3fb6dba3a -F test/fts4merge.test d841f283bf9557d549afde513fe38d0b48adc4f7 +F test/fts4merge.test 1c3389a3be18498934baf76afe67663d8b4b5e42 F test/fts4merge2.test 5faa558d1b672f82b847d2a337465fa745e46891 F test/func.test 6c5ce11e3a0021ca3c0649234e2d4454c89110ca F test/func2.test 772d66227e4e6684b86053302e2d74a2500e1e0f @@ -994,7 +994,7 @@ F tool/tostr.awk e75472c2f98dd76e06b8c9c1367f4ab07e122d06 F tool/vdbe-compress.tcl d70ea6d8a19e3571d7ab8c9b75cba86d1173ff0f F tool/warnings-clang.sh 9f406d66e750e8ac031c63a9ef3248aaa347ef2a F tool/warnings.sh fbc018d67fd7395f440c28f33ef0f94420226381 -P 36ae510de45be44efd34cff242d02fb21b7419ac -R 326f29ae3378aab5424c0bd2deaa1142 +P 570473729d6561d81e6e5f8884fd18487008636e +R 8deb5f38fb61fdd986c036580c00c7d8 U dan -Z 9fe983241614f7794efd59c0386308c4 +Z c18f3e75d81727125e658ae77334fefb diff --git a/manifest.uuid b/manifest.uuid index 9cec3849f5..08619b20e5 100644 --- a/manifest.uuid +++ b/manifest.uuid @@ -1 +1 @@ -570473729d6561d81e6e5f8884fd18487008636e \ No newline at end of file +cd34bc1af4ba608ea3b52bab55bcfe0086711900 \ No newline at end of file diff --git a/test/fts3_common.tcl b/test/fts3_common.tcl index 6c9c2fcec9..f031f927d6 100644 --- a/test/fts3_common.tcl +++ b/test/fts3_common.tcl @@ -66,10 +66,10 @@ proc fts3_build_db_2 {n} { for {set i 0} {$i < $n} {incr i} { set word "" - set n [llength $chars] - append word [lindex $chars [expr {($i / 1) % $n}]] - append word [lindex $chars [expr {($i / $n) % $n}]] - append word [lindex $chars [expr {($i / ($n*$n)) % $n}]] + set nChar [llength $chars] + append word [lindex $chars [expr {($i / 1) % $nChar}]] + append word [lindex $chars [expr {($i / $nChar) % $nChar}]] + append word [lindex $chars [expr {($i / ($nChar*$nChar)) % $nChar}]] db eval { INSERT INTO t2(docid, content) VALUES($i, $word) } } diff --git a/test/fts4merge.test b/test/fts4merge.test index a5995921f3..9f7e05b0ed 100644 --- a/test/fts4merge.test +++ b/test/fts4merge.test @@ -47,9 +47,9 @@ for {set i 0} {$i<20} {incr i} { 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} + 0 {0 1 2 3} + 1 {0 1 2 3 4 5 6} + 2 {0 1 2 3} } for {set i 0} {$i<100} {incr i} { @@ -64,9 +64,9 @@ 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} + 1 {0 1 2} + 2 0 + 3 0 } #------------------------------------------------------------------------- @@ -103,7 +103,7 @@ do_test 3.1 { fts3_integrity_check t2 } {ok} do_execsql_test 3.2 { SELECT level, group_concat(idx, ' ') FROM t2_segdir GROUP BY level } { - 0 {0 1 2 3 4 5 6 7} + 0 {0 1 2 3 4 5 6} 1 {0 1 2 3 4} 2 {0 1 2 3 4} 3 {0 1 2 3 4 5 6} @@ -113,10 +113,10 @@ do_execsql_test 3.3 { INSERT INTO t2(t2) VALUES('merge=1000000,2'); SELECT level, group_concat(idx, ' ') FROM t2_segdir GROUP BY level } { - 0 {0 1} + 0 0 1 {0 1} 2 0 - 3 {0 1} + 3 {0 1} 4 {0 1} 5 0 } -- 2.47.2