Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Add the MemPage.noPayload boolean and use it to help cellSizePtr() and btreeParseCellPtr() run faster. |
---|---|
Downloads: | Tarball | ZIP archive | SQL archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
8e3375313ebbf26b68561f3ed31d2a48 |
User & Date: | drh 2014-09-24 00:59:08 |
Context
2014-09-24
| ||
01:23 | Shorten all lines of source code in btree.c to at most 80 characters. No logical changes. check-in: 5dd41cdb user: drh tags: trunk | |
00:59 | Add the MemPage.noPayload boolean and use it to help cellSizePtr() and btreeParseCellPtr() run faster. check-in: 8e337531 user: drh tags: trunk | |
2014-09-23
| ||
23:12 | Remove an unused C-preprocessor macro. No functional changes to the code. check-in: f480582c user: drh tags: trunk | |
Changes
Changes to src/btree.c.
970 970 ** takes a pointer to the body of the cell as its second argument. 971 971 */ 972 972 static void btreeParseCellPtr( 973 973 MemPage *pPage, /* Page containing the cell */ 974 974 u8 *pCell, /* Pointer to the cell text. */ 975 975 CellInfo *pInfo /* Fill in this structure */ 976 976 ){ 977 - u8 *pIter = &pCell[pPage->childPtrSize]; 977 + u8 *pIter; /* For scanning through pCell */ 978 978 u32 nPayload; /* Number of bytes of cell payload */ 979 979 980 980 assert( sqlite3_mutex_held(pPage->pBt->mutex) ); 981 981 assert( pPage->leaf==0 || pPage->leaf==1 ); 982 - if( pPage->intKey ){ 983 - if( pPage->hasData ){ 984 - assert( pIter==pCell ); 985 - pIter += getVarint32(pIter, nPayload); 986 - }else{ 987 - nPayload = 0; 988 - } 982 + if( pPage->intKeyLeaf ){ 983 + assert( pPage->childPtrSize==0 ); 984 + pIter = pCell + getVarint32(pCell, nPayload); 989 985 pIter += getVarint(pIter, (u64*)&pInfo->nKey); 986 + }else if( pPage->noPayload ){ 987 + assert( pPage->childPtrSize==4 ); 988 + pInfo->nSize = 4 + getVarint(&pCell[4], (u64*)&pInfo->nKey); 989 + pInfo->nPayload = 0; 990 + pInfo->nLocal = 0; 991 + pInfo->iOverflow = 0; 992 + pInfo->pPayload = 0; 993 + return; 990 994 }else{ 995 + pIter = pCell + pPage->childPtrSize; 991 996 pIter += getVarint32(pIter, nPayload); 992 997 pInfo->nKey = nPayload; 993 998 } 994 999 pInfo->nPayload = nPayload; 995 1000 pInfo->pPayload = pIter; 996 1001 testcase( nPayload==pPage->maxLocal ); 997 1002 testcase( nPayload==pPage->maxLocal+1 ); ................................................................................ 1042 1047 /* 1043 1048 ** Compute the total number of bytes that a Cell needs in the cell 1044 1049 ** data area of the btree-page. The return number includes the cell 1045 1050 ** data header and the local payload, but not any overflow page or 1046 1051 ** the space used by the cell pointer. 1047 1052 */ 1048 1053 static u16 cellSizePtr(MemPage *pPage, u8 *pCell){ 1049 - u8 *pIter = &pCell[pPage->childPtrSize]; 1050 - u8 *pEnd; 1051 - u32 nSize; 1054 + u8 *pIter = pCell + pPage->childPtrSize; /* For looping over bytes of pCell */ 1055 + u8 *pEnd; /* End mark for a varint */ 1056 + u32 nSize; /* Size value to return */ 1052 1057 1053 1058 #ifdef SQLITE_DEBUG 1054 1059 /* The value returned by this function should always be the same as 1055 1060 ** the (CellInfo.nSize) value found by doing a full parse of the 1056 1061 ** cell. If SQLITE_DEBUG is defined, an assert() at the bottom of 1057 1062 ** this function verifies that this invariant is not violated. */ 1058 1063 CellInfo debuginfo; 1059 1064 btreeParseCellPtr(pPage, pCell, &debuginfo); 1060 1065 #endif 1061 1066 1062 - if( pPage->intKey==0 || pPage->hasData ){ 1063 - nSize = *pIter; 1064 - if( nSize>=0x80 ){ 1065 - pEnd = &pIter[9]; 1066 - nSize &= 0x7f; 1067 - do{ 1068 - nSize = (nSize<<7) | (*++pIter & 0x7f); 1069 - }while( *(pIter)>=0x80 && pIter<pEnd ); 1070 - } 1071 - pIter++; 1072 - }else{ 1073 - nSize = 0; 1067 + if( pPage->noPayload ){ 1068 + pEnd = &pIter[9]; 1069 + while( (*pIter++)&0x80 && pIter<pEnd ); 1070 + assert( pPage->childPtrSize==4 ); 1071 + return (u16)(pIter - pCell); 1074 1072 } 1073 + nSize = *pIter; 1074 + if( nSize>=0x80 ){ 1075 + pEnd = &pIter[9]; 1076 + nSize &= 0x7f; 1077 + do{ 1078 + nSize = (nSize<<7) | (*++pIter & 0x7f); 1079 + }while( *(pIter)>=0x80 && pIter<pEnd ); 1080 + } 1081 + pIter++; 1075 1082 if( pPage->intKey ){ 1076 1083 /* pIter now points at the 64-bit integer key value, a variable length 1077 1084 ** integer. The following block moves pIter to point at the first byte 1078 1085 ** past the end of the key value. */ 1079 1086 pEnd = &pIter[9]; 1080 1087 while( (*pIter++)&0x80 && pIter<pEnd ); 1081 1088 } 1082 - 1083 1089 testcase( nSize==pPage->maxLocal ); 1084 1090 testcase( nSize==pPage->maxLocal+1 ); 1085 - if( nSize>pPage->maxLocal ){ 1091 + if( nSize<=pPage->maxLocal ){ 1092 + nSize += (u32)(pIter - pCell); 1093 + if( nSize<4 ) nSize = 4; 1094 + }else{ 1086 1095 int minLocal = pPage->minLocal; 1087 1096 nSize = minLocal + (nSize - minLocal) % (pPage->pBt->usableSize - 4); 1088 1097 testcase( nSize==pPage->maxLocal ); 1089 1098 testcase( nSize==pPage->maxLocal+1 ); 1090 1099 if( nSize>pPage->maxLocal ){ 1091 1100 nSize = minLocal; 1092 1101 } 1093 - nSize += 4; 1102 + nSize += 4 + (u16)(pIter - pCell); 1094 1103 } 1095 - nSize += (u32)(pIter - pCell); 1096 - 1097 - /* The minimum size of any cell is 4 bytes. */ 1098 - if( nSize<4 ){ 1099 - nSize = 4; 1100 - } 1101 - 1102 1104 assert( nSize==debuginfo.nSize || CORRUPT_DB ); 1103 1105 return (u16)nSize; 1104 1106 } 1105 1107 1106 1108 #ifdef SQLITE_DEBUG 1107 1109 /* This variation on cellSizePtr() is used inside of assert() statements 1108 1110 ** only. */ ................................................................................ 1438 1440 assert( sqlite3_mutex_held(pPage->pBt->mutex) ); 1439 1441 pPage->leaf = (u8)(flagByte>>3); assert( PTF_LEAF == 1<<3 ); 1440 1442 flagByte &= ~PTF_LEAF; 1441 1443 pPage->childPtrSize = 4-4*pPage->leaf; 1442 1444 pBt = pPage->pBt; 1443 1445 if( flagByte==(PTF_LEAFDATA | PTF_INTKEY) ){ 1444 1446 pPage->intKey = 1; 1445 - pPage->hasData = pPage->leaf; 1447 + pPage->intKeyLeaf = pPage->leaf; 1448 + pPage->noPayload = !pPage->leaf; 1446 1449 pPage->maxLocal = pBt->maxLeaf; 1447 1450 pPage->minLocal = pBt->minLeaf; 1448 1451 }else if( flagByte==PTF_ZERODATA ){ 1449 1452 pPage->intKey = 0; 1450 - pPage->hasData = 0; 1453 + pPage->intKeyLeaf = 0; 1454 + pPage->noPayload = 0; 1451 1455 pPage->maxLocal = pBt->maxLocal; 1452 1456 pPage->minLocal = pBt->minLocal; 1453 1457 }else{ 1454 1458 return SQLITE_CORRUPT_BKPT; 1455 1459 } 1456 1460 pPage->max1bytePayload = pBt->max1bytePayload; 1457 1461 return SQLITE_OK; ................................................................................ 3851 3855 ** Failure is not possible. This function always returns SQLITE_OK. 3852 3856 ** It might just as well be a procedure (returning void) but we continue 3853 3857 ** to return an integer result code for historical reasons. 3854 3858 */ 3855 3859 int sqlite3BtreeDataSize(BtCursor *pCur, u32 *pSize){ 3856 3860 assert( cursorHoldsMutex(pCur) ); 3857 3861 assert( pCur->eState==CURSOR_VALID ); 3858 - assert( pCur->apPage[pCur->iPage]->intKey==1 ); 3862 + assert( pCur->apPage[pCur->iPage]->intKeyLeaf==1 ); 3859 3863 getCellInfo(pCur); 3860 3864 *pSize = pCur->info.nPayload; 3861 3865 return SQLITE_OK; 3862 3866 } 3863 3867 3864 3868 /* 3865 3869 ** Given the page number of an overflow page in the database (parameter ................................................................................ 4686 4690 assert( biasRight==0 || biasRight==1 ); 4687 4691 idx = upr>>(1-biasRight); /* idx = biasRight ? upr : (lwr+upr)/2; */ 4688 4692 pCur->aiIdx[pCur->iPage] = (u16)idx; 4689 4693 if( xRecordCompare==0 ){ 4690 4694 for(;;){ 4691 4695 i64 nCellKey; 4692 4696 pCell = findCell(pPage, idx) + pPage->childPtrSize; 4693 - if( pPage->hasData ){ 4697 + if( pPage->intKeyLeaf ){ 4694 4698 while( 0x80 <= *(pCell++) ){ 4695 4699 if( pCell>=pPage->aDataEnd ) return SQLITE_CORRUPT_BKPT; 4696 4700 } 4697 4701 } 4698 4702 getVarint(pCell, (u64*)&nCellKey); 4699 4703 if( nCellKey<intKey ){ 4700 4704 lwr = idx+1; ................................................................................ 5613 5617 ** buffer space that is separate from the pPage buffer area */ 5614 5618 assert( pCell<pPage->aData || pCell>=&pPage->aData[pBt->pageSize] 5615 5619 || sqlite3PagerIswriteable(pPage->pDbPage) ); 5616 5620 5617 5621 /* Fill in the header. */ 5618 5622 nHeader = pPage->childPtrSize; 5619 5623 nPayload = nData + nZero; 5620 - if( pPage->hasData ){ 5621 - assert( pPage->intKey ); 5624 + if( pPage->intKeyLeaf ){ 5622 5625 nHeader += putVarint32(&pCell[nHeader], nPayload); 5623 5626 }else{ 5624 5627 assert( nData==0 ); 5625 5628 assert( nZero==0 ); 5626 5629 } 5627 5630 nHeader += putVarint(&pCell[nHeader], *(u64*)&nKey); 5628 5631 ................................................................................ 6387 6390 ** apCell[] include child pointers. Either way, all cells in apCell[] 6388 6391 ** are alike. 6389 6392 ** 6390 6393 ** leafCorrection: 4 if pPage is a leaf. 0 if pPage is not a leaf. 6391 6394 ** leafData: 1 if pPage holds key+data and pParent holds only keys. 6392 6395 */ 6393 6396 leafCorrection = apOld[0]->leaf*4; 6394 - leafData = apOld[0]->hasData; 6397 + leafData = apOld[0]->intKeyLeaf; 6395 6398 for(i=0; i<nOld; i++){ 6396 6399 int limit; 6397 6400 6398 6401 /* Before doing anything else, take a copy of the i'th original sibling 6399 6402 ** The rest of this function will use data from the copies rather 6400 6403 ** that the original pages since the original pages will be in the 6401 6404 ** process of being overwritten. */ ................................................................................ 6963 6966 }else{ 6964 6967 MemPage * const pParent = pCur->apPage[iPage-1]; 6965 6968 int const iIdx = pCur->aiIdx[iPage-1]; 6966 6969 6967 6970 rc = sqlite3PagerWrite(pParent->pDbPage); 6968 6971 if( rc==SQLITE_OK ){ 6969 6972 #ifndef SQLITE_OMIT_QUICKBALANCE 6970 - if( pPage->hasData 6973 + if( pPage->intKeyLeaf 6971 6974 && pPage->nOverflow==1 6972 6975 && pPage->aiOvfl[0]==pPage->nCell 6973 6976 && pParent->pgno!=1 6974 6977 && pParent->nCell==iIdx 6975 6978 ){ 6976 6979 /* Call balance_quick() to create a new sibling of pPage on which 6977 6980 ** to store the overflow cell. balance_quick() inserts a new cell
Changes to src/btreeInt.h.
269 269 ** 270 270 ** Access to all fields of this structure is controlled by the mutex 271 271 ** stored in MemPage.pBt->mutex. 272 272 */ 273 273 struct MemPage { 274 274 u8 isInit; /* True if previously initialized. MUST BE FIRST! */ 275 275 u8 nOverflow; /* Number of overflow cell bodies in aCell[] */ 276 - u8 intKey; /* True if intkey flag is set */ 277 - u8 leaf; /* True if leaf flag is set */ 278 - u8 hasData; /* True if this page stores data */ 276 + u8 intKey; /* True if table b-trees. False for index b-trees */ 277 + u8 intKeyLeaf; /* True if the leaf of an intKey table */ 278 + u8 noPayload; /* True if internal intKey page (thus w/o data) */ 279 + u8 leaf; /* True if a leaf page */ 279 280 u8 hdrOffset; /* 100 for page 1. 0 otherwise */ 280 281 u8 childPtrSize; /* 0 if leaf==1. 4 if leaf==0 */ 281 282 u8 max1bytePayload; /* min(maxLocal,127) */ 282 283 u16 maxLocal; /* Copy of BtShared.maxLocal or BtShared.maxLeaf */ 283 284 u16 minLocal; /* Copy of BtShared.minLocal or BtShared.minLeaf */ 284 285 u16 cellOffset; /* Index in aData of first cell pointer */ 285 286 u16 nFree; /* Number of free bytes on the page */