Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | Add support for the AND, OR and NOT operators to fts5. |
|---|---|
| Downloads: | Tarball | ZIP archive | SQL archive |
| Timelines: | family | ancestors | descendants | both | trunk |
| Files: | files | file ages | folders |
| SHA1: |
c2efd983b0a863924d2b4e7b8e230231 |
| User & Date: | dan 2012-12-29 09:56:46 |
Context
|
2012-12-29
| ||
| 15:16 | Add fts5rnd1.test, a modified version of fts3rnd.test that works with fts5. check-in: 29d07b13f0 user: dan tags: trunk | |
| 09:56 | Add support for the AND, OR and NOT operators to fts5. check-in: c2efd983b0 user: dan tags: trunk | |
|
2012-12-28
| ||
| 20:01 | Add support for NEAR queries to fts5. check-in: ed403fecf2 user: dan tags: trunk | |
Changes
Changes to src/fts5.c.
147 148 149 150 151 152 153 154 155 156 157 158 159 160 .... 1555 1556 1557 1558 1559 1560 1561 1562 1563 1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 .... 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 .... 1779 1780 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 .... 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 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 1868 1869 1870 1871 1872 1873 1874 1875 1876 1877 1878 1879 1880 1881 1882 1883 1884 1885 1886 1887 1888 1889 1890 1891 1892 1893 1894 1895 1896 |
};
struct Fts5ExprNode {
int eType;
Fts5Phrase *pPhrase;
Fts5ExprNode *pLeft;
Fts5ExprNode *pRight;
};
struct Fts5Expr {
Fts5ExprNode *pRoot;
};
/*
................................................................................
*pnPk = nKey - p->nPrefix;
}
}
return rc;
}
static int fts5KeyCompare(
const u8 *aLeft, int nLeft,
const u8 *aRight, int nRight
){
int nMin = (nLeft > nRight) ? nRight : nLeft;
int res;
res = memcmp(aLeft, aRight, nMin);
return (res ? res : (nLeft-nRight));
}
static int fts5TokenAdvanceToMatch(
InstanceList *p,
InstanceList *pFirst,
int iOff,
................................................................................
fts5InstanceListInit(pTrim->aList, pTrim->nList, &in);
fts5InstanceListInit(pTrim->aList, pTrim->nList, &out);
fts5InstanceListNext(&trail);
fts5InstanceListNext(&lead);
fts5InstanceListNext(&in);
while( bEof==0 ){
/* Check if the current position is a match */
if( fts5IsNear(&trail, &in, nTrail)
|| fts5IsNear(&in, &lead, nLead)
){
fts5InstanceListAppend(&out, in.iCol, in.iWeight, in.iOff);
bEof = fts5InstanceListNext(&in);
}else{
if( fts5InstanceListEof(&trail)==0
&& (trail.iCol<in.iCol || trail.iOff>=in.iOff)
){
fts5InstanceListNext(&trail);
}
else if( (lead.iList<lead.nList)
&& (lead.iCol<in.iCol || lead.iOff<=in.iOff)
){
fts5InstanceListNext(&trail);
}else{
bEof = fts5InstanceListNext(&in);
}
}
................................................................................
rc = fts5PhraseIsMatch(pCsr, pPhrase, &bMatch, &pAdvance);
if( rc!=SQLITE4_OK || bMatch ) break;
rc = sqlite4KVCursorNext(pAdvance->pCsr);
}while( rc==SQLITE4_OK );
return rc;
}
static int fts5PhraseAdvance(Fts5Cursor *pCsr, Fts5Phrase *pPhrase){
int rc = sqlite4KVCursorNext(pPhrase->aStr[0].aToken[0].pCsr);
if( rc==SQLITE4_OK ) rc = fts5PhraseAdvanceToMatch(pCsr, pPhrase);
return rc;
}
int sqlite4Fts5Next(Fts5Cursor *pCsr){
Fts5Phrase *pPhrase;
int rc;
assert( pCsr->pExpr->pRoot->eType==TOKEN_PRIMITIVE );
pPhrase = pCsr->pExpr->pRoot->pPhrase;
rc = fts5PhraseAdvance(pCsr, pPhrase);
return rc;
}
int sqlite4Fts5Open(
sqlite4 *db, /* Database handle */
Fts5Info *pInfo, /* Index description */
const char *zMatch, /* Match expression */
int bDesc, /* True to iterate in desc. order of PK */
................................................................................
** to point to the first entry in the range it will scan. */
rc = fts5OpenCursors(db, pInfo, pCsr);
}
if( rc!=SQLITE4_OK ){
sqlite4Fts5Close(db, pCsr);
pCsr = 0;
}else{
rc = fts5PhraseAdvanceToMatch(pCsr, pCsr->pExpr->pRoot->pPhrase);
}
*ppCsr = pCsr;
return rc;
}
/*
** Return true if the cursor passed as the second argument currently points
** to a valid entry, or false otherwise.
*/
int sqlite4Fts5Valid(Fts5Cursor *pCsr){
const KVByteArray *aKey;
KVSize nKey;
KVCursor *pKVCsr;
int rc;
assert( pCsr->pExpr->pRoot->eType==TOKEN_PRIMITIVE );
pKVCsr = pCsr->pExpr->pRoot->pPhrase->aStr[0].aToken[0].pCsr;
rc = sqlite4KVCursorKey(pKVCsr, &aKey, &nKey);
return (rc==SQLITE4_OK);
}
int sqlite4Fts5Pk(
Fts5Cursor *pCsr,
int iTbl,
KVByteArray **paKey,
KVSize *pnKey
){
const KVByteArray *aKey;
KVSize nKey;
KVCursor *pKVCsr;
int rc;
int i;
int i2;
int nReq;
assert( pCsr->pExpr->pRoot->eType==TOKEN_PRIMITIVE );
pKVCsr = pCsr->pExpr->pRoot->pPhrase->aStr[0].aToken[0].pCsr;
rc = sqlite4KVCursorKey(pKVCsr, &aKey, &nKey);
if( rc!=SQLITE4_OK ) return rc;
i = sqlite4VarintLen(pCsr->pInfo->iRoot);
while( aKey[i] ) i++;
i++;
nReq = sqlite4VarintLen(iTbl) + (nKey-i);
if( nReq>pCsr->nKeyAlloc ){
pCsr->aKey = sqlite4DbReallocOrFree(pCsr->db, pCsr->aKey, nReq*2);
if( !pCsr->aKey ) return SQLITE4_NOMEM;
pCsr->nKeyAlloc = nReq*2;
}
i2 = putVarint32(pCsr->aKey, iTbl);
memcpy(&pCsr->aKey[i2], &aKey[i], nKey-i);
*paKey = pCsr->aKey;
*pnKey = nReq;
return SQLITE4_OK;
}
/**************************************************************************
|
> > > > > > > | > > | > | > < > > > > | | > > > > > | | < > > > > > > | > | < < > > > > > > > > > > > > > > > > > > > > > > > | > > > > | < < | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | > > > > > > > > > > > > > > > | < < < < < | < < < < < < < < | > | | < | < < < < < < | | | |
147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 .... 1557 1558 1559 1560 1561 1562 1563 1564 1565 1566 1567 1568 1569 1570 1571 1572 1573 1574 1575 1576 1577 1578 1579 1580 1581 1582 1583 1584 1585 1586 1587 .... 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 1712 1713 .... 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 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 1858 1859 1860 1861 1862 1863 1864 1865 1866 1867 1868 1869 1870 1871 1872 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 .... 1927 1928 1929 1930 1931 1932 1933 1934 1935 1936 1937 1938 1939 1940 1941 1942 1943 1944 1945 1946 1947 1948 1949 1950 1951 1952 1953 1954 1955 1956 1957 1958 1959 1960 1961 1962 1963 1964 1965 1966 1967 1968 1969 1970 1971 1972 1973 1974 1975 1976 1977 |
};
struct Fts5ExprNode {
int eType;
Fts5Phrase *pPhrase;
Fts5ExprNode *pLeft;
Fts5ExprNode *pRight;
const u8 *aPk; /* Primary key of current entry (or null) */
int nPk; /* Size of aPk[] in bytes */
};
struct Fts5Expr {
Fts5ExprNode *pRoot;
};
/*
................................................................................
*pnPk = nKey - p->nPrefix;
}
}
return rc;
}
/*
** Compare keys (aLeft/nLeft) and (aRight/nRight) using the ordinary memcmp()
** method. Except, if either aLeft or aRight are NULL, consider them larger
** than all other values.
*/
static int fts5KeyCompare(
const u8 *aLeft, int nLeft,
const u8 *aRight, int nRight
){
int res;
int nMin;
res = (aLeft==0) - (aRight==0);
if( res==0 ){
nMin = (nLeft > nRight) ? nRight : nLeft;
res = memcmp(aLeft, aRight, nMin);
}
return (res ? res : (nLeft-nRight));
}
static int fts5TokenAdvanceToMatch(
InstanceList *p,
InstanceList *pFirst,
int iOff,
................................................................................
fts5InstanceListInit(pTrim->aList, pTrim->nList, &in);
fts5InstanceListInit(pTrim->aList, pTrim->nList, &out);
fts5InstanceListNext(&trail);
fts5InstanceListNext(&lead);
fts5InstanceListNext(&in);
while( bEof==0 ){
if( fts5IsNear(&trail, &in, nTrail)
|| fts5IsNear(&in, &lead, nLead)
){
/* The current position is a match. Append an entry to the output
** and advance the input cursor. */
fts5InstanceListAppend(&out, in.iCol, in.iWeight, in.iOff);
bEof = fts5InstanceListNext(&in);
}else{
/* The current position is not a match. Advance one of the trailing,
** leading or input cursors. */
if( fts5InstanceListEof(&trail)==0
&& (trail.iCol<in.iCol || trail.iOff>=in.iOff)
){
fts5InstanceListNext(&trail);
}
else if( fts5InstanceListEof(&lead)==0
&& (lead.iCol<in.iCol || lead.iOff<=in.iOff)
){
fts5InstanceListNext(&trail);
}else{
bEof = fts5InstanceListNext(&in);
}
}
................................................................................
rc = fts5PhraseIsMatch(pCsr, pPhrase, &bMatch, &pAdvance);
if( rc!=SQLITE4_OK || bMatch ) break;
rc = sqlite4KVCursorNext(pAdvance->pCsr);
}while( rc==SQLITE4_OK );
return rc;
}
static int fts5ExprAdvance(Fts5Cursor *pCsr, Fts5ExprNode *p, int bFirst){
int rc = SQLITE4_OK;
switch( p->eType ){
case TOKEN_PRIMITIVE: {
Fts5Phrase *pPhrase = p->pPhrase;
if( bFirst==0 ) rc = sqlite4KVCursorNext(pPhrase->aStr[0].aToken[0].pCsr);
if( rc==SQLITE4_OK ) rc = fts5PhraseAdvanceToMatch(pCsr, pPhrase);
if( rc==SQLITE4_OK ){
rc = fts5TokenPk(&pPhrase->aStr[0].aToken[0], &p->aPk, &p->nPk);
}else{
p->aPk = 0;
p->nPk = 0;
if( rc==SQLITE4_NOTFOUND ) rc = SQLITE4_OK;
}
break;
}
case TOKEN_AND:
p->aPk = 0;
p->nPk = 0;
rc = fts5ExprAdvance(pCsr, p->pLeft, bFirst);
if( rc==SQLITE4_OK ) rc = fts5ExprAdvance(pCsr, p->pRight, bFirst);
while( rc==SQLITE4_OK && p->pLeft->aPk && p->pRight->aPk ){
int res = fts5KeyCompare(
p->pLeft->aPk, p->pLeft->nPk, p->pRight->aPk, p->pRight->nPk
);
if( res<0 ){
rc = fts5ExprAdvance(pCsr, p->pLeft, 0);
}else if( res>0 ){
rc = fts5ExprAdvance(pCsr, p->pRight, 0);
}else{
p->aPk = p->pLeft->aPk;
p->nPk = p->pLeft->nPk;
break;
}
}
break;
case TOKEN_OR: {
int res = 0;
if( bFirst==0 ){
res = fts5KeyCompare(
p->pLeft->aPk, p->pLeft->nPk, p->pRight->aPk, p->pRight->nPk
);
}
if( res<=0 ) rc = fts5ExprAdvance(pCsr, p->pLeft, bFirst);
if( rc==SQLITE4_OK && res>=0 ){
rc = fts5ExprAdvance(pCsr, p->pRight, bFirst);
}
res = fts5KeyCompare(
p->pLeft->aPk, p->pLeft->nPk, p->pRight->aPk, p->pRight->nPk
);
if( res>0 ){
p->aPk = p->pRight->aPk;
p->nPk = p->pRight->nPk;
}else{
p->aPk = p->pLeft->aPk;
p->nPk = p->pLeft->nPk;
}
assert( p->aPk!=0 || (p->pLeft->aPk==0 && p->pRight->aPk==0) );
break;
}
default: assert( p->eType==TOKEN_NOT );
p->aPk = 0;
p->nPk = 0;
rc = fts5ExprAdvance(pCsr, p->pLeft, bFirst);
if( bFirst && rc==SQLITE4_OK ){
rc = fts5ExprAdvance(pCsr, p->pRight, bFirst);
}
while( rc==SQLITE4_OK && p->pLeft->aPk && p->pRight->aPk ){
int res = fts5KeyCompare(
p->pLeft->aPk, p->pLeft->nPk, p->pRight->aPk, p->pRight->nPk
);
if( res<0 ){
break;
}else if( res>0 ){
rc = fts5ExprAdvance(pCsr, p->pRight, 0);
}else{
rc = fts5ExprAdvance(pCsr, p->pLeft, 0);
}
}
p->aPk = p->pLeft->aPk;
p->nPk = p->pLeft->nPk;
break;
}
assert( rc!=SQLITE4_NOTFOUND );
return rc;
}
int sqlite4Fts5Next(Fts5Cursor *pCsr){
return fts5ExprAdvance(pCsr, pCsr->pExpr->pRoot, 0);
}
int sqlite4Fts5Open(
sqlite4 *db, /* Database handle */
Fts5Info *pInfo, /* Index description */
const char *zMatch, /* Match expression */
int bDesc, /* True to iterate in desc. order of PK */
................................................................................
** to point to the first entry in the range it will scan. */
rc = fts5OpenCursors(db, pInfo, pCsr);
}
if( rc!=SQLITE4_OK ){
sqlite4Fts5Close(db, pCsr);
pCsr = 0;
}else{
rc = fts5ExprAdvance(pCsr, pCsr->pExpr->pRoot, 1);
}
*ppCsr = pCsr;
return rc;
}
/*
** Return true if the cursor passed as the second argument currently points
** to a valid entry, or false otherwise.
*/
int sqlite4Fts5Valid(Fts5Cursor *pCsr){
return( pCsr->pExpr->pRoot->aPk!=0 );
}
int sqlite4Fts5Pk(
Fts5Cursor *pCsr,
int iTbl,
KVByteArray **paKey,
KVSize *pnKey
){
int i;
int nReq;
const u8 *aPk;
int nPk;
aPk = pCsr->pExpr->pRoot->aPk;
nPk = pCsr->pExpr->pRoot->nPk;
nReq = sqlite4VarintLen(iTbl) + nPk;
if( nReq>pCsr->nKeyAlloc ){
pCsr->aKey = sqlite4DbReallocOrFree(pCsr->db, pCsr->aKey, nReq*2);
if( !pCsr->aKey ) return SQLITE4_NOMEM;
pCsr->nKeyAlloc = nReq*2;
}
i = putVarint32(pCsr->aKey, iTbl);
memcpy(&pCsr->aKey[i], aPk, nPk);
*paKey = pCsr->aKey;
*pnKey = nReq;
return SQLITE4_OK;
}
/**************************************************************************
|
Changes to src/vdbe.c.
4922
4923
4924
4925
4926
4927
4928
4929
4930
4931
4932
4933
4934
4935
4936
4937
4938
4939
4940
4941
4942
4943
4944
4945
....
4946
4947
4948
4949
4950
4951
4952
4953
4954
4955
4956
4957
4958
4959
4960
4961
|
assert( pOp->p4type==P4_FTS5INFO );
pInfo = pOp->p4.pFtsInfo;
pCur = allocateCursor(p, pOp->p1, 0, pInfo->iDb, 0);
if( pCur ){
rc = sqlite4Fts5Open(db, pInfo, zMatch, pOp->p5, &pCur->pFts, &p->zErrMsg);
}
if( rc==SQLITE4_NOTFOUND ){
rc = SQLITE4_OK;
pc = pOp->p2-1;
}
#if 0
if( rc==SQLITE4_OK && 0==sqlite4Fts5Valid(pCur->pFts) ){
pc = pOp->p2-1;
}
#endif
break;
}
/* Opcode: FtsNext P1 P2 * * *
**
** Advance FTS cursor P1 to the next entry and jump to instruction P2. Or,
** if there is no next entry, set the cursor to point to EOF and fall through
................................................................................
** to the next instruction.
*/
case OP_FtsNext: {
VdbeCursor *pCsr;
pCsr = p->apCsr[pOp->p1];
rc = sqlite4Fts5Next(pCsr->pFts);
if( rc==SQLITE4_OK ) pc = pOp->p2-1;
if( rc==SQLITE4_NOTFOUND ) rc = SQLITE4_OK;
break;
}
/* Opcode: FtsPk P1 P2 * * *
**
** P1 is an FTS cursor that points to a valid entry (not EOF). Copy the PK
|
<
<
<
<
<
<
<
|
<
|
4922
4923
4924
4925
4926
4927
4928
4929
4930
4931
4932
4933
4934
4935
4936
4937
4938
....
4939
4940
4941
4942
4943
4944
4945
4946
4947
4948
4949
4950
4951
4952
4953
|
assert( pOp->p4type==P4_FTS5INFO );
pInfo = pOp->p4.pFtsInfo;
pCur = allocateCursor(p, pOp->p1, 0, pInfo->iDb, 0);
if( pCur ){
rc = sqlite4Fts5Open(db, pInfo, zMatch, pOp->p5, &pCur->pFts, &p->zErrMsg);
}
if( rc==SQLITE4_OK && 0==sqlite4Fts5Valid(pCur->pFts) ){
pc = pOp->p2-1;
}
break;
}
/* Opcode: FtsNext P1 P2 * * *
**
** Advance FTS cursor P1 to the next entry and jump to instruction P2. Or,
** if there is no next entry, set the cursor to point to EOF and fall through
................................................................................
** to the next instruction.
*/
case OP_FtsNext: {
VdbeCursor *pCsr;
pCsr = p->apCsr[pOp->p1];
rc = sqlite4Fts5Next(pCsr->pFts);
if( rc==SQLITE4_OK && sqlite4Fts5Valid(pCsr->pFts) ) pc = pOp->p2-1;
break;
}
/* Opcode: FtsPk P1 P2 * * *
**
** P1 is an FTS cursor that points to a valid entry (not EOF). Copy the PK
|
Changes to test/fts5query1.test.
63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
INSERT INTO t1 VALUES(1, 'a b c d e f g h i j k l m n o p q r s t u');
INSERT INTO t1 VALUES(2, 'a e i o u b c d f g h j k l m n p q r s t');
INSERT INTO t1 VALUES(3, 'b c d f g h j k l m n p q r s t v w x y z');
INSERT INTO t1 VALUES(4, 'a e i o u');
}
foreach {tn stmt res} {
1 {SELECT x FROM t1 WHERE t1 MATCH 'a NEAR/5 i'} {2 4}
2 {SELECT x FROM t1 WHERE t1 MATCH 'a NEAR/3 b'} {1}
3 {SELECT x FROM t1 WHERE t1 MATCH 'a NEAR/2 d'} {1}
4 {SELECT x FROM t1 WHERE t1 MATCH 'a NEAR/2 e'} {2 4}
5 {SELECT x FROM t1 WHERE t1 MATCH 'a NEAR/3 e'} {1 2 4}
6 {SELECT x FROM t1 WHERE t1 MATCH 'b+c NEAR/2 g+h'} {2 3}
7 {SELECT x FROM t1 WHERE t1 MATCH 'b+c NEAR/3 g+h'} {1 2 3}
8 {SELECT x FROM t1 WHERE t1 MATCH 'b+c NEAR/2 g+h+j'} {2 3}
9 {SELECT x FROM t1 WHERE t1 MATCH 'b+c+d NEAR/1 g+h'} {2 3}
} {
do_execsql_test 3.$tn $stmt $res
}
finish_test
|
| | | | | | | | | > > > |
63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 |
INSERT INTO t1 VALUES(1, 'a b c d e f g h i j k l m n o p q r s t u');
INSERT INTO t1 VALUES(2, 'a e i o u b c d f g h j k l m n p q r s t');
INSERT INTO t1 VALUES(3, 'b c d f g h j k l m n p q r s t v w x y z');
INSERT INTO t1 VALUES(4, 'a e i o u');
}
foreach {tn stmt res} {
1 {SELECT x FROM t1 WHERE t1 MATCH 'a NEAR/5 i'} {2 4}
2 {SELECT x FROM t1 WHERE t1 MATCH 'a NEAR/3 b'} {1}
3 {SELECT x FROM t1 WHERE t1 MATCH 'a NEAR/2 d'} {1}
4 {SELECT x FROM t1 WHERE t1 MATCH 'a NEAR/2 e'} {2 4}
5 {SELECT x FROM t1 WHERE t1 MATCH 'a NEAR/3 e'} {1 2 4}
6 {SELECT x FROM t1 WHERE t1 MATCH 'b+c NEAR/2 g+h'} {2 3}
7 {SELECT x FROM t1 WHERE t1 MATCH 'b+c NEAR/3 g+h'} {1 2 3}
8 {SELECT x FROM t1 WHERE t1 MATCH 'b+c NEAR/2 g+h+j'} {2 3}
9 {SELECT x FROM t1 WHERE t1 MATCH 'b+c+d NEAR/1 g+h'} {2 3}
10 {SELECT x FROM t1 WHERE t1 MATCH 'a AND d'} {1 2}
11 {SELECT x FROM t1 WHERE t1 MATCH 'a OR d'} {1 2 3 4}
12 {SELECT x FROM t1 WHERE t1 MATCH 'a NOT d'} {4}
} {
do_execsql_test 3.$tn $stmt $res
}
finish_test
|