SQLite

Check-in [39902a7041]
Login

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

Overview
Comment:Optimizations to the BTree module for a modest speed improvement. (CVS 810)
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 39902a70417475225956704a037493515e9b08b9
User & Date: drh 2003-01-04 16:48:09.000
Context
2003-01-04
18:53
Another optimization to the btree logic. (CVS 811) (check-in: 03d2067361 user: drh tags: trunk)
16:48
Optimizations to the BTree module for a modest speed improvement. (CVS 810) (check-in: 39902a7041 user: drh tags: trunk)
2003-01-03
02:04
Allow the rollback journal to be empty except for its header. Ticket #212. (CVS 809) (check-in: 1ba41bc2af user: drh tags: trunk)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/btree.c.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
** 2001 September 15
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** $Id: btree.c,v 1.76 2003/01/02 14:43:56 drh Exp $
**
** This file implements a external (disk-based) database using BTrees.
** For a detailed discussion of BTrees, refer to
**
**     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
**     "Sorting And Searching", pages 473-480. Addison-Wesley
**     Publishing Company, Reading, Massachusetts.











|







1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/*
** 2001 September 15
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** $Id: btree.c,v 1.77 2003/01/04 16:48:09 drh Exp $
**
** This file implements a external (disk-based) database using BTrees.
** For a detailed discussion of BTrees, refer to
**
**     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
**     "Sorting And Searching", pages 473-480. Addison-Wesley
**     Publishing Company, Reading, Massachusetts.
315
316
317
318
319
320
321
322


323

324
325
326
327
328
329
330
331
332
333
** The pageDestructor() routine handles that chore.
*/
struct MemPage {
  union {
    char aDisk[SQLITE_PAGE_SIZE];  /* Page data stored on disk */
    PageHdr hdr;                   /* Overlay page header */
  } u;
  int isInit;                    /* True if auxiliary data is initialized */


  MemPage *pParent;              /* The parent of this page.  NULL for root */

  int nFree;                     /* Number of free bytes in u.aDisk[] */
  int nCell;                     /* Number of entries on this page */
  int isOverfull;                /* Some apCell[] points outside u.aDisk[] */
  Cell *apCell[MX_CELL+2];       /* All data entires in sorted order */
};

/*
** The in-memory image of a disk page has the auxiliary information appended
** to the end.  EXTRA_SIZE is the number of bytes of space needed to hold
** that extra information.







|
>
>

>


<







315
316
317
318
319
320
321
322
323
324
325
326
327
328

329
330
331
332
333
334
335
** The pageDestructor() routine handles that chore.
*/
struct MemPage {
  union {
    char aDisk[SQLITE_PAGE_SIZE];  /* Page data stored on disk */
    PageHdr hdr;                   /* Overlay page header */
  } u;
  u8 isInit;                     /* True if auxiliary data is initialized */
  u8 idxShift;                   /* True if apCell[] indices have changed */
  u8 isOverfull;                 /* Some apCell[] points outside u.aDisk[] */
  MemPage *pParent;              /* The parent of this page.  NULL for root */
  int idxParent;                 /* Index in pParent->apCell[] of this node */
  int nFree;                     /* Number of free bytes in u.aDisk[] */
  int nCell;                     /* Number of entries on this page */

  Cell *apCell[MX_CELL+2];       /* All data entires in sorted order */
};

/*
** The in-memory image of a disk page has the auxiliary information appended
** to the end.  EXTRA_SIZE is the number of bytes of space needed to hold
** that extra information.
1343
1344
1345
1346
1347
1348
1349






1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369

1370
1371
1372
1373





















1374
1375
1376
1377
1378
1379

1380
1381
1382
1383
1384
1385
1386
  MemPage *pNewPage;
  Btree *pBt = pCur->pBt;

  rc = sqlitepager_get(pBt->pPager, newPgno, (void**)&pNewPage);
  if( rc ) return rc;
  rc = initPage(pBt, pNewPage, newPgno, pCur->pPage);
  if( rc ) return rc;






  sqlitepager_unref(pCur->pPage);
  pCur->pPage = pNewPage;
  pCur->idx = 0;
  return SQLITE_OK;
}

/*
** Move the cursor up to the parent page.
**
** pCur->idx is set to the cell index that contains the pointer
** to the page we are coming from.  If we are coming from the
** right-most child page then pCur->idx is set to one more than
** the largest cell index.
*/
static int moveToParent(BtCursor *pCur){
  Pgno oldPgno;
  MemPage *pParent;
  int i;
  pParent = pCur->pPage->pParent;
  if( pParent==0 ) return SQLITE_INTERNAL;

  oldPgno = sqlitepager_pagenumber(pCur->pPage);
  sqlitepager_ref(pParent);
  sqlitepager_unref(pCur->pPage);
  pCur->pPage = pParent;





















  pCur->idx = pParent->nCell;
  oldPgno = SWAB32(pCur->pBt, oldPgno);
  for(i=0; i<pParent->nCell; i++){
    if( pParent->apCell[i]->h.leftChild==oldPgno ){
      pCur->idx = i;
      break;

    }
  }
  return SQLITE_OK;
}

