Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | Experiment using linear interpolation, instead of a strict binary search, when looking for integer-keyed rows on a single b-tree page. The experiment was not successful. The number of key comparisons is reduced by about 15%, but the added complexity of the search logic causes an overall reduction in performance. The patch is saved for historical reference only. |
|---|---|
| Downloads: | Tarball | ZIP archive | SQL archive |
| Timelines: | family | ancestors | linear-interpolation |
| Files: | files | file ages | folders |
| SHA1: |
c705cf856d314d1e9e5371b7758d3c8a |
| User & Date: | drh 2014-09-24 04:38:14 |
Context
|
2014-09-24
| ||
| 04:38 | Experiment using linear interpolation, instead of a strict binary search, when looking for integer-keyed rows on a single b-tree page. The experiment was not successful. The number of key comparisons is reduced by about 15%, but the added complexity of the search logic causes an overall reduction in performance. The patch is saved for historical reference only. Closed-Leaf check-in: c705cf85 user: drh tags: linear-interpolation | |
| 02:05 | Have the clearCell() routine return the cell size to the caller, rather than have the caller make a separate call to cellSizePtr(). check-in: f21d2175 user: drh tags: trunk | |
Changes
Changes to src/btree.c.
4691
4692
4693
4694
4695
4696
4697
4698
4699
4700
4701
4702
4703
4704
4705
4706
4707
4708
4709
4710
4711
4712
4713
4714
4715
4716
4717
4718
4719
....
4720
4721
4722
4723
4724
4725
4726
4727
4728
4729
4730
4731
4732
4733
4734
4735
|
assert( pPage->intKey==(pIdxKey==0) );
lwr = 0;
upr = pPage->nCell-1;
assert( biasRight==0 || biasRight==1 );
idx = upr>>(1-biasRight); /* idx = biasRight ? upr : (lwr+upr)/2; */
pCur->aiIdx[pCur->iPage] = (u16)idx;
if( xRecordCompare==0 ){
for(;;){
i64 nCellKey;
pCell = findCell(pPage, idx) + pPage->childPtrSize;
if( pPage->intKeyLeaf ){
while( 0x80 <= *(pCell++) ){
if( pCell>=pPage->aDataEnd ) return SQLITE_CORRUPT_BKPT;
}
}
getVarint(pCell, (u64*)&nCellKey);
if( nCellKey<intKey ){
lwr = idx+1;
if( lwr>upr ){ c = -1; break; }
}else if( nCellKey>intKey ){
upr = idx-1;
if( lwr>upr ){ c = +1; break; }
}else{
assert( nCellKey==intKey );
pCur->curFlags |= BTCF_ValidNKey;
pCur->info.nKey = nCellKey;
pCur->aiIdx[pCur->iPage] = (u16)idx;
if( !pPage->leaf ){
lwr = idx;
................................................................................
goto moveto_next_layer;
}else{
*pRes = 0;
rc = SQLITE_OK;
goto moveto_finish;
}
}
assert( lwr+upr>=0 );
idx = (lwr+upr)>>1; /* idx = (lwr+upr)/2; */
}
}else{
for(;;){
int nCell;
pCell = findCell(pPage, idx) + pPage->childPtrSize;
/* The maximum supported page-size is 65536 bytes. This means that
|
>
>
>
>
>
>
|
>
|
>
>
>
>
>
>
>
>
|
4691
4692
4693
4694
4695
4696
4697
4698
4699
4700
4701
4702
4703
4704
4705
4706
4707
4708
4709
4710
4711
4712
4713
4714
4715
4716
4717
4718
4719
4720
4721
4722
4723
4724
4725
....
4726
4727
4728
4729
4730
4731
4732
4733
4734
4735
4736
4737
4738
4739
4740
4741
4742
4743
4744
4745
4746
4747
4748
4749
4750
|
assert( pPage->intKey==(pIdxKey==0) );
lwr = 0;
upr = pPage->nCell-1;
assert( biasRight==0 || biasRight==1 );
idx = upr>>(1-biasRight); /* idx = biasRight ? upr : (lwr+upr)/2; */
pCur->aiIdx[pCur->iPage] = (u16)idx;
if( xRecordCompare==0 ){
u8 bits = 0;
i64 iLwr = 0, iUpr = 0;
for(;;){
i64 nCellKey;
pCell = findCell(pPage, idx) + pPage->childPtrSize;
if( pPage->intKeyLeaf ){
while( 0x80 <= *(pCell++) ){
if( pCell>=pPage->aDataEnd ) return SQLITE_CORRUPT_BKPT;
}
}
getVarint(pCell, (u64*)&nCellKey);
if( nCellKey<intKey ){
lwr = idx+1;
if( lwr>upr ){ c = -1; break; }
iLwr = nCellKey;
bits |= 1;
}else if( nCellKey>intKey ){
upr = idx-1;
if( lwr>upr ){ c = +1; break; }
iUpr = nCellKey;
bits |= 2;
}else{
assert( nCellKey==intKey );
pCur->curFlags |= BTCF_ValidNKey;
pCur->info.nKey = nCellKey;
pCur->aiIdx[pCur->iPage] = (u16)idx;
if( !pPage->leaf ){
lwr = idx;
................................................................................
goto moveto_next_layer;
}else{
*pRes = 0;
rc = SQLITE_OK;
goto moveto_finish;
}
}
assert( lwr>=0 && upr>=lwr );
if( bits<3 || upr<=lwr+2 ){
idx = (lwr+upr)>>1; /* idx = (lwr+upr)/2; */
}else if( (iUpr - iLwr)>100000 ){
i64 spacing = (iUpr-iLwr)/(upr-lwr);
idx = (intKey-iLwr)/spacing+lwr;
assert( idx>=lwr && idx<=upr );
}else{
idx = (intKey-iLwr)*(upr-lwr)/(iUpr-iLwr)+lwr;
assert( idx>=lwr && idx<=upr );
}
}
}else{
for(;;){
int nCell;
pCell = findCell(pPage, idx) + pPage->childPtrSize;
/* The maximum supported page-size is 65536 bytes. This means that
|