/ Check-in [862418e3]
Login

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

Overview
Comment:Use a WITHOUT ROWID table to index fts5 btree leaves. This is faster to query and only slightly larger than storing btree nodes within an intkey table.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | fts5-btree-index
Files: files | file ages | folders
SHA1: 862418e3506d4b7cca9c44d58c2eb9dc915d75c9
User & Date: dan 2015-07-15 19:46:02
Context
2015-07-16
20:24
Merge trunk changes, including fixes for compiler warnings in fts5 code, with this branch. check-in: 7190d79b user: dan tags: fts5-btree-index
2015-07-15
19:46
Use a WITHOUT ROWID table to index fts5 btree leaves. This is faster to query and only slightly larger than storing btree nodes within an intkey table. check-in: 862418e3 user: dan tags: fts5-btree-index
18:35
Fix some harmless compiler warnings. check-in: 110cd84f user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to ext/fts5/fts5_config.c.

    13     13   ** This is an SQLite module implementing full-text search.
    14     14   */
    15     15   
    16     16   
    17     17   
    18     18   #include "fts5Int.h"
    19     19   
    20         -#define FTS5_DEFAULT_PAGE_SIZE   1000
           20  +#define FTS5_DEFAULT_PAGE_SIZE   4050
    21     21   #define FTS5_DEFAULT_AUTOMERGE      4
    22     22   #define FTS5_DEFAULT_CRISISMERGE   16
    23     23   
    24     24   /* Maximum allowed page size */
    25     25   #define FTS5_MAX_PAGE_SIZE (128*1024)
    26     26   
    27     27   static int fts5_iswhitespace(char x){

Changes to ext/fts5/fts5_index.c.

   283    283   
   284    284   /*
   285    285   ** Each time a blob is read from the %_data table, it is padded with this
   286    286   ** many zero bytes. This makes it easier to decode the various record formats
   287    287   ** without overreading if the records are corrupt.
   288    288   */
   289    289   #define FTS5_DATA_ZERO_PADDING 8
          290  +#define FTS5_DATA_PADDING 20
   290    291   
   291         -typedef struct Fts5BtreeIter Fts5BtreeIter;
   292         -typedef struct Fts5BtreeIterLevel Fts5BtreeIterLevel;
   293    292   typedef struct Fts5Data Fts5Data;
   294    293   typedef struct Fts5DlidxIter Fts5DlidxIter;
   295    294   typedef struct Fts5DlidxLvl Fts5DlidxLvl;
   296    295   typedef struct Fts5DlidxWriter Fts5DlidxWriter;
   297    296   typedef struct Fts5NodeIter Fts5NodeIter;
   298    297   typedef struct Fts5PageWriter Fts5PageWriter;
   299    298   typedef struct Fts5SegIter Fts5SegIter;
................................................................................
   329    328     /* Error state. */
   330    329     int rc;                         /* Current error code */
   331    330   
   332    331     /* State used by the fts5DataXXX() functions. */
   333    332     sqlite3_blob *pReader;          /* RO incr-blob open on %_data table */
   334    333     sqlite3_stmt *pWriter;          /* "INSERT ... %_data VALUES(?,?)" */
   335    334     sqlite3_stmt *pDeleter;         /* "DELETE FROM %_data ... id>=? AND id<=?" */
          335  +  sqlite3_stmt *pIdxWriter;       /* "INSERT ... %_idx VALUES(?,?,?,?)" */
          336  +  sqlite3_stmt *pIdxDeleter;      /* "DELETE FROM %_idx WHERE segid=? */
          337  +  sqlite3_stmt *pIdxSelect;
   336    338     int nRead;                      /* Total number of blocks read */
   337    339   };
   338    340   
   339    341   struct Fts5DoclistIter {
   340    342     u8 *a;
   341    343     int n;
   342    344     int i;
................................................................................
   383    385     int pgno;                       /* Page number for this page */
   384    386     int bPrevValid;                 /* True if iPrev is valid */
   385    387     i64 iPrev;                      /* Previous docid value written to page */
   386    388     Fts5Buffer buf;                 /* Buffer containing page data */
   387    389   };
   388    390   struct Fts5SegWriter {
   389    391     int iSegid;                     /* Segid to write to */
   390         -  int nWriter;                    /* Number of entries in aWriter */
   391         -  Fts5PageWriter *aWriter;        /* Array of PageWriter objects */
          392  +  Fts5PageWriter writer;          /* PageWriter object */
   392    393     i64 iPrevRowid;                 /* Previous docid written to current leaf */
   393    394     u8 bFirstRowidInDoclist;        /* True if next rowid is first in doclist */
   394    395     u8 bFirstRowidInPage;           /* True if next rowid is first in page */
   395    396     u8 bFirstTermInPage;            /* True if next term will be first in leaf */
   396    397     int nLeafWritten;               /* Number of leaf pages written */
   397    398     int nEmpty;                     /* Number of contiguous term-less nodes */
   398    399   
   399    400     int nDlidx;                     /* Allocated size of aDlidx[] array */
   400    401     Fts5DlidxWriter *aDlidx;        /* Array of Fts5DlidxWriter objects */
          402  +
          403  +  /* Values to insert into the %_idx table */
          404  +  Fts5Buffer btterm;              /* TODO: Docs */
          405  +  int iBtPage;                    /* TODO: This */
   401    406   };
   402    407   
   403    408   /*
   404    409   ** Object for iterating through the merged results of one or more segments,
   405    410   ** visiting each term/docid pair in the merged data.
   406    411   **
   407    412   ** nSeg is always a power of two greater than or equal to the number of
................................................................................
   565    570   struct Fts5DlidxIter {
   566    571     int nLvl;
   567    572     int iSegid;
   568    573     Fts5DlidxLvl aLvl[1];
   569    574   };
   570    575   
   571    576   
   572         -
   573         -/*
   574         -** An Fts5BtreeIter object is used to iterate through all entries in the
   575         -** b-tree hierarchy belonging to a single fts5 segment. In this case the
   576         -** "b-tree hierarchy" is all b-tree nodes except leaves. Each entry in the
   577         -** b-tree hierarchy consists of the following:
   578         -**
   579         -**   iLeaf:  The page number of the leaf page the entry points to.
   580         -**
   581         -**   term:   A split-key that all terms on leaf page $iLeaf must be greater
   582         -**           than or equal to. The "term" associated with the first b-tree
   583         -**           hierarchy entry (the one that points to leaf page 1) is always 
   584         -**           an empty string.
   585         -**
   586         -**   nEmpty: The number of empty (termless) leaf pages that immediately
   587         -**           following iLeaf.
   588         -**
   589         -** The Fts5BtreeIter object is only used as part of the integrity-check code.
   590         -*/
   591         -struct Fts5BtreeIterLevel {
   592         -  Fts5NodeIter s;                 /* Iterator for the current node */
   593         -  Fts5Data *pData;                /* Data for the current node */
   594         -};
   595         -struct Fts5BtreeIter {
   596         -  Fts5Index *p;                   /* FTS5 backend object */
   597         -  Fts5StructureSegment *pSeg;     /* Iterate through this segment's b-tree */
   598         -  int nLvl;                       /* Size of aLvl[] array */
   599         -  Fts5BtreeIterLevel *aLvl;       /* Level for each tier of b-tree */
   600         -
   601         -  /* Output variables */
   602         -  Fts5Buffer term;                /* Current term */
   603         -  int iLeaf;                      /* Leaf containing terms >= current term */
   604         -  int nEmpty;                     /* Number of "empty" leaves following iLeaf */
   605         -  int bEof;                       /* Set to true at EOF */
   606         -  int bDlidx;                     /* True if there exists a dlidx */
   607         -};
   608         -
   609    577   
   610    578   /*
   611    579   ** The first argument passed to this macro is a pointer to an Fts5Buffer
   612    580   ** object.
   613    581   */
   614    582   #define fts5BufferSize(pBuf,n) {                \
   615    583     if( pBuf->nSpace<n ) {                        \
................................................................................
   744    712           fts5BufferSize(pBuf, MAX(nByte, p->pConfig->pgsz) + 20);
   745    713           pBuf->n = nByte;
   746    714           aOut = pBuf->p;
   747    715           if( aOut==0 ){
   748    716             rc = SQLITE_NOMEM;
   749    717           }
   750    718         }else{
   751         -        int nSpace = nByte + FTS5_DATA_ZERO_PADDING;
          719  +        int nSpace = nByte + FTS5_DATA_PADDING;
   752    720           pRet = (Fts5Data*)sqlite3_malloc(nSpace+sizeof(Fts5Data));
   753    721           if( pRet ){
   754    722             pRet->n = nByte;
   755    723             aOut = pRet->p = (u8*)&pRet[1];
   756    724           }else{
   757    725             rc = SQLITE_NOMEM;
   758    726           }
................................................................................
   800    768   /*
   801    769   ** Release a reference to data record returned by an earlier call to
   802    770   ** fts5DataRead().
   803    771   */
   804    772   static void fts5DataRelease(Fts5Data *pData){
   805    773     sqlite3_free(pData);
   806    774   }
          775  +
          776  +static int fts5IndexPrepareStmt(
          777  +  Fts5Index *p,
          778  +  sqlite3_stmt **ppStmt,
          779  +  char *zSql
          780  +){
          781  +  if( p->rc==SQLITE_OK ){
          782  +    if( zSql ){
          783  +      p->rc = sqlite3_prepare_v2(p->pConfig->db, zSql, -1, ppStmt, 0);
          784  +    }else{
          785  +      p->rc = SQLITE_NOMEM;
          786  +    }
          787  +  }
          788  +  sqlite3_free(zSql);
          789  +  return p->rc;
          790  +}
          791  +
   807    792   
   808    793   /*
   809    794   ** INSERT OR REPLACE a record into the %_data table.
   810    795   */
   811    796   static void fts5DataWrite(Fts5Index *p, i64 iRowid, const u8 *pData, int nData){
   812    797     if( p->rc!=SQLITE_OK ) return;
   813    798   
   814    799     if( p->pWriter==0 ){
   815    800       int rc = SQLITE_OK;
   816    801       Fts5Config *pConfig = p->pConfig;
   817         -    char *zSql = sqlite3Fts5Mprintf(&rc,
   818         -        "REPLACE INTO '%q'.%Q(id, block) VALUES(?,?)", pConfig->zDb, p->zDataTbl
   819         -    );
   820         -    if( zSql ){
   821         -      rc = sqlite3_prepare_v2(pConfig->db, zSql, -1, &p->pWriter, 0);
   822         -      sqlite3_free(zSql);
   823         -    }
   824         -    if( rc!=SQLITE_OK ){
   825         -      p->rc = rc;
   826         -      return;
   827         -    }
          802  +    fts5IndexPrepareStmt(p, &p->pWriter, sqlite3_mprintf(
          803  +          "REPLACE INTO '%q'.'%q_data'(id, block) VALUES(?,?)", 
          804  +          pConfig->zDb, pConfig->zName
          805  +    ));
          806  +    if( p->rc ) return;
   828    807     }
   829    808   
   830    809     sqlite3_bind_int64(p->pWriter, 1, iRowid);
   831    810     sqlite3_bind_blob(p->pWriter, 2, pData, nData, SQLITE_STATIC);
   832    811     sqlite3_step(p->pWriter);
   833    812     p->rc = sqlite3_reset(p->pWriter);
   834    813   }
................................................................................
   841    820   static void fts5DataDelete(Fts5Index *p, i64 iFirst, i64 iLast){
   842    821     if( p->rc!=SQLITE_OK ) return;
   843    822   
   844    823     if( p->pDeleter==0 ){
   845    824       int rc;
   846    825       Fts5Config *pConfig = p->pConfig;
   847    826       char *zSql = sqlite3_mprintf(
   848         -        "DELETE FROM '%q'.%Q WHERE id>=? AND id<=?", pConfig->zDb, p->zDataTbl
          827  +        "DELETE FROM '%q'.'%q_data' WHERE id>=? AND id<=?", 
          828  +          pConfig->zDb, pConfig->zName
   849    829       );
   850    830       if( zSql==0 ){
   851    831         rc = SQLITE_NOMEM;
   852    832       }else{
   853    833         rc = sqlite3_prepare_v2(pConfig->db, zSql, -1, &p->pDeleter, 0);
   854    834         sqlite3_free(zSql);
   855    835       }
................................................................................
   868    848   /*
   869    849   ** Remove all records associated with segment iSegid.
   870    850   */
   871    851   static void fts5DataRemoveSegment(Fts5Index *p, int iSegid){
   872    852     i64 iFirst = FTS5_SEGMENT_ROWID(iSegid, 0, 0);
   873    853     i64 iLast = FTS5_SEGMENT_ROWID(iSegid+1, 0, 0)-1;
   874    854     fts5DataDelete(p, iFirst, iLast);
          855  +  if( p->pIdxDeleter==0 ){
          856  +    Fts5Config *pConfig = p->pConfig;
          857  +    fts5IndexPrepareStmt(p, &p->pIdxDeleter, sqlite3_mprintf(
          858  +          "DELETE FROM '%q'.'%q_idx' WHERE segid=?",
          859  +          pConfig->zDb, pConfig->zName
          860  +    ));
          861  +  }
          862  +  if( p->rc==SQLITE_OK ){
          863  +    sqlite3_bind_int(p->pIdxDeleter, 1, iSegid);
          864  +    sqlite3_step(p->pIdxDeleter);
          865  +    p->rc = sqlite3_reset(p->pIdxDeleter);
          866  +  }
   875    867   }
   876    868   
   877    869   /*
   878    870   ** Release a reference to an Fts5Structure object returned by an earlier 
   879    871   ** call to fts5StructureRead() or fts5StructureDecode().
   880    872   */
   881    873   static void fts5StructureRelease(Fts5Structure *pStruct){
................................................................................
  2330   2322     assert( bGe==0 || (flags & FTS5INDEX_QUERY_DESC)==0 );
  2331   2323     assert( pTerm && nTerm );
  2332   2324     memset(pIter, 0, sizeof(*pIter));
  2333   2325     pIter->pSeg = pSeg;
  2334   2326   
  2335   2327     /* This block sets stack variable iPg to the leaf page number that may
  2336   2328     ** contain term (pTerm/nTerm), if it is present in the segment. */
  2337         -  for(h=pSeg->nHeight-1; h>0; h--){
  2338         -    i64 iRowid = FTS5_SEGMENT_ROWID(pSeg->iSegid, h, iPg);
  2339         -    fts5DataBuffer(p, pBuf, iRowid);
  2340         -    if( p->rc ) break;
  2341         -    iPg = fts5NodeSeek(pBuf, pTerm, nTerm, &bDlidx);
         2329  +  if( p->pIdxSelect==0 ){
         2330  +    Fts5Config *pConfig = p->pConfig;
         2331  +    fts5IndexPrepareStmt(p, &p->pIdxSelect, sqlite3_mprintf(
         2332  +          "SELECT pgno, dlidx FROM '%q'.'%q_idx' WHERE "
         2333  +          "segid=? AND term<=? ORDER BY term DESC LIMIT 1",
         2334  +          pConfig->zDb, pConfig->zName
         2335  +    ));
  2342   2336     }
         2337  +  if( p->rc ) return;
         2338  +  sqlite3_bind_int(p->pIdxSelect, 1, pSeg->iSegid);
         2339  +  sqlite3_bind_blob(p->pIdxSelect, 2, pTerm, nTerm, SQLITE_STATIC);
         2340  +  if( SQLITE_ROW==sqlite3_step(p->pIdxSelect) ){
         2341  +    iPg = sqlite3_column_int(p->pIdxSelect, 0);
         2342  +    bDlidx = sqlite3_column_int(p->pIdxSelect, 1);
         2343  +  }
         2344  +  p->rc = sqlite3_reset(p->pIdxSelect);
  2343   2345   
  2344   2346     if( iPg<pSeg->pgnoFirst ){
  2345   2347       iPg = pSeg->pgnoFirst;
  2346   2348       bDlidx = 0;
  2347   2349     }
  2348   2350   
  2349   2351     pIter->iLeafPgno = iPg - 1;
................................................................................
  3166   3168         pWriter->nDlidx = nLvl;
  3167   3169       }
  3168   3170     }
  3169   3171     return p->rc;
  3170   3172   }
  3171   3173   
  3172   3174   /*
  3173         -** If an "nEmpty" record must be written to the b-tree before the next
  3174         -** term, write it now. 
  3175         -*/
  3176         -static void fts5WriteBtreeNEmpty(Fts5Index *p, Fts5SegWriter *pWriter){
  3177         -  if( pWriter->nEmpty ){
  3178         -    int bFlag = 0;
  3179         -    Fts5PageWriter *pPg;
  3180         -    pPg = &pWriter->aWriter[1];
  3181         -
  3182         -    /* If there were FTS5_MIN_DLIDX_SIZE or more empty leaf pages written
  3183         -    ** to the database, also write the doclist-index to disk.  */
  3184         -    if( pWriter->aDlidx[0].buf.n>0 && pWriter->nEmpty>=FTS5_MIN_DLIDX_SIZE ){
  3185         -      bFlag = 1;
  3186         -    }
  3187         -    fts5WriteDlidxClear(p, pWriter, bFlag);
  3188         -    fts5BufferAppendVarint(&p->rc, &pPg->buf, bFlag);
  3189         -    fts5BufferAppendVarint(&p->rc, &pPg->buf, pWriter->nEmpty);
  3190         -    pWriter->nEmpty = 0;
  3191         -  }else{
  3192         -    fts5WriteDlidxClear(p, pWriter, 0);
  3193         -  }
  3194         -
  3195         -  assert( pWriter->nDlidx==0 || pWriter->aDlidx[0].buf.n==0 );
  3196         -  assert( pWriter->nDlidx==0 || pWriter->aDlidx[0].bPrevValid==0 );
  3197         -}
  3198         -
  3199         -static void fts5WriteBtreeGrow(Fts5Index *p, Fts5SegWriter *pWriter){
         3175  +** If the current doclist-index accumulating in pWriter->aDlidx[] is large
         3176  +** enough, flush it to disk and return 1. Otherwise discard it and return
         3177  +** zero.
         3178  +*/
         3179  +static int fts5WriteFlushDlidx(Fts5Index *p, Fts5SegWriter *pWriter){
         3180  +  int bFlag = 0;
         3181  +
         3182  +  /* If there were FTS5_MIN_DLIDX_SIZE or more empty leaf pages written
         3183  +  ** to the database, also write the doclist-index to disk.  */
         3184  +  if( pWriter->aDlidx[0].buf.n>0 && pWriter->nEmpty>=FTS5_MIN_DLIDX_SIZE ){
         3185  +    bFlag = 1;
         3186  +  }
         3187  +  fts5WriteDlidxClear(p, pWriter, bFlag);
         3188  +  pWriter->nEmpty = 0;
         3189  +  return bFlag;
         3190  +}
         3191  +
         3192  +/*
         3193  +** This function is called whenever processing of the doclist for the 
         3194  +** last term on leaf page (pWriter->iBtPage) is completed. 
         3195  +**
         3196  +** The doclist-index for that term is currently stored in-memory within the
         3197  +** Fts5SegWriter.aDlidx[] array. If it is large enough, this function
         3198  +** writes it out to disk. Or, if it is too small to bother with, discards
         3199  +** it.
         3200  +**
         3201  +** Fts5SegWriter.btterm currently contains the first term on page iBtPage.
         3202  +*/
         3203  +static void fts5WriteFlushBtree(Fts5Index *p, Fts5SegWriter *pWriter){
         3204  +  int bFlag;
         3205  +
         3206  +  assert( pWriter->iBtPage || pWriter->nEmpty==0 );
         3207  +  if( pWriter->iBtPage==0 ) return;
         3208  +  bFlag = fts5WriteFlushDlidx(p, pWriter);
         3209  +
  3200   3210     if( p->rc==SQLITE_OK ){
  3201         -    Fts5PageWriter *aNew;
  3202         -    Fts5PageWriter *pNew;
  3203         -    int nNew = sizeof(Fts5PageWriter) * (pWriter->nWriter+1);
  3204         -
  3205         -    aNew = (Fts5PageWriter*)sqlite3_realloc(pWriter->aWriter, nNew);
  3206         -    if( aNew==0 ){
  3207         -      p->rc = SQLITE_NOMEM;
  3208         -      return;
  3209         -    }
  3210         -
  3211         -    pNew = &aNew[pWriter->nWriter];
  3212         -    memset(pNew, 0, sizeof(Fts5PageWriter));
  3213         -    pNew->pgno = 1;
  3214         -    fts5BufferAppendVarint(&p->rc, &pNew->buf, 1);
  3215         -
  3216         -    pWriter->nWriter++;
  3217         -    pWriter->aWriter = aNew;
         3211  +    const char *z = (pWriter->btterm.n>0?(const char*)pWriter->btterm.p:"");
         3212  +    /* The following was already done in fts5WriteInit(): */
         3213  +    /* sqlite3_bind_int(p->pIdxWriter, 1, pWriter->iSegid); */
         3214  +    sqlite3_bind_blob(p->pIdxWriter, 2, z, pWriter->btterm.n, SQLITE_STATIC);
         3215  +    sqlite3_bind_int(p->pIdxWriter, 3, pWriter->iBtPage);
         3216  +    sqlite3_bind_int(p->pIdxWriter, 4, bFlag);
         3217  +    sqlite3_step(p->pIdxWriter);
         3218  +    p->rc = sqlite3_reset(p->pIdxWriter);
  3218   3219     }
         3220  +  pWriter->iBtPage = 0;
  3219   3221   }
  3220   3222   
  3221   3223   /*
  3222   3224   ** This is called once for each leaf page except the first that contains
  3223   3225   ** at least one term. Argument (nTerm/pTerm) is the split-key - a term that
  3224   3226   ** is larger than all terms written to earlier leaves, and equal to or
  3225   3227   ** smaller than the first term on the new leaf.
................................................................................
  3228   3230   ** has already occurred when this function is called, it is a no-op.
  3229   3231   */
  3230   3232   static void fts5WriteBtreeTerm(
  3231   3233     Fts5Index *p,                   /* FTS5 backend object */
  3232   3234     Fts5SegWriter *pWriter,         /* Writer object */
  3233   3235     int nTerm, const u8 *pTerm      /* First term on new page */
  3234   3236   ){
  3235         -  int iHeight;
  3236         -  for(iHeight=1; 1; iHeight++){
  3237         -    Fts5PageWriter *pPage;
  3238         -
  3239         -    if( iHeight>=pWriter->nWriter ){
  3240         -      fts5WriteBtreeGrow(p, pWriter);
  3241         -      if( p->rc ) return;
  3242         -    }
  3243         -    pPage = &pWriter->aWriter[iHeight];
  3244         -
  3245         -    fts5WriteBtreeNEmpty(p, pWriter);
  3246         -
  3247         -    if( pPage->buf.n>=p->pConfig->pgsz ){
  3248         -      /* pPage will be written to disk. The term will be written into the
  3249         -      ** parent of pPage.  */
  3250         -      i64 iRowid = FTS5_SEGMENT_ROWID(pWriter->iSegid, iHeight, pPage->pgno);
  3251         -      fts5DataWrite(p, iRowid, pPage->buf.p, pPage->buf.n);
  3252         -      fts5BufferZero(&pPage->buf);
  3253         -      fts5BufferZero(&pPage->term);
  3254         -      fts5BufferAppendVarint(&p->rc, &pPage->buf, pPage[-1].pgno);
  3255         -      pPage->pgno++;
  3256         -    }else{
  3257         -      int nPre = fts5PrefixCompress(pPage->term.n, pPage->term.p, nTerm, pTerm);
  3258         -      fts5BufferAppendVarint(&p->rc, &pPage->buf, nPre+2);
  3259         -      fts5BufferAppendVarint(&p->rc, &pPage->buf, nTerm-nPre);
  3260         -      fts5BufferAppendBlob(&p->rc, &pPage->buf, nTerm-nPre, pTerm+nPre);
  3261         -      fts5BufferSet(&p->rc, &pPage->term, nTerm, pTerm);
  3262         -      break;
  3263         -    }
  3264         -  }
         3237  +  fts5WriteFlushBtree(p, pWriter);
         3238  +  fts5BufferSet(&p->rc, &pWriter->btterm, nTerm, pTerm);
         3239  +  pWriter->iBtPage = pWriter->writer.pgno;
  3265   3240   }
  3266   3241   
  3267   3242   /*
  3268   3243   ** This function is called when flushing a leaf page that contains no
  3269   3244   ** terms at all to disk.
  3270   3245   */
  3271   3246   static void fts5WriteBtreeNoTerm(
................................................................................
  3341   3316       }else{
  3342   3317         bDone = 1;
  3343   3318       }
  3344   3319   
  3345   3320       if( pDlidx->bPrevValid ){
  3346   3321         iVal = iRowid - pDlidx->iPrev;
  3347   3322       }else{
  3348         -      i64 iPgno = (i==0 ? pWriter->aWriter[0].pgno : pDlidx[-1].pgno);
         3323  +      i64 iPgno = (i==0 ? pWriter->writer.pgno : pDlidx[-1].pgno);
  3349   3324         assert( pDlidx->buf.n==0 );
  3350   3325         sqlite3Fts5BufferAppendVarint(&p->rc, &pDlidx->buf, !bDone);
  3351   3326         sqlite3Fts5BufferAppendVarint(&p->rc, &pDlidx->buf, iPgno);
  3352   3327         iVal = iRowid;
  3353   3328       }
  3354   3329   
  3355   3330       sqlite3Fts5BufferAppendVarint(&p->rc, &pDlidx->buf, iVal);
................................................................................
  3356   3331       pDlidx->bPrevValid = 1;
  3357   3332       pDlidx->iPrev = iRowid;
  3358   3333     }
  3359   3334   }
  3360   3335   
  3361   3336   static void fts5WriteFlushLeaf(Fts5Index *p, Fts5SegWriter *pWriter){
  3362   3337     static const u8 zero[] = { 0x00, 0x00, 0x00, 0x00 };
  3363         -  Fts5PageWriter *pPage = &pWriter->aWriter[0];
         3338  +  Fts5PageWriter *pPage = &pWriter->writer;
  3364   3339     i64 iRowid;
  3365   3340   
  3366   3341     if( pWriter->bFirstTermInPage ){
  3367   3342       /* No term was written to this page. */
  3368   3343       assert( 0==fts5GetU16(&pPage->buf.p[2]) );
  3369   3344       fts5WriteBtreeNoTerm(p, pWriter);
  3370   3345     }
................................................................................
  3395   3370   */
  3396   3371   static void fts5WriteAppendTerm(
  3397   3372     Fts5Index *p, 
  3398   3373     Fts5SegWriter *pWriter,
  3399   3374     int nTerm, const u8 *pTerm 
  3400   3375   ){
  3401   3376     int nPrefix;                    /* Bytes of prefix compression for term */
  3402         -  Fts5PageWriter *pPage = &pWriter->aWriter[0];
         3377  +  Fts5PageWriter *pPage = &pWriter->writer;
  3403   3378   
  3404   3379     assert( pPage->buf.n==0 || pPage->buf.n>4 );
  3405   3380     if( pPage->buf.n==0 ){
  3406   3381       /* Zero the first term and first docid fields */
  3407   3382       static const u8 zero[] = { 0x00, 0x00, 0x00, 0x00 };
  3408   3383       fts5BufferAppendBlob(&p->rc, &pPage->buf, 4, zero);
  3409   3384       assert( pWriter->bFirstTermInPage );
................................................................................
  3430   3405         ** copy of (pTerm/nTerm) into the parent node. This is slightly
  3431   3406         ** inefficient, but still correct.  */
  3432   3407         int n = nTerm;
  3433   3408         if( pPage->term.n ){
  3434   3409           n = 1 + fts5PrefixCompress(pPage->term.n, pPage->term.p, nTerm, pTerm);
  3435   3410         }
  3436   3411         fts5WriteBtreeTerm(p, pWriter, n, pTerm);
  3437         -      pPage = &pWriter->aWriter[0];
         3412  +      pPage = &pWriter->writer;
  3438   3413       }
  3439   3414     }else{
  3440   3415       nPrefix = fts5PrefixCompress(pPage->term.n, pPage->term.p, nTerm, pTerm);
  3441   3416       fts5BufferAppendVarint(&p->rc, &pPage->buf, nPrefix);
  3442   3417     }
  3443   3418   
  3444   3419     /* Append the number of bytes of new data, then the term data itself
................................................................................
  3468   3443   static void fts5WriteAppendRowid(
  3469   3444     Fts5Index *p, 
  3470   3445     Fts5SegWriter *pWriter,
  3471   3446     i64 iRowid,
  3472   3447     int nPos
  3473   3448   ){
  3474   3449     if( p->rc==SQLITE_OK ){
  3475         -    Fts5PageWriter *pPage = &pWriter->aWriter[0];
         3450  +    Fts5PageWriter *pPage = &pWriter->writer;
  3476   3451   
  3477   3452       /* If this is to be the first docid written to the page, set the 
  3478   3453       ** docid-pointer in the page-header. Also append a value to the dlidx
  3479   3454       ** buffer, in case a doclist-index is required.  */
  3480   3455       if( pWriter->bFirstRowidInPage ){
  3481   3456         fts5PutU16(pPage->buf.p, pPage->buf.n);
  3482   3457         fts5WriteDlidxAppend(p, pWriter, iRowid);
................................................................................
  3503   3478   
  3504   3479   static void fts5WriteAppendPoslistData(
  3505   3480     Fts5Index *p, 
  3506   3481     Fts5SegWriter *pWriter, 
  3507   3482     const u8 *aData, 
  3508   3483     int nData
  3509   3484   ){
  3510         -  Fts5PageWriter *pPage = &pWriter->aWriter[0];
         3485  +  Fts5PageWriter *pPage = &pWriter->writer;
  3511   3486     const u8 *a = aData;
  3512   3487     int n = nData;
  3513   3488     
  3514   3489     assert( p->pConfig->pgsz>0 );
  3515   3490     while( p->rc==SQLITE_OK && (pPage->buf.n + n)>=p->pConfig->pgsz ){
  3516   3491       int nReq = p->pConfig->pgsz - pPage->buf.n;
  3517   3492       int nCopy = 0;
................................................................................
  3526   3501     }
  3527   3502     if( n>0 ){
  3528   3503       fts5BufferAppendBlob(&p->rc, &pPage->buf, n, a);
  3529   3504     }
  3530   3505   }
  3531   3506   
  3532   3507   static void fts5WriteAppendZerobyte(Fts5Index *p, Fts5SegWriter *pWriter){
  3533         -  fts5BufferAppendVarint(&p->rc, &pWriter->aWriter[0].buf, 0);
         3508  +  fts5BufferAppendVarint(&p->rc, &pWriter->writer.buf, 0);
  3534   3509   }
  3535   3510   
  3536   3511   /*
  3537   3512   ** Flush any data cached by the writer object to the database. Free any
  3538   3513   ** allocations associated with the writer.
  3539   3514   */
  3540   3515   static void fts5WriteFinish(
  3541   3516     Fts5Index *p, 
  3542   3517     Fts5SegWriter *pWriter,         /* Writer object */
  3543   3518     int *pnHeight,                  /* OUT: Height of the b-tree */
  3544   3519     int *pnLeaf                     /* OUT: Number of leaf pages in b-tree */
  3545   3520   ){
  3546   3521     int i;
         3522  +  Fts5PageWriter *pLeaf = &pWriter->writer;
  3547   3523     if( p->rc==SQLITE_OK ){
  3548         -    Fts5PageWriter *pLeaf = &pWriter->aWriter[0];
  3549   3524       if( pLeaf->pgno==1 && pLeaf->buf.n==0 ){
  3550   3525         *pnLeaf = 0;
  3551   3526         *pnHeight = 0;
  3552   3527       }else{
  3553   3528         if( pLeaf->buf.n>4 ){
  3554   3529           fts5WriteFlushLeaf(p, pWriter);
  3555   3530         }
  3556   3531         *pnLeaf = pLeaf->pgno-1;
  3557         -      if( pWriter->nWriter==1 && pWriter->nEmpty>=FTS5_MIN_DLIDX_SIZE ){
  3558         -        fts5WriteBtreeGrow(p, pWriter);
  3559         -      }
  3560         -      if( pWriter->nWriter>1 ){
  3561         -        fts5WriteBtreeNEmpty(p, pWriter);
  3562         -      }
  3563         -      *pnHeight = pWriter->nWriter;
  3564   3532   
  3565         -      for(i=1; i<pWriter->nWriter; i++){
  3566         -        Fts5PageWriter *pPg = &pWriter->aWriter[i];
  3567         -        fts5DataWrite(p, 
  3568         -            FTS5_SEGMENT_ROWID(pWriter->iSegid, i, pPg->pgno), 
  3569         -            pPg->buf.p, pPg->buf.n
  3570         -        );
  3571         -      }
         3533  +      fts5WriteFlushBtree(p, pWriter);
         3534  +      *pnHeight = 0;
  3572   3535       }
  3573   3536     }
  3574         -  for(i=0; i<pWriter->nWriter; i++){
  3575         -    Fts5PageWriter *pPg = &pWriter->aWriter[i];
  3576         -    fts5BufferFree(&pPg->term);
  3577         -    fts5BufferFree(&pPg->buf);
  3578         -  }
  3579         -  sqlite3_free(pWriter->aWriter);
         3537  +  fts5BufferFree(&pLeaf->term);
         3538  +  fts5BufferFree(&pLeaf->buf);
         3539  +  fts5BufferFree(&pWriter->btterm);
  3580   3540   
  3581   3541     for(i=0; i<pWriter->nDlidx; i++){
  3582   3542       sqlite3Fts5BufferFree(&pWriter->aDlidx[i].buf);
  3583   3543     }
  3584   3544     sqlite3_free(pWriter->aDlidx);
  3585   3545   }
  3586   3546   
................................................................................
  3588   3548     Fts5Index *p, 
  3589   3549     Fts5SegWriter *pWriter, 
  3590   3550     int iSegid
  3591   3551   ){
  3592   3552     memset(pWriter, 0, sizeof(Fts5SegWriter));
  3593   3553     pWriter->iSegid = iSegid;
  3594   3554   
  3595         -  pWriter->aWriter = (Fts5PageWriter*)fts5IdxMalloc(p, sizeof(Fts5PageWriter));
  3596         -  if( fts5WriteDlidxGrow(p, pWriter, 1) ) return;
  3597         -  pWriter->nWriter = 1;
  3598         -  pWriter->nDlidx = 1;
  3599         -  pWriter->aWriter[0].pgno = 1;
         3555  +  fts5WriteDlidxGrow(p, pWriter, 1);
         3556  +  pWriter->writer.pgno = 1;
  3600   3557     pWriter->bFirstTermInPage = 1;
  3601         -}
         3558  +  pWriter->iBtPage = 1;
  3602   3559   
  3603         -static void fts5WriteInitForAppend(
  3604         -  Fts5Index *p,                   /* FTS5 backend object */
  3605         -  Fts5SegWriter *pWriter,         /* Writer to initialize */
  3606         -  Fts5StructureSegment *pSeg      /* Segment object to append to */
  3607         -){
  3608         -  int nByte = pSeg->nHeight * sizeof(Fts5PageWriter);
  3609         -  memset(pWriter, 0, sizeof(Fts5SegWriter));
  3610         -  pWriter->iSegid = pSeg->iSegid;
  3611         -  pWriter->aWriter = (Fts5PageWriter*)fts5IdxMalloc(p, nByte);
  3612         -  pWriter->aDlidx = (Fts5DlidxWriter*)fts5IdxMalloc(p, sizeof(Fts5DlidxWriter));
         3560  +  if( p->pIdxWriter==0 ){
         3561  +    Fts5Config *pConfig = p->pConfig;
         3562  +    fts5IndexPrepareStmt(p, &p->pIdxWriter, sqlite3_mprintf(
         3563  +          "INSERT INTO '%q'.'%q_idx'(segid,term,pgno,dlidx) VALUES(?,?,?,?)", 
         3564  +          pConfig->zDb, pConfig->zName
         3565  +    ));
         3566  +  }
  3613   3567   
  3614   3568     if( p->rc==SQLITE_OK ){
  3615         -    int pgno = 1;
  3616         -    int i;
  3617         -    pWriter->nDlidx = 1;
  3618         -    pWriter->nWriter = pSeg->nHeight;
  3619         -    pWriter->aWriter[0].pgno = pSeg->pgnoLast+1;
  3620         -    for(i=pSeg->nHeight-1; i>0; i--){
  3621         -      i64 iRowid = FTS5_SEGMENT_ROWID(pWriter->iSegid, i, pgno);
  3622         -      Fts5PageWriter *pPg = &pWriter->aWriter[i];
  3623         -      pPg->pgno = pgno;
  3624         -      fts5DataBuffer(p, &pPg->buf, iRowid);
  3625         -      if( p->rc==SQLITE_OK ){
  3626         -        Fts5NodeIter ss;
  3627         -        fts5NodeIterInit(pPg->buf.p, pPg->buf.n, &ss);
  3628         -        while( ss.aData ) fts5NodeIterNext(&p->rc, &ss);
  3629         -        fts5BufferSet(&p->rc, &pPg->term, ss.term.n, ss.term.p);
  3630         -        pgno = ss.iChild;
  3631         -        fts5NodeIterFree(&ss);
  3632         -      }
  3633         -    }
  3634         -    assert( p->rc!=SQLITE_OK || (pgno+pWriter->nEmpty)==pSeg->pgnoLast );
  3635         -    pWriter->bFirstTermInPage = 1;
  3636         -    assert( pWriter->aWriter[0].term.n==0 );
         3569  +    sqlite3_bind_int(p->pIdxWriter, 1, pWriter->iSegid);
  3637   3570     }
  3638   3571   }
  3639   3572   
  3640   3573   /*
  3641   3574   ** Iterator pIter was used to iterate through the input segments of on an
  3642   3575   ** incremental merge operation. This function is called if the incremental
  3643   3576   ** merge step has finished but the input has not been completely exhausted.
................................................................................
  3669   3602           fts5BufferZero(&buf);
  3670   3603           fts5BufferAppendBlob(&p->rc, &buf, sizeof(aHdr), aHdr);
  3671   3604           fts5BufferAppendVarint(&p->rc, &buf, pSeg->term.n);
  3672   3605           fts5BufferAppendBlob(&p->rc, &buf, pSeg->term.n, pSeg->term.p);
  3673   3606           fts5BufferAppendBlob(&p->rc, &buf, pData->n - iOff, &pData->p[iOff]);
  3674   3607           fts5DataRelease(pData);
  3675   3608           pSeg->pSeg->pgnoFirst = pSeg->iTermLeafPgno;
  3676         -        fts5DataDelete(p, FTS5_SEGMENT_ROWID(iId, 0, 1),iLeafRowid);
         3609  +        fts5DataDelete(p, FTS5_SEGMENT_ROWID(iId, 0, 1), iLeafRowid);
  3677   3610           fts5DataWrite(p, iLeafRowid, buf.p, buf.n);
  3678   3611         }
  3679   3612       }
  3680   3613     }
  3681   3614     fts5BufferFree(&buf);
  3682   3615   }
  3683   3616   
................................................................................
  3716   3649   
  3717   3650     memset(&writer, 0, sizeof(Fts5SegWriter));
  3718   3651     memset(&term, 0, sizeof(Fts5Buffer));
  3719   3652     if( pLvl->nMerge ){
  3720   3653       pLvlOut = &pStruct->aLevel[iLvl+1];
  3721   3654       assert( pLvlOut->nSeg>0 );
  3722   3655       nInput = pLvl->nMerge;
  3723         -    fts5WriteInitForAppend(p, &writer, &pLvlOut->aSeg[pLvlOut->nSeg-1]);
  3724   3656       pSeg = &pLvlOut->aSeg[pLvlOut->nSeg-1];
         3657  +
         3658  +    fts5WriteInit(p, &writer, pSeg->iSegid);
         3659  +    writer.writer.pgno = pSeg->pgnoLast+1;
         3660  +    writer.iBtPage = 0;
  3725   3661     }else{
  3726   3662       int iSegid = fts5AllocateSegid(p, pStruct);
  3727   3663   
  3728   3664       /* Extend the Fts5Structure object as required to ensure the output
  3729   3665       ** segment exists. */
  3730   3666       if( iLvl==pStruct->nLevel-1 ){
  3731   3667         fts5StructureAddLevel(&p->rc, ppStruct);
................................................................................
  3808   3744       pLvl->nSeg -= nInput;
  3809   3745       pLvl->nMerge = 0;
  3810   3746       if( pSeg->pgnoLast==0 ){
  3811   3747         pLvlOut->nSeg--;
  3812   3748         pStruct->nSegment--;
  3813   3749       }
  3814   3750     }else{
  3815         -    assert( pSeg->nHeight>0 && pSeg->pgnoLast>0 );
         3751  +    assert( pSeg->pgnoLast>0 );
  3816   3752       fts5TrimSegments(p, pIter);
  3817   3753       pLvl->nMerge = nInput;
  3818   3754     }
  3819   3755   
  3820   3756     fts5MultiIterFree(p, pIter);
  3821   3757     fts5BufferFree(&term);
  3822   3758     if( pnRem ) *pnRem -= writer.nLeafWritten;
................................................................................
  3983   3919   
  3984   3920       Fts5SegWriter writer;
  3985   3921       fts5WriteInit(p, &writer, iSegid);
  3986   3922   
  3987   3923       /* Pre-allocate the buffer used to assemble leaf pages to the target
  3988   3924       ** page size.  */
  3989   3925       assert( pgsz>0 );
  3990         -    pBuf = &writer.aWriter[0].buf;
         3926  +    pBuf = &writer.writer.buf;
  3991   3927       fts5BufferGrow(&p->rc, pBuf, pgsz + 20);
  3992   3928   
  3993   3929       /* Begin scanning through hash table entries. This loop runs once for each
  3994   3930       ** term/doclist currently stored within the hash table. */
  3995   3931       if( p->rc==SQLITE_OK ){
  3996   3932         memset(pBuf->p, 0, 4);
  3997   3933         pBuf->n = 4;
................................................................................
  4007   3943         sqlite3Fts5HashScanEntry(pHash, &zTerm, &pDoclist, &nDoclist);
  4008   3944         nTerm = strlen(zTerm);
  4009   3945   
  4010   3946         /* Decide if the term will fit on the current leaf. If it will not, 
  4011   3947         ** flush the leaf to disk here.  */
  4012   3948         if( (pBuf->n + nTerm + 2) > pgsz ){
  4013   3949           fts5WriteFlushLeaf(p, &writer);
  4014         -        pBuf = &writer.aWriter[0].buf;
         3950  +        pBuf = &writer.writer.buf;
  4015   3951           if( (nTerm + 32) > pBuf->nSpace ){
  4016   3952             fts5BufferGrow(&p->rc, pBuf, nTerm + 32 - pBuf->n);
  4017   3953             if( p->rc ) break;
  4018   3954           }
  4019   3955         }
  4020   3956   
  4021   3957         /* Write the term to the leaf. And if it is the first on the leaf, and
................................................................................
  4024   3960         if( writer.bFirstTermInPage==0 ){
  4025   3961           int nPre = fts5PrefixCompress(nTerm, zPrev, nTerm, (const u8*)zTerm);
  4026   3962           pBuf->n += sqlite3Fts5PutVarint(&pBuf->p[pBuf->n], nPre);
  4027   3963           nSuffix = nTerm - nPre;
  4028   3964         }else{
  4029   3965           fts5PutU16(&pBuf->p[2], pBuf->n);
  4030   3966           writer.bFirstTermInPage = 0;
  4031         -        if( writer.aWriter[0].pgno!=1 ){
         3967  +        if( writer.writer.pgno!=1 ){
  4032   3968             int nPre = fts5PrefixCompress(nTerm, zPrev, nTerm, (const u8*)zTerm);
  4033   3969             fts5WriteBtreeTerm(p, &writer, nPre+1, (const u8*)zTerm);
  4034         -          pBuf = &writer.aWriter[0].buf;
         3970  +          pBuf = &writer.writer.buf;
  4035   3971             assert( nPre<nTerm );
  4036   3972           }
  4037   3973           nSuffix = nTerm;
  4038   3974         }
  4039   3975         pBuf->n += sqlite3Fts5PutVarint(&pBuf->p[pBuf->n], nSuffix);
  4040   3976         fts5BufferSafeAppendBlob(pBuf, (const u8*)&zTerm[nTerm-nSuffix], nSuffix);
  4041   3977   
  4042   3978         /* We just wrote a term into page writer.aWriter[0].pgno. If a 
  4043   3979         ** doclist-index is to be generated for this doclist, it will be
  4044   3980         ** associated with this page. */
  4045   3981         assert( writer.nDlidx>0 && writer.aDlidx[0].buf.n==0 );
  4046         -      writer.aDlidx[0].pgno = writer.aWriter[0].pgno;
         3982  +      writer.aDlidx[0].pgno = writer.writer.pgno;
  4047   3983   
  4048   3984         if( pgsz>=(pBuf->n + nDoclist + 1) ){
  4049   3985           /* The entire doclist will fit on the current leaf. */
  4050   3986           fts5BufferSafeAppendBlob(pBuf, pDoclist, nDoclist);
  4051   3987         }else{
  4052   3988           i64 iRowid = 0;
  4053   3989           i64 iDelta = 0;
................................................................................
  4096   4032                   n = fts5PoslistPrefix(&pPoslist[iPos], nSpace);
  4097   4033                 }
  4098   4034                 assert( n>0 );
  4099   4035                 fts5BufferSafeAppendBlob(pBuf, &pPoslist[iPos], n);
  4100   4036                 iPos += n;
  4101   4037                 if( pBuf->n>=pgsz ){
  4102   4038                   fts5WriteFlushLeaf(p, &writer);
  4103         -                pBuf = &writer.aWriter[0].buf;
         4039  +                pBuf = &writer.writer.buf;
  4104   4040                 }
  4105   4041                 if( iPos>=nCopy ) break;
  4106   4042               }
  4107   4043             }
  4108   4044             iOff += nCopy;
  4109   4045           }
  4110   4046         }
