Zeitschriftenartikel
Sorting in Column Stores
Vorschaubild nicht verfügbar
Volltext URI
Dokumententyp
Text/Journal Article
Zusatzinformation
Datum
2011
Autor:innen
Zeitschriftentitel
ISSN der Zeitschrift
Bandtitel
Verlag
Springer
Zusammenfassung
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.