About

With mutable, our goal is to develop a database system that allows for efficient prototyping of research ideas while striving for competitive performance with state-of-the-art systems.

In database research, performance is often considered a measure of novelty and quality, and so one is frequently confronted with the question how to evaluate or assess a new research idea. Consider for instance the development and evaluation of a new join algorithm. There are two extremes to approaching this task: start from scratch or implement into an existing system. The former approach allows for a more detailed evaluation of the algorithm in a controlled environment. However, the downside is a considerable development effort, e.g. input data must be provided in a suitable format to the join algorithm. Furthermore, it is difficult to compare the findings with related work and estimate its behaviour in existing systems. The latter approach enables focusing on implementing the join algorithm by relying on existing infrastructure. Despite the fact that these systems evolved over time and were developed by domain experts, certain design decisions that were made induce notable overhead, like a sub-optimal data layout. This negatively affects the ability to evaluate the performance of the join algorithm and to reason about experimental results.

The development of mutable aims to overcome these obstacles through the following contributions:

clean interfaces for a separation of concerns,
modern programming techniques to achieve abstraction without cost,
modular design for interchangeable components.

With the design of mutable, we are able to implement research ideas with low effort by leveraging abstraction while achieving competitive performance.

Defining Papers

Immanuel Haffner, Jens Dittrich mutable - A Modern DBMS for Research and Fast Prototyping CIDR 2023
Few to zero DBMSs provide extensibility together with implementations of modern concepts, like query compilation for example. We see this as an impeding factor in academic research in our domain. Therefore, in this work, we present mutable, a system developed at our group, that is fitted to academic research and education. mutable features a modular design, where individual components can be composed to form a complete system. Each component can be replaced by an alternative implementation, thereby mutating the system. Our fine-granular design of components allows for precise mutation of the system. Metaprogramming and just-in-time compilation are used to remedy abstraction overheads. In this demo, we present the high-level design goals of mutable, discuss our vision of a modular design, present some of the components, provide an outlook to research we conducted within mutable, and demonstrate some developer-facing features.
```
@inproceedings{haffner23mutable,
    author    = {Haffner, Immanuel and Dittrich, Jens},
    title     = {mu\emph{t}able: A Modern DBMS for Research and Fast Prototyping},
    year      = {2023},
    publisher = {cidrdb.org}
}
                                        
```
Immanuel Haffner, Jens Dittrich A Simplified Architecture for Fast, Adaptive Compilation and Execution of SQL Queries EDBT 2023
Query compilation is crucial to efficiently execute query plans. In the past decade, we have witnessed considerable progress in this field, including compilation with LLVM, adaptively switching from interpretation to compiled code, as well as adaptively switching from non-optimized to optimized code. All of these ideas aim to reduce latency and/or increase throughput. However, these approaches require immense engineering effort, a considerable part of which includes reengineering very fundamental techniques from the compiler construction community, like register allocation or machine code generation techniques studied in this field for decades.
In this paper, we argue that we should design compiling query engines conceptually very differently: rather than racing against the compiler construction community - a race we cannot win in the long run - we argue that code compilation and execution techniques should be fully delegated to an existing engine rather than being reinvented by database architects. By carefully choosing a suitable code compilation and execution engine we are able to get just-in-time code compilation (including the full range from non-optimized to fully optimized code) as well as adaptive execution in the sense of dynamically replacing code at runtime - for free! Moreover, as we rely on the vibrant compiler construction community, it is foreseeable that we will easily benefit from future improvements without any additional engineering effort. We propose this conceptual architecture using WebAssembly and V8 as an example. In addition, we implement this architecture as part of a real database system: mutable. We provide an extensive experimental study using TPC-H data and queries. Our results show that we are able to match or even outperform state-of-the-art systems like HyPer.
```
@inproceedings{haffner23simplified,
    author    = {Haffner, Immanuel and Dittrich, Jens},
    title     = {A Simplified Architecture for Fast, Adaptive Compilation and Execution of SQL Queries},
    year      = {2023},
    booktitle = {Proceedings of the 26th International Conference on Extending Database
                 Technology, {EDBT} 2023, Ioannina, Greece, March 28 - March 31, 2023},
    publisher = {OpenProceedings.org}
}
                                        
```
Immanuel Haffner, Jens Dittrich Efficiently Computing Join Orders with Heuristic Search SIGMOD 2023
Join order optimization is one of the most fundamental problems in processing queries on relational data. It has been studied extensively for almost four decades now. Still, because of its NP hardness, no generally efficient solution exists and the problem remains an important topic of research. The scope of algorithms to compute join orders ranges from exhaustive enumeration, to combinatorics based on graph properties, to greedy search, to genetic algorithms, to recently investigated machine learning. A few works exist that use heuristic search to compute join orders. However, a theoretical argument why and how heuristic search is applicable to join order optimization is lacking.
In this work, we investigate join order optimization via heuristic search. In particular, we provide a strong theoretical framework, in which we reduce join order optimization to the shortest path problem. We then thoroughly analyze the properties of this problem and the applicability of heuristic search. We devise crucial optimizations to make heuristic search tractable. We implement join ordering via heuristic search in a real DBMS and conduct an extensive empirical study. Our findings show that for star- and clique-shaped queries, heuristic search finds optimal plans an order of magnitude faster than current state of the art. Our suboptimal solutions further extend the cost/time Pareto frontier.
```
@inproceedings{haffner23joinorders,
    author    = {Haffner, Immanuel and Dittrich, Jens},
    title     = {Efficiently Computing Join Orders with Heuristic Search},
    year      = {2023},
    booktitle = {SIGMOD},
    publisher = {ACM}
}
                                        
```