/ Check-in [fda89b05]
Login
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

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 | SQL archive
Timelines: family | ancestors | descendants | both | btree-opt2
Files: files | file ages | folders
SHA1: fda89b0512477f9da09fd0f4e548ed4b13efd49d
User & Date: drh 2015-06-23 17:09:53
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: f77f2f48 user: drh tags: btree-opt2
17:09
Faster loading of cell pointers into the b.apCell array in balance_nonroot. check-in: fda89b05 user: drh tags: btree-opt2
16:00
Avoid unnecessary cachedCellSize() calls in the cell partition adjustment phase of balance_nonroot(). check-in: 6319ee12 user: drh tags: btree-opt2
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/btree.c.

952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
....
7050
7051
7052
7053
7054
7055
7056
7057
7058
7059
7060
7061
7062
7063
7064
....
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
** 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.
*/
................................................................................
  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;
................................................................................
    **
    ** 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 );







<







 







|







 







<



|


|
>






|

>
|

<
>
>

<







952
953
954
955
956
957
958

959
960
961
962
963
964
965
....
7049
7050
7051
7052
7053
7054
7055
7056
7057
7058
7059
7060
7061
7062
7063
....
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
** 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.
*/
................................................................................
  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;
................................................................................
    **
    ** 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 );