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: |
f6a0193f5a32603eb48bddc6297042db |
| 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
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 +