ToC path:

Database Design Considerations

This section explains some database design considerations with respect to eXtremeDB. It is not an exhaustive treatment of the topic of database design. That is a very large subject and well beyond the scope of this document. Rather, the objective here is to shed light on the workings of eXtremeDB in order that developers can make informed database design decisions choosing from the many available options.

Types of Database Design Considerations

Logical vs. Physical

Logical design considerations involve how you will conceptually organize the data: what objects you will define, how they are interrelated, what means you will employ to affect the relationships, what access methods are required, and the performance requirements of your application. In this process, you will decide things like: what indexes are needed and of which kind, whether an Object Identifier (oid) will be needed and what its structure should be, which classes will have oids, whether to implement interclass relationships via oid and ref, autoid and autoid_t, via indexes, or to de-normalize and use a vector instead.

The physical design considerations are things like: page size, initial database size, incremental extensions, whether certain fields can be optional, and whether classes can be compact.

eXtremeDB imposes very few limitations. However, it is important to be aware of the following:

There is a limit of 64K (65,536) classes per database.

Each class can have up to 64K fields, subject to a limit of 2^32 (4,294,967,296) bytes per object.

An index can include 64K fields.

A database can have at most 64K indexes.

A database can store 2^32 (or 2^64 on 64 bit platforms) objects per class.

Vectors are limited to 64K elements (vector elements are indexed by an unsigned 2-byte integer).

Page size can be as low as 40 bytes and as much as 64K, but as explained below, this is not a limitation in any practical sense.

Strings are limited to 64K in size. If storing larger strings is a possibility, this will require a blob field.

Page Size

The eXtremeDB runtime provides its own optimized memory management. It includes a low-level page manager and a heap manager. When a database instance is created, memory space is allocated on the heap or claimed (declared) in static memory. This memory is formatted by the runtime and used the entire time the database exists. A small portion of this memory is dedicated for database runtime control structures. The page manager controls the remainder along with any extensions. The memory is partitioned into pages, each page having the same size (page_size). The page manager is a very fast and efficient mechanism. It allows any page released by any consumer (for example, by a tree index) to be used immediately by any other consumer (for example, by the object layout manager). The page_size parameter is passed to the runtime at the time the database instance is created and affects all the derived memory managers.

As a rule of thumb, page_size should be between 60 and 512 bytes; a 100 byte page works fine in most situations. The page_size should be a multiple of 4, and if it is not the runtime will adjust it internally. Almost all memory used by the database instance is used to store objects or index data. The overhead imposed by the index memory managers is not really affected by the page_size when it is larger than 60 bytes. This is because the fixed part of the index control data is typically between 4 and 12 bytes per page. Therefore, the page size mostly affects the overhead imposed by object layout managers.

Objects that have dynamic data fields, such as strings or vectors, always occupy whole pages. Multiple fixed size objects can share a page. This means, for example, that if the page size is 100 bytes and some object with dynamic fields took 440 bytes including all control data, then 60 bytes (= 5*100 – 440) would be wasted. It is not really possible to determine in advance the exact optimal page size. It depends on the object size distribution at runtime: the actual sizes of the dynamic data, the dynamic sequence of operations, and what type of objects will be stored most frequently, etc. To determine runtime memory requirements, the calculator tool is provided to do memory calculations using the actual application database dictionary and specified numbers of objects. The statistics generated by the calculator make it easy to adjust the page size parameter in order to optimize memory use.

Initial Database Size

eXtremeDB allows the application to define multiple memory devices at runtime. If the maximum amount of memory that can be used for storage is known, it can be specified in the database open parameters to claim that memory in advance. The runtime creates a page manager that uses contiguous address space for object storage. Once claimed, the physical memory cannot be returned back to the operating environment without destroying the database. So, if the maximum database size is not known in advance, the application can claim a reasonably sized block of memory first and then extend that amount at runtime as necessary.

Extending Database Size

Practically, there are no performance penalties associated with extending database memory and the application doesn’t need to be aware of how the page manager works. The only issue to be concerned about with memory extension is that none of the “database” memory can be returned back to the operating system without destroying the database content. (For a detailed discussion of memory management see the Database Control pages).

Using OIDs

Estimating the Number of oid Entries

