Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | Add other bt optimizations. Fix a problem in mutex_noop.c. |
|---|---|
| Downloads: | Tarball | ZIP archive | SQL archive |
| Timelines: | family | ancestors | descendants | both | trunk |
| Files: | files | file ages | folders |
| SHA1: |
1ecbf355e361b19ea0915be2b11dd932 |
| User & Date: | dan 2014-02-22 19:54:37 |
Context
|
2014-03-18
| ||
| 19:29 | Fix an important typo in the varint decoder documentation. check-in: f392aec8a5 user: drh tags: trunk | |
|
2014-02-22
| ||
| 19:54 | Add other bt optimizations. Fix a problem in mutex_noop.c. check-in: 1ecbf355e3 user: dan tags: trunk | |
|
2014-02-21
| ||
| 17:36 | Performance tweaks for seek operations. check-in: 18ae7f9855 user: dan tags: trunk | |
Changes
Changes to src/bt_main.c.
445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 .... 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 .... 1182 1183 1184 1185 1186 1187 1188 1189 1190 1191 1192 1193 1194 1195 .... 3521 3522 3523 3524 3525 3526 3527 3528 3529 3530 3531 3532 3533 3534 .... 3655 3656 3657 3658 3659 3660 3661 3662 3663 3664 3665 3666 3667 3668 3669 |
static int btCsrDescend(BtCursor *pCsr, u32 pgno, BtPage **ppPg){
int rc;
if( pCsr->nPg>=BT_MAX_DEPTH ){
rc = btErrorBkpt(SQLITE4_CORRUPT);
}else{
assert( pCsr->nPg>=0 );
rc = sqlite4BtPageGet(pCsr->base.pDb->pPager, pgno, ppPg);
if( rc==SQLITE4_OK ){
assert( *ppPg );
pCsr->apPage[pCsr->nPg] = *ppPg;
pCsr->nPg++;
}
}
return rc;
}
/*
** Move the cursor from the current page to the parent. Return
** SQLITE4_NOTFOUND if the cursor already points to the root page,
................................................................................
BtCursor *pCsr, /* Cursor object to seek */
u8 *aPrefix, /* 8-byte key prefix, or NULL */
const void *pK, /* Key to seek for */
int nK, /* Size of key pK in bytes */
int eSeek, /* Seek mode (a BT_SEEK_XXX constant) */
int eCsrseek
){
const int pgsz = sqlite4BtPagerPagesize(pCsr->base.pDb->pPager);
u32 pgno; /* Page number for next page to load */
int rc = SQLITE4_OK; /* Return Code */
assert( eSeek==BT_SEEK_EQ || eCsrseek!=BT_CSRSEEK_RESEEK );
assert( eSeek==BT_SEEK_GE || eCsrseek!=BT_CSRSEEK_UPDATE );
/* Reset the cursor */
btCsrReset(pCsr, 0);
/* Figure out the root page number */
assert( pCsr->iRoot>1 && pCsr->nPg==0 );
pgno = pCsr->iRoot;
while( rc==SQLITE4_OK && pgno ){
/* Load page number pgno into the b-tree */
BtPage *pPg;
rc = btCsrDescend(pCsr, pgno, &pPg);
if( rc==SQLITE4_OK ){
int nCell; /* Number of cells on this page */
int iHi; /* pK/nK is <= than cell iHi */
int iLo; /* pK/nK is > than cell (iLo-1) */
int res; /* Result of comparison */
u8 *aData = btPageData(pPg);
u16 *aCellPtr = btCellPtrFind(aData, pgsz, 0);
int bLeaf = ((btFlags(aData) & BT_PGFLAGS_INTERNAL)==0);
iLo = 0;
iHi = nCell = btCellCount(aData, pgsz);
if( btFlags(aData) & BT_PGFLAGS_LARGEKEYS ){
while( iHi>iLo ){
int iTst = (iHi+iLo)/2; /* Cell to compare to pK/nK */
u8 *pCell = &aData[btGetU16(aCellPtr - iTst)];
int n = *pCell;
pCsr->aiCell[pCsr->nPg-1] = iTst;
rc = btCellKeyCompare(pCsr, bLeaf, 0, pK, nK, &res);
if( rc!=SQLITE4_OK ) break;
if( res<0 ){
/* Cell iTst is SMALLER than pK/nK */
iLo = iTst+1;
}else{
/* Cell iTst is LARGER than (or equal to) pK/nK */
iHi = iTst;
if( res==0 ) break;
}
}
}else{
while( iHi>iLo ){
int iTst = (iHi+iLo)/2; /* Cell to compare to pK/nK */
u8 *pCell = &aData[btGetU16(aCellPtr - iTst)];
int n = *pCell;
res = memcmp(&pCell[1], pK, MIN(nK, n));
if( res<0 || (res==0 && (res = n - nK)<0) ){
/* Cell iTst is SMALLER than pK/nK */
iLo = iTst+1;
}else{
/* Cell iTst is LARGER than (or equal to) pK/nK */
iHi = iTst;
if( res==0 ) break;
}
}
}
if( rc!=SQLITE4_OK ) break;
iHi += (nCell>0 && bLeaf==0 && res==0);
pCsr->aiCell[pCsr->nPg-1] = iHi;
if( bLeaf==0 ){
if( iHi==nCell ) pgno = btGetU32(&aData[1]);
else{
u8 *pCell = btCellFind(aData, pgsz, iHi);
pgno = btGetU32(&pCell[1 + (int)*pCell]);
}
}else{
pgno = 0;
if( nCell==0 ){
rc = SQLITE4_NOTFOUND;
}else if( res!=0 ){
if( eSeek==BT_SEEK_EQ ){
if( eCsrseek==BT_CSRSEEK_RESEEK ){
rc = SQLITE4_OK;
................................................................................
rc = sqlite4BtCsrNext((bt_cursor*)pCsr);
}
}
}
if( rc==SQLITE4_OK ) rc = SQLITE4_INEXACT;
}
}
}
}
}
if( rc!=SQLITE4_OK && rc!=SQLITE4_INEXACT && eCsrseek!=BT_CSRSEEK_UPDATE ){
btCsrReset(pCsr, 0);
}
................................................................................
pCsr->aiCell[1] = pCsr->aiCell[0];
pCsr->apPage[1] = pNew;
pCsr->aiCell[0] = 0;
}
return rc;
}
/*
** The cursor currently points to a cell on a b-tree page that may or
** may not be a leaf page. This routine modifies the contents of that
** page, balancing the b-tree if necessary. The page is modified as
** follows:
**
................................................................................
pHdr->iSubBlock = 0;
}
}
if( rc==SQLITE4_OK && pCsr->nPg==1 ){
rc = btExtendTree(pCsr);
}
if( rc==SQLITE4_OK ){
rc = btBalance(pCsr, bLeaf, nKV, apKV);
}
}
return rc;
}
static int btDeleteFromPage(BtCursor *pCsr, int nDel){
|
| < | | < > | < > | | | > > | | < < | > > > | < > | > > > < < > > > > > < > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | > |
445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 .... 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079 1080 1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106 1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129 1130 1131 1132 1133 1134 1135 1136 1137 1138 1139 1140 1141 1142 1143 1144 1145 1146 1147 1148 1149 1150 1151 1152 1153 1154 1155 1156 1157 1158 1159 1160 1161 1162 1163 1164 1165 1166 1167 1168 1169 .... 1189 1190 1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203 1204 1205 .... 3531 3532 3533 3534 3535 3536 3537 3538 3539 3540 3541 3542 3543 3544 3545 3546 3547 3548 3549 3550 3551 3552 3553 3554 3555 3556 3557 3558 3559 3560 3561 3562 3563 3564 3565 3566 3567 3568 3569 3570 3571 3572 3573 3574 3575 3576 3577 3578 3579 3580 3581 3582 3583 3584 3585 3586 3587 3588 3589 3590 3591 3592 3593 3594 3595 3596 3597 3598 3599 3600 3601 .... 3722 3723 3724 3725 3726 3727 3728 3729 3730 3731 3732 3733 3734 3735 3736 3737 3738 |
static int btCsrDescend(BtCursor *pCsr, u32 pgno, BtPage **ppPg){
int rc;
if( pCsr->nPg>=BT_MAX_DEPTH ){
rc = btErrorBkpt(SQLITE4_CORRUPT);
}else{
assert( pCsr->nPg>=0 );
rc = sqlite4BtPageGet(pCsr->base.pDb->pPager, pgno, ppPg);
assert( ((*ppPg)==0)==(rc!=SQLITE4_OK) );
pCsr->apPage[pCsr->nPg] = *ppPg;
pCsr->nPg++;
}
return rc;
}
/*
** Move the cursor from the current page to the parent. Return
** SQLITE4_NOTFOUND if the cursor already points to the root page,
................................................................................
BtCursor *pCsr, /* Cursor object to seek */
u8 *aPrefix, /* 8-byte key prefix, or NULL */
const void *pK, /* Key to seek for */
int nK, /* Size of key pK in bytes */
int eSeek, /* Seek mode (a BT_SEEK_XXX constant) */
int eCsrseek
){
BtPager *pPager = pCsr->base.pDb->pPager;
const int pgsz = sqlite4BtPagerPagesize(pPager);
u32 pgno; /* Page number for next page to load */
int rc; /* Return Code */
assert( eSeek==BT_SEEK_EQ || eCsrseek!=BT_CSRSEEK_RESEEK );
assert( eSeek==BT_SEEK_GE || eCsrseek!=BT_CSRSEEK_UPDATE );
/* Reset the cursor */
btCsrReset(pCsr, 0);
/* Figure out the root page number */
assert( pCsr->iRoot>1 && pCsr->nPg==0 );
pgno = pCsr->iRoot;
while( 1 ){
/* Load page number pgno into the b-tree cursor. */
BtPage *pPg;
rc = sqlite4BtPageGet(pPager, pgno, &pPg);
pCsr->apPage[pCsr->nPg++] = pPg;
if( rc==SQLITE4_OK ){
int nCell; /* Number of cells on this page */
int iHi; /* pK/nK is <= than cell iHi */
int iLo; /* pK/nK is > than cell (iLo-1) */
int res; /* Result of comparison */
u8 *aData = btPageData(pPg);
u16 *aCellPtr = (u16*)btCellPtrFind(aData, pgsz, 0);
int bLeaf = ((btFlags(aData) & BT_PGFLAGS_INTERNAL)==0);
iLo = 0;
iHi = nCell = btCellCount(aData, pgsz);
if( btFlags(aData) & BT_PGFLAGS_LARGEKEYS ){
while( iHi>iLo ){
int iTst = (iHi+iLo)/2; /* Cell to compare to pK/nK */
u8 *pCell = &aData[btGetU16((u8*)(aCellPtr - iTst))];
pCsr->aiCell[pCsr->nPg-1] = iTst;
rc = btCellKeyCompare(pCsr, bLeaf, 0, pK, nK, &res);
if( res<0 ){
/* Cell iTst is SMALLER than pK/nK */
iLo = iTst+1;
}else{
/* Cell iTst is LARGER than (or equal to) pK/nK */
iHi = iTst;
if( res==0 ){
iHi += !bLeaf;
break;
}
}
}
}else{
while( iHi>iLo ){
int iTst = (iHi+iLo)/2; /* Cell to compare to pK/nK */
u8 *pCell = &aData[btGetU16((u8*)(aCellPtr - iTst))];
int n = *pCell;
res = memcmp(&pCell[1], pK, MIN(nK, n));
if( res<0 || (res==0 && (res = n - nK)<0) ){
/* Cell iTst is SMALLER than pK/nK */
iLo = iTst+1;
}else{
/* Cell iTst is LARGER than (or equal to) pK/nK */
iHi = iTst;
if( res==0 ){
iHi += !bLeaf;
break;
}
}
}
}
if( rc!=SQLITE4_OK ) break;
pCsr->aiCell[pCsr->nPg-1] = iHi;
if( bLeaf==0 ){
if( iHi==nCell ) pgno = btGetU32(&aData[1]);
else{
u8 *pCell = btCellFind(aData, pgsz, iHi);
pgno = btGetU32(&pCell[1 + (int)*pCell]);
}
if( pCsr->nPg==BT_MAX_DEPTH ){
rc = btErrorBkpt(SQLITE4_CORRUPT);
break;
}
}else{
if( nCell==0 ){
rc = SQLITE4_NOTFOUND;
}else if( res!=0 ){
if( eSeek==BT_SEEK_EQ ){
if( eCsrseek==BT_CSRSEEK_RESEEK ){
rc = SQLITE4_OK;
................................................................................
rc = sqlite4BtCsrNext((bt_cursor*)pCsr);
}
}
}
if( rc==SQLITE4_OK ) rc = SQLITE4_INEXACT;
}
}
/* The cursor now points to a leaf page. Break out of the loop. */
break;
}
}
}
if( rc!=SQLITE4_OK && rc!=SQLITE4_INEXACT && eCsrseek!=BT_CSRSEEK_UPDATE ){
btCsrReset(pCsr, 0);
}
................................................................................
pCsr->aiCell[1] = pCsr->aiCell[0];
pCsr->apPage[1] = pNew;
pCsr->aiCell[0] = 0;
}
return rc;
}
/*
** The cursor passed as the first argument points to a leaf page into
** which the array of KV pairs specified by the second and third arguments
** would be inserted, except that there is insufficient free space on
** the page.
**
** If nKV==1, the tree is more than one level high (i.e. the root is not a
** leaf) and the new key is larger than all existing keys on the page,
** handle this in the same way as an SQLite3 "quick-balance" operation.
** Return SQLITE4_OK if successful, or an error code if an error occurs.
**
** If the quick-balance is not attempted, return SQLITE4_NOTFOUND.
*/
static int btTryAppend(BtCursor *pCsr, int nKV, KeyValue *apKV){
int rc = SQLITE4_NOTFOUND;
if( nKV==1 && pCsr->nPg>1 ){
bt_db *pDb = pCsr->base.pDb;
const int pgsz = sqlite4BtPagerPagesize(pDb->pPager);
BtPage *pOld = pCsr->apPage[pCsr->nPg-1];
u8 *aData = btPageData(pOld);
int nCell = btCellCount(aData, pgsz);
if( nCell==pCsr->aiCell[pCsr->nPg-1] ){
KeyValue kv;
BtPage *pNew = 0;
rc = btAllocateNonOverflow(pDb, &pNew);
if( rc==SQLITE4_OK ){
aData = btPageData(pNew);
btPutU16(&aData[pgsz-2], 0);
aData[0] = 0x00;
pCsr->apPage[pCsr->nPg-1] = pNew;
pCsr->aiCell[pCsr->nPg-1] = 0;
rc = btInsertAndBalance(pCsr, 1, apKV);
}
if( rc==SQLITE4_OK ){
rc = btSetChildPgno(pDb,
pCsr->apPage[pCsr->nPg-2], pCsr->aiCell[pCsr->nPg-2],
sqlite4BtPagePgno(pNew)
);
}
if( rc==SQLITE4_OK ){
assert( pCsr->apPage[pCsr->nPg-1]==pNew );
btPrefixKey(pgsz, pOld, pNew, &kv);
kv.pgno = sqlite4BtPagePgno(pOld);
kv.pV = 0;
kv.nV = 0;
kv.eType = 0;
rc = btCsrAscend(pCsr, 1);
}
if( rc==SQLITE4_OK ){
rc = btInsertAndBalance(pCsr, 1, &kv);
}
if( pNew ) sqlite4BtPageRelease(pOld);
}
}
return rc;
}
/*
** The cursor currently points to a cell on a b-tree page that may or
** may not be a leaf page. This routine modifies the contents of that
** page, balancing the b-tree if necessary. The page is modified as
** follows:
**
................................................................................
pHdr->iSubBlock = 0;
}
}
if( rc==SQLITE4_OK && pCsr->nPg==1 ){
rc = btExtendTree(pCsr);
}
if( rc==SQLITE4_OK ){
if( bLeaf==0 || SQLITE4_NOTFOUND==(rc = btTryAppend(pCsr, nKV, apKV)) ){
rc = btBalance(pCsr, bLeaf, nKV, apKV);
}
}
}
return rc;
}
static int btDeleteFromPage(BtCursor *pCsr, int nDel){
|
Changes to src/bt_pager.c.
626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 |
BtPage *pNext;
assert( p->iTransactionLevel>=2 );
rc = btPagerDbhdrFlush(p);
btCloseSavepoints(p, 2, 0);
for(pPg=p->pDirty; rc==SQLITE4_OK && pPg; pPg=pNext){
pNext = pPg->pNextDirty;
pPg->flags &= ~(BT_PAGE_DIRTY);
pPg->pNextDirty = 0;
if( rc==SQLITE4_OK ){
int nPg = ((pNext==0) ? p->pHdr->nPg : 0);
rc = sqlite4BtLogWrite(p->pLog, pPg->pgno, pPg->aData, nPg);
}
if( pPg->nRef==0 ) btLruAdd(p, pPg);
}
p->pDirty = pPg;
sqlite4BtLogSnapshotEndWrite(p->pLog);
nLogsize = sqlite4BtLogSize(p->pLog);
|
> > > < < < < |
626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 |
BtPage *pNext;
assert( p->iTransactionLevel>=2 );
rc = btPagerDbhdrFlush(p);
btCloseSavepoints(p, 2, 0);
for(pPg=p->pDirty; rc==SQLITE4_OK && pPg; pPg=pNext){
int nPg;
pNext = pPg->pNextDirty;
nPg = ((pNext==0) ? p->pHdr->nPg : 0);
rc = sqlite4BtLogWrite(p->pLog, pPg->pgno, pPg->aData, nPg);
pPg->flags &= ~(BT_PAGE_DIRTY);
pPg->pNextDirty = 0;
if( pPg->nRef==0 ) btLruAdd(p, pPg);
}
p->pDirty = pPg;
sqlite4BtLogSnapshotEndWrite(p->pLog);
nLogsize = sqlite4BtLogSize(p->pLog);
|
Changes to src/mutex_noop.c.
107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 |
** The sqlite4_mutex_alloc() routine allocates a new
** mutex and returns a pointer to it. If it returns NULL
** that means that a mutex could not be allocated.
*/
static sqlite4_mutex *debugMutexAlloc(void *pX, int id){
sqlite4_env *pEnv = (sqlite4_env*)pX;
sqlite4DebugMutex *pNew = 0;
pNew = sqlite4Malloc(pEnv, sizeof(*pNew));
if( pNew ){
pNew->id = id;
pNew->cnt = 0;
pNew->pEnv = pEnv;
}
return (sqlite4_mutex*)pNew;
}
/*
** This routine deallocates a previously allocated mutex.
*/
|
> > > > > > > > > > | | | | | > > |
107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 |
** The sqlite4_mutex_alloc() routine allocates a new
** mutex and returns a pointer to it. If it returns NULL
** that means that a mutex could not be allocated.
*/
static sqlite4_mutex *debugMutexAlloc(void *pX, int id){
sqlite4_env *pEnv = (sqlite4_env*)pX;
sqlite4DebugMutex *pNew = 0;
static sqlite4DebugMutex aStaticMutex[] = {
{ { 0 }, 0, 0, 0 }
};
if( id==SQLITE4_MUTEX_STATIC_KV ){
pNew = &aStaticMutex[0];
pNew->pEnv = pEnv;
pNew->base.pMutexMethods = sqlite4NoopMutex();
}else{
pNew = sqlite4Malloc(pEnv, sizeof(*pNew));
if( pNew ){
pNew->id = id;
pNew->cnt = 0;
pNew->pEnv = pEnv;
pNew->base.pMutexMethods = sqlite4NoopMutex();
}
}
return (sqlite4_mutex*)pNew;
}
/*
** This routine deallocates a previously allocated mutex.
*/
|