/ Check-in [ab0a4f44]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Following an incr-merge operation that does not completely consume its input segments, store context in the rowid==1 row of the %_stat table that allows the next incr-merge to pick up where the previous left off.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | fts4-incr-merge
Files: files | file ages | folders
SHA1: ab0a4f44fb67e9f0cb82297b80e728ca58cdb0fb
User & Date: dan 2012-03-22 16:48:12
Context
2012-03-22
17:48
Add test cases to fts4merge.test. check-in: ecab2083 user: dan tags: fts4-incr-merge
16:48
Following an incr-merge operation that does not completely consume its input segments, store context in the rowid==1 row of the %_stat table that allows the next incr-merge to pick up where the previous left off. check-in: ab0a4f44 user: dan tags: fts4-incr-merge
2012-03-21
14:34
Add fts4merge3.test, for testing that older versions of FTS4 may interoperate with incr-merge capable versions. check-in: 903ec512 user: dan tags: fts4-incr-merge
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to ext/fts3/fts3_write.c.

    62     62   # define FTS3_NODE_CHUNKSIZE       test_fts3_node_chunksize
    63     63   # define FTS3_NODE_CHUNK_THRESHOLD test_fts3_node_chunk_threshold
    64     64   #else
    65     65   # define FTS3_NODE_CHUNKSIZE (4*1024) 
    66     66   # define FTS3_NODE_CHUNK_THRESHOLD (FTS3_NODE_CHUNKSIZE*4)
    67     67   #endif
    68     68   
           69  +/*
           70  +** The two values that may be meaningfully bound to the :1 parameter in
           71  +** statements SQL_REPLACE_STAT and SQL_SELECT_STAT.
           72  +*/
           73  +#define FTS_STAT_DOCTOTAL      0
           74  +#define FTS_STAT_INCRMERGEHINT 1
    69     75   
    70     76   /*
    71     77   ** If FTS_LOG_MERGES is defined, call sqlite3_log() to report each automatic
    72     78   ** and incremental merge operation that takes place. This is used for 
    73     79   ** debugging FTS only, it should not usually be turned on in production
    74     80   ** systems.
    75     81   */
................................................................................
   239    245   #define SQL_SELECT_SEGDIR_MAX_LEVEL   15
   240    246   #define SQL_DELETE_SEGDIR_LEVEL       16
   241    247   #define SQL_DELETE_SEGMENTS_RANGE     17
   242    248   #define SQL_CONTENT_INSERT            18
   243    249   #define SQL_DELETE_DOCSIZE            19
   244    250   #define SQL_REPLACE_DOCSIZE           20
   245    251   #define SQL_SELECT_DOCSIZE            21
   246         -#define SQL_SELECT_DOCTOTAL           22
   247         -#define SQL_REPLACE_DOCTOTAL          23
          252  +#define SQL_SELECT_STAT               22
          253  +#define SQL_REPLACE_STAT              23
   248    254   
   249    255   #define SQL_SELECT_ALL_PREFIX_LEVEL   24
   250    256   #define SQL_DELETE_ALL_TERMS_SEGDIR   25
   251    257   #define SQL_DELETE_SEGDIR_RANGE       26
   252    258   #define SQL_SELECT_ALL_LANGID         27
   253    259   #define SQL_FIND_MERGE_LEVEL          28
   254    260   #define SQL_MAX_LEAF_NODE_ESTIMATE    29
................................................................................
   301    307   
   302    308   /* 16 */  "DELETE FROM %Q.'%q_segdir' WHERE level = ?",
   303    309   /* 17 */  "DELETE FROM %Q.'%q_segments' WHERE blockid BETWEEN ? AND ?",
   304    310   /* 18 */  "INSERT INTO %Q.'%q_content' VALUES(%s)",
   305    311   /* 19 */  "DELETE FROM %Q.'%q_docsize' WHERE docid = ?",
   306    312   /* 20 */  "REPLACE INTO %Q.'%q_docsize' VALUES(?,?)",
   307    313   /* 21 */  "SELECT size FROM %Q.'%q_docsize' WHERE docid=?",
   308         -/* 22 */  "SELECT value FROM %Q.'%q_stat' WHERE id=0",
   309         -/* 23 */  "REPLACE INTO %Q.'%q_stat' VALUES(0,?)",
          314  +/* 22 */  "SELECT value FROM %Q.'%q_stat' WHERE id=?",
          315  +/* 23 */  "REPLACE INTO %Q.'%q_stat' VALUES(?,?)",
   310    316   /* 24 */  "",
   311    317   /* 25 */  "",
   312    318   
   313    319   /* 26 */ "DELETE FROM %Q.'%q_segdir' WHERE level BETWEEN ? AND ?",
   314    320   /* 27 */ "SELECT DISTINCT level / (1024 * ?) FROM %Q.'%q_segdir'",
   315    321   
   316    322   /* This statement is used to determine which level to read the input from
   317    323   ** when performing an incremental merge. It returns the absolute level number
   318    324   ** of the oldest level in the db that contains at least ? segments. Or,
   319    325   ** if no level in the FTS index contains more than ? segments, the statement
   320    326   ** returns zero rows.  */
   321         -/* 28 */ "SELECT level FROM %Q.'%q_segdir' GROUP BY level HAVING count(*)>?"
          327  +/* 28 */ "SELECT level FROM %Q.'%q_segdir' GROUP BY level HAVING count(*)>=?"
   322    328            "  ORDER BY (level %% 1024) DESC LIMIT 1",
   323    329   
   324    330   /* Estimate the upper limit on the number of leaf nodes in a new segment
   325    331   ** created by merging the oldest :2 segments from absolute level :1. See 
   326    332   ** function fts3Incrmerge() for details.  */
   327    333   /* 29 */ "SELECT 2 * total(1 + leaves_end_block - start_block) "
   328    334            "  FROM %Q.'%q_segdir' WHERE level = ? AND idx < ?",
