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 |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
fd7e41f0eed80fb1c7e18eb84834ec3c |
User & Date: | drh 2002-07-08 10:59:51.000 |
Context
2002-07-08
| ||
22:03 | Add support for TEMPORARY views. The code is here but it is mostly untested. (CVS 668) (check-in: 87cd10c1f6 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: fd7e41f0ee 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: 3c2dea4310 user: drh tags: trunk) | |
Changes
Changes to src/btree.c.
1 2 3 4 5 6 7 8 9 10 11 | /* ** 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. ** ************************************************************************* | | | 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.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. |
︙ | ︙ | |||
1505 1506 1507 1508 1509 1510 1511 1512 | ** 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. */ | > > > > > | | 1505 1506 1507 1508 1509 1510 1511 1512 1513 1514 1515 1516 1517 1518 1519 1520 1521 1522 1523 1524 1525 | ** 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); |
︙ | ︙ | |||
1529 1530 1531 1532 1533 1534 1535 1536 | } pInfo = (FreelistInfo*)pOvfl->aPayload; if( pInfo->nFree==0 ){ *pPgno = pPage1->freeList; pPage1->freeList = pOvfl->iNext; *ppPage = (MemPage*)pOvfl; }else{ pInfo->nFree--; | > > > > > > > > > > > > > > | > | 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 | } 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); } } |
︙ | ︙ | |||
1656 1657 1658 1659 1660 1661 1662 1663 1664 1665 1666 1667 1668 1669 1670 1671 1672 1673 1674 1675 1676 1677 1678 1679 | 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; pNext = &pCell->ovfl; pSpace = pCell->aPayload; spaceLeft = MX_LOCAL_PAYLOAD; pPayload = pKey; pKey = 0; nPayload = nKey; pPrior = 0; while( nPayload>0 ){ if( spaceLeft==0 ){ | > | > > | 1676 1677 1678 1679 1680 1681 1682 1683 1684 1685 1686 1687 1688 1689 1690 1691 1692 1693 1694 1695 1696 1697 1698 1699 1700 1701 1702 1703 1704 1705 1706 1707 1708 1709 1710 1711 1712 | 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; pNext = &pCell->ovfl; pSpace = pCell->aPayload; 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; |
︙ | ︙ | |||
1982 1983 1984 1985 1986 1987 1988 | ** 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; | | | 2005 2006 2007 2008 2009 2010 2011 2012 2013 2014 2015 2016 2017 2018 2019 | ** 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 ){ |
︙ | ︙ | |||
2167 2168 2169 2170 2171 2172 2173 | 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{ | | | 2190 2191 2192 2193 2194 2195 2196 2197 2198 2199 2200 2201 2202 2203 2204 | 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; } |
︙ | ︙ | |||
2451 2452 2453 2454 2455 2456 2457 | int rc; if( !pBt->inTrans ){ return SQLITE_ERROR; /* Must start a transaction first */ } if( pBt->readOnly ){ return SQLITE_READONLY; } | | | 2474 2475 2476 2477 2478 2479 2480 2481 2482 2483 2484 2485 2486 2487 2488 | 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; } |
︙ | ︙ |