/ Check-in [fd7e41f0]
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:In the BTree subsystem, when using pages from the freelist, attempt to select pages close to related pages in order to keep data structures near each other in the database file. This improves access speed in some circumstances. (CVS 667)
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: fd7e41f0eed80fb1c7e18eb84834ec3cea74a649
User & Date: drh 2002-07-08 10:59:51
Context
2002-07-08
22:03
Add support for TEMPORARY views. The code is here but it is mostly untested. (CVS 668) check-in: 87cd10c1 user: drh tags: trunk
10:59
In the BTree subsystem, when using pages from the freelist, attempt to select pages close to related pages in order to keep data structures near each other in the database file. This improves access speed in some circumstances. (CVS 667) check-in: fd7e41f0 user: drh tags: trunk
02:16
Make the BTree balance() routine a little faster by reusing database pages locally rather than freeing and reallocating them. (CVS 666) check-in: 3c2dea43 user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/btree.c.

5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
....
1505
1506
1507
1508
1509
1510
1511





1512
1513
1514
1515
1516
1517
1518
1519
1520
....
1529
1530
1531
1532
1533
1534
1535














1536

1537
1538
1539
1540
1541
1542
1543
1544
....
1656
1657
1658
1659
1660
1661
1662

1663
1664
1665
1666
1667
1668
1669
....
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682


1683
1684
1685
1686
1687
1688
1689
....
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
....
2167
2168
2169
2170
2171
2172
2173
2174
2175
2176
2177
2178
2179
2180
2181
....
2451
2452
2453
2454
2455
2456
2457
2458
2459
2460
2461
2462
2463
2464
2465
** 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.66 2002/07/08 02:16:38 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.
................................................................................
** has already been called on the new page.)  The new page has also
** been referenced and the calling routine is responsible for calling
** sqlitepager_unref() on the new page when it is done.
**
** SQLITE_OK is returned on success.  Any other return value indicates
** an error.  *ppPage and *pPgno are undefined in the event of an error.
** Do not invoke sqlitepager_unref() on *ppPage if an error is returned.





