/ 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 Unified Diffs Ignore Whitespace Patch

Changes to src/btree.c.

4658
4659
4660
4661
4662
4663
4664
4665
4666
4667
4668
4669
4670
4671
4672
4673
4674
4675
4676
4677
4678
4679
4680
4681
4682
4683

4684
4685
4686
4687
4688
4689
4690
4691
4692
4693
4694
4695
4696
4697
4698
4699
4700

4701



4702
4703
4704
4705
4706
4707
4708
4709
4710
4711
4712
4713
....
4741
4742
4743
4744
4745
4746
4747

4748
4749
4750
4751
4752
4753
4754
4755
4756
4757
4758

4759
4760
4761
4762
4763
4764
4765
4766
4767



4768
4769
4770
4771
4772
4773
4774
    ** would have already detected db corruption. Similarly, pPage must
    ** be the right kind (index or table) of b-tree page. Otherwise
    ** a moveToChild() or moveToRoot() call would have detected corruption.  */
    assert( pPage->nCell>0 );
    assert( pPage->intKey==(pIdxKey==0) );
    lwr = 0;
    upr = pPage->nCell-1;
    if( biasRight ){
      pCur->aiIdx[pCur->iPage] = (u16)(idx = upr);
    }else{
      pCur->aiIdx[pCur->iPage] = (u16)(idx = (upr+lwr)/2);
    }
    pCur->info.nSize = 0;
    if( pPage->intKey ){
      assert( idx==pCur->aiIdx[pCur->iPage] );
      for(;;){
        i64 nCellKey;
        pCell = findCell(pPage, idx) + pPage->childPtrSize;
        if( pPage->hasData ){
          u32 dummy;
          pCell += getVarint32(pCell, dummy);
        }
        getVarint(pCell, (u64*)&nCellKey);
        if( nCellKey==intKey ){
          pCur->validNKey = 1;
          pCur->info.nKey = nCellKey;

          if( !pPage->leaf ){
            lwr = idx;
            break;
          }else{
            *pRes = 0;
            rc = SQLITE_OK;
            goto moveto_finish;
          }
        }else if( nCellKey<intKey ){
          c = -1;
          lwr = idx+1;
        }else{
          assert( nCellKey>intKey );
          c = +1;
          upr = idx-1;
        }
        if( lwr>upr ) break;

        pCur->aiIdx[pCur->iPage] = (u16)(idx = (lwr+upr)/2);



      }
    }else{
      for(;;){
        int nCell;
        assert( idx==pCur->aiIdx[pCur->iPage] );
        pCell = findCell(pPage, idx) + pPage->childPtrSize;

        /* The maximum supported page-size is 65536 bytes. This means that
        ** the maximum number of record bytes stored on an index B-Tree
        ** page is less than 16384 bytes and may be stored as a 2-byte
        ** varint. This information is used to attempt to avoid parsing 
        ** the entire cell by checking for the cases where the record is 
................................................................................
          btreeParseCellPtr(pPage, pCellBody, &pCur->info);
          nCell = (int)pCur->info.nKey;
          pCellKey = sqlite3Malloc( nCell );
          if( pCellKey==0 ){
            rc = SQLITE_NOMEM;
            goto moveto_finish;
          }

          rc = accessPayload(pCur, 0, nCell, (unsigned char*)pCellKey, 0);
          if( rc ){
            sqlite3_free(pCellKey);
            goto moveto_finish;
          }
          c = sqlite3VdbeRecordCompare(nCell, pCellKey, pIdxKey);
          sqlite3_free(pCellKey);
        }
        if( c==0 ){
          *pRes = 0;
          rc = SQLITE_OK;

          goto moveto_finish;
        }
        if( c<0 ){
          lwr = idx+1;
        }else{
          upr = idx-1;
        }
        if( lwr>upr ) break;
        pCur->aiIdx[pCur->iPage] = (u16)(idx = (lwr+upr)/2);



      }
    }
    assert( lwr==upr+1 || (pPage->intKey && !pPage->leaf) );
    assert( pPage->isInit );
    if( pPage->leaf ){
      assert( pCur->aiIdx[pCur->iPage]<pCur->apPage[pCur->iPage]->nCell );
      *pRes = c;







|
|
<
<
<


<











>









<



<


|
>
|
>
>
>




<







 







>











>







|
|
>
>
>







4658
4659
4660
4661
4662
4663
4664
4665
4666



4667
4668

4669
4670
4671
4672
4673
4674
4675
4676
4677
4678
4679
4680
4681
4682
4683
4684
4685
4686
4687
4688
4689

4690
4691
4692

4693
4694
4695
4696
4697
4698
4699
4700
4701
4702
4703
4704

4705
4706
4707
4708
4709
4710
4711
....
4739
4740
4741
4742
4743
4744
4745
4746
4747
4748
4749
4750
4751
4752
4753
4754
4755
4756
4757
4758
4759
4760
4761
4762
4763
4764
4765
4766
4767
4768
4769
4770
4771
4772
4773
4774
4775
4776
4777
    ** would have already detected db corruption. Similarly, pPage must
    ** be the right kind (index or table) of b-tree page. Otherwise
    ** a moveToChild() or moveToRoot() call would have detected corruption.  */
    assert( pPage->nCell>0 );
    assert( pPage->intKey==(pIdxKey==0) );
    lwr = 0;
    upr = pPage->nCell-1;
    idx = biasRight ? upr : (upr+lwr)/2;
    pCur->aiIdx[pCur->iPage] = (u16)idx;



    pCur->info.nSize = 0;
    if( pPage->intKey ){

      for(;;){
        i64 nCellKey;
        pCell = findCell(pPage, idx) + pPage->childPtrSize;
        if( pPage->hasData ){
          u32 dummy;
          pCell += getVarint32(pCell, dummy);
        }
        getVarint(pCell, (u64*)&nCellKey);
        if( nCellKey==intKey ){
          pCur->validNKey = 1;
          pCur->info.nKey = nCellKey;
          pCur->aiIdx[pCur->iPage] = (u16)idx;
          if( !pPage->leaf ){
            lwr = idx;
            break;
          }else{
            *pRes = 0;
            rc = SQLITE_OK;
            goto moveto_finish;
          }
        }else if( nCellKey<intKey ){

          lwr = idx+1;
        }else{
          assert( nCellKey>intKey );

          upr = idx-1;
        }
        if( lwr>upr ){
          c = nCellKey<intKey ? -1 : +1;
          pCur->aiIdx[pCur->iPage] = (u16)idx;
          break;
        }
        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
        ** the maximum number of record bytes stored on an index B-Tree
        ** page is less than 16384 bytes and may be stored as a 2-byte
        ** varint. This information is used to attempt to avoid parsing 
        ** the entire cell by checking for the cases where the record is 
................................................................................
          btreeParseCellPtr(pPage, pCellBody, &pCur->info);
          nCell = (int)pCur->info.nKey;
          pCellKey = sqlite3Malloc( nCell );
          if( pCellKey==0 ){
            rc = SQLITE_NOMEM;
            goto moveto_finish;
          }
          pCur->aiIdx[pCur->iPage] = (u16)idx;
          rc = accessPayload(pCur, 0, nCell, (unsigned char*)pCellKey, 0);
          if( rc ){
            sqlite3_free(pCellKey);
            goto moveto_finish;
          }
          c = sqlite3VdbeRecordCompare(nCell, pCellKey, pIdxKey);
          sqlite3_free(pCellKey);
        }
        if( c==0 ){
          *pRes = 0;
          rc = SQLITE_OK;
          pCur->aiIdx[pCur->iPage] = (u16)idx;
          goto moveto_finish;
        }
        if( c<0 ){
          lwr = idx+1;
        }else{
          upr = idx-1;
        }
        if( lwr>upr ){
          pCur->aiIdx[pCur->iPage] = (u16)idx;
          break;
        }
        idx = (lwr+upr)/2;
      }
    }
    assert( lwr==upr+1 || (pPage->intKey && !pPage->leaf) );
    assert( pPage->isInit );
    if( pPage->leaf ){
      assert( pCur->aiIdx[pCur->iPage]<pCur->apPage[pCur->iPage]->nCell );
      *pRes = c;