/ Check-in [f6a0193f]
Login

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

Overview
Comment:Allow the "order=DESC" and "order=ASC" parameters in FTS4 "CREATE VIRTUAL TABLE" statements. Tables created with "order=DESC" store all doclists in descending order, which allows optimizations normally applied to "ORDER BY docid ASC" queries to be used with "ORDER BY docid DESC" queries instead.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | fts3-prefix-search
Files: files | file ages | folders
SHA1: f6a0193f5a32603eb48bddc6297042dbd2ffe96e
User & Date: dan 2011-06-04 20:04:35
Context
2011-06-04
20:13
Remove some unreachable code. check-in: 650e1a79 user: dan tags: fts3-prefix-search
20:04
Allow the "order=DESC" and "order=ASC" parameters in FTS4 "CREATE VIRTUAL TABLE" statements. Tables created with "order=DESC" store all doclists in descending order, which allows optimizations normally applied to "ORDER BY docid ASC" queries to be used with "ORDER BY docid DESC" queries instead. check-in: f6a0193f user: dan tags: fts3-prefix-search
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
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to ext/fts3/fts3.c.

   419    419     *pVal += iVal;
   420    420   }
   421    421   
   422    422   /*
   423    423   ** When this function is called, *pp points to the first byte following a
   424    424   ** varint that is part of a doclist (or position-list, or any other list
   425    425   ** of varints). This function moves *pp to point to the start of that varint,
   426         -** and decrements the value stored in *pVal by the varint value.
          426  +** and sets *pVal by the varint value.
   427    427   **
   428    428   ** Argument pStart points to the first byte of the doclist that the
   429    429   ** varint is part of.
   430    430   */
   431         -static void fts3GetReverseDeltaVarint(
          431  +static void fts3GetReverseVarint(
   432    432     char **pp, 
   433    433     char *pStart, 
   434    434     sqlite3_int64 *pVal
   435    435   ){
   436    436     sqlite3_int64 iVal;
   437    437     char *p = *pp;
   438    438   
................................................................................
   440    440     ** interested in. So, unless the doclist is corrupt, the 0x80 bit is
   441    441     ** clear on character p[-1]. */
   442    442     for(p = (*pp)-2; p>=pStart && *p&0x80; p--);
   443    443     p++;
   444    444     *pp = p;
   445    445   
   446    446     sqlite3Fts3GetVarint(p, &iVal);
   447         -  *pVal -= iVal;
          447  +  *pVal = iVal;
   448    448   }
   449    449   
   450    450   /*
   451    451   ** As long as *pp has not reached its end (pEnd), then do the same
   452    452   ** as fts3GetDeltaVarint(): read a single varint and add it to *pVal.
   453    453   ** But if we have reached the end of the varint, just set *pp=0 and
   454    454   ** leave *pVal unchanged.
................................................................................
   912    912     int iCol;                       /* Column index */
   913    913     int nString = 0;                /* Bytes required to hold all column names */
   914    914     int nCol = 0;                   /* Number of columns in the FTS table */
   915    915     char *zCsr;                     /* Space for holding column names */
   916    916     int nDb;                        /* Bytes required to hold database name */
   917    917     int nName;                      /* Bytes required to hold table name */
   918    918     int isFts4 = (argv[0][3]=='4'); /* True for FTS4, false for FTS3 */
   919         -  int bNoDocsize = 0;             /* True to omit %_docsize table */
   920    919     const char **aCol;              /* Array of column names */
   921    920     sqlite3_tokenizer *pTokenizer = 0;        /* Tokenizer for this table */
   922    921   
   923         -  char *zPrefix = 0;              /* Prefix parameter value (or NULL) */
   924    922     int nIndex;                     /* Size of aIndex[] array */
   925    923     struct Fts3Index *aIndex;       /* Array of indexes for this table */
   926    924     struct Fts3Index *aFree = 0;    /* Free this before returning */
   927    925   
   928         -  char *zCompress = 0;
   929         -  char *zUncompress = 0;
          926  +  int bNoDocsize = 0;             /* True to omit %_docsize table */
          927  +  int bDescIdx = 0;               /* True to store descending indexes */
          928  +
          929  +  char *zMatchinfo = 0;           /* Prefix parameter value (or NULL) */
          930  +  char *zPrefix = 0;              /* Prefix parameter value (or NULL) */
          931  +  char *zCompress = 0;            /* compress=? parameter (or NULL) */
          932  +  char *zUncompress = 0;          /* uncompress=? parameter (or NULL) */
          933  +  char *zOrder = 0;               /* order=? parameter (or NULL) */
          934  +  struct Fts4Option {
          935  +    const char *zOpt;
          936  +    int nOpt;
          937  +    char **pzVar;
          938  +  } aFts4Opt[] = {
          939  +    { "matchinfo",   9, 0 },
          940  +    { "prefix",      6, 0 },
          941  +    { "compress",    8, 0 },
          942  +    { "uncompress", 10, 0 },
          943  +    { "order",       5, 0 }
          944  +  };
          945  +  aFts4Opt[0].pzVar = &zMatchinfo;
          946  +  aFts4Opt[1].pzVar = &zPrefix;
          947  +  aFts4Opt[2].pzVar = &zCompress;
          948  +  aFts4Opt[3].pzVar = &zUncompress;
          949  +  aFts4Opt[4].pzVar = &zOrder;
   930    950   
   931    951     assert( strlen(argv[0])==4 );
   932    952     assert( (sqlite3_strnicmp(argv[0], "fts4", 4)==0 && isFts4)
   933    953          || (sqlite3_strnicmp(argv[0], "fts3", 4)==0 && !isFts4)
   934    954     );
   935    955   
   936    956     nDb = (int)strlen(argv[1]) + 1;
................................................................................
   963    983        && 0==sqlite3Fts3IsIdChar(z[8])
   964    984       ){
   965    985         rc = sqlite3Fts3InitTokenizer(pHash, &z[9], &pTokenizer, pzErr);
   966    986       }
   967    987   
   968    988       /* Check if it is an FTS4 special argument. */
   969    989       else if( isFts4 && fts3IsSpecialColumn(z, &nKey, &zVal) ){
          990  +      int iOpt;
   970    991         if( !zVal ){
   971    992           rc = SQLITE_NOMEM;
   972         -        goto fts3_init_out;
   973         -      }
   974         -      if( nKey==9 && 0==sqlite3_strnicmp(z, "matchinfo", 9) ){
   975         -        if( strlen(zVal)==4 && 0==sqlite3_strnicmp(zVal, "fts3", 4) ){
   976         -          bNoDocsize = 1;
   977         -        }else{
   978         -          *pzErr = sqlite3_mprintf("unrecognized matchinfo: %s", zVal);
          993  +      }else{
          994  +        for(iOpt=0; iOpt<SizeofArray(aFts4Opt); iOpt++){
          995  +          if( nKey==aFts4Opt[iOpt].nOpt 
          996  +           && !sqlite3_strnicmp(z, aFts4Opt[iOpt].zOpt, aFts4Opt[iOpt].nOpt) 
          997  +          ){
          998  +            char **pzVar = aFts4Opt[iOpt].pzVar;
          999  +            sqlite3_free(*pzVar);
         1000  +            *pzVar = zVal;
         1001  +            zVal = 0;
         1002  +            break;
         1003  +          }
         1004  +        }
         1005  +        if( zVal ){
         1006  +          *pzErr = sqlite3_mprintf("unrecognized parameter: %s", z);
   979   1007             rc = SQLITE_ERROR;
         1008  +          sqlite3_free(zVal);
   980   1009           }
   981         -      }else if( nKey==8 && 0==sqlite3_strnicmp(z, "compress", 8) ){
   982         -        zCompress = zVal;
   983         -        zVal = 0;
   984         -      }else if( nKey==10 && 0==sqlite3_strnicmp(z, "uncompress", 10) ){
   985         -        zUncompress = zVal;
   986         -        zVal = 0;
   987         -      }else if( nKey==6 && 0==sqlite3_strnicmp(z, "prefix", 6) ){
   988         -        sqlite3_free(zPrefix);
   989         -        zPrefix = zVal;
   990         -        zVal = 0;
   991         -      }else{
   992         -        *pzErr = sqlite3_mprintf("unrecognized parameter: %s", z);
   993         -        rc = SQLITE_ERROR;
   994   1010         }
   995         -      sqlite3_free(zVal);
   996   1011       }
   997   1012   
   998   1013       /* Otherwise, the argument is a column name. */
   999   1014       else {
  1000   1015         nString += (int)(strlen(z) + 1);
  1001   1016         aCol[nCol++] = z;
  1002   1017       }
................................................................................
  1005   1020   
  1006   1021     if( nCol==0 ){
  1007   1022       assert( nString==0 );
  1008   1023       aCol[0] = "content";
  1009   1024       nString = 8;
  1010   1025       nCol = 1;
  1011   1026     }
         1027  +
         1028  +  if( zMatchinfo ){
         1029  +    if( strlen(zMatchinfo)!=4 || sqlite3_strnicmp(zMatchinfo, "fts3", 4) ){
         1030  +      *pzErr = sqlite3_mprintf("unrecognized matchinfo: %s", zMatchinfo);
         1031  +      rc = SQLITE_ERROR;
         1032  +      goto fts3_init_out;
         1033  +    }
         1034  +    bNoDocsize = 1;
         1035  +  }
         1036  +
         1037  +  if( zOrder ){
         1038  +    if( (strlen(zOrder)!=3 || sqlite3_strnicmp(zOrder, "asc", 3)) 
         1039  +     && (strlen(zOrder)!=4 || sqlite3_strnicmp(zOrder, "desc", 3)) 
         1040  +    ){
         1041  +      *pzErr = sqlite3_mprintf("unrecognized order: %s", zOrder);
         1042  +      rc = SQLITE_ERROR;
         1043  +      goto fts3_init_out;
         1044  +    }
         1045  +    bDescIdx = (zOrder[0]=='d' || zOrder[0]=='D');
         1046  +  }
  1012   1047   
  1013   1048     if( pTokenizer==0 ){
  1014   1049       rc = sqlite3Fts3InitTokenizer(pHash, "simple", &pTokenizer, pzErr);
  1015   1050       if( rc!=SQLITE_OK ) goto fts3_init_out;
  1016   1051     }
  1017   1052     assert( pTokenizer );
  1018   1053   
................................................................................
  1042   1077     p->nPendingData = 0;
  1043   1078     p->azColumn = (char **)&p[1];
  1044   1079     p->pTokenizer = pTokenizer;
  1045   1080     p->nNodeSize = 1000;
  1046   1081     p->nMaxPendingData = FTS3_MAX_PENDING_DATA;
  1047   1082     p->bHasDocsize = (isFts4 && bNoDocsize==0);
  1048   1083     p->bHasStat = isFts4;
         1084  +  p->bDescIdx = bDescIdx;
  1049   1085     TESTONLY( p->inTransaction = -1 );
  1050   1086     TESTONLY( p->mxSavepoint = -1 );
  1051   1087   
  1052   1088     p->aIndex = (struct Fts3Index *)&p->azColumn[nCol];
  1053   1089     memcpy(p->aIndex, aIndex, sizeof(struct Fts3Index) * nIndex);
  1054   1090     p->nIndex = nIndex;
  1055   1091     for(i=0; i<nIndex; i++){
................................................................................
  1104   1140     fts3DeclareVtab(&rc, p);
  1105   1141   
  1106   1142   fts3_init_out:
  1107   1143     sqlite3_free(zPrefix);
  1108   1144     sqlite3_free(aFree);
  1109   1145     sqlite3_free(zCompress);
  1110   1146     sqlite3_free(zUncompress);
         1147  +  sqlite3_free(zOrder);
         1148  +  sqlite3_free(zMatchinfo);
  1111   1149     sqlite3_free((void *)aCol);
  1112   1150     if( rc!=SQLITE_OK ){
  1113   1151       if( p ){
  1114   1152         fts3DisconnectMethod((sqlite3_vtab *)p);
  1115   1153       }else if( pTokenizer ){
  1116   1154         pTokenizer->pModule->xDestroy(pTokenizer);
  1117   1155       }
................................................................................
  1876   1914   
  1877   1915   /*
  1878   1916   ** Values that may be used as the first parameter to fts3DoclistMerge().
  1879   1917   */
  1880   1918   #define MERGE_NOT        2        /* D + D -> D */
  1881   1919   #define MERGE_AND        3        /* D + D -> D */
  1882   1920   #define MERGE_OR         4        /* D + D -> D */
  1883         -#define MERGE_POS_OR     5        /* P + P -> P */
  1884   1921   #define MERGE_PHRASE     6        /* P + P -> D */
  1885         -#define MERGE_POS_PHRASE 7        /* P + P -> P */
  1886   1922   #define MERGE_NEAR       8        /* P + P -> D */
         1923  +
         1924  +#define MERGE_POS_OR     5        /* P + P -> P */
         1925  +#define MERGE_POS_PHRASE 7        /* P + P -> P */
  1887   1926   #define MERGE_POS_NEAR   9        /* P + P -> P */
  1888   1927   
  1889   1928   /*
  1890   1929   ** Merge the two doclists passed in buffer a1 (size n1 bytes) and a2
  1891   1930   ** (size n2 bytes). The output is written to pre-allocated buffer aBuffer,
  1892   1931   ** which is guaranteed to be large enough to hold the results. The number
  1893   1932   ** of bytes written to aBuffer is stored in *pnBuffer before returning.
................................................................................
  1920   1959     int nDoc = 0;
  1921   1960   
  1922   1961     assert( mergetype==MERGE_OR     || mergetype==MERGE_POS_OR 
  1923   1962          || mergetype==MERGE_AND    || mergetype==MERGE_NOT
  1924   1963          || mergetype==MERGE_PHRASE || mergetype==MERGE_POS_PHRASE
  1925   1964          || mergetype==MERGE_NEAR   || mergetype==MERGE_POS_NEAR
  1926   1965     );
         1966  +  assert( mergetype==MERGE_POS_PHRASE || mergetype==MERGE_POS_NEAR );
  1927   1967   
  1928   1968     if( !aBuffer ){
  1929   1969       *pnBuffer = 0;
  1930   1970       return SQLITE_NOMEM;
  1931   1971     }
  1932   1972   
  1933   1973     /* Read the first docid from each doclist */
................................................................................
  2060   2100   */
  2061   2101   typedef struct TermSelect TermSelect;
  2062   2102   struct TermSelect {
  2063   2103     int isReqPos;
  2064   2104     char *aaOutput[16];             /* Malloc'd output buffer */
  2065   2105     int anOutput[16];               /* Size of output in bytes */
  2066   2106   };
         2107  +
         2108  +
         2109  +static void fts3GetDeltaVarint3(
         2110  +  char **pp, 
         2111  +  char *pEnd, 
         2112  +  int bDescIdx,
         2113  +  sqlite3_int64 *pVal
         2114  +){
         2115  +  if( *pp>=pEnd ){
         2116  +    *pp = 0;
         2117  +  }else{
         2118  +    sqlite3_int64 iVal;
         2119  +    *pp += sqlite3Fts3GetVarint(*pp, &iVal);
         2120  +    if( bDescIdx ){
         2121  +      *pVal -= iVal;
         2122  +    }else{
         2123  +      *pVal += iVal;
         2124  +    }
         2125  +  }
         2126  +}
         2127  +
         2128  +static void fts3PutDeltaVarint3(
         2129  +  char **pp,                      /* IN/OUT: Output pointer */
         2130  +  int bDescIdx,                   /* True for descending docids */
         2131  +  sqlite3_int64 *piPrev,          /* IN/OUT: Previous value written to list */
         2132  +  int *pbFirst,                   /* IN/OUT: True after first int written */
         2133  +  sqlite3_int64 iVal              /* Write this value to the list */
         2134  +){
         2135  +  sqlite3_int64 iWrite;
         2136  +  if( bDescIdx==0 || *pbFirst==0 ){
         2137  +    iWrite = iVal - *piPrev;
         2138  +  }else{
         2139  +    iWrite = *piPrev - iVal;
         2140  +  }
         2141  +  assert( *pbFirst || *piPrev==0 );
         2142  +  assert( *pbFirst==0 || iWrite>0 );
         2143  +  *pp += sqlite3Fts3PutVarint(*pp, iWrite);
         2144  +  *piPrev = iVal;
         2145  +  *pbFirst = 1;
         2146  +}
         2147  +
         2148  +#define COMPARE_DOCID(i1, i2) ((bDescIdx?-1:1) * (i1-i2))
         2149  +
         2150  +static int fts3DoclistOrMerge(
         2151  +  int bDescIdx,                   /* True if arguments are desc */
         2152  +  u8 *a1, int n1,                 /* First doclist */
         2153  +  u8 *a2, int n2,                 /* Second doclist */
         2154  +  u8 **paOut, int *pnOut          /* OUT: Malloc'd doclist */
         2155  +){
         2156  +  sqlite3_int64 i1 = 0;
         2157  +  sqlite3_int64 i2 = 0;
         2158  +  sqlite3_int64 iPrev = 0;
         2159  +  char *pEnd1 = &a1[n1];
         2160  +  char *pEnd2 = &a2[n2];
         2161  +  char *p1 = a1;
         2162  +  char *p2 = a2;
         2163  +  char *p;
         2164  +  int nOut;
         2165  +  char *aOut;
         2166  +  int bFirstOut = 0;
         2167  +
         2168  +  *paOut = 0;
         2169  +  *pnOut = 0;
         2170  +  aOut = sqlite3_malloc(n1+n2);
         2171  +  if( !aOut ) return SQLITE_NOMEM;
         2172  +
         2173  +  p = aOut;
         2174  +  fts3GetDeltaVarint3(&p1, pEnd1, 0, &i1);
         2175  +  fts3GetDeltaVarint3(&p2, pEnd2, 0, &i2);
         2176  +  while( p1 || p2 ){
         2177  +    sqlite3_int64 iDiff = COMPARE_DOCID(i1, i2);
         2178  +
         2179  +    if( p2 && p1 && iDiff==0 ){
         2180  +      fts3PutDeltaVarint3(&p, bDescIdx, &iPrev, &bFirstOut, i1);
         2181  +      fts3PoslistMerge(&p, &p1, &p2);
         2182  +      fts3GetDeltaVarint3(&p1, pEnd1, bDescIdx, &i1);
         2183  +      fts3GetDeltaVarint3(&p2, pEnd2, bDescIdx, &i2);
         2184  +    }else if( !p2 || (p1 && iDiff<0) ){
         2185  +      fts3PutDeltaVarint3(&p, bDescIdx, &iPrev, &bFirstOut, i1);
         2186  +      fts3PoslistCopy(&p, &p1);
         2187  +      fts3GetDeltaVarint3(&p1, pEnd1, bDescIdx, &i1);
         2188  +    }else{
         2189  +      fts3PutDeltaVarint3(&p, bDescIdx, &iPrev, &bFirstOut, i2);
         2190  +      fts3PoslistCopy(&p, &p2);
         2191  +      fts3GetDeltaVarint3(&p2, pEnd2, bDescIdx, &i2);
         2192  +    }
         2193  +  }
         2194  +
         2195  +  *paOut = aOut;
         2196  +  *pnOut = (p-aOut);
         2197  +  return SQLITE_OK;
         2198  +}
         2199  +
         2200  +static void fts3DoclistPhraseMerge(
         2201  +  int bDescIdx,                   /* True if arguments are desc */
         2202  +  int nDist,                      /* Distance from left to right (1=adjacent) */
         2203  +  u8 *aLeft, int nLeft,           /* Left doclist */
         2204  +  u8 *aRight, int *pnRight        /* IN/OUT: Right/output doclist */
         2205  +){
         2206  +  sqlite3_int64 i1 = 0;
         2207  +  sqlite3_int64 i2 = 0;
         2208  +  sqlite3_int64 iPrev = 0;
         2209  +  char *pEnd1 = &aLeft[nLeft];
         2210  +  char *pEnd2 = &aRight[*pnRight];
         2211  +  char *p1 = aLeft;
         2212  +  char *p2 = aRight;
         2213  +  char *p;
         2214  +  int bFirstOut = 0;
         2215  +  char *aOut = aRight;
         2216  +
         2217  +  assert( nDist>0 );
         2218  +
         2219  +  p = aOut;
         2220  +  fts3GetDeltaVarint3(&p1, pEnd1, 0, &i1);
         2221  +  fts3GetDeltaVarint3(&p2, pEnd2, 0, &i2);
         2222  +
         2223  +  while( p1 && p2 ){
         2224  +    sqlite3_int64 iDiff = COMPARE_DOCID(i1, i2);
         2225  +    if( iDiff==0 ){
         2226  +      char *pSave = p;
         2227  +      sqlite3_int64 iPrevSave = iPrev;
         2228  +      int bFirstOutSave = bFirstOut;
         2229  +
         2230  +      fts3PutDeltaVarint3(&p, bDescIdx, &iPrev, &bFirstOut, i1);
         2231  +      if( 0==fts3PoslistPhraseMerge(&p, nDist, 0, 1, &p1, &p2) ){
         2232  +        p = pSave;
         2233  +        iPrev = iPrevSave;
         2234  +        bFirstOut = bFirstOutSave;
         2235  +      }
         2236  +      fts3GetDeltaVarint3(&p1, pEnd1, bDescIdx, &i1);
         2237  +      fts3GetDeltaVarint3(&p2, pEnd2, bDescIdx, &i2);
         2238  +    }else if( iDiff<0 ){
         2239  +      fts3PoslistCopy(0, &p1);
         2240  +      fts3GetDeltaVarint3(&p1, pEnd1, bDescIdx, &i1);
         2241  +    }else{
         2242  +      fts3PoslistCopy(0, &p2);
         2243  +      fts3GetDeltaVarint3(&p2, pEnd2, bDescIdx, &i2);
         2244  +    }
         2245  +  }
         2246  +
         2247  +  *pnRight = p - aOut;
         2248  +}
         2249  +
         2250  +/*
         2251  +** This function merges two doclists according to the requirements of a
         2252  +** NEAR operator.
         2253  +*/
         2254  +static int fts3DoclistNearMerge(
         2255  +  int bDescIdx,
         2256  +  int mergetype,                  /* MERGE_POS_NEAR or MERGE_NEAR */
         2257  +  int nNear,                      /* Parameter to NEAR operator */
         2258  +  int nTokenLeft,                 /* Number of tokens in LHS phrase arg */
         2259  +  char *aLeft,                    /* Doclist for LHS (incl. positions) */
         2260  +  int nLeft,                      /* Size of LHS doclist in bytes */
         2261  +  int nTokenRight,                /* As nTokenLeft */
         2262  +  char *aRight,                   /* As aLeft */
         2263  +  int nRight,                     /* As nRight */
         2264  +  char **paOut,                   /* OUT: Results of merge (malloced) */
         2265  +  int *pnOut                      /* OUT: Sized of output buffer */
         2266  +){
         2267  +  char *aOut;                     /* Buffer to write output doclist to */
         2268  +  char *aTmp;                     /* Temp buffer used by PoslistNearMerge() */
         2269  +
         2270  +  sqlite3_int64 i1 = 0;
         2271  +  sqlite3_int64 i2 = 0;
         2272  +  sqlite3_int64 iPrev = 0;
         2273  +  int bFirstOut = 0;
         2274  +
         2275  +  char *pEnd1 = &aLeft[nLeft];
         2276  +  char *pEnd2 = &aRight[nRight];
         2277  +  char *p1 = aLeft;
         2278  +  char *p2 = aRight;
         2279  +  char *p;
         2280  +
         2281  +  int nParam1 = nNear+nTokenRight;
         2282  +  int nParam2 = nNear+nTokenLeft;
         2283  +
         2284  +  p = aOut = sqlite3_malloc(nLeft+nRight+1);
         2285  +  aTmp = sqlite3_malloc(2*(nLeft+nRight+1));
         2286  +  if( !aOut || !aTmp ){
         2287  +    sqlite3_free(aOut);
         2288  +    sqlite3_free(aTmp);
         2289  +    *paOut = 0;
         2290  +    *pnOut = 0;
         2291  +    return SQLITE_NOMEM;
         2292  +  }
         2293  +
         2294  +  fts3GetDeltaVarint3(&p1, pEnd1, 0, &i1);
         2295  +  fts3GetDeltaVarint3(&p2, pEnd2, 0, &i2);
         2296  +
         2297  +  while( p1 && p2 ){
         2298  +    sqlite3_int64 iDiff = COMPARE_DOCID(i1, i2);
         2299  +    if( iDiff==0 ){
         2300  +      char *pSave = p;
         2301  +      sqlite3_int64 iPrevSave = iPrev;
         2302  +      int bFirstOutSave = bFirstOut;
         2303  +      fts3PutDeltaVarint3(&p, bDescIdx, &iPrev, &bFirstOut, i1);
         2304  +      if( !fts3PoslistNearMerge(&p, aTmp, nParam1, nParam2, &p1, &p2) ){
         2305  +        p = pSave;
         2306  +        iPrev = iPrevSave;
         2307  +        bFirstOut = bFirstOutSave;
         2308  +      }
         2309  +
         2310  +      fts3GetDeltaVarint3(&p1, pEnd1, bDescIdx, &i1);
         2311  +      fts3GetDeltaVarint3(&p2, pEnd2, bDescIdx, &i2);
         2312  +    }else if( iDiff<0 ){
         2313  +      fts3PoslistCopy(0, &p1);
         2314  +      fts3GetDeltaVarint3(&p1, pEnd1, bDescIdx, &i1);
         2315  +    }else{
         2316  +      fts3PoslistCopy(0, &p2);
         2317  +      fts3GetDeltaVarint3(&p2, pEnd2, bDescIdx, &i2);
         2318  +    }
         2319  +  }
         2320  +
         2321  +  sqlite3_free(aTmp);
         2322  +  *paOut = aOut;
         2323  +  *pnOut = p - aOut;
         2324  +  return SQLITE_OK;
         2325  +}
         2326  +
         2327  +
  2067   2328   
  2068   2329   /*
  2069   2330   ** Merge all doclists in the TermSelect.aaOutput[] array into a single
  2070   2331   ** doclist stored in TermSelect.aaOutput[0]. If successful, delete all
  2071   2332   ** other doclists (except the aaOutput[0] one) and return SQLITE_OK.
  2072   2333   **
  2073   2334   ** If an OOM error occurs, return SQLITE_NOMEM. In this case it is
  2074   2335   ** the responsibility of the caller to free any doclists left in the
  2075   2336   ** TermSelect.aaOutput[] array.
  2076   2337   */
  2077         -static int fts3TermSelectMerge(TermSelect *pTS){
         2338  +static int fts3TermSelectMerge(Fts3Table *p, TermSelect *pTS){
  2078   2339     int mergetype = (pTS->isReqPos ? MERGE_POS_OR : MERGE_OR);
  2079   2340     char *aOut = 0;
  2080   2341     int nOut = 0;
  2081   2342     int i;
  2082   2343   
  2083   2344     /* Loop through the doclists in the aaOutput[] array. Merge them all
  2084   2345     ** into a single doclist.
................................................................................
  2086   2347     for(i=0; i<SizeofArray(pTS->aaOutput); i++){
  2087   2348       if( pTS->aaOutput[i] ){
  2088   2349         if( !aOut ){
  2089   2350           aOut = pTS->aaOutput[i];
  2090   2351           nOut = pTS->anOutput[i];
  2091   2352           pTS->aaOutput[i] = 0;
  2092   2353         }else{
  2093         -        int nNew = nOut + pTS->anOutput[i];
  2094         -        char *aNew = sqlite3_malloc(nNew);
  2095         -        if( !aNew ){
         2354  +        int nNew;
         2355  +        u8 *aNew;
         2356  +
         2357  +        int rc = fts3DoclistOrMerge(p->bDescIdx, 
         2358  +            pTS->aaOutput[i], pTS->anOutput[i], aOut, nOut, &aNew, &nNew
         2359  +        );
         2360  +        if( rc!=SQLITE_OK ){
  2096   2361             sqlite3_free(aOut);
  2097         -          return SQLITE_NOMEM;
         2362  +          return rc;
  2098   2363           }
  2099         -        fts3DoclistMerge(mergetype, 0, 0,
  2100         -            aNew, &nNew, pTS->aaOutput[i], pTS->anOutput[i], aOut, nOut, 0
  2101         -        );
         2364  +
  2102   2365           sqlite3_free(pTS->aaOutput[i]);
  2103   2366           sqlite3_free(aOut);
  2104   2367           pTS->aaOutput[i] = 0;
  2105   2368           aOut = aNew;
  2106   2369           nOut = nNew;
  2107   2370         }
  2108   2371       }
................................................................................
  2130   2393   
  2131   2394     UNUSED_PARAMETER(p);
  2132   2395     UNUSED_PARAMETER(zTerm);
  2133   2396     UNUSED_PARAMETER(nTerm);
  2134   2397   
  2135   2398     if( pTS->aaOutput[0]==0 ){
  2136   2399       /* If this is the first term selected, copy the doclist to the output
  2137         -    ** buffer using memcpy(). TODO: Add a way to transfer control of the
  2138         -    ** aDoclist buffer from the caller so as to avoid the memcpy().
  2139         -    */
         2400  +    ** buffer using memcpy(). */
  2140   2401       pTS->aaOutput[0] = sqlite3_malloc(nDoclist);
  2141   2402       pTS->anOutput[0] = nDoclist;
  2142   2403       if( pTS->aaOutput[0] ){
  2143   2404         memcpy(pTS->aaOutput[0], aDoclist, nDoclist);
  2144   2405       }else{
  2145   2406         return SQLITE_NOMEM;
  2146   2407       }
................................................................................
  2147   2408     }else{
  2148   2409       int mergetype = (pTS->isReqPos ? MERGE_POS_OR : MERGE_OR);
  2149   2410       char *aMerge = aDoclist;
  2150   2411       int nMerge = nDoclist;
  2151   2412       int iOut;
  2152   2413   
  2153   2414       for(iOut=0; iOut<SizeofArray(pTS->aaOutput); iOut++){
  2154         -      char *aNew;
  2155         -      int nNew;
  2156   2415         if( pTS->aaOutput[iOut]==0 ){
  2157   2416           assert( iOut>0 );
  2158   2417           pTS->aaOutput[iOut] = aMerge;
  2159   2418           pTS->anOutput[iOut] = nMerge;
  2160   2419           break;
  2161         -      }
  2162         -
  2163         -      nNew = nMerge + pTS->anOutput[iOut];
  2164         -      aNew = sqlite3_malloc(nNew);
  2165         -      if( !aNew ){
  2166         -        if( aMerge!=aDoclist ){
  2167         -          sqlite3_free(aMerge);
  2168         -        }
  2169         -        return SQLITE_NOMEM;
  2170         -      }
  2171         -      fts3DoclistMerge(mergetype, 0, 0, aNew, &nNew, 
  2172         -          pTS->aaOutput[iOut], pTS->anOutput[iOut], aMerge, nMerge, 0
  2173         -      );
  2174         -
  2175         -      if( iOut>0 ) sqlite3_free(aMerge);
  2176         -      sqlite3_free(pTS->aaOutput[iOut]);
  2177         -      pTS->aaOutput[iOut] = 0;
  2178         -
  2179         -      aMerge = aNew;
  2180         -      nMerge = nNew;
  2181         -      if( (iOut+1)==SizeofArray(pTS->aaOutput) ){
  2182         -        pTS->aaOutput[iOut] = aMerge;
  2183         -        pTS->anOutput[iOut] = nMerge;
         2420  +      }else{
         2421  +        u8 *aNew;
         2422  +        int nNew;
         2423  +
         2424  +        int rc = fts3DoclistOrMerge(p->bDescIdx, aMerge, nMerge, 
         2425  +            pTS->aaOutput[iOut], pTS->anOutput[iOut], &aNew, &nNew
         2426  +        );
         2427  +        if( rc!=SQLITE_OK ){
         2428  +          if( aMerge!=aDoclist ) sqlite3_free(aMerge);
         2429  +          return rc;
         2430  +        }
         2431  +
         2432  +        if( aMerge!=aDoclist ) sqlite3_free(aMerge);
         2433  +        sqlite3_free(pTS->aaOutput[iOut]);
         2434  +        pTS->aaOutput[iOut] = 0;
         2435  +  
         2436  +        aMerge = aNew;
         2437  +        nMerge = nNew;
         2438  +        if( (iOut+1)==SizeofArray(pTS->aaOutput) ){
         2439  +          pTS->aaOutput[iOut] = aMerge;
         2440  +          pTS->anOutput[iOut] = nMerge;
         2441  +        }
  2184   2442         }
  2185   2443       }
  2186   2444     }
  2187   2445     return SQLITE_OK;
  2188   2446   }
  2189   2447   
  2190   2448   /*
................................................................................
  2422   2680     ){
  2423   2681       rc = fts3TermSelectCb(p, (void *)&tsc, 
  2424   2682           pSegcsr->zTerm, pSegcsr->nTerm, pSegcsr->aDoclist, pSegcsr->nDoclist
  2425   2683       );
  2426   2684     }
  2427   2685   
  2428   2686     if( rc==SQLITE_OK ){
  2429         -    rc = fts3TermSelectMerge(&tsc);
         2687  +    rc = fts3TermSelectMerge(p, &tsc);
  2430   2688     }
  2431   2689     if( rc==SQLITE_OK ){
  2432   2690       *ppOut = tsc.aaOutput[0];
  2433   2691       *pnOut = tsc.anOutput[0];
  2434   2692     }else{
  2435   2693       int i;
  2436   2694       for(i=0; i<SizeofArray(tsc.aaOutput); i++){
................................................................................
  2472   2730         }
  2473   2731       }
  2474   2732     }
  2475   2733   
  2476   2734     return nDoc;
  2477   2735   }
  2478   2736   
  2479         -/*
  2480         -** This function merges two doclists according to the requirements of a
  2481         -** NEAR operator.
  2482         -**
  2483         -** Both input doclists must include position information. The output doclist 
  2484         -** includes position information if the first argument to this function
  2485         -** is MERGE_POS_NEAR, or does not if it is MERGE_NEAR.
  2486         -*/
  2487         -static int fts3NearMerge(
  2488         -  int mergetype,                  /* MERGE_POS_NEAR or MERGE_NEAR */
  2489         -  int nNear,                      /* Parameter to NEAR operator */
  2490         -  int nTokenLeft,                 /* Number of tokens in LHS phrase arg */
  2491         -  char *aLeft,                    /* Doclist for LHS (incl. positions) */
  2492         -  int nLeft,                      /* Size of LHS doclist in bytes */
  2493         -  int nTokenRight,                /* As nTokenLeft */
  2494         -  char *aRight,                   /* As aLeft */
  2495         -  int nRight,                     /* As nRight */
  2496         -  char **paOut,                   /* OUT: Results of merge (malloced) */
  2497         -  int *pnOut                      /* OUT: Sized of output buffer */
  2498         -){
  2499         -  char *aOut;                     /* Buffer to write output doclist to */
  2500         -  int rc;                         /* Return code */
  2501         -
  2502         -  assert( mergetype==MERGE_POS_NEAR || MERGE_NEAR );
  2503         -
  2504         -  aOut = sqlite3_malloc(nLeft+nRight+1);
  2505         -  if( aOut==0 ){
  2506         -    rc = SQLITE_NOMEM;
  2507         -  }else{
  2508         -    rc = fts3DoclistMerge(mergetype, nNear+nTokenRight, nNear+nTokenLeft, 
  2509         -      aOut, pnOut, aLeft, nLeft, aRight, nRight, 0
  2510         -    );
  2511         -    if( rc!=SQLITE_OK ){
  2512         -      sqlite3_free(aOut);
  2513         -      aOut = 0;
  2514         -    }
  2515         -  }
  2516         -
  2517         -  *paOut = aOut;
  2518         -  return rc;
  2519         -}
  2520         -
  2521   2737   /*
  2522   2738   ** Advance the cursor to the next row in the %_content table that
  2523   2739   ** matches the search criteria.  For a MATCH search, this will be
  2524   2740   ** the next row that matches. For a full-table scan, this will be
  2525   2741   ** simply the next row in the %_content table.  For a docid lookup,
  2526   2742   ** this routine simply sets the EOF flag.
  2527   2743   **
................................................................................
  2584   2800   
  2585   2801     /* In case the cursor has been used before, clear it now. */
  2586   2802     sqlite3_finalize(pCsr->pStmt);
  2587   2803     sqlite3_free(pCsr->aDoclist);
  2588   2804     sqlite3Fts3ExprFree(pCsr->pExpr);
  2589   2805     memset(&pCursor[1], 0, sizeof(Fts3Cursor)-sizeof(sqlite3_vtab_cursor));
  2590   2806   
  2591         -  pCsr->bDesc = (idxStr && idxStr[0]=='D');
         2807  +  if( idxStr ){
         2808  +    pCsr->bDesc = (idxStr[0]=='D');
         2809  +  }else{
         2810  +    pCsr->bDesc = p->bDescIdx;
         2811  +  }
  2592   2812     pCsr->eSearch = (i16)idxNum;
  2593   2813   
  2594   2814     if( idxNum!=FTS3_DOCID_SEARCH && idxNum!=FTS3_FULLSCAN_SEARCH ){
  2595   2815       int iCol = idxNum-FTS3_FULLTEXT_SEARCH;
  2596   2816       const char *zQuery = (const char *)sqlite3_value_text(apVal[0]);
  2597   2817   
  2598   2818       if( zQuery==0 && sqlite3_value_type(apVal[0])!=SQLITE_NULL ){
................................................................................
  2623   2843   
  2624   2844     /* Compile a SELECT statement for this cursor. For a full-table-scan, the
  2625   2845     ** statement loops through all rows of the %_content table. For a
  2626   2846     ** full-text query or docid lookup, the statement retrieves a single
  2627   2847     ** row by docid.
  2628   2848     */
  2629   2849     if( idxNum==FTS3_FULLSCAN_SEARCH ){
  2630         -    const char *zSort = (idxStr ? idxStr : "ASC");
         2850  +    const char *zSort = (pCsr->bDesc ? "DESC" : "ASC");
  2631   2851       const char *zTmpl = "SELECT %s FROM %Q.'%q_content' AS x ORDER BY docid %s";
  2632   2852       zSql = sqlite3_mprintf(zTmpl, p->zReadExprlist, p->zDb, p->zName, zSort);
  2633   2853     }else{
  2634   2854       const char *zTmpl = "SELECT %s FROM %Q.'%q_content' AS x WHERE docid = ?";
  2635   2855       zSql = sqlite3_mprintf(zTmpl, p->zReadExprlist, p->zDb, p->zName);
  2636   2856     }
  2637   2857     if( !zSql ) return SQLITE_NOMEM;
................................................................................
  3261   3481             nDoclist = 0;
  3262   3482             break;
  3263   3483           }else if( aDoclist==0 ){
  3264   3484             aDoclist = pThis;
  3265   3485             nDoclist = nThis;
  3266   3486           }else{
  3267   3487             assert( iPrev>=0 );
  3268         -          fts3DoclistMerge(MERGE_POS_PHRASE, iToken-iPrev, 
  3269         -              0, pThis, &nThis, aDoclist, nDoclist, pThis, nThis, 0
         3488  +          fts3DoclistPhraseMerge(pTab->bDescIdx,
         3489  +              iToken-iPrev, aDoclist, nDoclist, pThis, &nThis
  3270   3490             );
  3271   3491             sqlite3_free(aDoclist);
  3272   3492             aDoclist = pThis;
  3273   3493             nDoclist = nThis;
  3274   3494           }
  3275   3495           iPrev = iToken;
  3276   3496         }
................................................................................
  3407   3627   ** function has been called successfully on an Fts3Phrase, it may be
  3408   3628   ** used with fts3EvalPhraseNext() to iterate through the matching docids.
  3409   3629   */
  3410   3630   static int fts3EvalPhraseStart(Fts3Cursor *pCsr, int bOptOk, Fts3Phrase *p){
  3411   3631     int rc;
  3412   3632     Fts3Doclist *pList = &p->doclist;
  3413   3633     Fts3PhraseToken *pFirst = &p->aToken[0];
         3634  +  Fts3Table *pTab = (Fts3Table *)pCsr->base.pVtab;
  3414   3635   
  3415   3636     assert( pList->aAll==0 );
  3416   3637   
  3417         -  if( pCsr->bDesc==0 && bOptOk==1 && p->nToken==1 
         3638  +  if( pCsr->bDesc==pTab->bDescIdx && bOptOk==1 && p->nToken==1 
  3418   3639      && pFirst->pSegcsr && pFirst->pSegcsr->bLookup 
  3419   3640     ){
  3420   3641       /* Use the incremental approach. */
  3421         -    Fts3Table *pTab = (Fts3Table *)pCsr->base.pVtab;
  3422   3642       int iCol = (p->iColumn >= pTab->nColumn ? -1 : p->iColumn);
  3423   3643       rc = sqlite3Fts3MsrIncrStart(
  3424   3644           pTab, pFirst->pSegcsr, iCol, pFirst->z, pFirst->n);
  3425   3645       p->bIncr = 1;
  3426   3646   
  3427   3647     }else{
  3428   3648       /* Load the full doclist for the phrase into memory. */
................................................................................
  3429   3649       rc = fts3EvalPhraseLoad(pCsr, p);
  3430   3650       p->bIncr = 0;
  3431   3651     }
  3432   3652   
  3433   3653     assert( rc!=SQLITE_OK || p->nToken<1 || p->aToken[0].pSegcsr==0 || p->bIncr );
  3434   3654     return rc;
  3435   3655   }
         3656  +
         3657  +void sqlite3Fts3DoclistPrev(
         3658  +  int bDescIdx,                   /* True if the doclist is desc */
         3659  +  char *aDoclist,                 /* Pointer to entire doclist */
         3660  +  int nDoclist,                   /* Length of aDoclist in bytes */
         3661  +  char **ppIter,                  /* IN/OUT: Iterator pointer */
         3662  +  sqlite3_int64 *piDocid,         /* IN/OUT: Docid pointer */
         3663  +  int *pnList,                    /* IN/OUT: List length pointer */
         3664  +  u8 *pbEof                       /* OUT: End-of-file flag */
         3665  +){
         3666  +  char *p = *ppIter;
         3667  +  int iMul = (bDescIdx ? -1 : 1);
         3668  +
         3669  +  assert( *pbEof==0 );
         3670  +  assert( p || *piDocid==0 );
         3671  +  assert( !p || (p>aDoclist && p<&aDoclist[nDoclist]) );
         3672  +
         3673  +  if( p==0 ){
         3674  +    sqlite3_int64 iDocid = 0;
         3675  +    char *pNext = 0;
         3676  +    char *pDocid = aDoclist;
         3677  +    char *pEnd = &aDoclist[nDoclist];
         3678  +
         3679  +    pDocid += sqlite3Fts3GetVarint(pDocid, &iDocid);
         3680  +    pNext = pDocid;
         3681  +    fts3PoslistCopy(0, &pDocid);
         3682  +    while( pDocid<pEnd ){
         3683  +      sqlite3_int64 iDelta;
         3684  +      pDocid += sqlite3Fts3GetVarint(pDocid, &iDelta);
         3685  +      iDocid += (iMul * iDelta);
         3686  +      pNext = pDocid;
         3687  +      fts3PoslistCopy(0, &pDocid);
         3688  +    }
         3689  +
         3690  +    *pnList = pEnd - pNext;
         3691  +    *ppIter = pNext;
         3692  +    *piDocid = iDocid;
         3693  +  }else{
         3694  +    sqlite3_int64 iDelta;
         3695  +    fts3GetReverseVarint(&p, aDoclist, &iDelta);
         3696  +    *piDocid -= (iMul * iDelta);
         3697  +
         3698  +    if( p==aDoclist ){
         3699  +      *pbEof = 1;
         3700  +    }else{
         3701  +      char *pSave = p;
         3702  +      fts3ReversePoslist(aDoclist, &p);
         3703  +      *pnList = (pSave - p);
         3704  +    }
         3705  +    *ppIter = p;
         3706  +  }
         3707  +}
  3436   3708   
  3437   3709   /*
  3438   3710   ** Attempt to move the phrase iterator to point to the next matching docid. 
  3439   3711   ** If an error occurs, return an SQLite error code. Otherwise, return 
  3440   3712   ** SQLITE_OK.
  3441   3713   **
  3442   3714   ** If there is no "next" entry and no error occurs, then *pbEof is set to
................................................................................
  3446   3718   static int fts3EvalPhraseNext(
  3447   3719     Fts3Cursor *pCsr, 
  3448   3720     Fts3Phrase *p, 
  3449   3721     u8 *pbEof
  3450   3722   ){
  3451   3723     int rc = SQLITE_OK;
  3452   3724     Fts3Doclist *pDL = &p->doclist;
         3725  +  Fts3Table *pTab = (Fts3Table *)pCsr->base.pVtab;
  3453   3726   
  3454   3727     if( p->bIncr ){
  3455         -    Fts3Table *pTab = (Fts3Table *)pCsr->base.pVtab;
  3456   3728       assert( p->nToken==1 );
  3457   3729       rc = sqlite3Fts3MsrIncrNext(pTab, p->aToken[0].pSegcsr, 
  3458   3730           &pDL->iDocid, &pDL->pList, &pDL->nList
  3459   3731       );
  3460   3732       if( rc==SQLITE_OK && !pDL->pList ){
  3461   3733         *pbEof = 1;
  3462   3734       }
  3463         -  }else if( pCsr->bDesc && pDL->aAll ){
  3464         -
  3465         -    if( pDL->pNextDocid==0 ){
  3466         -      sqlite3_int64 iDocid = 0;
  3467         -      char *pNext;
  3468         -      char *pDocid = pDL->aAll;
  3469         -      char *pEnd = &pDocid[pDL->nAll];
  3470         -
  3471         -      while( pDocid<pEnd ){
  3472         -        fts3GetDeltaVarint(&pDocid, &iDocid);
  3473         -        pDL->pNextDocid = pDocid;
  3474         -        pDL->pList = pDocid;
  3475         -        fts3PoslistCopy(0, &pDocid);
  3476         -      }
  3477         -      pDL->nList = (pEnd - pDL->pList);
  3478         -      pDL->iDocid = iDocid;
  3479         -    }else{
  3480         -
  3481         -      assert( *pbEof==0 );
  3482         -      assert( pDL->pNextDocid>pDL->aAll );
  3483         -
  3484         -      fts3GetReverseDeltaVarint(
  3485         -          &pDL->pNextDocid, pDL->aAll, &pDL->iDocid
  3486         -      );
  3487         -      if( pDL->pNextDocid==pDL->aAll ){
  3488         -        *pbEof = 1;
  3489         -      }else{
  3490         -        char *pSave = pDL->pNextDocid;
  3491         -        fts3ReversePoslist(pDL->aAll, &pDL->pNextDocid);
  3492         -        pDL->pList = pDL->pNextDocid;
  3493         -        pDL->nList = pSave - pDL->pNextDocid;
  3494         -      }
  3495         -    }
  3496         -
         3735  +  }else if( pCsr->bDesc!=pTab->bDescIdx && pDL->aAll ){
         3736  +    sqlite3Fts3DoclistPrev(pTab->bDescIdx, pDL->aAll, pDL->nAll, 
         3737  +        &pDL->pNextDocid, &pDL->iDocid, &pDL->nList, pbEof
         3738  +    );
         3739  +    pDL->pList = pDL->pNextDocid;
  3497   3740     }else{
  3498         -
  3499   3741       char *pIter;
  3500   3742       if( pDL->pNextDocid ){
  3501   3743         pIter = pDL->pNextDocid;
  3502   3744       }else{
  3503   3745         pIter = pDL->aAll;
  3504   3746       }
  3505   3747   
  3506   3748       if( pIter>=&pDL->aAll[pDL->nAll] ){
  3507   3749         /* We have already reached the end of this doclist. EOF. */
  3508   3750         *pbEof = 1;
  3509   3751       }else{
  3510         -      fts3GetDeltaVarint(&pIter, &pDL->iDocid);
         3752  +      sqlite3_int64 iDelta;
         3753  +      pIter += sqlite3Fts3GetVarint(pIter, &iDelta);
         3754  +      if( pTab->bDescIdx==0 || pDL->pNextDocid==0 ){
         3755  +        pDL->iDocid += iDelta;
         3756  +      }else{
         3757  +        pDL->iDocid -= iDelta;
         3758  +      }
  3511   3759         pDL->pList = pIter;
  3512   3760         fts3PoslistCopy(0, &pIter);
  3513   3761         pDL->nList = (pIter - pDL->pList);
  3514   3762         pDL->pNextDocid = pIter;
  3515   3763         *pbEof = 0;
  3516   3764       }
  3517   3765     }
................................................................................
  3542   3790         fts3EvalStartReaders(pCsr, pExpr->pRight, bOptOk, pRc);
  3543   3791         pExpr->bDeferred = (pExpr->pLeft->bDeferred && pExpr->pRight->bDeferred);
  3544   3792       }
  3545   3793     }
  3546   3794   }
  3547   3795   
  3548   3796   static void fts3EvalNearMerge(
         3797  +  int bDescIdx,
  3549   3798     Fts3Expr *p1,
  3550   3799     Fts3Expr *p2,
  3551   3800     int nNear,
  3552   3801     int *pRc
  3553   3802   ){
  3554   3803     if( *pRc==SQLITE_OK ){
  3555   3804       int rc;                         /* Return code */
................................................................................
  3563   3812         sqlite3_free(pRight->doclist.aAll);
  3564   3813         pRight->doclist.aAll = 0;
  3565   3814         pRight->doclist.nAll = 0;
  3566   3815       }else if( pRight->doclist.aAll ){
  3567   3816         char *aOut;                 /* Buffer in which to assemble new doclist */
  3568   3817         int nOut;                   /* Size of buffer aOut in bytes */
  3569   3818     
  3570         -      *pRc = fts3NearMerge(MERGE_POS_NEAR, nNear, 
         3819  +      *pRc = fts3DoclistNearMerge(bDescIdx, MERGE_POS_NEAR, nNear, 
  3571   3820             pLeft->nToken, pLeft->doclist.aAll, pLeft->doclist.nAll,
  3572   3821             pRight->nToken, pRight->doclist.aAll, pRight->doclist.nAll,
  3573   3822             &aOut, &nOut
  3574   3823         );
  3575   3824         sqlite3_free(pRight->doclist.aAll);
  3576   3825         pRight->doclist.aAll = aOut;
  3577   3826         pRight->doclist.nAll = nOut;
................................................................................
  3598   3847           nPhrase++;
  3599   3848         }
  3600   3849   
  3601   3850         aPhrase = (Fts3Expr **)sqlite3_malloc(sizeof(Fts3Expr *) * nPhrase);
  3602   3851         if( !aPhrase ){
  3603   3852           *pRc = SQLITE_NOMEM;
  3604   3853         }else{
         3854  +        Fts3Table *p = (Fts3Table *)pCsr->base.pVtab;
  3605   3855           int i = 1;
  3606   3856           aPhrase[0] = pLeft;
  3607   3857           do {
  3608   3858             pLeft = pLeft->pParent;
  3609   3859             aPhrase[i++] = pLeft->pRight;
  3610   3860           }while( pLeft!=pExpr );
  3611   3861   
  3612   3862           for(i=0; i<(nPhrase-1); i++){
  3613   3863             int nNear = aPhrase[i+1]->pParent->nNear;
  3614         -          fts3EvalNearMerge(aPhrase[i], aPhrase[i+1], nNear, pRc);
         3864  +          fts3EvalNearMerge(p->bDescIdx, aPhrase[i], aPhrase[i+1], nNear, pRc);
  3615   3865           }
  3616   3866           for(i=nPhrase-2; i>=0; i--){
  3617   3867             int nNear = aPhrase[i+1]->pParent->nNear;
  3618         -          fts3EvalNearMerge(aPhrase[i+1], aPhrase[i], nNear, pRc);
         3868  +          fts3EvalNearMerge(p->bDescIdx, aPhrase[i+1], aPhrase[i], nNear, pRc);
  3619   3869           }
  3620   3870   
  3621   3871           sqlite3_free(aPhrase);
  3622   3872         }
  3623   3873   
  3624   3874       }else{
  3625   3875         fts3EvalNearTrim(pCsr, pExpr->pLeft, pRc);

Changes to ext/fts3/fts3Int.h.

   176    176   
   177    177     char *zReadExprlist;
   178    178     char *zWriteExprlist;
   179    179   
   180    180     int nNodeSize;                  /* Soft limit for node size */
   181    181     u8 bHasStat;                    /* True if %_stat table exists */
   182    182     u8 bHasDocsize;                 /* True if %_docsize table exists */
          183  +  u8 bDescIdx;                    /* True if doclists are in reverse order */
   183    184     int nPgsz;                      /* Page size for host database */
   184    185     char *zSegmentsTbl;             /* Name of %_segments table */
   185    186     sqlite3_blob *pSegments;        /* Blob handle open on %_segments table */
   186    187   
   187    188     /* TODO: Fix the first paragraph of this comment.
   188    189     **
   189    190     ** The following hash table is used to buffer pending index updates during
................................................................................
   232    233     Fts3Expr *pExpr;                /* Parsed MATCH query string */
   233    234     int nPhrase;                    /* Number of matchable phrases in query */
   234    235     Fts3DeferredToken *pDeferred;   /* Deferred search tokens, if any */
   235    236     sqlite3_int64 iPrevId;          /* Previous id read from aDoclist */
   236    237     char *pNextId;                  /* Pointer into the body of aDoclist */
   237    238     char *aDoclist;                 /* List of docids for full-text queries */
   238    239     int nDoclist;                   /* Size of buffer at aDoclist */
   239         -  int bDesc;                      /* True to sort in descending order */
          240  +  u8 bDesc;                       /* True to sort in descending order */
   240    241     int eEvalmode;                  /* An FTS3_EVAL_XX constant */
   241    242     int nRowAvg;                    /* Average size of database rows, in pages */
   242    243   
   243    244     int isMatchinfoNeeded;          /* True when aMatchinfo[] needs filling in */
   244    245     u32 *aMatchinfo;                /* Information about most recent match */
   245    246     int nMatchinfo;                 /* Number of elements in aMatchinfo[] */
   246    247     char *zMatchinfo;               /* Matchinfo specification */
................................................................................
   434    435   
   435    436   /* fts3.c */
   436    437   int sqlite3Fts3PutVarint(char *, sqlite3_int64);
   437    438   int sqlite3Fts3GetVarint(const char *, sqlite_int64 *);
   438    439   int sqlite3Fts3GetVarint32(const char *, int *);
   439    440   int sqlite3Fts3VarintLen(sqlite3_uint64);
   440    441   void sqlite3Fts3Dequote(char *);
          442  +void sqlite3Fts3DoclistPrev(int,char*,int,char**,sqlite3_int64*,int*,u8*);
   441    443   
   442    444   int sqlite3Fts3ExprLoadDoclist(Fts3Cursor *, Fts3Expr *);
   443    445   int sqlite3Fts3ExprNearTrim(Fts3Expr *, Fts3Expr *, int);
   444    446   
   445    447   /* fts3_tokenizer.c */
   446    448   const char *sqlite3Fts3NextToken(const char *, int *);
   447    449   int sqlite3Fts3InitHashTable(sqlite3 *, Fts3Hash *, const char *);
................................................................................
   490    492       Fts3Table*, Fts3MultiSegReader*, int, const char*, int);
   491    493   int sqlite3Fts3MsrIncrNext(
   492    494       Fts3Table *, Fts3MultiSegReader *, sqlite3_int64 *, char **, int *);
   493    495   char *sqlite3Fts3EvalPhrasePoslist(Fts3Cursor *, Fts3Expr *, int iCol); 
   494    496   int sqlite3Fts3MsrOvfl(Fts3Cursor *, Fts3MultiSegReader *, int *);
   495    497   
   496    498   int sqlite3Fts3DeferredTokenList(Fts3DeferredToken *, char **, int *);
          499  +
   497    500   
   498    501   #endif /* _FTSINT_H */

Changes to ext/fts3/fts3_write.c.

    58     58   /* #define FTS3_NODE_CHUNK_THRESHOLD 1 */
    59     59   
    60     60   typedef struct PendingList PendingList;
    61     61   typedef struct SegmentNode SegmentNode;
    62     62   typedef struct SegmentWriter SegmentWriter;
    63     63   
    64     64   /*
    65         -** Data structure used while accumulating terms in the pending-terms hash
    66         -** table. The hash table entry maps from term (a string) to a malloc'd
    67         -** instance of this structure.
           65  +** An instance of the following data structure is used to build doclists
           66  +** incrementally. See function fts3PendingListAppend() for details.
    68     67   */
    69     68   struct PendingList {
    70     69     int nData;
    71     70     char *aData;
    72     71     int nSpace;
    73     72     sqlite3_int64 iLastDocid;
    74     73     sqlite3_int64 iLastCol;
................................................................................
   126    125     */
   127    126     int nTerm;                      /* Number of bytes in current term */
   128    127     char *zTerm;                    /* Pointer to current term */
   129    128     int nTermAlloc;                 /* Allocated size of zTerm buffer */
   130    129     char *aDoclist;                 /* Pointer to doclist of current entry */
   131    130     int nDoclist;                   /* Size of doclist in current entry */
   132    131   
   133         -  /* The following variables are used to iterate through the current doclist */
          132  +  /* The following variables are used by fts3SegReaderNextDocid() to iterate 
          133  +  ** through the current doclist (aDoclist/nDoclist).
          134  +  */
   134    135     char *pOffsetList;
          136  +  int nOffsetList;                /* For descending pending seg-readers only */
   135    137     sqlite3_int64 iDocid;
   136    138   };
   137    139   
   138    140   #define fts3SegReaderIsPending(p) ((p)->ppNextElem!=0)
   139    141   #define fts3SegReaderIsRootOnly(p) ((p)->aNode==(char *)&(p)[1])
   140    142   
   141    143   /*
................................................................................
   569    571     if( p!=*pp ){
   570    572       *pp = p;
   571    573       return 1;
   572    574     }
   573    575     return 0;
   574    576   }
   575    577   
          578  +/*
          579  +** Free a PendingList object allocated by fts3PendingListAppend().
          580  +*/
          581  +static void fts3PendingListDelete(PendingList *pList){
          582  +  sqlite3_free(pList);
          583  +}
          584  +
          585  +/*
          586  +** Add an entry to one of the pending-terms hash tables.
          587  +*/
   576    588   static int fts3PendingTermsAddOne(
   577    589     Fts3Table *p,
   578    590     int iCol,
   579    591     int iPos,
   580         -  Fts3Hash *pHash,
          592  +  Fts3Hash *pHash,                /* Pending terms hash table to add entry to */
   581    593     const char *zToken,
   582    594     int nToken
   583    595   ){
   584    596     PendingList *pList;
   585    597     int rc = SQLITE_OK;
   586    598   
   587    599     pList = (PendingList *)fts3HashFind(pHash, zToken, nToken);
................................................................................
   709    721   */
   710    722   void sqlite3Fts3PendingTermsClear(Fts3Table *p){
   711    723     int i;
   712    724     for(i=0; i<p->nIndex; i++){
   713    725       Fts3HashElem *pElem;
   714    726       Fts3Hash *pHash = &p->aIndex[i].hPending;
   715    727       for(pElem=fts3HashFirst(pHash); pElem; pElem=fts3HashNext(pElem)){
   716         -      sqlite3_free(fts3HashData(pElem));
          728  +      PendingList *pList = (PendingList *)fts3HashData(pElem);
          729  +      fts3PendingListDelete(pList);
   717    730       }
   718    731       fts3HashClear(pHash);
   719    732     }
   720    733     p->nPendingData = 0;
   721    734   }
   722    735   
   723    736   /*
................................................................................
  1110   1123       assert( pReader->pBlob==0 );
  1111   1124       if( bIncr && pReader->nPopulate<pReader->nNode ){
  1112   1125         pReader->pBlob = p->pSegments;
  1113   1126         p->pSegments = 0;
  1114   1127       }
  1115   1128       pNext = pReader->aNode;
  1116   1129     }
         1130  +
         1131  +  assert( !fts3SegReaderIsPending(pReader) );
  1117   1132   
  1118   1133     rc = fts3SegReaderRequire(pReader, pNext, FTS3_VARINT_MAX*2);
  1119   1134     if( rc!=SQLITE_OK ) return rc;
  1120   1135     
  1121   1136     /* Because of the FTS3_NODE_PADDING bytes of padding, the following is 
  1122         -  ** safe (no risk of overread) even if the node data is corrupted.  
  1123         -  */
         1137  +  ** safe (no risk of overread) even if the node data is corrupted. */
  1124   1138     pNext += sqlite3Fts3GetVarint32(pNext, &nPrefix);
  1125   1139     pNext += sqlite3Fts3GetVarint32(pNext, &nSuffix);
  1126   1140     if( nPrefix<0 || nSuffix<=0 
  1127   1141      || &pNext[nSuffix]>&pReader->aNode[pReader->nNode] 
  1128   1142     ){
  1129   1143       return SQLITE_CORRUPT_VTAB;
  1130   1144     }
................................................................................
  1161   1175     return SQLITE_OK;
  1162   1176   }
  1163   1177   
  1164   1178   /*
  1165   1179   ** Set the SegReader to point to the first docid in the doclist associated
  1166   1180   ** with the current term.
  1167   1181   */
  1168         -static int fts3SegReaderFirstDocid(Fts3SegReader *pReader){
  1169         -  int rc;
         1182  +static int fts3SegReaderFirstDocid(Fts3Table *pTab, Fts3SegReader *pReader){
         1183  +  int rc = SQLITE_OK;
  1170   1184     assert( pReader->aDoclist );
  1171   1185     assert( !pReader->pOffsetList );
  1172         -  rc = fts3SegReaderRequire(pReader, pReader->aDoclist, FTS3_VARINT_MAX);
  1173         -  if( rc==SQLITE_OK ){
  1174         -    int n = sqlite3Fts3GetVarint(pReader->aDoclist, &pReader->iDocid);
  1175         -    pReader->pOffsetList = &pReader->aDoclist[n];
         1186  +  if( pTab->bDescIdx && fts3SegReaderIsPending(pReader) ){
         1187  +    u8 bEof = 0;
         1188  +    pReader->iDocid = 0;
         1189  +    pReader->nOffsetList = 0;
         1190  +    sqlite3Fts3DoclistPrev(0,
         1191  +        pReader->aDoclist, pReader->nDoclist, &pReader->pOffsetList, 
         1192  +        &pReader->iDocid, &pReader->nOffsetList, &bEof
         1193  +    );
         1194  +  }else{
         1195  +    rc = fts3SegReaderRequire(pReader, pReader->aDoclist, FTS3_VARINT_MAX);
         1196  +    if( rc==SQLITE_OK ){
         1197  +      int n = sqlite3Fts3GetVarint(pReader->aDoclist, &pReader->iDocid);
         1198  +      pReader->pOffsetList = &pReader->aDoclist[n];
         1199  +    }
  1176   1200     }
  1177   1201     return rc;
  1178   1202   }
  1179   1203   
  1180   1204   /*
  1181   1205   ** Advance the SegReader to point to the next docid in the doclist
  1182   1206   ** associated with the current term.
................................................................................
  1184   1208   ** If arguments ppOffsetList and pnOffsetList are not NULL, then 
  1185   1209   ** *ppOffsetList is set to point to the first column-offset list
  1186   1210   ** in the doclist entry (i.e. immediately past the docid varint).
  1187   1211   ** *pnOffsetList is set to the length of the set of column-offset
  1188   1212   ** lists, not including the nul-terminator byte. For example:
  1189   1213   */
  1190   1214   static int fts3SegReaderNextDocid(
  1191         -  Fts3SegReader *pReader,
  1192         -  char **ppOffsetList,
  1193         -  int *pnOffsetList
         1215  +  Fts3Table *pTab,
         1216  +  Fts3SegReader *pReader,         /* Reader to advance to next docid */
         1217  +  char **ppOffsetList,            /* OUT: Pointer to current position-list */
         1218  +  int *pnOffsetList               /* OUT: Length of *ppOffsetList in bytes */
  1194   1219   ){
  1195   1220     int rc = SQLITE_OK;
  1196   1221     char *p = pReader->pOffsetList;
  1197   1222     char c = 0;
  1198   1223   
  1199         -  /* Pointer p currently points at the first byte of an offset list. The
  1200         -  ** following two lines advance it to point one byte past the end of
  1201         -  ** the same offset list.
  1202         -  */
  1203         -  while( 1 ){
  1204         -    int nRead;
  1205         -    int rc;
  1206         -
  1207         -    while( *p | c ) c = *p++ & 0x80;
  1208         -    assert( *p==0 );
  1209         -    if( pReader->pBlob==0 || (p - pReader->aNode)!=pReader->nPopulate ) break;
  1210         -    rc = fts3SegReaderIncrRead(pReader);
  1211         -    if( rc!=SQLITE_OK ) return rc;
  1212         -  }
  1213         -  p++;
  1214         -
  1215         -  /* If required, populate the output variables with a pointer to and the
  1216         -  ** size of the previous offset-list.
  1217         -  */
  1218         -  if( ppOffsetList ){
  1219         -    *ppOffsetList = pReader->pOffsetList;
  1220         -    *pnOffsetList = (int)(p - pReader->pOffsetList - 1);
  1221         -  }
  1222         -
  1223         -  /* If there are no more entries in the doclist, set pOffsetList to
  1224         -  ** NULL. Otherwise, set Fts3SegReader.iDocid to the next docid and
  1225         -  ** Fts3SegReader.pOffsetList to point to the next offset list before
  1226         -  ** returning.
  1227         -  */
  1228         -  if( p>=&pReader->aDoclist[pReader->nDoclist] ){
  1229         -    pReader->pOffsetList = 0;
  1230         -  }else{
  1231         -    rc = fts3SegReaderRequire(pReader, p, FTS3_VARINT_MAX);
  1232         -    if( rc==SQLITE_OK ){
  1233         -      sqlite3_int64 iDelta;
  1234         -      pReader->pOffsetList = p + sqlite3Fts3GetVarint(p, &iDelta);
  1235         -      pReader->iDocid += iDelta;
         1224  +  assert( p );
         1225  +
         1226  +  if( pTab->bDescIdx && fts3SegReaderIsPending(pReader) ){
         1227  +    /* A pending-terms seg-reader for an FTS4 table that uses order=desc.
         1228  +    ** Pending-terms doclists are always built up in ascending order, so
         1229  +    ** we have to iterate through them backwards here. */
         1230  +    u8 bEof = 0;
         1231  +    if( ppOffsetList ){
         1232  +      *ppOffsetList = pReader->pOffsetList;
         1233  +      *pnOffsetList = pReader->nOffsetList - 1;
         1234  +    }
         1235  +    sqlite3Fts3DoclistPrev(0,
         1236  +        pReader->aDoclist, pReader->nDoclist, &p, &pReader->iDocid,
         1237  +        &pReader->nOffsetList, &bEof
         1238  +    );
         1239  +    if( bEof ){
         1240  +      pReader->pOffsetList = 0;
         1241  +    }else{
         1242  +      pReader->pOffsetList = p;
         1243  +    }
         1244  +  }else{
         1245  +
         1246  +    /* Pointer p currently points at the first byte of an offset list. The
         1247  +    ** following block advances it to point one byte past the end of
         1248  +    ** the same offset list. */
         1249  +    while( 1 ){
         1250  +  
         1251  +      /* The following line of code (and the "p++" below the while() loop) is
         1252  +      ** normally all that is required to move pointer p to the desired 
         1253  +      ** position. The exception is if this node is being loaded from disk
         1254  +      ** incrementally and pointer "p" now points to the first byte passed
         1255  +      ** the populated part of pReader->aNode[].
         1256  +      */
         1257  +      while( *p | c ) c = *p++ & 0x80;
         1258  +      assert( *p==0 );
         1259  +  
         1260  +      if( pReader->pBlob==0 || p<&pReader->aNode[pReader->nPopulate] ) break;
         1261  +      rc = fts3SegReaderIncrRead(pReader);
         1262  +      if( rc!=SQLITE_OK ) return rc;
         1263  +    }
         1264  +    p++;
         1265  +  
         1266  +    /* If required, populate the output variables with a pointer to and the
         1267  +    ** size of the previous offset-list.
         1268  +    */
         1269  +    if( ppOffsetList ){
         1270  +      *ppOffsetList = pReader->pOffsetList;
         1271  +      *pnOffsetList = (int)(p - pReader->pOffsetList - 1);
         1272  +    }
         1273  +  
         1274  +    /* If there are no more entries in the doclist, set pOffsetList to
         1275  +    ** NULL. Otherwise, set Fts3SegReader.iDocid to the next docid and
         1276  +    ** Fts3SegReader.pOffsetList to point to the next offset list before
         1277  +    ** returning.
         1278  +    */
         1279  +    if( p>=&pReader->aDoclist[pReader->nDoclist] ){
         1280  +      pReader->pOffsetList = 0;
         1281  +    }else{
         1282  +      rc = fts3SegReaderRequire(pReader, p, FTS3_VARINT_MAX);
         1283  +      if( rc==SQLITE_OK ){
         1284  +        sqlite3_int64 iDelta;
         1285  +        pReader->pOffsetList = p + sqlite3Fts3GetVarint(p, &iDelta);
         1286  +        if( pTab->bDescIdx ){
         1287  +          pReader->iDocid -= iDelta;
         1288  +        }else{
         1289  +          pReader->iDocid += iDelta;
         1290  +        }
         1291  +      }
  1236   1292       }
  1237   1293     }
  1238   1294   
  1239   1295     return SQLITE_OK;
  1240   1296   }
  1241   1297   
  1242   1298   /*
................................................................................
  1593   1649     int rc = (pLhs->pOffsetList==0)-(pRhs->pOffsetList==0);
  1594   1650     if( rc==0 ){
  1595   1651       if( pLhs->iDocid==pRhs->iDocid ){
  1596   1652         rc = pRhs->iIdx - pLhs->iIdx;
  1597   1653       }else{
  1598   1654         rc = (pLhs->iDocid > pRhs->iDocid) ? 1 : -1;
  1599   1655       }
         1656  +  }
         1657  +  assert( pLhs->aNode && pRhs->aNode );
         1658  +  return rc;
         1659  +}
         1660  +static int fts3SegReaderDoclistCmpRev(Fts3SegReader *pLhs, Fts3SegReader *pRhs){
         1661  +  int rc = (pLhs->pOffsetList==0)-(pRhs->pOffsetList==0);
         1662  +  if( rc==0 ){
         1663  +    if( pLhs->iDocid==pRhs->iDocid ){
         1664  +      rc = pRhs->iIdx - pLhs->iIdx;
         1665  +    }else{
         1666  +      rc = (pLhs->iDocid < pRhs->iDocid) ? 1 : -1;
         1667  +    }
  1600   1668     }
  1601   1669     assert( pLhs->aNode && pRhs->aNode );
  1602   1670     return rc;
  1603   1671   }
  1604   1672   
  1605   1673   /*
  1606   1674   ** Compare the term that the Fts3SegReader object passed as the first argument
................................................................................
  2286   2354     Fts3MultiSegReader *pCsr,       /* Cursor object */
  2287   2355     int iCol,                       /* Column to match on. */
  2288   2356     const char *zTerm,              /* Term to iterate through a doclist for */
  2289   2357     int nTerm                       /* Number of bytes in zTerm */
  2290   2358   ){
  2291   2359     int i;
  2292   2360     int nSegment = pCsr->nSegment;
         2361  +  int (*xCmp)(Fts3SegReader *, Fts3SegReader *) = (
         2362  +    p->bDescIdx ? fts3SegReaderDoclistCmpRev : fts3SegReaderDoclistCmp
         2363  +  );
  2293   2364   
  2294   2365     assert( pCsr->pFilter==0 );
  2295   2366     assert( zTerm && nTerm>0 );
  2296   2367   
  2297   2368     /* Advance each segment iterator until it points to the term zTerm/nTerm. */
  2298   2369     for(i=0; i<nSegment; i++){
  2299   2370       Fts3SegReader *pSeg = pCsr->apSegment[i];
................................................................................
  2311   2382         break;
  2312   2383       }
  2313   2384     }
  2314   2385     pCsr->nAdvance = i;
  2315   2386   
  2316   2387     /* Advance each of the segments to point to the first docid. */
  2317   2388     for(i=0; i<pCsr->nAdvance; i++){
  2318         -    int rc = fts3SegReaderFirstDocid(pCsr->apSegment[i]);
         2389  +    int rc = fts3SegReaderFirstDocid(p, pCsr->apSegment[i]);
  2319   2390       if( rc!=SQLITE_OK ) return rc;
  2320   2391     }
  2321         -  fts3SegReaderSort(pCsr->apSegment, i, i, fts3SegReaderDoclistCmp);
         2392  +  fts3SegReaderSort(pCsr->apSegment, i, i, xCmp);
  2322   2393   
  2323   2394     assert( iCol<0 || iCol<p->nColumn );
  2324   2395     pCsr->iColFilter = iCol;
  2325   2396   
  2326   2397     return SQLITE_OK;
  2327   2398   }
  2328   2399   
................................................................................
  2331   2402     Fts3MultiSegReader *pMsr,       /* Multi-segment-reader handle */
  2332   2403     sqlite3_int64 *piDocid,         /* OUT: Docid value */
  2333   2404     char **paPoslist,               /* OUT: Pointer to position list */
  2334   2405     int *pnPoslist                  /* OUT: Size of position list in bytes */
  2335   2406   ){
  2336   2407     int nMerge = pMsr->nAdvance;
  2337   2408     Fts3SegReader **apSegment = pMsr->apSegment;
         2409  +  int (*xCmp)(Fts3SegReader *, Fts3SegReader *) = (
         2410  +    p->bDescIdx ? fts3SegReaderDoclistCmpRev : fts3SegReaderDoclistCmp
         2411  +  );
  2338   2412   
  2339   2413     if( nMerge==0 ){
  2340   2414       *paPoslist = 0;
  2341   2415       return SQLITE_OK;
  2342   2416     }
  2343   2417   
  2344   2418     while( 1 ){
................................................................................
  2352   2426       }else{
  2353   2427         int rc;
  2354   2428         char *pList;
  2355   2429         int nList;
  2356   2430         int j;
  2357   2431         sqlite3_int64 iDocid = apSegment[0]->iDocid;
  2358   2432   
  2359         -      rc = fts3SegReaderNextDocid(apSegment[0], &pList, &nList);
         2433  +      rc = fts3SegReaderNextDocid(p, apSegment[0], &pList, &nList);
  2360   2434         j = 1;
  2361   2435         while( rc==SQLITE_OK 
  2362   2436           && j<nMerge
  2363   2437           && apSegment[j]->pOffsetList
  2364   2438           && apSegment[j]->iDocid==iDocid
  2365   2439         ){
  2366         -        fts3SegReaderNextDocid(apSegment[j], 0, 0);
         2440  +        rc = fts3SegReaderNextDocid(p, apSegment[j], 0, 0);
  2367   2441           j++;
  2368   2442         }
  2369   2443         if( rc!=SQLITE_OK ) return rc;
  2370         -
  2371         -      fts3SegReaderSort(pMsr->apSegment, nMerge, j, fts3SegReaderDoclistCmp);
         2444  +      fts3SegReaderSort(pMsr->apSegment, nMerge, j, xCmp);
  2372   2445   
  2373   2446         if( pMsr->iColFilter>=0 ){
  2374   2447           fts3ColumnFilter(pMsr->iColFilter, &pList, &nList);
  2375   2448         }
  2376   2449   
  2377   2450         if( nList>0 ){
  2378   2451           *piDocid = iDocid;
................................................................................
  2429   2502     int isColFilter =    (pCsr->pFilter->flags & FTS3_SEGMENT_COLUMN_FILTER);
  2430   2503     int isPrefix =       (pCsr->pFilter->flags & FTS3_SEGMENT_PREFIX);
  2431   2504     int isScan =         (pCsr->pFilter->flags & FTS3_SEGMENT_SCAN);
  2432   2505   
  2433   2506     Fts3SegReader **apSegment = pCsr->apSegment;
  2434   2507     int nSegment = pCsr->nSegment;
  2435   2508     Fts3SegFilter *pFilter = pCsr->pFilter;
         2509  +  int (*xCmp)(Fts3SegReader *, Fts3SegReader *) = (
         2510  +    p->bDescIdx ? fts3SegReaderDoclistCmpRev : fts3SegReaderDoclistCmp
         2511  +  );
  2436   2512   
  2437   2513     if( pCsr->nSegment==0 ) return SQLITE_OK;
  2438   2514   
  2439   2515     do {
  2440   2516       int nMerge;
  2441   2517       int i;
  2442   2518     
................................................................................
  2479   2555           && apSegment[nMerge]->nTerm==pCsr->nTerm 
  2480   2556           && 0==memcmp(pCsr->zTerm, apSegment[nMerge]->zTerm, pCsr->nTerm)
  2481   2557       ){
  2482   2558         nMerge++;
  2483   2559       }
  2484   2560   
  2485   2561       assert( isIgnoreEmpty || (isRequirePos && !isColFilter) );
  2486         -    if( nMerge==1 && !isIgnoreEmpty ){
         2562  +    if( nMerge==1 
         2563  +     && !isIgnoreEmpty 
         2564  +     && (p->bDescIdx==0 || fts3SegReaderIsPending(apSegment[0])==0)
         2565  +    ){
  2487   2566         pCsr->aDoclist = apSegment[0]->aDoclist;
  2488   2567         pCsr->nDoclist = apSegment[0]->nDoclist;
  2489   2568         rc = SQLITE_ROW;
  2490   2569       }else{
  2491   2570         int nDoclist = 0;           /* Size of doclist */
  2492   2571         sqlite3_int64 iPrev = 0;    /* Previous docid stored in doclist */
  2493   2572   
  2494   2573         /* The current term of the first nMerge entries in the array
  2495   2574         ** of Fts3SegReader objects is the same. The doclists must be merged
  2496   2575         ** and a single term returned with the merged doclist.
  2497   2576         */
  2498   2577         for(i=0; i<nMerge; i++){
  2499         -        fts3SegReaderFirstDocid(apSegment[i]);
         2578  +        fts3SegReaderFirstDocid(p, apSegment[i]);
  2500   2579         }
  2501         -      fts3SegReaderSort(apSegment, nMerge, nMerge, fts3SegReaderDoclistCmp);
         2580  +      fts3SegReaderSort(apSegment, nMerge, nMerge, xCmp);
  2502   2581         while( apSegment[0]->pOffsetList ){
  2503   2582           int j;                    /* Number of segments that share a docid */
  2504   2583           char *pList;
  2505   2584           int nList;
  2506   2585           int nByte;
  2507   2586           sqlite3_int64 iDocid = apSegment[0]->iDocid;
  2508         -        fts3SegReaderNextDocid(apSegment[0], &pList, &nList);
         2587  +        fts3SegReaderNextDocid(p, apSegment[0], &pList, &nList);
  2509   2588           j = 1;
  2510   2589           while( j<nMerge
  2511   2590               && apSegment[j]->pOffsetList
  2512   2591               && apSegment[j]->iDocid==iDocid
  2513   2592           ){
  2514         -          fts3SegReaderNextDocid(apSegment[j], 0, 0);
         2593  +          fts3SegReaderNextDocid(p, apSegment[j], 0, 0);
  2515   2594             j++;
  2516   2595           }
  2517   2596   
  2518   2597           if( isColFilter ){
  2519   2598             fts3ColumnFilter(pFilter->iCol, &pList, &nList);
  2520   2599           }
  2521   2600   
  2522   2601           if( !isIgnoreEmpty || nList>0 ){
  2523         -          nByte = sqlite3Fts3VarintLen(iDocid-iPrev) + (isRequirePos?nList+1:0);
         2602  +
         2603  +          /* Calculate the 'docid' delta value to write into the merged 
         2604  +          ** doclist. */
         2605  +          sqlite3_int64 iDelta;
         2606  +          if( p->bDescIdx && nDoclist>0 ){
         2607  +            iDelta = iPrev - iDocid;
         2608  +          }else{
         2609  +            iDelta = iDocid - iPrev;
         2610  +          }
         2611  +          assert( iDelta>0 || (nDoclist==0 && iDelta==iDocid) );
         2612  +          assert( nDoclist>0 || iDelta==iDocid );
         2613  +
         2614  +          nByte = sqlite3Fts3VarintLen(iDelta) + (isRequirePos?nList+1:0);
  2524   2615             if( nDoclist+nByte>pCsr->nBuffer ){
  2525   2616               char *aNew;
  2526   2617               pCsr->nBuffer = (nDoclist+nByte)*2;
  2527   2618               aNew = sqlite3_realloc(pCsr->aBuffer, pCsr->nBuffer);
  2528   2619               if( !aNew ){
  2529   2620                 return SQLITE_NOMEM;
  2530   2621               }
  2531   2622               pCsr->aBuffer = aNew;
  2532   2623             }
  2533         -          nDoclist += sqlite3Fts3PutVarint(
  2534         -              &pCsr->aBuffer[nDoclist], iDocid-iPrev
  2535         -          );
         2624  +          nDoclist += sqlite3Fts3PutVarint(&pCsr->aBuffer[nDoclist], iDelta);
  2536   2625             iPrev = iDocid;
  2537   2626             if( isRequirePos ){
  2538   2627               memcpy(&pCsr->aBuffer[nDoclist], pList, nList);
  2539   2628               nDoclist += nList;
  2540   2629               pCsr->aBuffer[nDoclist++] = '\0';
  2541   2630             }
  2542   2631           }
  2543   2632   
  2544         -        fts3SegReaderSort(apSegment, nMerge, j, fts3SegReaderDoclistCmp);
         2633  +        fts3SegReaderSort(apSegment, nMerge, j, xCmp);
  2545   2634         }
  2546   2635         if( nDoclist>0 ){
  2547   2636           pCsr->aDoclist = pCsr->aBuffer;
  2548   2637           pCsr->nDoclist = nDoclist;
  2549   2638           rc = SQLITE_ROW;
  2550   2639         }
  2551   2640       }
................................................................................
  2879   2968       *pnByte = pDeferred->pList->nData;
  2880   2969       return pDeferred->pList->aData;
  2881   2970     }
  2882   2971     *pnByte = 0;
  2883   2972     return 0;
  2884   2973   }
  2885   2974   
  2886         -/*
  2887         -** Helper fucntion for FreeDeferredDoclists(). This function removes all
  2888         -** references to deferred doclists from within the tree of Fts3Expr 
  2889         -** structures headed by 
  2890         -*/
  2891         -static void fts3DeferredDoclistClear(Fts3Expr *pExpr){
  2892         -  if( pExpr ){
  2893         -    Fts3Phrase *pPhrase = pExpr->pPhrase;
  2894         -    fts3DeferredDoclistClear(pExpr->pLeft);
  2895         -    fts3DeferredDoclistClear(pExpr->pRight);
  2896         -  }
  2897         -}
  2898         -
  2899   2975   /*
  2900   2976   ** Delete all cached deferred doclists. Deferred doclists are cached
  2901   2977   ** (allocated) by the sqlite3Fts3CacheDeferredDoclists() function.
  2902   2978   */
  2903   2979   void sqlite3Fts3FreeDeferredDoclists(Fts3Cursor *pCsr){
  2904   2980     Fts3DeferredToken *pDef;
  2905   2981     for(pDef=pCsr->pDeferred; pDef; pDef=pDef->pNext){
  2906         -    sqlite3_free(pDef->pList);
         2982  +    fts3PendingListDelete(pDef->pList);
  2907   2983       pDef->pList = 0;
  2908   2984     }
  2909         -  if( pCsr->pDeferred ){
  2910         -    fts3DeferredDoclistClear(pCsr->pExpr);
  2911         -  }
  2912   2985   }
  2913   2986   
  2914   2987   /*
  2915   2988   ** Free all entries in the pCsr->pDeffered list. Entries are added to 
  2916   2989   ** this list using sqlite3Fts3DeferToken().
  2917   2990   */
  2918   2991   void sqlite3Fts3FreeDeferredTokens(Fts3Cursor *pCsr){
  2919   2992     Fts3DeferredToken *pDef;
  2920   2993     Fts3DeferredToken *pNext;
  2921   2994     for(pDef=pCsr->pDeferred; pDef; pDef=pNext){
  2922   2995       pNext = pDef->pNext;
  2923         -    sqlite3_free(pDef->pList);
         2996  +    fts3PendingListDelete(pDef->pList);
  2924   2997       sqlite3_free(pDef);
  2925   2998     }
  2926   2999     pCsr->pDeferred = 0;
  2927   3000   }
  2928   3001   
  2929   3002   /*
  2930   3003   ** Generate deferred-doclists for all tokens in the pCsr->pDeferred list

Changes to test/fts3sort.test.

    17     17   
    18     18   # If SQLITE_ENABLE_FTS3 is defined, omit this file.
    19     19   ifcapable !fts3 {
    20     20     finish_test
    21     21     return
    22     22   }
    23     23   
    24         -set testprefix fts3sort
    25     24   
    26         -proc build_database {nRow} {
           25  +proc build_database {nRow param} {
    27     26     db close
    28     27     forcedelete test.db
    29     28     sqlite3 db test.db
    30     29   
    31     30     set vocab [list    aa ab ac   ba bb bc    ca cb cc   da]
    32     31     expr srand(0)
    33     32   
    34         -  execsql { CREATE VIRTUAL TABLE t1 USING fts4 }
           33  +  execsql "CREATE VIRTUAL TABLE t1 USING fts4($param)"
    35     34     for {set i 0} {$i < $nRow} {incr i} {
    36     35       set v [expr int(rand()*1000000)]
    37     36       set doc [list]
    38     37       for {set div 1} {$div < 1000000} {set div [expr $div*10]} {
    39     38         lappend doc [lindex $vocab [expr ($v/$div) % 10]]
    40     39       }
    41     40       execsql { INSERT INTO t1 VALUES($doc) }
    42     41     }
    43     42   }
    44     43   
    45         -set nRow 1000
    46         -do_test 1.0 {
    47         -  build_database $nRow
    48         -  execsql { SELECT count(*) FROM t1 }
    49         -} $nRow
           44  +set testprefix fts3sort
           45  +
           46  +unset -nocomplain CONTROL
           47  +foreach {t param} {
           48  +  1     ""
           49  +  2     "order=asc"
           50  +  3     "order=desc"
           51  +} {
           52  +
           53  +  set testprefix fts3sort-1.$t
    50     54   
    51         -foreach {tn query} {
           55  +  set nRow 1000
           56  +  do_test 1.0 {
           57  +    build_database $nRow $param
           58  +    execsql { SELECT count(*) FROM t1 }
           59  +  } $nRow
           60  +  
           61  +  foreach {tn query} {
    52     62     1   "SELECT docid, * FROM t1"
    53     63     2   "SELECT docid, * FROM t1 WHERE t1 MATCH 'aa'"
    54     64     3   "SELECT docid, * FROM t1 WHERE t1 MATCH 'a*'"
    55     65     4   "SELECT docid, quote(matchinfo(t1)) FROM t1 WHERE t1 MATCH 'a*'"
    56     66     5   "SELECT docid, quote(matchinfo(t1,'pcnxals')) FROM t1 WHERE t1 MATCH 'b*'"
    57     67     6   "SELECT docid, * FROM t1 WHERE t1 MATCH 'a* b* c*'"
    58     68     7   "SELECT docid, * FROM t1 WHERE t1 MATCH 'aa OR da'"
    59     69     8   "SELECT docid, * FROM t1 WHERE t1 MATCH 'nosuchtoken'"
    60     70     9   "SELECT docid, snippet(t1) FROM t1 WHERE t1 MATCH 'aa OR da'"
    61     71     10  "SELECT docid, snippet(t1) FROM t1 WHERE t1 MATCH 'aa OR nosuchtoken'"
    62         -} {
    63         -
    64         -  unset -nocomplain A B C D
    65         -  set A_list [list]
    66         -  set B_list [list]
    67         -  set C_list [list]
    68         -  set D_list [list]
           72  +  11  "SELECT docid, snippet(t1) FROM t1 WHERE t1 MATCH 'aa NEAR bb'"
           73  +  12  "SELECT docid, snippet(t1) FROM t1 WHERE t1 MATCH '\"aa bb\"'"
           74  +  13  "SELECT docid, content FROM t1 WHERE t1 MATCH 'aa NEAR/2 bb NEAR/3 cc'"
           75  +  14  "SELECT docid, content FROM t1 WHERE t1 MATCH '\"aa bb cc\"'"
           76  +  } {
           77  +  
           78  +    unset -nocomplain A B C D
           79  +    set A_list [list]
           80  +    set B_list [list]
           81  +    set C_list [list]
           82  +    set D_list [list]
           83  +  
           84  +    unset -nocomplain X
           85  +    db eval "$query ORDER BY rowid ASC"  X  { 
           86  +      set A($X(docid)) [array get X] 
           87  +      lappend A_list $X(docid)
           88  +    }
           89  +    unset -nocomplain X
           90  +    db eval "$query ORDER BY rowid DESC" X  { 
           91  +      set B($X(docid)) [array get X] 
           92  +      lappend B_list $X(docid)
           93  +    }
           94  +    unset -nocomplain X
           95  +    db eval "$query ORDER BY docid ASC"  X  { 
           96  +      set C($X(docid)) [array get X] 
           97  +      lappend C_list $X(docid)
           98  +    }
           99  +    unset -nocomplain X
          100  +    db eval "$query ORDER BY docid DESC" X  { 
          101  +      set D($X(docid)) [array get X] 
          102  +      lappend D_list $X(docid)
          103  +    }
          104  +  
          105  +    do_test $tn.1 { set A_list } [lsort -integer -increasing $A_list]
          106  +    do_test $tn.2 { set B_list } [lsort -integer -decreasing $B_list]
          107  +    do_test $tn.3 { set C_list } [lsort -integer -increasing $C_list]
          108  +    do_test $tn.4 { set D_list } [lsort -integer -decreasing $D_list]
          109  +  
          110  +    unset -nocomplain DATA
          111  +    unset -nocomplain X
          112  +    db eval "$query" X  { 
          113  +      set DATA($X(docid)) [array get X] 
          114  +    }
          115  +  
          116  +    do_test $tn.5 { lsort [array get A] } [lsort [array get DATA]]
          117  +    do_test $tn.6 { lsort [array get B] } [lsort [array get DATA]]
          118  +    do_test $tn.7 { lsort [array get C] } [lsort [array get DATA]]
          119  +    do_test $tn.8 { lsort [array get D] } [lsort [array get DATA]]
    69    120   
    70         -  unset -nocomplain X
    71         -  db eval "$query ORDER BY rowid ASC"  X  { 
    72         -    set A($X(docid)) [array get X] 
    73         -    lappend A_list $X(docid)
    74         -  }
    75         -  unset -nocomplain X
    76         -  db eval "$query ORDER BY rowid DESC" X  { 
    77         -    set B($X(docid)) [array get X] 
    78         -    lappend B_list $X(docid)
    79         -  }
    80         -  unset -nocomplain X
    81         -  db eval "$query ORDER BY docid ASC"  X  { 
    82         -    set C($X(docid)) [array get X] 
    83         -    lappend C_list $X(docid)
          121  +    if {[info exists CONTROL($tn)]} {
          122  +      do_test $tn.9 { set CONTROL($tn) } [lsort [array get DATA]]
          123  +    } else {
          124  +      set CONTROL($tn) [lsort [array get DATA]]
          125  +    }
    84    126     }
    85         -  unset -nocomplain X
    86         -  db eval "$query ORDER BY docid DESC" X  { 
    87         -    set D($X(docid)) [array get X] 
    88         -    lappend D_list $X(docid)
    89         -  }
          127  +}
          128  +unset -nocomplain CONTROL
          129  +
          130  +set testprefix fts3sort
    90    131   
    91         -  do_test 1.$tn.1 { set A_list } [lsort -integer -increasing $A_list]
    92         -  do_test 1.$tn.2 { set B_list } [lsort -integer -decreasing $B_list]
    93         -  do_test 1.$tn.3 { set C_list } [lsort -integer -increasing $C_list]
    94         -  do_test 1.$tn.4 { set D_list } [lsort -integer -decreasing $D_list]
    95         -
    96         -  unset -nocomplain DATA
    97         -  unset -nocomplain X
    98         -  db eval "$query" X  { 
    99         -    set DATA($X(docid)) [array get X] 
   100         -  }
   101         -
   102         -  do_test 1.$tn.5 { lsort [array get A] } [lsort [array get DATA]]
   103         -  do_test 1.$tn.6 { lsort [array get B] } [lsort [array get DATA]]
   104         -  do_test 1.$tn.7 { lsort [array get C] } [lsort [array get DATA]]
   105         -  do_test 1.$tn.8 { lsort [array get D] } [lsort [array get DATA]]
          132  +#-------------------------------------------------------------------------
          133  +# Tests for parsing the "order=asc" and "order=desc" directives.
          134  +#
          135  +foreach {tn param res} {
          136  +  1 "order=asc"             {0 {}}
          137  +  2 "order=desc"            {0 {}}
          138  +  3 "order=dec"             {1 {unrecognized order: dec}}
          139  +  4 "order=xxx, order=asc"  {0 {}}
          140  +} {
          141  +  execsql { DROP TABLE IF EXISTS t1 }
          142  +  do_catchsql_test 2.1.$tn "
          143  +    CREATE VIRTUAL TABLE t1 USING fts4(a, b, $param)
          144  +  " $res
   106    145   }
          146  +
          147  +do_execsql_test 2.2 {
          148  +  BEGIN;
          149  +    CREATE VIRTUAL TABLE t2 USING fts4(order=desc);
          150  +    INSERT INTO t2 VALUES('aa bb');
          151  +    INSERT INTO t2 VALUES('bb cc');
          152  +    INSERT INTO t2 VALUES('cc aa');
          153  +    SELECT docid FROM t2 WHERE t2 MATCH 'aa';
          154  +  END;
          155  +} {3 1}
          156  +do_execsql_test 2.3 {
          157  +  SELECT docid FROM t2 WHERE t2 MATCH 'aa';
          158  +} {3 1}
   107    159   
   108    160   finish_test
          161  +