SQLite

Check-in [fda89b0512]
Login

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

Overview
Comment:Faster loading of cell pointers into the b.apCell array in balance_nonroot.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | btree-opt2
Files: files | file ages | folders
SHA1: fda89b0512477f9da09fd0f4e548ed4b13efd49d
User & Date: drh 2015-06-23 17:09:53.066
Context
2015-06-23
18:24
Multiple overflow cells are always adjacent and sequential. Exploit this invariant for a small size reduction and performance increase and add assert()s to prove the invariant. (check-in: f77f2f48f4 user: drh tags: btree-opt2)
17:09
Faster loading of cell pointers into the b.apCell array in balance_nonroot. (check-in: fda89b0512 user: drh tags: btree-opt2)
16:00
Avoid unnecessary cachedCellSize() calls in the cell partition adjustment phase of balance_nonroot(). (check-in: 6319ee1256 user: drh tags: btree-opt2)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/btree.c.
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
** the page, 1 means the second cell, and so forth) return a pointer
** to the cell content.
**
** This routine works only for pages that do not contain overflow cells.
*/
#define findCell(P,I) \
  ((P)->aData + ((P)->maskPage & get2byte(&(P)->aCellIdx[2*(I)])))
#define findCellv2(D,M,O,I) (D+(M&get2byte(D+(O+2*(I)))))

/*
** Sort the overflow cells of a page into index order.
**
** An O(N*N) algorithm is used.  But that should not be a problem
** since N is only very rarely more than 1.
*/







<







952
953
954
955
956
957
958

959
960
961
962
963
964
965
** the page, 1 means the second cell, and so forth) return a pointer
** to the cell content.
**
** This routine works only for pages that do not contain overflow cells.
*/
#define findCell(P,I) \
  ((P)->aData + ((P)->maskPage & get2byte(&(P)->aCellIdx[2*(I)])))


/*
** Sort the overflow cells of a page into index order.
**
** An O(N*N) algorithm is used.  But that should not be a problem
** since N is only very rarely more than 1.
*/
7050
7051
7052
7053
7054
7055
7056
7057
7058
7059
7060
7061
7062
7063
7064
7065
7066
7067
7068
7069
7070
7071
7072
7073
7074
7075
7076
7077
7078
7079
7080
7081
7082
7083

7084
7085
7086
7087
7088
7089
7090
7091

7092
7093
7094

7095
7096
7097
7098
7099
7100
7101
7102
7103
  leafCorrection = b.pRef->leaf*4;
  leafData = b.pRef->intKeyLeaf;
  for(i=0; i<nOld; i++){
    MemPage *pOld = apOld[i];
    int limit = pOld->nCell;
    u8 *aData = pOld->aData;
    u16 maskPage = pOld->maskPage;
    u16 cellOffset = pOld->cellOffset;

    /* Verify that all sibling pages are of the same "type" (table-leaf,
    ** table-interior, index-leaf, or index-interior).
    */
    if( pOld->aData[0]!=apOld[0]->aData[0] ){
      rc = SQLITE_CORRUPT_BKPT;
      goto balance_cleanup;
    }

    /* Load b.apCell[] with pointers to all cells in pOld.  Intersperse
    ** overflow cells in the correct sequence.  
    **
    ** This must be done in advance.  Once the balance starts, the cell
    ** offset section of the btree page will be overwritten and we will no
    ** long be able to find the cells if a pointer to each cell is not saved
    ** first.
    */
    memset(&b.szCell[b.nCell], 0, sizeof(b.szCell[0])*limit);
    j = 0;
    if( pOld->nOverflow>0 ){
      memset(&b.szCell[b.nCell+limit], 0, sizeof(b.szCell[0])*pOld->nOverflow);
      btreeSortOverflow(pOld);
      for(k=0; k<pOld->nOverflow; k++){
        limit = pOld->aiOvfl[k] - k;
        while( j<limit ){
          b.apCell[b.nCell] = findCellv2(aData, maskPage, cellOffset, j);

          b.nCell++;
          j++;
        }
        b.apCell[b.nCell] = pOld->apOvfl[k];
        b.nCell++;
      }
      limit = pOld->nCell;
    }

    while( j<limit ){
      assert( b.nCell<nMaxCells );
      b.apCell[b.nCell] = findCellv2(aData, maskPage, cellOffset, j);

      b.nCell++;
      j++;
    }

    cntOld[i] = b.nCell;
    if( i<nOld-1 && !leafData){
      u16 sz = (u16)szNew[i];
      u8 *pTemp;
      assert( b.nCell<nMaxCells );







|


















<



|


|
>






|

>
|

|
>

<







7049
7050
7051
7052
7053
7054
7055
7056
7057
7058
7059
7060
7061
7062
7063
7064
7065
7066
7067
7068
7069
7070
7071
7072
7073
7074

7075
7076
7077
7078
7079
7080
7081
7082
7083
7084
7085
7086
7087
7088
7089
7090
7091
7092
7093
7094
7095
7096

7097
7098
7099
7100
7101
7102
7103
  leafCorrection = b.pRef->leaf*4;
  leafData = b.pRef->intKeyLeaf;
  for(i=0; i<nOld; i++){
    MemPage *pOld = apOld[i];
    int limit = pOld->nCell;
    u8 *aData = pOld->aData;
    u16 maskPage = pOld->maskPage;
    u8 *piCell = aData + pOld->cellOffset;

    /* Verify that all sibling pages are of the same "type" (table-leaf,
    ** table-interior, index-leaf, or index-interior).
    */
    if( pOld->aData[0]!=apOld[0]->aData[0] ){
      rc = SQLITE_CORRUPT_BKPT;
      goto balance_cleanup;
    }

    /* Load b.apCell[] with pointers to all cells in pOld.  Intersperse
    ** overflow cells in the correct sequence.  
    **
    ** This must be done in advance.  Once the balance starts, the cell
    ** offset section of the btree page will be overwritten and we will no
    ** long be able to find the cells if a pointer to each cell is not saved
    ** first.
    */
    memset(&b.szCell[b.nCell], 0, sizeof(b.szCell[0])*limit);

    if( pOld->nOverflow>0 ){
      memset(&b.szCell[b.nCell+limit], 0, sizeof(b.szCell[0])*pOld->nOverflow);
      btreeSortOverflow(pOld);
      for(j=k=0; k<pOld->nOverflow; k++){
        limit = pOld->aiOvfl[k] - k;
        while( j<limit ){
          b.apCell[b.nCell] = aData + (maskPage & get2byte(piCell));
          piCell += 2;
          b.nCell++;
          j++;
        }
        b.apCell[b.nCell] = pOld->apOvfl[k];
        b.nCell++;
      }
      limit = pOld->nCell - j;
    }
    limit += b.nCell;
    while( b.nCell<limit ){
      assert( b.nCell<nMaxCells );
      b.apCell[b.nCell] = aData + (maskPage & get2byte(piCell));
      piCell += 2;
      b.nCell++;

    }

    cntOld[i] = b.nCell;
    if( i<nOld-1 && !leafData){
      u16 sz = (u16)szNew[i];
      u8 *pTemp;
      assert( b.nCell<nMaxCells );