/ Check-in [37a7d303]
Login
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

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

Overview
Comment:Have the fts5 integrity-check verify that doclist indexes match the contents of the leaf pages that they index.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | fts5
Files: files | file ages | folders
SHA1: 37a7d3035eb4bbad7e32fe550321ac9fae611a57
User & Date: dan 2014-08-01 19:27:07
Context
2014-08-01
20:13
Add a special case to the integrity-check code to check that the final integer in a doclist index is as expected. check-in: c9893415 user: dan tags: fts5
19:27
Have the fts5 integrity-check verify that doclist indexes match the contents of the leaf pages that they index. check-in: 37a7d303 user: dan tags: fts5
11:16
Add "doclist index" records to the database. These are to make navigating within very large doclists faster. They are not yet used by queries. check-in: 89377421 user: dan tags: fts5
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to ext/fts5/fts5_index.c.

   251    251   #ifdef SQLITE_DEBUG
   252    252   static int fts5Corrupt() { return SQLITE_CORRUPT_VTAB; }
   253    253   # define FTS5_CORRUPT fts5Corrupt()
   254    254   #else
   255    255   # define FTS5_CORRUPT SQLITE_CORRUPT_VTAB
   256    256   #endif
   257    257   
          258  +#ifdef SQLITE_DEBUG
          259  +static int fts5MissingData() { return 0; }
          260  +#else
          261  +# define fts5MissingData() 
          262  +#endif
          263  +
   258    264   
   259    265   typedef struct Fts5BtreeIter Fts5BtreeIter;
   260    266   typedef struct Fts5BtreeIterLevel Fts5BtreeIterLevel;
   261    267   typedef struct Fts5ChunkIter Fts5ChunkIter;
   262    268   typedef struct Fts5Data Fts5Data;
   263    269   typedef struct Fts5MultiSegIter Fts5MultiSegIter;
   264    270   typedef struct Fts5NodeIter Fts5NodeIter;
................................................................................
   526    532     int nData;
   527    533     int iOff;
   528    534   
   529    535     /* Output variables */
   530    536     Fts5Buffer term;
   531    537     int nEmpty;
   532    538     int iChild;
          539  +  int bDlidx;
   533    540   };
   534    541   
   535    542   /*
   536    543   ** An Fts5BtreeIter object is used to iterate through all entries in the
   537    544   ** b-tree hierarchy belonging to a single fts5 segment. In this case the
   538    545   ** "b-tree hierarchy" is all b-tree nodes except leaves. Each entry in the
   539    546   ** b-tree hierarchy consists of the following:
................................................................................
   562    569     Fts5BtreeIterLevel *aLvl;       /* Level for each tier of b-tree */
   563    570   
   564    571     /* Output variables */
   565    572     Fts5Buffer term;                /* Current term */
   566    573     int iLeaf;                      /* Leaf containing terms >= current term */
   567    574     int nEmpty;                     /* Number of "empty" leaves following iLeaf */
   568    575     int bEof;                       /* Set to true at EOF */
          576  +  int bDlidx;                     /* True if there exists a dlidx */
   569    577   };
   570    578   
   571    579   static void fts5PutU16(u8 *aOut, u16 iVal){
   572    580     aOut[0] = (iVal>>8);
   573    581     aOut[1] = (iVal&0xFF);
   574    582   }
   575    583   
