Big Data Analytics Group

Extending SQL to Return a Subdatabase
Every SQL statement is limited to return a single, possibly denormalized table. This approximately 50-year-old design decision has far-reaching consequences. The most apparent problem is the redundancy introduced through denormalization, which can result in long transfer times of query results and high memory usage for materializing intermediate results. Additionally, regardless of their goals, users are forced to fit query computations into one single result, mixing the data retrieval and transformation aspect of SQL. Moreover, both problems violate the principles and core ideas of normal forms. In this paper, we argue for eliminating the single-table limitation of SQL. We extend SQL's SELECT clause by the keyword `RESULTDB' to support returning a result subdatabase. Our extension has clear semantics, i.e., by annotating any existing SQL statement with the RESULTDB keyword, the DBMS returns the tables participating in the query, each restricted to the relevant tuples that occur in the traditional single-table query result. Thus, we do not denormalize the query result in any way. Our approach has significant, far-reaching consequences, impacting the querying of hierarchical data, materialized views, and distributed databases, while maintaining backward compatibility. In addition, our proposal paves the way for a long list of exciting future research opportunities. We propose multiple algorithms to integrate our feature into both closed-source and open-source database systems. For closed-source systems, we provide several SQL-based rewrite methods. In addition, we present an efficient algorithm for cyclic and acyclic join graphs that we integrated into an open-source database system. We conduct a comprehensive experimental study. Our results show that returning multiple individual result sets can significantly decrease the result set size. Furthermore, our rewrite methods and algorithm introduce minimal overhead and can even outperform single-table execution in certain cases.

@misc{Nix2025ExtendingSQL,
      title={Extending SQL to Return a Subdatabase},
      author={Joris Nix and Jens Dittrich},
      year={2025}
}
                        

Generic Version Control: Configurable Versioning for Application-Specific Requirements
Even though Multi-Version Concurrency Control (MVCC) and Git look very different from a user point of view, both systems conceptually do very similar things. In this paper, we thoroughly compare both systems w.r.t. their logical and physical differences and commonalities. We argue that both systems converge to a common one-size-fits-all system. One key to that system is the observation that nested transactions and the Git commit-graph are conceptually the same thing. Another crucial insight is the need for database researchers to rethink conflict resolution and reconciliation. This shift can reduce abort rates, address concurrency issues within the database layer, and eliminate unnecessary round-trips to the application layer. Based on our observations, we propose a unified system, Generic Version Control (GenericVC), combining the best of both worlds. In fact, by combining features from both Git and MVCC, we obtain more than the sum of its parts: the ability to support new hybrid use case

@misc{YD2025L,
      title={Generic Version Control: Configurable Versioning for Application-Specific Requirements},
      author={Gunce Su Yilmaz and Jens Dittrich},
      booktitle = {CIDR},
      year={2025}
}
                        

What if an SQL Statement Returned a Database?
Every SQL statement is limited to return a single, possibly denormalized, table. This design decision has far reaching consequences. (1.) for databases users in terms of slow query performance, long query result transfer times, usability-issues of SQL in web applications and object-relational mappers. In addition, (2.) for database architects it has consequences when designing query optimizers leading to logical (algebraic) join enumeration effort, memory consumption for intermediate result materialization, and physical operator selection effort. So basically, the entire query optimization stack is shaped by that design decision. In this paper, we argue that the single-table limitation should be dropped. We extend the SELECT-clause of SQL by a keyword 'RESULTDB' to support returning a result database. Our approach has clear semantics, i.e. our extended SQL returns subsets of all tables with only those tuples that would be part of the traditional (single-table) query result set, however without performing any denormalization through joins. Our SQL-extension is downward compatible. Moreover, we discuss the surprisingly long list of benefits of our approach. First, for database users: far simpler and more readable application code, better query performance, smaller query results, better query result transfer times. Second, for database architects, we present how to leverage existing closed source systems as well as change open source database systems to support our feature. We propose a couple of algorithms to integrate our feature into both closed-source as well as open source database systems. We present an initial experimental study with promising results.

@misc{nix2023sql,
      title={What if an SQL Statement Returned a Database?},
      author={Joris Nix and Jens Dittrich},
      year={2023},
      eprint={2312.00638},
      archivePrefix={arXiv},
      primaryClass={cs.DB}
}
                        

Efficiently Computing Join Orders with Heuristic Search
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}
}
                       

mutable: A Modern DBMS for Research and Fast Prototyping
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}
}
                       

A Simplified Architecture for Fast, Adaptive Compilation and Execution of SQL Queries
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}
}
                       

Code

A Critical Analysis of Recursive Model Indexes
The recursive model index (RMI) has recently been introduced as a machine-learned replacement for traditional indexes over sorted data, achieving remarkably fast lookups. Follow-up work focused on explaining RMI's performance and automatically configuring RMIs through enumeration. Unfortunately, configuring RMIs involves setting several hyperparameters, the enumeration of which is often too time-consuming in practice. Therefore, in this work, we conduct the first inventor-independent broad analysis of RMIs with the goal of understanding the impact of each hyperparameter on performance. In particular, we show that in addition to model types and layer size, error bounds and search algorithms must be considered to achieve the best possible performance. Based on our findings, we develop a simple-to-follow guideline for configuring RMIs. We evaluate our guideline by comparing the resulting RMIs with a number of state-of-the-art indexes, both learned and traditional. We show that our simple guideline is sufficient to achieve competitive performance with other learned indexes and RMIs whose configuration was determined using an expensive enumeration procedure. In addition, while carefully reimplementing RMIs, we are able to improve the build time by 2.5x to 6.3x.

