Sorting in Column Stores

Abstract

In recent years, we have seen a number of new database architectures based on the idea of vertical fragmentation of relations. These architectures target the analysis of huge amounts of relational data, because vertical fragmentation facilitates column scans which are common in analytic applications at the expense of single-tuple operations. Although sorting is a common operation for analytics, few is known about sorting vertically fragmented relations. This paper compares various possibilities to apply (external) merge sort to vertically fragmented relations on different layers of the memory hierarchy and gives hints on when to apply which one. We propose a Greedy algorithm to find the optimum mixture of steps that leads to a sorted version of a given relation which is stored column-wise.