A performance model for preplanned disk sorting

The idea of preplanning strings on disks which are merged together is investigated from a performance point of view. Schemes of internal buffer allocation, initial string creation by an internal sort, and string distribution on disks are evaluated. An algorithm is given for the construction of suboptimal merge trees called plannable merge trees.

A cost model is presented for accurate preplanning which consists of detailed assumptions on disk allocation fork input disks andr-way merge planning. Timing considerations for sort and merge including hardware characteristics of moveable head disks show a significant gain of time compared to widely used sort/merge applications.

Der Ansatz, Strings, die zusammengemischt werden, auf Magnetplatten vorzuplanen, wird unter Leistungsgesichtspunkten untersucht. Konzepte für die interne Pufferzuordnung, für die Erzeugung der anfänglichen Strings durch ein internes Sortierverfahren, und für die Stringverteilung auf Magnetplatten werden ausgewertet. Ein Algorithmus beschreibt die Konstruktion von suboptimalen Mischbäumen, die planbare Mischbäume genannt werden.

Ein Kostenmodell, das auf detaillierte Annahmen der Zuordnung vonk Eingabeplatten und der Planung einesr-Wege-Mischens beruht, wird für das exakte Vorplanen aufgestellt. Zeitbetrachtungen für Sortieren und Mischen, die Hardware-Eigenschaften von Magnetplatten einschließen, zeigen signifikante Zeitgewinne verglichen mit weitverbreiteten Sortier- und Mischverfahren.

Authors and Affiliations

1. Institut für Informatik, Technische Universität München, Arcisstraße 21, D-8000, München 21, Federal Republic of Germany

   R. Bayer

2. Fachbereich Informatik, Technische Hochschule Darmstadt, Hochschulstraße 1, D-6100, Darmstadt, Federal Republic of Germany

   T. Härder

Reprints and permissions