Information Systems Group - Prof. Jens Dittrich

Overview

Modern enterprises need to pick the right DBMSs e.g. OLTP, OLAP, streaming systems, scan-oriented systems among others, each tailored to a specific use-case application, for their data managing problems. This makes using specialized solutions for each application costly due to licensing fees, integration overhead and DBA costs.

Additionally, it is tedious to integrate these specialized solutions together. Alternatively, enterprises use a single specialized DBMS for all applications and thereby compromise heavily on performance. Further, a particular DBMS (e.g. row store) cannot adapt and change into a different DBMS (e.g. streaming system), as the workload changes, even though much of the code and technology is replicated anyways and database store being the only major change.

Therefore, the goal of OctopusDB is to fit several use-cases while reducing costs, boosting performance, and improving the ease-of-use at the same time. We believe that by dropping the assumption of a fixed store, as in traditional systems like row store and column store, and instead having a flexible storage scheme we can realize much better performance without compromising the cost. For this, our objective is to abstract all storage layouts into a single abstract concept and thus have a single optimization problem in place of heterogenous database tunings in traditional databases. Currently, we are investigating a number of physical storage level decisions such as layout, partitioning, cracking and developing techniques and algorithms to achieve them automatically and dynamically in OctopusDB.

Publications

Victor Alvarez, Felix Martin Schuhknecht, Jens Dittrich, Stefan Richter
Main Memory Adaptive Indexing for Multi-core Systems
SIGMOD DaMoN 2014.
Abstract / [bib], Slides
Main Memory Adaptive Indexing for Multi-core Systems
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.
```
@inproceedings{ASDR14_DAMON,
  author    = {Victor Alvarez, Felix Martin Schuhknecht, Jens Dittrich, Stefan Richter},
  title     = {{Main Memory Adaptive Indexing for Multi-core Systems}},
  booktitle = {DaMoN},
  year      = {June 23, 2014},
}
```
Victor Alvarez, Felix Martin Schuhknecht, Jens Dittrich, Stefan Richter
Main Memory Adaptive Indexing for Multi-core Systems
arXiv:1404.2034 [cs.DB], April 9, 2014.
Abstract / [bib]
Main Memory Adaptive Indexing for Multi-core Systems
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 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; along a variant of a recently published parallel version of radix sort. Parallel sorting algorithms serve as a realistic baseline for multi-threaded adaptive indexing techniques. In total we experimentally compare seven parallel algorithms. Additionally, we extensively profile all considered algorithms. The initial set of experiments considered in this paper indicates that our parallel algorithms significantly improve over previously known ones. Our results 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.
```
@article{ASDR14,
   author    = {Victor Alvarez, Felix Martin Schuhknecht, Jens Dittrich, Stefan Richter},
   title     = {{Main Memory Adaptive Indexing for Multi-core Systems}},
   journal   = {CoRR},
   volume    = {arXiv:1404.2034},
   year      = {April 9, 2014},
}
```
Felix Martin Schuhknecht, Alekh Jindal, Jens Dittrich
The Uncracked Pieces in Database Cracking
Best paper award
PVLDB 2013/VLDB 2014. Abstract / [bib] / SourceCode
The Uncracked Pieces in Database Cracking
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.
```
@article{SJD13,
   author    = {Felix Martin Schuhknecht and Alekh Jindal and Jens Dittrich},
   title     = {{The Uncracked Pieces in Database Cracking}},
   journal   = {PVLDB},
   volume    = {7},
   number    = {2},
   year      = {2013},
   }
```
Alekh Jindal, Endre Palatinus, Vladimir Pavlov, Jens Dittrich
A Comparison of Knives for Bread Slicing
VLDB 2013/PVLDB, Riva, Italy. VLDB 2013/PVLDB, Riva, Italy. Abstract / [bib]
A Comparison of Knives for Bread Slicing
Vertical partitioning is a crucial step in physical database design in row-oriented databases. A number of vertical partitioning algorithms have been proposed over the last three decades for a variety of niche scenarios. In principle, the underlying problem remains the same: decompose a table into one or more vertical partitions. However, it is not clear how good different vertical partitioning algorithms are in comparison to each other. In fact, it is not even clear how to experimentally compare different vertical partitioning algorithms. In this paper, we present an exhaustive experimental study of several vertical partitioning algorithms. We categorize vertical partitioning algorithms into 5 major classes, based on their approach to the vertical partitioning problem. We survey 6 vertical partitioning algorithms and discuss their pros and cons. We identify the major differences in the use-case settings for different algorithms and describe how to make an apples-to-apples comparison of different vertical partitioning algorithms under the same setting. We propose 4 metrics to compare vertical partitioning algorithms. We show experimental results from the TPC-H and SSB benchmark and present four key lessons learned: (1) we can do 4 orders of magnitude less computation and still find the optimal layouts, (2) the benefits of vertical partitioning depend strongly on the database buffer size, (3) HillClimb is the best vertical partitioning algorithm, and (4) vertical partitioning for TPC-H-like benchmarks can improve over column layout by only up to 5%.
```
@article{JPP+13,
   author    = {Alekh Jindal and Endre Palatinus and Vladimir Pavlov and Jens Dittrich},
   title     = {{A Comparison of Knives for Bread Slicing}},
   journal   = {PVLDB},
   volume    = {6},
   number    = {6},
   year      = {2013},
   pages     = {361-372},
   }
```
Alekh Jindal, Jorge-Arnulfo Quiane-Ruiz, Jens Dittrich
WWHow! Freeing Data Storage from Cages
CIDR 2013, Outrageous Ideas and Vision Track, Asilomar, USA. Abstract / [bib]
WWHow! Freeing Data Storage from Cages
Efficient data storage is a key component of data managing systems to achieve good performance. However, currently data storage is either heavily constrained by static decisions (e.g. ﬁxed data stores in DBMSs) or left to be tuned and conﬁgured by users (e.g. manual data backup in File Systems). In this paper, we take a holistic view of data storage and envision a virtual storage layer. Our virtual storage layer provides a uniﬁed storage framework for several use-cases including personal, enterprise, and cloud storage.
```
@inproceedings{JQD13,
   author    = {Alekh Jindal and Jorge-Arnulfo Quian{\'e}-Ruiz and Jens Dittrich},
   title     = {{WWHow! Freeing Data Storage from Cages}},
   booktitle = {CIDR},
   year      = {2013},
   }
```
Alekh Jindal, Felix Martin Schuhknecht, Jens Dittrich, Karen Khachatryan, Alexander Bunte
How Achaeans Would Construct Columns in Troy
CIDR 2013, Asilomar, USA. Abstract / [bib]
How Achaeans Would Construct Columns in Troy
Column stores are becoming popular with data analytics in modern enterprises. However, traditionally, database vendors offer column stores as a different database product all together. As a result there is an all-or-none situation for column store features. To bridge the gap, a recent effort introduced column store functionality in SQL server (a row store) by making deep seated changes in the database system. However, this approach is expensive in terms of time and effort. In addition, it is limited to SQL server. In this paper, we present Trojan Columns, a novel technique for injecting column store functionality into a given closed source row-oriented com- mercial database system. Trojan Columns does not need access to the source code of the database system. Instead, it uses UDFs as a pluggable storage layer to write and read data. Furthermore, Trojan Columns is transparent to users, i.e. users do not need to change their schema and their queries remain almost unchanged. We demonstrate Trojan Columns on a row-oriented commercial database DBMS-X, a closed source top notch database system. We show experimental results from TPC-H benchmarks. Our results show that Trojan Columns can improve the performance of DBMS- X by a factor of up to 9 for TPC-H queries and up to factor 17 for micro-benchmarks — without changing the source code and with minimal user effort.
```
@inproceedings{JSD+13,
   author    = {Alekh Jindal and Felix Schuhknecht and Jens Dittrich and Karen Khachatryan and Alexander Bunte},
   title     = {{How Achaeans Would Construct Columns in Troy}},
   booktitle = {CIDR},
   year      = {2013},
   }
```
Alekh Jindal, Jens Dittrich
Relax and Let the Database do the Partitioning Online
VLDB BIRTE 2011, Seattle, USA. TR Abstract / [bib]
Relax and Let the Database do the Partitioning Online
Vertical and Horizontal partitions allow database administrators (DBAs) to considerably improve the performance of business intelligence applications. However, finding and defining suitable horizontal and vertical partitions is a daunting task even for experienced DBAs. This is because the DBA has to understand the physical query execution plans for each query in the workload very well to make appropriate design decisions. To facilitate this process several algorithms and advisory tools have been developed over the past years. These tools, however, still keep the DBA in the loop. This means, the physical design cannot be changed without human intervention. This is problematic in situations where a skilled DBA is either not available or the workload changes over time, e.g. due to new DB applications, changed hardware, an increasing dataset size, or bursts in the query workload. In this paper, we present AutoStore: a self-tuning data store which rather than keeping the DBA in the loop, monitors the current workload and partitions the data automatically at checkpoint time intervals — without human intervention. This allows AutoStore to gradually adapt the partitions to best fit the observed query workload. In contrast to previous work, we express partitioning as a One-Dimensional Partitioning Problem (1DPP), with Horizontal (HPP) and Vertical Partitioning Problem (VPP) being just two variants of it. We provide an efficient O^2 P (One-dimensional Online Partitioning) algorithm to solve 1DPP. O^2 P is faster than the specialized affinity-based VPP algorithm by more than two orders of magnitude, and yet it does not loose much on partitioning quality. AutoStore is a part of the OctopusDB vision of a One Size Fits All Database System [13]. Our experimental results on TPC-H datasets show that AutoStore outperforms row and column layouts by up to a factor of 2.
```
@inproceedings{JD11,
   author    = {Alekh Jindal and Jens Dittrich},
   title     = {{Relax and Let the Database Do the Partitioning Online}},
   booktitle = {BIRTE},
   year      = {2011},
   pages     = {65-80},
   }
			
```
Alekh Jindal, Jorge-Arnulfo Quiane-Ruiz, Jens Dittrich
Trojan Data Layouts: Right Shoes for a Running Elephant
ACM SOCC 2011, Cascais, Portugal. Abstract / [bib]
Trojan Data Layouts: Right Shoes for a Running Elephant
MapReduce is becoming ubiquitous in large-scale data analysis. Several recent works have shown that the performance of Hadoop MapReduce could be improved, for instance, by creating indexes in a non-invasive manner. However, they ignore the impact of the data layout used inside data blocks of Hadoop Distributed File System (HDFS). In this paper, we analyze different data layouts in detail in the context of MapReduce and argue that Row, Column, and PAX layouts can lead to poor system performance. We propose a new data layout, coined Trojan Layout, that internally organizes data blocks into attribute groups according to the workload in order to improve data access times. A salient feature of Trojan Layout is that it fully preserves the fault-tolerance properties of MapReduce. We implement our Trojan Layout idea in HDFS 0.20.3 and call the resulting system Trojan HDFS. We exploit the fact that HDFS stores multiple replicas of each data block on different computing nodes. Trojan HDFS automatically creates a different Trojan Layout per replica to better fit the workload. As a result, we are able to schedule incoming MapReduce jobs to data block replicas with the most suitable Trojan Layout. We evaluate our approach using three real-world workloads. We compare Trojan Layouts against Hadoop using Row and PAX layouts. The results demonstrate that Trojan Layout allows MapReduce jobs to read their input data up to 4.8 times faster than Row layout and up to 3.5 times faster than PAX layout.
```
@inproceedings{JQD11,
   author    = {Alekh Jindal and Jorge-Arnulfo Quian{\'e}-Ruiz and Jens Dittrich},
   title     = {{Trojan data layouts: right shoes for a running elephant}},
   booktitle = {SoCC},
   year      = {2011},
   pages     = {21},
   }
```
Jens Dittrich, Alekh Jindal
Towards a One Size Fits All Database Architecture
CIDR 2011, Outrageous Ideas and Vision Track, Asilomar.
(youtube)
Best Outrageous Ideas and Vision Paper Award (CCC Blog) Abstract / [bib]
Towards a One Size Fits All Database Architecture
We propose a new type of database system coined OctopusDB. Our approach suggests a unified, one size fits all data processing architecture for OLTP, OLAP, streaming systems, and scan-oriented database systems. OctopusDB radically departs from existing architectures in the following way: it uses a logical event log as its primary storage structure. To make this approach efficient we introduce the concept of Storage Views (SV) , i.e. secondary, alternative physical data representations covering all or subsets of the primary log. OctopusDB (1) allows us to use different types of SVs for different subsets of the data; and (2) eliminates the need to use different types of database systems for different applications. Thus, based on the workload, OctopusDB emulates different types of systems (row stores, column stores, streaming systems, and more importantly, any hybrid combination of these). This is a feature impossible to achieve with traditional DBMSs.
```
@inproceedings{DJ11,
   author    = {Jens Dittrich and Alekh Jindal},
   title     = {{Towards a One Size Fits All Database Architecture}},
   booktitle = {CIDR},
   year      = {2011},
   pages     = {195-198},
   }
```
Alekh Jindal
The Mimicking Octopus: Towards a one-size-fits-all Database Architecture
VLDB 2010 PhD Workshop, Singapore. Abstract

