SQLite

Check-in [e6685af815]
Login

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

Overview
Comment:Add 3-byte and 6-byte integer serial types. This makes databases smaller and faster. Should we go ahead and add 5- and 7-byte integer types too? (CVS 1499)
Downloads: Tarball | ZIP archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: e6685af815c4c0c7f09bb097a59a121862b865cf
User & Date: drh 2004-05-30 21:14:59.000
Context
2004-05-31
08:26
Replace OP_Begin, OP_Commit and OP_Rollback with OP_AutoCommit. (CVS 1500) (check-in: b8ed812c92 user: danielk1977 tags: trunk)
2004-05-30
21:14
Add 3-byte and 6-byte integer serial types. This makes databases smaller and faster. Should we go ahead and add 5- and 7-byte integer types too? (CVS 1499) (check-in: e6685af815 user: drh tags: trunk)
20:46
Various speed enhancements. (CVS 1498) (check-in: a0db15bba6 user: drh tags: trunk)
Changes
Side-by-Side Diff Ignore Whitespace Patch
Changes to src/vdbe.c.
39
40
41
42
43
44
45
46

47
48
49
50
51
52
53
39
40
41
42
43
44
45

46
47
48
49
50
51
52
53







-
+







**
** Various scripts scan this source file in order to generate HTML
** documentation, headers files, or other derived files.  The formatting
** of the code in this file is, therefore, important.  See other comments
** in this file for details.  If in doubt, do not deviate from existing
** commenting and indentation practices when changing or adding code.
**
** $Id: vdbe.c,v 1.349 2004/05/30 20:46:09 drh Exp $
** $Id: vdbe.c,v 1.350 2004/05/30 21:14:59 drh Exp $
*/
#include "sqliteInt.h"
#include "os.h"
#include <ctype.h>
#include "vdbeInt.h"

/*
3710
3711
3712
3713
3714
3715
3716
3717

3718
3719
3720
3721
3722
3723
3724
3710
3711
3712
3713
3714
3715
3716

3717
3718
3719
3720
3721
3722
3723
3724







-
+







  assert( pTos>=p->aStack );
  assert( pTos->flags & MEM_Blob );
  z = pTos->z;
  n = pTos->n;
  k = sqlite3GetVarint32(z, &serial_type);
  for(; k<n && i>0; i--){
    k += sqlite3GetVarint32(&z[k], &serial_type);
    if( serial_type==6 ){   /* Serial type 6 is a NULL */
    if( serial_type==0 ){   /* Serial type 0 is a NULL */
      pc = pOp->p2-1;
      break;
    }
  }
  Release(pTos);
  pTos--;
  break;
Changes to src/vdbeaux.c.
1113
1114
1115
1116
1117
1118
1119
1120

1121
1122
1123
1124
1125
1126
1127






1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140

1141
1142
1143
1144
1145
1146

1147
1148



1149
1150
1151

1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169

1170
1171
1172

1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189

1190
1191
1192
1193
1194

1195
1196
1197

1198
1199
1200
1201
1202
1203
1204
1113
1114
1115
1116
1117
1118
1119

1120
1121
1122





1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140

1141
1142
1143
1144
1145
1146
1147
1148


1149
1150
1151
1152
1153

1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170


1171
1172
1173

1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187


1188

1189
1190
1191
1192
1193

1194
1195
1196

1197
1198
1199
1200
1201
1202
1203
1204







-
+


-
-
-
-
-
+
+
+
+
+
+












-
+






+
-
-
+
+
+


-
+
















-
-
+


-
+













-
-

-
+




-
+


-
+







** the end. Hence these functions allow the caller to handle the
** serial-type and data blob seperately.
**
** The following table describes the various storage classes for data:
**
**   serial type        bytes of data      type
**   --------------     ---------------    ---------------
**      0                     -            Not a type.
**      0                     0            NULL
**      1                     1            signed integer
**      2                     2            signed integer
**      3                     4            signed integer
**      4                     8            signed integer
**      5                     8            IEEE float
**      6                     0            NULL
**     7..11                               reserved for expansion
**      3                     3            signed integer
**      4                     4            signed integer
**      5                     6            signed integer
**      6                     8            signed integer
**      7                     8            IEEE float
**     8-11                                reserved for expansion
**    N>=12 and even       (N-12)/2        BLOB
**    N>=13 and odd        (N-13)/2        text
**
*/

