Compression

Dictionary Encoding Delta Encoding Run-Length Encoding Bit Packing / Mostly Encoding Null Suppression

Hyrise includes a compression framework based on C++ iterators and zero-cost abstractions. Such zero-cost abstractions avoid the runtime overheads of dynamic dispatching for increased compile times. As a heavy-weight compression algorithm, LZ4 is also supported.

Concurrency Control

Multi-version Concurrency Control (MVCC)

For each row, three pieces of information are stored: The commit id of the transaction that successfully inserted the row (begin cid), that of the transaction that fully deleted it (end cid), and the transaction id of the transaction that currently modifies it. The linked Wiki page describes how these are used to calculate the row's visibility.

Data Model

Relational

Indexes

Adaptive Radix Tree (ART)

Adaptive Radix Trees (ARTs) and Group Key Indexes are used. These are created on a per-chunk basis and different chunks can have different types of indexes. Additionally, probabilistic filters are used for access avoidance in cases where no index exists.

Isolation Levels

Snapshot Isolation

Joins

Nested Loop Join Hash Join Sort-Merge Join Semi Join Index Nested Loop Join

Query Compilation

Not Supported

A JIT-compiled execution engine was partially implemented. The underlying approach to transferring data from and to the JIT engine turned out to be a bottleneck, which was why it was ultimately removed.

Query Execution

Materialized Model

Most operators produce position lists that contain chunk ids and chunk offsets. Together with a pointer to the original table, these can be used to reference data without fully materializing it. The JIT engine (see above) uses a Tuple-at-a-Time Model.

Query Interface

SQL Stored Procedures

The SQLPipeline is an interface that takes an SQL string and returns the result table(s). Hyrise uses its own SQL-Parser to translate SQL queries into an Abstract Syntax Tree (AST). These are converted into a logical query plan (LQP), which is optimized, translated into a physical query plan (PQP) and finally executed. The pipeline handles both query plan caching and stored procedures.

Storage Architecture

In-Memory

Storage Model

Decomposition Storage Model (Columnar)

Hyrise started as one of the first databases with a hybrid memory layout. With the rewrite, only columnar storage is implemented. Hybrid layouts are planned to come back, but are not a high priority.

Stored Procedures

Supported

Stored Procedures are stored as named, static entries in the otherwise automatic query cache.

System Architecture

Shared-Everything

The current version of Hyrise runs on a single node. Replication, which was part of Hyrise1, is planned.

Views

Virtual Views

Views are stored as logical query plans (LQPs). For a query selecting from a view, the LQP is inserted at the position at which usually a stored table would appear before the optimizer is called. This makes it possible for the optimizer to optimize across view boundaries - for example pushing down additional predicates into the view.