SQLite

Check-in [83c064cae4]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Fix a recently introduced problem with deleting entries from index tables. (CVS 5754)
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 83c064cae481ca95b7107e22e98fc599fe85a2da
User & Date: danielk1977 2008-09-30 09:31:45.000
Context
2008-09-30
14:06
Change leading tabs into spaces. (CVS 5755) (check-in: 4e536463c1 user: drh tags: trunk)
09:31
Fix a recently introduced problem with deleting entries from index tables. (CVS 5754) (check-in: 83c064cae4 user: danielk1977 tags: trunk)
04:20
Misc clean up. Wrapped a CE only variable in if-defs. Changed to only provide cache hint for CE builds (as this prevents CE from compressing the file.) Performance testing on XP and Vista showed caching hint had little effect when the DB size was much smaller than the O/S disk cache size, and provided only marginal benefit when the DB size was much larger than the cache. On Vista, overall system performance was hurt for very large DBs. Ticket #3387. (CVS 5753) (check-in: 15dd0169a4 user: shane tags: trunk)
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/btree.c.
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.520 2008/09/29 16:41:32 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"












|







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.521 2008/09/30 09:31:45 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"

5879
5880
5881
5882
5883
5884
5885
5886
5887
5888
5889
5890
5891
5892
5893
5894

5895
5896
5897
5898
5899

5900
5901
5902
5903
5904
5905
5906
5907
5908
5909
5910
5911
5912
5913
5914



















5915
5916
5917
5918



























5919








