by Varun Jain, James Lennon, and Harshita Gupta

LSM-Trees and B-Trees are the two primary data structures used as storage engines in modern key-value (KV) stores. These two structures are optimal for different workloads; LSM-Trees perform better on update queries, whereas B-Trees are preferable for short range lookups. KV stores today use one or the other. However, for modern applications with increasingly diverse workloads, limiting KV stores to utilize only one of the two designs leads to a significant loss in performance. We propose a novel method of online transitioning a KV store from an LSM-Tree to a B-Tree and vice versa. This allows KV stores to smoothly adapt to changing workloads and use the optimal data structure as the workload changes.

by Meena Jagadeesan and Garrett Tanzer

Selecting the optimal storage engine and tuning for an application requires comparing the latency of diverse workloads executed on different data structures. In this work, we start to develop an average-case analysis of the performance of storage engines that can achieve significantly more accurate predictions than existing worst-case models. We propose a distribution-aware framework to predict the latency of diverse workloads executed on a vast number of data structures. As a case study, we use our framework to produce cost models for a diverse family of key-value storage engine tunings, and verify our models on RocksDB and WiredTiger.

by Demi Guo

We present practical learning-based search algorithms that make it possible to automatically design key-value data structures. Our work allows searching within a space of 10100 possible designs for the optimal data structure. The input is a workload specification and the output is an abstract syntax tree which can be absorbed by modern code-generation techniques. Given the vast design space our solution is based on learning and we show that it can find the close to optimal data structure design in a matter of a few seconds.

by Neil Band

As the number of layers and the amount of training data increases, the trend is to train deep neural networks in parallel across devices. In such scenarios, neural network training is increasingly bottlenecked by high memory requirements posed by intermediate results, or feature maps, that are produced during the forward pass and consumed during the backward pass. We recognize that the best-performing device parallelization configurations should consider memory usage in addition to the canonical metric of computation time. Towards this we introduce MemFlow, an optimization framework for distributed deep learning that performs joint optimization over memory usage and computation time when searching for a parallelization strategy. MemFlow consists of: (i) a task graph with memory usage estimates; (ii) a memory-aware execution simulator; and (iii) a Markov Chain Monte Carlo search algorithm that considers various degrees of recomputation i.e., discarding feature maps during the forward pass and recomputing them during the backward pass. Our experiments demonstrate that under memory constraints, MemFlow can readily locate valid and superior parallelization strategies unattainable with previous frameworks.

by Varun Jain, James Lennon, and Harshita Gupta

LSM-Trees and B-Trees are the two primary data structures used as storage engines in modern key-value (KV) stores. These two structures are optimal for different workloads; LSM-Trees perform better on update queries, whereas B-Trees are preferable for short range lookups. KV stores today use one or the other. However, for modern applications with increasingly diverse workloads, limiting KV stores to utilize only one of the two designs leads to a significant loss in performance. We propose a novel method of online transitioning a KV store from an LSM-Tree to a B-Tree and vice versa. This allows KV stores to smoothly adapt to changing workloads and use the optimal data structure as the workload changes.

by Thomas Lively, Luca Schroeder, and Carlos Mendizábal

Modern persistent key-value stores typically use a log-structured merge-tree (LSM-tree) design, which allows for high write throughput. Our observation is that the LSM-tree, however, has suboptimal performance during read-intensive workload windows with non-uniform key access distributions. To address this shortcoming, we propose and analyze a simple decision scheme that can be added to any LSM-based key-value store and dramatically reduce the number of disk I/Os for these classes of workloads. The key insight is that copying a frequently accessed key to the top of an LSM-tree ("splaying") allows cheaper reads on that key in the near future.

by Graham Lustiber

