/ Check-in [ba359d78]
Login

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

Overview
Comment:Add "segment promotion" to fts5. This prevents the FTS index from growing indefinitely as data is added and deleted.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | fts5
Files: files | file ages | folders
SHA1: ba359d78e166d78e0dc89e3c63a9a41e9ffea989
User & Date: dan 2014-08-07 18:47:33
Context
2014-08-09
18:02
Use multiple memory allocations for a single Fts5Structure object. This is probably less efficient but much easier to get right. check-in: 2821825f user: dan tags: fts5
2014-08-07
18:47
Add "segment promotion" to fts5. This prevents the FTS index from growing indefinitely as data is added and deleted. check-in: ba359d78 user: dan tags: fts5
2014-08-06
20:04
Avoid writing delete markers to the oldest segment in an FTS index. check-in: 1baeb1ce user: dan tags: fts5
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to ext/fts5/fts5_index.c.

   651    651     }else{
   652    652       sqlite3Fts5BufferAppendPrintf(pRc, pBuf, "(idx=%d segid=%d h=%d pgno=%d)",
   653    653           iIdx, iSegid, iHeight, iPgno
   654    654       );
   655    655     }
   656    656   }
   657    657   
          658  +static void fts5DebugStructure(
          659  +  int *pRc,                       /* IN/OUT: error code */
          660  +  Fts5Buffer *pBuf,
          661  +  Fts5Structure *p
          662  +){
          663  +  int iLvl, iSeg;                 /* Iterate through levels, segments */
          664  +
          665  +  for(iLvl=0; iLvl<p->nLevel; iLvl++){
          666  +    Fts5StructureLevel *pLvl = &p->aLevel[iLvl];
          667  +    sqlite3Fts5BufferAppendPrintf(pRc, pBuf, 
          668  +        " {lvl=%d nMerge=%d", iLvl, pLvl->nMerge
          669  +    );
          670  +    for(iSeg=0; iSeg<pLvl->nSeg; iSeg++){
          671  +      Fts5StructureSegment *pSeg = &pLvl->aSeg[iSeg];
          672  +      sqlite3Fts5BufferAppendPrintf(pRc, pBuf, 
          673  +          " {id=%d h=%d leaves=%d..%d}", pSeg->iSegid, pSeg->nHeight, 
          674  +          pSeg->pgnoFirst, pSeg->pgnoLast
          675  +      );
          676  +    }
          677  +    sqlite3Fts5BufferAppendPrintf(pRc, pBuf, "}");
          678  +  }
          679  +}
          680  +
          681  +
   658    682   
   659    683   static void fts5PutU16(u8 *aOut, u16 iVal){
   660    684     aOut[0] = (iVal>>8);
   661    685     aOut[1] = (iVal&0xFF);
   662    686   }
   663    687   
   664    688   static u16 fts5GetU16(const u8 *aIn){
................................................................................
  1075   1099         fts5BufferAppendVarint(&p->rc, &buf, pLvl->aSeg[iSeg].pgnoLast);
  1076   1100       }
  1077   1101     }
  1078   1102   
  1079   1103     fts5DataWrite(p, FTS5_STRUCTURE_ROWID(iIdx), buf.p, buf.n);
  1080   1104     fts5BufferFree(&buf);
  1081   1105   }
         1106  +
         1107  +#if 0
         1108  +static void fts5PrintStructure(const char *zCaption, Fts5Structure *pStruct){
         1109  +  int rc = SQLITE_OK;
         1110  +  Fts5Buffer buf;
         1111  +  memset(&buf, 0, sizeof(buf));
         1112  +  fts5DebugStructure(&rc, &buf, pStruct);
         1113  +  fprintf(stdout, "%s: %s\n", zCaption, buf.p);
         1114  +  fflush(stdout);
         1115  +  fts5BufferFree(&buf);
         1116  +}
         1117  +#else
         1118  +# define fts5PrintStructure(x,y)
         1119  +#endif
         1120  +
         1121  +/*
         1122  +** Return a copy of index structure pStruct. Except, promote as many segments
         1123  +** as possible to level iPromote. If an OOM occurs, NULL is returned.
         1124  +*/
         1125  +static void fts5StructurePromoteTo(
         1126  +  Fts5Index *p,
         1127  +  int iPromote,
         1128  +  int szPromote,
         1129  +  Fts5Structure *pStruct
         1130  +){
         1131  +  Fts5Structure *pNew;
         1132  +  u8 *pSpace;
         1133  +  int nSeg = fts5StructureCountSegments(pStruct);
         1134  +  int nLvl = pStruct->nLevel;
         1135  +  int nByte = (
         1136  +      sizeof(Fts5Structure) + 
         1137  +      sizeof(Fts5StructureLevel) * (nLvl+1) +
         1138  +      sizeof(Fts5StructureSegment) * (nSeg+nLvl+1)
         1139  +  );
         1140  +  int iTst;
         1141  +
         1142  +  pNew = fts5IdxMalloc(p, nByte);
         1143  +  if( !pNew ) return;
         1144  +  pNew->nWriteCounter = pStruct->nWriteCounter;
         1145  +  pNew->nLevel = pStruct->nLevel;
         1146  +  pSpace = (u8*)&pNew->aLevel[nLvl+1];
         1147  +
         1148  +  for(iTst=0; iTst<nLvl; iTst++){
         1149  +    int nCopy;
         1150  +    Fts5StructureLevel *pLvlOut = &pNew->aLevel[iTst];
         1151  +    pLvlOut->aSeg = (Fts5StructureSegment*)pSpace;
         1152  +
         1153  +    if( iTst==iPromote ){
         1154  +      int il, is;
         1155  +      int nSegCopy = 0;
         1156  +
         1157  +      /* Figure out the number of segments that will be promoted. */
         1158  +      for(il=iTst+1; il<pStruct->nLevel; il++){
         1159  +        Fts5StructureLevel *pLvl = &pStruct->aLevel[il];
         1160  +        if( pLvl->nMerge ) break;
         1161  +        for(is=pLvl->nSeg-1; is>=0; is--){
         1162  +          Fts5StructureSegment *pSeg = &pLvl->aSeg[is];
         1163  +          int sz = pSeg->pgnoLast - pSeg->pgnoFirst + 1;
         1164  +          if( sz>szPromote ){
         1165  +            il = pStruct->nLevel;
         1166  +            break;
         1167  +          }
         1168  +          nSegCopy++;
         1169  +        }
         1170  +      }
         1171  +      assert( nSegCopy>0 );
         1172  +      pSpace += (nSegCopy * sizeof(Fts5StructureSegment));
         1173  +      pLvlOut->nSeg = nSegCopy;
         1174  +
         1175  +      for(il=iTst+1; il<pStruct->nLevel && nSegCopy>0; il++){
         1176  +        Fts5StructureLevel *pLvl = &pStruct->aLevel[il];
         1177  +        for(is=pLvl->nSeg-1; is>=0 && nSegCopy>0; is--){
         1178  +          Fts5StructureSegment *pSeg = &pLvl->aSeg[is];
         1179  +          nSegCopy--;
         1180  +          memcpy(&pLvlOut->aSeg[nSegCopy], pSeg, sizeof(Fts5StructureSegment));
         1181  +          pLvl->nSeg--;
         1182  +        }
         1183  +      }
         1184  +      assert( nSegCopy==0 );
         1185  +    }
         1186  +
         1187  +    nCopy = pStruct->aLevel[iTst].nSeg * sizeof(Fts5StructureSegment);
         1188  +    if( nCopy ) memcpy(pSpace, pStruct->aLevel[iTst].aSeg, nCopy);
         1189  +    pSpace += (nCopy + sizeof(Fts5StructureSegment));
         1190  +    pLvlOut->nSeg += pStruct->aLevel[iTst].nSeg;
         1191  +  }
         1192  +
         1193  +  fts5PrintStructure("NEW", pNew);
         1194  +  memcpy(pStruct, pNew, nByte);
         1195  +  for(iTst=0; iTst<pNew->nLevel; iTst++){
         1196  +    int iOff = pNew->aLevel[iTst].aSeg - (Fts5StructureSegment*)pNew;
         1197  +    pStruct->aLevel[iTst].aSeg = &((Fts5StructureSegment*)pStruct)[iOff];
         1198  +  }
         1199  +  sqlite3_free(pNew);
         1200  +}
         1201  +
         1202  +/*
         1203  +** A new segment has just been written to level iLvl of index structure
         1204  +** pStruct. This function determines if any segments should be promoted
         1205  +** as a result. Segments are promoted in two scenarios:
         1206  +**
         1207  +**   a) If the segment just written is smaller than one or more segments
         1208  +**      within the previous populated level, it is promoted to the previous
         1209  +**      populated level.
         1210  +**
         1211  +**   b) If the segment just written is larger than the newest segment on
         1212  +**      the next populated level, then that segment, and any other adjacent
         1213  +**      segments that are also smaller than the one just written, are 
         1214  +**      promoted. 
         1215  +**
         1216  +** If one or more segments are promoted, the structure object is updated
         1217  +** to reflect this.
         1218  +*/
         1219  +static void fts5StructurePromote(
         1220  +  Fts5Index *p,                   /* FTS5 backend object */
         1221  +  int iLvl,                       /* Index level just updated */
         1222  +  Fts5Structure *pStruct          /* Index structure */
         1223  +){
         1224  +  if( p->rc==SQLITE_OK ){
         1225  +    int iTst;
         1226  +    int iPromote = -1;
         1227  +    int szPromote;                /* Promote anything this size or smaller */
         1228  +    Fts5StructureSegment *pSeg;   /* Segment just written */
         1229  +    Fts5StructureLevel *pTst;
         1230  +    int szSeg;                    /* Size of segment just written */
         1231  +
         1232  +
         1233  +    pSeg = &pStruct->aLevel[iLvl].aSeg[pStruct->aLevel[iLvl].nSeg-1];
         1234  +    szSeg = (1 + pSeg->pgnoLast - pSeg->pgnoFirst);
         1235  +
         1236  +    /* Check for condition (a) */
         1237  +    for(iTst=iLvl-1; iTst>=0 && pStruct->aLevel[iTst].nSeg==0; iTst--);
         1238  +    pTst = &pStruct->aLevel[iTst];
         1239  +    if( iTst>=0 && pTst->nMerge==0 ){
         1240  +      int i;
         1241  +      int szMax = 0;
         1242  +      for(i=0; i<pTst->nSeg; i++){
         1243  +        int sz = pTst->aSeg[i].pgnoLast - pTst->aSeg[i].pgnoFirst + 1;
         1244  +        if( sz>szMax ) szMax = sz;
         1245  +      }
         1246  +      if( szMax>=szSeg ){
         1247  +        /* Condition (a) is true. Promote the newest segment on level 
         1248  +        ** iLvl to level iTst.  */
         1249  +        iPromote = iTst;
         1250  +        szPromote = szMax;
         1251  +      }
         1252  +    }
         1253  +
         1254  +    /* Check for condition (b) */
         1255  +    if( iPromote<0 ){
         1256  +      Fts5StructureLevel *pTst;
         1257  +      for(iTst=iLvl+1; iTst<pStruct->nLevel; iTst++){
         1258  +        pTst = &pStruct->aLevel[iTst];
         1259  +        if( pTst->nSeg ) break;
         1260  +      }
         1261  +      if( iTst<pStruct->nLevel && pTst->nMerge==0 ){
         1262  +        Fts5StructureSegment *pSeg2 = &pTst->aSeg[pTst->nSeg-1];
         1263  +        int sz = pSeg2->pgnoLast - pSeg2->pgnoFirst + 1;
         1264  +        if( sz<=szSeg ){
         1265  +          iPromote = iLvl;
         1266  +          szPromote = szSeg;
         1267  +        }
         1268  +      }
         1269  +    }
         1270  +
         1271  +    /* If iPromote is greater than or equal to zero at this point, then it
         1272  +    ** is the level number of a level to which segments that consist of
         1273  +    ** szPromote or fewer pages should be promoted. */ 
         1274  +    if( iPromote>=0 ){
         1275  +      fts5PrintStructure("BEFORE", pStruct);
         1276  +      fts5StructurePromoteTo(p, iPromote, szPromote, pStruct);
         1277  +      fts5PrintStructure("AFTER", pStruct);
         1278  +    }
         1279  +  }
         1280  +}
  1082   1281   
  1083   1282   
  1084   1283   /*
  1085   1284   ** If the pIter->iOff offset currently points to an entry indicating one
  1086   1285   ** or more term-less nodes, advance past it and set pIter->nEmpty to
  1087   1286   ** the number of empty child nodes.
  1088   1287   */
