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

Foreign Keys

Supported

Indexes

B+Tree

Umbra supports B^2-Trees, a modified 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

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

Umbra executes queries using traditional binary joins such as hash-joins and 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.

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 all but the longest-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

Umbra supports SQL and ArrayQL as query interfaces, where ArrayQL operators are compiled into relational algebra operators.

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 2 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

Hybrid

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.