We introduce E-tree, a new variant of the family of B-tree indexes, designed for evolving workloads. E-tree reshapes itself to maintain optimal memory layout as the access patterns change, achieved by dropping the requirement of having a fixed, global index design. Instead, E-tree uses different memory layout patterns for different regions of the tree and continuously reconsiders those design decisions as the workload evolves. We describe E-tree, explore heuristics to determine the reshaping patterns, and demonstrate experimentally that it has strong potential by outperforming state-of-the-art fixed designs in evolving workloads.

by Alex Liu

Joins have traditionally been the most expensive database operator, but they are required to query normalized schemas. In turn, normalized schemas are necessary to minimize update costs and space usage. Joins can be avoided altogether by using a denormalized schema instead of a normalized schema; this improves analytical query processing times at the tradeoff of increased update overhead, loading cost, and storage requirements.

In our work, we show that we can achieve the best of both worlds by leveraging partial, incremental, and dynamic denormalized tables to avoid join operators, resulting in fast query performance while retaining the minimized loading, update, and storage costs of a normalized schema. We introduce adaptive denormalization for modern main memory systems. We replace the traditional join operations with efficient scans over the relevant partial universal tables without incur- ring the prohibitive costs of full denormalization.

by Stella Pantela

Just-In-Time (JIT) compilation increasingly becomes a key technology for modern database systems. It allows the creation of code on-the-fly to perfectly match an active query. In the past, it has been argued that a query should be compiled to a single loop that performs all query actions, for example, all selects over all relevant columns. On the other hand, vectorization – a common feature in modern data systems – allows for better results by evaluating the query predicates sequentially in different tight for-loops.

In this paper, we study JIT compilation for modern in- memory column-stores in detail and we show that, contrary to the common belief that vectorization outweighs the benefits of having one loop, there are cases in which creating a single loop is actually the optimal solution. In fact, deciding between multiple or a single loop is not a static decision; instead, it depends on (per column) query selectivity. We perform our experiments on a modern column-store prototype that supports vectorization and we show that, depending on selectivity, a different code layout is optimal. When a select operator is implemented with a no-branch design, for low selectivity creating multiple loops performs better than a single loop. A single tight loop performs better otherwise.

by Wilson Qin

As modern main-memory optimized data systems increasingly rely on fast scans, lightweight indexes that allow for data skipping play a crucial role in data filtering to reduce system I/O. Scans benefit from data skipping when the data order is sorted, semi-sorted, or comprised of clustered values. However data skipping loses effectiveness over arbitrary data distributions. Applying data skipping techniques over non-sorted data can significantly decrease query performance since the extra cost of metadata reads result in no corresponding scan performance gains. We introduce adaptive data skipping as a framework for structures and techniques that respond to a vast array of data distributions and query workloads. We reveal an adaptive zonemaps design and implementation on a main-memory column store prototype to demonstrate that adaptive data skipping has potential for 1.4X speedup.

by Oreoluwa Babarinsa

As main-memory sizes have grown, data systems have been able to process entire large-scale data-sets in memory. However, because memory speeds have been not been keeping pace with CPU speeds, the cost of moving data into CPU caches has begun to dominate certain operations within in-memory data systems. Recent advances in hardware architectures point to near memory computation capabilities becoming possible soon. This allows us to rethink how database systems process queries and how they split computation across the various computational units. In this paper, we present JAFAR, a near data processing accelerator for pushing selects down to memory. Through a detailed simulation of JAFAR hardware we show it has the potential to provide up to 900% improvement for select operations in modern column-stores.

by Joshua Pan

Log-Structured Merge-Tree (LSM-tree) based storage engines power numerous applications from social media to machine learning, networks, and Blockchain. Today, storage engine performance deteriorates as data increases especially for skewed workloads due in a large part to inefficient filters. LSM-tree based storage engines rely on the effectiveness of filters to prune unneeded disk accesses. We present an adaptive filter that remembers frequent false positives to turn them into true negatives for future queries. The filter is tailored for integration in state-of-the-art storage engines, and we compare it against traditional workload agnostic filters. We show that our adaptive filter can provide up to 2× end-to-end throughput improvement.