/ Check-in [b43e9a5b]
Login

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

Overview
Comment:Improve performance of the fts5 AND operator.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | fts5
Files: files | file ages | folders
SHA1: b43e9a5b7a0483ccb102316a4dbc5e32b5bc69ec
User & Date: dan 2015-06-01 19:17:06
Context
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
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
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to ext/fts5/fts5_expr.c.

40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58






59
60
61
62
63
64
65
...
311
312
313
314
315
316
317
318

319

320
321
322
323
324
325
326
...
680
681
682
683
684
685
686

687
688
689
690
691
692
693
...
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
...
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
....
1016
1017
1018
1019
1020
1021
1022
1023

1024

1025
1026
1027
1028
1029
1030
1031
....
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
....
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
1142
1143
1144
1145
1146
1147
....
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190


1191
1192
1193
1194
1195
1196
1197
....
1226
1227
1228
1229
1230
1231
1232

1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
....
1573
1574
1575
1576
1577
1578
1579











1580
1581
1582
1583
1584
1585
1586
....
1588
1589
1590
1591
1592
1593
1594



1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608






1609
1610
1611
1612
1613
1614



1615
1616
1617
1618
1619
1620
1621
....
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739



1740
1741
1742
1743
1744
1745
1746
....
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790

1791
1792
1793
1794
1795
1796
1797
1798
1799
1800
1801
1802
1803


1804
1805
1806
1807
1808

1809
1810
1811
1812

1813
1814
1815
1816
1817
1818
1819
  Fts5ExprPhrase **apExprPhrase;  /* Pointers to phrase objects */
};

/*
** eType:
**   Expression node type. Always one of:
**
**       FTS5_AND                 (pLeft, pRight valid)
**       FTS5_OR                  (pLeft, pRight valid)
**       FTS5_NOT                 (pLeft, pRight valid)
**       FTS5_STRING              (pNear valid)
*/
struct Fts5ExprNode {
  int eType;                      /* Node type */
  Fts5ExprNode *pLeft;            /* Left hand child node */
  Fts5ExprNode *pRight;           /* Right hand child node */
  Fts5ExprNearset *pNear;         /* For FTS5_STRING - cluster of phrases */
  int bEof;                       /* True at EOF */
  i64 iRowid;                     /* Current rowid */






};

/*
** An instance of the following structure represents a single search term
** or term prefix.
*/
struct Fts5ExprTerm {
................................................................................
}

/*
** Free the expression node object passed as the only argument.
*/
void sqlite3Fts5ParseNodeFree(Fts5ExprNode *p){
  if( p ){
    sqlite3Fts5ParseNodeFree(p->pLeft);

    sqlite3Fts5ParseNodeFree(p->pRight);

    sqlite3Fts5ParseNearsetFree(p->pNear);
    sqlite3_free(p);
  }
}

/*
** Free the expression object passed as the only argument.
................................................................................
      }
    }while( bMatch==0 );
  }

  pNode->iRowid = iLast;
  return rc;
}


/*
** IN/OUT parameter (*pa) points to a position list n bytes in size. If
** the position list contains entries for column iCol, then (*pa) is set
** to point to the sub-position-list for that column and the number of
** bytes in it returned. Or, if the argument position list does not
** contain any entries for column iCol, return 0.
................................................................................
  return rc;
}

/* fts5ExprNodeNext() calls fts5ExprNodeNextMatch(). And vice-versa. */
static int fts5ExprNodeNextMatch(Fts5Expr*, Fts5ExprNode*);












static int fts5RowidCmp(
  Fts5Expr *pExpr,
  i64 iLhs,
  i64 iRhs
){
  assert( pExpr->bDesc==0 || pExpr->bDesc==1 );
  if( pExpr->bDesc==0 ){
................................................................................
    if( iLhs<iRhs ) return -1;
    return (iLhs > iRhs);
  }else{
    if( iLhs>iRhs ) return -1;
    return (iLhs < iRhs);
  }
}































































