Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Use multiple memory allocations for a single Fts5Structure object. This is probably less efficient but much easier to get right. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | fts5 |
Files: | files | file ages | folders |
SHA1: |
2821825f7a481755a333dcdcad780b3e |
User & Date: | dan 2014-08-09 18:02:27.223 |
Context
2014-08-09
| ||
18:22 | Fix an uninitialized variable causing a problem during fts5 table initialization. (check-in: a14fa876f0 user: dan tags: fts5) | |
18:02 | Use multiple memory allocations for a single Fts5Structure object. This is probably less efficient but much easier to get right. (check-in: 2821825f7a 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: ba359d78e1 user: dan tags: fts5) | |
Changes
Changes to ext/fts5/fts5_index.c.
︙ | ︙ | |||
62 63 64 65 66 67 68 | ** ** 1. Structure Records: ** ** The set of segments that make up an index - the index structure - are ** recorded in a single record within the %_data table. The record is a list ** of SQLite varints. ** | > > > > > > | | 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 | ** ** 1. Structure Records: ** ** The set of segments that make up an index - the index structure - are ** recorded in a single record within the %_data table. The record is a list ** of SQLite varints. ** ** The record begins with three varints: ** ** + number of levels, ** + total number of segments on all levels, ** + value of write counter. ** ** Then, for each level from 0 to nMax: ** ** + number of input segments in ongoing merge. ** + total number of segments in level. ** + for each segment from oldest to newest: ** + segment id (always > 0) ** + b-tree height (1 -> root is leaf, 2 -> root is parent of leaf etc.) ** + first leaf page number (often 1) |
︙ | ︙ | |||
703 704 705 706 707 708 709 710 711 712 713 714 715 716 | p->rc = SQLITE_NOMEM; }else{ memset(pRet, 0, nByte); } return pRet; } /* ** Compare the contents of the pLeft buffer with the pRight/nRight blob. ** ** Return -ve if pLeft is smaller than pRight, 0 if they are equal or ** +ve if pRight is smaller than pLeft. In other words: ** | > > > > > > > > > > > > | 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 | p->rc = SQLITE_NOMEM; }else{ memset(pRet, 0, nByte); } return pRet; } static void *fts5MallocZero(int *pRc, int nByte){ void *pRet = 0; if( *pRc==SQLITE_OK ){ pRet = sqlite3_malloc(nByte); if( pRet==0 && nByte>0 ){ *pRc = SQLITE_NOMEM; }else{ memset(pRet, 0, nByte); } } return pRet; } /* ** Compare the contents of the pLeft buffer with the pRight/nRight blob. ** ** Return -ve if pLeft is smaller than pRight, 0 if they are equal or ** +ve if pRight is smaller than pLeft. In other words: ** |
︙ | ︙ | |||
969 970 971 972 973 974 975 | Fts5Structure **ppOut /* OUT: Deserialized object */ ){ int rc = SQLITE_OK; int i = 0; int iLvl; int nLevel = 0; int nSegment = 0; | | | | < | | < | < < > | < | | > > > | | | | | | | < < < > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 | Fts5Structure **ppOut /* OUT: Deserialized object */ ){ int rc = SQLITE_OK; int i = 0; int iLvl; int nLevel = 0; int nSegment = 0; int nByte; /* Bytes of space to allocate at pRet */ Fts5Structure *pRet = 0; /* Structure object to return */ /* Read the total number of levels and segments from the start of the ** structure record. */ i = getVarint32(&pData[i], nLevel); i += getVarint32(&pData[i], nSegment); nByte = ( sizeof(Fts5Structure) + /* Main structure */ sizeof(Fts5StructureLevel) * (nLevel) /* aLevel[] array */ ); pRet = (Fts5Structure*)fts5MallocZero(&rc, nByte); if( pRet ){ pRet->nLevel = nLevel; i += sqlite3GetVarint(&pData[i], &pRet->nWriteCounter); for(iLvl=0; rc==SQLITE_OK && iLvl<nLevel; iLvl++){ Fts5StructureLevel *pLvl = &pRet->aLevel[iLvl]; int nTotal; int iSeg; i += getVarint32(&pData[i], pLvl->nMerge); i += getVarint32(&pData[i], nTotal); assert( nTotal>=pLvl->nMerge ); pLvl->aSeg = (Fts5StructureSegment*)fts5MallocZero(&rc, nTotal * sizeof(Fts5StructureSegment) ); if( rc==SQLITE_OK ){ pLvl->nSeg = nTotal; for(iSeg=0; iSeg<nTotal; iSeg++){ i += getVarint32(&pData[i], pLvl->aSeg[iSeg].iSegid); i += getVarint32(&pData[i], pLvl->aSeg[iSeg].nHeight); i += getVarint32(&pData[i], pLvl->aSeg[iSeg].pgnoFirst); i += getVarint32(&pData[i], pLvl->aSeg[iSeg].pgnoLast); } } } } *ppOut = pRet; return rc; } /* ** */ static void fts5StructureAddLevel(int *pRc, Fts5Structure **ppStruct){ if( *pRc==SQLITE_OK ){ Fts5Structure *pStruct = *ppStruct; int nLevel = pStruct->nLevel; int nByte = ( sizeof(Fts5Structure) + /* Main structure */ sizeof(Fts5StructureLevel) * (nLevel+1) /* aLevel[] array */ ); pStruct = sqlite3_realloc(pStruct, nByte); if( pStruct ){ memset(&pStruct->aLevel[nLevel], 0, sizeof(Fts5StructureLevel)); pStruct->nLevel++; *ppStruct = pStruct; }else{ *pRc = SQLITE_NOMEM; } } } /* ** Extend level iLvl so that there is room for at least nExtra more ** segments. */ static void fts5StructureExtendLevel( int *pRc, Fts5Structure *pStruct, int iLvl, int nExtra, int bInsert ){ if( *pRc==SQLITE_OK ){ Fts5StructureLevel *pLvl = &pStruct->aLevel[iLvl]; Fts5StructureSegment *aNew; int nByte; nByte = (pLvl->nSeg + nExtra) * sizeof(Fts5StructureSegment); aNew = sqlite3_realloc(pLvl->aSeg, nByte); if( aNew ){ if( bInsert==0 ){ memset(&aNew[pLvl->nSeg], 0, sizeof(Fts5StructureSegment) * nExtra); }else{ int nMove = pLvl->nSeg * sizeof(Fts5StructureSegment); memmove(&aNew[nExtra], aNew, nMove); memset(aNew, 0, sizeof(Fts5StructureSegment) * nExtra); } pLvl->aSeg = aNew; }else{ *pRc = SQLITE_NOMEM; } } } /* ** Read, deserialize and return the structure record for index iIdx. ** ** The Fts5Structure.aLevel[] and each Fts5StructureLevel.aSeg[] array ** are over-allocated as described for function fts5StructureDecode() ** above. |
︙ | ︙ | |||
1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 | } /* ** Release a reference to an Fts5Structure object returned by an earlier ** call to fts5StructureRead() or fts5StructureDecode(). */ static void fts5StructureRelease(Fts5Structure *pStruct){ sqlite3_free(pStruct); } /* ** Return the total number of segments in index structure pStruct. */ static int fts5StructureCountSegments(Fts5Structure *pStruct){ | > > > > | 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 | } /* ** Release a reference to an Fts5Structure object returned by an earlier ** call to fts5StructureRead() or fts5StructureDecode(). */ static void fts5StructureRelease(Fts5Structure *pStruct){ int i; for(i=0; i<pStruct->nLevel; i++){ sqlite3_free(pStruct->aLevel[i].aSeg); } sqlite3_free(pStruct); } /* ** Return the total number of segments in index structure pStruct. */ static int fts5StructureCountSegments(Fts5Structure *pStruct){ |
︙ | ︙ | |||
1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 | fprintf(stdout, "%s: %s\n", zCaption, buf.p); fflush(stdout); fts5BufferFree(&buf); } #else # define fts5PrintStructure(x,y) #endif /* ** Return a copy of index structure pStruct. Except, promote as many segments ** as possible to level iPromote. If an OOM occurs, NULL is returned. */ static void fts5StructurePromoteTo( Fts5Index *p, int iPromote, int szPromote, Fts5Structure *pStruct ){ | > > > > < < < < < < < < < < < < < < < < < < < < < < < | < > < | | < | | < | | | < < < < < | | < < < < < < < | | | < < < < < < < < < < < < < < < < | 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 | fprintf(stdout, "%s: %s\n", zCaption, buf.p); fflush(stdout); fts5BufferFree(&buf); } #else # define fts5PrintStructure(x,y) #endif static int fts5SegmentSize(Fts5StructureSegment *pSeg){ return 1 + pSeg->pgnoLast - pSeg->pgnoFirst; } /* ** Return a copy of index structure pStruct. Except, promote as many segments ** as possible to level iPromote. If an OOM occurs, NULL is returned. */ static void fts5StructurePromoteTo( Fts5Index *p, int iPromote, int szPromote, Fts5Structure *pStruct ){ int il, is; Fts5StructureLevel *pOut = &pStruct->aLevel[iPromote]; for(il=iPromote+1; il<pStruct->nLevel; il++){ Fts5StructureLevel *pLvl = &pStruct->aLevel[il]; for(is=pLvl->nSeg-1; is>=0; is--){ int sz = fts5SegmentSize(&pLvl->aSeg[is]); if( sz>szPromote ) return; fts5StructureExtendLevel(&p->rc, pStruct, iPromote, 1, 1); if( p->rc ) return; memcpy(pOut->aSeg, &pLvl->aSeg[is], sizeof(Fts5StructureSegment)); pOut->nSeg++; pLvl->nSeg--; } } } /* ** A new segment has just been written to level iLvl of index structure ** pStruct. This function determines if any segments should be promoted ** as a result. Segments are promoted in two scenarios: ** |
︙ | ︙ | |||
3302 3303 3304 3305 3306 3307 3308 | ** ** If an error occurs, set the Fts5Index.rc error code. If an error has ** already occurred, this function is a no-op. */ static void fts5IndexWork( Fts5Index *p, /* FTS5 backend object */ int iIdx, /* Index to work on */ | | > | 3327 3328 3329 3330 3331 3332 3333 3334 3335 3336 3337 3338 3339 3340 3341 3342 3343 3344 | ** ** If an error occurs, set the Fts5Index.rc error code. If an error has ** already occurred, this function is a no-op. */ static void fts5IndexWork( Fts5Index *p, /* FTS5 backend object */ int iIdx, /* Index to work on */ Fts5Structure **ppStruct, /* IN/OUT: Current structure of index */ int nLeaf /* Number of output leaves just written */ ){ Fts5Structure *pStruct = *ppStruct; i64 nWrite; /* Initial value of write-counter */ int nWork; /* Number of work-quanta to perform */ int nRem; /* Number of leaf pages left to write */ /* Update the write-counter. While doing so, set nWork. */ nWrite = pStruct->nWriteCounter; nWork = ((nWrite + nLeaf) / p->nWorkUnit) - (nWrite / p->nWorkUnit); |
︙ | ︙ | |||
3345 3346 3347 3348 3349 3350 3351 3352 3353 3354 3355 3356 3357 3358 3359 3360 3361 | #ifdef SQLITE_DEBUG for(iLvl=0; nBest==0 && iLvl<pStruct->nLevel; iLvl++){ assert( pStruct->aLevel[iLvl].nSeg==0 ); } #endif if( nBest<p->nMinMerge && pStruct->aLevel[iBestLvl].nMerge==0 ) break; fts5IndexMergeLevel(p, iIdx, pStruct, iBestLvl, &nRem); fts5StructurePromote(p, iBestLvl+1, pStruct); assert( nRem==0 || p->rc==SQLITE_OK ); } } /* ** Flush the contents of in-memory hash table iHash to a new level-0 ** segment on disk. Also update the corresponding structure record. ** | > > > > > | 3371 3372 3373 3374 3375 3376 3377 3378 3379 3380 3381 3382 3383 3384 3385 3386 3387 3388 3389 3390 3391 3392 | #ifdef SQLITE_DEBUG for(iLvl=0; nBest==0 && iLvl<pStruct->nLevel; iLvl++){ assert( pStruct->aLevel[iLvl].nSeg==0 ); } #endif if( nBest<p->nMinMerge && pStruct->aLevel[iBestLvl].nMerge==0 ) break; if( iBestLvl==pStruct->nLevel-1 ){ fts5StructureAddLevel(&p->rc, &pStruct); } fts5StructureExtendLevel(&p->rc, pStruct, iBestLvl+1, 1, 0); fts5IndexMergeLevel(p, iIdx, pStruct, iBestLvl, &nRem); fts5StructurePromote(p, iBestLvl+1, pStruct); assert( nRem==0 || p->rc==SQLITE_OK ); *ppStruct = pStruct; } } /* ** Flush the contents of in-memory hash table iHash to a new level-0 ** segment on disk. Also update the corresponding structure record. ** |
︙ | ︙ | |||
3389 3390 3391 3392 3393 3394 3395 | pNext = pIter->pNext; fts5WritePendingDoclist(p, &writer, pIter); fts5FreePendingDoclist(pIter); } fts5WriteFinish(p, &writer, &nHeight, &pgnoLast); /* Edit the Fts5Structure and write it back to the database. */ | | > > > > | | | | | | | > | | 3420 3421 3422 3423 3424 3425 3426 3427 3428 3429 3430 3431 3432 3433 3434 3435 3436 3437 3438 3439 3440 3441 3442 3443 3444 3445 3446 3447 | pNext = pIter->pNext; fts5WritePendingDoclist(p, &writer, pIter); fts5FreePendingDoclist(pIter); } fts5WriteFinish(p, &writer, &nHeight, &pgnoLast); /* Edit the Fts5Structure and write it back to the database. */ if( pStruct->nLevel==0 ){ fts5StructureAddLevel(&p->rc, &pStruct); } fts5StructureExtendLevel(&p->rc, pStruct, 0, 1, 0); if( p->rc==SQLITE_OK ){ pSeg = &pStruct->aLevel[0].aSeg[ pStruct->aLevel[0].nSeg++ ]; pSeg->iSegid = iSegid; pSeg->nHeight = nHeight; pSeg->pgnoFirst = 1; pSeg->pgnoLast = pgnoLast; } } fts5IndexWork(p, iHash, &pStruct, pgnoLast); fts5StructureWrite(p, iHash, pStruct); fts5StructureRelease(pStruct); } /* ** Flush any data stored in the in-memory hash tables to the database. */ |
︙ | ︙ |