158 Data representation

C++ is used in this chapter to illustrate mappings from Predica into an implementation. This provides a convenient way to understand possible in-memory representations. Predica provides physical implementation independence, so in general the compiler is free to map Predica types to physical representations that favour space efficiency and performance. The persistence of these representations is introduced briefly here and discussed in more detail later.

The mapping to an in-memory representation in a low-level language such as C++ is typically inaccessible to users. There is therefore no requirement for the representation itself to enforce the Predica constraints. The compiler and runtime may diagnose violations elsewhere while using a simpler internal representation. Constraint enforcement is specified independently in Constraint-Violating Updates.

Mapping Predica types to structures

One of the most important implementation approaches is to map Predica types to what C++ calls structures. Where the cardinality constraints permit it, a concrete instantiation of a generic Predica value type can then have a fixed, compact in-memory layout. For example, consider these generic types: 


value Point<Type T>
{
    T x;
    T y;
}

value Circle<Type T>
{
    Point<T> centre;
    T radius;
}

Instantiating these types as Point<Float32> and Circle<Float32> fixes each coordinate and radius to the Predica Float32 type. An implementation in C++ can represent those values using float fields: 


struct PointFloat32
{
    float x;
    float y;
};

struct CircleFloat32
{
    PointFloat32 centre;
    float radius;
};

Using fixed-size arrays

An attribute with a fixed cardinality can be represented by a fixed-size array. For example: 


value Triangle<Type T>
{
    Point<T> vertex[3];
}

Because every Triangle<T> has exactly three vertices, Triangle<Float32> can be mapped directly to a C++ structure containing a std::array<PointFloat32, 3>: 


struct TriangleFloat32
{
    std::array<PointFloat32, 3> vertex;
};

Using B-trees

Attributes with a many-valued cardinality can be represented by B-trees. For example, consider the following Predica types: 


entity Supplier
{
    String id;
    String name;
    Integer status;
    String city;
    key {id};
}

entity ShipmentsSystem
{
    Supplier supplier*;
}

The many-valued attribute can be mapped to a btree<Key, Value> member in C++. The key of the B-tree is the id key declared by Supplier. 


struct Supplier
{
    std::string id;
    std::string name;
    std::int64_t status;
    std::string city;
};

struct ShipmentsSystem
{
    btree<std::string, Supplier> supplier;
};

A btree<K, V> hides a great deal of complexity, including:

  • internal pointers;
  • merging, splitting, and rotating nodes;
  • binary search within nodes;
  • lookup by key;
  • iteration over a given key range;
  • set operations such as intersection, union, and difference, implemented using an approach resembling the merge step of merge sort;
  • lazy loading of nodes from secondary storage; and
  • tracking dirty nodes whose in-memory contents differ from the version on disk and which therefore need to be written back.

A persistent B-tree allows an implementation to deal with billions of records without loading the entire collection into memory. Opening the database can be fast because loading ShipmentsSystem need only load the root node of the supplier B-tree; other nodes can be loaded on demand. Operations can remain very efficient because B-tree nodes have high fan-out. For example, with a fan-out of 1000, a suitably laid-out tree can locate a record using only two random-access fetches from disk after the root node has been loaded.

Specialised variants may be preferable for particular workloads. In a B+ tree, all mapped values are stored in leaf nodes, while internal nodes store only the keys needed for navigation. This can be superior when keys are small compared with their mapped values because more keys fit in each internal node, increasing the fan-out. The leaf nodes can also be linked together, allowing faster iteration through the values and efficient traversal of key ranges.

Choosing collection representations

Using a B-tree for every many-valued attribute would be a significant pessimisation. When a collection is expected to have low cardinality, a contiguous vector can use less memory, require fewer allocations, and provide better cache locality. Linear search over a small vector can also be faster than traversing a B-tree. 


struct ShipmentsSystem
{
    std::vector<Supplier> supplier;
};

Other possible C++ representations include:

  • std::map, commonly implemented as a red-black tree, when ordered keys and logarithmic lookup and update are useful, and the cardinality is low enough that the collection can reasonably be expected to fit in memory; unlike a persistent B-tree, it does not lazily load nodes from secondary storage;
  • std::unordered_map when hashing is available and fast lookup by key is more important than key order; it generally carries the same assumption that the collection fits in memory and can have substantial memory overhead;
  • std::set when only distinct values, rather than separate keys and values, need to be stored; and
  • std::queue when the implementation only needs first-in, first-out access to the values.

The choice between a vector, a B-tree, and another representation is a physical implementation decision. It can be based on expected cardinality, observed data, access patterns, cardinality constraints, and other implementation assumptions. Regardless of that choice, the implementation must preserve the Predica cardinality and key constraints; when a vector is used, uniqueness of Supplier.id must still be enforced. Comparison and hashing must agree with Predica equality.

Mapping types to objects with identity

The same Predica entity may occur in multiple attribute extensions. This suggests an implementation in which those occurrences are represented by references to a single object with implementation-level identity. For example, the same shipment can occur under both a supplier and a part: 


entity Supplier
{
    String id;
    Shipment shipment* where shipment.supplier = this;
    key {id};
}

entity Part
{
    String id;
    Shipment shipment* where shipment.part = this;
    key {id};
}

entity Shipment
{
    Supplier supplier;
    Part part;
    Integer quantity;
    key {supplier, part};
}

In C++, the direct mapping of these multiple occurrences is to dynamically allocate one Shipment object and store memory pointers to that same object under both the supplier and the part. std::shared_ptr can be used for those pointers to manage the lifetime of the object: 