/*
** 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
................................................................................
    switch( pNode->eType ){
      case FTS5_STRING: {
        rc = fts5ExprNearAdvanceFirst(pExpr, pNode, bFromValid, iFrom);
        break;
      };

      case FTS5_AND: {
        Fts5ExprNode *pLeft = pNode->pLeft;
        rc = fts5ExprNodeNext(pExpr, pLeft, bFromValid, iFrom);
        if( rc==SQLITE_OK && pLeft->bEof==0 ){
          assert( !bFromValid || fts5RowidCmp(pExpr, pLeft->iRowid, iFrom)>=0 );
          rc = fts5ExprNodeNext(pExpr, pNode->pRight, 1, pLeft->iRowid);
        }
        break;
      }

      case FTS5_OR: {
        Fts5ExprNode *p1 = pNode->pLeft;
        Fts5ExprNode *p2 = pNode->pRight;
        int cmp = fts5NodeCompare(pExpr, p1, p2);






        if( cmp<=0 || (bFromValid && fts5RowidCmp(pExpr,p1->iRowid,iFrom)<0) ){

          rc = fts5ExprNodeNext(pExpr, p1, bFromValid, iFrom);
        }

        if( cmp>=0 || (bFromValid && fts5RowidCmp(pExpr,p2->iRowid,iFrom)<0) ){
          if( rc==SQLITE_OK ){
            rc = fts5ExprNodeNext(pExpr, p2, bFromValid, iFrom);
          }
        }

        break;
      }

      default: assert( pNode->eType==FTS5_NOT ); {

        rc = fts5ExprNodeNext(pExpr, pNode->pLeft, bFromValid, iFrom);
        break;
      }
    }

    if( rc==SQLITE_OK ){
      rc = fts5ExprNodeNextMatch(pExpr, pNode);
    }
................................................................................
    Fts5ExprNearset *pNear = pNode->pNear;
    int i;
    for(i=0; i<pNear->nPhrase; i++){
      Fts5ExprPhrase *pPhrase = pNear->apPhrase[i];
      pPhrase->poslist.n = 0;
    }
  }else{
    fts5ExprNodeZeroPoslist(pNode->pLeft);

    fts5ExprNodeZeroPoslist(pNode->pRight);

  }
}

static int fts5ExprNodeTest(
  int *pRc, 
  Fts5Expr *pExpr, 
  i64 iRowid,
................................................................................
    switch( pNode->eType ){
      case FTS5_STRING:
        bRes = fts5ExprNearTest(pRc, pExpr, pNode);
        if( *pRc ) bRes = 0;
        break;

      case FTS5_AND: {
        int bRes1 = fts5ExprNodeTest(pRc, pExpr, iRowid, pNode->pLeft);

        int bRes2 = fts5ExprNodeTest(pRc, pExpr, iRowid, pNode->pRight);
        assert( (bRes1==0 || bRes1==1) && (bRes2==0 || bRes2==1) );


        bRes = (bRes1 && bRes2);


        if( bRes1!=bRes2 ){

          fts5ExprNodeZeroPoslist(bRes1 ? pNode->pLeft : pNode->pRight);
        }


        break;
      }

      case FTS5_OR: {
        int bRes1 = fts5ExprNodeTest(pRc, pExpr, iRowid, pNode->pLeft);

        int bRes2 = fts5ExprNodeTest(pRc, pExpr, iRowid, pNode->pRight);


        bRes = (bRes1 || bRes2);

        break;
      }

      default:
        assert( pNode->eType==FTS5_NOT );

        bRes = fts5ExprNodeTest(pRc, pExpr, iRowid, pNode->pLeft);
        break;
    }
  }

  return bRes;
}


static void fts5ExprSetEof(Fts5ExprNode *pNode){
  if( pNode ){
    pNode->bEof = 1;
    fts5ExprSetEof(pNode->pLeft);
    fts5ExprSetEof(pNode->pRight);
  }
}

/*
** 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 fts5ExprNodeNextMatch(
  Fts5Expr *pExpr,                /* Expression of which pNode is a part */
................................................................................
        rc = fts5ExprNearNextMatch(pExpr, pNode);
