/ Check-in [28149a78]
Login

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

Overview
Comment:Changes to improve performance and support LIMIT clauses on fts3 tables. This branch is unstable for now.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | fts3-prefix-search
Files: files | file ages | folders
SHA1:28149a7882a1e9dfe4a75ec5b91d176ebe6284e9
User & Date: dan 2011-06-02 19:57:24
Context
2011-06-03
18:00
FTS changes: Remove unreachable code. Fix bugs. When processing a large doclist incrementally, read from disk incrementally too. check-in: a4c7e282 user: dan tags: fts3-prefix-search
2011-06-02
19:57
Changes to improve performance and support LIMIT clauses on fts3 tables. This branch is unstable for now. check-in: 28149a78 user: dan tags: fts3-prefix-search
2011-05-28
15:57
Minor changes made while planning a larger change. check-in: 84097a4c user: dan tags: fts3-prefix-search
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to ext/fts3/fts3.c.

   309    309   
   310    310   #include "fts3.h"
   311    311   #ifndef SQLITE_CORE 
   312    312   # include "sqlite3ext.h"
   313    313     SQLITE_EXTENSION_INIT1
   314    314   #endif
   315    315   
          316  +static char *fts3EvalPhrasePoslist(Fts3Phrase *, int *);
          317  +static sqlite3_int64 fts3EvalPhraseDocid(Fts3Phrase *);
          318  +
   316    319   /* 
   317    320   ** Write a 64-bit variable-length integer to memory starting at p[0].
   318    321   ** The length of data written will be between 1 and FTS3_VARINT_MAX bytes.
   319    322   ** The number of bytes written is returned.
   320    323   */
   321    324   int sqlite3Fts3PutVarint(char *p, sqlite_int64 v){
   322    325     unsigned char *q = (unsigned char *) p;
................................................................................
  1203   1206     } 
  1204   1207   
  1205   1208     /* Regardless of the strategy selected, FTS can deliver rows in rowid (or
  1206   1209     ** docid) order. Both ascending and descending are possible. 
  1207   1210     */
  1208   1211     if( pInfo->nOrderBy==1 ){
  1209   1212       struct sqlite3_index_orderby *pOrder = &pInfo->aOrderBy[0];
  1210         -    if( pOrder->iColumn<0 || pOrder->iColumn==p->nColumn+1 ){
         1213  +    if( pOrder->desc==0 
         1214  +     && (pOrder->iColumn<0 || pOrder->iColumn==p->nColumn+1) 
         1215  +    ){
  1211   1216         if( pOrder->desc ){
  1212   1217           pInfo->idxStr = "DESC";
  1213   1218         }else{
  1214   1219           pInfo->idxStr = "ASC";
  1215   1220         }
         1221  +      pInfo->orderByConsumed = 1;
  1216   1222       }
  1217         -    pInfo->orderByConsumed = 1;
  1218   1223     }
  1219   1224   
  1220   1225     return SQLITE_OK;
  1221   1226   }
  1222   1227   
  1223   1228   /*
  1224   1229   ** Implementation of xOpen method.
................................................................................
  1252   1257     sqlite3Fts3FreeDeferredTokens(pCsr);
  1253   1258     sqlite3_free(pCsr->aDoclist);
  1254   1259     sqlite3_free(pCsr->aMatchinfo);
  1255   1260     sqlite3_free(pCsr);
  1256   1261     return SQLITE_OK;
  1257   1262   }
  1258   1263   
         1264  +static int fts3RowidMethod(sqlite3_vtab_cursor *, sqlite3_int64*);
         1265  +
  1259   1266   /*
  1260   1267   ** Position the pCsr->pStmt statement so that it is on the row
  1261   1268   ** of the %_content table that contains the last match.  Return
  1262   1269   ** SQLITE_OK on success.  
  1263   1270   */
  1264   1271   static int fts3CursorSeek(sqlite3_context *pContext, Fts3Cursor *pCsr){
  1265   1272     if( pCsr->isRequireSeek ){
  1266         -    pCsr->isRequireSeek = 0;
  1267   1273       sqlite3_bind_int64(pCsr->pStmt, 1, pCsr->iPrevId);
         1274  +    pCsr->isRequireSeek = 0;
  1268   1275       if( SQLITE_ROW==sqlite3_step(pCsr->pStmt) ){
  1269   1276         return SQLITE_OK;
  1270   1277       }else{
  1271   1278         int rc = sqlite3_reset(pCsr->pStmt);
  1272   1279         if( rc==SQLITE_OK ){
  1273   1280           /* If no row was found and no error has occured, then the %_content
  1274   1281           ** table is missing a row that is present in the full-text index.
................................................................................
  2216   2223     return SQLITE_OK;
  2217   2224   }
  2218   2225   
  2219   2226   /*
  2220   2227   ** Append SegReader object pNew to the end of the pCsr->apSegment[] array.
  2221   2228   */
  2222   2229   static int fts3SegReaderCursorAppend(
  2223         -  Fts3SegReaderCursor *pCsr, 
         2230  +  Fts3MultiSegReader *pCsr, 
  2224   2231     Fts3SegReader *pNew
  2225   2232   ){
  2226   2233     if( (pCsr->nSegment%16)==0 ){
  2227   2234       Fts3SegReader **apNew;
  2228   2235       int nByte = (pCsr->nSegment + 16)*sizeof(Fts3SegReader*);
  2229   2236       apNew = (Fts3SegReader **)sqlite3_realloc(pCsr->apSegment, nByte);
  2230   2237       if( !apNew ){
................................................................................
  2241   2248     Fts3Table *p,                   /* FTS3 table handle */
  2242   2249     int iIndex,                     /* Index to search (from 0 to p->nIndex-1) */
  2243   2250     int iLevel,                     /* Level of segments to scan */
  2244   2251     const char *zTerm,              /* Term to query for */
  2245   2252     int nTerm,                      /* Size of zTerm in bytes */
  2246   2253     int isPrefix,                   /* True for a prefix search */
  2247   2254     int isScan,                     /* True to scan from zTerm to EOF */
  2248         -  Fts3SegReaderCursor *pCsr       /* Cursor object to populate */
         2255  +  Fts3MultiSegReader *pCsr       /* Cursor object to populate */
  2249   2256   ){
  2250   2257     int rc = SQLITE_OK;
  2251   2258     int rc2;
  2252   2259     sqlite3_stmt *pStmt = 0;
  2253   2260   
  2254   2261     /* If iLevel is less than 0 and this is not a scan, include a seg-reader 
  2255   2262     ** for the pending-terms. If this is a scan, then this call must be being
................................................................................
  2312   2319     Fts3Table *p,                   /* FTS3 table handle */
  2313   2320     int iIndex,                     /* Index to search (from 0 to p->nIndex-1) */
  2314   2321     int iLevel,                     /* Level of segments to scan */
  2315   2322     const char *zTerm,              /* Term to query for */
  2316   2323     int nTerm,                      /* Size of zTerm in bytes */
  2317   2324     int isPrefix,                   /* True for a prefix search */
  2318   2325     int isScan,                     /* True to scan from zTerm to EOF */
  2319         -  Fts3SegReaderCursor *pCsr       /* Cursor object to populate */
         2326  +  Fts3MultiSegReader *pCsr       /* Cursor object to populate */
  2320   2327   ){
  2321   2328     assert( iIndex>=0 && iIndex<p->nIndex );
  2322   2329     assert( iLevel==FTS3_SEGCURSOR_ALL
  2323   2330         ||  iLevel==FTS3_SEGCURSOR_PENDING 
  2324   2331         ||  iLevel>=0
  2325   2332     );
  2326   2333     assert( iLevel<FTS3_SEGDIR_MAXLEVEL );
................................................................................
  2327   2334     assert( FTS3_SEGCURSOR_ALL<0 && FTS3_SEGCURSOR_PENDING<0 );
  2328   2335     assert( isPrefix==0 || isScan==0 );
  2329   2336   
  2330   2337     /* "isScan" is only set to true by the ft4aux module, an ordinary
  2331   2338     ** full-text tables. */
  2332   2339     assert( isScan==0 || p->aIndex==0 );
  2333   2340   
  2334         -  memset(pCsr, 0, sizeof(Fts3SegReaderCursor));
         2341  +  memset(pCsr, 0, sizeof(Fts3MultiSegReader));
  2335   2342   
  2336   2343     return fts3SegReaderCursor(
  2337   2344         p, iIndex, iLevel, zTerm, nTerm, isPrefix, isScan, pCsr
  2338   2345     );
  2339   2346   }
  2340   2347   
  2341   2348   static int fts3SegReaderCursorAddZero(
  2342   2349     Fts3Table *p,
  2343   2350     const char *zTerm,
  2344   2351     int nTerm,
  2345         -  Fts3SegReaderCursor *pCsr
         2352  +  Fts3MultiSegReader *pCsr
  2346   2353   ){
  2347   2354     return fts3SegReaderCursor(p, 0, FTS3_SEGCURSOR_ALL, zTerm, nTerm, 0, 0,pCsr);
  2348   2355   }
  2349   2356   
  2350   2357   
  2351         -static int fts3TermSegReaderCursor(
         2358  +int sqlite3Fts3TermSegReaderCursor(
  2352   2359     Fts3Cursor *pCsr,               /* Virtual table cursor handle */
  2353   2360     const char *zTerm,              /* Term to query for */
  2354   2361     int nTerm,                      /* Size of zTerm in bytes */
  2355   2362     int isPrefix,                   /* True for a prefix search */
  2356         -  Fts3SegReaderCursor **ppSegcsr  /* OUT: Allocated seg-reader cursor */
         2363  +  Fts3MultiSegReader **ppSegcsr   /* OUT: Allocated seg-reader cursor */
  2357   2364   ){
  2358         -  Fts3SegReaderCursor *pSegcsr;   /* Object to allocate and return */
         2365  +  Fts3MultiSegReader *pSegcsr;   /* Object to allocate and return */
  2359   2366     int rc = SQLITE_NOMEM;          /* Return code */
  2360   2367   
  2361         -  pSegcsr = sqlite3_malloc(sizeof(Fts3SegReaderCursor));
         2368  +  pSegcsr = sqlite3_malloc(sizeof(Fts3MultiSegReader));
  2362   2369     if( pSegcsr ){
  2363   2370       int i;
  2364   2371       int nCost = 0;
  2365   2372       int bFound = 0;               /* True once an index has been found */
  2366   2373       Fts3Table *p = (Fts3Table *)pCsr->base.pVtab;
  2367   2374   
  2368   2375       if( isPrefix ){
  2369   2376         for(i=1; bFound==0 && i<p->nIndex; i++){
  2370   2377           if( p->aIndex[i].nPrefix==nTerm ){
  2371   2378             bFound = 1;
  2372   2379             rc = sqlite3Fts3SegReaderCursor(
  2373   2380                 p, i, FTS3_SEGCURSOR_ALL, zTerm, nTerm, 0, 0, pSegcsr);
         2381  +          pSegcsr->bLookup = 1;
  2374   2382           }
  2375   2383         }
  2376   2384   
  2377   2385         for(i=1; bFound==0 && i<p->nIndex; i++){
  2378   2386           if( p->aIndex[i].nPrefix==nTerm+1 ){
  2379   2387             bFound = 1;
  2380   2388             rc = sqlite3Fts3SegReaderCursor(
................................................................................
  2387   2395         }
  2388   2396       }
  2389   2397   
  2390   2398       if( bFound==0 ){
  2391   2399         rc = sqlite3Fts3SegReaderCursor(
  2392   2400             p, 0, FTS3_SEGCURSOR_ALL, zTerm, nTerm, isPrefix, 0, pSegcsr
  2393   2401         );
         2402  +      pSegcsr->bLookup = !isPrefix;
  2394   2403       }
  2395   2404       for(i=0; rc==SQLITE_OK && i<pSegcsr->nSegment; i++){
  2396   2405         rc = sqlite3Fts3SegReaderCost(pCsr, pSegcsr->apSegment[i], &nCost);
  2397   2406       }
  2398   2407       pSegcsr->nCost = nCost;
  2399   2408     }
  2400   2409   
  2401   2410     *ppSegcsr = pSegcsr;
  2402   2411     return rc;
  2403   2412   }
  2404   2413   
  2405         -static void fts3SegReaderCursorFree(Fts3SegReaderCursor *pSegcsr){
         2414  +static void fts3SegReaderCursorFree(Fts3MultiSegReader *pSegcsr){
  2406   2415     sqlite3Fts3SegReaderFinish(pSegcsr);
  2407   2416     sqlite3_free(pSegcsr);
  2408   2417   }
  2409   2418   
  2410   2419   /*
  2411   2420   ** This function retreives the doclist for the specified term (or term
  2412   2421   ** prefix) from the database. 
................................................................................
  2423   2432     Fts3PhraseToken *pTok,          /* Token to query for */
  2424   2433     int iColumn,                    /* Column to query (or -ve for all columns) */
  2425   2434     int isReqPos,                   /* True to include position lists in output */
  2426   2435     int *pnOut,                     /* OUT: Size of buffer at *ppOut */
  2427   2436     char **ppOut                    /* OUT: Malloced result buffer */
  2428   2437   ){
  2429   2438     int rc;                         /* Return code */
  2430         -  Fts3SegReaderCursor *pSegcsr;   /* Seg-reader cursor for this term */
         2439  +  Fts3MultiSegReader *pSegcsr;   /* Seg-reader cursor for this term */
  2431   2440     TermSelect tsc;                 /* Context object for fts3TermSelectCb() */
  2432   2441     Fts3SegFilter filter;           /* Segment term filter configuration */
  2433   2442   
  2434   2443     pSegcsr = pTok->pSegcsr;
  2435   2444     memset(&tsc, 0, sizeof(TermSelect));
  2436   2445     tsc.isReqPos = isReqPos;
  2437   2446   
................................................................................
  2550   2559         pOut += sqlite3Fts3PutVarint(pOut, delta);
  2551   2560       }
  2552   2561   
  2553   2562       *pnList = (int)(pOut - aList);
  2554   2563     }
  2555   2564   }
  2556   2565   
  2557         -/* 
         2566  +/*
  2558   2567   ** Return a DocList corresponding to the phrase *pPhrase.
  2559   2568   **
  2560   2569   ** If this function returns SQLITE_OK, but *pnOut is set to a negative value,
  2561   2570   ** then no tokens in the phrase were looked up in the full-text index. This
  2562   2571   ** is only possible when this function is called from within xFilter(). The
  2563   2572   ** caller should assume that all documents match the phrase. The actual
  2564   2573   ** filtering will take place in xNext().
................................................................................
  2578   2587     int isTermPos = (pPhrase->nToken>1 || isReqPos);
  2579   2588     Fts3Table *p = (Fts3Table *)pCsr->base.pVtab;
  2580   2589     int isFirst = 1;
  2581   2590   
  2582   2591     int iPrevTok = 0;
  2583   2592     int nDoc = 0;
  2584   2593   
  2585         -  /* If this is an xFilter() evaluation, create a segment-reader for each
  2586         -  ** phrase token. Or, if this is an xNext() or snippet/offsets/matchinfo
  2587         -  ** evaluation, only create segment-readers if there are no Fts3DeferredToken
  2588         -  ** objects attached to the phrase-tokens.
  2589         -  */
  2590         -  for(ii=0; ii<pPhrase->nToken; ii++){
  2591         -    Fts3PhraseToken *pTok = &pPhrase->aToken[ii];
  2592         -    if( pTok->pSegcsr==0 ){
  2593         -      if( (pCsr->eEvalmode==FTS3_EVAL_FILTER)
  2594         -       || (pCsr->eEvalmode==FTS3_EVAL_NEXT && pCsr->pDeferred==0) 
  2595         -       || (pCsr->eEvalmode==FTS3_EVAL_MATCHINFO && pTok->bFulltext) 
  2596         -      ){
  2597         -        rc = fts3TermSegReaderCursor(
  2598         -            pCsr, pTok->z, pTok->n, pTok->isPrefix, &pTok->pSegcsr
  2599         -        );
  2600         -        if( rc!=SQLITE_OK ) return rc;
  2601         -      }
  2602         -    }
  2603         -  }
  2604         -
  2605   2594     for(ii=0; ii<pPhrase->nToken; ii++){
  2606   2595       Fts3PhraseToken *pTok;        /* Token to find doclist for */
  2607   2596       int iTok = 0;                 /* The token being queried this iteration */
  2608   2597       char *pList = 0;              /* Pointer to token doclist */
  2609   2598       int nList = 0;                /* Size of buffer at pList */
  2610   2599   
  2611   2600       /* Select a token to process. If this is an xFilter() call, then tokens 
................................................................................
  2622   2611         pTok = &pPhrase->aToken[iTok];
  2623   2612       }else{
  2624   2613         int nMinCost = 0x7FFFFFFF;
  2625   2614         int jj;
  2626   2615   
  2627   2616         /* Find the remaining token with the lowest cost. */
  2628   2617         for(jj=0; jj<pPhrase->nToken; jj++){
  2629         -        Fts3SegReaderCursor *pSegcsr = pPhrase->aToken[jj].pSegcsr;
         2618  +        Fts3MultiSegReader *pSegcsr = pPhrase->aToken[jj].pSegcsr;
  2630   2619           if( pSegcsr && pSegcsr->nCost<nMinCost ){
  2631   2620             iTok = jj;
  2632   2621             nMinCost = pSegcsr->nCost;
  2633   2622           }
  2634   2623         }
  2635   2624         pTok = &pPhrase->aToken[iTok];
  2636   2625   
................................................................................
  2824   2813     assert( pCsr->eEvalmode==FTS3_EVAL_FILTER );
  2825   2814     if( pnExpr && pExpr->eType!=FTSQUERY_AND ){
  2826   2815       (*pnExpr)++;
  2827   2816       pnExpr = 0;
  2828   2817     }
  2829   2818   
  2830   2819     if( pExpr->eType==FTSQUERY_PHRASE ){
         2820  +    int ii;                       /* Used to iterate through phrase tokens */
  2831   2821       Fts3Phrase *pPhrase = pExpr->pPhrase;
  2832         -    int ii;
  2833   2822   
  2834   2823       for(ii=0; rc==SQLITE_OK && ii<pPhrase->nToken; ii++){
  2835   2824         Fts3PhraseToken *pTok = &pPhrase->aToken[ii];
  2836   2825         if( pTok->pSegcsr==0 ){
  2837         -        rc = fts3TermSegReaderCursor(
         2826  +        rc = sqlite3Fts3TermSegReaderCursor(
  2838   2827               pCsr, pTok->z, pTok->n, pTok->isPrefix, &pTok->pSegcsr
  2839   2828           );
  2840   2829         }
  2841   2830       }
  2842   2831     }else{ 
  2843   2832       rc = fts3ExprAllocateSegReaders(pCsr, pExpr->pLeft, pnExpr);
  2844   2833       if( rc==SQLITE_OK ){
................................................................................
  2876   2865   static int fts3ExprCost(Fts3Expr *pExpr){
  2877   2866     int nCost;                      /* Return value */
  2878   2867     if( pExpr->eType==FTSQUERY_PHRASE ){
  2879   2868       Fts3Phrase *pPhrase = pExpr->pPhrase;
  2880   2869       int ii;
  2881   2870       nCost = 0;
  2882   2871       for(ii=0; ii<pPhrase->nToken; ii++){
  2883         -      Fts3SegReaderCursor *pSegcsr = pPhrase->aToken[ii].pSegcsr;
         2872  +      Fts3MultiSegReader *pSegcsr = pPhrase->aToken[ii].pSegcsr;
  2884   2873         if( pSegcsr ) nCost += pSegcsr->nCost;
  2885   2874       }
  2886   2875     }else{
  2887   2876       nCost = fts3ExprCost(pExpr->pLeft) + fts3ExprCost(pExpr->pRight);
  2888   2877     }
  2889   2878     return nCost;
  2890   2879   }
................................................................................
  3171   3160   ** subsequently to determine whether or not an EOF was hit.
  3172   3161   */
  3173   3162   static int fts3NextMethod(sqlite3_vtab_cursor *pCursor){
  3174   3163     int res;
  3175   3164     int rc = SQLITE_OK;             /* Return code */
  3176   3165     Fts3Cursor *pCsr = (Fts3Cursor *)pCursor;
  3177   3166   
  3178         -  pCsr->eEvalmode = FTS3_EVAL_NEXT;
  3179         -  do {
  3180         -    if( pCsr->aDoclist==0 ){
  3181         -      if( SQLITE_ROW!=sqlite3_step(pCsr->pStmt) ){
  3182         -        pCsr->isEof = 1;
  3183         -        rc = sqlite3_reset(pCsr->pStmt);
  3184         -        break;
  3185         -      }
  3186         -      pCsr->iPrevId = sqlite3_column_int64(pCsr->pStmt, 0);
  3187         -    }else{
  3188         -      if( pCsr->desc==0 ){
  3189         -        if( pCsr->pNextId>=&pCsr->aDoclist[pCsr->nDoclist] ){
         3167  +  if( pCsr->bIncremental ){
         3168  +    rc = sqlite3Fts3EvalNext(pCsr, pCsr->pExpr);
         3169  +  }else{
         3170  +    pCsr->eEvalmode = FTS3_EVAL_NEXT;
         3171  +    do {
         3172  +      if( pCsr->aDoclist==0 ){
         3173  +        if( SQLITE_ROW!=sqlite3_step(pCsr->pStmt) ){
  3190   3174             pCsr->isEof = 1;
         3175  +          rc = sqlite3_reset(pCsr->pStmt);
  3191   3176             break;
  3192   3177           }
  3193         -        fts3GetDeltaVarint(&pCsr->pNextId, &pCsr->iPrevId);
         3178  +        pCsr->iPrevId = sqlite3_column_int64(pCsr->pStmt, 0);
  3194   3179         }else{
  3195         -        fts3GetReverseDeltaVarint(&pCsr->pNextId,pCsr->aDoclist,&pCsr->iPrevId);
  3196         -        if( pCsr->pNextId<=pCsr->aDoclist ){
  3197         -          pCsr->isEof = 1;
  3198         -          break;
         3180  +        if( pCsr->desc==0 ){
         3181  +          if( pCsr->pNextId>=&pCsr->aDoclist[pCsr->nDoclist] ){
         3182  +            pCsr->isEof = 1;
         3183  +            break;
         3184  +          }
         3185  +          fts3GetDeltaVarint(&pCsr->pNextId, &pCsr->iPrevId);
         3186  +        }else{
         3187  +          fts3GetReverseDeltaVarint(&pCsr->pNextId,pCsr->aDoclist,&pCsr->iPrevId);
         3188  +          if( pCsr->pNextId<=pCsr->aDoclist ){
         3189  +            pCsr->isEof = 1;
         3190  +            break;
         3191  +          }
  3199   3192           }
         3193  +        sqlite3_reset(pCsr->pStmt);
         3194  +        pCsr->isRequireSeek = 1;
         3195  +        pCsr->isMatchinfoNeeded = 1;
  3200   3196         }
  3201         -      sqlite3_reset(pCsr->pStmt);
  3202         -      pCsr->isRequireSeek = 1;
  3203         -      pCsr->isMatchinfoNeeded = 1;
  3204         -    }
  3205         -  }while( SQLITE_OK==(rc = fts3EvalDeferred(pCsr, &res)) && res==0 );
         3197  +    }while( SQLITE_OK==(rc = fts3EvalDeferred(pCsr, &res)) && res==0 );
         3198  +  }
  3206   3199   
  3207   3200     return rc;
  3208   3201   }
  3209   3202   
  3210   3203   /*
  3211   3204   ** This is the xFilter interface for the virtual table.  See
  3212   3205   ** the virtual table xFilter method documentation for additional
................................................................................
  3226   3219   static int fts3FilterMethod(
  3227   3220     sqlite3_vtab_cursor *pCursor,   /* The cursor used for this query */
  3228   3221     int idxNum,                     /* Strategy index */
  3229   3222     const char *idxStr,             /* Unused */
  3230   3223     int nVal,                       /* Number of elements in apVal */
  3231   3224     sqlite3_value **apVal           /* Arguments for the indexing scheme */
  3232   3225   ){
  3233         -  const char *azSql[] = {
  3234         -    "SELECT %s FROM %Q.'%q_content' AS x WHERE docid = ?",   /* non-full-scan */
  3235         -    "SELECT %s FROM %Q.'%q_content' AS x ORDER BY docid %s", /* full-scan */
  3236         -  };
  3237         -  int rc;                         /* Return code */
         3226  +  int rc;
  3238   3227     char *zSql;                     /* SQL statement used to access %_content */
  3239   3228     Fts3Table *p = (Fts3Table *)pCursor->pVtab;
  3240   3229     Fts3Cursor *pCsr = (Fts3Cursor *)pCursor;
  3241   3230   
  3242   3231     UNUSED_PARAMETER(idxStr);
  3243   3232     UNUSED_PARAMETER(nVal);
  3244   3233   
................................................................................
  3262   3251       }
  3263   3252   
  3264   3253       rc = sqlite3Fts3ExprParse(p->pTokenizer, p->azColumn, p->nColumn, 
  3265   3254           iCol, zQuery, -1, &pCsr->pExpr
  3266   3255       );
  3267   3256       if( rc!=SQLITE_OK ){
  3268   3257         if( rc==SQLITE_ERROR ){
  3269         -        p->base.zErrMsg = sqlite3_mprintf("malformed MATCH expression: [%s]",
  3270         -                                          zQuery);
         3258  +        static const char *zErr = "malformed MATCH expression: [%s]";
         3259  +        p->base.zErrMsg = sqlite3_mprintf(zErr, zQuery);
  3271   3260         }
  3272   3261         return rc;
  3273   3262       }
  3274   3263   
  3275   3264       rc = sqlite3Fts3ReadLock(p);
  3276   3265       if( rc!=SQLITE_OK ) return rc;
  3277   3266   
  3278         -    rc = fts3EvalExpr(pCsr, pCsr->pExpr, &pCsr->aDoclist, &pCsr->nDoclist, 0);
         3267  +    pCsr->bIncremental = 1;
         3268  +    rc = sqlite3Fts3EvalStart(pCsr, pCsr->pExpr, 1);
         3269  +
  3279   3270       sqlite3Fts3SegmentsClose(p);
  3280   3271       if( rc!=SQLITE_OK ) return rc;
  3281   3272       pCsr->pNextId = pCsr->aDoclist;
  3282   3273       pCsr->iPrevId = 0;
  3283   3274     }
  3284   3275   
  3285   3276     /* Compile a SELECT statement for this cursor. For a full-table-scan, the
  3286   3277     ** statement loops through all rows of the %_content table. For a
  3287   3278     ** full-text query or docid lookup, the statement retrieves a single
  3288   3279     ** row by docid.
  3289   3280     */
  3290         -  zSql = (char *)azSql[idxNum==FTS3_FULLSCAN_SEARCH];
  3291         -  zSql = sqlite3_mprintf(
  3292         -      zSql, p->zReadExprlist, p->zDb, p->zName, (idxStr ? idxStr : "ASC")
  3293         -  );
  3294         -  if( !zSql ){
  3295         -    rc = SQLITE_NOMEM;
         3281  +  if( idxNum==FTS3_FULLSCAN_SEARCH ){
         3282  +    const char *zSort = (idxStr ? idxStr : "ASC");
         3283  +    const char *zTmpl = "SELECT %s FROM %Q.'%q_content' AS x ORDER BY docid %s";
         3284  +    zSql = sqlite3_mprintf(zTmpl, p->zReadExprlist, p->zDb, p->zName, zSort);
  3296   3285     }else{
  3297         -    rc = sqlite3_prepare_v2(p->db, zSql, -1, &pCsr->pStmt, 0);
  3298         -    sqlite3_free(zSql);
         3286  +    const char *zTmpl = "SELECT %s FROM %Q.'%q_content' AS x WHERE docid = ?";
         3287  +    zSql = sqlite3_mprintf(zTmpl, p->zReadExprlist, p->zDb, p->zName);
  3299   3288     }
  3300         -  if( rc==SQLITE_OK && idxNum==FTS3_DOCID_SEARCH ){
         3289  +  if( !zSql ) return SQLITE_NOMEM;
         3290  +  rc = sqlite3_prepare_v2(p->db, zSql, -1, &pCsr->pStmt, 0);
         3291  +  sqlite3_free(zSql);
         3292  +  if( rc!=SQLITE_OK ) return rc;
         3293  +
         3294  +  if( idxNum==FTS3_DOCID_SEARCH ){
  3301   3295       rc = sqlite3_bind_value(pCsr->pStmt, 1, apVal[0]);
         3296  +    if( rc!=SQLITE_OK ) return rc;
  3302   3297     }
  3303         -  pCsr->eSearch = (i16)idxNum;
  3304   3298   
  3305   3299     assert( pCsr->desc==0 );
  3306         -  if( rc!=SQLITE_OK ) return rc;
         3300  +  pCsr->eSearch = (i16)idxNum;
  3307   3301     if( rc==SQLITE_OK && pCsr->nDoclist>0 && idxStr && idxStr[0]=='D' ){
  3308   3302       sqlite3_int64 iDocid = 0;
  3309   3303       char *csr = pCsr->aDoclist;
  3310   3304       while( csr<&pCsr->aDoclist[pCsr->nDoclist] ){
  3311   3305         fts3GetDeltaVarint(&csr, &iDocid);
  3312   3306       }
  3313   3307       pCsr->pNextId = csr;
................................................................................
  3333   3327   ** This is the xRowid method. The SQLite core calls this routine to
  3334   3328   ** retrieve the rowid for the current row of the result set. fts3
  3335   3329   ** exposes %_content.docid as the rowid for the virtual table. The
  3336   3330   ** rowid should be written to *pRowid.
  3337   3331   */
  3338   3332   static int fts3RowidMethod(sqlite3_vtab_cursor *pCursor, sqlite_int64 *pRowid){
  3339   3333     Fts3Cursor *pCsr = (Fts3Cursor *) pCursor;
  3340         -  if( pCsr->aDoclist ){
         3334  +  if( pCsr->bIncremental ){
         3335  +    *pRowid = sqlite3Fts3EvalDocid(pCsr, pCsr->pExpr);
         3336  +  }else if( pCsr->aDoclist ){
  3341   3337       *pRowid = pCsr->iPrevId;
  3342   3338     }else{
  3343   3339       /* This branch runs if the query is implemented using a full-table scan
  3344   3340       ** (not using the full-text index). In this case grab the rowid from the
  3345   3341       ** SELECT statement.
  3346   3342       */
  3347   3343       assert( pCsr->isRequireSeek==0 );
................................................................................
  3456   3452   /*
  3457   3453   ** Load the doclist associated with expression pExpr to pExpr->aDoclist.
  3458   3454   ** The loaded doclist contains positions as well as the document ids.
  3459   3455   ** This is used by the matchinfo(), snippet() and offsets() auxillary
  3460   3456   ** functions.
  3461   3457   */
  3462   3458   int sqlite3Fts3ExprLoadDoclist(Fts3Cursor *pCsr, Fts3Expr *pExpr){
  3463         -  int rc;
  3464         -  Fts3Phrase *pPhrase = pExpr->pPhrase;
  3465         -  assert( pExpr->eType==FTSQUERY_PHRASE && pPhrase );
  3466         -  assert( pCsr->eEvalmode==FTS3_EVAL_NEXT );
  3467         -  rc = fts3EvalExpr(pCsr, pExpr, &pPhrase->aDoclist, &pPhrase->nDoclist, 1);
         3459  +  int rc = SQLITE_OK;
         3460  +  if( pCsr->bIncremental==0 ){
         3461  +    Fts3Phrase *pPhrase = pExpr->pPhrase;
         3462  +    assert( pExpr->eType==FTSQUERY_PHRASE && pPhrase );
         3463  +    assert( pCsr->eEvalmode==FTS3_EVAL_NEXT );
         3464  +    rc = fts3EvalExpr(pCsr, pExpr, &pPhrase->aDoclist, &pPhrase->nDoclist, 1);
         3465  +  }
  3468   3466     return rc;
  3469   3467   }
  3470   3468   
  3471   3469   /*
  3472   3470   ** TODO: This is something to do with matchinfo(). Similar to
  3473   3471   ** sqlite3ExprLoadDoclists() but slightly different.
  3474   3472   **
................................................................................
  3476   3474   */
  3477   3475   int sqlite3Fts3ExprLoadFtDoclist(
  3478   3476     Fts3Cursor *pCsr, 
  3479   3477     Fts3Expr *pExpr,
  3480   3478     char **paDoclist,
  3481   3479     int *pnDoclist
  3482   3480   ){
  3483         -  int rc;
         3481  +  int rc = SQLITE_OK;
         3482  +  assert( pExpr->eType==FTSQUERY_PHRASE && pExpr->pPhrase );
  3484   3483     assert( pCsr->eEvalmode==FTS3_EVAL_NEXT );
  3485         -  assert( pExpr->eType==FTSQUERY_PHRASE && pExpr->pPhrase );
         3484  +  assert( pCsr->bIncremental==0 );
  3486   3485     pCsr->eEvalmode = FTS3_EVAL_MATCHINFO;
  3487   3486     rc = fts3EvalExpr(pCsr, pExpr, paDoclist, pnDoclist, 1);
  3488   3487     pCsr->eEvalmode = FTS3_EVAL_NEXT;
  3489   3488     return rc;
  3490   3489   }
  3491   3490   
  3492   3491   
................................................................................
  3503   3502       c = *p--; 
  3504   3503     }
  3505   3504     if( p>pStart ){ p = &p[2]; }
  3506   3505     while( *p++&0x80 );
  3507   3506     *ppPoslist = p;
  3508   3507   }
  3509   3508   
  3510         -
  3511         -/*
  3512         -** After ExprLoadDoclist() (see above) has been called, this function is
  3513         -** used to iterate/search through the position lists that make up the doclist
  3514         -** stored in pExpr->aDoclist.
  3515         -*/
  3516         -char *sqlite3Fts3FindPositions(
  3517         -  Fts3Cursor *pCursor,            /* Associate FTS3 cursor */
  3518         -  Fts3Expr *pExpr,                /* Access this expressions doclist */
  3519         -  sqlite3_int64 iDocid,           /* Docid associated with requested pos-list */
  3520         -  int iCol                        /* Column of requested pos-list */
  3521         -){
  3522         -  Fts3Phrase *pPhrase = pExpr->pPhrase;
  3523         -  assert( pPhrase->isLoaded );
  3524         -
  3525         -  if( pPhrase->aDoclist ){
  3526         -    char *pEnd = &pPhrase->aDoclist[pPhrase->nDoclist];
  3527         -    char *pCsr;
  3528         -
  3529         -    if( pPhrase->pCurrent==0 ){
  3530         -      if( pCursor->desc==0 ){
  3531         -        pPhrase->pCurrent = pPhrase->aDoclist;
  3532         -        pPhrase->iCurrent = 0;
  3533         -        fts3GetDeltaVarint(&pPhrase->pCurrent, &pPhrase->iCurrent);
  3534         -      }else{
  3535         -        pCsr = pPhrase->aDoclist;
  3536         -        while( pCsr<pEnd ){
  3537         -          fts3GetDeltaVarint(&pCsr, &pPhrase->iCurrent);
  3538         -          fts3PoslistCopy(0, &pCsr);
  3539         -        }
  3540         -        fts3ReversePoslist(pPhrase->aDoclist, &pCsr);
  3541         -        pPhrase->pCurrent = pCsr;
  3542         -      }
  3543         -    }
  3544         -    pCsr = pPhrase->pCurrent;
  3545         -    assert( pCsr );
  3546         -
  3547         -    while( (pCursor->desc==0 && pCsr<pEnd) 
  3548         -        || (pCursor->desc && pCsr>pPhrase->aDoclist) 
  3549         -    ){
  3550         -      if( pCursor->desc==0 && pPhrase->iCurrent<iDocid ){
  3551         -        fts3PoslistCopy(0, &pCsr);
  3552         -        if( pCsr<pEnd ){
  3553         -          fts3GetDeltaVarint(&pCsr, &pPhrase->iCurrent);
  3554         -        }
  3555         -        pPhrase->pCurrent = pCsr;
  3556         -      }else if( pCursor->desc && pPhrase->iCurrent>iDocid ){
  3557         -        fts3GetReverseDeltaVarint(&pCsr, pPhrase->aDoclist, &pPhrase->iCurrent);
  3558         -        fts3ReversePoslist(pPhrase->aDoclist, &pCsr);
  3559         -        pPhrase->pCurrent = pCsr;
  3560         -      }else{
  3561         -        if( pPhrase->iCurrent==iDocid ){
  3562         -          int iThis = 0;
  3563         -          if( iCol<0 ){
  3564         -            /* If iCol is negative, return a pointer to the start of the
  3565         -            ** position-list (instead of a pointer to the start of a list
  3566         -            ** of offsets associated with a specific column).
  3567         -            */
  3568         -            return pCsr;
  3569         -          }
  3570         -          while( iThis<iCol ){
  3571         -            fts3ColumnlistCopy(0, &pCsr);
  3572         -            if( *pCsr==0x00 ) return 0;
  3573         -            pCsr++;
  3574         -            pCsr += sqlite3Fts3GetVarint32(pCsr, &iThis);
  3575         -          }
  3576         -          if( iCol==iThis && (*pCsr&0xFE) ) return pCsr;
  3577         -        }
  3578         -        return 0;
  3579         -      }
  3580         -    }
  3581         -  }
  3582         -
  3583         -  return 0;
  3584         -}
  3585         -
  3586   3509   /*
  3587   3510   ** Helper function used by the implementation of the overloaded snippet(),
  3588   3511   ** offsets() and optimize() SQL functions.
  3589   3512   **
  3590   3513   ** If the value passed as the third argument is a blob of size
  3591   3514   ** sizeof(Fts3Cursor*), then the blob contents are copied to the 
  3592   3515   ** output variable *ppCsr and SQLITE_OK is returned. Otherwise, an error
................................................................................
  3981   3904     char **pzErrMsg,
  3982   3905     const sqlite3_api_routines *pApi
  3983   3906   ){
  3984   3907     SQLITE_EXTENSION_INIT2(pApi)
  3985   3908     return sqlite3Fts3Init(db);
  3986   3909   }
  3987   3910   #endif
         3911  +
         3912  +/*************************************************************************
         3913  +**************************************************************************
         3914  +**************************************************************************
         3915  +**************************************************************************
         3916  +*************************************************************************/
         3917  +
         3918  +
         3919  +/*
         3920  +** Allocate an Fts3MultiSegReader for each token in the expression headed
         3921  +** by pExpr. 
         3922  +**
         3923  +** An Fts3SegReader object is a cursor that can seek or scan a range of
         3924  +** entries within a single segment b-tree. An Fts3MultiSegReader uses multiple
         3925  +** Fts3SegReader objects internally to provide an interface to seek or scan
         3926  +** within the union of all segments of a b-tree. Hence the name.
         3927  +**
         3928  +** If the allocated Fts3MultiSegReader just seeks to a single entry in a
         3929  +** segment b-tree (if the term is not a prefix or it is a prefix for which
         3930  +** there exists prefix b-tree of the right length) then it may be traversed
         3931  +** and merged incrementally. Otherwise, it has to be merged into an in-memory 
         3932  +** doclist and then traversed.
         3933  +*/
         3934  +static void fts3EvalAllocateReaders(
         3935  +  Fts3Cursor *pCsr, 
         3936  +  Fts3Expr *pExpr, 
         3937  +  int *pnToken,                   /* OUT: Total number of tokens in phrase. */
         3938  +  int *pRc
         3939  +){
         3940  +  if( pExpr && SQLITE_OK==*pRc ){
         3941  +    if( pExpr->eType==FTSQUERY_PHRASE ){
         3942  +      int i;
         3943  +      int nToken = pExpr->pPhrase->nToken;
         3944  +      *pnToken += nToken;
         3945  +      for(i=0; i<nToken; i++){
         3946  +        Fts3PhraseToken *pToken = &pExpr->pPhrase->aToken[i];
         3947  +        int rc = sqlite3Fts3TermSegReaderCursor(pCsr, 
         3948  +            pToken->z, pToken->n, pToken->isPrefix, &pToken->pSegcsr
         3949  +        );
         3950  +        if( rc!=SQLITE_OK ){
         3951  +          *pRc = rc;
         3952  +          return;
         3953  +        }
         3954  +      }
         3955  +    }else{
         3956  +      fts3EvalAllocateReaders(pCsr, pExpr->pLeft, pnToken, pRc);
         3957  +      fts3EvalAllocateReaders(pCsr, pExpr->pRight, pnToken, pRc);
         3958  +    }
         3959  +  }
         3960  +}
         3961  +
         3962  +static int fts3EvalPhraseLoad(
         3963  +  Fts3Cursor *pCsr, 
         3964  +  Fts3Phrase *p
         3965  +){
         3966  +  Fts3Table *pTab = (Fts3Table *)pCsr->base.pVtab;
         3967  +  int iToken;
         3968  +  int rc = SQLITE_OK;
         3969  +
         3970  +  char *aDoclist = 0;
         3971  +  int nDoclist = 0;
         3972  +  int iPrev = -1;
         3973  +
         3974  +  for(iToken=0; rc==SQLITE_OK && iToken<p->nToken; iToken++){
         3975  +    Fts3PhraseToken *pToken = &p->aToken[iToken];
         3976  +    assert( pToken->pSegcsr || pToken->pDeferred );
         3977  +
         3978  +    if( pToken->pDeferred==0 ){
         3979  +      int nThis = 0;
         3980  +      char *pThis = 0;
         3981  +      rc = fts3TermSelect(pTab, pToken, p->iColumn, 1, &nThis, &pThis);
         3982  +      if( rc==SQLITE_OK ){
         3983  +        if( pThis==0 ){
         3984  +          sqlite3_free(aDoclist);
         3985  +          aDoclist = 0;
         3986  +          nDoclist = 0;
         3987  +          break;
         3988  +        }else if( aDoclist==0 ){
         3989  +          aDoclist = pThis;
         3990  +          nDoclist = nThis;
         3991  +        }else{
         3992  +          assert( iPrev>=0 );
         3993  +          fts3DoclistMerge(MERGE_POS_PHRASE, iToken-iPrev, 
         3994  +              0, pThis, &nThis, aDoclist, nDoclist, pThis, nThis, 0
         3995  +          );
         3996  +          sqlite3_free(aDoclist);
         3997  +          aDoclist = pThis;
         3998  +          nDoclist = nThis;
         3999  +        }
         4000  +        iPrev = iToken;
         4001  +      }
         4002  +    }
         4003  +  }
         4004  +
         4005  +  if( rc==SQLITE_OK ){
         4006  +    p->doclist.aAll = aDoclist;
         4007  +    p->doclist.nAll = nDoclist;
         4008  +  }else{
         4009  +    sqlite3_free(aDoclist);
         4010  +  }
         4011  +  return rc;
         4012  +}
         4013  +
         4014  +static int fts3EvalDeferredPhrase(Fts3Cursor *pCsr, Fts3Phrase *pPhrase){
         4015  +  Fts3Table *pTab = (Fts3Table *)pCsr->base.pVtab;
         4016  +  int iToken;
         4017  +  int rc = SQLITE_OK;
         4018  +
         4019  +  int nMaxUndeferred = -1;
         4020  +  char *aPoslist = 0;
         4021  +  int nPoslist = 0;
         4022  +  int iPrev = -1;
         4023  +
         4024  +  for(iToken=0; rc==SQLITE_OK && iToken<pPhrase->nToken; iToken++){
         4025  +    Fts3PhraseToken *pToken = &pPhrase->aToken[iToken];
         4026  +    Fts3DeferredToken *pDeferred = pToken->pDeferred;
         4027  +
         4028  +    if( pDeferred ){
         4029  +      char *pList;
         4030  +      int nList;
         4031  +      rc = sqlite3Fts3DeferredTokenList(pDeferred, &pList, &nList);
         4032  +      if( rc!=SQLITE_OK ) return rc;
         4033  +
         4034  +      if( pList==0 ){
         4035  +        sqlite3_free(aPoslist);
         4036  +        pPhrase->doclist.pList = 0;
         4037  +        pPhrase->doclist.nList = 0;
         4038  +        return SQLITE_OK;
         4039  +
         4040  +      }else if( aPoslist==0 ){
         4041  +        aPoslist = pList;
         4042  +        nPoslist = nList;
         4043  +
         4044  +      }else{
         4045  +        assert( iPrev>=0 );
         4046  +
         4047  +        char *aOut = pList;
         4048  +        char *p1 = aPoslist;
         4049  +        char *p2 = aOut;
         4050  +
         4051  +        fts3PoslistPhraseMerge(&aOut, iToken-iPrev, 0, 1, &p1, &p2);
         4052  +        sqlite3_free(aPoslist);
         4053  +        aPoslist = pList;
         4054  +        nPoslist = aOut - aPoslist;
         4055  +        if( nPoslist==0 ){
         4056  +          sqlite3_free(aPoslist);
         4057  +          pPhrase->doclist.pList = 0;
         4058  +          pPhrase->doclist.nList = 0;
         4059  +          return SQLITE_OK;
         4060  +        }
         4061  +      }
         4062  +      iPrev = iToken;
         4063  +    }else{
         4064  +      nMaxUndeferred = iToken;
         4065  +    }
         4066  +  }
         4067  +
         4068  +  if( iPrev>=0 ){
         4069  +    if( nMaxUndeferred<0 ){
         4070  +      pPhrase->doclist.pList = aPoslist;
         4071  +      pPhrase->doclist.nList = nPoslist;
         4072  +      pPhrase->doclist.iDocid = pCsr->iPrevId;
         4073  +    }else{
         4074  +      int nDistance;
         4075  +      char *p1;
         4076  +      char *p2;
         4077  +      char *aOut;
         4078  +
         4079  +      if( nMaxUndeferred>iPrev ){
         4080  +        p1 = aPoslist;
         4081  +        p2 = pPhrase->doclist.pList;
         4082  +        nDistance = nMaxUndeferred - iPrev;
         4083  +      }else{
         4084  +        p1 = pPhrase->doclist.pList;
         4085  +        p2 = aPoslist;
         4086  +        nDistance = iPrev - nMaxUndeferred;
         4087  +      }
         4088  +
         4089  +      aOut = (char *)sqlite3_malloc(nPoslist+8);
         4090  +      if( !aOut ){
         4091  +        sqlite3_free(aPoslist);
         4092  +        return SQLITE_NOMEM;
         4093  +      }
         4094  +      
         4095  +      pPhrase->doclist.pList = aOut;
         4096  +      if( fts3PoslistPhraseMerge(&aOut, nDistance, 0, 1, &p1, &p2) ){
         4097  +        pPhrase->doclist.nList = (aOut - pPhrase->doclist.pList);
         4098  +        sqlite3_free(aPoslist);
         4099  +      }else{
         4100  +        sqlite3_free(aOut);
         4101  +        pPhrase->doclist.pList = 0;
         4102  +        pPhrase->doclist.nList = 0;
         4103  +      }
         4104  +    }
         4105  +  }
         4106  +
         4107  +  return SQLITE_OK;
         4108  +}
         4109  +
         4110  +
         4111  +/*
         4112  +** The following three functions:
         4113  +**
         4114  +**     fts3EvalPhraseStart()
         4115  +**     fts3EvalPhraseNext()
         4116  +**     fts3EvalPhraseReset()
         4117  +**
         4118  +** May be used with a phrase object after fts3EvalAllocateReaders() has been
         4119  +** called to iterate through the set of docids that match the phrase.
         4120  +**
         4121  +** After a successful call to fts3EvalPhraseNext(), the following two 
         4122  +** functions may be called to access the current docid and position-list.
         4123  +**
         4124  +**     fts3EvalPhraseDocid()
         4125  +**     fts3EvalPhrasePoslist()
         4126  +*/
         4127  +static int fts3EvalPhraseStart(Fts3Cursor *pCsr, int bOptOk, Fts3Phrase *p){
         4128  +  int rc;
         4129  +  Fts3Doclist *pList = &p->doclist;
         4130  +  Fts3PhraseToken *pFirst = &p->aToken[0];
         4131  +
         4132  +  assert( pList->aAll==0 );
         4133  +
         4134  +  if( p->nToken==1 && bOptOk==1 
         4135  +   && pFirst->pSegcsr && pFirst->pSegcsr->bLookup 
         4136  +  ){
         4137  +    /* Use the incremental approach. */
         4138  +    Fts3Table *pTab = (Fts3Table *)pCsr->base.pVtab;
         4139  +    int iCol = (p->iColumn >= pTab->nColumn ? -1 : p->iColumn);
         4140  +    rc = sqlite3Fts3MsrIncrStart(
         4141  +        pTab, pFirst->pSegcsr, iCol, pFirst->z, pFirst->n);
         4142  +    p->bIncr = 1;
         4143  +
         4144  +  }else{
         4145  +
         4146  +    /* Load the full doclist for the phrase into memory. */
         4147  +    rc = fts3EvalPhraseLoad(pCsr, p);
         4148  +    p->bIncr = 0;
         4149  +  }
         4150  +
         4151  +  assert( rc!=SQLITE_OK || p->nToken<1 || p->aToken[0].pSegcsr==0 || p->bIncr );
         4152  +  return rc;
         4153  +}
         4154  +
         4155  +/*
         4156  +** Attempt to move the phrase iterator to point to the next matching docid. 
         4157  +** If an error occurs, return an SQLite error code. Otherwise, return 
         4158  +** SQLITE_OK.
         4159  +**
         4160  +** If there is no "next" entry and no error occurs, then *pbEof is set to
         4161  +** 1 before returning. Otherwise, if no error occurs and the iterator is
         4162  +** successfully advanced, *pbEof is set to 0.
         4163  +*/
         4164  +static int fts3EvalPhraseNext(Fts3Cursor *pCsr, Fts3Phrase *p, u8 *pbEof){
         4165  +  int rc = SQLITE_OK;
         4166  +
         4167  +  if( p->bIncr ){
         4168  +    Fts3Table *pTab = (Fts3Table *)pCsr->base.pVtab;
         4169  +    assert( p->nToken==1 );
         4170  +    rc = sqlite3Fts3MsrIncrNext(pTab, p->aToken[0].pSegcsr, 
         4171  +        &p->doclist.iDocid, &p->doclist.pList, &p->doclist.nList
         4172  +    );
         4173  +    if( rc==SQLITE_OK && !p->doclist.pList ){
         4174  +      *pbEof = 1;
         4175  +    }
         4176  +  }else{
         4177  +    char *pIter;
         4178  +    Fts3Doclist *pDL = &p->doclist;
         4179  +
         4180  +    if( pDL->pNextDocid ){
         4181  +      pIter = pDL->pNextDocid;
         4182  +    }else{
         4183  +      pIter = pDL->aAll;
         4184  +    }
         4185  +
         4186  +    if( pIter>=&pDL->aAll[pDL->nAll] ){
         4187  +      /* We have already reached the end of this doclist. EOF. */
         4188  +      *pbEof = 1;
         4189  +    }else{
         4190  +      fts3GetDeltaVarint(&pIter, &pDL->iDocid);
         4191  +      pDL->pList = pIter;
         4192  +      fts3PoslistCopy(0, &pIter);
         4193  +      pDL->nList = (pIter - pDL->pList);
         4194  +      pDL->pNextDocid = pIter;
         4195  +      *pbEof = 0;
         4196  +    }
         4197  +  }
         4198  +
         4199  +  return rc;
         4200  +}
         4201  +
         4202  +static int fts3EvalPhraseReset(Fts3Cursor *pCsr, Fts3Phrase *p){
         4203  +  return SQLITE_OK;
         4204  +}
         4205  +
         4206  +static sqlite3_int64 fts3EvalPhraseDocid(Fts3Phrase *p){
         4207  +  return p->doclist.iDocid;
         4208  +}
         4209  +
         4210  +static char *fts3EvalPhrasePoslist(Fts3Phrase *p, int *pnList){
         4211  +  if( pnList ){
         4212  +    *pnList = p->doclist.nList;
         4213  +  }
         4214  +  return p->doclist.pList;
         4215  +}
         4216  +
         4217  +static void fts3EvalStartReaders(
         4218  +  Fts3Cursor *pCsr, 
         4219  +  Fts3Expr *pExpr, 
         4220  +  int bOptOk,
         4221  +  int *pRc
         4222  +){
         4223  +  if( pExpr && SQLITE_OK==*pRc ){
         4224  +    if( pExpr->eType==FTSQUERY_PHRASE ){
         4225  +      int i;
         4226  +      int nToken = pExpr->pPhrase->nToken;
         4227  +      for(i=0; i<nToken; i++){
         4228  +        if( pExpr->pPhrase->aToken[i].pDeferred==0 ) break;
         4229  +      }
         4230  +      pExpr->bDeferred = (i==nToken);
         4231  +      *pRc = fts3EvalPhraseStart(pCsr, bOptOk, pExpr->pPhrase);
         4232  +    }else{
         4233  +      if( pExpr->eType==FTSQUERY_NEAR ){
         4234  +        bOptOk = 0;
         4235  +      }
         4236  +      fts3EvalStartReaders(pCsr, pExpr->pLeft, bOptOk, pRc);
         4237  +      fts3EvalStartReaders(pCsr, pExpr->pRight, bOptOk, pRc);
         4238  +      pExpr->bDeferred = (pExpr->pLeft->bDeferred && pExpr->pRight->bDeferred);
         4239  +    }
         4240  +  }
         4241  +}
         4242  +
         4243  +static void fts3EvalNearMerge(
         4244  +  Fts3Expr *p1,
         4245  +  Fts3Expr *p2,
         4246  +  int nNear,
         4247  +  int *pRc
         4248  +){
         4249  +  if( *pRc==SQLITE_OK ){
         4250  +    int rc;                         /* Return code */
         4251  +    Fts3Phrase *pLeft = p1->pPhrase;
         4252  +    Fts3Phrase *pRight = p2->pPhrase;
         4253  +  
         4254  +    assert( p2->eType==FTSQUERY_PHRASE && pLeft );
         4255  +    assert( p2->eType==FTSQUERY_PHRASE && pRight );
         4256  +  
         4257  +    if( pLeft->doclist.aAll==0 ){
         4258  +      sqlite3_free(pRight->doclist.aAll);
         4259  +      pRight->doclist.aAll = 0;
         4260  +      pRight->doclist.nAll = 0;
         4261  +    }else if( pRight->doclist.aAll ){
         4262  +      char *aOut;                 /* Buffer in which to assemble new doclist */
         4263  +      int nOut;                   /* Size of buffer aOut in bytes */
         4264  +  
         4265  +      *pRc = fts3NearMerge(MERGE_POS_NEAR, nNear, 
         4266  +          pLeft->nToken, pLeft->doclist.aAll, pLeft->doclist.nAll,
         4267  +          pRight->nToken, pRight->doclist.aAll, pRight->doclist.nAll,
         4268  +          &aOut, &nOut
         4269  +      );
         4270  +      sqlite3_free(pRight->doclist.aAll);
         4271  +      pRight->doclist.aAll = aOut;
         4272  +      pRight->doclist.nAll = nOut;
         4273  +    }
         4274  +  }
         4275  +}
         4276  +
         4277  +static void fts3EvalNearTrim(Fts3Cursor *pCsr, Fts3Expr *pExpr, int *pRc){
         4278  +
         4279  +  if( pExpr && SQLITE_OK==*pRc ){
         4280  +    if( pExpr->eType==FTSQUERY_NEAR ){
         4281  +      Fts3Expr *pLeft = pExpr->pLeft;
         4282  +      int nPhrase = 2;
         4283  +      Fts3Expr **aPhrase;
         4284  +
         4285  +      assert( pLeft );
         4286  +      assert( pExpr->pRight );
         4287  +      assert( pExpr->pRight->eType==FTSQUERY_PHRASE );
         4288  +
         4289  +      while( pLeft->eType!=FTSQUERY_PHRASE ){
         4290  +        assert( pLeft->eType==FTSQUERY_NEAR );
         4291  +        assert( pLeft->pRight->eType==FTSQUERY_PHRASE );
         4292  +        pLeft = pLeft->pLeft;
         4293  +        nPhrase++;
         4294  +      }
         4295  +
         4296  +      aPhrase = (Fts3Expr **)sqlite3_malloc(sizeof(Fts3Expr *) * nPhrase);
         4297  +      if( !aPhrase ){
         4298  +        *pRc = SQLITE_NOMEM;
         4299  +      }else{
         4300  +        int i = 1;
         4301  +        aPhrase[0] = pLeft;
         4302  +        do {
         4303  +          pLeft = pLeft->pParent;
         4304  +          aPhrase[i++] = pLeft->pRight;
         4305  +        }while( pLeft!=pExpr );
         4306  +
         4307  +        for(i=0; i<(nPhrase-1); i++){
         4308  +          int nNear = aPhrase[i+1]->pParent->nNear;
         4309  +          fts3EvalNearMerge(aPhrase[i], aPhrase[i+1], nNear, pRc);
         4310  +        }
         4311  +        for(i=nPhrase-2; i>=0; i--){
         4312  +          int nNear = aPhrase[i+1]->pParent->nNear;
         4313  +          fts3EvalNearMerge(aPhrase[i+1], aPhrase[i], nNear, pRc);
         4314  +        }
         4315  +
         4316  +        sqlite3_free(aPhrase);
         4317  +      }
         4318  +
         4319  +    }else{
         4320  +      fts3EvalNearTrim(pCsr, pExpr->pLeft, pRc);
         4321  +      fts3EvalNearTrim(pCsr, pExpr->pRight, pRc);
         4322  +    }
         4323  +  }
         4324  +}
         4325  +
         4326  +typedef struct Fts3TokenAndCost Fts3TokenAndCost;
         4327  +struct Fts3TokenAndCost {
         4328  +  Fts3PhraseToken *pToken;
         4329  +  int nOvfl;
         4330  +  int iCol;
         4331  +};
         4332  +
         4333  +static void fts3EvalTokenCosts(
         4334  +  Fts3Cursor *pCsr, 
         4335  +  Fts3Expr *pExpr, 
         4336  +  Fts3TokenAndCost **ppTC,
         4337  +  int *pRc
         4338  +){
         4339  +  if( *pRc==SQLITE_OK && pExpr ){
         4340  +    if( pExpr->eType==FTSQUERY_PHRASE ){
         4341  +      Fts3Phrase *pPhrase = pExpr->pPhrase;
         4342  +      int i;
         4343  +      for(i=0; *pRc==SQLITE_OK && i<pPhrase->nToken; i++){
         4344  +        Fts3TokenAndCost *pTC = (*ppTC)++;
         4345  +        pTC->pToken = &pPhrase->aToken[i];
         4346  +        pTC->iCol = pPhrase->iColumn;
         4347  +        *pRc = sqlite3Fts3MsrOvfl(pCsr, pTC->pToken->pSegcsr, &pTC->nOvfl);
         4348  +      }
         4349  +    }else if( pExpr->eType==FTSQUERY_AND ){
         4350  +      fts3EvalTokenCosts(pCsr, pExpr->pLeft, ppTC, pRc);
         4351  +      fts3EvalTokenCosts(pCsr, pExpr->pRight, ppTC, pRc);
         4352  +    }
         4353  +  }
         4354  +}
         4355  +
         4356  +static int fts3EvalAverageDocsize(Fts3Cursor *pCsr, int *pnPage){
         4357  +  if( pCsr->nRowAvg==0 ){
         4358  +    /* The average document size, which is required to calculate the cost
         4359  +     ** of each doclist, has not yet been determined. Read the required 
         4360  +     ** data from the %_stat table to calculate it.
         4361  +     **
         4362  +     ** Entry 0 of the %_stat table is a blob containing (nCol+1) FTS3 
         4363  +     ** varints, where nCol is the number of columns in the FTS3 table.
         4364  +     ** The first varint is the number of documents currently stored in
         4365  +     ** the table. The following nCol varints contain the total amount of
         4366  +     ** data stored in all rows of each column of the table, from left
         4367  +     ** to right.
         4368  +     */
         4369  +    int rc;
         4370  +    Fts3Table *p = (Fts3Table*)pCsr->base.pVtab;
         4371  +    sqlite3_stmt *pStmt;
         4372  +    sqlite3_int64 nDoc = 0;
         4373  +    sqlite3_int64 nByte = 0;
         4374  +    const char *pEnd;
         4375  +    const char *a;
         4376  +
         4377  +    rc = sqlite3Fts3SelectDoctotal(p, &pStmt);
         4378  +    if( rc!=SQLITE_OK ) return rc;
         4379  +    a = sqlite3_column_blob(pStmt, 0);
         4380  +    assert( a );
         4381  +
         4382  +    pEnd = &a[sqlite3_column_bytes(pStmt, 0)];
         4383  +    a += sqlite3Fts3GetVarint(a, &nDoc);
         4384  +    while( a<pEnd ){
         4385  +      a += sqlite3Fts3GetVarint(a, &nByte);
         4386  +    }
         4387  +    if( nDoc==0 || nByte==0 ){
         4388  +      sqlite3_reset(pStmt);
         4389  +      return SQLITE_CORRUPT_VTAB;
         4390  +    }
         4391  +
         4392  +    pCsr->nRowAvg = (int)(((nByte / nDoc) + p->nPgsz) / p->nPgsz);
         4393  +    assert( pCsr->nRowAvg>0 ); 
         4394  +    rc = sqlite3_reset(pStmt);
         4395  +    if( rc!=SQLITE_OK ) return rc;
         4396  +  }
         4397  +
         4398  +  *pnPage = pCsr->nRowAvg;
         4399  +  return SQLITE_OK;
         4400  +}
         4401  +
         4402  +int sqlite3Fts3EvalStart(Fts3Cursor *pCsr, Fts3Expr *pExpr, int bOptOk){
         4403  +  Fts3Table *pTab = (Fts3Table *)pCsr->base.pVtab;
         4404  +  int rc = SQLITE_OK;
         4405  +  int nToken = 0;
         4406  +
         4407  +  /* Allocate a MultiSegReader for each token in the expression. */
         4408  +  fts3EvalAllocateReaders(pCsr, pExpr, &nToken, &rc);
         4409  +
         4410  +  /* Call fts3EvalPhraseStart() on all phrases in the expression. TODO:
         4411  +  ** This call will eventually also be responsible for determining which
         4412  +  ** tokens are 'deferred' until the document text is loaded into memory.
         4413  +  **
         4414  +  ** Each token in each phrase is dealt with using one of the following
         4415  +  ** three strategies:
         4416  +  **
         4417  +  **   1. Entire doclist loaded into memory as part of the
         4418  +  **      fts3EvalStartReaders() call.
         4419  +  **
         4420  +  **   2. Doclist loaded into memory incrementally, as part of each
         4421  +  **      sqlite3Fts3EvalNext() call.
         4422  +  **
         4423  +  **   3. Token doclist is never loaded. Instead, documents are loaded into
         4424  +  **      memory and scanned for the token as part of the sqlite3Fts3EvalNext()
         4425  +  **      call. This is known as a "deferred" token.
         4426  +  */
         4427  +
         4428  +  /* If bOptOk is true, check if there are any tokens that can be 
         4429  +  ** deferred (strategy 3). */
         4430  +  if( rc==SQLITE_OK && bOptOk && nToken>1 && pTab->bHasStat ){
         4431  +    Fts3TokenAndCost *aTC;
         4432  +    aTC = (Fts3TokenAndCost *)sqlite3_malloc(sizeof(Fts3TokenAndCost) * nToken);
         4433  +    if( !aTC ){
         4434  +      rc = SQLITE_NOMEM;
         4435  +    }else{
         4436  +      int ii;
         4437  +      int nDocEst = 0;
         4438  +      int nDocSize;
         4439  +      Fts3TokenAndCost *pTC = aTC;
         4440  +
         4441  +      rc = fts3EvalAverageDocsize(pCsr, &nDocSize);
         4442  +      fts3EvalTokenCosts(pCsr, pExpr, &pTC, &rc);
         4443  +      nToken = pTC-aTC;
         4444  +
         4445  +      for(ii=0; rc==SQLITE_OK && ii<nToken; ii++){
         4446  +        int jj;
         4447  +        pTC = 0;
         4448  +        for(jj=0; jj<nToken; jj++){
         4449  +          if( aTC[jj].pToken && (!pTC || aTC[jj].nOvfl<pTC->nOvfl) ){
         4450  +            pTC = &aTC[jj];
         4451  +          }
         4452  +        }
         4453  +        assert( pTC );
         4454  +
         4455  +        /* At this point pTC points to the cheapest remaining token. */
         4456  +        if( ii==0 ){
         4457  +          if( pTC->nOvfl ){
         4458  +            nDocEst = (pTC->nOvfl * pTab->nPgsz + pTab->nPgsz) / 10;
         4459  +          }else{
         4460  +            /* TODO: Fix this so that the doclist need not be read twice. */
         4461  +            Fts3PhraseToken *pToken = pTC->pToken;
         4462  +            int nList = 0;
         4463  +            char *pList = 0;
         4464  +            rc = fts3TermSelect(pTab, pToken, pTC->iCol, 1, &nList, &pList);
         4465  +            if( rc==SQLITE_OK ){
         4466  +              nDocEst = fts3DoclistCountDocids(1, pList, nList);
         4467  +            }
         4468  +            sqlite3_free(pList);
         4469  +            if( rc==SQLITE_OK ){
         4470  +              rc = sqlite3Fts3TermSegReaderCursor(pCsr, 
         4471  +                pToken->z, pToken->n, pToken->isPrefix, &pToken->pSegcsr
         4472  +              );
         4473  +            }
         4474  +          }
         4475  +        }else{
         4476  +          if( pTC->nOvfl>=(nDocEst*nDocSize) ){
         4477  +            Fts3PhraseToken *pToken = pTC->pToken;
         4478  +            rc = sqlite3Fts3DeferToken(pCsr, pToken, pTC->iCol);
         4479  +            fts3SegReaderCursorFree(pToken->pSegcsr);
         4480  +            pToken->pSegcsr = 0;
         4481  +          }
         4482  +          nDocEst = 1 + (nDocEst/4);
         4483  +        }
         4484  +        pTC->pToken = 0;
         4485  +      }
         4486  +      sqlite3_free(aTC);
         4487  +    }
         4488  +  }
         4489  +
         4490  +  fts3EvalStartReaders(pCsr, pExpr, bOptOk, &rc);
         4491  +
         4492  +  /* Fix the results of NEAR expressions. */
         4493  +  fts3EvalNearTrim(pCsr, pExpr, &rc);
         4494  +
         4495  +  return rc;
         4496  +}
         4497  +
         4498  +static void fts3EvalNext(
         4499  +  Fts3Cursor *pCsr, 
         4500  +  Fts3Expr *pExpr, 
         4501  +  int *pRc
         4502  +){
         4503  +  if( *pRc==SQLITE_OK ){
         4504  +
         4505  +    pExpr->bStart = 1;
         4506  +    switch( pExpr->eType ){
         4507  +
         4508  +      case FTSQUERY_NEAR:
         4509  +      case FTSQUERY_AND: {
         4510  +        Fts3Expr *pLeft = pExpr->pLeft;
         4511  +        Fts3Expr *pRight = pExpr->pRight;
         4512  +
         4513  +        assert( !pLeft->bDeferred || !pRight->bDeferred );
         4514  +        if( pLeft->bDeferred ){
         4515  +          fts3EvalNext(pCsr, pRight, pRc);
         4516  +          pExpr->iDocid = pRight->iDocid;
         4517  +          pExpr->bEof = pRight->bEof;
         4518  +        }else if( pRight->bDeferred ){
         4519  +          fts3EvalNext(pCsr, pLeft, pRc);
         4520  +          pExpr->iDocid = pLeft->iDocid;
         4521  +          pExpr->bEof = pLeft->bEof;
         4522  +        }else{
         4523  +          fts3EvalNext(pCsr, pLeft, pRc);
         4524  +          fts3EvalNext(pCsr, pRight, pRc);
         4525  +
         4526  +          while( !pLeft->bEof && !pRight->bEof && *pRc==SQLITE_OK ){
         4527  +            int iDiff = pLeft->iDocid - pRight->iDocid;
         4528  +            if( iDiff==0 ) break;
         4529  +            if( iDiff<0 ){
         4530  +              fts3EvalNext(pCsr, pLeft, pRc);
         4531  +            }else{
         4532  +              fts3EvalNext(pCsr, pRight, pRc);
         4533  +            }
         4534  +          }
         4535  +    
         4536  +          pExpr->iDocid = pLeft->iDocid;
         4537  +          pExpr->bEof = (pLeft->bEof || pRight->bEof);
         4538  +        }
         4539  +        break;
         4540  +      }
         4541  +  
         4542  +      case FTSQUERY_OR: {
         4543  +        Fts3Expr *pLeft = pExpr->pLeft;
         4544  +        Fts3Expr *pRight = pExpr->pRight;
         4545  +
         4546  +        assert( pLeft->bStart || pLeft->iDocid==pRight->iDocid );
         4547  +        assert( pRight->bStart || pLeft->iDocid==pRight->iDocid );
         4548  +
         4549  +        if( pLeft->iDocid==pRight->iDocid ){
         4550  +          fts3EvalNext(pCsr, pLeft, pRc);
         4551  +          fts3EvalNext(pCsr, pRight, pRc);
         4552  +        }else if( 
         4553  +          pRight->bEof || (pLeft->bEof==0 && pLeft->iDocid<pRight->iDocid) 
         4554  +        ){
         4555  +          fts3EvalNext(pCsr, pLeft, pRc);
         4556  +        }else{
         4557  +          fts3EvalNext(pCsr, pRight, pRc);
         4558  +        }
         4559  +  
         4560  +        pExpr->bEof = (pLeft->bEof && pRight->bEof);
         4561  +        if( pRight->bEof || (pLeft->bEof==0 &&  pLeft->iDocid<pRight->iDocid) ){
         4562  +          pExpr->iDocid = pLeft->iDocid;
         4563  +        }else{
         4564  +          pExpr->iDocid = pRight->iDocid;
         4565  +        }
         4566  +
         4567  +        break;
         4568  +      }
         4569  +
         4570  +      case FTSQUERY_NOT: {
         4571  +        Fts3Expr *pLeft = pExpr->pLeft;
         4572  +        Fts3Expr *pRight = pExpr->pRight;
         4573  +
         4574  +        if( pRight->bStart==0 ){
         4575  +          fts3EvalNext(pCsr, pRight, pRc);
         4576  +          assert( *pRc!=SQLITE_OK || pRight->bStart );
         4577  +        }
         4578  +        do {
         4579  +          fts3EvalNext(pCsr, pLeft, pRc);
         4580  +          if( pLeft->bEof ) break;
         4581  +          while( !*pRc && !pRight->bEof && pRight->iDocid<pLeft->iDocid ){
         4582  +            fts3EvalNext(pCsr, pRight, pRc);
         4583  +          }
         4584  +        }while( !pRight->bEof && pRight->iDocid==pLeft->iDocid && !*pRc );
         4585  +        pExpr->iDocid = pLeft->iDocid;
         4586  +        pExpr->bEof = pLeft->bEof;
         4587  +        break;
         4588  +      }
         4589  +
         4590  +      default:
         4591  +        assert( pExpr->eType==FTSQUERY_PHRASE );
         4592  +        *pRc = fts3EvalPhraseNext(pCsr, pExpr->pPhrase, &pExpr->bEof);
         4593  +        pExpr->iDocid = fts3EvalPhraseDocid(pExpr->pPhrase);
         4594  +        break;
         4595  +    }
         4596  +  }
         4597  +}
         4598  +
         4599  +static int fts3EvalDeferredTest(Fts3Cursor *pCsr, Fts3Expr *pExpr, int *pRc){
         4600  +  int bHit = 0;
         4601  +  if( *pRc==SQLITE_OK ){
         4602  +    switch( pExpr->eType ){
         4603  +      case FTSQUERY_NEAR:
         4604  +      case FTSQUERY_AND:
         4605  +        bHit = (
         4606  +            fts3EvalDeferredTest(pCsr, pExpr->pLeft, pRc)
         4607  +         && fts3EvalDeferredTest(pCsr, pExpr->pRight, pRc)
         4608  +        );
         4609  +        break;
         4610  +
         4611  +      case FTSQUERY_OR:
         4612  +        bHit = (
         4613  +            fts3EvalDeferredTest(pCsr, pExpr->pLeft, pRc)
         4614  +         || fts3EvalDeferredTest(pCsr, pExpr->pRight, pRc)
         4615  +        );
         4616  +        break;
         4617  +
         4618  +      case FTSQUERY_NOT:
         4619  +        bHit = (
         4620  +            fts3EvalDeferredTest(pCsr, pExpr->pLeft, pRc)
         4621  +         && !fts3EvalDeferredTest(pCsr, pExpr->pRight, pRc)
         4622  +        );
         4623  +        break;
         4624  +
         4625  +      default:
         4626  +        assert( pExpr->eType==FTSQUERY_PHRASE );
         4627  +        *pRc = fts3EvalDeferredPhrase(pCsr, pExpr->pPhrase);
         4628  +        bHit = (pExpr->pPhrase->doclist.pList!=0);
         4629  +        pExpr->iDocid = pCsr->iPrevId;
         4630  +        break;
         4631  +    }
         4632  +  }
         4633  +  return bHit;
         4634  +}
         4635  +
         4636  +/*
         4637  +** Return 1 if both of the following are true:
         4638  +**
         4639  +**   1. *pRc is SQLITE_OK when this function returns, and
         4640  +**
         4641  +**   2. After scanning the current FTS table row for the deferred tokens,
         4642  +**      it is determined that the row does not match the query.
         4643  +*/
         4644  +static int fts3EvalLoadDeferred(Fts3Cursor *pCsr, int *pRc){
         4645  +  int rc = *pRc;
         4646  +  int bMiss = 0;
         4647  +  if( rc==SQLITE_OK && pCsr->pDeferred ){
         4648  +    rc = fts3CursorSeek(0, pCsr);
         4649  +    if( rc==SQLITE_OK ){
         4650  +      sqlite3Fts3FreeDeferredDoclists(pCsr);
         4651  +      rc = sqlite3Fts3CacheDeferredDoclists(pCsr);
         4652  +    }
         4653  +    bMiss = (0==fts3EvalDeferredTest(pCsr, pCsr->pExpr, &rc));
         4654  +    sqlite3Fts3FreeDeferredDoclists(pCsr);
         4655  +    *pRc = rc;
         4656  +  }
         4657  +  return (rc==SQLITE_OK && bMiss);
         4658  +}
         4659  +
         4660  +/*
         4661  +** Advance to the next document that matches the expression passed as an
         4662  +** argument.
         4663  +*/
         4664  +int sqlite3Fts3EvalNext(Fts3Cursor *pCsr, Fts3Expr *pExpr){
         4665  +  int rc = SQLITE_OK;             /* Return Code */
         4666  +  assert( pCsr->isEof==0 );
         4667  +  assert( pCsr->bIncremental );
         4668  +  if( pExpr==0 ){
         4669  +    pCsr->isEof = 1;
         4670  +  }else{
         4671  +    do {
         4672  +      sqlite3_reset(pCsr->pStmt);
         4673  +      fts3EvalNext(pCsr, pExpr, &rc);
         4674  +      pCsr->isEof = pExpr->bEof;
         4675  +      pCsr->isRequireSeek = 1;
         4676  +      pCsr->isMatchinfoNeeded = 1;
         4677  +      pCsr->iPrevId = pExpr->iDocid;
         4678  +    }while( pCsr->isEof==0 && fts3EvalLoadDeferred(pCsr, &rc) );
         4679  +  }
         4680  +  return rc;
         4681  +}
         4682  +
         4683  +int sqlite3Fts3EvalFinish(Fts3Cursor *pCsr, Fts3Expr *pExpr){
         4684  +  return SQLITE_OK;
         4685  +}
         4686  +
         4687  +sqlite3_int64 sqlite3Fts3EvalDocid(Fts3Cursor *pCsr, Fts3Expr *pExpr){
         4688  +  return pExpr->iDocid;
         4689  +}
         4690  +
         4691  +/*
         4692  +** Return a pointer to the entire doclist, including positions, associated 
         4693  +** with the phrase passed as the second argument.
         4694  +*/
         4695  +int sqlite3Fts3EvalPhraseDoclist(
         4696  +  Fts3Cursor *pCsr,               /* FTS3 cursor object */
         4697  +  Fts3Expr *pExpr,                /* Phrase to return doclist for */
         4698  +  const char **ppList,            /* OUT: Buffer containing doclist */
         4699  +  int *pnList                     /* OUT: Size of returned buffer, in bytes */
         4700  +){
         4701  +  int rc = SQLITE_OK;
         4702  +  Fts3Phrase *pPhrase = pExpr->pPhrase;
         4703  +
         4704  +  if( pPhrase->bIncr ){
         4705  +    /* This phrase was being loaded from disk incrementally. But the 
         4706  +    ** matchinfo() function requires that the entire doclist be loaded into
         4707  +    ** memory. This block loads the doclist into memory and modifies the
         4708  +    ** Fts3Phrase structure so that it does not use the incremental strategy.
         4709  +    */
         4710  +    TESTONLY( int bEof = pExpr->bEof; )
         4711  +    TESTONLY( int bStart = pExpr->bStart; )
         4712  +    sqlite3_int64 iDocid = pExpr->iDocid;
         4713  +
         4714  +    sqlite3Fts3EvalPhraseCleanup(pPhrase);
         4715  +    pExpr->iDocid = 0;
         4716  +
         4717  +    rc = sqlite3Fts3EvalStart(pCsr, pExpr, 0);
         4718  +    assert( pExpr->bEof==bEof );
         4719  +    assert( pExpr->bStart==bStart );
         4720  +    assert( rc!=SQLITE_OK || pPhrase->bIncr==0 );
         4721  +    if( pExpr->bStart && !pExpr->bEof ){
         4722  +      pExpr->bStart = 0;
         4723  +      while( rc==SQLITE_OK && pExpr->bEof==0 && pExpr->iDocid!=iDocid ){
         4724  +        fts3EvalNext(pCsr, pExpr, &rc);
         4725  +      }
         4726  +    }
         4727  +  }
         4728  +
         4729  +  *pnList = pPhrase->doclist.nAll;
         4730  +  *ppList = pPhrase->doclist.aAll;
         4731  +  return rc;
         4732  +}
         4733  +
         4734  +char *sqlite3Fts3EvalPhrasePoslist(
         4735  +  Fts3Cursor *pCsr,               /* FTS3 cursor object */
         4736  +  Fts3Expr *pExpr,                /* Phrase to return doclist for */
         4737  +  sqlite3_int64 iDocid,           /* Docid to return position list for */
         4738  +  int iCol                        /* Column to return position list for */
         4739  +){
         4740  +  Fts3Phrase *pPhrase = pExpr->pPhrase;
         4741  +  Fts3Table *pTab = (Fts3Table *)pCsr->base.pVtab;
         4742  +  char *pIter = pPhrase->doclist.pList;
         4743  +  int iThis;
         4744  +
         4745  +  assert( iCol>=0 && iCol<pTab->nColumn );
         4746  +  if( !pIter 
         4747  +   || pExpr->bEof 
         4748  +   || pExpr->iDocid!=iDocid
         4749  +   || (pPhrase->iColumn<pTab->nColumn && pPhrase->iColumn!=iCol) 
         4750  +  ){
         4751  +    return 0;
         4752  +  }
         4753  +
         4754  +  assert( pPhrase->doclist.nList>0 );
         4755  +  if( *pIter==0x01 ){
         4756  +    pIter++;
         4757  +    pIter += sqlite3Fts3GetVarint32(pIter, &iThis);
         4758  +  }else{
         4759  +    iThis = 0;
         4760  +  }
         4761  +  while( iThis<iCol ){
         4762  +    fts3ColumnlistCopy(0, &pIter);
         4763  +    if( *pIter==0x00 ) return 0;
         4764  +    pIter++;
         4765  +    pIter += sqlite3Fts3GetVarint32(pIter, &iThis);
         4766  +  }
         4767  +
         4768  +  return ((iCol==iThis)?pIter:0);
         4769  +}
         4770  +
         4771  +void sqlite3Fts3EvalPhraseCleanup(Fts3Phrase *pPhrase){
         4772  +  int i;
         4773  +  sqlite3_free(pPhrase->doclist.aAll);
         4774  +  memset(&pPhrase->doclist, 0, sizeof(Fts3Doclist));
         4775  +  for(i=0; i<pPhrase->nToken; i++){
         4776  +    fts3SegReaderCursorFree(pPhrase->aToken[i].pSegcsr);
         4777  +    pPhrase->aToken[i].pSegcsr = 0;
         4778  +  }
         4779  +}
  3988   4780   
  3989   4781   #endif

Changes to ext/fts3/fts3Int.h.

    43     43   /*
    44     44   ** Macro to return the number of elements in an array. SQLite has a
    45     45   ** similar macro called ArraySize(). Use a different name to avoid
    46     46   ** a collision when building an amalgamation with built-in FTS3.
    47     47   */
    48     48   #define SizeofArray(X) ((int)(sizeof(X)/sizeof(X[0])))
    49     49   
           50  +
           51  +#ifndef MIN
           52  +# define MIN(x,y) ((x)<(y)?(x):(y))
           53  +#endif
           54  +
    50     55   /*
    51     56   ** Maximum length of a varint encoded integer. The varint format is different
    52     57   ** from that used by SQLite, so the maximum length is 10, not 9.
    53     58   */
    54     59   #define FTS3_VARINT_MAX 10
    55     60   
    56     61   /*
................................................................................
   138    143   
   139    144   typedef struct Fts3Table Fts3Table;
   140    145   typedef struct Fts3Cursor Fts3Cursor;
   141    146   typedef struct Fts3Expr Fts3Expr;
   142    147   typedef struct Fts3Phrase Fts3Phrase;
   143    148   typedef struct Fts3PhraseToken Fts3PhraseToken;
   144    149   
          150  +typedef struct Fts3Doclist Fts3Doclist;
   145    151   typedef struct Fts3SegFilter Fts3SegFilter;
   146    152   typedef struct Fts3DeferredToken Fts3DeferredToken;
   147    153   typedef struct Fts3SegReader Fts3SegReader;
   148         -typedef struct Fts3SegReaderCursor Fts3SegReaderCursor;
          154  +typedef struct Fts3MultiSegReader Fts3MultiSegReader;
   149    155   
   150    156   /*
   151    157   ** A connection to a fulltext index is an instance of the following
   152    158   ** structure. The xCreate and xConnect methods create an instance
   153    159   ** of this structure and xDestroy and xDisconnect free that instance.
   154    160   ** All other methods receive a pointer to the structure as one of their
   155    161   ** arguments.
................................................................................
   220    226   struct Fts3Cursor {
   221    227     sqlite3_vtab_cursor base;       /* Base class used by SQLite core */
   222    228     i16 eSearch;                    /* Search strategy (see below) */
   223    229     u8 isEof;                       /* True if at End Of Results */
   224    230     u8 isRequireSeek;               /* True if must seek pStmt to %_content row */
   225    231     sqlite3_stmt *pStmt;            /* Prepared statement in use by the cursor */
   226    232     Fts3Expr *pExpr;                /* Parsed MATCH query string */
          233  +  int bIncremental;               /* True to use incremental querying */
   227    234     int nPhrase;                    /* Number of matchable phrases in query */
   228    235     Fts3DeferredToken *pDeferred;   /* Deferred search tokens, if any */
   229    236     sqlite3_int64 iPrevId;          /* Previous id read from aDoclist */
   230    237     char *pNextId;                  /* Pointer into the body of aDoclist */
   231    238     char *aDoclist;                 /* List of docids for full-text queries */
   232    239     int nDoclist;                   /* Size of buffer at aDoclist */
   233    240     int desc;                       /* True to sort in descending order */
................................................................................
   259    266   ** indicating that all columns should be searched,
   260    267   ** then eSearch would be set to FTS3_FULLTEXT_SEARCH+4.
   261    268   */
   262    269   #define FTS3_FULLSCAN_SEARCH 0    /* Linear scan of %_content table */
   263    270   #define FTS3_DOCID_SEARCH    1    /* Lookup by rowid on %_content table */
   264    271   #define FTS3_FULLTEXT_SEARCH 2    /* Full-text index search */
   265    272   
          273  +
          274  +struct Fts3Doclist {
          275  +  char *aAll;                    /* Array containing doclist (or NULL) */
          276  +  int nAll;                      /* Size of a[] in bytes */
          277  +
          278  +  sqlite3_int64 iDocid;          /* Current docid (if p!=0) */
          279  +  char *pNextDocid;              /* Pointer to next docid */
          280  +  char *pList;                   /* Pointer to position list following iDocid */
          281  +  int nList;                     /* Length of position list */
          282  +} doclist;
          283  +
   266    284   /*
   267    285   ** A "phrase" is a sequence of one or more tokens that must match in
   268    286   ** sequence.  A single token is the base case and the most common case.
   269    287   ** For a sequence of tokens contained in double-quotes (i.e. "one two three")
   270    288   ** nToken will be the number of tokens in the string.
   271    289   */
   272    290   struct Fts3PhraseToken {
................................................................................
   273    291     char *z;                        /* Text of the token */
   274    292     int n;                          /* Number of bytes in buffer z */
   275    293     int isPrefix;                   /* True if token ends with a "*" character */
   276    294   
   277    295     /* Variables above this point are populated when the expression is
   278    296     ** parsed (by code in fts3_expr.c). Below this point the variables are
   279    297     ** used when evaluating the expression. */
   280         -
   281    298     int bFulltext;                  /* True if full-text index was used */
   282         -  Fts3SegReaderCursor *pSegcsr;   /* Segment-reader for this token */
   283    299     Fts3DeferredToken *pDeferred;   /* Deferred token object for this token */
          300  +  Fts3MultiSegReader *pSegcsr;    /* Segment-reader for this token */
   284    301   };
   285    302   
   286    303   struct Fts3Phrase {
   287         -  /* Variables populated by fts3_expr.c when parsing a MATCH expression */
   288         -  int nToken;                /* Number of tokens in the phrase */
   289         -  int iColumn;               /* Index of column this phrase must match */
          304  +  /* Cache of doclist for this phrase. */
          305  +  Fts3Doclist doclist;
          306  +  int bIncr;                 /* True if doclist is loaded incrementally */
   290    307   
          308  +#if 1
   291    309     int isLoaded;              /* True if aDoclist/nDoclist are initialized. */
   292    310     char *aDoclist;            /* Buffer containing doclist */
   293    311     int nDoclist;              /* Size of aDoclist in bytes */
   294    312     sqlite3_int64 iCurrent;
   295    313     char *pCurrent;
          314  +#endif
   296    315   
          316  +  /* Variables below this point are populated by fts3_expr.c when parsing 
          317  +  ** a MATCH expression. Everything above is part of the evaluation phase. 
          318  +  */
          319  +  int nToken;                /* Number of tokens in the phrase */
          320  +  int iColumn;               /* Index of column this phrase must match */
   297    321     Fts3PhraseToken aToken[1]; /* One entry for each token in the phrase */
   298    322   };
   299    323   
   300    324   /*
   301    325   ** A tree of these objects forms the RHS of a MATCH operator.
   302    326   **
   303    327   ** If Fts3Expr.eType is FTSQUERY_PHRASE and isLoaded is true, then aDoclist 
................................................................................
   313    337   struct Fts3Expr {
   314    338     int eType;                 /* One of the FTSQUERY_XXX values defined below */
   315    339     int nNear;                 /* Valid if eType==FTSQUERY_NEAR */
   316    340     Fts3Expr *pParent;         /* pParent->pLeft==this or pParent->pRight==this */
   317    341     Fts3Expr *pLeft;           /* Left operand */
   318    342     Fts3Expr *pRight;          /* Right operand */
   319    343     Fts3Phrase *pPhrase;       /* Valid if eType==FTSQUERY_PHRASE */
          344  +
          345  +  /* The following are used by the fts3_eval.c module. */
          346  +  sqlite3_int64 iDocid;      /* Current docid */
          347  +  u8 bEof;                   /* True this expression is at EOF already */
          348  +  u8 bStart;                 /* True if iDocid is valid */
          349  +  u8 bDeferred;              /* True if this expression is entirely deferred */
   320    350   };
   321    351   
   322    352   /*
   323    353   ** Candidate values for Fts3Query.eType. Note that the order of the first
   324    354   ** four values is in order of precedence when parsing expressions. For 
   325    355   ** example, the following:
   326    356   **
................................................................................
   362    392   char *sqlite3Fts3DeferredDoclist(Fts3DeferredToken *, int *);
   363    393   void sqlite3Fts3SegmentsClose(Fts3Table *);
   364    394   
   365    395   /* Special values interpreted by sqlite3SegReaderCursor() */
   366    396   #define FTS3_SEGCURSOR_PENDING        -1
   367    397   #define FTS3_SEGCURSOR_ALL            -2
   368    398   
   369         -int sqlite3Fts3SegReaderStart(Fts3Table*, Fts3SegReaderCursor*, Fts3SegFilter*);
   370         -int sqlite3Fts3SegReaderStep(Fts3Table *, Fts3SegReaderCursor *);
   371         -void sqlite3Fts3SegReaderFinish(Fts3SegReaderCursor *);
          399  +int sqlite3Fts3SegReaderStart(Fts3Table*, Fts3MultiSegReader*, Fts3SegFilter*);
          400  +int sqlite3Fts3SegReaderStep(Fts3Table *, Fts3MultiSegReader *);
          401  +void sqlite3Fts3SegReaderFinish(Fts3MultiSegReader *);
          402  +
   372    403   int sqlite3Fts3SegReaderCursor(
   373         -    Fts3Table *, int, int, const char *, int, int, int, Fts3SegReaderCursor *);
          404  +    Fts3Table *, int, int, const char *, int, int, int, Fts3MultiSegReader *);
   374    405   
   375    406   /* Flags allowed as part of the 4th argument to SegmentReaderIterate() */
   376    407   #define FTS3_SEGMENT_REQUIRE_POS   0x00000001
   377    408   #define FTS3_SEGMENT_IGNORE_EMPTY  0x00000002
   378    409   #define FTS3_SEGMENT_COLUMN_FILTER 0x00000004
   379    410   #define FTS3_SEGMENT_PREFIX        0x00000008
   380    411   #define FTS3_SEGMENT_SCAN          0x00000010
................................................................................
   383    414   struct Fts3SegFilter {
   384    415     const char *zTerm;
   385    416     int nTerm;
   386    417     int iCol;
   387    418     int flags;
   388    419   };
   389    420   
   390         -struct Fts3SegReaderCursor {
          421  +struct Fts3MultiSegReader {
   391    422     /* Used internally by sqlite3Fts3SegReaderXXX() calls */
   392    423     Fts3SegReader **apSegment;      /* Array of Fts3SegReader objects */
   393    424     int nSegment;                   /* Size of apSegment array */
   394    425     int nAdvance;                   /* How many seg-readers to advance */
   395    426     Fts3SegFilter *pFilter;         /* Pointer to filter object */
   396    427     char *aBuffer;                  /* Buffer to merge doclists in */
   397    428     int nBuffer;                    /* Allocated size of aBuffer[] in bytes */
   398    429   
   399         -  /* Cost of running this iterator. Used by fts3.c only. */
   400         -  int nCost;
          430  +  int iColFilter;                 /* If >=0, filter for this column */
          431  +
          432  +  /* Used by fts3.c only. */
          433  +  int nCost;                      /* Cost of running iterator */
          434  +  int bLookup;                    /* True if a lookup of a single entry. */
   401    435   
   402    436     /* Output values. Valid only after Fts3SegReaderStep() returns SQLITE_ROW. */
   403    437     char *zTerm;                    /* Pointer to term buffer */
   404    438     int nTerm;                      /* Size of zTerm in bytes */
   405    439     char *aDoclist;                 /* Pointer to doclist buffer */
   406    440     int nDoclist;                   /* Size of aDoclist[] in bytes */
   407    441   };
................................................................................
   409    443   /* fts3.c */
   410    444   int sqlite3Fts3PutVarint(char *, sqlite3_int64);
   411    445   int sqlite3Fts3GetVarint(const char *, sqlite_int64 *);
   412    446   int sqlite3Fts3GetVarint32(const char *, int *);
   413    447   int sqlite3Fts3VarintLen(sqlite3_uint64);
   414    448   void sqlite3Fts3Dequote(char *);
   415    449   
   416         -char *sqlite3Fts3FindPositions(Fts3Cursor *, Fts3Expr *, sqlite3_int64, int);
   417    450   int sqlite3Fts3ExprLoadDoclist(Fts3Cursor *, Fts3Expr *);
   418    451   int sqlite3Fts3ExprLoadFtDoclist(Fts3Cursor *, Fts3Expr *, char **, int *);
   419    452   int sqlite3Fts3ExprNearTrim(Fts3Expr *, Fts3Expr *, int);
   420    453   
   421    454   /* fts3_tokenizer.c */
   422    455   const char *sqlite3Fts3NextToken(const char *, int *);
   423    456   int sqlite3Fts3InitHashTable(sqlite3 *, Fts3Hash *, const char *);
................................................................................
   442    475   int sqlite3Fts3ExprInitTestInterface(sqlite3 *db);
   443    476   int sqlite3Fts3InitTerm(sqlite3 *db);
   444    477   #endif
   445    478   
   446    479   /* fts3_aux.c */
   447    480   int sqlite3Fts3InitAux(sqlite3 *db);
   448    481   
          482  +int sqlite3Fts3TermSegReaderCursor(
          483  +  Fts3Cursor *pCsr,               /* Virtual table cursor handle */
          484  +  const char *zTerm,              /* Term to query for */
          485  +  int nTerm,                      /* Size of zTerm in bytes */
          486  +  int isPrefix,                   /* True for a prefix search */
          487  +  Fts3MultiSegReader **ppSegcsr   /* OUT: Allocated seg-reader cursor */
          488  +);
          489  +
          490  +int sqlite3Fts3EvalPhraseCache(Fts3Cursor *, Fts3Phrase *);
          491  +sqlite3_int64 sqlite3Fts3EvalDocid(Fts3Cursor *, Fts3Expr *);
          492  +int sqlite3Fts3EvalPhraseDoclist(Fts3Cursor*, Fts3Expr*, const char**,int*);
          493  +void sqlite3Fts3EvalPhraseCleanup(Fts3Phrase *);
          494  +
          495  +int sqlite3Fts3EvalStart(Fts3Cursor *, Fts3Expr *, int);
          496  +int sqlite3Fts3EvalNext(Fts3Cursor *pCsr, Fts3Expr *pExpr);
          497  +int sqlite3Fts3MsrIncrStart(
          498  +    Fts3Table*, Fts3MultiSegReader*, int, const char*, int);
          499  +int sqlite3Fts3MsrIncrNext(
          500  +    Fts3Table *, Fts3MultiSegReader *, sqlite3_int64 *, char **, int *);
          501  +char *sqlite3Fts3EvalPhrasePoslist(
          502  +  Fts3Cursor *, Fts3Expr *, sqlite3_int64, int iCol); 
          503  +int sqlite3Fts3MsrOvfl(Fts3Cursor *, Fts3MultiSegReader *, int *);
          504  +
          505  +int sqlite3Fts3DeferredTokenList(Fts3DeferredToken *, char **, int *);
          506  +
   449    507   #endif /* _FTSINT_H */

Changes to ext/fts3/fts3_aux.c.

    24     24   struct Fts3auxTable {
    25     25     sqlite3_vtab base;              /* Base class used by SQLite core */
    26     26     Fts3Table *pFts3Tab;
    27     27   };
    28     28   
    29     29   struct Fts3auxCursor {
    30     30     sqlite3_vtab_cursor base;       /* Base class used by SQLite core */
    31         -  Fts3SegReaderCursor csr;        /* Must be right after "base" */
           31  +  Fts3MultiSegReader csr;        /* Must be right after "base" */
    32     32     Fts3SegFilter filter;
    33     33     char *zStop;
    34     34     int nStop;                      /* Byte-length of string zStop */
    35     35     int isEof;                      /* True if cursor is at EOF */
    36     36     sqlite3_int64 iRowid;           /* Current rowid */
    37     37   
    38     38     int iCol;                       /* Current value of 'col' column */

Changes to ext/fts3/fts3_expr.c.

   764    764   ** Free a parsed fts3 query expression allocated by sqlite3Fts3ExprParse().
   765    765   */
   766    766   void sqlite3Fts3ExprFree(Fts3Expr *p){
   767    767     if( p ){
   768    768       assert( p->eType==FTSQUERY_PHRASE || p->pPhrase==0 );
   769    769       sqlite3Fts3ExprFree(p->pLeft);
   770    770       sqlite3Fts3ExprFree(p->pRight);
   771         -    if( p->pPhrase ) sqlite3_free(p->pPhrase->aDoclist);
          771  +    if( p->pPhrase ){
          772  +      sqlite3Fts3EvalPhraseCleanup(p->pPhrase);
          773  +      sqlite3_free(p->pPhrase->aDoclist);
          774  +    }
   772    775       sqlite3_free(p);
   773    776     }
   774    777   }
   775    778   
   776    779   /****************************************************************************
   777    780   *****************************************************************************
   778    781   ** Everything after this point is just test code.

Changes to ext/fts3/fts3_snippet.c.

   412    412   static int fts3SnippetFindPositions(Fts3Expr *pExpr, int iPhrase, void *ctx){
   413    413     SnippetIter *p = (SnippetIter *)ctx;
   414    414     SnippetPhrase *pPhrase = &p->aPhrase[iPhrase];
   415    415     char *pCsr;
   416    416   
   417    417     pPhrase->nToken = pExpr->pPhrase->nToken;
   418    418   
   419         -  pCsr = sqlite3Fts3FindPositions(p->pCsr, pExpr, p->pCsr->iPrevId, p->iCol);
          419  +  pCsr = sqlite3Fts3EvalPhrasePoslist(p->pCsr, pExpr, p->pCsr->iPrevId,p->iCol);
   420    420     if( pCsr ){
   421    421       int iFirst = 0;
   422    422       pPhrase->pList = pCsr;
   423    423       fts3GetDeltaPosition(&pCsr, &iFirst);
   424    424       pPhrase->pHead = pCsr;
   425    425       pPhrase->pTail = pCsr;
   426    426       pPhrase->iHead = iFirst;
................................................................................
   822    822   */
   823    823   static int fts3ExprGlobalHitsCb(
   824    824     Fts3Expr *pExpr,                /* Phrase expression node */
   825    825     int iPhrase,                    /* Phrase number (numbered from zero) */
   826    826     void *pCtx                      /* Pointer to MatchInfo structure */
   827    827   ){
   828    828     MatchInfo *p = (MatchInfo *)pCtx;
   829         -  Fts3Cursor *pCsr = p->pCursor;
   830         -  Fts3Phrase *pPhrase = pExpr->pPhrase; 
   831         -  char *pIter;
   832         -  char *pEnd;
   833         -  char *pFree = 0;
   834    829     u32 *aOut = &p->aMatchinfo[3*iPhrase*p->nCol];
   835    830   
   836         -  assert( pPhrase->isLoaded );
   837         -
   838         -  if( pCsr->pDeferred ){
   839         -    int ii;
   840         -    for(ii=0; ii<pPhrase->nToken; ii++){
   841         -      if( pPhrase->aToken[ii].bFulltext ) break;
   842         -    }
   843         -    if( ii<pPhrase->nToken ){
   844         -      int nFree = 0;
   845         -      int rc = sqlite3Fts3ExprLoadFtDoclist(pCsr, pExpr, &pFree, &nFree);
   846         -      if( rc!=SQLITE_OK ) return rc;
   847         -      pIter = pFree;
   848         -      pEnd = &pFree[nFree];
   849         -    }else{
   850         -      int iCol;                   /* Column index */
   851         -      for(iCol=0; iCol<p->nCol; iCol++){
   852         -        aOut[iCol*3 + 1] = (u32)p->nDoc;
   853         -        aOut[iCol*3 + 2] = (u32)p->nDoc;
   854         -      }
   855         -      return SQLITE_OK;
          831  +  if( pExpr->bDeferred ){
          832  +    int iCol;                   /* Column index */
          833  +    for(iCol=0; iCol<p->nCol; iCol++){
          834  +      aOut[iCol*3 + 1] = (u32)p->nDoc;
          835  +      aOut[iCol*3 + 2] = (u32)p->nDoc;
   856    836       }
   857    837     }else{
   858         -    pIter = pPhrase->aDoclist;
   859         -    pEnd = &pPhrase->aDoclist[pPhrase->nDoclist];
          838  +    char *pIter;
          839  +    char *pEnd;
          840  +    int n;
          841  +    int rc = sqlite3Fts3EvalPhraseDoclist(
          842  +        p->pCursor, pExpr, (const char **)&pIter, &n
          843  +    );
          844  +    if( rc!=SQLITE_OK ) return rc;
          845  +    pEnd = &pIter[n];
          846  +
          847  +    /* Fill in the global hit count matrix row for this phrase. */
          848  +    while( pIter<pEnd ){
          849  +      while( *pIter++ & 0x80 );      /* Skip past docid. */
          850  +      fts3LoadColumnlistCounts(&pIter, &aOut[1], 1);
          851  +    }
   860    852     }
   861    853   
   862         -  /* Fill in the global hit count matrix row for this phrase. */
   863         -  while( pIter<pEnd ){
   864         -    while( *pIter++ & 0x80 );      /* Skip past docid. */
   865         -    fts3LoadColumnlistCounts(&pIter, &aOut[1], 1);
   866         -  }
   867         -
   868         -  sqlite3_free(pFree);
   869    854     return SQLITE_OK;
   870    855   }
   871    856   
   872    857   /*
   873    858   ** fts3ExprIterate() callback used to collect the "local" part of the
   874    859   ** FTS3_MATCHINFO_HITS array. The local stats are those elements of the 
   875    860   ** array that are different for each row returned by the query.
................................................................................
   878    863     Fts3Expr *pExpr,                /* Phrase expression node */
   879    864     int iPhrase,                    /* Phrase number */
   880    865     void *pCtx                      /* Pointer to MatchInfo structure */
   881    866   ){
   882    867     MatchInfo *p = (MatchInfo *)pCtx;
   883    868     int iStart = iPhrase * p->nCol * 3;
   884    869     int i;
          870  +  sqlite3_int64 iDocid = p->pCursor->iPrevId;
   885    871   
   886         -  for(i=0; i<p->nCol; i++) p->aMatchinfo[iStart+i*3] = 0;
   887         -
   888         -  if( pExpr->pPhrase->aDoclist ){
          872  +  for(i=0; i<p->nCol; i++){
   889    873       char *pCsr;
   890         -
   891         -    pCsr = sqlite3Fts3FindPositions(p->pCursor, pExpr, p->pCursor->iPrevId, -1);
          874  +    pCsr = sqlite3Fts3EvalPhrasePoslist(p->pCursor, pExpr, iDocid, i);
   892    875       if( pCsr ){
   893         -      fts3LoadColumnlistCounts(&pCsr, &p->aMatchinfo[iStart], 0);
          876  +      p->aMatchinfo[iStart+i*3] = fts3ColumnlistCount(&pCsr);
          877  +    }else{
          878  +      p->aMatchinfo[iStart+i*3] = 0;
   894    879       }
   895    880     }
   896    881   
   897    882     return SQLITE_OK;
   898    883   }
   899    884   
   900    885   static int fts3MatchinfoCheck(
................................................................................
   972    957   ** iterating through a multi-column position-list corresponding to the
   973    958   ** hits for a single phrase on a single row in order to calculate the
   974    959   ** values for a matchinfo() FTS3_MATCHINFO_LCS request.
   975    960   */
   976    961   typedef struct LcsIterator LcsIterator;
   977    962   struct LcsIterator {
   978    963     Fts3Expr *pExpr;                /* Pointer to phrase expression */
   979         -  char *pRead;                    /* Cursor used to iterate through aDoclist */
   980    964     int iPosOffset;                 /* Tokens count up to end of this phrase */
   981         -  int iCol;                       /* Current column number */
          965  +  char *pRead;                    /* Cursor used to iterate through aDoclist */
   982    966     int iPos;                       /* Current position */
   983    967   };
   984    968   
   985    969   /* 
   986    970   ** If LcsIterator.iCol is set to the following value, the iterator has
   987    971   ** finished iterating through all offsets for all columns.
   988    972   */
................................................................................
  1005    989   */
  1006    990   static int fts3LcsIteratorAdvance(LcsIterator *pIter){
  1007    991     char *pRead = pIter->pRead;
  1008    992     sqlite3_int64 iRead;
  1009    993     int rc = 0;
  1010    994   
  1011    995     pRead += sqlite3Fts3GetVarint(pRead, &iRead);
  1012         -  if( iRead==0 ){
  1013         -    pIter->iCol = LCS_ITERATOR_FINISHED;
          996  +  if( iRead==0 || iRead==1 ){
          997  +    pRead = 0;
  1014    998       rc = 1;
  1015    999     }else{
  1016         -    if( iRead==1 ){
  1017         -      pRead += sqlite3Fts3GetVarint(pRead, &iRead);
  1018         -      pIter->iCol = (int)iRead;
  1019         -      pIter->iPos = pIter->iPosOffset;
  1020         -      pRead += sqlite3Fts3GetVarint(pRead, &iRead);
  1021         -      rc = 1;
  1022         -    }
  1023   1000       pIter->iPos += (int)(iRead-2);
  1024   1001     }
  1025   1002   
  1026   1003     pIter->pRead = pRead;
  1027   1004     return rc;
  1028   1005   }
  1029   1006     
................................................................................
  1039   1016   ** undefined.
  1040   1017   */
  1041   1018   static int fts3MatchinfoLcs(Fts3Cursor *pCsr, MatchInfo *pInfo){
  1042   1019     LcsIterator *aIter;
  1043   1020     int i;
  1044   1021     int iCol;
  1045   1022     int nToken = 0;
         1023  +  sqlite3_int64 iDocid = pCsr->iPrevId;
  1046   1024   
  1047   1025     /* Allocate and populate the array of LcsIterator objects. The array
  1048   1026     ** contains one element for each matchable phrase in the query.
  1049   1027     **/
  1050   1028     aIter = sqlite3_malloc(sizeof(LcsIterator) * pCsr->nPhrase);
  1051   1029     if( !aIter ) return SQLITE_NOMEM;
  1052   1030     memset(aIter, 0, sizeof(LcsIterator) * pCsr->nPhrase);
  1053   1031     (void)fts3ExprIterate(pCsr->pExpr, fts3MatchinfoLcsCb, (void*)aIter);
         1032  +
  1054   1033     for(i=0; i<pInfo->nPhrase; i++){
  1055   1034       LcsIterator *pIter = &aIter[i];
  1056   1035       nToken -= pIter->pExpr->pPhrase->nToken;
  1057   1036       pIter->iPosOffset = nToken;
  1058         -    pIter->pRead = sqlite3Fts3FindPositions(pCsr,pIter->pExpr,pCsr->iPrevId,-1);
  1059         -    if( pIter->pRead ){
  1060         -      pIter->iPos = pIter->iPosOffset;
  1061         -      fts3LcsIteratorAdvance(&aIter[i]);
  1062         -    }else{
  1063         -      pIter->iCol = LCS_ITERATOR_FINISHED;
  1064         -    }
  1065   1037     }
  1066   1038   
  1067   1039     for(iCol=0; iCol<pInfo->nCol; iCol++){
  1068   1040       int nLcs = 0;                 /* LCS value for this column */
  1069   1041       int nLive = 0;                /* Number of iterators in aIter not at EOF */
  1070   1042   
  1071         -    /* Loop through the iterators in aIter[]. Set nLive to the number of
  1072         -    ** iterators that point to a position-list corresponding to column iCol.
  1073         -    */
  1074   1043       for(i=0; i<pInfo->nPhrase; i++){
  1075         -      assert( aIter[i].iCol>=iCol );
  1076         -      if( aIter[i].iCol==iCol ) nLive++;
         1044  +      LcsIterator *pIt = &aIter[i];
         1045  +      pIt->pRead = sqlite3Fts3EvalPhrasePoslist(pCsr, pIt->pExpr, iDocid, iCol);
         1046  +      if( pIt->pRead ){
         1047  +        pIt->iPos = pIt->iPosOffset;
         1048  +        fts3LcsIteratorAdvance(&aIter[i]);
         1049  +        nLive++;
         1050  +      }
  1077   1051       }
  1078   1052   
  1079         -    /* The following loop runs until all iterators in aIter[] have finished
  1080         -    ** iterating through positions in column iCol. Exactly one of the 
  1081         -    ** iterators is advanced each time the body of the loop is run.
  1082         -    */
  1083   1053       while( nLive>0 ){
  1084   1054         LcsIterator *pAdv = 0;      /* The iterator to advance by one position */
  1085   1055         int nThisLcs = 0;           /* LCS for the current iterator positions */
  1086   1056   
  1087   1057         for(i=0; i<pInfo->nPhrase; i++){
  1088   1058           LcsIterator *pIter = &aIter[i];
  1089         -        if( iCol!=pIter->iCol ){  
         1059  +        if( pIter->pRead==0 ){
  1090   1060             /* This iterator is already at EOF for this column. */
  1091   1061             nThisLcs = 0;
  1092   1062           }else{
  1093   1063             if( pAdv==0 || pIter->iPos<pAdv->iPos ){
  1094   1064               pAdv = pIter;
  1095   1065             }
  1096   1066             if( nThisLcs==0 || pIter->iPos==pIter[-1].iPos ){
................................................................................
  1422   1392     TermOffsetCtx *p = (TermOffsetCtx *)ctx;
  1423   1393     int nTerm;                      /* Number of tokens in phrase */
  1424   1394     int iTerm;                      /* For looping through nTerm phrase terms */
  1425   1395     char *pList;                    /* Pointer to position list for phrase */
  1426   1396     int iPos = 0;                   /* First position in position-list */
  1427   1397   
  1428   1398     UNUSED_PARAMETER(iPhrase);
  1429         -  pList = sqlite3Fts3FindPositions(p->pCsr, pExpr, p->iDocid, p->iCol);
         1399  +  pList = sqlite3Fts3EvalPhrasePoslist(p->pCsr, pExpr, p->iDocid, p->iCol);
  1430   1400     nTerm = pExpr->pPhrase->nToken;
  1431   1401     if( pList ){
  1432   1402       fts3GetDeltaPosition(&pList, &iPos);
  1433   1403       assert( iPos>=0 );
  1434   1404     }
  1435   1405   
  1436   1406     for(iTerm=0; iTerm<nTerm; iTerm++){

Changes to ext/fts3/fts3_term.c.

    29     29     sqlite3_vtab base;              /* Base class used by SQLite core */
    30     30     int iIndex;                     /* Index for Fts3Table.aIndex[] */
    31     31     Fts3Table *pFts3Tab;
    32     32   };
    33     33   
    34     34   struct Fts3termCursor {
    35     35     sqlite3_vtab_cursor base;       /* Base class used by SQLite core */
    36         -  Fts3SegReaderCursor csr;        /* Must be right after "base" */
           36  +  Fts3MultiSegReader csr;        /* Must be right after "base" */
    37     37     Fts3SegFilter filter;
    38     38   
    39     39     int isEof;                      /* True if cursor is at EOF */
    40     40     char *pNext;
    41     41   
    42     42     sqlite3_int64 iRowid;           /* Current 'rowid' value */
    43     43     sqlite3_int64 iDocid;           /* Current 'docid' value */

Changes to ext/fts3/fts3_write.c.

  1150   1150     Fts3SegReader *pReader,         /* Segment-reader handle */
  1151   1151     int *pnCost                     /* IN/OUT: Number of bytes read */
  1152   1152   ){
  1153   1153     Fts3Table *p = (Fts3Table*)pCsr->base.pVtab;
  1154   1154     int rc = SQLITE_OK;             /* Return code */
  1155   1155     int nCost = 0;                  /* Cost in bytes to return */
  1156   1156     int pgsz = p->nPgsz;            /* Database page size */
         1157  +
         1158  +  assert( pgsz>0 );
  1157   1159   
  1158   1160     /* If this seg-reader is reading the pending-terms table, or if all data
  1159   1161     ** for the segment is stored on the root page of the b-tree, then the cost
  1160   1162     ** is zero. In this case all required data is already in main memory.
  1161   1163     */
  1162   1164     if( p->bHasStat 
  1163   1165      && !fts3SegReaderIsPending(pReader) 
................................................................................
  1218   1220         }
  1219   1221       }
  1220   1222     }
  1221   1223   
  1222   1224     *pnCost += nCost;
  1223   1225     return rc;
  1224   1226   }
         1227  +
         1228  +int sqlite3Fts3MsrOvfl(
         1229  +  Fts3Cursor *pCsr, 
         1230  +  Fts3MultiSegReader *pMsr,
         1231  +  int *pnOvfl
         1232  +){
         1233  +  Fts3Table *p = (Fts3Table*)pCsr->base.pVtab;
         1234  +  int nOvfl = 0;
         1235  +  int ii;
         1236  +  int rc = SQLITE_OK;
         1237  +  int pgsz = p->nPgsz;
         1238  +
         1239  +  assert( p->bHasStat );
         1240  +  assert( pgsz>0 );
         1241  +
         1242  +  for(ii=0; rc==SQLITE_OK && ii<pMsr->nSegment; ii++){
         1243  +    Fts3SegReader *pReader = pMsr->apSegment[ii];
         1244  +    if( !fts3SegReaderIsPending(pReader) 
         1245  +     && !fts3SegReaderIsRootOnly(pReader) 
         1246  +    ){
         1247  +      int jj;
         1248  +      for(jj=pReader->iStartBlock; jj<=pReader->iLeafEndBlock; jj++){
         1249  +        int nBlob;
         1250  +        rc = sqlite3Fts3ReadBlock(p, jj, 0, &nBlob);
         1251  +        if( rc!=SQLITE_OK ) break;
         1252  +        if( (nBlob+35)>pgsz ){
         1253  +          nOvfl += (nBlob + 34)/pgsz;
         1254  +        }
         1255  +      }
         1256  +    }
         1257  +  }
         1258  +  *pnOvfl = nOvfl;
         1259  +  return rc;
         1260  +}
  1225   1261   
  1226   1262   /*
  1227   1263   ** Free all allocations associated with the iterator passed as the 
  1228   1264   ** second argument.
  1229   1265   */
  1230   1266   void sqlite3Fts3SegReaderFree(Fts3SegReader *pReader){
  1231   1267     if( pReader && !fts3SegReaderIsPending(pReader) ){
................................................................................
  2135   2171       p = &pList[1];
  2136   2172       p += sqlite3Fts3GetVarint32(p, &iCurrent);
  2137   2173     }
  2138   2174   
  2139   2175     *ppList = pList;
  2140   2176     *pnList = nList;
  2141   2177   }
         2178  +
         2179  +int sqlite3Fts3MsrIncrStart(
         2180  +  Fts3Table *p,                   /* Virtual table handle */
         2181  +  Fts3MultiSegReader *pCsr,       /* Cursor object */
         2182  +  int iCol,                       /* Column to match on. */
         2183  +  const char *zTerm,              /* Term to iterate through a doclist for */
         2184  +  int nTerm                       /* Number of bytes in zTerm */
         2185  +){
         2186  +  int i;
         2187  +  int nSegment = pCsr->nSegment;
         2188  +
         2189  +  assert( pCsr->pFilter==0 );
         2190  +  assert( zTerm && nTerm>0 );
         2191  +
         2192  +  /* Advance each segment iterator until it points to the term zTerm/nTerm. */
         2193  +  for(i=0; i<nSegment; i++){
         2194  +    Fts3SegReader *pSeg = pCsr->apSegment[i];
         2195  +    do {
         2196  +      int rc = fts3SegReaderNext(p, pSeg);
         2197  +      if( rc!=SQLITE_OK ) return rc;
         2198  +    }while( fts3SegReaderTermCmp(pSeg, zTerm, nTerm)<0 );
         2199  +  }
         2200  +  fts3SegReaderSort(pCsr->apSegment, nSegment, nSegment, fts3SegReaderCmp);
         2201  +
         2202  +  /* Determine how many of the segments actually point to zTerm/nTerm. */
         2203  +  for(i=0; i<nSegment; i++){
         2204  +    Fts3SegReader *pSeg = pCsr->apSegment[i];
         2205  +    if( !pSeg->aNode || fts3SegReaderTermCmp(pSeg, zTerm, nTerm) ){
         2206  +      break;
         2207  +    }
         2208  +  }
         2209  +  pCsr->nAdvance = i;
         2210  +
         2211  +  /* Advance each of the segments to point to the first docid. */
         2212  +  for(i=0; i<pCsr->nAdvance; i++){
         2213  +    fts3SegReaderFirstDocid(pCsr->apSegment[i]);
         2214  +  }
         2215  +
         2216  +  assert( iCol<0 || iCol<p->nColumn );
         2217  +  pCsr->iColFilter = iCol;
         2218  +
         2219  +  return SQLITE_OK;
         2220  +}
         2221  +
         2222  +int sqlite3Fts3MsrIncrNext(
         2223  +  Fts3Table *p,                   /* Virtual table handle */
         2224  +  Fts3MultiSegReader *pMsr,       /* Multi-segment-reader handle */
         2225  +  sqlite3_int64 *piDocid,         /* OUT: Docid value */
         2226  +  char **paPoslist,               /* OUT: Pointer to position list */
         2227  +  int *pnPoslist                  /* OUT: Size of position list in bytes */
         2228  +){
         2229  +  int rc = SQLITE_OK;
         2230  +  int nMerge = pMsr->nAdvance;
         2231  +  Fts3SegReader **apSegment = pMsr->apSegment;
         2232  +
         2233  +  if( nMerge==0 ){
         2234  +    *paPoslist = 0;
         2235  +    return SQLITE_OK;
         2236  +  }
         2237  +
         2238  +  while( 1 ){
         2239  +    Fts3SegReader *pSeg;
         2240  +    fts3SegReaderSort(pMsr->apSegment, nMerge, nMerge, fts3SegReaderDoclistCmp);
         2241  +    pSeg = pMsr->apSegment[0];
         2242  +
         2243  +    if( pSeg->pOffsetList==0 ){
         2244  +      *paPoslist = 0;
         2245  +      break;
         2246  +    }else{
         2247  +      char *pList;
         2248  +      int nList;
         2249  +      int j;
         2250  +      sqlite3_int64 iDocid = apSegment[0]->iDocid;
         2251  +
         2252  +      fts3SegReaderNextDocid(apSegment[0], &pList, &nList);
         2253  +      j = 1;
         2254  +      while( j<nMerge
         2255  +        && apSegment[j]->pOffsetList
         2256  +        && apSegment[j]->iDocid==iDocid
         2257  +      ){
         2258  +        fts3SegReaderNextDocid(apSegment[j], 0, 0);
         2259  +      }
         2260  +
         2261  +      if( pMsr->iColFilter>=0 ){
         2262  +        fts3ColumnFilter(pMsr->iColFilter, &pList, &nList);
         2263  +      }
         2264  +
         2265  +      if( nList>0 ){
         2266  +        *piDocid = iDocid;
         2267  +        *paPoslist = pList;
         2268  +        *pnPoslist = nList;
         2269  +        break;
         2270  +      }
         2271  +    }
         2272  +  }
         2273  +
         2274  +  return rc;
         2275  +}
  2142   2276   
  2143   2277   int sqlite3Fts3SegReaderStart(
  2144   2278     Fts3Table *p,                   /* Virtual table handle */
  2145         -  Fts3SegReaderCursor *pCsr,      /* Cursor object */
         2279  +  Fts3MultiSegReader *pCsr,       /* Cursor object */
  2146   2280     Fts3SegFilter *pFilter          /* Restrictions on range of iteration */
  2147   2281   ){
  2148   2282     int i;
  2149   2283   
  2150   2284     /* Initialize the cursor object */
  2151   2285     pCsr->pFilter = pFilter;
  2152   2286   
................................................................................
  2169   2303         pCsr->apSegment, pCsr->nSegment, pCsr->nSegment, fts3SegReaderCmp);
  2170   2304   
  2171   2305     return SQLITE_OK;
  2172   2306   }
  2173   2307   
  2174   2308   int sqlite3Fts3SegReaderStep(
  2175   2309     Fts3Table *p,                   /* Virtual table handle */
  2176         -  Fts3SegReaderCursor *pCsr       /* Cursor object */
         2310  +  Fts3MultiSegReader *pCsr        /* Cursor object */
  2177   2311   ){
  2178   2312     int rc = SQLITE_OK;
  2179   2313   
  2180   2314     int isIgnoreEmpty =  (pCsr->pFilter->flags & FTS3_SEGMENT_IGNORE_EMPTY);
  2181   2315     int isRequirePos =   (pCsr->pFilter->flags & FTS3_SEGMENT_REQUIRE_POS);
  2182   2316     int isColFilter =    (pCsr->pFilter->flags & FTS3_SEGMENT_COLUMN_FILTER);
  2183   2317     int isPrefix =       (pCsr->pFilter->flags & FTS3_SEGMENT_PREFIX);
................................................................................
  2303   2437         }
  2304   2438       }
  2305   2439       pCsr->nAdvance = nMerge;
  2306   2440     }while( rc==SQLITE_OK );
  2307   2441   
  2308   2442     return rc;
  2309   2443   }
         2444  +
  2310   2445   
  2311   2446   void sqlite3Fts3SegReaderFinish(
  2312         -  Fts3SegReaderCursor *pCsr       /* Cursor object */
         2447  +  Fts3MultiSegReader *pCsr       /* Cursor object */
  2313   2448   ){
  2314   2449     if( pCsr ){
  2315   2450       int i;
  2316   2451       for(i=0; i<pCsr->nSegment; i++){
  2317   2452         sqlite3Fts3SegReaderFree(pCsr->apSegment[i]);
  2318   2453       }
  2319   2454       sqlite3_free(pCsr->apSegment);
................................................................................
  2338   2473   */
  2339   2474   static int fts3SegmentMerge(Fts3Table *p, int iIndex, int iLevel){
  2340   2475     int rc;                         /* Return code */
  2341   2476     int iIdx = 0;                   /* Index of new segment */
  2342   2477     int iNewLevel = 0;              /* Level/index to create new segment at */
  2343   2478     SegmentWriter *pWriter = 0;     /* Used to write the new, merged, segment */
  2344   2479     Fts3SegFilter filter;           /* Segment term filter condition */
  2345         -  Fts3SegReaderCursor csr;        /* Cursor to iterate through level(s) */
         2480  +  Fts3MultiSegReader csr;        /* Cursor to iterate through level(s) */
  2346   2481     int bIgnoreEmpty = 0;           /* True to ignore empty segments */
  2347   2482   
  2348   2483     assert( iLevel==FTS3_SEGCURSOR_ALL
  2349   2484          || iLevel==FTS3_SEGCURSOR_PENDING
  2350   2485          || iLevel>=0
  2351   2486     );
  2352   2487     assert( iLevel<FTS3_SEGDIR_MAXLEVEL );
................................................................................
  2741   2876           rc = fts3PendingListAppendVarint(&pDef->pList, 0);
  2742   2877         }
  2743   2878       }
  2744   2879     }
  2745   2880   
  2746   2881     return rc;
  2747   2882   }
         2883  +
         2884  +int sqlite3Fts3DeferredTokenList(
         2885  +  Fts3DeferredToken *p, 
         2886  +  char **ppData, 
         2887  +  int *pnData
         2888  +){
         2889  +  char *pRet;
         2890  +  int nSkip;
         2891  +  sqlite3_int64 dummy;
         2892  +
         2893  +  *ppData = 0;
         2894  +  *pnData = 0;
         2895  +
         2896  +  if( p->pList==0 ){
         2897  +    return SQLITE_OK;
         2898  +  }
         2899  +
         2900  +  pRet = (char *)sqlite3_malloc(p->pList->nData);
         2901  +  if( !pRet ) return SQLITE_NOMEM;
         2902  +
         2903  +  nSkip = sqlite3Fts3GetVarint(p->pList->aData, &dummy);
         2904  +  *pnData = p->pList->nData - nSkip;
         2905  +  *ppData = pRet;
         2906  +  
         2907  +  memcpy(pRet, &p->pList->aData[nSkip], *pnData);
         2908  +  return SQLITE_OK;
         2909  +}
  2748   2910   
  2749   2911   /*
  2750   2912   ** Add an entry for token pToken to the pCsr->pDeferred list.
  2751   2913   */
  2752   2914   int sqlite3Fts3DeferToken(
  2753   2915     Fts3Cursor *pCsr,               /* Fts3 table cursor */
  2754   2916     Fts3PhraseToken *pToken,        /* Token to defer */

Changes to test/fts3defer.test.

    16     16   ifcapable !fts3 {
    17     17     finish_test
    18     18     return
    19     19   }
    20     20   
    21     21   set sqlite_fts3_enable_parentheses 1
    22     22   
           23  +set fts3_simple_deferred_tokens_only 1
           24  +
    23     25   set ::testprefix fts3defer
    24     26   
    25     27   #--------------------------------------------------------------------------
    26     28   # Test cases fts3defer-1.* are the "warm body" cases. The database contains
    27     29   # one row with 15000 instances of the token "a". This makes the doclist for
    28     30   # "a" so large that FTS3 will avoid loading it in most cases.
    29     31   #
................................................................................
   253    255   
   254    256     do_select_test 1.1 {
   255    257       SELECT rowid FROM t1 WHERE t1 MATCH 'jk xnxhf'
   256    258     } {13 29 40 47 48 52 63 92}
   257    259     do_select_test 1.2 {
   258    260       SELECT rowid FROM t1 WHERE t1 MATCH 'jk eh'
   259    261     } {100}
   260         -if {$tn==3} breakpoint
   261    262     do_select_test 1.3 {
   262    263       SELECT rowid FROM t1 WHERE t1 MATCH 'jk ubwrfqnbjf'
   263    264     } {7 70 98}
   264    265     do_select_test 1.4 {
   265    266       SELECT rowid FROM t1 WHERE t1 MATCH 'duszemmzl jk'
   266    267     } {3 5 8 10 13 18 20 23 32 37 41 43 55 60 65 67 72 74 76 81 94 96 97}
   267    268     do_select_test 1.5 {
................................................................................
   278    279     } {68 100}
   279    280     do_select_test 1.9 {
   280    281       SELECT rowid FROM t1 WHERE t1 MATCH 'zm ubwrfqnbjf'
   281    282     } {7 70 98}
   282    283     do_select_test 1.10 {
   283    284       SELECT rowid FROM t1 WHERE t1 MATCH 'z* vgsld'
   284    285     } {10 13 17 31 35 51 58 88 89 90 93 100}
   285         -  do_select_test 1.11 {
   286         -    SELECT rowid FROM t1 
   287         -    WHERE t1 MATCH '(
   288         -      zdu OR zexh OR zf OR zhbrzadb OR zidhxhbtv OR 
   289         -      zk OR zkhdvkw OR zm OR zsmhnf
   290         -    ) vgsld'
   291         -  } {10 13 17 31 35 51 58 88 89 90 93 100}
          286  +
          287  +  if { $fts3_simple_deferred_tokens_only==0 } {
          288  +    do_select_test 1.11 {
          289  +      SELECT rowid FROM t1 
          290  +      WHERE t1 MATCH '(
          291  +        zdu OR zexh OR zf OR zhbrzadb OR zidhxhbtv OR 
          292  +        zk OR zkhdvkw OR zm OR zsmhnf
          293  +      ) vgsld'
          294  +    } {10 13 17 31 35 51 58 88 89 90 93 100}
          295  +  }
   292    296   
   293    297     do_select_test 2.1 {
   294    298       SELECT rowid FROM t1 WHERE t1 MATCH '"zm agmckuiu"'
   295    299     } {3 24 52 53}
   296    300     do_select_test 2.2 {
   297    301       SELECT rowid FROM t1 WHERE t1 MATCH '"zm zf"'
   298    302     } {33 53 75 88 101}
................................................................................
   360    364     # The following block of tests runs normally with FTS3 or FTS4 without the
   361    365     # long doclists zeroed. And with OOM-injection for FTS4 with long doclists
   362    366     # zeroed. Change this by messing with the [set dmt_modes] commands above.
   363    367     #
   364    368     foreach DO_MALLOC_TEST $dmt_modes {
   365    369       
   366    370       # Phrase search.
          371  +    #
   367    372       do_select_test 5.$DO_MALLOC_TEST.1 {
   368    373         SELECT rowid FROM t1 WHERE t1 MATCH '"jk mjpavjuhw"'
   369    374       } {8 15 36 64 67 72}
   370    375   
   371    376       # Multiple tokens search.
   372    377       do_select_test 5.$DO_MALLOC_TEST.2 {
   373    378         SELECT rowid FROM t1 WHERE t1 MATCH 'duszemmzl zm'
................................................................................
   412    417     } {10}
   413    418     do_select_test 6.2.1 {
   414    419       SELECT rowid FROM t1 WHERE t1 MATCH '"jk xduvfhk"'
   415    420     } {8}
   416    421     do_select_test 6.2.2 {
   417    422       SELECT rowid FROM t1 WHERE t1 MATCH '"zm azavwm"'
   418    423     } {15 26 92 96}
   419         -  do_select_test 6.2.3 {
   420         -    SELECT rowid FROM t1 WHERE t1 MATCH '"jk xduvfhk" OR "zm azavwm"'
   421         -  } {8 15 26 92 96}
          424  +  if {$fts3_simple_deferred_tokens_only==0} {
          425  +    do_select_test 6.2.3 {
          426  +      SELECT rowid FROM t1 WHERE t1 MATCH '"jk xduvfhk" OR "zm azavwm"'
          427  +    } {8 15 26 92 96}
          428  +  }
   422    429   }
   423    430   
   424    431   set testprefix fts3defer
   425    432   
   426    433   do_execsql_test 3.1 {
   427    434     CREATE VIRTUAL TABLE x1 USING fts4(a, b);
   428    435     INSERT INTO x1 VALUES('a b c', 'd e f');

Changes to test/permutations.test.

   175    175   } -files {
   176    176     fts3aa.test fts3ab.test fts3ac.test fts3ad.test fts3ae.test
   177    177     fts3af.test fts3ag.test fts3ah.test fts3ai.test fts3aj.test
   178    178     fts3ak.test fts3al.test fts3am.test fts3an.test fts3ao.test
   179    179     fts3atoken.test fts3b.test fts3c.test fts3cov.test fts3d.test
   180    180     fts3defer.test fts3defer2.test fts3e.test fts3expr.test fts3expr2.test 
   181    181     fts3near.test fts3query.test fts3shared.test fts3snippet.test 
          182  +  fts3sort.test
   182    183   
   183    184     fts3fault.test fts3malloc.test fts3matchinfo.test
   184    185   
   185    186     fts3aux1.test fts3comp1.test
   186    187   }
   187    188   
   188    189