301. Algorithms for Sorting and Sort-Based Database Operations Using a Special-Function Unit
- Author
-
Chiang Lee, Stanley Y. W. Su, and Herman Lam
- Subjects
Sorting algorithm ,Database ,Computer science ,Radix sort ,Process (computing) ,Sorting ,Parallel computing ,computer.software_genre ,Set (abstract data type) ,Computer for operations with functions ,sort ,computer ,Algorithm ,Database machine - Abstract
This paper presents the design of a Special Function Unit for DataBase operations (SFU-DB), which is used as a backend database machine for performing sort and sort-based database operations. This machine implements a most-significant-digit-first radix sort algorithm by using a special hardware device called Automatic Retrieval Memory (ARM). The ARM performs an efficient content-to-address mapping to sort the data. Without performing any comparisons in the sorting process, the SFU-DB avoids the lower bound constraint on comparison-based sorting algorithms and achieves a complexity of O(n) for both execution time and main memory size. Based on the sorting algorithm, the SFU-DB also performs other primitive database operations such as relational join, elimination of duplicates, set union, set intersection, and set difference with a complexity of O(n). The capacity of the SFU-DB is limited by the size of its main memory rather than by the number of special processing elements as in most sorting machines. Hence, the SFU-DB has a better cost/performance and is more suitable for processing very large databases. Currently, a prototype SFU-DB system is under construction.
- Published
- 1988