#endif
        rc = fts5ExprNearNextRowidMatch(pExpr, pNode);
        break;
      }

      case FTS5_AND: {
        Fts5ExprNode *p1 = pNode->pLeft;
        Fts5ExprNode *p2 = pNode->pRight;

        while( p1->bEof==0 && p2->bEof==0 && p2->iRowid!=p1->iRowid ){
          Fts5ExprNode *pAdv;
          i64 iFrom;
          assert( pExpr->bDesc==0 || pExpr->bDesc==1 );
          if( pExpr->bDesc==(p1->iRowid > p2->iRowid) ){
            pAdv = p1;
            iFrom = p2->iRowid;
          }else{
            pAdv = p2;
            iFrom = p1->iRowid;
          }
          rc = fts5ExprNodeNext(pExpr, pAdv, 1, iFrom);
          if( rc!=SQLITE_OK ) break;
        }
        if( p1->bEof || p2->bEof ){
          fts5ExprSetEof(pNode);
        }
        pNode->iRowid = p1->iRowid;
        break;
      }

      case FTS5_OR: {
        Fts5ExprNode *p1 = pNode->pLeft;


        Fts5ExprNode *p2 = pNode->pRight;
        Fts5ExprNode *pNext = (fts5NodeCompare(pExpr, p1, p2) > 0 ? p2 : p1);
        pNode->bEof = pNext->bEof;



        pNode->iRowid = pNext->iRowid;

        break;
      }

      default: assert( pNode->eType==FTS5_NOT ); {
        Fts5ExprNode *p1 = pNode->pLeft;
        Fts5ExprNode *p2 = pNode->pRight;


        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);
          }
................................................................................
#if 0
      rc = fts5ExprNearNextMatch(pExpr, pNode);
#endif
      rc = fts5ExprNearNextRowidMatch(pExpr, pNode);
    }

  }else{
    rc = fts5ExprNodeFirst(pExpr, pNode->pLeft);
    if( rc==SQLITE_OK ){
      rc = fts5ExprNodeFirst(pExpr, pNode->pRight);
    }


    if( rc==SQLITE_OK ){
      rc = fts5ExprNodeNextMatch(pExpr, pNode);
    }
  }
  return rc;
}

................................................................................
** Move to the next document 
**
** Return SQLITE_OK if successful, or an SQLite error code otherwise. It
** is not considered an error if the query does not match any documents.
*/
int sqlite3Fts5ExprNext(Fts5Expr *p){
  int rc;

  do {
    rc = fts5ExprNodeNext(p, p->pRoot, 0, 0);
  }while( p->pRoot->bEof==0 
      && fts5ExprNodeTest(&rc, p, p->pRoot->iRowid, p->pRoot)==0 
      && rc==SQLITE_OK 
  );
  return rc;
}

int sqlite3Fts5ExprEof(Fts5Expr *p){
  return (p->pRoot==0 || p->pRoot->bEof);
................................................................................
){
  if( pNear ){
    pNear->pColset = pColset;
  }else{
    sqlite3_free(pColset);
  }
}












/*
** Allocate and return a new expression object. If anything goes wrong (i.e.
** OOM error), leave an error code in pParse and return NULL.
*/
Fts5ExprNode *sqlite3Fts5ParseNode(
  Fts5Parse *pParse,              /* Parse context */
................................................................................
  Fts5ExprNode *pLeft,            /* Left hand child expression */
  Fts5ExprNode *pRight,           /* Right hand child expression */
  Fts5ExprNearset *pNear          /* For STRING expressions, the near cluster */
){
  Fts5ExprNode *pRet = 0;

  if( pParse->rc==SQLITE_OK ){



    assert( (eType!=FTS5_STRING && !pNear)
        || (eType==FTS5_STRING && !pLeft && !pRight)
    );
    if( eType==FTS5_STRING && pNear==0 ) return 0;
    if( eType!=FTS5_STRING && pLeft==0 ) return pRight;
    if( eType!=FTS5_STRING && pRight==0 ) return pLeft;
    pRet = (Fts5ExprNode*)sqlite3_malloc(sizeof(Fts5ExprNode));
    if( pRet==0 ){
      pParse->rc = SQLITE_NOMEM;
    }else{
      memset(pRet, 0, sizeof(*pRet));
      pRet->eType = eType;
      pRet->pLeft = pLeft;
      pRet->pRight = pRight;






      pRet->pNear = pNear;
      if( eType==FTS5_STRING ){
        int iPhrase;
        for(iPhrase=0; iPhrase<pNear->nPhrase; iPhrase++){
          pNear->apPhrase[iPhrase]->pNode = pRet;
        }



      }
    }
  }

  if( pRet==0 ){
    assert( pParse->rc!=SQLITE_OK );
    sqlite3Fts5ParseNodeFree(pLeft);
................................................................................
      if( zRet ) zRet = fts5PrintfAppend(zRet, "}");
      if( zRet==0 ) return 0;
    }

    if( zRet==0 ) return 0;

  }else{
    char *zOp = 0;
    char *z1 = 0;
    char *z2 = 0;
    switch( pExpr->eType ){
      case FTS5_AND: zOp = "AND"; break;
      case FTS5_NOT: zOp = "NOT"; break;
      default: 
        assert( pExpr->eType==FTS5_OR );
        zOp = "OR"; 
        break;
    }

    z1 = fts5ExprPrintTcl(pConfig, zNearsetCmd, pExpr->pLeft);
    z2 = fts5ExprPrintTcl(pConfig, zNearsetCmd, pExpr->pRight);
    if( z1 && z2 ){
      zRet = sqlite3_mprintf("%s [%s] [%s]", zOp, z1, z2);
    }
    sqlite3_free(z1);
    sqlite3_free(z2);



  }

  return zRet;
}