struct Supplier;
struct Part;
struct Shipment;

struct Supplier
{
    std::string id;
    std::vector<std::shared_ptr<Shipment>> shipment;
};

struct Part
{
    std::string id;
    std::vector<std::shared_ptr<Shipment>> shipment;
};

struct Shipment
{
    Supplier* supplier;
    Part* part;
    std::int64_t quantity;
};

Supplier supplier;
Part part;
std::shared_ptr<Shipment> shipment = std::make_shared<Shipment>();
shipment->supplier = &supplier;
shipment->part = &part;
supplier.shipment.push_back(shipment);
part.shipment.push_back(shipment);

Both collections refer to one object rather than containing independent copies of the shipment. The identity supplied by the C++ object is an implementation mechanism and is not part of the Predica value's semantics. The back-pointers from Shipment to Supplier and Part are non-owning, and their validity is maintained by the implementation.

Lazy loading from secondary storage

Whenever Predica types are mapped to memory representations using pointers, there is an opportunity to represent persistent objects using object identifiers in a persistent object store and to make pointer dereference trigger loading from disk on demand. This behaviour can be embodied in smart pointers, pointer swizzling, or faulting.

Mapping quotient types

A quotient type defines values as equivalence classes over a representation. For example, Rational<T> can be parameterised by an integer type: 


quotient Rational<Type T> where T isa Integer
{
    T numerator;
    T denominator where denominator > 0;

    equivalence
    {
        x ~ y where
            x.numerator * y.denominator = y.numerator * x.denominator;
    }
}

The direct mapping is a structure that directly implements the representation fields and implements the equivalence relation in operator==: 


template<typename T>
struct Rational
{
    T numerator;
    T denominator;

    bool operator==(const Rational& other) const
    {
        return numerator * other.denominator
            == other.numerator * denominator;
    }
};

Structural equality of the two fields would be incorrect: for example, 1/2 and 2/4 are different representatives of the same quotient value. The C++ equality operator therefore compares the representatives using the equivalence relation declared by the Predica type.

Column-oriented representations

The structure mappings described earlier are row-oriented: the attributes of each value are stored together. A more specialised alternative is a column-oriented representation, in which the values of each attribute are stored together. For example, Supplier could be represented conceptually as: 


struct SupplierColumns
{
    std::vector<std::string> id;
    std::vector<std::string> name;
    std::vector<std::int64_t> status;
    std::vector<std::string> city;
};

Entries at the same physical position belong to the same supplier. This position is an implementation-level row identifier and is not part of Predica semantics. A separate index can map the declared supplier key to its physical position.

Column-oriented storage is particularly useful for scans, projections, and aggregations because a query need load only the attributes it uses. Keeping values of the same type together improves cache locality, permits vectorised processing, and creates opportunities for dictionary encoding, run-length encoding, delta encoding, bit packing, and other specialised compression. Column pages can also record summary information such as minimum and maximum values, allowing a query to skip pages that cannot contain a result.

Column-oriented representations are particularly suitable for read-heavy analytical workloads, especially data warehousing, where queries scan many records but use only a subset of their attributes. They are generally less suitable for workloads dominated by individual record retrieval and frequent fine-grained updates. Updates can still be supported through techniques such as delta stores, batching, and hybrid representations.

A column-oriented representation need not be the mutable authoritative representation. It may instead be a read-only analytical replica derived from a transactional primary store. Committed changes can be propagated to it through a log, change-data-capture stream, or periodic batch. This allows the replica to use immutable, compressed column segments optimised for analytical queries.

Cardinality constraints can guide the column representation. An exactly-one attribute can use a dense array, an optional attribute can use a presence bitmap and an array of present values, and a many-valued attribute can use an offsets array together with a values array. Fixed-cardinality attributes can reserve a fixed number of entries for each value.

The disadvantages are that reconstructing a complete value requires gathering its attributes from several columns, while individual updates may require coordinated changes to several structures. A compiler can therefore choose row-oriented, column-oriented, or hybrid layouts for different types and workloads without changing the observable Predica semantics.

Serialisation and deserialisation of in-memory structures

Serialisation of a value produces a stream of bytes representing its state. This can cause data that is non-contiguous in memory to become a contiguous byte sequence when it is turned into a blob: the serialised state of an object stored on disk. Deserialisation performs the reverse mapping, reconstructing an in-memory representation from the byte stream.

For example, an in-memory structure containing std::string, std::vector, std::deque, std::map, std::unordered_map, std::set, std::unique_ptr, or std::shared_ptr members can be traversed and serialised into a single object on disk. The internal allocations, nodes, and pointers do not need to retain their in-memory layout in the serialised representation. Serialising into a blob can therefore also improve space efficiency: pointer addresses and in-memory allocation overhead are not serialised, while necessary relationships can use compact serialised references.

The ideal blob size is generally of the same order as the natural chunk size for the storage medium. This relationship is discussed in the chapter on chunk size.

  • Blobs that are too small incur excessive I/O latency and metadata overhead.
  • Blobs that are too large cause read and write amplification when only a small part of the blob is needed or changed.

Small object graphs can be serialized as blobs, while large collections can remain partitioned into independently loaded B-tree nodes.

This is very useful for performance because fine-grained random access to data on secondary storage is one of the largest performance costs in database systems. Reading or writing a contiguous blob can replace many small, scattered storage I/O operations with a much smaller number of larger I/O operations.