Dynamic and compressed vectors

The underlying data structure upon which the whole database system is founded is a compressed and extensible vector type. HPDS makes extensive use of vectors to implement hashtables, string pools and the columns of relations. The bit-lengths of the integers that have to be stored in these structures vary widely, both between structures and over the lifetime of an individual instance. The integers stored may take on values in the millions, necessitating a 32 bit integer representation were conventional arrays used. In many other cases, the values in the arrays will be drawn from small finite sets whose indexes require only a few bits. HPDS provides for both extremes by basing its store on integer vectors that are extensible both in length and in width.

  
Figure 3.2: Dynamic vectors are allocated store in a number of blocks with a maximum of 8K bytes per block

The vectors are implemented as object classes with bit-aligned elements, stored in a series of blocks as shown in figure 3.2. This block structure is designed to reduce the costs associated with growing the vectors. Growing a vector involves the following algorithm:

1. if (size mod maxblocksize )=0 then
   1. grow the Illife vector by 1
   2. append a new block of minblocksize to the Illife vector.
2. otherwise
   1. allocate a new block twice the size of the last block,
   2. copy over the contents of the old last block to this,
   3. replace the last pointer in the Illife vector with the address of the new block.