Datalog is an increasingly popular recursive query language that is declarative by design, meaning its programs must be translated by an engine into the actual physical execution plan. When generating this plan, a central decision is how to physically represent all involved relations, an aspect in which existing Datalog engines are surprisingly restrictive and often resort to one-size-fits-all solutions. The reason for this is that the typical execution plan of a Datalog program not only performs a single type of operation against the physical representations, but a mixture of operations, such as insertions, lookups, and containment-checks. Further, the relevance of each operation type highly depends on the workload characteristics, which range from familiar properties such as the size, multiplicity, and arity of the individual relations to very specific Datalog properties, such as the "interweaving" of rules when relations occur multiple times, and in particular the recursiveness of the query which might generate new tuples on the fly during evaluation. This indicates that a variety of physical representations, each with its own strengths and weaknesses, is required to meet the specific needs of different workload situations. To evaluate this, we conduct an in-depth experimental study of the interplay between potentially suitable physical representations and seven dimensions of workload characteristics that vary across actual Datalog programs, revealing which properties actually matter. Based on these insights, we design an automatic selection mechanism that utilizes a set of decision trees to identify suitable physical representations for a given workload.

In recent work, it has been shown that NVIDIA's ray tracing cores on RTX video cards can be exploited to realize hardware-accelerated lookups for GPU-resident database indexes. This is done by materializing all keys as triangles in a 3D scene. Lookups are performed by firing rays into the scene and utilizing the built-in index structure to detect collisions with triangles in a hardware-accelerated fashion. While this approach, called RTIndeX (or RX for short), is indeed promising, it currently suffers from three limitations: (1) significant memory overhead per key, (2) slow range lookups, and (3) poor updateability. In this work, we show that all three problems can be tackled by a single design change: Generalizing RX to become a coarse-granular index cgRX, which no longer indexes individual keys, but key buckets. We show that representing buckets in 3D space such that the lookup of a key is performed both correctly and efficiently is highly nontrivial and requires a careful orchestration of positioning triangles and firing rays in a specific sequence. Our experimental evaluation shows that cgRX offers the most bang for the buck(et) by providing a up to 6.9 x higher ratio of throughput to memory footprint than comparable baselines (that support range lookups). At the same time, cgRX improves the range-lookup performance over RX by up to 15 x and offers practical updatability that is up to 5.6x faster than rebuilding from scratch

Data processing in climate research regularly involves analyzing massive datasets, particularly atmospheric model data that spans around the globe. A typical task is to align this model data with measurement series for validation or trend analysis. Unfortunately, for this task, traditional join operations prove extremely inefficient: They load vast amounts of data into main-memory only to discard most of it afterwards due to the high selectivity typically occurring in these joins.To address this issue, we introduce a new operation we call the Gather Join. This method optimizes highly selective join operations by directly loading only the portions of the larger dataset that are actually relevant to the join result. We achieve this by exploiting the spatio-temporal information that is typically encoded in the file structure of the dataset. We present three different strategies for realizing the Gather Join, where we integrate the operation in the cluster computing framework Apache Spark to handle the multidimensional atmospheric datasets stored in NetCDF files. Our results show that the Gather Join outperforms the traditional join operation by a factor of up to 135x for the tested datasets. Increasing the selectivity of the join query is expected to further enhance these performance gains.

In main-memory column stores, column scans are one of the base operations performed when answering analytical queries. Typically, one or multiple columns must be filtered with respect to the given query predicate, which, by default, involves inspecting all data of the involved columns. To reduce the amount of data to scan, there exist essentially two strategies: (1) Create a coarse-granular index on the column, then use it for early pruning during each scan. While creating such an index is relatively lightweight, unfortunately, accessing the relevant portions of the column through the index causes unpleasant overhead during scanning. (2) Create materialized views that contain semantic portions of the column and filter on these. While this enables fast scans, unfortunately, it requires physical copying and causes significant space overhead. To break this trade-off, in the following, we propose a view-based strategy that avoids any physical copying of column data while providing optimal scan performance. We achieve this by utilizing tools of the virtual memory subsystem provided by the OS: On the lowest level, we materialize all columns within physical main memory. On top of that, we allow the creation of arbitrarily many partial views in virtual memory that map to subsets of the physical columns having certain properties of interest. Creation, maintenance, and usage of these partial virtual views happens fully adaptively as a side-product of scan-based query processing.

Research projects in the database community are often evaluated based on experimental results. A typical evaluation setup looks as follows: Multiple methods to compare with each other are embedded in a single shared benchmarking codebase. In this codebase, all methods execute an identical workload to collect the individual execution times. This seems reasonable: Since the only difference between individual test runs are the methods themselves, any observed time difference can be attributed to these methods. Also, such a benchmarking codebase can be used for gradual optimization: If one method runs slowly, its code can be optimized and re-evaluated. If its performance improves, this improvement can be attributed to the particular optimization.