................................................................................
   665    673         Fts5Config *pConfig = p->pConfig;
   666    674         rc = sqlite3_blob_open(pConfig->db, 
   667    675             pConfig->zDb, p->zDataTbl, "block", iRowid, 0, &p->pReader
   668    676         );
   669    677       }else{
   670    678         rc = sqlite3_blob_reopen(p->pReader, iRowid);
   671    679       }
          680  +
          681  +    if( rc ) fts5MissingData();
   672    682   
   673    683       if( rc==SQLITE_OK ){
   674    684         int nByte = sqlite3_blob_bytes(p->pReader);
   675    685         if( pBuf ){
   676    686           fts5BufferZero(pBuf);
   677    687           fts5BufferGrow(&rc, pBuf, nByte);
   678    688           rc = sqlite3_blob_read(p->pReader, pBuf->p, nByte, 0);
................................................................................
   976    986   /*
   977    987   ** If the pIter->iOff offset currently points to an entry indicating one
   978    988   ** or more term-less nodes, advance past it and set pIter->nEmpty to
   979    989   ** the number of empty child nodes.
   980    990   */
   981    991   static void fts5NodeIterGobbleNEmpty(Fts5NodeIter *pIter){
   982    992     if( pIter->iOff<pIter->nData && 0==(pIter->aData[pIter->iOff] & 0xfe) ){
          993  +    pIter->bDlidx = pIter->aData[pIter->iOff] & 0x01;
   983    994       pIter->iOff++;
   984    995       pIter->iOff += getVarint32(&pIter->aData[pIter->iOff], pIter->nEmpty);
   985    996     }else{
   986    997       pIter->nEmpty = 0;
          998  +    pIter->bDlidx = 0;
   987    999     }
   988   1000   }
   989   1001   
   990   1002   /*
   991   1003   ** Advance to the next entry within the node.
   992   1004   */
   993   1005   static void fts5NodeIterNext(int *pRc, Fts5NodeIter *pIter){
................................................................................
  2078   2090   
  2079   2091   /*
  2080   2092   ** If an "nEmpty" record must be written to the b-tree before the next
  2081   2093   ** term, write it now.
  2082   2094   */
  2083   2095   static void fts5WriteBtreeNEmpty(Fts5Index *p, Fts5SegWriter *pWriter){
  2084   2096     if( pWriter->nEmpty ){
  2085         -    Fts5PageWriter *pPg = &pWriter->aWriter[1];
  2086   2097       int bFlag = 0;
         2098  +    Fts5PageWriter *pPg;
         2099  +    pPg = &pWriter->aWriter[1];
  2087   2100       if( pWriter->nEmpty>=FTS5_MIN_DLIDX_SIZE ){
  2088   2101         i64 iKey = FTS5_DOCLIST_IDX_ROWID(
  2089   2102             pWriter->iIdx, pWriter->iSegid, 
  2090   2103             pWriter->aWriter[0].pgno - 1 - pWriter->nEmpty
  2091   2104         );
         2105  +      assert( pWriter->dlidx.n>0 );
  2092   2106         fts5DataWrite(p, iKey, pWriter->dlidx.p, pWriter->dlidx.n);
  2093   2107         bFlag = 1;
  2094   2108       }
  2095   2109       fts5BufferAppendVarint(&p->rc, &pPg->buf, bFlag);
  2096   2110       fts5BufferAppendVarint(&p->rc, &pPg->buf, pWriter->nEmpty);
  2097   2111       pWriter->nEmpty = 0;
  2098   2112     }
................................................................................
  2099   2113   
  2100   2114     /* Whether or not it was written to disk, zero the doclist index at this
  2101   2115     ** point */
  2102   2116     sqlite3Fts5BufferZero(&pWriter->dlidx);
  2103   2117     pWriter->bDlidxPrevValid = 0;
  2104   2118   }
  2105   2119   
         2120  +static void fts5WriteBtreeGrow(Fts5Index *p, Fts5SegWriter *pWriter){
         2121  +  Fts5PageWriter *aNew;
         2122  +  Fts5PageWriter *pNew;
         2123  +  int nNew = sizeof(Fts5PageWriter) * (pWriter->nWriter+1);
         2124  +
         2125  +  aNew = (Fts5PageWriter*)sqlite3_realloc(pWriter->aWriter, nNew);
         2126  +  if( aNew==0 ) return;
         2127  +
         2128  +  pNew = &aNew[pWriter->nWriter];
         2129  +  memset(pNew, 0, sizeof(Fts5PageWriter));
         2130  +  pNew->pgno = 1;
         2131  +  fts5BufferAppendVarint(&p->rc, &pNew->buf, 1);
         2132  +
         2133  +  pWriter->nWriter++;
         2134  +  pWriter->aWriter = aNew;
         2135  +}
  2106   2136   
  2107   2137   /*
  2108   2138   ** This is called once for each leaf page except the first that contains
  2109   2139   ** at least one term. Argument (nTerm/pTerm) is the split-key - a term that
  2110   2140   ** is larger than all terms written to earlier leaves, and equal to or
  2111   2141   ** smaller than the first term on the new leaf.
  2112   2142   **
................................................................................
  2119   2149     int nTerm, const u8 *pTerm      /* First term on new page */
  2120   2150   ){
  2121   2151     int iHeight;
  2122   2152     for(iHeight=1; 1; iHeight++){
  2123   2153       Fts5PageWriter *pPage;
  2124   2154   
  2125   2155       if( iHeight>=pWriter->nWriter ){
  2126         -      Fts5PageWriter *aNew;
  2127         -      Fts5PageWriter *pNew;
  2128         -      int nNew = sizeof(Fts5PageWriter) * (pWriter->nWriter+1);
  2129         -      aNew = (Fts5PageWriter*)sqlite3_realloc(pWriter->aWriter, nNew);
  2130         -      if( aNew==0 ) return;
  2131         -
  2132         -      pNew = &aNew[pWriter->nWriter];
  2133         -      memset(pNew, 0, sizeof(Fts5PageWriter));
  2134         -      pNew->pgno = 1;
  2135         -      fts5BufferAppendVarint(&p->rc, &pNew->buf, 1);
  2136         -
  2137         -      pWriter->nWriter++;
  2138         -      pWriter->aWriter = aNew;
         2156  +      fts5WriteBtreeGrow(p, pWriter);
         2157  +      if( p->rc ) return;
  2139   2158       }
  2140   2159       pPage = &pWriter->aWriter[iHeight];
  2141   2160   
  2142   2161       fts5WriteBtreeNEmpty(p, pWriter);
  2143   2162   
  2144   2163       if( pPage->buf.n>=p->pgsz ){
  2145   2164         /* pPage will be written to disk. The term will be written into the
................................................................................
  2198   2217   static void fts5WriteFlushLeaf(Fts5Index *p, Fts5SegWriter *pWriter){
  2199   2218     static const u8 zero[] = { 0x00, 0x00, 0x00, 0x00 };
  2200   2219     Fts5PageWriter *pPage = &pWriter->aWriter[0];
  2201   2220     i64 iRowid;
  2202   2221   
  2203   2222     if( pPage->term.n==0 ){
  2204   2223       /* No term was written to this page. */
         2224  +    assert( 0==fts5GetU16(&pPage->buf.p[2]) );
  2205   2225       fts5WriteBtreeNoTerm(p, pWriter);
  2206   2226     }
  2207   2227   
  2208   2228     /* Write the current page to the db. */
  2209   2229     iRowid = FTS5_SEGMENT_ROWID(pWriter->iIdx, pWriter->iSegid, 0, pPage->pgno);
  2210   2230     fts5DataWrite(p, iRowid, pPage->buf.p, pPage->buf.n);
  2211   2231   
................................................................................
  2375   2395     Fts5Index *p, 
  2376   2396     Fts5SegWriter *pWriter,         /* Writer object */
  2377   2397     int *pnHeight,                  /* OUT: Height of the b-tree */
  2378   2398     int *pnLeaf                     /* OUT: Number of leaf pages in b-tree */
  2379   2399   ){
  2380   2400     int i;
  2381   2401     *pnLeaf = pWriter->aWriter[0].pgno;
  2382         -  *pnHeight = pWriter->nWriter;
  2383   2402     fts5WriteFlushLeaf(p, pWriter);
         2403  +  if( pWriter->nWriter==1 && pWriter->nEmpty>=FTS5_MIN_DLIDX_SIZE ){
         2404  +    fts5WriteBtreeGrow(p, pWriter);
         2405  +  }
  2384   2406     if( pWriter->nWriter>1 ){
  2385   2407       fts5WriteBtreeNEmpty(p, pWriter);
  2386   2408     }
         2409  +  *pnHeight = pWriter->nWriter;
         2410  +
  2387   2411     for(i=1; i<pWriter->nWriter; i++){
  2388   2412       Fts5PageWriter *pPg = &pWriter->aWriter[i];
  2389   2413       i64 iRow = FTS5_SEGMENT_ROWID(pWriter->iIdx, pWriter->iSegid, i, pPg->pgno);
  2390   2414       fts5DataWrite(p, iRow, pPg->buf.p, pPg->buf.n);
  2391   2415     }
  2392   2416     for(i=0; i<pWriter->nWriter; i++){
  2393   2417       Fts5PageWriter *pPg = &pWriter->aWriter[i];
................................................................................
  2901   2925   
  2902   2926     if( pIter->nLvl==0 || p->rc ){
  2903   2927       pIter->bEof = 1;
  2904   2928       pIter->iLeaf = pSeg->pgnoLast;
  2905   2929     }else{
  2906   2930       pIter->nEmpty = pIter->aLvl[0].s.nEmpty;
  2907   2931       pIter->iLeaf = pIter->aLvl[0].s.iChild;
         2932  +    pIter->bDlidx = pIter->aLvl[0].s.bDlidx;
  2908   2933     }
  2909   2934   }
  2910   2935   
  2911   2936   static void fts5BtreeIterNext(Fts5BtreeIter *pIter){
  2912   2937     Fts5Index *p = pIter->p;
  2913   2938     int i;
  2914   2939   
................................................................................
  2936   2961         if( pLvl->pData ){
  2937   2962           fts5NodeIterInit(pLvl->pData->p, pLvl->pData->n, &pLvl->s);
  2938   2963         }
  2939   2964       }
  2940   2965     }
  2941   2966   
  2942   2967     pIter->nEmpty = pIter->aLvl[0].s.nEmpty;
         2968  +  pIter->bDlidx = pIter->aLvl[0].s.bDlidx;
  2943   2969     pIter->iLeaf = pIter->aLvl[0].s.iChild;
  2944   2970     assert( p->rc==SQLITE_OK || pIter->bEof );
  2945   2971   }
  2946   2972   
  2947   2973   static void fts5BtreeIterFree(Fts5BtreeIter *pIter){
  2948   2974     int i;
  2949   2975     for(i=0; i<pIter->nLvl; i++){
................................................................................
  2953   2979         fts5DataRelease(pLvl->pData);
  2954   2980         pLvl->pData = 0;
  2955   2981       }
  2956   2982     }
  2957   2983     sqlite3_free(pIter->aLvl);
  2958   2984     fts5BufferFree(&pIter->term);
  2959   2985   }
         2986  +
         2987  +typedef struct DoclistIdxIter DoclistIdxIter;
         2988  +struct DoclistIdxIter {
         2989  +  Fts5Data *pDlidx;             /* Data for doclist index, if any */
         2990  +  int iOff;                     /* Current offset into pDlidx */
         2991  +  int bRowidValid;              /* iRowid is valid */
         2992  +
         2993  +  int bZero;                    /* True if current leaf has no rowid */
         2994  +  i64 iRowid;                   /* If bZero==0, first rowid on leaf */
         2995  +};
         2996  +
         2997  +/*
         2998  +** Return non-zero if EOF is reached.
         2999  +*/
         3000  +static int fts5IndexDoclistIterNext(DoclistIdxIter *pIter){
         3001  +  i64 iVal;
         3002  +  if( pIter->iOff>=pIter->pDlidx->n ) return 1;
         3003  +  pIter->iOff += getVarint(&pIter->pDlidx->p[pIter->iOff], (u64*)&iVal);
         3004  +  if( iVal==0 ){
         3005  +    pIter->bZero = 1;
         3006  +  }else{
         3007  +    pIter->bZero = 0;
         3008  +    if( pIter->bRowidValid ){
         3009  +      pIter->iRowid -= iVal;
         3010  +    }else{
         3011  +      pIter->bRowidValid = 1;
         3012  +      pIter->iRowid = iVal;
         3013  +    }
         3014  +  }
         3015  +  return 0;
         3016  +}
  2960   3017   
  2961   3018   static void fts5IndexIntegrityCheckSegment(
  2962   3019     Fts5Index *p,                   /* FTS5 backend object */
  2963   3020     int iIdx,                       /* Index that pSeg is a part of */
  2964   3021     Fts5StructureSegment *pSeg      /* Segment to check internal consistency */
  2965   3022   ){
  2966   3023     Fts5BtreeIter iter;             /* Used to iterate through b-tree hierarchy */
................................................................................
  2970   3027         iter.bEof==0;
  2971   3028         fts5BtreeIterNext(&iter)
  2972   3029     ){
  2973   3030       i64 iRow;                     /* Rowid for this leaf */
  2974   3031       Fts5Data *pLeaf;              /* Data for this leaf */
  2975   3032       int iOff;                     /* Offset of first term on leaf */
  2976   3033       int i;                        /* Used to iterate through empty leaves */
         3034  +    DoclistIdxIter dliter;        /* For iterating through any doclist index */
  2977   3035   
  2978   3036       /* If the leaf in question has already been trimmed from the segment, 
  2979   3037       ** ignore this b-tree entry. Otherwise, load it into memory. */
  2980   3038       if( iter.iLeaf<pSeg->pgnoFirst ) continue;
  2981   3039       iRow = FTS5_SEGMENT_ROWID(iIdx, pSeg->iSegid, 0, iter.iLeaf);
  2982   3040       pLeaf = fts5DataRead(p, iRow);
  2983   3041       if( pLeaf==0 ) break;
................................................................................
  2995   3053         if( res==0 ) res = nTerm - iter.term.n;
  2996   3054         if( res<0 ){
  2997   3055           p->rc = FTS5_CORRUPT;
  2998   3056         }
  2999   3057       }
  3000   3058       fts5DataRelease(pLeaf);
  3001   3059       if( p->rc ) break;
         3060  +
         3061  +    memset(&dliter, 0, sizeof(DoclistIdxIter));
         3062  +    if( iter.bDlidx ){
         3063  +      i64 iDlidxRowid = FTS5_DOCLIST_IDX_ROWID(iIdx, pSeg->iSegid, iter.iLeaf);
         3064  +      dliter.pDlidx = fts5DataRead(p, iDlidxRowid);
         3065  +    }
  3002   3066   
  3003   3067       /* Now check that the iter.nEmpty leaves following the current leaf
  3004   3068       ** (a) exist and (b) contain no terms. */
  3005   3069       for(i=1; i<=iter.nEmpty; i++){
  3006   3070         pLeaf = fts5DataRead(p, iRow+i);
  3007   3071         if( pLeaf && 0!=fts5GetU16(&pLeaf->p[2]) ){
  3008   3072           p->rc = FTS5_CORRUPT;
         3073  +      }
         3074  +      if( pLeaf && dliter.pDlidx ){
         3075  +        if( fts5IndexDoclistIterNext(&dliter) ){
         3076  +          p->rc = FTS5_CORRUPT;
         3077  +        }else{
         3078  +          int iRowidOff = fts5GetU16(&pLeaf->p[0]);
         3079  +          if( dliter.bZero ){
         3080  +            if( iRowidOff!=0 ) p->rc = FTS5_CORRUPT;
         3081  +          }else{
         3082  +            i64 iRowid;
         3083  +            getVarint(&pLeaf->p[iRowidOff], (u64*)&iRowid);
         3084  +            if( iRowid!=dliter.iRowid ) p->rc = FTS5_CORRUPT;
         3085  +          }
         3086  +        }
  3009   3087         }
  3010   3088         fts5DataRelease(pLeaf);
  3011   3089       }
         3090  +    fts5DataRelease(dliter.pDlidx);
  3012   3091     }
  3013   3092   
  3014   3093     if( p->rc==SQLITE_OK && iter.iLeaf!=pSeg->pgnoLast ){
  3015   3094       p->rc = FTS5_CORRUPT;
  3016   3095     }
  3017   3096   
  3018   3097     fts5BtreeIterFree(&iter);
