Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Fix an auto-vacuum bug that occurs when a btree cell is promoted to the parent page during a delete. (CVS 2043) |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
b7d953e1195897de4869ec241a65e8a3 |
User & Date: | danielk1977 2004-11-03 03:01:17.000 |
Context
2004-11-03
| ||
03:52 | Auto-vacuum bugfix: Do not attempt to move a pointer-map page during auto-vacuum. (CVS 2044) (check-in: bd50fbb5fe user: danielk1977 tags: trunk) | |
03:01 | Fix an auto-vacuum bug that occurs when a btree cell is promoted to the parent page during a delete. (CVS 2043) (check-in: b7d953e119 user: danielk1977 tags: trunk) | |
2004-11-02
| ||
18:15 | Fix a problem in the pragma.test script. (CVS 2041) (check-in: a2c9c45c80 user: drh tags: trunk) | |
Changes
Changes to src/btree.c.
1 2 3 4 5 6 7 8 9 10 11 | /* ** 2004 April 6 ** ** 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 | /* ** 2004 April 6 ** ** 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.200 2004/11/03 03:01:17 danielk1977 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. |
︙ | ︙ | |||
1749 1750 1751 1752 1753 1754 1755 | rc = sqlite3pager_truncate(pBt->pPager, finDbSize); if( rc!=SQLITE_OK ) goto autovacuum_out; autovacuum_out: /* TODO: A goto autovacuum_out; will fail to call releasePage() on ** outstanding references. Fix. */ | < < < < < | 1749 1750 1751 1752 1753 1754 1755 1756 1757 1758 1759 1760 1761 1762 | rc = sqlite3pager_truncate(pBt->pPager, finDbSize); if( rc!=SQLITE_OK ) goto autovacuum_out; autovacuum_out: /* TODO: A goto autovacuum_out; will fail to call releasePage() on ** outstanding references. Fix. */ assert( nRef==*sqlite3pager_stats(pPager) ); if( rc!=SQLITE_OK ){ sqlite3pager_rollback(pPager); } return rc; } #endif |
︙ | ︙ | |||
3170 3171 3172 3173 3174 3175 3176 | ** pointer-map must be updated accordingly. ** ** TODO: This looks like quite an expensive thing to do. Investigate. */ if( pBt->autoVacuum ){ CellInfo info; parseCellPtr(pPage, pCell, &info); | | | 3165 3166 3167 3168 3169 3170 3171 3172 3173 3174 3175 3176 3177 3178 3179 | ** pointer-map must be updated accordingly. ** ** TODO: This looks like quite an expensive thing to do. Investigate. */ if( pBt->autoVacuum ){ CellInfo info; parseCellPtr(pPage, pCell, &info); if( (info.nData+(pPage->intKey?0:info.nKey))>info.nLocal ){ Pgno pgnoOvfl = get4byte(&pCell[info.iOverflow]); rc = ptrmapPut(pBt, pgnoOvfl, PTRMAP_OVERFLOW1, pPage->pgno); if( rc!=SQLITE_OK ) return rc; } } #endif } |
︙ | ︙ | |||
3230 3231 3232 3233 3234 3235 3236 | ** will not fit, then make a copy of the cell content into pTemp if ** pTemp is not null. Regardless of pTemp, allocate a new entry ** in pPage->aOvfl[] and make it point to the cell content (either ** in pTemp or the original pCell) and also record its index. ** Allocating a new entry in pPage->aCell[] implies that ** pPage->nOverflow is incremented. */ | | | 3225 3226 3227 3228 3229 3230 3231 3232 3233 3234 3235 3236 3237 3238 3239 | ** will not fit, then make a copy of the cell content into pTemp if ** pTemp is not null. Regardless of pTemp, allocate a new entry ** in pPage->aOvfl[] and make it point to the cell content (either ** in pTemp or the original pCell) and also record its index. ** Allocating a new entry in pPage->aCell[] implies that ** pPage->nOverflow is incremented. */ static int insertCell( MemPage *pPage, /* Page into which we are copying */ int i, /* New cell becomes the i-th cell of the page */ u8 *pCell, /* Content of the new cell */ int sz, /* Bytes of content in pCell */ u8 *pTemp /* Temp storage space for pCell, if needed */ ){ int idx; /* Where to write new cell content in data[] */ |
︙ | ︙ | |||
3287 3288 3289 3290 3291 3292 3293 3294 3295 3296 3297 3298 3299 3300 | ptr[1] = ptr[-1]; } put2byte(&data[ins], idx); put2byte(&data[hdr+3], pPage->nCell); pPage->idxShift = 1; pageIntegrity(pPage); } } /* ** Add a list of cells to a page. The page should be initially empty. ** The cells are guaranteed to fit on the page. */ static void assemblePage( | > > > > > > > > > > > > > > > > | 3282 3283 3284 3285 3286 3287 3288 3289 3290 3291 3292 3293 3294 3295 3296 3297 3298 3299 3300 3301 3302 3303 3304 3305 3306 3307 3308 3309 3310 3311 | ptr[1] = ptr[-1]; } put2byte(&data[ins], idx); put2byte(&data[hdr+3], pPage->nCell); pPage->idxShift = 1; pageIntegrity(pPage); } #ifndef SQLITE_OMIT_AUTOVACUUM if( pPage->pBt->autoVacuum ){ /* The cell may contain a pointer to an overflow page. If so, write ** the entry for the overflow page into the pointer map. */ CellInfo info; parseCellPtr(pPage, pCell, &info); if( (info.nData+(pPage->intKey?0:info.nKey))>info.nLocal ){ Pgno pgnoOvfl = get4byte(&pCell[info.iOverflow]); int rc = ptrmapPut(pPage->pBt, pgnoOvfl, PTRMAP_OVERFLOW1, pPage->pgno); if( rc!=SQLITE_OK ) return rc; } } #endif return SQLITE_OK; } /* ** Add a list of cells to a page. The page should be initially empty. ** The cells are guaranteed to fit on the page. */ static void assemblePage( |
︙ | ︙ | |||
3756 3757 3758 3759 3760 3761 3762 | pTemp = 0; }else{ pCell -= 4; pTemp = &aSpace[iSpace]; iSpace += sz; assert( iSpace<=pBt->psAligned*5 ); } | | > | 3767 3768 3769 3770 3771 3772 3773 3774 3775 3776 3777 3778 3779 3780 3781 3782 | pTemp = 0; }else{ pCell -= 4; pTemp = &aSpace[iSpace]; iSpace += sz; assert( iSpace<=pBt->psAligned*5 ); } rc = insertCell(pParent, nxDiv, pCell, sz, pTemp); if( rc!=SQLITE_OK ) goto balance_cleanup; put4byte(findOverflowCell(pParent,nxDiv), pNew->pgno); j++; nxDiv++; } } assert( j==nCell ); if( (pageFlags & PTF_LEAF)==0 ){ |
︙ | ︙ | |||
4063 4064 4065 4066 4067 4068 4069 | }else if( loc<0 && pPage->nCell>0 ){ assert( pPage->leaf ); pCur->idx++; pCur->info.nSize = 0; }else{ assert( pPage->leaf ); } | | > | 4075 4076 4077 4078 4079 4080 4081 4082 4083 4084 4085 4086 4087 4088 4089 4090 | }else if( loc<0 && pPage->nCell>0 ){ assert( pPage->leaf ); pCur->idx++; pCur->info.nSize = 0; }else{ assert( pPage->leaf ); } rc = insertCell(pPage, pCur->idx, newCell, szNew, 0); if( rc!=SQLITE_OK ) goto end_insert; rc = balance(pPage); /* sqlite3BtreePageDump(pCur->pBt, pCur->pgnoRoot, 1); */ /* fflush(stdout); */ if( rc==SQLITE_OK ){ moveToRoot(pCur); } end_insert: |
︙ | ︙ | |||
4143 4144 4145 4146 4147 4148 4149 | pCur->pgnoRoot, pPage->pgno, leafCur.pPage->pgno)); dropCell(pPage, pCur->idx, cellSizePtr(pPage, pCell)); pNext = findCell(leafCur.pPage, leafCur.idx); szNext = cellSizePtr(leafCur.pPage, pNext); assert( MX_CELL_SIZE(pBt)>=szNext+4 ); tempCell = sqliteMallocRaw( MX_CELL_SIZE(pBt) ); if( tempCell==0 ) return SQLITE_NOMEM; | | > | 4156 4157 4158 4159 4160 4161 4162 4163 4164 4165 4166 4167 4168 4169 4170 4171 | pCur->pgnoRoot, pPage->pgno, leafCur.pPage->pgno)); dropCell(pPage, pCur->idx, cellSizePtr(pPage, pCell)); pNext = findCell(leafCur.pPage, leafCur.idx); szNext = cellSizePtr(leafCur.pPage, pNext); assert( MX_CELL_SIZE(pBt)>=szNext+4 ); tempCell = sqliteMallocRaw( MX_CELL_SIZE(pBt) ); if( tempCell==0 ) return SQLITE_NOMEM; rc = insertCell(pPage, pCur->idx, pNext-4, szNext+4, tempCell); if( rc!=SQLITE_OK ) return rc; put4byte(findOverflowCell(pPage, pCur->idx), pgnoChild); rc = balance(pPage); sqliteFree(tempCell); if( rc ) return rc; dropCell(leafCur.pPage, leafCur.idx, szNext); rc = balance(leafCur.pPage); releaseTempCursor(&leafCur); |
︙ | ︙ |
Changes to test/autovacuum.test.
1 2 3 4 5 6 7 8 9 10 11 12 13 | # 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 SELECT statement. # | | | < < < < < < < | | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 | # 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 SELECT statement. # # $Id: autovacuum.test,v 1.3 2004/11/03 03:01:17 danielk1977 Exp $ set testdir [file dirname $argv0] source $testdir/tester.tcl proc make_str {char len} { set str [string repeat $char. $len] return [string range $str 0 [expr $len-1]] } proc file_pages {} { return [expr [file size test.db] / 1024] } do_test autovacuum-1.1 { execsql { CREATE TABLE av1(a); CREATE INDEX av1_idx ON av1(a); } } {} set ENTRY_LEN 3000 set delete_orders [list] lappend delete_orders {1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20} lappend delete_orders {20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1} lappend delete_orders {8 18 2 4 14 11 13 3 10 7 9 5 12 17 19 15 20 6 16 1} lappend delete_orders {10 3 11 17 19 20 7 4 13 6 1 14 16 12 9 18 8 15 5 2} lappend delete_orders {{1 2 3 4 5 6 7 8 9 10} {11 12 13 14 15 16 17 18 19 20}} lappend delete_orders \ {{19 8 17 15} {16 11 9 14} {18 5 3 1} {13 20 7 2} {6 12 4 10}} set tn 0 foreach delete_order $delete_orders { incr tn # Set up the table. set ::tbl_data [list] foreach i [lsort -integer [eval concat $delete_order]] { execsql "INSERT INTO av1 (oid, a) VALUES($i, '[make_str $i $ENTRY_LEN]')" lappend ::tbl_data [make_str $i $ENTRY_LEN] } do_test autovacuum-1.$tn.1 { execsql { pragma integrity_check } } {ok} foreach delete $delete_order { do_test autovacuum-1.$tn.($delete).1 { execsql " DELETE FROM av1 WHERE oid IN ([join $delete ,]) " } {} do_test autovacuum-1.$tn.($delete).2 { execsql { pragma integrity_check } } {ok} foreach d $delete { set idx [lsearch $::tbl_data [make_str $d $ENTRY_LEN]] set ::tbl_data [lreplace $::tbl_data $idx $idx] } do_test autovacuum-1.$tn.($delete).3 { execsql { select a from av1 } } $::tbl_data } do_test autovacuum-1.$tn.3 { file_pages } {4} } finish_test |