/ Check-in [4d6de3e9]
Login

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

Overview
Comment:Merge fts4-incr-merge with trunk.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1:4d6de3e9bef3487f2d89167939ab2c42872d05b3
User & Date: dan 2012-03-29 15:11:32
Context
2012-03-30
00:00
Fix compiler warnings on GCC and MSVC and fix a C89-ism that broke the build for MSVC. check-in: b451c0f9 user: drh tags: trunk
2012-03-29
15:11
Merge fts4-incr-merge with trunk. check-in: 4d6de3e9 user: dan tags: trunk
14:29
Disable the LIKE optimization if the column on the left-hand-side of the LIKE operator belongs to a virtual table. check-in: 0bacb879 user: dan tags: trunk
2012-03-28
16:44
Merge in the latest changes from trunk. Closed-Leaf check-in: 66c4aaad user: drh tags: fts4-incr-merge
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to ext/fts3/fts3.c.

    66     66   **
    67     67   ** FTS3 used to optionally store character offsets using a compile-time
    68     68   ** option.  But that functionality is no longer supported.
    69     69   **
    70     70   ** A doclist is stored like this:
    71     71   **
    72     72   ** array {
    73         -**   varint docid;
           73  +**   varint docid;          (delta from previous doclist)
    74     74   **   array {                (position list for column 0)
    75     75   **     varint position;     (2 more than the delta from previous position)
    76     76   **   }
    77     77   **   array {
    78     78   **     varint POS_COLUMN;   (marks start of position list for new column)
    79     79   **     varint column;       (index of new column)
    80     80   **     array {
................................................................................
    97     97   **   value:     123 5 9 1 1 14 35 0 234 72 0
    98     98   **
    99     99   ** The 123 value is the first docid.  For column zero in this document
   100    100   ** there are two matches at positions 3 and 10 (5-2 and 9-2+3).  The 1
   101    101   ** at D signals the start of a new column; the 1 at E indicates that the
   102    102   ** new column is column number 1.  There are two positions at 12 and 45
   103    103   ** (14-2 and 35-2+12).  The 0 at H indicate the end-of-document.  The
   104         -** 234 at I is the next docid.  It has one position 72 (72-2) and then
   105         -** terminates with the 0 at K.
          104  +** 234 at I is the delta to next docid (357).  It has one position 70
          105  +** (72-2) and then terminates with the 0 at K.
   106    106   **
   107    107   ** A "position-list" is the list of positions for multiple columns for
   108    108   ** a single docid.  A "column-list" is the set of positions for a single
   109    109   ** column.  Hence, a position-list consists of one or more column-lists,
   110    110   ** a document record consists of a docid followed by a position-list and
   111    111   ** a doclist consists of one or more document records.
   112    112   **
................................................................................
   565    565       }
   566    566   
   567    567       sqlite3_free(zSql);
   568    568       sqlite3_free(zCols);
   569    569       *pRc = rc;
   570    570     }
   571    571   }
          572  +
          573  +/*
          574  +** Create the %_stat table if it does not already exist.
          575  +*/
          576  +void sqlite3Fts3CreateStatTable(int *pRc, Fts3Table *p){
          577  +  fts3DbExec(pRc, p->db, 
          578  +      "CREATE TABLE IF NOT EXISTS %Q.'%q_stat'"
          579  +          "(id INTEGER PRIMARY KEY, value BLOB);",
          580  +      p->zDb, p->zName
          581  +  );
          582  +  if( (*pRc)==SQLITE_OK ) p->bHasStat = 1;
          583  +}
   572    584   
   573    585   /*
   574    586   ** Create the backing store tables (%_content, %_segments and %_segdir)
   575    587   ** required by the FTS3 table passed as the only argument. This is done
   576    588   ** as part of the vtab xCreate() method.
   577    589   **
   578    590   ** If the p->bHasDocsize boolean is true (indicating that this is an
................................................................................
   626    638     );
   627    639     if( p->bHasDocsize ){
   628    640       fts3DbExec(&rc, db, 
   629    641           "CREATE TABLE %Q.'%q_docsize'(docid INTEGER PRIMARY KEY, size BLOB);",
   630    642           p->zDb, p->zName
   631    643       );
   632    644     }
          645  +  assert( p->bHasStat==p->bFts4 );
   633    646     if( p->bHasStat ){
   634         -    fts3DbExec(&rc, db, 
   635         -        "CREATE TABLE %Q.'%q_stat'(id INTEGER PRIMARY KEY, value BLOB);",
   636         -        p->zDb, p->zName
   637         -    );
          647  +    sqlite3Fts3CreateStatTable(&rc, p);
   638    648     }
   639    649     return rc;
   640    650   }
   641    651   
   642    652   /*
   643    653   ** Store the current database page-size in bytes in p->nPgsz.
   644    654   **
................................................................................
  1271   1281     p->nColumn = nCol;
  1272   1282     p->nPendingData = 0;
  1273   1283     p->azColumn = (char **)&p[1];
  1274   1284     p->pTokenizer = pTokenizer;
  1275   1285     p->nMaxPendingData = FTS3_MAX_PENDING_DATA;
  1276   1286     p->bHasDocsize = (isFts4 && bNoDocsize==0);
  1277   1287     p->bHasStat = isFts4;
         1288  +  p->bFts4 = isFts4;
  1278   1289     p->bDescIdx = bDescIdx;
         1290  +  p->bAutoincrmerge = 0xff;   /* 0xff means setting unknown */
  1279   1291     p->zContentTbl = zContent;
  1280   1292     p->zLanguageid = zLanguageid;
  1281   1293     zContent = 0;
  1282   1294     zLanguageid = 0;
  1283   1295     TESTONLY( p->inTransaction = -1 );
  1284   1296     TESTONLY( p->mxSavepoint = -1 );
  1285   1297   
................................................................................
  1323   1335   
  1324   1336     /* If this is an xCreate call, create the underlying tables in the 
  1325   1337     ** database. TODO: For xConnect(), it could verify that said tables exist.
  1326   1338     */
  1327   1339     if( isCreate ){
  1328   1340       rc = fts3CreateTables(p);
  1329   1341     }
         1342  +
         1343  +  /* Check to see if a legacy fts3 table has been "upgraded" by the
         1344  +  ** addition of a %_stat table so that it can use incremental merge.
         1345  +  */
         1346  +  if( !isFts4 && !isCreate ){
         1347  +    int rc2 = SQLITE_OK;
         1348  +    fts3DbExec(&rc2, db, "SELECT 1 FROM %Q.'%q_stat' WHERE id=2",
         1349  +               p->zDb, p->zName);
         1350  +    if( rc2==SQLITE_OK ) p->bHasStat = 1;
         1351  +  }
  1330   1352   
  1331   1353     /* Figure out the page-size for the database. This is required in order to
  1332   1354     ** estimate the cost of loading large doclists from the database.  */
  1333   1355     fts3DatabasePageSize(&rc, p);
  1334   1356     p->nNodeSize = p->nPgsz-35;
  1335   1357   
  1336   1358     /* Declare the table schema to SQLite. */
................................................................................
  2667   2689   
  2668   2690   /*
  2669   2691   ** Set up a cursor object for iterating through a full-text index or a 
  2670   2692   ** single level therein.
  2671   2693   */
  2672   2694   int sqlite3Fts3SegReaderCursor(
  2673   2695     Fts3Table *p,                   /* FTS3 table handle */
  2674         -  int iLangid,
         2696  +  int iLangid,                    /* Language-id to search */
  2675   2697     int iIndex,                     /* Index to search (from 0 to p->nIndex-1) */
  2676   2698     int iLevel,                     /* Level of segments to scan */
  2677   2699     const char *zTerm,              /* Term to query for */
  2678   2700     int nTerm,                      /* Size of zTerm in bytes */
  2679   2701     int isPrefix,                   /* True for a prefix search */
  2680   2702     int isScan,                     /* True to scan from zTerm to EOF */
  2681   2703     Fts3MultiSegReader *pCsr       /* Cursor object to populate */
................................................................................
  2685   2707         ||  iLevel==FTS3_SEGCURSOR_PENDING 
  2686   2708         ||  iLevel>=0
  2687   2709     );
  2688   2710     assert( iLevel<FTS3_SEGDIR_MAXLEVEL );
  2689   2711     assert( FTS3_SEGCURSOR_ALL<0 && FTS3_SEGCURSOR_PENDING<0 );
  2690   2712     assert( isPrefix==0 || isScan==0 );
  2691   2713   
  2692         -  /* "isScan" is only set to true by the ft4aux module, an ordinary
  2693         -  ** full-text tables. */
  2694         -  assert( isScan==0 || p->aIndex==0 );
  2695         -
  2696   2714     memset(pCsr, 0, sizeof(Fts3MultiSegReader));
  2697         -
  2698   2715     return fts3SegReaderCursor(
  2699   2716         p, iLangid, iIndex, iLevel, zTerm, nTerm, isPrefix, isScan, pCsr
  2700   2717     );
  2701   2718   }
  2702   2719   
  2703   2720   /*
  2704   2721   ** In addition to its current configuration, have the Fts3MultiSegReader
................................................................................
  2955   2972         return SQLITE_NOMEM;
  2956   2973       }
  2957   2974   
  2958   2975       pCsr->iLangid = 0;
  2959   2976       if( nVal==2 ) pCsr->iLangid = sqlite3_value_int(apVal[1]);
  2960   2977   
  2961   2978       rc = sqlite3Fts3ExprParse(p->pTokenizer, pCsr->iLangid,
  2962         -        p->azColumn, p->bHasStat, p->nColumn, iCol, zQuery, -1, &pCsr->pExpr
         2979  +        p->azColumn, p->bFts4, p->nColumn, iCol, zQuery, -1, &pCsr->pExpr
  2963   2980       );
  2964   2981       if( rc!=SQLITE_OK ){
  2965   2982         if( rc==SQLITE_ERROR ){
  2966   2983           static const char *zErr = "malformed MATCH expression: [%s]";
  2967   2984           p->base.zErrMsg = sqlite3_mprintf(zErr, zQuery);
  2968   2985         }
  2969   2986         return rc;
................................................................................
  3098   3115   }
  3099   3116   
  3100   3117   /*
  3101   3118   ** Implementation of xSync() method. Flush the contents of the pending-terms
  3102   3119   ** hash-table to the database.
  3103   3120   */
  3104   3121   static int fts3SyncMethod(sqlite3_vtab *pVtab){
  3105         -  int rc = sqlite3Fts3PendingTermsFlush((Fts3Table *)pVtab);
  3106         -  sqlite3Fts3SegmentsClose((Fts3Table *)pVtab);
         3122  +
         3123  +  /* Following an incremental-merge operation, assuming that the input
         3124  +  ** segments are not completely consumed (the usual case), they are updated
         3125  +  ** in place to remove the entries that have already been merged. This
         3126  +  ** involves updating the leaf block that contains the smallest unmerged
         3127  +  ** entry and each block (if any) between the leaf and the root node. So
         3128  +  ** if the height of the input segment b-trees is N, and input segments
         3129  +  ** are merged eight at a time, updating the input segments at the end
         3130  +  ** of an incremental-merge requires writing (8*(1+N)) blocks. N is usually
         3131  +  ** small - often between 0 and 2. So the overhead of the incremental
         3132  +  ** merge is somewhere between 8 and 24 blocks. To avoid this overhead
         3133  +  ** dwarfing the actual productive work accomplished, the incremental merge
         3134  +  ** is only attempted if it will write at least 64 leaf blocks. Hence
         3135  +  ** nMinMerge.
         3136  +  **
         3137  +  ** Of course, updating the input segments also involves deleting a bunch
         3138  +  ** of blocks from the segments table. But this is not considered overhead
         3139  +  ** as it would also be required by a crisis-merge that used the same input 
         3140  +  ** segments.
         3141  +  */
         3142  +  const int nMinMerge = 64;       /* Minimum amount of incr-merge work to do */
         3143  +
         3144  +  Fts3Table *p = (Fts3Table*)pVtab;
         3145  +  int rc = sqlite3Fts3PendingTermsFlush(p);
         3146  +
         3147  +  if( rc==SQLITE_OK && p->bAutoincrmerge==1 && p->nLeafAdd>(nMinMerge/16) ){
         3148  +    int mxLevel = 0;              /* Maximum relative level value in db */
         3149  +    int A;                        /* Incr-merge parameter A */
         3150  +
         3151  +    rc = sqlite3Fts3MaxLevel(p, &mxLevel);
         3152  +    assert( rc==SQLITE_OK || mxLevel==0 );
         3153  +    A = p->nLeafAdd * mxLevel;
         3154  +    A += (A/2);
         3155  +    if( A>nMinMerge ) rc = sqlite3Fts3Incrmerge(p, A, 8);
         3156  +  }
         3157  +  sqlite3Fts3SegmentsClose(p);
  3107   3158     return rc;
  3108   3159   }
  3109   3160   
  3110   3161   /*
  3111   3162   ** Implementation of xBegin() method. This is a no-op.
  3112   3163   */
  3113   3164   static int fts3BeginMethod(sqlite3_vtab *pVtab){
  3114         -  TESTONLY( Fts3Table *p = (Fts3Table*)pVtab );
         3165  +  Fts3Table *p = (Fts3Table*)pVtab;
  3115   3166     UNUSED_PARAMETER(pVtab);
  3116   3167     assert( p->pSegments==0 );
  3117   3168     assert( p->nPendingData==0 );
  3118   3169     assert( p->inTransaction!=1 );
  3119   3170     TESTONLY( p->inTransaction = 1 );
  3120   3171     TESTONLY( p->mxSavepoint = -1; );
         3172  +  p->nLeafAdd = 0;
  3121   3173     return SQLITE_OK;
  3122   3174   }
  3123   3175   
  3124   3176   /*
  3125   3177   ** Implementation of xCommit() method. This is a no-op. The contents of
  3126   3178   ** the pending-terms hash-table have already been flushed into the database
  3127   3179   ** by fts3SyncMethod().
................................................................................
  3408   3460   
  3409   3461   /*
  3410   3462   ** The xSavepoint() method.
  3411   3463   **
  3412   3464   ** Flush the contents of the pending-terms table to disk.
  3413   3465   */
  3414   3466   static int fts3SavepointMethod(sqlite3_vtab *pVtab, int iSavepoint){
         3467  +  int rc = SQLITE_OK;
  3415   3468     UNUSED_PARAMETER(iSavepoint);
  3416   3469     assert( ((Fts3Table *)pVtab)->inTransaction );
  3417   3470     assert( ((Fts3Table *)pVtab)->mxSavepoint < iSavepoint );
  3418   3471     TESTONLY( ((Fts3Table *)pVtab)->mxSavepoint = iSavepoint );
  3419         -  return fts3SyncMethod(pVtab);
         3472  +  if( ((Fts3Table *)pVtab)->bIgnoreSavepoint==0 ){
         3473  +    rc = fts3SyncMethod(pVtab);
         3474  +  }
         3475  +  return rc;
  3420   3476   }
  3421   3477   
  3422   3478   /*
  3423   3479   ** The xRelease() method.
  3424   3480   **
  3425   3481   ** This is a no-op.
  3426   3482   */
................................................................................
  4327   4383     int nToken = 0;
  4328   4384     int nOr = 0;
  4329   4385   
  4330   4386     /* Allocate a MultiSegReader for each token in the expression. */
  4331   4387     fts3EvalAllocateReaders(pCsr, pCsr->pExpr, &nToken, &nOr, &rc);
  4332   4388   
  4333   4389     /* Determine which, if any, tokens in the expression should be deferred. */
  4334         -  if( rc==SQLITE_OK && nToken>1 && pTab->bHasStat ){
         4390  +  if( rc==SQLITE_OK && nToken>1 && pTab->bFts4 ){
  4335   4391       Fts3TokenAndCost *aTC;
  4336   4392       Fts3Expr **apOr;
  4337   4393       aTC = (Fts3TokenAndCost *)sqlite3_malloc(
  4338   4394           sizeof(Fts3TokenAndCost) * nToken
  4339   4395         + sizeof(Fts3Expr *) * nOr * 2
  4340   4396       );
  4341   4397       apOr = (Fts3Expr **)&aTC[nToken];
................................................................................
  5142   5198       memset(&pPhrase->doclist, 0, sizeof(Fts3Doclist));
  5143   5199       for(i=0; i<pPhrase->nToken; i++){
  5144   5200         fts3SegReaderCursorFree(pPhrase->aToken[i].pSegcsr);
  5145   5201         pPhrase->aToken[i].pSegcsr = 0;
  5146   5202       }
  5147   5203     }
  5148   5204   }
         5205  +
  5149   5206   
  5150   5207   /*
  5151   5208   ** Return SQLITE_CORRUPT_VTAB.
  5152   5209   */
  5153   5210   #ifdef SQLITE_DEBUG
  5154   5211   int sqlite3Fts3Corrupt(){
  5155   5212     return SQLITE_CORRUPT_VTAB;

Changes to ext/fts3/fts3Int.h.

    63     63   */
    64     64   #define SizeofArray(X) ((int)(sizeof(X)/sizeof(X[0])))
    65     65   
    66     66   
    67     67   #ifndef MIN
    68     68   # define MIN(x,y) ((x)<(y)?(x):(y))
    69     69   #endif
           70  +#ifndef MAX
           71  +# define MAX(x,y) ((x)>(y)?(x):(y))
           72  +#endif
    70     73   
    71     74   /*
    72     75   ** Maximum length of a varint encoded integer. The varint format is different
    73     76   ** from that used by SQLite, so the maximum length is 10, not 9.
    74     77   */
    75     78   #define FTS3_VARINT_MAX 10
    76     79   
................................................................................
   117    120   ** false.
   118    121   */
   119    122   #ifdef SQLITE_COVERAGE_TEST
   120    123   # define ALWAYS(x) (1)
   121    124   # define NEVER(X)  (0)
   122    125   #else
   123    126   # define ALWAYS(x) (x)
   124         -# define NEVER(X)  (x)
          127  +# define NEVER(x)  (x)
   125    128   #endif
   126    129   
   127    130   /*
   128    131   ** Internal types used by SQLite.
   129    132   */
   130    133   typedef unsigned char u8;         /* 1-byte (or larger) unsigned integer */
   131    134   typedef short int i16;            /* 2-byte (or larger) signed integer */
   132    135   typedef unsigned int u32;         /* 4-byte unsigned integer */
   133    136   typedef sqlite3_uint64 u64;       /* 8-byte unsigned integer */
          137  +typedef sqlite3_int64 i64;        /* 8-byte signed integer */
   134    138   
   135    139   /*
   136    140   ** Macro used to suppress compiler warnings for unused parameters.
   137    141   */
   138    142   #define UNUSED_PARAMETER(x) (void)(x)
   139    143   
   140    144   /*
................................................................................
   189    193     const char *zDb;                /* logical database name */
   190    194     const char *zName;              /* virtual table name */
   191    195     int nColumn;                    /* number of named columns in virtual table */
   192    196     char **azColumn;                /* column names.  malloced */
   193    197     sqlite3_tokenizer *pTokenizer;  /* tokenizer for inserts and queries */
   194    198     char *zContentTbl;              /* content=xxx option, or NULL */
   195    199     char *zLanguageid;              /* languageid=xxx option, or NULL */
          200  +  u8 bAutoincrmerge;              /* True if automerge=1 */
          201  +  u32 nLeafAdd;                   /* Number of leaf blocks added this trans */
   196    202   
   197    203     /* Precompiled statements used by the implementation. Each of these 
   198    204     ** statements is run and reset within a single virtual table API call. 
   199    205     */
   200         -  sqlite3_stmt *aStmt[28];
          206  +  sqlite3_stmt *aStmt[37];
   201    207   
   202    208     char *zReadExprlist;
   203    209     char *zWriteExprlist;
   204    210   
   205    211     int nNodeSize;                  /* Soft limit for node size */
          212  +  u8 bFts4;                       /* True for FTS4, false for FTS3 */
   206    213     u8 bHasStat;                    /* True if %_stat table exists */
   207    214     u8 bHasDocsize;                 /* True if %_docsize table exists */
   208    215     u8 bDescIdx;                    /* True if doclists are in reverse order */
          216  +  u8 bIgnoreSavepoint;            /* True to ignore xSavepoint invocations */
   209    217     int nPgsz;                      /* Page size for host database */
   210    218     char *zSegmentsTbl;             /* Name of %_segments table */
   211    219     sqlite3_blob *pSegments;        /* Blob handle open on %_segments table */
   212    220   
   213         -  /* TODO: Fix the first paragraph of this comment.
   214         -  **
          221  +  /* 
   215    222     ** The following array of hash tables is used to buffer pending index 
   216         -  ** updates during transactions. Variable nPendingData estimates the memory 
   217         -  ** size of the pending data, including hash table overhead, not including
   218         -  ** malloc overhead.  When nPendingData exceeds nMaxPendingData, the buffer 
   219         -  ** is flushed automatically. Variable iPrevDocid is the docid of the most 
   220         -  ** recently inserted record.
          223  +  ** updates during transactions. All pending updates buffered at any one
          224  +  ** time must share a common language-id (see the FTS4 langid= feature).
          225  +  ** The current language id is stored in variable iPrevLangid.
   221    226     **
   222    227     ** A single FTS4 table may have multiple full-text indexes. For each index
   223    228     ** there is an entry in the aIndex[] array. Index 0 is an index of all the
   224    229     ** terms that appear in the document set. Each subsequent index in aIndex[]
   225    230     ** is an index of prefixes of a specific length.
          231  +  **
          232  +  ** Variable nPendingData contains an estimate the memory consumed by the 
          233  +  ** pending data structures, including hash table overhead, but not including
          234  +  ** malloc overhead.  When nPendingData exceeds nMaxPendingData, all hash
          235  +  ** tables are flushed to disk. Variable iPrevDocid is the docid of the most 
          236  +  ** recently inserted record.
   226    237     */
   227    238     int nIndex;                     /* Size of aIndex[] */
   228    239     struct Fts3Index {
   229    240       int nPrefix;                  /* Prefix length (0 for main terms index) */
   230    241       Fts3Hash hPending;            /* Pending terms table for this index */
   231    242     } *aIndex;
   232    243     int nMaxPendingData;            /* Max pending data before flush to disk */
................................................................................
   417    428   int sqlite3Fts3SelectDocsize(Fts3Table *, sqlite3_int64, sqlite3_stmt **);
   418    429   
   419    430   void sqlite3Fts3FreeDeferredTokens(Fts3Cursor *);
   420    431   int sqlite3Fts3DeferToken(Fts3Cursor *, Fts3PhraseToken *, int);
   421    432   int sqlite3Fts3CacheDeferredDoclists(Fts3Cursor *);
   422    433   void sqlite3Fts3FreeDeferredDoclists(Fts3Cursor *);
   423    434   void sqlite3Fts3SegmentsClose(Fts3Table *);
          435  +int sqlite3Fts3MaxLevel(Fts3Table *, int *);
   424    436   
   425    437   /* Special values interpreted by sqlite3SegReaderCursor() */
   426    438   #define FTS3_SEGCURSOR_PENDING        -1
   427    439   #define FTS3_SEGCURSOR_ALL            -2
   428    440   
   429    441   int sqlite3Fts3SegReaderStart(Fts3Table*, Fts3MultiSegReader*, Fts3SegFilter*);
   430    442   int sqlite3Fts3SegReaderStep(Fts3Table *, Fts3MultiSegReader *);
................................................................................
   468    480     /* Output values. Valid only after Fts3SegReaderStep() returns SQLITE_ROW. */
   469    481     char *zTerm;                    /* Pointer to term buffer */
   470    482     int nTerm;                      /* Size of zTerm in bytes */
   471    483     char *aDoclist;                 /* Pointer to doclist buffer */
   472    484     int nDoclist;                   /* Size of aDoclist[] in bytes */
   473    485   };
   474    486   
          487  +int sqlite3Fts3Incrmerge(Fts3Table*,int,int);
          488  +
   475    489   /* fts3.c */
   476    490   int sqlite3Fts3PutVarint(char *, sqlite3_int64);
   477    491   int sqlite3Fts3GetVarint(const char *, sqlite_int64 *);
   478    492   int sqlite3Fts3GetVarint32(const char *, int *);
   479    493   int sqlite3Fts3VarintLen(sqlite3_uint64);
   480    494   void sqlite3Fts3Dequote(char *);
   481    495   void sqlite3Fts3DoclistPrev(int,char*,int,char**,sqlite3_int64*,int*,u8*);
   482    496   int sqlite3Fts3EvalPhraseStats(Fts3Cursor *, Fts3Expr *, u32 *);
   483    497   int sqlite3Fts3FirstFilter(sqlite3_int64, char *, int, char *);
          498  +void sqlite3Fts3CreateStatTable(int*, Fts3Table*);
   484    499   
   485    500   /* fts3_tokenizer.c */
   486    501   const char *sqlite3Fts3NextToken(const char *, int *);
   487    502   int sqlite3Fts3InitHashTable(sqlite3 *, Fts3Hash *, const char *);
   488    503   int sqlite3Fts3InitTokenizer(Fts3Hash *pHash, const char *, 
   489    504       sqlite3_tokenizer **, char **
   490    505   );

