/ Check-in [b7d953e1]
Login

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 | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: b7d953e1195897de4869ec241a65e8a3d1320efb
User & Date: danielk1977 2004-11-03 03:01:17
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: bd50fbb5 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: b7d953e1 user: danielk1977 tags: trunk
2004-11-02
18:15
Fix a problem in the pragma.test script. (CVS 2041) check-in: a2c9c45c user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to src/btree.c.

5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
....
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
....
3170
3171
3172
3173
3174
3175
3176
3177
3178
3179
3180
3181
3182
3183
3184
....
3230
3231
3232
3233
3234
3235
3236
3237
3238
3239
3240
3241
3242
3243
3244
....
3287
3288
3289
3290
3291
3292
3293
















3294
3295
3296
3297
3298
3299
3300
....
3756
3757
3758
3759
3760
3761
3762
3763

3764
3765
3766
3767
3768
3769
3770
....
4063
4064
4065
4066
4067
4068
4069
4070

4071
4072
4073
4074
4075
4076
4077
....
4143
4144
4145
4146
4147
4148
4149
4150

4151
4152
4153
4154
4155
4156
4157
** 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.199 2004/11/02 18:05:09 drh 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.
................................................................................
  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.
  */
#ifndef NDEBUG
  if( nRef!=*sqlite3pager_stats(pPager) ){
    sqlite3pager_refdump(pPager);
  }
#endif
  assert( nRef==*sqlite3pager_stats(pPager) );
  if( rc!=SQLITE_OK ){
    sqlite3pager_rollback(pPager);
  }
  return rc;
}
#endif
................................................................................
    ** 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.iOverflow ){
        Pgno pgnoOvfl = get4byte(&pCell[info.iOverflow]);
        rc = ptrmapPut(pBt, pgnoOvfl, PTRMAP_OVERFLOW1, pPage->pgno);
        if( rc!=SQLITE_OK ) return rc;
      }
    }
#endif
  }
................................................................................
** 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 void 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[] */
................................................................................
      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(
................................................................................
        pTemp = 0;
      }else{
        pCell -= 4;
        pTemp = &aSpace[iSpace];
        iSpace += sz;
        assert( iSpace<=pBt->psAligned*5 );
      }
      insertCell(pParent, nxDiv, pCell, sz, pTemp);

      put4byte(findOverflowCell(pParent,nxDiv), pNew->pgno);
      j++;
      nxDiv++;
    }
  }
  assert( j==nCell );
  if( (pageFlags & PTF_LEAF)==0 ){
................................................................................
  }else if( loc<0 && pPage->nCell>0 ){
    assert( pPage->leaf );
    pCur->idx++;
    pCur->info.nSize = 0;
  }else{
    assert( pPage->leaf );
  }
  insertCell(pPage, pCur->idx, newCell, szNew, 0);

  rc = balance(pPage);
  /* sqlite3BtreePageDump(pCur->pBt, pCur->pgnoRoot, 1); */
  /* fflush(stdout); */
  if( rc==SQLITE_OK ){
    moveToRoot(pCur);
  }
end_insert:
................................................................................
       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;
    insertCell(pPage, pCur->idx, pNext-4, szNext+4, tempCell);

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







|







 







<
<
<
<
<







 







|







 







|







 







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







 







|
>







 







|
>







 







|
>







5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
....
1749
1750
1751
1752
1753
1754
1755





1756
1757
1758
1759
1760
1761
1762
....
3165
3166
3167
3168
3169
3170
3171
3172
3173
3174
3175
3176
3177
3178
3179
....
3225
3226
3227
3228
3229
3230
3231
3232
3233
3234
3235
3236
3237
3238
3239
....
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
....
3767
3768
3769
3770
3771
3772
3773
3774
3775
3776
3777
3778
3779
3780
3781
3782
....
4075
4076
4077
4078
4079
4080
4081
4082
4083
4084
4085
4086
4087
4088
4089
4090
....
4156
4157
4158
4159
4160
4161
4162
4163
4164
4165
4166
4167
4168
4169
4170
4171
** 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.
................................................................................
  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
................................................................................
    ** 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
  }
................................................................................
** 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[] */
................................................................................
      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(
................................................................................
        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 ){
................................................................................
  }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:
................................................................................
       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.

7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
..
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
..
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#    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.2 2004/11/02 14:40:32 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]
  }

# puts "File has [file_pages] pages"

  do_test autovacuum-1.$tn.1 {
    execsql {
      pragma integrity_check
    }
  } {ok}

  foreach delete $delete_order {
# if {$delete==6} { set btree_trace 1 ; breakpoint }
    do_test autovacuum-1.$tn.($delete).1 {
      execsql "
        DELETE FROM av1 WHERE oid IN ([join $delete ,])
      "
    } {}
set btree_trace 0

    do_test autovacuum-1.$tn.($delete).2 {
      execsql {
        pragma integrity_check
      }
    } {ok}

................................................................................
      set ::tbl_data [lreplace $::tbl_data $idx $idx]
    }
    do_test autovacuum-1.$tn.($delete).3 {
      execsql {
        select a from av1
      }
    } $::tbl_data
# if {$::nErr>0} finish_test
  }

  do_test autovacuum-1.$tn.3 {
    file_pages
  } {3}
}

finish_test








|







 







|










<



<












<
<







<





<







 







<




|




7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
..
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
..
78
79
80
81
82
83
84

85
86
87
88
89
90
91
92
93
#    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}

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