Umbra is a relational DBMS designed to support high performance for OLAP and OLTP workloads using flash-based storage. Umbra seeks to provide the performance of a pure main-memory DBMS for workloads that fit within main memory, with the scalability of a disk-based system. Umbra's buffer manager is based on LeanStore but instead uses variable-sized pages, enabling disk-based data structures to be accessed without any levels of indirection. Umbra integrates Worst-Case Optimal Joins (WCOJ) into the query optimizer, allowing WCOJ to be used for sub-plans of a query, improving performance for queries with large intermediate results. Umbra extends the query compilation approach from Hyper with a low-latency backend, Flying Start, which emits x86 machine code in a single pass. Umbra also supports User-Defined Operators (UDOs), which extend the DBMS functionality to support custom algorithms written in C++.
Umbra is the new DBMS built at the Technical University of Munich (TUM) after the HyPer project. The Umbra project was initiated in 2018 by Prof. Thomas Neumann and advised by Prof. Alfons Kemper, with frequent collaborations with Prof. Viktor Leis and Prof. Jana Giceva.
Umbra performs dictionary encoding of strings.
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.
Relational Array / Matrix / Vector
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.
Umbra supports B²-Tree indexes, a modified version of a B+Tree which embeds another trie-based search tree within each page.
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.
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.
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.
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:
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.
Umbra uses data-centric query processing, executing operators tuple-at-a-time.
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:
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.
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.
Umbra supports querying of Apache Parquet files.
Decomposition Storage Model (Columnar)
Umbra stores relations in B+Trees using the PAX layout for leaf pages.
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.
Technische Universität München