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

Overview
Comment:Fix another bug in b-tree rebalancing.
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: f4df828793bf8266c3887ff17a9993210ebb3aa4
User & Date: dan 2013-10-08 17:38:49.258
Context
2013-10-08
20:37
Add hooks to run the "lsmtest" tree-structure tests and performance comparisons on the btree module. check-in: 8140c0abef user: dan tags: trunk
17:38
Fix another bug in b-tree rebalancing. check-in: f4df828793 user: dan tags: trunk
2013-10-07
20:43
Further progress on b-tree module. check-in: 51c2c9358d user: dan tags: trunk
Changes
Unified Diff Ignore Whitespace Patch
Changes to src/bt_main.c.
︙︙
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316

      fprintf(f, "%02X", (int)pCell[j]);
    }
    if( btFlags(aData, nData) & BT_PGFLAGS_INTERNAL ){
      fprintf(f, "  child=%d ", (int)btGetU32(&pCell[j]));
    }
    fprintf(f, "\n");
  }


}

static int printPgToStderr(BtPage *pPg){
  printPage(stderr, sqlite4BtPagePgno(pPg), sqlite4BtPageData(pPg), 1024);
  return 0;
}
#endif








<
<








301
302
303
304
305
306
307


308
309
310
311
312
313
314

      fprintf(f, "%02X", (int)pCell[j]);
    }
    if( btFlags(aData, nData) & BT_PGFLAGS_INTERNAL ){
      fprintf(f, "  child=%d ", (int)btGetU32(&pCell[j]));
    }
    fprintf(f, "\n");
  }


}

static int printPgToStderr(BtPage *pPg){
  printPage(stderr, sqlite4BtPagePgno(pPg), sqlite4BtPageData(pPg), 1024);
  return 0;
}
#endif
︙︙
1287
1288
1289
1290
1291
1292
1293

1294
1295
1296
1297
1298
1299
1300

#endif

 rebalance_out:
  for(iPg=0; iPg<array_size(ctx.apPg); iPg++){
    sqlite4BtPageRelease(ctx.apPg[iPg]);
  }
  btFreeBuffer(pDb, ctx.pTmp);

  return rc;
}

static int btExtendTree(bt_cursor *pCsr){
  bt_db * const pDb = pCsr->pDb;
  const int pgsz = sqlite4BtPagerPagesize(pDb->pPager);
  int rc;                         /* Return code */








>








1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299

#endif

 rebalance_out:
  for(iPg=0; iPg<array_size(ctx.apPg); iPg++){
    sqlite4BtPageRelease(ctx.apPg[iPg]);
  }
  btFreeBuffer(pDb, ctx.pTmp);
  sqlite4_free(pDb->pEnv, ctx.anCellSz);
  return rc;
}

