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 algo-rithms 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 al-gorithms are in comparison to each other. In fact, it is not even clear how to experimentally compare different vertical partitioning algo-rithms. In this paper, we present an exhaustive experimental study of several vertical partitioning algorithms. We categorize vertical partitioning algorithms along three dimensions. We survey six ver-tical 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 compari-son of different vertical partitioning algorithms under the same set-ting. We propose four metrics to compare vertical partitioning al-gorithms. We show experimental results from the TPC-H and SSB benchmark and present four key lessons learned: (1) we can do four orders of magnitude less computation and still find the optimal lay-outs, (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%