/ Check-in [88680698]
Login

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

Overview
Comment:More improvements to sqlite3BtreeMovetoUnpacked() performance.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | btree-optimization
Files: files | file ages | folders
SHA1:88680698231b7141401f7166e3aff8dbc6008030
User & Date: drh 2013-11-25 14:10:15
Context
2013-11-25
15:01
More optimizations to sqlite3BtreeMovetoUnpacked(). But there are failures in TH3. Committing this intermediate state to facilitate bisecting. check-in: f80497be user: drh tags: btree-optimization
14:10
More improvements to sqlite3BtreeMovetoUnpacked() performance. check-in: 88680698 user: drh tags: btree-optimization
02:38
Performance improvements in sqlite3BtreeMovetoUnpacked(). check-in: d0fb7ace user: drh tags: btree-optimization
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/btree.c.

  4658   4658       ** would have already detected db corruption. Similarly, pPage must
  4659   4659       ** be the right kind (index or table) of b-tree page. Otherwise
  4660   4660       ** a moveToChild() or moveToRoot() call would have detected corruption.  */
  4661   4661       assert( pPage->nCell>0 );
  4662   4662       assert( pPage->intKey==(pIdxKey==0) );
  4663   4663       lwr = 0;
  4664   4664       upr = pPage->nCell-1;
  4665         -    if( biasRight ){
  4666         -      pCur->aiIdx[pCur->iPage] = (u16)(idx = upr);
  4667         -    }else{
  4668         -      pCur->aiIdx[pCur->iPage] = (u16)(idx = (upr+lwr)/2);
  4669         -    }
         4665  +    idx = biasRight ? upr : (upr+lwr)/2;
         4666  +    pCur->aiIdx[pCur->iPage] = (u16)idx;
  4670   4667       pCur->info.nSize = 0;
  4671   4668       if( pPage->intKey ){
  4672         -      assert( idx==pCur->aiIdx[pCur->iPage] );
  4673   4669         for(;;){
  4674   4670           i64 nCellKey;
  4675   4671           pCell = findCell(pPage, idx) + pPage->childPtrSize;
  4676   4672           if( pPage->hasData ){
  4677   4673             u32 dummy;
  4678   4674             pCell += getVarint32(pCell, dummy);
  4679   4675           }
  4680   4676           getVarint(pCell, (u64*)&nCellKey);
  4681   4677           if( nCellKey==intKey ){
  4682   4678             pCur->validNKey = 1;
  4683   4679             pCur->info.nKey = nCellKey;
         4680  +          pCur->aiIdx[pCur->iPage] = (u16)idx;
  4684   4681             if( !pPage->leaf ){
  4685   4682               lwr = idx;
  4686   4683               break;
  4687   4684             }else{
  4688   4685               *pRes = 0;
  4689   4686               rc = SQLITE_OK;
  4690   4687               goto moveto_finish;
  4691   4688             }
  4692   4689           }else if( nCellKey<intKey ){
  4693         -          c = -1;
  4694   4690             lwr = idx+1;
  4695   4691           }else{
  4696   4692             assert( nCellKey>intKey );
  4697         -          c = +1;
  4698   4693             upr = idx-1;
  4699   4694           }
  4700         -        if( lwr>upr ) break;
  4701         -        pCur->aiIdx[pCur->iPage] = (u16)(idx = (lwr+upr)/2);
         4695  +        if( lwr>upr ){
         4696  +          c = nCellKey<intKey ? -1 : +1;
         4697  +          pCur->aiIdx[pCur->iPage] = (u16)idx;
         4698  +          break;
         4699  +        }
         4700  +        idx = (lwr+upr)/2;
  4702   4701         }
  4703   4702       }else{
  4704   4703         for(;;){
  4705   4704           int nCell;
  4706         -        assert( idx==pCur->aiIdx[pCur->iPage] );
  4707   4705           pCell = findCell(pPage, idx) + pPage->childPtrSize;
  4708   4706   
  4709   4707           /* The maximum supported page-size is 65536 bytes. This means that
  4710   4708           ** the maximum number of record bytes stored on an index B-Tree
  4711   4709           ** page is less than 16384 bytes and may be stored as a 2-byte
  4712   4710           ** varint. This information is used to attempt to avoid parsing 
  4713   4711           ** the entire cell by checking for the cases where the record is 
................................................................................
  4741   4739             btreeParseCellPtr(pPage, pCellBody, &pCur->info);
  4742   4740             nCell = (int)pCur->info.nKey;
  4743   4741             pCellKey = sqlite3Malloc( nCell );
  4744   4742             if( pCellKey==0 ){
  4745   4743               rc = SQLITE_NOMEM;
  4746   4744               goto moveto_finish;
  4747   4745             }
         4746  +          pCur->aiIdx[pCur->iPage] = (u16)idx;
  4748   4747             rc = accessPayload(pCur, 0, nCell, (unsigned char*)pCellKey, 0);
  4749   4748             if( rc ){
  4750   4749               sqlite3_free(pCellKey);
  4751   4750               goto moveto_finish;
  4752   4751             }
  4753   4752             c = sqlite3VdbeRecordCompare(nCell, pCellKey, pIdxKey);
  4754   4753             sqlite3_free(pCellKey);
  4755   4754           }
  4756   4755           if( c==0 ){
  4757   4756             *pRes = 0;
  4758   4757             rc = SQLITE_OK;
         4758  +          pCur->aiIdx[pCur->iPage] = (u16)idx;
  4759   4759             goto moveto_finish;
  4760   4760           }
  4761   4761           if( c<0 ){
  4762   4762             lwr = idx+1;
  4763   4763           }else{
  4764   4764             upr = idx-1;
  4765   4765           }
  4766         -        if( lwr>upr ) break;
  4767         -        pCur->aiIdx[pCur->iPage] = (u16)(idx = (lwr+upr)/2);
         4766  +        if( lwr>upr ){
         4767  +          pCur->aiIdx[pCur->iPage] = (u16)idx;
         4768  +          break;
         4769  +        }
         4770  +        idx = (lwr+upr)/2;
  4768   4771         }
  4769   4772       }
  4770   4773       assert( lwr==upr+1 || (pPage->intKey && !pPage->leaf) );
  4771   4774       assert( pPage->isInit );
  4772   4775       if( pPage->leaf ){
  4773   4776         assert( pCur->aiIdx[pCur->iPage]<pCur->apPage[pCur->iPage]->nCell );
  4774   4777         *pRes = c;