/ Check-in [c705cf85]
Login

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: c705cf856d314d1e9e5371b7758d3c8a46099391
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
Hide Diffs Unified Diffs Ignore Whitespace Patch

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