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 |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
d6b66cd7b89fbd964f798d160a34caac |
User & Date: | dan 2015-10-05 15:39:45.681 |
Context
2015-10-05
| ||
19:41 | Improve performance of prefix queries without a prefix index on fts5 tables. (check-in: f2f0184e9e 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: d6b66cd7b8 user: dan tags: trunk) | |
11:57 | Add fts5txt2db.tcl, a tool for creating sample fts4/5 databases from text files. (check-in: 44f1ce30d1 user: dan tags: trunk) | |
Changes
Changes to ext/fts3/fts3_expr.c.
︙ | ︙ | |||
789 790 791 792 793 794 795 | 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; } | > | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < < > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | | | | | | | | | | | | | | | | | | | | > > > | > > > > > > > > > > > > > > > > > > > > > > | 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 | 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] | > > | 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 | 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] |
︙ | ︙ | |||
197 198 199 200 201 202 203 204 205 206 | 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 | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 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 | 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 |