/ Check-in [e6685af8]
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 | SQL archive
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: e6685af815c4c0c7f09bb097a59a121862b865cf
User & Date: drh 2004-05-30 21:14:59
Context
2004-05-31
08:26
Replace OP_Begin, OP_Commit and OP_Rollback with OP_AutoCommit. (CVS 1500) check-in: b8ed812c 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: e6685af8 user: drh tags: trunk
20:46
Various speed enhancements. (CVS 1498) check-in: a0db15bb user: drh tags: trunk
Changes
Hide Diffs Side-by-Side Diffs Ignore Whitespace Patch

Changes to src/vdbe.c.

    39     39   **
    40     40   ** Various scripts scan this source file in order to generate HTML
    41     41   ** documentation, headers files, or other derived files.  The formatting
    42     42   ** of the code in this file is, therefore, important.  See other comments
    43     43   ** in this file for details.  If in doubt, do not deviate from existing
    44     44   ** commenting and indentation practices when changing or adding code.
    45     45   **
    46         -** $Id: vdbe.c,v 1.349 2004/05/30 20:46:09 drh Exp $
           46  +** $Id: vdbe.c,v 1.350 2004/05/30 21:14:59 drh Exp $
    47     47   */
    48     48   #include "sqliteInt.h"
    49     49   #include "os.h"
    50     50   #include <ctype.h>
    51     51   #include "vdbeInt.h"
    52     52   
    53     53   /*
................................................................................
  3710   3710     assert( pTos>=p->aStack );
  3711   3711     assert( pTos->flags & MEM_Blob );
  3712   3712     z = pTos->z;
  3713   3713     n = pTos->n;
  3714   3714     k = sqlite3GetVarint32(z, &serial_type);
  3715   3715     for(; k<n && i>0; i--){
  3716   3716       k += sqlite3GetVarint32(&z[k], &serial_type);
  3717         -    if( serial_type==6 ){   /* Serial type 6 is a NULL */
         3717  +    if( serial_type==0 ){   /* Serial type 0 is a NULL */
  3718   3718         pc = pOp->p2-1;
  3719   3719         break;
  3720   3720       }
  3721   3721     }
  3722   3722     Release(pTos);
  3723   3723     pTos--;
  3724   3724     break;