static char *fts5ExprPrint(Fts5Config *pConfig, Fts5ExprNode *pExpr){
  char *zRet = 0;
................................................................................

    if( pNear->nPhrase>1 ){
      zRet = fts5PrintfAppend(zRet, ", %d)", pNear->nNear);
      if( zRet==0 ) return 0;
    }

  }else{
    char *zOp = 0;
    char *z1 = 0;
    char *z2 = 0;

    switch( pExpr->eType ){
      case FTS5_AND: zOp = "AND"; break;
      case FTS5_NOT: zOp = "NOT"; break;
      default:  
        assert( pExpr->eType==FTS5_OR );
        zOp = "OR"; 
        break;
    }

    z1 = fts5ExprPrint(pConfig, pExpr->pLeft);
    z2 = fts5ExprPrint(pConfig, pExpr->pRight);
    if( z1 && z2 ){
      int b1 = pExpr->pLeft->eType!=FTS5_STRING;


      int b2 = pExpr->pRight->eType!=FTS5_STRING;
      zRet = sqlite3_mprintf("%s%s%s %s %s%s%s", 
          b1 ? "(" : "", z1, b1 ? ")" : "",
          zOp, 
          b2 ? "(" : "", z2, b2 ? ")" : ""

      );
    }
    sqlite3_free(z1);
    sqlite3_free(z2);

  }

  return zRet;
}

/*
** The implementation of user-defined scalar functions fts5_expr() (bTcl==0)







|
|
|




<
<
<


>
>
>
>
>
>







 







|
>
|
>







 







>







 







>
>
>
>
>
>
>
>
>
>







 







>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>







 







|

<
<
<
<




|
|
<

>
>
>
>
>
|
>
|
|
<
<
<
<







>
|







 







|
>
|
>







 







|
>
|
<
>
|
<
>
>
|
>
|
|
>
>




|
>
|
>
|
<
>





>
|








<
<
<
<
<
<
<
<







 







|
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<




|
>
>
|
|
<
>
>
>

>




|
|
>







 







|
|
|

>
>







 







>

|
|
|







 







>
>
>
>
>
>
>
>
>
>
>







 







>
>
>

|




|
|
|
|
|
|
|
|
>
>
>
>
>
>






>
>
>







 







|
|
<









|
|
|
|
|
|
|
>
>
>







 







|
|
<
>

|
|


|



|
|
|
|
>
>
|
<
<
|
|
>
|
|
<
|
>







40
41
42
43
44
45
46
47
48
49
50
51
52
53



54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
...
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
...
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
...
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
....
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
....
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
....
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
1142
1143
1144

1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160








1161
1162
1163
1164
1165
1166
1167
....
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
....
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
....
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
....
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
....
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
....
1804
1805
1806
1807
1808
1809
1810
1811
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
....
1873
1874
1875
1876
1877
1878
1879
1880
1881

1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898


1899
1900
1901
1902
1903

1904
1905
1906
1907
1908
1909
1910
1911
1912
  Fts5ExprPhrase **apExprPhrase;  /* Pointers to phrase objects */
};

/*
** eType:
**   Expression node type. Always one of:
**
**       FTS5_AND                 (nChild, apChild valid)
**       FTS5_OR                  (nChild, apChild valid)
**       FTS5_NOT                 (nChild, apChild valid)
**       FTS5_STRING              (pNear valid)
*/
struct Fts5ExprNode {
  int eType;                      /* Node type */



  int bEof;                       /* True at EOF */
  i64 iRowid;                     /* Current rowid */
  Fts5ExprNearset *pNear;         /* For FTS5_STRING - cluster of phrases */

  /* Child nodes. For a NOT node, this array always contains 2 entries. For 
  ** AND or OR nodes, it contains 2 or more entries.  */
  int nChild;                     /* Number of child nodes */
  Fts5ExprNode *apChild[0];       /* Array of child nodes */
};

