Joint Index, Sorting, and Compression Optimization for Memory-Efficient Spatio-Temporal Data Management

The wide distribution of location-acquisition technologies has led to large volumes of spatio-temporal data, which are the foundation for a broad spectrum of applications. Based on these applications’ performance requirements, in-memory databases are used to store and process the data. As DRAM capacities are limited and expensive, modern database systems apply various configuration optimizations (e.g., compression) to reduce the memory footprint. The selection of cost and performance balancing configurations is challenging due to the vast amount of possible setups consisting of mutually dependent individual decisions. In this paper, we present a linear programming approach to determine fine-grained configuration decisions for spatio-temporal workloads. By dividing the data into partitions of fixed size, we can apply the compression, sorting, and index selections on a fine-grained level to reflect spatiotemporal access patterns. Our approach jointly optimizes these configurations to maximize performance under a given memory budget. We demonstrate on a real-world dataset that models specifically optimized for spatio-temporal data characteristics allow us to reduce the memory footprint (up to 60% by equal performance) and increase the performance (up to 80% by equal memory size) compared to established rule-based heuristics.

I. Introduction

Spatio-temporal data reflects the trajectories of moving objects and enables the analysis of movement patterns, which are increasingly used in various applications. A moving object’s trajectory is represented by a chronologically ordered sequence of timestamped geographical coordinates accumulated by various positioning systems (e.g., GPS). To store and process spatio-temporal data is not a trivial task due to the massive volumes of continuously captured data and the need for interactive response times. The increased performance requirements of spatio-temporal data mining applications have shifted the data management to in-memory architectures [1]. Especially for main-memory optimized databases that keep the most data in relatively limited and expensive DRAM, a more efficient utilization of the available resources can significantly affect the operating costs [2]. While removing auxiliary data structures (e.g., indexes) or applying compression techniques with higher compression rates reduce the memory footprint, they equally affect the runtime performance. Modern database systems support fine-grained decisions for these configurations [3]– [7]. This approach enables applying different optimizations such as compression, indexing, and ordering configurations for various partitions of the data independently. All single configuration decisions have an impact on the overall memory consumption and runtime performance. Additionally, they mutually influence each other, which makes the determination of performance-optimized and memory-efficient configurations difficult [8], [9]. There are several general approaches in existing work that optimize specific aspects like the compression schema selection [2] or the selection of optimized index structures [10], [11]. As the different configuration decisions mutually influence each other, we seek to jointly optimize the compression, index, and ordering configuration to determine the best runtime performance for a given workload, data characteristics, and memory budget. Note, each of those individual tuning problems is, in general, already challenging. We are still able to address a joint optimization of these dimensions, as we exploit the specific characteristics of spatio-temporal data and applications, i.e., a limited number of columns and few query types. Further, to obtain a manageable problem complexity, we focus on single-attribute indexes.