/*
** Move the cursor to the root page







>
>
>
>
>
>

















|


>




>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|
|
|
|
|
|
>







1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
  MemPage *pNewPage;
  Btree *pBt = pCur->pBt;

  rc = sqlitepager_get(pBt->pPager, newPgno, (void**)&pNewPage);
  if( rc ) return rc;
  rc = initPage(pBt, pNewPage, newPgno, pCur->pPage);
  if( rc ) return rc;
  assert( pCur->idx>=pCur->pPage->nCell
          || pCur->pPage->apCell[pCur->idx]->h.leftChild==SWAB32(pBt,newPgno) );
  assert( pCur->idx<pCur->pPage->nCell
          || pCur->pPage->u.hdr.rightChild==SWAB32(pBt,newPgno) );
  pNewPage->idxParent = pCur->idx;
  pCur->pPage->idxShift = 0;
  sqlitepager_unref(pCur->pPage);
  pCur->pPage = pNewPage;
  pCur->idx = 0;
  return SQLITE_OK;
}

/*
** Move the cursor up to the parent page.
**
** pCur->idx is set to the cell index that contains the pointer
** to the page we are coming from.  If we are coming from the
** right-most child page then pCur->idx is set to one more than
** the largest cell index.
*/
static int moveToParent(BtCursor *pCur){
  Pgno oldPgno;
  MemPage *pParent;
  int idxParent;
  pParent = pCur->pPage->pParent;
  if( pParent==0 ) return SQLITE_INTERNAL;
  idxParent = pCur->pPage->idxParent;
  oldPgno = sqlitepager_pagenumber(pCur->pPage);
  sqlitepager_ref(pParent);
  sqlitepager_unref(pCur->pPage);
  pCur->pPage = pParent;
  assert( pParent->idxShift==0 );
  if( pParent->idxShift==0 ){
    pCur->idx = idxParent;
#ifndef NDEBUG  
    /* Verify that pCur->idx is the correct index to point back to the child
    ** page we just came from 
    */
    oldPgno = SWAB32(pCur->pBt, oldPgno);
    if( pCur->idx<pParent->nCell ){
      assert( pParent->apCell[idxParent]->h.leftChild==oldPgno );
    }else{
      assert( pParent->u.hdr.rightChild==oldPgno );
    }
#endif
  }else{
    /* The MemPage.idxShift flag indicates that cell indices might have 
    ** changed since idxParent was set and hence idxParent might be out
    ** of date.  So recompute the parent cell index by scanning all cells
    ** and locating the one that points to the child we just came from.
    */
    int i;
    pCur->idx = pParent->nCell;
    oldPgno = SWAB32(pCur->pBt, oldPgno);
    for(i=0; i<pParent->nCell; i++){
      if( pParent->apCell[i]->h.leftChild==oldPgno ){
        pCur->idx = i;
        break;
      }
    }
  }
  return SQLITE_OK;
}

/*
** Move the cursor to the root page
1423
1424
1425
1426
1427
1428
1429

1430
1431
1432
1433
1434
1435
1436
** finds the right-most entry beneath the *page*.
*/
static int moveToRightmost(BtCursor *pCur){
  Pgno pgno;
  int rc;

  while( (pgno = pCur->pPage->u.hdr.rightChild)!=0 ){

    rc = moveToChild(pCur, SWAB32(pCur->pBt, pgno));
    if( rc ) return rc;
  }
  pCur->idx = pCur->pPage->nCell - 1;
  return SQLITE_OK;
}








>