/*
** An instance of the following structure represents a single search term
** or term prefix.
*/
struct Fts5ExprTerm {
................................................................................
}

/*
** Free the expression node object passed as the only argument.
*/
void sqlite3Fts5ParseNodeFree(Fts5ExprNode *p){
  if( p ){
    int i;
    for(i=0; i<p->nChild; i++){
      sqlite3Fts5ParseNodeFree(p->apChild[i]);
    }
    sqlite3Fts5ParseNearsetFree(p->pNear);
    sqlite3_free(p);
  }
}

/*
** Free the expression object passed as the only argument.
................................................................................
      }
    }while( bMatch==0 );
  }

  pNode->iRowid = iLast;
  return rc;
}


/*
** IN/OUT parameter (*pa) points to a position list n bytes in size. If
** the position list contains entries for column iCol, then (*pa) is set
** to point to the sub-position-list for that column and the number of
** bytes in it returned. Or, if the argument position list does not
** contain any entries for column iCol, return 0.
................................................................................
  return rc;
}

/* fts5ExprNodeNext() calls fts5ExprNodeNextMatch(). And vice-versa. */
static int fts5ExprNodeNextMatch(Fts5Expr*, Fts5ExprNode*);


/*
** If pExpr is an ASC iterator, this function returns a value with the
** same sign as:
**
**   (iLhs - iRhs)
**
** Otherwise, if this is a DESC iterator, the opposite is returned:
**
**   (iRhs - iLhs)
*/
static int fts5RowidCmp(
  Fts5Expr *pExpr,
  i64 iLhs,
  i64 iRhs
){
  assert( pExpr->bDesc==0 || pExpr->bDesc==1 );
  if( pExpr->bDesc==0 ){
................................................................................
    if( iLhs<iRhs ) return -1;
    return (iLhs > iRhs);
  }else{
    if( iLhs>iRhs ) return -1;
    return (iLhs < iRhs);
  }
}

static void fts5ExprSetEof(Fts5ExprNode *pNode){
  if( pNode ){
    int i;
    pNode->bEof = 1;
    for(i=0; i<pNode->nChild; i++){
      fts5ExprSetEof(pNode->apChild[i]);
    }
  }
}


static int fts5ExprNodeNext(Fts5Expr*, Fts5ExprNode*, int, i64);

/*
** Argument pNode is an FTS5_AND node.
*/
static int fts5ExprAndNextRowid(
  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 {
    bMatch = 1;
    for(iChild=0; iChild<pAnd->nChild; iChild++){
      Fts5ExprNode *pChild = pAnd->apChild[iChild];
      if( 0 && pChild->eType==FTS5_STRING ){
        /* TODO */
      }else{
        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 );
      if( pChild->bEof ){
        fts5ExprSetEof(pAnd);
        bMatch = 1;
        break;
      }else if( iLast!=pChild->iRowid ){
        bMatch = 0;
        iLast = pChild->iRowid;
      }
    }
  }while( bMatch==0 );

  pAnd->iRowid = iLast;
  return SQLITE_OK;
}


