Self-organizing tuple reconstruction in column-stores

Column-stores gained popularity as a promising physical \ndesign alternative. Each attribute of a relation is physically stored as a separate column \nallowing queries to \nload only the required attributes. \nThe overhead incurred is \non-the-fly tuple reconstruction for multi-attribute queries. \nEach tuple reconstruction \nis a join of two columns based on tuple IDs, making it a \nsignificant cost component. \nThe ultimate physical design is to have multiple presorted copies of each base table \nsuch that tuples are already appropriately organized in multiple different orders across the various columns. This requires \nthe ability to predict the workload, idle time to prepare, and infrequent updates. \n \nIn this paper, we propose a novel design, \\emph{partial sideways cracking}, \nthat \nminimizes the tuple reconstruction cost in a self-organizing way. \nIt achieves performance similar to using presorted data, \nbut without requiring the heavy initial presorting step itself. \nInstead, it handles \ndynamic, unpredictable workloads with no idle time and frequent updates. \nAuxiliary dynamic data structures, called \\emph{cracker maps}, \nprovide a direct mapping between pairs of attributes used together in queries for tuple reconstruction. \nA map is continuously physically reorganized as an integral part of query evaluation, \nproviding faster and reduced data access for future queries. \nTo enable flexible and self-organizing behavior in storage-limited environments, \nmaps are materialized only partially \nas demanded by the workload. Each map is a collection of \nseparate chunks that are individually reorganized, dropped or recreated as needed. \nWe implemented partial sideways cracking in an open-source column-store. \nA detailed experimental analysis \ndemonstrates that it brings significant performance benefits \nfor multi-attribute queries. \