Changes to ext/fts3/fts3_snippet.c.

   790    790   static int fts3MatchinfoCheck(
   791    791     Fts3Table *pTab, 
   792    792     char cArg,
   793    793     char **pzErr
   794    794   ){
   795    795     if( (cArg==FTS3_MATCHINFO_NPHRASE)
   796    796      || (cArg==FTS3_MATCHINFO_NCOL)
   797         -   || (cArg==FTS3_MATCHINFO_NDOC && pTab->bHasStat)
   798         -   || (cArg==FTS3_MATCHINFO_AVGLENGTH && pTab->bHasStat)
          797  +   || (cArg==FTS3_MATCHINFO_NDOC && pTab->bFts4)
          798  +   || (cArg==FTS3_MATCHINFO_AVGLENGTH && pTab->bFts4)
   799    799      || (cArg==FTS3_MATCHINFO_LENGTH && pTab->bHasDocsize)
   800    800      || (cArg==FTS3_MATCHINFO_LCS)
   801    801      || (cArg==FTS3_MATCHINFO_HITS)
   802    802     ){
   803    803       return SQLITE_OK;
   804    804     }
   805    805     *pzErr = sqlite3_mprintf("unrecognized matchinfo request: %c", cArg);

Changes to ext/fts3/fts3_write.c.

    20     20   #include "fts3Int.h"
    21     21   #if !defined(SQLITE_CORE) || defined(SQLITE_ENABLE_FTS3)
    22     22   
    23     23   #include <string.h>
    24     24   #include <assert.h>
    25     25   #include <stdlib.h>
    26     26   
           27  +
           28  +#define FTS_MAX_APPENDABLE_HEIGHT 16
           29  +
    27     30   /*
    28     31   ** When full-text index nodes are loaded from disk, the buffer that they
    29     32   ** are loaded into has the following number of bytes of padding at the end 
    30     33   ** of it. i.e. if a full-text index node is 900 bytes in size, then a buffer
    31     34   ** of 920 bytes is allocated for it.
    32     35   **
    33     36   ** This means that if we have a pointer into a buffer containing node data,
................................................................................
    58     61   int test_fts3_node_chunk_threshold = (4*1024)*4;
    59     62   # define FTS3_NODE_CHUNKSIZE       test_fts3_node_chunksize
    60     63   # define FTS3_NODE_CHUNK_THRESHOLD test_fts3_node_chunk_threshold
    61     64   #else
    62     65   # define FTS3_NODE_CHUNKSIZE (4*1024) 
    63     66   # define FTS3_NODE_CHUNK_THRESHOLD (FTS3_NODE_CHUNKSIZE*4)
    64     67   #endif
           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
           75  +#define FTS_STAT_AUTOINCRMERGE 2
           76  +
           77  +/*
           78  +** If FTS_LOG_MERGES is defined, call sqlite3_log() to report each automatic
           79  +** and incremental merge operation that takes place. This is used for 
           80  +** debugging FTS only, it should not usually be turned on in production
           81  +** systems.
           82  +*/
           83  +#ifdef FTS3_LOG_MERGES
           84  +static void fts3LogMerge(int nMerge, sqlite3_int64 iAbsLevel){
           85  +  sqlite3_log(SQLITE_OK, "%d-way merge from level %d", nMerge, (int)iAbsLevel);
           86  +}
           87  +#else
           88  +#define fts3LogMerge(x, y)
           89  +#endif
           90  +
    65     91   
    66     92   typedef struct PendingList PendingList;
    67     93   typedef struct SegmentNode SegmentNode;
    68     94   typedef struct SegmentWriter SegmentWriter;
    69     95   
    70     96   /*
    71     97   ** An instance of the following data structure is used to build doclists
................................................................................
   220    246   #define SQL_SELECT_SEGDIR_MAX_LEVEL   15
   221    247   #define SQL_DELETE_SEGDIR_LEVEL       16
   222    248   #define SQL_DELETE_SEGMENTS_RANGE     17
   223    249   #define SQL_CONTENT_INSERT            18
   224    250   #define SQL_DELETE_DOCSIZE            19
   225    251   #define SQL_REPLACE_DOCSIZE           20
   226    252   #define SQL_SELECT_DOCSIZE            21
   227         -#define SQL_SELECT_DOCTOTAL           22
   228         -#define SQL_REPLACE_DOCTOTAL          23
          253  +#define SQL_SELECT_STAT               22
          254  +#define SQL_REPLACE_STAT              23
   229    255   
   230    256   #define SQL_SELECT_ALL_PREFIX_LEVEL   24
   231    257   #define SQL_DELETE_ALL_TERMS_SEGDIR   25
   232         -
   233    258   #define SQL_DELETE_SEGDIR_RANGE       26
   234         -
   235    259   #define SQL_SELECT_ALL_LANGID         27
          260  +#define SQL_FIND_MERGE_LEVEL          28
          261  +#define SQL_MAX_LEAF_NODE_ESTIMATE    29
          262  +#define SQL_DELETE_SEGDIR_ENTRY       30
          263  +#define SQL_SHIFT_SEGDIR_ENTRY        31
          264  +#define SQL_SELECT_SEGDIR             32
          265  +#define SQL_CHOMP_SEGDIR              33
          266  +#define SQL_SEGMENT_IS_APPENDABLE     34
          267  +#define SQL_SELECT_INDEXES            35
          268  +#define SQL_SELECT_MXLEVEL            36
   236    269   
   237    270   /*
   238    271   ** This function is used to obtain an SQLite prepared statement handle
   239    272   ** for the statement identified by the second argument. If successful,
   240    273   ** *pp is set to the requested statement handle and SQLITE_OK returned.
   241    274   ** Otherwise, an SQLite error code is returned and *pp is set to 0.
   242    275   **
................................................................................
   257    290   /* 2  */  "DELETE FROM %Q.'%q_content'",
   258    291   /* 3  */  "DELETE FROM %Q.'%q_segments'",
   259    292   /* 4  */  "DELETE FROM %Q.'%q_segdir'",
   260    293   /* 5  */  "DELETE FROM %Q.'%q_docsize'",
   261    294   /* 6  */  "DELETE FROM %Q.'%q_stat'",
   262    295   /* 7  */  "SELECT %s WHERE rowid=?",
   263    296   /* 8  */  "SELECT (SELECT max(idx) FROM %Q.'%q_segdir' WHERE level = ?) + 1",
   264         -/* 9  */  "INSERT INTO %Q.'%q_segments'(blockid, block) VALUES(?, ?)",
          297  +/* 9  */  "REPLACE INTO %Q.'%q_segments'(blockid, block) VALUES(?, ?)",
   265    298   /* 10 */  "SELECT coalesce((SELECT max(blockid) FROM %Q.'%q_segments') + 1, 1)",
   266         -/* 11 */  "INSERT INTO %Q.'%q_segdir' VALUES(?,?,?,?,?,?)",
          299  +/* 11 */  "REPLACE INTO %Q.'%q_segdir' VALUES(?,?,?,?,?,?)",
   267    300   
   268    301             /* Return segments in order from oldest to newest.*/ 
   269    302   /* 12 */  "SELECT idx, start_block, leaves_end_block, end_block, root "
   270    303               "FROM %Q.'%q_segdir' WHERE level = ? ORDER BY idx ASC",
   271    304   /* 13 */  "SELECT idx, start_block, leaves_end_block, end_block, root "
   272    305               "FROM %Q.'%q_segdir' WHERE level BETWEEN ? AND ?"
   273    306               "ORDER BY level DESC, idx ASC",
................................................................................
   277    310   
   278    311   /* 16 */  "DELETE FROM %Q.'%q_segdir' WHERE level = ?",
   279    312   /* 17 */  "DELETE FROM %Q.'%q_segments' WHERE blockid BETWEEN ? AND ?",
   280    313   /* 18 */  "INSERT INTO %Q.'%q_content' VALUES(%s)",
   281    314   /* 19 */  "DELETE FROM %Q.'%q_docsize' WHERE docid = ?",
   282    315   /* 20 */  "REPLACE INTO %Q.'%q_docsize' VALUES(?,?)",
   283    316   /* 21 */  "SELECT size FROM %Q.'%q_docsize' WHERE docid=?",
   284         -/* 22 */  "SELECT value FROM %Q.'%q_stat' WHERE id=0",
   285         -/* 23 */  "REPLACE INTO %Q.'%q_stat' VALUES(0,?)",
          317  +/* 22 */  "SELECT value FROM %Q.'%q_stat' WHERE id=?",
          318  +/* 23 */  "REPLACE INTO %Q.'%q_stat' VALUES(?,?)",
   286    319   /* 24 */  "",
   287    320   /* 25 */  "",
   288    321   
   289    322   /* 26 */ "DELETE FROM %Q.'%q_segdir' WHERE level BETWEEN ? AND ?",
   290    323   /* 27 */ "SELECT DISTINCT level / (1024 * ?) FROM %Q.'%q_segdir'",
   291    324   
          325  +/* This statement is used to determine which level to read the input from
          326  +** when performing an incremental merge. It returns the absolute level number
          327  +** of the oldest level in the db that contains at least ? segments. Or,
          328  +** if no level in the FTS index contains more than ? segments, the statement
          329  +** returns zero rows.  */
          330  +/* 28 */ "SELECT level FROM %Q.'%q_segdir' GROUP BY level HAVING count(*)>=?"
          331  +         "  ORDER BY (level %% 1024) ASC LIMIT 1",
          332  +
          333  +/* Estimate the upper limit on the number of leaf nodes in a new segment
          334  +** created by merging the oldest :2 segments from absolute level :1. See 
          335  +** function sqlite3Fts3Incrmerge() for details.  */
          336  +/* 29 */ "SELECT 2 * total(1 + leaves_end_block - start_block) "
          337  +         "  FROM %Q.'%q_segdir' WHERE level = ? AND idx < ?",
          338  +
          339  +/* SQL_DELETE_SEGDIR_ENTRY
          340  +**   Delete the %_segdir entry on absolute level :1 with index :2.  */
          341  +/* 30 */ "DELETE FROM %Q.'%q_segdir' WHERE level = ? AND idx = ?",
          342  +
          343  +/* SQL_SHIFT_SEGDIR_ENTRY
          344  +**   Modify the idx value for the segment with idx=:3 on absolute level :2
          345  +**   to :1.  */
          346  +/* 31 */ "UPDATE %Q.'%q_segdir' SET idx = ? WHERE level=? AND idx=?",
          347  +
          348  +/* SQL_SELECT_SEGDIR
          349  +**   Read a single entry from the %_segdir table. The entry from absolute 
          350  +**   level :1 with index value :2.  */
          351  +/* 32 */  "SELECT idx, start_block, leaves_end_block, end_block, root "
          352  +            "FROM %Q.'%q_segdir' WHERE level = ? AND idx = ?",
          353  +
          354  +/* SQL_CHOMP_SEGDIR
          355  +**   Update the start_block (:1) and root (:2) fields of the %_segdir
          356  +**   entry located on absolute level :3 with index :4.  */
          357  +/* 33 */  "UPDATE %Q.'%q_segdir' SET start_block = ?, root = ?"
          358  +            "WHERE level = ? AND idx = ?",
          359  +
          360  +/* SQL_SEGMENT_IS_APPENDABLE
          361  +**   Return a single row if the segment with end_block=? is appendable. Or
          362  +**   no rows otherwise.  */
          363  +/* 34 */  "SELECT 1 FROM %Q.'%q_segments' WHERE blockid=? AND block IS NULL",
          364  +
          365  +/* SQL_SELECT_INDEXES
          366  +**   Return the list of valid segment indexes for absolute level ?  */
          367  +/* 35 */  "SELECT idx FROM %Q.'%q_segdir' WHERE level=? ORDER BY 1 ASC",
          368  +
          369  +/* SQL_SELECT_MXLEVEL
          370  +**   Return the largest relative level in the FTS index or indexes.  */
          371  +/* 36 */  "SELECT max( level %% 1024 ) FROM %Q.'%q_segdir'"
   292    372     };
   293    373     int rc = SQLITE_OK;
   294    374     sqlite3_stmt *pStmt;
   295    375   
   296    376     assert( SizeofArray(azSql)==SizeofArray(p->aStmt) );
   297    377     assert( eStmt<SizeofArray(azSql) && eStmt>=0 );
   298    378     
