Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Optimize seek operations on fts5 b-trees. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
8cf02090ce53ec150492d77d9e5e5f27 |
User & Date: | dan 2015-07-04 18:44:07.139 |
Context
2015-07-05
| ||
22:15 | Do not allow recursive CTEs that use aggregate queries in the recursive part. (check-in: 6d2999afbc user: drh tags: trunk) | |
2015-07-04
| ||
18:44 | Optimize seek operations on fts5 b-trees. (check-in: 8cf02090ce user: dan tags: trunk) | |
18:15 | Preserve the number of requested PAGECACHE pages even if the memory pointer or size is zero. Enhance the pcache1.c header comment to explain the memory layout of a page cache line. (check-in: dacb2a615c user: drh tags: trunk) | |
Changes
Changes to ext/fts5/fts5_index.c.
︙ | ︙ | |||
2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 | iOff += fts5GetPoslistSize(&pLeaf->p[iOff], &nPos, &bDummy); iOff += nPos; } } pIter->pDlidx = fts5DlidxIterInit(p, bRev, iSeg, pIter->iTermLeafPgno); } /* ** Initialize the object pIter to point to term pTerm/nTerm within segment ** pSeg. If there is no such term in the index, the iterator is set to EOF. ** ** If an error occurs, Fts5Index.rc is set to an appropriate error code. If ** an error has already occurred when this function is called, it is a no-op. | > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 2020 2021 2022 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 2049 2050 2051 2052 2053 2054 2055 2056 2057 2058 2059 2060 2061 2062 2063 2064 2065 2066 2067 2068 2069 2070 2071 2072 2073 2074 2075 2076 2077 2078 2079 2080 2081 2082 2083 2084 2085 2086 2087 2088 2089 2090 2091 2092 2093 2094 2095 2096 2097 2098 2099 2100 2101 2102 2103 2104 2105 2106 2107 2108 2109 2110 2111 2112 2113 2114 2115 2116 2117 2118 2119 2120 2121 2122 2123 2124 2125 2126 2127 2128 2129 2130 2131 2132 | iOff += fts5GetPoslistSize(&pLeaf->p[iOff], &nPos, &bDummy); iOff += nPos; } } pIter->pDlidx = fts5DlidxIterInit(p, bRev, iSeg, pIter->iTermLeafPgno); } #ifdef SQLITE_DEBUG static void fts5AssertNodeSeekOk( Fts5Data *pNode, const u8 *pTerm, int nTerm, /* Term to search for */ int iExpectPg, int bExpectDlidx ){ int bDlidx; int iPg; int rc = SQLITE_OK; Fts5NodeIter node; fts5NodeIterInit(pNode->p, pNode->n, &node); assert( node.term.n==0 ); iPg = node.iChild; bDlidx = node.bDlidx; for(fts5NodeIterNext(&rc, &node); node.aData && fts5BufferCompareBlob(&node.term, pTerm, nTerm)<=0; fts5NodeIterNext(&rc, &node) ){ iPg = node.iChild; bDlidx = node.bDlidx; } fts5NodeIterFree(&node); assert( rc!=SQLITE_OK || iPg==iExpectPg ); assert( rc!=SQLITE_OK || bDlidx==bExpectDlidx ); } #else #define fts5AssertNodeSeekOk(v,w,x,y,z) #endif /* ** Argument pNode is an internal b-tree node. This function searches ** within the node for the largest term that is smaller than or equal ** to (pTerm/nTerm). ** ** It returns the associated page number. Or, if (pTerm/nTerm) is smaller ** than all terms within the node, the leftmost child page number. ** ** Before returning, (*pbDlidx) is set to true if the last term on the ** returned child page number has a doclist-index. Or left as is otherwise. */ static int fts5NodeSeek( Fts5Data *pNode, /* Node to search */ const u8 *pTerm, int nTerm, /* Term to search for */ int *pbDlidx /* OUT: True if dlidx flag is set */ ){ int iPg; u8 *pPtr = pNode->p; u8 *pEnd = &pPtr[pNode->n]; int nMatch = 0; /* Number of bytes of pTerm already matched */ assert( *pbDlidx==0 ); pPtr += fts5GetVarint32(pPtr, iPg); while( pPtr<pEnd ){ int nEmpty = 0; int nKeep; int nNew; /* If there is a "no terms" record at pPtr, read it now. Store the ** number of termless pages in nEmpty. If it indicates a doclist-index, ** set (*pbDlidx) to true.*/ if( *pPtr<2 ){ *pbDlidx = (*pPtr==0x01); pPtr++; pPtr += fts5GetVarint32(pPtr, nEmpty); } /* Read the next "term" pointer. Set nKeep to the number of bytes to ** keep from the previous term, and nNew to the number of bytes of ** new data that will be appended to it. */ nKeep = (int)*pPtr++; nNew = (int)*pPtr++; if( (nKeep | nNew) & 0x0080 ){ pPtr -= 2; pPtr += fts5GetVarint32(pPtr, nKeep); pPtr += fts5GetVarint32(pPtr, nNew); } nKeep -= 2; /* Compare (pTerm/nTerm) to the current term on the node (the one described ** by nKeep/nNew). If the node term is larger, break out of the while() ** loop. ** ** Otherwise, if (pTerm/nTerm) is larger or the two terms are equal, ** leave variable nMatch set to the size of the largest prefix common to ** both terms in bytes. */ if( nKeep==nMatch ){ int nTst = MIN(nNew, nTerm-nMatch); int i; for(i=0; i<nTst; i++){ if( pTerm[nKeep+i]!=pPtr[i] ) break; } nMatch += i; assert( nMatch<=nTerm ); if( i<nNew && (nMatch==nTerm || pPtr[i] > pTerm[nMatch]) ) break; }else if( nKeep<nMatch ){ break; } iPg += 1 + nEmpty; *pbDlidx = 0; pPtr += nNew; } fts5AssertNodeSeekOk(pNode, pTerm, nTerm, iPg, *pbDlidx); return iPg; } /* ** Initialize the object pIter to point to term pTerm/nTerm within segment ** pSeg. If there is no such term in the index, the iterator is set to EOF. ** ** If an error occurs, Fts5Index.rc is set to an appropriate error code. If ** an error has already occurred when this function is called, it is a no-op. |
︙ | ︙ | |||
2036 2037 2038 2039 2040 2041 2042 | assert( pTerm && nTerm ); memset(pIter, 0, sizeof(*pIter)); pIter->pSeg = pSeg; /* This block sets stack variable iPg to the leaf page number that may ** contain term (pTerm/nTerm), if it is present in the segment. */ for(h=pSeg->nHeight-1; h>0; h--){ | < < < | < < < < < < < < < < | 2148 2149 2150 2151 2152 2153 2154 2155 2156 2157 2158 2159 2160 2161 2162 2163 2164 2165 2166 | assert( pTerm && nTerm ); memset(pIter, 0, sizeof(*pIter)); pIter->pSeg = pSeg; /* This block sets stack variable iPg to the leaf page number that may ** contain term (pTerm/nTerm), if it is present in the segment. */ for(h=pSeg->nHeight-1; h>0; h--){ i64 iRowid = FTS5_SEGMENT_ROWID(pSeg->iSegid, h, iPg); Fts5Data *pNode = fts5DataRead(p, iRowid); if( pNode==0 ) break; iPg = fts5NodeSeek(pNode, pTerm, nTerm, &bDlidx); fts5DataRelease(pNode); } if( iPg<pSeg->pgnoFirst ){ iPg = pSeg->pgnoFirst; bDlidx = 0; } |
︙ | ︙ |