/ Check-in [9992b1ae]
Login
SQLite training in Houston TX on 2019-11-05 (details)
Part of the 2019 Tcl Conference

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 | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 9992b1aecdbbc7a260f00cb6ef78b500aeab22df
User & Date: danielk1977 2008-07-19 11:49:07
Context
2008-07-19
13:43
To ensure SQLITE_THREADSAFE is always defined, have test_mutex.c include sqliteInt.h. (CVS 5443) check-in: d8be91e2 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: 9992b1ae user: danielk1977 tags: trunk
2008-07-18
23:47
Remove dead code from os_win.c. Ticket #3232. (CVS 5441) check-in: 5c5c1f72 user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/btree.c.

     5      5   ** a legal notice, here is a blessing:
     6      6   **
     7      7   **    May you do good and not evil.
     8      8   **    May you find forgiveness for yourself and forgive others.
     9      9   **    May you share freely, never taking more than you give.
    10     10   **
    11     11   *************************************************************************
    12         -** $Id: btree.c,v 1.489 2008/07/18 17:16:26 drh Exp $
           12  +** $Id: btree.c,v 1.490 2008/07/19 11:49:07 danielk1977 Exp $
    13     13   **
    14     14   ** This file implements a external (disk-based) database using BTrees.
    15     15   ** See the header comment on "btreeInt.h" for additional information.
    16     16   ** Including a description of file format and an overview of operation.
    17     17   */
    18     18   #include "btreeInt.h"
    19     19   