/*
** 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
................................................................................
    switch( pNode->eType ){
      case FTS5_STRING: {
        rc = fts5ExprNearAdvanceFirst(pExpr, pNode, bFromValid, iFrom);
        break;
      };

      case FTS5_AND: {
        Fts5ExprNode *pLeft = pNode->apChild[0];
        rc = fts5ExprNodeNext(pExpr, pLeft, bFromValid, iFrom);




        break;
      }

      case FTS5_OR: {
        int i;
        int iLast = pNode->iRowid;


        for(i=0; rc==SQLITE_OK && 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)
            ){
              rc = fts5ExprNodeNext(pExpr, p1, bFromValid, iFrom);
            }




          }
        }

        break;
      }

      default: assert( pNode->eType==FTS5_NOT ); {
        assert( pNode->nChild==2 );
        rc = fts5ExprNodeNext(pExpr, pNode->apChild[0], bFromValid, iFrom);
        break;
      }
    }

    if( rc==SQLITE_OK ){
      rc = fts5ExprNodeNextMatch(pExpr, pNode);
    }
................................................................................
    Fts5ExprNearset *pNear = pNode->pNear;
    int i;
    for(i=0; i<pNear->nPhrase; i++){
      Fts5ExprPhrase *pPhrase = pNear->apPhrase[i];
      pPhrase->poslist.n = 0;
    }
  }else{
    int i;
    for(i=0; i<pNode->nChild; i++){
      fts5ExprNodeZeroPoslist(pNode->apChild[i]);
    }
  }
}

static int fts5ExprNodeTest(
  int *pRc, 
  Fts5Expr *pExpr, 
  i64 iRowid,
................................................................................
    switch( pNode->eType ){
      case FTS5_STRING:
        bRes = fts5ExprNearTest(pRc, pExpr, pNode);
        if( *pRc ) bRes = 0;
        break;

      case FTS5_AND: {
        int i;
        for(i=0; i<pNode->nChild; i++){
          if( fts5ExprNodeTest(pRc, pExpr, iRowid, pNode->apChild[i])==0 ){

            break;
          }

        }
        bRes = (i==pNode->nChild);
        if( bRes==0 && i>0 ){
          for(i=0; i<pNode->nChild; i++){
            fts5ExprNodeZeroPoslist(pNode->apChild[i]);
          }
        }

        break;
      }

      case FTS5_OR: {
        int i;
        for(i=0; i<pNode->nChild; i++){
          if( fts5ExprNodeTest(pRc, pExpr, iRowid, pNode->apChild[i]) ){
            bRes = 1;
          }

        }
        break;
      }

      default:
        assert( pNode->eType==FTS5_NOT );
        assert( pNode->nChild==2 );
        bRes = fts5ExprNodeTest(pRc, pExpr, iRowid, pNode->apChild[0]);
        break;
    }
  }

  return bRes;
}










/*
** 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 fts5ExprNodeNextMatch(
  Fts5Expr *pExpr,                /* Expression of which pNode is a part */
................................................................................
        rc = fts5ExprNearNextMatch(pExpr, pNode);
#endif
        rc = fts5ExprNearNextRowidMatch(pExpr, pNode);
        break;
      }

      case FTS5_AND: {
        rc = fts5ExprAndNextRowid(pExpr, pNode);




















        break;
      }

      case FTS5_OR: {
        Fts5ExprNode *pNext = pNode->apChild[0];
        int i;
        for(i=1; i<pNode->nChild; i++){
          Fts5ExprNode *pChild = pNode->apChild[i];
          if( fts5NodeCompare(pExpr, pNext, pChild)>0 ){

            pNext = pChild;
          }
        }
        pNode->iRowid = pNext->iRowid;
        pNode->bEof = pNext->bEof;
        break;
      }

      default: assert( pNode->eType==FTS5_NOT ); {
        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);
          }
................................................................................
#if 0
      rc = fts5ExprNearNextMatch(pExpr, pNode);
#endif
      rc = fts5ExprNearNextRowidMatch(pExpr, pNode);
    }

  }else{
    int i;
    for(i=0; i<pNode->nChild && rc==SQLITE_OK; i++){
      rc = fts5ExprNodeFirst(pExpr, pNode->apChild[i]);
    }

    pNode->iRowid = pNode->apChild[0]->iRowid;
    if( rc==SQLITE_OK ){
      rc = fts5ExprNodeNextMatch(pExpr, pNode);
    }
  }
  return rc;
}

................................................................................
** Move to the next document 
**
** Return SQLITE_OK if successful, or an SQLite error code otherwise. It
** is not considered an error if the query does not match any documents.
*/
int sqlite3Fts5ExprNext(Fts5Expr *p){
  int rc;
  Fts5ExprNode *pRoot = p->pRoot;
  do {
    rc = fts5ExprNodeNext(p, pRoot, 0, 0);
  }while( pRoot->bEof==0 
      && fts5ExprNodeTest(&rc, p, pRoot->iRowid, p->pRoot)==0 
      && rc==SQLITE_OK 
  );
  return rc;
}

int sqlite3Fts5ExprEof(Fts5Expr *p){
  return (p->pRoot==0 || p->pRoot->bEof);
................................................................................
){
  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);
  }else{
    p->apChild[p->nChild++] = pSub;
  }
}