................................................................................
  4129   4065         pSeg->nHeight = nHeight;
  4130   4066         pSeg->pgnoFirst = 1;
  4131   4067         pSeg->pgnoLast = pgnoLast;
  4132   4068         pStruct->nSegment++;
  4133   4069       }
  4134   4070       fts5StructurePromote(p, 0, pStruct);
  4135   4071     }
  4136         -
  4137   4072   
  4138   4073     fts5IndexAutomerge(p, &pStruct, pgnoLast);
  4139   4074     fts5IndexCrisismerge(p, &pStruct);
  4140   4075     fts5StructureWrite(p, pStruct);
  4141   4076     fts5StructureRelease(pStruct);
  4142   4077   }
  4143   4078   
................................................................................
  4558   4493       p->nWorkUnit = FTS5_WORK_UNIT;
  4559   4494       p->nMaxPendingData = 1024*1024;
  4560   4495       p->zDataTbl = sqlite3Fts5Mprintf(&rc, "%s_data", pConfig->zName);
  4561   4496       if( p->zDataTbl && bCreate ){
  4562   4497         rc = sqlite3Fts5CreateTable(
  4563   4498             pConfig, "data", "id INTEGER PRIMARY KEY, block BLOB", 0, pzErr
  4564   4499         );
         4500  +      if( rc==SQLITE_OK ){
         4501  +        rc = sqlite3Fts5CreateTable(pConfig, "idx", 
         4502  +            "segid, term, pgno, dlidx, PRIMARY KEY(segid, term)", 
         4503  +            1, pzErr
         4504  +        );
         4505  +      }
  4565   4506         if( rc==SQLITE_OK ){
  4566   4507           rc = sqlite3Fts5IndexReinit(p);
  4567   4508         }
  4568   4509       }
  4569   4510     }
  4570   4511   
  4571   4512     assert( rc!=SQLITE_OK || p->rc==SQLITE_OK );
