Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Enhance the performance of fts5 AND and OR queries. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
62ea9e5ab8bc1a20245beebceb5ea62d |
User & Date: | dan 2016-02-02 17:40:41.411 |
Context
2016-02-02
| ||
21:19 | Add tests to restore full coverage of fts5 code. (check-in: 063755c815 user: dan tags: trunk) | |
17:40 | Enhance the performance of fts5 AND and OR queries. (check-in: 62ea9e5ab8 user: dan tags: trunk) | |
02:04 | Enhance the comment on the sqlite3_index_constraint object to bring attention to the fact than iColumn field can be negative for a rowid. (check-in: d8b7b1996e user: drh tags: trunk) | |
Changes
Changes to ext/fts5/fts5Int.h.
︙ | ︙ | |||
315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 | typedef struct Fts5Index Fts5Index; typedef struct Fts5IndexIter Fts5IndexIter; struct Fts5IndexIter { i64 iRowid; const u8 *pData; int nData; }; /* ** Values used as part of the flags argument passed to IndexQuery(). */ #define FTS5INDEX_QUERY_PREFIX 0x0001 /* Prefix query */ #define FTS5INDEX_QUERY_DESC 0x0002 /* Docs in descending rowid order */ #define FTS5INDEX_QUERY_TEST_NOIDX 0x0004 /* Do not use prefix index */ | > > > | 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 | typedef struct Fts5Index Fts5Index; typedef struct Fts5IndexIter Fts5IndexIter; struct Fts5IndexIter { i64 iRowid; const u8 *pData; int nData; u8 bEof; }; #define sqlite3Fts5IterEof(x) ((x)->bEof) /* ** Values used as part of the flags argument passed to IndexQuery(). */ #define FTS5INDEX_QUERY_PREFIX 0x0001 /* Prefix query */ #define FTS5INDEX_QUERY_DESC 0x0002 /* Docs in descending rowid order */ #define FTS5INDEX_QUERY_TEST_NOIDX 0x0004 /* Do not use prefix index */ |
︙ | ︙ | |||
380 381 382 383 384 385 386 | Fts5IndexIter **ppIter /* OUT: New iterator object */ ); /* ** The various operations on open token or token prefix iterators opened ** using sqlite3Fts5IndexQuery(). */ | < | 383 384 385 386 387 388 389 390 391 392 393 394 395 396 | Fts5IndexIter **ppIter /* OUT: New iterator object */ ); /* ** The various operations on open token or token prefix iterators opened ** using sqlite3Fts5IndexQuery(). */ int sqlite3Fts5IterNext(Fts5IndexIter*); int sqlite3Fts5IterNextFrom(Fts5IndexIter*, i64 iMatch); i64 sqlite3Fts5IterRowid(Fts5IndexIter*); /* ** Close an iterator opened by sqlite3Fts5IndexQuery(). */ |
︙ | ︙ |
Changes to ext/fts5/fts5_expr.c.
︙ | ︙ | |||
299 300 301 302 303 304 305 | int bRetValid = 0; Fts5ExprTerm *p; assert( pTerm->pSynonym ); assert( bDesc==0 || bDesc==1 ); for(p=pTerm; p; p=p->pSynonym){ if( 0==sqlite3Fts5IterEof(p->pIter) ){ | | | 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 | int bRetValid = 0; Fts5ExprTerm *p; assert( pTerm->pSynonym ); assert( bDesc==0 || bDesc==1 ); for(p=pTerm; p; p=p->pSynonym){ if( 0==sqlite3Fts5IterEof(p->pIter) ){ i64 iRowid = p->pIter->iRowid; if( bRetValid==0 || (bDesc!=(iRowid<iRet)) ){ iRet = iRowid; bRetValid = 1; } } } |
︙ | ︙ | |||
332 333 334 335 336 337 338 | int nAlloc = 4; int rc = SQLITE_OK; Fts5ExprTerm *p; assert( pTerm->pSynonym ); for(p=pTerm; p; p=p->pSynonym){ Fts5IndexIter *pIter = p->pIter; | | | 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 | int nAlloc = 4; int rc = SQLITE_OK; Fts5ExprTerm *p; assert( pTerm->pSynonym ); for(p=pTerm; p; p=p->pSynonym){ Fts5IndexIter *pIter = p->pIter; if( sqlite3Fts5IterEof(pIter)==0 && pIter->iRowid==iRowid ){ if( pIter->nData==0 ) continue; if( nIter==nAlloc ){ int nByte = sizeof(Fts5PoslistReader) * nAlloc * 2; Fts5PoslistReader *aNew = (Fts5PoslistReader*)sqlite3_malloc(nByte); if( aNew==0 ){ rc = SQLITE_NOMEM; goto synonym_poslist_out; |
︙ | ︙ | |||
627 628 629 630 631 632 633 | int bRet = a[0].pOut->n>0; *pRc = rc; if( a!=aStatic ) sqlite3_free(a); return bRet; } } | < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < | | | | 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 | int bRet = a[0].pOut->n>0; *pRc = rc; if( a!=aStatic ) sqlite3_free(a); return bRet; } } /* ** Advance iterator pIter until it points to a value equal to or laster ** than the initial value of *piLast. If this means the iterator points ** to a value laster than *piLast, update *piLast to the new lastest value. ** ** If the iterator reaches EOF, set *pbEof to true before returning. If ** an error occurs, set *pRc to an error code. If either *pbEof or *pRc ** are set, return a non-zero value. Otherwise, return zero. */ static int fts5ExprAdvanceto( Fts5IndexIter *pIter, /* Iterator to advance */ int bDesc, /* True if iterator is "rowid DESC" */ i64 *piLast, /* IN/OUT: Lastest rowid seen so far */ int *pRc, /* OUT: Error code */ int *pbEof /* OUT: Set to true if EOF */ ){ i64 iLast = *piLast; i64 iRowid; iRowid = pIter->iRowid; if( (bDesc==0 && iLast>iRowid) || (bDesc && iLast<iRowid) ){ int rc = sqlite3Fts5IterNextFrom(pIter, iLast); if( rc || sqlite3Fts5IterEof(pIter) ){ *pRc = rc; *pbEof = 1; return 1; } iRowid = pIter->iRowid; assert( (bDesc==0 && iRowid>=iLast) || (bDesc==1 && iRowid<=iLast) ); } *piLast = iRowid; return 0; } static int fts5ExprSynonymAdvanceto( Fts5ExprTerm *pTerm, /* Term iterator to advance */ int bDesc, /* True if iterator is "rowid DESC" */ i64 *piLast, /* IN/OUT: Lastest rowid seen so far */ int *pRc /* OUT: Error code */ ){ int rc = SQLITE_OK; i64 iLast = *piLast; Fts5ExprTerm *p; int bEof = 0; for(p=pTerm; rc==SQLITE_OK && p; p=p->pSynonym){ if( sqlite3Fts5IterEof(p->pIter)==0 ){ i64 iRowid = p->pIter->iRowid; if( (bDesc==0 && iLast>iRowid) || (bDesc && iLast<iRowid) ){ rc = sqlite3Fts5IterNextFrom(p->pIter, iLast); } } } if( rc!=SQLITE_OK ){ |
︙ | ︙ | |||
805 806 807 808 809 810 811 | if( i==pNear->nPhrase && (i==1 || fts5ExprNearIsMatch(pRc, pNear)) ){ return 1; } return 0; } } | < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < | 739 740 741 742 743 744 745 746 747 748 749 750 751 752 | if( i==pNear->nPhrase && (i==1 || fts5ExprNearIsMatch(pRc, pNear)) ){ return 1; } return 0; } } /* ** Initialize all term iterators in the pNear object. If any term is found ** to match no documents at all, return immediately without initializing any ** further iterators. */ static int fts5ExprNearInitAll( |
︙ | ︙ | |||
952 953 954 955 956 957 958 | return rc; } } } return rc; } | < < < < | 788 789 790 791 792 793 794 795 796 797 798 799 800 801 | return rc; } } } return rc; } /* ** If pExpr is an ASC iterator, this function returns a value with the ** same sign as: ** ** (iLhs - iRhs) ** |
︙ | ︙ | |||
1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 | for(i=0; i<pNode->nChild; i++){ fts5ExprNodeZeroPoslist(pNode->apChild[i]); } } } /* ** Argument pNode is an FTS5_AND node. */ | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | < < < | | | | | < | 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053 1054 1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 | for(i=0; i<pNode->nChild; i++){ fts5ExprNodeZeroPoslist(pNode->apChild[i]); } } } /* ** Compare the values currently indicated by the two nodes as follows: ** ** res = (*p1) - (*p2) ** ** Nodes that point to values that come later in the iteration order are ** considered to be larger. Nodes at EOF are the largest of all. ** ** This means that if the iteration order is ASC, then numerically larger ** rowids are considered larger. Or if it is the default DESC, numerically ** smaller rowids are larger. */ static int fts5NodeCompare( Fts5Expr *pExpr, Fts5ExprNode *p1, Fts5ExprNode *p2 ){ if( p2->bEof ) return -1; if( p1->bEof ) return +1; return fts5RowidCmp(pExpr, p1->iRowid, p2->iRowid); } /* ** All individual term iterators in pNear are guaranteed to be valid when ** this function is called. This function checks if all term iterators ** point to the same rowid, and if not, advances them until they do. ** If an EOF is reached before this happens, *pbEof is set to true before ** returning. ** ** SQLITE_OK is returned if an error occurs, or an SQLite error code ** otherwise. It is not considered an error code if an iterator reaches ** EOF. */ static int fts5ExprNodeTest_STRING( Fts5Expr *pExpr, /* Expression pPhrase belongs to */ Fts5ExprNode *pNode ){ Fts5ExprNearset *pNear = pNode->pNear; Fts5ExprPhrase *pLeft = pNear->apPhrase[0]; int rc = SQLITE_OK; i64 iLast; /* Lastest rowid any iterator points to */ int i, j; /* Phrase and token index, respectively */ int bMatch; /* True if all terms are at the same rowid */ const int bDesc = pExpr->bDesc; /* Check that this node should not be FTS5_TERM */ assert( pNear->nPhrase>1 || pNear->apPhrase[0]->nTerm>1 || pNear->apPhrase[0]->aTerm[0].pSynonym ); /* Initialize iLast, the "lastest" rowid any iterator points to. If the ** iterator skips through rowids in the default ascending order, this means ** the maximum rowid. Or, if the iterator is "ORDER BY rowid DESC", then it ** means the minimum rowid. */ if( pLeft->aTerm[0].pSynonym ){ iLast = fts5ExprSynonymRowid(&pLeft->aTerm[0], bDesc, 0); }else{ iLast = pLeft->aTerm[0].pIter->iRowid; } do { bMatch = 1; for(i=0; i<pNear->nPhrase; i++){ Fts5ExprPhrase *pPhrase = pNear->apPhrase[i]; for(j=0; j<pPhrase->nTerm; j++){ Fts5ExprTerm *pTerm = &pPhrase->aTerm[j]; if( pTerm->pSynonym ){ i64 iRowid = fts5ExprSynonymRowid(pTerm, bDesc, 0); if( iRowid==iLast ) continue; bMatch = 0; if( fts5ExprSynonymAdvanceto(pTerm, bDesc, &iLast, &rc) ){ pNode->bNomatch = 0; pNode->bEof = 1; return rc; } }else{ Fts5IndexIter *pIter = pPhrase->aTerm[j].pIter; if( pIter->iRowid==iLast ) continue; bMatch = 0; if( fts5ExprAdvanceto(pIter, bDesc, &iLast, &rc, &pNode->bEof) ){ return rc; } } } } }while( bMatch==0 ); pNode->iRowid = iLast; pNode->bNomatch = ((0==fts5ExprNearTest(&rc, pExpr, pNode)) && rc==SQLITE_OK); assert( pNode->bEof==0 || pNode->bNomatch==0 ); return rc; } /* ** Advance the first term iterator in the first phrase of pNear. Set output ** variable *pbEof to true if it reaches EOF or if an error occurs. ** ** Return SQLITE_OK if successful, or an SQLite error code if an error ** occurs. */ static int fts5ExprNodeNext_STRING( Fts5Expr *pExpr, /* Expression pPhrase belongs to */ Fts5ExprNode *pNode, /* FTS5_STRING or FTS5_TERM node */ int bFromValid, i64 iFrom ){ Fts5ExprTerm *pTerm = &pNode->pNear->apPhrase[0]->aTerm[0]; int rc = SQLITE_OK; pNode->bNomatch = 0; if( pTerm->pSynonym ){ int bEof = 1; Fts5ExprTerm *p; /* Find the firstest rowid any synonym points to. */ i64 iRowid = fts5ExprSynonymRowid(pTerm, pExpr->bDesc, 0); /* Advance each iterator that currently points to iRowid. Or, if iFrom ** is valid - each iterator that points to a rowid before iFrom. */ for(p=pTerm; p; p=p->pSynonym){ if( sqlite3Fts5IterEof(p->pIter)==0 ){ i64 ii = p->pIter->iRowid; if( ii==iRowid || (bFromValid && ii!=iFrom && (ii>iFrom)==pExpr->bDesc) ){ if( bFromValid ){ rc = sqlite3Fts5IterNextFrom(p->pIter, iFrom); }else{ rc = sqlite3Fts5IterNext(p->pIter); } if( rc!=SQLITE_OK ) break; if( sqlite3Fts5IterEof(p->pIter)==0 ){ bEof = 0; } }else{ bEof = 0; } } } /* Set the EOF flag if either all synonym iterators are at EOF or an ** error has occurred. */ pNode->bEof = (rc || bEof); }else{ Fts5IndexIter *pIter = pTerm->pIter; assert( Fts5NodeIsString(pNode) ); if( bFromValid ){ rc = sqlite3Fts5IterNextFrom(pIter, iFrom); }else{ rc = sqlite3Fts5IterNext(pIter); } pNode->bEof = (rc || sqlite3Fts5IterEof(pIter)); } if( pNode->bEof==0 ){ assert( rc==SQLITE_OK ); rc = fts5ExprNodeTest_STRING(pExpr, pNode); } return rc; } static int fts5ExprNodeTest_TERM( Fts5Expr *pExpr, /* Expression that pNear is a part of */ Fts5ExprNode *pNode /* The "NEAR" node (FTS5_TERM) */ ){ /* As this "NEAR" object is actually a single phrase that consists ** of a single term only, grab pointers into the poslist managed by the ** fts5_index.c iterator object. This is much faster than synthesizing ** a new poslist the way we have to for more complicated phrase or NEAR ** expressions. */ Fts5ExprPhrase *pPhrase = pNode->pNear->apPhrase[0]; Fts5IndexIter *pIter = pPhrase->aTerm[0].pIter; assert( pNode->eType==FTS5_TERM ); assert( pNode->pNear->nPhrase==1 && pPhrase->nTerm==1 ); assert( pPhrase->aTerm[0].pSynonym==0 ); pPhrase->poslist.n = pIter->nData; if( pExpr->pConfig->eDetail==FTS5_DETAIL_FULL ){ pPhrase->poslist.p = (u8*)pIter->pData; } pNode->iRowid = pIter->iRowid; pNode->bNomatch = (pPhrase->poslist.n==0); return SQLITE_OK; } /* ** xNext() method for a node of type FTS5_TERM. */ static int fts5ExprNodeNext_TERM( Fts5Expr *pExpr, Fts5ExprNode *pNode, int bFromValid, i64 iFrom ){ int rc; Fts5IndexIter *pIter = pNode->pNear->apPhrase[0]->aTerm[0].pIter; assert( pNode->bEof==0 ); if( bFromValid ){ rc = sqlite3Fts5IterNextFrom(pIter, iFrom); }else{ rc = sqlite3Fts5IterNext(pIter); } if( rc==SQLITE_OK && sqlite3Fts5IterEof(pIter)==0 ){ rc = fts5ExprNodeTest_TERM(pExpr, pNode); }else{ pNode->bEof = 1; pNode->bNomatch = 0; } return rc; } static void fts5ExprNodeTest_OR( Fts5Expr *pExpr, /* Expression of which pNode is a part */ Fts5ExprNode *pNode /* Expression node to test */ ){ Fts5ExprNode *pNext = pNode->apChild[0]; int i; for(i=1; i<pNode->nChild; i++){ Fts5ExprNode *pChild = pNode->apChild[i]; int cmp = fts5NodeCompare(pExpr, pNext, pChild); if( cmp>0 || (cmp==0 && pChild->bNomatch==0) ){ pNext = pChild; } } pNode->iRowid = pNext->iRowid; pNode->bEof = pNext->bEof; pNode->bNomatch = pNext->bNomatch; } static int fts5ExprNodeNext_OR( Fts5Expr *pExpr, Fts5ExprNode *pNode, int bFromValid, i64 iFrom ){ int i; i64 iLast = pNode->iRowid; for(i=0; i<pNode->nChild; i++){ Fts5ExprNode *p1 = pNode->apChild[i]; assert( p1->bEof || fts5RowidCmp(pExpr, p1->iRowid, iLast)>=0 ); if( p1->bEof==0 ){ if( (p1->iRowid==iLast) || (bFromValid && fts5RowidCmp(pExpr, p1->iRowid, iFrom)<0) ){ int rc = fts5ExprNodeNext(pExpr, p1, bFromValid, iFrom); if( rc!=SQLITE_OK ) return rc; } } } fts5ExprNodeTest_OR(pExpr, pNode); return SQLITE_OK; } /* ** Argument pNode is an FTS5_AND node. */ static int fts5ExprNodeTest_AND( Fts5Expr *pExpr, /* Expression pPhrase belongs to */ Fts5ExprNode *pAnd /* FTS5_AND node to advance */ ){ int iChild; i64 iLast = pAnd->iRowid; int rc = SQLITE_OK; int bMatch; assert( pAnd->bEof==0 ); do { pAnd->bNomatch = 0; bMatch = 1; for(iChild=0; iChild<pAnd->nChild; iChild++){ Fts5ExprNode *pChild = pAnd->apChild[iChild]; int cmp = fts5RowidCmp(pExpr, iLast, pChild->iRowid); if( cmp>0 ){ /* Advance pChild until it points to iLast or laster */ rc = fts5ExprNodeNext(pExpr, pChild, 1, iLast); if( rc!=SQLITE_OK ) return rc; } /* If the child node is now at EOF, so is the parent AND node. Otherwise, ** the child node is guaranteed to have advanced at least as far as ** rowid iLast. So if it is not at exactly iLast, pChild->iRowid is the ** new lastest rowid seen so far. */ assert( pChild->bEof || fts5RowidCmp(pExpr, iLast, pChild->iRowid)<=0 ); |
︙ | ︙ | |||
1064 1065 1066 1067 1068 1069 1070 | if( pAnd->bNomatch && pAnd!=pExpr->pRoot ){ fts5ExprNodeZeroPoslist(pAnd); } pAnd->iRowid = iLast; return SQLITE_OK; } | < < < < < < < < < < < < < < < < < < < < < < < < < < | > > > > | < | > > > > > > > > | | < < > > > | > | | > | < > | | > > > < < < < < < < | < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < | < < < < | | | < < < < < < < < < < < < < < < < | < | | | < < | < < < < < < < < < < < < < < < < < < < < < < | < < < < < < < | 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 1206 1207 1208 1209 1210 1211 1212 1213 1214 1215 1216 1217 1218 1219 1220 1221 1222 1223 1224 1225 1226 1227 1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246 1247 1248 1249 1250 1251 1252 1253 1254 1255 1256 1257 1258 1259 | if( pAnd->bNomatch && pAnd!=pExpr->pRoot ){ fts5ExprNodeZeroPoslist(pAnd); } pAnd->iRowid = iLast; return SQLITE_OK; } static int fts5ExprNodeNext_AND( Fts5Expr *pExpr, Fts5ExprNode *pNode, int bFromValid, i64 iFrom ){ int rc = fts5ExprNodeNext(pExpr, pNode->apChild[0], bFromValid, iFrom); if( rc==SQLITE_OK ){ rc = fts5ExprNodeTest_AND(pExpr, pNode); } return rc; } static int fts5ExprNodeTest_NOT( Fts5Expr *pExpr, /* Expression pPhrase belongs to */ Fts5ExprNode *pNode /* FTS5_NOT node to advance */ ){ int rc = SQLITE_OK; Fts5ExprNode *p1 = pNode->apChild[0]; Fts5ExprNode *p2 = pNode->apChild[1]; assert( pNode->nChild==2 ); while( rc==SQLITE_OK && p1->bEof==0 ){ int cmp = fts5NodeCompare(pExpr, p1, p2); if( cmp>0 ){ rc = fts5ExprNodeNext(pExpr, p2, 1, p1->iRowid); cmp = fts5NodeCompare(pExpr, p1, p2); } assert( rc!=SQLITE_OK || cmp<=0 ); if( cmp || p2->bNomatch ) break; rc = fts5ExprNodeNext(pExpr, p1, 0, 0); } pNode->bEof = p1->bEof; pNode->bNomatch = p1->bNomatch; pNode->iRowid = p1->iRowid; if( p1->bEof ){ fts5ExprNodeZeroPoslist(p2); } return rc; } static int fts5ExprNodeNext_NOT( Fts5Expr *pExpr, Fts5ExprNode *pNode, int bFromValid, i64 iFrom ){ int rc = fts5ExprNodeNext(pExpr, pNode->apChild[0], bFromValid, iFrom); if( rc==SQLITE_OK ){ rc = fts5ExprNodeTest_NOT(pExpr, pNode); } return rc; } /* ** If pNode currently points to a match, this function returns SQLITE_OK ** without modifying it. Otherwise, pNode is advanced until it does point ** to a match or EOF is reached. */ static int fts5ExprNodeTest( Fts5Expr *pExpr, /* Expression of which pNode is a part */ Fts5ExprNode *pNode /* Expression node to test */ ){ int rc = SQLITE_OK; if( pNode->bEof==0 ){ switch( pNode->eType ){ case FTS5_STRING: { rc = fts5ExprNodeTest_STRING(pExpr, pNode); break; } case FTS5_TERM: { rc = fts5ExprNodeTest_TERM(pExpr, pNode); break; } case FTS5_AND: { rc = fts5ExprNodeTest_AND(pExpr, pNode); break; } case FTS5_OR: { fts5ExprNodeTest_OR(pExpr, pNode); break; } default: assert( pNode->eType==FTS5_NOT ); { rc = fts5ExprNodeTest_NOT(pExpr, pNode); break; } } } return rc; } |
︙ | ︙ | |||
1325 1326 1327 1328 1329 1330 1331 | assert( pNode->eType==FTS5_NOT ); pNode->bEof = pNode->apChild[0]->bEof; break; } } if( rc==SQLITE_OK ){ | | | 1297 1298 1299 1300 1301 1302 1303 1304 1305 1306 1307 1308 1309 1310 1311 | assert( pNode->eType==FTS5_NOT ); pNode->bEof = pNode->apChild[0]->bEof; break; } } if( rc==SQLITE_OK ){ rc = fts5ExprNodeTest(pExpr, pNode); } return rc; } /* ** Begin iterating through the set of documents in index pIdx matched by |
︙ | ︙ | |||
1686 1687 1688 1689 1690 1691 1692 | /* All the allocations succeeded. Put the expression object together. */ pNew->pIndex = pExpr->pIndex; pNew->pConfig = pExpr->pConfig; pNew->nPhrase = 1; pNew->apExprPhrase[0] = sCtx.pPhrase; pNew->pRoot->pNear->apPhrase[0] = sCtx.pPhrase; pNew->pRoot->pNear->nPhrase = 1; | < > > | 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679 | /* All the allocations succeeded. Put the expression object together. */ pNew->pIndex = pExpr->pIndex; pNew->pConfig = pExpr->pConfig; pNew->nPhrase = 1; pNew->apExprPhrase[0] = sCtx.pPhrase; pNew->pRoot->pNear->apPhrase[0] = sCtx.pPhrase; pNew->pRoot->pNear->nPhrase = 1; sCtx.pPhrase->pNode = pNew->pRoot; if( pOrig->nTerm==1 && pOrig->aTerm[0].pSynonym==0 ){ pNew->pRoot->eType = FTS5_TERM; pNew->pRoot->xNext = fts5ExprNodeNext_TERM; }else{ pNew->pRoot->eType = FTS5_STRING; pNew->pRoot->xNext = fts5ExprNodeNext_STRING; } }else{ sqlite3Fts5ExprFree(pNew); fts5ExprPhraseFree(sCtx.pPhrase); pNew = 0; } |
︙ | ︙ | |||
1839 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 | if( pNear ){ pNear->pColset = pColset; }else{ sqlite3_free(pColset); } } static void fts5ExprAddChildren(Fts5ExprNode *p, Fts5ExprNode *pSub){ if( p->eType!=FTS5_NOT && pSub->eType==p->eType ){ int nByte = sizeof(Fts5ExprNode*) * pSub->nChild; memcpy(&p->apChild[p->nChild], pSub->apChild, nByte); p->nChild += pSub->nChild; sqlite3_free(pSub); | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 1812 1813 1814 1815 1816 1817 1818 1819 1820 1821 1822 1823 1824 1825 1826 1827 1828 1829 1830 1831 1832 1833 1834 1835 1836 1837 1838 1839 1840 1841 1842 1843 1844 1845 1846 1847 1848 1849 1850 1851 1852 1853 1854 1855 1856 1857 | if( pNear ){ pNear->pColset = pColset; }else{ sqlite3_free(pColset); } } static void fts5ExprAssignXNext(Fts5ExprNode *pNode){ switch( pNode->eType ){ case FTS5_STRING: { Fts5ExprNearset *pNear = pNode->pNear; if( pNear->nPhrase==1 && pNear->apPhrase[0]->nTerm==1 && pNear->apPhrase[0]->aTerm[0].pSynonym==0 ){ pNode->eType = FTS5_TERM; pNode->xNext = fts5ExprNodeNext_TERM; }else{ pNode->xNext = fts5ExprNodeNext_STRING; } break; }; case FTS5_OR: { pNode->xNext = fts5ExprNodeNext_OR; break; }; case FTS5_AND: { pNode->xNext = fts5ExprNodeNext_AND; break; }; default: assert( pNode->eType==FTS5_NOT ); { pNode->xNext = fts5ExprNodeNext_NOT; break; }; } } static void fts5ExprAddChildren(Fts5ExprNode *p, Fts5ExprNode *pSub){ if( p->eType!=FTS5_NOT && pSub->eType==p->eType ){ int nByte = sizeof(Fts5ExprNode*) * pSub->nChild; memcpy(&p->apChild[p->nChild], pSub->apChild, nByte); p->nChild += pSub->nChild; sqlite3_free(pSub); |
︙ | ︙ | |||
1887 1888 1889 1890 1891 1892 1893 | if( pRight->eType==eType ) nChild += pRight->nChild-1; } nByte = sizeof(Fts5ExprNode) + sizeof(Fts5ExprNode*)*(nChild-1); pRet = (Fts5ExprNode*)sqlite3Fts5MallocZero(&pParse->rc, nByte); if( pRet ){ | < > < < < < | | > > > | 1892 1893 1894 1895 1896 1897 1898 1899 1900 1901 1902 1903 1904 1905 1906 1907 1908 1909 1910 1911 1912 1913 1914 1915 1916 1917 1918 1919 1920 1921 1922 1923 1924 1925 1926 1927 1928 | if( pRight->eType==eType ) nChild += pRight->nChild-1; } nByte = sizeof(Fts5ExprNode) + sizeof(Fts5ExprNode*)*(nChild-1); pRet = (Fts5ExprNode*)sqlite3Fts5MallocZero(&pParse->rc, nByte); if( pRet ){ pRet->eType = eType; pRet->pNear = pNear; fts5ExprAssignXNext(pRet); if( eType==FTS5_STRING ){ int iPhrase; for(iPhrase=0; iPhrase<pNear->nPhrase; iPhrase++){ pNear->apPhrase[iPhrase]->pNode = pRet; } if( pParse->pConfig->eDetail!=FTS5_DETAIL_FULL && (pNear->nPhrase!=1 || pNear->apPhrase[0]->nTerm!=1) ){ assert( pParse->rc==SQLITE_OK ); pParse->rc = SQLITE_ERROR; assert( pParse->zErr==0 ); pParse->zErr = sqlite3_mprintf( "fts5: %s queries are not supported (detail!=full)", pNear->nPhrase==1 ? "phrase": "NEAR" ); sqlite3_free(pRet); pRet = 0; } }else{ fts5ExprAddChildren(pRet, pLeft); fts5ExprAddChildren(pRet, pRight); } } } |
︙ | ︙ |
Changes to ext/fts5/fts5_index.c.
︙ | ︙ | |||
514 515 516 517 518 519 520 | /* Invoked to set output variables. */ void (*xSetOutputs)(Fts5Iter*, Fts5SegIter*); int nSeg; /* Size of aSeg[] array */ int bRev; /* True to iterate in reverse order */ u8 bSkipEmpty; /* True to skip deleted entries */ | < | 514 515 516 517 518 519 520 521 522 523 524 525 526 527 | /* Invoked to set output variables. */ void (*xSetOutputs)(Fts5Iter*, Fts5SegIter*); int nSeg; /* Size of aSeg[] array */ int bRev; /* True to iterate in reverse order */ u8 bSkipEmpty; /* True to skip deleted entries */ u8 bFiltered; /* True if column-filter already applied */ i64 iSwitchRowid; /* Firstest rowid of other than aFirst[1] */ Fts5CResult *aFirst; /* Current merge state (see above) */ Fts5SegIter aSeg[1]; /* Array of segment iterators */ }; |
︙ | ︙ | |||
2455 2456 2457 2458 2459 2460 2461 | ** are correct. */ static void fts5AssertMultiIterSetup(Fts5Index *p, Fts5Iter *pIter){ if( p->rc==SQLITE_OK ){ Fts5SegIter *pFirst = &pIter->aSeg[ pIter->aFirst[1].iFirst ]; int i; | | | 2454 2455 2456 2457 2458 2459 2460 2461 2462 2463 2464 2465 2466 2467 2468 | ** are correct. */ static void fts5AssertMultiIterSetup(Fts5Index *p, Fts5Iter *pIter){ if( p->rc==SQLITE_OK ){ Fts5SegIter *pFirst = &pIter->aSeg[ pIter->aFirst[1].iFirst ]; int i; assert( (pFirst->pLeaf==0)==pIter->base.bEof ); /* Check that pIter->iSwitchRowid is set correctly. */ for(i=0; i<pIter->nSeg; i++){ Fts5SegIter *p1 = &pIter->aSeg[i]; assert( p1==pFirst || p1->pLeaf==0 || fts5BufferCompare(&pFirst->term, &p1->term) |
︙ | ︙ | |||
2727 2728 2729 2730 2731 2732 2733 | } /* ** Set the pIter->bEof variable based on the state of the sub-iterators. */ static void fts5MultiIterSetEof(Fts5Iter *pIter){ Fts5SegIter *pSeg = &pIter->aSeg[ pIter->aFirst[1].iFirst ]; | | | 2726 2727 2728 2729 2730 2731 2732 2733 2734 2735 2736 2737 2738 2739 2740 | } /* ** Set the pIter->bEof variable based on the state of the sub-iterators. */ static void fts5MultiIterSetEof(Fts5Iter *pIter){ Fts5SegIter *pSeg = &pIter->aSeg[ pIter->aFirst[1].iFirst ]; pIter->base.bEof = pSeg->pLeaf==0; pIter->iSwitchRowid = pSeg->iRowid; } /* ** Move the iterator to the next entry. ** ** If an error occurs, an error code is left in Fts5Index.rc. It is not |
︙ | ︙ | |||
2960 2961 2962 2963 2964 2965 2966 | pIter->flags |= FTS5_SEGITER_REVERSE; fts5SegIterReverseInitPage(p, pIter); }else{ fts5SegIterLoadNPos(p, pIter); } pData = 0; }else{ | | | | | 2959 2960 2961 2962 2963 2964 2965 2966 2967 2968 2969 2970 2971 2972 2973 2974 2975 2976 2977 2978 2979 2980 2981 2982 2983 2984 2985 2986 2987 2988 2989 2990 2991 | pIter->flags |= FTS5_SEGITER_REVERSE; fts5SegIterReverseInitPage(p, pIter); }else{ fts5SegIterLoadNPos(p, pIter); } pData = 0; }else{ pNew->base.bEof = 1; } fts5SegIterSetNext(p, pIter); *ppOut = pNew; } fts5DataRelease(pData); } /* ** Return true if the iterator is at EOF or if an error has occurred. ** False otherwise. */ static int fts5MultiIterEof(Fts5Index *p, Fts5Iter *pIter){ assert( p->rc || (pIter->aSeg[ pIter->aFirst[1].iFirst ].pLeaf==0)==pIter->base.bEof ); return (p->rc || pIter->base.bEof); } /* ** Return the rowid of the entry that the iterator currently points ** to. If the iterator points to EOF when this function is called the ** results are undefined. */ |
︙ | ︙ | |||
5205 5206 5207 5208 5209 5210 5211 | } return fts5IndexReturn(p); } /* ** Return true if the iterator passed as the only argument is at EOF. */ | < < < < < | 5204 5205 5206 5207 5208 5209 5210 5211 5212 5213 5214 5215 5216 5217 | } return fts5IndexReturn(p); } /* ** Return true if the iterator passed as the only argument is at EOF. */ /* ** Move to the next matching rowid. */ int sqlite3Fts5IterNext(Fts5IndexIter *pIndexIter){ Fts5Iter *pIter = (Fts5Iter*)pIndexIter; assert( pIter->pIndex->rc==SQLITE_OK ); fts5MultiIterNext(pIter->pIndex, pIter, 0, 0); |
︙ | ︙ | |||
5235 5236 5237 5238 5239 5240 5241 | fts5MultiIterNext(p, pIter, 0, 0); if( p->rc==SQLITE_OK ){ Fts5SegIter *pSeg = &pIter->aSeg[ pIter->aFirst[1].iFirst ]; if( pSeg->pLeaf && pSeg->term.p[0]!=FTS5_MAIN_PREFIX ){ fts5DataRelease(pSeg->pLeaf); pSeg->pLeaf = 0; | | < < < < < < < | 5229 5230 5231 5232 5233 5234 5235 5236 5237 5238 5239 5240 5241 5242 5243 5244 5245 5246 5247 5248 5249 5250 5251 5252 5253 5254 5255 5256 5257 5258 5259 5260 | fts5MultiIterNext(p, pIter, 0, 0); if( p->rc==SQLITE_OK ){ Fts5SegIter *pSeg = &pIter->aSeg[ pIter->aFirst[1].iFirst ]; if( pSeg->pLeaf && pSeg->term.p[0]!=FTS5_MAIN_PREFIX ){ fts5DataRelease(pSeg->pLeaf); pSeg->pLeaf = 0; pIter->base.bEof = 1; } } return fts5IndexReturn(pIter->pIndex); } /* ** Move to the next matching rowid that occurs at or after iMatch. The ** definition of "at or after" depends on whether this iterator iterates ** in ascending or descending rowid order. */ int sqlite3Fts5IterNextFrom(Fts5IndexIter *pIndexIter, i64 iMatch){ Fts5Iter *pIter = (Fts5Iter*)pIndexIter; fts5MultiIterNextFrom(pIter->pIndex, pIter, iMatch); return fts5IndexReturn(pIter->pIndex); } /* ** Return the current term. */ const char *sqlite3Fts5IterTerm(Fts5IndexIter *pIndexIter, int *pn){ int n; const char *z = (const char*)fts5MultiIterTerm((Fts5Iter*)pIndexIter, &n); *pn = n-1; |
︙ | ︙ | |||
5446 5447 5448 5449 5450 5451 5452 | ){ int eDetail = p->pConfig->eDetail; u64 cksum = *pCksum; Fts5IndexIter *pIter = 0; int rc = sqlite3Fts5IndexQuery(p, z, n, flags, 0, &pIter); while( rc==SQLITE_OK && 0==sqlite3Fts5IterEof(pIter) ){ | | | 5433 5434 5435 5436 5437 5438 5439 5440 5441 5442 5443 5444 5445 5446 5447 | ){ int eDetail = p->pConfig->eDetail; u64 cksum = *pCksum; Fts5IndexIter *pIter = 0; int rc = sqlite3Fts5IndexQuery(p, z, n, flags, 0, &pIter); while( rc==SQLITE_OK && 0==sqlite3Fts5IterEof(pIter) ){ i64 rowid = pIter->iRowid; if( eDetail==FTS5_DETAIL_NONE ){ cksum ^= sqlite3Fts5IndexEntryCksum(rowid, 0, 0, iIdx, z, n); }else{ Fts5PoslistReader sReader; for(sqlite3Fts5PoslistReaderInit(pIter->pData, pIter->nData, &sReader); sReader.bEof==0; |
︙ | ︙ |
Changes to ext/fts5/tool/fts5speed.tcl.
︙ | ︙ | |||
8 9 10 11 12 13 14 15 16 17 18 19 20 21 | {100 "SELECT count(*) FROM t1 WHERE t1 MATCH 'enron AND myapps'"} {1 "SELECT count(*) FROM t1 WHERE t1 MATCH 'en* AND my*'"} {1 "SELECT count(*) FROM t1 WHERE t1 MATCH 'c:t*'"} {1 "SELECT count(*) FROM t1 WHERE t1 MATCH 'a:t* OR b:t* OR c:t* OR d:t* OR e:t* OR f:t* OR g:t*'"} {1 "SELECT count(*) FROM t1 WHERE t1 MATCH 'a:t*'"} {2 "SELECT count(*) FROM t1 WHERE t1 MATCH 'c:the'"} } proc usage {} { global Q puts stderr "Usage: $::argv0 DATABASE QUERY" puts stderr "" for {set i 1} {$i <= [llength $Q]} {incr i} { | > > > > | 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 | {100 "SELECT count(*) FROM t1 WHERE t1 MATCH 'enron AND myapps'"} {1 "SELECT count(*) FROM t1 WHERE t1 MATCH 'en* AND my*'"} {1 "SELECT count(*) FROM t1 WHERE t1 MATCH 'c:t*'"} {1 "SELECT count(*) FROM t1 WHERE t1 MATCH 'a:t* OR b:t* OR c:t* OR d:t* OR e:t* OR f:t* OR g:t*'"} {1 "SELECT count(*) FROM t1 WHERE t1 MATCH 'a:t*'"} {2 "SELECT count(*) FROM t1 WHERE t1 MATCH 'c:the'"} {2 "SELECT count(*) FROM t1 WHERE t1 MATCH 'd:holmes OR e:holmes OR f:holmes OR g:holmes'" } {2 "SELECT count(*) FROM t1 WHERE t1 MATCH 'd:holmes AND e:holmes AND f:holmes AND g:holmes'" } {4 "SELECT count(*) FROM t1 WHERE t1 MATCH 'd:holmes NOT e:holmes'" } } proc usage {} { global Q puts stderr "Usage: $::argv0 DATABASE QUERY" puts stderr "" for {set i 1} {$i <= [llength $Q]} {incr i} { |
︙ | ︙ |