/*
** Return the serial-type for the value stored in pMem.
*/
u32 sqlite3VdbeSerialType(Mem *pMem){
  int flags = pMem->flags;

  if( flags&MEM_Null ){
    return 6;
    return 0;
  }
  if( flags&MEM_Int ){
    /* Figure out whether to use 1, 2, 4 or 8 bytes. */
    i64 i = pMem->i;
    if( i>=-127 && i<=127 ) return 1;
    if( i>=-32767 && i<=32767 ) return 2;
    if( i>=-8388607 && i<=8388607 ) return 3;
    if( i>=-2147483647 && i<=2147483647 ) return 3;
    return 4;
    if( i>=-2147483647 && i<=2147483647 ) return 4;
    if( i>=-140737488355328L && i<=140737488355328L ) return 5;
    return 6;
  }
  if( flags&MEM_Real ){
    return 5;
    return 7;
  }
  if( flags&MEM_Str ){
    int n = pMem->n;
    assert( n>=0 );
    return ((n*2) + 13);
  }
  if( flags&MEM_Blob ){
    return (pMem->n*2 + 12);
  }
  return 0;
}

/*
** Return the length of the data corresponding to the supplied serial-type.
*/
int sqlite3VdbeSerialTypeLen(u32 serial_type){
  assert( serial_type!=0 );
  if( serial_type>6 ){
  if( serial_type>=12 ){
    return (serial_type-12)/2;
  }else{
    static u8 aSize[] = { 0, 1, 2, 4, 8, 8, 0, };
    static u8 aSize[] = { 0, 1, 2, 3, 4, 6, 8, 8, 0, 0, 0, 0 };
    return aSize[serial_type];
  }
}

/*
** Write the serialized data blob for the value stored in pMem into 
** buf. It is assumed that the caller has allocated sufficient space.
** Return the number of bytes written.
*/ 
int sqlite3VdbeSerialPut(unsigned char *buf, Mem *pMem){
  u32 serial_type = sqlite3VdbeSerialType(pMem);
  int len;

  assert( serial_type!=0 );
 
  /* NULL */
  if( serial_type==6 ){
  if( serial_type==0 ){
    return 0;
  }
 
  /* Integer and Real */
  if( serial_type<=5 ){
  if( serial_type<=7 ){
    u64 v;
    int i;
    if( serial_type==5 ){
    if( serial_type==7 ){
      v = *(u64*)&pMem->r;
    }else{
      v = *(u64*)&pMem->i;
    }
    len = i = sqlite3VdbeSerialTypeLen(serial_type);
    while( i-- ){
      buf[i] = (v&0xFF);
1221
1222
1223
1224
1225
1226
1227





1228
1229
1230

1231
1232

1233
1234
1235
1236
1237
1238
1239
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233


1234
1235

1236
1237
1238
1239
1240
1241
1242
1243







+
+
+
+
+

-
-
+

-
+







int sqlite3VdbeSerialGet(
  const unsigned char *buf,     /* Buffer to deserialize from */
  u32 serial_type,              /* Serial type to deserialize */
  Mem *pMem                     /* Memory cell to write value into */
){
  int len;

  if( serial_type==0 ){
    /* NULL */
    pMem->flags = MEM_Null;
    return 0;
  }
  len = sqlite3VdbeSerialTypeLen(serial_type);
  assert( serial_type!=0 );
  if( serial_type<=5 ){
  if( serial_type<=7 ){
    /* Integer and Real */
    if( serial_type<=3 ){
    if( serial_type<=4 ){
      /* 32-bit integer type.  This is handled by a special case for
      ** performance reasons. */
      int v = buf[0];
      int n;
      if( v&0x80 ){
        v |= -256;
      }
1249
1250
1251
1252
1253
1254
1255
1256

1257
1258
1259
1260
1261
1262
1263
1264

1265

1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1253
1254
1255
1256
1257
1258
1259

1260
1261
1262
1263
1264
1265
1266
1267

1268
1269
1270
1271
1272
1273
1274
1275
1276
1277





1278
1279
1280
1281
1282
1283
1284







-
+







-
+

+







-
-
-
-
-








      if( buf[0]&0x80 ){
        v = -1;
      }
      for(n=0; n<len; n++){
        v = (v<<8) | buf[n];
      }
      if( serial_type==5 ){
      if( serial_type==7 ){
        pMem->flags = MEM_Real;
        pMem->r = *(double*)&v;
      }else{
        pMem->flags = MEM_Int;
        pMem->i = *(i64*)&v;
      }
    }
  }else if( serial_type>=12 ){
  }else{
    /* String or blob */
    assert( serial_type>=12 );
    pMem->z = (char *)buf;
    pMem->n = len;
    if( serial_type&0x01 ){
      pMem->flags = MEM_Str | MEM_Ephem;
    }else{
      pMem->flags = MEM_Blob | MEM_Ephem;
    }
  }else{
    /* NULL */
    assert( serial_type==6 );
    assert( len==0 );
    pMem->flags = MEM_Null;
  }
  return len;
}

/*
** The following is the comparison function for (non-integer)
** keys in the btrees.  This function returns negative, zero, or
Changes to test/btree.test.
1
2
3
4
5
6
7
8
9
10
11
12
13
14

15
16
17
18
19
20
21
1
2
3
4
5
6
7
8
9
10
11
12
13

14
15
16
17
18
19
20
21













-
+







# 2001 September 15
#
# 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.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script is btree database backend
#
# $Id: btree.test,v 1.25 2004/05/18 15:57:42 drh Exp $
# $Id: btree.test,v 1.26 2004/05/30 21:14:59 drh Exp $


set testdir [file dirname $argv0]
source $testdir/tester.tcl

# Basic functionality.  Open and close a database.
#
516
517
518
519
520
521
522

523
524
525
526
527
528

529
530

531
532
533
534
535
536
537
538


539
540
541
542
543
544

545
546
547

548
549
550
551
552
553










554
555
556
557
558
559

560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578


579
580
581
582
583


584
585
586
587
588
589
590
591



592
593
594
595
596
597
598
516
517
518
519
520
521
522
523
524
525
526
527
528

529
530

531
532
533
534
535
536
537
538

539
540
541
542
543
544
545

546
547
548

549
550
551




552
553
554
555
556
557
558
559
560
561
562
563
564
565
566

567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584


585
586
587
588
589


590
591
592
593
594
595
596
597
598

599
600
601
602
603
604
605
606
607
608







+





-
+

-
+







-
+
+





-
+


-
+


-
-
-
-
+
+
+
+
+
+
+
+
+
+





-
+

















-
-
+
+



-
-
+
+







-
+
+
+







#   2.  Delete every other entry of table 1.
#   3.  Insert a single entry that requires more contiguous
#       space than is available.
#
do_test btree-7.1 {
  btree_begin_transaction $::b1
} {}
if 0 {
catch {unset key}
catch {unset data}
do_test btree-7.2 {
  # Each record will be 10 bytes in size.
  #   + 100 bytes of database header
  #   + 6 bytes of table header
  #   + 8 bytes of table header
  #   + 91*10=910 bytes of cells
  # Totals 1016 bytes.  8 bytes left over
  # Totals 1018 bytes.  6 bytes left over
  # Keys are 1000 through 1090.
  for {set i 1000} {$i<1091} {incr i} {
    set key $i
    set data [format %5d $i]
    btree_insert $::c1 $key $data
  }
  lrange [btree_cursor_info $::c1] 4 5
} {8 1}
} {6 0}
#btree_tree_dump $::b1 1
do_test btree-7.3 {
  for {set i 1001} {$i<1091} {incr i 2} {
    btree_move_to $::c1 $i
    btree_delete $::c1
  }
  # Freed 45 blocks.  Total freespace is 458
  # Freed 45 blocks.  Total freespace is 456
  # Keys remaining are even numbers between 1000 and 1090, inclusive
  lrange [btree_cursor_info $::c1] 4 5
} {458 46}
} {456 45}
#btree_tree_dump $::b1 1
do_test btree-7.4 {
  # The largest free block is 10 bytes long.  So if we insert
  # a record bigger than 10 bytes it should force a defrag
  # The record is 20 bytes long.
  btree_insert $::c1 2000 {123456789_12345}
  # The largest free block is 8 bytes long.  But there is also a
  # huge hole between the cell pointer array and the cellcontent.
  # But if we insert a large enough record, it should force a defrag.
  set data 123456789_
  append data $data
  append data $data
  append data $data
  append data $data
  append data $data
  btree_insert $::c1 2000 $data
  btree_move_to $::c1 2000
  btree_key $::c1
} {2000}
do_test btree-7.5 {
  lrange [btree_cursor_info $::c1] 4 5
} {438 1}
} {343 0}
#btree_tree_dump $::b1 1

# Delete an entry to make a hole of a known size, then immediately recreate
# that entry.  This tests the path into allocateSpace where the hole exactly
# matches the size of the desired space.
#
# Keys are even numbers between 1000 and 1090 and one record of 2000.
# There are 47 keys total.
#
do_test btree-7.6 {
  btree_move_to $::c1 1006
  btree_delete $::c1
  btree_move_to $::c1 1010
  btree_delete $::c1
} {}
do_test btree-7.7 {
  lrange [btree_cursor_info $::c1] 4 5
} {458 3}   ;# Create two new holes of 10 bytes each
#btree_page_dump $::b1 2
} {363 2}   ;# Create two new holes of 10 bytes each
#btree_page_dump $::b1 1
do_test btree-7.8 {
  btree_insert $::c1 1006 { 1006}
  lrange [btree_cursor_info $::c1] 4 5
} {448 2}   ;# Filled in the first hole
#btree_page_dump $::b1 2
} {353 1}   ;# Filled in the first hole
btree_page_dump $::b1 1

# Make sure the freeSpace() routine properly coaleses adjacent memory blocks
#
do_test btree-7.9 {
  btree_move_to $::c1 1012
  btree_delete $::c1
  lrange [btree_cursor_info $::c1] 4 5
} {458 2}  ;# Coalesce with the whole before
} {363 2}  ;# Coalesce with the hole before
btree_page_dump $::b1 1
exit
do_test btree-7.10 {
  btree_move_to $::c1 1008
  btree_delete $::c1
  lrange [btree_cursor_info $::c1] 4 5
} {468 2}  ;# Coalesce with whole after
do_test btree-7.11 {
  btree_move_to $::c1 1030
609
610
611
612
613
614
615

616
617
618
619
620
621
622
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633







+







  btree_delete $::c1
  lrange [btree_cursor_info $::c1] 4 5
} {498 3}   ;# The freed space should coalesce on both ends
#btree_page_dump $::b1 2
do_test btree-7.15 {
  lindex [btree_pager_stats $::b1] 1
} {1}
} ;# endif

# Check to see that data on overflow pages work correctly.
#
do_test btree-8.1 {
  set data "*** This is a very long key "
  while {[string length $data]<1234} {append data $data}
  set ::data $data
883
884
885
886
887
888
889
890

891
892
893
894
895
896
897
894
895
896
897
898
899
900

901
902
903
904
905
906
907
908







-
+







  #btree_tree_dump $::b1 2
}

# Create a tree with lots more pages
#
catch {unset ::data}
catch {unset ::key}
for {set i 31} {$i<=999} {incr i} {
for {set i 31} {$i<=2000} {incr i} {
  do_test btree-11.1.$i.1 {
    set key [format %03d $i]
    set ::data "*** $key *** $key *** $key *** $key ***"
    btree_insert $::c1 $key $data
    btree_move_to $::c1 $key
    btree_key $::c1
  } [format %03d $i]
914
915
916
917
918
919
920
921
922
923
924

925
926

927
928

929
930

931
932
933
934


935
936
937
938
939
940
941
925
926
927
928
929
930
931

932
933
934
935
936

937
938

939
940

941
942
943
944

945
946
947
948
949
950
951
952
953







-



+

-
+

-
+

-
+



-
+
+







  btree_close_cursor $::c1
  lindex [btree_pager_stats $::b1] 1
} {1}
do_test btree-11.3 {
  set ::c1 [btree_cursor $::b1 2 1]
  lindex [btree_pager_stats $::b1] 1
} {2}
#btree_page_dump $::b1 2

# Delete the dividers on the root page
#
#btree_page_dump $::b1 2
do_test btree-11.4 {
  btree_move_to $::c1 551
  btree_move_to $::c1 1667
  btree_delete $::c1
  btree_move_to $::c1 551
  btree_move_to $::c1 1667
  set k [btree_key $::c1]
  if {$k==550} {
  if {$k==1666} {
    set k [btree_next $::c1]
  }
  btree_key $::c1
} {552}
} {1668}
#btree_page_dump $::b1 2

# Change the data on an intermediate node such that the node becomes overfull
# and has to split.  We happen to know that intermediate nodes exist on
# 337, 401 and 465 by the btree_page_dumps above
#
catch {unset ::data}
set ::data {This is going to be a very long data segment}