SQLite

Changes On Branch btree-optimization
Login

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

Changes In Branch btree-optimization Excluding Merge-Ins

This is equivalent to a diff from 8f3c767a to b48c4e40

2013-11-25
20:50
Optimizations to the sqlite3BtreeMovetoUnpacked() routine in storage engine making it about 17.8% faster, which in turn makes SQLite over 1.2% faster overall. (check-in: 032e8993 user: drh tags: trunk)
20:14
Return an SQLITE_CORRUPT error if the content size field of a table record extends off the end of a page. (Closed-Leaf check-in: b48c4e40 user: drh tags: btree-optimization)
17:38
Uses shifts rather than division for arithmetic on the cell indices, since those indices are always non-negative. (check-in: 5bf2a3fe user: drh tags: btree-optimization)
09:36
Initial work on isolating usage of the Windows header file. (check-in: 0d42c6b8 user: mistachkin tags: winHdr)
02:38
Performance improvements in sqlite3BtreeMovetoUnpacked(). (check-in: d0fb7ace user: drh tags: btree-optimization)
2013-11-24
23:18
Better support for UTF-8 paths on Cygwin. (Closed-Leaf check-in: 484162b6 user: mistachkin tags: cygUtf8)
01:14
Add the --scratch parameter to speedtest1. Improved error messages when misconfiguring memory parameters in speedtest1. (check-in: 8f3c767a user: drh tags: trunk)
00:46
The MEMSYS5 algorithm does not have to return the block with the lowest address. Any block of the appropriate size will do. Use the first block found on the freelist for the appropriate size for a performance improvement. (check-in: 12e612e8 user: drh tags: trunk)

Changes to src/btree.c.