................................................................................
  4522   4522     return SQLITE_OK;
  4523   4523   }
  4524   4524   
  4525   4525   /*
  4526   4526   ** Change the MemPage.pParent pointer on the page whose number is
  4527   4527   ** given in the second argument so that MemPage.pParent holds the
  4528   4528   ** pointer in the third argument.
         4529  +**
         4530  +** If the final argument, updatePtrmap, is non-zero and the database
         4531  +** is an auto-vacuum database, then the pointer-map entry for pgno
         4532  +** is updated.
  4529   4533   */
  4530         -static int reparentPage(BtShared *pBt, Pgno pgno, MemPage *pNewParent, int idx){
         4534  +static int reparentPage(
         4535  +  BtShared *pBt,                /* B-Tree structure */
         4536  +  Pgno pgno,                    /* Page number of child being adopted */
         4537  +  MemPage *pNewParent,          /* New parent of pgno */
         4538  +  int idx,                      /* Index of child page pgno in pNewParent */
         4539  +  int updatePtrmap              /* If true, update pointer-map for pgno */
         4540  +){
  4531   4541     MemPage *pThis;
  4532   4542     DbPage *pDbPage;
  4533   4543   
  4534   4544     assert( sqlite3_mutex_held(pBt->mutex) );
  4535   4545     assert( pNewParent!=0 );
  4536   4546     if( pgno==0 ) return SQLITE_OK;
  4537   4547     assert( pBt->pPager!=0 );
................................................................................
  4547   4557         }
  4548   4558         pThis->idxParent = idx;
  4549   4559       }
  4550   4560       sqlite3PagerUnref(pDbPage);
  4551   4561     }
  4552   4562   
  4553   4563   #ifndef SQLITE_OMIT_AUTOVACUUM
  4554         -  if( pBt->autoVacuum ){
         4564  +  if( pBt->autoVacuum && updatePtrmap ){
  4555   4565       return ptrmapPut(pBt, pgno, PTRMAP_BTREE, pNewParent->pgno);
  4556   4566     }
         4567  +
         4568  +#ifndef NDEBUG
         4569  +  /* If the updatePtrmap flag was clear, assert that the entry in the
         4570  +  ** pointer-map is already correct.
         4571  +  */
         4572  +  if( pBt->autoVacuum ){
         4573  +    u8 eType;
         4574  +    Pgno ii;
         4575  +    ptrmapGet(pBt, pgno, &eType, &ii);
         4576  +    assert( ii==pNewParent->pgno && eType==PTRMAP_BTREE );
         4577  +  }
         4578  +#endif
         4579  +
  4557   4580   #endif
  4558   4581     return SQLITE_OK;
  4559   4582   }
  4560   4583   
  4561   4584   
  4562   4585   
  4563   4586   /*
................................................................................
  4565   4588   ** to pPage.
  4566   4589   **
  4567   4590   ** In other words, for every child of pPage, invoke reparentPage()
  4568   4591   ** to make sure that each child knows that pPage is its parent.
  4569   4592   **
  4570   4593   ** This routine gets called after you memcpy() one page into
  4571   4594   ** another.
         4595  +**
         4596  +** If updatePtrmap is true, then the pointer-map entries for all child
         4597  +** pages of pPage are updated.
  4572   4598   */
  4573         -static int reparentChildPages(MemPage *pPage){
  4574         -  int i;
  4575         -  BtShared *pBt = pPage->pBt;
         4599  +static int reparentChildPages(MemPage *pPage, int updatePtrmap){
  4576   4600     int rc = SQLITE_OK;
  4577         -
  4578   4601     assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  4579         -  if( pPage->leaf ) return SQLITE_OK;
         4602  +  if( !pPage->leaf ){
         4603  +    int i;
         4604  +    BtShared *pBt = pPage->pBt;
         4605  +    Pgno iRight = get4byte(&pPage->aData[pPage->hdrOffset+8]);
  4580   4606   
  4581         -  for(i=0; i<pPage->nCell; i++){
  4582         -    u8 *pCell = findCell(pPage, i);
  4583         -    rc = reparentPage(pBt, get4byte(pCell), pPage, i);
  4584         -    if( rc!=SQLITE_OK ) return rc;
         4607  +    for(i=0; i<pPage->nCell; i++){
         4608  +      u8 *pCell = findCell(pPage, i);
         4609  +      rc = reparentPage(pBt, get4byte(pCell), pPage, i, updatePtrmap);
         4610  +      if( rc!=SQLITE_OK ) return rc;
         4611  +    }
         4612  +    rc = reparentPage(pBt, iRight, pPage, i, updatePtrmap);
         4613  +    pPage->idxShift = 0;
  4585   4614     }
  4586         -  rc = reparentPage(pBt, get4byte(&pPage->aData[pPage->hdrOffset+8]), 
  4587         -                    pPage, i);
  4588         -  pPage->idxShift = 0;
  4589   4615     return rc;
  4590   4616   }
  4591   4617   
  4592   4618   /*
  4593   4619   ** Remove the i-th cell from pPage.  This routine effects pPage only.
  4594   4620   ** The cell content is not freed or deallocated.  It is assumed that
  4595   4621   ** the cell content has been copied someplace else.  This routine just
................................................................................
  5346   5372       assert( j<nMaxCells );
  5347   5373       assert( pNew->pgno==pgnoNew[i] );
  5348   5374       zeroPage(pNew, pageFlags);
  5349   5375       assemblePage(pNew, cntNew[i]-j, &apCell[j], &szCell[j]);
  5350   5376       assert( pNew->nCell>0 || (nNew==1 && cntNew[0]==0) );
  5351   5377       assert( pNew->nOverflow==0 );
  5352   5378   
  5353         -#ifndef SQLITE_OMIT_AUTOVACUUM
  5354   5379       /* If this is an auto-vacuum database, update the pointer map entries
  5355   5380       ** that point to the siblings that were rearranged. These can be: left
  5356   5381       ** children of cells, the right-child of the page, or overflow pages
  5357   5382       ** pointed to by cells.
  5358   5383       */
         5384  +#ifndef SQLITE_OMIT_AUTOVACUUM
  5359   5385       if( pBt->autoVacuum ){
  5360   5386         for(k=j; k<cntNew[i]; k++){
  5361   5387           assert( k<nMaxCells );
  5362   5388           if( aFrom[k]==0xFF || apCopy[aFrom[k]]->pgno!=pNew->pgno ){
  5363   5389             rc = ptrmapPutOvfl(pNew, k-j);
         5390  +          if( rc==SQLITE_OK && leafCorrection==0 ){
         5391  +            rc = ptrmapPut(pBt, get4byte(apCell[k]), PTRMAP_BTREE, pNew->pgno);
         5392  +          }
  5364   5393             if( rc!=SQLITE_OK ){
  5365   5394               goto balance_cleanup;
  5366   5395             }
  5367   5396           }
  5368   5397         }
  5369   5398       }
  5370   5399   #endif
................................................................................
  5381   5410   
  5382   5411         assert( j<nMaxCells );
  5383   5412         pCell = apCell[j];
  5384   5413         sz = szCell[j] + leafCorrection;
  5385   5414         pTemp = &aSpace2[iSpace2];
  5386   5415         if( !pNew->leaf ){
  5387   5416           memcpy(&pNew->aData[8], pCell, 4);
         5417  +#ifndef SQLITE_OMIT_AUTOVACUUM
         5418  +        if( pBt->autoVacuum 
         5419  +         && (aFrom[j]==0xFF || apCopy[aFrom[j]]->pgno!=pNew->pgno)
         5420  +        ){
         5421  +          rc = ptrmapPut(pBt, get4byte(pCell), PTRMAP_BTREE, pNew->pgno);
         5422  +          if( rc!=SQLITE_OK ){
         5423  +            goto balance_cleanup;
         5424  +          }
         5425  +        }
         5426  +#endif
  5388   5427         }else if( leafData ){
  5389   5428           /* If the tree is a leaf-data tree, and the siblings are leaves, 
  5390   5429           ** then there is no divider cell in apCell[]. Instead, the divider 
  5391   5430           ** cell consists of the integer key for the right-most cell of 
  5392   5431           ** the sibling-page assembled above only.
  5393   5432           */
  5394   5433           CellInfo info;
................................................................................
  5432   5471             goto balance_cleanup;
  5433   5472           }
  5434   5473         }
  5435   5474   #endif
  5436   5475         j++;
  5437   5476         nxDiv++;
  5438   5477       }
         5478  +
         5479  +#ifndef SQLITE_OMIT_AUTOVACUUM
         5480  +    /* Set the pointer-map entry for the new sibling page. */
         5481  +    if( pBt->autoVacuum ){
         5482  +      rc = ptrmapPut(pBt, pNew->pgno, PTRMAP_BTREE, pParent->pgno);
         5483  +      if( rc!=SQLITE_OK ){
         5484  +        goto balance_cleanup;
         5485  +      }
         5486  +    }
         5487  +#endif
  5439   5488     }
  5440   5489     assert( j==nCell );
  5441   5490     assert( nOld>0 );
  5442   5491     assert( nNew>0 );
  5443   5492     if( (pageFlags & PTF_LEAF)==0 ){
  5444         -    memcpy(&apNew[nNew-1]->aData[8], &apCopy[nOld-1]->aData[8], 4);
         5493  +    u8 *zChild = &apCopy[nOld-1]->aData[8];
         5494  +    memcpy(&apNew[nNew-1]->aData[8], zChild, 4);
         5495  +#ifndef SQLITE_OMIT_AUTOVACUUM
         5496  +    if( pBt->autoVacuum ){
         5497  +      rc = ptrmapPut(pBt, get4byte(zChild), PTRMAP_BTREE, apNew[nNew-1]->pgno);
         5498  +      if( rc!=SQLITE_OK ){
         5499  +        goto balance_cleanup;
         5500  +      }
         5501  +    }
         5502  +#endif
  5445   5503     }
  5446   5504     if( nxDiv==pParent->nCell+pParent->nOverflow ){
  5447   5505       /* Right-most sibling is the right-most child of pParent */
  5448   5506       put4byte(&pParent->aData[pParent->hdrOffset+8], pgnoNew[nNew-1]);
  5449   5507     }else{
  5450   5508       /* Right-most sibling is the left child of the first entry in pParent
  5451   5509       ** past the right-most divider entry */
................................................................................
  5452   5510       put4byte(findOverflowCell(pParent, nxDiv), pgnoNew[nNew-1]);
  5453   5511     }
  5454   5512   
  5455   5513     /*
  5456   5514     ** Reparent children of all cells.
  5457   5515     */
  5458   5516     for(i=0; i<nNew; i++){
  5459         -    rc = reparentChildPages(apNew[i]);
         5517  +    rc = reparentChildPages(apNew[i], 0);
  5460   5518       if( rc!=SQLITE_OK ) goto balance_cleanup;
  5461   5519     }
  5462         -  rc = reparentChildPages(pParent);
         5520  +  rc = reparentChildPages(pParent, 0);
  5463   5521     if( rc!=SQLITE_OK ) goto balance_cleanup;
  5464   5522   
  5465   5523     /*
  5466   5524     ** Balance the parent page.  Note that the current page (pPage) might
  5467   5525     ** have been added to the freelist so it might no longer be initialized.
  5468   5526     ** But the parent page will always be initialized.
  5469   5527     */