................................................................................
   388    394     *pp = pStmt;
   389    395     return rc;
   390    396   }
   391    397   
   392    398   
   393    399   static int fts3SelectDocsize(
   394    400     Fts3Table *pTab,                /* FTS3 table handle */
   395         -  int eStmt,                      /* Either SQL_SELECT_DOCSIZE or DOCTOTAL */
   396    401     sqlite3_int64 iDocid,           /* Docid to bind for SQL_SELECT_DOCSIZE */
   397    402     sqlite3_stmt **ppStmt           /* OUT: Statement handle */
   398    403   ){
   399    404     sqlite3_stmt *pStmt = 0;        /* Statement requested from fts3SqlStmt() */
   400    405     int rc;                         /* Return code */
   401    406   
   402         -  assert( eStmt==SQL_SELECT_DOCSIZE || eStmt==SQL_SELECT_DOCTOTAL );
   403         -
   404         -  rc = fts3SqlStmt(pTab, eStmt, &pStmt, 0);
          407  +  rc = fts3SqlStmt(pTab, SQL_SELECT_DOCSIZE, &pStmt, 0);
   405    408     if( rc==SQLITE_OK ){
   406         -    if( eStmt==SQL_SELECT_DOCSIZE ){
   407         -      sqlite3_bind_int64(pStmt, 1, iDocid);
   408         -    }
          409  +    sqlite3_bind_int64(pStmt, 1, iDocid);
   409    410       rc = sqlite3_step(pStmt);
   410    411       if( rc!=SQLITE_ROW || sqlite3_column_type(pStmt, 0)!=SQLITE_BLOB ){
   411    412         rc = sqlite3_reset(pStmt);
   412    413         if( rc==SQLITE_OK ) rc = FTS_CORRUPT_VTAB;
   413    414         pStmt = 0;
   414    415       }else{
   415    416         rc = SQLITE_OK;
................................................................................
   420    421     return rc;
   421    422   }
   422    423   
   423    424   int sqlite3Fts3SelectDoctotal(
   424    425     Fts3Table *pTab,                /* Fts3 table handle */
   425    426     sqlite3_stmt **ppStmt           /* OUT: Statement handle */
   426    427   ){
   427         -  return fts3SelectDocsize(pTab, SQL_SELECT_DOCTOTAL, 0, ppStmt);
          428  +  sqlite3_stmt *pStmt = 0;
          429  +  int rc;
          430  +  rc = fts3SqlStmt(pTab, SQL_SELECT_STAT, &pStmt, 0);
          431  +  if( rc==SQLITE_OK ){
          432  +    sqlite3_bind_int(pStmt, 1, FTS_STAT_DOCTOTAL);
          433  +    if( sqlite3_step(pStmt)!=SQLITE_ROW
          434  +     || sqlite3_column_type(pStmt, 0)!=SQLITE_BLOB
          435  +    ){
          436  +      rc = sqlite3_reset(pStmt);
          437  +      if( rc==SQLITE_OK ) rc = FTS_CORRUPT_VTAB;
          438  +      pStmt = 0;
          439  +    }
          440  +  }
          441  +  *ppStmt = pStmt;
          442  +  return rc;
   428    443   }
   429    444   
   430    445   int sqlite3Fts3SelectDocsize(
   431    446     Fts3Table *pTab,                /* Fts3 table handle */
   432    447     sqlite3_int64 iDocid,           /* Docid to read size data for */
   433    448     sqlite3_stmt **ppStmt           /* OUT: Statement handle */
   434    449   ){
   435         -  return fts3SelectDocsize(pTab, SQL_SELECT_DOCSIZE, iDocid, ppStmt);
          450  +  return fts3SelectDocsize(pTab, iDocid, ppStmt);
   436    451   }
   437    452   
   438    453   /*
   439    454   ** Similar to fts3SqlStmt(). Except, after binding the parameters in
   440    455   ** array apVal[] to the SQL statement identified by eStmt, the statement
   441    456   ** is executed.
   442    457   **
................................................................................
  3090   3105     if( *pRC ) return;
  3091   3106     a = sqlite3_malloc( (sizeof(u32)+10)*nStat );
  3092   3107     if( a==0 ){
  3093   3108       *pRC = SQLITE_NOMEM;
  3094   3109       return;
  3095   3110     }
  3096   3111     pBlob = (char*)&a[nStat];
  3097         -  rc = fts3SqlStmt(p, SQL_SELECT_DOCTOTAL, &pStmt, 0);
         3112  +  rc = fts3SqlStmt(p, SQL_SELECT_STAT, &pStmt, 0);
  3098   3113     if( rc ){
  3099   3114       sqlite3_free(a);
  3100   3115       *pRC = rc;
  3101   3116       return;
  3102   3117     }
         3118  +  sqlite3_bind_int(pStmt, 1, FTS_STAT_DOCTOTAL);
  3103   3119     if( sqlite3_step(pStmt)==SQLITE_ROW ){
  3104   3120       fts3DecodeIntArray(nStat, a,
  3105   3121            sqlite3_column_blob(pStmt, 0),
  3106   3122            sqlite3_column_bytes(pStmt, 0));
  3107   3123     }else{
  3108   3124       memset(a, 0, sizeof(u32)*(nStat) );
  3109   3125     }
................................................................................
  3119   3135         x = 0;
  3120   3136       }else{
  3121   3137         x = x + aSzIns[i] - aSzDel[i];
  3122   3138       }
  3123   3139       a[i+1] = x;
  3124   3140     }
  3125   3141     fts3EncodeIntArray(nStat, a, pBlob, &nBlob);
  3126         -  rc = fts3SqlStmt(p, SQL_REPLACE_DOCTOTAL, &pStmt, 0);
         3142  +  rc = fts3SqlStmt(p, SQL_REPLACE_STAT, &pStmt, 0);
  3127   3143     if( rc ){
  3128   3144       sqlite3_free(a);
  3129   3145       *pRC = rc;
  3130   3146       return;
  3131   3147     }
  3132         -  sqlite3_bind_blob(pStmt, 1, pBlob, nBlob, SQLITE_STATIC);
         3148  +  sqlite3_bind_int(pStmt, 1, FTS_STAT_DOCTOTAL);
         3149  +  sqlite3_bind_blob(pStmt, 2, pBlob, nBlob, SQLITE_STATIC);
  3133   3150     sqlite3_step(pStmt);
  3134   3151     *pRC = sqlite3_reset(pStmt);
  3135   3152     sqlite3_free(a);
  3136   3153   }
  3137   3154   
  3138   3155   /*
  3139   3156   ** Merge the entire database so that there is one segment for each 
................................................................................
  3273   3290     nByte = sizeof(Fts3SegReader *) * nSeg;
  3274   3291     pCsr->apSegment = (Fts3SegReader **)sqlite3_malloc(nByte);
  3275   3292   
  3276   3293     if( pCsr->apSegment==0 ){
  3277   3294       rc = SQLITE_NOMEM;
  3278   3295     }else{
  3279   3296       memset(pCsr->apSegment, 0, nByte);
  3280         -    pCsr->nSegment = nSeg;
  3281   3297       rc = fts3SqlStmt(p, SQL_SELECT_LEVEL, &pStmt, 0);
  3282   3298     }
  3283   3299     if( rc==SQLITE_OK ){
  3284   3300       int i;
  3285   3301       int rc2;
  3286   3302       sqlite3_bind_int64(pStmt, 1, iAbsLevel);
         3303  +    assert( pCsr->nSegment==0 );
  3287   3304       for(i=0; rc==SQLITE_OK && sqlite3_step(pStmt)==SQLITE_ROW && i<nSeg; i++){
  3288   3305         rc = sqlite3Fts3SegReaderNew(i, 0,
  3289   3306             sqlite3_column_int64(pStmt, 1),        /* segdir.start_block */
  3290   3307             sqlite3_column_int64(pStmt, 2),        /* segdir.leaves_end_block */
  3291   3308             sqlite3_column_int64(pStmt, 3),        /* segdir.end_block */
  3292   3309             sqlite3_column_blob(pStmt, 4),         /* segdir.root */
  3293   3310             sqlite3_column_bytes(pStmt, 4),        /* segdir.root */
  3294   3311             &pCsr->apSegment[i]
  3295   3312         );
         3313  +      pCsr->nSegment++;
  3296   3314       }
  3297   3315       rc2 = sqlite3_reset(pStmt);
  3298   3316       if( rc==SQLITE_OK ) rc = rc2;
  3299   3317     }
  3300   3318   
  3301   3319     return rc;
  3302   3320   }