................................................................................
  4581   4522   */
  4582   4523   int sqlite3Fts5IndexClose(Fts5Index *p){
  4583   4524     int rc = SQLITE_OK;
  4584   4525     if( p ){
  4585   4526       assert( p->pReader==0 );
  4586   4527       sqlite3_finalize(p->pWriter);
  4587   4528       sqlite3_finalize(p->pDeleter);
         4529  +    sqlite3_finalize(p->pIdxWriter);
         4530  +    sqlite3_finalize(p->pIdxDeleter);
         4531  +    sqlite3_finalize(p->pIdxSelect);
  4588   4532       sqlite3Fts5HashFree(p->pHash);
  4589   4533       sqlite3Fts5BufferFree(&p->scratch);
  4590   4534       sqlite3_free(p->zDataTbl);
  4591   4535       sqlite3_free(p);
  4592   4536     }
  4593   4537     return rc;
  4594   4538   }
................................................................................
  4930   4874     ret += (ret<<3) + iCol;
  4931   4875     ret += (ret<<3) + iPos;
  4932   4876     if( iIdx>=0 ) ret += (ret<<3) + (FTS5_MAIN_PREFIX + iIdx);
  4933   4877     for(i=0; i<nTerm; i++) ret += (ret<<3) + pTerm[i];
  4934   4878     return ret;
  4935   4879   }
  4936   4880   
  4937         -static void fts5BtreeIterInit(
  4938         -  Fts5Index *p, 
  4939         -  Fts5StructureSegment *pSeg, 
  4940         -  Fts5BtreeIter *pIter
  4941         -){
  4942         -  int nByte;
  4943         -  int i;
  4944         -  nByte = sizeof(pIter->aLvl[0]) * (pSeg->nHeight-1);
  4945         -  memset(pIter, 0, sizeof(*pIter));
  4946         -  if( nByte ){
  4947         -    pIter->aLvl = (Fts5BtreeIterLevel*)fts5IdxMalloc(p, nByte);
  4948         -  }
  4949         -  if( p->rc==SQLITE_OK ){
  4950         -    pIter->nLvl = pSeg->nHeight-1;
  4951         -    pIter->p = p;
  4952         -    pIter->pSeg = pSeg;
  4953         -  }
  4954         -  for(i=0; p->rc==SQLITE_OK && i<pIter->nLvl; i++){
  4955         -    i64 iRowid = FTS5_SEGMENT_ROWID(pSeg->iSegid, i+1, 1);
  4956         -    Fts5Data *pData;
  4957         -    pIter->aLvl[i].pData = pData = fts5DataRead(p, iRowid);
  4958         -    if( pData ){
  4959         -      fts5NodeIterInit(pData->p, pData->n, &pIter->aLvl[i].s);
  4960         -    }
  4961         -  }
  4962         -
  4963         -  if( pIter->nLvl==0 || p->rc ){
  4964         -    pIter->bEof = 1;
  4965         -    pIter->iLeaf = pSeg->pgnoLast;
  4966         -  }else{
  4967         -    pIter->nEmpty = pIter->aLvl[0].s.nEmpty;
  4968         -    pIter->iLeaf = pIter->aLvl[0].s.iChild;
  4969         -    pIter->bDlidx = pIter->aLvl[0].s.bDlidx;
  4970         -  }
  4971         -}
  4972         -
  4973         -static void fts5BtreeIterNext(Fts5BtreeIter *pIter){
  4974         -  Fts5Index *p = pIter->p;
  4975         -  int i;
  4976         -
  4977         -  assert( pIter->bEof==0 && pIter->aLvl[0].s.aData );
  4978         -  for(i=0; i<pIter->nLvl && p->rc==SQLITE_OK; i++){
  4979         -    Fts5BtreeIterLevel *pLvl = &pIter->aLvl[i];
  4980         -    fts5NodeIterNext(&p->rc, &pLvl->s);
  4981         -    if( pLvl->s.aData ){
  4982         -      fts5BufferSet(&p->rc, &pIter->term, pLvl->s.term.n, pLvl->s.term.p);
  4983         -      break;
  4984         -    }else{
  4985         -      fts5NodeIterFree(&pLvl->s);
  4986         -      fts5DataRelease(pLvl->pData);
  4987         -      pLvl->pData = 0;
  4988         -    }
  4989         -  }
  4990         -  if( i==pIter->nLvl || p->rc ){
  4991         -    pIter->bEof = 1;
  4992         -  }else{
  4993         -    int iSegid = pIter->pSeg->iSegid;
  4994         -    for(i--; i>=0; i--){
  4995         -      Fts5BtreeIterLevel *pLvl = &pIter->aLvl[i];
  4996         -      i64 iRowid = FTS5_SEGMENT_ROWID(iSegid, i+1, pLvl[1].s.iChild);
  4997         -      pLvl->pData = fts5DataRead(p, iRowid);
  4998         -      if( pLvl->pData ){
  4999         -        fts5NodeIterInit(pLvl->pData->p, pLvl->pData->n, &pLvl->s);
  5000         -      }
  5001         -    }
  5002         -  }
  5003         -
  5004         -  pIter->nEmpty = pIter->aLvl[0].s.nEmpty;
  5005         -  pIter->bDlidx = pIter->aLvl[0].s.bDlidx;
  5006         -  pIter->iLeaf = pIter->aLvl[0].s.iChild;
  5007         -}
  5008         -
  5009         -static void fts5BtreeIterFree(Fts5BtreeIter *pIter){
  5010         -  int i;
  5011         -  for(i=0; i<pIter->nLvl; i++){
  5012         -    Fts5BtreeIterLevel *pLvl = &pIter->aLvl[i];
  5013         -    fts5NodeIterFree(&pLvl->s);
  5014         -    if( pLvl->pData ){
  5015         -      fts5DataRelease(pLvl->pData);
  5016         -      pLvl->pData = 0;
  5017         -    }
  5018         -  }
  5019         -  sqlite3_free(pIter->aLvl);
  5020         -  fts5BufferFree(&pIter->term);
  5021         -}
  5022         -
  5023   4881   #ifdef SQLITE_DEBUG
  5024   4882   /*
  5025   4883   ** This function is purely an internal test. It does not contribute to 
  5026   4884   ** FTS functionality, or even the integrity-check, in any way.
  5027   4885   **
  5028   4886   ** Instead, it tests that the same set of pgno/rowid combinations are 
  5029   4887   ** visited regardless of whether the doclist-index identified by parameters
................................................................................
  5162   5020     p->rc = rc;
  5163   5021   }
  5164   5022    
  5165   5023   #else
  5166   5024   # define fts5TestDlidxReverse(x,y,z)
  5167   5025   # define fts5TestTerm(u,v,w,x,y,z)
  5168   5026   #endif
         5027  +
         5028  +/*
         5029  +** Check that:
         5030  +**
         5031  +**   1) All leaves of pSeg between iFirst and iLast (inclusive) exist and
         5032  +**      contain zero terms.
         5033  +**   2) All leaves of pSeg between iNoRowid and iLast (inclusive) exist and
         5034  +**      contain zero rowids.
         5035  +*/
         5036  +static void fts5IndexIntegrityCheckEmpty(
         5037  +  Fts5Index *p,
         5038  +  Fts5StructureSegment *pSeg,     /* Segment to check internal consistency */
         5039  +  int iFirst,
         5040  +  int iNoRowid,
         5041  +  int iLast
         5042  +){
         5043  +  int i;
         5044  +
         5045  +  /* Now check that the iter.nEmpty leaves following the current leaf
         5046  +  ** (a) exist and (b) contain no terms. */
         5047  +  for(i=iFirst; p->rc==SQLITE_OK && i<=iLast; i++){
         5048  +    Fts5Data *pLeaf = fts5DataRead(p, FTS5_SEGMENT_ROWID(pSeg->iSegid, 0, i));
         5049  +    if( pLeaf ){
         5050  +      if( 0!=fts5GetU16(&pLeaf->p[2]) ) p->rc = FTS5_CORRUPT;
         5051  +      if( i>=iNoRowid && 0!=fts5GetU16(&pLeaf->p[0]) ) p->rc = FTS5_CORRUPT;
         5052  +    }
         5053  +    fts5DataRelease(pLeaf);
         5054  +    if( p->rc ) break;
         5055  +  }
         5056  +}
  5169   5057   
  5170   5058   static void fts5IndexIntegrityCheckSegment(
  5171   5059     Fts5Index *p,                   /* FTS5 backend object */
  5172   5060     Fts5StructureSegment *pSeg      /* Segment to check internal consistency */
  5173   5061   ){
  5174         -  Fts5BtreeIter iter;             /* Used to iterate through b-tree hierarchy */
         5062  +  Fts5Config *pConfig = p->pConfig;
         5063  +  sqlite3_stmt *pStmt = 0;
         5064  +  int rc2;
         5065  +  int iIdxPrevLeaf = pSeg->pgnoFirst-1;
         5066  +  int iDlidxPrevLeaf = pSeg->pgnoLast;
  5175   5067   
  5176   5068     if( pSeg->pgnoFirst==0 ) return;
         5069  +
         5070  +  fts5IndexPrepareStmt(p, &pStmt, sqlite3_mprintf(
         5071  +      "SELECT segid, term, pgno, dlidx FROM '%q'.'%q_idx' WHERE segid=%d",
         5072  +      pConfig->zDb, pConfig->zName, pSeg->iSegid
         5073  +  ));
  5177   5074   
  5178   5075     /* Iterate through the b-tree hierarchy.  */
  5179         -  for(fts5BtreeIterInit(p, pSeg, &iter);
  5180         -      p->rc==SQLITE_OK && iter.bEof==0;
  5181         -      fts5BtreeIterNext(&iter)
  5182         -  ){
         5076  +  while( p->rc==SQLITE_OK && SQLITE_ROW==sqlite3_step(pStmt) ){
  5183   5077       i64 iRow;                     /* Rowid for this leaf */
  5184   5078       Fts5Data *pLeaf;              /* Data for this leaf */
  5185   5079       int iOff;                     /* Offset of first term on leaf */
  5186   5080       int i;                        /* Used to iterate through empty leaves */
         5081  +
         5082  +    int nIdxTerm = sqlite3_column_bytes(pStmt, 1);
         5083  +    const char *zIdxTerm = (const char*)sqlite3_column_text(pStmt, 1);
         5084  +    int iIdxLeaf = sqlite3_column_int(pStmt, 2);
         5085  +    int bIdxDlidx = sqlite3_column_int(pStmt, 3);
  5187   5086   
  5188   5087       /* If the leaf in question has already been trimmed from the segment, 
  5189   5088       ** ignore this b-tree entry. Otherwise, load it into memory. */
  5190         -    if( iter.iLeaf<pSeg->pgnoFirst ) continue;
  5191         -    iRow = FTS5_SEGMENT_ROWID(pSeg->iSegid, 0, iter.iLeaf);
         5089  +    if( iIdxLeaf<pSeg->pgnoFirst ) continue;
         5090  +    iRow = FTS5_SEGMENT_ROWID(pSeg->iSegid, 0, iIdxLeaf);
  5192   5091       pLeaf = fts5DataRead(p, iRow);
  5193   5092       if( pLeaf==0 ) break;
  5194   5093   
  5195   5094       /* Check that the leaf contains at least one term, and that it is equal
  5196         -    ** to or larger than the split-key in iter.term.  Also check that if there
         5095  +    ** to or larger than the split-key in zIdxTerm.  Also check that if there
  5197   5096       ** is also a rowid pointer within the leaf page header, it points to a
  5198   5097       ** location before the term.  */
  5199   5098       iOff = fts5GetU16(&pLeaf->p[2]);
  5200   5099       if( iOff==0 ){
  5201   5100         p->rc = FTS5_CORRUPT;
  5202   5101       }else{
  5203   5102         int iRowidOff;
................................................................................
  5205   5104         int res;                    /* Comparison of term and split-key */
  5206   5105   
  5207   5106         iRowidOff = fts5GetU16(&pLeaf->p[0]);
  5208   5107         if( iRowidOff>=iOff ){
  5209   5108           p->rc = FTS5_CORRUPT;
  5210   5109         }else{
  5211   5110           iOff += fts5GetVarint32(&pLeaf->p[iOff], nTerm);
  5212         -        res = memcmp(&pLeaf->p[iOff], iter.term.p, MIN(nTerm, iter.term.n));
  5213         -        if( res==0 ) res = nTerm - iter.term.n;
         5111  +        res = memcmp(&pLeaf->p[iOff], zIdxTerm, MIN(nTerm, nIdxTerm));
         5112  +        if( res==0 ) res = nTerm - nIdxTerm;
  5214   5113           if( res<0 ) p->rc = FTS5_CORRUPT;
  5215   5114         }
  5216   5115       }
  5217   5116       fts5DataRelease(pLeaf);
  5218   5117       if( p->rc ) break;
  5219   5118   
  5220   5119   
  5221   5120       /* Now check that the iter.nEmpty leaves following the current leaf
  5222   5121       ** (a) exist and (b) contain no terms. */
  5223         -    for(i=1; p->rc==SQLITE_OK && i<=iter.nEmpty; i++){
  5224         -      pLeaf = fts5DataRead(p, iRow+i);
  5225         -      if( pLeaf && 0!=fts5GetU16(&pLeaf->p[2]) ){
  5226         -        p->rc = FTS5_CORRUPT;
  5227         -      }
  5228         -      fts5DataRelease(pLeaf);
  5229         -    }
         5122  +    fts5IndexIntegrityCheckEmpty(
         5123  +        p, pSeg, iIdxPrevLeaf+1, iDlidxPrevLeaf+1, iIdxLeaf-1
         5124  +    );
         5125  +    if( p->rc ) break;
  5230   5126   
  5231   5127       /* If there is a doclist-index, check that it looks right. */
  5232         -    if( iter.bDlidx ){
         5128  +    if( bIdxDlidx ){
  5233   5129         Fts5DlidxIter *pDlidx = 0;  /* For iterating through doclist index */
  5234         -      int iPrevLeaf = iter.iLeaf;
         5130  +      int iPrevLeaf = iIdxLeaf;
  5235   5131         int iSegid = pSeg->iSegid;
  5236   5132         int iPg;
  5237   5133         i64 iKey;
  5238   5134   
  5239         -      for(pDlidx=fts5DlidxIterInit(p, 0, iSegid, iter.iLeaf);
         5135  +      for(pDlidx=fts5DlidxIterInit(p, 0, iSegid, iIdxLeaf);
  5240   5136             fts5DlidxIterEof(p, pDlidx)==0;
  5241   5137             fts5DlidxIterNext(p, pDlidx)
  5242   5138         ){
  5243   5139   
  5244   5140           /* Check any rowid-less pages that occur before the current leaf. */
  5245   5141           for(iPg=iPrevLeaf+1; iPg<fts5DlidxIterPgno(pDlidx); iPg++){
  5246   5142             iKey = FTS5_SEGMENT_ROWID(iSegid, 0, iPg);
................................................................................
  5265   5161               fts5GetVarint(&pLeaf->p[iRowidOff], (u64*)&iRowid);
  5266   5162               if( iRowid!=fts5DlidxIterRowid(pDlidx) ) p->rc = FTS5_CORRUPT;
  5267   5163             }
  5268   5164             fts5DataRelease(pLeaf);
  5269   5165           }
  5270   5166         }
  5271   5167   
  5272         -      for(iPg=iPrevLeaf+1; iPg<=(iter.iLeaf + iter.nEmpty); iPg++){
  5273         -        iKey = FTS5_SEGMENT_ROWID(iSegid, 0, iPg);
  5274         -        pLeaf = fts5DataRead(p, iKey);
  5275         -        if( pLeaf ){
  5276         -          if( fts5GetU16(&pLeaf->p[0])!=0 ) p->rc = FTS5_CORRUPT;
  5277         -          fts5DataRelease(pLeaf);
  5278         -        }
  5279         -      }
  5280         -
         5168  +      iDlidxPrevLeaf = iPg;
  5281   5169         fts5DlidxIterFree(pDlidx);
  5282         -      fts5TestDlidxReverse(p, iSegid, iter.iLeaf);
         5170  +      fts5TestDlidxReverse(p, iSegid, iIdxLeaf);
         5171  +    }else{
         5172  +      iDlidxPrevLeaf = pSeg->pgnoLast;
         5173  +      /* TODO: Check there is no doclist index */
  5283   5174       }
         5175  +
         5176  +    iIdxPrevLeaf = iIdxLeaf;
  5284   5177     }
  5285   5178   
         5179  +  rc2 = sqlite3_finalize(pStmt);
         5180  +  if( p->rc==SQLITE_OK ) p->rc = rc2;
         5181  +
  5286   5182     /* Page iter.iLeaf must now be the rightmost leaf-page in the segment */
         5183  +#if 0
  5287   5184     if( p->rc==SQLITE_OK && iter.iLeaf!=pSeg->pgnoLast ){
  5288   5185       p->rc = FTS5_CORRUPT;
  5289   5186     }
  5290         -
  5291         -  fts5BtreeIterFree(&iter);
         5187  +#endif
  5292   5188   }
  5293   5189   
  5294   5190   
  5295   5191   /*
  5296   5192   ** Run internal checks to ensure that the FTS index (a) is internally 
  5297   5193   ** consistent and (b) contains entries for which the XOR of the checksums
  5298   5194   ** as calculated by fts5IndexEntryCksum() is cksum.

Changes to ext/fts5/fts5_storage.c.

   176    176   /*
   177    177   ** Drop all shadow tables. Return SQLITE_OK if successful or an SQLite error
   178    178   ** code otherwise.
   179    179   */
   180    180   int sqlite3Fts5DropAll(Fts5Config *pConfig){
   181    181     int rc = fts5ExecPrintf(pConfig->db, 0, 
   182    182         "DROP TABLE IF EXISTS %Q.'%q_data';"
          183  +      "DROP TABLE IF EXISTS %Q.'%q_idx';"
   183    184         "DROP TABLE IF EXISTS %Q.'%q_config';",
          185  +      pConfig->zDb, pConfig->zName,
   184    186         pConfig->zDb, pConfig->zName,
   185    187         pConfig->zDb, pConfig->zName
   186    188     );
   187    189     if( rc==SQLITE_OK && pConfig->bColumnsize ){
   188    190       rc = fts5ExecPrintf(pConfig->db, 0, 
   189    191           "DROP TABLE IF EXISTS %Q.'%q_docsize';",
   190    192           pConfig->zDb, pConfig->zName
................................................................................
   214    216   }
   215    217   
   216    218   int sqlite3Fts5StorageRename(Fts5Storage *pStorage, const char *zName){
   217    219     Fts5Config *pConfig = pStorage->pConfig;
   218    220     int rc = sqlite3Fts5StorageSync(pStorage, 1);
   219    221   
   220    222     fts5StorageRenameOne(pConfig, &rc, "data", zName);
          223  +  fts5StorageRenameOne(pConfig, &rc, "idx", zName);
   221    224     fts5StorageRenameOne(pConfig, &rc, "config", zName);
   222    225     if( pConfig->bColumnsize ){
   223    226       fts5StorageRenameOne(pConfig, &rc, "docsize", zName);
   224    227     }
   225    228     if( pConfig->eContent==FTS5_CONTENT_NORMAL ){
   226    229       fts5StorageRenameOne(pConfig, &rc, "content", zName);
   227    230     }

Changes to ext/fts5/test/fts5aa.test.

    23     23   
    24     24   do_execsql_test 1.0 {
    25     25     CREATE VIRTUAL TABLE t1 USING fts5(a, b, c);
    26     26     SELECT name, sql FROM sqlite_master;
    27     27   } {
    28     28     t1 {CREATE VIRTUAL TABLE t1 USING fts5(a, b, c)}
    29     29     t1_data {CREATE TABLE 't1_data'(id INTEGER PRIMARY KEY, block BLOB)}
           30  +  t1_idx {CREATE TABLE 't1_idx'(segid, term, pgno, dlidx, PRIMARY KEY(segid, term)) WITHOUT ROWID}
    30     31     t1_content {CREATE TABLE 't1_content'(id INTEGER PRIMARY KEY, c0, c1, c2)}
    31     32     t1_docsize {CREATE TABLE 't1_docsize'(id INTEGER PRIMARY KEY, sz BLOB)}
    32     33     t1_config {CREATE TABLE 't1_config'(k PRIMARY KEY, v) WITHOUT ROWID}
    33     34   }
    34     35   
    35     36   do_execsql_test 1.1 {
    36     37     DROP TABLE t1;
................................................................................
    43     44   reset_db
    44     45   do_execsql_test 2.0 {
    45     46     CREATE VIRTUAL TABLE t1 USING fts5(x,y);
    46     47   }
    47     48   do_execsql_test 2.1 {
    48     49     INSERT INTO t1 VALUES('a b c', 'd e f');
    49     50   }
           51  +
    50     52   do_test 2.2 {
    51     53     execsql { SELECT fts5_decode(id, block) FROM t1_data WHERE id==10 }
    52         -} {/{\(structure\) {lvl=0 nMerge=0 nSeg=1 {id=[0123456789]* h=1 leaves=1..1}}}/}
           54  +} {/{\(structure\) {lvl=0 nMerge=0 nSeg=1 {id=[0123456789]* h=0 leaves=1..1}}}/}
    53     55   
    54     56   foreach w {a b c d e f} {
    55     57     do_execsql_test 2.3.$w.asc {
    56     58       SELECT rowid FROM t1 WHERE t1 MATCH $w;
    57     59     } {1}
    58     60     do_execsql_test 2.3.$w.desc {
    59     61       SELECT rowid FROM t1 WHERE t1 MATCH $w ORDER BY rowid DESC;

Changes to ext/fts5/test/fts5content.test.

   243    243   #-------------------------------------------------------------------------
   244    244   # Check that a contentless table can be dropped.
   245    245   #
   246    246   reset_db
   247    247   do_execsql_test 6.1 {
   248    248     CREATE VIRTUAL TABLE xx USING fts5(x, y, content="");
   249    249     SELECT name FROM sqlite_master;
   250         -} {xx xx_data xx_docsize xx_config}
          250  +} {xx xx_data xx_idx xx_docsize xx_config}
   251    251   do_execsql_test 6.2 {
   252    252     DROP TABLE xx;
   253    253     SELECT name FROM sqlite_master;
   254    254   } {}
   255    255   
   256    256   
   257    257   finish_test
   258    258