Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Improve the performance of balance_nonroot() on auto-vacuum databases by reducing the number of calls to ptrmapPut(). (CVS 5442) |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
9992b1aecdbbc7a260f00cb6ef78b500 |
User & Date: | danielk1977 2008-07-19 11:49:07.000 |
Context
2008-07-19
| ||
13:43 | To ensure SQLITE_THREADSAFE is always defined, have test_mutex.c include sqliteInt.h. (CVS 5443) (check-in: d8be91e2d2 user: danielk1977 tags: trunk) | |
11:49 | Improve the performance of balance_nonroot() on auto-vacuum databases by reducing the number of calls to ptrmapPut(). (CVS 5442) (check-in: 9992b1aecd user: danielk1977 tags: trunk) | |
2008-07-18
| ||
23:47 | Remove dead code from os_win.c. Ticket #3232. (CVS 5441) (check-in: 5c5c1f7279 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.490 2008/07/19 11:49:07 danielk1977 Exp $ ** ** This file implements a external (disk-based) database using BTrees. ** See the header comment on "btreeInt.h" for additional information. ** Including a description of file format and an overview of operation. */ #include "btreeInt.h" |
︙ | ︙ | |||
4522 4523 4524 4525 4526 4527 4528 4529 | return SQLITE_OK; } /* ** Change the MemPage.pParent pointer on the page whose number is ** given in the second argument so that MemPage.pParent holds the ** pointer in the third argument. */ | > > > > | > > > > > > | 4522 4523 4524 4525 4526 4527 4528 4529 4530 4531 4532 4533 4534 4535 4536 4537 4538 4539 4540 4541 4542 4543 4544 4545 4546 4547 | return SQLITE_OK; } /* ** Change the MemPage.pParent pointer on the page whose number is ** given in the second argument so that MemPage.pParent holds the ** pointer in the third argument. ** ** If the final argument, updatePtrmap, is non-zero and the database ** is an auto-vacuum database, then the pointer-map entry for pgno ** is updated. */ static int reparentPage( BtShared *pBt, /* B-Tree structure */ Pgno pgno, /* Page number of child being adopted */ MemPage *pNewParent, /* New parent of pgno */ int idx, /* Index of child page pgno in pNewParent */ int updatePtrmap /* If true, update pointer-map for pgno */ ){ MemPage *pThis; DbPage *pDbPage; assert( sqlite3_mutex_held(pBt->mutex) ); assert( pNewParent!=0 ); if( pgno==0 ) return SQLITE_OK; assert( pBt->pPager!=0 ); |
︙ | ︙ | |||
4547 4548 4549 4550 4551 4552 4553 | } pThis->idxParent = idx; } sqlite3PagerUnref(pDbPage); } #ifndef SQLITE_OMIT_AUTOVACUUM | | > > > > > > > > > > > > > > > > | < < < | > > > | | | | | | < | > | 4557 4558 4559 4560 4561 4562 4563 4564 4565 4566 4567 4568 4569 4570 4571 4572 4573 4574 4575 4576 4577 4578 4579 4580 4581 4582 4583 4584 4585 4586 4587 4588 4589 4590 4591 4592 4593 4594 4595 4596 4597 4598 4599 4600 4601 4602 4603 4604 4605 4606 4607 4608 4609 4610 4611 4612 4613 4614 4615 4616 4617 4618 4619 4620 4621 | } pThis->idxParent = idx; } sqlite3PagerUnref(pDbPage); } #ifndef SQLITE_OMIT_AUTOVACUUM if( pBt->autoVacuum && updatePtrmap ){ return ptrmapPut(pBt, pgno, PTRMAP_BTREE, pNewParent->pgno); } #ifndef NDEBUG /* If the updatePtrmap flag was clear, assert that the entry in the ** pointer-map is already correct. */ if( pBt->autoVacuum ){ u8 eType; Pgno ii; ptrmapGet(pBt, pgno, &eType, &ii); assert( ii==pNewParent->pgno && eType==PTRMAP_BTREE ); } #endif #endif return SQLITE_OK; } /* ** Change the pParent pointer of all children of pPage to point back ** to pPage. ** ** In other words, for every child of pPage, invoke reparentPage() ** to make sure that each child knows that pPage is its parent. ** ** This routine gets called after you memcpy() one page into ** another. ** ** If updatePtrmap is true, then the pointer-map entries for all child ** pages of pPage are updated. */ static int reparentChildPages(MemPage *pPage, int updatePtrmap){ int rc = SQLITE_OK; assert( sqlite3_mutex_held(pPage->pBt->mutex) ); if( !pPage->leaf ){ int i; BtShared *pBt = pPage->pBt; Pgno iRight = get4byte(&pPage->aData[pPage->hdrOffset+8]); for(i=0; i<pPage->nCell; i++){ u8 *pCell = findCell(pPage, i); rc = reparentPage(pBt, get4byte(pCell), pPage, i, updatePtrmap); if( rc!=SQLITE_OK ) return rc; } rc = reparentPage(pBt, iRight, pPage, i, updatePtrmap); pPage->idxShift = 0; } return rc; } /* ** Remove the i-th cell from pPage. This routine effects pPage only. ** The cell content is not freed or deallocated. It is assumed that ** the cell content has been copied someplace else. This routine just |
︙ | ︙ | |||
5346 5347 5348 5349 5350 5351 5352 | assert( j<nMaxCells ); assert( pNew->pgno==pgnoNew[i] ); zeroPage(pNew, pageFlags); assemblePage(pNew, cntNew[i]-j, &apCell[j], &szCell[j]); assert( pNew->nCell>0 || (nNew==1 && cntNew[0]==0) ); assert( pNew->nOverflow==0 ); | < > > > > | 5372 5373 5374 5375 5376 5377 5378 5379 5380 5381 5382 5383 5384 5385 5386 5387 5388 5389 5390 5391 5392 5393 5394 5395 5396 5397 5398 5399 | assert( j<nMaxCells ); assert( pNew->pgno==pgnoNew[i] ); zeroPage(pNew, pageFlags); assemblePage(pNew, cntNew[i]-j, &apCell[j], &szCell[j]); assert( pNew->nCell>0 || (nNew==1 && cntNew[0]==0) ); assert( pNew->nOverflow==0 ); /* If this is an auto-vacuum database, update the pointer map entries ** that point to the siblings that were rearranged. These can be: left ** children of cells, the right-child of the page, or overflow pages ** pointed to by cells. */ #ifndef SQLITE_OMIT_AUTOVACUUM if( pBt->autoVacuum ){ for(k=j; k<cntNew[i]; k++){ assert( k<nMaxCells ); if( aFrom[k]==0xFF || apCopy[aFrom[k]]->pgno!=pNew->pgno ){ rc = ptrmapPutOvfl(pNew, k-j); if( rc==SQLITE_OK && leafCorrection==0 ){ rc = ptrmapPut(pBt, get4byte(apCell[k]), PTRMAP_BTREE, pNew->pgno); } if( rc!=SQLITE_OK ){ goto balance_cleanup; } } } } #endif |
︙ | ︙ | |||
5381 5382 5383 5384 5385 5386 5387 5388 5389 5390 5391 5392 5393 5394 | assert( j<nMaxCells ); pCell = apCell[j]; sz = szCell[j] + leafCorrection; pTemp = &aSpace2[iSpace2]; if( !pNew->leaf ){ memcpy(&pNew->aData[8], pCell, 4); }else if( leafData ){ /* If the tree is a leaf-data tree, and the siblings are leaves, ** then there is no divider cell in apCell[]. Instead, the divider ** cell consists of the integer key for the right-most cell of ** the sibling-page assembled above only. */ CellInfo info; | > > > > > > > > > > | 5410 5411 5412 5413 5414 5415 5416 5417 5418 5419 5420 5421 5422 5423 5424 5425 5426 5427 5428 5429 5430 5431 5432 5433 | assert( j<nMaxCells ); pCell = apCell[j]; sz = szCell[j] + leafCorrection; pTemp = &aSpace2[iSpace2]; if( !pNew->leaf ){ memcpy(&pNew->aData[8], pCell, 4); #ifndef SQLITE_OMIT_AUTOVACUUM if( pBt->autoVacuum && (aFrom[j]==0xFF || apCopy[aFrom[j]]->pgno!=pNew->pgno) ){ rc = ptrmapPut(pBt, get4byte(pCell), PTRMAP_BTREE, pNew->pgno); if( rc!=SQLITE_OK ){ goto balance_cleanup; } } #endif }else if( leafData ){ /* If the tree is a leaf-data tree, and the siblings are leaves, ** then there is no divider cell in apCell[]. Instead, the divider ** cell consists of the integer key for the right-most cell of ** the sibling-page assembled above only. */ CellInfo info; |
︙ | ︙ | |||
5432 5433 5434 5435 5436 5437 5438 5439 5440 5441 5442 5443 | goto balance_cleanup; } } #endif j++; nxDiv++; } } assert( j==nCell ); assert( nOld>0 ); assert( nNew>0 ); if( (pageFlags & PTF_LEAF)==0 ){ | > > > > > > > > > > > | > > > > > > > > | | | 5471 5472 5473 5474 5475 5476 5477 5478 5479 5480 5481 5482 5483 5484 5485 5486 5487 5488 5489 5490 5491 5492 5493 5494 5495 5496 5497 5498 5499 5500 5501 5502 5503 5504 5505 5506 5507 5508 5509 5510 5511 5512 5513 5514 5515 5516 5517 5518 5519 5520 5521 5522 5523 5524 5525 5526 5527 | goto balance_cleanup; } } #endif j++; nxDiv++; } #ifndef SQLITE_OMIT_AUTOVACUUM /* Set the pointer-map entry for the new sibling page. */ if( pBt->autoVacuum ){ rc = ptrmapPut(pBt, pNew->pgno, PTRMAP_BTREE, pParent->pgno); if( rc!=SQLITE_OK ){ goto balance_cleanup; } } #endif } assert( j==nCell ); assert( nOld>0 ); assert( nNew>0 ); if( (pageFlags & PTF_LEAF)==0 ){ u8 *zChild = &apCopy[nOld-1]->aData[8]; memcpy(&apNew[nNew-1]->aData[8], zChild, 4); #ifndef SQLITE_OMIT_AUTOVACUUM if( pBt->autoVacuum ){ rc = ptrmapPut(pBt, get4byte(zChild), PTRMAP_BTREE, apNew[nNew-1]->pgno); if( rc!=SQLITE_OK ){ goto balance_cleanup; } } #endif } if( nxDiv==pParent->nCell+pParent->nOverflow ){ /* Right-most sibling is the right-most child of pParent */ put4byte(&pParent->aData[pParent->hdrOffset+8], pgnoNew[nNew-1]); }else{ /* Right-most sibling is the left child of the first entry in pParent ** past the right-most divider entry */ put4byte(findOverflowCell(pParent, nxDiv), pgnoNew[nNew-1]); } /* ** Reparent children of all cells. */ for(i=0; i<nNew; i++){ rc = reparentChildPages(apNew[i], 0); if( rc!=SQLITE_OK ) goto balance_cleanup; } rc = reparentChildPages(pParent, 0); if( rc!=SQLITE_OK ) goto balance_cleanup; /* ** Balance the parent page. Note that the current page (pPage) might ** have been added to the freelist so it might no longer be initialized. ** But the parent page will always be initialized. */ |
︙ | ︙ | |||
5563 5564 5565 5566 5567 5568 5569 | pPage->pParent = 0; rc = sqlite3BtreeInitPage(pPage, 0); assert( rc==SQLITE_OK ); freePage(pChild); TRACE(("BALANCE: transfer child %d into root %d\n", pChild->pgno, pPage->pgno)); } | | | 5621 5622 5623 5624 5625 5626 5627 5628 5629 5630 5631 5632 5633 5634 5635 | pPage->pParent = 0; rc = sqlite3BtreeInitPage(pPage, 0); assert( rc==SQLITE_OK ); freePage(pChild); TRACE(("BALANCE: transfer child %d into root %d\n", pChild->pgno, pPage->pgno)); } rc = reparentChildPages(pPage, 1); assert( pPage->nOverflow==0 ); #ifndef SQLITE_OMIT_AUTOVACUUM if( pBt->autoVacuum ){ int i; for(i=0; i<pPage->nCell; i++){ rc = ptrmapPutOvfl(pPage, i); if( rc!=SQLITE_OK ){ |
︙ | ︙ | |||
5641 5642 5643 5644 5645 5646 5647 5648 5649 | if( rc ) goto balancedeeper_out; for(i=0; i<pChild->nCell; i++){ rc = ptrmapPutOvfl(pChild, i); if( rc!=SQLITE_OK ){ goto balancedeeper_out; } } } #endif | > > | > | 5699 5700 5701 5702 5703 5704 5705 5706 5707 5708 5709 5710 5711 5712 5713 5714 5715 5716 5717 5718 | if( rc ) goto balancedeeper_out; for(i=0; i<pChild->nCell; i++){ rc = ptrmapPutOvfl(pChild, i); if( rc!=SQLITE_OK ){ goto balancedeeper_out; } } rc = reparentChildPages(pChild, 1); } #endif if( rc==SQLITE_OK ){ rc = balance_nonroot(pChild); } balancedeeper_out: releasePage(pChild); return rc; } /* |
︙ | ︙ |