Compression

Dictionary Encoding

Umbra performs dictionary encoding of strings.

Concurrency Control

Multi-version Concurrency Control (MVCC)

Umbra employs Multi-Version Concurrency Control (MVCC) for its concurrency control scheme. Umbra defaults to a purely in-memory MVCC scheme and falls back to a different scheme for bulk operations. By default, version chains are stored exclusively in memory and are associated with pages through local mapping tables. For bulk operations, the transaction is given exclusive write access to the relevant relations by setting the "created" or "deleted" bits directly on the database pages, creating "virtual versions" of a database object.

Data Model

Relational Array / Matrix

Umbra supports the relational model with SQL as well as the Array data model with ArrayQL. ArrayQL is translated to ArrayQL algebra, where the ArrayQL operators are compiled to relational algebra operators. ArrayQL can be used as a separate query interface or invoked through User-Defined Functions (UDFs) in SQL.

Indexes

B+Tree

Umbra supports B²-Tree indexes, a modified version of a B+Tree which embeds another trie-based search tree within each page.

Isolation Levels

Serializable

Umbra supports the "Serializable" isolation level, implemented with a graph-based scheduling algorithm that delivers linear scalability in transaction throughput with the number of cores.

Joins

Hash Join Semi Join Index Nested Loop Join Worst-Case Optimal Join

Umbra executes queries using traditional binary joins such as hash-joins and index nested-loop joins. Additionally, Umbra has integrated Worst-Case Optimal Joins (WCOJ) into the query optimizer and execution engine. Worst-case optimal joins provide superior performance to binary joins when the cardinality of intermediate joins is large. Therefore, during query optimization, Umbra detects when a portion of the query plan would result in large intermediate results and use a WCOJ instead. To execute a WCOJ, Umbra builds hash-trie indexes on the involved relations and performs a multi-way join using these indexes.

Parallel Execution

Intra-Operator (Horizontal) Inter-Operator (Vertical) Bushy

Umbra uses morsel-driven parallelism, pioneered by the HyPer database system. Morsel-driven parallelism supports bushy, inter-operator and intra-operator parallelism.

Query Compilation

JIT Compilation

Umbra performs Just-In-Time (JIT) compilation of queries into Umbra IR, a custom intermediate representation (IR) similar to LLVM IR but optimized for use in a database system. After generating Umbra IR, the code is lowered using one of two backends:

1. LLVM
2. Flying Start

The LLVM backend emits LLVM IR, compiled at optimization level -O3. This backend is the slowest but generates the fastest executing code, making it suitable for long-running queries.

The Flying Start backend emits x86 machine code using asmJIT, generating x86 in a single pass. In addition, the Flying Start backend implements Stack Space Reuse, Machine Register Allocation, Lazy Address Calculation, and Comparison-Branch Fusion optimizations. As a result, the code generated by Flying Start has performance on par with code generated by LLVM -O0 (i.e., with optimizations disabled). Additionally, Flying Start outperforms interpretation of Umbra IR, making Flying Start suitable for short-running queries.

Umbra supports adaptive execution, pioneered by HyPer, allowing the DBMS to switch execution strategies while processing a single query. Umbra first generates x86 machine code using the Flying Start backend and then switches to the code generated by the LLVM backend for long-running queries.

Query Execution

Tuple-at-a-Time Model

Umbra uses data-centric query processing, executing operators tuple-at-a-time.

Query Interface

SQL

In addition to SQL and ArrayQL, Umbra allows the user to extend the functionality of the DBMS with custom algorithms with User-Defined Operators (UDOs). UDOs can be written in C++, conforming to an interface consisting of two functions:

1. void Accept(const InputTuple &tuple);
2. bool Process();

The "Accept" function is invoked for each input tuple to the UDO and is responsible for implementing "per-tuple" processing. The "Process" function is invoked only once when all of the input tuples have been seen and is responsible for producing the output of the UDO by calling the "Emit" function, which sends one output tuple to the parent operator. To support custom algorithms that process the entire input at once (i.e., aggregations or sorting), the "Accept" function should store all tuples of the input, and the "Process" function should then iteratively loop over these tuples to compute the output.

UDOs are written in C++ and compiled with Clang at optimization level -O3 to ELF object files, saving the intermediate LLVM bitcode in the process. When a query invokes a UDO, the ELF object file is dynamically loaded into the DBMS process using a custom linker to handle global state and runtime dependencies (such as libc and libstdc++). During query processing, the UDO is invoked from the compiled query. During query processing, the adaptive execution framework may detect that the current query is long-running and compile the current query using the LLVM backend. During query compilation to LLVM, the intermediate LLVM bitcode saved during the compilation of the UDO is directly inlined into the compiled query, enabling LLVM to perform optimizations across the query and UDO.

Storage Architecture

Disk-oriented

Umbra uses flash storage (SSDs) and relies on the LeanStore buffer manager extended to support variable-sized pages. Pages sizes are powers of two, starting at 64KiB, ranging up to the total size of the buffer pool. Pages of each size class are allocated contiguously as a segment of virtual memory address space that spans the entire buffer pool. Each segment is allocated using the mmap() system call as a private anonymous mapping, where the virtual memory address range is not backed by physical memory. When pages are accessed, pread() reads the data from disk into the virtual memory address, and the kernel creates an associated virtual memory mapping. During eviction, pwrite() writes the data to disk, allowing the physical memory to be reused with the madvise() system call.

Storage Format

Apache Parquet

Umbra supports querying of Apache Parquet files.

Storage Model

Decomposition Storage Model (Columnar)

Umbra stores relations in B+Trees using the PAX layout for leaf pages.

Views

Virtual Views Materialized Views

Umbra supports Virtual Views and "Continuous Views," which are Materialized Views maintained over append-only data streams. Continuous Views are maintained by splitting view maintenance between inserts and queries, achieving superior performance to deferred or incremental view maintenance approaches.