  Physical data layout is an important performance factor for modern databases.
Clustering, i.e., storing similar values in proximity, can lead to performance
gains in several ways. We present an automated model to determine beneficial
clustering columns and a clustering algorithm for the column-oriented,
memory-resident database Hyrise. To automatically select clustering columns,
the model analyzes the database's workload and provides estimates by how much
certain clustering columns would impact the workload's latency. We evaluate the
precision of the model's estimates, as well as the overall quality of its
clustering suggestions. To apply a determined clustering configuration, we
developed an online clustering algorithm. The clustering algorithm supports an
arbitrary number of clustering dimensions. We show that the algorithm is robust
against concurrently running data modifying queries. We obtain a 5% latency
reduction for the TPC-H benchmark when clustering the lineitem table and a 4%
latency reduction for the TPC-DS benchmark when clustering the store_sales
table.

Databases