Data management on GPUs has become increasingly relevant due to a tremendous rise in processing power and available GPU memory. Similar to main-memory systems, there is a need for performant GPU-resident index structures to speed up query processing. Unfortunately, mapping indexes efficiently to the highly parallel and hard-to-program hardware is challenging and often fails to yield the desired performance and flexibility. Instead of proposing yet another hand-tailored index, we investigate whether we can exploit an indexing mechanism that is already built into modern GPUs: The raytracing hardware accelerator provided by NVIDIA RTX GPUs. To do so, we re-phrase the database indexing problem as a raytracing problem, where we express the dataset to be indexed as objects in a 3D scene, and point/range lookups as rays across the scene. In this combination, coined RX in the following, lookups are performed as intersection tests in hardware by dedicated raytracing cores. To analyze the pros, cons, and usefulness of the raytracing pipeline for database indexing, we carefully evaluate RX along fourteen dimensions and demonstrate its competitiveness and potential in a large variety of situations.

Research in atmospheric physics, meteorology, and weather prediction requires the processing of very large multi-dimensional observational or modeled datasets on a daily basis. One of the numerous existing array engines looks like the natural choice for this task. Interestingly, the actual data analysis situation in the community looks surprisingly different: Researchers often process their data manually using hand-written Python or Julia scripts that directly operate on the raw data files. This results in poor performance due to a lack of data-driven optimizations, as well as poor scalability due to being restricted to a single physical machine. Reasons for this trend lie in the high complexity and upfront effort associated with any specialized system: Distributed large-scale engines must be set up carefully and data must be be converted/transferred into the the proprietary representation of the system. The users, who are typically not computer scientists or data management experts, must adopt and use a specialized multi-dimensional query language to formulate their analytical tasks.

The volume of data that is processed and produced by modern data-intensive applications is constantly increasing. Of course, along with the volume, the interest in analyzing and interpreting this data increases as well. As a consequence, more and more DBMSs and processing frameworks are specialized towards the efficient execution of long-running, read-only analytical queries. Unfortunately, to enable analysis, the data first has to be moved from the source application to the analytics tool via a lengthy ETL process, which increases the runtime and complexity of the analysis pipeline. In this work, we advocate to simply skip ETL altogether. With AnyOLAP, we can perform online analysis of data directly within the source application and while it is running. In the proposed demonstration, the audience will get the chance to put AnyOLAP to the test on a set of data-intensive applications that are supposed to be analyzed while they are up and running. As the entire analysis pipeline of AnyOLAP will be exposed to the audience in form of live and interactive visualizations, users will be able to experience the benefits of true online analysis firsthand.

Within the last few years, a countless number of blockchain systems have emerged on the market, each one claiming to revolutionize the way of distributed transaction processing in one way or the other. Many blockchain features, such as byzantine fault tolerance, are indeed valuable additions in modern environments. However, despite all the hype around the technology, many of the challenges that blockchain systems have to face are fundamental transaction management problems. These are largely shared with traditional database systems, which have been around for decades already. These similarities become especially visible for systems, that blur the lines between blockchain systems and classical database systems. A great example of this is Hyperledger Fabric, an open-source permissioned blockchain system under development by IBM. By implementing parallel transaction processing, Fabric's workflow is highly motivated by optimistic concurrency control mechanisms in classical database systems. This raises two questions: (1)~Which conceptual similarities and differences do actually exist between a system such as Fabric and a classical distributed database system? (2)~Is it possible to improve on the performance of Fabric by transitioning technology from the database world to blockchains and thus blurring the lines between these two types of systems even further? To tackle these questions, we first explore Fabric from the perspective of database research, where we observe weaknesses in the transaction pipeline. We then solve these issues by transitioning well-understood database concepts to Fabric, namely transaction reordering as well as early transaction abort. Our experimental evaluation under the Smallbank benchmark as well as under a custom workload shows that our improved version Fabric++ significantly increases the throughput of successful transactions over the vanilla version by up to a factor of 12x, while decreasing the average latency to almost half.

Database indexes are a core technique to speed up data retrieval in any kind of data processing system. However, in the presence of schemas with many attributes it becomes infeasible to create indexes for all columns, as maintenance costs and space requirements are simply too high. In these situations, a much more promising approach is to adaptively index the data, i.e. the database gradually partitions (or cracks) those columns that are frequently used in selections. In doing so, the "indexedness" of a table adapts to the requirements of the workload. A large body of work has investigated database cracking, which is a subset of adaptive indexing.

In nature, many species became extinct as they could not adapt quickly enough to their environment. They were simply not fit enough to adapt to more and more challenging circumstances. Similar things happen when algorithms are too static to cope with particular challenges of their "environment", be it the workload, the machine, or the user requirements. In this regard, in this paper we explore the well-researched and fascinating family of adaptive indexing algorithms. Classical adaptive indexes solely adapt the indexedness of the data to the workload. However, we will learn that so far we have overlooked a second higher level of adaptivity, namely the one of the indexing algorithm itself. We will coin this second level of adaptivity meta-adaptivity. Based on a careful experimental analysis, we will develop an adaptive index, which realizes meta-adaptivity by (1) generalizing the way reorganization is performed, (2) reacting to the evolving indexedness and varying reorganization effort, and (3) defusing skewed distributions in the input data. As we will demonstrate, this allows us to emulate the characteristics of a large set of specialized adaptive indexing algorithms. In an extensive experimental study we will show that our meta-adaptive index is extremely fit in a variety of environments and outperforms a large amount of specialized adaptive indexes under various query access patterns and key distributions.