................................................................................
  3965   3983   
  3966   3984       rc2 = sqlite3_reset(pSelect);
  3967   3985       if( rc==SQLITE_OK ) rc = rc2;
  3968   3986     }
  3969   3987   
  3970   3988     return rc;
  3971   3989   }
         3990  +
         3991  +/*
         3992  +** Determine the largest segment index value that exists within absolute
         3993  +** level iAbsLevel+1. If no error occurs, set *piIdx to this value plus
         3994  +** one before returning SQLITE_OK. Or, if there are no segments at all 
         3995  +** within level iAbsLevel, set *piIdx to zero.
         3996  +**
         3997  +** If an error occurs, return an SQLite error code. The final value of
         3998  +** *piIdx is undefined in this case.
         3999  +*/
         4000  +static int fts3IncrmergeOutputIdx( 
         4001  +  Fts3Table *p,                   /* FTS Table handle */
         4002  +  sqlite3_int64 iAbsLevel,        /* Absolute index of input segments */
         4003  +  int *piIdx                      /* OUT: Next free index at iAbsLevel+1 */
         4004  +){
         4005  +  int rc;
         4006  +  sqlite3_stmt *pOutputIdx = 0;   /* SQL used to find output index */
         4007  +
         4008  +  rc = fts3SqlStmt(p, SQL_NEXT_SEGMENT_INDEX, &pOutputIdx, 0);
         4009  +  if( rc==SQLITE_OK ){
         4010  +    sqlite3_bind_int64(pOutputIdx, 1, iAbsLevel+1);
         4011  +    sqlite3_step(pOutputIdx);
         4012  +    *piIdx = sqlite3_column_int(pOutputIdx, 0);
         4013  +    rc = sqlite3_reset(pOutputIdx);
         4014  +  }
         4015  +
         4016  +  return rc;
         4017  +}
  3972   4018   
  3973   4019   /* 
  3974         -** Either allocate an output segment or locate an existing appendable 
  3975         -** output segment to append to. An "appendable" output segment is
  3976         -** slightly different to a normal one, as the required range of keys in
  3977         -** the %_segments table must be allocated up front.
         4020  +** Allocate an appendable output segment on absolute level iAbsLevel+1
         4021  +** with idx value iIdx.
  3978   4022   **
  3979   4023   ** In the %_segdir table, a segment is defined by the values in three
  3980   4024   ** columns:
  3981   4025   **
  3982   4026   **     start_block
  3983   4027   **     leaves_end_block
  3984   4028   **     end_block
................................................................................
  3997   4041   **
  3998   4042   ** In the actual code below, the value "16" is replaced with the 
  3999   4043   ** pre-processor macro FTS_MAX_APPENDABLE_HEIGHT.
  4000   4044   */
  4001   4045   static int fts3IncrmergeWriter( 
  4002   4046     Fts3Table *p,                   /* Fts3 table handle */
  4003   4047     sqlite3_int64 iAbsLevel,        /* Absolute level of input segments */
         4048  +  int iIdx,                       /* Index of new output segment */
  4004   4049     Fts3MultiSegReader *pCsr,       /* Cursor that data will be read from */
  4005   4050     IncrmergeWriter *pWriter        /* Populate this object */
  4006   4051   ){
  4007   4052     int rc;                         /* Return Code */
  4008   4053     int i;                          /* Iterator variable */
  4009   4054     int nLeafEst;                   /* Blocks allocated for leaf nodes */
  4010         -  int iIdx;                       /* Index of output segment */
  4011   4055     sqlite3_stmt *pLeafEst = 0;     /* SQL used to determine nLeafEst */
  4012   4056     sqlite3_stmt *pFirstBlock = 0;  /* SQL used to determine first block */
  4013         -  sqlite3_stmt *pOutputIdx = 0;   /* SQL used to find output index */
  4014         -  const char *zKey = pCsr->zTerm; /* First key to be appended to output */
  4015         -  int nKey = pCsr->nTerm;         /* Size of zKey in bytes */
  4016         -
  4017         -  rc = fts3SqlStmt(p, SQL_NEXT_SEGMENT_INDEX, &pOutputIdx, 0);
  4018         -  if( rc==SQLITE_OK ){
  4019         -    sqlite3_bind_int64(pOutputIdx, 1, iAbsLevel+1);
  4020         -    sqlite3_step(pOutputIdx);
  4021         -    iIdx = sqlite3_column_int(pOutputIdx, 0) - 1;
  4022         -    rc = sqlite3_reset(pOutputIdx);
  4023         -  }
  4024         -  if( rc!=SQLITE_OK ) return rc;
  4025         -
  4026         -  assert( zKey );
  4027         -  assert( pWriter->nLeafEst==0 );
  4028         -  rc = fts3IncrmergeLoad(p, iAbsLevel, iIdx, zKey, nKey, pWriter);
  4029         -  if( rc!=SQLITE_OK || pWriter->nLeafEst ) return rc;
  4030         -  iIdx++;
  4031   4057   
  4032   4058     /* Calculate nLeafEst. */
  4033   4059     rc = fts3SqlStmt(p, SQL_MAX_LEAF_NODE_ESTIMATE, &pLeafEst, 0);
  4034   4060     if( rc==SQLITE_OK ){
  4035   4061       sqlite3_bind_int64(pLeafEst, 1, iAbsLevel);
  4036   4062       sqlite3_bind_int64(pLeafEst, 2, pCsr->nSegment);
  4037   4063       if( SQLITE_ROW==sqlite3_step(pLeafEst) ){
................................................................................
  4186   4212   ** SQLite error code otherwise.
  4187   4213   */
  4188   4214   static int fts3TruncateSegment(
  4189   4215     Fts3Table *p,                   /* FTS3 table handle */
  4190   4216     sqlite3_int64 iAbsLevel,        /* Absolute level of segment to modify */
  4191   4217     int iIdx,                       /* Index within level of segment to modify */
  4192   4218     const char *zTerm,              /* Remove terms smaller than this */
  4193         -  int nTerm                       /* Number of bytes in buffer zTerm */
         4219  +  int nTerm                      /* Number of bytes in buffer zTerm */
  4194   4220   ){
  4195   4221     int rc = SQLITE_OK;             /* Return code */
  4196   4222     Blob root = {0,0,0};            /* New root page image */
  4197   4223     Blob block = {0,0,0};           /* Buffer used for any other block */
  4198   4224     sqlite3_int64 iBlock = 0;       /* Block id */
  4199   4225     sqlite3_int64 iNewStart = 0;    /* New value for iStartBlock */
  4200   4226     sqlite3_int64 iOldStart = 0;    /* Old value for iStartBlock */
  4201         -  int rc2;                        /* sqlite3_reset() return code */
  4202   4227     sqlite3_stmt *pFetch = 0;       /* Statement used to fetch segdir */
  4203   4228   
  4204         -  assert( p->aStmt[SQL_SELECT_SEGDIR] );
  4205         -  pFetch = p->aStmt[SQL_SELECT_SEGDIR];
  4206         -
  4207         -  sqlite3_bind_int64(pFetch, 1, iAbsLevel);
  4208         -  sqlite3_bind_int(pFetch, 2, iIdx);
  4209         -  if( SQLITE_ROW==sqlite3_step(pFetch) ){
  4210         -    const char *aRoot = sqlite3_column_blob(pFetch, 4);
  4211         -    int nRoot = sqlite3_column_bytes(pFetch, 4);
  4212         -    iOldStart = sqlite3_column_int64(pFetch, 1);
  4213         -    rc = fts3TruncateNode(aRoot, nRoot, &root, zTerm, nTerm, &iBlock);
         4229  +  rc = fts3SqlStmt(p, SQL_SELECT_SEGDIR, &pFetch, 0);
         4230  +  if( rc==SQLITE_OK ){
         4231  +    int rc2;                      /* sqlite3_reset() return code */
         4232  +    sqlite3_bind_int64(pFetch, 1, iAbsLevel);
         4233  +    sqlite3_bind_int(pFetch, 2, iIdx);
         4234  +    if( SQLITE_ROW==sqlite3_step(pFetch) ){
         4235  +      const char *aRoot = sqlite3_column_blob(pFetch, 4);
         4236  +      int nRoot = sqlite3_column_bytes(pFetch, 4);
         4237  +      iOldStart = sqlite3_column_int64(pFetch, 1);
         4238  +      rc = fts3TruncateNode(aRoot, nRoot, &root, zTerm, nTerm, &iBlock);
         4239  +    }
         4240  +    rc2 = sqlite3_reset(pFetch);
         4241  +    if( rc==SQLITE_OK ) rc = rc2;
  4214   4242     }
  4215         -  rc2 = sqlite3_reset(pFetch);
  4216         -  if( rc==SQLITE_OK ) rc = rc2;
  4217   4243   
  4218   4244     while( rc==SQLITE_OK && iBlock ){
  4219   4245       char *aBlock = 0;
  4220   4246       int nBlock = 0;
  4221   4247       iNewStart = iBlock;
  4222   4248   
  4223   4249       rc = sqlite3Fts3ReadBlock(p, iBlock, &aBlock, &nBlock, 0);
................................................................................
  4269   4295   ** its data was copied to the output segment by the incrmerge operation)
  4270   4296   ** or modified in place so that it no longer contains those entries that
  4271   4297   ** have been duplicated in the output segment.
  4272   4298   */
  4273   4299   static int fts3IncrmergeChomp(
  4274   4300     Fts3Table *p,                   /* FTS table handle */
  4275   4301     sqlite3_int64 iAbsLevel,        /* Absolute level containing segments */
  4276         -  Fts3MultiSegReader *pCsr        /* Chomp all segments opened by this cursor */
         4302  +  Fts3MultiSegReader *pCsr,       /* Chomp all segments opened by this cursor */
         4303  +  int *pnRem                      /* Number of segments not deleted */
  4277   4304   ){
  4278   4305     int i;
         4306  +  int nRem = 0;
  4279   4307     int rc = SQLITE_OK;
  4280   4308   
  4281   4309     for(i=pCsr->nSegment-1; i>=0 && rc==SQLITE_OK; i--){
  4282   4310       Fts3SegReader *pSeg = 0;
  4283   4311       int j;
  4284   4312   
  4285   4313       /* Find the Fts3SegReader object with Fts3SegReader.iIdx==i. It is hiding
................................................................................
  4292   4320   
  4293   4321       if( pSeg->aNode==0 ){
  4294   4322         /* Seg-reader is at EOF. Remove the entire input segment. */
  4295   4323         rc = fts3DeleteSegment(p, pSeg);
  4296   4324         if( rc==SQLITE_OK ){
  4297   4325           rc = fts3RemoveSegdirEntry(p, iAbsLevel, pSeg->iIdx);
  4298   4326         }
         4327  +      *pnRem = 0;
  4299   4328       }else{
  4300   4329         /* The incremental merge did not copy all the data from this 
  4301   4330         ** segment to the upper level. The segment is modified in place
  4302   4331         ** so that it contains no keys smaller than zTerm/nTerm. */ 
  4303   4332         const char *zTerm = pSeg->zTerm;
  4304   4333         int nTerm = pSeg->nTerm;
  4305   4334         rc = fts3TruncateSegment(p, iAbsLevel, pSeg->iIdx, zTerm, nTerm);
         4335  +      nRem++;
  4306   4336       }
  4307   4337     }
         4338  +
         4339  +  *pnRem = nRem;
         4340  +  return rc;
         4341  +}
         4342  +
         4343  +/*
         4344  +** Store an incr-merge hint in the database.
         4345  +*/
         4346  +static int fts3IncrmergeHintStore(
         4347  +  Fts3Table *p,                   /* FTS3 table handle */
         4348  +  sqlite3_int64 iAbsLevel,        /* Absolute level to read input data from */
         4349  +  int nMerge                      /* Number of segments to merge */
         4350  +){
         4351  +  char aBlob[FTS3_VARINT_MAX * 2];
         4352  +  int nBlob = 0;
         4353  +  int rc;
         4354  +  sqlite3_stmt *pReplace = 0;
         4355  +
         4356  +  assert( p->bHasStat );
         4357  +  nBlob += sqlite3Fts3PutVarint(&aBlob[nBlob], iAbsLevel);
         4358  +  nBlob += sqlite3Fts3PutVarint(&aBlob[nBlob], nMerge);
         4359  +
         4360  +  rc = fts3SqlStmt(p, SQL_REPLACE_STAT, &pReplace, 0);
         4361  +  if( rc==SQLITE_OK ){
         4362  +    sqlite3_bind_int(pReplace, 1, FTS_STAT_INCRMERGEHINT);
         4363  +    sqlite3_bind_blob(pReplace, 2, aBlob, nBlob, SQLITE_TRANSIENT);
         4364  +    sqlite3_step(pReplace);
         4365  +    rc = sqlite3_reset(pReplace);
         4366  +  }
         4367  +
         4368  +  return rc;
         4369  +}
         4370  +
         4371  +/*
         4372  +** Load an incr-merge hint from the database.
         4373  +**
         4374  +** The incr-merge hint, if one exists, is stored in the rowid==1 row of
         4375  +** the %_stat table.
         4376  +*/
         4377  +static int fts3IncrmergeHintLoad(
         4378  +  Fts3Table *p,                   /* FTS3 table handle */
         4379  +  sqlite3_int64 *piAbsLevel,      /* Absolute level to read input data from */
         4380  +  int *pnMerge                    /* Number of segments to merge */
         4381  +){
         4382  +  sqlite3_stmt *pSelect = 0;
         4383  +  int rc;
         4384  +
         4385  +  *pnMerge = 0;
         4386  +  *piAbsLevel = 0;
         4387  +
         4388  +  rc = fts3SqlStmt(p, SQL_SELECT_STAT, &pSelect, 0);
         4389  +  if( rc==SQLITE_OK ){
         4390  +    sqlite3_bind_int(pSelect, 1, FTS_STAT_INCRMERGEHINT);
         4391  +    if( SQLITE_ROW==sqlite3_step(pSelect) ){
         4392  +      char *aHint = sqlite3_column_blob(pSelect, 0);
         4393  +      int nHint = sqlite3_column_bytes(pSelect, 0);
         4394  +      if( aHint ){
         4395  +        int i;
         4396  +        char aBlob[FTS3_VARINT_MAX * 2];
         4397  +        memcpy(aBlob, aHint, MAX(sizeof(aBlob), nHint));
         4398  +        i = sqlite3Fts3GetVarint(aBlob, piAbsLevel);
         4399  +        sqlite3Fts3GetVarint32(&aBlob[i], pnMerge);
         4400  +      }
         4401  +    }
         4402  +    rc = sqlite3_reset(pSelect);
         4403  +  }
  4308   4404   
  4309   4405     return rc;
  4310   4406   }
  4311   4407   
  4312   4408   /*
  4313   4409   ** Attempt an incremental merge that writes nMerge leaf blocks.
  4314   4410   **
................................................................................
  4315   4411   ** Incremental merges happen nMin segments at a time. The two
  4316   4412   ** segments to be merged are the nMin oldest segments (the ones with
  4317   4413   ** the smallest indexes) in the highest level that contains at least
  4318   4414   ** nMin segments. Multiple merges might occur in an attempt to write the 
  4319   4415   ** quota of nMerge leaf blocks.
  4320   4416   */
  4321   4417   static int fts3Incrmerge(Fts3Table *p, int nMerge, int nMin){
  4322         -  int rc = SQLITE_OK;             /* Return code */
         4418  +  int rc;                         /* Return code */
  4323   4419     int nRem = nMerge;              /* Number of leaf pages yet to  be written */
         4420  +  int bUseHint = 1;               /* True if hint has not yet been attempted */
         4421  +  sqlite3_int64 iHintAbsLevel = 0;/* Hint level */
         4422  +  int nHintSeg = 0;               /* Hint number of segments */
         4423  +  int nSeg = 0;                   /* Number of input segments */
         4424  +  sqlite3_int64 iAbsLevel = 0;    /* Absolute level number to work on */
  4324   4425   
  4325   4426     assert( nMin>=2 );
         4427  +
         4428  +  rc = fts3IncrmergeHintLoad(p, &iHintAbsLevel, &nHintSeg);
         4429  +  if( nHintSeg==0 ) bUseHint = 0;
  4326   4430   
  4327   4431     while( rc==SQLITE_OK && nRem>0 ){
  4328         -    sqlite3_int64 iAbsLevel;        /* Absolute level number to work on */
  4329         -    sqlite3_stmt *pFindLevel = 0;   /* SQL used to determine iAbsLevel */
  4330   4432       Fts3MultiSegReader *pCsr;       /* Cursor used to read input data */
  4331   4433       Fts3SegFilter *pFilter;         /* Filter used with cursor pCsr */
  4332   4434       IncrmergeWriter *pWriter;       /* Writer object */
  4333   4435       const int nAlloc = sizeof(*pCsr) + sizeof(*pFilter) + sizeof(*pWriter);
  4334   4436   
  4335         -    /* Determine which level to merge segments from. Any level, from any
  4336         -    ** prefix or language index may be selected. Stack variable iAbsLevel 
  4337         -    ** is set to the absolute level number of the level to merge from.  */
  4338         -    rc = fts3SqlStmt(p, SQL_FIND_MERGE_LEVEL, &pFindLevel, 0);
  4339         -    sqlite3_bind_int(pFindLevel, 1, nMin);
  4340         -    if( sqlite3_step(pFindLevel)!=SQLITE_ROW ){
  4341         -      /* There are no levels with nMin or more segments. Or an error has
  4342         -      ** occurred. Either way, exit early.  */
  4343         -      return sqlite3_reset(pFindLevel);
         4437  +    if( bUseHint ){
         4438  +      iAbsLevel = iHintAbsLevel;
         4439  +      nSeg = nHintSeg;
         4440  +    }else{
         4441  +      sqlite3_stmt *pFindLevel = 0; /* SQL used to determine iAbsLevel */
         4442  +
         4443  +      /* Determine which level to merge segments from. Any level, from any
         4444  +      ** prefix or language index may be selected. Stack variable iAbsLevel 
         4445  +      ** is set to the absolute level number of the level to merge from.  */
         4446  +      rc = fts3SqlStmt(p, SQL_FIND_MERGE_LEVEL, &pFindLevel, 0);
         4447  +      sqlite3_bind_int(pFindLevel, 1, nMin);
         4448  +      if( sqlite3_step(pFindLevel)!=SQLITE_ROW ){
         4449  +        /* There are no levels with nMin or more segments. Or an error has
         4450  +         ** occurred. Either way, exit early.  */
         4451  +        rc = sqlite3_reset(pFindLevel);
         4452  +        iAbsLevel = 0;
         4453  +        nSeg = 0;
         4454  +        break;
         4455  +      }
         4456  +      iAbsLevel = sqlite3_column_int64(pFindLevel, 0);
         4457  +      nSeg = nMin;
         4458  +      sqlite3_reset(pFindLevel);
  4344   4459       }
  4345         -    iAbsLevel = sqlite3_column_int64(pFindLevel, 0);
  4346         -    sqlite3_reset(pFindLevel);
  4347   4460   
  4348   4461       /* Allocate space for the cursor, filter and writer objects */
  4349   4462       pWriter = (IncrmergeWriter *)sqlite3_malloc(nAlloc);
  4350   4463       if( !pWriter ) return SQLITE_NOMEM;
  4351   4464       memset(pWriter, 0, nAlloc);
  4352   4465       pFilter = (Fts3SegFilter *)&pWriter[1];
  4353   4466       pCsr = (Fts3MultiSegReader *)&pFilter[1];
  4354   4467   
  4355         -    /* Open a cursor to iterate through the contents of indexes 0 and 1 of
  4356         -    ** the selected absolute level. */
         4468  +    /* Open a cursor to iterate through the contents of the oldest nSeg 
         4469  +    ** indexes of absolute level iAbsLevel. If this cursor is opened using 
         4470  +    ** the 'hint' parameters, it is possible that there are less than nSeg
         4471  +    ** segments available in level iAbsLevel. In this case, no work is
         4472  +    ** done on iAbsLevel - fall through to the next iteration of the loop 
         4473  +    ** to start work on some other level.  */
  4357   4474       pFilter->flags = FTS3_SEGMENT_REQUIRE_POS;
  4358         -    rc = fts3IncrmergeCsr(p, iAbsLevel, nMin, pCsr);
  4359         -    fts3LogMerge(nMin, iAbsLevel);
  4360         -    if( rc==SQLITE_OK ){
  4361         -      rc = sqlite3Fts3SegReaderStart(p, pCsr, pFilter);
  4362         -    }
  4363         -    if( rc==SQLITE_OK ){
  4364         -      if( SQLITE_ROW==(rc = sqlite3Fts3SegReaderStep(p, pCsr)) ){
  4365         -        rc = fts3IncrmergeWriter(p, iAbsLevel, pCsr, pWriter);
         4475  +    rc = fts3IncrmergeCsr(p, iAbsLevel, nSeg, pCsr);
         4476  +    if( pCsr->nSegment==nSeg && SQLITE_OK==rc
         4477  +     && SQLITE_OK ==(rc = sqlite3Fts3SegReaderStart(p, pCsr, pFilter))
         4478  +     && SQLITE_ROW==(rc = sqlite3Fts3SegReaderStep(p, pCsr))
         4479  +    ){
         4480  +      int iIdx = 0;               /* Largest idx in level (iAbsLevel+1) */
         4481  +      rc = fts3IncrmergeOutputIdx(p, iAbsLevel, &iIdx);
         4482  +      if( rc==SQLITE_OK ){
         4483  +        if( bUseHint && iIdx>0 ){
         4484  +          const char *zKey = pCsr->zTerm;
         4485  +          int nKey = pCsr->nTerm;
         4486  +          rc = fts3IncrmergeLoad(p, iAbsLevel, iIdx-1, zKey, nKey, pWriter);
         4487  +        }else{
         4488  +          rc = fts3IncrmergeWriter(p, iAbsLevel, iIdx, pCsr, pWriter);
         4489  +        }
         4490  +      }
         4491  +
         4492  +      if( rc==SQLITE_OK && pWriter->nLeafEst ){
         4493  +        fts3LogMerge(nSeg, iAbsLevel);
         4494  +        do {
         4495  +          rc = fts3IncrmergeAppend(p, pWriter, pCsr);
         4496  +          if( rc==SQLITE_OK ) rc = sqlite3Fts3SegReaderStep(p, pCsr);
         4497  +          if( pWriter->nWork>=nRem && rc==SQLITE_ROW ) rc = SQLITE_OK;
         4498  +        }while( rc==SQLITE_ROW );
         4499  +
         4500  +        /* Update or delete the input segments */
  4366   4501           if( rc==SQLITE_OK ){
  4367         -          do {
  4368         -            rc = fts3IncrmergeAppend(p, pWriter, pCsr);
  4369         -            if( rc==SQLITE_OK ) rc = sqlite3Fts3SegReaderStep(p, pCsr);
  4370         -            if( pWriter->nWork>=nRem && rc==SQLITE_ROW ) rc = SQLITE_OK;
  4371         -          }while( rc==SQLITE_ROW );
         4502  +          nRem -= (1 + pWriter->nWork);
         4503  +          rc = fts3IncrmergeChomp(p, iAbsLevel, pCsr, &nSeg);
  4372   4504           }
  4373   4505         }
  4374         -    }
  4375         -    fts3IncrmergeRelease(p, pWriter, &rc);
  4376         -    nRem -= (1 + pWriter->nWork);
  4377   4506   
  4378         -    /* Update or delete the input segments */
  4379         -    if( rc==SQLITE_OK ){
  4380         -      rc = fts3IncrmergeChomp(p, iAbsLevel, pCsr);
         4507  +      fts3IncrmergeRelease(p, pWriter, &rc);
  4381   4508       }
  4382   4509   
  4383   4510       sqlite3Fts3SegReaderFinish(pCsr);
  4384   4511       sqlite3_free(pWriter);
         4512  +    bUseHint = 0;
         4513  +  }
         4514  +
         4515  +  /* Write the hint values into the %_stat table for the next incr-merger */
         4516  +  if( rc==SQLITE_OK && (iAbsLevel!=iHintAbsLevel || nHintSeg!=nSeg) ){
         4517  +    rc = fts3IncrmergeHintStore(p, iAbsLevel, nSeg);
  4385   4518     }
  4386   4519   
  4387   4520     return rc;
  4388   4521   }
  4389   4522   
  4390   4523   /*
  4391   4524   ** Process statements of the form:

Changes to test/fts4merge.test.

    59     59       SELECT docid FROM t1 WHERE t1 MATCH 'zero one two three'
    60     60     } {123 132 213 231 312 321}
    61     61   }
    62     62   
    63     63   do_execsql_test 1.5 { 
    64     64     SELECT level, group_concat(idx, ' ') FROM t1_segdir GROUP BY level 
    65     65   } {
    66         -  0 {0 1 2 3} 
    67         -  1 {0 1 2} 
    68         -  2 0
           66  +  2 {0 1}
    69     67     3 0
    70     68   }
    71     69   
    72     70   #-------------------------------------------------------------------------
    73     71   # Test cases 2.* test that errors in the xxx part of the 'merge=xxx' are
    74     72   # handled correctly.
    75     73   #
................................................................................
   110    108   }
   111    109   
   112    110   do_execsql_test 3.3 { 
   113    111     INSERT INTO t2(t2) VALUES('merge=1000000,2');
   114    112     SELECT level, group_concat(idx, ' ') FROM t2_segdir GROUP BY level 
   115    113   } {
   116    114     0 0 
   117         -  1 {0 1} 
   118         -  2 0 
   119         -  3 {0 1} 
   120         -  4 {0 1} 
   121         -  5 0
          115  +  2 0
          116  +  3 0 
          117  +  4 0
          118  +  6 0
          119  +}
          120  +
          121  +#-------------------------------------------------------------------------
          122  +# Test cases 4.*
          123  +#
          124  +reset_db
          125  +do_execsql_test 4.1 {
          126  +  PRAGMA page_size = 512;
          127  +  CREATE VIRTUAL TABLE t4 USING fts4;
          128  +  PRAGMA main.page_size;
          129  +} {512}
          130  +
          131  +do_test 4.2 {
          132  +  foreach x {a c b d e f g h i j k l m n o p} {
          133  +    execsql "INSERT INTO t4 VALUES('[string repeat $x 600]')"
          134  +  }
          135  +  execsql {SELECT level, group_concat(idx, ' ') FROM t4_segdir GROUP BY level}
          136  +} {0 {0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15}}
          137  +
          138  +foreach {tn expect} {
          139  +  1  "0 {0 1 2 3 4 5 6 7 8 9 10 11 12 13} 1 0"
          140  +  2  "0 {0 1 2 3 4 5 6 7 8 9 10 11 12}    1 0"
          141  +  3  "0 {0 1 2 3 4 5 6 7 8 9 10 11}       1 0"
          142  +  4  "0 {0 1 2 3 4 5 6 7 8 9 10}          1 0"
          143  +  5  "0 {0 1 2 3 4 5 6 7 8 9}             1 0"
          144  +  6  "0 {0 1 2 3 4 5 6 7 8}               1 0"
          145  +  7  "0 {0 1 2 3 4 5 6 7}                 1 0"
          146  +  8  "0 {0 1 2 3 4 5 6}                   1 0"
          147  +  9  "0 {0 1 2 3 4 5}                     1 0"
          148  +} {
          149  +  do_execsql_test 4.3.$tn {
          150  +    INSERT INTO t4(t4) VALUES('merge=1,16');
          151  +    SELECT level, group_concat(idx, ' ') FROM t4_segdir GROUP BY level;
          152  +  } $expect
   122    153   }
   123    154   
   124         -finish_test
          155  +do_execsql_test 4.4.1 {
          156  +  SELECT quote(value) FROM t4_stat WHERE rowid=1
          157  +} {X'0006'}
          158  +
          159  +do_execsql_test 4.4.2 {
          160  +  DELETE FROM t4_stat WHERE rowid=1;
          161  +  INSERT INTO t4(t4) VALUES('merge=1,12');
          162  +  SELECT level, group_concat(idx, ' ') FROM t4_segdir GROUP BY level;
          163  +} "0 {0 1 2 3 4 5}                     1 0"
          164  +
   125    165   
          166  +finish_test