/ Check-in [9992b1ae]
Login

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 Unified Diffs Show Whitespace Changes Patch

Changes to src/btree.c.

5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
....
4522
4523
4524
4525
4526
4527
4528




4529
4530






4531
4532
4533
4534
4535
4536
4537
....
4547
4548
4549
4550
4551
4552
4553
4554
4555
4556













4557
4558
4559
4560
4561
4562
4563
....
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
....
5346
5347
5348
5349
5350
5351
5352
5353
5354
5355
5356
5357
5358

5359
5360
5361
5362
5363



5364
5365
5366
5367
5368
5369
5370
....
5381
5382
5383
5384
5385
5386
5387










5388
5389
5390
5391
5392
5393
5394
....
5432
5433
5434
5435
5436
5437
5438










5439
5440
5441
5442
5443

5444








5445
5446
5447
5448
5449
5450
5451
....
5452
5453
5454
5455
5456
5457
5458
5459
5460
5461
5462
5463
5464
5465
5466
5467
5468
5469
....
5563
5564
5565
5566
5567
5568
5569
5570
5571
5572
5573
5574
5575
5576
5577
....
5641
5642
5643
5644
5645
5646
5647

5648
5649

5650

5651
5652
5653
5654
5655
5656
5657
** 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.489 2008/07/18 17:16:26 drh 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"

................................................................................
  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.




*/
static int reparentPage(BtShared *pBt, Pgno pgno, MemPage *pNewParent, int idx){






  MemPage *pThis;
  DbPage *pDbPage;

  assert( sqlite3_mutex_held(pBt->mutex) );
  assert( pNewParent!=0 );
  if( pgno==0 ) return SQLITE_OK;
  assert( pBt->pPager!=0 );
................................................................................
      }
      pThis->idxParent = idx;
    }
    sqlite3PagerUnref(pDbPage);
  }

#ifndef SQLITE_OMIT_AUTOVACUUM
  if( pBt->autoVacuum ){
    return ptrmapPut(pBt, pgno, PTRMAP_BTREE, pNewParent->pgno);
  }













#endif
  return SQLITE_OK;
}



/*
................................................................................
** 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.



*/
static int reparentChildPages(MemPage *pPage){
  int i;
  BtShared *pBt = pPage->pBt;
  int rc = SQLITE_OK;

  assert( sqlite3_mutex_held(pPage->pBt->mutex) );
  if( pPage->leaf ) return SQLITE_OK;




  for(i=0; i<pPage->nCell; i++){
    u8 *pCell = findCell(pPage, i);
    rc = reparentPage(pBt, get4byte(pCell), pPage, i);
    if( rc!=SQLITE_OK ) return rc;
  }
  rc = reparentPage(pBt, get4byte(&pPage->aData[pPage->hdrOffset+8]), 
                    pPage, i);
  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
................................................................................
    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 );

#ifndef SQLITE_OMIT_AUTOVACUUM
    /* 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.
    */

    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 ){
            goto balance_cleanup;
          }
        }
      }
    }
#endif
................................................................................

      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;
................................................................................
          goto balance_cleanup;
        }
      }
#endif
      j++;
      nxDiv++;
    }










  }
  assert( j==nCell );
  assert( nOld>0 );
  assert( nNew>0 );
  if( (pageFlags & PTF_LEAF)==0 ){

    memcpy(&apNew[nNew-1]->aData[8], &apCopy[nOld-1]->aData[8], 4);








  }
  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]);
    if( rc!=SQLITE_OK ) goto balance_cleanup;
  }
  rc = reparentChildPages(pParent);
  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.
  */
................................................................................
      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);
    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 ){
................................................................................
    if( rc ) goto balancedeeper_out;
    for(i=0; i<pChild->nCell; i++){
      rc = ptrmapPutOvfl(pChild, i);
      if( rc!=SQLITE_OK ){
        goto balancedeeper_out;
      }
    }

  }
#endif

  rc = balance_nonroot(pChild);


balancedeeper_out:
  releasePage(pChild);
  return rc;
}

/*







|







 







>
>
>
>

|
>
>
>
>
>
>







 







|


>
>
>
>
>
>
>
>
>
>
>
>
>







 







>
>
>

|
<
<

<

|
>
>
>



|
|
|
|
<
|
>







 







<





>





>
>
>







 







>
>
>
>
>
>
>
>
>
>







 







>
>
>
>
>
>
>
>
>
>





>
|
>
>
>
>
>
>
>
>







 







|


|







 







|







 







>


>
|
>







5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
....
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
....
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
....
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
....
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
....
5410
5411
5412
5413
5414
5415
5416
5417
5418
5419
5420
5421
5422
5423
5424
5425
5426
5427
5428
5429
5430
5431
5432
5433
....
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
....
5621
5622
5623
5624
5625
5626
5627
5628
5629
5630
5631
5632
5633
5634
5635
....
5699
5700
5701
5702
5703
5704
5705
5706
5707
5708
5709
5710
5711
5712
5713
5714
5715
5716
5717
5718
** 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"

................................................................................
  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 );
................................................................................
      }
      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;
}



/*
................................................................................
** 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
................................................................................
    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
................................................................................

      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;
................................................................................
          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.
  */
................................................................................
      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 ){
................................................................................
    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;
}

/*