4643
4644
4645
4646
4647
4648
4649
4650
4651
4652
4653
4654
4655
4656
4657
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
  if( pCur->eState==CURSOR_INVALID ){
    *pRes = -1;
    assert( pCur->pgnoRoot==0 || pCur->apPage[pCur->iPage]->nCell==0 );
    return SQLITE_OK;
  }
  assert( pCur->apPage[0]->intKey || pIdxKey );
  for(;;){
    int lwr, upr, idx;
    Pgno chldPg;
    MemPage *pPage = pCur->apPage[pCur->iPage];
    int c;

    /* pPage->nCell must be greater than zero. If this is the root-page
    ** the cursor would have been INVALID above and this for(;;) loop
    ** not run. If this is not the root-page, then the moveToChild() routine
    ** 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);
    }

    for(;;){
      u8 *pCell;                          /* Pointer to current cell in pPage */

      assert( idx==pCur->aiIdx[pCur->iPage] );
      pCur->info.nSize = 0;
      pCell = findCell(pPage, idx) + pPage->childPtrSize;
      if( pPage->intKey ){
        i64 nCellKey;
        if( pPage->hasData ){
          u32 dummy;
          pCell += getVarint32(pCell, dummy);

        }

        getVarint(pCell, (u64*)&nCellKey);
        if( nCellKey==intKey ){
          c = 0;

        }else if( nCellKey<intKey ){
          c = -1;

        }else{
          assert( nCellKey>intKey );
          c = +1;
        }
        pCur->validNKey = 1;
        pCur->info.nKey = nCellKey;




      }else{













        /* 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 
        ** stored entirely within the b-tree page by inspecting the first 
        ** 2 bytes of the cell.
        */
        int nCell = pCell[0];
        if( nCell<=pPage->max1bytePayload
         /* && (pCell+nCell)<pPage->aDataEnd */
        ){
          /* This branch runs if the record-size field of the cell is a
          ** single byte varint and the record fits entirely on the main
          ** b-tree page.  */
          testcase( pCell+nCell+1==pPage->aDataEnd );







|


|











|
|
<
|
<
>
|
<
|
<
<
|
<
<

<
|
>
|
>

|
|
>
|
|
>

|
<
<
|
|
>
>
>
>
|
>
>
>
>
>
>
>
>
>
>
>
>
>








|







4643
4644
4645
4646
4647
4648
4649
4650
4651
4652
4653
4654
4655
4656
4657
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
4714
4715
4716
4717
4718
4719
4720
4721
  if( pCur->eState==CURSOR_INVALID ){
    *pRes = -1;
    assert( pCur->pgnoRoot==0 || pCur->apPage[pCur->iPage]->nCell==0 );
    return SQLITE_OK;
  }
  assert( pCur->apPage[0]->intKey || pIdxKey );
  for(;;){
    int lwr, upr, idx, c;
    Pgno chldPg;
    MemPage *pPage = pCur->apPage[pCur->iPage];
    u8 *pCell;                          /* Pointer to current cell in pPage */

    /* pPage->nCell must be greater than zero. If this is the root-page
    ** the cursor would have been INVALID above and this for(;;) loop
    ** not run. If this is not the root-page, then the moveToChild() routine
    ** 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;
    assert( biasRight==0 || biasRight==1 );
    idx = upr>>(1-biasRight); /* idx = biasRight ? upr : (lwr+upr)/2; */

    pCur->aiIdx[pCur->iPage] = (u16)idx;

    if( pPage->intKey ){
      for(;;){

        i64 nCellKey;


        pCell = findCell(pPage, idx) + pPage->childPtrSize;


        if( pPage->hasData ){

          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->validNKey = 1;
          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
        ** 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 
        ** stored entirely within the b-tree page by inspecting the first 
        ** 2 bytes of the cell.
        */
        nCell = pCell[0];
        if( nCell<=pPage->max1bytePayload
         /* && (pCell+nCell)<pPage->aDataEnd */
        ){
          /* This branch runs if the record-size field of the cell is a
          ** single byte varint and the record fits entirely on the main
          ** b-tree page.  */
          testcase( pCell+nCell+1==pPage->aDataEnd );
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
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
4778
4779
4780
4781
4782
4783


4784
4785
4786
4787
4788
4789
4790
          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 ){
        if( pPage->intKey && !pPage->leaf ){
          lwr = idx;

          break;
        }else{

          *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 ){
      chldPg = 0;
    }else if( lwr>=pPage->nCell ){
      chldPg = get4byte(&pPage->aData[pPage->hdrOffset+8]);
    }else{
      chldPg = get4byte(findCell(pPage, lwr));
    }
    if( chldPg==0 ){
      assert( pCur->aiIdx[pCur->iPage]<pCur->apPage[pCur->iPage]->nCell );

      *pRes = c;
      rc = SQLITE_OK;
      goto moveto_finish;
    }






    pCur->aiIdx[pCur->iPage] = (u16)lwr;
    pCur->info.nSize = 0;
    pCur->validNKey = 0;
    rc = moveToChild(pCur, chldPg);
    if( rc ) goto moveto_finish;
  }
moveto_finish:


  return rc;
}


/*
** Return TRUE if the cursor is not pointing at an entry of the table.
**







>








<
|
<
|
>
|

>


>


<
<
<
<
<
<
|
<
>
>

<




<
<
<
<
<
<
<

>




>
>
>
>
>
>

<
<

|


>
>







4738
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
4778
4779
4780
4781
4782
4783
4784
4785


4786
4787
4788
4789
4790
4791
4792
4793
4794
4795
4796
4797
4798
          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 ){

          lwr = idx+1;
        }else if( c>0 ){
          upr = idx-1;
        }else{
          assert( c==0 );
          *pRes = 0;
          rc = SQLITE_OK;
          pCur->aiIdx[pCur->iPage] = (u16)idx;
          goto moveto_finish;
        }






        if( lwr>upr ) break;

        assert( lwr+upr>=0 );
        idx = (lwr+upr)>>1;  /* 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 );
      pCur->aiIdx[pCur->iPage] = (u16)idx;
      *pRes = c;
      rc = SQLITE_OK;
      goto moveto_finish;
    }
moveto_next_layer:
    if( lwr>=pPage->nCell ){
      chldPg = get4byte(&pPage->aData[pPage->hdrOffset+8]);
    }else{
      chldPg = get4byte(findCell(pPage, lwr));
    }
    pCur->aiIdx[pCur->iPage] = (u16)lwr;


    rc = moveToChild(pCur, chldPg);
    if( rc ) break;
  }
moveto_finish:
  pCur->info.nSize = 0;
  pCur->validNKey = 0;
  return rc;
}


/*
** Return TRUE if the cursor is not pointing at an entry of the table.
**

Changes to src/vdbe.c.

4071
4072
4073
4074
4075
4076
4077
4078
4079
4080
4081
4082
4083
4084
4085
    nZero = pData->u.nZero;
  }else{
    nZero = 0;
  }
  sqlite3BtreeSetCachedRowid(pC->pCursor, 0);
  rc = sqlite3BtreeInsert(pC->pCursor, 0, iKey,
                          pData->z, pData->n, nZero,
                          pOp->p5 & OPFLAG_APPEND, seekResult
  );
  pC->rowidIsValid = 0;
  pC->deferredMoveto = 0;
  pC->cacheStatus = CACHE_STALE;

  /* Invoke the update-hook if required. */
  if( rc==SQLITE_OK && db->xUpdateCallback && pOp->p4.z ){







|







4071
4072
4073
4074
4075
4076
4077
4078
4079
4080
4081
4082
4083
4084
4085
    nZero = pData->u.nZero;
  }else{
    nZero = 0;
  }
  sqlite3BtreeSetCachedRowid(pC->pCursor, 0);
  rc = sqlite3BtreeInsert(pC->pCursor, 0, iKey,
                          pData->z, pData->n, nZero,
                          (pOp->p5 & OPFLAG_APPEND)!=0, seekResult
  );
  pC->rowidIsValid = 0;
  pC->deferredMoveto = 0;
  pC->cacheStatus = CACHE_STALE;

  /* Invoke the update-hook if required. */
  if( rc==SQLITE_OK && db->xUpdateCallback && pOp->p4.z ){