1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
** finds the right-most entry beneath the *page*.
*/
static int moveToRightmost(BtCursor *pCur){
  Pgno pgno;
  int rc;

  while( (pgno = pCur->pPage->u.hdr.rightChild)!=0 ){
    pCur->idx = pCur->pPage->nCell;
    rc = moveToChild(pCur, SWAB32(pCur->pBt, pgno));
    if( rc ) return rc;
  }
  pCur->idx = pCur->pPage->nCell - 1;
  return SQLITE_OK;
}

1532
1533
1534
1535
1536
1537
1538

1539
1540
1541
1542
1543
1544
1545
      chldPg = pPage->apCell[lwr]->h.leftChild;
    }
    if( chldPg==0 ){
      pCur->iMatch = c;
      if( pRes ) *pRes = c;
      return SQLITE_OK;
    }

    rc = moveToChild(pCur, SWAB32(pCur->pBt, chldPg));
    if( rc ) return rc;
  }
  /* NOT REACHED */
}

/*







>







1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
      chldPg = pPage->apCell[lwr]->h.leftChild;
    }
    if( chldPg==0 ){
      pCur->iMatch = c;
      if( pRes ) *pRes = c;
      return SQLITE_OK;
    }
    pCur->idx = lwr;
    rc = moveToChild(pCur, SWAB32(pCur->pBt, chldPg));
    if( rc ) return rc;
  }
  /* NOT REACHED */
}

/*
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901

1902
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920

1921
1922
1923
1924
1925
1926
1927
}

/*
** Change the MemPage.pParent pointer on the page whose number is
** given in the second argument so that MemPage.pParent holds the
** pointer in the third argument.
*/
static void reparentPage(Pager *pPager, Pgno pgno, MemPage *pNewParent){
  MemPage *pThis;

  if( pgno==0 ) return;
  assert( pPager!=0 );
  pThis = sqlitepager_lookup(pPager, pgno);
  if( pThis && pThis->isInit ){
    if( pThis->pParent!=pNewParent ){
      if( pThis->pParent ) sqlitepager_unref(pThis->pParent);
      pThis->pParent = pNewParent;
      if( pNewParent ) sqlitepager_ref(pNewParent);
    }

    sqlitepager_unref(pThis);
  }
}

/*
** Reparent all children of the given page to be the given page.
** In other words, for every child of pPage, invoke reparentPage()
** to make sure that each child knows that pPage is its parent.
**
** This routine gets called after you memcpy() one page into
** another.
*/
static void reparentChildPages(Btree *pBt, MemPage *pPage){
  int i;
  Pager *pPager = pBt->pPager;
  for(i=0; i<pPage->nCell; i++){
    reparentPage(pPager, SWAB32(pBt, pPage->apCell[i]->h.leftChild), pPage);
  }
  reparentPage(pPager, SWAB32(pBt, pPage->u.hdr.rightChild), pPage);

}

/*
** Remove the i-th cell from pPage.  This routine effects pPage only.
** The cell content is not freed or deallocated.  It is assumed that
** the cell content has been copied someplace else.  This routine just
** removes the reference to the cell from pPage.







|











>
















|

|
>







1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
1936
1937
1938
1939
1940
1941
1942
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
}

/*
** Change the MemPage.pParent pointer on the page whose number is
** given in the second argument so that MemPage.pParent holds the
** pointer in the third argument.
*/
static void reparentPage(Pager *pPager, Pgno pgno, MemPage *pNewParent,int idx){
  MemPage *pThis;

  if( pgno==0 ) return;
  assert( pPager!=0 );
  pThis = sqlitepager_lookup(pPager, pgno);
  if( pThis && pThis->isInit ){
    if( pThis->pParent!=pNewParent ){
      if( pThis->pParent ) sqlitepager_unref(pThis->pParent);
      pThis->pParent = pNewParent;
      if( pNewParent ) sqlitepager_ref(pNewParent);
    }
    pThis->idxParent = idx;
    sqlitepager_unref(pThis);
  }
}

/*
** Reparent all children of the given page to be the given page.
** In other words, for every child of pPage, invoke reparentPage()
** to make sure that each child knows that pPage is its parent.
**
** This routine gets called after you memcpy() one page into
** another.
*/
static void reparentChildPages(Btree *pBt, MemPage *pPage){
  int i;
  Pager *pPager = pBt->pPager;
  for(i=0; i<pPage->nCell; i++){
    reparentPage(pPager, SWAB32(pBt, pPage->apCell[i]->h.leftChild), pPage, i);
  }
  reparentPage(pPager, SWAB32(pBt, pPage->u.hdr.rightChild), pPage, i);
  pPage->idxShift = 0;
}