................................................................................
  3214   3293     a = sqlite3_value_blob(apVal[1]);
  3215   3294     fts5DecodeRowid(iRowid, &iIdx, &iSegid, &iHeight, &iPgno);
  3216   3295   
  3217   3296     if( iHeight==FTS5_SEGMENT_MAX_HEIGHT ){
  3218   3297       int i = 0;
  3219   3298       i64 iPrev;
  3220   3299       sqlite3Fts5BufferAppendPrintf(&rc, &s, "(dlidx idx=%d segid=%d pgno=%d)",
  3221         -        iIdx, iSegid, iHeight, iPgno
         3300  +        iIdx, iSegid, iPgno
  3222   3301       );
  3223   3302       if( n>0 ){
  3224   3303         i = getVarint(&a[i], (u64*)&iPrev);
  3225   3304         sqlite3Fts5BufferAppendPrintf(&rc, &s, " %lld", iPrev);
  3226   3305       }
  3227   3306       while( i<n ){
  3228   3307         i64 iVal;
................................................................................
  3301   3380             sqlite3Fts5BufferAppendPrintf(&rc, &s, " left=%d", ss.iChild);
  3302   3381           }else{
  3303   3382             sqlite3Fts5BufferAppendPrintf(&rc,&s, " \"%.*s\"", 
  3304   3383                 ss.term.n, ss.term.p
  3305   3384             );
  3306   3385           }
  3307   3386           if( ss.nEmpty ){
  3308         -          sqlite3Fts5BufferAppendPrintf(&rc, &s, " empty=%d", ss.nEmpty);
         3387  +          sqlite3Fts5BufferAppendPrintf(&rc, &s, " empty=%d%s", ss.nEmpty,
         3388  +              ss.bDlidx ? "*" : ""
         3389  +          );
  3309   3390           }
  3310   3391         }
  3311   3392         fts5NodeIterFree(&ss);
  3312   3393       }
  3313   3394     }
  3314   3395     
  3315   3396     if( rc==SQLITE_OK ){

Changes to test/fts5ah.test.

    45     45     SELECT rowid FROM t1 WHERE t1 MATCH 'y AND x'
    46     46   } [lsort -integer -decr $Y]
    47     47   
    48     48   do_execsql_test 1.3 {
    49     49     INSERT INTO t1(t1) VALUES('integrity-check');
    50     50   }
    51     51   
    52         -do_execsql_test 1.4 {
    53         -  SELECT count(*) FROM t1_data
    54         -}
    55     52   
    56     53   
    57     54   finish_test
    58     55   

Changes to test/permutations.test.

   222    222     fts4growth.test fts4growth2.test
   223    223   }
   224    224   
   225    225   test_suite "fts5" -prefix "" -description {
   226    226     All FTS5 tests.
   227    227   } -files {
   228    228     fts5aa.test fts5ab.test fts5ac.test fts5ad.test fts5ae.test fts5ea.test
   229         -  fts5af.test fts5ag.test
          229  +  fts5af.test fts5ag.test fts5ah.test
   230    230   }
   231    231   
   232    232   test_suite "nofaultsim" -prefix "" -description {
   233    233     "Very" quick test suite. Runs in less than 5 minutes on a workstation. 
   234    234     This test suite is the same as the "quick" tests, except that some files
   235    235     that test malloc and IO errors are omitted.
   236    236   } -files [