@article{maltry22critical,
  author    = {Marcel Maltry and Jens Dittrich},
  title     = {A Critical Analysis of Recursive Model Indexes},
  journal   = {Proc. {VLDB} Endow.},
  volume    = {15},
  number    = {5},
  pages     = {1079--1091},
  year      = {2022},
  url       = {https://www.vldb.org/pvldb/vol15/p1079-maltry.pdf}
}
                                        

Code
The next 50 Years in Database Indexing or: The Case for Automatically Generated Index Structures
Index structures are a building block of query processing and computer science in general. Since the dawn of computer technology there have been index structures. And since then, a myriad of index structures are being invented and published each and every year. In this paper we argue that the very idea of "inventing an index" is a misleading concept in the first place. It is the analogue of "inventing a physical query plan". This paper is a paradigm shift in which we propose to drop the idea to handcraft index structures (as done for binary search trees over B-trees to any form of learned index) altogether. We present a new automatic index breeding framework coined Genetic Generic Generation of Index Structures (GENE). It is based on the observation that almost all index structures are assembled along three principal dimensions: (1) structural building blocks, e.g., a B-tree is assembled from two different structural node types (inner and leaf nodes), (2) a couple of invariants, e.g., for a B-tree all paths have the same length, and (3) decisions on the internal layout of nodes (row or column layout, etc.). We propose a generic indexing framework that can mimic many existing index structures along those dimensions. Based on that framework we propose a generic genetic index generation algorithm that, given a workload and an optimization goal, can automatically assemble and mutate, in other words 'breed' new index structure 'species'. In our experiments we follow multiple goals. We reexamine some good old wisdom from database technology. Given a specific workload, will GENE even breed an index that is equivalent to what our textbooks and papers currently recommend for such a workload? Or can we do even more? Our initial results strongly indicate that generated indexes are the next step in designing index structures.

@article{DNS21_GENE,
  author    = {Jens Dittrich and Joris Nix and Christian Sch{\"{o}}n},
  title     = {The next 50 Years in Database Indexing or: The Case for Automatically Generated Index Structures},
  journal   = {Proc. {VLDB} Endow.},
  volume    = {15},
  number    = {3},
  pages     = {527--540},
  year      = {2021},
  url       = {http://www.vldb.org/pvldb/vol15/p527-dittrich.pdf}
}
                                        

A Critical Analysis of Recursive Model Indexes
Learned indexes like the recursive model index (RMI) have recently been introduced as a machine-learned replacement for traditional indexes with possibly game-changing results for how database indexes are constructed and used. Has the time come to discard our good old hand-crafted index structures that have been invented over the past decades? We believe that such a bold claim -- with substantial impact on the database world -- is worth a deep examination that clarifies when RMIs have benefits and when not. We present the first inventor-independent study critically examining RMIs. To do so, we revisit the original paper and carefully reimplemented RMIs. We proceed by reproducing the most important experiments from the original paper and follow-up papers all involving the inventors. We extend the original experiments by adding more baselines and considering more configurations. Further, we give insight on why and when RMIs perform well. Our results show that while the general observation of the original work that "any index is a model of the underlying data" is truly inspiring, some conclusions drawn in the original work may mislead database architects to take unfortunate and too radical design decisions. In particular, we show that other types of indexes outperform RMIs in some situations. In addition, we will show that the performance of RMIs is surprisingly sensitive to different data distributions. We conclude by giving a clear guideline for database architects when to use RMIs, other learned indexes, or traditional indexes.

@misc{maltry2021critical,
    title={A Critical Analysis of Recursive Model Indexes},
    author={Marcel Maltry and Jens Dittrich},
    year={2021},
    eprint={2106.16166},
    archivePrefix={arXiv},
    primaryClass={cs.DB}
}
                        

Fast Compilation and Execution of SQL Queries with WebAssembly
Interpreted execution of queries, as in the vectorized model, suffers from interpretation overheads. By compiling queries this interpretation overhead is eliminated at the cost of a compilation phase that delays execution, sacrificing latency for throughput. For short-lived queries, minimizing latency is important, while for long-running queries throughput outweighs latency. Because neither a purely interpretive model nor a purely compiling model can provide low latency and high throughput, adaptive solutions emerged. Adaptive systems seamlessly transition from interpreted to compiled execution, achieving low latency for short-lived queries and high throughput for long-running queries. However, these adaptive systems pose an immense development effort and require expert knowledge in both interpreter and compiler design.
In this work, we investigate query execution by compilation to WebAssembly. We are able to compile even complex queries in less than a millisecond to machine code with near-optimal performance. By delegating execution of WebAssembly to the V8 engine, we are able to seamlessly transition from rapidly compiled yet non-optimized code to thoroughly optimized code during execution. Our approach provides both low latency and high throughput, is adaptive out of the box, and is straight forward to implement. The drastically reduced compilation times even enable us to explore generative programming of library code, that is fully inlined by construction. Our experimental evaluation confirms that our approach yields competitive and sometimes superior performance.

@misc{haffner2021fast,
    title={Fast Compilation and Execution of SQL Queries with WebAssembly},
    author={Immanuel Haffner and Jens Dittrich},
    year={2021},
    eprint={2104.15098},
    archivePrefix={arXiv},
    primaryClass={cs.DB}
}
                        

Database (Lecture) Streams on the Cloud: An Experience Report on Teaching an Undergrad Database Lecture during a Pandemic
This is an experience report on teaching the undergrad lecture Big Data Engineering at Saarland University in summer term 2020 online. We describe our teaching philosophy, the tools used, what worked and what did not work. As we received extremely positive feedback from the students, we will continue to use the same teaching model for other lectures in the future.

@inproceedings{DM21_TEACHING,
    author    = {Jens Dittrich and Marcel Maltry},
    title     = {{Database (Lecture) Streams on the Cloud: An Experience Report on Teaching an Undergrad Database Lecture during a Pandemic}},
    journal   = {Datenbank-Spektrum},
    volume    = {?},
    year      = {2021}
}

ChainifyDB: How to Blockchainify any Data Management System
Today's permissioned blockchain systems come in a stand-alone fashion and require the users to integrate yet another full-fledged transaction processing system into their already complex data management landscape. This seems odd as blockchains and traditional DBMSs share considerable parts of their processing stack. Therefore, rather than replacing the established infrastructure, we advocate to "chainify" existing DBMSs by installing a lightweight blockchain layer on top. Unfortunately, this task is challenging: Users might have different black-box DBMSs in operation, which potentially behave differently. Furthermore, we cannot trust any component of the network at any point in time. To deal with such setups, we introduce a new processing model called Whatever-Voting (WV), pronounced [weave]. It allows us to create a highly flexible permissioned blockchain layer coined chainifyDB that (a) is centered around bullet-proof database technology, (b) can be easily integrated into an existing heterogeneous database landscape, (c) is able to recover deviating organizations, and (d) adds only up to 8.5% of overhead on the underlying database systems while providing an up to 6x higher throughput than Hyperledger Fabric.

Database (Lecture) Streams on the Cloud: An Experience Report on Teaching an Undergrad Database Lecture during a Pandemic
This is an experience report on teaching the undergrad lecture Big Data Engineering at Saarland University in summer term 2020 online. We describe our teaching philosophy, the tools used, what worked and what did not work. As we received extremely positive feedback from the students, in the future, we will continue to use the same teaching model for other lectures.

@inproceedings{DM20_TEACHING,
    author    = {Jens Dittrich and Marcel Maltry},
    title     = {{Database (Lecture) Streams on the Cloud: An Experience Report on Teaching an Undergrad Database Lecture during a Pandemic}},
    journal   = {CoRR},
    volume    = {abs/2010.07011},
    year      = {2020}
}

There is No Such Thing as an "Index"! or: The next 500 Indexing Papers
Index structures are a building block of query processing and computer science in general. Since the dawn of computer technology there have been index structures. And since then, a myriad of index structures are being invented and published each and every year. In this paper we argue that the very idea of "inventing an index" is a misleading concept in the first place. It is the analogue of "inventing a physical query plan". This paper is a paradigm shift in which we propose to drop the idea to handcraft index structures (as done for binary search trees over B-trees to any form of learned index) altogether. We present a new automatic index breeding framework coined Genetic Generic Generation of Index Structures (G3oI). It is based on the observation that almost all index structures are assembled along three principal dimensions: (1) structural building blocks, e.g., a B-tree is assembled from two different structural node types (inner and leaf nodes), (2) a couple of invariants, e.g., for a B-tree all paths have the same length, and (3) decisions on the internal layout of nodes (row or column layout, etc.). We propose a generic indexing framework that can mimic many existing index structures along those dimensions. Based on that framework we propose a generic genetic index generation algorithm that, given a workload and an optimization goal, can automatically assemble and mutate, in other words 'breed' new index structure 'species'. In our experiments we follow multiple goals. We reexamine some good old wisdom from database technology. Given a specific workload, will G3oI even breed an index that is equivalent to what our textbooks and papers currently recommend for such a workload? Or can we do even more? Our initial results strongly indicate that generated indexes are the next step in designing "index structures".

@inproceedings{DNS20_G3OI,
    author    = {Jens Dittrich and Joris Nix and Christian Schön},
    title     = {{There is No Such Thing as an "Index"! or: The next 500 Indexing Papers}},
    journal   = {CoRR},
    volume    = {abs/2009.10669},
    year      = {2020}
}

ChainifyDB: How to Blockchainify any Data Management System
Today's permissioned blockchain systems come in a stand-alone fashion and require the users to integrate yet another full-fledged transaction processing system into their already complex data management landscape. This seems odd as blockchains and traditional DBMSs share large parts of their processing stack. Thus, rather than replacing the established data systems altogether, we advocate to simply 'chainify' them with a blockchain layer on top. Unfortunately, this task is far more challenging than it sounds: As we want to build upon heterogeneous transaction processing systems, which potentially behave differently, we cannot rely on every organization to execute every transaction deterministically in the same way. Further, as these systems are already filled with data and being used by top-level applications, we also cannot rely on every organization being resilient against tampering with its local data. Therefore, in this work, we will drop these assumptions and introduce a powerful processing model that avoids them in the first place: The so-called Whatever-LedgerConsensus (WLC) model allows us to create a highly flexible permissioned blockchain layer coined ChainifyDB that (a) is centered around bullet-proof database technology, (b) makes even stronger guarantees than existing permissioned systems, (c) provides a sophisticated recovery mechanism, (d) has an up to 6x higher throughput than the permissioned blockchain system Fabric, and (e) can easily be integrated into an existing heterogeneous database landscape.

@inproceedings{SSDA19_CHAINIFYDB,
    author    = {Felix Martin Schuhknecht and Ankur Sharma and Jens Dittrich and Divya Agrawal},
    title     = {{ChainifyDB: How to Blockchainify any Data Management System}},
    journal   = {CoRR},
    volume    = {abs/1912.04820},
    year      = {2019}
}
                        

The Case for Deep Query Optimisation
Query Optimisation (QO) is the most important optimisation problem in databases. The goal of QO is to compute the best physical plan uner a given cost model. In that process, physical operators are used as building blocks for the planning and optimisation process. In this paper, we propose to deepen that process. We present Deep Query Optimisation (DQO). In DQO, we break up the abstraction of a ‘physical’ operator to consider more fine-granular subcomponents. These subcomponents are then used to enumerate (sub-)plans both offline and at query time. This idea triggers several exciting research directions: (1) How exactly can DQO help to compute better plans than (shallow) QO and at which costs? (2) DQO can be used to precompute and synthesise database operators and any other database component as Materialised Algorithmic Views (MAVs). (3) We identify the Algorithmic View Selection Problem (AVSP), i.e. which MAVs should be materialised when? This paper presents the high-level idea of DQO using an analogy inspired from biology. Then we proceed to question the terms ‘physical’ and ‘physical operator’. We present experiments with a ‘physical operator’ formerly known as ‘hash-based grouping’. We benchmark that operator both independently as well as in the context of DQO-enabled dynamic programming. We conclude by sketching a DQO research agenda.

@inproceedings{DN20_CIDR,
    author    = {Jens Dittrich and Joris Nix},
    title     = {{The Case for Deep Query Optimisation}},
    booktitle = {CIDR},
    year      = {2020}
} 

The Case for Deep Query Optimisation
Query Optimisation (QO) is the most important optimisation problem in databases. The goal of QO is to compute the best physical plan uner a given cost model. In that process, physical operators are used as building blocks for the planning and optimisation process. In this paper, we propose to deepen that process. We present Deep Query Optimisation (DQO). In DQO, we break up the abstraction of a ‘physical’ operator to consider more fine-granular subcomponents. These subcomponents are then used to enumerate (sub-)plans both offline and at query time. This idea triggers several exciting research directions: (1) How exactly can DQO help to compute better plans than (shallow) QO and at which costs? (2) DQO can be used to precompute and synthesise database operators and any other database component as Materialised Algorithmic Views (MAVs). (3) We identify the Algorithmic View Selection Problem (AVSP), i.e. which MAVs should be materialised when? This paper presents the high-level idea of DQO using an analogy inspired from biology. Then we proceed to question the terms ‘physical’ and ‘physical operator’. We present experiments with a ‘physical operator’ formerly known as ‘hash-based grouping’. We benchmark that operator both independently as well as in the context of DQO-enabled dynamic programming. We conclude by sketching a DQO research agenda.

@inproceedings{DN19_ARXIV,
    author    = {Jens Dittrich and Joris Nix},
    title     = {{The Case for Deep Query Optimisation}},
    journal   = {CoRR},
    volume    = {abs/908.08341},
    year      = {2019}
}                       

Make Thunderbolts Less Frightening - Predicting Extreme Weather Using Deep Learning
Forecasting severe weather conditions is still a very challenging and computationally expensive task due to the enormous amount of data and the complexity of the underlying physics. Machine learning approaches and especially deep learning have however shown huge improvements in many research areas dealing with large datasets in recent years. In this work, we tackle one specific sub-problem of weather forecasting, namely the prediction of thunderstorms and lightning. We propose the use of a convolutional neural network architecture inspired by UNet++ and ResNet to predict thunderstorms as a binary classification problem based on satellite images and lightnings recorded in the past. We achieve a probability of detection of more than 94% for lightnings within the next 15 minutes while at the same time minimizing the false alarm ratio compared to previous approaches.

@inproceedings{SD19_ARXIV,
    author    = {Christian {Sch{\"o}n} and Jens Dittrich},
    title     = {{Make Thunderbolts Less Frightening - Predicting Extreme Weather Using Deep Learning}},
    journal   = {CoRR},
    volume    = {abs/1912.01277},
    year      = {2019},
    note      = {Accepted as Poster for the Workshop Tackling Climate Change with Machine Learning at NeurIPS 2019}
}
                        

Blurring the Lines between Blockchains and Database Systems: the Case of Hyperledger Fabric
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 sys- tems 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 un- der 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 con- ceptual 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 transac- tions over the vanilla version by up to a factor of 12x, while decreasing the average latency to almost half.

@inproceedings{SSDD19_SIGMOD,
    author    = {Ankur Sharma and Felix Martin Schuhknecht and Divya Agrawal and Jens Dittrich},
    title     = {{Blurring the Lines between Blockchains and Database Systems: the Case of Hyperledger Fabric}},
    booktitle = {SIGMOD},
    year      = {2019},
}
                        

The Error is the Feature: how to Forecast Lightning using a Model Prediction Error
Despite the progress throughout the last decades, weather forecasting is still a challenging and computationally expensive task. Most models which are currently operated by meteo- rological services around the world rely on numerical weather prediction, a system based on mathematical algorithms describing physical effects. Recent progress in artificial intelligence however demonstrates that machine learning can be successfully applied to many research fields, especially areas dealing with big data that can be used for training. Current approaches to predict thunderstorms often focus on indices describing temper- ature differences in the atmosphere. If these indices reach a critical threshold, the forecast system emits a thunderstorm warning. Other meteorological systems such as radar and lightning detection systems are added for a more precise prediction. This paper describes a new approach to the prediction of lightnings based on machine learning rather than complex numerical computations. The error of optical flow algorithms applied to images of meteorological satellites is interpreted as a sign for convection potentially leading to thunderstorms. These results are used as the base for the feature generation phase incorporating different convolution steps. Tree classifier models are then trained to predict lightnings within the next few hours (called nowcasting) based on these features. The evaluation section compares the predictive power of the different models and the impact of different features on the classification result.

@inproceedings{SDM19_SIGKDD,
    author = {Christian {Sch{\"o}n} and Jens {Dittrich} and Richard {M{\"u}ller}},
    title = "{The Error is the Feature: how to Forecast Lightning using a Model Prediction Error}",
    booktitle = {SIGKDD},
    year = {2019},
}
                        

How to Databasify a Blockchain: the Case of Hyperledger Fabric
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 (BFT), 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 having a relaxed view on BFT, the transaction pipeline of Fabric highly resembles the workflow of classical distributed databases 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 shows that our improved version Fabric++ significantly increases the throughput of successful transactions over the vanilla version by up to a factor of 3x.

@inproceedings{SSAD18_ARXIV,
    author    = {Ankur Sharma and Felix Martin Schuhknecht and Divya Agrawal and Jens Dittrich},
    title     = {{How to Databasify a Blockchain: the Case of Hyperledger Fabric}},
    journal   = {CoRR},
    volume    = {abs/1810.13177},
    year      = {2018},
}                       

An Analysis and Comparison of Database Cracking Kernels
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 in- dexes 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 re- quirements of the workload. A large body of work has investigated database cracking, which is a subset of adaptive indexing. Irrespective of their algorithmic behavior, essentially all these works have in common, that the proposed methods use a simple two-sided in-place cracking kernel at the core, which performs a partitioning step. As this partitioning makes a large portion of the total indexing effort, the choice of the kernel can make a factor of two difference in the running time for a method sitting on top. To approach the topic, we first perform an experimental evalua- tion of existing state-of-the-art kernels and study their respective downsides in detail. Based on the gained insights, we propose both an advanced version of the best existing kernel as well as a new and unconventional approach, which utilizes features of the operating system as well as data parallelism. In our final evaluation of all kernels, we vary entry size, index layout, selectivity, and number of threads, and provide a decision tree to select the best cracking kernel for the respective situation.

@inproceedings{HSD18_DAMON,
    author    = {Immanuel Haffner and Felix Martin Schuhknecht and Jens Dittrich},
    title     = {{An Analysis and Comparison of Database Cracking Kernels}},
    booktitle = {SIGMOD DaMoN},
    year      = {2018},
}                       

Accelerating Analytical Processing in MVCC using Fine-Granular High-Frequency Virtual Snapshotting
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 shortrunning 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. The most significant challenge of a hybrid approach is to generate the snapshots at a high frequency. Previous approaches heavily suffered from the high cost of snapshot creation. In our approach termed AnKer, we follow the current trend of co-designing underlying system components and the DBMS, to overcome the restrictions of the OS by introducing a custom system call vm_snapshot. It allows fine-granular snapshot creation that is orders of magnitudes faster than state-of-the-art approaches. Our experimental evaluation on an HTAP workload based on TPC-C transactions and OLAP queries show that our snapshotting mechanism is more than a factor of 100x faster than fork-based snapshotting and that the latency of OLAP queries is up to a factor of 4x lower than MVCC in a single execution engine. Besides, our approach enables a higher OLTP throughput than all state-of-the-art methods.

@inproceedings{SSD18_SIGMOD,
    author    = {Ankur Sharma and Felix Martin Schuhknecht and Jens Dittrich},
    title     = {{Accelerating Analytical Processing in MVCC using Fine-Granular High-Frequency Virtual Snapshotting}},
    booktitle = {SIGMOD},
    year      = {2018},
}                       

The Case for Automatic Database Administration using Deep Reinforcement Learning
Like any large software system, a full-fledged DBMS offers an overwhelming amount of configuration knobs. These range from static initialisation parameters like buffer sizes, degree of concurrency, or level of replication to complex runtime decisions like creating a secondary index on a particular column or reorganising the physical layout of the store. To simplify the configuration, industry grade DBMSs are usually shipped with various advisory tools, that provide recommendations for given workloads and machines. However, reality shows that the actual configuration, tuning, and maintenance is usually still done by a human administrator, relying on intuition and experience. Recent work on deep reinforcement learning has shown very promising results in solving problems, that require such a sense of intuition. For instance, it has been applied very successfully in learning how to play complicated games with enormous search spaces. Motivated by these achievements, in this work we explore how deep reinforcement learning can be used to administer a DBMS. First, we will describe how deep reinforcement learning can be used to automatically tune an arbitrary software system like a DBMS by defining a problem environment. Second, we showcase our concept of NoDBA at the concrete example of index selection and evaluate how well it recommends indexes for given workloads.

@inproceedings{SSD18_ARXIV,
    author    = {Ankur Sharma and Felix Martin Schuhknecht and Jens Dittrich},
    title     = {{The Case for Automatic Database Administration using Deep Reinforcement Learning}},
    journal   = {CoRR},
    volume    = {abs/1801.05643},
    year      = {2018},
}                       

Adaptive 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.

@inproceedings{SDL18_ICDE,
    author    = {Felix Martin Schuhknecht and Jens Dittrich and Laurent Linden},
    title     = {{Adaptive Adaptive Indexing}},
    booktitle = {ICDE},
    year      = {2018},
}                       

Accelerating Analytical Processing in MVCC using Fine-Granular High-Frequency Virtual Snapshotting
Efficient transactional management is a delicate task. As systems face transactions of inherently different types, ranging from point updates to long running analytical computations, it is hard to satisfy their individual requirements with a single processing component. Unfortunately, most systems nowadays rely on such a single component that implements its parallelism using multi-version concurrency control (MVCC). While MVCC parallelizes short-running OLTP transactions very well, it struggles in the presence of mixed workloads containing long-running scan-centric OLAP queries, as scans have to work their way through large amounts of versioned data. To overcome this problem, we propose a system, which reintroduces the concept of heterogeneous transaction processing: OLAP transactions are outsourced to run on separate (virtual) snapshots while OLTP transactions run on the most recent representation of the database. Inside both components, MVCC ensures a high degree of concurrency. The biggest challenge of such a heterogeneous approach is to generate the snapshots at a high frequency. Previous approaches heavily suffered from the tremendous cost of snapshot creation. In our system, we overcome the restrictions of the OS by introducing a custom system call vm_snapshot, that is hand-tailored to our precise needs: it allows fine-granular snapshot creation at very high frequencies, rendering the snapshot creation phase orders of magnitudes faster than state-of-the-art approaches. Our experimental evaluation on a heterogeneous workload based on TPC-H transactions and handcrafted OLTP transactions shows that our system enables significantly higher analytical transaction throughputs on mixed workloads than homogeneous approaches. In this sense, we introduce a system that accelerates Analytical processing by introducing custom Kernel functionalities: AnKerDB.

@inproceedings{SSD17_ARXIV,
    author    = {Ankur Sharma and Felix Martin Schuhknecht and Jens Dittrich},
    title     = {{Accelerating Analytical Processing in {MVCC} using Fine-Granular High-Frequency Virtual Snapshotting}},
    journal   = {CoRR},
    volume    = {abs/1709.04284},
    year      = {2017},
}                       

An Experimental Analysis of Different Key-Value Stores and Relational Databases
Nowadays, databases serve two main workloads: Online Transaction Processing (OLTP) and Online Analytic Processing (OLAP). For decades, relational databases dominated both areas. With the hype on NoSQL databases, the picture has changed. Initially designed as inter-process hash tables handling OLTP requested, some key-value store vendors have started to tackle the area of OLAP as well. Therefore, in this performance study, we compare the relational databases PostgreSQL, MonetDB, and HyPer with the key-value stores Redis and Aerospike in their write, read, and analytical capabilities. Based on the results, we investigate the reasons of the database’s respective advantages and disadvantages.

@inproceedings{GSD17_BTW,
    author    = {David Gembalczyk and Felix Martin Schuhknecht and Jens Dittrich},
    title     = {{An Experimental Analysis of Different Key-Value Stores and Relational Databases}},
    booktitle = {Datenbanksysteme f{\"{u}}r Business, Technologie und Web {(BTW})},
    year      = {2017},
}                       

Runtime Fragility in Main Memory
In this paper we investigate the following problem: Given a database workload (tables and queries), which data layout (row, column or a suitable PAX-layout) should we choose in order to get the best possible performance? We show that this is not an easy problem. We explore careful combinations of various parameters that have an impact on the performance including: (1) the schema, (2) the CPU architecture, (3) the compiler, and (4) the optimization level. We include a CPU from each of the past 4 generations of Intel CPUs.
In addition, we demonstrate the importance of taking variance into account when deciding on the optimal storage layout. We observe considerable variance throughout our measurements which makes it difficult to argue along means over different runs of an experiment. Therefore, we compute confidence intervals for all measurements and exploit this to detect outliers and define classes of methods that we are not allowed to distinguish statistically. The variance of different performance measurements can be so significant that the optimal solution may not be the best one in practice.
Our results also indicate that a carefully or ill-chosen compilation setup can trigger a performance gain or loss of factor 1.1 to factor 25 in even the simplest workloads: a table with four attributes and a simple query reading those attributes. This latter observation is not caused by variance in the measured runtimes, but due to using a different compiler setup. Besides the compilation setup, the data layout is another source of query time fragility. Various size metrics of the memory subsystem are round numbers in binary, or put more simply: powers of 2 in decimal. System engineers have followed this tradition over time. Surprisingly, there exists a use-case in query processing where using powers of 2 is always a suboptimal choice, leading to one more cause of fragile query times. Using this finding, we will show how to improve tuple-reconstruction costs by using a novel main-memory data-layout.

@inproceedings{DP16_IMDM,
    author    = {Endre Palatinus, Jens Dittrich},
    title     = {{Runtime Fragility in Main Memory}},
    booktitle = {IMDM @ VLDB2016},
    year      = {2016},
}

SourceCode RUMA has it: Rewired User-space Memory Access is Possible!
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.

@inproceedings{SDS16_VLDB,
    author    = {Felix Martin Schuhknecht, Jens Dittrich, Ankur Sharma},
    title     = {{RUMA has it: Rewired User-space Memory Access is Possible!}},
    booktitle = {PVLDB, to appear},
    year      = {2016},
}

Patterns in Data Management (A Flipped Textbook)
This book is not a standard textbook on database techniques. This book was written extending and complementing preexisting educational videos on database technology I designed and recorded in winter 2013/14. The main goal of these videos was to use them in my flipped classroom “Database Systems” which is an intermediate-level university course designed for B.Sc. students in their third year or M.Sc. students of computer science and related disciplines. Though in general my students liked both the flipped classroom model and (most of) the videos, several students asked for an additional written script that would allow them to quickly lookup explanations for material in text that would otherwise be hard to re-find in the videos. Therefore, in spring 2015, I started working on such a course script which more and more evolved into something that I feel comfortable calling it a book. One central question I had to confront was: would I repeat all material from the videos in the textbook? In other words, would the book be designed to work without the videos? I quickly realized that writing such an old-fashioned text-oriented book, a “textbook”, wouldn’t be the appropriate thing to do anymore in 2015. My videos as well as the accompanying material are freely available to everyone anyways. And unless you are sitting on the local train from Saarbrücken to Neustadt, you will almost always have Internet access to watch them. In fact, downloading the videos in advance isn’t terribly hard anyway. This observation changed the original purpose of what this book would be good for: not so much the primary source of the course’s content, but a different view on that content, explaining that content where possible in other words. In addition, one goal was to be concise in the textual explanations allowing you to quickly re-find and remember things you learned from the videos without going through a large body of text. Therefore you will find several things in this book, including: (1) links to videos as well as slides I designed for this course, (2) for each video a textual summary of the video content phrased as questions and answers plus the most important slides and graphics from the videos, (3) Q&As as well as (4) exercises.

@BOOK{Dit15_book,
    author    = {Jens Dittrich},
    title     = {{Patterns in Data Management}},
    year      = {2016},
    url       = {http://www.amazon.com/Patterns-Data-Management-Flipped-Textbook-ebook/dp/B01BEXUYMK}
}

An Experimental Comparison of Thirteen Relational Equi-Joins in Main Memory
Relational equi-joins are at the heart of almost every query plan. They have been studied, improved, and reexamined on a regular basis since the existence of the database community. In the past four years several new join algorithms have been proposed and experimentally evaluated. Some of those papers contradict each other in their experimental findings. This makes it surprisingly hard to answer a very simple question: what is the fastest join algorithm in 2015? In this paper we will try to develop an answer. We start with an end-to-end black box comparison of the most important methods. Afterwards, we inspect the internals of these algorithms in a white box comparison. We derive improved variants of state-of-the-art join algorithms by applying optimizations like software-write combine buffers, various hash table implementations, as well as NUMA-awareness in terms of data placement and scheduling. We also inspect various radix partitioning strategies. Eventually, we are in the position to perform a comprehensive comparison of thirteen different join algorithms. We factor in scaling effects in terms of size of the input datasets, the number of threads, different page sizes, and data distributions. Furthermore, we analyze the impact of various joins on an (unchanged) TPC-H query. Finally, we conclude with a list of major lessons learned from our study and a guideline for practitioners implementing massive main-memory joins. As is the case with almost all algorithms in databases, we will learn that there is no single best join algorithm. Each algorithm has its strength and weaknesses and shines in different areas of the parameter space.

@inproceedings{SCD16_SIGMOD,
    author    = {Stefan Schuh, Xiao Chen, Jens Dittrich},
    title     = {{An Experimental Comparison of Thirteen Relational Equi-Joins in Main Memory}},
    booktitle = {SIGMOD},
    year      = {2016},
}

A Seven-Dimensional Analysis of Hashing Methods and its Implications on Query Processing
Hashing is a solved problem. It allows us to get constant time access for lookups. Hashing is also simple. It is safe to use an arbitrary method as a black box and expect good performance and optimizations to hashing can only improve it by a negligible delta. Why are all of the previous statements plain wrong? That is what this paper is about. In this paper we thoroughly study hashing for integer keys and carefully analyze the most common hashing methods in a five-dimensional requirements space: (1) data-distribution, (2) load factor, (3) dataset size, (4) read/write-ratio, and (5) un/successful-ratio. Each point in that design space may potentially suggest a different hashing scheme, and additionally also a different hash function. We show that a right or wrong decision in picking the right hashing scheme and hash function combination may lead to significant difference in performance. To substantiate this claim, we carefully analyze two additional dimensions: (6) five representative hashing schemes (which includes an improved variant of Robin Hood hashing), (7) four important classes of hash functions widely used today. That is, we consider 20 different combinations in total. Finally, we also provide a glimpse about the effect of table memory layout and the use of SIMD instructions. Our study clearly indicates that picking the right combination may have considerable impact on insert and lookup performance, as well as memory footprint. A major conclusion of our work is that hashing should be considered a white box before blindly using it in applications, such as query processing. Finally, we also provide a strong guideline about when to use which hashing method.

@inproceedings{RAD16_VLDB,
    author    = {Stefan Richter, Victor Alvarez, Jens Dittrich},
    title     = {{A Seven-Dimensional Analysis of Hashing Methods and its Implications on Query Processing}},
    booktitle = {PVLDB},
    year      = {2015},
}

An Experimental Evaluation and Analysis of 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. Our 2014 VLDB paper “The Uncracked Pieces in Database Cracking” was the first comparative study of these different methods by an independent group. In this article, we extend our published experimental study on database cracking and bring it to an up-to-date state. 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. Additionally to our conference paper, we now also look at a recently published study about CPU efficiency (predication cracking). We evaluate these works and show possible directions to do even better. As a further extension, we evaluate the whole class of parallel cracking algorithms that were proposed in three recent works. Altogether, in this work we revisit 8 papers on database cracking and evaluate in total 18 cracking methods, 6 sorting algorithms, and 3 full index structures. Additionally, we test cracking under a variety of experimental settings, including high selectivity queries, low selectivity queries, varying selectivity, and multiple query access patterns. Finally, we compare cracking against different sorting algorithms as well as against different main-memory optimized 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) parallelizing cracking algorithms efficiently is a hard task, (iv) cracking depends heavily on query selectivity, (v) cracking needs to catch up with modern indexing trends, and (vi) different indexing algorithms have different indexing signatures.

@inproceedings{SJD15_VLDBJ,
    author    = {Felix Martin Schuhknecht, Alekh Jindal, Jens Dittrich},
    title     = {{An Experimental Evaluation and Analysis of Database Cracking}},
    booktitle = {VLDBJ},
    year      = {2015},
}

Janiform Intra-Document Analytics for Reproducible Research
Peer-reviewed publication of research papers is a cornerstone of science. However, one of the many issues of our publication culture is that our publications only publish a summary of the final result of a long project. This means that we put well-polished graphs describing (some) of our experimental results into our publications. However, the algorithms, input datasets, benchmarks, raw result datasets, as well as scripts that were used to produce the graphs in the first place are rarely published and typically not available to other researchers. Often they are only available when personally asking the authors. In many cases, however, they are not available at all. This means from a long workflow that led to producing a graph for a research paper, we only publish the final result rather than the entire workflow. This is unfortunate and has been criticized in various scientific communities. In this demo we argue that one part of the problem is our dated view on what a “document” and hence “a publication” is, should, and can be. As a remedy, we introduce portable database files (PDbF). These files are janiform, i.e. they are at the same time a standard static pdf as well as a highly dynamic (offline) HTML-document. PDbFs allow you to access the raw data behind a graph, perform OLAP-style analysis, and reproduce your own graphs from the raw data — all of this within a portable document. We demo a tool allowing you to create PDbFs smoothly from within LATEX. This tool allows you to preserve the workflow of raw measurement data to its final graphical output through all processing steps. Notice that this pdf already showcases our technology: rename this file to “.html” and see what happens (currently we support the desktop versions of Firefox, Chrome, and Safari). But please: do not try to rename this file to “.ova” and mount it in VirtualBox.

@inproceedings{DB15_VLDB,
    author    = {Jens Dittrich, Patrick Bender},
    title     = {{Janiform Intra-Document Analytics for Reproducible Research}},
    booktitle = {VLDB},
    year      = {2015},
}

SourceCode

On the Surprising Difficulty of Simple Things: the Case of Radix Partitioning
Partitioning a dataset into ranges is a task that is common in various applications such as sorting and hashing 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. In its most primitive form, coined original version from here on, it partitions a dataset into 2 to the power of R (where R ≤ 32) partitions: in the first pass over the data, we count for each partition the number of entries that will be sent to it. From this generated histogram, we calculate the start index of each partition. The second pass over the data finally copies the entries to their designated partitions. Despite of its simple nature, several interesting techniques can be applied to enhance this algorithm such as software-managed buffers, non-temporal streaming operations, prefetching, and memory layout with many variables having an influence on the performance like buffer sizes, number of partitions, and page sizes. Although being heavily used in the database literature, it is unclear how these techniques individually contribute to the performance of partitioning. Therefore, in this work we will incrementally extend the original version by the mentioned optimizations to carefully analyze the individual impact on the partitioning process. As a result this paper provides a strong guideline on when to use which optimization for partitioning.

@inproceedings{SKD15_VLDB,
    author    = {Felix Martin Schuhknecht, Pankaj Khanchandani, Jens Dittrich},
    title     = {{On the Surprising Difficulty of Simple Things: the Case of Radix Partitioning}},
    booktitle = {VLDB},
    year      = {2015},
}

A Comparison of Adaptive Radix Trees and Hash Tables
With prices of main memory constantly decreasing, people nowadays are more interested in performing their computations in main memory, and leave high I/O costs of traditional disk-based systems out of the equation. This change of paradigm, however, represents new challenges to the way data should be stored and indexed in main memory in order to be processed efficiently. Traditional data structures, like the venerable B-tree, were designed to work on disk-based systems, but they are no longer the way to go in main-memory systems, at least not in their original form, due to the poor cache utilization of the systems they run on. Because of this, in particular, during the last decade there has been a considerable amount of research on index data structures for main-memory systems. Among the most recent and more interesting data structures for main-memory systems there is the recently-proposed adaptive radix tree ARTful (ART for short). The authors of ART presented experiments that indicate that ART was clearly a better choice over other recent tree-based data structures like FAST and B+-trees. However, ART was not the first adaptive radix tree. To the best of our knowledge, the first was the Judy Array (Judy for short), and a comparison between ART and Judy was not shown. Moreover, the same set of experiments indicated that only a hash table was competitive to ART. The hash table used by the authors of ART in their study was a chained hash table, but this kind of hash tables can be suboptimal in terms of space and performance due to their potentially high use of pointers. In this paper we present a thorough experimental comparison between ART, Judy, two variants of hashing via quadratic probing, and three variants of Cuckoo hashing. These hashing schemes are known to be very efficient. For our study we consider whether the data structures are to be used as a non-covering index (relying on an additional store), or as a covering index (covering key-value pairs). We consider both OLAP and OLTP scenarios. Our experiments strongly indicate that neither ART nor Judy are competitive to the aforementioned hashing schemes in terms of performance, and, in the case of ART, sometimes not even in terms of space.

@inproceedings{ARCD15_ICDE,
    author    = {Victor Alvarez, Stefan Richter, Xiao Chen, Jens Dittrich},
    title     = {{A Comparison of Adaptive Radix Trees and Hash Tables}},
    booktitle = {ICDE},
    year      = {2015},
}

The Case for Small Data Management
Exabytes of data; several hundred thousand TPC-C transactions per second on a single computing core; scale-up to hundreds of cores and a dozen Terabytes of main memory; scale-out to thousands of nodes with close to Petabyte-sized main memories; and massively parallel query processing are a reality in data management. But, hold on a second: for how many users exactly? How many users do you know that really have to handle these kinds of massive datasets and extreme query workloads? On the other hand: how many users do you know that are fighting to handle relatively small datasets, say in the range of a few thousand to a few million rows per table? How come some of the most popular open source DBMS have hopelessly outdated optimizers producing inefficient query plans? How come people don’t care and love it anyway? Could it be that most of the world’s data management problems are actually quite small? How can we increase the impact of database research in areas when datasets are small? What are the typical problems? What does this mean for database research? We discuss research challenges, directions, and a concrete technical solution coined PDbF: Portable Database Files.

@inproceedings{Dit15_CIDR,
    author    = {Jens Dittrich},
    title     = {{The Case for Small Data Management}},
    booktitle = {CIDR},
    year      = {2015},
}

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},
}

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},
}

Die Umgedrehte Vorlesung — Chancen für die Informatiklehre
Dieser Artikel beschreibt die Erfahrung des Autors mit einer Umgedrehten Datenbankvorlesung. Bei einer Umgedrehten Vorlesung findet die Wissensaneignung zunächst mit Hilfe von Lehrvideos statt. In der ursprünglichen Vorlesungszeit wird das gelernte Material dann gemeinsam eingeübt. Dieses Vorlesungsformat ist ein hybrides Format zwischen traditioneller Vorlesung und den sogenannten MOOCs (Massive Open Online Courses).

@article{Dit13,
   author    = {Jens Dittrich},
   title     = {{Die Umgedrehte Vorlesung — Chancen für die Informatiklehre}},
   journal   = {Datenbank-Spektrum},
   volume    = {?},
   number    = {?},
   year      = {2013},
   pages     = {?},
   }
                        

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},
   }

Towards Zero-Overhead Static and Adaptive Indexing in Hadoop
Hadoop MapReduce has evolved to an important industry standard for massive parallel data processing and has become widely adopted for a variety of use cases. Recent works have shown that indexes can improve the performance of selective MapReduce jobs dramatically. However, one major weakness of existing approaches are high index creation costs. We present HAIL (Hadoop Aggressive Indexing Library), a novel indexing approach for HDFS and Hadoop MapReduce. HAIL creates different clustered indexes over terabytes of data with minimal, often invisible costs and it dramatically improves runtimes of several classes of MapReduce jobs. HAIL features two different indexing pipelines, static indexing and adaptive indexing. HAIL static indexing efficiently indexes datasets while uploading them to HDFS. Thereby, HAIL leverages the default replication of Hadoop and enhances it with logical replication. This allows HAIL to create multiple clustered indexes for a dataset, e.g. one for each physical replica. Still, in terms of upload time, HAIL matches or even improves over the performance of standard HDFS. Additionally, HAIL adaptive indexing allows for automatic, incremental indexing at job runtime with minimal runtime overhead. For example, HAIL adaptive indexing can completely index a dataset as byproduct of only four MapReduce jobs while incurring an overhead as low as 11% for the very first of those job only. In our experiments, we show that HAIL improves job runtimes by up to 68x over Hadoop. This article is an extended version of the VLDB 2012 paper “Only Aggressive Elephants are Fast Elephants” (PVLDB, 5(11):1591-1602, 2012).

@article{RQS+13,
   author    = {Stefan Richter and Jorge-Arnulfo Quian{\'e}-Ruiz  and Stefan Schuh and Jens Dittrich},
   title     = {{Towards Zero-Overhead Static and Adaptive Indexing in Hadoop}},
   journal   = {VLDB Journal},
   year      = {2013},
   }

Mosquito: Another One Bites the Data Upload STream
Mosquito is a lightweight and adaptive physical design framework for Hadoop. Mosquito connects to existing data pipelines in Hadoop MapReduce and/or HDFS, observes the data, and creates better physical designs, i.e. indexes, as a byproduct. Our approach is minimally invasive, yet it allows users and developers to easily improve the runtime of Hadoop. We present three important use cases: first, how to create indexes as a byproduct of data uploads into HDFS; second, how to create indexes as a byproduct of map tasks; and third, how to execute map tasks as a byproduct of HDFS data uploads. These use cases may even be combined.

@article{DRS+13,
   author    = {Stefan Richter and Jens Dittrich and Stefan Schuh and Tobias Frey},
   title     = {{Mosquito: Another One Bites the Data Upload STream}},
   journal   = {PVLDB},
   volume    = {6},
   number    = {12},
   year      = {2013},
   pages     = {unknown},
   }

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},
   }

Efficient OR Hadoop: Why Not Both?
In this article, we give an overview of research related to Big Data processing in Hadoop going on at the Information Systems Group at Saarland University. We discuss how to make Hadoop efficient. We briefly survey four of our projects in this context: Hadoop++, Trojan Layouts, HAIL, and LIAH. All projects aim to provide efficient physical layouts in Hadoop including vertically partitioned data layouts, clustered indexes, and adaptively created clustered indexes. Most of our techniques come (almost) for free: they create little to no overhead in comparison to standard Hadoop.

@article{DRS13,
   author    = {Jens Dittrich and Stefan Richter and Stefan Schuh},
   title     = {{Efficient OR Hadoop: Why Not Both?}},
   journal   = {Datenbank-Spektrum},
   volume    = {13},
   number    = {1},
   year      = {2013},
   pages     = {17-22},
   }

Towards Zero-Overhead Adaptive Indexing in Hadoop
Several research works have focused on supporting index access in MapReduce systems. These works have allowed users to significantly speed up selective MapReduce jobs by orders of magnitude. However, all these proposals require users to create indexes upfront, which might be a difficult task in certain applications (such as in scientific and social applications) where workloads are evolving or hard to predict. To overcome this problem, we propose LIAH (Lazy Indexing and Adaptivity in Hadoop), a parallel, adaptive approach for indexing at minimal costs for MapReduce systems. The main idea of LIAH is to automatically and incrementally adapt to users' workloads by creating clustered indexes on HDFS data blocks as a byproduct of executing MapReduce jobs. Besides distributing indexing efforts over multiple computing nodes, LIAH also parallelises indexing with both map tasks computation and disk I/O. All this without any additional data copy in main memory and with minimal synchronisation. The beauty of LIAH is that it piggybacks index creation on map tasks, which read relevant data from disk to main memory anyways. Hence, LIAH does not introduce any additional read I/O-costs and exploit free CPU cycles. As a result and in contrast to existing adaptive indexing works, LIAH has a very low (or invisible) indexing overhead, usually for the very first job. Still, LIAH can quickly converge to a complete index, i.e. all HDFS data blocks are indexed. Especially, LIAH can trade early job runtime improvements with fast complete index convergence. We compare LIAH with HAIL, a state-of-the-art indexing technique, as well as with standard Hadoop with respect to indexing overhead and workload performance.

@article{RQS+12,
   author    = {Stefan Richter and Jorge-Arnulfo Quian{\'e}-Ruiz and Stefan Schuh and Jens Dittrich},
   title     = {{Towards Zero-Overhead Adaptive Indexing in Hadoop}},
   journal   = {CoRR},
   volume    = {abs/1212.3480},
   year      = {2012},
   }

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. fixed data stores in DBMSs) or left to be tuned and configured 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 unified 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},
   }

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},
   }

Efficient Big Data Processing in Hadoop MapReduce
This tutorial is motivated by the clear need of many organizations, companies, and researchers to deal with big data volumes efficiently. Examples include web analytics applications, scientific applications, and social networks. A popular data processing engine for big data is Hadoop MapReduce. Early versions of Hadoop MapReduce suffered from severe performance problems. Today, this is becoming history. There are many techniques that can be used with Hadoop MapReduce jobs to boost performance by orders of magnitude. In this tutorial we teach such techniques. First, we will briefly familiarize the audience with Hadoop MapReduce and motivate its use for big data processing. Then, we will focus on different data management techniques, going from job optimization to physical data organization like data layouts and indexes. Throughout this tutorial, we will highlight the similarities and differences between Hadoop MapReduce and Parallel DBMS. Furthermore, we will point out unresolved research problems and open issues.

@article{DQ12,
   author    = {Jens Dittrich and Jorge-Arnulfo Quian{\'e}-Ruiz},
   title     = {{Efficient Big Data Processing in Hadoop MapReduce}},
   journal   = {PVLDB},
   volume    = {5},
   number    = {12},
   year      = {2012},
   pages     = {2014-2015},
   }

Only Aggressive Elephants are Fast Elephants
Yellow elephants are slow. A major reason is that they consume their inputs entirely before responding to an elephant rider’s orders. Some clever riders have trained their yellow elephants to only con- sume parts of the inputs before responding. However, the teaching time to make an elephant do that is high. So high that the teaching lessons often do not pay off. We take a different approach. We make elephants aggressive; only this will make them very fast. We propose HAIL (Hadoop Aggressive Indexing Library), an enhancement of HDFS and Hadoop MapReduce that dramatically improves runtimes of several classes of MapReduce jobs. HAIL changes the upload pipeline of HDFS in order to create different clustered indexes on each data block replica. An interesting feature of HAIL is that we typically create a win-win situation: we improve both data upload to HDFS and the runtime of the actual Hadoop MapReduce job. In terms of data upload, HAIL improves over HDFS by up to 60% with the default replication factor of three. In terms of query execution, we demonstrate that HAIL runs up to 68x faster than Hadoop. In our experiments, we use six clusters including physical and EC2 clusters of up to 100 nodes. A series of scalability experiments also demonstrates the superiority of HAIL.

@article{DQR+12,
   author    = {Jens Dittrich and Jorge-Arnulfo Quian{\'e}-Ruiz and Stefan Richter and Stefan Schuh and Alekh Jindal and J{\"o}rg Schad},
   title     = {{Only Aggressive Elephants are Fast Elephants}},
   journal   = {PVLDB},
   volume    = {5},
   number    = {11},
   year      = {2012},
   pages     = {1591-1602},
   }

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},
   }

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},
   }
                        

Paper Bricks: An Alternative to Complete-Story Peer Reviewing
The peer review system as used in several computer science communities has several flaws including long review times, overloaded reviewers, as well as fostering of niche topics. These flaws decrease quality, lower impact, slowdown the innovation process, and lead to frustration of authors, readers, and reviewers. In order to fix this, we propose a new peer review system termed paper bricks. Paper bricks has several advantages over the existing system including shorter publications, better competition for new ideas, as well as an accelerated innovation process. Furthermore, paper bricks may be implemented with minimal change to the existing peer review systems.

@article{D11,
   author    = {Jens Dittrich},
   title     = {{PaperBricks: An Alternative to Complete-Story Peer Reviewing}},
   journal   = {CoRR},
   volume    = {abs/1102.3523},
   year      = {2011},
   }

RAFT at Work: Speeding-Up MapReduce Applications under Task and Node Failures
The MapReduce framework is typically deployed on very large computing clusters where task and node failures are no longer an exception but the rule. Thus, fault-tolerance is an important aspect for the efficient operation of MapReduce jobs. However, currently MapReduce implementations fully recompute failed tasks (subparts of a job) from the beginning. This can significantly decrease the runtime performance of MapReduce applications. We present an alternative system that implements RAFT ideas. RAFT is a family of powerful and inexpensive Recovery Algorithms for Fast-Tracking MapReduce jobs under task and node failures. To recover from task failures, RAFT exploits the intermediate results persisted by MapReduce at several points in time. RAFT piggybacks checkpoints on the task progress computation. To recover from node failures, RAFT maintains a per-map task list of all input key-value pairs producing intermediate results and pushes intermediate results to reducers. In this demo, we demonstrate that RAFT recovers efficiently from both task and node failures. Further, the audience can compare RAFT with Hadoop via an easy-to-use web interface.

@inproceedings{QPS+11,
   author    = {Jorge-Arnulfo Quian{\'e}-Ruiz and Christoph Pinkel and J{\"o}rg Schad and Jens Dittrich},
   title     = {{RAFT at work: speeding-up mapreduce applications under task and node failures}},
   booktitle = {SIGMOD Conference},
   year      = {2011},
   pages     = {1225-1228},
   }

MOVIES: Indexing Moving Objects by Shooting Index Images
With the exponential growth of moving objects data to the Gigabyte range, it has become critical to develop effective techniques for indexing, updating, and querying these massive data sets. To meet the high update rate as well as low query response time requirements of moving object applications, this paper takes a novel approach in moving object indexing. In our approach, we do not require a sophisticated index structure that needs to be adjusted for each incoming update. Rather, we construct conceptually simple short-lived index images that we only keep for a very short period of time (sub-seconds) in main memory. As a consequence, the resulting technique MOVIES supports at the same time high query rates and high update rates, trading this property for query result staleness. Moreover, MOVIES is the first main memory method supporting time-parameterized predictive queries. To support this feature, we present two algorithms: non-predictive MOVIES and predictive MOVIES . We obtain the surprising result that a predictive indexing approach considered state-of-the-art in an external-memory scenario does not scale well in a main memory environment. In fact, our results show that MOVIES outperforms state- of-the-art moving object indexes such as a main-memory adapted B x -tree by orders of magnitude w.r.t. update rates and query rates. In our experimental evaluation, we index the complete road network of Germany consisting of 40,000,000 road segments and 38,000,000 nodes. We scale our workload up to 100,000,000 moving objects, 58,000,000 updates per second and 10,000 queries per second, a scenario at a scale unmatched by any previous work.

@article{DBS11,
   author    = {Jens Dittrich and Lukas Blunschi and Marcos Antonio Vaz Salles},
   title     = {{MOVIES: indexing moving objects by shooting index images}},
   journal   = {GeoInformatica},
   volume    = {15},
   number    = {4},
   year      = {2011},
   pages     = {727-767},
   }

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},
   }

RAFTing MapReduce: Fast Recovery on the Raft
MapReduce is a computing paradigm that has gained a lot of popularity as it allows non-expert users to easily run complex analytical tasks at very large-scale. At such scale, task and node failures are no longer an exception but rather a characteristic of large-scale systems. This makes fault-tolerance a critical issue for the efficient operation of any application. MapReduce automatically reschedules failed tasks to available nodes, which in turn recompute such tasks from scratch. However, this policy can significantly decrease performance of applications. In this paper, we propose a family of Recovery Algorithms for Fast-Tracking (RAFT) MapReduce. As ease-of-use is a major feature of MapReduce, RAFT focuses on simplicity and also non-intrusiveness, in order to be implementation-independent. To efficiently recover from task failures, RAFT exploits the fact that MapReduce produces and persists intermediate results at several points in time. RAFT piggy-backs checkpoints on the task progress computation. To deal with multiple node failures, we propose query metadata checkpointing. We keep track of the mapping between input key-value pairs and intermediate data for all reduce tasks. Thereby, RAFT does not need to re-execute completed map tasks entirely. Instead RAFT only recomputes intermediate data that were processed for local reduce tasks and hence not shipped to another node for processing. We also introduce a scheduling strategy taking full advantage of these recovery algorithms. We implemented RAFT on top of Hadoop and evaluated it on a 45-node cluster using three common analytical tasks. Overall, our experimental results demonstrate that RAFT outperforms Hadoop runtimes by 23% on average under task and node failures. The results also show that RAFT has negligible runtime overhead.

@inproceedings{QPS+11,
   author    = {Jorge-Arnulfo Quian{\'e}-Ruiz and Christoph Pinkel and J{\"o}rg Schad and Jens Dittrich},
   title     = {{RAFTing MapReduce: Fast recovery on the RAFT}},
   booktitle = {ICDE},
   year      = {2011},
   pages     = {589-600},
   }

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 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. In this paper we discuss building a new type of database system which fits 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 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. 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.

Flying Yellow Elephant: Predictable and Efficient MapReduce in the Cloud
Today, growing datasets require new technologies as standard technologies — such as parallel DBMSs — do not easily scale to such level. On the one side, there is the MapReduce paradigm allowing non-expert users to easily define large distributed jobs. On the other side, there is Cloud Computing providing a pay-as-you-go infrastructure for such computations. This PhD project aims at improving the combination of both technologies, especially for the following issues: (i) predictability of performance, (ii) runtime optimization and (iii) Cloud-aware scheduling. These issues can result in significant runtime overhead or non-optimal use of computing resources, which in a Cloud setting directly correlates to high monetary cost. We present preliminary results that confirm a significant improvement on performance when addressing some of these issues. Further, we discuss research challenges and initial ideas for above mentioned issues.

Hadoop++: Making a Yellow Elephant Run Like a Cheetah (Without It Even Noticing)
MapReduce is a computing paradigm that has gained a lot of attention in recent years from industry and research. Unlike parallel DBMSs, MapReduce allows non-expert users to run complex analytical tasks over very large data sets on very large clusters and clouds. However, this comes at a price: MapReduce processes tasks in a scan-oriented fashion. Hence, the performance of Hadoop — an open-source implementation of MapReduce — often does not match the one of a well-configured parallel DBMS. In this paper we propose a new type of system named Hadoop ++ : it boosts task performance without changing the Hadoop framework at all (Hadoop does not even ‘notice it’). To reach this goal, rather than changing a working system (Hadoop), we inject our technology at the right places through UDFs only and a ff ect Hadoop from inside . This has three important consequences: First, Hadoop ++ signifi- cantly outperforms Hadoop. Second, any future changes of Hadoop may directly be used with Hadoop ++ without rewriting any glue code. Third, Hadoop ++ does not need to change the Hadoop in- terface. Our experiments show the superiority of Hadoop ++ over both Hadoop and HadoopDB for tasks related to indexing and join processing.

@article{DQJ+10,
   author    = {Jens Dittrich and Jorge-Arnulfo Quian{\'e}-Ruiz and Alekh Jindal and Yagiz Kargin and Vinay Setty and J{\"o}rg Schad},
   title     = {{Hadoop++: Making a Yellow Elephant Run Like a Cheetah (Without It Even Noticing)}},
   journal   = {PVLDB},
   volume    = {3},
   number    = {1},
   year      = {2010},
   pages     = {518-529},
   }

Runtime Measurements in the Cloud: Observing, Analyzing, and Reducing Variance
One of the main reasons why cloud computing has gained so much popularity is due to its ease of use and its ability to scale computing resources on demand. As a result, users can now rent computing nodes on large commercial clusters through several vendors, such as Amazon and rackspace. However, despite the attention paid by Cloud providers, performance unpredictability is a major issue in Cloud computing for (1) database researchers performing wall clock experiments, and (2) database applications providing servicelevel agreements. In this paper, we carry out a study of the performance variance of the most widely used Cloud infrastructure (Amazon EC2) from different perspectives. We use established microbenchmarks to measure performance variance in CPU, I/O, and network. And, we use a multi-node MapReduce application to quantify the impact on real data- intensive applications. We collected data for an entire month and compare it with the results obtained on a local cluster. Our results show that EC2 performance varies a lot and often falls into two bands having a large performance gap in-between — which is somewhat surprising. We observe in our experiments that these two bands correspond to the different virtual system types provided by Amazon. Moreover, we analyze results considering different availability zones, points in time, and locations. This analysis indicates that, among others, the choice of availability zone also influences the performance variability. A major conclusion of our work is that the variance on EC2 is currently so high that wall clock experiments may only be performed with considerable care. To this end, we provide some hints to users.

@article{SDQ10,
   author    = {J{\"o}rg Schad and Jens Dittrich and Jorge-Arnulfo Quian{\'e}-Ruiz},
   title     = {{Runtime Measurements in the Cloud: Observing, Analyzing, and Reducing Variance}},
   journal   = {PVLDB},
   volume    = {3},
   number    = {1},
   year      = {2010},
   pages     = {460-471},
   }

Interesting-Phrase Mining for Ad-Hoc Text Analytics
Large text corpora with news, customer mail and reports, or Web 2.0 contributions offer a great potential for enhancing business-intelligence applications. We propose a framework for performing text ana- lytics on such data in a versatile, efficient, and scalable manner. While much of the prior literature has emphasized mining key- words or tags in blogs or social-tagging communities, we empha- size the analysis of interesting phrases. These include named en- tities, important quotations, market slogans, and other multi-word phrases that are prominent in a dynamically derived ad-hoc sub- set of the corpus, e.g., being frequent in the subset but relatively infrequent in the overall corpus. We develop preprocessing and in- dexing methods for phrases, paired with new search techniques for the top-k most interesting phrases in ad-hoc subsets of the corpus. Our framework is evaluated using a large-scale real-world corpus of New York Times news articles.

@article{BBD+10,
   author    = {Srikanta J. Bedathur and Klaus Berberich and Jens Dittrich and Nikos Mamoulis and Gerhard Weikum},
   title     ={{Interesting-Phrase Mining for Ad-Hoc Text Analytics}},
   journal   = {PVLDB},
   volume    = {3},
   number    = {1},
   year      = {2010},
   pages     = {1348-1357}
}

Intensional Associations in Dataspaces
Dataspace applications necessitate the creation of associations among data items over time. For example, once information about people is extracted from sources on the Web, associations among them may emerge as a consequence of different criteria, such as their city of origin or their elected hobbies. In this paper, we advocate a declarative approach to specifying these associations. We propose that each set of associations be defined by an association trail. An association trail is a query-based definition of how items are connected by intensional (i.e., virtual) association edges to other items in the dataspace. We study the problem of processing neighborhood queries over such intensional association graphs. The naive approach to neighborhood query processing over intensional graphs is to materialize the whole graph and then apply previous work on dataspace graph indexing to answer queries. We present in this paper a novel indexing technique, the grouping-compressed index (GCI), that has better worst-case indexing cost than the naive approach. In our experiments, GCI is shown to provide an order of magnitude gain in indexing cost over the naive approach, while remaining competitive in query processing time.

@inproceedings{SDB10,
   author    = {Marcos Antonio Vaz Salles and Jens Dittrich and Lukas Blunschi},
   title     = {{Intensional associations in dataspaces}},
   booktitle = {ICDE},
   year      = {2010},
   pages     = {984-987},
   }

iMeMex: From Search to Information Integration and Back
In this paper, we report on lessons learned while building iMeMex , the first incarnation of a Personal Dataspace Management System (PDSMS). In contrast to traditional keyword search engines, users may not only search their collections with iMeMex but also semantically integrate them over time. As a consequence, the system may improve on precision and recall of queries in a pay-as-you-go fashion. We discuss the impact of several conceptual and architectural decisions made in iMeMex and outline open research challenges in combining search and information integration in order to build personal dataspace management systems.

@article{DSB09,
   author    = {Jens Dittrich and Marcos Antonio Vaz Salles and Lukas Blunschi},
   title     = {{iMeMex: From Search to Information Integration and Back}},
   journal   = {IEEE Data Eng. Bull.},
   volume    = {32},
   number    = {2},
   year      = {2009},
   pages     = {28-35},
   }

Indexing Moving Objects using Short-Lived Throwaway Indexes
With the exponential growth of moving objects data to the Gigabyte range, it has become critical to develop effective techniques for indexing, updating, and querying these massive data sets. To meet the high update rate as well as low query response time requirements of moving object applications, this paper takes a novel approach in moving object indexing. In our approach we do not require a sophisticated index structure that needs to be adjusted for each incoming update. Rather we construct conceptually simple short-lived throwaway indexes which we only keep for a very short period of time (sub-seconds) in main memory. As a consequence, the resulting technique MOVIES supports at the same time high query rates and high update rates and trades this for query result staleness. Moreover, MOVIES is the first main memory method supporting time-parameterized predictive queries. To support this feature we present two algorithms: non-predictive MOVIES and predictive MOVIES. We obtain the surprising result that a predictive indexing approach — considered state-of-the-art in an external-memory scenario — does not scale well in a main memory environment. In fact our results show that MOVIES outperforms state-of-the-art moving object indexes like a main-memory adapted B x -tree by orders of magnitude w.r.t. update rates and query rates. Finally, our experimental evaluation uses a workload unmatched by any previous work. We index the complete road network of Germany consisting of 40,000,000 road segments and 38,000,000 nodes. We scale our workload up to 100,000,000 moving objects, 58,000,000 updates per second and 10,000 queries per second which is unmatched by any previous work.

@inproceedings{DBS09,
   author    = {Jens Dittrich and Lukas Blunschi and Marcos Antonio Vaz Salles},
   title     = {{Indexing Moving Objects Using Short-Lived Throwaway Indexes}},
   booktitle = {SSTD},
   year      = {2009},
   pages     = {189-207}
}

Dwarfs in the Rearview Mirror: How Big are they really?
Online-Analytical Processing (OLAP) has been a field of competing technologies for the past ten years. One of the still unsolved challenges of OLAP is how to provide quick response times on any Terabyte-sized business data problem. Recently, a very clever multi-dimensional index structure termed Dwarf [26] has been proposed offering excellent query response times as well as unmatched index compression rates. The proposed index seems to scale well for both large data sets as well as high dimensions. Motivated by these surprisingly excellent results, we take a look into the rearview mirror. We have re-implemented the Dwarf index from scratch and make three contributions. First, we successfully repeat several of the experiments of the original paper. Second, we substantially correct some of the experimental results reported by the inventors. Some of our results differ by orders of magnitude. To better understand these differences, we provide additional experiments that better explain the behavior of the Dwarf index. Third, we provide missing experiments comparing Dwarf to baseline query processing strategies. This should give practitioners a better guideline to understand for which cases Dwarf indexes could be useful in practice.

@article{DBS08,
   author    = {Jens Dittrich and Lukas Blunschi and Marcos Antonio Vaz Salles},
   title     = {{Dwarfs in the Rearview Mirror: How big are they really?}},
   journal   = {PVLDB},
   volume    = {1},
   number    = {2},
   year      = {2008},
   pages     = {1586-1597}
}

The Repeatability Experiment of SIGMOD 2008
SIGMOD 2008 was the first database conference that offered to test submitters’ programs against their data to verify the experiments published. This paper discusses the rationale for this effort, the community’s reaction, our experiences, and advice for future similar efforts.

@article{MAA+08,
   author    = {Ioana Manolescu and Loredana Afanasiev and Andrei Arion and Jens Dittrich and Stefan Manegold and Neoklis Polyzotis and Karl Schnaitter and Pierre Senellart and Spyros Zoupanos and Dennis Shasha},
   title     = {{The repeatability experiment of SIGMOD 2008}},
   journal   = {SIGMOD Record},
   volume    = {37},
   number    = {1},
   year      = {2008},
   pages     = {39-45},
   }

iTrails: Pay-as-you-go Information Integration in Dataspaces
Dataspace management has been recently identified as a new agenda for information management [17, 22] and information integration [23]. In sharp contrast to standard information integration architectures, a dataspace management system is a data-coexistence approach: it does not require any investments in semantic integration before querying services on the data are provided. Rather, a dataspace can be gradually enhanced over time by defining relationships among the data. Defining those integration semantics gradually is termed pay-as-you-go information integration [17], as time and effort (pay) are needed over time (go) to provide integration semantics. The benefits are better query results (gain). This paper is the first to explore pay-as-you-go information integration in dataspaces. We provide a technique for declarative pay-as-you-go information integration named iTrails. The core idea of our approach is to declaratively add lightweight ‘hints’ (trails) to a search engine thus allowing gradual enrichment of loosely integrated data sources. Our experiments confirm that iTrails can be efficiently implemented introducing only little overhead during query execution. At the same time iTrails strongly improves the quality of query results. Furthermore, we present rewriting and pruning techniques that allow us to scale iTrails to tens of thousands of trail definitions with minimal growth in the rewritten query size.

@inproceedings{SDK+07,
   author    = {Marcos Antonio Vaz Salles and Jens-Peter Dittrich and Shant Kirakos Karakashian and Olivier Ren{\'e} Girard and Lukas Blunschi},
   title     = {{iTrails: Pay-as-you-go Information Integration in Dataspaces}},
   booktitle = {VLDB},
   year      = {2007},
   pages     = {663-674},
   }

A Dataspace Odyssey: The iMeMex Personal Dataspace Management System (Demo Paper)
A Personal Dataspace includes all data pertaining to a user on all his local disks and on remote servers such as network drives, email and web servers. This data is represented by a heterogeneous mix of files, emails, bookmarks, music, pictures, calendar, personal information streams and so on. We demonstrate a new breed of system that is able to handle the entire Personal Dataspace of a user. Our system, named iMeMex (integrated memex), is a first implementation of a Personal DataSpace Management System (PDSMS). Visions for this type of systems have been proposed recently [13, 10, 12, 17]. We showcase how iMeMex allows dataspace navigation across data source/file boundaries, how iMeMex offers rich con- textual information on query results and how our system returns best-effort results.

@inproceedings{BDG+07,
   author    = {Lukas Blunschi and Jens-Peter Dittrich and Olivier Ren{\'e} Girard and Shant Kirakos Karakashian and Marcos Antonio Vaz Salles},
   title     = {{A Dataspace Odyssey: The iMeMex Personal Dataspace Management System (Demo)}},
   booktitle = {CIDR},
   year      = {2007},
   pages     = {114-119}
}

iDM: A Unified and Versatile Data Model for Personal Dataspace Management
Personal Information Management Systems require a powerful and versatile data model that is able to represent a highly heterogeneous mix of data such as relational data, XML, file content, folder hierarchies, emails and email attachments, data streams, RSS feeds and dynamically computed documents, e.g. ActiveXML [3]. Interestingly, until now no approach was proposed that is able to represent all of the above data in a single, powerful yet simple data model. This paper fills this gap. We present the iMeMex Data Model (iDM) for personal information management. iDM is able to represent unstructured, semi-structured and structured data inside a single model. Moreover, iDM is powerful enough to represent graph-structured data, intensional data as well as infinite data streams. Further, our model enables to represent the structural information available inside files. As a consequence, the artificial boundary be- tween inside and outside a file is removed to enable a new class of queries. As iDM allows the representation of the whole personal dataspace [20] of a user in a single model, it is the foundation of the iMeMex Personal Dataspace Management System (PDSMS) [16, 14, 47]. This paper also presents results of an evaluation of an initial iDM implementation in iMeMex that show that iDM can be efficiently supported in a real PDSMS.

@inproceedings{DS06,
   author    = {Jens-Peter Dittrich and Marcos Antonio Vaz Salles},
   title     = {{iDM: A Unified and Versatile Data Model for Personal Dataspace Management}},
   booktitle = {VLDB},
   year      = {2006},
   pages     = {367-378}
}

iMeMex: Escapes from the Personal Information Jungle. (Demo Paper)
Modern computer work stations provide thousands of applications that store data in >100.000 files on the file system of the underlying OS. To handle these files data processing logic is re-invented inside each application. This results in a jungle of data processing solutions and a jungle of data and file formats. For a user, it is extremely hard to manage information in this jungle. Most of all it is impossible to use data distributed among different files and formats for combined queries, e.g., join and union operations. To solve the problems arising from file based data management, we present a software system called iMeMex as a unified solution to personal information management and integration. iMeMex is designed to integrate seamlessly into existing operating systems like Windows, Linux and Mac OS X. Our system enables existing applications to gradually dispose file based storage. By using iMeMex modern operating systems are enabled to make use of sophisticated DBMS, IR and data integration technologies. The seamless integration of iMeMex into existing operating systems enables new applications that provide concepts of data storage and analysis unseen before.

@inproceedings{DSK+05,
   author    = {Jens-Peter Dittrich and Marcos Antonio Vaz Salles and Donald Kossmann and Lukas Blunschi},
   title     ={{iMeMex: Escapes from the Personal Information Jungle}},
   booktitle = {VLDB},
   year      = {2005},
}

Bridging the Gap between OLAP and SQL. (Industry Track)
In the last ten years, database vendors have invested heavily in order to extend their products with new features for decision support. Examples of functionality that has been added are top N [2], ranking [13, 7], spreadsheet computations [19], grouping sets [14], data cube [9], and moving sums [15] in order to name just a few. Unfortunately, many modern OLAP systems do not use that functionality or replicate a great deal of it in addition to other database-related functionality. In fact, the gap between the functionality provided by an OLAP system and the functionality used from the underlying database systems has widened in the past, rather than narrowed. The reasons for this trend are that SQL as a data definition and query language, the relational model, and the client/server architecture of the current generation of database products have fundamental shortcomings for OLAP. This paper lists these deficiencies and presents the BTell OLAP engine as an example on how to bridge these shortcomings. In addition, we discuss how to extend current DBMS to better support OLAP in the future.

@inproceedings{DKK05,
   author    = {Jens-Peter Dittrich and Donald Kossmann and Alexander Kreutz},
   title     = {{Bridging the Gap between OLAP and SQL}},
   booktitle = {VLDB},
   year      = {2005},
   pages     = {1031-1042},
}

AGILE: Adaptive Indexing for Context-Aware Information Filters
Information filtering has become a key technology for modern information systems. The goal of an information filter is to route messages to the right recipients (possibly none) according to declarative rules called profiles. In order to deal with high volumes of messages, several index structures have been proposed in the past. The challenge addressed in this paper is to carry out stateful information filtering in which profiles refer to values in a database or to previous messages. The difficulty is that database update streams need to be processed in addition to messages. This paper presents AGILE, a way to extend existing index structures so that the indexes adapt to the message/update workload and show good performance in all situations. Performance experiments show that AGILE is overall the clear winner as compared to the best existing approaches. In extreme situations in which it is not the winner, the overheads are small.

@inproceedings{DFK05,
   author    = {Jens-Peter Dittrich and Peter M. Fischer and Donald Kossmann},
   title     = {{AGILE: Adaptive Indexing for Context-Aware Information Filters}},
   booktitle = {SIGMOD Conference},
   year      = {2005},
   pages     = {215-226}
}

On Producing Join Results Early
Support for exploratory interaction with databases in applications such as data mining requires that the first few results of an operation be available as quickly as possible. We study the algorithmic side of what can and what cannot be achieved for processing join operations. We develop strategies that modify the strict two-phase processing of the sort-merge paradigm, intermingling join steps with selected merge phases of the sort. We propose an algorithm that produces early join results for a broad class of join problems, including many not addressed well by hash-based algorithms. Our algorithm has no significant increase in the number of I/O operations needed to complete the join compared to standard sort-merge algorithms.

@inproceedings{DST+03,
   author    = {Jens-Peter Dittrich and Bernhard Seeger and David Scot Taylor and Peter Widmayer},
   title     = {{On Producing Join Results early}},
   booktitle = {PODS},
   year      = {2003},
   pages     = {134-142}
}

Progressive Merge Join: A Generic and Non-Blocking Sort-Based Join Algorithm
Support for exploratory interaction with databases in applications such as data mining requires that the first few results of an operation be available as quickly as possible. We study the algorithmic side of what can and what cannot be achieved for processing join operations. We develop strategies that modify the strict two-phase processing of the sort-merge paradigm, intermingling join steps with selected merge phases of the sort. We propose an algorithm that produces early join results for a broad class of join problems, including many not addressed well by hash-based algorithms. Our algorithm has no significant increase in the number of I/O operations needed to complete the join compared to standard sort-merge algorithms.

@inproceedings{DST+02,
   author    = {Jens-Peter Dittrich and Bernhard Seeger and David Scot Taylor and Peter Widmayer},
   title     = {{Progressive Merge Join: A Generic and Non-blocking Sort-based Join Algorithm}},
   booktitle = {VLDB},
   year      = {2002},
   pages     = {299-310}
}

GESS: a Scalable Similarity-Join Algorithm for Mining Large Data Sets in High Dimensional Spaces
The similarity join is an important operation for mining high-dimensional feature spaces. Given two data sets, the similarity join computes all tuples (x, y) that are within a distance ε.One of the most efficient algorithms for processing similarity-joins is the Multidimensional-Spatial Join (MSJ) by Koudas and Sevcik. In our previous work --- pursued for the two-dimensional case --- we found however that MSJ has several performance shortcomings in terms of CPU and I/O cost as well as memory-requirements. Therefore, MSJ is not generally applicable to high-dimensional data.In this paper, we propose a new algorithm named Generic External Space Sweep (GESS). GESS introduces a modest rate of data replication to reduce the number of expensive distance computations. We present a new cost-model for replication, an I/O model, and an inexpensive method for duplicate removal. The principal component of our algorithm is a highly flexible replication engine.Our analytical model predicts a tremendous reduction of the number of expensive distance computations by several orders of magnitude in comparison to MSJ (factor 107). In addition, the memory requirements of GESS are shown to be lower by several orders of magnitude. Furthermore, the I/O cost of our algorithm is by factor 2 better (independent from the fact whether replication occurs or not). Our analytical results are confirmed by a large series of simulations and experiments with synthetic and real high-dimensional data sets.

@inproceedings{DS01,
   author    = {Jens-Peter Dittrich and Bernhard Seeger},
   title     = {{GESS: A Scalable Similarity-join Algorithm for Mining Large Data Sets in High Dimensional Spaces}},
   booktitle = {KDD},
   year      = {2001},
   pages     = {47-56}
}

XXL - A Library Approach to Supporting Efficient Implementations of Advanced Database Queries
The similarity join is an important operation for mining high-dimensional feature spaces. Given two data sets, the similarity join computes all tuples (x, y) that are within a distance ε.One of the most efficient algorithms for processing similarity-joins is the Multidimensional-Spatial Join (MSJ) by Koudas and Sevcik. In our previous work --- pursued for the two-dimensional case --- we found however that MSJ has several performance shortcomings in terms of CPU and I/O cost as well as memory-requirements. Therefore, MSJ is not generally applicable to high-dimensional data.In this paper, we propose a new algorithm named Generic External Space Sweep (GESS). GESS introduces a modest rate of data replication to reduce the number of expensive distance computations. We present a new cost-model for replication, an I/O model, and an inexpensive method for duplicate removal. The principal component of our algorithm is a highly flexible replication engine.Our analytical model predicts a tremendous reduction of the number of expensive distance computations by several orders of magnitude in comparison to MSJ (factor 107). In addition, the memory requirements of GESS are shown to be lower by several orders of magnitude. Furthermore, the I/O cost of our algorithm is by factor 2 better (independent from the fact whether replication occurs or not). Our analytical results are confirmed by a large series of simulations and experiments with synthetic and real high-dimensional data sets.

@inproceedings{BBD+01,
   author    = {Jochen Van den Bercken and Bj{\"o}rn Blohsfeld and Jens-Peter Dittrich and J{\"u}rgen Kr{\"a}mer and Tobias Sch{\"a}fer and Martin Schneider and Bernhard Seeger},
   title     = {{XXL - A Library Approach to Supporting Efficient Implementations of Advanced Database Queries}},
   booktitle = {VLDB},
   year      = {2001}
}

javax.XXL: A Prototype for a Library of Query Processing Algorithms. (Demo paper)
Therefore, index structures can easily be used in queries. A typical example is a join cursor which consumes the outputs of two underlying cursors. Most of our work is however not dedicated to the area of relational databases, but mainly refers to spatial and temporal data. For spatial databases, for example, we provide several implementations of spatial join algorithms [3]. The cursor-based processing is however the major advantage of XXL in contrast to approaches like LEDA [6] and TPIE [7]. For more information on XXL see http://www.mathematik.uni-marburg.de/DBS/xxl.We will demonstrate the latest version of XXL using examples to show its core functionality. We will concentrate on three key aspects of XXL.Usage: We show how easily state-of-the-art spatial join-algorithms can be implemented in XXL using data from different sources. Reuse: We will demonstrate how to support different joins, e.g. spatial and temporal joins, using the same generic algorithm like Plug&Join [1].Comparability: We will demonstrate how XXL serves as an ideal testbed to compare query processing algorithms and index structures.

@inproceedings{BDS00,
   author    = {Jochen Van den Bercken and Jens-Peter Dittrich and Bernhard Seeger},
   title     ={{javax.XXL: A prototype for a Library of Query processing Algorithms}},
   booktitle = {SIGMOD Conference},
   year      = {2000},
   pages     = {588}
}

Data Redundancy and Duplicate Detection in Spatial Join Processing
The Partitioned Based Spatial-Merge Join (PBSM) of Patel and DeWitt and the Size Separation Spatial Join (S3J) of Koudas and Sevcik are considered to be among the most efficient methods for processing spatial (intersection) joins on two or more spatial relations. Both methods do not assume the presence of pre-existing spatial indices on the relations. In this paper, we propose several improvements of these join algorithms. In particular, we deal with the impact of data redundancy and duplicate detection on the performance of theses methods. For PBSM, we present a simple and inexpensive on-line method to detect duplicates in the response set. There is no need any- more for eliminating duplicates in a final sorting phase as it has been suggested originally. We also investigate in this paper the impact of different internal algorithms on the total runtime of PBSM. For S3J, we break with the original design goal and introduce controlled redundancy of data objects. Results of a large set of experiments with real datasets reveal that our suggested modifications of PBSM and S3J result in substantial performance improvements where PBSM is generally superior to S3J.

@inproceedings{DS00,
   author    = {Jens-Peter Dittrich and Bernhard Seeger},
   title     = {{Data Redundancy and Duplicate Detection in Spatial Join Processing}},
   booktitle = {ICDE},
   year      = {2000},
   pages     = {535-546}
}