Time travel in column stores

Recent studies have shown that column stores can outperform row stores significantly. This paper explores alternative approaches to extend column stores with versioning, i.e., time travel queries and the maintenance of historic data. On the one hand, adding versioning can actually simplify the design of a column store because it provides a solution for the implementation of updates, traditionally a weak point in the design of column stores. On the other hand, implementing a versioned column store is challenging because it imposes a two dimensional clustering problem: should the data be clustered by row or by version? This paper devises the details of three memory layouts: clustering by row, clustering by version, and hybrid clustering. Performance experiments demonstrate that all three approaches outperform a (traditional) versioned row store. The efficiency of these three memory layouts depends on the query and update workload. Furthermore, the performance experiments analyze the time-space tradeoff that can be made in the implementation of versioned column stores.