# 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.