memory_dynamic_rows.patch

   1 --- a/include/heap.h
   2 +++ b/include/heap.h
   3 @@ -34,7 +34,17 @@
   4  #include "my_compare.h"
   5  #include "my_tree.h"
   6
   7 -       /* defines used by heap-funktions */
   8 +/* Define index limits to be identical to MyISAM ones for compatibility. */
   9 +
  10 +#if MAX_INDEXES > HA_MAX_POSSIBLE_KEY
  11 +#define HP_MAX_KEY                  HA_MAX_POSSIBLE_KEY /* Max allowed keys */
  12 +#else
  13 +#define HP_MAX_KEY                  MAX_INDEXES         /* Max allowed keys */
  14 +#endif
  15 +
  16 +#define HP_MAX_KEY_LENGTH           1000            /* Max length in bytes */
  17 +
  18 +/* defines used by heap-funktions */
  19
  20  #define HP_MAX_LEVELS  4               /* 128^5 records is enough */
  21  #define HP_PTRS_IN_NOD 128
  22 @@ -130,22 +140,58 @@
  23    uint (*get_key_length)(struct st_hp_keydef *keydef, const uchar *key);
  24  } HP_KEYDEF;
  25
  26 -typedef struct st_heap_share
  27 +typedef struct st_heap_columndef               /* column information */
  28 +{
  29 +  int16  type;                         /* en_fieldtype */
  30 +  uint32 length;                       /* length of field */
  31 +  uint32 offset;                       /* Offset to position in row */
  32 +  uint8  null_bit;                     /* If column may be 0 */
  33 +  uint16 null_pos;                     /* position for null marker */
  34 +  uint8  length_bytes;                 /* length of the size, 1 o 2 bytes */
  35 +} HP_COLUMNDEF;
  36 +
  37 +typedef struct st_heap_dataspace   /* control data for data space */
  38  {
  39    HP_BLOCK block;
  40 +  /* Total chunks ever allocated in this dataspace */
  41 +  uint chunk_count;
  42 +  uint del_chunk_count;         /* Deleted chunks count */
  43 +  uchar *del_link;              /* Link to last deleted chunk */
  44 +  uint chunk_length;            /* Total length of one chunk */
  45 +  /* Length of payload that will be placed into one chunk */
  46 +  uint chunk_dataspace_length;
  47 +  /* Offset of the status flag relative to the chunk start */
  48 +  uint offset_status;
  49 +  /* Offset of the linking pointer relative to the chunk start */
  50 +  uint offset_link;
  51 +  /* Test whether records have variable size and so "next" pointer */
  52 +  uint is_variable_size;
  53 +  /* Total size allocated within this data space */
  54 +  ulonglong total_data_length;
  55 +} HP_DATASPACE;
  56 +
  57 +typedef struct st_heap_share
  58 +{
  59    HP_KEYDEF  *keydef;
  60 +  HP_COLUMNDEF *column_defs;
  61 +  /* Describes "block", which contains actual records */
  62 +  HP_DATASPACE recordspace;
  63    ulong min_records,max_records;       /* Params to open */
  64 -  ulonglong data_length,index_length,max_table_size;
  65 +  ulonglong index_length, max_table_size;
  66    uint key_stat_version;                /* version to indicate insert/delete */
  67 -  uint records;                                /* records */
  68 -  uint blength;                                /* records rounded up to 2^n */
  69 -  uint deleted;                                /* Deleted records in database */
  70 -  uint reclength;                      /* Length of one record */
  71 +  uint records;                        /* Actual record (row) count */
  72 +  uint blength;                        /* used_chunk_count rounded up to 2^n */
  73 +  /*
  74 +    Length of record's fixed part, which contains keys and always fits into the
  75 +    first chunk.
  76 +  */
  77 +  uint fixed_data_length;
  78 +  uint fixed_column_count;  /* Number of columns stored in fixed_data_length */
  79    uint changed;
  80    uint keys,max_key_length;
  81 +  uint column_count;
  82    uint currently_disabled_keys;    /* saved value from "keys" when disabled */
  83    uint open_count;
  84 -  uchar *del_link;                     /* Link to next block with del. rec */
  85    char * name;                 /* Name of "memory-file" */
  86    THR_LOCK lock;
  87    mysql_mutex_t intern_lock;            /* Locking for use with _locking */
  88 @@ -154,6 +200,7 @@
  89    uint auto_key;
  90    uint auto_key_type;                  /* real type of the auto key segment */
  91    ulonglong auto_increment;
  92 +  uint blobs;  /* Number of blobs in table */
  93  } HP_SHARE;
  94
  95  struct st_hp_hash_info;
  96 @@ -163,7 +210,7 @@
  97    HP_SHARE *s;
  98    uchar *current_ptr;
  99    struct st_hp_hash_info *current_hash_ptr;
 100 -  ulong current_record,next_block;
 101 +  ulong current_record;
 102    int lastinx,errkey;
 103    int  mode;                           /* Mode of file (READONLY..) */
 104    uint opt_flag,update;
 105 @@ -176,6 +223,9 @@
 106    my_bool implicit_emptied;
 107    THR_LOCK_DATA lock;
 108    LIST open_list;
 109 +  uchar *blob_buffer;  /* Temporary buffer used to return BLOB values */
 110 +  uint blob_size;      /* Current blob_buffer size */
 111 +  uint blob_offset;    /* Current offset in blob_buffer */
 112  } HP_INFO;
 113
 114
 115 @@ -197,6 +247,14 @@
 116      open_count to 1. Is only looked at if not internal_table.
 117    */
 118    my_bool pin_share;
 119 +  uint columns;
 120 +  HP_COLUMNDEF *columndef;
 121 +  uint fixed_key_fieldnr;
 122 +  uint fixed_data_size;
 123 +  uint keys_memory_size;
 124 +  uint max_chunk_size;
 125 +  uint is_dynamic;
 126 +  uint blobs;
 127  } HP_CREATE_INFO;
 128
 129         /* Prototypes for heap-functions */
 130 @@ -213,9 +271,8 @@
 131  extern int heap_scan(register HP_INFO *info, uchar *record);
 132  extern int heap_delete(HP_INFO *info,const uchar *buff);
 133  extern int heap_info(HP_INFO *info,HEAPINFO *x,int flag);
 134 -extern int heap_create(const char *name,
 135 -                       HP_CREATE_INFO *create_info, HP_SHARE **share,
 136 -                       my_bool *created_new_share);
 137 +extern int heap_create(const char *name, HP_CREATE_INFO *create_info,
 138 +                       HP_SHARE **res, my_bool *created_new_share);
 139  extern int heap_delete_table(const char *name);
 140  extern void heap_drop_table(HP_INFO *info);
 141  extern int heap_extra(HP_INFO *info,enum ha_extra_function function);
 142 --- a/mysql-test/r/create.result
 143 +++ b/mysql-test/r/create.result
 144 @@ -33,10 +33,7 @@
 145  create table t1 (b char(0) not null, index(b));
 146  ERROR 42000: The used storage engine can't index column 'b'
 147  create table t1 (a int not null,b text) engine=heap;
 148 -ERROR 42000: The used table type doesn't support BLOB/TEXT columns
 149  drop table if exists t1;
 150 -Warnings:
 151 -Note   1051    Unknown table 't1'
 152  create table t1 (ordid int(8) not null auto_increment, ord  varchar(50) not null, primary key (ord,ordid)) engine=heap;
 153  ERROR 42000: Incorrect table definition; there can be only one auto column and it must be defined as a key
 154  create table not_existing_database.test (a int);
 155 --- a/mysql-test/r/ctype_utf8mb4_heap.result
 156 +++ b/mysql-test/r/ctype_utf8mb4_heap.result
 157 @@ -1124,6 +1124,8 @@
 158  a varchar(255) NOT NULL default '',
 159  KEY a (a)
 160  ) ENGINE=heap DEFAULT CHARSET=utf8mb4 COLLATE utf8mb4_general_ci;
 161 +Warnings:
 162 +Warning        1071    Specified key was too long; max key length is 1000 bytes
 163  insert into t1 values (_utf8mb4 0xe880bd);
 164  insert into t1 values (_utf8mb4 0x5b);
 165  select hex(a) from t1;
 166 @@ -1162,6 +1164,8 @@
 167  Warnings:
 168  Note   1051    Unknown table 't1'
 169  CREATE TABLE t1(a VARCHAR(255), KEY(a)) ENGINE=heap DEFAULT CHARSET=utf8mb4;
 170 +Warnings:
 171 +Warning        1071    Specified key was too long; max key length is 1000 bytes
 172  INSERT INTO t1 VALUES('uuABCDEFGHIGKLMNOPRSTUVWXYZ̈bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb');
 173  INSERT INTO t1 VALUES('uu');
 174  check table t1;
 175 --- a/mysql-test/t/create.test
 176 +++ b/mysql-test/t/create.test
 177 @@ -33,7 +33,7 @@
 178  drop table if exists t1,t2;
 179  --error 1167
 180  create table t1 (b char(0) not null, index(b));
 181 ---error 1163
 182 +# BLOB/TEXT fields are now supported by HEAP
 183  create table t1 (a int not null,b text) engine=heap;
 184  drop table if exists t1;
 185
 186 --- a/storage/heap/CMakeLists.txt
 187 +++ b/storage/heap/CMakeLists.txt
 188 @@ -20,6 +20,7 @@
 189                                 ha_heap.cc
 190                                 hp_delete.c hp_extra.c hp_hash.c hp_info.c hp_open.c hp_panic.c
 191                                 hp_rename.c hp_rfirst.c hp_rkey.c hp_rlast.c hp_rnext.c hp_rprev.c
 192 +                               hp_dspace.c hp_record.c
 193                                 hp_rrnd.c hp_rsame.c hp_scan.c hp_static.c hp_update.c hp_write.c)
 194
 195  MYSQL_ADD_PLUGIN(heap ${HEAP_SOURCES} STORAGE_ENGINE MANDATORY RECOMPILE_FOR_EMBEDDED)
 196 --- a/storage/heap/_check.c
 197 +++ b/storage/heap/_check.c
 198 @@ -43,7 +43,7 @@
 199  {
 200    int error;
 201    uint key;
 202 -  ulong records=0, deleted=0, pos, next_block;
 203 +  ulong records= 0, deleted= 0, chunk_count= 0, pos, next_block;
 204    HP_SHARE *share=info->s;
 205    HP_INFO save_info= *info;                    /* Needed because scan_init */
 206    DBUG_ENTER("heap_check_heap");
 207 @@ -64,31 +64,55 @@
 208    {
 209      if (pos < next_block)
 210      {
 211 -      info->current_ptr+= share->block.recbuffer;
 212 +      info->current_ptr+= share->recordspace.block.recbuffer;
 213      }
 214      else
 215      {
 216 -      next_block+= share->block.records_in_block;
 217 -      if (next_block >= share->records+share->deleted)
 218 +      next_block+= share->recordspace.block.records_in_block;
 219 +      if (next_block >= share->recordspace.chunk_count)
 220        {
 221 -       next_block= share->records+share->deleted;
 222 -       if (pos >= next_block)
 223 -         break;                                /* End of file */
 224 +        next_block= share->recordspace.chunk_count;
 225 +        if (pos >= next_block)
 226 +          break;                               /* End of file */
 227        }
 228      }
 229      hp_find_record(info,pos);
 230
 231 -    if (!info->current_ptr[share->reclength])
 232 +    switch (get_chunk_status(&share->recordspace, info->current_ptr)) {
 233 +    case CHUNK_STATUS_DELETED:
 234        deleted++;
 235 -    else
 236 +      chunk_count++;
 237 +      break;
 238 +    case CHUNK_STATUS_ACTIVE:
 239        records++;
 240 +        chunk_count++;
 241 +        break;
 242 +    case CHUNK_STATUS_LINKED:
 243 +      chunk_count++;
 244 +      break;
 245 +    default:
 246 +      DBUG_PRINT("error",
 247 +                 ("Unknown record status: Record: 0x%lx  Status %lu",
 248 +                  (long) info->current_ptr,
 249 +                  (ulong) get_chunk_status(&share->recordspace,
 250 +                                           info->current_ptr)));
 251 +        error|= 1;
 252 +        break;
 253 +    }
 254    }
 255
 256 -  if (records != share->records || deleted != share->deleted)
 257 -  {
 258 -    DBUG_PRINT("error",("Found rows: %lu (%lu)  deleted %lu (%lu)",
 259 -                       records, (ulong) share->records,
 260 -                        deleted, (ulong) share->deleted));
 261 +  /* TODO: verify linked chunks (no orphans, no cycles, no bad links) */
 262 +
 263 +  if (records != share->records ||
 264 +      chunk_count != share->recordspace.chunk_count ||
 265 +      deleted != share->recordspace.del_chunk_count)
 266 +  {
 267 +    DBUG_PRINT("error",
 268 +               ("Found rows: %lu (%lu) total chunks %lu (%lu) deleted chunks "
 269 +                "%lu (%lu)",
 270 +                records, (ulong) share->records,
 271 +                chunk_count, (ulong) share->recordspace.chunk_count,
 272 +                deleted, (ulong) share->recordspace.del_chunk_count));
 273      error= 1;
 274    }
 275    *info= save_info;
 276 @@ -177,7 +201,7 @@
 277      do
 278      {
 279        memcpy(&recpos, key + (*keydef->get_key_length)(keydef,key), sizeof(uchar*));
 280 -      key_length= hp_rb_make_key(keydef, info->recbuf, recpos, 0);
 281 +      key_length= hp_rb_make_key(keydef, info->recbuf, recpos, 0, TRUE);
 282        if (ha_key_cmp(keydef->seg, (uchar*) info->recbuf, (uchar*) key,
 283                      key_length, SEARCH_FIND | SEARCH_SAME, not_used))
 284        {
 285 --- a/storage/heap/_rectest.c
 286 +++ b/storage/heap/_rectest.c
 287 @@ -22,7 +22,9 @@
 288  {
 289    DBUG_ENTER("hp_rectest");
 290
 291 -  if (memcmp(info->current_ptr,old,(size_t) info->s->reclength))
 292 +  if (hp_process_record_data_to_chunkset(info->s, old,
 293 +                                         info->current_ptr,
 294 +                                         1))
 295    {
 296      DBUG_RETURN((my_errno=HA_ERR_RECORD_CHANGED)); /* Record have changed */
 297    }
 298 --- a/storage/heap/ha_heap.cc
 299 +++ b/storage/heap/ha_heap.cc
 300 @@ -114,6 +114,7 @@
 301
 302      rc= heap_create(name, &create_info, &internal_share, &created_new_share);
 303      my_free(create_info.keydef);
 304 +    my_free(create_info.columndef);
 305      if (rc)
 306        goto end;
 307
 308 @@ -195,6 +196,12 @@
 309    {
 310      if (table->key_info[i].algorithm == HA_KEY_ALG_BTREE)
 311        btree_keys.set_bit(i);
 312 +    /*
 313 +      Reset per-key block size specification so they are not shown
 314 +      in SHOW CREATE TABLE.
 315 +    */
 316 +    table->key_info[i].block_size= 0;
 317 +    table->key_info[i].flags&= ~HA_USES_BLOCK_SIZE;
 318    }
 319  }
 320
 321 @@ -428,6 +435,13 @@
 322    return 0;
 323  }
 324
 325 +enum row_type ha_heap::get_row_type() const
 326 +{
 327 +  if (file->s->recordspace.is_variable_size)
 328 +    return ROW_TYPE_DYNAMIC;
 329 +
 330 +  return ROW_TYPE_FIXED;
 331 +}
 332
 333  int ha_heap::extra(enum ha_extra_function operation)
 334  {
 335 @@ -645,23 +659,70 @@
 336  heap_prepare_hp_create_info(TABLE *table_arg, bool internal_table,
 337                              HP_CREATE_INFO *hp_create_info)
 338  {
 339 -  uint key, parts, mem_per_row= 0, keys= table_arg->s->keys;
 340 +  uint key, parts, mem_per_row_keys= 0, keys= table_arg->s->keys;
 341    uint auto_key= 0, auto_key_type= 0;
 342 -  ha_rows max_rows;
 343 +  uint fixed_key_fieldnr = 0, fixed_data_size = 0, next_field_pos = 0;
 344 +  uint column_idx, column_count= table_arg->s->fields;
 345 +  HP_COLUMNDEF *columndef;
 346    HP_KEYDEF *keydef;
 347    HA_KEYSEG *seg;
 348    TABLE_SHARE *share= table_arg->s;
 349    bool found_real_auto_increment= 0;
 350 +  uint blobs= 0;
 351
 352    bzero(hp_create_info, sizeof(*hp_create_info));
 353
 354 +  if (!(columndef= (HP_COLUMNDEF*) my_malloc(column_count *
 355 +                                             sizeof(HP_COLUMNDEF),
 356 +                                             MYF(MY_WME))))
 357 +    return my_errno;
 358 +
 359 +  for (column_idx= 0; column_idx < column_count; column_idx++)
 360 +  {
 361 +    Field* field= *(table_arg->field + column_idx);
 362 +    HP_COLUMNDEF* column= columndef + column_idx;
 363 +    column->type= (uint16) field->type();
 364 +    column->length= field->pack_length();
 365 +    column->offset= field->offset(table_arg->record[0]);
 366 +
 367 +    if (field->null_bit)
 368 +    {
 369 +      column->null_bit= field->null_bit;
 370 +      column->null_pos= (uint) (field->null_ptr -
 371 +                                (uchar*) table_arg->record[0]);
 372 +    }
 373 +    else
 374 +    {
 375 +      column->null_bit= 0;
 376 +      column->null_pos= 0;
 377 +    }
 378 +
 379 +    if (field->type() == MYSQL_TYPE_VARCHAR)
 380 +    {
 381 +      column->length_bytes= (uint8) (((Field_varstring *) field)->length_bytes);
 382 +    }
 383 +    else if (field->type() == MYSQL_TYPE_BLOB)
 384 +    {
 385 +      blobs++;
 386 +      column->length_bytes= (uint8)
 387 +        (((Field_blob *) field)->pack_length_no_ptr());
 388 +    }
 389 +    else
 390 +    {
 391 +      column->length_bytes= 0;
 392 +    }
 393 +  }
 394 +
 395    for (key= parts= 0; key < keys; key++)
 396      parts+= table_arg->key_info[key].key_parts;
 397
 398    if (!(keydef= (HP_KEYDEF*) my_malloc(keys * sizeof(HP_KEYDEF) +
 399                                        parts * sizeof(HA_KEYSEG),
 400                                        MYF(MY_WME))))
 401 +  {
 402 +    my_free((uchar *) columndef);
 403      return my_errno;
 404 +  }
 405    seg= reinterpret_cast<HA_KEYSEG*>(keydef + keys);
 406    for (key= 0; key < keys; key++)
 407    {
 408 @@ -677,11 +738,11 @@
 409      case HA_KEY_ALG_UNDEF:
 410      case HA_KEY_ALG_HASH:
 411        keydef[key].algorithm= HA_KEY_ALG_HASH;
 412 -      mem_per_row+= sizeof(char*) * 2; // = sizeof(HASH_INFO)
 413 +      mem_per_row_keys+= sizeof(char*) * 2; // = sizeof(HASH_INFO)
 414        break;
 415      case HA_KEY_ALG_BTREE:
 416        keydef[key].algorithm= HA_KEY_ALG_BTREE;
 417 -      mem_per_row+=sizeof(TREE_ELEMENT)+pos->key_length+sizeof(char*);
 418 +      mem_per_row_keys+=sizeof(TREE_ELEMENT)+pos->key_length+sizeof(char*);
 419        break;
 420      default:
 421        DBUG_ASSERT(0); // cannot happen
 422 @@ -706,6 +767,16 @@
 423        seg->length=  (uint) key_part->length;
 424        seg->flag=    key_part->key_part_flag;
 425
 426 +      next_field_pos= seg->start;
 427 +      if (field->type() == MYSQL_TYPE_VARCHAR)
 428 +      {
 429 +        Field *orig_field= *(table_arg->field + key_part->field->field_index);
 430 +        next_field_pos+= orig_field->pack_length();
 431 +      }
 432 +      else
 433 +      {
 434 +        next_field_pos+= seg->length;
 435 +      }
 436        if (field->flags & (ENUM_FLAG | SET_FLAG))
 437          seg->charset= &my_charset_bin;
 438        else
 439 @@ -731,9 +802,75 @@
 440          auto_key= key+ 1;
 441         auto_key_type= field->key_type();
 442        }
 443 +
 444 +      switch (seg->type) {
 445 +      case HA_KEYTYPE_SHORT_INT:
 446 +      case HA_KEYTYPE_LONG_INT:
 447 +      case HA_KEYTYPE_FLOAT:
 448 +      case HA_KEYTYPE_DOUBLE:
 449 +      case HA_KEYTYPE_USHORT_INT:
 450 +      case HA_KEYTYPE_ULONG_INT:
 451 +      case HA_KEYTYPE_LONGLONG:
 452 +      case HA_KEYTYPE_ULONGLONG:
 453 +      case HA_KEYTYPE_INT24:
 454 +      case HA_KEYTYPE_UINT24:
 455 +      case HA_KEYTYPE_INT8:
 456 +        seg->flag|= HA_SWAP_KEY;
 457 +        break;
 458 +      case HA_KEYTYPE_VARBINARY1:
 459 +        /* Case-insensitiveness is handled in coll->hash_sort */
 460 +        seg->type= HA_KEYTYPE_VARTEXT1;
 461 +        /* fall through */
 462 +      case HA_KEYTYPE_VARTEXT1:
 463 +        keydef[key].flag|= HA_VAR_LENGTH_KEY;
 464 +        /* Save number of bytes used to store length */
 465 +        if (seg->flag & HA_BLOB_PART)
 466 +          seg->bit_start= field->pack_length() - share->blob_ptr_size;
 467 +        else
 468 +          seg->bit_start= 1;
 469 +        break;
 470 +      case HA_KEYTYPE_VARBINARY2:
 471 +        /* Case-insensitiveness is handled in coll->hash_sort */
 472 +        /* fall_through */
 473 +      case HA_KEYTYPE_VARTEXT2:
 474 +        keydef[key].flag|= HA_VAR_LENGTH_KEY;
 475 +        /* Save number of bytes used to store length */
 476 +        if (seg->flag & HA_BLOB_PART)
 477 +          seg->bit_start= field->pack_length() - share->blob_ptr_size;
 478 +        else
 479 +          seg->bit_start= 2;
 480 +        /*
 481 +          Make future comparison simpler by only having to check for
 482 +          one type
 483 +        */
 484 +        seg->type= HA_KEYTYPE_VARTEXT1;
 485 +        break;
 486 +      default:
 487 +        break;
 488 +      }
 489 +
 490 +      if (next_field_pos > fixed_data_size)
 491 +      {
 492 +        fixed_data_size= next_field_pos;
 493 +      }
 494 +
 495 +
 496 +      if (field->field_index >= fixed_key_fieldnr)
 497 +      {
 498 +        /*
 499 +          Do not use seg->fieldnr as it's not reliable in case of temp tables
 500 +        */
 501 +        fixed_key_fieldnr= field->field_index + 1;
 502 +      }
 503      }
 504    }
 505 -  mem_per_row+= MY_ALIGN(share->reclength + 1, sizeof(char*));
 506 +
 507 +  if (fixed_data_size < share->null_bytes)
 508 +  {
 509 +    /* Make sure to include null fields regardless of the presense of keys */
 510 +    fixed_data_size = share->null_bytes;
 511 +  }
 512 +
 513    if (table_arg->found_next_number_field)
 514    {
 515      keydef[share->next_number_index].flag|= HA_AUTO_KEY;
 516 @@ -744,16 +881,19 @@
 517    hp_create_info->max_table_size=current_thd->variables.max_heap_table_size;
 518    hp_create_info->with_auto_increment= found_real_auto_increment;
 519    hp_create_info->internal_table= internal_table;
 520 -
 521 -  max_rows= (ha_rows) (hp_create_info->max_table_size / mem_per_row);
 522 -  if (share->max_rows && share->max_rows < max_rows)
 523 -    max_rows= share->max_rows;
 524 -
 525 -  hp_create_info->max_records= (ulong) max_rows;
 526 +  hp_create_info->max_chunk_size= share->key_block_size;
 527 +  hp_create_info->is_dynamic= (share->row_type == ROW_TYPE_DYNAMIC);
 528 +  hp_create_info->columns= column_count;
 529 +  hp_create_info->columndef= columndef;
 530 +  hp_create_info->fixed_key_fieldnr= fixed_key_fieldnr;
 531 +  hp_create_info->fixed_data_size= fixed_data_size;
 532 +  hp_create_info->max_records= (ulong) share->max_rows;
 533    hp_create_info->min_records= (ulong) share->min_rows;
 534    hp_create_info->keys= share->keys;
 535    hp_create_info->reclength= share->reclength;
 536 +  hp_create_info->keys_memory_size= mem_per_row_keys;
 537    hp_create_info->keydef= keydef;
 538 +  hp_create_info->blobs= blobs;
 539    return 0;
 540  }
 541
 542 @@ -773,6 +913,7 @@
 543                                   create_info->auto_increment_value - 1 : 0);
 544    error= heap_create(name, &hp_create_info, &internal_share, &created);
 545    my_free(hp_create_info.keydef);
 546 +  my_free(hp_create_info.columndef);
 547    DBUG_ASSERT(file == 0);
 548    return (error);
 549  }
 550 @@ -783,6 +924,13 @@
 551    table->file->info(HA_STATUS_AUTO);
 552    if (!(create_info->used_fields & HA_CREATE_USED_AUTO))
 553      create_info->auto_increment_value= stats.auto_increment_value;
 554 +  if (!(create_info->used_fields & HA_CREATE_USED_KEY_BLOCK_SIZE))
 555 +  {
 556 +    if (file->s->recordspace.is_variable_size)
 557 +      create_info->key_block_size= file->s->recordspace.chunk_length;
 558 +    else
 559 +      create_info->key_block_size= 0;
 560 +  }
 561  }
 562
 563  void ha_heap::get_auto_increment(ulonglong offset, ulonglong increment,
 564 --- a/storage/heap/ha_heap.h
 565 +++ b/storage/heap/ha_heap.h
 566 @@ -47,12 +47,11 @@
 567      return ((table_share->key_info[inx].algorithm == HA_KEY_ALG_BTREE) ?
 568              "BTREE" : "HASH");
 569    }
 570 -  /* Rows also use a fixed-size format */
 571 -  enum row_type get_row_type() const { return ROW_TYPE_FIXED; }
 572 +  enum row_type get_row_type() const;
 573    const char **bas_ext() const;
 574    ulonglong table_flags() const
 575    {
 576 -    return (HA_FAST_KEY_READ | HA_NO_BLOBS | HA_NULL_IN_KEY |
 577 +    return (HA_FAST_KEY_READ | HA_NULL_IN_KEY |
 578              HA_BINLOG_ROW_CAPABLE | HA_BINLOG_STMT_CAPABLE |
 579              HA_REC_NOT_IN_SEQ | HA_CAN_INSERT_DELAYED | HA_NO_TRANSACTIONS |
 580              HA_HAS_RECORDS | HA_STATS_RECORDS_IS_EXACT);
 581 @@ -64,8 +63,9 @@
 582              HA_ONLY_WHOLE_INDEX | HA_KEY_SCAN_NOT_ROR);
 583    }
 584    const key_map *keys_to_use_for_scanning() { return &btree_keys; }
 585 -  uint max_supported_keys()          const { return MAX_KEY; }
 586 -  uint max_supported_key_part_length() const { return MAX_KEY_LENGTH; }
 587 +  uint max_supported_keys()          const { return HP_MAX_KEY; }
 588 +  uint max_supported_key_length() const { return HP_MAX_KEY_LENGTH; }
 589 +  uint max_supported_key_part_length() const { return HP_MAX_KEY_LENGTH; }
 590    double scan_time()
 591    { return (double) (stats.records+stats.deleted) / 20.0+10; }
 592    double read_time(uint index, uint ranges, ha_rows rows)
 593 --- a/storage/heap/heapdef.h
 594 +++ b/storage/heap/heapdef.h
 595 @@ -32,6 +32,13 @@
 596  #define HP_MIN_RECORDS_IN_BLOCK 16
 597  #define HP_MAX_RECORDS_IN_BLOCK 8192
 598
 599 +/* this chunk has been deleted and can be reused */
 600 +#define CHUNK_STATUS_DELETED 0
 601 +/* this chunk represents the first part of a live record */
 602 +#define CHUNK_STATUS_ACTIVE  1
 603 +/* this chunk is a continuation from another chunk (part of chunkset) */
 604 +#define CHUNK_STATUS_LINKED  2
 605 +
 606         /* Some extern variables */
 607
 608  extern LIST *heap_open_list,*heap_share_list;
 609 @@ -42,7 +49,14 @@
 610  #define hp_find_hash(A,B) ((HASH_INFO*) hp_find_block((A),(B)))
 611
 612         /* Find pos for record and update it in info->current_ptr */
 613 -#define hp_find_record(info,pos) (info)->current_ptr= hp_find_block(&(info)->s->block,pos)
 614 +#define hp_find_record(info,pos) \
 615 +  (info)->current_ptr= hp_find_block(&(info)->s->recordspace.block,pos)
 616 +
 617 +#define get_chunk_status(info,ptr) (ptr[(info)->offset_status])
 618 +
 619 +#define get_chunk_count(info,rec_length) \
 620 +  ((rec_length + (info)->chunk_dataspace_length - 1) / \
 621 +   (info)->chunk_dataspace_length)
 622
 623  typedef struct st_hp_hash_info
 624  {
 625 @@ -90,7 +104,7 @@
 626                       const uchar *key);
 627  extern void hp_make_key(HP_KEYDEF *keydef,uchar *key,const uchar *rec);
 628  extern uint hp_rb_make_key(HP_KEYDEF *keydef, uchar *key,
 629 -                          const uchar *rec, uchar *recpos);
 630 +                          const uchar *rec, uchar *recpos, my_bool packed);
 631  extern uint hp_rb_key_length(HP_KEYDEF *keydef, const uchar *key);
 632  extern uint hp_rb_null_key_length(HP_KEYDEF *keydef, const uchar *key);
 633  extern uint hp_rb_var_key_length(HP_KEYDEF *keydef, const uchar *key);
 634 @@ -100,6 +114,23 @@
 635  extern void hp_clear_keys(HP_SHARE *info);
 636  extern uint hp_rb_pack_key(HP_KEYDEF *keydef, uchar *key, const uchar *old,
 637                             key_part_map keypart_map);
 638 +extern uint hp_calc_blob_length(uint length, const uchar *pos);
 639 +
 640 +/* Chunkset management (alloc/free/encode/decode) functions */
 641 +extern uchar *hp_allocate_chunkset(HP_DATASPACE *info, uint chunk_count);
 642 +extern int hp_reallocate_chunkset(HP_DATASPACE *info, uint chunk_count,
 643 +                                  uchar *pos);
 644 +extern void hp_free_chunks(HP_DATASPACE *info, uchar *pos);
 645 +extern void hp_clear_dataspace(HP_DATASPACE *info);
 646 +
 647 +extern uint hp_get_encoded_data_length(HP_SHARE *info, const uchar *record,
 648 +                                       uint *chunk_count);
 649 +extern void hp_copy_record_data_to_chunkset(HP_SHARE *info, const uchar *record,
 650 +                                            uchar *pos);
 651 +extern int hp_extract_record(HP_INFO *info, uchar *record, const uchar *pos);
 652 +extern uint hp_process_record_data_to_chunkset(HP_SHARE *info,
 653 +                                               const uchar *record, uchar *pos,
 654 +                                               uint is_compare);
 655
 656  extern mysql_mutex_t THR_LOCK_heap;
 657
 658 --- a/storage/heap/hp_clear.c
 659 +++ b/storage/heap/hp_clear.c
 660 @@ -31,16 +31,11 @@
 661  {
 662    DBUG_ENTER("hp_clear");
 663
 664 -  if (info->block.levels)
 665 -    (void) hp_free_level(&info->block,info->block.levels,info->block.root,
 666 -                       (uchar*) 0);
 667 -  info->block.levels=0;
 668 +  hp_clear_dataspace(&info->recordspace);
 669    hp_clear_keys(info);
 670 -  info->records= info->deleted= 0;
 671 -  info->data_length= 0;
 672 +  info->records= 0;
 673    info->blength=1;
 674    info->changed=0;
 675 -  info->del_link=0;
 676    DBUG_VOID_RETURN;
 677  }
 678
 679 @@ -158,7 +153,7 @@
 680    int error= 0;
 681    HP_SHARE *share= info->s;
 682
 683 -  if (share->data_length || share->index_length)
 684 +  if (share->recordspace.total_data_length || share->index_length)
 685      error= HA_ERR_CRASHED;
 686    else
 687      if (share->currently_disabled_keys)
 688 --- a/storage/heap/hp_close.c
 689 +++ b/storage/heap/hp_close.c
 690 @@ -46,6 +46,10 @@
 691      heap_open_list=list_delete(heap_open_list,&info->open_list);
 692    if (!--info->s->open_count && info->s->delete_on_close)
 693      hp_free(info->s);                          /* Table was deleted */
 694 +  if (info->blob_buffer)
 695 +  {
 696 +    my_free(info->blob_buffer);
 697 +  }
 698    my_free(info);
 699    DBUG_RETURN(error);
 700  }
 701 --- a/storage/heap/hp_create.c
 702 +++ b/storage/heap/hp_create.c
 703 @@ -14,11 +14,21 @@
 704     Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301  USA */
 705
 706  #include "heapdef.h"
 707 +#include <mysql_com.h>
 708 +#include <mysqld_error.h>
 709
 710  static int keys_compare(heap_rb_param *param, uchar *key1, uchar *key2);
 711 -static void init_block(HP_BLOCK *block,uint reclength,ulong min_records,
 712 +static void init_block(HP_BLOCK *block,uint chunk_length, ulong min_records,
 713                        ulong max_records);
 714
 715 +#define FIXED_REC_OVERHEAD (sizeof(uchar))
 716 +#define VARIABLE_REC_OVERHEAD (sizeof(uchar **) + sizeof(uchar))
 717 +
 718 +/* Minimum size that a chunk can take, 12 bytes on 32bit, 24 bytes on 64bit */
 719 +#define VARIABLE_MIN_CHUNK_SIZE                                         \
 720 +  ((sizeof(uchar **) + VARIABLE_REC_OVERHEAD + sizeof(uchar **) - 1) &  \
 721 +   ~(sizeof(uchar **) - 1))
 722 +
 723  /* Create a heap table */
 724
 725  int heap_create(const char *name, HP_CREATE_INFO *create_info,
 726 @@ -32,6 +42,7 @@
 727    uint keys= create_info->keys;
 728    ulong min_records= create_info->min_records;
 729    ulong max_records= create_info->max_records;
 730 +  ulong max_rows_for_stated_memory;
 731    DBUG_ENTER("heap_create");
 732
 733    if (!create_info->internal_table)
 734 @@ -48,15 +59,147 @@
 735
 736    if (!share)
 737    {
 738 +    uint chunk_dataspace_length, chunk_length, is_variable_size;
 739 +    uint fixed_data_length, fixed_column_count;
 740      HP_KEYDEF *keyinfo;
 741      DBUG_PRINT("info",("Initializing new table"));
 742 -
 743 +
 744 +    if (create_info->max_chunk_size)
 745 +    {
 746 +      uint configured_chunk_size= create_info->max_chunk_size;
 747 +
 748 +      /* User requested variable-size records, let's see if they're possible */
 749 +
 750 +      if (configured_chunk_size < create_info->fixed_data_size)
 751 +      {
 752 +        /*
 753 +          The resulting chunk_size cannot be smaller than fixed data part
 754 +          at the start of the first chunk which allows faster copying
 755 +          with a single memcpy().
 756 +        */
 757 +        my_error(ER_CANT_USE_OPTION_HERE, MYF(0), "key_block_size");
 758 +        goto err;
 759 +      }
 760 +
 761 +      if (reclength > configured_chunk_size + VARIABLE_REC_OVERHEAD ||
 762 +         create_info->blobs > 0)
 763 +      {
 764 +        /*
 765 +          Allow variable size only if we're saving some space, i.e.
 766 +          if a fixed-size record would take more space than variable-size
 767 +          one plus the variable-size overhead.
 768 +          There has to be at least one field after indexed fields.
 769 +          Note that NULL bits are already included in key_part_size.
 770 +        */
 771 +        is_variable_size= 1;
 772 +        chunk_dataspace_length= configured_chunk_size;
 773 +      }
 774 +      else
 775 +      {
 776 +        /* max_chunk_size is near the full reclength, let's use fixed size */
 777 +        is_variable_size= 0;
 778 +        chunk_dataspace_length= reclength;
 779 +      }
 780 +    }
 781 +    else if ((create_info->is_dynamic && reclength >
 782 +              256 + VARIABLE_REC_OVERHEAD)
 783 +             || create_info->blobs > 0)
 784 +    {
 785 +      /*
 786 +        User asked for dynamic records - use 256 as the chunk size, if that
 787 +        will may save some memory. Otherwise revert to fixed size format.
 788 +      */
 789 +      if ((create_info->fixed_data_size + VARIABLE_REC_OVERHEAD) > 256)
 790 +        chunk_dataspace_length= create_info->fixed_data_size;
 791 +      else
 792 +        chunk_dataspace_length= 256 - VARIABLE_REC_OVERHEAD;
 793 +
 794 +      is_variable_size= 1;
 795 +    }
 796 +    else
 797 +    {
 798 +      /*
 799 +        If max_chunk_size is not specified, put the whole record in one chunk
 800 +      */
 801 +      is_variable_size= 0;
 802 +      chunk_dataspace_length= reclength;
 803 +    }
 804 +
 805 +    if (is_variable_size)
 806 +    {
 807 +      /* Check whether we have any variable size records past key data */
 808 +      uint has_variable_fields= 0;
 809 +
 810 +      fixed_data_length= create_info->fixed_data_size;
 811 +      fixed_column_count= create_info->fixed_key_fieldnr;
 812 +
 813 +      for (i= create_info->fixed_key_fieldnr; i < create_info->columns; i++)
 814 +      {
 815 +        HP_COLUMNDEF *column= create_info->columndef + i;
 816 +       if ((column->type == MYSQL_TYPE_VARCHAR &&
 817 +            (column->length - column->length_bytes) >= 32) ||
 818 +           column->type == MYSQL_TYPE_BLOB)
 819 +        {
 820 +            /*
 821 +              The field has to be either blob or >= 5.0.3 true VARCHAR
 822 +              and have substantial length.
 823 +              TODO: do we want to calculate minimum length?
 824 +            */
 825 +            has_variable_fields= 1;
 826 +            break;
 827 +        }
 828 +
 829 +        if (has_variable_fields)
 830 +        {
 831 +          break;
 832 +        }
 833 +
 834 +        if ((column->offset + column->length) <= chunk_dataspace_length)
 835 +        {
 836 +          /* Still no variable-size columns, add one fixed-length */
 837 +          fixed_column_count= i + 1;
 838 +          fixed_data_length= column->offset + column->length;
 839 +        }
 840 +      }
 841 +
 842 +      if (!has_variable_fields && create_info->blobs == 0)
 843 +      {
 844 +        /*
 845 +          There is no need to use variable-size records without variable-size
 846 +          columns.
 847 +          Reset sizes if it's not variable size anymore.
 848 +        */
 849 +        is_variable_size= 0;
 850 +        chunk_dataspace_length= reclength;
 851 +        fixed_data_length= reclength;
 852 +        fixed_column_count= create_info->columns;
 853 +      }
 854 +    }
 855 +    else
 856 +    {
 857 +      fixed_data_length= reclength;
 858 +      fixed_column_count= create_info->columns;
 859 +    }
 860 +
 861      /*
 862 -      We have to store sometimes uchar* del_link in records,
 863 -      so the record length should be at least sizeof(uchar*)
 864 +      We store uchar* del_link inside the data area of deleted records,
 865 +      so the data length should be at least sizeof(uchar*)
 866      */
 867 -    set_if_bigger(reclength, sizeof (uchar*));
 868 -
 869 +    set_if_bigger(chunk_dataspace_length, sizeof (uchar **));
 870 +
 871 +    if (is_variable_size)
 872 +    {
 873 +      chunk_length= chunk_dataspace_length + VARIABLE_REC_OVERHEAD;
 874 +    }
 875 +    else
 876 +    {
 877 +      chunk_length= chunk_dataspace_length + FIXED_REC_OVERHEAD;
 878 +    }
 879 +
 880 +    /* Align chunk length to the next pointer */
 881 +    chunk_length= (uint) (chunk_length + sizeof(uchar **) - 1) &
 882 +      ~(sizeof(uchar **) - 1);
 883 +
 884      for (i= key_segs= max_length= 0, keyinfo= keydef; i < keys; i++, keyinfo++)
 885      {
 886        bzero((char*) &keyinfo->block,sizeof(keyinfo->block));
 887 @@ -73,42 +216,11 @@
 888             keyinfo->rb_tree.size_of_element++;
 889         }
 890         switch (keyinfo->seg[j].type) {
 891 -       case HA_KEYTYPE_SHORT_INT:
 892 -       case HA_KEYTYPE_LONG_INT:
 893 -       case HA_KEYTYPE_FLOAT:
 894 -       case HA_KEYTYPE_DOUBLE:
 895 -       case HA_KEYTYPE_USHORT_INT:
 896 -       case HA_KEYTYPE_ULONG_INT:
 897 -       case HA_KEYTYPE_LONGLONG:
 898 -       case HA_KEYTYPE_ULONGLONG:
 899 -       case HA_KEYTYPE_INT24:
 900 -       case HA_KEYTYPE_UINT24:
 901 -       case HA_KEYTYPE_INT8:
 902 -         keyinfo->seg[j].flag|= HA_SWAP_KEY;
 903 -          break;
 904          case HA_KEYTYPE_VARBINARY1:
 905 -          /* Case-insensitiveness is handled in coll->hash_sort */
 906 -          keyinfo->seg[j].type= HA_KEYTYPE_VARTEXT1;
 907 -          /* fall_through */
 908          case HA_KEYTYPE_VARTEXT1:
 909 -          keyinfo->flag|= HA_VAR_LENGTH_KEY;
 910 -          length+= 2;
 911 -          /* Save number of bytes used to store length */
 912 -          keyinfo->seg[j].bit_start= 1;
 913 -          break;
 914          case HA_KEYTYPE_VARBINARY2:
 915 -          /* Case-insensitiveness is handled in coll->hash_sort */
 916 -          /* fall_through */
 917          case HA_KEYTYPE_VARTEXT2:
 918 -          keyinfo->flag|= HA_VAR_LENGTH_KEY;
 919            length+= 2;
 920 -          /* Save number of bytes used to store length */
 921 -          keyinfo->seg[j].bit_start= 2;
 922 -          /*
 923 -            Make future comparison simpler by only having to check for
 924 -            one type
 925 -          */
 926 -          keyinfo->seg[j].type= HA_KEYTYPE_VARTEXT1;
 927            break;
 928         default:
 929           break;
 930 @@ -133,13 +245,34 @@
 931      }
 932      if (!(share= (HP_SHARE*) my_malloc((uint) sizeof(HP_SHARE)+
 933                                        keys*sizeof(HP_KEYDEF)+
 934 +                                       (create_info->columns *
 935 +                                        sizeof(HP_COLUMNDEF)) +
 936                                        key_segs*sizeof(HA_KEYSEG),
 937                                        MYF(MY_ZEROFILL))))
 938        goto err;
 939 -    share->keydef= (HP_KEYDEF*) (share + 1);
 940 +
 941 +    /*
 942 +      Max_records is used for estimating block sizes and for enforcement.
 943 +      Calculate the very maximum number of rows (if everything was one chunk)
 944 +      and then take either that value or configured max_records (pick smallest
 945 +      one).
 946 +    */
 947 +    max_rows_for_stated_memory= (ha_rows) (create_info->max_table_size /
 948 +                                           (create_info->keys_memory_size +
 949 +                                            chunk_length));
 950 +    max_records = ((max_records && max_records < max_rows_for_stated_memory) ?
 951 +                   max_records : max_rows_for_stated_memory);
 952 +
 953 +    share->column_defs= (HP_COLUMNDEF*) (share + 1);
 954 +    memcpy(share->column_defs, create_info->columndef,
 955 +           (size_t) (sizeof(create_info->columndef[0]) *
 956 +                     create_info->columns));
 957 +
 958 +    share->keydef= (HP_KEYDEF*) (share->column_defs + create_info->columns);
 959      share->key_stat_version= 1;
 960      keyseg= (HA_KEYSEG*) (share->keydef + keys);
 961 -    init_block(&share->block, reclength + 1, min_records, max_records);
 962 +    init_block(&share->recordspace.block, chunk_length, min_records,
 963 +               max_records);
 964         /* Fix keys */
 965      memcpy(share->keydef, keydef, (size_t) (sizeof(keydef[0]) * keys));
 966      for (i= 0, keyinfo= share->keydef; i < keys; i++, keyinfo++)
 967 @@ -177,15 +310,35 @@
 968      share->min_records= min_records;
 969      share->max_records= max_records;
 970      share->max_table_size= create_info->max_table_size;
 971 -    share->data_length= share->index_length= 0;
 972 -    share->reclength= reclength;
 973 +    share->index_length= 0;
 974      share->blength= 1;
 975      share->keys= keys;
 976      share->max_key_length= max_length;
 977 +    share->column_count= create_info->columns;
 978      share->changed= 0;
 979      share->auto_key= create_info->auto_key;
 980      share->auto_key_type= create_info->auto_key_type;
 981      share->auto_increment= create_info->auto_increment;
 982 +
 983 +    share->fixed_data_length= fixed_data_length;
 984 +    share->fixed_column_count= fixed_column_count;
 985 +    share->blobs= create_info->blobs;
 986 +
 987 +    share->recordspace.chunk_length= chunk_length;
 988 +    share->recordspace.chunk_dataspace_length= chunk_dataspace_length;
 989 +    share->recordspace.is_variable_size= is_variable_size;
 990 +    share->recordspace.total_data_length= 0;
 991 +
 992 +    if (is_variable_size) {
 993 +      share->recordspace.offset_link= chunk_dataspace_length;
 994 +      share->recordspace.offset_status= share->recordspace.offset_link +
 995 +        sizeof(uchar **);
 996 +    } else {
 997 +      /* Make it likely to fail if anyone uses this offset */
 998 +      share->recordspace.offset_link= 1 << 22;
 999 +      share->recordspace.offset_status= chunk_dataspace_length;
1000 +    }
1001 +
1002      /* Must be allocated separately for rename to work */
1003      if (!(share->name= my_strdup(name,MYF(0))))
1004      {
1005 @@ -227,7 +380,7 @@
1006                     param->search_flag, not_used);
1007  }
1008
1009 -static void init_block(HP_BLOCK *block, uint reclength, ulong min_records,
1010 +static void init_block(HP_BLOCK *block, uint chunk_length, ulong min_records,
1011                        ulong max_records)
1012  {
1013    uint i,recbuffer,records_in_block;
1014 @@ -235,7 +388,12 @@
1015    max_records= max(min_records,max_records);
1016    if (!max_records)
1017      max_records= 1000;                 /* As good as quess as anything */
1018 -  recbuffer= (uint) (reclength + sizeof(uchar**) - 1) & ~(sizeof(uchar**) - 1);
1019 +  /*
1020 +    We want to start each chunk at 8 bytes boundary, round recbuffer to the
1021 +    next 8.
1022 +  */
1023 +  recbuffer= (uint) (chunk_length + sizeof(uchar**) - 1) &
1024 +    ~(sizeof(uchar**) - 1);
1025    records_in_block= max_records / 10;
1026    if (records_in_block < 10 && max_records)
1027      records_in_block= 10;
1028 --- a/storage/heap/hp_delete.c
1029 +++ b/storage/heap/hp_delete.c
1030 @@ -22,6 +22,8 @@
1031    uchar *pos;
1032    HP_SHARE *share=info->s;
1033    HP_KEYDEF *keydef, *end, *p_lastinx;
1034 +  uint rec_length, chunk_count;
1035 +
1036    DBUG_ENTER("heap_delete");
1037    DBUG_PRINT("enter",("info: 0x%lx  record: 0x%lx", (long) info, (long) record));
1038
1039 @@ -31,6 +33,8 @@
1040      DBUG_RETURN(my_errno);                     /* Record changed */
1041    share->changed=1;
1042
1043 +  rec_length = hp_get_encoded_data_length(share, record, &chunk_count);
1044 +
1045    if ( --(share->records) < share->blength >> 1) share->blength>>=1;
1046    pos=info->current_ptr;
1047
1048 @@ -43,10 +47,7 @@
1049    }
1050
1051    info->update=HA_STATE_DELETED;
1052 -  *((uchar**) pos)=share->del_link;
1053 -  share->del_link=pos;
1054 -  pos[share->reclength]=0;             /* Record deleted */
1055 -  share->deleted++;
1056 +  hp_free_chunks(&share->recordspace, pos);
1057    info->current_hash_ptr=0;
1058  #if !defined(DBUG_OFF) && defined(EXTRA_HEAP_DEBUG)
1059    DBUG_EXECUTE("check_heap",heap_check_heap(info, 0););
1060 @@ -75,7 +76,8 @@
1061      info->last_pos= NULL; /* For heap_rnext/heap_rprev */
1062
1063    custom_arg.keyseg= keyinfo->seg;
1064 -  custom_arg.key_length= hp_rb_make_key(keyinfo, info->recbuf, record, recpos);
1065 +  custom_arg.key_length= hp_rb_make_key(keyinfo, info->recbuf, record, recpos,
1066 +                                        FALSE);
1067    custom_arg.search_flag= SEARCH_SAME;
1068    old_allocated= keyinfo->rb_tree.allocated;
1069    res= tree_delete(&keyinfo->rb_tree, info->recbuf, custom_arg.key_length,
1070 @@ -112,6 +114,7 @@
1071    blength=share->blength;
1072    if (share->records+1 == blength)
1073      blength+= blength;
1074 +
1075    lastpos=hp_find_hash(&keyinfo->block,share->records);
1076    last_ptr=0;
1077
1078 --- /dev/null
1079 +++ b/storage/heap/hp_dspace.c
1080 @@ -0,0 +1,440 @@
1081 +/* Copyright (C) 2000-2002 MySQL AB
1082 +   Copyright (C) 2008 eBay, Inc
1083 +
1084 +   This program is free software; you can redistribute it and/or modify
1085 +   it under the terms of the GNU General Public License as published by
1086 +   the Free Software Foundation; version 2 of the License.
1087 +
1088 +   This program is distributed in the hope that it will be useful,
1089 +   but WITHOUT ANY WARRANTY; without even the implied warranty of
1090 +   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
1091 +   GNU General Public License for more details.
1092 +
1093 +   You should have received a copy of the GNU General Public License
1094 +   along with this program; if not, write to the Free Software
1095 +   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
1096 +
1097 +/*
1098 +  Implements various base dataspace-related functions - allocate, free, clear
1099 +*/
1100 +
1101 +#include "heapdef.h"
1102 +
1103 +
1104 +/*
1105 +  MySQL Heap tables keep data in arrays of fixed-size chunks.
1106 +  These chunks are organized into two groups of HP_BLOCK structures:
1107 +    - group1 contains indexes, with one HP_BLOCK per key
1108 +      (part of HP_KEYDEF)
1109 +    - group2 contains record data, with single HP_BLOCK
1110 +      for all records, referenced by HP_SHARE.recordspace.block
1111 +
1112 +  While columns used in index are usually small, other columns
1113 +  in the table may need to accomodate larger data. Typically,
1114 +  larger data is placed into VARCHAR or BLOB columns. With actual
1115 +  sizes varying, Heap Engine has to support variable-sized records
1116 +  in memory. Heap Engine implements the concept of dataspace
1117 +  (HP_DATASPACE), which incorporates HP_BLOCK for the record data,
1118 +  and adds more information for managing variable-sized records.
1119 +
1120 +  Variable-size records are stored in multiple "chunks",
1121 +  which means that a single record of data (database "row") can
1122 +  consist of multiple chunks organized into one "set". HP_BLOCK
1123 +  contains chunks. In variable-size format, one record
1124 +  is represented as one or many chunks, depending on the actual
1125 +  data, while in fixed-size mode, one record is always represented
1126 +  as one chunk. The index structures would always point to the first
1127 +  chunk in the chunkset.
1128 +
1129 +  At the time of table creation, Heap Engine attempts to find out if
1130 +  variable-size records are desired. A user can request
1131 +  variable-size records by providing either row_type=dynamic or
1132 +  key_block_size=NNN table create option. Heap Engine will check
1133 +  whether key_block_size provides enough space in the first chunk
1134 +  to keep all null bits and columns that are used in indexes.
1135 +  If key_block_size is too small, table creation will be aborted
1136 +  with an error. Heap Engine will revert to fixed-size allocation
1137 +  mode if key_block_size provides no memory benefits (if the
1138 +  fixed-size record would always be shorter then the first chunk
1139 +  in the chunkset with the specified key_block_size).
1140 +
1141 +  In order to improve index search performance, Heap Engine needs
1142 +  to keep all null flags and all columns used as keys inside
1143 +  the first chunk of a chunkset. In particular, this means that
1144 +  all columns used as keys should be defined first in the table
1145 +  creation SQL. The length of data used by null bits and key columns
1146 +  is stored as fixed_data_length inside HP_SHARE. fixed_data_length
1147 +  will extend past last key column if more fixed-length fields can
1148 +  fit into the first chunk.
1149 +
1150 +  Variable-size records are necessary only in the presence of
1151 +  variable-size columns. Heap Engine will be looking for BLOB
1152 +  columns or VARCHAR columns, which declare length of 32 or more. If
1153 +  no such columns are found, table will be switched to fixed-size
1154 +  format. You should always try to put such columns at the end of
1155 +  the table definition.
1156 +
1157 +  Whenever data is being inserted or updated in the table
1158 +  Heap Engine will calculate how many chunks are necessary.
1159 +  For insert operations, Heap Engine allocates new chunkset in
1160 +  the recordspace. For update operations it will modify length of
1161 +  the existing chunkset, unlinking unnecessary chunks at the end,
1162 +  or allocating and adding more if larger length is necessary.
1163 +
1164 +  When writing data to chunks or copying data back to record,
1165 +  fixed-size columns are copied in their full format. VARCHARs and
1166 +  BLOBs are copied based on their actual length. Any NULL values
1167 +  after fixed_data_length are skipped.
1168 +
1169 +  The allocation and contents of the actual chunks varies between
1170 +  fixed and variable-size modes. Total chunk length is always
1171 +  aligned to the next sizeof(uchar*). Here is the format of
1172 +  fixed-size chunk:
1173 +      uchar[] - sizeof=chunk_dataspace_length, but at least
1174 +                sizeof(uchar*) bytes. Keeps actual data or pointer
1175 +                to the next deleted chunk.
1176 +                chunk_dataspace_length equals to full record length
1177 +      uchar   - status field (1 means "in use", 0 means "deleted")
1178 +
1179 +  Variable-size chunk uses different format:
1180 +      uchar[] - sizeof=chunk_dataspace_length, but at least
1181 +                sizeof(uchar*) bytes. Keeps actual data or pointer
1182 +                to the next deleted chunk.
1183 +                chunk_dataspace_length is set according to table
1184 +                setup (key_block_size)
1185 +      uchar*  - pointer to the next chunk in this chunkset,
1186 +                or NULL for the last chunk
1187 +      uchar   - status field (1 means "first", 0 means "deleted",
1188 +                2 means "linked")
1189 +
1190 +  When allocating a new chunkset of N chunks, Heap Engine will try
1191 +  to allocate chunks one-by-one, linking them as they become
1192 +  allocated. Allocation of a single chunk will attempt to reuse
1193 +  a deleted (freed) chunk. If no free chunks are available,
1194 +  it will attempt to allocate a new area inside HP_BLOCK.
1195 +  Freeing chunks will place them at the front of free list
1196 +  referenced by del_link in HP_DATASPACE. The newly freed chunk
1197 +  will contain reference to the previously freed chunk in its first
1198 +  sizeof(uchar*) of the payload space.
1199 +
1200 +  Here is open issues:
1201 +    -  It is not very nice to require people to keep key columns
1202 +       at the beginning of the table creation SQL. There are three
1203 +       proposed resolutions:
1204 +       a. Leave it as is. It's a reasonable limitation
1205 +       b. Add new HA_KEEP_KEY_COLUMNS_TO_FRONT flag to handler.h and
1206 +          make table.cpp align columns when it creates the table
1207 +       c. Make HeapEngine reorder columns in the chunk data, so that
1208 +          key columns go first. Add parallel HA_KEYSEG structures
1209 +          to distinguish positions in record vs. positions in
1210 +          the first chunk. Copy all data field-by-field rather than
1211 +          using single memcpy unless DBA kept key columns to
1212 +          the beginning.
1213 +    -  heap_check_heap needs verify linked chunks, looking for
1214 +       issues such as orphans, cycles, and bad links. However,
1215 +       Heap Engine today does not do similar things even for
1216 +       free list.
1217 +    -  In a more sophisticated implementation, some space can
1218 +       be saved even with all fixed-size columns if many of them
1219 +       have NULL value, as long as these columns are not used
1220 +       in indexes
1221 +    -  In variable-size format status should be moved to lower
1222 +       bits of the "next" pointer. Pointer is always aligned
1223 +       to sizeof(byte*), which is at least 4, leaving 2 lower
1224 +       bits free. This will save 8 bytes per chunk
1225 +       on 64-bit platform.
1226 +    -  As we do not want to modify FRM format or to add new SQL
1227 +       keywords, KEY_BLOCK_SIZE option of "CREATE TABLE" is reused
1228 +       to specify block size for Heap Engine tables.
1229 +    -  since all key columns must fit in the first chunk, having keys
1230 +       on BLOB columns is currently impossible. This limitation is
1231 +       relatively easiy to remove in future.
1232 +*/
1233 +
1234 +static uchar *hp_allocate_one_chunk(HP_DATASPACE *info);
1235 +
1236 +
1237 +/**
1238 +  Clear a dataspace
1239 +
1240 +  Frees memory and zeros-out any relevant counters in the dataspace
1241 +
1242 +  @param  info  the dataspace to clear
1243 +*/
1244 +
1245 +void hp_clear_dataspace(HP_DATASPACE *info)
1246 +{
1247 +  if (info->block.levels)
1248 +  {
1249 +    hp_free_level(&info->block,info->block.levels,info->block.root,
1250 +                  (uchar *) 0);
1251 +  }
1252 +  info->block.levels= 0;
1253 +  info->del_chunk_count= info->chunk_count= 0;
1254 +  info->del_link= 0;
1255 +  info->total_data_length= 0;
1256 +}
1257 +
1258 +
1259 +/**
1260 +  Allocate or reallocate a chunkset in the dataspace
1261 +
1262 +  Attempts to allocate a new chunkset or change the size of an existing chunkset
1263 +
1264 +  @param  info            the hosting dataspace
1265 +  @param  chunk_count     the number of chunks that we expect as the result
1266 +  @param  existing_set    non-null value asks function to resize existing
1267 +                          chunkset, return value would point to this set
1268 +
1269 +  @return  Pointer to the first chunk in the new or updated chunkset, or NULL
1270 +           if unsuccessful
1271 +*/
1272 +
1273 +static uchar *hp_allocate_variable_chunkset(HP_DATASPACE *info,
1274 +                                           uint chunk_count,
1275 +                                           uchar *existing_set)
1276 +{
1277 +  int alloc_count= chunk_count, i;
1278 +  uchar *first_chunk= 0, *curr_chunk= 0, *prev_chunk= 0;
1279 +  uchar  *last_existing_chunk= 0;
1280 +
1281 +  DBUG_ASSERT(alloc_count);
1282 +
1283 +  if (existing_set)
1284 +  {
1285 +    first_chunk= existing_set;
1286 +
1287 +    curr_chunk= existing_set;
1288 +    while (curr_chunk && alloc_count)
1289 +    {
1290 +      prev_chunk= curr_chunk;
1291 +      curr_chunk= *((uchar **) (curr_chunk + info->offset_link));
1292 +      alloc_count--;
1293 +    }
1294 +
1295 +    if (!alloc_count)
1296 +    {
1297 +      if (curr_chunk)
1298 +      {
1299 +        /*
1300 +          We came through all chunks and there is more left, let's truncate the
1301 +          list.
1302 +        */
1303 +        *((uchar **) (prev_chunk + info->offset_link))= NULL;
1304 +        hp_free_chunks(info, curr_chunk);
1305 +      }
1306 +
1307 +      return first_chunk;
1308 +    }
1309 +
1310 +    last_existing_chunk= prev_chunk;
1311 +  }
1312 +
1313 +  /*
1314 +    We can reach this point only if we're allocating new chunkset or more chunks
1315 +    in existing set.
1316 +  */
1317 +
1318 +  for (i= 0; i < alloc_count; i++)
1319 +  {
1320 +    curr_chunk= hp_allocate_one_chunk(info);
1321 +    if (!curr_chunk)
1322 +    {
1323 +      /* no space in the current block */
1324 +
1325 +      if (last_existing_chunk)
1326 +      {
1327 +        /* Truncate whatever was added at the end of the existing chunkset */
1328 +        prev_chunk= last_existing_chunk;
1329 +        curr_chunk= *((uchar **)(prev_chunk + info->offset_link));
1330 +        *((uchar **)(prev_chunk + info->offset_link))= NULL;
1331 +        hp_free_chunks(info, curr_chunk);
1332 +      }
1333 +      else if (first_chunk)
1334 +      {
1335 +        /* free any chunks previously allocated */
1336 +        hp_free_chunks(info, first_chunk);
1337 +      }
1338 +
1339 +      return NULL;
1340 +    }
1341 +
1342 +    /* mark as if this chunk is last in the chunkset */
1343 +    *((uchar **) (curr_chunk + info->offset_link))= 0;
1344 +
1345 +    if (prev_chunk)
1346 +    {
1347 +      /* tie them into a linked list */
1348 +      *((uchar **) (prev_chunk + info->offset_link))= curr_chunk;
1349 +      /* Record linked from active */
1350 +      curr_chunk[info->offset_status]= CHUNK_STATUS_LINKED;
1351 +    }
1352 +    else
1353 +    {
1354 +      /* Record active */
1355 +      curr_chunk[info->offset_status]= CHUNK_STATUS_ACTIVE;
1356 +    }
1357 +
1358 +    if (!first_chunk)
1359 +    {
1360 +      first_chunk= curr_chunk;
1361 +    }
1362 +
1363 +    prev_chunk= curr_chunk;
1364 +}
1365 +
1366 +  return first_chunk;
1367 +}
1368 +
1369 +
1370 +/**
1371 +  Allocate a new chunkset in the dataspace
1372 +
1373 +  Attempts to allocate a new chunkset
1374 +
1375 +  @param  info            the hosting dataspace
1376 +  @param  chunk_count     the number of chunks that we expect as the result
1377 +
1378 +  @return  Pointer to the first chunk in the new or updated chunkset, or NULL if
1379 +           unsuccessful
1380 +*/
1381 +
1382 +uchar *hp_allocate_chunkset(HP_DATASPACE *info, uint chunk_count)
1383 +{
1384 +  uchar *result;
1385 +
1386 +  DBUG_ENTER("hp_allocate_chunks");
1387 +
1388 +  if (info->is_variable_size)
1389 +  {
1390 +    result = hp_allocate_variable_chunkset(info, chunk_count, NULL);
1391 +  }
1392 +  else
1393 +  {
1394 +    result= hp_allocate_one_chunk(info);
1395 +    if (result)
1396 +    {
1397 +      result[info->offset_status]= CHUNK_STATUS_ACTIVE;
1398 +    }
1399 +
1400 +    DBUG_RETURN(result);
1401 +  }
1402 +
1403 +  DBUG_RETURN(result);
1404 +}
1405 +
1406 +
1407 +/**
1408 +  Reallocate an existing chunkset in the dataspace
1409 +
1410 +  Attempts to change the size of an existing chunkset
1411 +
1412 +  @param  info            the hosting dataspace
1413 +  @param  chunk_count     the number of chunks that we expect as the result
1414 +  @param  pos             pointer to the existing chunkset
1415 +
1416 +  @return  Error code or zero if successful
1417 +*/
1418 +
1419 +int hp_reallocate_chunkset(HP_DATASPACE *info, uint chunk_count, uchar *pos)
1420 +{
1421 +  DBUG_ENTER("hp_reallocate_chunks");
1422 +
1423 +  if (!info->is_variable_size)
1424 +  {
1425 +    /* Update should never change chunk_count in fixed-size mode */
1426 +    my_errno= HA_ERR_WRONG_COMMAND;
1427 +    return my_errno;
1428 +  }
1429 +
1430 +  /* Reallocate never moves the first chunk */
1431 +  if (!hp_allocate_variable_chunkset(info, chunk_count, pos))
1432 +    DBUG_RETURN(my_errno);
1433 +
1434 +  DBUG_RETURN(0);
1435 +}
1436 +
1437 +
1438 +/**
1439 +  Allocate a single chunk in the dataspace
1440 +
1441 +  Attempts to allocate a new chunk or reuse one from deleted list
1442 +
1443 +  @param  info            the hosting dataspace
1444 +
1445 +  @return  Pointer to the chunk, or NULL if unsuccessful
1446 +*/
1447 +
1448 +static uchar *hp_allocate_one_chunk(HP_DATASPACE *info)
1449 +{
1450 +  uchar *curr_chunk;
1451 +  size_t length;
1452 +  ulong block_pos;
1453 +
1454 +  if (info->del_link)
1455 +  {
1456 +    curr_chunk= info->del_link;
1457 +    info->del_link= *((uchar **) curr_chunk);
1458 +    info->del_chunk_count--;
1459 +
1460 +    DBUG_PRINT("hp_allocate_one_chunk",
1461 +               ("Used old position: 0x%lx",(long) curr_chunk));
1462 +    return curr_chunk;
1463 +  }
1464 +
1465 +  block_pos= (info->chunk_count % info->block.records_in_block);
1466 +  if (!block_pos)
1467 +  {
1468 +    if (hp_get_new_block(&info->block, &length))
1469 +    {
1470 +      /* no space in the current block */
1471 +      return NULL;
1472 +    }
1473 +
1474 +    info->total_data_length+= length;
1475 +  }
1476 +
1477 +  info->chunk_count++;
1478 +  curr_chunk= ((uchar *) info->block.level_info[0].last_blocks +
1479 +               block_pos * info->block.recbuffer);
1480 +
1481 +  DBUG_PRINT("hp_allocate_one_chunk",
1482 +             ("Used new position: 0x%lx", (long) curr_chunk));
1483 +
1484 +  return curr_chunk;
1485 +}
1486 +
1487 +
1488 +/**
1489 +  Free a list of chunks
1490 +
1491 +  Reclaims all chunks linked by the pointer,
1492 +  which could be the whole chunkset or a part of an existing chunkset
1493 +
1494 +  @param  info            the hosting dataspace
1495 +  @param  pos             pointer to the head of the chunkset
1496 +*/
1497 +
1498 +void hp_free_chunks(HP_DATASPACE *info, uchar *pos)
1499 +{
1500 +  uchar *curr_chunk= pos;
1501 +
1502 +  while (curr_chunk)
1503 +  {
1504 +    info->del_chunk_count++;
1505 +    *((uchar **) curr_chunk)= info->del_link;
1506 +    info->del_link= curr_chunk;
1507 +
1508 +    curr_chunk[info->offset_status]= CHUNK_STATUS_DELETED;
1509 +
1510 +    DBUG_PRINT("hp_free_chunks",("Freed position: 0x%lx", (long) curr_chunk));
1511 +
1512 +    if (!info->is_variable_size)
1513 +    {
1514 +      break;
1515 +    }
1516 +
1517 +    /* Delete next chunk in this chunkset */
1518 +    curr_chunk= *((uchar **)(curr_chunk + info->offset_link));
1519 +  }
1520 +}
1521 --- a/storage/heap/hp_extra.c
1522 +++ b/storage/heap/hp_extra.c
1523 @@ -56,7 +56,6 @@
1524    info->current_record= (ulong) ~0L;
1525    info->current_hash_ptr=0;
1526    info->update=0;
1527 -  info->next_block=0;
1528    return 0;
1529  }
1530
1531 --- a/storage/heap/hp_hash.c
1532 +++ b/storage/heap/hp_hash.c
1533 @@ -336,16 +336,26 @@
1534      {
1535        CHARSET_INFO *cs= seg->charset;
1536        uint pack_length= seg->bit_start;
1537 -      uint length= (pack_length == 1 ? (uint) *(uchar*) pos : uint2korr(pos));
1538 +      uint length= hp_calc_blob_length(pack_length, pos);
1539 +
1540 +      if (seg->flag & HA_BLOB_PART)
1541 +      {
1542 +        memcpy(&pos, pos + pack_length, sizeof(char *));
1543 +      }
1544 +      else
1545 +      {
1546 +        pos+= pack_length;
1547 +      }
1548 +
1549        if (cs->mbmaxlen > 1)
1550        {
1551          uint char_length;
1552 -        char_length= my_charpos(cs, pos + pack_length,
1553 -                                pos + pack_length + length,
1554 +        char_length= my_charpos(cs, pos,
1555 +                                pos + length,
1556                                  seg->length/cs->mbmaxlen);
1557          set_if_smaller(length, char_length);
1558        }
1559 -      cs->coll->hash_sort(cs, pos+pack_length, length, &nr, &nr2);
1560 +      cs->coll->hash_sort(cs, pos, length, &nr, &nr2);
1561      }
1562      else
1563      {
1564 @@ -545,18 +555,18 @@
1565        uint char_length1, char_length2;
1566        uint pack_length= seg->bit_start;
1567        CHARSET_INFO *cs= seg->charset;
1568 -      if (pack_length == 1)
1569 -      {
1570 -        char_length1= (uint) *(uchar*) pos1++;
1571 -        char_length2= (uint) *(uchar*) pos2++;
1572 -      }
1573 -      else
1574 +
1575 +      char_length1= hp_calc_blob_length(pack_length, pos1);
1576 +      char_length2= hp_calc_blob_length(pack_length, pos2);
1577 +      pos1+= pack_length;
1578 +      pos2+= pack_length;
1579 +
1580 +      if (seg->flag & HA_BLOB_PART)
1581        {
1582 -        char_length1= uint2korr(pos1);
1583 -        char_length2= uint2korr(pos2);
1584 -        pos1+= 2;
1585 -        pos2+= 2;
1586 +        memcpy(&pos1, pos1, sizeof(char *));
1587 +        memcpy(&pos2, pos2, sizeof(char *));
1588        }
1589 +
1590        if (cs->mbmaxlen > 1)
1591        {
1592          uint safe_length1= char_length1;
1593 @@ -668,6 +678,34 @@
1594  }
1595
1596
1597 +/**
1598 +   Returns a BLOB length stored in the specified number of bytes at the
1599 +   specified location.
1600 +
1601 +   @param length       the number of bytes used to store length
1602 +   @param pos          pointer to length bytes
1603 +
1604 +   @return  Length of BLOB data.
1605 +*/
1606 +
1607 +uint hp_calc_blob_length(uint bytes, const uchar *pos)
1608 +{
1609 +  switch (bytes) {
1610 +  case 1:
1611 +    return (uint) *pos;
1612 +  case 2:
1613 +    return uint2korr(pos);
1614 +  case 3:
1615 +    return uint3korr(pos);
1616 +  case 4:
1617 +    return uint4korr(pos);
1618 +  default:
1619 +    break;
1620 +  }
1621 +
1622 +  return 0; /* Impossible */
1623 +}
1624 +
1625         /* Copy a key from a record to a keybuffer */
1626
1627  void hp_make_key(HP_KEYDEF *keydef, uchar *key, const uchar *rec)
1628 @@ -678,18 +716,37 @@
1629    {
1630      CHARSET_INFO *cs= seg->charset;
1631      uint char_length= seg->length;
1632 -    uchar *pos= (uchar*) rec + seg->start;
1633 +    const uchar *pos= rec + seg->start;
1634      if (seg->null_bit)
1635        *key++= test(rec[seg->null_pos] & seg->null_bit);
1636 -    if (cs->mbmaxlen > 1)
1637 +
1638 +    if (seg->flag & HA_BLOB_PART)
1639      {
1640 -      char_length= my_charpos(cs, pos, pos + seg->length,
1641 -                              char_length / cs->mbmaxlen);
1642 -      set_if_smaller(char_length, seg->length); /* QQ: ok to remove? */
1643 +      uint tmp_length= hp_calc_blob_length(seg->bit_start, pos);
1644 +      uint length= min(seg->length, tmp_length);
1645 +
1646 +      memcpy(&pos, rec + seg->bit_start, sizeof(char *));
1647 +      if (cs->mbmaxlen > 1)
1648 +      {
1649 +        char_length= my_charpos(cs, pos, pos + seg->length,
1650 +                                char_length / cs->mbmaxlen);
1651 +        set_if_smaller(char_length, length); /* QQ: ok to remove? */
1652 +      }
1653 +      store_key_length_inc(key, char_length);
1654      }
1655 -    if (seg->type == HA_KEYTYPE_VARTEXT1)
1656 -      char_length+= seg->bit_start;             /* Copy also length */
1657 -    memcpy(key,rec+seg->start,(size_t) char_length);
1658 +    else
1659 +    {
1660 +      if (cs->mbmaxlen > 1)
1661 +      {
1662 +        char_length= my_charpos(cs, pos, pos + seg->length,
1663 +                                char_length / cs->mbmaxlen);
1664 +        set_if_smaller(char_length, seg->length); /* QQ: ok to remove? */
1665 +      }
1666 +      if (seg->type == HA_KEYTYPE_VARTEXT1)
1667 +        char_length+= seg->bit_start;             /* Copy also length */
1668 +    }
1669 +
1670 +    memcpy(key, pos, (size_t) char_length);
1671      key+= char_length;
1672    }
1673  }
1674 @@ -702,8 +759,8 @@
1675    } while(0)
1676
1677
1678 -uint hp_rb_make_key(HP_KEYDEF *keydef, uchar *key,
1679 -                   const uchar *rec, uchar *recpos)
1680 +uint hp_rb_make_key(HP_KEYDEF *keydef, uchar *key,
1681 +                    const uchar *rec, uchar *recpos, my_bool packed)
1682  {
1683    uchar *start_key= key;
1684    HA_KEYSEG *seg, *endseg;
1685 @@ -772,6 +829,29 @@
1686        key+= char_length;
1687        continue;
1688      }
1689 +    else if (seg->flag & HA_BLOB_PART)
1690 +    {
1691 +      uchar *pos=      (uchar*) rec + seg->start;
1692 +      uint tmp_length= hp_calc_blob_length(seg->bit_start, pos);
1693 +      uint length= min(seg->length, tmp_length);
1694 +      CHARSET_INFO *cs= seg->charset;
1695 +      char_length= seg->length / cs->mbmaxlen;
1696 +
1697 +      /* check_one_rb_key() calls hp_rb_make_key() for already packed records */
1698 +      if (!packed)
1699 +      {
1700 +        memcpy(&pos, pos + seg->bit_start, sizeof(char *));
1701 +      }
1702 +      else
1703 +      {
1704 +        pos+= seg->bit_start;
1705 +      }
1706 +      FIX_LENGTH(cs, pos, length, char_length);
1707 +      store_key_length_inc(key, char_length);
1708 +      memcpy(key, pos, (size_t) char_length);
1709 +      key+= char_length;
1710 +      continue;
1711 +    }
1712
1713      char_length= seg->length;
1714      if (seg->charset->mbmaxlen > 1)
1715 --- a/storage/heap/hp_info.c
1716 +++ b/storage/heap/hp_info.c
1717 @@ -47,9 +47,22 @@
1718  {
1719    DBUG_ENTER("heap_info");
1720    x->records         = info->s->records;
1721 -  x->deleted         = info->s->deleted;
1722 -  x->reclength       = info->s->reclength;
1723 -  x->data_length     = info->s->data_length;
1724 +  x->deleted         = info->s->recordspace.del_chunk_count;
1725 +
1726 +  if (info->s->recordspace.is_variable_size)
1727 +  {
1728 +    if (info->s->records)
1729 +      x->reclength   = (uint) (info->s->recordspace.total_data_length /
1730 +                               (ulonglong) info->s->records);
1731 +    else
1732 +      x->reclength   = info->s->recordspace.chunk_length;
1733 +  }
1734 +  else
1735 +  {
1736 +    x->reclength     = info->s->recordspace.chunk_dataspace_length;
1737 +  }
1738 +
1739 +  x->data_length     = info->s->recordspace.total_data_length;
1740    x->index_length    = info->s->index_length;
1741    x->max_records     = info->s->max_records;
1742    x->errkey          = info->errkey;
1743 --- a/storage/heap/hp_open.c
1744 +++ b/storage/heap/hp_open.c
1745 @@ -47,9 +47,9 @@
1746  #ifndef DBUG_OFF
1747    info->opt_flag= READ_CHECK_USED;             /* Check when changing */
1748  #endif
1749 -  DBUG_PRINT("exit",("heap: 0x%lx  reclength: %d  records_in_block: %d",
1750 -                    (long) info, share->reclength,
1751 -                     share->block.records_in_block));
1752 +  DBUG_PRINT("exit",("heap: 0x%lx  chunk_length: %d  records_in_block: %d",
1753 +                     (long) info, share->recordspace.chunk_length,
1754 +                     share->recordspace.block.records_in_block));
1755    DBUG_RETURN(info);
1756  }
1757
1758 --- /dev/null
1759 +++ b/storage/heap/hp_record.c
1760 @@ -0,0 +1,498 @@
1761 +/* Copyright (C) 2000-2002 MySQL AB
1762 +   Copyright (C) 2008 eBay, Inc
1763 +
1764 +   This program is free software; you can redistribute it and/or modify
1765 +   it under the terms of the GNU General Public License as published by
1766 +   the Free Software Foundation; version 2 of the License.
1767 +
1768 +   This program is distributed in the hope that it will be useful,
1769 +   but WITHOUT ANY WARRANTY; without even the implied warranty of
1770 +   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
1771 +   GNU General Public License for more details.
1772 +
1773 +   You should have received a copy of the GNU General Public License
1774 +   along with this program; if not, write to the Free Software
1775 +   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
1776 +
1777 +/*
1778 +  Implements various base record-related functions, such as encode and decode
1779 +  into chunks.
1780 +*/
1781 +
1782 +#include "heapdef.h"
1783 +#include <mysql_com.h>
1784 +
1785 +/**
1786 +  Calculate size of the record for the purpose of storing in chunks
1787 +
1788 +  Walk through the fields of the record and calculates the exact space
1789 +  needed in chunks as well the the total chunk count
1790 +
1791 +  @param       info         the hosting table
1792 +  @param       record       the record in standard unpacked format
1793 +  @param[out]  chunk_count  the number of chunks needed for this record
1794 +
1795 +  @return The size of the required storage in bytes
1796 +*/
1797 +
1798 +uint hp_get_encoded_data_length(HP_SHARE *info, const uchar *record,
1799 +                                uint *chunk_count)
1800 +{
1801 +  uint i, dst_offset;
1802 +
1803 +  dst_offset= info->fixed_data_length;
1804 +
1805 +  if (!info->recordspace.is_variable_size)
1806 +  {
1807 +    /* Nothing more to copy */
1808 +    *chunk_count= 1;
1809 +    return dst_offset;
1810 +  }
1811 +
1812 +  for (i= info->fixed_column_count; i < info->column_count; i++)
1813 +  {
1814 +    uint src_offset, length;
1815 +
1816 +    HP_COLUMNDEF *column= info->column_defs + i;
1817 +
1818 +    if (column->null_bit)
1819 +    {
1820 +      if (record[column->null_pos] & column->null_bit)
1821 +      {
1822 +        /* Skip all NULL values */
1823 +        continue;
1824 +      }
1825 +    }
1826 +
1827 +    src_offset= column->offset;
1828 +    if (column->type == MYSQL_TYPE_VARCHAR)
1829 +    {
1830 +      uint pack_length;
1831 +
1832 +      /* >= 5.0.3 true VARCHAR */
1833 +
1834 +      pack_length= column->length_bytes;
1835 +      length= pack_length + (pack_length == 1 ?
1836 +                             (uint) *(uchar *) (record + src_offset) :
1837 +                             uint2korr(record + src_offset));
1838 +    }
1839 +    else if (column->type == MYSQL_TYPE_BLOB)
1840 +    {
1841 +      uint pack_length= column->length_bytes;
1842 +
1843 +      length= pack_length + hp_calc_blob_length(pack_length,
1844 +                                                record + src_offset);
1845 +    }
1846 +    else
1847 +    {
1848 +      length= column->length;
1849 +    }
1850 +
1851 +    dst_offset+= length;
1852 +  }
1853 +
1854 +  *chunk_count= get_chunk_count(&info->recordspace, dst_offset);
1855 +
1856 +  return dst_offset;
1857 +}
1858 +
1859 +
1860 +#if !defined(DBUG_OFF) && defined(EXTRA_HEAP_DEBUG)
1861 +static void dump_chunk(HP_SHARE *info, const uchar *curr_chunk)
1862 +{
1863 +  uint i;
1864 +  fprintf(stdout, "Chunk dump at 0x%lx: ", (long) curr_chunk);
1865 +  for (i= 0; i < info->recordspace.chunk_dataspace_length; i++)
1866 +  {
1867 +    uint b= *((uchar *)(curr_chunk + i));
1868 +    if (b < 0x10)
1869 +    {
1870 +      fprintf(stdout, "0");
1871 +    }
1872 +    fprintf(stdout, "%lx ", (long) b);
1873 +  }
1874 +  fprintf(stdout, ". Next = 0x%lx, Status = %d\n",
1875 +          (long) (*((uchar **) (curr_chunk + info->recordspace.offset_link))),
1876 +          (uint) (*((uchar *) (curr_chunk + info->recordspace.offset_status))));
1877 +}
1878 +#endif
1879 +
1880 +/**
1881 +  Stores data from packed field into the preallocated chunkset,
1882 +  or performs data comparison
1883 +
1884 +  @param  info         the hosting table
1885 +  @param  data         the field data in packed format
1886 +  @param  length       the field data length
1887 +  @param  pos_ptr      the target chunkset
1888 +  @param  off_ptr      the pointer to the offset within the current chunkset
1889 +  @param  is_compare   flag indicating whether we should compare data or store
1890 +                       it
1891 +
1892 +  @return  Status of comparison
1893 +    @retval  non-zero  if comparison found data differences
1894 +    @retval  zero      otherwise
1895 +*/
1896 +
1897 +static inline uint
1898 +hp_process_field_data_to_chunkset(HP_SHARE *info, const uchar *data,
1899 +                                  uint length, uchar **pos_ptr, uint *off_ptr,
1900 +                                  uint is_compare)
1901 +{
1902 +  uint to_copy;
1903 +  uchar *curr_chunk= *pos_ptr;
1904 +  uint dst_offset= *off_ptr;
1905 +  uint rc= 1;
1906 +
1907 +  while (length > 0)
1908 +  {
1909 +
1910 +    to_copy= info->recordspace.chunk_dataspace_length - dst_offset;
1911 +    if (to_copy == 0)
1912 +    {
1913 +      /* Jump to the next chunk */
1914 +#if !defined(DBUG_OFF) && defined(EXTRA_HEAP_DEBUG)
1915 +      dump_chunk(info, curr_chunk);
1916 +#endif
1917 +      curr_chunk= *((uchar **) (curr_chunk + info->recordspace.offset_link));
1918 +      dst_offset= 0;
1919 +      continue;
1920 +    }
1921 +
1922 +    to_copy= min(length, to_copy);
1923 +
1924 +    if (is_compare)
1925 +    {
1926 +      if (memcmp(curr_chunk + dst_offset, data, (size_t) to_copy))
1927 +      {
1928 +        goto end;
1929 +      }
1930 +    }
1931 +    else
1932 +    {
1933 +      memcpy(curr_chunk + dst_offset, data, (size_t) to_copy);
1934 +    }
1935 +
1936 +    data+= to_copy;
1937 +    dst_offset+= to_copy;
1938 +    length-= to_copy;
1939 +  }
1940 +
1941 +  rc= 0;
1942 +
1943 +end:
1944 +  *pos_ptr= curr_chunk;
1945 +  *off_ptr= dst_offset;
1946 +
1947 +  return rc;
1948 +}
1949 +
1950 +/**
1951 +  Encodes or compares record
1952 +
1953 +  Copies data from original unpacked record into the preallocated chunkset,
1954 +  or performs data comparison
1955 +
1956 +  @param  info         the hosting table
1957 +  @param  record       the record in standard unpacked format
1958 +  @param  pos          the target chunkset
1959 +  @param  is_compare   flag indicating whether we should compare data or store
1960 +                       it
1961 +
1962 +  @return  Status of comparison
1963 +    @retval  non-zero  if comparison fond data differences
1964 +    @retval  zero      otherwise
1965 +*/
1966 +
1967 +uint hp_process_record_data_to_chunkset(HP_SHARE *info, const uchar *record,
1968 +                                        uchar *pos, uint is_compare)
1969 +{
1970 +  uint i, dst_offset;
1971 +  uchar *curr_chunk= pos;
1972 +
1973 +  if (is_compare)
1974 +  {
1975 +    if (memcmp(curr_chunk, record, (size_t) info->fixed_data_length))
1976 +    {
1977 +      return 1;
1978 +    }
1979 +  }
1980 +  else
1981 +  {
1982 +    memcpy(curr_chunk, record, (size_t) info->fixed_data_length);
1983 +  }
1984 +
1985 +  if (!info->recordspace.is_variable_size)
1986 +  {
1987 +    /* Nothing more to copy */
1988 +    return 0;
1989 +  }
1990 +
1991 +  dst_offset= info->fixed_data_length;
1992 +
1993 +  for (i= info->fixed_column_count; i < info->column_count; i++)
1994 +  {
1995 +    uint length;
1996 +    const uchar *data;
1997 +
1998 +    HP_COLUMNDEF *column= info->column_defs + i;
1999 +
2000 +    if (column->null_bit)
2001 +    {
2002 +      if (record[column->null_pos] & column->null_bit)
2003 +      {
2004 +        /* Skip all NULL values */
2005 +        continue;
2006 +      }
2007 +    }
2008 +
2009 +    data= record + column->offset;
2010 +    if (column->type == MYSQL_TYPE_VARCHAR)
2011 +    {
2012 +      uint pack_length;
2013 +
2014 +      /* >= 5.0.3 true VARCHAR */
2015 +
2016 +      /* Make sure to copy length indicator and actuals string bytes */
2017 +      pack_length= column->length_bytes;
2018 +      length= pack_length + (pack_length == 1 ? (uint) *data : uint2korr(data));
2019 +    }
2020 +    else if (column->type == MYSQL_TYPE_BLOB)
2021 +    {
2022 +      uint pack_length;
2023 +
2024 +      pack_length= column->length_bytes;
2025 +      /* Just want to store the length, so not interested in the return code */
2026 +      (void) hp_process_field_data_to_chunkset(info, data, pack_length,
2027 +                                               &curr_chunk, &dst_offset, 0);
2028 +      length= hp_calc_blob_length(pack_length, data);
2029 +      memcpy(&data, data + pack_length, sizeof(char *));
2030 +    }
2031 +    else
2032 +    {
2033 +      length= column->length;
2034 +    }
2035 +
2036 +    if (hp_process_field_data_to_chunkset(info, data, length, &curr_chunk,
2037 +                                          &dst_offset, is_compare))
2038 +    {
2039 +      return 1;
2040 +    }
2041 +  }
2042 +
2043 +#if !defined(DBUG_OFF) && defined(EXTRA_HEAP_DEBUG)
2044 +  dump_chunk(info, curr_chunk);
2045 +#endif
2046 +
2047 +  return 0;
2048 +}
2049 +
2050 +
2051 +/**
2052 +  Stores record in the heap table chunks
2053 +
2054 +  Copies data from original unpacked record into the preallocated chunkset
2055 +
2056 +  @param  info         the hosting table
2057 +  @param  record       the record in standard unpacked format
2058 +  @param  pos          the target chunkset
2059 +*/
2060 +
2061 +void hp_copy_record_data_to_chunkset(HP_SHARE *info, const uchar *record,
2062 +                                     uchar *pos)
2063 +{
2064 +  DBUG_ENTER("hp_copy_record_data_to_chunks");
2065 +
2066 +  hp_process_record_data_to_chunkset(info, record, pos, 0);
2067 +
2068 +  DBUG_VOID_RETURN;
2069 +}
2070 +
2071 +
2072 +/*
2073 +  Macro to switch curr_chunk to the next chunk in the chunkset and reset
2074 +  src_offset.
2075 +*/
2076 +#if !defined(DBUG_OFF) && defined(EXTRA_HEAP_DEBUG)
2077 +#define SWITCH_TO_NEXT_CHUNK_FOR_READ(share, curr_chunk, src_offset)     \
2078 +  {                                                                     \
2079 +    curr_chunk= *((uchar**) (curr_chunk + share->recordspace.offset_link)); \
2080 +    src_offset= 0;                                                      \
2081 +    dump_chunk(share, curr_chunk);                                       \
2082 +  }
2083 +#else
2084 +#define SWITCH_TO_NEXT_CHUNK_FOR_READ(share, curr_chunk, src_offset)     \
2085 +  {                                                                     \
2086 +    curr_chunk= *((uchar**) (curr_chunk + share->recordspace.offset_link)); \
2087 +    src_offset= 0;                                                      \
2088 +  }
2089 +#endif
2090 +
2091 +/**
2092 +  Copies record data from storage to unpacked record format
2093 +
2094 +  Copies data from chunkset into its original unpacked record
2095 +
2096 +  @param       info         the hosting table
2097 +  @param[out]  record       the target record in standard unpacked format
2098 +  @param       pos          the source chunkset
2099 +
2100 +  @return                   Status of conversion
2101 +    @retval   0             success
2102 +    @retval   1             out of memory
2103 +*/
2104 +
2105 +int hp_extract_record(HP_INFO *info, uchar *record, const uchar *pos)
2106 +{
2107 +  uint i, src_offset;
2108 +  const uchar *curr_chunk= pos;
2109 +  HP_SHARE *share= info->s;
2110 +  uint *rec_offsets= NULL;
2111 +  uint *buf_offsets= NULL;
2112 +  uint nblobs= 0;
2113 +  uint init_offset= share->blobs * sizeof(uint) * 2;
2114 +
2115 +  DBUG_ENTER("hp_extract_record");
2116 +
2117 +#if !defined(DBUG_OFF) && defined(EXTRA_HEAP_DEBUG)
2118 +  if (share->recordspace.is_variable_size)
2119 +  {
2120 +    dump_chunk(share, curr_chunk);
2121 +  }
2122 +#endif
2123 +
2124 +  memcpy(record, curr_chunk, (size_t) share->fixed_data_length);
2125 +
2126 +  if (!share->recordspace.is_variable_size)
2127 +  {
2128 +    /* Nothing more to copy */
2129 +    DBUG_RETURN(0);
2130 +  }
2131 +
2132 +  /* Reserve space for rec_offsets and buf_offsets.*/
2133 +  info->blob_offset= init_offset;
2134 +  src_offset= share->fixed_data_length;
2135 +
2136 +  for (i= share->fixed_column_count; i < share->column_count; i++)
2137 +  {
2138 +    uint length, is_null= 0;
2139 +    uchar *to;
2140 +
2141 +    HP_COLUMNDEF *column= share->column_defs + i;
2142 +
2143 +    if (column->null_bit)
2144 +    {
2145 +      if (record[column->null_pos] & column->null_bit)
2146 +      {
2147 +        is_null= 1;
2148 +      }
2149 +    }
2150 +
2151 +    if (is_null)
2152 +    {
2153 +      /* TODO: is memset really needed? */
2154 +      memset(record + column->offset, 0, column->length);
2155 +      continue;
2156 +    }
2157 +
2158 +    to= record + column->offset;
2159 +    if (column->type == MYSQL_TYPE_VARCHAR || column->type == MYSQL_TYPE_BLOB)
2160 +    {
2161 +      uint pack_length, i;
2162 +      uchar *tmp= to;
2163 +
2164 +      pack_length= column->length_bytes;
2165 +
2166 +      for (i= 0; i < pack_length; i++)
2167 +      {
2168 +        if (src_offset == share->recordspace.chunk_dataspace_length)
2169 +        {
2170 +          SWITCH_TO_NEXT_CHUNK_FOR_READ(share, curr_chunk, src_offset);
2171 +        }
2172 +        *to++= curr_chunk[src_offset++];
2173 +      }
2174 +      /*
2175 +        We copy byte-by-byte and then use hp_calc_blob_length to combine bytes
2176 +        in the right order.
2177 +      */
2178 +      length= hp_calc_blob_length(pack_length, tmp);
2179 +
2180 +      if (column->type == MYSQL_TYPE_BLOB && length == 0)
2181 +      {
2182 +        /*
2183 +          Store a zero pointer for zero-length BLOBs because the server
2184 +          relies on that (see Field_blob::val_*().
2185 +        */
2186 +        *(uchar **) to= 0;
2187 +      }
2188 +      else if (column->type == MYSQL_TYPE_BLOB && length > 0)
2189 +      {
2190 +        uint newsize= info->blob_offset + length;
2191 +
2192 +        DBUG_ASSERT(share->blobs > 0);
2193 +        /*
2194 +          Make sure we have enough space in blob_buffer and store the pointer
2195 +          to this blob in record.
2196 +        */
2197 +        if (info->blob_size < newsize)
2198 +        {
2199 +          uchar *ptr;
2200 +          ptr= my_realloc(info->blob_buffer, newsize, MYF(MY_ALLOW_ZERO_PTR));
2201 +          if (ptr == NULL)
2202 +          {
2203 +            DBUG_RETURN(1);
2204 +          }
2205 +
2206 +          if (info->blob_buffer == NULL)
2207 +          {
2208 +            memset(ptr, 0, init_offset);
2209 +          }
2210 +          info->blob_buffer= ptr;
2211 +          info->blob_size= newsize;
2212 +        }
2213 +
2214 +        rec_offsets= (uint *) info->blob_buffer;
2215 +        buf_offsets= rec_offsets + share->blobs;
2216 +
2217 +        rec_offsets[nblobs]= (uint) (to - record);
2218 +        buf_offsets[nblobs]= info->blob_offset;
2219 +        nblobs++;
2220 +
2221 +        /* Change 'to' so blob data is copied into blob_buffer */
2222 +        to= info->blob_buffer + info->blob_offset;
2223 +        info->blob_offset= newsize;
2224 +      }
2225 +    }
2226 +    else
2227 +    {
2228 +      length= column->length;
2229 +    }
2230 +
2231 +    while (length > 0)
2232 +    {
2233 +      uint to_copy;
2234 +
2235 +      to_copy= share->recordspace.chunk_dataspace_length - src_offset;
2236 +      if (to_copy == 0)
2237 +      {
2238 +        SWITCH_TO_NEXT_CHUNK_FOR_READ(share, curr_chunk, src_offset);
2239 +        to_copy= share->recordspace.chunk_dataspace_length;
2240 +      }
2241 +
2242 +      to_copy= min(length, to_copy);
2243 +
2244 +      memcpy(to, curr_chunk + src_offset, (size_t) to_copy);
2245 +      src_offset+= to_copy;
2246 +      to+= to_copy;
2247 +      length-= to_copy;
2248 +    }
2249 +  }
2250 +
2251 +  /* Store pointers to blob data in record */
2252 +  for (i= 0; i < nblobs; i++)
2253 +  {
2254 +    *(uchar **) (record + rec_offsets[i]) = info->blob_buffer + buf_offsets[i];
2255 +  }
2256 +
2257 +  DBUG_RETURN(0);
2258 +}
2259 --- a/storage/heap/hp_rfirst.c
2260 +++ b/storage/heap/hp_rfirst.c
2261 @@ -34,7 +34,10 @@
2262        memcpy(&pos, pos + (*keyinfo->get_key_length)(keyinfo, pos),
2263              sizeof(uchar*));
2264        info->current_ptr = pos;
2265 -      memcpy(record, pos, (size_t)share->reclength);
2266 +      if (hp_extract_record(info, record, pos))
2267 +      {
2268 +        DBUG_RETURN(my_errno);
2269 +      }
2270        /*
2271          If we're performing index_first on a table that was taken from
2272          table cache, info->lastkey_len is initialized to previous query.
2273 --- a/storage/heap/hp_rkey.c
2274 +++ b/storage/heap/hp_rkey.c
2275 @@ -67,7 +67,10 @@
2276      if (!(keyinfo->flag & HA_NOSAME))
2277        memcpy(info->lastkey, key, (size_t) keyinfo->length);
2278    }
2279 -  memcpy(record, pos, (size_t) share->reclength);
2280 +  if (hp_extract_record(info, record, pos))
2281 +  {
2282 +    DBUG_RETURN(my_errno);
2283 +  }
2284    info->update= HA_STATE_AKTIV;
2285    DBUG_RETURN(0);
2286  }
2287 --- a/storage/heap/hp_rlast.c
2288 +++ b/storage/heap/hp_rlast.c
2289 @@ -35,7 +35,10 @@
2290        memcpy(&pos, pos + (*keyinfo->get_key_length)(keyinfo, pos),
2291              sizeof(uchar*));
2292        info->current_ptr = pos;
2293 -      memcpy(record, pos, (size_t)share->reclength);
2294 +      if (hp_extract_record(info, record, pos))
2295 +      {
2296 +        DBUG_RETURN(my_errno);
2297 +      }
2298        info->update = HA_STATE_AKTIV;
2299      }
2300      else
2301 --- a/storage/heap/hp_rnext.c
2302 +++ b/storage/heap/hp_rnext.c
2303 @@ -109,7 +109,10 @@
2304        my_errno=HA_ERR_END_OF_FILE;
2305      DBUG_RETURN(my_errno);
2306    }
2307 -  memcpy(record,pos,(size_t) share->reclength);
2308 +  if (hp_extract_record(info, record, pos))
2309 +  {
2310 +    DBUG_RETURN(my_errno);
2311 +  }
2312    info->update=HA_STATE_AKTIV | HA_STATE_NEXT_FOUND;
2313    DBUG_RETURN(0);
2314  }
2315 --- a/storage/heap/hp_rprev.c
2316 +++ b/storage/heap/hp_rprev.c
2317 @@ -77,7 +77,10 @@
2318        my_errno=HA_ERR_END_OF_FILE;
2319      DBUG_RETURN(my_errno);
2320    }
2321 -  memcpy(record,pos,(size_t) share->reclength);
2322 +  if (hp_extract_record(info, record, pos))
2323 +  {
2324 +    DBUG_RETURN(my_errno);
2325 +  }
2326    info->update=HA_STATE_AKTIV | HA_STATE_PREV_FOUND;
2327    DBUG_RETURN(0);
2328  }
2329 --- a/storage/heap/hp_rrnd.c
2330 +++ b/storage/heap/hp_rrnd.c
2331 @@ -36,13 +36,18 @@
2332      info->update= 0;
2333      DBUG_RETURN(my_errno= HA_ERR_END_OF_FILE);
2334    }
2335 -  if (!info->current_ptr[share->reclength])
2336 +  if (get_chunk_status(&share->recordspace, info->current_ptr) !=
2337 +      CHUNK_STATUS_ACTIVE)
2338    {
2339 +    /* treat deleted and linked chunks as deleted */
2340      info->update= HA_STATE_PREV_FOUND | HA_STATE_NEXT_FOUND;
2341      DBUG_RETURN(my_errno=HA_ERR_RECORD_DELETED);
2342    }
2343    info->update=HA_STATE_PREV_FOUND | HA_STATE_NEXT_FOUND | HA_STATE_AKTIV;
2344 -  memcpy(record,info->current_ptr,(size_t) share->reclength);
2345 +  if (hp_extract_record(info, record, info->current_ptr))
2346 +  {
2347 +    DBUG_RETURN(my_errno);
2348 +  }
2349    DBUG_PRINT("exit", ("found record at 0x%lx", (long) info->current_ptr));
2350    info->current_hash_ptr=0;                    /* Can't use rnext */
2351    DBUG_RETURN(0);
2352 @@ -70,17 +75,17 @@
2353    {
2354      pos= ++info->current_record;
2355      if (pos % share->block.records_in_block && /* Quick next record */
2356 -       pos < share->records+share->deleted &&
2357 -       (info->update & HA_STATE_PREV_FOUND))
2358 +        pos < share->used_chunk_count + share->deleted_chunk_count &&
2359 +        (info->update & HA_STATE_PREV_FOUND))
2360      {
2361 -      info->current_ptr+=share->block.recbuffer;
2362 +      info->current_ptr+= share->block.recbufferlen;
2363        goto end;
2364      }
2365    }
2366    else
2367      info->current_record=pos;
2368
2369 -  if (pos >= share->records+share->deleted)
2370 +  if (pos >= share->used_chunk_count + share->deleted_chunk_count)
2371    {
2372      info->update= 0;
2373      DBUG_RETURN(my_errno= HA_ERR_END_OF_FILE);
2374 @@ -90,13 +95,17 @@
2375    hp_find_record(info, pos);
2376
2377  end:
2378 -  if (!info->current_ptr[share->reclength])
2379 +  if (GET_CHUNK_STATUS(info, info->current_ptr) != CHUNK_STATUS_ACTIVE)
2380    {
2381 +    /* treat deleted and linked chunks as deleted */
2382      info->update= HA_STATE_PREV_FOUND | HA_STATE_NEXT_FOUND;
2383      DBUG_RETURN(my_errno=HA_ERR_RECORD_DELETED);
2384    }
2385    info->update=HA_STATE_PREV_FOUND | HA_STATE_NEXT_FOUND | HA_STATE_AKTIV;
2386 -  memcpy(record,info->current_ptr,(size_t) share->reclength);
2387 +  if (hp_extract_record(info, record, info->current_ptr))
2388 +  {
2389 +    DBUG_RETURN(my_errno);
2390 +  }
2391    DBUG_PRINT("exit",("found record at 0x%lx",info->current_ptr));
2392    info->current_hash_ptr=0;                    /* Can't use rnext */
2393    DBUG_RETURN(0);
2394 --- a/storage/heap/hp_rsame.c
2395 +++ b/storage/heap/hp_rsame.c
2396 @@ -31,7 +31,8 @@
2397    DBUG_ENTER("heap_rsame");
2398
2399    test_active(info);
2400 -  if (info->current_ptr[share->reclength])
2401 +  if (get_chunk_status(&share->recordspace, info->current_ptr) ==
2402 +      CHUNK_STATUS_ACTIVE)
2403    {
2404      if (inx < -1 || inx >= (int) share->keys)
2405      {
2406 @@ -47,9 +48,15 @@
2407         DBUG_RETURN(my_errno);
2408        }
2409      }
2410 -    memcpy(record,info->current_ptr,(size_t) share->reclength);
2411 +    if (hp_extract_record(info, record, info->current_ptr))
2412 +    {
2413 +      DBUG_RETURN(my_errno);
2414 +    }
2415      DBUG_RETURN(0);
2416    }
2417 +
2418 +  /* treat deleted and linked chunks as deleted */
2419 +
2420    info->update=0;
2421
2422    DBUG_RETURN(my_errno=HA_ERR_RECORD_DELETED);
2423 --- a/storage/heap/hp_scan.c
2424 +++ b/storage/heap/hp_scan.c
2425 @@ -30,7 +30,6 @@
2426    info->lastinx= -1;
2427    info->current_record= (ulong) ~0L;           /* No current record */
2428    info->update=0;
2429 -  info->next_block=0;
2430    DBUG_RETURN(0);
2431  }
2432
2433 @@ -41,32 +40,26 @@
2434    DBUG_ENTER("heap_scan");
2435
2436    pos= ++info->current_record;
2437 -  if (pos < info->next_block)
2438 +  if (pos >= share->recordspace.chunk_count)
2439    {
2440 -    info->current_ptr+=share->block.recbuffer;
2441 +    info->update= 0;
2442 +    DBUG_RETURN(my_errno= HA_ERR_END_OF_FILE);
2443    }
2444 -  else
2445 -  {
2446 -    info->next_block+=share->block.records_in_block;
2447 -    if (info->next_block >= share->records+share->deleted)
2448 -    {
2449 -      info->next_block= share->records+share->deleted;
2450 -      if (pos >= info->next_block)
2451 -      {
2452 -       info->update= 0;
2453 -       DBUG_RETURN(my_errno= HA_ERR_END_OF_FILE);
2454 -      }
2455 -    }
2456 -    hp_find_record(info, pos);
2457 -  }
2458 -  if (!info->current_ptr[share->reclength])
2459 +
2460 +  hp_find_record(info, pos);
2461 +
2462 +  if (get_chunk_status(&share->recordspace, info->current_ptr) !=
2463 +      CHUNK_STATUS_ACTIVE)
2464    {
2465 -    DBUG_PRINT("warning",("Found deleted record"));
2466 +    DBUG_PRINT("warning",("Found deleted record or secondary chunk"));
2467      info->update= HA_STATE_PREV_FOUND | HA_STATE_NEXT_FOUND;
2468      DBUG_RETURN(my_errno=HA_ERR_RECORD_DELETED);
2469    }
2470    info->update= HA_STATE_PREV_FOUND | HA_STATE_NEXT_FOUND | HA_STATE_AKTIV;
2471 -  memcpy(record,info->current_ptr,(size_t) share->reclength);
2472 +  if (hp_extract_record(info, record, info->current_ptr))
2473 +  {
2474 +    DBUG_RETURN(my_errno);
2475 +  }
2476    info->current_hash_ptr=0;                    /* Can't use read_next */
2477    DBUG_RETURN(0);
2478  } /* heap_scan */
2479 --- a/storage/heap/hp_test1.c
2480 +++ b/storage/heap/hp_test1.c
2481 @@ -22,6 +22,7 @@
2482  #include <my_global.h>
2483  #include <my_sys.h>
2484  #include <m_string.h>
2485 +#include <mysql_com.h>
2486  #include "heap.h"
2487
2488  static int get_options(int argc, char *argv[]);
2489 @@ -35,6 +36,7 @@
2490    uchar record[128],key[32];
2491    const char *filename;
2492    HP_KEYDEF keyinfo[10];
2493 +  HP_COLUMNDEF columndef[2];
2494    HA_KEYSEG keyseg[4];
2495    HP_CREATE_INFO hp_create_info;
2496    HP_SHARE *tmp_share;
2497 @@ -51,6 +53,10 @@
2498    hp_create_info.reclength= 30;
2499    hp_create_info.max_records= (ulong) flag*100000L;
2500    hp_create_info.min_records= 10UL;
2501 +  hp_create_info.columns= 2;
2502 +  hp_create_info.columndef= columndef;
2503 +  hp_create_info.fixed_key_fieldnr= 30;
2504 +  hp_create_info.fixed_data_size= sizeof(char*) * 2;
2505
2506    keyinfo[0].keysegs=1;
2507    keyinfo[0].seg=keyseg;
2508 @@ -62,11 +68,20 @@
2509    keyinfo[0].seg[0].null_bit= 0;
2510    keyinfo[0].flag = HA_NOSAME;
2511
2512 +  memset(columndef, 0, 2 * sizeof(HP_COLUMNDEF));
2513 +  columndef[0].type= MYSQL_TYPE_STRING;
2514 +  columndef[0].offset= 1;
2515 +  columndef[0].length= 6;
2516 +  columndef[1].type= MYSQL_TYPE_STRING;
2517 +  columndef[1].offset= 7;
2518 +  columndef[1].length= 23;
2519 +
2520    deleted=0;
2521    bzero((uchar*) flags,sizeof(flags));
2522
2523    printf("- Creating heap-file\n");
2524 -  if (heap_create(filename, &hp_create_info, &tmp_share, &unused) ||
2525 +  if (heap_create(filename, &hp_create_info,
2526 +                  &tmp_share, &unused) ||
2527        !(file= heap_open(filename, 2)))
2528      goto err;
2529    printf("- Writing records:s\n");
2530 --- a/storage/heap/hp_test2.c
2531 +++ b/storage/heap/hp_test2.c
2532 @@ -18,6 +18,7 @@
2533
2534  #include "heapdef.h"           /* Because of hp_find_block */
2535  #include <signal.h>
2536 +#include <mysql_com.h>
2537
2538  #define MAX_RECORDS 100000
2539  #define MAX_KEYS 4
2540 @@ -44,6 +45,7 @@
2541    register uint i,j;
2542    uint ant,n1,n2,n3;
2543    uint write_count,update,opt_delete,check2,dupp_keys,found_key;
2544 +  uint mem_per_keys;
2545    int error;
2546    ulong pos;
2547    unsigned long key_check;
2548 @@ -53,6 +55,7 @@
2549    HP_SHARE *tmp_share;
2550    HP_KEYDEF keyinfo[MAX_KEYS];
2551    HA_KEYSEG keyseg[MAX_KEYS*5];
2552 +  HP_COLUMNDEF columndef[4];
2553    HEAP_PTR UNINIT_VAR(position);
2554    HP_CREATE_INFO hp_create_info;
2555    CHARSET_INFO *cs= &my_charset_latin1;
2556 @@ -65,12 +68,16 @@
2557    get_options(argc,argv);
2558
2559    bzero(&hp_create_info, sizeof(hp_create_info));
2560 -  hp_create_info.max_table_size= 1024L*1024L;
2561 +  hp_create_info.max_table_size= 1024L*1024L*1024L;
2562    hp_create_info.keys= keys;
2563    hp_create_info.keydef= keyinfo;
2564    hp_create_info.reclength= reclength;
2565    hp_create_info.max_records= (ulong) flag*100000L;
2566    hp_create_info.min_records= (ulong) recant/2;
2567 +  hp_create_info.columns= 4;
2568 +  hp_create_info.columndef= columndef;
2569 +  hp_create_info.fixed_key_fieldnr= 4;
2570 +  hp_create_info.fixed_data_size= 39;
2571
2572    write_count=update=opt_delete=0;
2573    key_check=0;
2574 @@ -118,11 +125,30 @@
2575    keyinfo[3].seg[0].null_pos=38;
2576    keyinfo[3].seg[0].charset=cs;
2577
2578 +  memset(columndef, 0, 4 * sizeof(HP_COLUMNDEF));
2579 +  columndef[0].type= MYSQL_TYPE_STRING;
2580 +  columndef[0].offset= 0;
2581 +  columndef[0].length= 6;
2582 +  columndef[1].type= MYSQL_TYPE_STRING;
2583 +  columndef[1].offset= 7;
2584 +  columndef[1].length= 6;
2585 +  columndef[2].type= MYSQL_TYPE_STRING;
2586 +  columndef[2].offset= 12;
2587 +  columndef[2].length= 8;
2588 +  columndef[3].type= MYSQL_TYPE_TINY;
2589 +  columndef[3].offset= 37;
2590 +  columndef[3].length= 1;
2591 +  columndef[3].null_bit= 1;
2592 +  columndef[3].null_pos= 38;
2593 +
2594 +  mem_per_keys= (sizeof(char*) * 2) * 4;
2595 +
2596    bzero((char*) key1,sizeof(key1));
2597    bzero((char*) key3,sizeof(key3));
2598
2599    printf("- Creating heap-file\n");
2600 -  if (heap_create(filename, &hp_create_info, &tmp_share, &unused) ||
2601 +  if (heap_create(filename, &hp_create_info,
2602 +                  &tmp_share, &unused) ||
2603        !(file= heap_open(filename, 2)))
2604      goto err;
2605    signal(SIGINT,endprog);
2606 --- a/storage/heap/hp_write.c
2607 +++ b/storage/heap/hp_write.c
2608 @@ -26,7 +26,6 @@
2609  #define HIGHFIND 4
2610  #define HIGHUSED 8
2611
2612 -static uchar *next_free_record_pos(HP_SHARE *info);
2613  static HASH_INFO *hp_find_free_hash(HP_SHARE *info, HP_BLOCK *block,
2614                                      ulong records);
2615
2616 @@ -35,6 +34,8 @@
2617    HP_KEYDEF *keydef, *end;
2618    uchar *pos;
2619    HP_SHARE *share=info->s;
2620 +  uint rec_length, chunk_count;
2621 +
2622    DBUG_ENTER("heap_write");
2623  #ifndef DBUG_OFF
2624    if (info->mode & O_RDONLY)
2625 @@ -42,7 +43,18 @@
2626      DBUG_RETURN(my_errno=EACCES);
2627    }
2628  #endif
2629 -  if (!(pos=next_free_record_pos(share)))
2630 +
2631 +  if ((share->records >= share->max_records && share->max_records) ||
2632 +      (share->recordspace.total_data_length + share->index_length >=
2633 +       share->max_table_size))
2634 +  {
2635 +    my_errno= HA_ERR_RECORD_FILE_FULL;
2636 +    DBUG_RETURN(my_errno);
2637 +  }
2638 +
2639 +  rec_length= hp_get_encoded_data_length(share, record, &chunk_count);
2640 +
2641 +  if (!(pos= hp_allocate_chunkset(&share->recordspace, chunk_count)))
2642      DBUG_RETURN(my_errno);
2643    share->changed=1;
2644
2645 @@ -53,8 +65,8 @@
2646        goto err;
2647    }
2648
2649 -  memcpy(pos,record,(size_t) share->reclength);
2650 -  pos[share->reclength]=1;             /* Mark record as not deleted */
2651 +  hp_copy_record_data_to_chunkset(share, record, pos);
2652 +
2653    if (++share->records == share->blength)
2654      share->blength+= share->blength;
2655    info->current_ptr=pos;
2656 @@ -88,10 +100,7 @@
2657      keydef--;
2658    }
2659
2660 -  share->deleted++;
2661 -  *((uchar**) pos)=share->del_link;
2662 -  share->del_link=pos;
2663 -  pos[share->reclength]=0;                     /* Record deleted */
2664 +  hp_free_chunks(&share->recordspace, pos);
2665
2666    DBUG_RETURN(my_errno);
2667  } /* heap_write */
2668 @@ -107,7 +116,8 @@
2669    uint old_allocated;
2670
2671    custom_arg.keyseg= keyinfo->seg;
2672 -  custom_arg.key_length= hp_rb_make_key(keyinfo, info->recbuf, record, recpos);
2673 +  custom_arg.key_length= hp_rb_make_key(keyinfo, info->recbuf, record, recpos,
2674 +                                        FALSE);
2675    if (keyinfo->flag & HA_NOSAME)
2676    {
2677      custom_arg.search_flag= SEARCH_FIND | SEARCH_UPDATE;
2678 @@ -129,42 +139,6 @@
2679    return 0;
2680  }
2681
2682 -       /* Find where to place new record */
2683 -
2684 -static uchar *next_free_record_pos(HP_SHARE *info)
2685 -{
2686 -  int block_pos;
2687 -  uchar *pos;
2688 -  size_t length;
2689 -  DBUG_ENTER("next_free_record_pos");
2690 -
2691 -  if (info->del_link)
2692 -  {
2693 -    pos=info->del_link;
2694 -    info->del_link= *((uchar**) pos);
2695 -    info->deleted--;
2696 -    DBUG_PRINT("exit",("Used old position: 0x%lx",(long) pos));
2697 -    DBUG_RETURN(pos);
2698 -  }
2699 -  if (!(block_pos=(info->records % info->block.records_in_block)))
2700 -  {
2701 -    if ((info->records > info->max_records && info->max_records) ||
2702 -        (info->data_length + info->index_length >= info->max_table_size))
2703 -    {
2704 -      my_errno=HA_ERR_RECORD_FILE_FULL;
2705 -      DBUG_RETURN(NULL);
2706 -    }
2707 -    if (hp_get_new_block(&info->block,&length))
2708 -      DBUG_RETURN(NULL);
2709 -    info->data_length+=length;
2710 -  }
2711 -  DBUG_PRINT("exit",("Used new position: 0x%lx",
2712 -                    (long) ((uchar*) info->block.level_info[0].last_blocks+
2713 -                             block_pos * info->block.recbuffer)));
2714 -  DBUG_RETURN((uchar*) info->block.level_info[0].last_blocks+
2715 -             block_pos*info->block.recbuffer);
2716 -}
2717 -
2718
2719  /*
2720    Write a hash-key to the hash-index
2721 --- a/storage/heap/hp_update.c
2722 +++ b/storage/heap/hp_update.c
2723 @@ -17,43 +17,66 @@
2724
2725  #include "heapdef.h"
2726
2727 -int heap_update(HP_INFO *info, const uchar *old, const uchar *heap_new)
2728 +int heap_update(HP_INFO *info, const uchar *old_record, const uchar *new_record)
2729  {
2730    HP_KEYDEF *keydef, *end, *p_lastinx;
2731    uchar *pos;
2732    my_bool auto_key_changed= 0;
2733    HP_SHARE *share= info->s;
2734 +  uint old_length, new_length;
2735 +  uint old_chunk_count, new_chunk_count;
2736 +
2737    DBUG_ENTER("heap_update");
2738
2739    test_active(info);
2740    pos=info->current_ptr;
2741
2742 -  if (info->opt_flag & READ_CHECK_USED && hp_rectest(info,old))
2743 +  if (info->opt_flag & READ_CHECK_USED && hp_rectest(info, old_record))
2744      DBUG_RETURN(my_errno);                             /* Record changed */
2745 +
2746 +  old_length = hp_get_encoded_data_length(share, old_record, &old_chunk_count);
2747 +  new_length = hp_get_encoded_data_length(share, new_record, &new_chunk_count);
2748 +
2749 +  if (new_chunk_count > old_chunk_count)
2750 +  {
2751 +    /* extend the old chunkset size as necessary, but do not shrink yet */
2752 +    if (hp_reallocate_chunkset(&share->recordspace, new_chunk_count, pos))
2753 +    {
2754 +      DBUG_RETURN(my_errno); /* Out of memory or table space */
2755 +    }
2756 +  }
2757 +
2758    if (--(share->records) < share->blength >> 1) share->blength>>= 1;
2759    share->changed=1;
2760
2761    p_lastinx= share->keydef + info->lastinx;
2762    for (keydef= share->keydef, end= keydef + share->keys; keydef < end; keydef++)
2763    {
2764 -    if (hp_rec_key_cmp(keydef, old, heap_new, 0))
2765 +    if (hp_rec_key_cmp(keydef, old_record, new_record, 0))
2766      {
2767 -      if ((*keydef->delete_key)(info, keydef, old, pos, keydef == p_lastinx) ||
2768 -          (*keydef->write_key)(info, keydef, heap_new, pos))
2769 +      if ((*keydef->delete_key)(info, keydef, old_record, pos,
2770 +                                keydef == p_lastinx) ||
2771 +          (*keydef->write_key)(info, keydef, new_record, pos))
2772          goto err;
2773        if (share->auto_key == (uint) (keydef - share->keydef + 1))
2774          auto_key_changed= 1;
2775      }
2776    }
2777
2778 -  memcpy(pos,heap_new,(size_t) share->reclength);
2779 +  hp_copy_record_data_to_chunkset(share, new_record, pos);
2780    if (++(share->records) == share->blength) share->blength+= share->blength;
2781
2782 +  if (new_chunk_count < old_chunk_count)
2783 +  {
2784 +    /* Shrink the chunkset to its new size */
2785 +    hp_reallocate_chunkset(&share->recordspace, new_chunk_count, pos);
2786 +  }
2787 +
2788  #if !defined(DBUG_OFF) && defined(EXTRA_HEAP_DEBUG)
2789    DBUG_EXECUTE("check_heap",heap_check_heap(info, 0););
2790  #endif
2791    if (auto_key_changed)
2792 -    heap_update_auto_increment(info, heap_new);
2793 +    heap_update_auto_increment(info, new_record);
2794    DBUG_RETURN(0);
2795
2796   err:
2797 @@ -63,7 +86,7 @@
2798      if (keydef->algorithm == HA_KEY_ALG_BTREE)
2799      {
2800        /* we don't need to delete non-inserted key from rb-tree */
2801 -      if ((*keydef->write_key)(info, keydef, old, pos))
2802 +      if ((*keydef->write_key)(info, keydef, old_record, pos))
2803        {
2804          if (++(share->records) == share->blength)
2805           share->blength+= share->blength;
2806 @@ -73,10 +96,10 @@
2807      }
2808      while (keydef >= share->keydef)
2809      {
2810 -      if (hp_rec_key_cmp(keydef, old, heap_new, 0))
2811 +      if (hp_rec_key_cmp(keydef, old_record, new_record, 0))
2812        {
2813 -       if ((*keydef->delete_key)(info, keydef, heap_new, pos, 0) ||
2814 -           (*keydef->write_key)(info, keydef, old, pos))
2815 +        if ((*keydef->delete_key)(info, keydef, new_record, pos, 0) ||
2816 +            (*keydef->write_key)(info, keydef, old_record, pos))
2817           break;
2818        }
2819        keydef--;
2820 @@ -84,5 +107,12 @@
2821    }
2822    if (++(share->records) == share->blength)
2823      share->blength+= share->blength;
2824 +
2825 +  if (new_chunk_count > old_chunk_count)
2826 +  {
2827 +    /* Shrink the chunkset to its original size */
2828 +    hp_reallocate_chunkset(&share->recordspace, old_chunk_count, pos);
2829 +  }
2830 +
2831    DBUG_RETURN(my_errno);
2832  } /* heap_update */