/ Check-in [ec69e09a]
Login

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

Overview
Comment:Change fts5 expression processing to avoid linear scans of long doclists caused by phrases that match specific columns only.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | fts5
Files: files | file ages | folders
SHA1: ec69e09a55b4daf1c40aeaaf9ee95091fe86f5c0
User & Date: dan 2015-06-01 09:15:20
References
2015-06-02
17:57
Reimplement [ec69e09a] so that each call to the xNext() method does not involve two iterations of the match expression tree (only one). check-in: 80fe305b user: dan tags: fts5
Context
2015-06-01
19:17
Improve performance of the fts5 AND operator. check-in: b43e9a5b user: dan tags: fts5
09:15
Change fts5 expression processing to avoid linear scans of long doclists caused by phrases that match specific columns only. check-in: ec69e09a user: dan tags: fts5
2015-05-30
11:49
Remove the "#include sqlite3Int.h" from fts5Int.h. check-in: e008c3c8 user: dan tags: fts5
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to ext/fts5/fts5_expr.c.

   649    649   ** EOF.
   650    650   */
   651    651   static int fts5ExprNearNextRowidMatch(
   652    652     Fts5Expr *pExpr,                /* Expression pPhrase belongs to */
   653    653     Fts5ExprNode *pNode
   654    654   ){
   655    655     Fts5ExprNearset *pNear = pNode->pNear;
   656         -  int rc = SQLITE_OK;
   657         -  int i, j;                       /* Phrase and token index, respectively */
   658    656     i64 iLast;                      /* Lastest rowid any iterator points to */
   659         -  int bMatch;                     /* True if all terms are at the same rowid */
          657  +  int rc = SQLITE_OK;
   660    658   
   661    659     /* Initialize iLast, the "lastest" rowid any iterator points to. If the
   662    660     ** iterator skips through rowids in the default ascending order, this means
   663    661     ** the maximum rowid. Or, if the iterator is "ORDER BY rowid DESC", then it
   664    662     ** means the minimum rowid.  */
   665    663     iLast = sqlite3Fts5IterRowid(pNear->apPhrase[0]->aTerm[0].pIter);
   666    664   
   667         -  do {
   668         -    bMatch = 1;
   669         -    for(i=0; i<pNear->nPhrase; i++){
   670         -      Fts5ExprPhrase *pPhrase = pNear->apPhrase[i];
   671         -      for(j=0; j<pPhrase->nTerm; j++){
   672         -        Fts5IndexIter *pIter = pPhrase->aTerm[j].pIter;
   673         -        i64 iRowid = sqlite3Fts5IterRowid(pIter);
   674         -        if( iRowid!=iLast ) bMatch = 0;
   675         -        if( fts5ExprAdvanceto(pIter, pExpr->bDesc, &iLast, &rc, &pNode->bEof) ){
   676         -          return rc;
          665  +  if( pNear->nPhrase>1 || pNear->apPhrase[0]->nTerm>1 ){
          666  +    int i, j;                     /* Phrase and token index, respectively */
          667  +    int bMatch;                   /* True if all terms are at the same rowid */
          668  +    do {
          669  +      bMatch = 1;
          670  +      for(i=0; i<pNear->nPhrase; i++){
          671  +        Fts5ExprPhrase *pPhrase = pNear->apPhrase[i];
          672  +        for(j=0; j<pPhrase->nTerm; j++){
          673  +          Fts5IndexIter *pIter = pPhrase->aTerm[j].pIter;
          674  +          i64 iRowid = sqlite3Fts5IterRowid(pIter);
          675  +          if( iRowid!=iLast ) bMatch = 0;
          676  +          if( fts5ExprAdvanceto(pIter, pExpr->bDesc, &iLast,&rc,&pNode->bEof) ){
          677  +            return rc;
          678  +          }
   677    679           }
   678    680         }
   679         -    }
   680         -  }while( bMatch==0 );
          681  +    }while( bMatch==0 );
          682  +  }
   681    683   
   682    684     pNode->iRowid = iLast;
   683    685     return rc;
   684    686   }
   685    687   
   686    688   /*
   687    689   ** IN/OUT parameter (*pa) points to a position list n bytes in size. If
................................................................................
   734    736       if( nSub ){
   735    737         fts5BufferAppendBlob(&rc, pBuf, nSub, pSub);
   736    738       }
   737    739     }
   738    740     return rc;
   739    741   }
   740    742   
          743  +static int fts5ExprNearTest(
          744  +  int *pRc,
          745  +  Fts5Expr *pExpr,                /* Expression that pNear is a part of */
          746  +  Fts5ExprNode *pNode             /* The "NEAR" node (FTS5_STRING) */
          747  +){
          748  +  Fts5ExprNearset *pNear = pNode->pNear;
          749  +  int rc = *pRc;
          750  +
          751  +  if( pNear->nPhrase==1 && pNear->apPhrase[0]->nTerm==1 ){
          752  +    /* If this "NEAR" object is actually a single phrase that consists 
          753  +    ** of a single term only, then grab pointers into the poslist
          754  +    ** managed by the fts5_index.c iterator object. This is much faster 
          755  +    ** than synthesizing a new poslist the way we have to for more
          756  +    ** complicated phrase or NEAR expressions.  */
          757  +    Fts5ExprPhrase *pPhrase = pNear->apPhrase[0];
          758  +    Fts5IndexIter *pIter = pPhrase->aTerm[0].pIter;
          759  +    Fts5ExprColset *pColset = pNear->pColset;
          760  +    const u8 *pPos;
          761  +    int nPos;
          762  +
          763  +    if( rc!=SQLITE_OK ) return 0;
          764  +    rc = sqlite3Fts5IterPoslist(pIter, &pPos, &nPos, &pNode->iRowid);
          765  +
          766  +    /* If the term may match any column, then this must be a match. 
          767  +    ** Return immediately in this case. Otherwise, try to find the
          768  +    ** part of the poslist that corresponds to the required column.
          769  +    ** If it can be found, return. If it cannot, the next iteration
          770  +    ** of the loop will test the next rowid in the database for this
          771  +    ** term.  */
          772  +    if( pColset==0 ){
          773  +      assert( pPhrase->poslist.nSpace==0 );
          774  +      pPhrase->poslist.p = (u8*)pPos;
          775  +      pPhrase->poslist.n = nPos;
          776  +    }else if( pColset->nCol==1 ){
          777  +      assert( pPhrase->poslist.nSpace==0 );
          778  +      pPhrase->poslist.n = fts5ExprExtractCol(&pPos, nPos, pColset->aiCol[0]);
          779  +      pPhrase->poslist.p = (u8*)pPos;
          780  +    }else if( rc==SQLITE_OK ){
          781  +      rc = fts5ExprExtractColset(pColset, pPos, nPos, &pPhrase->poslist);
          782  +    }
          783  +
          784  +    *pRc = rc;
          785  +    return (pPhrase->poslist.n>0);
          786  +  }else{
          787  +    int i;
          788  +
          789  +    /* Check that each phrase in the nearset matches the current row.
          790  +    ** Populate the pPhrase->poslist buffers at the same time. If any
          791  +    ** phrase is not a match, break out of the loop early.  */
          792  +    for(i=0; rc==SQLITE_OK && i<pNear->nPhrase; i++){
          793  +      Fts5ExprPhrase *pPhrase = pNear->apPhrase[i];
          794  +      if( pPhrase->nTerm>1 || pNear->pColset ){
          795  +        int bMatch = 0;
          796  +        rc = fts5ExprPhraseIsMatch(pExpr, pNear->pColset, pPhrase, &bMatch);
          797  +        if( bMatch==0 ) break;
          798  +      }else{
          799  +        rc = sqlite3Fts5IterPoslistBuffer(
          800  +            pPhrase->aTerm[0].pIter, &pPhrase->poslist
          801  +        );
          802  +      }
          803  +    }
          804  +
          805  +    *pRc = rc;
          806  +    if( i==pNear->nPhrase && (i==1 || fts5ExprNearIsMatch(pRc, pNear)) ){
          807  +      return 1;
          808  +    }
          809  +  }
          810  +
          811  +  return 0;
          812  +}
   741    813   
   742    814   /*
   743    815   ** Argument pNode points to a NEAR node. All individual term iterators 
   744    816   ** point to valid entries (not EOF).
   745    817   *
   746    818   ** This function tests if the term iterators currently all point to the
   747    819   ** same rowid, and if so, if the row matches the phrase and NEAR constraints. 
................................................................................
   756    828   ** otherwise. It is not considered an error code if an iterator reaches
   757    829   ** EOF.
   758    830   */
   759    831   static int fts5ExprNearNextMatch(
   760    832     Fts5Expr *pExpr,                /* Expression that pNear is a part of */
   761    833     Fts5ExprNode *pNode             /* The "NEAR" node (FTS5_STRING) */
   762    834   ){
   763         -  Fts5ExprNearset *pNear = pNode->pNear;
   764    835     int rc = SQLITE_OK;
   765    836   
          837  +  assert( pNode->pNear );
   766    838     while( 1 ){
   767    839   
   768         -    if( pNear->nPhrase==1 && pNear->apPhrase[0]->nTerm==1 ){
   769         -      /* If this "NEAR" object is actually a single phrase that consists 
   770         -      ** of a single term only, then grab pointers into the poslist
   771         -      ** managed by the fts5_index.c iterator object. This is much faster 
   772         -      ** than synthesizing a new poslist the way we have to for more
   773         -      ** complicated phrase or NEAR expressions.  */
   774         -      Fts5ExprPhrase *pPhrase = pNear->apPhrase[0];
   775         -      Fts5IndexIter *pIter = pPhrase->aTerm[0].pIter;
   776         -      Fts5ExprColset *pColset = pNear->pColset;
   777         -      const u8 *pPos;
   778         -      int nPos;
          840  +    /* Advance the iterators until they all point to the same rowid */
          841  +    rc = fts5ExprNearNextRowidMatch(pExpr, pNode);
          842  +    if( rc!=SQLITE_OK || pNode->bEof ) break;
   779    843   
   780         -      rc = sqlite3Fts5IterPoslist(pIter, &pPos, &nPos, &pNode->iRowid);
   781         -
   782         -      /* If the term may match any column, then this must be a match. 
   783         -      ** Return immediately in this case. Otherwise, try to find the
   784         -      ** part of the poslist that corresponds to the required column.
   785         -      ** If it can be found, return. If it cannot, the next iteration
   786         -      ** of the loop will test the next rowid in the database for this
   787         -      ** term.  */
   788         -      if( pColset==0 ){
   789         -        assert( pPhrase->poslist.nSpace==0 );
   790         -        pPhrase->poslist.p = (u8*)pPos;
   791         -        pPhrase->poslist.n = nPos;
   792         -      }else if( pColset->nCol==1 ){
   793         -        assert( pPhrase->poslist.nSpace==0 );
   794         -        pPhrase->poslist.n = fts5ExprExtractCol(&pPos, nPos, pColset->aiCol[0]);
   795         -        pPhrase->poslist.p = (u8*)pPos;
   796         -      }else if( rc==SQLITE_OK ){
   797         -        rc = fts5ExprExtractColset(pColset, pPos, nPos, &pPhrase->poslist);
   798         -      }
   799         -
   800         -      if( pPhrase->poslist.n ) return rc;
   801         -    }else{
   802         -      int i;
   803         -
   804         -      /* Advance the iterators until they all point to the same rowid */
   805         -      rc = fts5ExprNearNextRowidMatch(pExpr, pNode);
   806         -      if( rc!=SQLITE_OK || pNode->bEof ) break;
   807         -
   808         -      /* Check that each phrase in the nearset matches the current row.
   809         -      ** Populate the pPhrase->poslist buffers at the same time. If any
   810         -      ** phrase is not a match, break out of the loop early.  */
   811         -      for(i=0; rc==SQLITE_OK && i<pNear->nPhrase; i++){
   812         -        Fts5ExprPhrase *pPhrase = pNear->apPhrase[i];
   813         -        if( pPhrase->nTerm>1 || pNear->pColset ){
   814         -          int bMatch = 0;
   815         -          rc = fts5ExprPhraseIsMatch(pExpr, pNear->pColset, pPhrase, &bMatch);
   816         -          if( bMatch==0 ) break;
   817         -        }else{
   818         -          rc = sqlite3Fts5IterPoslistBuffer(
   819         -              pPhrase->aTerm[0].pIter, &pPhrase->poslist
   820         -          );
   821         -        }
   822         -      }
   823         -
   824         -      if( i==pNear->nPhrase ){
   825         -        if( i==1 ) break;
   826         -        if( fts5ExprNearIsMatch(&rc, pNear) ) break;
   827         -      }
   828         -    }
          844  +    if( fts5ExprNearTest(&rc, pExpr, pNode) ) break;
   829    845   
   830    846       /* If control flows to here, then the current rowid is not a match.
   831    847       ** Advance all term iterators in all phrases to the next rowid. */
   832    848       if( rc==SQLITE_OK ){
   833    849         rc = fts5ExprNearAdvanceFirst(pExpr, pNode, 0, 0);
   834    850       }
   835    851       if( pNode->bEof || rc!=SQLITE_OK ) break;
................................................................................
   938    954       switch( pNode->eType ){
   939    955         case FTS5_STRING: {
   940    956           rc = fts5ExprNearAdvanceFirst(pExpr, pNode, bFromValid, iFrom);
   941    957           break;
   942    958         };
   943    959   
   944    960         case FTS5_AND: {
   945         -        rc = fts5ExprNodeNext(pExpr, pNode->pLeft, bFromValid, iFrom);
   946         -        if( rc==SQLITE_OK ){
   947         -          /* todo: update (iFrom/bFromValid) here */
   948         -          rc = fts5ExprNodeNext(pExpr, pNode->pRight, bFromValid, iFrom);
          961  +        Fts5ExprNode *pLeft = pNode->pLeft;
          962  +        rc = fts5ExprNodeNext(pExpr, pLeft, bFromValid, iFrom);
          963  +        if( rc==SQLITE_OK && pLeft->bEof==0 ){
          964  +          assert( !bFromValid || fts5RowidCmp(pExpr, pLeft->iRowid, iFrom)>=0 );
          965  +          rc = fts5ExprNodeNext(pExpr, pNode->pRight, 1, pLeft->iRowid);
   949    966           }
   950    967           break;
   951    968         }
   952    969   
   953    970         case FTS5_OR: {
   954    971           Fts5ExprNode *p1 = pNode->pLeft;
   955    972           Fts5ExprNode *p2 = pNode->pRight;
................................................................................
   989   1006         || rc!=SQLITE_OK                                                  /* a */
   990   1007         || pNode->bEof                                                    /* b */
   991   1008         || pNode->iRowid==iFrom || pExpr->bDesc==(pNode->iRowid<iFrom)    /* c */
   992   1009     );
   993   1010   
   994   1011     return rc;
   995   1012   }
         1013  +
         1014  +static void fts5ExprNodeZeroPoslist(Fts5ExprNode *pNode){
         1015  +  if( pNode->eType==FTS5_STRING ){
         1016  +    Fts5ExprNearset *pNear = pNode->pNear;
         1017  +    int i;
         1018  +    for(i=0; i<pNear->nPhrase; i++){
         1019  +      Fts5ExprPhrase *pPhrase = pNear->apPhrase[i];
         1020  +      pPhrase->poslist.n = 0;
         1021  +    }
         1022  +  }else{
         1023  +    fts5ExprNodeZeroPoslist(pNode->pLeft);
         1024  +    fts5ExprNodeZeroPoslist(pNode->pRight);
         1025  +  }
         1026  +}
         1027  +
         1028  +static int fts5ExprNodeTest(
         1029  +  int *pRc, 
         1030  +  Fts5Expr *pExpr, 
         1031  +  i64 iRowid,
         1032  +  Fts5ExprNode *pNode
         1033  +){
         1034  +  int bRes = 0;
         1035  +  if( pNode->bEof || pNode->iRowid!=iRowid ){
         1036  +    bRes = 0;
         1037  +  }else {
         1038  +    switch( pNode->eType ){
         1039  +      case FTS5_STRING:
         1040  +        bRes = fts5ExprNearTest(pRc, pExpr, pNode);
         1041  +        if( *pRc ) bRes = 0;
         1042  +        break;
         1043  +
         1044  +      case FTS5_AND: {
         1045  +        int bRes1 = fts5ExprNodeTest(pRc, pExpr, iRowid, pNode->pLeft);
         1046  +        int bRes2 = fts5ExprNodeTest(pRc, pExpr, iRowid, pNode->pRight);
         1047  +        assert( (bRes1==0 || bRes1==1) && (bRes2==0 || bRes2==1) );
         1048  +
         1049  +        bRes = (bRes1 && bRes2);
         1050  +        if( bRes1!=bRes2 ){
         1051  +          fts5ExprNodeZeroPoslist(bRes1 ? pNode->pLeft : pNode->pRight);
         1052  +        }
         1053  +        break;
         1054  +      }
         1055  +
         1056  +      case FTS5_OR: {
         1057  +        int bRes1 = fts5ExprNodeTest(pRc, pExpr, iRowid, pNode->pLeft);
         1058  +        int bRes2 = fts5ExprNodeTest(pRc, pExpr, iRowid, pNode->pRight);
         1059  +
         1060  +        bRes = (bRes1 || bRes2);
         1061  +        break;
         1062  +      }
         1063  +
         1064  +      default:
         1065  +        assert( pNode->eType==FTS5_NOT );
         1066  +        bRes = fts5ExprNodeTest(pRc, pExpr, iRowid, pNode->pLeft);
         1067  +        break;
         1068  +    }
         1069  +  }
         1070  +
         1071  +  return bRes;
         1072  +}
         1073  +
   996   1074   
   997   1075   static void fts5ExprSetEof(Fts5ExprNode *pNode){
   998   1076     if( pNode ){
   999   1077       pNode->bEof = 1;
  1000   1078       fts5ExprSetEof(pNode->pLeft);
  1001   1079       fts5ExprSetEof(pNode->pRight);
  1002   1080     }
................................................................................
  1012   1090     Fts5ExprNode *pNode             /* Expression node to test */
  1013   1091   ){
  1014   1092     int rc = SQLITE_OK;
  1015   1093     if( pNode->bEof==0 ){
  1016   1094       switch( pNode->eType ){
  1017   1095   
  1018   1096         case FTS5_STRING: {
         1097  +#if 0
  1019   1098           rc = fts5ExprNearNextMatch(pExpr, pNode);
         1099  +#endif
         1100  +        rc = fts5ExprNearNextRowidMatch(pExpr, pNode);
  1020   1101           break;
  1021   1102         }
  1022   1103   
  1023   1104         case FTS5_AND: {
  1024   1105           Fts5ExprNode *p1 = pNode->pLeft;
  1025   1106           Fts5ExprNode *p2 = pNode->pRight;
  1026   1107   
................................................................................
  1061   1142           while( rc==SQLITE_OK && p1->bEof==0 ){
  1062   1143             int cmp = fts5NodeCompare(pExpr, p1, p2);
  1063   1144             if( cmp>0 ){
  1064   1145               rc = fts5ExprNodeNext(pExpr, p2, 1, p1->iRowid);
  1065   1146               cmp = fts5NodeCompare(pExpr, p1, p2);
  1066   1147             }
  1067   1148             assert( rc!=SQLITE_OK || cmp<=0 );
  1068         -          if( rc || cmp<0 ) break;
         1149  +          if( 0==fts5ExprNodeTest(&rc, pExpr, p1->iRowid, p2) ) break;
  1069   1150             rc = fts5ExprNodeNext(pExpr, p1, 0, 0);
  1070   1151           }
  1071   1152           pNode->bEof = p1->bEof;
  1072   1153           pNode->iRowid = p1->iRowid;
  1073   1154           break;
  1074   1155         }
  1075   1156       }
................................................................................
  1092   1173     if( pNode->eType==FTS5_STRING ){
  1093   1174   
  1094   1175       /* Initialize all term iterators in the NEAR object. */
  1095   1176       rc = fts5ExprNearInitAll(pExpr, pNode);
  1096   1177   
  1097   1178       /* Attempt to advance to the first match */
  1098   1179       if( rc==SQLITE_OK && pNode->bEof==0 ){
         1180  +#if 0
  1099   1181         rc = fts5ExprNearNextMatch(pExpr, pNode);
         1182  +#endif
         1183  +      rc = fts5ExprNearNextRowidMatch(pExpr, pNode);
  1100   1184       }
  1101   1185   
  1102   1186     }else{
  1103   1187       rc = fts5ExprNodeFirst(pExpr, pNode->pLeft);
  1104   1188       if( rc==SQLITE_OK ){
  1105   1189         rc = fts5ExprNodeFirst(pExpr, pNode->pRight);
  1106   1190       }
................................................................................
  1108   1192         rc = fts5ExprNodeNextMatch(pExpr, pNode);
  1109   1193       }
  1110   1194     }
  1111   1195     return rc;
  1112   1196   }
  1113   1197   
  1114   1198   
  1115         -
  1116   1199   /*
  1117   1200   ** Begin iterating through the set of documents in index pIdx matched by
  1118   1201   ** the MATCH expression passed as the first argument. If the "bDesc" parameter
  1119   1202   ** is passed a non-zero value, iteration is in descending rowid order. Or,
  1120   1203   ** if it is zero, in ascending order.
  1121   1204   **
  1122   1205   ** Return SQLITE_OK if successful, or an SQLite error code otherwise. It
  1123   1206   ** is not considered an error if the query does not match any documents.
  1124   1207   */
  1125   1208   int sqlite3Fts5ExprFirst(Fts5Expr *p, Fts5Index *pIdx, int bDesc){
         1209  +  Fts5ExprNode *pRoot = p->pRoot;
  1126   1210     int rc = SQLITE_OK;
  1127         -  if( p->pRoot ){
         1211  +  if( pRoot ){
  1128   1212       p->pIndex = pIdx;
  1129   1213       p->bDesc = bDesc;
  1130         -    rc = fts5ExprNodeFirst(p, p->pRoot);
         1214  +    rc = fts5ExprNodeFirst(p, pRoot);
         1215  +    if( pRoot->bEof==0 
         1216  +     && 0==fts5ExprNodeTest(&rc, p, pRoot->iRowid, pRoot) 
         1217  +     && rc==SQLITE_OK 
         1218  +    ){
         1219  +      rc = sqlite3Fts5ExprNext(p);
         1220  +    }
  1131   1221     }
  1132   1222     return rc;
  1133   1223   }
  1134   1224   
  1135   1225   /*
  1136   1226   ** Move to the next document 
  1137   1227   **
  1138   1228   ** Return SQLITE_OK if successful, or an SQLite error code otherwise. It
  1139   1229   ** is not considered an error if the query does not match any documents.
  1140   1230   */
  1141   1231   int sqlite3Fts5ExprNext(Fts5Expr *p){
  1142   1232     int rc;
  1143         -  rc = fts5ExprNodeNext(p, p->pRoot, 0, 0);
         1233  +  do {
         1234  +    rc = fts5ExprNodeNext(p, p->pRoot, 0, 0);
         1235  +  }while( p->pRoot->bEof==0 
         1236  +      && fts5ExprNodeTest(&rc, p, p->pRoot->iRowid, p->pRoot)==0 
         1237  +      && rc==SQLITE_OK 
         1238  +  );
  1144   1239     return rc;
  1145   1240   }
  1146   1241   
  1147   1242   int sqlite3Fts5ExprEof(Fts5Expr *p){
  1148   1243     return (p->pRoot==0 || p->pRoot->bEof);
  1149   1244   }
  1150   1245   

Changes to ext/fts5/test/fts5_common.tcl.

   275    275     if {[llength $a]==0 || [llength $b]==0} { return [list] }
   276    276     sort_poslist [concat $a $b]
   277    277   }
   278    278   proc OR {a b} {
   279    279     sort_poslist [concat $a $b]
   280    280   }
   281    281   proc NOT {a b} {
   282         -  if {[llength $b]} { return [list] }
          282  +  if {[llength $b]>0} { return [list] }
   283    283     return $a
   284    284   }
   285    285   

Changes to ext/fts5/test/fts5auto.test.

   222    222       {d}                             {j x i b x u y d c p v a h}   
   223    223       2391989
   224    224       {b n w x w f q h p i}           {e u b b i n a i o c d g}     
   225    225       {v a z o i e n l x l r}         {r u f o r k w m d w}         
   226    226       {k s}                           {r f e j q p w}               
   227    227   }
   228    228   
   229         -do_test 1.0 {
   230         -  execsql {
   231         -    BEGIN;
   232         -    CREATE VIRTUAL TABLE tt USING fts5(a, b, c, d, e, f);
   233         -  }
   234         -  foreach {rowid a b c d e f} $data {
   235         -    execsql {
   236         -      INSERT INTO tt(rowid, a, b, c, d, e, f) 
   237         -      VALUES($rowid, $a, $b, $c, $d, $e, $f)
   238         -    }
   239         -  }
   240         -  execsql {
   241         -    COMMIT;
   242         -  }
          229  +do_execsql_test 1.0 {
          230  +  CREATE VIRTUAL TABLE tt USING fts5(a, b, c, d, e, f);
   243    231   } {}
   244    232   
   245         -proc fts5_test_poslist {cmd} {
   246         -  set res [list]
   247         -  for {set i 0} {$i < [$cmd xInstCount]} {incr i} {
   248         -    lappend res [string map {{ } .} [$cmd xInst $i]]
   249         -  }
   250         -  set res
   251         -}
   252         -sqlite3_fts5_create_function db fts5_test_poslist fts5_test_poslist
          233  +fts5_aux_test_functions db
   253    234   
   254         -proc matchdata {expr} {
          235  +proc matchdata {expr {order ASC}} {
   255    236     set tclexpr [db one {
   256    237       SELECT fts5_expr_tcl(
   257    238         $expr, 'nearset $cols -pc ::pc', 'a','b','c','d','e','f'
   258    239       )
   259    240     }]
   260    241     set res [list]
   261    242   
   262         -  db eval {SELECT rowid, * FROM tt} {
          243  +  db eval "SELECT rowid, * FROM tt ORDER BY rowid $order" {
   263    244       set cols [list $a $b $c $d $e $f]
   264    245       set ::pc 0
   265    246       set rowdata [eval $tclexpr]
   266         -
   267         -    if {$rowdata != ""} {
   268         -      lappend res $rowid $rowdata
   269         -    }
          247  +    if {$rowdata != ""} { lappend res $rowid $rowdata }
   270    248     }
   271    249   
   272    250     set res
   273    251   }
          252  +
          253  +proc do_auto_test {tn expr} { 
          254  +  foreach order {asc desc} {
          255  +    set res [matchdata $expr $order]
          256  +    set testname "3.$tn.[string range $order 0 0].rows=[expr [llength $res]/2]"
          257  +
          258  +    set ::autotest_expr $expr
          259  +    do_execsql_test $testname [subst -novar {
          260  +      SELECT rowid, fts5_test_poslist(tt) FROM tt 
          261  +      WHERE tt MATCH $::autotest_expr ORDER BY rowid [set order]
          262  +    }] $res
          263  +  }
          264  +
          265  +
          266  +}
   274    267   
   275    268   #-------------------------------------------------------------------------
   276    269   #
   277    270   
   278         -do_execsql_test 2.0 {
   279         -  SELECT rowid, fts5_test_poslist(tt) FROM tt WHERE tt MATCH 'a AND b';
   280         -} [matchdata "a AND b"]
          271  +for {set fold 0} {$fold < 3} {incr fold} {
          272  +  switch $fold {
          273  +    0 { set map {} }
          274  +    1 { set map {
          275  +      a a  b a  c b  d b  e c  f c  g d  h d  
          276  +      i e  j e  k f  l f  m g  g g  o h  p h
          277  +      q i  r i  s j  t j  u k  v k  w l  x l
          278  +      y m  z m
          279  +    }}
   281    280   
   282         -do_test 2.1 {
   283         -  llength [matchdata "a AND b"]
   284         -} 62
          281  +    2 { set map {
          282  +      a a  b a  c a  d a  e a  f a  g a  h a  
          283  +      i b  j b  k b  l b  m b  g b  o b  p b
          284  +      q c  r c  s c  t c  u c  v c  w c  x c
          285  +    }}
          286  +  }
   285    287   
   286         -foreach {tn expr} {
   287         -  1 { [a] : x }
   288         -  2 { [a b] : x }
   289         -  3 { [a b f] : x }
   290         -  4 { [f a b] : x }
   291         -  5 { [f a b] : x y }
   292         -  6 { [f a b] : x + y }
   293         -  7 { [c a b] : x + c }
   294         -  8 { [c d] : "l m" }
   295         -  9 { [c e] : "l m" }
   296         -} {
   297         -  set res [matchdata $expr]
   298         -  do_test 3.$tn.[llength $res] {
          288  +  execsql {
          289  +    BEGIN;
          290  +    DELETE FROM tt;
          291  +  }
          292  +  foreach {rowid a b c d e f} [string map $map $data] {
   299    293       execsql {
   300         -      SELECT rowid, fts5_test_poslist(tt) FROM tt WHERE tt MATCH $expr
          294  +      INSERT INTO tt(rowid, a, b, c, d, e, f) 
          295  +      VALUES($rowid, $a, $b, $c, $d, $e, $f)
   301    296       }
   302         -  } $res
   303         -}
          297  +  }
          298  +  execsql COMMIT
          299  +
          300  +
          301  +  foreach {tn expr} {
          302  +    3.1 { [a] : x }
          303  +    3.2 { [a b] : x }
          304  +    3.3 { [a b f] : x }
          305  +    3.4 { [f a b] : x }
          306  +    3.5 { [f a b] : x y }
          307  +    3.6 { [f a b] : x + y }
          308  +    3.7 { [c a b] : x + c }
          309  +    3.8 { [c d] : "l m" }
          310  +    3.9 { [c e] : "l m" }
          311  +
          312  +    4.1 { a NOT b }
          313  +    4.2 { a NOT a:b }
          314  +    4.3 { a OR (b AND c) }
          315  +    4.4 { a OR (b AND [a b c]:c) }
          316  +    4.5 { a OR "b c" }
          317  +    4.6 { a OR b OR c }
   304    318   
          319  +    5.1 { a OR (b AND "b c") }
          320  +    5.2 { a OR (b AND "z c") }
          321  +  } {
          322  +    do_auto_test 3.$fold.$tn $expr
          323  +  }
          324  +}
   305    325   
   306    326   finish_test
   307    327