................................................................................
  5563   5621         pPage->pParent = 0;
  5564   5622         rc = sqlite3BtreeInitPage(pPage, 0);
  5565   5623         assert( rc==SQLITE_OK );
  5566   5624         freePage(pChild);
  5567   5625         TRACE(("BALANCE: transfer child %d into root %d\n",
  5568   5626                 pChild->pgno, pPage->pgno));
  5569   5627       }
  5570         -    rc = reparentChildPages(pPage);
         5628  +    rc = reparentChildPages(pPage, 1);
  5571   5629       assert( pPage->nOverflow==0 );
  5572   5630   #ifndef SQLITE_OMIT_AUTOVACUUM
  5573   5631       if( pBt->autoVacuum ){
  5574   5632         int i;
  5575   5633         for(i=0; i<pPage->nCell; i++){ 
  5576   5634           rc = ptrmapPutOvfl(pPage, i);
  5577   5635           if( rc!=SQLITE_OK ){
................................................................................
  5641   5699       if( rc ) goto balancedeeper_out;
  5642   5700       for(i=0; i<pChild->nCell; i++){
  5643   5701         rc = ptrmapPutOvfl(pChild, i);
  5644   5702         if( rc!=SQLITE_OK ){
  5645   5703           goto balancedeeper_out;
  5646   5704         }
  5647   5705       }
         5706  +    rc = reparentChildPages(pChild, 1);
  5648   5707     }
  5649   5708   #endif
  5650         -  rc = balance_nonroot(pChild);
         5709  +  if( rc==SQLITE_OK ){
         5710  +    rc = balance_nonroot(pChild);
         5711  +  }
  5651   5712   
  5652   5713   balancedeeper_out:
  5653   5714     releasePage(pChild);
  5654   5715     return rc;
  5655   5716   }
  5656   5717   
  5657   5718   /*