External sorting

External sorting describes sorting algorithms that are designed for very large amounts of data. Algorithms that work on large amounts of data that do not fit into main memory are commonly referred to as external memory algorithms . In the analysis of classic sorting algorithms (e.g. Quicksort ), storage hierarchies or access to data on data carriers of different speeds are usually not taken into account. However, the structure and hierarchy of the memory as well as how the algorithms handle it is decisive for the performance when sorting large amounts of data.

Parallel disk model

A common model for considering external memory algorithms is the Parallel Disk Model (PDM). This has a main memory of the size and one or more external memories of unlimited size, the so-called disks. The size data to be sorted can be found on these . For the sake of simplicity, the number of disks is often assumed and the simplified model is referred to as the External Memory Model (EMM). Aggarwal and Vitter also originally presented the model with a single disk, but several parallel read / write heads. The main memory as well as the external memory have a block size . With an IO operation, one block per disk can be loaded into the main memory or written back to the external memory. For a better overview, the input size and the size of the main memory are also given in blocks. In contrast to the analysis of classic sorting algorithms , the performance of an algorithm is not measured by the number of all operations, but only given by the number of IO operations. ${\displaystyle M}$ ${\displaystyle N}$ ${\displaystyle D=1}$ ${\displaystyle B}$ ${\displaystyle n=N/B}$ ${\displaystyle m=M/B}$

Lower bound

A general limit for the number of IO operations can be specified for sorting in the PDM. In the case of a single or multiple disks ( ), this is given by: ${\displaystyle D\geq 1}$

${\displaystyle \Theta ({\frac {N}{DB}}\log _{M/B}{\frac {N}{B}})=\Theta ({\frac {n}{D}}\log _{m}n)}$

In practice, is a small constant. In the atypical case , this limit only applies to comparison-based procedures . ${\displaystyle \log _{m}n}$ ${\displaystyle B\log m=o(\log n)}$

Algorithms

Merge Sort

The classic merge sort ajar, the External Memory merge sort . First of all the algorithm for shall be considered. Data segments consisting of blocks are loaded into the main memory one after the other , sorted there and written back to the external memory as a so-called run. The runs in the external memory are then combined on recursion levels by means of a K-Way merge. ${\displaystyle D=1}$ ${\displaystyle m}$ ${\displaystyle N/M}$ ${\displaystyle \log _{m}n}$

Simplified representation of the merge sort . First the individual runs are sorted in the main memory, then the runs are merged.

 for j=1 to n/M
     Lade nächstes Datensegment der Größe  ${\displaystyle M}$ in Hauptspeicher
     Sortiere Daten im Hauptspeicher
     Schreibe sortierte Daten als run  ${\displaystyle r_{1,j}}$ auf externen Speicher
 end

 for i=1 to  ${\displaystyle \lceil \log _{m}n\rceil }$
     for j=1 to  ${\displaystyle \lceil |r_{i}|/(m)\rceil }$
         Lade die jeweils ersten Blöcke der runs  ${\displaystyle r_{i,(j-1)(m)+1}...r_{i,j(m)}}$ in Merge-Buffer
         while Merge-Buffer nicht leer
             Merge runs  ${\displaystyle r_{i,(j-1)(m)+1}...r_{i,j(m)}}$
             Schreibe Output-Buffer in externen Speicher falls voll
             Lade nächsten Block in Hauptspeicher falls ein Merge-Buffer bereits komplett gemerged
         end
     end
 end

In order to use several parallel disks as efficiently as possible and to comply with the limit described above, blocks must be moved as far as possible in each IO step . In order to efficiently write the blocks back to the disks, the size of the internal buffer in the main memory, which contains the merged elements, is therefore expanded to include blocks. A prefetching buffer is also added to ensure a higher throughput when reading . If the elements in the previous steps were cleverly distributed on the individual disks and a suitable prefetching strategy was selected, a buffer size of blocks is sufficient . ${\displaystyle D}$ ${\displaystyle D}$ ${\displaystyle \Theta (D)}$

Distribution Sort

Similar to the merge sort , the distribution sort is also a recursive algorithm. The data should be divided into buckets according to partitioning elements. The rule here is that all elements within a bucket are smaller than each element in the following. This partitioning is then repeated recursively for the individual buckets. If the buckets are small enough to be able to be loaded completely into the main memory, they are sorted there. The concatenation of the sorted buckets thus forms the sorted order of the entire data. ${\displaystyle S-1}$ ${\displaystyle S}$

The choice of partitioning elements is crucial in order to obtain buckets of the same size as possible and thus to ensure good performance. This can be done in a probabilistic way, for example. A small, random amount of elements is sorted and the partitioning elements are selected from this. The size of the set is chosen so that the sorting of these is negligible for the number of IO operations and has no influence on the limit. With good partitioning, the recursion depth is . As for each bucket, a buffer is needed in the main memory, can by be estimated upwards. ${\displaystyle O(\log _{S}n)}$ ${\displaystyle S}$ ${\displaystyle \Theta (m)}$

In order to meet the limit given above, only IO operations may therefore be carried out on each recursion level. In order to load a bucket efficiently into main memory, its blocks must first have been evenly distributed over the various disks. The blocks belonging to the various buckets are either written together as a stripe from the output buffer in the main memory to the external memory or a stripe is created for each bucket. In the case of a stripe per bucket, randomized cycling can be used to ensure that the next blocks of the various buckets have to be written to as different disks as possible. This variant is also called Randomized Cycling Distribution Sort . ${\displaystyle \Theta (n/D)}$

Applications

Basically, sorting operations take up a large part of the computational effort. In the last few years the amount of data that is used for calculations has increased steadily. External memory algorithms are required to cope with this volume of data . Efficient external sorting is of particular importance, since many external memory algorithms are based on sorting processes .

credentials

1. ↑ ^{a b c d e} Jeffrey Scott Vitter: Algorithms and data structures for external memory . In: Foundations and Trends in Theoretical Computer Science . 2, No. 4, 2008, pp. 30-474.
2. ↑ Alok Aggarwal, Jeffrey Scott Vitter: The input / output complexity of sorting and related problems . In: Communications of the ACM . 31, No. 9, 1988, pp. 1116-1127.
3. ^ ^{A b c} Donald Knuth: The Art of Programming, Vol. 3 (Sorting and Searching) . Addison-Wesley, 1973.