/*
** Allocate and return a new expression object. If anything goes wrong (i.e.
** OOM error), leave an error code in pParse and return NULL.
*/
Fts5ExprNode *sqlite3Fts5ParseNode(
  Fts5Parse *pParse,              /* Parse context */
................................................................................
  Fts5ExprNode *pLeft,            /* Left hand child expression */
  Fts5ExprNode *pRight,           /* Right hand child expression */
  Fts5ExprNearset *pNear          /* For STRING expressions, the near cluster */
){
  Fts5ExprNode *pRet = 0;

  if( pParse->rc==SQLITE_OK ){
    int nChild = 0;               /* Number of children of returned node */
    int nByte;                    /* Bytes of space to allocate for this node */
 
    assert( (eType!=FTS5_STRING && !pNear)
         || (eType==FTS5_STRING && !pLeft && !pRight)
    );
    if( eType==FTS5_STRING && pNear==0 ) return 0;
    if( eType!=FTS5_STRING && pLeft==0 ) return pRight;
    if( eType!=FTS5_STRING && pRight==0 ) return pLeft;

    if( eType==FTS5_NOT ){
      nChild = 2;
    }else if( eType==FTS5_AND || eType==FTS5_OR ){
      nChild = 2;
      if( pLeft->eType==eType ) nChild += pLeft->nChild-1;
      if( pRight->eType==eType ) nChild += pRight->nChild-1;
    }

    nByte = sizeof(Fts5ExprNode) + sizeof(Fts5ExprNode*)*nChild;
    pRet = (Fts5ExprNode*)sqlite3Fts5MallocZero(&pParse->rc, nByte);

    if( pRet ){
      pRet->eType = eType;
      pRet->pNear = pNear;
      if( eType==FTS5_STRING ){
        int iPhrase;
        for(iPhrase=0; iPhrase<pNear->nPhrase; iPhrase++){
          pNear->apPhrase[iPhrase]->pNode = pRet;
        }
      }else{
        fts5ExprAddChildren(pRet, pLeft);
        fts5ExprAddChildren(pRet, pRight);
      }
    }
  }

  if( pRet==0 ){
    assert( pParse->rc!=SQLITE_OK );
    sqlite3Fts5ParseNodeFree(pLeft);
................................................................................
      if( zRet ) zRet = fts5PrintfAppend(zRet, "}");
      if( zRet==0 ) return 0;
    }

    if( zRet==0 ) return 0;

  }else{
    char const *zOp = 0;
    int i;

    switch( pExpr->eType ){
      case FTS5_AND: zOp = "AND"; break;
      case FTS5_NOT: zOp = "NOT"; break;
      default: 
        assert( pExpr->eType==FTS5_OR );
        zOp = "OR"; 
        break;
    }

    zRet = sqlite3_mprintf("%s", zOp);
    for(i=0; zRet && i<pExpr->nChild; i++){
      char *z = fts5ExprPrintTcl(pConfig, zNearsetCmd, pExpr->apChild[i]);
      if( !z ){
        sqlite3_free(zRet);
        zRet = 0;
      }else{
        zRet = fts5PrintfAppend(zRet, " [%z]", z);
      }
    }
  }

  return zRet;
}

static char *fts5ExprPrint(Fts5Config *pConfig, Fts5ExprNode *pExpr){
  char *zRet = 0;
................................................................................

    if( pNear->nPhrase>1 ){
      zRet = fts5PrintfAppend(zRet, ", %d)", pNear->nNear);
      if( zRet==0 ) return 0;
    }

  }else{
    char const *zOp = 0;
    int i;


    switch( pExpr->eType ){
      case FTS5_AND: zOp = " AND "; break;
      case FTS5_NOT: zOp = " NOT "; break;
      default:  
        assert( pExpr->eType==FTS5_OR );
        zOp = " OR "; 
        break;
    }

    for(i=0; i<pExpr->nChild; i++){
      char *z = fts5ExprPrint(pConfig, pExpr->apChild[i]);
      if( z==0 ){
        sqlite3_free(zRet);
        zRet = 0;
      }else{
        int b = (pExpr->apChild[i]->eType!=FTS5_STRING);


        zRet = fts5PrintfAppend(zRet, "%s%s%z%s", 
            (i==0 ? "" : zOp),
            (b?"(":""), z, (b?")":"")
        );
      }

      if( zRet==0 ) break;
    }
  }

  return zRet;
}

