An adaptive projection strategy and its implementation in column stores

Tuple reconstruction is an important component in column-stores. Some well-known column-stores, such as C-Store, employ projection to support tuple reconstruction. This paper proposes an adaptive projection strategy and an implementation method for projection. The proposed strategy employs association analysis to a considerable amount of query accesses submitted by users to group attributes of a relation into various projections. The strategy makes selections of projections adaptive to usage behaviors of users. This paper implements projections using main indexes and jointing address mapping indexes. The main index stores all columns of a projection, therefore, the proposed storage pattern is a compromise pattern rather than pure column store. But, with the proposed storage structure, the system not only avoids reading unnecessary attribute columns to answer query, but also does tuple reconstruction. The address mapping index is used to locate fast tuples. Finally, the experimental results on benchmark data set SSB show that the proposed strategy and implementation method can improve significantly the performance of multicolumn queries.