/*
** Remove the i-th cell from pPage.  This routine effects pPage only.
** The cell content is not freed or deallocated.  It is assumed that
** the cell content has been copied someplace else.  This routine just
** removes the reference to the cell from pPage.
1939
1940
1941
1942
1943
1944
1945

1946
1947
1948
1949
1950
1951
1952
  assert( sz==cellSize(pBt, pPage->apCell[idx]) );
  assert( sqlitepager_iswriteable(pPage) );
  freeSpace(pBt, pPage, Addr(pPage->apCell[idx]) - Addr(pPage), sz);
  for(j=idx; j<pPage->nCell-1; j++){
    pPage->apCell[j] = pPage->apCell[j+1];
  }
  pPage->nCell--;

}

/*
** Insert a new cell on pPage at cell index "i".  pCell points to the
** content of the cell.
**
** If the cell content will fit on the page, then put it there.  If it







>







1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
  assert( sz==cellSize(pBt, pPage->apCell[idx]) );
  assert( sqlitepager_iswriteable(pPage) );
  freeSpace(pBt, pPage, Addr(pPage->apCell[idx]) - Addr(pPage), sz);
  for(j=idx; j<pPage->nCell-1; j++){
    pPage->apCell[j] = pPage->apCell[j+1];
  }
  pPage->nCell--;
  pPage->idxShift = 1;
}

/*
** Insert a new cell on pPage at cell index "i".  pCell points to the
** content of the cell.
**
** If the cell content will fit on the page, then put it there.  If it
1971
1972
1973
1974
1975
1976
1977

1978
1979
1980
1981
1982
1983
1984
  if( idx<=0 ){
    pPage->isOverfull = 1;
    pPage->apCell[i] = pCell;
  }else{
    memcpy(&pPage->u.aDisk[idx], pCell, sz);
    pPage->apCell[i] = (Cell*)&pPage->u.aDisk[idx];
  }

}

/*
** Rebuild the linked list of cells on a page so that the cells
** occur in the order specified by the pPage->apCell[] array.  
** Invoke this routine once to repair damage after one or more
** invocations of either insertCell() or dropCell().







>







2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
  if( idx<=0 ){
    pPage->isOverfull = 1;
    pPage->apCell[i] = pCell;
  }else{
    memcpy(&pPage->u.aDisk[idx], pCell, sz);
    pPage->apCell[i] = (Cell*)&pPage->u.aDisk[idx];
  }
  pPage->idxShift = 1;
}

/*
** Rebuild the linked list of cells on a page so that the cells
** occur in the order specified by the pPage->apCell[] array.  
** Invoke this routine once to repair damage after one or more
** invocations of either insertCell() or dropCell().
2157
2158
2159
2160
2161
2162
2163

2164
2165
2166
2167
2168
2169
2170
    rc = sqlitepager_write(pPage);
    if( rc ) return rc;
    rc = allocatePage(pBt, &pChild, &pgnoChild, sqlitepager_pagenumber(pPage));
    if( rc ) return rc;
    assert( sqlitepager_iswriteable(pChild) );
    copyPage(pChild, pPage);
    pChild->pParent = pPage;

    sqlitepager_ref(pPage);
    pChild->isOverfull = 1;
    if( pCur && pCur->pPage==pPage ){
      sqlitepager_unref(pPage);
      pCur->pPage = pChild;
    }else{
      extraUnref = pChild;







>







2194
2195
2196
2197
2198
2199
2200
2201
2202
2203
2204
2205
2206
2207
2208
    rc = sqlitepager_write(pPage);
    if( rc ) return rc;
    rc = allocatePage(pBt, &pChild, &pgnoChild, sqlitepager_pagenumber(pPage));
    if( rc ) return rc;
    assert( sqlitepager_iswriteable(pChild) );
    copyPage(pChild, pPage);
    pChild->pParent = pPage;
    pChild->idxParent = pChild->nCell;
    sqlitepager_ref(pPage);
    pChild->isOverfull = 1;
    if( pCur && pCur->pPage==pPage ){
      sqlitepager_unref(pPage);
      pCur->pPage = pChild;
    }else{
      extraUnref = pChild;
2191
2192
2193
2194
2195
2196
2197
2198
2199
2200
2201
2202
2203
2204
2205
2206
2207
      idx = i;
      break;
    }
  }
  if( idx<0 && pParent->u.hdr.rightChild==swabPgno ){
    idx = pParent->nCell;
  }
  if( idx<0 ){
    return SQLITE_CORRUPT;
  }

  /*
  ** Initialize variables so that it will be safe to jump
  ** directly to balance_cleanup at any moment.
  */
  nOld = nNew = 0;
  sqlitepager_ref(pParent);