5920
5921
5922
5923
5924
5925
5926
5927
    ** do something we will leave a hole on an internal page.
    ** We have to fill the hole by moving in a cell from a leaf.  The
    ** next Cell after the one to be deleted is guaranteed to exist and
    ** to be a leaf so we can use it.
    */
    BtCursor leafCur;
    MemPage *pLeafPage;
    int iLeafIdx;

    unsigned char *pNext;
    int notUsed;
    unsigned char *tempCell = 0;
    assert( !pPage->intKey );
    sqlite3BtreeGetTempCursor(pCur, &leafCur);
    rc = sqlite3BtreeNext(&leafCur, &notUsed);
    if( rc==SQLITE_OK ){

      pLeafPage = leafCur.apPage[leafCur.iPage];
      iLeafIdx = leafCur.aiIdx[leafCur.iPage];
      rc = sqlite3PagerWrite(pLeafPage->pDbPage);
    }
    if( rc==SQLITE_OK ){

      u16 szNext;
      TRACE(("DELETE: table=%d delete internal from %d replace from leaf %d\n",
         pCur->pgnoRoot, pPage->pgno, pLeafPage->pgno));
      dropCell(pPage, idx, cellSizePtr(pPage, pCell));
      pNext = findCell(pLeafPage, iLeafIdx);
      szNext = cellSizePtr(pLeafPage, pNext);
      assert( MX_CELL_SIZE(pBt)>=szNext+4 );
      allocateTempSpace(pBt);
      tempCell = pBt->pTmpSpace;
      if( tempCell==0 ){
        rc = SQLITE_NOMEM;
      }
      if( rc==SQLITE_OK ){
        rc = insertCell(pPage, idx, pNext-4, szNext+4, tempCell, 0);
      }



















      if( rc==SQLITE_OK ){
        put4byte(findOverflowCell(pPage, idx), pgnoChild);
        rc = balance(pCur, 0);
      }



























      if( rc==SQLITE_OK ){








        dropCell(pLeafPage, iLeafIdx, szNext);
        rc = balance(&leafCur, 0);
      }
    }
    sqlite3BtreeReleaseTempCursor(&leafCur);
  }else{
    TRACE(("DELETE: table=%d delete from leaf %d\n",
       pCur->pgnoRoot, pPage->pgno));







<








>

<



>




|










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




>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
|
>
>
>
>
>
>
>
>
|







5879
5880
5881
5882
5883
5884
5885

5886
5887
5888
5889
5890
5891
5892
5893
5894
5895

5896
5897
5898
5899
5900
5901
5902
5903
5904
5905
5906
5907
5908
5909
5910
5911
5912
5913
5914
5915
5916
5917
5918
5919
5920
5921
5922
5923
5924
5925
5926
5927
5928
5929
5930
5931
5932
5933
5934
5935
5936
5937
5938
5939
5940
5941
5942
5943
5944
5945
5946
5947
5948
5949
5950
5951
5952
5953
5954
5955
5956
5957
5958
5959
5960
5961
5962
5963
5964
5965
5966
5967
5968
5969
5970
5971
5972
5973
5974
5975
5976
5977
5978
5979
5980
5981
    ** do something we will leave a hole on an internal page.
    ** We have to fill the hole by moving in a cell from a leaf.  The
    ** next Cell after the one to be deleted is guaranteed to exist and
    ** to be a leaf so we can use it.
    */
    BtCursor leafCur;
    MemPage *pLeafPage;


    unsigned char *pNext;
    int notUsed;
    unsigned char *tempCell = 0;
    assert( !pPage->intKey );
    sqlite3BtreeGetTempCursor(pCur, &leafCur);
    rc = sqlite3BtreeNext(&leafCur, &notUsed);
    if( rc==SQLITE_OK ){
      assert( leafCur.aiIdx[leafCur.iPage]==0 );
      pLeafPage = leafCur.apPage[leafCur.iPage];

      rc = sqlite3PagerWrite(pLeafPage->pDbPage);
    }
    if( rc==SQLITE_OK ){
      int leafCursorInvalid = 0;
      u16 szNext;
      TRACE(("DELETE: table=%d delete internal from %d replace from leaf %d\n",
         pCur->pgnoRoot, pPage->pgno, pLeafPage->pgno));
      dropCell(pPage, idx, cellSizePtr(pPage, pCell));
      pNext = findCell(pLeafPage, 0);
      szNext = cellSizePtr(pLeafPage, pNext);
      assert( MX_CELL_SIZE(pBt)>=szNext+4 );
      allocateTempSpace(pBt);
      tempCell = pBt->pTmpSpace;
      if( tempCell==0 ){
        rc = SQLITE_NOMEM;
      }
      if( rc==SQLITE_OK ){
        rc = insertCell(pPage, idx, pNext-4, szNext+4, tempCell, 0);
      }

      if( (pPage->nOverflow>0 || (pPage->nFree > pBt->usableSize*2/3)) &&
          (pLeafPage->nFree+2+szNext > pBt->usableSize*2/3)
      ){
        /* This branch is taken if the internal node is now either over or
        ** underfull and the leaf node will be underfull after the just cell 
        ** copied to the internal node is deleted from it. This is a special
        ** case because the call to balance() to correct the internal node
        ** may change the tree structure and invalidate the contents of
        ** the leafCur.apPage[] and leafCur.aiIdx[] arrays, which will be
        ** used by the balance() required to correct the underfull leaf
        ** node.
        **
        ** The formula used in the expression above are based on facets of
        ** the SQLite file-format that do not change over time.
        */
        leafCursorInvalid = 1;
      }        

      if( rc==SQLITE_OK ){
        put4byte(findOverflowCell(pPage, idx), pgnoChild);
        rc = balance(pCur, 0);
      }

      if( rc==SQLITE_OK && leafCursorInvalid ){
        /* The leaf-node is now underfull and so the tree needs to be 
        ** rebalanced. However, the balance() operation on the internal
        ** node above may have modified the structure of the B-Tree and
        ** so the current contents of leafCur.apPage[] and leafCur.aiIdx[]
        ** may not be trusted.
        **
        ** It is not possible to copy the ancestry from pCur, as the same
        ** balance() call has invalidated the pCur->apPage[] and aiIdx[]
        ** arrays. 
	**
	** The call to saveCursorPosition() below internally saves the 
	** key that leafCur is currently pointing to. Currently, there
	** are two copies of that key in the tree - one here on the leaf
	** page and one on some internal node in the tree. The copy on
	** the leaf node is always the next key in tree-order after the 
	** copy on the internal node. So, the call to sqlite3BtreeNext()
	** calls restoreCursorPosition() to point the cursor to the copy
	** stored on the internal node, then advances to the next entry,
	** which happens to be the copy of the key on the internal node.
	** Net effect: leafCur is pointing back where
        */
      #ifndef NDEBUG
        Pgno leafPgno = pLeafPage->pgno;
      #endif
        rc = saveCursorPosition(&leafCur);
        if( rc==SQLITE_OK ){
          rc = sqlite3BtreeNext(&leafCur, &notUsed);
        }
        pLeafPage = leafCur.apPage[leafCur.iPage];
        assert( pLeafPage->pgno==leafPgno );
        assert( leafCur.aiIdx[leafCur.iPage]==0 );
      }

      if( rc==SQLITE_OK ){
        dropCell(pLeafPage, 0, szNext);
        rc = balance(&leafCur, 0);
      }
    }
    sqlite3BtreeReleaseTempCursor(&leafCur);
  }else{
    TRACE(("DELETE: table=%d delete from leaf %d\n",
       pCur->pgnoRoot, pPage->pgno));
7022
7023
7024
7025
7026
7027
7028
7029
7030
7031
7032
7033
7034
7035
7036
            nCopy = nToPageSize;
          }else{
            zTo += (((iFrom-1)*nFromPageSize) - (i-1)*nToPageSize);
            nCopy = nFromPageSize;
          }

          memcpy(zTo, zFrom, nCopy);
	  sqlite3PagerUnref(pFromPage);
        }
      }

      if( pToPage ){
        MemPage *p = (MemPage *)sqlite3PagerGetExtra(pToPage);
        p->isInit = 0;
        sqlite3PagerUnref(pToPage);







|







7076
7077
7078
7079
7080
7081
7082
7083
7084
7085
7086
7087
7088
7089
7090
            nCopy = nToPageSize;
          }else{
            zTo += (((iFrom-1)*nFromPageSize) - (i-1)*nToPageSize);
            nCopy = nFromPageSize;
          }

          memcpy(zTo, zFrom, nCopy);
          sqlite3PagerUnref(pFromPage);
        }
      }

      if( pToPage ){
        MemPage *p = (MemPage *)sqlite3PagerGetExtra(pToPage);
        p->isInit = 0;
        sqlite3PagerUnref(pToPage);