Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Begin changing fts5 to use a delete flag so that delete markers may be annihilated more quickly. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | fts5 |
Files: | files | file ages | folders |
SHA1: |
9341c070bb6140dbf559680952909674 |
User & Date: | dan 2015-04-14 20:15:41.831 |
Context
2015-04-15
| ||
16:01 | Fix a problem preventing doclist indexes from being loaded. (check-in: b29109a083 user: dan tags: fts5) | |
2015-04-14
| ||
20:15 | Begin changing fts5 to use a delete flag so that delete markers may be annihilated more quickly. (check-in: 9341c070bb user: dan tags: fts5) | |
2015-04-11
| ||
18:25 | Have fts5 integrity check verify that prefix indexes contain the same values as returned by prefix queries on the main terms index. (check-in: bdb8e82ab6 user: dan tags: fts5) | |
Changes
Changes to ext/fts5/fts5_buffer.c.
︙ | |||
71 72 73 74 75 76 77 | 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 | - + | */ void sqlite3Fts5BufferAppendBlob( int *pRc, Fts5Buffer *pBuf, int nData, const u8 *pData ){ |
︙ |
Changes to ext/fts5/fts5_hash.c.
︙ | |||
58 59 60 61 62 63 64 65 66 67 68 69 70 71 | 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 | + | struct Fts5HashEntry { Fts5HashEntry *pHashNext; /* Next hash entry with same hash-key */ Fts5HashEntry *pScanNext; /* Next entry in sorted order */ int nAlloc; /* Total size of allocation */ int iSzPoslist; /* Offset of space for 4-byte poslist size */ int nData; /* Total bytes of data (incl. structure) */ u8 bDel; /* Set delete-flag @ iSzPoslist */ int iCol; /* Column of last value written */ int iPos; /* Position of last value written */ i64 iRowid; /* Rowid of last value written */ char zKey[0]; /* Nul-terminated entry key */ }; |
︙ | |||
163 164 165 166 167 168 169 | 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 | - - + + + - - + + - + - - - + + + | pHash->nSlot = nNew; pHash->aSlot = apNew; return SQLITE_OK; } static void fts5HashAddPoslistSize(Fts5HashEntry *p){ if( p->iSzPoslist ){ |
︙ | |||
273 274 275 276 277 278 279 280 281 282 283 284 285 286 | 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 | + + + | p->iCol = iCol; p->iPos = 0; } /* Append the new position offset */ p->nData += sqlite3PutVarint(&pPtr[p->nData], iPos - p->iPos + 2); p->iPos = iPos; }else{ /* This is a delete. Set the delete flag. */ p->bDel = 1; } nIncr += p->nData; *pHash->pnByte += nIncr; return SQLITE_OK; } |
︙ |
Changes to ext/fts5/fts5_index.c.
︙ | |||
434 435 436 437 438 439 440 | 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 | - + + | ** pSeg: ** The segment to iterate through. ** ** iLeafPgno: ** Current leaf page number within segment. ** ** iLeafOffset: |
︙ | |||
461 462 463 464 465 466 467 | 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 | - - - + + + | ** This flag is only ever set if FTS5_SEGITER_ONETERM is also set. If ** it is set, iterate through docids in descending order instead of the ** default ascending order. ** ** iRowidOffset/nRowidOffset/aRowidOffset: ** These are used if the FTS5_SEGITER_REVERSE flag is set. ** |
︙ | |||
488 489 490 491 492 493 494 495 496 497 498 499 500 501 | 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 | + + | int *aRowidOffset; /* Array of offset to rowid fields */ Fts5DlidxIter *pDlidx; /* If there is a doclist-index */ /* Variables populated based on current entry. */ Fts5Buffer term; /* Current term */ i64 iRowid; /* Current rowid */ int nPos; /* Number of bytes in current position list */ int bDel; /* True if the delete flag is set */ }; #define FTS5_SEGITER_ONETERM 0x01 #define FTS5_SEGITER_REVERSE 0x02 /* |
︙ | |||
718 719 720 721 722 723 724 | 721 722 723 724 725 726 727 728 729 730 731 732 733 734 | - - - - - - - - - - - | const u8 *pRight, int nRight /* Right hand side of comparison */ ){ int nCmp = MIN(pLeft->n, nRight); int res = memcmp(pLeft->p, pRight, nCmp); return (res==0 ? (pLeft->n - nRight) : res); } |
︙ | |||
1550 1551 1552 1553 1554 1555 1556 1557 1558 1559 1560 1561 1562 1563 | 1542 1543 1544 1545 1546 1547 1548 1549 1550 1551 1552 1553 1554 1555 1556 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 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 | + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + + - - - - + + + + + + + + + + | pIter->pLeaf = fts5DataRead(p, FTS5_SEGMENT_ROWID(pIter->iIdx, pSeg->iSegid, 0, pIter->iLeafPgno) ); }else{ pIter->pLeaf = 0; } } /* ** Argument p points to a buffer containing a varint to be interpreted as a ** position list size field. Read the varint and return the number of bytes ** read. Before returning, set *pnSz to the number of bytes in the position ** list, and *pbDel to true if the delete flag is set, or false otherwise. */ static int fts5GetPoslistSize(const u8 *p, int *pnSz, int *pbDel){ int nSz; int n = fts5GetVarint32(p, nSz); *pnSz = nSz/2; *pbDel = nSz & 0x0001; return n; } /* ** Fts5SegIter.iLeafOffset currently points to the first byte of a ** position-list size field. Read the value of the field and store it ** in the following variables: ** ** Fts5SegIter.nPos ** Fts5SegIter.bDel ** ** Leave Fts5SegIter.iLeafOffset pointing to the first byte of the ** position list content (if any). */ static void fts5SegIterLoadNPos(Fts5Index *p, Fts5SegIter *pIter){ if( p->rc==SQLITE_OK ){ int iOff = pIter->iLeafOffset; /* Offset to read at */ if( iOff>=pIter->pLeaf->n ){ assert( 0 ); fts5SegIterNextPage(p, pIter); if( pIter->pLeaf==0 ){ if( p->rc==SQLITE_OK ) p->rc = FTS5_CORRUPT; return; } iOff = 4; } iOff += fts5GetPoslistSize(pIter->pLeaf->p+iOff, &pIter->nPos,&pIter->bDel); pIter->iLeafOffset = iOff; } } /* ** Fts5SegIter.iLeafOffset currently points to the first byte of the ** "nSuffix" field of a term. Function parameter nKeep contains the value ** of the "nPrefix" field (if there was one - it is passed 0 if this is ** the first term in the segment). ** |
︙ | |||
1622 1623 1624 1625 1626 1627 1628 1629 1630 1631 1632 1633 1634 1635 | 1662 1663 1664 1665 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 1712 1713 1714 1715 1716 1717 1718 1719 1720 1721 1722 1723 1724 1725 1726 1727 1728 | + - - - - + + + + + + + + + + + - - - + + + | fts5SegIterNextPage(p, pIter); } if( p->rc==SQLITE_OK ){ u8 *a = pIter->pLeaf->p; pIter->iLeafOffset = fts5GetU16(&a[2]); fts5SegIterLoadTerm(p, pIter, 0); fts5SegIterLoadNPos(p, pIter); } } /* ** This function is only ever called on iterators created by calls to ** Fts5IndexQuery() with the FTS5INDEX_QUERY_DESC flag set. ** |
︙ | |||
1726 1727 1728 1729 1730 1731 1732 1733 | 1774 1775 1776 1777 1778 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 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 | + + + - + - + + + + - + + - + - - - - - + + + + + + - + - - - - - - | static int fts5SegIterIsDelete( Fts5Index *p, /* FTS5 backend object */ Fts5SegIter *pIter /* Iterator to advance */ ){ int bRet = 0; Fts5Data *pLeaf = pIter->pLeaf; if( p->rc==SQLITE_OK && pLeaf ){ bRet = pIter->nPos==0; /* bRet = pIter->bDel; */ #if 0 if( pIter->iLeafOffset<pLeaf->n ){ |
︙ | |||
1822 1823 1824 1825 1826 1827 1828 | 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 1908 1909 1910 1911 1912 1913 1914 1915 1916 1917 1918 1919 1920 1921 1922 1923 1924 1925 1926 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 1978 1979 1980 1981 1982 1983 1984 1985 1986 1987 1988 1989 1990 1991 1992 1993 1994 1995 1996 1997 1998 1999 2000 2001 2002 2003 2004 2005 | - - - - - - - - - - - + + + + + + + + + + + + + + - - - - - + + + + + + + + + + + + + - + - - - + + + + + + - - - + - + + - - + + - - - - - + - - + + - + + + | fts5DataRelease(pIter->pLeaf); pIter->pLeaf = 0; }else{ pIter->pLeaf->p = (u8*)pList; pIter->pLeaf->n = nList; sqlite3Fts5BufferSet(&p->rc, &pIter->term, strlen(zTerm), (u8*)zTerm); pIter->iLeafOffset = getVarint(pList, (u64*)&pIter->iRowid); |
︙ | |||
1962 1963 1964 1965 1966 1967 1968 1969 1970 | 2023 2024 2025 2026 2027 2028 2029 2030 2031 2032 2033 2034 2035 2036 2037 2038 2039 2040 2041 2042 2043 2044 2045 2046 2047 2048 | + - - + - - - + + + + - + - | assert( pIter->flags & FTS5_SEGITER_ONETERM ); assert( pIter->pDlidx==0 ); /* Check if the current doclist ends on this page. If it does, return ** early without loading the doclist-index (as it belongs to a different ** term. */ if( pIter->iTermLeafPgno==pIter->iLeafPgno ){ int nPos = pIter->nPos; while( iOff<pLeaf->n ){ i64 iDelta; |
︙ | |||
2044 2045 2046 2047 2048 2049 2050 2051 2052 2053 2054 2055 2056 2057 | 2105 2106 2107 2108 2109 2110 2111 2112 2113 2114 2115 2116 2117 2118 2119 | + | pIter->iLeafPgno = iPg - 1; fts5SegIterNextPage(p, pIter); if( pIter->pLeaf ){ int res; pIter->iLeafOffset = fts5GetU16(&pIter->pLeaf->p[2]); fts5SegIterLoadTerm(p, pIter, 0); fts5SegIterLoadNPos(p, pIter); do { res = fts5BufferCompareBlob(&pIter->term, pTerm, nTerm); if( res>=0 ) break; fts5SegIterNext(p, pIter, 0); }while( pIter->pLeaf && p->rc==SQLITE_OK ); if( bGe==0 && res ){ |
︙ | |||
2122 2123 2124 2125 2126 2127 2128 2129 2130 2131 2132 2133 2134 2135 | 2184 2185 2186 2187 2188 2189 2190 2191 2192 2193 2194 2195 2196 2197 2198 2199 | + + | pLeaf->n = nList; pIter->pLeaf = pLeaf; pIter->iLeafOffset = getVarint(pLeaf->p, (u64*)&pIter->iRowid); if( flags & FTS5INDEX_QUERY_DESC ){ pIter->flags |= FTS5_SEGITER_REVERSE; fts5SegIterReverseInitPage(p, pIter); }else{ fts5SegIterLoadNPos(p, pIter); } } } /* ** Zero the iterator passed as the only argument. */ |
︙ | |||
2292 2293 2294 2295 2296 2297 2298 2299 2300 2301 2302 2303 2304 2305 | 2356 2357 2358 2359 2360 2361 2362 2363 2364 2365 2366 2367 2368 2369 2370 | + | iOff = fts5GetU16(&a[0]); if( iOff<4 || iOff>=n ){ p->rc = FTS5_CORRUPT; }else{ iOff += getVarint(&a[iOff], (u64*)&pIter->iRowid); pIter->iLeafOffset = iOff; fts5SegIterLoadNPos(p, pIter); } } } /* ** Advance the iterator passed as the second argument until it is at or ** past rowid iFrom. Regardless of the value of iFrom, the iterator is |
︙ | |||
2466 2467 2468 2469 2470 2471 2472 | 2531 2532 2533 2534 2535 2536 2537 2538 2539 2540 2541 2542 2543 2544 2545 | - + | ** iterated data. */ static void fts5MultiIterNew( Fts5Index *p, /* FTS5 backend to iterate within */ Fts5Structure *pStruct, /* Structure of specific index */ int iIdx, /* Config.aHash[] index of FTS index */ int bSkipEmpty, /* True to ignore delete-keys */ |
︙ | |||
2649 2650 2651 2652 2653 2654 2655 | 2714 2715 2716 2717 2718 2719 2720 2721 2722 2723 2724 2725 2726 2727 2728 2729 2730 2731 2732 | - - - + + - - + - - - - - - - - - - | ** to calculate. */ if( pSeg->pSeg ){ int iId = pSeg->pSeg->iSegid; i64 rowid = FTS5_SEGMENT_ROWID(pSeg->iIdx, iId, 0, pSeg->iLeafPgno); pIter->iLeafRowid = rowid; } |
︙ | |||
3043 3044 3045 3046 3047 3048 3049 | 3096 3097 3098 3099 3100 3101 3102 3103 3104 3105 3106 3107 3108 3109 3110 3111 3112 3113 3114 3115 3116 | - + - + + | if( pPage->buf.n>=p->pConfig->pgsz ){ fts5WriteFlushLeaf(p, pWriter); pWriter->bFirstRowidInPage = 1; } } /* |
︙ | |||
3071 3072 3073 3074 3075 3076 3077 3078 3079 3080 3081 3082 3083 3084 | 3125 3126 3127 3128 3129 3130 3131 3132 3133 3134 3135 3136 3137 3138 3139 3140 | + + | }else{ assert( p->rc || iRowid>pWriter->iPrevRowid ); fts5BufferAppendVarint(&p->rc, &pPage->buf, iRowid - pWriter->iPrevRowid); } pWriter->iPrevRowid = iRowid; pWriter->bFirstRowidInDoclist = 0; pWriter->bFirstRowidInPage = 0; fts5BufferAppendVarint(&p->rc, &pPage->buf, nPos); if( pPage->buf.n>=p->pConfig->pgsz ){ fts5WriteFlushLeaf(p, pWriter); pWriter->bFirstRowidInPage = 1; } } } |
︙ | |||
3372 3373 3374 3375 3376 3377 3378 | 3428 3429 3430 3431 3432 3433 3434 3435 3436 3437 3438 3439 3440 3441 3442 3443 3444 | + - + - - - | } fts5WriteAppendTerm(p, &writer, nTerm, pTerm); fts5BufferSet(&p->rc, &term, nTerm, pTerm); bRequireDoclistTerm = 1; } /* Append the rowid to the output */ /* WRITEPOSLISTSIZE */ |
︙ | |||
3526 3527 3528 3529 3530 3531 3532 | 3580 3581 3582 3583 3584 3585 3586 3587 3588 3589 3590 3591 3592 3593 3594 3595 3596 3597 | - + - - + + + | /* ** Buffer aBuf[] contains a list of varints, all small enough to fit ** in a 32-bit integer. Return the size of the largest prefix of this ** list nMax bytes or less in size. */ static int fts5PoslistPrefix(const u8 *aBuf, int nMax){ |
︙ | |||
3637 3638 3639 3640 3641 3642 3643 | 3692 3693 3694 3695 3696 3697 3698 3699 3700 3701 3702 3703 3704 3705 3706 3707 3708 3709 3710 3711 | - + + - - - + + | int iOff = 0; int bFirstDocid = 0; /* The entire doclist will not fit on this leaf. The following ** loop iterates through the poslists that make up the current ** doclist. */ while( iOff<nDoclist ){ |
︙ | |||
3666 3667 3668 3669 3670 3671 3672 | 3721 3722 3723 3724 3725 3726 3727 3728 3729 3730 3731 3732 3733 3734 3735 3736 3737 3738 3739 3740 3741 3742 3743 3744 3745 3746 3747 3748 3749 | - + + - | /* The entire poslist will not fit on this leaf. So it needs ** to be broken into sections. The only qualification being ** that each varint must be stored contiguously. */ const u8 *pPoslist = &pDoclist[iOff]; int iPos = 0; while( 1 ){ int nSpace = pgsz - pBuf->n; |
︙ | |||
4093 4094 4095 4096 4097 4098 4099 4100 4101 4102 4103 4104 4105 4106 4107 4108 4109 4110 | 4148 4149 4150 4151 4152 4153 4154 4155 4156 4157 4158 4159 4160 4161 4162 4163 4164 4165 4166 4167 4168 4169 4170 4171 4172 4173 4174 4175 4176 | + - - - + + + | } fts5ChunkIterRelease(&iter); } } static void fts5DoclistIterNext(Fts5DoclistIter *pIter){ if( pIter->i<pIter->n ){ int bDummy; if( pIter->i ){ i64 iDelta; pIter->i += getVarint(&pIter->a[pIter->i], (u64*)&iDelta); if( pIter->bDesc ){ pIter->iRowid -= iDelta; }else{ pIter->iRowid += iDelta; } }else{ pIter->i += getVarint(&pIter->a[pIter->i], (u64*)&pIter->iRowid); } |
︙ | |||
4171 4172 4173 4174 4175 4176 4177 | 4227 4228 4229 4230 4231 4232 4233 4234 4235 4236 4237 4238 4239 4240 4241 | - + | Fts5Buffer out; Fts5Buffer tmp; memset(&out, 0, sizeof(out)); memset(&tmp, 0, sizeof(tmp)); fts5DoclistIterInit(p1, bDesc, &i1); fts5DoclistIterInit(p2, bDesc, &i2); |
︙ | |||
4432 4433 4434 4435 4436 4437 4438 4439 4440 4441 4442 4443 4444 4445 | 4488 4489 4490 4491 4492 4493 4494 4495 4496 4497 4498 4499 4500 4501 4502 4503 | + + | } if( rc==SQLITE_OK && ck1!=ck2 ) rc = FTS5_CORRUPT; /* If this is a prefix query, check that the results returned if the ** the index is disabled are the same. In both ASC and DESC order. */ if( iIdx>0 && rc==SQLITE_OK ){ int f = flags|FTS5INDEX_QUERY_TEST_NOIDX; static int nCall = 0; nCall++; ck2 = 0; rc = fts5QueryCksum(p, z, n, f, &ck2); if( rc==SQLITE_OK && ck1!=ck2 ) rc = FTS5_CORRUPT; } if( iIdx>0 && rc==SQLITE_OK ){ int f = flags|FTS5INDEX_QUERY_TEST_NOIDX|FTS5INDEX_QUERY_DESC; ck2 = 0; |
︙ | |||
5068 5069 5070 5071 5072 5073 5074 | 5126 5127 5128 5129 5130 5131 5132 5133 5134 5135 5136 5137 5138 5139 5140 5141 5142 | - - - + + + | if( iOff<n ){ iOff += sqlite3GetVarint(&a[iOff], (u64*)&iDocid); sqlite3Fts5BufferAppendPrintf(pRc, pBuf, " rowid=%lld", iDocid); } while( iOff<n ){ int nPos; |
︙ |
Changes to ext/fts5/test/fts5aa.test.
︙ | |||
17 18 19 20 21 22 23 | 17 18 19 20 21 22 23 24 25 26 27 28 29 30 | - - | # If SQLITE_ENABLE_FTS3 is defined, omit this file. ifcapable !fts5 { finish_test return } |
︙ | |||
325 326 327 328 329 330 331 | 323 324 325 326 327 328 329 330 331 332 333 334 335 336 | - | SELECT rowid FROM t1 WHERE t1 MATCH 'o'; } {1} do_execsql_test 13.6 { SELECT rowid FROM t1 WHERE t1 MATCH '.'; } {} |
︙ |
Changes to ext/fts5/test/fts5ah.test.
︙ | |||
90 91 92 93 94 95 96 | 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 | - + | do_test 1.6.$tn.1 { set n [execsql_reads $q] expr {$n < ($nReadX / 10)} } {1} do_test 1.6.$tn.2 { |
︙ |