*/
static int allocatePage(Btree *pBt, MemPage **ppPage, Pgno *pPgno){
  PageOne *pPage1 = pBt->page1;
  int rc;
  if( pPage1->freeList ){
    OverflowPage *pOvfl;
    FreelistInfo *pInfo;

    rc = sqlitepager_write(pPage1);
................................................................................
    }
    pInfo = (FreelistInfo*)pOvfl->aPayload;
    if( pInfo->nFree==0 ){
      *pPgno = pPage1->freeList;
      pPage1->freeList = pOvfl->iNext;
      *ppPage = (MemPage*)pOvfl;
    }else{














      pInfo->nFree--;

      *pPgno = pInfo->aFree[pInfo->nFree];
      rc = sqlitepager_get(pBt->pPager, *pPgno, (void**)ppPage);
      sqlitepager_unref(pOvfl);
      if( rc==SQLITE_OK ){
        sqlitepager_dont_rollback(*ppPage);
        rc = sqlitepager_write(*ppPage);
      }
    }
................................................................................
  OverflowPage *pOvfl, *pPrior;
  Pgno *pNext;
  int spaceLeft;
  int n, rc;
  int nPayload;
  const char *pPayload;
  char *pSpace;


  pCell->h.leftChild = 0;
  pCell->h.nKey = nKey & 0xffff;
  pCell->h.nKeyHi = nKey >> 16;
  pCell->h.nData = nData & 0xffff;
  pCell->h.nDataHi = nData >> 16;
  pCell->h.iNext = 0;
................................................................................
  spaceLeft = MX_LOCAL_PAYLOAD;
  pPayload = pKey;
  pKey = 0;
  nPayload = nKey;
  pPrior = 0;
  while( nPayload>0 ){
    if( spaceLeft==0 ){
      rc = allocatePage(pBt, (MemPage**)&pOvfl, pNext);
      if( rc ){
        *pNext = 0;


      }
      if( pPrior ) sqlitepager_unref(pPrior);
      if( rc ){
        clearCell(pBt, pCell);
        return rc;
      }
      pPrior = pOvfl;
................................................................................
    ** contents of the root into the child.  Then make the root
    ** page an empty page with rightChild pointing to the new
    ** child.  Then fall thru to the code below which will cause
    ** the overfull child page to be split.
    */
    rc = sqlitepager_write(pPage);
    if( rc ) return rc;
    rc = allocatePage(pBt, &pChild, &pgnoChild);
    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 ){
................................................................................
  for(i=0; i<k; i++){
    if( i<nOld ){
      apNew[i] = apOld[i];
      pgnoNew[i] = pgnoOld[i];
      apOld[i] = 0;
      sqlitepager_write(apNew[i]);
    }else{
      rc = allocatePage(pBt, &apNew[i], &pgnoNew[i]);
      if( rc ) goto balance_cleanup;
    }
    nNew++;
    zeroPage(apNew[i]);
    apNew[i]->isInit = 1;
  }

................................................................................
  int rc;
  if( !pBt->inTrans ){
    return SQLITE_ERROR;  /* Must start a transaction first */
  }
  if( pBt->readOnly ){
    return SQLITE_READONLY;
  }
  rc = allocatePage(pBt, &pRoot, &pgnoRoot);
  if( rc ) return rc;
  assert( sqlitepager_iswriteable(pRoot) );
  zeroPage(pRoot);
  sqlitepager_unref(pRoot);
  *piTable = (int)pgnoRoot;
  return SQLITE_OK;
}







|







 







>
>
>
>
>

|







 







>
>
>
>
>
>
>
>
>
>
>
>
>
>

>
|







 







>







 







|


>
>







 







|







 







|







 







|







5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
....
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
....
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
....
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
....
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
....
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
....
2190
2191
2192
2193
2194
2195
2196
2197
2198
2199
2200
2201
2202
2203
2204
....
2474
2475
2476
2477
2478
2479
2480
2481
2482
2483
2484
2485
2486
2487
2488
** 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.67 2002/07/08 10:59:51 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.
................................................................................
** has already been called on the new page.)  The new page has also
** been referenced and the calling routine is responsible for calling
** sqlitepager_unref() on the new page when it is done.
**
** SQLITE_OK is returned on success.  Any other return value indicates
** an error.  *ppPage and *pPgno are undefined in the event of an error.
** Do not invoke sqlitepager_unref() on *ppPage if an error is returned.
**
** If the "near" parameter is not 0, then a (feeble) effort is made to 
** locate a page close to the page number "near".  This can be used in an
** attempt to keep related pages close to each other in the database file,
** which in turn can make database access faster.
*/
static int allocatePage(Btree *pBt, MemPage **ppPage, Pgno *pPgno, Pgno near){
  PageOne *pPage1 = pBt->page1;
  int rc;
  if( pPage1->freeList ){
    OverflowPage *pOvfl;
    FreelistInfo *pInfo;

    rc = sqlitepager_write(pPage1);
................................................................................
    }
    pInfo = (FreelistInfo*)pOvfl->aPayload;
    if( pInfo->nFree==0 ){
      *pPgno = pPage1->freeList;
      pPage1->freeList = pOvfl->iNext;
      *ppPage = (MemPage*)pOvfl;
    }else{
      int closest;
      if( pInfo->nFree>1 && near>0 ){
        int i, dist;
        closest = 0;
        dist = pInfo->aFree[0] - near;
        if( dist<0 ) dist = -dist;
        for(i=1; i<pInfo->nFree; i++){
          int d2 = pInfo->aFree[i] - near;
          if( d2<0 ) d2 = -d2;
          if( d2<dist ) closest = i;
        }
      }else{
        closest = 0;
      }
      pInfo->nFree--;
      *pPgno = pInfo->aFree[closest];
      pInfo->aFree[closest] = pInfo->aFree[pInfo->nFree];
      rc = sqlitepager_get(pBt->pPager, *pPgno, (void**)ppPage);
      sqlitepager_unref(pOvfl);
      if( rc==SQLITE_OK ){
        sqlitepager_dont_rollback(*ppPage);
        rc = sqlitepager_write(*ppPage);
      }
    }
................................................................................
  OverflowPage *pOvfl, *pPrior;
  Pgno *pNext;
  int spaceLeft;
  int n, rc;
  int nPayload;
  const char *pPayload;
  char *pSpace;
  Pgno near = 0;

  pCell->h.leftChild = 0;
  pCell->h.nKey = nKey & 0xffff;
  pCell->h.nKeyHi = nKey >> 16;
  pCell->h.nData = nData & 0xffff;
  pCell->h.nDataHi = nData >> 16;
  pCell->h.iNext = 0;
................................................................................
  spaceLeft = MX_LOCAL_PAYLOAD;
  pPayload = pKey;
  pKey = 0;
  nPayload = nKey;
  pPrior = 0;
  while( nPayload>0 ){
    if( spaceLeft==0 ){
      rc = allocatePage(pBt, (MemPage**)&pOvfl, pNext, near);
      if( rc ){
        *pNext = 0;
      }else{
        near = *pNext;
      }
      if( pPrior ) sqlitepager_unref(pPrior);
      if( rc ){
        clearCell(pBt, pCell);
        return rc;
      }
      pPrior = pOvfl;
................................................................................
    ** contents of the root into the child.  Then make the root
    ** page an empty page with rightChild pointing to the new
    ** child.  Then fall thru to the code below which will cause
    ** the overfull child page to be split.
    */
    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 ){
................................................................................
  for(i=0; i<k; i++){
    if( i<nOld ){
      apNew[i] = apOld[i];
      pgnoNew[i] = pgnoOld[i];
      apOld[i] = 0;
      sqlitepager_write(apNew[i]);
    }else{
      rc = allocatePage(pBt, &apNew[i], &pgnoNew[i], pgnoNew[i-1]);
      if( rc ) goto balance_cleanup;
    }
    nNew++;
    zeroPage(apNew[i]);
    apNew[i]->isInit = 1;
  }

................................................................................
  int rc;
  if( !pBt->inTrans ){
    return SQLITE_ERROR;  /* Must start a transaction first */
  }
  if( pBt->readOnly ){
    return SQLITE_READONLY;
  }
  rc = allocatePage(pBt, &pRoot, &pgnoRoot, 0);
  if( rc ) return rc;
  assert( sqlitepager_iswriteable(pRoot) );
  zeroPage(pRoot);
  sqlitepager_unref(pRoot);
  *piTable = (int)pgnoRoot;
  return SQLITE_OK;
}