Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Further optimizations for fts5 b-tree seeks. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
f37899686c032145f431f81c10727385 |
User & Date: | dan 2015-07-07 08:29:32.749 |
Context
2015-07-07
| ||
19:07 | Add a test case to verify that "PRAGMA data_version" works as expected when an OTA client writes to the database. (check-in: 6441f2dc9e user: dan tags: trunk) | |
08:29 | Further optimizations for fts5 b-tree seeks. (check-in: f37899686c user: dan tags: trunk) | |
2015-07-06
| ||
20:27 | Speed up seek operations on fts5 b-tree structures. (check-in: 7b7da1eb43 user: dan tags: trunk) | |
Changes
Changes to ext/fts5/fts5_index.c.
︙ | ︙ | |||
2128 2129 2130 2131 2132 2133 2134 2135 2136 2137 2138 2139 2140 2141 2142 2143 2144 2145 2146 2147 | *pbDlidx = 0; pPtr += nNew; } fts5AssertNodeSeekOk(pNode, pTerm, nTerm, iPg, *pbDlidx); return iPg; } /* ** The iterator object passed as the second argument currently contains ** no valid values except for the Fts5SegIter.pLeaf member variable. This ** function searches the leaf page for a term matching (pTerm/nTerm). ** */ static void fts5LeafSeek( Fts5Index *p, /* Leave any error code here */ int bGe, /* True for a >= search */ Fts5SegIter *pIter, /* Iterator to seek */ const u8 *pTerm, int nTerm /* Term to search for */ ){ | > > > > > > > > > > > > > > > > > > > > > | 2128 2129 2130 2131 2132 2133 2134 2135 2136 2137 2138 2139 2140 2141 2142 2143 2144 2145 2146 2147 2148 2149 2150 2151 2152 2153 2154 2155 2156 2157 2158 2159 2160 2161 2162 2163 2164 2165 2166 2167 2168 | *pbDlidx = 0; pPtr += nNew; } fts5AssertNodeSeekOk(pNode, pTerm, nTerm, iPg, *pbDlidx); return iPg; } #define fts5IndexGetVarint32(a, iOff, nVal) { \ nVal = a[iOff++]; \ if( nVal & 0x80 ){ \ iOff--; \ iOff += fts5GetVarint32(&a[iOff], nVal); \ } \ } #define fts5IndexSkipVarint(a, iOff) { \ int iEnd = iOff+9; \ while( (a[iOff++] & 0x80) && iOff<iEnd ); \ } /* ** The iterator object passed as the second argument currently contains ** no valid values except for the Fts5SegIter.pLeaf member variable. This ** function searches the leaf page for a term matching (pTerm/nTerm). ** ** If the specified term is found on the page, then the iterator is left ** pointing to it. If argument bGe is zero and the term is not found, ** the iterator is left pointing at EOF. ** ** If bGe is non-zero and the specified term is not found, then the ** iterator is left pointing to the smallest term in the segment that ** is larger than the specified term, even if this term is not on the ** current page. */ static void fts5LeafSeek( Fts5Index *p, /* Leave any error code here */ int bGe, /* True for a >= search */ Fts5SegIter *pIter, /* Iterator to seek */ const u8 *pTerm, int nTerm /* Term to search for */ ){ |
︙ | ︙ | |||
2164 2165 2166 2167 2168 2169 2170 | while( 1 ){ int i; int nCmp; i64 rowid; /* Figure out how many new bytes are in this term */ | | < < < < < | 2185 2186 2187 2188 2189 2190 2191 2192 2193 2194 2195 2196 2197 2198 2199 | while( 1 ){ int i; int nCmp; i64 rowid; /* Figure out how many new bytes are in this term */ fts5IndexGetVarint32(a, iOff, nNew); if( nKeep<nMatch ){ goto search_failed; } assert( nKeep>=nMatch ); if( nKeep==nMatch ){ |
︙ | ︙ | |||
2196 2197 2198 2199 2200 2201 2202 | }else if( i<nNew && a[iOff+i]>pTerm[nMatch] ){ goto search_failed; } } iOff += nNew; /* Skip past the doclist. If the end of the page is reached, bail out. */ | < | > > | > > | > < > | > | > < < < < | < | 2212 2213 2214 2215 2216 2217 2218 2219 2220 2221 2222 2223 2224 2225 2226 2227 2228 2229 2230 2231 2232 2233 2234 2235 2236 2237 2238 2239 2240 2241 2242 2243 2244 2245 | }else if( i<nNew && a[iOff+i]>pTerm[nMatch] ){ goto search_failed; } } iOff += nNew; /* Skip past the doclist. If the end of the page is reached, bail out. */ while( 1 ){ int nPos; /* Skip past docid delta */ fts5IndexSkipVarint(a, iOff); /* Skip past position list */ fts5IndexGetVarint32(a, iOff, nPos); iOff += (nPos >> 1); if( iOff>=n ) goto search_failed; /* If this is the end of the doclist, break out of the loop */ if( a[iOff]==0x00 ){ iOff++; break; } }; /* Read the nKeep field of the next term. */ fts5IndexGetVarint32(a, iOff, nKeep); } search_failed: if( bGe==0 ){ fts5DataRelease(pIter->pLeaf); pIter->pLeaf = 0; return; |
︙ | ︙ |