/ Check-in [ee44bb25]
Login

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

Overview
Comment:Improvements to the way balance_nonroot() constructs the b.apCell array of pointers to cells.
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | btree-opt2
Files: files | file ages | folders
SHA1:ee44bb25b2a88e25ba2afe37cf03ba199692a3a0
User & Date: drh 2015-06-23 14:49:42
Context
2015-06-23
15:36
Change pageInsertArray() and pageFreeArray() so that they use the CellArray object and compute cell sizes as needed, resulting in smaller and faster code. check-in: f7f41818 user: drh tags: btree-opt2
14:49
Improvements to the way balance_nonroot() constructs the b.apCell array of pointers to cells. check-in: ee44bb25 user: drh tags: btree-opt2
13:02
Merge the compound SELECT operator fix from trunk. check-in: a7be554f user: drh tags: btree-opt2
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/btree.c.

954
955
956
957
958
959
960
961
962

963
964

965
966

967
968
969
970
971
972
973
974
975
976
977
978
979
980

981
982
983
984
985
986
987
....
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
**
** 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)))))


/*

** This a more complex version of findCell() that works for
** pages that do contain overflow cells.

*/
static u8 *findOverflowCell(MemPage *pPage, int iCell){

  int i;
  assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  for(i=pPage->nOverflow-1; i>=0; i--){
    int k;
    k = pPage->aiOvfl[i];
    if( k<=iCell ){
      if( k==iCell ){
        return pPage->apOvfl[i];
      }
      iCell--;
    }
  }
  return findCell(pPage, iCell);
}


/*
** This is common tail processing for btreeParseCellPtr() and
** btreeParseCellPtrIndex() for the case when the cell does not fit entirely
** on a single B-tree page.  Make necessary adjustments to the CellInfo
** structure.
*/
................................................................................
  ** leafCorrection:  4 if pPage is a leaf.  0 if pPage is not a leaf.
  **       leafData:  1 if pPage holds key+data and pParent holds only keys.
  */
  b.pRef = apOld[0];
  leafCorrection = b.pRef->leaf*4;
  leafData = b.pRef->intKeyLeaf;
  for(i=0; i<nOld; i++){
    int limit;
    MemPage *pOld = apOld[i];





    /* 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;
    }

    limit = pOld->nCell+pOld->nOverflow;







    memset(&b.szCell[b.nCell], 0, sizeof(b.szCell[0])*limit);

    if( pOld->nOverflow>0 ){




      for(j=0; j<limit; j++){

        assert( b.nCell<nMaxCells );


        b.apCell[b.nCell] = findOverflowCell(pOld, j);
        b.nCell++;
      }
    }else{
      u8 *aData = pOld->aData;
      u16 maskPage = pOld->maskPage;
      u16 cellOffset = pOld->cellOffset;

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

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







<

>
|
|
>

<
>
|
<
|
|
|
|
|
<

<


<

>







 







<

>
>
>
>









|
>
>
>
>
>
>
>

>

>
>
>
>
|
>
|
>
>
|


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







954
955
956
957
958
959
960

961
962
963
964
965
966

967
968

969
970
971
972
973

974

975
976

977
978
979
980
981
982
983
984
985
....
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
7104
7105
7106
7107
7108
7109
7110
**
** 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.
*/

static void btreeSortOverflow(MemPage *p){
  int j, k;

  for(j=0; j<p->nOverflow-1; j++){
    for(k=j+1; k<p->nOverflow; k++){
      if( p->aiOvfl[j]>p->aiOvfl[k] ){
        SWAP(u16, p->aiOvfl[j], p->aiOvfl[k]);
        SWAP(u8*, p->apOvfl[j], p->apOvfl[k]);

      }

    }
  }

}


/*
** This is common tail processing for btreeParseCellPtr() and
** btreeParseCellPtrIndex() for the case when the cell does not fit entirely
** on a single B-tree page.  Make necessary adjustments to the CellInfo
** structure.
*/
................................................................................
  ** leafCorrection:  4 if pPage is a leaf.  0 if pPage is not a leaf.
  **       leafData:  1 if pPage holds key+data and pParent holds only keys.
  */
  b.pRef = apOld[0];
  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 );
      b.szCell[b.nCell] = sz;
      pTemp = &aSpace1[iSpace1];