Efficient transaction management is a delicate task. As systems face transactions of inherently different types, ranging from point updates to long-running analytical queries, it is hard to satisfy their requirements with a single execution engine. Unfortunately, most systems rely on such a design that implements its parallelism using multi-version concurrency control. While MVCC parallelizes short-running OLTP transactions well, it struggles in the presence of mixed workloads containing long-running OLAP queries, as scans have to work their way through vast amounts of versioned data. To overcome this problem, we reintroduce the concept of hybrid processing and combine it with state-of-the-art MVCC: OLAP queries are outsourced to run on separate virtual snapshots while OLTP transactions run on the most recent version of the database. Inside both execution engines, we still apply MVCC.

Memory management is one of the most boring topics in database research. It plays a minor role in tasks like free-space management or efficient space usage. Here and there we also realize its impact on database performance when worrying about NUMA-aware memory allocation, data compacting, snapshotting, and defragmentation. But, overall, let's face it: the entire topic sounds as exciting as 'garbage collection' or 'debugging a program for memory leaks'. What if there were a technique that would promote memory management from a third class helper thingie to a first class citizen in algorithm and systems design? What if that technique turned the role of memory management in a database system (and any other data processing system) upside-down? What if that technique could be identified as a key for re-designing various core algorithms with the effect of outperforming existing state-of-the-art methods considerably? Then we would write this paper. We introduce RUMA: Rewired User-space Memory Access. It allows for physiological data management, i.e. we allow developers to freely rewire the mappings from virtual to physical memory (in user space) while at the same time exploiting the virtual memory support offered by hardware and operating system. We show that fundamental database building blocks such as array operations, partitioning, sorting, and snapshotting benefit strongly from RUMA.

Partitioning a dataset into ranges is a task that is common in various applications such as sorting [1,6,7,8,9] and hashing [3] which are in turn building blocks for almost any type of query processing. Especially radix-based partitioning is very popular due to its simplicity and high performance over comparison-based versions [6].

Adaptive indexing is a concept that considers index creation in databases as a by-product of query processing; as opposed to traditional full index creation where the indexing effort is performed up front before answering any queries. Adaptive indexing has received a considerable amount of attention, and several algorithms have been proposed over the past few years; including a recent experimental study comparing a large number of existing methods. Until now, however, most adaptive indexing algorithms have been designed single-threaded, yet with multi-core systems already well established, the idea of designing parallel algorithms for adaptive indexing is very natural. In this regard, and to the best of our knowledge, only one parallel algorithm for adaptive indexing has recently appeared in the literature: The parallel version of standard cracking. In this paper we describe three alternative parallel algorithms for adaptive indexing, including a second variant of a parallel standard cracking algorithm. Additionally, we describe a hybrid parallel sorting algorithm, and a NUMA-aware method based on sorting. We then thoroughly compare all these algorithms experimentally. Parallel sorting algorithms serve as a realistic baseline for multi-threaded adaptive indexing techniques. In total we experimentally compare seven parallel algorithms. The initial set of experiments considered in this paper indicates that our parallel algorithms significantly improve over previously known ones. Our results also suggest that, although adaptive indexing algorithms are a good design choice in single-threaded environments, the rules change considerably in the parallel case. That is, in future highly-parallel environments, sorting algorithms could be serious alternatives to adaptive indexing.

Database cracking has been an area of active research in recent years. The core idea of database cracking is to create indexes adaptively and incrementally as a side-product of query processing. Several works have proposed different cracking techniques for different aspects including updates, tuple-reconstruction, convergence, concurrency-control, and robustness. However, there is a lack of any comparative study of these different methods by an independent group. In this paper, we conduct an experimental study on database cracking. Our goal is to critically review several aspects, identify the potential, and propose promising directions in database cracking. With this study, we hope to expand the scope of database cracking and possibly leverage cracking in database engines other than MonetDB. We repeat several prior database cracking works including the core cracking algorithms as well as three other works on convergence (hybrid cracking), tuple-reconstruction (sideways cracking), and robustness (stochastic cracking) respectively. We evaluate these works and show possible directions to do even better. We further test cracking under a variety of experimental settings, including high selectivity queries, low selectivity queries, and multiple query access patterns. Finally, we compare cracking against different sorting algorithms as well as against different main-memory optimised indexes, including the recently proposed Adaptive Radix Tree (ART). Our results show that: (i) the previously proposed cracking algorithms are repeatable, (ii) there is still enough room to significantly improve the previously proposed cracking algorithms, (iii) cracking depends heavily on query selectivity, (iv) cracking needs to catch up with modern indexing trends, and (v) different indexing algorithms have different indexing signatures.