................................................................................
  3147   3346       for(iLvl=0; nBest==0 && iLvl<pStruct->nLevel; iLvl++){
  3148   3347         assert( pStruct->aLevel[iLvl].nSeg==0 );
  3149   3348       }
  3150   3349   #endif
  3151   3350   
  3152   3351       if( nBest<p->nMinMerge && pStruct->aLevel[iBestLvl].nMerge==0 ) break;
  3153   3352       fts5IndexMergeLevel(p, iIdx, pStruct, iBestLvl, &nRem);
         3353  +    fts5StructurePromote(p, iBestLvl+1, pStruct);
  3154   3354       assert( nRem==0 || p->rc==SQLITE_OK );
  3155   3355     }
  3156   3356   }
  3157   3357   
  3158   3358   /*
  3159   3359   ** Flush the contents of in-memory hash table iHash to a new level-0 
  3160   3360   ** segment on disk. Also update the corresponding structure record.
................................................................................
  3685   3885   */
  3686   3886   static void fts5DecodeStructure(
  3687   3887     int *pRc,                       /* IN/OUT: error code */
  3688   3888     Fts5Buffer *pBuf,
  3689   3889     const u8 *pBlob, int nBlob
  3690   3890   ){
  3691   3891     int rc;                         /* Return code */
  3692         -  int iLvl, iSeg;                 /* Iterate through levels, segments */
  3693   3892     Fts5Structure *p = 0;           /* Decoded structure object */
  3694   3893   
  3695   3894     rc = fts5StructureDecode(pBlob, nBlob, &p);
  3696   3895     if( rc!=SQLITE_OK ){
  3697   3896       *pRc = rc;
  3698   3897       return;
  3699   3898     }
  3700   3899   
  3701         -  for(iLvl=0; iLvl<p->nLevel; iLvl++){
  3702         -    Fts5StructureLevel *pLvl = &p->aLevel[iLvl];
  3703         -    sqlite3Fts5BufferAppendPrintf(pRc, pBuf, 
  3704         -        " {lvl=%d nMerge=%d", iLvl, pLvl->nMerge
  3705         -    );
  3706         -    for(iSeg=0; iSeg<pLvl->nSeg; iSeg++){
  3707         -      Fts5StructureSegment *pSeg = &pLvl->aSeg[iSeg];
  3708         -      sqlite3Fts5BufferAppendPrintf(pRc, pBuf, 
  3709         -          " {id=%d h=%d leaves=%d..%d}", pSeg->iSegid, pSeg->nHeight, 
  3710         -          pSeg->pgnoFirst, pSeg->pgnoLast
  3711         -      );
  3712         -    }
  3713         -    sqlite3Fts5BufferAppendPrintf(pRc, pBuf, "}");
  3714         -  }
  3715         -
         3900  +  fts5DebugStructure(pRc, pBuf, p);
  3716   3901     fts5StructureRelease(p);
  3717   3902   }
  3718   3903   
  3719   3904   /*
  3720   3905   ** Buffer (a/n) is assumed to contain a list of serialized varints. Read
  3721   3906   ** each varint and append its string representation to buffer pBuf. Return
  3722   3907   ** after either the input buffer is exhausted or a 0 value is read.

Changes to test/fts5aj.test.

    53     53     if {$iTest > 1000} { execsql { DELETE FROM t1 WHERE rowid=($iTest-1000) } }
    54     54     set new [doc]
    55     55     execsql { INSERT INTO t1 VALUES($new) }
    56     56     if {$iTest==10000} { set sz1 [db one {SELECT count(*) FROM t1_data}] }
    57     57     if {0==($iTest % 1000)} {
    58     58       set sz [db one {SELECT count(*) FROM t1_data}]
    59     59       set s [structure]
    60         -    do_test 1.$iTest.$sz.{$s} {} {}
           60  +    do_execsql_test 1.$iTest.$sz.{$s} {
           61  +      INSERT INTO t1(t1) VALUES('integrity-check') 
           62  +    }
    61     63     }
    62     64   }
    63     65   
    64         -#db eval { SELECT rowid, fts5_decode(rowid, block) aS r FROM t1_data} {puts $r}
    65         -
    66     66   do_execsql_test 2.0 { INSERT INTO t1(t1) VALUES('integrity-check') }
    67         -
    68     67   
    69     68   
    70     69   finish_test
    71     70