/ Check-in [a9877f61]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Bias the b-tree binary search toward the high end. The common case is to append data and this heuristic makes append run much faster because there are fewer comparisons. (CVS 3740)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: a9877f616b24737152627841fcbd80cc28426f1e
User & Date: drh 2007-03-29 04:43:26
Context
2007-03-29
05:51
Change BtreeMoveto so that it can be biased to the right or to the center. Use a right bias when appending and a center bias when searching. This gives about a 15% reduction in calls to sqlite3VdbeRecordCompare. (CVS 3741) check-in: ad4a6b1a user: drh tags: trunk
04:43
Bias the b-tree binary search toward the high end. The common case is to append data and this heuristic makes append run much faster because there are fewer comparisons. (CVS 3740) check-in: a9877f61 user: drh tags: trunk
02:26
Get LEMON working again when YYSTACKDEPTH is greater than zero. (CVS 3739) check-in: e72c81db user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/btree.c.

     5      5   ** a legal notice, here is a blessing:
     6      6   **
     7      7   **    May you do good and not evil.
     8      8   **    May you find forgiveness for yourself and forgive others.
     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12         -** $Id: btree.c,v 1.343 2007/03/27 14:05:23 drh Exp $
           12  +** $Id: btree.c,v 1.344 2007/03/29 04:43:26 drh Exp $
    13     13   **
    14     14   ** This file implements a external (disk-based) database using BTrees.
    15     15   ** For a detailed discussion of BTrees, refer to
    16     16   **
    17     17   **     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
    18     18   **     "Sorting And Searching", pages 473-480. Addison-Wesley
    19     19   **     Publishing Company, Reading, Massachusetts.
................................................................................
  3301   3301   **                  exactly matches pKey.
  3302   3302   **
  3303   3303   **     *pRes>0      The cursor is left pointing at an entry that
  3304   3304   **                  is larger than pKey.
  3305   3305   */
  3306   3306   int sqlite3BtreeMoveto(BtCursor *pCur, const void *pKey, i64 nKey, int *pRes){
  3307   3307     int rc;
  3308         -  int tryRightmost;
  3309   3308     rc = moveToRoot(pCur);
  3310   3309     if( rc ) return rc;
  3311   3310     assert( pCur->pPage );
  3312   3311     assert( pCur->pPage->isInit );
  3313         -  tryRightmost = pCur->pPage->intKey;
  3314   3312     if( pCur->eState==CURSOR_INVALID ){
  3315   3313       *pRes = -1;
  3316   3314       assert( pCur->pPage->nCell==0 );
  3317   3315       return SQLITE_OK;
  3318   3316     }
  3319   3317     for(;;){
  3320   3318       int lwr, upr;
................................................................................
  3322   3320       MemPage *pPage = pCur->pPage;
  3323   3321       int c = -1;  /* pRes return if table is empty must be -1 */
  3324   3322       lwr = 0;
  3325   3323       upr = pPage->nCell-1;
  3326   3324       if( !pPage->intKey && pKey==0 ){
  3327   3325         return SQLITE_CORRUPT_BKPT;
  3328   3326       }
  3329         -    while( lwr<=upr ){
         3327  +    pCur->idx = upr;
         3328  +    if( lwr<=upr ) for(;;){
  3330   3329         void *pCellKey;
  3331   3330         i64 nCellKey;
  3332         -      pCur->idx = (lwr+upr)/2;
  3333   3331         pCur->info.nSize = 0;
  3334   3332         if( pPage->intKey ){
  3335   3333           u8 *pCell;
  3336         -        if( tryRightmost ){
  3337         -          pCur->idx = upr;
  3338         -        }
  3339   3334           pCell = findCell(pPage, pCur->idx) + pPage->childPtrSize;
  3340   3335           if( pPage->hasData ){
  3341   3336             u32 dummy;
  3342   3337             pCell += getVarint32(pCell, &dummy);
  3343   3338           }
  3344   3339           getVarint(pCell, (u64 *)&nCellKey);
  3345   3340           if( nCellKey<nKey ){
  3346   3341             c = -1;
  3347   3342           }else if( nCellKey>nKey ){
  3348   3343             c = +1;
  3349         -          tryRightmost = 0;
  3350   3344           }else{
  3351   3345             c = 0;
  3352   3346           }
  3353   3347         }else{
  3354   3348           int available;
  3355   3349           pCellKey = (void *)fetchPayload(pCur, &available, 0);
  3356   3350           nCellKey = pCur->info.nKey;
................................................................................
  3376   3370           }
  3377   3371         }
  3378   3372         if( c<0 ){
  3379   3373           lwr = pCur->idx+1;
  3380   3374         }else{
  3381   3375           upr = pCur->idx-1;
  3382   3376         }
         3377  +      if( lwr>upr ){
         3378  +        break;
         3379  +      }
         3380  +      pCur->idx = (lwr+upr)/2;
  3383   3381       }
  3384   3382       assert( lwr==upr+1 );
  3385   3383       assert( pPage->isInit );
  3386   3384       if( pPage->leaf ){
  3387   3385         chldPg = 0;
  3388   3386       }else if( lwr>=pPage->nCell ){
  3389   3387         chldPg = get4byte(&pPage->aData[pPage->hdrOffset+8]);