static int btExtendTree(bt_cursor *pCsr){
  bt_db * const pDb = pCsr->pDb;
  const int pgsz = sqlite4BtPagerPagesize(pDb->pPager);
  int rc;                         /* Return code */
︙︙
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422

    rc = sqlite4BtPageWrite(pLeaf);
    if( rc==SQLITE4_OK ){
      aData = sqlite4BtPageData(pLeaf);

      /* Make space within the cell pointer array */
      if( iCell!=nCell ){
        u8 *aFrom = btCellPtrFind(aData, pgsz, nCell-1);
        u8 *aTo = btCellPtrFind(aData, pgsz, nCell);
        memmove(aTo, aFrom, (nCell-iCell) * 2);
      }

      for(i=0; i<nKV; i++){
        /* Write the cell pointer */
        btPutU16(btCellPtrFind(aData, pgsz, iCell+i), iWrite);
      








|








1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421

    rc = sqlite4BtPageWrite(pLeaf);
    if( rc==SQLITE4_OK ){
      aData = sqlite4BtPageData(pLeaf);

      /* Make space within the cell pointer array */
      if( iCell!=nCell ){
        u8 *aFrom = btCellPtrFind(aData, pgsz, nCell-1);
        u8 *aTo = btCellPtrFind(aData, pgsz, nCell-1+nKV);
        memmove(aTo, aFrom, (nCell-iCell) * 2);
      }

      for(i=0; i<nKV; i++){
        /* Write the cell pointer */
        btPutU16(btCellPtrFind(aData, pgsz, iCell+i), iWrite);
︙︙
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532

      }
      if( rc==SQLITE4_OK ){
        u8 *a = sqlite4BtPageData(pChild);
        memcpy(aData, a, pgsz);
        rc = sqlite4BtPageTrim(pChild);
      }
    }
  }else if( nCell==0 || (nFree<(pgsz/3) && bLeaf==0) ){
    rc = btBalance(pCsr, bLeaf, 0, 0);
  }
  return rc;
}

/*
** Insert a new key/value pair or replace an existing one.








|








1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531

      }
      if( rc==SQLITE4_OK ){
        u8 *a = sqlite4BtPageData(pChild);
        memcpy(aData, a, pgsz);
        rc = sqlite4BtPageTrim(pChild);
      }
    }
  }else if( nCell==0 || (nFree>(2*pgsz/3) && bLeaf==0) ){
    rc = btBalance(pCsr, bLeaf, 0, 0);
  }
  return rc;
}

/*
** Insert a new key/value pair or replace an existing one.
︙︙
Changes to test/simple3.test.
︙︙
87
88
89
90
91
92
93

94
95










96










97
98
99
100
101
102
103
104
105
106
107
108
109
110
111

112
113
114


115
116
117
118
119
120
121
122
123


124
125
126
127
128
129
130

131
132
133
134
135
136
137
138


139
140

141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160

  INSERT INTO t1 VALUES(6, $val);
}

do_execsql_test 2.5 { 
  SELECT a, length(b) FROM t1 
} {1 200  3 200  4 200  5 200  6 200}


#--------------------------------------------------------------------------
# Insert many rows in sequence.










#










do_test 3.0 {
  catch { db close }
  forcedelete test.db
  sqlite4 db file:test.db?kv=bt
} {}

do_execsql_test 3.1 {
  CREATE TABLE t1(a PRIMARY KEY, b);
}

for {set i 0} {$i < 100} {incr i} {
  lappend rows $i
  do_execsql_test 3.2.$i {
    INSERT INTO t1 VALUES($i, randomblob(200));
    SELECT a FROM t1 ORDER BY a;

  } $rows
}
set nInitial 100



if 1 {
for {set i 0} {$i < 100} {incr i} {
  if {[set_test_counter errors]} break
  do_test 3.3.$i {
    for {set j 0} {$j < 1000} {incr j} {
      set pk [expr 100 + $i*1000 + $j]
      execsql { INSERT INTO t1 VALUES($pk, randomblob(200)) }
    }


    execsql { SELECT count(*) FROM t1 } 
  } [expr ($i+1)*1000 + 100]
}
set nInitial 100100
}

do_test 3.4 {

  for {set i 0} {$i < $nInitial} {incr i} {
    set res [execsql {SELECT count(*) FROM t1 WHERE a = $i}]
    if {$res!="1"} { error "res = $res for i=$i" }
  }
} {}

#--------------------------------------------------------------------------
# Remove many rows in sequence.


#
for {set i 0} {$i < 100} {incr i} {

if {$i == 5} breakpoint
  do_execsql_test 4.1.$i {
    DELETE FROM t1 WHERE a = $i;
    SELECT count(*) FROM t1;
  } [expr $nInitial - 1 - $i]
  if {[set_test_counter errors]} break
}

for {set i 100} {$i < $nInitial} {incr i 1000} {
  if {[set_test_counter errors]} break
  do_test 4.2.$i {
    for {set j 0} {$j < 1000} {incr j} {
      execsql { DELETE FROM t1 WHERE a = ($i + $j) }
    }
    execsql { SELECT count(*) FROM t1 }
  } [expr $nInitial - $i - 1000]
}

finish_test









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










|
|
|
|
|
>
|
|
|
>
>
|
<
<
<
<
<
<
|
<
>
>
|
|
|
<
|
|
|
>
|
|
|
|
|
|
<
|
>
>
|
<
>
|
|
<
|
|
<
|
|
<
<
<
<
<
<
<
<





87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139






140

141
142
143
144
145

146
147
148
149
150
151
152
153
154
155

156
157
158
159

160
161
162

163
164

165
166








167
168
169
170

  INSERT INTO t1 VALUES(6, $val);
}

do_execsql_test 2.5 { 
  SELECT a, length(b) FROM t1 
} {1 200  3 200  4 200  5 200  6 200}


#-------------------------------------------------------------------------

proc lshuffle {list} {
  set nVal [llength $list]
  for {set i 0} {$i < $nVal} {incr i} {
    set i2 [expr int(rand()*$nVal)]
    set tmp [lindex $list $i]
    lset list $i [lindex $list $i2]
    lset list $i2 $tmp
  }
  return $list
}

proc K {a} { set a }

proc int_list {nVal} {
  set ret [list]
  for {set i 0} {$i < $nVal} {incr i} {
    lappend ret $i
  }
  return $ret
}

do_test 3.0 {
  catch { db close }
  forcedelete test.db
  sqlite4 db file:test.db?kv=bt
} {}

do_execsql_test 3.1 {
  CREATE TABLE t1(a PRIMARY KEY, b);
}

set nRow 100000
set nStep [expr $nRow / 50]

foreach {tn shuffle_proc} {
  1 K
  2 lshuffle
} {
  
  set iRow 0
  foreach k [$shuffle_proc [int_list $nRow]] {
    incr iRow
    






    execsql { INSERT INTO t1 VALUES($k, randomblob(100)); }

    if {0==($iRow % $nStep)} {
      do_execsql_test 4.$tn.1.$iRow {
        SELECT count(*) FROM t1;
      } $iRow
    }

  }
  
  do_test 4.$tn.2 {
    set nInitial [db one {SELECT count(*) FROM t1}]
    for {set i 0} {$i < $nRow} {incr i} {
      set res [execsql {SELECT count(*) FROM t1 WHERE a = $i}]
      if {$res!="1"} { error "res = $res for i=$i" }
    }
  } {}
  

  set iRow 0
  foreach k [$shuffle_proc [int_list $nRow]] {
    incr iRow
    

    execsql { DELETE FROM t1 WHERE a = $k }
    if {0==($iRow % $nStep)} {
      do_execsql_test 4.$tn.3.$iRow {

        SELECT count(*) FROM t1;
      } [expr $nRow - $iRow]

    }
  }








}

finish_test