................................................................................
   321    401       for(i=0; rc==SQLITE_OK && i<nParam; i++){
   322    402         rc = sqlite3_bind_value(pStmt, i+1, apVal[i]);
   323    403       }
   324    404     }
   325    405     *pp = pStmt;
   326    406     return rc;
   327    407   }
          408  +
   328    409   
   329    410   static int fts3SelectDocsize(
   330    411     Fts3Table *pTab,                /* FTS3 table handle */
   331         -  int eStmt,                      /* Either SQL_SELECT_DOCSIZE or DOCTOTAL */
   332    412     sqlite3_int64 iDocid,           /* Docid to bind for SQL_SELECT_DOCSIZE */
   333    413     sqlite3_stmt **ppStmt           /* OUT: Statement handle */
   334    414   ){
   335    415     sqlite3_stmt *pStmt = 0;        /* Statement requested from fts3SqlStmt() */
   336    416     int rc;                         /* Return code */
   337    417   
   338         -  assert( eStmt==SQL_SELECT_DOCSIZE || eStmt==SQL_SELECT_DOCTOTAL );
   339         -
   340         -  rc = fts3SqlStmt(pTab, eStmt, &pStmt, 0);
          418  +  rc = fts3SqlStmt(pTab, SQL_SELECT_DOCSIZE, &pStmt, 0);
   341    419     if( rc==SQLITE_OK ){
   342         -    if( eStmt==SQL_SELECT_DOCSIZE ){
   343         -      sqlite3_bind_int64(pStmt, 1, iDocid);
   344         -    }
          420  +    sqlite3_bind_int64(pStmt, 1, iDocid);
   345    421       rc = sqlite3_step(pStmt);
   346    422       if( rc!=SQLITE_ROW || sqlite3_column_type(pStmt, 0)!=SQLITE_BLOB ){
   347    423         rc = sqlite3_reset(pStmt);
   348    424         if( rc==SQLITE_OK ) rc = FTS_CORRUPT_VTAB;
   349    425         pStmt = 0;
   350    426       }else{
   351    427         rc = SQLITE_OK;
................................................................................
   356    432     return rc;
   357    433   }
   358    434   
   359    435   int sqlite3Fts3SelectDoctotal(
   360    436     Fts3Table *pTab,                /* Fts3 table handle */
   361    437     sqlite3_stmt **ppStmt           /* OUT: Statement handle */
   362    438   ){
   363         -  return fts3SelectDocsize(pTab, SQL_SELECT_DOCTOTAL, 0, ppStmt);
          439  +  sqlite3_stmt *pStmt = 0;
          440  +  int rc;
          441  +  rc = fts3SqlStmt(pTab, SQL_SELECT_STAT, &pStmt, 0);
          442  +  if( rc==SQLITE_OK ){
          443  +    sqlite3_bind_int(pStmt, 1, FTS_STAT_DOCTOTAL);
          444  +    if( sqlite3_step(pStmt)!=SQLITE_ROW
          445  +     || sqlite3_column_type(pStmt, 0)!=SQLITE_BLOB
          446  +    ){
          447  +      rc = sqlite3_reset(pStmt);
          448  +      if( rc==SQLITE_OK ) rc = FTS_CORRUPT_VTAB;
          449  +      pStmt = 0;
          450  +    }
          451  +  }
          452  +  *ppStmt = pStmt;
          453  +  return rc;
   364    454   }
   365    455   
   366    456   int sqlite3Fts3SelectDocsize(
   367    457     Fts3Table *pTab,                /* Fts3 table handle */
   368    458     sqlite3_int64 iDocid,           /* Docid to read size data for */
   369    459     sqlite3_stmt **ppStmt           /* OUT: Statement handle */
   370    460   ){
   371         -  return fts3SelectDocsize(pTab, SQL_SELECT_DOCSIZE, iDocid, ppStmt);
          461  +  return fts3SelectDocsize(pTab, iDocid, ppStmt);
   372    462   }
   373    463   
   374    464   /*
   375    465   ** Similar to fts3SqlStmt(). Except, after binding the parameters in
   376    466   ** array apVal[] to the SQL statement identified by eStmt, the statement
   377    467   ** is executed.
   378    468   **
................................................................................
   454    544   ** Language 1 indexes are allocated immediately following language 0.
   455    545   **
   456    546   ** So, for a system with nPrefix prefix indexes configured, the block of
   457    547   ** absolute levels that corresponds to language-id iLangid and index 
   458    548   ** iIndex starts at absolute level ((iLangid * (nPrefix+1) + iIndex) * 1024).
   459    549   */
   460    550   static sqlite3_int64 getAbsoluteLevel(
   461         -  Fts3Table *p, 
   462         -  int iLangid, 
   463         -  int iIndex, 
   464         -  int iLevel
          551  +  Fts3Table *p,                   /* FTS3 table handle */
          552  +  int iLangid,                    /* Language id */
          553  +  int iIndex,                     /* Index in p->aIndex[] */
          554  +  int iLevel                      /* Level of segments */
   465    555   ){
   466    556     sqlite3_int64 iBase;            /* First absolute level for iLangid/iIndex */
   467    557     assert( iLangid>=0 );
   468    558     assert( p->nIndex>0 );
   469    559     assert( iIndex>=0 && iIndex<p->nIndex );
   470    560   
   471    561     iBase = ((sqlite3_int64)iLangid * p->nIndex + iIndex) * FTS3_SEGDIR_MAXLEVEL;
   472    562     return iBase + iLevel;
   473    563   }
   474         -
   475    564   
   476    565   /*
   477    566   ** Set *ppStmt to a statement handle that may be used to iterate through
   478    567   ** all rows in the %_segdir table, from oldest to newest. If successful,
   479    568   ** return SQLITE_OK. If an error occurs while preparing the statement, 
   480    569   ** return an SQLite error code.
   481    570   **
................................................................................
  1034   1123     if( rc==SQLITE_OK ){
  1035   1124       /* If iNext is FTS3_MERGE_COUNT, indicating that level iLevel is already
  1036   1125       ** full, merge all segments in level iLevel into a single iLevel+1
  1037   1126       ** segment and allocate (newly freed) index 0 at level iLevel. Otherwise,
  1038   1127       ** if iNext is less than FTS3_MERGE_COUNT, allocate index iNext.
  1039   1128       */
  1040   1129       if( iNext>=FTS3_MERGE_COUNT ){
         1130  +      fts3LogMerge(16, getAbsoluteLevel(p, iLangid, iIndex, iLevel));
  1041   1131         rc = fts3SegmentMerge(p, iLangid, iIndex, iLevel);
  1042   1132         *piIdx = 0;
  1043   1133       }else{
  1044   1134         *piIdx = iNext;
  1045   1135       }
  1046   1136     }
  1047   1137   
................................................................................
  1081   1171     char **paBlob,                  /* OUT: Blob data in malloc'd buffer */
  1082   1172     int *pnBlob,                    /* OUT: Size of blob data */
  1083   1173     int *pnLoad                     /* OUT: Bytes actually loaded */
  1084   1174   ){
  1085   1175     int rc;                         /* Return code */
  1086   1176   
  1087   1177     /* pnBlob must be non-NULL. paBlob may be NULL or non-NULL. */
  1088         -  assert( pnBlob);
         1178  +  assert( pnBlob );
  1089   1179   
  1090   1180     if( p->pSegments ){
  1091   1181       rc = sqlite3_blob_reopen(p->pSegments, iBlockid);
  1092   1182     }else{
  1093   1183       if( 0==p->zSegmentsTbl ){
  1094   1184         p->zSegmentsTbl = sqlite3_mprintf("%s_segments", p->zName);
  1095   1185         if( 0==p->zSegmentsTbl ) return SQLITE_NOMEM;
................................................................................
  1422   1512   ){
  1423   1513     Fts3Table *p = (Fts3Table*)pCsr->base.pVtab;
  1424   1514     int nOvfl = 0;
  1425   1515     int ii;
  1426   1516     int rc = SQLITE_OK;
  1427   1517     int pgsz = p->nPgsz;
  1428   1518   
  1429         -  assert( p->bHasStat );
         1519  +  assert( p->bFts4 );
  1430   1520     assert( pgsz>0 );
  1431   1521   
  1432   1522     for(ii=0; rc==SQLITE_OK && ii<pMsr->nSegment; ii++){
  1433   1523       Fts3SegReader *pReader = pMsr->apSegment[ii];
  1434   1524       if( !fts3SegReaderIsPending(pReader) 
  1435   1525        && !fts3SegReaderIsRootOnly(pReader) 
  1436   1526       ){
................................................................................
  1779   1869       sqlite3_bind_int64(pStmt, 1, iBlock);
  1780   1870       sqlite3_bind_blob(pStmt, 2, z, n, SQLITE_STATIC);
  1781   1871       sqlite3_step(pStmt);
  1782   1872       rc = sqlite3_reset(pStmt);
  1783   1873     }
  1784   1874     return rc;
  1785   1875   }
         1876  +
         1877  +/*
         1878  +** Find the largest relative level number in the table. If successful, set
         1879  +** *pnMax to this value and return SQLITE_OK. Otherwise, if an error occurs,
         1880  +** set *pnMax to zero and return an SQLite error code.
         1881  +*/
         1882  +int sqlite3Fts3MaxLevel(Fts3Table *p, int *pnMax){
         1883  +  int rc;
         1884  +  int mxLevel = 0;
         1885  +  sqlite3_stmt *pStmt = 0;
         1886  +
         1887  +  rc = fts3SqlStmt(p, SQL_SELECT_MXLEVEL, &pStmt, 0);
         1888  +  if( rc==SQLITE_OK ){
         1889  +    if( SQLITE_ROW==sqlite3_step(pStmt) ){
         1890  +      mxLevel = sqlite3_column_int(pStmt, 0);
         1891  +    }
         1892  +    rc = sqlite3_reset(pStmt);
         1893  +  }
         1894  +  *pnMax = mxLevel;
         1895  +  return rc;
         1896  +}
  1786   1897   
  1787   1898   /* 
  1788   1899   ** Insert a record into the %_segdir table.
  1789   1900   */
  1790   1901   static int fts3WriteSegdir(
  1791   1902     Fts3Table *p,                   /* Virtual table handle */
  1792   1903     sqlite3_int64 iLevel,           /* Value for "level" field (absolute level) */
................................................................................
  2096   2207   
  2097   2208     if( nData>0 && nData+nReq>p->nNodeSize ){
  2098   2209       int rc;
  2099   2210   
  2100   2211       /* The current leaf node is full. Write it out to the database. */
  2101   2212       rc = fts3WriteSegment(p, pWriter->iFree++, pWriter->aData, nData);
  2102   2213       if( rc!=SQLITE_OK ) return rc;
         2214  +    p->nLeafAdd++;
  2103   2215   
  2104   2216       /* Add the current term to the interior node tree. The term added to
  2105   2217       ** the interior tree must:
  2106   2218       **
  2107   2219       **   a) be greater than the largest term on the leaf node just written
  2108   2220       **      to the database (still available in pWriter->zTerm), and
  2109   2221       **
................................................................................
  2204   2316             p, iLevel, iIdx, pWriter->iFirst, iLastLeaf, iLast, zRoot, nRoot);
  2205   2317       }
  2206   2318     }else{
  2207   2319       /* The entire tree fits on the root node. Write it to the segdir table. */
  2208   2320       rc = fts3WriteSegdir(
  2209   2321           p, iLevel, iIdx, 0, 0, 0, pWriter->aData, pWriter->nData);
  2210   2322     }
         2323  +  p->nLeafAdd++;
  2211   2324     return rc;
  2212   2325   }
  2213   2326   
  2214   2327   /*
  2215   2328   ** Release all memory held by the SegmentWriter object passed as the 
  2216   2329   ** first argument.
  2217   2330   */
................................................................................
  2284   2397         getAbsoluteLevel(p, iLangid, iIndex, FTS3_SEGDIR_MAXLEVEL-1)
  2285   2398     );
  2286   2399     if( SQLITE_ROW==sqlite3_step(pStmt) ){
  2287   2400       *pnMax = sqlite3_column_int64(pStmt, 0);
  2288   2401     }
  2289   2402     return sqlite3_reset(pStmt);
  2290   2403   }
         2404  +
         2405  +/*
         2406  +** Delete all entries in the %_segments table associated with the segment
         2407  +** opened with seg-reader pSeg. This function does not affect the contents
         2408  +** of the %_segdir table.
         2409  +*/
         2410  +static int fts3DeleteSegment(
         2411  +  Fts3Table *p,                   /* FTS table handle */
         2412  +  Fts3SegReader *pSeg             /* Segment to delete */
         2413  +){
         2414  +  int rc = SQLITE_OK;             /* Return code */
         2415  +  if( pSeg->iStartBlock ){
         2416  +    sqlite3_stmt *pDelete;        /* SQL statement to delete rows */
         2417  +    rc = fts3SqlStmt(p, SQL_DELETE_SEGMENTS_RANGE, &pDelete, 0);
         2418  +    if( rc==SQLITE_OK ){
         2419  +      sqlite3_bind_int64(pDelete, 1, pSeg->iStartBlock);
         2420  +      sqlite3_bind_int64(pDelete, 2, pSeg->iEndBlock);
         2421  +      sqlite3_step(pDelete);
         2422  +      rc = sqlite3_reset(pDelete);
         2423  +    }
         2424  +  }
         2425  +  return rc;
         2426  +}
  2291   2427   
  2292   2428   /*
  2293   2429   ** This function is used after merging multiple segments into a single large
  2294   2430   ** segment to delete the old, now redundant, segment b-trees. Specifically,
  2295   2431   ** it:
  2296   2432   ** 
  2297   2433   **   1) Deletes all %_segments entries for the segments associated with 
................................................................................
  2307   2443     Fts3Table *p,                   /* Virtual table handle */
  2308   2444     int iLangid,                    /* Language id */
  2309   2445     int iIndex,                     /* Index for p->aIndex */
  2310   2446     int iLevel,                     /* Level of %_segdir entries to delete */
  2311   2447     Fts3SegReader **apSegment,      /* Array of SegReader objects */
  2312   2448     int nReader                     /* Size of array apSegment */
  2313   2449   ){
  2314         -  int rc;                         /* Return Code */
         2450  +  int rc = SQLITE_OK;             /* Return Code */
  2315   2451     int i;                          /* Iterator variable */
  2316         -  sqlite3_stmt *pDelete;          /* SQL statement to delete rows */
         2452  +  sqlite3_stmt *pDelete = 0;      /* SQL statement to delete rows */
  2317   2453   
  2318         -  rc = fts3SqlStmt(p, SQL_DELETE_SEGMENTS_RANGE, &pDelete, 0);
  2319   2454     for(i=0; rc==SQLITE_OK && i<nReader; i++){
  2320         -    Fts3SegReader *pSegment = apSegment[i];
  2321         -    if( pSegment->iStartBlock ){
  2322         -      sqlite3_bind_int64(pDelete, 1, pSegment->iStartBlock);
  2323         -      sqlite3_bind_int64(pDelete, 2, pSegment->iEndBlock);
  2324         -      sqlite3_step(pDelete);
  2325         -      rc = sqlite3_reset(pDelete);
  2326         -    }
         2455  +    rc = fts3DeleteSegment(p, apSegment[i]);
  2327   2456     }
  2328   2457     if( rc!=SQLITE_OK ){
  2329   2458       return rc;
  2330   2459     }
  2331   2460   
  2332   2461     assert( iLevel>=0 || iLevel==FTS3_SEGCURSOR_ALL );
  2333   2462     if( iLevel==FTS3_SEGCURSOR_ALL ){
................................................................................
  2895   3024   
  2896   3025   /* 
  2897   3026   ** Flush the contents of pendingTerms to level 0 segments.
  2898   3027   */
  2899   3028   int sqlite3Fts3PendingTermsFlush(Fts3Table *p){
  2900   3029     int rc = SQLITE_OK;
  2901   3030     int i;
         3031  +        
  2902   3032     for(i=0; rc==SQLITE_OK && i<p->nIndex; i++){
  2903   3033       rc = fts3SegmentMerge(p, p->iPrevLangid, i, FTS3_SEGCURSOR_PENDING);
  2904   3034       if( rc==SQLITE_DONE ) rc = SQLITE_OK;
  2905   3035     }
  2906   3036     sqlite3Fts3PendingTermsClear(p);
         3037  +
         3038  +  /* Determine the auto-incr-merge setting if unknown.  If enabled,
         3039  +  ** estimate the number of leaf blocks of content to be written
         3040  +  */
         3041  +  if( rc==SQLITE_OK && p->bHasStat
         3042  +   && p->bAutoincrmerge==0xff && p->nLeafAdd>0
         3043  +  ){
         3044  +    sqlite3_stmt *pStmt = 0;
         3045  +    rc = fts3SqlStmt(p, SQL_SELECT_STAT, &pStmt, 0);
         3046  +    if( rc==SQLITE_OK ){
         3047  +      sqlite3_bind_int(pStmt, 1, FTS_STAT_AUTOINCRMERGE);
         3048  +      rc = sqlite3_step(pStmt);
         3049  +      p->bAutoincrmerge = (rc==SQLITE_ROW && sqlite3_column_int(pStmt, 0));
         3050  +      rc = sqlite3_reset(pStmt);
         3051  +    }
         3052  +  }
  2907   3053     return rc;
  2908   3054   }
  2909   3055   
  2910   3056   /*
  2911   3057   ** Encode N integers as varints into a blob.
  2912   3058   */
  2913   3059   static void fts3EncodeIntArray(
................................................................................
  3010   3156     if( *pRC ) return;
  3011   3157     a = sqlite3_malloc( (sizeof(u32)+10)*nStat );
  3012   3158     if( a==0 ){
  3013   3159       *pRC = SQLITE_NOMEM;
  3014   3160       return;
  3015   3161     }
  3016   3162     pBlob = (char*)&a[nStat];
  3017         -  rc = fts3SqlStmt(p, SQL_SELECT_DOCTOTAL, &pStmt, 0);
         3163  +  rc = fts3SqlStmt(p, SQL_SELECT_STAT, &pStmt, 0);
  3018   3164     if( rc ){
  3019   3165       sqlite3_free(a);
  3020   3166       *pRC = rc;
  3021   3167       return;
  3022   3168     }
         3169  +  sqlite3_bind_int(pStmt, 1, FTS_STAT_DOCTOTAL);
  3023   3170     if( sqlite3_step(pStmt)==SQLITE_ROW ){
  3024   3171       fts3DecodeIntArray(nStat, a,
  3025   3172            sqlite3_column_blob(pStmt, 0),
  3026   3173            sqlite3_column_bytes(pStmt, 0));
  3027   3174     }else{
  3028   3175       memset(a, 0, sizeof(u32)*(nStat) );
  3029   3176     }
................................................................................
  3039   3186         x = 0;
  3040   3187       }else{
  3041   3188         x = x + aSzIns[i] - aSzDel[i];
  3042   3189       }
  3043   3190       a[i+1] = x;
  3044   3191     }
  3045   3192     fts3EncodeIntArray(nStat, a, pBlob, &nBlob);
  3046         -  rc = fts3SqlStmt(p, SQL_REPLACE_DOCTOTAL, &pStmt, 0);
         3193  +  rc = fts3SqlStmt(p, SQL_REPLACE_STAT, &pStmt, 0);
  3047   3194     if( rc ){
  3048   3195       sqlite3_free(a);
  3049   3196       *pRC = rc;
  3050   3197       return;
  3051   3198     }
  3052         -  sqlite3_bind_blob(pStmt, 1, pBlob, nBlob, SQLITE_STATIC);
         3199  +  sqlite3_bind_int(pStmt, 1, FTS_STAT_DOCTOTAL);
         3200  +  sqlite3_bind_blob(pStmt, 2, pBlob, nBlob, SQLITE_STATIC);
  3053   3201     sqlite3_step(pStmt);
  3054   3202     *pRC = sqlite3_reset(pStmt);
  3055   3203     sqlite3_free(a);
  3056   3204   }
  3057   3205   
  3058   3206   /*
  3059   3207   ** Merge the entire database so that there is one segment for each 
................................................................................
  3150   3298         }else{
  3151   3299           nEntry++;
  3152   3300           for(iCol=0; iCol<=p->nColumn; iCol++){
  3153   3301             aSzIns[iCol] += aSz[iCol];
  3154   3302           }
  3155   3303         }
  3156   3304       }
  3157         -    if( p->bHasStat ){
         3305  +    if( p->bFts4 ){
  3158   3306         fts3UpdateDocTotals(&rc, p, aSzIns, aSzDel, nEntry);
  3159   3307       }
  3160   3308       sqlite3_free(aSz);
  3161   3309   
  3162   3310       if( pStmt ){
  3163   3311         int rc2 = sqlite3_finalize(pStmt);
  3164   3312         if( rc==SQLITE_OK ){
................................................................................
  3166   3314         }
  3167   3315       }
  3168   3316     }
  3169   3317   
  3170   3318     return rc;
  3171   3319   }
  3172   3320   
         3321  +
         3322  +/*
         3323  +** This function opens a cursor used to read the input data for an 
         3324  +** incremental merge operation. Specifically, it opens a cursor to scan
         3325  +** the oldest nSeg segments (idx=0 through idx=(nSeg-1)) in absolute 
         3326  +** level iAbsLevel.
         3327  +*/
         3328  +static int fts3IncrmergeCsr(
         3329  +  Fts3Table *p,                   /* FTS3 table handle */
         3330  +  sqlite3_int64 iAbsLevel,        /* Absolute level to open */
         3331  +  int nSeg,                       /* Number of segments to merge */
         3332  +  Fts3MultiSegReader *pCsr        /* Cursor object to populate */
         3333  +){
         3334  +  int rc;                         /* Return Code */
         3335  +  sqlite3_stmt *pStmt = 0;        /* Statement used to read %_segdir entry */  
         3336  +  int nByte;                      /* Bytes allocated at pCsr->apSegment[] */
         3337  +
         3338  +  /* Allocate space for the Fts3MultiSegReader.aCsr[] array */
         3339  +  memset(pCsr, 0, sizeof(*pCsr));
         3340  +  nByte = sizeof(Fts3SegReader *) * nSeg;
         3341  +  pCsr->apSegment = (Fts3SegReader **)sqlite3_malloc(nByte);
         3342  +
         3343  +  if( pCsr->apSegment==0 ){
         3344  +    rc = SQLITE_NOMEM;
         3345  +  }else{
         3346  +    memset(pCsr->apSegment, 0, nByte);
         3347  +    rc = fts3SqlStmt(p, SQL_SELECT_LEVEL, &pStmt, 0);
         3348  +  }
         3349  +  if( rc==SQLITE_OK ){
         3350  +    int i;
         3351  +    int rc2;
         3352  +    sqlite3_bind_int64(pStmt, 1, iAbsLevel);
         3353  +    assert( pCsr->nSegment==0 );
         3354  +    for(i=0; rc==SQLITE_OK && sqlite3_step(pStmt)==SQLITE_ROW && i<nSeg; i++){
         3355  +      rc = sqlite3Fts3SegReaderNew(i, 0,
         3356  +          sqlite3_column_int64(pStmt, 1),        /* segdir.start_block */
         3357  +          sqlite3_column_int64(pStmt, 2),        /* segdir.leaves_end_block */
         3358  +          sqlite3_column_int64(pStmt, 3),        /* segdir.end_block */
         3359  +          sqlite3_column_blob(pStmt, 4),         /* segdir.root */
         3360  +          sqlite3_column_bytes(pStmt, 4),        /* segdir.root */
         3361  +          &pCsr->apSegment[i]
         3362  +      );
         3363  +      pCsr->nSegment++;
         3364  +    }
         3365  +    rc2 = sqlite3_reset(pStmt);
         3366  +    if( rc==SQLITE_OK ) rc = rc2;
         3367  +  }
         3368  +
         3369  +  return rc;
         3370  +}
         3371  +
         3372  +typedef struct IncrmergeWriter IncrmergeWriter;
         3373  +typedef struct NodeWriter NodeWriter;
         3374  +typedef struct Blob Blob;
         3375  +typedef struct NodeReader NodeReader;
         3376  +
         3377  +/*
         3378  +** An instance of the following structure is used as a dynamic buffer
         3379  +** to build up nodes or other blobs of data in.
         3380  +**
         3381  +** The function blobGrowBuffer() is used to extend the allocation.
         3382  +*/
         3383  +struct Blob {
         3384  +  char *a;                        /* Pointer to allocation */
         3385  +  int n;                          /* Number of valid bytes of data in a[] */
         3386  +  int nAlloc;                     /* Allocated size of a[] (nAlloc>=n) */
         3387  +};
         3388  +
         3389  +/*
         3390  +** This structure is used to build up buffers containing segment b-tree 
         3391  +** nodes (blocks).
         3392  +*/
         3393  +struct NodeWriter {
         3394  +  sqlite3_int64 iBlock;           /* Current block id */
         3395  +  Blob key;                       /* Last key written to the current block */
         3396  +  Blob block;                     /* Current block image */
         3397  +};
         3398  +
         3399  +/*
         3400  +** An object of this type contains the state required to create or append
         3401  +** to an appendable b-tree segment.
         3402  +*/
         3403  +struct IncrmergeWriter {
         3404  +  int nLeafEst;                   /* Space allocated for leaf blocks */
         3405  +  int nWork;                      /* Number of leaf pages flushed */
         3406  +  sqlite3_int64 iAbsLevel;        /* Absolute level of input segments */
         3407  +  int iIdx;                       /* Index of *output* segment in iAbsLevel+1 */
         3408  +  sqlite3_int64 iStart;           /* Block number of first allocated block */
         3409  +  sqlite3_int64 iEnd;             /* Block number of last allocated block */
         3410  +  NodeWriter aNodeWriter[FTS_MAX_APPENDABLE_HEIGHT];
         3411  +};
         3412  +
         3413  +/*
         3414  +** An object of the following type is used to read data from a single
         3415  +** FTS segment node. See the following functions:
         3416  +**
         3417  +**     nodeReaderInit()
         3418  +**     nodeReaderNext()
         3419  +**     nodeReaderRelease()
         3420  +*/
         3421  +struct NodeReader {
         3422  +  const char *aNode;
         3423  +  int nNode;
         3424  +  int iOff;                       /* Current offset within aNode[] */
         3425  +
         3426  +  /* Output variables. Containing the current node entry. */
         3427  +  sqlite3_int64 iChild;           /* Pointer to child node */
         3428  +  Blob term;                      /* Current term */
         3429  +  const char *aDoclist;           /* Pointer to doclist */
         3430  +  int nDoclist;                   /* Size of doclist in bytes */
         3431  +};
         3432  +
         3433  +/*
         3434  +** If *pRc is not SQLITE_OK when this function is called, it is a no-op.
         3435  +** Otherwise, if the allocation at pBlob->a is not already at least nMin
         3436  +** bytes in size, extend (realloc) it to be so.
         3437  +**
         3438  +** If an OOM error occurs, set *pRc to SQLITE_NOMEM and leave pBlob->a
         3439  +** unmodified. Otherwise, if the allocation succeeds, update pBlob->nAlloc
         3440  +** to reflect the new size of the pBlob->a[] buffer.
         3441  +*/
         3442  +static void blobGrowBuffer(Blob *pBlob, int nMin, int *pRc){
         3443  +  if( *pRc==SQLITE_OK && nMin>pBlob->nAlloc ){
         3444  +    int nAlloc = nMin;
         3445  +    char *a = (char *)sqlite3_realloc(pBlob->a, nAlloc);
         3446  +    if( a ){
         3447  +      pBlob->nAlloc = nAlloc;
         3448  +      pBlob->a = a;
         3449  +    }else{
         3450  +      *pRc = SQLITE_NOMEM;
         3451  +    }
         3452  +  }
         3453  +}
         3454  +
         3455  +/*
         3456  +** Attempt to advance the node-reader object passed as the first argument to
         3457  +** the next entry on the node. 
         3458  +**
         3459  +** Return an error code if an error occurs (SQLITE_NOMEM is possible). 
         3460  +** Otherwise return SQLITE_OK. If there is no next entry on the node
         3461  +** (e.g. because the current entry is the last) set NodeReader->aNode to
         3462  +** NULL to indicate EOF. Otherwise, populate the NodeReader structure output 
         3463  +** variables for the new entry.
         3464  +*/
         3465  +static int nodeReaderNext(NodeReader *p){
         3466  +  int bFirst = (p->term.n==0);    /* True for first term on the node */
         3467  +  int nPrefix = 0;                /* Bytes to copy from previous term */
         3468  +  int nSuffix = 0;                /* Bytes to append to the prefix */
         3469  +  int rc = SQLITE_OK;             /* Return code */
         3470  +
         3471  +  assert( p->aNode );
         3472  +  if( p->iChild && bFirst==0 ) p->iChild++;
         3473  +  if( p->iOff>=p->nNode ){
         3474  +    /* EOF */
         3475  +    p->aNode = 0;
         3476  +  }else{
         3477  +    if( bFirst==0 ){
         3478  +      p->iOff += sqlite3Fts3GetVarint32(&p->aNode[p->iOff], &nPrefix);
         3479  +    }
         3480  +    p->iOff += sqlite3Fts3GetVarint32(&p->aNode[p->iOff], &nSuffix);
         3481  +
         3482  +    blobGrowBuffer(&p->term, nPrefix+nSuffix, &rc);
         3483  +    if( rc==SQLITE_OK ){
         3484  +      memcpy(&p->term.a[nPrefix], &p->aNode[p->iOff], nSuffix);
         3485  +      p->term.n = nPrefix+nSuffix;
         3486  +      p->iOff += nSuffix;
         3487  +      if( p->iChild==0 ){
         3488  +        p->iOff += sqlite3Fts3GetVarint32(&p->aNode[p->iOff], &p->nDoclist);
         3489  +        p->aDoclist = &p->aNode[p->iOff];
         3490  +        p->iOff += p->nDoclist;
         3491  +      }
         3492  +    }
         3493  +  }
         3494  +
         3495  +  assert( p->iOff<=p->nNode );
         3496  +
         3497  +  return rc;
         3498  +}
         3499  +
         3500  +/*
         3501  +** Release all dynamic resources held by node-reader object *p.
         3502  +*/
         3503  +static void nodeReaderRelease(NodeReader *p){
         3504  +  sqlite3_free(p->term.a);
         3505  +}
         3506  +
         3507  +/*
         3508  +** Initialize a node-reader object to read the node in buffer aNode/nNode.
         3509  +**
         3510  +** If successful, SQLITE_OK is returned and the NodeReader object set to 
         3511  +** point to the first entry on the node (if any). Otherwise, an SQLite
         3512  +** error code is returned.
         3513  +*/
         3514  +static int nodeReaderInit(NodeReader *p, const char *aNode, int nNode){
         3515  +  memset(p, 0, sizeof(NodeReader));
         3516  +  p->aNode = aNode;
         3517  +  p->nNode = nNode;
         3518  +
         3519  +  /* Figure out if this is a leaf or an internal node. */
         3520  +  if( p->aNode[0] ){
         3521  +    /* An internal node. */
         3522  +    p->iOff = 1 + sqlite3Fts3GetVarint(&p->aNode[1], &p->iChild);
         3523  +  }else{
         3524  +    p->iOff = 1;
         3525  +  }
         3526  +
         3527  +  return nodeReaderNext(p);
         3528  +}
         3529  +
         3530  +/*
         3531  +** This function is called while writing an FTS segment each time a leaf o
         3532  +** node is finished and written to disk. The key (zTerm/nTerm) is guaranteed
         3533  +** to be greater than the largest key on the node just written, but smaller
         3534  +** than or equal to the first key that will be written to the next leaf
         3535  +** node.
         3536  +**
         3537  +** The block id of the leaf node just written to disk may be found in
         3538  +** (pWriter->aNodeWriter[0].iBlock) when this function is called.
         3539  +*/
         3540  +static int fts3IncrmergePush(
         3541  +  Fts3Table *p,                   /* Fts3 table handle */
         3542  +  IncrmergeWriter *pWriter,       /* Writer object */
         3543  +  const char *zTerm,              /* Term to write to internal node */
         3544  +  int nTerm                       /* Bytes at zTerm */
         3545  +){
         3546  +  sqlite3_int64 iPtr = pWriter->aNodeWriter[0].iBlock;
         3547  +  int iLayer;
         3548  +
         3549  +  assert( nTerm>0 );
         3550  +  for(iLayer=1; ALWAYS(iLayer<FTS_MAX_APPENDABLE_HEIGHT); iLayer++){
         3551  +    sqlite3_int64 iNextPtr = 0;
         3552  +    NodeWriter *pNode = &pWriter->aNodeWriter[iLayer];
         3553  +    int rc = SQLITE_OK;
         3554  +    int nPrefix;
         3555  +    int nSuffix;
         3556  +    int nSpace;
         3557  +
         3558  +    /* Figure out how much space the key will consume if it is written to
         3559  +    ** the current node of layer iLayer. Due to the prefix compression, 
         3560  +    ** the space required changes depending on which node the key is to
         3561  +    ** be added to.  */
         3562  +    nPrefix = fts3PrefixCompress(pNode->key.a, pNode->key.n, zTerm, nTerm);
         3563  +    nSuffix = nTerm - nPrefix;
         3564  +    nSpace  = sqlite3Fts3VarintLen(nPrefix);
         3565  +    nSpace += sqlite3Fts3VarintLen(nSuffix) + nSuffix;
         3566  +
         3567  +    if( pNode->key.n==0 || (pNode->block.n + nSpace)<=p->nNodeSize ){ 
         3568  +      /* If the current node of layer iLayer contains zero keys, or if adding
         3569  +      ** the key to it will not cause it to grow to larger than nNodeSize 
         3570  +      ** bytes in size, write the key here.  */
         3571  +
         3572  +      Blob *pBlk = &pNode->block;
         3573  +      if( pBlk->n==0 ){
         3574  +        blobGrowBuffer(pBlk, p->nNodeSize, &rc);
         3575  +        if( rc==SQLITE_OK ){
         3576  +          pBlk->a[0] = (char)iLayer;
         3577  +          pBlk->n = 1 + sqlite3Fts3PutVarint(&pBlk->a[1], iPtr);
         3578  +        }
         3579  +      }
         3580  +      blobGrowBuffer(pBlk, pBlk->n + nSpace, &rc);
         3581  +      blobGrowBuffer(&pNode->key, nTerm, &rc);
         3582  +
         3583  +      if( rc==SQLITE_OK ){
         3584  +        if( pNode->key.n ){
         3585  +          pBlk->n += sqlite3Fts3PutVarint(&pBlk->a[pBlk->n], nPrefix);
         3586  +        }
         3587  +        pBlk->n += sqlite3Fts3PutVarint(&pBlk->a[pBlk->n], nSuffix);
         3588  +        memcpy(&pBlk->a[pBlk->n], &zTerm[nPrefix], nSuffix);
         3589  +        pBlk->n += nSuffix;
         3590  +
         3591  +        memcpy(pNode->key.a, zTerm, nTerm);
         3592  +        pNode->key.n = nTerm;
         3593  +      }
         3594  +    }else{
         3595  +      /* Otherwise, flush the the current node of layer iLayer to disk.
         3596  +      ** Then allocate a new, empty sibling node. The key will be written
         3597  +      ** into the parent of this node. */
         3598  +      rc = fts3WriteSegment(p, pNode->iBlock, pNode->block.a, pNode->block.n);
         3599  +
         3600  +      assert( pNode->block.nAlloc>=p->nNodeSize );
         3601  +      pNode->block.a[0] = (char)iLayer;
         3602  +      pNode->block.n = 1 + sqlite3Fts3PutVarint(&pNode->block.a[1], iPtr+1);
         3603  +
         3604  +      iNextPtr = pNode->iBlock;
         3605  +      pNode->iBlock++;
         3606  +      pNode->key.n = 0;
         3607  +    }
         3608  +
         3609  +    if( rc!=SQLITE_OK || iNextPtr==0 ) return rc;
         3610  +    iPtr = iNextPtr;
         3611  +  }
         3612  +
         3613  +  assert( 0 );
         3614  +  return 0;
         3615  +}
         3616  +
         3617  +/*
         3618  +** Append a term and (optionally) doclist to the FTS segment node currently
         3619  +** stored in blob *pNode. The node need not contain any terms, but the
         3620  +** header must be written before this function is called.
         3621  +**
         3622  +** A node header is a single 0x00 byte for a leaf node, or a height varint
         3623  +** followed by the left-hand-child varint for an internal node.
         3624  +**
         3625  +** The term to be appended is passed via arguments zTerm/nTerm. For a 
         3626  +** leaf node, the doclist is passed as aDoclist/nDoclist. For an internal
         3627  +** node, both aDoclist and nDoclist must be passed 0.
         3628  +**
         3629  +** If the size of the value in blob pPrev is zero, then this is the first
         3630  +** term written to the node. Otherwise, pPrev contains a copy of the 
         3631  +** previous term. Before this function returns, it is updated to contain a
         3632  +** copy of zTerm/nTerm.
         3633  +**
         3634  +** It is assumed that the buffer associated with pNode is already large
         3635  +** enough to accommodate the new entry. The buffer associated with pPrev
         3636  +** is extended by this function if requrired.
         3637  +**
         3638  +** If an error (i.e. OOM condition) occurs, an SQLite error code is
         3639  +** returned. Otherwise, SQLITE_OK.
         3640  +*/
         3641  +static int fts3AppendToNode(
         3642  +  Blob *pNode,                    /* Current node image to append to */
         3643  +  Blob *pPrev,                    /* Buffer containing previous term written */
         3644  +  const char *zTerm,              /* New term to write */
         3645  +  int nTerm,                      /* Size of zTerm in bytes */
         3646  +  const char *aDoclist,           /* Doclist (or NULL) to write */
         3647  +  int nDoclist                    /* Size of aDoclist in bytes */ 
         3648  +){
         3649  +  int rc = SQLITE_OK;             /* Return code */
         3650  +  int bFirst = (pPrev->n==0);     /* True if this is the first term written */
         3651  +  int nPrefix;                    /* Size of term prefix in bytes */
         3652  +  int nSuffix;                    /* Size of term suffix in bytes */
         3653  +
         3654  +  /* Node must have already been started. There must be a doclist for a
         3655  +  ** leaf node, and there must not be a doclist for an internal node.  */
         3656  +  assert( pNode->n>0 );
         3657  +  assert( (pNode->a[0]=='\0')==(aDoclist!=0) );
         3658  +
         3659  +  blobGrowBuffer(pPrev, nTerm, &rc);
         3660  +  if( rc!=SQLITE_OK ) return rc;
         3661  +
         3662  +  nPrefix = fts3PrefixCompress(pPrev->a, pPrev->n, zTerm, nTerm);
         3663  +  nSuffix = nTerm - nPrefix;
         3664  +  memcpy(pPrev->a, zTerm, nTerm);
         3665  +  pPrev->n = nTerm;
         3666  +
         3667  +  if( bFirst==0 ){
         3668  +    pNode->n += sqlite3Fts3PutVarint(&pNode->a[pNode->n], nPrefix);
         3669  +  }
         3670  +  pNode->n += sqlite3Fts3PutVarint(&pNode->a[pNode->n], nSuffix);
         3671  +  memcpy(&pNode->a[pNode->n], &zTerm[nPrefix], nSuffix);
         3672  +  pNode->n += nSuffix;
         3673  +
         3674  +  if( aDoclist ){
         3675  +    pNode->n += sqlite3Fts3PutVarint(&pNode->a[pNode->n], nDoclist);
         3676  +    memcpy(&pNode->a[pNode->n], aDoclist, nDoclist);
         3677  +    pNode->n += nDoclist;
         3678  +  }
         3679  +
         3680  +  assert( pNode->n<=pNode->nAlloc );
         3681  +
         3682  +  return SQLITE_OK;
         3683  +}
         3684  +
         3685  +/*
         3686  +** Append the current term and doclist pointed to by cursor pCsr to the
         3687  +** appendable b-tree segment opened for writing by pWriter.
         3688  +**
         3689  +** Return SQLITE_OK if successful, or an SQLite error code otherwise.
         3690  +*/
         3691  +static int fts3IncrmergeAppend(
         3692  +  Fts3Table *p,                   /* Fts3 table handle */
         3693  +  IncrmergeWriter *pWriter,       /* Writer object */
         3694  +  Fts3MultiSegReader *pCsr        /* Cursor containing term and doclist */
         3695  +){
         3696  +  const char *zTerm = pCsr->zTerm;
         3697  +  int nTerm = pCsr->nTerm;
         3698  +  const char *aDoclist = pCsr->aDoclist;
         3699  +  int nDoclist = pCsr->nDoclist;
         3700  +  int rc = SQLITE_OK;           /* Return code */
         3701  +  int nSpace;                   /* Total space in bytes required on leaf */
         3702  +  int nPrefix;                  /* Size of prefix shared with previous term */
         3703  +  int nSuffix;                  /* Size of suffix (nTerm - nPrefix) */
         3704  +  NodeWriter *pLeaf;            /* Object used to write leaf nodes */
         3705  +
         3706  +  pLeaf = &pWriter->aNodeWriter[0];
         3707  +  nPrefix = fts3PrefixCompress(pLeaf->key.a, pLeaf->key.n, zTerm, nTerm);
         3708  +  nSuffix = nTerm - nPrefix;
         3709  +
         3710  +  nSpace  = sqlite3Fts3VarintLen(nPrefix);
         3711  +  nSpace += sqlite3Fts3VarintLen(nSuffix) + nSuffix;
         3712  +  nSpace += sqlite3Fts3VarintLen(nDoclist) + nDoclist;
         3713  +
         3714  +  /* If the current block is not empty, and if adding this term/doclist
         3715  +  ** to the current block would make it larger than Fts3Table.nNodeSize
         3716  +  ** bytes, write this block out to the database. */
         3717  +  if( pLeaf->block.n>0 && (pLeaf->block.n + nSpace)>p->nNodeSize ){
         3718  +    rc = fts3WriteSegment(p, pLeaf->iBlock, pLeaf->block.a, pLeaf->block.n);
         3719  +    pWriter->nWork++;
         3720  +
         3721  +    /* Add the current term to the parent node. The term added to the 
         3722  +    ** parent must:
         3723  +    **
         3724  +    **   a) be greater than the largest term on the leaf node just written
         3725  +    **      to the database (still available in pLeaf->key), and
         3726  +    **
         3727  +    **   b) be less than or equal to the term about to be added to the new
         3728  +    **      leaf node (zTerm/nTerm).
         3729  +    **
         3730  +    ** In other words, it must be the prefix of zTerm 1 byte longer than
         3731  +    ** the common prefix (if any) of zTerm and pWriter->zTerm.
         3732  +    */
         3733  +    if( rc==SQLITE_OK ){
         3734  +      rc = fts3IncrmergePush(p, pWriter, zTerm, nPrefix+1);
         3735  +    }
         3736  +
         3737  +    /* Advance to the next output block */
         3738  +    pLeaf->iBlock++;
         3739  +    pLeaf->key.n = 0;
         3740  +    pLeaf->block.n = 0;
         3741  +
         3742  +    nPrefix = 0;
         3743  +    nSuffix = nTerm;
         3744  +    nSpace  = 1;
         3745  +    nSpace += sqlite3Fts3VarintLen(nSuffix) + nSuffix;
         3746  +    nSpace += sqlite3Fts3VarintLen(nDoclist) + nDoclist;
         3747  +  }
         3748  +
         3749  +  blobGrowBuffer(&pLeaf->block, pLeaf->block.n + nSpace, &rc);
         3750  +
         3751  +  if( rc==SQLITE_OK ){
         3752  +    if( pLeaf->block.n==0 ){
         3753  +      pLeaf->block.n = 1;
         3754  +      pLeaf->block.a[0] = '\0';
         3755  +    }
         3756  +    rc = fts3AppendToNode(
         3757  +        &pLeaf->block, &pLeaf->key, zTerm, nTerm, aDoclist, nDoclist
         3758  +    );
         3759  +  }
         3760  +
         3761  +  return rc;
         3762  +}
         3763  +
         3764  +/*
         3765  +** This function is called to release all dynamic resources held by the
         3766  +** merge-writer object pWriter, and if no error has occurred, to flush
         3767  +** all outstanding node buffers held by pWriter to disk.
         3768  +**
         3769  +** If *pRc is not SQLITE_OK when this function is called, then no attempt
         3770  +** is made to write any data to disk. Instead, this function serves only
         3771  +** to release outstanding resources.
         3772  +**
         3773  +** Otherwise, if *pRc is initially SQLITE_OK and an error occurs while
         3774  +** flushing buffers to disk, *pRc is set to an SQLite error code before
         3775  +** returning.
         3776  +*/
         3777  +static void fts3IncrmergeRelease(
         3778  +  Fts3Table *p,                   /* FTS3 table handle */
         3779  +  IncrmergeWriter *pWriter,       /* Merge-writer object */
         3780  +  int *pRc                        /* IN/OUT: Error code */
         3781  +){
         3782  +  int i;                          /* Used to iterate through non-root layers */
         3783  +  int iRoot;                      /* Index of root in pWriter->aNodeWriter */
         3784  +  NodeWriter *pRoot;              /* NodeWriter for root node */
         3785  +  int rc = *pRc;                  /* Error code */
         3786  +
         3787  +  /* Set iRoot to the index in pWriter->aNodeWriter[] of the output segment 
         3788  +  ** root node. If the segment fits entirely on a single leaf node, iRoot
         3789  +  ** will be set to 0. If the root node is the parent of the leaves, iRoot
         3790  +  ** will be 1. And so on.  */
         3791  +  for(iRoot=FTS_MAX_APPENDABLE_HEIGHT-1; iRoot>=0; iRoot--){
         3792  +    NodeWriter *pNode = &pWriter->aNodeWriter[iRoot];
         3793  +    if( pNode->block.n>0 ) break;
         3794  +    assert( *pRc || pNode->block.nAlloc==0 );
         3795  +    assert( *pRc || pNode->key.nAlloc==0 );
         3796  +    sqlite3_free(pNode->block.a);
         3797  +    sqlite3_free(pNode->key.a);
         3798  +  }
         3799  +
         3800  +  /* Empty output segment. This is a no-op. */
         3801  +  if( iRoot<0 ) return;
         3802  +
         3803  +  /* The entire output segment fits on a single node. Normally, this means
         3804  +  ** the node would be stored as a blob in the "root" column of the %_segdir
         3805  +  ** table. However, this is not permitted in this case. The problem is that 
         3806  +  ** space has already been reserved in the %_segments table, and so the 
         3807  +  ** start_block and end_block fields of the %_segdir table must be populated. 
         3808  +  ** And, by design or by accident, released versions of FTS cannot handle 
         3809  +  ** segments that fit entirely on the root node with start_block!=0.
         3810  +  **
         3811  +  ** Instead, create a synthetic root node that contains nothing but a 
         3812  +  ** pointer to the single content node. So that the segment consists of a
         3813  +  ** single leaf and a single interior (root) node.
         3814  +  **
         3815  +  ** Todo: Better might be to defer allocating space in the %_segments 
         3816  +  ** table until we are sure it is needed.
         3817  +  */
         3818  +  if( iRoot==0 ){
         3819  +    Blob *pBlock = &pWriter->aNodeWriter[1].block;
         3820  +    blobGrowBuffer(pBlock, 1 + FTS3_VARINT_MAX, &rc);
         3821  +    if( rc==SQLITE_OK ){
         3822  +      pBlock->a[0] = 0x01;
         3823  +      pBlock->n = 1 + sqlite3Fts3PutVarint(
         3824  +          &pBlock->a[1], pWriter->aNodeWriter[0].iBlock
         3825  +      );
         3826  +    }
         3827  +    iRoot = 1;
         3828  +  }
         3829  +  pRoot = &pWriter->aNodeWriter[iRoot];
         3830  +
         3831  +  /* Flush all currently outstanding nodes to disk. */
         3832  +  for(i=0; i<iRoot; i++){
         3833  +    NodeWriter *pNode = &pWriter->aNodeWriter[i];
         3834  +    if( pNode->block.n>0 && rc==SQLITE_OK ){
         3835  +      rc = fts3WriteSegment(p, pNode->iBlock, pNode->block.a, pNode->block.n);
         3836  +    }
         3837  +    sqlite3_free(pNode->block.a);
         3838  +    sqlite3_free(pNode->key.a);
         3839  +  }
         3840  +
         3841  +  /* Write the %_segdir record. */
         3842  +  if( rc==SQLITE_OK ){
         3843  +    rc = fts3WriteSegdir(p, 
         3844  +        pWriter->iAbsLevel+1,               /* level */
         3845  +        pWriter->iIdx,                      /* idx */
         3846  +        pWriter->iStart,                    /* start_block */
         3847  +        pWriter->aNodeWriter[0].iBlock,     /* leaves_end_block */
         3848  +        pWriter->iEnd,                      /* end_block */
         3849  +        pRoot->block.a, pRoot->block.n      /* root */
         3850  +    );
         3851  +  }
         3852  +  sqlite3_free(pRoot->block.a);
         3853  +  sqlite3_free(pRoot->key.a);
         3854  +
         3855  +  *pRc = rc;
         3856  +}
         3857  +
         3858  +/*
         3859  +** Compare the term in buffer zLhs (size in bytes nLhs) with that in
         3860  +** zRhs (size in bytes nRhs) using memcmp. If one term is a prefix of
         3861  +** the other, it is considered to be smaller than the other.
         3862  +**
         3863  +** Return -ve if zLhs is smaller than zRhs, 0 if it is equal, or +ve
         3864  +** if it is greater.
         3865  +*/
         3866  +static int fts3TermCmp(
         3867  +  const char *zLhs, int nLhs,     /* LHS of comparison */
         3868  +  const char *zRhs, int nRhs      /* RHS of comparison */
         3869  +){
         3870  +  int nCmp = MIN(nLhs, nRhs);
         3871  +  int res;
         3872  +
         3873  +  res = memcmp(zLhs, zRhs, nCmp);
         3874  +  if( res==0 ) res = nLhs - nRhs;
         3875  +
         3876  +  return res;
         3877  +}
         3878  +
         3879  +
         3880  +/*
         3881  +** Query to see if the entry in the %_segments table with blockid iEnd is 
         3882  +** NULL. If no error occurs and the entry is NULL, set *pbRes 1 before
         3883  +** returning. Otherwise, set *pbRes to 0. 
         3884  +**
         3885  +** Or, if an error occurs while querying the database, return an SQLite 
         3886  +** error code. The final value of *pbRes is undefined in this case.
         3887  +**
         3888  +** This is used to test if a segment is an "appendable" segment. If it
         3889  +** is, then a NULL entry has been inserted into the %_segments table
         3890  +** with blockid %_segdir.end_block.
         3891  +*/
         3892  +static int fts3IsAppendable(Fts3Table *p, sqlite3_int64 iEnd, int *pbRes){
         3893  +  int bRes = 0;                   /* Result to set *pbRes to */
         3894  +  sqlite3_stmt *pCheck = 0;       /* Statement to query database with */
         3895  +  int rc;                         /* Return code */
         3896  +
         3897  +  rc = fts3SqlStmt(p, SQL_SEGMENT_IS_APPENDABLE, &pCheck, 0);
         3898  +  if( rc==SQLITE_OK ){
         3899  +    sqlite3_bind_int64(pCheck, 1, iEnd);
         3900  +    if( SQLITE_ROW==sqlite3_step(pCheck) ) bRes = 1;
         3901  +    rc = sqlite3_reset(pCheck);
         3902  +  }
         3903  +  
         3904  +  *pbRes = bRes;
         3905  +  return rc;
         3906  +}
         3907  +
         3908  +/*
         3909  +** This function is called when initializing an incremental-merge operation.
         3910  +** It checks if the existing segment with index value iIdx at absolute level 
         3911  +** (iAbsLevel+1) can be appended to by the incremental merge. If it can, the
         3912  +** merge-writer object *pWriter is initialized to write to it.
         3913  +**
         3914  +** An existing segment can be appended to by an incremental merge if:
         3915  +**
         3916  +**   * It was initially created as an appendable segment (with all required
         3917  +**     space pre-allocated), and
         3918  +**
         3919  +**   * The first key read from the input (arguments zKey and nKey) is 
         3920  +**     greater than the largest key currently stored in the potential
         3921  +**     output segment.
         3922  +*/
         3923  +static int fts3IncrmergeLoad(
         3924  +  Fts3Table *p,                   /* Fts3 table handle */
         3925  +  sqlite3_int64 iAbsLevel,        /* Absolute level of input segments */
         3926  +  int iIdx,                       /* Index of candidate output segment */
         3927  +  const char *zKey,               /* First key to write */
         3928  +  int nKey,                       /* Number of bytes in nKey */
         3929  +  IncrmergeWriter *pWriter        /* Populate this object */
         3930  +){
         3931  +  int rc;                         /* Return code */
         3932  +  sqlite3_stmt *pSelect = 0;      /* SELECT to read %_segdir entry */
         3933  +
         3934  +  rc = fts3SqlStmt(p, SQL_SELECT_SEGDIR, &pSelect, 0);
         3935  +  if( rc==SQLITE_OK ){
         3936  +    sqlite3_int64 iStart = 0;     /* Value of %_segdir.start_block */
         3937  +    sqlite3_int64 iLeafEnd = 0;   /* Value of %_segdir.leaves_end_block */
         3938  +    sqlite3_int64 iEnd = 0;       /* Value of %_segdir.end_block */
         3939  +    const char *aRoot = 0;        /* Pointer to %_segdir.root buffer */
         3940  +    int nRoot = 0;                /* Size of aRoot[] in bytes */
         3941  +    int rc2;                      /* Return code from sqlite3_reset() */
         3942  +    int bAppendable = 0;          /* Set to true if segment is appendable */
         3943  +
         3944  +    /* Read the %_segdir entry for index iIdx absolute level (iAbsLevel+1) */
         3945  +    sqlite3_bind_int64(pSelect, 1, iAbsLevel+1);
         3946  +    sqlite3_bind_int(pSelect, 2, iIdx);
         3947  +    if( sqlite3_step(pSelect)==SQLITE_ROW ){
         3948  +      iStart = sqlite3_column_int64(pSelect, 1);
         3949  +      iLeafEnd = sqlite3_column_int64(pSelect, 2);
         3950  +      iEnd = sqlite3_column_int64(pSelect, 3);
         3951  +      nRoot = sqlite3_column_bytes(pSelect, 4);
         3952  +      aRoot = sqlite3_column_blob(pSelect, 4);
         3953  +    }else{
         3954  +      return sqlite3_reset(pSelect);
         3955  +    }
         3956  +
         3957  +    /* Check for the zero-length marker in the %_segments table */
         3958  +    rc = fts3IsAppendable(p, iEnd, &bAppendable);
         3959  +
         3960  +    /* Check that zKey/nKey is larger than the largest key the candidate */
         3961  +    if( rc==SQLITE_OK && bAppendable ){
         3962  +      char *aLeaf = 0;
         3963  +      int nLeaf = 0;
         3964  +
         3965  +      rc = sqlite3Fts3ReadBlock(p, iLeafEnd, &aLeaf, &nLeaf, 0);
         3966  +      if( rc==SQLITE_OK ){
         3967  +        NodeReader reader;
         3968  +        for(rc = nodeReaderInit(&reader, aLeaf, nLeaf);
         3969  +            rc==SQLITE_OK && reader.aNode;
         3970  +            rc = nodeReaderNext(&reader)
         3971  +        ){
         3972  +          assert( reader.aNode );
         3973  +        }
         3974  +        if( fts3TermCmp(zKey, nKey, reader.term.a, reader.term.n)<=0 ){
         3975  +          bAppendable = 0;
         3976  +        }
         3977  +        nodeReaderRelease(&reader);
         3978  +      }
         3979  +      sqlite3_free(aLeaf);
         3980  +    }
         3981  +
         3982  +    if( rc==SQLITE_OK && bAppendable ){
         3983  +      /* It is possible to append to this segment. Set up the IncrmergeWriter
         3984  +      ** object to do so.  */
         3985  +      int i;
         3986  +      int nHeight = (int)aRoot[0];
         3987  +      NodeWriter *pNode;
         3988  +
         3989  +      pWriter->nLeafEst = ((iEnd - iStart) + 1) / FTS_MAX_APPENDABLE_HEIGHT;
         3990  +      pWriter->iStart = iStart;
         3991  +      pWriter->iEnd = iEnd;
         3992  +      pWriter->iAbsLevel = iAbsLevel;
         3993  +      pWriter->iIdx = iIdx;
         3994  +
         3995  +      for(i=nHeight+1; i<FTS_MAX_APPENDABLE_HEIGHT; i++){
         3996  +        pWriter->aNodeWriter[i].iBlock = pWriter->iStart + i*pWriter->nLeafEst;
         3997  +      }
         3998  +
         3999  +      pNode = &pWriter->aNodeWriter[nHeight];
         4000  +      pNode->iBlock = pWriter->iStart + pWriter->nLeafEst*nHeight;
         4001  +      blobGrowBuffer(&pNode->block, MAX(nRoot, p->nNodeSize), &rc);
         4002  +      if( rc==SQLITE_OK ){
         4003  +        memcpy(pNode->block.a, aRoot, nRoot);
         4004  +        pNode->block.n = nRoot;
         4005  +      }
         4006  +
         4007  +      for(i=nHeight; i>=0 && rc==SQLITE_OK; i--){
         4008  +        pNode = &pWriter->aNodeWriter[i];
         4009  +        NodeReader reader;
         4010  +
         4011  +        rc = nodeReaderInit(&reader, pNode->block.a, pNode->block.n);
         4012  +        while( reader.aNode && rc==SQLITE_OK ) rc = nodeReaderNext(&reader);
         4013  +        blobGrowBuffer(&pNode->key, reader.term.n, &rc);
         4014  +        if( rc==SQLITE_OK ){
         4015  +          memcpy(pNode->key.a, reader.term.a, reader.term.n);
         4016  +          pNode->key.n = reader.term.n;
         4017  +          if( i>0 ){
         4018  +            char *aBlock = 0;
         4019  +            int nBlock = 0;
         4020  +            pNode = &pWriter->aNodeWriter[i-1];
         4021  +            pNode->iBlock = reader.iChild;
         4022  +            rc = sqlite3Fts3ReadBlock(p, reader.iChild, &aBlock, &nBlock, 0);
         4023  +            blobGrowBuffer(&pNode->block, MAX(nBlock, p->nNodeSize), &rc);
         4024  +            if( rc==SQLITE_OK ){
         4025  +              memcpy(pNode->block.a, aBlock, nBlock);
         4026  +              pNode->block.n = nBlock;
         4027  +            }
         4028  +            sqlite3_free(aBlock);
         4029  +          }
         4030  +        }
         4031  +        nodeReaderRelease(&reader);
         4032  +      }
         4033  +    }
         4034  +
         4035  +    rc2 = sqlite3_reset(pSelect);
         4036  +    if( rc==SQLITE_OK ) rc = rc2;
         4037  +  }
         4038  +
         4039  +  return rc;
         4040  +}
         4041  +
         4042  +/*
         4043  +** Determine the largest segment index value that exists within absolute
         4044  +** level iAbsLevel+1. If no error occurs, set *piIdx to this value plus
         4045  +** one before returning SQLITE_OK. Or, if there are no segments at all 
         4046  +** within level iAbsLevel, set *piIdx to zero.
         4047  +**
         4048  +** If an error occurs, return an SQLite error code. The final value of
         4049  +** *piIdx is undefined in this case.
         4050  +*/
         4051  +static int fts3IncrmergeOutputIdx( 
         4052  +  Fts3Table *p,                   /* FTS Table handle */
         4053  +  sqlite3_int64 iAbsLevel,        /* Absolute index of input segments */
         4054  +  int *piIdx                      /* OUT: Next free index at iAbsLevel+1 */
         4055  +){
         4056  +  int rc;
         4057  +  sqlite3_stmt *pOutputIdx = 0;   /* SQL used to find output index */
         4058  +
         4059  +  rc = fts3SqlStmt(p, SQL_NEXT_SEGMENT_INDEX, &pOutputIdx, 0);
         4060  +  if( rc==SQLITE_OK ){
         4061  +    sqlite3_bind_int64(pOutputIdx, 1, iAbsLevel+1);
         4062  +    sqlite3_step(pOutputIdx);
         4063  +    *piIdx = sqlite3_column_int(pOutputIdx, 0);
         4064  +    rc = sqlite3_reset(pOutputIdx);
         4065  +  }
         4066  +
         4067  +  return rc;
         4068  +}
         4069  +
         4070  +/* 
         4071  +** Allocate an appendable output segment on absolute level iAbsLevel+1
         4072  +** with idx value iIdx.
         4073  +**
         4074  +** In the %_segdir table, a segment is defined by the values in three
         4075  +** columns:
         4076  +**
         4077  +**     start_block
         4078  +**     leaves_end_block
         4079  +**     end_block
         4080  +**
         4081  +** When an appendable segment is allocated, it is estimated that the
         4082  +** maximum number of leaf blocks that may be required is the sum of the
         4083  +** number of leaf blocks consumed by the input segments, plus the number
         4084  +** of input segments, multiplied by two. This value is stored in stack 
         4085  +** variable nLeafEst.
         4086  +**
         4087  +** A total of 16*nLeafEst blocks are allocated when an appendable segment
         4088  +** is created ((1 + end_block - start_block)==16*nLeafEst). The contiguous
         4089  +** array of leaf nodes starts at the first block allocated. The array
         4090  +** of interior nodes that are parents of the leaf nodes start at block
         4091  +** (start_block + (1 + end_block - start_block) / 16). And so on.
         4092  +**
         4093  +** In the actual code below, the value "16" is replaced with the 
         4094  +** pre-processor macro FTS_MAX_APPENDABLE_HEIGHT.
         4095  +*/
         4096  +static int fts3IncrmergeWriter( 
         4097  +  Fts3Table *p,                   /* Fts3 table handle */
         4098  +  sqlite3_int64 iAbsLevel,        /* Absolute level of input segments */
         4099  +  int iIdx,                       /* Index of new output segment */
         4100  +  Fts3MultiSegReader *pCsr,       /* Cursor that data will be read from */
         4101  +  IncrmergeWriter *pWriter        /* Populate this object */
         4102  +){
         4103  +  int rc;                         /* Return Code */
         4104  +  int i;                          /* Iterator variable */
         4105  +  int nLeafEst;                   /* Blocks allocated for leaf nodes */
         4106  +  sqlite3_stmt *pLeafEst = 0;     /* SQL used to determine nLeafEst */
         4107  +  sqlite3_stmt *pFirstBlock = 0;  /* SQL used to determine first block */
         4108  +
         4109  +  /* Calculate nLeafEst. */
         4110  +  rc = fts3SqlStmt(p, SQL_MAX_LEAF_NODE_ESTIMATE, &pLeafEst, 0);
         4111  +  if( rc==SQLITE_OK ){
         4112  +    sqlite3_bind_int64(pLeafEst, 1, iAbsLevel);
         4113  +    sqlite3_bind_int64(pLeafEst, 2, pCsr->nSegment);
         4114  +    if( SQLITE_ROW==sqlite3_step(pLeafEst) ){
         4115  +      nLeafEst = sqlite3_column_int(pLeafEst, 0);
         4116  +    }
         4117  +    rc = sqlite3_reset(pLeafEst);
         4118  +  }
         4119  +  if( rc!=SQLITE_OK ) return rc;
         4120  +
         4121  +  /* Calculate the first block to use in the output segment */
         4122  +  rc = fts3SqlStmt(p, SQL_NEXT_SEGMENTS_ID, &pFirstBlock, 0);
         4123  +  if( rc==SQLITE_OK ){
         4124  +    if( SQLITE_ROW==sqlite3_step(pFirstBlock) ){
         4125  +      pWriter->iStart = sqlite3_column_int64(pFirstBlock, 0);
         4126  +      pWriter->iEnd = pWriter->iStart - 1;
         4127  +      pWriter->iEnd += nLeafEst * FTS_MAX_APPENDABLE_HEIGHT;
         4128  +    }
         4129  +    rc = sqlite3_reset(pFirstBlock);
         4130  +  }
         4131  +  if( rc!=SQLITE_OK ) return rc;
         4132  +
         4133  +  /* Insert the marker in the %_segments table to make sure nobody tries
         4134  +  ** to steal the space just allocated. This is also used to identify 
         4135  +  ** appendable segments.  */
         4136  +  rc = fts3WriteSegment(p, pWriter->iEnd, 0, 0);
         4137  +  if( rc!=SQLITE_OK ) return rc;
         4138  +
         4139  +  pWriter->iAbsLevel = iAbsLevel;
         4140  +  pWriter->nLeafEst = nLeafEst;
         4141  +  pWriter->iIdx = iIdx;
         4142  +
         4143  +  /* Set up the array of NodeWriter objects */
         4144  +  for(i=0; i<FTS_MAX_APPENDABLE_HEIGHT; i++){
         4145  +    pWriter->aNodeWriter[i].iBlock = pWriter->iStart + i*pWriter->nLeafEst;
         4146  +  }
         4147  +  return SQLITE_OK;
         4148  +}
         4149  +
         4150  +/*
         4151  +** Remove an entry from the %_segdir table. This involves running the 
         4152  +** following two statements:
         4153  +**
         4154  +**   DELETE FROM %_segdir WHERE level = :iAbsLevel AND idx = :iIdx
         4155  +**   UPDATE %_segdir SET idx = idx - 1 WHERE level = :iAbsLevel AND idx > :iIdx
         4156  +**
         4157  +** The DELETE statement removes the specific %_segdir level. The UPDATE 
         4158  +** statement ensures that the remaining segments have contiguously allocated
         4159  +** idx values.
         4160  +*/
         4161  +static int fts3RemoveSegdirEntry(
         4162  +  Fts3Table *p,                   /* FTS3 table handle */
         4163  +  sqlite3_int64 iAbsLevel,        /* Absolute level to delete from */
         4164  +  int iIdx                        /* Index of %_segdir entry to delete */
         4165  +){
         4166  +  int rc;                         /* Return code */
         4167  +  sqlite3_stmt *pDelete = 0;      /* DELETE statement */
         4168  +
         4169  +  rc = fts3SqlStmt(p, SQL_DELETE_SEGDIR_ENTRY, &pDelete, 0);
         4170  +  if( rc==SQLITE_OK ){
         4171  +    sqlite3_bind_int64(pDelete, 1, iAbsLevel);
         4172  +    sqlite3_bind_int(pDelete, 2, iIdx);
         4173  +    sqlite3_step(pDelete);
         4174  +    rc = sqlite3_reset(pDelete);
         4175  +  }
         4176  +
         4177  +  return rc;
         4178  +}
         4179  +
         4180  +/*
         4181  +** One or more segments have just been removed from absolute level iAbsLevel.
         4182  +** Update the 'idx' values of the remaining segments in the level so that
         4183  +** the idx values are a contiguous sequence starting from 0.
         4184  +*/
         4185  +static int fts3RepackSegdirLevel(
         4186  +  Fts3Table *p,                   /* FTS3 table handle */
         4187  +  sqlite3_int64 iAbsLevel         /* Absolute level to repack */
         4188  +){
         4189  +  int rc;                         /* Return code */
         4190  +  int *aIdx = 0;                  /* Array of remaining idx values */
         4191  +  int nIdx = 0;                   /* Valid entries in aIdx[] */
         4192  +  int nAlloc = 0;                 /* Allocated size of aIdx[] */
         4193  +  int i;                          /* Iterator variable */
         4194  +  sqlite3_stmt *pSelect = 0;      /* Select statement to read idx values */
         4195  +  sqlite3_stmt *pUpdate = 0;      /* Update statement to modify idx values */
         4196  +
         4197  +  rc = fts3SqlStmt(p, SQL_SELECT_INDEXES, &pSelect, 0);
         4198  +  if( rc==SQLITE_OK ){
         4199  +    int rc2;
         4200  +    sqlite3_bind_int64(pSelect, 1, iAbsLevel);
         4201  +    while( SQLITE_ROW==sqlite3_step(pSelect) ){
         4202  +      if( nIdx>=nAlloc ){
         4203  +        int *aNew;
         4204  +        nAlloc += 16;
         4205  +        aNew = sqlite3_realloc(aIdx, nAlloc*sizeof(int));
         4206  +        if( !aNew ){
         4207  +          rc = SQLITE_NOMEM;
         4208  +          break;
         4209  +        }
         4210  +        aIdx = aNew;
         4211  +      }
         4212  +      aIdx[nIdx++] = sqlite3_column_int(pSelect, 0);
         4213  +    }
         4214  +    rc2 = sqlite3_reset(pSelect);
         4215  +    if( rc==SQLITE_OK ) rc = rc2;
         4216  +  }
         4217  +
         4218  +  if( rc==SQLITE_OK ){
         4219  +    rc = fts3SqlStmt(p, SQL_SHIFT_SEGDIR_ENTRY, &pUpdate, 0);
         4220  +  }
         4221  +  if( rc==SQLITE_OK ){
         4222  +    sqlite3_bind_int64(pUpdate, 2, iAbsLevel);
         4223  +  }
         4224  +
         4225  +  assert( p->bIgnoreSavepoint==0 );
         4226  +  p->bIgnoreSavepoint = 1;
         4227  +  for(i=0; rc==SQLITE_OK && i<nIdx; i++){
         4228  +    if( aIdx[i]!=i ){
         4229  +      sqlite3_bind_int(pUpdate, 3, aIdx[i]);
         4230  +      sqlite3_bind_int(pUpdate, 1, i);
         4231  +      sqlite3_step(pUpdate);
         4232  +      rc = sqlite3_reset(pUpdate);
         4233  +    }
         4234  +  }
         4235  +  p->bIgnoreSavepoint = 0;
         4236  +
         4237  +  sqlite3_free(aIdx);
         4238  +  return rc;
         4239  +}
         4240  +
         4241  +static void fts3StartNode(Blob *pNode, int iHeight, sqlite3_int64 iChild){
         4242  +  pNode->a[0] = (char)iHeight;
         4243  +  if( iChild ){
         4244  +    assert( pNode->nAlloc>=1+sqlite3Fts3VarintLen(iChild) );
         4245  +    pNode->n = 1 + sqlite3Fts3PutVarint(&pNode->a[1], iChild);
         4246  +  }else{
         4247  +    assert( pNode->nAlloc>=1 );
         4248  +    pNode->n = 1;
         4249  +  }
         4250  +}
         4251  +
         4252  +/*
         4253  +** The first two arguments are a pointer to and the size of a segment b-tree
         4254  +** node. The node may be a leaf or an internal node.
         4255  +**
         4256  +** This function creates a new node image in blob object *pNew by copying
         4257  +** all terms that are greater than or equal to zTerm/nTerm (for leaf nodes)
         4258  +** or greater than zTerm/nTerm (for internal nodes) from aNode/nNode.
         4259  +*/
         4260  +static int fts3TruncateNode(
         4261  +  const char *aNode,              /* Current node image */
         4262  +  int nNode,                      /* Size of aNode in bytes */
         4263  +  Blob *pNew,                     /* OUT: Write new node image here */
         4264  +  const char *zTerm,              /* Omit all terms smaller than this */
         4265  +  int nTerm,                      /* Size of zTerm in bytes */
         4266  +  sqlite3_int64 *piBlock          /* OUT: Block number in next layer down */
         4267  +){
         4268  +  NodeReader reader;              /* Reader object */
         4269  +  Blob prev = {0, 0, 0};          /* Previous term written to new node */
         4270  +  int rc = SQLITE_OK;             /* Return code */
         4271  +  int bLeaf = aNode[0]=='\0';     /* True for a leaf node */
         4272  +
         4273  +  /* Allocate required output space */
         4274  +  blobGrowBuffer(pNew, nNode, &rc);
         4275  +  if( rc!=SQLITE_OK ) return rc;
         4276  +  pNew->n = 0;
         4277  +
         4278  +  /* Populate new node buffer */
         4279  +  for(rc = nodeReaderInit(&reader, aNode, nNode); 
         4280  +      rc==SQLITE_OK && reader.aNode; 
         4281  +      rc = nodeReaderNext(&reader)
         4282  +  ){
         4283  +    if( pNew->n==0 ){
         4284  +      int res = fts3TermCmp(reader.term.a, reader.term.n, zTerm, nTerm);
         4285  +      if( res<0 || (bLeaf==0 && res==0) ) continue;
         4286  +      fts3StartNode(pNew, (int)aNode[0], reader.iChild);
         4287  +      *piBlock = reader.iChild;
         4288  +    }
         4289  +    rc = fts3AppendToNode(
         4290  +        pNew, &prev, reader.term.a, reader.term.n,
         4291  +        reader.aDoclist, reader.nDoclist
         4292  +    );
         4293  +    if( rc!=SQLITE_OK ) break;
         4294  +  }
         4295  +  if( pNew->n==0 ){
         4296  +    fts3StartNode(pNew, (int)aNode[0], reader.iChild);
         4297  +    *piBlock = reader.iChild;
         4298  +  }
         4299  +  assert( pNew->n<=pNew->nAlloc );
         4300  +
         4301  +  nodeReaderRelease(&reader);
         4302  +  sqlite3_free(prev.a);
         4303  +  return rc;
         4304  +}
         4305  +
         4306  +/*
         4307  +** Remove all terms smaller than zTerm/nTerm from segment iIdx in absolute 
         4308  +** level iAbsLevel. This may involve deleting entries from the %_segments
         4309  +** table, and modifying existing entries in both the %_segments and %_segdir
         4310  +** tables.
         4311  +**
         4312  +** SQLITE_OK is returned if the segment is updated successfully. Or an
         4313  +** SQLite error code otherwise.
         4314  +*/
         4315  +static int fts3TruncateSegment(
         4316  +  Fts3Table *p,                   /* FTS3 table handle */
         4317  +  sqlite3_int64 iAbsLevel,        /* Absolute level of segment to modify */
         4318  +  int iIdx,                       /* Index within level of segment to modify */
         4319  +  const char *zTerm,              /* Remove terms smaller than this */
         4320  +  int nTerm                      /* Number of bytes in buffer zTerm */
         4321  +){
         4322  +  int rc = SQLITE_OK;             /* Return code */
         4323  +  Blob root = {0,0,0};            /* New root page image */
         4324  +  Blob block = {0,0,0};           /* Buffer used for any other block */
         4325  +  sqlite3_int64 iBlock = 0;       /* Block id */
         4326  +  sqlite3_int64 iNewStart = 0;    /* New value for iStartBlock */
         4327  +  sqlite3_int64 iOldStart = 0;    /* Old value for iStartBlock */
         4328  +  sqlite3_stmt *pFetch = 0;       /* Statement used to fetch segdir */
         4329  +
         4330  +  rc = fts3SqlStmt(p, SQL_SELECT_SEGDIR, &pFetch, 0);
         4331  +  if( rc==SQLITE_OK ){
         4332  +    int rc2;                      /* sqlite3_reset() return code */
         4333  +    sqlite3_bind_int64(pFetch, 1, iAbsLevel);
         4334  +    sqlite3_bind_int(pFetch, 2, iIdx);
         4335  +    if( SQLITE_ROW==sqlite3_step(pFetch) ){
         4336  +      const char *aRoot = sqlite3_column_blob(pFetch, 4);
         4337  +      int nRoot = sqlite3_column_bytes(pFetch, 4);
         4338  +      iOldStart = sqlite3_column_int64(pFetch, 1);
         4339  +      rc = fts3TruncateNode(aRoot, nRoot, &root, zTerm, nTerm, &iBlock);
         4340  +    }
         4341  +    rc2 = sqlite3_reset(pFetch);
         4342  +    if( rc==SQLITE_OK ) rc = rc2;
         4343  +  }
         4344  +
         4345  +  while( rc==SQLITE_OK && iBlock ){
         4346  +    char *aBlock = 0;
         4347  +    int nBlock = 0;
         4348  +    iNewStart = iBlock;
         4349  +
         4350  +    rc = sqlite3Fts3ReadBlock(p, iBlock, &aBlock, &nBlock, 0);
         4351  +    if( rc==SQLITE_OK ){
         4352  +      rc = fts3TruncateNode(aBlock, nBlock, &block, zTerm, nTerm, &iBlock);
         4353  +    }
         4354  +    if( rc==SQLITE_OK ){
         4355  +      rc = fts3WriteSegment(p, iNewStart, block.a, block.n);
         4356  +    }
         4357  +    sqlite3_free(aBlock);
         4358  +  }
         4359  +
         4360  +  /* Variable iNewStart now contains the first valid leaf node. */
         4361  +  if( rc==SQLITE_OK && iNewStart ){
         4362  +    sqlite3_stmt *pDel = 0;
         4363  +    rc = fts3SqlStmt(p, SQL_DELETE_SEGMENTS_RANGE, &pDel, 0);
         4364  +    if( rc==SQLITE_OK ){
         4365  +      sqlite3_bind_int64(pDel, 1, iOldStart);
         4366  +      sqlite3_bind_int64(pDel, 2, iNewStart-1);
         4367  +      sqlite3_step(pDel);
         4368  +      rc = sqlite3_reset(pDel);
         4369  +    }
         4370  +  }
         4371  +
         4372  +  if( rc==SQLITE_OK ){
         4373  +    sqlite3_stmt *pChomp = 0;
         4374  +    rc = fts3SqlStmt(p, SQL_CHOMP_SEGDIR, &pChomp, 0);
         4375  +    if( rc==SQLITE_OK ){
         4376  +      sqlite3_bind_int64(pChomp, 1, iNewStart);
         4377  +      sqlite3_bind_blob(pChomp, 2, root.a, root.n, SQLITE_STATIC);
         4378  +      sqlite3_bind_int64(pChomp, 3, iAbsLevel);
         4379  +      sqlite3_bind_int(pChomp, 4, iIdx);
         4380  +      sqlite3_step(pChomp);
         4381  +      rc = sqlite3_reset(pChomp);
         4382  +    }
         4383  +  }
         4384  +
         4385  +  sqlite3_free(root.a);
         4386  +  sqlite3_free(block.a);
         4387  +  return rc;
         4388  +}
         4389  +
         4390  +/*
         4391  +** This function is called after an incrmental-merge operation has run to
         4392  +** merge (or partially merge) two or more segments from absolute level
         4393  +** iAbsLevel.
         4394  +**
         4395  +** Each input segment is either removed from the db completely (if all of
         4396  +** its data was copied to the output segment by the incrmerge operation)
         4397  +** or modified in place so that it no longer contains those entries that
         4398  +** have been duplicated in the output segment.
         4399  +*/
         4400  +static int fts3IncrmergeChomp(
         4401  +  Fts3Table *p,                   /* FTS table handle */
         4402  +  sqlite3_int64 iAbsLevel,        /* Absolute level containing segments */
         4403  +  Fts3MultiSegReader *pCsr,       /* Chomp all segments opened by this cursor */
         4404  +  int *pnRem                      /* Number of segments not deleted */
         4405  +){
         4406  +  int i;
         4407  +  int nRem = 0;
         4408  +  int rc = SQLITE_OK;
         4409  +
         4410  +  for(i=pCsr->nSegment-1; i>=0 && rc==SQLITE_OK; i--){
         4411  +    Fts3SegReader *pSeg = 0;
         4412  +    int j;
         4413  +
         4414  +    /* Find the Fts3SegReader object with Fts3SegReader.iIdx==i. It is hiding
         4415  +    ** somewhere in the pCsr->apSegment[] array.  */
         4416  +    for(j=0; ALWAYS(j<pCsr->nSegment); j++){
         4417  +      pSeg = pCsr->apSegment[j];
         4418  +      if( pSeg->iIdx==i ) break;
         4419  +    }
         4420  +    assert( j<pCsr->nSegment && pSeg->iIdx==i );
         4421  +
         4422  +    if( pSeg->aNode==0 ){
         4423  +      /* Seg-reader is at EOF. Remove the entire input segment. */
         4424  +      rc = fts3DeleteSegment(p, pSeg);
         4425  +      if( rc==SQLITE_OK ){
         4426  +        rc = fts3RemoveSegdirEntry(p, iAbsLevel, pSeg->iIdx);
         4427  +      }
         4428  +      *pnRem = 0;
         4429  +    }else{
         4430  +      /* The incremental merge did not copy all the data from this 
         4431  +      ** segment to the upper level. The segment is modified in place
         4432  +      ** so that it contains no keys smaller than zTerm/nTerm. */ 
         4433  +      const char *zTerm = pSeg->zTerm;
         4434  +      int nTerm = pSeg->nTerm;
         4435  +      rc = fts3TruncateSegment(p, iAbsLevel, pSeg->iIdx, zTerm, nTerm);
         4436  +      nRem++;
         4437  +    }
         4438  +  }
         4439  +
         4440  +  if( rc==SQLITE_OK && nRem!=pCsr->nSegment ){
         4441  +    rc = fts3RepackSegdirLevel(p, iAbsLevel);
         4442  +  }
         4443  +
         4444  +  *pnRem = nRem;
         4445  +  return rc;
         4446  +}
         4447  +
         4448  +/*
         4449  +** Store an incr-merge hint in the database.
         4450  +*/
         4451  +static int fts3IncrmergeHintStore(Fts3Table *p, Blob *pHint){
         4452  +  sqlite3_stmt *pReplace = 0;
         4453  +  int rc;                         /* Return code */
         4454  +
         4455  +  rc = fts3SqlStmt(p, SQL_REPLACE_STAT, &pReplace, 0);
         4456  +  if( rc==SQLITE_OK ){
         4457  +    sqlite3_bind_int(pReplace, 1, FTS_STAT_INCRMERGEHINT);
         4458  +    sqlite3_bind_blob(pReplace, 2, pHint->a, pHint->n, SQLITE_STATIC);
         4459  +    sqlite3_step(pReplace);
         4460  +    rc = sqlite3_reset(pReplace);
         4461  +  }
         4462  +
         4463  +  return rc;
         4464  +}
         4465  +
         4466  +/*
         4467  +** Load an incr-merge hint from the database. The incr-merge hint, if one 
         4468  +** exists, is stored in the rowid==1 row of the %_stat table.
         4469  +**
         4470  +** If successful, populate blob *pHint with the value read from the %_stat
         4471  +** table and return SQLITE_OK. Otherwise, if an error occurs, return an
         4472  +** SQLite error code.
         4473  +*/
         4474  +static int fts3IncrmergeHintLoad(Fts3Table *p, Blob *pHint){
         4475  +  sqlite3_stmt *pSelect = 0;
         4476  +  int rc;
         4477  +
         4478  +  pHint->n = 0;
         4479  +  rc = fts3SqlStmt(p, SQL_SELECT_STAT, &pSelect, 0);
         4480  +  if( rc==SQLITE_OK ){
         4481  +    int rc2;
         4482  +    sqlite3_bind_int(pSelect, 1, FTS_STAT_INCRMERGEHINT);
         4483  +    if( SQLITE_ROW==sqlite3_step(pSelect) ){
         4484  +      const char *aHint = sqlite3_column_blob(pSelect, 0);
         4485  +      int nHint = sqlite3_column_bytes(pSelect, 0);
         4486  +      if( aHint ){
         4487  +        blobGrowBuffer(pHint, nHint, &rc);
         4488  +        if( rc==SQLITE_OK ){
         4489  +          memcpy(pHint->a, aHint, nHint);
         4490  +          pHint->n = nHint;
         4491  +        }
         4492  +      }
         4493  +    }
         4494  +    rc2 = sqlite3_reset(pSelect);
         4495  +    if( rc==SQLITE_OK ) rc = rc2;
         4496  +  }
         4497  +
         4498  +  return rc;
         4499  +}
         4500  +
         4501  +/*
         4502  +** If *pRc is not SQLITE_OK when this function is called, it is a no-op.
         4503  +** Otherwise, append an entry to the hint stored in blob *pHint. Each entry
         4504  +** consists of two varints, the absolute level number of the input segments 
         4505  +** and the number of input segments.
         4506  +**
         4507  +** If successful, leave *pRc set to SQLITE_OK and return. If an error occurs,
         4508  +** set *pRc to an SQLite error code before returning.
         4509  +*/
         4510  +static void fts3IncrmergeHintPush(
         4511  +  Blob *pHint,                    /* Hint blob to append to */
         4512  +  i64 iAbsLevel,                  /* First varint to store in hint */
         4513  +  int nInput,                     /* Second varint to store in hint */
         4514  +  int *pRc                        /* IN/OUT: Error code */
         4515  +){
         4516  +  blobGrowBuffer(pHint, pHint->n + 2*FTS3_VARINT_MAX, pRc);
         4517  +  if( *pRc==SQLITE_OK ){
         4518  +    pHint->n += sqlite3Fts3PutVarint(&pHint->a[pHint->n], iAbsLevel);
         4519  +    pHint->n += sqlite3Fts3PutVarint(&pHint->a[pHint->n], (i64)nInput);
         4520  +  }
         4521  +}
         4522  +
         4523  +/*
         4524  +** Read the last entry (most recently pushed) from the hint blob *pHint
         4525  +** and then remove the entry. Write the two values read to *piAbsLevel and 
         4526  +** *pnInput before returning.
         4527  +**
         4528  +** If no error occurs, return SQLITE_OK. If the hint blob in *pHint does
         4529  +** not contain at least two valid varints, return SQLITE_CORRUPT_VTAB.
         4530  +*/
         4531  +static int fts3IncrmergeHintPop(Blob *pHint, i64 *piAbsLevel, int *pnInput){
         4532  +  const int nHint = pHint->n;
         4533  +  int i;
         4534  +
         4535  +  i = pHint->n-2;
         4536  +  while( i>0 && (pHint->a[i-1] & 0x80) ) i--;
         4537  +  while( i>0 && (pHint->a[i-1] & 0x80) ) i--;
         4538  +
         4539  +  pHint->n = i;
         4540  +  i += sqlite3Fts3GetVarint(&pHint->a[i], piAbsLevel);
         4541  +  i += sqlite3Fts3GetVarint32(&pHint->a[i], pnInput);
         4542  +  if( i!=nHint ) return SQLITE_CORRUPT_VTAB;
         4543  +
         4544  +  return SQLITE_OK;
         4545  +}
         4546  +
         4547  +
         4548  +/*
         4549  +** Attempt an incremental merge that writes nMerge leaf blocks.
         4550  +**
         4551  +** Incremental merges happen nMin segments at a time. The two
         4552  +** segments to be merged are the nMin oldest segments (the ones with
         4553  +** the smallest indexes) in the highest level that contains at least
         4554  +** nMin segments. Multiple merges might occur in an attempt to write the 
         4555  +** quota of nMerge leaf blocks.
         4556  +*/
         4557  +int sqlite3Fts3Incrmerge(Fts3Table *p, int nMerge, int nMin){
         4558  +  int rc;                         /* Return code */
         4559  +  int nRem = nMerge;              /* Number of leaf pages yet to  be written */
         4560  +  Fts3MultiSegReader *pCsr;       /* Cursor used to read input data */
         4561  +  Fts3SegFilter *pFilter;         /* Filter used with cursor pCsr */
         4562  +  IncrmergeWriter *pWriter;       /* Writer object */
         4563  +  int nSeg = 0;                   /* Number of input segments */
         4564  +  sqlite3_int64 iAbsLevel = 0;    /* Absolute level number to work on */
         4565  +  Blob hint = {0, 0, 0};          /* Hint read from %_stat table */
         4566  +  int bDirtyHint = 0;             /* True if blob 'hint' has been modified */
         4567  +
         4568  +  /* Allocate space for the cursor, filter and writer objects */
         4569  +  const int nAlloc = sizeof(*pCsr) + sizeof(*pFilter) + sizeof(*pWriter);
         4570  +  pWriter = (IncrmergeWriter *)sqlite3_malloc(nAlloc);
         4571  +  if( !pWriter ) return SQLITE_NOMEM;
         4572  +  pFilter = (Fts3SegFilter *)&pWriter[1];
         4573  +  pCsr = (Fts3MultiSegReader *)&pFilter[1];
         4574  +
         4575  +  rc = fts3IncrmergeHintLoad(p, &hint);
         4576  +  while( rc==SQLITE_OK && nRem>0 ){
         4577  +    const i64 nMod = FTS3_SEGDIR_MAXLEVEL * p->nIndex;
         4578  +    sqlite3_stmt *pFindLevel = 0; /* SQL used to determine iAbsLevel */
         4579  +    int bUseHint = 0;             /* True if attempting to append */
         4580  +
         4581  +    /* Search the %_segdir table for the absolute level with the smallest
         4582  +    ** relative level number that contains at least nMin segments, if any.
         4583  +    ** If one is found, set iAbsLevel to the absolute level number and
         4584  +    ** nSeg to nMin. If no level with at least nMin segments can be found, 
         4585  +    ** set nSeg to -1.
         4586  +    */
         4587  +    rc = fts3SqlStmt(p, SQL_FIND_MERGE_LEVEL, &pFindLevel, 0);
         4588  +    sqlite3_bind_int(pFindLevel, 1, nMin);
         4589  +    if( sqlite3_step(pFindLevel)==SQLITE_ROW ){
         4590  +      iAbsLevel = sqlite3_column_int64(pFindLevel, 0);
         4591  +      nSeg = nMin;
         4592  +    }else{
         4593  +      nSeg = -1;
         4594  +    }
         4595  +    rc = sqlite3_reset(pFindLevel);
         4596  +
         4597  +    /* If the hint read from the %_stat table is not empty, check if the
         4598  +    ** last entry in it specifies a relative level smaller than or equal
         4599  +    ** to the level identified by the block above (if any). If so, this 
         4600  +    ** iteration of the loop will work on merging at the hinted level.
         4601  +    */
         4602  +    if( rc==SQLITE_OK && hint.n ){
         4603  +      int nHint = hint.n;
         4604  +      sqlite3_int64 iHintAbsLevel = 0;      /* Hint level */
         4605  +      int nHintSeg = 0;                     /* Hint number of segments */
         4606  +
         4607  +      rc = fts3IncrmergeHintPop(&hint, &iHintAbsLevel, &nHintSeg);
         4608  +      if( nSeg<0 || (iAbsLevel % nMod) >= (iHintAbsLevel % nMod) ){
         4609  +        iAbsLevel = iHintAbsLevel;
         4610  +        nSeg = nHintSeg;
         4611  +        bUseHint = 1;
         4612  +        bDirtyHint = 1;
         4613  +      }else{
         4614  +        /* This undoes the effect of the HintPop() above - so that no entry
         4615  +        ** is removed from the hint blob.  */
         4616  +        hint.n = nHint;
         4617  +      }
         4618  +    }
         4619  +
         4620  +    /* If nSeg is less that zero, then there is no level with at least
         4621  +    ** nMin segments and no hint in the %_stat table. No work to do.
         4622  +    ** Exit early in this case.  */
         4623  +    if( nSeg<0 ) break;
         4624  +
         4625  +    /* Open a cursor to iterate through the contents of the oldest nSeg 
         4626  +    ** indexes of absolute level iAbsLevel. If this cursor is opened using 
         4627  +    ** the 'hint' parameters, it is possible that there are less than nSeg
         4628  +    ** segments available in level iAbsLevel. In this case, no work is
         4629  +    ** done on iAbsLevel - fall through to the next iteration of the loop 
         4630  +    ** to start work on some other level.  */
         4631  +    memset(pWriter, 0, nAlloc);
         4632  +    pFilter->flags = FTS3_SEGMENT_REQUIRE_POS;
         4633  +    if( rc==SQLITE_OK ){
         4634  +      rc = fts3IncrmergeCsr(p, iAbsLevel, nSeg, pCsr);
         4635  +    }
         4636  +    if( SQLITE_OK==rc && pCsr->nSegment==nSeg
         4637  +     && SQLITE_OK==(rc = sqlite3Fts3SegReaderStart(p, pCsr, pFilter))
         4638  +     && SQLITE_ROW==(rc = sqlite3Fts3SegReaderStep(p, pCsr))
         4639  +    ){
         4640  +      int iIdx = 0;               /* Largest idx in level (iAbsLevel+1) */
         4641  +      rc = fts3IncrmergeOutputIdx(p, iAbsLevel, &iIdx);
         4642  +      if( rc==SQLITE_OK ){
         4643  +        if( bUseHint && iIdx>0 ){
         4644  +          const char *zKey = pCsr->zTerm;
         4645  +          int nKey = pCsr->nTerm;
         4646  +          rc = fts3IncrmergeLoad(p, iAbsLevel, iIdx-1, zKey, nKey, pWriter);
         4647  +        }else{
         4648  +          rc = fts3IncrmergeWriter(p, iAbsLevel, iIdx, pCsr, pWriter);
         4649  +        }
         4650  +      }
         4651  +
         4652  +      if( rc==SQLITE_OK && pWriter->nLeafEst ){
         4653  +        fts3LogMerge(nSeg, iAbsLevel);
         4654  +        do {
         4655  +          rc = fts3IncrmergeAppend(p, pWriter, pCsr);
         4656  +          if( rc==SQLITE_OK ) rc = sqlite3Fts3SegReaderStep(p, pCsr);
         4657  +          if( pWriter->nWork>=nRem && rc==SQLITE_ROW ) rc = SQLITE_OK;
         4658  +        }while( rc==SQLITE_ROW );
         4659  +
         4660  +        /* Update or delete the input segments */
         4661  +        if( rc==SQLITE_OK ){
         4662  +          nRem -= (1 + pWriter->nWork);
         4663  +          rc = fts3IncrmergeChomp(p, iAbsLevel, pCsr, &nSeg);
         4664  +          if( nSeg!=0 ){
         4665  +            bDirtyHint = 1;
         4666  +            fts3IncrmergeHintPush(&hint, iAbsLevel, nSeg, &rc);
         4667  +          }
         4668  +        }
         4669  +      }
         4670  +
         4671  +      fts3IncrmergeRelease(p, pWriter, &rc);
         4672  +    }
         4673  +
         4674  +    sqlite3Fts3SegReaderFinish(pCsr);
         4675  +  }
         4676  +
         4677  +  /* Write the hint values into the %_stat table for the next incr-merger */
         4678  +  if( bDirtyHint && rc==SQLITE_OK ){
         4679  +    rc = fts3IncrmergeHintStore(p, &hint);
         4680  +  }
         4681  +
         4682  +  sqlite3_free(pWriter);
         4683  +  sqlite3_free(hint.a);
         4684  +  return rc;
         4685  +}
         4686  +
         4687  +/*
         4688  +** Convert the text beginning at *pz into an integer and return
         4689  +** its value.  Advance *pz to point to the first character past
         4690  +** the integer.
         4691  +*/
         4692  +static int fts3Getint(const char **pz){
         4693  +  const char *z = *pz;
         4694  +  int i = 0;
         4695  +  while( (*z)>='0' && (*z)<='9' ) i = 10*i + *(z++) - '0';
         4696  +  *pz = z;
         4697  +  return i;
         4698  +}
         4699  +
         4700  +/*
         4701  +** Process statements of the form:
         4702  +**
         4703  +**    INSERT INTO table(table) VALUES('merge=A,B');
         4704  +**
         4705  +** A and B are integers that decode to be the number of leaf pages
         4706  +** written for the merge, and the minimum number of segments on a level
         4707  +** before it will be selected for a merge, respectively.
         4708  +*/
         4709  +static int fts3DoIncrmerge(
         4710  +  Fts3Table *p,                   /* FTS3 table handle */
         4711  +  const char *zParam              /* Nul-terminated string containing "A,B" */
         4712  +){
         4713  +  int rc;
         4714  +  int nMin = (FTS3_MERGE_COUNT / 2);
         4715  +  int nMerge = 0;
         4716  +  const char *z = zParam;
         4717  +
         4718  +  /* Read the first integer value */
         4719  +  nMerge = fts3Getint(&z);
         4720  +
         4721  +  /* If the first integer value is followed by a ',',  read the second
         4722  +  ** integer value. */
         4723  +  if( z[0]==',' && z[1]!='\0' ){
         4724  +    z++;
         4725  +    nMin = fts3Getint(&z);
         4726  +  }
         4727  +
         4728  +  if( z[0]!='\0' || nMin<2 ){
         4729  +    rc = SQLITE_ERROR;
         4730  +  }else{
         4731  +    rc = SQLITE_OK;
         4732  +    if( !p->bHasStat ){
         4733  +      assert( p->bFts4==0 );
         4734  +      sqlite3Fts3CreateStatTable(&rc, p);
         4735  +    }
         4736  +    if( rc==SQLITE_OK ){
         4737  +      rc = sqlite3Fts3Incrmerge(p, nMerge, nMin);
         4738  +    }
         4739  +    sqlite3Fts3SegmentsClose(p);
         4740  +  }
         4741  +  return rc;
         4742  +}
         4743  +
         4744  +/*
         4745  +** Process statements of the form:
         4746  +**
         4747  +**    INSERT INTO table(table) VALUES('automerge=X');
         4748  +**
         4749  +** where X is an integer.  X==0 means to turn automerge off.  X!=0 means
         4750  +** turn it on.  The setting is persistent.
         4751  +*/
         4752  +static int fts3DoAutoincrmerge(
         4753  +  Fts3Table *p,                   /* FTS3 table handle */
         4754  +  const char *zParam              /* Nul-terminated string containing boolean */
         4755  +){
         4756  +  int rc = SQLITE_OK;
         4757  +  sqlite3_stmt *pStmt = 0;
         4758  +  p->bAutoincrmerge = fts3Getint(&zParam)!=0;
         4759  +  if( !p->bHasStat ){
         4760  +    assert( p->bFts4==0 );
         4761  +    sqlite3Fts3CreateStatTable(&rc, p);
         4762  +    if( rc ) return rc;
         4763  +  }
         4764  +  rc = fts3SqlStmt(p, SQL_REPLACE_STAT, &pStmt, 0);
         4765  +  if( rc ) return rc;;
         4766  +  sqlite3_bind_int(pStmt, 1, FTS_STAT_AUTOINCRMERGE);
         4767  +  sqlite3_bind_int(pStmt, 2, p->bAutoincrmerge);
         4768  +  sqlite3_step(pStmt);
         4769  +  rc = sqlite3_reset(pStmt);
         4770  +  return rc;
         4771  +}
         4772  +
         4773  +/*
         4774  +** Return a 64-bit checksum for the FTS index entry specified by the
         4775  +** arguments to this function.
         4776  +*/
         4777  +static u64 fts3ChecksumEntry(
         4778  +  const char *zTerm,              /* Pointer to buffer containing term */
         4779  +  int nTerm,                      /* Size of zTerm in bytes */
         4780  +  int iLangid,                    /* Language id for current row */
         4781  +  int iIndex,                     /* Index (0..Fts3Table.nIndex-1) */
         4782  +  i64 iDocid,                     /* Docid for current row. */
         4783  +  int iCol,                       /* Column number */
         4784  +  int iPos                        /* Position */
         4785  +){
         4786  +  int i;
         4787  +  u64 ret = (u64)iDocid;
         4788  +
         4789  +  ret += (ret<<3) + iLangid;
         4790  +  ret += (ret<<3) + iIndex;
         4791  +  ret += (ret<<3) + iCol;
         4792  +  ret += (ret<<3) + iPos;
         4793  +  for(i=0; i<nTerm; i++) ret += (ret<<3) + zTerm[i];
         4794  +
         4795  +  return ret;
         4796  +}
         4797  +
         4798  +/*
         4799  +** Return a checksum of all entries in the FTS index that correspond to
         4800  +** language id iLangid. The checksum is calculated by XORing the checksums
         4801  +** of each individual entry (see fts3ChecksumEntry()) together.
         4802  +**
         4803  +** If successful, the checksum value is returned and *pRc set to SQLITE_OK.
         4804  +** Otherwise, if an error occurs, *pRc is set to an SQLite error code. The
         4805  +** return value is undefined in this case.
         4806  +*/
         4807  +static u64 fts3ChecksumIndex(
         4808  +  Fts3Table *p,                   /* FTS3 table handle */
         4809  +  int iLangid,                    /* Language id to return cksum for */
         4810  +  int iIndex,                     /* Index to cksum (0..p->nIndex-1) */
         4811  +  int *pRc                        /* OUT: Return code */
         4812  +){
         4813  +  Fts3SegFilter filter;
         4814  +  Fts3MultiSegReader csr;
         4815  +  int rc;
         4816  +  u64 cksum = 0;
         4817  +
         4818  +  assert( *pRc==SQLITE_OK );
         4819  +
         4820  +  memset(&filter, 0, sizeof(filter));
         4821  +  memset(&csr, 0, sizeof(csr));
         4822  +  filter.flags =  FTS3_SEGMENT_REQUIRE_POS|FTS3_SEGMENT_IGNORE_EMPTY;
         4823  +  filter.flags |= FTS3_SEGMENT_SCAN;
         4824  +
         4825  +  rc = sqlite3Fts3SegReaderCursor(
         4826  +      p, iLangid, iIndex, FTS3_SEGCURSOR_ALL, 0, 0, 0, 1,&csr
         4827  +  );
         4828  +  if( rc==SQLITE_OK ){
         4829  +    rc = sqlite3Fts3SegReaderStart(p, &csr, &filter);
         4830  +  }
         4831  +
         4832  +  if( rc==SQLITE_OK ){
         4833  +    while( SQLITE_ROW==(rc = sqlite3Fts3SegReaderStep(p, &csr)) ){
         4834  +      char *pCsr = csr.aDoclist;
         4835  +      char *pEnd = &pCsr[csr.nDoclist];
         4836  +
         4837  +      i64 iDocid = 0;
         4838  +      i64 iCol = 0;
         4839  +      i64 iPos = 0;
         4840  +
         4841  +      pCsr += sqlite3Fts3GetVarint(pCsr, &iDocid);
         4842  +      while( pCsr<pEnd ){
         4843  +        i64 iVal = 0;
         4844  +        pCsr += sqlite3Fts3GetVarint(pCsr, &iVal);
         4845  +        if( pCsr<pEnd ){
         4846  +          if( iVal==0 || iVal==1 ){
         4847  +            iCol = 0;
         4848  +            iPos = 0;
         4849  +            if( iVal ){
         4850  +              pCsr += sqlite3Fts3GetVarint(pCsr, &iCol);
         4851  +            }else{
         4852  +              pCsr += sqlite3Fts3GetVarint(pCsr, &iVal);
         4853  +              iDocid += iVal;
         4854  +            }
         4855  +          }else{
         4856  +            iPos += (iVal - 2);
         4857  +            cksum = cksum ^ fts3ChecksumEntry(
         4858  +                csr.zTerm, csr.nTerm, iLangid, iIndex, iDocid, iCol, iPos
         4859  +            );
         4860  +          }
         4861  +        }
         4862  +      }
         4863  +    }
         4864  +  }
         4865  +  sqlite3Fts3SegReaderFinish(&csr);
         4866  +
         4867  +  *pRc = rc;
         4868  +  return cksum;
         4869  +}
         4870  +
         4871  +/*
         4872  +** Check if the contents of the FTS index match the current contents of the
         4873  +** content table. If no error occurs and the contents do match, set *pbOk
         4874  +** to true and return SQLITE_OK. Or if the contents do not match, set *pbOk
         4875  +** to false before returning.
         4876  +**
         4877  +** If an error occurs (e.g. an OOM or IO error), return an SQLite error 
         4878  +** code. The final value of *pbOk is undefined in this case.
         4879  +*/
         4880  +static int fts3IntegrityCheck(Fts3Table *p, int *pbOk){
         4881  +  int rc = SQLITE_OK;             /* Return code */
         4882  +  u64 cksum1 = 0;                 /* Checksum based on FTS index contents */
         4883  +  u64 cksum2 = 0;                 /* Checksum based on %_content contents */
         4884  +  sqlite3_stmt *pAllLangid = 0;   /* Statement to return all language-ids */
         4885  +
         4886  +  /* This block calculates the checksum according to the FTS index. */
         4887  +  rc = fts3SqlStmt(p, SQL_SELECT_ALL_LANGID, &pAllLangid, 0);
         4888  +  if( rc==SQLITE_OK ){
         4889  +    int rc2;
         4890  +    sqlite3_bind_int(pAllLangid, 1, p->nIndex);
         4891  +    while( rc==SQLITE_OK && sqlite3_step(pAllLangid)==SQLITE_ROW ){
         4892  +      int iLangid = sqlite3_column_int(pAllLangid, 0);
         4893  +      int i;
         4894  +      for(i=0; i<p->nIndex; i++){
         4895  +        cksum1 = cksum1 ^ fts3ChecksumIndex(p, iLangid, i, &rc);
         4896  +      }
         4897  +    }
         4898  +    rc2 = sqlite3_reset(pAllLangid);
         4899  +    if( rc==SQLITE_OK ) rc = rc2;
         4900  +  }
         4901  +
         4902  +  /* This block calculates the checksum according to the %_content table */
         4903  +  rc = fts3SqlStmt(p, SQL_SELECT_ALL_LANGID, &pAllLangid, 0);
         4904  +  if( rc==SQLITE_OK ){
         4905  +    sqlite3_tokenizer_module const *pModule = p->pTokenizer->pModule;
         4906  +    sqlite3_stmt *pStmt = 0;
         4907  +    char *zSql;
         4908  +   
         4909  +    zSql = sqlite3_mprintf("SELECT %s" , p->zReadExprlist);
         4910  +    if( !zSql ){
         4911  +      rc = SQLITE_NOMEM;
         4912  +    }else{
         4913  +      rc = sqlite3_prepare_v2(p->db, zSql, -1, &pStmt, 0);
         4914  +      sqlite3_free(zSql);
         4915  +    }
         4916  +
         4917  +    while( rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(pStmt) ){
         4918  +      i64 iDocid = sqlite3_column_int64(pStmt, 0);
         4919  +      int iLang = langidFromSelect(p, pStmt);
         4920  +      int iCol;
         4921  +
         4922  +      for(iCol=0; rc==SQLITE_OK && iCol<p->nColumn; iCol++){
         4923  +        const char *zText = (const char *)sqlite3_column_text(pStmt, iCol+1);
         4924  +        int nText = sqlite3_column_bytes(pStmt, iCol+1);
         4925  +        sqlite3_tokenizer_cursor *pT = 0;
         4926  +
         4927  +        rc = sqlite3Fts3OpenTokenizer(p->pTokenizer, iLang, zText, nText, &pT);
         4928  +        while( rc==SQLITE_OK ){
         4929  +          char const *zToken;       /* Buffer containing token */
         4930  +          int nToken;               /* Number of bytes in token */
         4931  +          int iDum1, iDum2;         /* Dummy variables */
         4932  +          int iPos;                 /* Position of token in zText */
         4933  +
         4934  +          rc = pModule->xNext(pT, &zToken, &nToken, &iDum1, &iDum2, &iPos);
         4935  +          if( rc==SQLITE_OK ){
         4936  +            int i;
         4937  +            cksum2 = cksum2 ^ fts3ChecksumEntry(
         4938  +                zToken, nToken, iLang, 0, iDocid, iCol, iPos
         4939  +            );
         4940  +            for(i=1; i<p->nIndex; i++){
         4941  +              if( p->aIndex[i].nPrefix<=nToken ){
         4942  +                cksum2 = cksum2 ^ fts3ChecksumEntry(
         4943  +                  zToken, p->aIndex[i].nPrefix, iLang, i, iDocid, iCol, iPos
         4944  +                );
         4945  +              }
         4946  +            }
         4947  +          }
         4948  +        }
         4949  +        if( pT ) pModule->xClose(pT);
         4950  +        if( rc==SQLITE_DONE ) rc = SQLITE_OK;
         4951  +      }
         4952  +    }
         4953  +
         4954  +    sqlite3_finalize(pStmt);
         4955  +  }
         4956  +
         4957  +  *pbOk = (cksum1==cksum2);
         4958  +  return rc;
         4959  +}
         4960  +
         4961  +/*
         4962  +** Run the integrity-check. If no error occurs and the current contents of
         4963  +** the FTS index are correct, return SQLITE_OK. Or, if the contents of the
         4964  +** FTS index are incorrect, return SQLITE_CORRUPT_VTAB.
         4965  +**
         4966  +** Or, if an error (e.g. an OOM or IO error) occurs, return an SQLite 
         4967  +** error code.
         4968  +**
         4969  +** The integrity-check works as follows. For each token and indexed token
         4970  +** prefix in the document set, a 64-bit checksum is calculated (by code
         4971  +** in fts3ChecksumEntry()) based on the following:
         4972  +**
         4973  +**     + The index number (0 for the main index, 1 for the first prefix
         4974  +**       index etc.),
         4975  +**     + The token (or token prefix) text itself, 
         4976  +**     + The language-id of the row it appears in,
         4977  +**     + The docid of the row it appears in,
         4978  +**     + The column it appears in, and
         4979  +**     + The tokens position within that column.
         4980  +**
         4981  +** The checksums for all entries in the index are XORed together to create
         4982  +** a single checksum for the entire index.
         4983  +**
         4984  +** The integrity-check code calculates the same checksum in two ways:
         4985  +**
         4986  +**     1. By scanning the contents of the FTS index, and 
         4987  +**     2. By scanning and tokenizing the content table.
         4988  +**
         4989  +** If the two checksums are identical, the integrity-check is deemed to have
         4990  +** passed.
         4991  +*/
         4992  +static int fts3DoIntegrityCheck(
         4993  +  Fts3Table *p                    /* FTS3 table handle */
         4994  +){
         4995  +  int rc;
         4996  +  int bOk = 0;
         4997  +  rc = fts3IntegrityCheck(p, &bOk);
         4998  +  if( rc==SQLITE_OK && bOk==0 ) rc = SQLITE_CORRUPT_VTAB;
         4999  +  return rc;
         5000  +}
         5001  +
  3173   5002   /*
  3174   5003   ** Handle a 'special' INSERT of the form:
  3175   5004   **
  3176   5005   **   "INSERT INTO tbl(tbl) VALUES(<expr>)"
  3177   5006   **
  3178   5007   ** Argument pVal contains the result of <expr>. Currently the only 
  3179   5008   ** meaningful value to insert is the text 'optimize'.
................................................................................
  3185   5014   
  3186   5015     if( !zVal ){
  3187   5016       return SQLITE_NOMEM;
  3188   5017     }else if( nVal==8 && 0==sqlite3_strnicmp(zVal, "optimize", 8) ){
  3189   5018       rc = fts3DoOptimize(p, 0);
  3190   5019     }else if( nVal==7 && 0==sqlite3_strnicmp(zVal, "rebuild", 7) ){
  3191   5020       rc = fts3DoRebuild(p);
         5021  +  }else if( nVal==15 && 0==sqlite3_strnicmp(zVal, "integrity-check", 15) ){
         5022  +    rc = fts3DoIntegrityCheck(p);
         5023  +  }else if( nVal>6 && 0==sqlite3_strnicmp(zVal, "merge=", 6) ){
         5024  +    rc = fts3DoIncrmerge(p, &zVal[6]);
         5025  +  }else if( nVal>10 && 0==sqlite3_strnicmp(zVal, "automerge=", 10) ){
         5026  +    rc = fts3DoAutoincrmerge(p, &zVal[10]);
  3192   5027   #ifdef SQLITE_TEST
  3193   5028     }else if( nVal>9 && 0==sqlite3_strnicmp(zVal, "nodesize=", 9) ){
  3194   5029       p->nNodeSize = atoi(&zVal[9]);
  3195   5030       rc = SQLITE_OK;
  3196   5031     }else if( nVal>11 && 0==sqlite3_strnicmp(zVal, "maxpending=", 9) ){
  3197   5032       p->nMaxPendingData = atoi(&zVal[11]);
  3198   5033       rc = SQLITE_OK;
................................................................................
  3380   5215   }
  3381   5216   
  3382   5217   /*
  3383   5218   ** This function does the work for the xUpdate method of FTS3 virtual
  3384   5219   ** tables. The schema of the virtual table being:
  3385   5220   **
  3386   5221   **     CREATE TABLE <table name>( 
  3387         -**       <user COLUMns>,
         5222  +**       <user columns>,
  3388   5223   **       <table name> HIDDEN, 
  3389   5224   **       docid HIDDEN, 
  3390   5225   **       <langid> HIDDEN
  3391   5226   **     );
  3392   5227   **
  3393   5228   ** 
  3394   5229   */
