A Multiway Merge Sorter for Sorting of Large Databases

概要

論文の詳細を見る
A multiway merge algorithm by using specialized hardware is proposed for sorting a large number of records. By adopting a sorting array that compares k records in parallel and a data-driven control technique that selects k strings for merging, the algorithm performs merge processing for a large number of k-way whose speed is in-dependent of the merge ways. A large number of records can be sorted by iteration of the k-way merge operations. The number of iterations is substantially reduced by increasing the number of merge ways. A compact hardware sorter can be achieved to satisfy both speed and capacity respectively since the sorting array and the working storage can be implemented independently. The database processor RINDA applies the multiway merge sorter for accelerating sorts and joins. The configuration and performance of the sorter are also discussed.
一般社団法人情報処理学会の論文
1992-11-30