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 | SQL archive |
| Timelines: | family | ancestors | descendants | both | fts5 |
| Files: | files | file ages | folders |
| SHA1: |
9341c070bb6140dbf559680952909674 |
| User & Date: | dan 2015-04-14 20:15:41 |
Context
|
2015-04-15
| ||
| 16:01 | Fix a problem preventing doclist indexes from being loaded. (check-in: b29109a0 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: 9341c070 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: bdb8e82a user: dan tags: fts5) | |
Changes
Changes to ext/fts5/fts5_buffer.c.
71 71 */ 72 72 void sqlite3Fts5BufferAppendBlob( 73 73 int *pRc, 74 74 Fts5Buffer *pBuf, 75 75 int nData, 76 76 const u8 *pData 77 77 ){ 78 - assert( nData>=0 ); 78 + assert( *pRc || nData>=0 ); 79 79 if( sqlite3Fts5BufferGrow(pRc, pBuf, nData) ) return; 80 80 memcpy(&pBuf->p[pBuf->n], pData, nData); 81 81 pBuf->n += nData; 82 82 } 83 83 84 84 /* 85 85 ** Append the nul-terminated string zStr to the buffer pBuf. This function
Changes to ext/fts5/fts5_hash.c.
58 58 struct Fts5HashEntry { 59 59 Fts5HashEntry *pHashNext; /* Next hash entry with same hash-key */ 60 60 Fts5HashEntry *pScanNext; /* Next entry in sorted order */ 61 61 62 62 int nAlloc; /* Total size of allocation */ 63 63 int iSzPoslist; /* Offset of space for 4-byte poslist size */ 64 64 int nData; /* Total bytes of data (incl. structure) */ 65 + u8 bDel; /* Set delete-flag @ iSzPoslist */ 65 66 66 67 int iCol; /* Column of last value written */ 67 68 int iPos; /* Position of last value written */ 68 69 i64 iRowid; /* Rowid of last value written */ 69 70 char zKey[0]; /* Nul-terminated entry key */ 70 71 }; 71 72 ................................................................................ 163 164 pHash->nSlot = nNew; 164 165 pHash->aSlot = apNew; 165 166 return SQLITE_OK; 166 167 } 167 168 168 169 static void fts5HashAddPoslistSize(Fts5HashEntry *p){ 169 170 if( p->iSzPoslist ){ 170 - /* WRITEPOSLISTSIZE */ 171 171 u8 *pPtr = (u8*)p; 172 - int nSz = (p->nData - p->iSzPoslist - 1) * 2; 172 + int nSz = (p->nData - p->iSzPoslist - 1); /* Size in bytes */ 173 + int nPos = nSz*2 + p->bDel; /* Value of nPos field */ 173 174 174 - if( nSz<=127 ){ 175 - pPtr[p->iSzPoslist] = nSz; 175 + assert( p->bDel==0 || p->bDel==1 ); 176 + if( nPos<=127 ){ 177 + pPtr[p->iSzPoslist] = nPos; 176 178 }else{ 177 - int nByte = sqlite3Fts5GetVarintLen((u32)nSz); 178 - /* WRITEPOSLISTSIZE */ 179 - memmove(&pPtr[p->iSzPoslist + nByte], &pPtr[p->iSzPoslist + 1], nSz/2); 180 - sqlite3PutVarint(&pPtr[p->iSzPoslist], nSz); 179 + int nByte = sqlite3Fts5GetVarintLen((u32)nPos); 180 + memmove(&pPtr[p->iSzPoslist + nByte], &pPtr[p->iSzPoslist + 1], nSz); 181 + sqlite3PutVarint(&pPtr[p->iSzPoslist], nPos); 181 182 p->nData += (nByte-1); 182 183 } 184 + p->bDel = 0; 183 185 p->iSzPoslist = 0; 184 186 } 185 187 } 186 188 187 189 int sqlite3Fts5HashWrite( 188 190 Fts5Hash *pHash, 189 191 i64 iRowid, /* Rowid for this entry */ ................................................................................ 273 275 p->iCol = iCol; 274 276 p->iPos = 0; 275 277 } 276 278 277 279 /* Append the new position offset */ 278 280 p->nData += sqlite3PutVarint(&pPtr[p->nData], iPos - p->iPos + 2); 279 281 p->iPos = iPos; 282 + }else{ 283 + /* This is a delete. Set the delete flag. */ 284 + p->bDel = 1; 280 285 } 281 286 nIncr += p->nData; 282 287 283 288 *pHash->pnByte += nIncr; 284 289 return SQLITE_OK; 285 290 } 286 291
Changes to ext/fts5/fts5_index.c.
434 434 ** pSeg: 435 435 ** The segment to iterate through. 436 436 ** 437 437 ** iLeafPgno: 438 438 ** Current leaf page number within segment. 439 439 ** 440 440 ** iLeafOffset: 441 -** Byte offset within the current leaf that is one byte past the end of the 441 +** Byte offset within the current leaf that is the first byte of the 442 +** position list data (one byte passed the position-list size field). 442 443 ** rowid field of the current entry. Usually this is the size field of the 443 444 ** position list data. The exception is if the rowid for the current entry 444 445 ** is the last thing on the leaf page. 445 446 ** 446 447 ** pLeaf: 447 448 ** Buffer containing current leaf page data. Set to NULL at EOF. 448 449 ** ................................................................................ 461 462 ** This flag is only ever set if FTS5_SEGITER_ONETERM is also set. If 462 463 ** it is set, iterate through docids in descending order instead of the 463 464 ** default ascending order. 464 465 ** 465 466 ** iRowidOffset/nRowidOffset/aRowidOffset: 466 467 ** These are used if the FTS5_SEGITER_REVERSE flag is set. 467 468 ** 468 -** Each time a new page is loaded, the iterator is set to point to the 469 -** final rowid. Additionally, the aRowidOffset[] array is populated 470 -** with the byte offsets of all relevant rowid fields on the page. 469 +** For each rowid on the page corresponding to the current term, the 470 +** corresponding aRowidOffset[] entry is set to the byte offset of the 471 +** start of the "position-list-size" field within the page. 471 472 */ 472 473 struct Fts5SegIter { 473 474 Fts5StructureSegment *pSeg; /* Segment to iterate through */ 474 475 int iIdx; /* Byte offset within current leaf */ 475 476 int flags; /* Mask of configuration flags */ 476 477 int iLeafPgno; /* Current leaf page number */ 477 478 Fts5Data *pLeaf; /* Current leaf data */ ................................................................................ 488 489 int *aRowidOffset; /* Array of offset to rowid fields */ 489 490 490 491 Fts5DlidxIter *pDlidx; /* If there is a doclist-index */ 491 492 492 493 /* Variables populated based on current entry. */ 493 494 Fts5Buffer term; /* Current term */ 494 495 i64 iRowid; /* Current rowid */ 496 + int nPos; /* Number of bytes in current position list */ 497 + int bDel; /* True if the delete flag is set */ 495 498 }; 496 499 497 500 #define FTS5_SEGITER_ONETERM 0x01 498 501 #define FTS5_SEGITER_REVERSE 0x02 499 502 500 503 501 504 /* ................................................................................ 718 721 const u8 *pRight, int nRight /* Right hand side of comparison */ 719 722 ){ 720 723 int nCmp = MIN(pLeft->n, nRight); 721 724 int res = memcmp(pLeft->p, pRight, nCmp); 722 725 return (res==0 ? (pLeft->n - nRight) : res); 723 726 } 724 727 725 -#if 0 726 -static int fts5CompareBlob( 727 - const u8 *pLeft, int nLeft, 728 - const u8 *pRight, int nRight 729 -){ 730 - int nCmp = MIN(nLeft, nRight); 731 - int res = memcmp(pLeft, pRight, nCmp); 732 - return (res==0 ? (nLeft - nRight) : res); 733 -} 734 -#endif 735 - 736 728 /* 737 729 ** Compare the contents of the two buffers using memcmp(). If one buffer 738 730 ** is a prefix of the other, it is considered the lesser. 739 731 ** 740 732 ** Return -ve if pLeft is smaller than pRight, 0 if they are equal or 741 733 ** +ve if pRight is smaller than pLeft. In other words: 742 734 ** ................................................................................ 1550 1542 pIter->pLeaf = fts5DataRead(p, 1551 1543 FTS5_SEGMENT_ROWID(pIter->iIdx, pSeg->iSegid, 0, pIter->iLeafPgno) 1552 1544 ); 1553 1545 }else{ 1554 1546 pIter->pLeaf = 0; 1555 1547 } 1556 1548 } 1549 + 1550 +/* 1551 +** Argument p points to a buffer containing a varint to be interpreted as a 1552 +** position list size field. Read the varint and return the number of bytes 1553 +** read. Before returning, set *pnSz to the number of bytes in the position 1554 +** list, and *pbDel to true if the delete flag is set, or false otherwise. 1555 +*/ 1556 +static int fts5GetPoslistSize(const u8 *p, int *pnSz, int *pbDel){ 1557 + int nSz; 1558 + int n = fts5GetVarint32(p, nSz); 1559 + *pnSz = nSz/2; 1560 + *pbDel = nSz & 0x0001; 1561 + return n; 1562 +} 1563 + 1564 +/* 1565 +** Fts5SegIter.iLeafOffset currently points to the first byte of a 1566 +** position-list size field. Read the value of the field and store it 1567 +** in the following variables: 1568 +** 1569 +** Fts5SegIter.nPos 1570 +** Fts5SegIter.bDel 1571 +** 1572 +** Leave Fts5SegIter.iLeafOffset pointing to the first byte of the 1573 +** position list content (if any). 1574 +*/ 1575 +static void fts5SegIterLoadNPos(Fts5Index *p, Fts5SegIter *pIter){ 1576 + if( p->rc==SQLITE_OK ){ 1577 + int iOff = pIter->iLeafOffset; /* Offset to read at */ 1578 + if( iOff>=pIter->pLeaf->n ){ 1579 + assert( 0 ); 1580 + fts5SegIterNextPage(p, pIter); 1581 + if( pIter->pLeaf==0 ){ 1582 + if( p->rc==SQLITE_OK ) p->rc = FTS5_CORRUPT; 1583 + return; 1584 + } 1585 + iOff = 4; 1586 + } 1587 + iOff += fts5GetPoslistSize(pIter->pLeaf->p+iOff, &pIter->nPos,&pIter->bDel); 1588 + pIter->iLeafOffset = iOff; 1589 + } 1590 +} 1557 1591 1558 1592 /* 1559 1593 ** Fts5SegIter.iLeafOffset currently points to the first byte of the 1560 1594 ** "nSuffix" field of a term. Function parameter nKeep contains the value 1561 1595 ** of the "nPrefix" field (if there was one - it is passed 0 if this is 1562 1596 ** the first term in the segment). 1563 1597 ** 1564 -** This function populates (Fts5SegIter.term) and (Fts5SegIter.iRowid) 1565 -** accordingly and leaves (Fts5SegIter.iLeafOffset) set to the offset to 1566 -** the size field of the first position list. The position list belonging 1567 -** to document (Fts5SegIter.iRowid). 1598 +** This function populates: 1599 +** 1600 +** Fts5SegIter.term 1601 +** Fts5SegIter.rowid 1602 +** Fts5SegIter.nPos 1603 +** Fts5SegIter.bDel 1604 +** 1605 +** accordingly and leaves (Fts5SegIter.iLeafOffset) set to the content of 1606 +** the first position list. The position list belonging to document 1607 +** (Fts5SegIter.iRowid). 1568 1608 */ 1569 1609 static void fts5SegIterLoadTerm(Fts5Index *p, Fts5SegIter *pIter, int nKeep){ 1570 1610 u8 *a = pIter->pLeaf->p; /* Buffer to read data from */ 1571 1611 int iOff = pIter->iLeafOffset; /* Offset to read at */ 1572 1612 int nNew; /* Bytes of new data */ 1573 1613 1574 1614 iOff += fts5GetVarint32(&a[iOff], nNew); ................................................................................ 1622 1662 fts5SegIterNextPage(p, pIter); 1623 1663 } 1624 1664 1625 1665 if( p->rc==SQLITE_OK ){ 1626 1666 u8 *a = pIter->pLeaf->p; 1627 1667 pIter->iLeafOffset = fts5GetU16(&a[2]); 1628 1668 fts5SegIterLoadTerm(p, pIter, 0); 1669 + fts5SegIterLoadNPos(p, pIter); 1629 1670 } 1630 1671 } 1631 1672 1632 1673 /* 1633 1674 ** This function is only ever called on iterators created by calls to 1634 1675 ** Fts5IndexQuery() with the FTS5INDEX_QUERY_DESC flag set. 1635 1676 ** 1636 -** When this function is called, iterator pIter points to the first rowid 1637 -** on the current leaf associated with the term being queried. This function 1638 -** advances it to point to the last such rowid and, if necessary, initializes 1639 -** the aRowidOffset[] and iRowidOffset variables. 1677 +** The iterator is in an unusual state when this function is called: the 1678 +** Fts5SegIter.iLeafOffset variable is set to the offset of the start of 1679 +** the position-list size field for the first relevant rowid on the page. 1680 +** Fts5SegIter.rowid is set, but nPos and bDel are not. 1681 +** 1682 +** This function advances the iterator so that it points to the last 1683 +** relevant rowid on the page and, if necessary, initializes the 1684 +** aRowidOffset[] and iRowidOffset variables. At this point the iterator 1685 +** is in its regular state - Fts5SegIter.iLeafOffset points to the first 1686 +** byte of the position list content associated with said rowid. 1640 1687 */ 1641 1688 static void fts5SegIterReverseInitPage(Fts5Index *p, Fts5SegIter *pIter){ 1642 1689 int n = pIter->pLeaf->n; 1643 1690 int i = pIter->iLeafOffset; 1644 1691 u8 *a = pIter->pLeaf->p; 1645 1692 int iRowidOffset = 0; 1646 1693 1647 1694 while( p->rc==SQLITE_OK && i<n ){ 1648 1695 i64 iDelta = 0; 1649 1696 int nPos; 1697 + int bDummy; 1650 1698 1651 - /* READPOSLISTSIZE */ 1652 - i += fts5GetVarint32(&a[i], nPos); 1653 - i += nPos / 2; 1699 + i += fts5GetPoslistSize(&a[i], &nPos, &bDummy); 1700 + i += nPos; 1654 1701 if( i>=n ) break; 1655 1702 i += getVarint(&a[i], (u64*)&iDelta); 1656 1703 if( iDelta==0 ) break; 1657 1704 pIter->iRowid += iDelta; 1658 1705 1659 1706 if( iRowidOffset>=pIter->nRowidOffset ){ 1660 1707 int nNew = pIter->nRowidOffset + 8; ................................................................................ 1667 1714 pIter->nRowidOffset = nNew; 1668 1715 } 1669 1716 1670 1717 pIter->aRowidOffset[iRowidOffset++] = pIter->iLeafOffset; 1671 1718 pIter->iLeafOffset = i; 1672 1719 } 1673 1720 pIter->iRowidOffset = iRowidOffset; 1721 + fts5SegIterLoadNPos(p, pIter); 1674 1722 } 1675 1723 1676 1724 /* 1677 1725 ** 1678 1726 */ 1679 1727 static void fts5SegIterReverseNewPage(Fts5Index *p, Fts5SegIter *pIter){ 1680 1728 assert( pIter->flags & FTS5_SEGITER_REVERSE ); ................................................................................ 1726 1774 static int fts5SegIterIsDelete( 1727 1775 Fts5Index *p, /* FTS5 backend object */ 1728 1776 Fts5SegIter *pIter /* Iterator to advance */ 1729 1777 ){ 1730 1778 int bRet = 0; 1731 1779 Fts5Data *pLeaf = pIter->pLeaf; 1732 1780 if( p->rc==SQLITE_OK && pLeaf ){ 1781 + bRet = pIter->nPos==0; 1782 + /* bRet = pIter->bDel; */ 1783 +#if 0 1733 1784 if( pIter->iLeafOffset<pLeaf->n ){ 1734 - bRet = (pLeaf->p[pIter->iLeafOffset]==0x00); 1785 + bRet = ((pLeaf->p[pIter->iLeafOffset] & 0xFE)==0x00); 1735 1786 }else{ 1736 1787 Fts5Data *pNew = fts5DataRead(p, FTS5_SEGMENT_ROWID( 1737 1788 pIter->iIdx, pIter->pSeg->iSegid, 0, pIter->iLeafPgno+1 1738 1789 )); 1739 1790 if( pNew ){ 1740 - bRet = (pNew->p[4]==0x00); 1791 + bRet = ((pNew->p[4] & 0xFE)==0x00); 1741 1792 fts5DataRelease(pNew); 1742 1793 } 1743 1794 } 1795 +#endif 1744 1796 } 1745 1797 return bRet; 1746 1798 } 1747 1799 1748 1800 /* 1749 1801 ** Advance iterator pIter to the next entry. 1750 1802 ** ................................................................................ 1756 1808 Fts5Index *p, /* FTS5 backend object */ 1757 1809 Fts5SegIter *pIter, /* Iterator to advance */ 1758 1810 int *pbNewTerm /* OUT: Set for new term */ 1759 1811 ){ 1760 1812 assert( pbNewTerm==0 || *pbNewTerm==0 ); 1761 1813 if( p->rc==SQLITE_OK ){ 1762 1814 if( pIter->flags & FTS5_SEGITER_REVERSE ){ 1815 + 1763 1816 if( pIter->iRowidOffset>0 ){ 1764 1817 u8 *a = pIter->pLeaf->p; 1765 1818 int iOff; 1766 1819 int nPos; 1820 + int bDummy; 1767 1821 i64 iDelta; 1768 - pIter->iRowidOffset--; 1769 1822 1770 - pIter->iLeafOffset = iOff = pIter->aRowidOffset[pIter->iRowidOffset]; 1771 - /* READPOSLISTSIZE */ 1772 - iOff += fts5GetVarint32(&a[iOff], nPos); 1773 - iOff += (nPos / 2); 1774 - getVarint(&a[iOff], (u64*)&iDelta); 1775 - pIter->iRowid -= iDelta; 1823 + if( p->rc==SQLITE_OK ){ 1824 + pIter->iRowidOffset--; 1825 + pIter->iLeafOffset = iOff = pIter->aRowidOffset[pIter->iRowidOffset]; 1826 + iOff += fts5GetPoslistSize(&a[iOff], &nPos, &bDummy); 1827 + iOff += nPos; 1828 + getVarint(&a[iOff], (u64*)&iDelta); 1829 + pIter->iRowid -= iDelta; 1830 + fts5SegIterLoadNPos(p, pIter); 1831 + } 1776 1832 }else{ 1777 1833 fts5SegIterReverseNewPage(p, pIter); 1778 1834 } 1779 1835 }else{ 1780 1836 Fts5Data *pLeaf = pIter->pLeaf; 1781 1837 int iOff; 1782 1838 int bNewTerm = 0; 1783 1839 int nKeep = 0; 1784 1840 1785 1841 /* Search for the end of the position list within the current page. */ 1786 1842 u8 *a = pLeaf->p; 1787 1843 int n = pLeaf->n; 1788 1844 1789 - iOff = pIter->iLeafOffset; 1790 - if( iOff<n ){ 1791 - int nPoslist; 1792 - /* READPOSLISTSIZE */ 1793 - iOff += fts5GetVarint32(&a[iOff], nPoslist); 1794 - iOff += nPoslist / 2; 1795 - } 1845 + iOff = pIter->iLeafOffset + pIter->nPos; 1796 1846 1797 1847 if( iOff<n ){ 1798 1848 /* The next entry is on the current page */ 1799 1849 u64 iDelta; 1800 1850 iOff += sqlite3GetVarint(&a[iOff], &iDelta); 1801 1851 pIter->iLeafOffset = iOff; 1802 1852 if( iDelta==0 ){ ................................................................................ 1822 1872 fts5DataRelease(pIter->pLeaf); 1823 1873 pIter->pLeaf = 0; 1824 1874 }else{ 1825 1875 pIter->pLeaf->p = (u8*)pList; 1826 1876 pIter->pLeaf->n = nList; 1827 1877 sqlite3Fts5BufferSet(&p->rc, &pIter->term, strlen(zTerm), (u8*)zTerm); 1828 1878 pIter->iLeafOffset = getVarint(pList, (u64*)&pIter->iRowid); 1829 - if( pIter->flags & FTS5_SEGITER_REVERSE ){ 1830 - assert( 0 ); 1831 - fts5SegIterReverseInitPage(p, pIter); 1832 - } 1833 1879 } 1834 1880 }else{ 1835 1881 iOff = 0; 1836 1882 /* Next entry is not on the current page */ 1837 1883 while( iOff==0 ){ 1838 1884 fts5SegIterNextPage(p, pIter); 1839 1885 pLeaf = pIter->pLeaf; ................................................................................ 1846 1892 pIter->iLeafOffset = iOff; 1847 1893 bNewTerm = 1; 1848 1894 } 1849 1895 } 1850 1896 } 1851 1897 1852 1898 /* Check if the iterator is now at EOF. If so, return early. */ 1853 - if( pIter->pLeaf && bNewTerm ){ 1854 - if( pIter->flags & FTS5_SEGITER_ONETERM ){ 1855 - fts5DataRelease(pIter->pLeaf); 1856 - pIter->pLeaf = 0; 1899 + if( pIter->pLeaf ){ 1900 + if( bNewTerm ){ 1901 + if( pIter->flags & FTS5_SEGITER_ONETERM ){ 1902 + fts5DataRelease(pIter->pLeaf); 1903 + pIter->pLeaf = 0; 1904 + }else{ 1905 + fts5SegIterLoadTerm(p, pIter, nKeep); 1906 + fts5SegIterLoadNPos(p, pIter); 1907 + if( pbNewTerm ) *pbNewTerm = 1; 1908 + } 1857 1909 }else{ 1858 - fts5SegIterLoadTerm(p, pIter, nKeep); 1859 - if( pbNewTerm ) *pbNewTerm = 1; 1910 + fts5SegIterLoadNPos(p, pIter); 1860 1911 } 1861 1912 } 1862 1913 } 1863 1914 } 1864 1915 } 1916 + 1917 +#define SWAPVAL(T, a, b) { T tmp; tmp=a; a=b; b=tmp; } 1865 1918 1866 1919 /* 1867 1920 ** Iterator pIter currently points to the first rowid in a doclist. This 1868 1921 ** function sets the iterator up so that iterates in reverse order through 1869 1922 ** the doclist. 1870 1923 */ 1871 1924 static void fts5SegIterReverse(Fts5Index *p, int iIdx, Fts5SegIter *pIter){ 1872 - Fts5Data *pLeaf; /* Current leaf data */ 1873 - int iOff = pIter->iLeafOffset; /* Byte offset within current leaf */ 1874 1925 Fts5Data *pLast = 0; 1875 1926 int pgnoLast = 0; 1876 1927 1877 - /* Move to the page that contains the last rowid in this doclist. */ 1878 - pLeaf = pIter->pLeaf; 1879 - 1880 1928 if( pIter->pDlidx ){ 1881 1929 int iSegid = pIter->pSeg->iSegid; 1882 1930 pgnoLast = pIter->pDlidx->iLeafPgno; 1883 1931 pLast = fts5DataRead(p, FTS5_SEGMENT_ROWID(iIdx, iSegid, 0, pgnoLast)); 1884 1932 }else{ 1933 + int iOff; /* Byte offset within pLeaf */ 1934 + Fts5Data *pLeaf = pIter->pLeaf; /* Current leaf data */ 1935 + 1936 + /* Currently, Fts5SegIter.iLeafOffset (and iOff) points to the first 1937 + ** byte of position-list content for the current rowid. Back it up 1938 + ** so that it points to the start of the position-list size field. */ 1939 + pIter->iLeafOffset -= sqlite3Fts5GetVarintLen(pIter->nPos*2 + pIter->bDel); 1940 + iOff = pIter->iLeafOffset; 1941 + assert( iOff>=4 ); 1942 + 1943 + /* Search for a new term within the current leaf. If one can be found, 1944 + ** then this page contains the largest rowid for the current term. */ 1885 1945 while( iOff<pLeaf->n ){ 1886 1946 int nPos; 1887 1947 i64 iDelta; 1948 + int bDummy; 1888 1949 1889 - /* Position list size in bytes */ 1890 - /* READPOSLISTSIZE */ 1891 - iOff += fts5GetVarint32(&pLeaf->p[iOff], nPos); 1892 - iOff += (nPos / 2); 1950 + /* Read the position-list size field */ 1951 + iOff += fts5GetPoslistSize(&pLeaf->p[iOff], &nPos, &bDummy); 1952 + iOff += nPos; 1893 1953 if( iOff>=pLeaf->n ) break; 1894 1954 1895 1955 /* Rowid delta. Or, if 0x00, the end of doclist marker. */ 1896 1956 nPos = getVarint(&pLeaf->p[iOff], (u64*)&iDelta); 1897 1957 if( iDelta==0 ) break; 1898 1958 iOff += nPos; 1899 1959 } 1900 1960 1961 + /* If this condition is true then the largest rowid for the current 1962 + ** term may not be stored on the current page. So search forward to 1963 + ** see where said rowid really is. */ 1901 1964 if( iOff>=pLeaf->n ){ 1965 + int pgno; 1902 1966 Fts5StructureSegment *pSeg = pIter->pSeg; 1903 - i64 iAbs = FTS5_SEGMENT_ROWID(iIdx, pSeg->iSegid, 0, pIter->iLeafPgno); 1904 - i64 iLast = FTS5_SEGMENT_ROWID(iIdx, pSeg->iSegid, 0, pSeg->pgnoLast); 1905 1967 1906 1968 /* The last rowid in the doclist may not be on the current page. Search 1907 - ** forward to find the page containing the last rowid. */ 1908 - for(iAbs++; p->rc==SQLITE_OK && iAbs<=iLast; iAbs++){ 1969 + ** forward to find the page containing the last rowid. */ 1970 + for(pgno=pIter->iLeafPgno+1; !p->rc && pgno<=pSeg->pgnoLast; pgno++){ 1971 + i64 iAbs = FTS5_SEGMENT_ROWID(iIdx, pSeg->iSegid, 0, pgno); 1909 1972 Fts5Data *pNew = fts5DataRead(p, iAbs); 1910 1973 if( pNew ){ 1911 1974 int iRowid, iTerm; 1912 1975 fts5LeafHeader(pNew, &iRowid, &iTerm); 1913 1976 if( iRowid ){ 1914 - Fts5Data *pTmp = pLast; 1915 - pLast = pNew; 1916 - pNew = pTmp; 1917 - pgnoLast = iAbs & (((i64)1 << FTS5_DATA_PAGE_B) - 1); 1918 - } 1919 - if( iTerm ){ 1920 - iAbs = iLast; 1977 + SWAPVAL(Fts5Data*, pNew, pLast); 1978 + pgnoLast = pgno; 1921 1979 } 1922 1980 fts5DataRelease(pNew); 1981 + if( iTerm ) break; 1923 1982 } 1924 1983 } 1925 1984 } 1926 1985 } 1927 1986 1928 1987 /* If pLast is NULL at this point, then the last rowid for this doclist 1929 1988 ** lies on the page currently indicated by the iterator. In this case 1930 - ** iLastOff is set to the value that pIter->iLeafOffset will take when 1931 - ** the iterator points to that rowid. 1989 + ** pIter->iLeafOffset is already set to point to the position-list size 1990 + ** field associated with the first relevant rowid on the page. 1932 1991 ** 1933 1992 ** Or, if pLast is non-NULL, then it is the page that contains the last 1934 - ** rowid. 1993 + ** rowid. In this case configure the iterator so that it points to the 1994 + ** first rowid on this page. 1935 1995 */ 1936 1996 if( pLast ){ 1937 1997 int dummy; 1998 + int iOff; 1938 1999 fts5DataRelease(pIter->pLeaf); 1939 2000 pIter->pLeaf = pLast; 1940 2001 pIter->iLeafPgno = pgnoLast; 1941 2002 fts5LeafHeader(pLast, &iOff, &dummy); 1942 2003 iOff += getVarint(&pLast->p[iOff], (u64*)&pIter->iRowid); 1943 2004 pIter->iLeafOffset = iOff; 1944 2005 } ................................................................................ 1962 2023 assert( pIter->flags & FTS5_SEGITER_ONETERM ); 1963 2024 assert( pIter->pDlidx==0 ); 1964 2025 1965 2026 /* Check if the current doclist ends on this page. If it does, return 1966 2027 ** early without loading the doclist-index (as it belongs to a different 1967 2028 ** term. */ 1968 2029 if( pIter->iTermLeafPgno==pIter->iLeafPgno ){ 2030 + int nPos = pIter->nPos; 1969 2031 while( iOff<pLeaf->n ){ 1970 2032 i64 iDelta; 1971 - int nPoslist; 1972 2033 1973 - /* iOff is currently the offset of the size field of a position list. */ 1974 - /* READPOSLISTSIZE */ 1975 - iOff += fts5GetVarint32(&pLeaf->p[iOff], nPoslist); 1976 - iOff += nPoslist / 2; 2034 + /* iOff is currently the offset of the start of position list data */ 2035 + iOff += nPos; 2036 + iOff += getVarint(&pLeaf->p[iOff], (u64*)&iDelta); 2037 + if( iDelta==0 ) return; 1977 2038 1978 2039 if( iOff<pLeaf->n ){ 1979 - iOff += getVarint(&pLeaf->p[iOff], (u64*)&iDelta); 1980 - if( iDelta==0 ) return; 2040 + int bDummy; 2041 + iOff += fts5GetPoslistSize(&pLeaf->p[iOff], &nPos, &bDummy); 1981 2042 } 1982 2043 } 1983 2044 } 1984 2045 1985 2046 fts5DlidxIterInit(p, bRev, iIdx, iSeg, pIter->iTermLeafPgno, &pIter->pDlidx); 1986 2047 } 1987 2048 ................................................................................ 2044 2105 pIter->iLeafPgno = iPg - 1; 2045 2106 fts5SegIterNextPage(p, pIter); 2046 2107 2047 2108 if( pIter->pLeaf ){ 2048 2109 int res; 2049 2110 pIter->iLeafOffset = fts5GetU16(&pIter->pLeaf->p[2]); 2050 2111 fts5SegIterLoadTerm(p, pIter, 0); 2112 + fts5SegIterLoadNPos(p, pIter); 2051 2113 do { 2052 2114 res = fts5BufferCompareBlob(&pIter->term, pTerm, nTerm); 2053 2115 if( res>=0 ) break; 2054 2116 fts5SegIterNext(p, pIter, 0); 2055 2117 }while( pIter->pLeaf && p->rc==SQLITE_OK ); 2056 2118 2057 2119 if( bGe==0 && res ){ ................................................................................ 2122 2184 pLeaf->n = nList; 2123 2185 pIter->pLeaf = pLeaf; 2124 2186 pIter->iLeafOffset = getVarint(pLeaf->p, (u64*)&pIter->iRowid); 2125 2187 2126 2188 if( flags & FTS5INDEX_QUERY_DESC ){ 2127 2189 pIter->flags |= FTS5_SEGITER_REVERSE; 2128 2190 fts5SegIterReverseInitPage(p, pIter); 2191 + }else{ 2192 + fts5SegIterLoadNPos(p, pIter); 2129 2193 } 2130 2194 } 2131 2195 } 2132 2196 2133 2197 /* 2134 2198 ** Zero the iterator passed as the only argument. 2135 2199 */ ................................................................................ 2292 2356 2293 2357 iOff = fts5GetU16(&a[0]); 2294 2358 if( iOff<4 || iOff>=n ){ 2295 2359 p->rc = FTS5_CORRUPT; 2296 2360 }else{ 2297 2361 iOff += getVarint(&a[iOff], (u64*)&pIter->iRowid); 2298 2362 pIter->iLeafOffset = iOff; 2363 + fts5SegIterLoadNPos(p, pIter); 2299 2364 } 2300 2365 } 2301 2366 } 2302 2367 2303 2368 /* 2304 2369 ** Advance the iterator passed as the second argument until it is at or 2305 2370 ** past rowid iFrom. Regardless of the value of iFrom, the iterator is ................................................................................ 2466 2531 ** iterated data. 2467 2532 */ 2468 2533 static void fts5MultiIterNew( 2469 2534 Fts5Index *p, /* FTS5 backend to iterate within */ 2470 2535 Fts5Structure *pStruct, /* Structure of specific index */ 2471 2536 int iIdx, /* Config.aHash[] index of FTS index */ 2472 2537 int bSkipEmpty, /* True to ignore delete-keys */ 2473 - int flags, /* True for >= */ 2538 + int flags, /* FTS5INDEX_QUERY_XXX flags */ 2474 2539 const u8 *pTerm, int nTerm, /* Term to seek to (or NULL/0) */ 2475 2540 int iLevel, /* Level to iterate (-1 for all) */ 2476 2541 int nSegment, /* Number of segments to merge (iLevel>=0) */ 2477 2542 Fts5MultiSegIter **ppOut /* New object */ 2478 2543 ){ 2479 2544 int nSeg; /* Number of segments merged */ 2480 2545 int nSlot; /* Power of two >= nSeg */ ................................................................................ 2649 2714 ** to calculate. */ 2650 2715 if( pSeg->pSeg ){ 2651 2716 int iId = pSeg->pSeg->iSegid; 2652 2717 i64 rowid = FTS5_SEGMENT_ROWID(pSeg->iIdx, iId, 0, pSeg->iLeafPgno); 2653 2718 pIter->iLeafRowid = rowid; 2654 2719 } 2655 2720 2656 - if( iOff<pLeaf->n ){ 2657 - fts5DataReference(pLeaf); 2658 - pIter->pLeaf = pLeaf; 2659 - }else{ 2660 - pIter->nRem = 1; 2661 - fts5ChunkIterNext(p, pIter); 2662 - if( p->rc ) return; 2663 - iOff = 4; 2664 - pLeaf = pIter->pLeaf; 2665 - } 2666 - 2667 - /* READPOSLISTSIZE */ 2668 - iOff += fts5GetVarint32(&pLeaf->p[iOff], pIter->nRem); 2669 - pIter->nRem = pIter->nRem / 2; 2721 + fts5DataReference(pLeaf); 2722 + pIter->pLeaf = pLeaf; 2723 + pIter->nRem = pSeg->nPos; 2670 2724 pIter->n = MIN(pLeaf->n - iOff, pIter->nRem); 2671 2725 pIter->p = pLeaf->p + iOff; 2672 - 2673 2726 if( pIter->n==0 ){ 2674 2727 fts5ChunkIterNext(p, pIter); 2675 2728 } 2676 2729 } 2677 2730 2678 2731 static void fts5ChunkIterRelease(Fts5ChunkIter *pIter){ 2679 2732 fts5DataRelease(pIter->pLeaf); ................................................................................ 3043 3096 if( pPage->buf.n>=p->pConfig->pgsz ){ 3044 3097 fts5WriteFlushLeaf(p, pWriter); 3045 3098 pWriter->bFirstRowidInPage = 1; 3046 3099 } 3047 3100 } 3048 3101 3049 3102 /* 3050 -** Append a docid to the writers output. 3103 +** Append a docid and position-list size field to the writers output. 3051 3104 */ 3052 3105 static void fts5WriteAppendRowid( 3053 3106 Fts5Index *p, 3054 3107 Fts5SegWriter *pWriter, 3055 - i64 iRowid 3108 + i64 iRowid, 3109 + int nPos 3056 3110 ){ 3057 3111 if( p->rc==SQLITE_OK ){ 3058 3112 Fts5PageWriter *pPage = &pWriter->aWriter[0]; 3059 3113 3060 3114 /* If this is to be the first docid written to the page, set the 3061 3115 ** docid-pointer in the page-header. Also append a value to the dlidx 3062 3116 ** buffer, in case a doclist-index is required. */ ................................................................................ 3071 3125 }else{ 3072 3126 assert( p->rc || iRowid>pWriter->iPrevRowid ); 3073 3127 fts5BufferAppendVarint(&p->rc, &pPage->buf, iRowid - pWriter->iPrevRowid); 3074 3128 } 3075 3129 pWriter->iPrevRowid = iRowid; 3076 3130 pWriter->bFirstRowidInDoclist = 0; 3077 3131 pWriter->bFirstRowidInPage = 0; 3132 + 3133 + fts5BufferAppendVarint(&p->rc, &pPage->buf, nPos); 3078 3134 3079 3135 if( pPage->buf.n>=p->pConfig->pgsz ){ 3080 3136 fts5WriteFlushLeaf(p, pWriter); 3081 3137 pWriter->bFirstRowidInPage = 1; 3082 3138 } 3083 3139 } 3084 3140 } ................................................................................ 3372 3428 } 3373 3429 fts5WriteAppendTerm(p, &writer, nTerm, pTerm); 3374 3430 fts5BufferSet(&p->rc, &term, nTerm, pTerm); 3375 3431 bRequireDoclistTerm = 1; 3376 3432 } 3377 3433 3378 3434 /* Append the rowid to the output */ 3379 - fts5WriteAppendRowid(p, &writer, fts5MultiIterRowid(pIter)); 3380 - 3381 - /* Copy the position list from input to output */ 3382 3435 /* WRITEPOSLISTSIZE */ 3383 - fts5WriteAppendPoslistInt(p, &writer, sPos.nRem * 2); 3436 + fts5WriteAppendRowid(p, &writer, fts5MultiIterRowid(pIter), sPos.nRem*2); 3437 + 3384 3438 for(/* noop */; !fts5ChunkIterEof(p, &sPos); fts5ChunkIterNext(p, &sPos)){ 3385 3439 fts5WriteAppendPoslistData(p, &writer, sPos.p, sPos.n); 3386 3440 } 3387 3441 } 3388 3442 3389 3443 fts5ChunkIterRelease(&sPos); 3390 3444 } ................................................................................ 3526 3580 3527 3581 /* 3528 3582 ** Buffer aBuf[] contains a list of varints, all small enough to fit 3529 3583 ** in a 32-bit integer. Return the size of the largest prefix of this 3530 3584 ** list nMax bytes or less in size. 3531 3585 */ 3532 3586 static int fts5PoslistPrefix(const u8 *aBuf, int nMax){ 3533 - int ret = 0; 3587 + int ret; 3588 + u32 dummy; 3589 + ret = fts5GetVarint32(aBuf, dummy); 3534 3590 while( 1 ){ 3535 - u32 dummy; 3536 3591 int i = fts5GetVarint32(&aBuf[ret], dummy); 3537 3592 if( (ret + i) > nMax ) break; 3538 3593 ret += i; 3539 3594 } 3540 3595 return ret; 3541 3596 } 3542 3597 ................................................................................ 3637 3692 int iOff = 0; 3638 3693 int bFirstDocid = 0; 3639 3694 3640 3695 /* The entire doclist will not fit on this leaf. The following 3641 3696 ** loop iterates through the poslists that make up the current 3642 3697 ** doclist. */ 3643 3698 while( iOff<nDoclist ){ 3644 - u32 nPos; 3699 + int nPos; 3645 3700 int nCopy; 3701 + int bDummy; 3646 3702 iOff += getVarint(&pDoclist[iOff], (u64*)&iDelta); 3647 - /* READPOSLISTSIZE */ 3648 - nCopy = fts5GetVarint32(&pDoclist[iOff], nPos); 3649 - nCopy += (nPos / 2); 3703 + nCopy = fts5GetPoslistSize(&pDoclist[iOff], &nPos, &bDummy); 3704 + nCopy += nPos; 3650 3705 iRowid += iDelta; 3651 3706 3652 3707 if( bFirstDocid ){ 3653 3708 fts5PutU16(&pBuf->p[0], pBuf->n); /* first docid on page */ 3654 3709 pBuf->n += sqlite3PutVarint(&pBuf->p[pBuf->n], iRowid); 3655 3710 bFirstDocid = 0; 3656 3711 }else{ ................................................................................ 3666 3721 /* The entire poslist will not fit on this leaf. So it needs 3667 3722 ** to be broken into sections. The only qualification being 3668 3723 ** that each varint must be stored contiguously. */ 3669 3724 const u8 *pPoslist = &pDoclist[iOff]; 3670 3725 int iPos = 0; 3671 3726 while( 1 ){ 3672 3727 int nSpace = pgsz - pBuf->n; 3673 - int n; 3728 + int n = 0; 3674 3729 if( (nCopy - iPos)<=nSpace ){ 3675 3730 n = nCopy - iPos; 3676 3731 }else{ 3677 3732 n = fts5PoslistPrefix(&pPoslist[iPos], nSpace); 3678 3733 } 3734 + assert( n>0 ); 3679 3735 fts5BufferSafeAppendBlob(pBuf, &pPoslist[iPos], n); 3680 3736 iPos += n; 3681 3737 if( iPos>=nCopy ) break; 3682 3738 fts5WriteFlushLeaf(p, &writer); 3683 3739 pBuf = &writer.aWriter[0].buf; 3684 3740 } 3685 3741 bFirstDocid = 1; 3686 3742 } 3687 - assert( pBuf->n<=pgsz ); 3688 3743 iOff += nCopy; 3689 3744 } 3690 3745 } 3691 3746 3692 3747 pBuf->p[pBuf->n++] = '\0'; 3693 3748 assert( pBuf->n<=pBuf->nSpace ); 3694 3749 zPrev = (const u8*)zTerm; ................................................................................ 4093 4148 } 4094 4149 fts5ChunkIterRelease(&iter); 4095 4150 } 4096 4151 } 4097 4152 4098 4153 static void fts5DoclistIterNext(Fts5DoclistIter *pIter){ 4099 4154 if( pIter->i<pIter->n ){ 4155 + int bDummy; 4100 4156 if( pIter->i ){ 4101 4157 i64 iDelta; 4102 4158 pIter->i += getVarint(&pIter->a[pIter->i], (u64*)&iDelta); 4103 4159 if( pIter->bDesc ){ 4104 4160 pIter->iRowid -= iDelta; 4105 4161 }else{ 4106 4162 pIter->iRowid += iDelta; 4107 4163 } 4108 4164 }else{ 4109 4165 pIter->i += getVarint(&pIter->a[pIter->i], (u64*)&pIter->iRowid); 4110 4166 } 4111 - /* READPOSLISTSIZE */ 4112 - pIter->i += fts5GetVarint32(&pIter->a[pIter->i], pIter->nPoslist); 4113 - pIter->nPoslist = pIter->nPoslist / 2; 4167 + pIter->i += fts5GetPoslistSize( 4168 + &pIter->a[pIter->i], &pIter->nPoslist, &bDummy 4169 + ); 4114 4170 pIter->aPoslist = &pIter->a[pIter->i]; 4115 4171 pIter->i += pIter->nPoslist; 4116 4172 }else{ 4117 4173 pIter->aPoslist = 0; 4118 4174 } 4119 4175 } 4120 4176 ................................................................................ 4171 4227 Fts5Buffer out; 4172 4228 Fts5Buffer tmp; 4173 4229 memset(&out, 0, sizeof(out)); 4174 4230 memset(&tmp, 0, sizeof(tmp)); 4175 4231 4176 4232 fts5DoclistIterInit(p1, bDesc, &i1); 4177 4233 fts5DoclistIterInit(p2, bDesc, &i2); 4178 - while( i1.aPoslist!=0 || i2.aPoslist!=0 ){ 4234 + while( p->rc==SQLITE_OK && (i1.aPoslist!=0 || i2.aPoslist!=0) ){ 4179 4235 if( i2.aPoslist==0 || (i1.aPoslist && 4180 4236 ( (bDesc && i1.iRowid>i2.iRowid) || (!bDesc && i1.iRowid<i2.iRowid) ) 4181 4237 )){ 4182 4238 /* Copy entry from i1 */ 4183 4239 fts5MergeAppendDocid(&p->rc, bDesc, &out, &iLastRowid, i1.iRowid); 4184 4240 /* WRITEPOSLISTSIZE */ 4185 4241 fts5BufferAppendVarint(&p->rc, &out, i1.nPoslist * 2); ................................................................................ 4432 4488 } 4433 4489 if( rc==SQLITE_OK && ck1!=ck2 ) rc = FTS5_CORRUPT; 4434 4490 4435 4491 /* If this is a prefix query, check that the results returned if the 4436 4492 ** the index is disabled are the same. In both ASC and DESC order. */ 4437 4493 if( iIdx>0 && rc==SQLITE_OK ){ 4438 4494 int f = flags|FTS5INDEX_QUERY_TEST_NOIDX; 4495 +static int nCall = 0; 4496 +nCall++; 4439 4497 ck2 = 0; 4440 4498 rc = fts5QueryCksum(p, z, n, f, &ck2); 4441 4499 if( rc==SQLITE_OK && ck1!=ck2 ) rc = FTS5_CORRUPT; 4442 4500 } 4443 4501 if( iIdx>0 && rc==SQLITE_OK ){ 4444 4502 int f = flags|FTS5INDEX_QUERY_TEST_NOIDX|FTS5INDEX_QUERY_DESC; 4445 4503 ck2 = 0; ................................................................................ 5068 5126 5069 5127 if( iOff<n ){ 5070 5128 iOff += sqlite3GetVarint(&a[iOff], (u64*)&iDocid); 5071 5129 sqlite3Fts5BufferAppendPrintf(pRc, pBuf, " rowid=%lld", iDocid); 5072 5130 } 5073 5131 while( iOff<n ){ 5074 5132 int nPos; 5075 - /* READPOSLISTSIZE */ 5076 - iOff += fts5GetVarint32(&a[iOff], nPos); 5077 - iOff += fts5DecodePoslist(pRc, pBuf, &a[iOff], MIN(n-iOff, nPos / 2)); 5133 + int bDummy; 5134 + iOff += fts5GetPoslistSize(&a[iOff], &nPos, &bDummy); 5135 + iOff += fts5DecodePoslist(pRc, pBuf, &a[iOff], MIN(n-iOff, nPos)); 5078 5136 if( iOff<n ){ 5079 5137 i64 iDelta; 5080 5138 iOff += sqlite3GetVarint(&a[iOff], (u64*)&iDelta); 5081 5139 if( iDelta==0 ) return iOff; 5082 5140 iDocid += iDelta; 5083 5141 sqlite3Fts5BufferAppendPrintf(pRc, pBuf, " rowid=%lld", iDocid); 5084 5142 }
Changes to ext/fts5/test/fts5aa.test.
17 17 18 18 # If SQLITE_ENABLE_FTS3 is defined, omit this file. 19 19 ifcapable !fts5 { 20 20 finish_test 21 21 return 22 22 } 23 23 24 -if 1 { 25 - 26 24 do_execsql_test 1.0 { 27 25 CREATE VIRTUAL TABLE t1 USING fts5(a, b, c); 28 26 SELECT name, sql FROM sqlite_master; 29 27 } { 30 28 t1 {CREATE VIRTUAL TABLE t1 USING fts5(a, b, c)} 31 29 t1_data {CREATE TABLE 't1_data'(id INTEGER PRIMARY KEY, block BLOB)} 32 30 t1_content {CREATE TABLE 't1_content'(id INTEGER PRIMARY KEY, c0, c1, c2)} ................................................................................ 325 323 SELECT rowid FROM t1 WHERE t1 MATCH 'o'; 326 324 } {1} 327 325 328 326 do_execsql_test 13.6 { 329 327 SELECT rowid FROM t1 WHERE t1 MATCH '.'; 330 328 } {} 331 329 332 -} 333 330 #------------------------------------------------------------------------- 334 331 # 335 332 reset_db 336 333 do_execsql_test 14.1 { 337 334 CREATE VIRTUAL TABLE t1 USING fts5(x, y); 338 335 INSERT INTO t1(t1, rank) VALUES('pgsz', 32); 339 336 WITH d(x,y) AS (
Changes to ext/fts5/test/fts5ah.test.
90 90 91 91 do_test 1.6.$tn.1 { 92 92 set n [execsql_reads $q] 93 93 expr {$n < ($nReadX / 10)} 94 94 } {1} 95 95 96 96 do_test 1.6.$tn.2 { 97 - set n [execsql_reads "$q ORDER BY rowid ASC"] 97 + set n [execsql_reads "$q ORDER BY rowid DESC"] 98 98 expr {$n < ($nReadX / 10)} 99 99 } {1} 100 100 101 101 do_execsql_test 1.6.$tn.3 $q [lsort -int -incr $res] 102 102 do_execsql_test 1.6.$tn.4 "$q ORDER BY rowid DESC" [lsort -int -decr $res] 103 103 } 104 104 105 105 #db eval {SELECT rowid, fts5_decode(rowid, block) aS r FROM t1_data} {puts $r} 106 106 107 107 finish_test 108 108