................................................................................
  3512   5347       }
  3513   5348       if( p->bHasDocsize ){
  3514   5349         fts3InsertDocsize(&rc, p, aSzIns);
  3515   5350       }
  3516   5351       nChng++;
  3517   5352     }
  3518   5353   
  3519         -  if( p->bHasStat ){
         5354  +  if( p->bFts4 ){
  3520   5355       fts3UpdateDocTotals(&rc, p, aSzIns, aSzDel, nChng);
  3521   5356     }
  3522   5357   
  3523   5358    update_out:
  3524   5359     sqlite3_free(aSzIns);
  3525   5360     sqlite3Fts3SegmentsClose(p);
  3526   5361     return rc;

Added ext/fts3/tool/fts3view.c.

            1  +/*
            2  +** This program is a debugging and analysis utility that displays
            3  +** information about an FTS3 or FTS4 index.
            4  +**
            5  +** Link this program against the SQLite3 amalgamation with the
            6  +** SQLITE_ENABLE_FTS4 compile-time option.  Then run it as:
            7  +**
            8  +**    fts3view DATABASE
            9  +**
           10  +** to get a list of all FTS3/4 tables in DATABASE, or do
           11  +**
           12  +**    fts3view DATABASE TABLE COMMAND ....
           13  +**
           14  +** to see various aspects of the TABLE table.  Type fts3view with no
           15  +** arguments for a list of available COMMANDs.
           16  +*/
           17  +#include <stdio.h>
           18  +#include <stdarg.h>
           19  +#include <stdlib.h>
           20  +#include <string.h>
           21  +#include <ctype.h>
           22  +#include "sqlite3.h"
           23  +
           24  +/*
           25  +** Extra command-line arguments:
           26  +*/
           27  +int nExtra;
           28  +char **azExtra;
           29  +
           30  +/*
           31  +** Look for a command-line argument.
           32  +*/
           33  +const char *findOption(const char *zName, int hasArg, const char *zDefault){
           34  +  int i;
           35  +  const char *zResult = zDefault;
           36  +  for(i=0; i<nExtra; i++){
           37  +    const char *z = azExtra[i];
           38  +    while( z[0]=='-' ) z++;
           39  +    if( strcmp(z, zName)==0 ){
           40  +      int j = 1;
           41  +      if( hasArg==0 || i==nExtra-1 ) j = 0;
           42  +      zResult = azExtra[i+j];
           43  +      while( i+j<nExtra ){
           44  +        azExtra[i] = azExtra[i+j+1];
           45  +        i++;
           46  +      }
           47  +      break;
           48  +    }
           49  +  }
           50  +  return zResult;       
           51  +}
           52  +
           53  +
           54  +/*
           55  +** Prepare an SQL query
           56  +*/
           57  +static sqlite3_stmt *prepare(sqlite3 *db, const char *zFormat, ...){
           58  +  va_list ap;
           59  +  char *zSql;
           60  +  sqlite3_stmt *pStmt;
           61  +  int rc;
           62  +
           63  +  va_start(ap, zFormat);
           64  +  zSql = sqlite3_vmprintf(zFormat, ap);
           65  +  va_end(ap);
           66  +  rc = sqlite3_prepare_v2(db, zSql, -1, &pStmt, 0);
           67  +  if( rc ){
           68  +    fprintf(stderr, "Error: %s\nSQL: %s\n", sqlite3_errmsg(db), zSql);
           69  +    exit(1);
           70  +  }
           71  +  sqlite3_free(zSql);
           72  +  return pStmt;
           73  +}
           74  +
           75  +/*
           76  +** Run an SQL statement
           77  +*/
           78  +static int runSql(sqlite3 *db, const char *zFormat, ...){
           79  +  va_list ap;
           80  +  char *zSql;
           81  +  int rc;
           82  +
           83  +  va_start(ap, zFormat);
           84  +  zSql = sqlite3_vmprintf(zFormat, ap);
           85  +  rc = sqlite3_exec(db, zSql, 0, 0, 0);
           86  +  va_end(ap);
           87  +  return rc;
           88  +}
           89  +
           90  +/*
           91  +** Show the table schema
           92  +*/
           93  +static void showSchema(sqlite3 *db, const char *zTab){
           94  +  sqlite3_stmt *pStmt;
           95  +  pStmt = prepare(db,
           96  +            "SELECT sql FROM sqlite_master"
           97  +            " WHERE name LIKE '%q%%'"
           98  +            " ORDER BY 1",
           99  +            zTab);
          100  +  while( sqlite3_step(pStmt)==SQLITE_ROW ){
          101  +    printf("%s;\n", sqlite3_column_text(pStmt, 0));
          102  +  }
          103  +  sqlite3_finalize(pStmt);
          104  +  pStmt = prepare(db, "PRAGMA page_size");
          105  +  while( sqlite3_step(pStmt)==SQLITE_ROW ){
          106  +    printf("PRAGMA page_size=%s;\n", sqlite3_column_text(pStmt, 0));
          107  +  }
          108  +  sqlite3_finalize(pStmt);
          109  +  pStmt = prepare(db, "PRAGMA journal_mode");
          110  +  while( sqlite3_step(pStmt)==SQLITE_ROW ){
          111  +    printf("PRAGMA journal_mode=%s;\n", sqlite3_column_text(pStmt, 0));
          112  +  }
          113  +  sqlite3_finalize(pStmt);
          114  +  pStmt = prepare(db, "PRAGMA auto_vacuum");
          115  +  while( sqlite3_step(pStmt)==SQLITE_ROW ){
          116  +    const char *zType = "???";
          117  +    switch( sqlite3_column_int(pStmt, 0) ){
          118  +      case 0:  zType = "OFF";         break;
          119  +      case 1:  zType = "FULL";        break;
          120  +      case 2:  zType = "INCREMENTAL"; break;
          121  +    }
          122  +    printf("PRAGMA auto_vacuum=%s;\n", zType);
          123  +  }
          124  +  sqlite3_finalize(pStmt);
          125  +  pStmt = prepare(db, "PRAGMA encoding");
          126  +  while( sqlite3_step(pStmt)==SQLITE_ROW ){
          127  +    printf("PRAGMA encoding=%s;\n", sqlite3_column_text(pStmt, 0));
          128  +  }
          129  +  sqlite3_finalize(pStmt);
          130  +}
          131  +
          132  +/* 
          133  +** Read a 64-bit variable-length integer from memory starting at p[0].
          134  +** Return the number of bytes read, or 0 on error.
          135  +** The value is stored in *v.
          136  +*/
          137  +int getVarint(const unsigned char *p, sqlite_int64 *v){
          138  +  const unsigned char *q = p;
          139  +  sqlite_uint64 x = 0, y = 1;
          140  +  while( (*q&0x80)==0x80 && q-(unsigned char *)p<9 ){
          141  +    x += y * (*q++ & 0x7f);
          142  +    y <<= 7;
          143  +  }
          144  +  x += y * (*q++);
          145  +  *v = (sqlite_int64) x;
          146  +  return (int) (q - (unsigned char *)p);
          147  +}
          148  +
          149  +
          150  +/* Show the content of the %_stat table
          151  +*/
          152  +static void showStat(sqlite3 *db, const char *zTab){
          153  +  sqlite3_stmt *pStmt;
          154  +  pStmt = prepare(db, "SELECT id, value FROM '%q_stat'", zTab);
          155  +  while( sqlite3_step(pStmt)==SQLITE_ROW ){
          156  +    printf("stat[%d] =", sqlite3_column_int(pStmt, 0));
          157  +    switch( sqlite3_column_type(pStmt, 1) ){
          158  +      case SQLITE_INTEGER: {
          159  +        printf(" %d\n", sqlite3_column_int(pStmt, 1));
          160  +        break;
          161  +      }
          162  +      case SQLITE_BLOB: {
          163  +        unsigned char *x = (unsigned char*)sqlite3_column_blob(pStmt, 1);
          164  +        int len = sqlite3_column_bytes(pStmt, 1);
          165  +        int i = 0;
          166  +        sqlite3_int64 v;
          167  +        while( i<len ){
          168  +          i += getVarint(x, &v);
          169  +          printf(" %lld", v);
          170  +        }
          171  +        printf("\n");
          172  +        break;
          173  +      }
          174  +    }
          175  +  }
          176  +  sqlite3_finalize(pStmt);
          177  +}
          178  +
          179  +/*
          180  +** Report on the vocabulary.  This creates an fts4aux table with a random
          181  +** name, but deletes it in the end.
          182  +*/
          183  +static void showVocabulary(sqlite3 *db, const char *zTab){
          184  +  char *zAux;
          185  +  sqlite3_uint64 r;
          186  +  sqlite3_stmt *pStmt;
          187  +  int nDoc = 0;
          188  +  int nToken = 0;
          189  +  int nOccurrence = 0;
          190  +  int nTop;
          191  +  int n, i;
          192  +
          193  +  sqlite3_randomness(sizeof(r), &r);
          194  +  zAux = sqlite3_mprintf("viewer_%llx", zTab, r);
          195  +  runSql(db, "BEGIN");
          196  +  pStmt = prepare(db, "SELECT count(*) FROM %Q", zTab);
          197  +  while( sqlite3_step(pStmt)==SQLITE_ROW ){
          198  +    nDoc = sqlite3_column_int(pStmt, 0);
          199  +  }
          200  +  sqlite3_finalize(pStmt);
          201  +  printf("Number of documents...................... %9d\n", nDoc);
          202  +
          203  +  runSql(db, "CREATE VIRTUAL TABLE %s USING fts4aux(%Q)", zAux, zTab);
          204  +  pStmt = prepare(db, 
          205  +             "SELECT count(*), sum(occurrences) FROM %s WHERE col='*'",
          206  +             zAux);
          207  +  while( sqlite3_step(pStmt)==SQLITE_ROW ){
          208  +    nToken = sqlite3_column_int(pStmt, 0);
          209  +    nOccurrence = sqlite3_column_int(pStmt, 1);
          210  +  }
          211  +  sqlite3_finalize(pStmt);
          212  +  printf("Total tokens in all documents............ %9d\n", nOccurrence);
          213  +  printf("Total number of distinct tokens.......... %9d\n", nToken);
          214  +  if( nToken==0 ) goto end_vocab;
          215  +
          216  +  n = 0;
          217  +  pStmt = prepare(db, "SELECT count(*) FROM %s"
          218  +                      " WHERE col='*' AND occurrences==1", zAux);
          219  +  while( sqlite3_step(pStmt)==SQLITE_ROW ){
          220  +    n = sqlite3_column_int(pStmt, 0);
          221  +  }
          222  +  sqlite3_finalize(pStmt);
          223  +  printf("Tokens used exactly once................. %9d %5.2f%%\n",
          224  +          n, n*100.0/nToken);
          225  +
          226  +  n = 0;
          227  +  pStmt = prepare(db, "SELECT count(*) FROM %s"
          228  +                      " WHERE col='*' AND documents==1", zAux);
          229  +  while( sqlite3_step(pStmt)==SQLITE_ROW ){
          230  +    n = sqlite3_column_int(pStmt, 0);
          231  +  }
          232  +  sqlite3_finalize(pStmt);
          233  +  printf("Tokens used in only one document......... %9d %5.2f%%\n",
          234  +          n, n*100.0/nToken);
          235  +
          236  +  if( nDoc>=2000 ){
          237  +    n = 0;
          238  +    pStmt = prepare(db, "SELECT count(*) FROM %s"
          239  +                        " WHERE col='*' AND occurrences<=%d", zAux, nDoc/1000);
          240  +    while( sqlite3_step(pStmt)==SQLITE_ROW ){
          241  +      n = sqlite3_column_int(pStmt, 0);
          242  +    }
          243  +    sqlite3_finalize(pStmt);
          244  +    printf("Tokens used in 0.1%% or less of docs...... %9d %5.2f%%\n",
          245  +            n, n*100.0/nToken);
          246  +  }
          247  +
          248  +  if( nDoc>=200 ){
          249  +    n = 0;
          250  +    pStmt = prepare(db, "SELECT count(*) FROM %s"
          251  +                        " WHERE col='*' AND occurrences<=%d", zAux, nDoc/100);
          252  +    while( sqlite3_step(pStmt)==SQLITE_ROW ){
          253  +      n = sqlite3_column_int(pStmt, 0);
          254  +    }
          255  +    sqlite3_finalize(pStmt);
          256  +    printf("Tokens used in 1%% or less of docs........ %9d %5.2f%%\n",
          257  +            n, n*100.0/nToken);
          258  +  }
          259  +
          260  +  nTop = atoi(findOption("top", 1, "25"));
          261  +  printf("The %d most common tokens:\n", nTop);
          262  +  pStmt = prepare(db,
          263  +            "SELECT term, documents FROM %s"
          264  +            " WHERE col='*'"
          265  +            " ORDER BY documents DESC, term"
          266  +            " LIMIT %d", zAux, nTop);
          267  +  i = 0;
          268  +  while( sqlite3_step(pStmt)==SQLITE_ROW ){
          269  +    i++;
          270  +    n = sqlite3_column_int(pStmt, 1);
          271  +    printf("  %2d. %-30s %9d docs %5.2f%%\n", i,
          272  +      sqlite3_column_text(pStmt, 0), n, n*100.0/nDoc);
          273  +  }
          274  +  sqlite3_finalize(pStmt);
          275  +
          276  +end_vocab:
          277  +  runSql(db, "ROLLBACK");
          278  +  sqlite3_free(zAux);
          279  +}
          280  +
          281  +/*
          282  +** Report on the number and sizes of segments
          283  +*/
          284  +static void showSegmentStats(sqlite3 *db, const char *zTab){
          285  +  sqlite3_stmt *pStmt;
          286  +  int nSeg = 0;
          287  +  sqlite3_int64 szSeg = 0, mxSeg = 0;
          288  +  int nIdx = 0;
          289  +  sqlite3_int64 szIdx = 0, mxIdx = 0;
          290  +  int nRoot = 0;
          291  +  sqlite3_int64 szRoot = 0, mxRoot = 0;
          292  +  sqlite3_int64 mx;
          293  +  int nLeaf;
          294  +  int n;
          295  +  int pgsz;
          296  +  int mxLevel;
          297  +  int i;
          298  +
          299  +  pStmt = prepare(db,
          300  +                  "SELECT count(*), sum(length(block)), max(length(block))"
          301  +                  " FROM '%q_segments'",
          302  +                  zTab);
          303  +  while( sqlite3_step(pStmt)==SQLITE_ROW ){
          304  +    nSeg = sqlite3_column_int(pStmt, 0);
          305  +    szSeg = sqlite3_column_int64(pStmt, 1);
          306  +    mxSeg = sqlite3_column_int64(pStmt, 2);
          307  +  }
          308  +  sqlite3_finalize(pStmt);
          309  +  pStmt = prepare(db,
          310  +            "SELECT count(*), sum(length(block)), max(length(block))"
          311  +            "  FROM '%q_segments' a JOIN '%q_segdir' b"
          312  +            " WHERE a.blockid BETWEEN b.leaves_end_block+1 AND b.end_block",
          313  +            zTab, zTab);
          314  +  while( sqlite3_step(pStmt)==SQLITE_ROW ){
          315  +    nIdx = sqlite3_column_int(pStmt, 0);
          316  +    szIdx = sqlite3_column_int64(pStmt, 1);
          317  +    mxIdx = sqlite3_column_int64(pStmt, 2);
          318  +  }
          319  +  sqlite3_finalize(pStmt);
          320  +  pStmt = prepare(db,
          321  +            "SELECT count(*), sum(length(root)), max(length(root))"
          322  +            "  FROM '%q_segdir'",
          323  +            zTab);
          324  +  while( sqlite3_step(pStmt)==SQLITE_ROW ){
          325  +    nRoot = sqlite3_column_int(pStmt, 0);
          326  +    szRoot = sqlite3_column_int64(pStmt, 1);
          327  +    mxRoot = sqlite3_column_int64(pStmt, 2);
          328  +  }
          329  +  sqlite3_finalize(pStmt);
          330  +
          331  +  printf("Number of segments....................... %9d\n", nSeg+nRoot);
          332  +  printf("Number of leaf segments.................. %9d\n", nSeg-nIdx);
          333  +  printf("Number of index segments................. %9d\n", nIdx);
          334  +  printf("Number of root segments.................. %9d\n", nRoot);
          335  +  printf("Total size of all segments............... %9lld\n", szSeg+szRoot);
          336  +  printf("Total size of all leaf segments.......... %9lld\n", szSeg-szIdx);
          337  +  printf("Total size of all index segments......... %9lld\n", szIdx);
          338  +  printf("Total size of all root segments.......... %9lld\n", szRoot);
          339  +  if( nSeg>0 ){
          340  +    printf("Average size of all segments............. %11.1f\n",
          341  +            (double)(szSeg+szRoot)/(double)(nSeg+nRoot));
          342  +    printf("Average size of leaf segments............ %11.1f\n",
          343  +            (double)(szSeg-szIdx)/(double)(nSeg-nIdx));
          344  +  }
          345  +  if( nIdx>0 ){
          346  +    printf("Average size of index segments........... %11.1f\n",
          347  +            (double)szIdx/(double)nIdx);
          348  +  }
          349  +  if( nRoot>0 ){
          350  +    printf("Average size of root segments............ %11.1f\n",
          351  +            (double)szRoot/(double)nRoot);
          352  +  }
          353  +  mx = mxSeg;
          354  +  if( mx<mxRoot ) mx = mxRoot;
          355  +  printf("Maximum segment size..................... %9lld\n", mx);
          356  +  printf("Maximum index segment size............... %9lld\n", mxIdx);
          357  +  printf("Maximum root segment size................ %9lld\n", mxRoot);
          358  +
          359  +  pStmt = prepare(db, "PRAGMA page_size");
          360  +  pgsz = 1024;
          361  +  while( sqlite3_step(pStmt)==SQLITE_ROW ){
          362  +    pgsz = sqlite3_column_int(pStmt, 0);
          363  +  }
          364  +  sqlite3_finalize(pStmt);
          365  +  printf("Database page size....................... %9d\n", pgsz);
          366  +  pStmt = prepare(db,
          367  +            "SELECT count(*)"
          368  +            "  FROM '%q_segments' a JOIN '%q_segdir' b"
          369  +            " WHERE a.blockid BETWEEN b.start_block AND b.leaves_end_block"
          370  +            "   AND length(a.block)>%d",
          371  +            zTab, zTab, pgsz-45);
          372  +  n = 0;
          373  +  while( sqlite3_step(pStmt)==SQLITE_ROW ){
          374  +    n = sqlite3_column_int(pStmt, 0);
          375  +  }
          376  +  sqlite3_finalize(pStmt);
          377  +  nLeaf = nSeg - nIdx;
          378  +  printf("Leaf segments larger than %5d bytes.... %9d   %5.2f%%\n",
          379  +         pgsz-45, n, n*100.0/nLeaf);
          380  +
          381  +  pStmt = prepare(db, "SELECT max(level%%1024) FROM '%q_segdir'", zTab);
          382  +  mxLevel = 0;
          383  +  while( sqlite3_step(pStmt)==SQLITE_ROW ){
          384  +    mxLevel = sqlite3_column_int(pStmt, 0);
          385  +  }
          386  +  sqlite3_finalize(pStmt);
          387  +
          388  +  for(i=0; i<=mxLevel; i++){
          389  +    pStmt = prepare(db,
          390  +           "SELECT count(*), sum(len), avg(len), max(len), sum(len>%d),"
          391  +           "       count(distinct idx)"
          392  +           "  FROM (SELECT length(a.block) AS len, idx"
          393  +           "          FROM '%q_segments' a JOIN '%q_segdir' b"
          394  +           "         WHERE (a.blockid BETWEEN b.start_block"
          395  +                                       " AND b.leaves_end_block)"
          396  +           "           AND (b.level%%1024)==%d)",
          397  +           pgsz-45, zTab, zTab, i);
          398  +    if( sqlite3_step(pStmt)==SQLITE_ROW
          399  +     && (nLeaf = sqlite3_column_int(pStmt, 0))>0
          400  +    ){
          401  +      int nIdx = sqlite3_column_int(pStmt, 5);
          402  +      sqlite3_int64 sz;
          403  +      printf("For level %d:\n", i);
          404  +      printf("  Number of indexes...................... %9d\n", nIdx);
          405  +      printf("  Number of leaf segments................ %9d\n", nLeaf);
          406  +      if( nIdx>1 ){
          407  +        printf("  Average leaf segments per index........ %11.1f\n",
          408  +               (double)nLeaf/(double)nIdx);
          409  +      }
          410  +      printf("  Total size of all leaf segments........ %9lld\n",
          411  +             (sz = sqlite3_column_int64(pStmt, 1)));
          412  +      printf("  Average size of leaf segments.......... %11.1f\n",
          413  +             sqlite3_column_double(pStmt, 2));
          414  +      if( nIdx>1 ){
          415  +        printf("  Average leaf segment size per index.... %11.1f\n",
          416  +               (double)sz/(double)nIdx);
          417  +      }
          418  +      printf("  Maximum leaf segment size.............. %9lld\n",
          419  +             sqlite3_column_int64(pStmt, 3));
          420  +      n = sqlite3_column_int(pStmt, 4);
          421  +      printf("  Leaf segments larger than %5d bytes.. %9d   %5.2f%%\n",
          422  +             pgsz-45, n, n*100.0/nLeaf);
          423  +    }
          424  +    sqlite3_finalize(pStmt);
          425  +  }
          426  +}
          427  +
          428  +/*
          429  +** Print a single "tree" line of the segdir map output.
          430  +*/
          431  +static void printTreeLine(sqlite3_int64 iLower, sqlite3_int64 iUpper){
          432  +  printf("                 tree   %9lld", iLower);
          433  +  if( iUpper>iLower ){
          434  +    printf(" thru %9lld  (%lld blocks)", iUpper, iUpper-iLower+1);
          435  +  }
          436  +  printf("\n");
          437  +}
          438  +
          439  +/*
          440  +** Check to see if the block of a %_segments entry is NULL.
          441  +*/
          442  +static int isNullSegment(sqlite3 *db, const char *zTab, sqlite3_int64 iBlockId){
          443  +  sqlite3_stmt *pStmt;
          444  +  int rc = 1;
          445  +
          446  +  pStmt = prepare(db, "SELECT block IS NULL FROM '%q_segments'"
          447  +                      " WHERE blockid=%lld", zTab, iBlockId);
          448  +  if( sqlite3_step(pStmt)==SQLITE_ROW ){
          449  +    rc = sqlite3_column_int(pStmt, 0);
          450  +  }
          451  +  sqlite3_finalize(pStmt);
          452  +  return rc;
          453  +}
          454  +
          455  +/*
          456  +** Show a map of segments derived from the %_segdir table.
          457  +*/
          458  +static void showSegdirMap(sqlite3 *db, const char *zTab){
          459  +  int mxIndex, iIndex;
          460  +  sqlite3_stmt *pStmt = 0;
          461  +  sqlite3_stmt *pStmt2 = 0;
          462  +  int prevLevel;
          463  +
          464  +  pStmt = prepare(db, "SELECT max(level/1024) FROM '%q_segdir'", zTab);
          465  +  if( sqlite3_step(pStmt)==SQLITE_ROW ){
          466  +    mxIndex = sqlite3_column_int(pStmt, 0);
          467  +  }else{
          468  +    mxIndex = 0;
          469  +  }
          470  +  sqlite3_finalize(pStmt);
          471  +
          472  +  printf("Number of inverted indices............... %3d\n", mxIndex+1);
          473  +  pStmt = prepare(db,
          474  +    "SELECT level, idx, start_block, leaves_end_block, end_block, rowid"
          475  +    "  FROM '%q_segdir'"
          476  +    " WHERE level/1024==?"
          477  +    " ORDER BY level DESC, idx",
          478  +    zTab);
          479  +  pStmt2 = prepare(db,
          480  +    "SELECT blockid FROM '%q_segments'"
          481  +    " WHERE blockid BETWEEN ? AND ? ORDER BY blockid",
          482  +    zTab);
          483  +  for(iIndex=0; iIndex<=mxIndex; iIndex++){
          484  +    if( mxIndex>0 ){
          485  +      printf("**************************** Index %d "
          486  +             "****************************\n", iIndex);
          487  +    }
          488  +    sqlite3_bind_int(pStmt, 1, iIndex);
          489  +    prevLevel = -1;
          490  +    while( sqlite3_step(pStmt)==SQLITE_ROW ){
          491  +      int iLevel = sqlite3_column_int(pStmt, 0)%1024;
          492  +      int iIdx = sqlite3_column_int(pStmt, 1);
          493  +      sqlite3_int64 iStart = sqlite3_column_int64(pStmt, 2);
          494  +      sqlite3_int64 iLEnd = sqlite3_column_int64(pStmt, 3);
          495  +      sqlite3_int64 iEnd = sqlite3_column_int64(pStmt, 4);
          496  +      char rtag[20];
          497  +      if( iLevel!=prevLevel ){
          498  +        printf("level %2d idx %2d", iLevel, iIdx);
          499  +        prevLevel = iLevel;
          500  +      }else{
          501  +        printf("         idx %2d", iIdx);
          502  +      }
          503  +      sqlite3_snprintf(sizeof(rtag), rtag, "r%lld",
          504  +                       sqlite3_column_int64(pStmt,5));
          505  +      printf("  root   %9s\n", rtag);
          506  +      if( iLEnd>iStart ){
          507  +        sqlite3_int64 iLower, iPrev, iX;
          508  +        if( iLEnd+1<=iEnd ){
          509  +          sqlite3_bind_int64(pStmt2, 1, iLEnd+1);
          510  +          sqlite3_bind_int64(pStmt2, 2, iEnd);
          511  +          iLower = -1;        
          512  +          while( sqlite3_step(pStmt2)==SQLITE_ROW ){
          513  +            iX = sqlite3_column_int64(pStmt2, 0);
          514  +            if( iLower<0 ){
          515  +              iLower = iPrev = iX;
          516  +            }else if( iX==iPrev+1 ){
          517  +              iPrev = iX;
          518  +            }else{
          519  +              printTreeLine(iLower, iPrev);
          520  +              iLower = iPrev = iX;
          521  +            }
          522  +          }
          523  +          sqlite3_reset(pStmt2);
          524  +          if( iLower>=0 ){
          525  +            if( iLower==iPrev && iLower==iEnd
          526  +             && isNullSegment(db,zTab,iLower)
          527  +            ){
          528  +              printf("                 null   %9lld\n", iLower);
          529  +            }else{
          530  +              printTreeLine(iLower, iPrev);
          531  +            }
          532  +          }
          533  +        }
          534  +        printf("                 leaves %9lld thru %9lld  (%lld blocks)\n",
          535  +               iStart, iLEnd, iLEnd - iStart + 1);
          536  +      }
          537  +    }
          538  +    sqlite3_reset(pStmt);
          539  +  }
          540  +  sqlite3_finalize(pStmt);
          541  +  sqlite3_finalize(pStmt2);
          542  +}
          543  +
          544  +/*
          545  +** Decode a single segment block and display the results on stdout.
          546  +*/
          547  +static void decodeSegment(
          548  +  const unsigned char *aData,   /* Content to print */
          549  +  int nData                     /* Number of bytes of content */
          550  +){
          551  +  sqlite3_int64 iChild;
          552  +  sqlite3_int64 iPrefix;
          553  +  sqlite3_int64 nTerm;
          554  +  sqlite3_int64 n;
          555  +  sqlite3_int64 iDocsz;
          556  +  int iHeight;
          557  +  int i = 0;
          558  +  int cnt = 0;
          559  +  char zTerm[1000];
          560  +
          561  +  i += getVarint(aData, &n);
          562  +  iHeight = (int)n;
          563  +  printf("height: %d\n", iHeight);
          564  +  if( iHeight>0 ){
          565  +    i += getVarint(aData+i, &iChild);
          566  +    printf("left-child: %lld\n", iChild);
          567  +  }
          568  +  while( i<nData ){
          569  +    if( (cnt++)>0 ){
          570  +      i += getVarint(aData+i, &iPrefix);
          571  +    }else{
          572  +      iPrefix = 0;
          573  +    }
          574  +    i += getVarint(aData+i, &nTerm);
          575  +    if( iPrefix+nTerm+1 >= sizeof(zTerm) ){
          576  +      fprintf(stderr, "term to long\n");
          577  +      exit(1);
          578  +    }
          579  +    memcpy(zTerm+iPrefix, aData+i, nTerm);
          580  +    zTerm[iPrefix+nTerm] = 0;
          581  +    i += nTerm;
          582  +    if( iHeight==0 ){
          583  +      i += getVarint(aData+i, &iDocsz);
          584  +      printf("term: %-25s doclist %7lld bytes offset %d\n", zTerm, iDocsz, i);
          585  +      i += iDocsz;
          586  +    }else{
          587  +      printf("term: %-25s child %lld\n", zTerm, ++iChild);
          588  +    }
          589  +  }
          590  +}
          591  +  
          592  +  
          593  +/*
          594  +** Print a a blob as hex and ascii.
          595  +*/
          596  +static void printBlob(
          597  +  const unsigned char *aData,   /* Content to print */
          598  +  int nData                     /* Number of bytes of content */
          599  +){
          600  +  int i, j;
          601  +  const char *zOfstFmt;
          602  +  const int perLine = 16;
          603  +
          604  +  if( (nData&~0xfff)==0 ){
          605  +    zOfstFmt = " %03x: ";
          606  +  }else if( (nData&~0xffff)==0 ){
          607  +    zOfstFmt = " %04x: ";
          608  +  }else if( (nData&~0xfffff)==0 ){
          609  +    zOfstFmt = " %05x: ";
          610  +  }else if( (nData&~0xffffff)==0 ){
          611  +    zOfstFmt = " %06x: ";
          612  +  }else{
          613  +    zOfstFmt = " %08x: ";
          614  +  }
          615  +
          616  +  for(i=0; i<nData; i += perLine){
          617  +    fprintf(stdout, zOfstFmt, i);
          618  +    for(j=0; j<perLine; j++){
          619  +      if( i+j>nData ){
          620  +        fprintf(stdout, "   ");
          621  +      }else{
          622  +        fprintf(stdout,"%02x ", aData[i+j]);
          623  +      }
          624  +    }
          625  +    for(j=0; j<perLine; j++){
          626  +      if( i+j>nData ){
          627  +        fprintf(stdout, " ");
          628  +      }else{
          629  +        fprintf(stdout,"%c", isprint(aData[i+j]) ? aData[i+j] : '.');
          630  +      }
          631  +    }
          632  +    fprintf(stdout,"\n");
          633  +  }
          634  +}
          635  +
          636  +/*
          637  +** Convert text to a 64-bit integer
          638  +*/
          639  +static sqlite3_int64 atoi64(const char *z){
          640  +  sqlite3_int64 v = 0;
          641  +  while( z[0]>='0' && z[0]<='9' ){
          642  +     v = v*10 + z[0] - '0';
          643  +     z++;
          644  +  }
          645  +  return v;
          646  +}
          647  +
          648  +/*
          649  +** Return a prepared statement which, when stepped, will return in its
          650  +** first column the blob associated with segment zId.  If zId begins with
          651  +** 'r' then it is a rowid of a %_segdir entry.  Otherwise it is a
          652  +** %_segment entry.
          653  +*/
          654  +static sqlite3_stmt *prepareToGetSegment(
          655  +  sqlite3 *db,         /* The database */
          656  +  const char *zTab,    /* The FTS3/4 table name */
          657  +  const char *zId      /* ID of the segment to open */
          658  +){
          659  +  sqlite3_stmt *pStmt;
          660  +  if( zId[0]=='r' ){
          661  +    pStmt = prepare(db, "SELECT root FROM '%q_segdir' WHERE rowid=%lld",
          662  +                    zTab, atoi64(zId+1));
          663  +  }else{
          664  +    pStmt = prepare(db, "SELECT block FROM '%q_segments' WHERE blockid=%lld",
          665  +                    zTab, atoi64(zId));
          666  +  }
          667  +  return pStmt;
          668  +}
          669  +
          670  +/*
          671  +** Print the content of a segment or of the root of a segdir.  The segment
          672  +** or root is identified by azExtra[0].  If the first character of azExtra[0]
          673  +** is 'r' then the remainder is the integer rowid of the %_segdir entry.
          674  +** If the first character of azExtra[0] is not 'r' then, then all of
          675  +** azExtra[0] is an integer which is the block number.
          676  +**
          677  +** If the --raw option is present in azExtra, then a hex dump is provided.
          678  +** Otherwise a decoding is shown.
          679  +*/
          680  +static void showSegment(sqlite3 *db, const char *zTab){
          681  +  const unsigned char *aData;
          682  +  int nData;
          683  +  sqlite3_stmt *pStmt;
          684  +
          685  +  pStmt = prepareToGetSegment(db, zTab, azExtra[0]);
          686  +  if( sqlite3_step(pStmt)!=SQLITE_ROW ){
          687  +    sqlite3_finalize(pStmt);
          688  +    return;
          689  +  }
          690  +  nData = sqlite3_column_bytes(pStmt, 0);
          691  +  aData = sqlite3_column_blob(pStmt, 0);
          692  +  printf("Segment %s of size %d bytes:\n", azExtra[0], nData);
          693  +  if( findOption("raw", 0, 0)!=0 ){
          694  +    printBlob(aData, nData);
          695  +  }else{
          696  +    decodeSegment(aData, nData);
          697  +  }
          698  +  sqlite3_finalize(pStmt);
          699  +}
          700  +
          701  +/*
          702  +** Decode a single doclist and display the results on stdout.
          703  +*/
          704  +static void decodeDoclist(
          705  +  const unsigned char *aData,   /* Content to print */
          706  +  int nData                     /* Number of bytes of content */
          707  +){
          708  +  sqlite3_int64 iPrevDocid = 0;
          709  +  sqlite3_int64 iDocid;
          710  +  sqlite3_int64 iPos;
          711  +  sqlite3_int64 iPrevPos = 0;
          712  +  sqlite3_int64 iCol;
          713  +  int i = 0;
          714  +
          715  +  while( i<nData ){
          716  +    i += getVarint(aData+i, &iDocid);
          717  +    printf("docid %lld col0", iDocid+iPrevDocid);
          718  +    iPrevDocid += iDocid;
          719  +    iPrevPos = 0;
          720  +    while( 1 ){
          721  +      i += getVarint(aData+i, &iPos);
          722  +      if( iPos==1 ){
          723  +        i += getVarint(aData+i, &iCol);
          724  +        printf(" col%lld", iCol);
          725  +        iPrevPos = 0;
          726  +      }else if( iPos==0 ){
          727  +        printf("\n");
          728  +        break;
          729  +      }else{
          730  +        iPrevPos += iPos - 2;
          731  +        printf(" %lld", iPrevPos);
          732  +      }
          733  +    }
          734  +  }
          735  +}
          736  +  
          737  +
          738  +/*
          739  +** Print the content of a doclist.  The segment or segdir-root is
          740  +** identified by azExtra[0].  If the first character of azExtra[0]
          741  +** is 'r' then the remainder is the integer rowid of the %_segdir entry.
          742  +** If the first character of azExtra[0] is not 'r' then, then all of
          743  +** azExtra[0] is an integer which is the block number.  The offset
          744  +** into the segment is identified by azExtra[1].  The size of the doclist
          745  +** is azExtra[2].
          746  +**
          747  +** If the --raw option is present in azExtra, then a hex dump is provided.
          748  +** Otherwise a decoding is shown.
          749  +*/
          750  +static void showDoclist(sqlite3 *db, const char *zTab){
          751  +  const unsigned char *aData;
          752  +  sqlite3_int64 offset, nData;
          753  +  sqlite3_stmt *pStmt;
          754  +
          755  +  offset = atoi64(azExtra[1]);
          756  +  nData = atoi64(azExtra[2]);
          757  +  pStmt = prepareToGetSegment(db, zTab, azExtra[0]);
          758  +  if( sqlite3_step(pStmt)!=SQLITE_ROW ){
          759  +    sqlite3_finalize(pStmt);
          760  +    return;
          761  +  }
          762  +  aData = sqlite3_column_blob(pStmt, 0);
          763  +  printf("Doclist at %s offset %lld of size %lld bytes:\n",
          764  +         azExtra[0], offset, nData);
          765  +  if( findOption("raw", 0, 0)!=0 ){
          766  +    printBlob(aData+offset, nData);
          767  +  }else{
          768  +    decodeDoclist(aData+offset, nData);
          769  +  }
          770  +  sqlite3_finalize(pStmt);
          771  +}
          772  +
          773  +/*
          774  +** Show the top N largest segments
          775  +*/
          776  +static void listBigSegments(sqlite3 *db, const char *zTab){
          777  +  int nTop, i;
          778  +  sqlite3_stmt *pStmt;
          779  +  sqlite3_int64 sz;
          780  +  sqlite3_int64 id;
          781  +
          782  +  nTop = atoi(findOption("top", 1, "25"));
          783  +  printf("The %d largest segments:\n", nTop);
          784  +  pStmt = prepare(db,
          785  +            "SELECT blockid, length(block) AS len FROM '%q_segments'"
          786  +            " ORDER BY 2 DESC, 1"
          787  +            " LIMIT %d", zTab, nTop);
          788  +  i = 0;
          789  +  while( sqlite3_step(pStmt)==SQLITE_ROW ){
          790  +    i++;
          791  +    id = sqlite3_column_int64(pStmt, 0);
          792  +    sz = sqlite3_column_int64(pStmt, 1);
          793  +    printf("  %2d. %9lld size %lld\n", i, id, sz);
          794  +  }
          795  +  sqlite3_finalize(pStmt);
          796  +}
          797  +
          798  +
          799  +
          800  +static void usage(const char *argv0){
          801  +  fprintf(stderr, "Usage: %s DATABASE\n"
          802  +                  "   or: %s DATABASE FTS3TABLE ARGS...\n", argv0, argv0);
          803  +  fprintf(stderr,
          804  +    "ARGS:\n"
          805  +    "  big-segments [--top N]                    show the largest segments\n"
          806  +    "  doclist BLOCKID OFFSET SIZE [--raw]       Decode a doclist\n"
          807  +    "  schema                                    FTS table schema\n"
          808  +    "  segdir                                    directory of segments\n"
          809  +    "  segment BLOCKID [--raw]                   content of a segment\n"
          810  +    "  segment-stats                             info on segment sizes\n"
          811  +    "  stat                                      the %%_stat table\n"
          812  +    "  vocabulary [--top N]                      document vocabulary\n"
          813  +  );
          814  +  exit(1);
          815  +}
          816  +
          817  +int main(int argc, char **argv){
          818  +  sqlite3 *db;
          819  +  int rc;
          820  +  const char *zTab;
          821  +  const char *zCmd;
          822  +
          823  +  if( argc<2 ) usage(argv[0]);
          824  +  rc = sqlite3_open(argv[1], &db);
          825  +  if( rc ){
          826  +    fprintf(stderr, "Cannot open %s\n", argv[1]);
          827  +    exit(1);
          828  +  }
          829  +  if( argc==2 ){
          830  +    sqlite3_stmt *pStmt;
          831  +    int cnt = 0;
          832  +    pStmt = prepare(db, "SELECT b.sql"
          833  +                        "  FROM sqlite_master a, sqlite_master b"
          834  +                        " WHERE a.name GLOB '*_segdir'"
          835  +                        "   AND b.name=substr(a.name,1,length(a.name)-7)"
          836  +                        " ORDER BY 1");
          837  +    while( sqlite3_step(pStmt)==SQLITE_ROW ){
          838  +      cnt++;
          839  +      printf("%s;\n", sqlite3_column_text(pStmt, 0));
          840  +    }
          841  +    sqlite3_finalize(pStmt);
          842  +    if( cnt==0 ){
          843  +      printf("/* No FTS3/4 tables found in database %s */\n", argv[1]);
          844  +    }
          845  +    return 0;
          846  +  }
          847  +  if( argc<4 ) usage(argv[0]);
          848  +  zTab = argv[2];
          849  +  zCmd = argv[3];
          850  +  nExtra = argc-4;
          851  +  azExtra = argv+4;
          852  +  if( strcmp(zCmd,"big-segments")==0 ){
          853  +    listBigSegments(db, zTab);
          854  +  }else if( strcmp(zCmd,"doclist")==0 ){
          855  +    if( argc<7 ) usage(argv[0]);
          856  +    showDoclist(db, zTab);
          857  +  }else if( strcmp(zCmd,"schema")==0 ){
          858  +    showSchema(db, zTab);
          859  +  }else if( strcmp(zCmd,"segdir")==0 ){
          860  +    showSegdirMap(db, zTab);
          861  +  }else if( strcmp(zCmd,"segment")==0 ){
          862  +    if( argc<5 ) usage(argv[0]);
          863  +    showSegment(db, zTab);
          864  +  }else if( strcmp(zCmd,"segment-stats")==0 ){
          865  +    showSegmentStats(db, zTab);
          866  +  }else if( strcmp(zCmd,"stat")==0 ){
          867  +    showStat(db, zTab);
          868  +  }else if( strcmp(zCmd,"vocabulary")==0 ){
          869  +    showVocabulary(db, zTab);
          870  +  }else{
          871  +    usage(argv[0]);
          872  +  }
          873  +  return 0; 
          874  +}

Changes to test/backcompat.test.

    23     23   # for documentation of the available commands.
    24     24   #
    25     25   
    26     26   set testdir [file dirname $argv0]
    27     27   source $testdir/tester.tcl
    28     28   source $testdir/lock_common.tcl
    29     29   source $testdir/malloc_common.tcl
           30  +source $testdir/bc_common.tcl
    30     31   db close
    31     32   
    32         -# Search for binaries to test against. Any executable files that match
    33         -# our naming convention are assumed to be testfixture binaries to test
    34         -# against.
    35         -#
    36         -set binaries [list]
    37         -set pattern "[file tail [info nameofexec]]?*"
    38         -if {$tcl_platform(platform)=="windows"} {
    39         -  set pattern [string map {\.exe {}} $pattern]
    40         -}
    41         -foreach file [glob -nocomplain $pattern] {
    42         -  if {[file executable $file] && [file isfile $file]} {lappend binaries $file}
    43         -}
    44         -if {[llength $binaries]==0} {
    45         -  puts "WARNING: No historical binaries to test against."
    46         -  puts "WARNING: No backwards-compatibility tests have been run."
           33  +if {"" == [bc_find_binaries backcompat.test]} {
    47     34     finish_test
    48     35     return
    49     36   }
    50         -proc get_version {binary} {
    51         -  set chan [launch_testfixture $binary]
    52         -  set v [testfixture $chan { sqlite3 -version }]
    53         -  close $chan
    54         -  set v
    55         -}
    56         -foreach bin $binaries {
    57         -  puts -nonewline "Testing against $bin - "
    58         -  flush stdout
    59         -  puts "version [get_version $bin]"
    60         -}
    61     37   
    62     38   proc do_backcompat_test {rv bin1 bin2 script} {
    63     39   
    64     40     forcedelete test.db
    65     41   
    66     42     if {$bin1 != ""} { set ::bc_chan1 [launch_testfixture $bin1] }
    67     43     set ::bc_chan2 [launch_testfixture $bin2]
................................................................................
    89     65     catch { close $::bc_chan2 }
    90     66     catch { close $::bc_chan1 }
    91     67   }
    92     68   
    93     69   array set ::incompatible [list]
    94     70   proc do_allbackcompat_test {script} {
    95     71   
    96         -  foreach bin $::binaries {
           72  +  foreach bin $::BC(binaries) {
    97     73       set nErr [set_test_counter errors]
    98     74       foreach dir {0 1} {
    99     75   
   100     76         set bintag [string map {testfixture {}} $bin]
   101     77         set bintag [string map {\.exe {}} $bintag]
   102     78         if {$bintag == ""} {set bintag self}
   103     79         set ::bcname ".$bintag.$dir."

Added test/bc_common.tcl.

            1  +
            2  +
            3  +
            4  +proc bc_find_binaries {zCaption} {
            5  +  # Search for binaries to test against. Any executable files that match
            6  +  # our naming convention are assumed to be testfixture binaries to test
            7  +  # against.
            8  +  #
            9  +  set binaries [list]
           10  +  set pattern "[file tail [info nameofexec]]?*"
           11  +  if {$::tcl_platform(platform)=="windows"} {
           12  +    set pattern [string map {\.exe {}} $pattern]
           13  +  }
           14  +  foreach file [glob -nocomplain $pattern] {
           15  +    if {[file executable $file] && [file isfile $file]} {lappend binaries $file}
           16  +  }
           17  +
           18  +  if {[llength $binaries]==0} {
           19  +    puts "WARNING: No historical binaries to test against."
           20  +    puts "WARNING: Omitting backwards-compatibility tests"
           21  +  }
           22  +
           23  +  foreach bin $binaries {
           24  +    puts -nonewline "Testing against $bin - "
           25  +    flush stdout
           26  +    puts "version [get_version $bin]"
           27  +  }
           28  +
           29  +  set ::BC(binaries) $binaries
           30  +  return $binaries
           31  +}
           32  +
           33  +proc get_version {binary} {
           34  +  set chan [launch_testfixture $binary]
           35  +  set v [testfixture $chan { sqlite3 -version }]
           36  +  close $chan
           37  +  set v
           38  +}
           39  +
           40  +proc do_bc_test {bin script} {
           41  +
           42  +  forcedelete test.db
           43  +  set ::bc_chan [launch_testfixture $bin]
           44  +
           45  +  proc code1 {tcl} { uplevel #0 $tcl }
           46  +  proc code2 {tcl} { testfixture $::bc_chan $tcl }
           47  +  proc sql1 sql { code1 [list db eval $sql] }
           48  +  proc sql2 sql { code2 [list db eval $sql] }
           49  +
           50  +  code1 { sqlite3 db test.db }
           51  +  code2 { sqlite3 db test.db }
           52  +
           53  +  set bintag [string map {testfixture {}} $bin]
           54  +  set bintag [string map {\.exe {}} $bintag]
           55  +  if {$bintag == ""} {set bintag self}
           56  +  set saved_prefix $::testprefix
           57  +  append ::testprefix ".$bintag"
           58  +
           59  +  uplevel $script
           60  +
           61  +  set ::testprefix $saved_prefix
           62  +
           63  +  catch { code1 { db close } }
           64  +  catch { code2 { db close } }
           65  +  catch { close $::bc_chan }
           66  +}
           67  +
           68  +proc do_all_bc_test {script} {
           69  +  foreach bin $::BC(binaries) {
           70  +    uplevel [list do_bc_test $bin $script]
           71  +  }
           72  +}

Changes to test/fts3_common.tcl.

     9      9   #
    10     10   #***********************************************************************
    11     11   #
    12     12   # This file contains common code used the fts3 tests. At one point
    13     13   # equivalent functionality was implemented in C code. But it is easier
    14     14   # to use Tcl.
    15     15   #
           16  +
           17  +#-------------------------------------------------------------------------
           18  +# INSTRUCTIONS
           19  +#
           20  +# The following commands are available:
           21  +#
           22  +#   fts3_build_db_1 N
           23  +#     Using database handle [db] create an FTS4 table named t1 and populate
           24  +#     it with N rows of data. N must be less than 10,000. Refer to the
           25  +#     header comments above the proc implementation below for details.
           26  +#
           27  +#   fts3_build_db_2 N
           28  +#     Using database handle [db] create an FTS4 table named t2 and populate
           29  +#     it with N rows of data. N must be less than 100,000. Refer to the
           30  +#     header comments above the proc implementation below for details.
           31  +#
           32  +#   fts3_integrity_check TBL
           33  +#     TBL must be an FTS table in the database currently opened by handle
           34  +#     [db]. This proc loads and tokenizes all documents within the table,
           35  +#     then checks that the current contents of the FTS index matches the
           36  +#     results.
           37  +#
           38  +#   fts3_terms TBL WHERE
           39  +#     Todo.
           40  +#
           41  +#   fts3_doclist TBL TERM WHERE
           42  +#     Todo.
           43  +#
           44  +#
           45  +#
           46  +
           47  +#-------------------------------------------------------------------------
           48  +# USAGE: fts3_build_db_1 SWITCHES N
           49  +#
           50  +# Build a sample FTS table in the database opened by database connection 
           51  +# [db]. The name of the new table is "t1".
           52  +#
           53  +proc fts3_build_db_1 {args} {
           54  +
           55  +  set default(-module) fts4
           56  +
           57  +  set nArg [llength $args]
           58  +  if {($nArg%2)==0} {
           59  +    error "wrong # args: should be \"fts3_build_db_1 ?switches? n\""
           60  +  }
           61  +
           62  +  set n [lindex $args [expr $nArg-1]]
           63  +  array set opts [array get default]
           64  +  array set opts [lrange $args 0 [expr $nArg-2]]
           65  +  foreach k [array names opts] {
           66  +    if {0==[info exists default($k)]} { error "unknown option: $k" }
           67  +  }
           68  +
           69  +  if {$n > 10000} {error "n must be <= 10000"}
           70  +  db eval "CREATE VIRTUAL TABLE t1 USING $opts(-module) (x, y)"
           71  +
           72  +  set xwords [list zero one two three four five six seven eight nine ten]
           73  +  set ywords [list alpha beta gamma delta epsilon zeta eta theta iota kappa]
           74  +
           75  +  for {set i 0} {$i < $n} {incr i} {
           76  +    set x ""
           77  +    set y ""
           78  +
           79  +    set x [list]
           80  +    lappend x [lindex $xwords [expr ($i / 1000) % 10]]
           81  +    lappend x [lindex $xwords [expr ($i / 100)  % 10]]
           82  +    lappend x [lindex $xwords [expr ($i / 10)   % 10]]
           83  +    lappend x [lindex $xwords [expr ($i / 1)   % 10]]
           84  +
           85  +    set y [list]
           86  +    lappend y [lindex $ywords [expr ($i / 1000) % 10]]
           87  +    lappend y [lindex $ywords [expr ($i / 100)  % 10]]
           88  +    lappend y [lindex $ywords [expr ($i / 10)   % 10]]
           89  +    lappend y [lindex $ywords [expr ($i / 1)   % 10]]
           90  +
           91  +    db eval { INSERT INTO t1(docid, x, y) VALUES($i, $x, $y) }
           92  +  }
           93  +}
           94  +
           95  +#-------------------------------------------------------------------------
           96  +# USAGE: fts3_build_db_2 N ARGS
           97  +#
           98  +# Build a sample FTS table in the database opened by database connection 
           99  +# [db]. The name of the new table is "t2".
          100  +#
          101  +proc fts3_build_db_2 {args} {
          102  +
          103  +  set default(-module) fts4
          104  +  set default(-extra)   ""
          105  +
          106  +  set nArg [llength $args]
          107  +  if {($nArg%2)==0} {
          108  +    error "wrong # args: should be \"fts3_build_db_1 ?switches? n\""
          109  +  }
          110  +
          111  +  set n [lindex $args [expr $nArg-1]]
          112  +  array set opts [array get default]
          113  +  array set opts [lrange $args 0 [expr $nArg-2]]
          114  +  foreach k [array names opts] {
          115  +    if {0==[info exists default($k)]} { error "unknown option: $k" }
          116  +  }
          117  +
          118  +  if {$n > 100000} {error "n must be <= 100000"}
          119  +
          120  +  set sql "CREATE VIRTUAL TABLE t2 USING $opts(-module) (content"
          121  +  if {$opts(-extra) != ""} {
          122  +    append sql ", " $opts(-extra)
          123  +  }
          124  +  append sql ")"
          125  +  db eval $sql
          126  +
          127  +  set chars [list a b c d e f g h  i j k l m n o p  q r s t u v w x  y z ""]
          128  +
          129  +  for {set i 0} {$i < $n} {incr i} {
          130  +    set word ""
          131  +    set nChar [llength $chars]
          132  +    append word [lindex $chars [expr {($i / 1)   % $nChar}]]
          133  +    append word [lindex $chars [expr {($i / $nChar)  % $nChar}]]
          134  +    append word [lindex $chars [expr {($i / ($nChar*$nChar)) % $nChar}]]
          135  +
          136  +    db eval { INSERT INTO t2(docid, content) VALUES($i, $word) }
          137  +  }
          138  +}
    16    139   
    17    140   #-------------------------------------------------------------------------
    18    141   # USAGE: fts3_integrity_check TBL
    19    142   #
    20    143   # This proc is used to verify that the full-text index is consistent with
    21    144   # the contents of the fts3 table. In other words, it checks that the
    22    145   # data in the %_contents table matches that in the %_segdir and %_segments 
................................................................................
    42    165   #      
    43    166   #
    44    167   proc fts3_integrity_check {tbl} {
    45    168   
    46    169     fts3_read2 $tbl 1 A
    47    170   
    48    171     foreach zTerm [array names A] {
          172  +    #puts $zTerm
    49    173       foreach doclist $A($zTerm) {
    50    174         set docid 0
    51    175         while {[string length $doclist]>0} {
    52    176           set iCol 0
    53    177           set iPos 0
    54    178           set lPos [list]
    55    179           set lCol [list]
................................................................................
    93    217         set sql {SELECT fts3_tokenizer_test('simple', $c)}
    94    218   
    95    219         foreach {pos term dummy} [db one $sql] {
    96    220           if {![info exists C($iDoc,$iCol,$pos)]} {
    97    221             set es "Error at docid=$iDoc col=$iCol pos=$pos. Index is missing"
    98    222             lappend errors $es
    99    223           } else {
   100         -          if {$C($iDoc,$iCol,$pos) != "$term"} {
          224  +          if {[string compare $C($iDoc,$iCol,$pos) $term]} {
   101    225               set    es "Error at docid=$iDoc col=$iCol pos=$pos. Index "
   102    226               append es "has \"$C($iDoc,$iCol,$pos)\", document has \"$term\""
   103    227               lappend errors $es
   104    228             }
   105    229             unset C($iDoc,$iCol,$pos)
   106    230           }
   107    231         }
................................................................................
   229    353   
   230    354     while {[string length $blob] > 0} {
   231    355       set nPrefix [gobble_varint blob]
   232    356       set nSuffix [gobble_varint blob]
   233    357   
   234    358       set zTerm [string range $zPrev 0 [expr $nPrefix-1]]
   235    359       append zTerm [gobble_string blob $nSuffix]
   236         -    set doclist [gobble_string blob [gobble_varint blob]]
          360  +    set nDoclist [gobble_varint blob]
          361  +    set doclist [gobble_string blob $nDoclist]
   237    362   
   238    363       lappend terms $zTerm $doclist
   239    364       set zPrev $zTerm
   240    365     }
   241    366   
   242    367     return $terms
   243    368   }
................................................................................
   245    370   proc fts3_read2 {tbl where varname} {
   246    371     upvar $varname a
   247    372     array unset a
   248    373     db eval " SELECT start_block, leaves_end_block, root 
   249    374               FROM ${tbl}_segdir WHERE $where
   250    375               ORDER BY level ASC, idx DESC
   251    376     " {
   252         -    if {$start_block == 0} {
          377  +    set c 0
          378  +    binary scan $root c c
          379  +    if {$c==0} {
   253    380         foreach {t d} [fts3_readleaf $root] { lappend a($t) $d }
   254    381       } else {
   255    382         db eval " SELECT block 
   256    383                   FROM ${tbl}_segments 
   257    384                   WHERE blockid>=$start_block AND blockid<=$leaves_end_block
   258    385                   ORDER BY blockid
   259    386         " {
   260    387           foreach {t d} [fts3_readleaf $block] { lappend a($t) $d }
   261         -
   262    388         }
   263    389       }
   264    390     }
   265    391   }
   266    392   
   267    393   proc fts3_read {tbl where varname} {
   268    394     upvar $varname a

Added test/fts4check.test.

            1  +# 2012 March 26
            2  +#
            3  +# The author disclaims copyright to this source code.  In place of
            4  +# a legal notice, here is a blessing:
            5  +#
            6  +#    May you do good and not evil.
            7  +#    May you find forgiveness for yourself and forgive others.
            8  +#    May you share freely, never taking more than you give.
            9  +#
           10  +#*************************************************************************
           11  +# This file implements regression tests for SQLite library. The
           12  +# focus of this script is testing the FTS 'integrity-check' function,
           13  +# used to check if the current FTS index accurately reflects the content
           14  +# of the table.
           15  +#
           16  +
           17  +set testdir [file dirname $argv0]
           18  +source $testdir/tester.tcl
           19  +source $testdir/fts3_common.tcl
           20  +set ::testprefix fts4check
           21  +
           22  +# If SQLITE_ENABLE_FTS3 is defined, omit this file.
           23  +ifcapable !fts3 {
           24  +  finish_test
           25  +  return
           26  +}
           27  +
           28  +# Run the integrity-check on FTS table $tbl using database handle $db. If
           29  +# the integrity-check passes, return "ok". Otherwise, throw an exception.
           30  +#
           31  +proc fts_integrity {db tbl} {
           32  +  $db eval "INSERT INTO $tbl ($tbl) VALUES('integrity-check')"
           33  +  return "ok"
           34  +}
           35  +
           36  +#-------------------------------------------------------------------------
           37  +# Test cases 1.*
           38  +#
           39  +#   1.0: Build a reasonably sized FTS table (5000 rows).
           40  +#
           41  +#   1.1: Run the integrity check code to check it passes.
           42  +#
           43  +#   1.2: Make a series of minor changes to the underlying FTS data structures
           44  +#        (e.g. delete or insert a row from the %_content table). Check that
           45  +#        this causes the integrity-check code to fail.
           46  +#
           47  +
           48  +# Build an FTS table and check the integrity-check passes.
           49  +#
           50  +do_test 1.0 { fts3_build_db_1 5000 } {}
           51  +do_test 1.1 { fts_integrity db t1 } {ok}
           52  +
           53  +# Mess around with the underlying tables. Check that this causes the
           54  +# integrity-check test to fail.
           55  +#
           56  +foreach {tn disruption} {
           57  +  1 {
           58  +    INSERT INTO t1_content(docid, c0x, c1y) VALUES(NULL, 'a', 'b');
           59  +  }
           60  +  2 {
           61  +    DELETE FROM t1_content WHERE docid = (SELECT max(docid) FROM t1_content);
           62  +  }
           63  +  3 {
           64  +    DELETE FROM t1_segdir WHERE level=0 AND idx=(
           65  +      SELECT max(idx) FROM t1_segdir WHERE level=0
           66  +    );
           67  +  }
           68  +} {
           69  +  do_execsql_test  1.2.1.$tn "BEGIN; $disruption"
           70  +  do_catchsql_test 1.2.2.$tn {
           71  +    INSERT INTO t1 (t1) VALUES('integrity-check')
           72  +  } {1 {database disk image is malformed}}
           73  +  do_execsql_test  1.2.3.$tn "ROLLBACK"
           74  +}
           75  +
           76  +do_test 1.3 { fts_integrity db t1 } {ok}
           77  +
           78  +#-------------------------------------------------------------------------
           79  +# Test cases 2.*
           80  +#
           81  +#   2.0: Build a reasonably sized FTS table (20000 rows) that includes
           82  +#        prefix indexes.
           83  +#
           84  +#   2.1: Run the integrity check code to check it passes.
           85  +#
           86  +#   2.2: Make a series of minor changes to the underlying FTS data structures
           87  +#        (e.g. delete or insert a row from the %_content table). Check that
           88  +#        this causes the integrity-check code to fail.
           89  +#
           90  +
           91  +do_test 2.0 { fts3_build_db_2 -extra {prefix="3,1"} 20000 } {}
           92  +do_test 2.1 { fts_integrity db t2 } {ok}
           93  +foreach {tn disruption} {
           94  +  1 {
           95  +    INSERT INTO t2_content VALUES(NULL, 'xyz')
           96  +  }
           97  +  3 {
           98  +    DELETE FROM t2_segdir WHERE level=0 AND idx=(
           99  +      SELECT max(idx) FROM t2_segdir WHERE level=1024
          100  +    );
          101  +  }
          102  +} {
          103  +  do_execsql_test  2.2.1.$tn "BEGIN; $disruption"
          104  +  do_catchsql_test 2.2.2.$tn {
          105  +    INSERT INTO t2 (t2) VALUES('integrity-check')
          106  +  } {1 {database disk image is malformed}}
          107  +  do_execsql_test  2.2.3.$tn "ROLLBACK"
          108  +}
          109  +
          110  +
          111  +#-------------------------------------------------------------------------
          112  +# Test cases 3.*
          113  +#
          114  +#   3.0: Build a reasonably sized FTS table (5000 rows) that includes
          115  +#        prefix indexes and uses the languageid= feature.
          116  +#
          117  +#   3.1: Run the integrity check code to check it passes.
          118  +#
          119  +#   3.2: Make a series of minor changes to the underlying FTS data structures
          120  +#        (e.g. delete or insert a row from the %_content table). Check that
          121  +#        this causes the integrity-check code to fail.
          122  +#
          123  +do_test 3.0 {
          124  +  reset_db
          125  +  fts3_build_db_1 5000
          126  +  execsql {
          127  +    CREATE VIRTUAL TABLE t3 USING fts4(x, y, prefix="2,3", languageid=langid);
          128  +  }
          129  +  foreach docid [execsql {SELECT docid FROM t1 ORDER BY 1 ASC}] {
          130  +    execsql {
          131  +      INSERT INTO t3(x, y, langid) 
          132  +      SELECT x, y, (docid%9)*4 FROM t1 WHERE docid=$docid;
          133  +    }
          134  +  }
          135  +} {}
          136  +do_test 3.1 { fts_integrity db t3 } {ok}
          137  +
          138  +foreach {tn disruption} {
          139  +  1 {
          140  +    INSERT INTO t3_content(c0x, c1y, langid) VALUES(NULL, 'a', 0);
          141  +  }
          142  +  2 {
          143  +    UPDATE t3_content SET langid=langid+1 WHERE rowid = (
          144  +      SELECT max(rowid) FROM t3_content
          145  +    )
          146  +  }
          147  +} {
          148  +  do_execsql_test  3.2.1.$tn "BEGIN; $disruption"
          149  +  do_catchsql_test 3.2.2.$tn {
          150  +    INSERT INTO t3 (t3) VALUES('integrity-check')
          151  +  } {1 {database disk image is malformed}}
          152  +  do_execsql_test  3.2.3.$tn "ROLLBACK"
          153  +}
          154  +
          155  +finish_test

Changes to test/fts4langid.test.

   468    468   
   469    469     do_execsql_test 5.4.$lid.3 {
   470    470       SELECT count(*) FROM t6_segdir;
   471    471       SELECT count(*) FROM t6_segments;
   472    472     } {8 0}
   473    473   
   474    474     do_execsql_test 5.4.$lid.4 {
   475         -    INSERT INTO t6(t6) VALUES('optimize');
          475  +    INSERT INTO t6(t6) VALUES('merge=100,3');
          476  +    INSERT INTO t6(t6) VALUES('merge=100,3');
   476    477       SELECT docid FROM t6 WHERE t6 MATCH '"zero zero"' AND lid=$lid;
   477    478     } {1 2 5}
   478    479   
   479    480     do_execsql_test 5.4.$lid.5 {
   480    481       SELECT count(*) FROM t6_segdir;
   481    482       SELECT count(*) FROM t6_segments;
   482         -  } {1 0}
          483  +  } {4 4}
   483    484   }
   484         -
   485         -
   486    485   finish_test

Added test/fts4merge.test.

            1  +# 2012 March 06
            2  +#
            3  +# The author disclaims copyright to this source code.  In place of
            4  +# a legal notice, here is a blessing:
            5  +#
            6  +#    May you do good and not evil.
            7  +#    May you find forgiveness for yourself and forgive others.
            8  +#    May you share freely, never taking more than you give.
            9  +#
           10  +#*************************************************************************
           11  +# This file implements regression tests for SQLite library.  The
           12  +# focus of this script is testing the incremental merge function.
           13  +#
           14  +
           15  +set testdir [file dirname $argv0]
           16  +source $testdir/tester.tcl
           17  +source $testdir/fts3_common.tcl
           18  +
           19  +# If SQLITE_ENABLE_FTS3 is defined, omit this file.
           20  +ifcapable !fts3 {
           21  +  finish_test
           22  +  return
           23  +}
           24  +
           25  +proc fts3_integrity_check {tbl} {
           26  +  db eval "INSERT INTO $tbl ($tbl) VALUES('integrity-check')"
           27  +  return "ok"
           28  +}
           29  +
           30  +foreach mod {fts3 fts4} {
           31  +  set ::testprefix fts4merge-$mod
           32  +  reset_db
           33  +
           34  +  #-------------------------------------------------------------------------
           35  +  # Test cases 1.*
           36  +  #
           37  +  do_test 1.0 { fts3_build_db_1 -module $mod 1004 } {}
           38  +  do_test 1.1 { fts3_integrity_check t1 } {ok}
           39  +  do_execsql_test 1.1 { 
           40  +    SELECT level, group_concat(idx, ' ') FROM t1_segdir GROUP BY level 
           41  +  } {
           42  +    0 {0 1 2 3 4 5 6 7 8 9 10 11} 
           43  +    1 {0 1 2 3 4 5 6 7 8 9 10 11 12 13}
           44  +    2 {0 1 2}
           45  +  }
           46  +  
           47  +  for {set i 0} {$i<20} {incr i} {
           48  +    do_execsql_test 1.2.$i.1 { INSERT INTO t1(t1) VALUES('merge=1') }
           49  +    do_test 1.2.$i.2 { fts3_integrity_check t1 } ok
           50  +    do_execsql_test 1.2.$i.3 { 
           51  +      SELECT docid FROM t1 WHERE t1 MATCH 'zero one two three'
           52  +    } {123 132 213 231 312 321}
           53  +  }
           54  +  
           55  +  do_execsql_test 1.3 { 
           56  +    SELECT level, group_concat(idx, ' ') FROM t1_segdir GROUP BY level 
           57  +  } {
           58  +    0 {0 1 2 3} 
           59  +    1 {0 1 2 3 4 5 6} 
           60  +    2 {0 1 2 3}
           61  +  }
           62  +  
           63  +  for {set i 0} {$i<100} {incr i} {
           64  +    do_execsql_test 1.4.$i { INSERT INTO t1(t1) VALUES('merge=1,4') }
           65  +    do_test 1.4.$i.2 { fts3_integrity_check t1 } ok
           66  +    do_execsql_test 1.4.$i.3 { 
           67  +      SELECT docid FROM t1 WHERE t1 MATCH 'zero one two three'
           68  +    } {123 132 213 231 312 321}
           69  +  }
           70  +  
           71  +  do_execsql_test 1.5 { 
           72  +    SELECT level, group_concat(idx, ' ') FROM t1_segdir GROUP BY level 
           73  +  } {
           74  +    2 {0 1}
           75  +    3 0
           76  +  }
           77  +  
           78  +  #-------------------------------------------------------------------------
           79  +  # Test cases 2.* test that errors in the xxx part of the 'merge=xxx' are
           80  +  # handled correctly.
           81  +  #
           82  +  do_execsql_test 2.0 "CREATE VIRTUAL TABLE t2 USING $mod"
           83  +  
           84  +  foreach {tn arg} {
           85  +    1   {merge=abc}
           86  +    2   {merge=%%%}
           87  +    3   {merge=,}
           88  +    4   {merge=5,}
           89  +    5   {merge=6,%}
           90  +    6   {merge=6,six}
           91  +    7   {merge=6,1}
           92  +    8   {merge=6,0}
           93  +  } {
           94  +    do_catchsql_test 2.$tn { 
           95  +      INSERT INTO t2(t2) VALUES($arg);
           96  +    } {1 {SQL logic error or missing database}}
           97  +  }
           98  +  
           99  +  #-------------------------------------------------------------------------
          100  +  # Test cases 3.*
          101  +  #
          102  +  do_test 3.0 { 
          103  +    reset_db
          104  +    execsql { PRAGMA page_size = 512 }
          105  +    fts3_build_db_2 -module $mod 30040 
          106  +  } {}
          107  +  do_test 3.1 { fts3_integrity_check t2 } {ok}
          108  +  
          109  +  do_execsql_test 3.2 { 
          110  +    SELECT level, group_concat(idx, ' ') FROM t2_segdir GROUP BY level 
          111  +  } {
          112  +    0 {0 1 2 3 4 5 6} 
          113  +    1 {0 1 2 3 4} 
          114  +    2 {0 1 2 3 4} 
          115  +    3 {0 1 2 3 4 5 6}
          116  +  }
          117  +  
          118  +  do_execsql_test 3.3 { 
          119  +    INSERT INTO t2(t2) VALUES('merge=1000000,2');
          120  +    SELECT level, group_concat(idx, ' ') FROM t2_segdir GROUP BY level 
          121  +  } {
          122  +    0 0 
          123  +    2 0
          124  +    3 0 
          125  +    4 0
          126  +    6 0
          127  +  }
          128  +  
          129  +  #-------------------------------------------------------------------------
          130  +  # Test cases 4.*
          131  +  #
          132  +  reset_db
          133  +  do_execsql_test 4.1 "
          134  +    PRAGMA page_size = 512;
          135  +    CREATE VIRTUAL TABLE t4 USING $mod;
          136  +    PRAGMA main.page_size;
          137  +  " {512}
          138  +  
          139  +  do_test 4.2 {
          140  +    foreach x {a c b d e f g h i j k l m n o p} {
          141  +      execsql "INSERT INTO t4 VALUES('[string repeat $x 600]')"
          142  +    }
          143  +    execsql {SELECT level, group_concat(idx, ' ') FROM t4_segdir GROUP BY level}
          144  +  } {0 {0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15}}
          145  +  
          146  +  foreach {tn expect} {
          147  +    1  "0 {0 1 2 3 4 5 6 7 8 9 10 11 12 13} 1 0"
          148  +    2  "0 {0 1 2 3 4 5 6 7 8 9 10 11 12}    1 0"
          149  +    3  "0 {0 1 2 3 4 5 6 7 8 9 10 11}       1 0"
          150  +    4  "0 {0 1 2 3 4 5 6 7 8 9 10}          1 0"
          151  +    5  "0 {0 1 2 3 4 5 6 7 8 9}             1 0"
          152  +    6  "0 {0 1 2 3 4 5 6 7 8}               1 0"
          153  +    7  "0 {0 1 2 3 4 5 6 7}                 1 0"
          154  +    8  "0 {0 1 2 3 4 5 6}                   1 0"
          155  +    9  "0 {0 1 2 3 4 5}                     1 0"
          156  +  } {
          157  +    do_execsql_test 4.3.$tn {
          158  +      INSERT INTO t4(t4) VALUES('merge=1,16');
          159  +      SELECT level, group_concat(idx, ' ') FROM t4_segdir GROUP BY level;
          160  +    } $expect
          161  +  }
          162  +  
          163  +  do_execsql_test 4.4.1 {
          164  +    SELECT quote(value) FROM t4_stat WHERE rowid=1
          165  +  } {X'0006'}
          166  +  
          167  +  do_execsql_test 4.4.2 {
          168  +    DELETE FROM t4_stat WHERE rowid=1;
          169  +    INSERT INTO t4(t4) VALUES('merge=1,12');
          170  +    SELECT level, group_concat(idx, ' ') FROM t4_segdir GROUP BY level;
          171  +  } "0 {0 1 2 3 4 5}                     1 0"
          172  +  
          173  +  
          174  +  #-------------------------------------------------------------------------
          175  +  # Test cases 5.*
          176  +  #
          177  +  # Test that if a crisis-merge occurs that disrupts an ongoing incremental
          178  +  # merge, the next call to "merge=A,B" identifies this and starts a new
          179  +  # incremental merge. There are two scenarios:
          180  +  #
          181  +  #   * There are less segments on the input level that the disrupted
          182  +  #     incremental merge operated on, or
          183  +  #   
          184  +  #   * Sufficient segments exist on the input level but the segments 
          185  +  #     contain keys smaller than the largest key in the potential output 
          186  +  #     segment.
          187  +  # 
          188  +  do_test 5.1 {
          189  +    reset_db
          190  +    fts3_build_db_1 -module $mod 1000
          191  +  } {}
          192  +  
          193  +  do_execsql_test 5.2 {
          194  +    SELECT level, group_concat(idx, ' ') FROM t1_segdir GROUP BY level;
          195  +  } {
          196  +    0 {0 1 2 3 4 5 6 7} 
          197  +    1 {0 1 2 3 4 5 6 7 8 9 10 11 12 13} 
          198  +    2 {0 1 2}
          199  +  }
          200  +  
          201  +  do_execsql_test 5.3 {
          202  +    INSERT INTO t1(t1) VALUES('merge=1,5');
          203  +    INSERT INTO t1(t1) VALUES('merge=1,5');
          204  +    SELECT level, group_concat(idx, ' ') FROM t1_segdir GROUP BY level;
          205  +  } {
          206  +    0 {0 1 2}
          207  +    1 {0 1 2 3 4 5 6 7 8 9 10 11 12 13 14} 
          208  +    2 {0 1 2 3}
          209  +  }
          210  +  
          211  +  do_execsql_test 5.4 {SELECT quote(value) from t1_stat WHERE rowid=1} {X'0105'}
          212  +  do_test 5.5 {
          213  +    foreach docid [execsql {SELECT docid FROM t1}] {
          214  +      execsql {INSERT INTO t1 SELECT * FROM t1 WHERE docid=$docid}
          215  +    }
          216  +  } {}
          217  +  
          218  +  do_execsql_test 5.6 {SELECT quote(value) from t1_stat WHERE rowid=1} {X'0105'}
          219  +  
          220  +  do_execsql_test 5.7 {
          221  +    SELECT level, group_concat(idx, ' ') FROM t1_segdir GROUP BY level;
          222  +    SELECT quote(value) from t1_stat WHERE rowid=1;
          223  +  } {
          224  +    0 {0 1 2 3 4 5 6 7 8 9 10} 
          225  +    1 {0 1 2 3 4 5 6 7 8 9 10 11 12} 
          226  +    2 {0 1 2 3 4 5 6 7}
          227  +    X'0105'
          228  +  }
          229  +  
          230  +  do_execsql_test 5.8 {
          231  +    INSERT INTO t1(t1) VALUES('merge=1,6');
          232  +    INSERT INTO t1(t1) VALUES('merge=1,6');
          233  +    SELECT level, group_concat(idx, ' ') FROM t1_segdir GROUP BY level;
          234  +    SELECT quote(value) from t1_stat WHERE rowid=1;
          235  +  } {
          236  +    0 {0 1 2 3 4} 
          237  +    1 {0 1 2 3 4 5 6 7 8 9 10 11 12 13} 
          238  +    2 {0 1 2 3 4 5 6 7 8} X'0106'
          239  +  }
          240  +  
          241  +  do_test 5.8.1 { fts3_integrity_check t1 } ok
          242  +  
          243  +  do_test 5.9 {
          244  +    set L [expr 16*16*7 + 16*3 + 12]
          245  +    foreach docid [execsql {
          246  +        SELECT docid FROM t1 UNION ALL SELECT docid FROM t1 LIMIT $L
          247  +    }] {
          248  +      execsql {INSERT INTO t1 SELECT * FROM t1 WHERE docid=$docid}
          249  +    }
          250  +  } {}
          251  +  
          252  +  do_execsql_test 5.10 {
          253  +    SELECT level, group_concat(idx, ' ') FROM t1_segdir GROUP BY level;
          254  +    SELECT quote(value) from t1_stat WHERE rowid=1;
          255  +  } {
          256  +    0 0 1 {0 1} 2 0 3 0 X'0106'
          257  +  }
          258  +  
          259  +  do_execsql_test 5.11 {
          260  +    INSERT INTO t1(t1) VALUES('merge=1,6');
          261  +    SELECT level, group_concat(idx, ' ') FROM t1_segdir GROUP BY level;
          262  +    SELECT quote(value) from t1_stat WHERE rowid=1;
          263  +  } {
          264  +    0 0 1 {0 1} 2 0 3 0 X''
          265  +  }
          266  +  
          267  +  #-------------------------------------------------------------------------
          268  +  # Test cases 6.*
          269  +  #
          270  +  # At one point the following test caused an assert() to fail (because the
          271  +  # second 'merge=1,2' operation below actually "merges" a single input
          272  +  # segment, which was unexpected).
          273  +  #
          274  +  do_test 6.1 {
          275  +    reset_db
          276  +    set a [string repeat a 900]
          277  +    set b [string repeat b 900]
          278  +    set c [string repeat c 900]
          279  +    set d [string repeat d 900]
          280  +
          281  +    execsql "CREATE VIRTUAL TABLE t1 USING $mod"
          282  +    execsql {
          283  +      BEGIN;
          284  +        INSERT INTO t1 VALUES($a);
          285  +        INSERT INTO t1 VALUES($b);
          286  +      COMMIT;
          287  +      BEGIN;
          288  +        INSERT INTO t1 VALUES($c);
          289  +        INSERT INTO t1 VALUES($d);
          290  +      COMMIT;
          291  +    }
          292  +  
          293  +    execsql {
          294  +      INSERT INTO t1(t1) VALUES('merge=1,2');
          295  +      INSERT INTO t1(t1) VALUES('merge=1,2');
          296  +    }
          297  +  } {}
          298  +  
          299  +  #-------------------------------------------------------------------------
          300  +  # Test cases 7.*
          301  +  #
          302  +  # Test that the value returned by sqlite3_total_changes() increases by
          303  +  # 1 following a no-op "merge=A,B", or by more than 1 if actual work is
          304  +  # performed.
          305  +  #
          306  +  do_test 7.0 {
          307  +    reset_db
          308  +    fts3_build_db_1 -module $mod 1000
          309  +  } {}
          310  +  
          311  +  do_execsql_test 7.1 {
          312  +    SELECT level, group_concat(idx, ' ') FROM t1_segdir GROUP BY level
          313  +  } {
          314  +    0 {0 1 2 3 4 5 6 7} 
          315  +    1 {0 1 2 3 4 5 6 7 8 9 10 11 12 13} 
          316  +    2 {0 1 2}
          317  +  }
          318  +  do_test 7.2 {
          319  +    set x [db total_changes]
          320  +    execsql { INSERT INTO t1(t1) VALUES('merge=2,10') }
          321  +    expr { ([db total_changes] - $x)>1 }
          322  +  } {1}
          323  +  do_test 7.3 {
          324  +    set x [db total_changes]
          325  +    execsql { INSERT INTO t1(t1) VALUES('merge=200,10') }
          326  +    expr { ([db total_changes] - $x)>1 }
          327  +  } {1}
          328  +  do_test 7.4 {
          329  +    set x [db total_changes]
          330  +    execsql { INSERT INTO t1(t1) VALUES('merge=200,10') }
          331  +    expr { ([db total_changes] - $x)>1 }
          332  +  } {0}
          333  +  do_test 7.5 {
          334  +    set x [db total_changes]
          335  +    execsql { INSERT INTO t1(t1) VALUES('merge=200,10') }
          336  +    expr { ([db total_changes] - $x)>1 }
          337  +  } {0}
          338  +
          339  +}
          340  +
          341  +finish_test

Added test/fts4merge2.test.

            1  +
            2  +
            3  +set testdir [file dirname $argv0]
            4  +source $testdir/tester.tcl
            5  +source $testdir/fts3_common.tcl
            6  +source $testdir/malloc_common.tcl
            7  +set ::testprefix fts4merge2
            8  +
            9  +# If SQLITE_ENABLE_FTS3 is defined, omit this file.
           10  +ifcapable !fts3 {
           11  +  finish_test
           12  +  return
           13  +}
           14  +
           15  +do_test 1.0 {
           16  +  fts3_build_db_1 1000
           17  +  faultsim_save_and_close
           18  +} {}
           19  +
           20  +do_faultsim_test 1.1 -faults oom-* -prep {
           21  +  faultsim_restore_and_reopen
           22  +} -body {
           23  +  execsql { INSERT INTO t1(t1) VALUES('merge=32,4') }
           24  +} -test {
           25  +  faultsim_test_result {0 {}} 
           26  +}
           27  +
           28  +do_faultsim_test 1.2 -faults oom-t* -prep {
           29  +  if {$iFail<100} {set iFail 803}
           30  +  faultsim_restore_and_reopen
           31  +} -body {
           32  +  execsql { INSERT INTO t1(t1) VALUES('merge=1,2') }
           33  +  execsql { INSERT INTO t1(t1) VALUES('merge=1,2') }
           34  +} -test {
           35  +  faultsim_test_result {0 {}} 
           36  +}
           37  +
           38  +finish_test

Added test/fts4merge3.test.

            1  +# 2012 March 06
            2  +#
            3  +# The author disclaims copyright to this source code.  In place of
            4  +# a legal notice, here is a blessing:
            5  +#
            6  +#    May you do good and not evil.
            7  +#    May you find forgiveness for yourself and forgive others.
            8  +#    May you share freely, never taking more than you give.
            9  +#
           10  +#*************************************************************************
           11  +# This file implements regression tests for SQLite library.  The
           12  +# focus of this script is testing the incremental merge function.
           13  +#
           14  +
           15  +set testdir [file dirname $argv0]
           16  +source $testdir/tester.tcl
           17  +source $testdir/fts3_common.tcl
           18  +source $testdir/lock_common.tcl
           19  +source $testdir/bc_common.tcl
           20  +
           21  +set ::testprefix fts4merge3
           22  +
           23  +if {"" == [bc_find_binaries backcompat.test]} {
           24  +  finish_test
           25  +  return
           26  +}
           27  +
           28  +do_all_bc_test {
           29  +
           30  +  sql2 { PRAGMA page_size = 512 }
           31  +  if { 0==[catch { sql2 { CREATE VIRTUAL TABLE x USING fts4 } } ] } {
           32  +
           33  +    # Build a large database.
           34  +    set msg "this takes around 12 seconds"
           35  +    do_test "1.1 ($msg)" { fts3_build_db_2 20000 } {}
           36  +
           37  +    # Run some queries on it, using the old and new versions.
           38  +    do_test 1.2 { sql1 "SELECT docid FROM t2 WHERE t2 MATCH 'abc'" } {1485}
           39  +    do_test 1.3 { sql2 "SELECT docid FROM t2 WHERE t2 MATCH 'abc'" } {1485}
           40  +
           41  +    do_test 1.4 { sql2 "PRAGMA page_count" } {1286}
           42  +    do_test 1.5 { sql2 { 
           43  +      SELECT level, count(*) FROM t2_segdir GROUP BY level ORDER BY 1
           44  +    } } [list 0 15    1 1     2 14    3 4]
           45  +
           46  +    # Run some incr-merge operations on the db.
           47  +    for {set i 0} {$i<10} {incr i} {
           48  +      do_test 1.6.$i.1 { sql1 { INSERT INTO t2(t2) VALUES('merge=2,2') } } {}
           49  +      do_test 1.6.$i.2 { 
           50  +        sql2 "SELECT docid FROM t2 WHERE t2 MATCH 'abc'" 
           51  +      } {1485}
           52  +    }
           53  +
           54  +    do_test 1.7 { sql2 { 
           55  +      SELECT level, count(*) FROM t2_segdir GROUP BY level ORDER BY 1
           56  +    } } [list  0 1  2 18  3 5]
           57  +
           58  +    # Using the old connection, insert many rows. 
           59  +    do_test 1.8 {
           60  +      for {set i 0} {$i < 1500} {incr i} {
           61  +        sql2 "INSERT INTO t2 SELECT content FROM t2 WHERE docid = $i"
           62  +      }
           63  +    } {}
           64  +
           65  +    do_test 1.9 { sql2 { 
           66  +      SELECT level, count(*) FROM t2_segdir GROUP BY level ORDER BY 1
           67  +    } } [list  0 13  1 13  2 5  3 6]
           68  +
           69  +    # Run a big incr-merge operation on the db.
           70  +    do_test 1.10 { sql1 { INSERT INTO t2(t2) VALUES('merge=2000,2') } } {}
           71  +    do_test 1.11 { 
           72  +      sql2 "SELECT docid FROM t2 WHERE t2 MATCH 'abc'" 
           73  +    } {1485 21485}
           74  +
           75  +    do_test 1.12 {
           76  +      for {set i 0} {$i < 1500} {incr i} {
           77  +        sql2 "INSERT INTO t2 SELECT content FROM t2 WHERE docid = $i"
           78  +      }
           79  +    } {}
           80  +    do_test 1.13 { 
           81  +      sql2 "SELECT docid FROM t2 WHERE t2 MATCH 'abc'" 
           82  +    } {1485 21485 22985}
           83  +
           84  +    do_test 1.14 { 
           85  +      sql2 "INSERT INTO t2(t2) VALUES('optimize')"
           86  +      sql2 "SELECT docid FROM t2 WHERE t2 MATCH 'abc'" 
           87  +    } {1485 21485 22985}
           88  +
           89  +    do_test 1.15 { sql2 { 
           90  +      SELECT level, count(*) FROM t2_segdir GROUP BY level ORDER BY 1
           91  +    } } {6 1}
           92  +  }
           93  +}
           94  +
           95  +
           96  +finish_test

Changes to test/permutations.test.

   180    180     fts3defer.test fts3defer2.test fts3e.test fts3expr.test fts3expr2.test 
   181    181     fts3near.test fts3query.test fts3shared.test fts3snippet.test 
   182    182     fts3sort.test
   183    183     fts3fault.test fts3malloc.test fts3matchinfo.test
   184    184     fts3aux1.test fts3comp1.test fts3auto.test
   185    185     fts4aa.test fts4content.test
   186    186     fts3conf.test fts3prefix.test fts3fault2.test fts3corrupt.test
   187         -  fts3corrupt2.test fts3first.test fts4langid.test
          187  +  fts3corrupt2.test fts3first.test fts4langid.test fts4merge.test
          188  +  fts4check.test
   188    189   }
   189    190   
   190    191   
   191    192   lappend ::testsuitelist xxx
   192    193   #-------------------------------------------------------------------------
   193    194   # Define the coverage related test suites:
   194    195   #

Changes to test/trace2.test.

   126    126   
   127    127     do_trace_test 2.2 {
   128    128       INSERT INTO x1 VALUES('North northwest wind between 8 and 14 mph');
   129    129     } {
   130    130       "INSERT INTO x1 VALUES('North northwest wind between 8 and 14 mph');" 
   131    131       "-- INSERT INTO 'main'.'x1_content' VALUES(?,(?))" 
   132    132       "-- REPLACE INTO 'main'.'x1_docsize' VALUES(?,?)" 
   133         -    "-- SELECT value FROM 'main'.'x1_stat' WHERE id=0" 
   134         -    "-- REPLACE INTO 'main'.'x1_stat' VALUES(0,?)" 
          133  +    "-- SELECT value FROM 'main'.'x1_stat' WHERE id=?" 
          134  +    "-- REPLACE INTO 'main'.'x1_stat' VALUES(?,?)" 
   135    135       "-- SELECT (SELECT max(idx) FROM 'main'.'x1_segdir' WHERE level = ?) + 1" 
   136    136       "-- SELECT coalesce((SELECT max(blockid) FROM 'main'.'x1_segments') + 1, 1)"
   137         -    "-- INSERT INTO 'main'.'x1_segdir' VALUES(?,?,?,?,?,?)"
          137  +    "-- REPLACE INTO 'main'.'x1_segdir' VALUES(?,?,?,?,?,?)"
   138    138     }
   139    139   
   140    140     do_trace_test 2.3 {
   141    141       INSERT INTO x1(x1) VALUES('optimize');
   142    142     } {
   143    143       "INSERT INTO x1(x1) VALUES('optimize');"
   144    144       "-- SELECT DISTINCT level / (1024 * ?) FROM 'main'.'x1_segdir'"
   145    145       "-- SELECT idx, start_block, leaves_end_block, end_block, root FROM 'main'.'x1_segdir' WHERE level BETWEEN ? AND ?ORDER BY level DESC, idx ASC"
   146    146       "-- SELECT max(level) FROM 'main'.'x1_segdir' WHERE level BETWEEN ? AND ?"
   147    147       "-- SELECT coalesce((SELECT max(blockid) FROM 'main'.'x1_segments') + 1, 1)"
   148    148       "-- DELETE FROM 'main'.'x1_segdir' WHERE level BETWEEN ? AND ?"
   149         -    "-- INSERT INTO 'main'.'x1_segdir' VALUES(?,?,?,?,?,?)"
          149  +    "-- REPLACE INTO 'main'.'x1_segdir' VALUES(?,?,?,?,?,?)"
   150    150     }
   151    151   }
   152    152   
   153    153   finish_test