The Mimicking Octopus: Towards a one-size-fits-all Database Architecture
Modern enterprises need to pick the right DBMSs e.g. OLTP, OLAP, streaming systems, scan-oriented systems among others, each tailored to a speciﬁc use-case application, for their data managing problems. This makes using specialized solutions for each application costly due to licensing fees, integration overhead and DBA costs. Additionally, it is tedious to integrate these specialized solutions together. Alternatively, enterprises use a single specialized DBMS for all applications and thereby compromise heavily on performance. Further, a particular DBMS (e.g. row store) cannot adapt and change into a different DBMS (e.g. streaming system), as the workload changes, even though much of the code and technology is replicated anyways. In this paper we discuss building a new type of database system which ﬁts several use-cases while reducing costs, boosting performance, and improving the ease-of-use at the same time. We present the research challenges in building such a system. We believe that by dropping the assumption of a ﬁxed store, as in traditional systems like row store and column store, and instead having a ﬂexible storage scheme we can realize much better performance without compromising the cost. We outline OctopusDB as our plan for such a system and discuss how it can mimic several existing as well as newer systems. To do so, we present the concept of storage view as an abstraction of all storage layouts in OctopusDB. We discuss how the heterogenous optimization problems in OctopusDB can be reduced to a single problem: storage view selection; and describe how a Holistic Storage View Optimizer can deal with it. We present simulation results to justify our core idea and experimental evidence on our initial prototype to demonstrate our approach. Finally, we detail the next steps in our work.

OctopusDB

Overview

Why did we name the system "OctopusDB"?

People

Publications