/*
** The implementation of user-defined scalar functions fts5_expr() (bTcl==0)

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

267
268
269
270
271
272
273
274

275

276
277
278
279
280
281
282
283
284
285

  return $res
}

#-------------------------------------------------------------------------
# Logical operators used by the commands returned by fts5_tcl_expr().
#
proc AND {a b} {

  if {[llength $a]==0 || [llength $b]==0} { return [list] }

  sort_poslist [concat $a $b]
}
proc OR {a b} {
  sort_poslist [concat $a $b]
}
proc NOT {a b} {
  if {[llength $b]>0} { return [list] }
  return $a
}








|
>
|
>
|

|
|






267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287

  return $res
}

#-------------------------------------------------------------------------
# Logical operators used by the commands returned by fts5_tcl_expr().
#
proc AND {args} {
  foreach a $args {
    if {[llength $a]==0} { return [list] }
  }
  sort_poslist [concat {*}$args]
}
proc OR {args} {
  sort_poslist [concat {*}$args]
}
proc NOT {a b} {
  if {[llength $b]>0} { return [list] }
  return $a
}

Changes to ext/fts5/test/fts5ea.test.

40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
  5  {one AND two}                   {"one" AND "two"}
  6  {one+two}                       {"one" + "two"}
  7  {one AND two OR three}          {("one" AND "two") OR "three"}
  8  {one OR two AND three}          {"one" OR ("two" AND "three")}
  9  {NEAR(one two)}                 {NEAR("one" "two", 10)}
  10 {NEAR("one three"* two, 5)}     {NEAR("one" + "three" * "two", 5)}
  11 {a OR b NOT c}                  {"a" OR ("b" NOT "c")}
  12 "\x20one\x20two\x20three"       {("one" AND "two") AND "three"}
  13 "\x09one\x0Atwo\x0Dthree"       {("one" AND "two") AND "three"}
  14 {"abc""def"}                    {"abc" + "def"}
} {
  do_execsql_test 1.$tn {SELECT fts5_expr($expr)} [list $res]
}

foreach {tn expr res} {
  1 {c1:abc}                           







|
|







40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
  5  {one AND two}                   {"one" AND "two"}
  6  {one+two}                       {"one" + "two"}
  7  {one AND two OR three}          {("one" AND "two") OR "three"}
  8  {one OR two AND three}          {"one" OR ("two" AND "three")}
  9  {NEAR(one two)}                 {NEAR("one" "two", 10)}
  10 {NEAR("one three"* two, 5)}     {NEAR("one" + "three" * "two", 5)}
  11 {a OR b NOT c}                  {"a" OR ("b" NOT "c")}
  12 "\x20one\x20two\x20three"       {"one" AND "two" AND "three"}
  13 "\x09one\x0Atwo\x0Dthree"       {"one" AND "two" AND "three"}
  14 {"abc""def"}                    {"abc" + "def"}
} {
  do_execsql_test 1.$tn {SELECT fts5_expr($expr)} [list $res]
}

foreach {tn expr res} {
  1 {c1:abc}                           

Changes to ext/fts5/test/fts5fault4.test.

302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322

#-------------------------------------------------------------------------
# OOM in fts5_expr() SQL function.
#
do_faultsim_test 10.1 -faults oom-t* -body {
  db one { SELECT fts5_expr('a AND b NEAR(a b)') }
} -test {
  faultsim_test_result {0 {"a" AND ("b" AND NEAR("a" "b", 10))}} 
}

do_faultsim_test 10.2 -faults oom-t* -body {
  db one { SELECT fts5_expr_tcl('x:"a b c" AND b NEAR(a b)', 'ns', 'x') }
} -test {
  set res {AND [ns -col 0 -- {a b c}] [AND [ns -- {b}] [ns -near 10 -- {a} {b}]]}
  faultsim_test_result [list 0 $res]
}

do_faultsim_test 10.3 -faults oom-t* -body {
  db one { SELECT fts5_expr('x:a', 'x') }
} -test {
  faultsim_test_result {0 {x : "a"}}







|





|







302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322

#-------------------------------------------------------------------------
# OOM in fts5_expr() SQL function.
#
do_faultsim_test 10.1 -faults oom-t* -body {
  db one { SELECT fts5_expr('a AND b NEAR(a b)') }
} -test {
  faultsim_test_result {0 {"a" AND "b" AND NEAR("a" "b", 10)}} 
}

do_faultsim_test 10.2 -faults oom-t* -body {
  db one { SELECT fts5_expr_tcl('x:"a b c" AND b NEAR(a b)', 'ns', 'x') }
} -test {
  set res {AND [ns -col 0 -- {a b c}] [ns -- {b}] [ns -near 10 -- {a} {b}]}
  faultsim_test_result [list 0 $res]
}

do_faultsim_test 10.3 -faults oom-t* -body {
  db one { SELECT fts5_expr('x:a', 'x') }
} -test {
  faultsim_test_result {0 {x : "a"}}