Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | Update fts3 so that expressions to the left and right of a NOT operator are balanced. This prevents relatively small expressions (a dozen terms or so) that are children of NOT operators from triggering the "expression tree is too large" error. |
|---|---|
| Downloads: | Tarball | ZIP archive | SQL archive |
| Timelines: | family | ancestors | descendants | both | trunk |
| Files: | files | file ages | folders |
| SHA1: |
d6b66cd7b89fbd964f798d160a34caac |
| User & Date: | dan 2015-10-05 15:39:45 |
Context
|
2015-10-05
| ||
| 19:41 | Improve performance of prefix queries without a prefix index on fts5 tables. check-in: f2f0184e user: dan tags: trunk | |
| 15:39 | Update fts3 so that expressions to the left and right of a NOT operator are balanced. This prevents relatively small expressions (a dozen terms or so) that are children of NOT operators from triggering the "expression tree is too large" error. check-in: d6b66cd7 user: dan tags: trunk | |
| 11:57 | Add fts5txt2db.tcl, a tool for creating sample fts4/5 databases from text files. check-in: 44f1ce30 user: dan tags: trunk | |
Changes
Changes to ext/fts3/fts3_expr.c.
789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 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 |
Fts3Expr *pFree = 0; /* List of free nodes. Linked by pParent. */
int eType = pRoot->eType; /* Type of node in this tree */
if( nMaxDepth==0 ){
rc = SQLITE_ERROR;
}
if( rc==SQLITE_OK && (eType==FTSQUERY_AND || eType==FTSQUERY_OR) ){
Fts3Expr **apLeaf;
apLeaf = (Fts3Expr **)sqlite3_malloc(sizeof(Fts3Expr *) * nMaxDepth);
if( 0==apLeaf ){
rc = SQLITE_NOMEM;
}else{
memset(apLeaf, 0, sizeof(Fts3Expr *) * nMaxDepth);
}
if( rc==SQLITE_OK ){
int i;
Fts3Expr *p;
/* Set $p to point to the left-most leaf in the tree of eType nodes. */
for(p=pRoot; p->eType==eType; p=p->pLeft){
assert( p->pParent==0 || p->pParent->pLeft==p );
assert( p->pLeft && p->pRight );
}
/* This loop runs once for each leaf in the tree of eType nodes. */
while( 1 ){
int iLvl;
Fts3Expr *pParent = p->pParent; /* Current parent of p */
assert( pParent==0 || pParent->pLeft==p );
p->pParent = 0;
if( pParent ){
pParent->pLeft = 0;
}else{
pRoot = 0;
}
rc = fts3ExprBalance(&p, nMaxDepth-1);
if( rc!=SQLITE_OK ) break;
for(iLvl=0; p && iLvl<nMaxDepth; iLvl++){
if( apLeaf[iLvl]==0 ){
apLeaf[iLvl] = p;
p = 0;
}else{
assert( pFree );
pFree->pLeft = apLeaf[iLvl];
pFree->pRight = p;
pFree->pLeft->pParent = pFree;
pFree->pRight->pParent = pFree;
p = pFree;
pFree = pFree->pParent;
p->pParent = 0;
apLeaf[iLvl] = 0;
}
}
if( p ){
sqlite3Fts3ExprFree(p);
rc = SQLITE_TOOBIG;
break;
}
/* If that was the last leaf node, break out of the loop */
if( pParent==0 ) break;
/* Set $p to point to the next leaf in the tree of eType nodes */
for(p=pParent->pRight; p->eType==eType; p=p->pLeft);
/* Remove pParent from the original tree. */
assert( pParent->pParent==0 || pParent->pParent->pLeft==pParent );
pParent->pRight->pParent = pParent->pParent;
if( pParent->pParent ){
pParent->pParent->pLeft = pParent->pRight;
}else{
assert( pParent==pRoot );
pRoot = pParent->pRight;
}
/* Link pParent into the free node list. It will be used as an
** internal node of the new tree. */
pParent->pParent = pFree;
pFree = pParent;
}
if( rc==SQLITE_OK ){
p = 0;
for(i=0; i<nMaxDepth; i++){
if( apLeaf[i] ){
if( p==0 ){
p = apLeaf[i];
p->pParent = 0;
}else{
assert( pFree!=0 );
pFree->pRight = p;
pFree->pLeft = apLeaf[i];
pFree->pLeft->pParent = pFree;
pFree->pRight->pParent = pFree;
p = pFree;
pFree = pFree->pParent;
p->pParent = 0;
}
}
}
pRoot = p;
}else{
/* An error occurred. Delete the contents of the apLeaf[] array
** and pFree list. Everything else is cleaned up by the call to
** sqlite3Fts3ExprFree(pRoot) below. */
Fts3Expr *pDel;
for(i=0; i<nMaxDepth; i++){
sqlite3Fts3ExprFree(apLeaf[i]);
}
while( (pDel=pFree)!=0 ){
pFree = pDel->pParent;
sqlite3_free(pDel);
}
}
assert( pFree==0 );
sqlite3_free( apLeaf );
}
}
if( rc!=SQLITE_OK ){
sqlite3Fts3ExprFree(pRoot);
pRoot = 0;
}
*pp = pRoot;
return rc;
}
|
> | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | > > > | > > > > > > > > > > > > > > > > > > > > > > |
789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 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 |
Fts3Expr *pFree = 0; /* List of free nodes. Linked by pParent. */
int eType = pRoot->eType; /* Type of node in this tree */
if( nMaxDepth==0 ){
rc = SQLITE_ERROR;
}
if( rc==SQLITE_OK ){
if( (eType==FTSQUERY_AND || eType==FTSQUERY_OR) ){
Fts3Expr **apLeaf;
apLeaf = (Fts3Expr **)sqlite3_malloc(sizeof(Fts3Expr *) * nMaxDepth);
if( 0==apLeaf ){
rc = SQLITE_NOMEM;
}else{
memset(apLeaf, 0, sizeof(Fts3Expr *) * nMaxDepth);
}
if( rc==SQLITE_OK ){
int i;
Fts3Expr *p;
/* Set $p to point to the left-most leaf in the tree of eType nodes. */
for(p=pRoot; p->eType==eType; p=p->pLeft){
assert( p->pParent==0 || p->pParent->pLeft==p );
assert( p->pLeft && p->pRight );
}
/* This loop runs once for each leaf in the tree of eType nodes. */
while( 1 ){
int iLvl;
Fts3Expr *pParent = p->pParent; /* Current parent of p */
assert( pParent==0 || pParent->pLeft==p );
p->pParent = 0;
if( pParent ){
pParent->pLeft = 0;
}else{
pRoot = 0;
}
rc = fts3ExprBalance(&p, nMaxDepth-1);
if( rc!=SQLITE_OK ) break;
for(iLvl=0; p && iLvl<nMaxDepth; iLvl++){
if( apLeaf[iLvl]==0 ){
apLeaf[iLvl] = p;
p = 0;
}else{
assert( pFree );
pFree->pLeft = apLeaf[iLvl];
pFree->pRight = p;
pFree->pLeft->pParent = pFree;
pFree->pRight->pParent = pFree;
p = pFree;
pFree = pFree->pParent;
p->pParent = 0;
apLeaf[iLvl] = 0;
}
}
if( p ){
sqlite3Fts3ExprFree(p);
rc = SQLITE_TOOBIG;
break;
}
/* If that was the last leaf node, break out of the loop */
if( pParent==0 ) break;
/* Set $p to point to the next leaf in the tree of eType nodes */
for(p=pParent->pRight; p->eType==eType; p=p->pLeft);
/* Remove pParent from the original tree. */
assert( pParent->pParent==0 || pParent->pParent->pLeft==pParent );
pParent->pRight->pParent = pParent->pParent;
if( pParent->pParent ){
pParent->pParent->pLeft = pParent->pRight;
}else{
assert( pParent==pRoot );
pRoot = pParent->pRight;
}
/* Link pParent into the free node list. It will be used as an
** internal node of the new tree. */
pParent->pParent = pFree;
pFree = pParent;
}
if( rc==SQLITE_OK ){
p = 0;
for(i=0; i<nMaxDepth; i++){
if( apLeaf[i] ){
if( p==0 ){
p = apLeaf[i];
p->pParent = 0;
}else{
assert( pFree!=0 );
pFree->pRight = p;
pFree->pLeft = apLeaf[i];
pFree->pLeft->pParent = pFree;
pFree->pRight->pParent = pFree;
p = pFree;
pFree = pFree->pParent;
p->pParent = 0;
}
}
}
pRoot = p;
}else{
/* An error occurred. Delete the contents of the apLeaf[] array
** and pFree list. Everything else is cleaned up by the call to
** sqlite3Fts3ExprFree(pRoot) below. */
Fts3Expr *pDel;
for(i=0; i<nMaxDepth; i++){
sqlite3Fts3ExprFree(apLeaf[i]);
}
while( (pDel=pFree)!=0 ){
pFree = pDel->pParent;
sqlite3_free(pDel);
}
}
assert( pFree==0 );
sqlite3_free( apLeaf );
}
}else if( eType==FTSQUERY_NOT ){
Fts3Expr *pLeft = pRoot->pLeft;
Fts3Expr *pRight = pRoot->pRight;
pRoot->pLeft = 0;
pRoot->pRight = 0;
pLeft->pParent = 0;
pRight->pParent = 0;
rc = fts3ExprBalance(&pLeft, nMaxDepth-1);
if( rc==SQLITE_OK ){
rc = fts3ExprBalance(&pRight, nMaxDepth-1);
}
if( rc!=SQLITE_OK ){
sqlite3Fts3ExprFree(pRight);
sqlite3Fts3ExprFree(pLeft);
}else{
assert( pLeft && pRight );
pRoot->pLeft = pLeft;
pLeft->pParent = pRoot;
pRoot->pRight = pRight;
pRight->pParent = pRoot;
}
}
}
if( rc!=SQLITE_OK ){
sqlite3Fts3ExprFree(pRoot);
pRoot = 0;
}
*pp = pRoot;
return rc;
}
|
Changes to test/fts3expr3.test.
117
118
119
120
121
122
123
124
125
126
127
128
129
130
...
197
198
199
200
201
202
203
204
205
206
|
proc balanced_andor_tree {nEntry} {
set tree [balanced_exprtree_structure $nEntry]
set node "{[balanced_and_tree $nEntry]}"
regsub -all AND $node OR node
regsub -all xxx $tree $node tree
return $tree
}
# Test that queries like "1 AND 2 AND 3 AND 4..." are transformed to
# balanced trees by FTS.
#
for {set i 1} {$i < 100} {incr i} {
do_test 1.$i {
test_fts3expr2 [random_and_query $i]
................................................................................
set query [random_andor_query 12]
set result [balanced_andor_tree 12]
do_faultsim_test fts3expr3-fault-1 -faults oom-* -body {
test_fts3expr2 $::query
} -test {
faultsim_test_result [list 0 $::result]
}
set sqlite_fts3_enable_parentheses 0
finish_test
|
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
...
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
|
proc balanced_andor_tree {nEntry} {
set tree [balanced_exprtree_structure $nEntry]
set node "{[balanced_and_tree $nEntry]}"
regsub -all AND $node OR node
regsub -all xxx $tree $node tree
return $tree
}
if 1 {
# Test that queries like "1 AND 2 AND 3 AND 4..." are transformed to
# balanced trees by FTS.
#
for {set i 1} {$i < 100} {incr i} {
do_test 1.$i {
test_fts3expr2 [random_and_query $i]
................................................................................
set query [random_andor_query 12]
set result [balanced_andor_tree 12]
do_faultsim_test fts3expr3-fault-1 -faults oom-* -body {
test_fts3expr2 $::query
} -test {
faultsim_test_result [list 0 $::result]
}
}
#-------------------------------------------------------------------
foreach {tn expr res} {
1 {1 OR 2 OR 3 OR 4} {OR {OR {P 1} {P 2}} {OR {P 3} {P 4}}}
2 {1 OR (2 AND 3 AND 4 AND 5)}
{OR {P 1} {AND {AND {P 2} {P 3}} {AND {P 4} {P 5}}}}
3 {(2 AND 3 AND 4 AND 5) OR 1}
{OR {AND {AND {P 2} {P 3}} {AND {P 4} {P 5}}} {P 1}}
4 {1 AND (2 OR 3 OR 4 OR 5)}
{AND {P 1} {OR {OR {P 2} {P 3}} {OR {P 4} {P 5}}}}
5 {(2 OR 3 OR 4 OR 5) AND 1}
{AND {OR {OR {P 2} {P 3}} {OR {P 4} {P 5}}} {P 1}}
6 {(2 OR 3 OR 4 OR 5) NOT 1}
{NOT {OR {OR {P 2} {P 3}} {OR {P 4} {P 5}}} {P 1}}
7 {1 NOT (2 OR 3 OR 4 OR 5)}
{NOT {P 1} {OR {OR {P 2} {P 3}} {OR {P 4} {P 5}}}}
8 {(1 OR 2 OR 3 OR 4) NOT (5 AND 6 AND 7 AND 8)}
{NOT {OR {OR {P 1} {P 2}} {OR {P 3} {P 4}}} {AND {AND {P 5} {P 6}} {AND {P 7} {P 8}}}}
} {
do_test 5.1.$tn {
test_fts3expr2 $expr
} $res
}
set sqlite_fts3_enable_parentheses 0
finish_test
|