SQLite

Check-in [f77f2f48f4]
Login

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

Overview
Comment: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.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | btree-opt2
Files: files | file ages | folders
SHA1: f77f2f48f48e374a72b6c054142f7a3ec0b1483c
User & Date: drh 2015-06-23 18:24:25.456
Context
2015-06-23
21:35
Testability improvement. (Closed-Leaf check-in: eed6a33145 user: drh tags: btree-opt2)
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)
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
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
** 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.
*/
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.
*/







<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<







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)])))




















/*
** 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.
*/
6239
6240
6241
6242
6243
6244
6245








6246
6247
6248
6249
6250
6251
6252
    if( iChild ){
      put4byte(pCell, iChild);
    }
    j = pPage->nOverflow++;
    assert( j<(int)(sizeof(pPage->apOvfl)/sizeof(pPage->apOvfl[0])) );
    pPage->apOvfl[j] = pCell;
    pPage->aiOvfl[j] = (u16)i;








  }else{
    int rc = sqlite3PagerWrite(pPage->pDbPage);
    if( rc!=SQLITE_OK ){
      *pRC = rc;
      return;
    }
    assert( sqlite3PagerIswriteable(pPage->pDbPage) );







>
>
>
>
>
>
>
>







6220
6221
6222
6223
6224
6225
6226
6227
6228
6229
6230
6231
6232
6233
6234
6235
6236
6237
6238
6239
6240
6241
    if( iChild ){
      put4byte(pCell, iChild);
    }
    j = pPage->nOverflow++;
    assert( j<(int)(sizeof(pPage->apOvfl)/sizeof(pPage->apOvfl[0])) );
    pPage->apOvfl[j] = pCell;
    pPage->aiOvfl[j] = (u16)i;

    /* When multiple overflows occur, they are always sequential and in
    ** sorted order.  This invariants arise because multiple overflows can
    ** only occur when inserting divider cells into the parent page during
    ** balancing, and the dividers are adjacent and sorted.
    */
    assert( j==0 || pPage->aiOvfl[j-1]<(u16)i ); /* Overflows in sorted order */
    assert( j==0 || i==pPage->aiOvfl[j-1]+1 );   /* Overflows are sequential */
  }else{
    int rc = sqlite3PagerWrite(pPage->pDbPage);
    if( rc!=SQLITE_OK ){
      *pRC = rc;
      return;
    }
    assert( sqlite3PagerIswriteable(pPage->pDbPage) );
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
  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;







>









|
>
|
>
>
>
>
>
>
>
>









<
<
|
|
|
|
|
<
|
>
>



|

|
|







7039
7040
7041
7042
7043
7044
7045
7046
7047
7048
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
  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;
    u8 *piEnd;

    /* 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.  If pOld
    ** constains overflow cells, include them in the b.apCell[] array
    ** in the correct spot.
    **
    ** Note that when there are multiple overflow cells, it is always the
    ** case that they are sequential and adjacent.  This invariant arises
    ** because multiple overflows can only occurs when inserting divider
    ** cells into a parent on a prior balance, and divider cells are always
    ** adjacent and are inserted in order.  There is an assert() tagged
    ** with "NOTE 1" in the overflow cell insertion loop to prove this
    ** invariant.
    **
    ** 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);


      limit = pOld->aiOvfl[0];
      for(j=0; j<limit; j++){
        b.apCell[b.nCell] = aData + (maskPage & get2byte(piCell));
        piCell += 2;
        b.nCell++;

      }
      for(k=0; k<pOld->nOverflow; k++){
        assert( k==0 || pOld->aiOvfl[k-1]+1==pOld->aiOvfl[k] );/* NOTE 1 */
        b.apCell[b.nCell] = pOld->apOvfl[k];
        b.nCell++;
      }
      limit = pOld->nCell - pOld->aiOvfl[0];
    }
    piEnd = aData + pOld->cellOffset + 2*pOld->nCell;
    while( piCell<piEnd ){
      assert( b.nCell<nMaxCells );
      b.apCell[b.nCell] = aData + (maskPage & get2byte(piCell));
      piCell += 2;
      b.nCell++;
    }

    cntOld[i] = b.nCell;