|
|
<







2229
2230
2231
2232
2233
2234
2235
2236
2237

2238
2239
2240
2241
2242
2243
2244
      idx = i;
      break;
    }
  }
  if( idx<0 && pParent->u.hdr.rightChild==swabPgno ){
    idx = pParent->nCell;
  }
  assert( idx>=0 );
  /* assert( pParent->idxShift || idx==pPage->idxParent ); */


  /*
  ** Initialize variables so that it will be safe to jump
  ** directly to balance_cleanup at any moment.
  */
  nOld = nNew = 0;
  sqlitepager_ref(pParent);
2231
2232
2233
2234
2235
2236
2237

2238
2239
2240
2241
2242
2243
2244
    }else{
      break;
    }
    rc = sqlitepager_get(pBt->pPager, pgnoOld[i], (void**)&apOld[i]);
    if( rc ) goto balance_cleanup;
    rc = initPage(pBt, apOld[i], pgnoOld[i], pParent);
    if( rc ) goto balance_cleanup;

    nOld++;
  }

  /*
  ** Set iCur to be the index in apCell[] of the cell that the cursor
  ** is pointing to.  We will need this later on in order to keep the
  ** cursor pointing at the same cell.  If pCur points to a page that







>







2268
2269
2270
2271
2272
2273
2274
2275
2276
2277
2278
2279
2280
2281
2282
    }else{
      break;
    }
    rc = sqlitepager_get(pBt->pPager, pgnoOld[i], (void**)&apOld[i]);
    if( rc ) goto balance_cleanup;
    rc = initPage(pBt, apOld[i], pgnoOld[i], pParent);
    if( rc ) goto balance_cleanup;
    apOld[i]->idxParent = k;
    nOld++;
  }

  /*
  ** Set iCur to be the index in apCell[] of the cell that the cursor
  ** is pointing to.  We will need this later on in order to keep the
  ** cursor pointing at the same cell.  If pCur points to a page that
Changes to test/table.test.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 2001 September 15
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this file is testing the CREATE TABLE statement.
#
# $Id: table.test,v 1.20 2002/08/31 18:53:09 drh Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

# Create a basic table and verify it is added to sqlite_master
#
do_test table-1.1 {













|







1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# 2001 September 15
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this file is testing the CREATE TABLE statement.
#
# $Id: table.test,v 1.21 2003/01/04 16:48:10 drh Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

# Create a basic table and verify it is added to sqlite_master
#
do_test table-1.1 {
213
214
215
216
217
218
219
220
221
222

223
224
225
226
227
228
229

# Drop the even numbered tables
#
set r {}
for {set i 1} {$i<=100} {incr i 2} {
  lappend r [format test%03d $i]
}
#execsql {--vdbe-trace-on--}
do_test table-4.2 {
  for {set i 2} {$i<=100} {incr i 2} {

    set sql "DROP TABLE [format TEST%03d $i]"
    execsql $sql
  }
  execsql {SELECT name FROM sqlite_master WHERE type!='meta' ORDER BY name}
} $r
#exit








<


>







213
214
215
216
217
218
219

220
221
222
223
224
225
226
227
228
229

# Drop the even numbered tables
#
set r {}
for {set i 1} {$i<=100} {incr i 2} {
  lappend r [format test%03d $i]
}

do_test table-4.2 {
  for {set i 2} {$i<=100} {incr i 2} {
    # if {$i==38} {execsql {pragma vdbe_trace=on}}
    set sql "DROP TABLE [format TEST%03d $i]"
    execsql $sql
  }
  execsql {SELECT name FROM sqlite_master WHERE type!='meta' ORDER BY name}
} $r
#exit