Changes to src/vdbeaux.c.

  1113   1113   ** the end. Hence these functions allow the caller to handle the
  1114   1114   ** serial-type and data blob seperately.
  1115   1115   **
  1116   1116   ** The following table describes the various storage classes for data:
  1117   1117   **
  1118   1118   **   serial type        bytes of data      type
  1119   1119   **   --------------     ---------------    ---------------
  1120         -**      0                     -            Not a type.
         1120  +**      0                     0            NULL
  1121   1121   **      1                     1            signed integer
  1122   1122   **      2                     2            signed integer
  1123         -**      3                     4            signed integer
  1124         -**      4                     8            signed integer
  1125         -**      5                     8            IEEE float
  1126         -**      6                     0            NULL
  1127         -**     7..11                               reserved for expansion
         1123  +**      3                     3            signed integer
         1124  +**      4                     4            signed integer
         1125  +**      5                     6            signed integer
         1126  +**      6                     8            signed integer
         1127  +**      7                     8            IEEE float
         1128  +**     8-11                                reserved for expansion
  1128   1129   **    N>=12 and even       (N-12)/2        BLOB
  1129   1130   **    N>=13 and odd        (N-13)/2        text
  1130   1131   **
  1131   1132   */
  1132   1133   
  1133   1134   /*
  1134   1135   ** Return the serial-type for the value stored in pMem.
  1135   1136   */
  1136   1137   u32 sqlite3VdbeSerialType(Mem *pMem){
  1137   1138     int flags = pMem->flags;
  1138   1139   
  1139   1140     if( flags&MEM_Null ){
  1140         -    return 6;
         1141  +    return 0;
  1141   1142     }
  1142   1143     if( flags&MEM_Int ){
  1143   1144       /* Figure out whether to use 1, 2, 4 or 8 bytes. */
  1144   1145       i64 i = pMem->i;
  1145   1146       if( i>=-127 && i<=127 ) return 1;
  1146   1147       if( i>=-32767 && i<=32767 ) return 2;
  1147         -    if( i>=-2147483647 && i<=2147483647 ) return 3;
  1148         -    return 4;
         1148  +    if( i>=-8388607 && i<=8388607 ) return 3;
         1149  +    if( i>=-2147483647 && i<=2147483647 ) return 4;
         1150  +    if( i>=-140737488355328L && i<=140737488355328L ) return 5;
         1151  +    return 6;
  1149   1152     }
  1150   1153     if( flags&MEM_Real ){
  1151         -    return 5;
         1154  +    return 7;
  1152   1155     }
  1153   1156     if( flags&MEM_Str ){
  1154   1157       int n = pMem->n;
  1155   1158       assert( n>=0 );
  1156   1159       return ((n*2) + 13);
  1157   1160     }
  1158   1161     if( flags&MEM_Blob ){
................................................................................
  1161   1164     return 0;
  1162   1165   }
  1163   1166   
  1164   1167   /*
  1165   1168   ** Return the length of the data corresponding to the supplied serial-type.
  1166   1169   */
  1167   1170   int sqlite3VdbeSerialTypeLen(u32 serial_type){
  1168         -  assert( serial_type!=0 );
  1169         -  if( serial_type>6 ){
         1171  +  if( serial_type>=12 ){
  1170   1172       return (serial_type-12)/2;
  1171   1173     }else{
  1172         -    static u8 aSize[] = { 0, 1, 2, 4, 8, 8, 0, };
         1174  +    static u8 aSize[] = { 0, 1, 2, 3, 4, 6, 8, 8, 0, 0, 0, 0 };
  1173   1175       return aSize[serial_type];
  1174   1176     }
  1175   1177   }
  1176   1178   
  1177   1179   /*
  1178   1180   ** Write the serialized data blob for the value stored in pMem into 
  1179   1181   ** buf. It is assumed that the caller has allocated sufficient space.
  1180   1182   ** Return the number of bytes written.
  1181   1183   */ 
  1182   1184   int sqlite3VdbeSerialPut(unsigned char *buf, Mem *pMem){
  1183   1185     u32 serial_type = sqlite3VdbeSerialType(pMem);
  1184   1186     int len;
  1185   1187   
  1186         -  assert( serial_type!=0 );
  1187         - 
  1188   1188     /* NULL */
  1189         -  if( serial_type==6 ){
         1189  +  if( serial_type==0 ){
  1190   1190       return 0;
  1191   1191     }
  1192   1192    
  1193   1193     /* Integer and Real */
  1194         -  if( serial_type<=5 ){
         1194  +  if( serial_type<=7 ){
  1195   1195       u64 v;
  1196   1196       int i;
  1197         -    if( serial_type==5 ){
         1197  +    if( serial_type==7 ){
  1198   1198         v = *(u64*)&pMem->r;
  1199   1199       }else{
  1200   1200         v = *(u64*)&pMem->i;
  1201   1201       }
  1202   1202       len = i = sqlite3VdbeSerialTypeLen(serial_type);
  1203   1203       while( i-- ){
  1204   1204         buf[i] = (v&0xFF);
................................................................................
  1221   1221   int sqlite3VdbeSerialGet(
  1222   1222     const unsigned char *buf,     /* Buffer to deserialize from */
  1223   1223     u32 serial_type,              /* Serial type to deserialize */
  1224   1224     Mem *pMem                     /* Memory cell to write value into */
  1225   1225   ){
  1226   1226     int len;
  1227   1227   
         1228  +  if( serial_type==0 ){
         1229  +    /* NULL */
         1230  +    pMem->flags = MEM_Null;
         1231  +    return 0;
         1232  +  }
  1228   1233     len = sqlite3VdbeSerialTypeLen(serial_type);
  1229         -  assert( serial_type!=0 );
  1230         -  if( serial_type<=5 ){
         1234  +  if( serial_type<=7 ){
  1231   1235       /* Integer and Real */
  1232         -    if( serial_type<=3 ){
         1236  +    if( serial_type<=4 ){
  1233   1237         /* 32-bit integer type.  This is handled by a special case for
  1234   1238         ** performance reasons. */
  1235   1239         int v = buf[0];
  1236   1240         int n;
  1237   1241         if( v&0x80 ){
  1238   1242           v |= -256;
  1239   1243         }
................................................................................
  1249   1253   
  1250   1254         if( buf[0]&0x80 ){
  1251   1255           v = -1;
  1252   1256         }
  1253   1257         for(n=0; n<len; n++){
  1254   1258           v = (v<<8) | buf[n];
  1255   1259         }
  1256         -      if( serial_type==5 ){
         1260  +      if( serial_type==7 ){
  1257   1261           pMem->flags = MEM_Real;
  1258   1262           pMem->r = *(double*)&v;
  1259   1263         }else{
  1260   1264           pMem->flags = MEM_Int;
  1261   1265           pMem->i = *(i64*)&v;
  1262   1266         }
  1263   1267       }
  1264         -  }else if( serial_type>=12 ){
         1268  +  }else{
  1265   1269       /* String or blob */
         1270  +    assert( serial_type>=12 );
  1266   1271       pMem->z = (char *)buf;
  1267   1272       pMem->n = len;
  1268   1273       if( serial_type&0x01 ){
  1269   1274         pMem->flags = MEM_Str | MEM_Ephem;
  1270   1275       }else{
  1271   1276         pMem->flags = MEM_Blob | MEM_Ephem;
  1272   1277       }
  1273         -  }else{
  1274         -    /* NULL */
  1275         -    assert( serial_type==6 );
  1276         -    assert( len==0 );
  1277         -    pMem->flags = MEM_Null;
  1278   1278     }
  1279   1279     return len;
  1280   1280   }
  1281   1281   
  1282   1282   /*
  1283   1283   ** The following is the comparison function for (non-integer)
  1284   1284   ** keys in the btrees.  This function returns negative, zero, or

Changes to test/btree.test.

     7      7   #    May you find forgiveness for yourself and forgive others.
     8      8   #    May you share freely, never taking more than you give.
     9      9   #
    10     10   #***********************************************************************
    11     11   # This file implements regression tests for SQLite library.  The
    12     12   # focus of this script is btree database backend
    13     13   #
    14         -# $Id: btree.test,v 1.25 2004/05/18 15:57:42 drh Exp $
           14  +# $Id: btree.test,v 1.26 2004/05/30 21:14:59 drh Exp $
    15     15   
    16     16   
    17     17   set testdir [file dirname $argv0]
    18     18   source $testdir/tester.tcl
    19     19   
    20     20   # Basic functionality.  Open and close a database.
    21     21   #
................................................................................
   516    516   #   2.  Delete every other entry of table 1.
   517    517   #   3.  Insert a single entry that requires more contiguous
   518    518   #       space than is available.
   519    519   #
   520    520   do_test btree-7.1 {
   521    521     btree_begin_transaction $::b1
   522    522   } {}
          523  +if 0 {
   523    524   catch {unset key}
   524    525   catch {unset data}
   525    526   do_test btree-7.2 {
   526    527     # Each record will be 10 bytes in size.
   527    528     #   + 100 bytes of database header
   528         -  #   + 6 bytes of table header
          529  +  #   + 8 bytes of table header
   529    530     #   + 91*10=910 bytes of cells
   530         -  # Totals 1016 bytes.  8 bytes left over
          531  +  # Totals 1018 bytes.  6 bytes left over
   531    532     # Keys are 1000 through 1090.
   532    533     for {set i 1000} {$i<1091} {incr i} {
   533    534       set key $i
   534    535       set data [format %5d $i]
   535    536       btree_insert $::c1 $key $data
   536    537     }
   537    538     lrange [btree_cursor_info $::c1] 4 5
   538         -} {8 1}
          539  +} {6 0}
          540  +#btree_tree_dump $::b1 1
   539    541   do_test btree-7.3 {
   540    542     for {set i 1001} {$i<1091} {incr i 2} {
   541    543       btree_move_to $::c1 $i
   542    544       btree_delete $::c1
   543    545     }
   544         -  # Freed 45 blocks.  Total freespace is 458
          546  +  # Freed 45 blocks.  Total freespace is 456
   545    547     # Keys remaining are even numbers between 1000 and 1090, inclusive
   546    548     lrange [btree_cursor_info $::c1] 4 5
   547         -} {458 46}
          549  +} {456 45}
   548    550   #btree_tree_dump $::b1 1
   549    551   do_test btree-7.4 {
   550         -  # The largest free block is 10 bytes long.  So if we insert
   551         -  # a record bigger than 10 bytes it should force a defrag
   552         -  # The record is 20 bytes long.
   553         -  btree_insert $::c1 2000 {123456789_12345}
          552  +  # The largest free block is 8 bytes long.  But there is also a
          553  +  # huge hole between the cell pointer array and the cellcontent.
          554  +  # But if we insert a large enough record, it should force a defrag.
          555  +  set data 123456789_
          556  +  append data $data
          557  +  append data $data
          558  +  append data $data
          559  +  append data $data
          560  +  append data $data
          561  +  btree_insert $::c1 2000 $data
   554    562     btree_move_to $::c1 2000
   555    563     btree_key $::c1
   556    564   } {2000}
   557    565   do_test btree-7.5 {
   558    566     lrange [btree_cursor_info $::c1] 4 5
   559         -} {438 1}
          567  +} {343 0}
   560    568   #btree_tree_dump $::b1 1
   561    569   
   562    570   # Delete an entry to make a hole of a known size, then immediately recreate
   563    571   # that entry.  This tests the path into allocateSpace where the hole exactly
   564    572   # matches the size of the desired space.
   565    573   #
   566    574   # Keys are even numbers between 1000 and 1090 and one record of 2000.
................................................................................
   570    578     btree_move_to $::c1 1006
   571    579     btree_delete $::c1
   572    580     btree_move_to $::c1 1010
   573    581     btree_delete $::c1
   574    582   } {}
   575    583   do_test btree-7.7 {
   576    584     lrange [btree_cursor_info $::c1] 4 5
   577         -} {458 3}   ;# Create two new holes of 10 bytes each
   578         -#btree_page_dump $::b1 2
          585  +} {363 2}   ;# Create two new holes of 10 bytes each
          586  +#btree_page_dump $::b1 1
   579    587   do_test btree-7.8 {
   580    588     btree_insert $::c1 1006 { 1006}
   581    589     lrange [btree_cursor_info $::c1] 4 5
   582         -} {448 2}   ;# Filled in the first hole
   583         -#btree_page_dump $::b1 2
          590  +} {353 1}   ;# Filled in the first hole
          591  +btree_page_dump $::b1 1
   584    592   
   585    593   # Make sure the freeSpace() routine properly coaleses adjacent memory blocks
   586    594   #
   587    595   do_test btree-7.9 {
   588    596     btree_move_to $::c1 1012
   589    597     btree_delete $::c1
   590    598     lrange [btree_cursor_info $::c1] 4 5
   591         -} {458 2}  ;# Coalesce with the whole before
          599  +} {363 2}  ;# Coalesce with the hole before
          600  +btree_page_dump $::b1 1
          601  +exit
   592    602   do_test btree-7.10 {
   593    603     btree_move_to $::c1 1008
   594    604     btree_delete $::c1
   595    605     lrange [btree_cursor_info $::c1] 4 5
   596    606   } {468 2}  ;# Coalesce with whole after
   597    607   do_test btree-7.11 {
   598    608     btree_move_to $::c1 1030
................................................................................
   609    619     btree_delete $::c1
   610    620     lrange [btree_cursor_info $::c1] 4 5
   611    621   } {498 3}   ;# The freed space should coalesce on both ends
   612    622   #btree_page_dump $::b1 2
   613    623   do_test btree-7.15 {
   614    624     lindex [btree_pager_stats $::b1] 1
   615    625   } {1}
          626  +} ;# endif
   616    627   
   617    628   # Check to see that data on overflow pages work correctly.
   618    629   #
   619    630   do_test btree-8.1 {
   620    631     set data "*** This is a very long key "
   621    632     while {[string length $data]<1234} {append data $data}
   622    633     set ::data $data
................................................................................
   883    894     #btree_tree_dump $::b1 2
   884    895   }
   885    896   
   886    897   # Create a tree with lots more pages
   887    898   #
   888    899   catch {unset ::data}
   889    900   catch {unset ::key}
   890         -for {set i 31} {$i<=999} {incr i} {
          901  +for {set i 31} {$i<=2000} {incr i} {
   891    902     do_test btree-11.1.$i.1 {
   892    903       set key [format %03d $i]
   893    904       set ::data "*** $key *** $key *** $key *** $key ***"
   894    905       btree_insert $::c1 $key $data
   895    906       btree_move_to $::c1 $key
   896    907       btree_key $::c1
   897    908     } [format %03d $i]
................................................................................
   914    925     btree_close_cursor $::c1
   915    926     lindex [btree_pager_stats $::b1] 1
   916    927   } {1}
   917    928   do_test btree-11.3 {
   918    929     set ::c1 [btree_cursor $::b1 2 1]
   919    930     lindex [btree_pager_stats $::b1] 1
   920    931   } {2}
   921         -#btree_page_dump $::b1 2
   922    932   
   923    933   # Delete the dividers on the root page
   924    934   #
          935  +#btree_page_dump $::b1 2
   925    936   do_test btree-11.4 {
   926         -  btree_move_to $::c1 551
          937  +  btree_move_to $::c1 1667
   927    938     btree_delete $::c1
   928         -  btree_move_to $::c1 551
          939  +  btree_move_to $::c1 1667
   929    940     set k [btree_key $::c1]
   930         -  if {$k==550} {
          941  +  if {$k==1666} {
   931    942       set k [btree_next $::c1]
   932    943     }
   933    944     btree_key $::c1
   934         -} {552}
          945  +} {1668}
          946  +#btree_page_dump $::b1 2
   935    947   
   936    948   # Change the data on an intermediate node such that the node becomes overfull
   937    949   # and has to split.  We happen to know that intermediate nodes exist on
   938    950   # 337, 401 and 465 by the btree_page_dumps above
   939    951   #
   940    952   catch {unset ::data}
   941    953   set ::data {This is going to be a very long data segment}