A custom oid can be defined for C, C++ and Python applications in the database schema. (oids are not supported in the Java and C# APIs.) The DDL specification requires an estimate of the total number of oids that will be created. This number is used by the runtime to build the oid hash table. (See the section Hash and Autoid Indexes page for an explanation of how to specify static and dynamic hash tables and how they are managed by the eXtremeDB runtime.)

oid Design Considerations

Classes should use an oid if the application data model has one. In other words, if objects described in the schema have some native identifying information and that information is common between objects of different types, then an oid is a natural way to represent this model. If the application’s objects are identified differently depending on their type, then an oid should not be used. The oid can have several fields, but they must be of fixed size.

Use of Structures

The eXtremeDB structure meaning and usage is almost the same as in C. A struct declaration names a type and specifies a list of elements of the structure that can have different types. Structures and simple types are building blocks to construct object definitions. Structures can be used as fields of other structures. In contrast to C/C++ though, eXtremeDB structures cannot be instantiated without a class, nor do they take any memory by themselves; they can only exist as a field of an object. eXtremeDB structures merely present a compact way to program with data that is used across multiple classes. Also, it is very common for applications to use structures as vector fields. There are a couple of unconventional (not C-like) ways that eXtremeDB uses structures: the declaration of an oid requires a structure (even if the oid is a single field), and use of optional fields; only structure fields can be declared as optional.

Note that eXtremeDB allows indexing by structure field(s) even when the structure is used as a vector field.

Compact Modifier for Class Declarations

The compact class qualifier limits the size of the class’ elements to 64K. This is because 2-byte offsets are used instead of 4-byte offsets to address within each object’s layout. Obviously, there is an overhead imposed by eXtremeDB to support certain data layouts. A large portion of this overhead is due to the fact that dynamic data types are supported, such as vectors, strings and optional fields. For instance, each string field is implemented as an offset to the actual data. For a compact class this offset is 2 bytes, otherwise it is 4 bytes. Another example is an optional field. It is common in applications for some data to not be known at the time of creation for a particular object. Instead of reserving space for such data within each object, it can be declared as optional. eXtremeDB will place an offset to the actual data within the data layout. Then if data is not present (or has been erased) this offset is null. The space for the structure is only allocated when necessary to store the data. All these offsets are 2-bytes in the compact model.

Note that the total 64K limit of a compact object size does not include blobs defined for the class. It is still possible to have a large blob (> 64K in size) for compact classes. Addressing within a blob is not affected by the compact declaration.

The –c or –compact options for the mcocomp schema compiler can be used to make all classes of a database compact.

For example, consider a class that contains two string fields and one optional structure. For 1000 objects of this class, the compact declaration would save (at least) 3*2*1000 = 6000 bytes of overhead (3 fields, 2 bytes less overhead each, times 1000 objects equals 6,000 bytes).

The only limitation with compact classes is the total size of an object, 64K. If it is known that objects of a class will always require less than 64K it is beneficial to use the compact qualifier.

Char<n> vs. String

The char<n> declaration defines a fixed length byte array of n bytes (where n <= 64K). The string declaration defines a variable length byte array <= 64K. In the case of char<n>, n bytes will be consumed for this field by every object (instance of the class). It is best to use char<n> when exactly n bytes are used in every instance, as for example in a social security number field that is a required entry. In the case of a string element, eXtremeDB imposes 2 or 4-bytes overhead (depending on the compact qualifier, see above) for each instance.

Blob

An object having K allocated blobs has (4 + 8*K) bytes allocated within the object layout. A 32-byte header is written for each blob when it is stored, within the first blob page, plus 8 bytes for the 2nd through N-th pages.

Vector

Like string and blob, a minimum of 2-bytes or 4-bytes of overhead is imposed for each vector of each object. If the vector is of structures or strings, then the overhead is 2 * (N+1) (compact) or 4 * (N+1) (normal) where N is the number of elements in the vector. If the vector is a simple type, the overhead is only 2 (compact) or 4 (normal) bytes.

Vectors, unlike blobs, have structure. The elements of a vector can be efficiently located by offset within the vector. In contrast, blob access methods are like sequential file access - the blob is a series of bytes, exactly as a file is. Because of this, it is always better to use a vector when the data is regular in nature and needs to be accessed by the element number.

Variable vs. Fixed Length Elements

This discussion applies to char / string (and Unicode variants) and fixed-size arrays versus vectors.

eXtremeDB stores all fixed-size elements of a class on a single page and variable length elements on separate pages (to allow them to grow). The page with the fixed-size elements contains a 2- or 4-byte offset for each variable length field.

As a consequence, using variable length fields may actually use database space less efficiently than defining a fixed length element even knowing that a portion of the fixed length element may go unused.

For example, suppose we have a page size of 100 bytes and a character field that might hold between 8 and 50 characters, with the average length being 18. A field definition of char<50> will leave 32 bytes, on average, unused. But a string field will use 2 (or 4) extra bytes and leave at least 50 bytes unused on the page that eXtremeDB uses for the string field. In this circumstance, a fixed length character field would be better. Conversely, a character field that must allow for up to 256 bytes would be better defined as a string field.

The same basic principle applies to the choice of fixed length arrays or variable length vectors.

Optional Structure Fields

Only structures can be declared optional, so to make a single field optional, it must be included in a structure with just that one field as an element. If a structure is declared optional, 4 bytes (normal) or 2 bytes (compact) are used by eXtremeDB for the offset. This is the overhead of an optional structure compared to an ordinary structure. Obviously, if a structure is always present, there is no advantage to declaring it optional.

Note that optional structure elements cannot be used in an index.

Voluntary Indexes

The advantages of indexes on a class are fast searches and runtime-maintained order (for all but hash indexes). It naturally requires additional time to create or modify the index on inserts, updates and deletes and extra memory space to keep index control structures. Normally, indexes are created at the time of database instance initialization and are maintained during the life of the database. However, some indexes are useful for a particular purpose or task only, and after the completion of that task the index is no longer needed. Another common scenario is the need for fast processing at a certain point of execution, i.e. an application could be required to acquire boot stage data faster or have some other period at a high transaction rate, but without performing any complex searches at that time, while normally the transaction rate is lower but search operations must be complex and fast. Here a voluntary index can be used (unless a hash index is required – hash indexes cannot be voluntary) and index creation deferred until after the critical performance period.

Voluntary indexes can be created, used for a series of transactions and then destroyed. Because index creation is a relatively “heavy” operation, it does not make sense to always create an index if all that is needed is to perform a few searches at some particular time during execution. In this case the indexes can be declared voluntary and built as needed prior to the search operation.

Voluntary indexes use the same algorithms and consume the same space as regular indexes; they differ only by their ability to be created and destroyed dynamically, and by the fact that voluntary indexes are not created automatically when the database instance is created.

Hash and Tree Indexes

eXtremeDB provides hash index algorithms and tree index algorithms of a rich variety of types, modified for efficient operations in memory when the associated class is transient. The b-tree index algorithm is the most general; it can be used for all kinds of searches and for ordered fetches. A b-tree index can be unique or not unique and is searchable by ranges and partial key values. In addition to the b-tree, eXtremeDB provides specialized tree-type indexes including “Patricia Trie”, “R-Tree” and “Kd-Tree” that are described in detail in the Indexes and Cursors pages. A hash index is only suitable for search by equality, or for an unordered sequential scan, and can also be unique or nonunique. Hash indexes can exhibit better average performance, for both insert and lookup operations, compared to a tree index, but this also depends on the initial hash table size and on key distribution.

In the ideal case, the hash table will be sized to contain one entry (sometimes called a “bucket”) for each database object being indexed which means that a single hash table lookup (a simple hash function calculation) will suffice to access each database object. But in reality, regardless of the table size, the hash function does not guarantee a unique value and consequently multiple index values can map to the same bucket (called a “conflict”) and a linked list of object pointers (called a “collision chain”) will result.

So if the number of database objects is known beforehand, this number can be specified in the schema declaration for the index and will result in optimal performance. But if the number of database objects cannot be known with a reasonable degree of confidence, an eXtremeDB feature called dynamic hash will automatically re-allocate the hash table as needed. This will avoid (a) long collision chains if the estimated number of objects is too small, or (b) wasting memory in the case of an overly cautious large estimate. (Please refer to the C API Indexes and Cursors page for further details on dynamic hash.)

Memory consumption is comparable for tree and hash indexes of transient classes. The Hash and Autoid index page gives a method for estimating index memory consumption.

List Indexes

Each list declaration will create an additional dynamic structure, which will consume resources similar to those taken by a tree index. The list declaration is useful when:

objects of a class have to be accessed sequentially

the application does not require any particular order in which objects are accessed

there is no suitable index for the class

Note that the list declaration is a deprecated feature, supported for backward compatibility. eXtremeDB version 4.0 introduced the possibility to instantiate a cursor over the entries of a hash index, eliminating the need for list cursors.

Vector of Structs vs. Objects of a Class

An object is characterized, in part, by the fact that when it is deleted all of its dependent parts are deleted (i.e. all its scalar fields, structs, arrays, vectors, strings and blobs). To accomplish this, these dependent parts of an object are stored using an object layout manager. In order to express one-to-many relationships between parts of the object it may be very efficient to use a vector. For example, a vector of strings will take only 2 or 4 bytes for the vector itself plus 2 or 4 bytes overhead per string, whereas making a separate object from each string will require at least one page for each string, so the overhead may be more significant. Vectors are useful when the object model in an application already contains dynamically structured items. Say, for example, an application needs to collect radar measurements for various “Targets”, and that each measurement is a set of structures. Its database could be defined as follows:
 
    struct Target
    {
        uint2 x;
        uint2 y;
        uint2 dx;
        uint2 dy;
        uint2 type;
    };
 
    class Measurement
    {
        uint4 timestamp;
        uint4 radar_number;
        vector< Target > targets;
    }
     
Alternatively, in “normalized” form, it could be defined:
 
    class Target2
    {
        uint4  m_unique_id; // ref to measurement
        uint2 x;
        uint2 y;
        uint2 dx;
        uint2 dy;
        uint2 type;
    }
 
    class Measurement2
    {
        uint4 m_unique_id;
        uint4 timestamp;
        uint4 radar_number;
    }
     
As an exercise, build an application that stores an intensive stream of Measurements and makes some simple lookups of the data. For instance, one that deletes all Measurements that are older then 30 minutes and periodically requests radar beacons (indicated by the field radar_number) that have detected targets of a given type. It will demonstrate that the first (eXtremeDB) approach will perform far faster and will take far less space because fewer objects have to be maintained and fewer operations have to be performed.