Spirit-III: an advanced relational database machine introducing a novel data-staging architecture with Tuple Stream Filters to preprocess relational algebra

ABSTRACT

This paper proposes an advanced architecture of the relational database machine (RDBM), named SPIRIT-III, which is basically organized into a three-level memory hierarchy with a sophisticated data-staging and preprocessing architecture for executing relational algebra. SPIRIT-III aims at totally improving both I/O and CPU processing boundary problems and has two major architectural features. One is the introduction of the relational-database-oriented data-staging mechanism, called the look-ahead data-staging mechanism, which can optimally schedule data movement in the memory hierarchy. The other is to attach refined preprocessing mechanisms for relational algebra operations to data transfer lines connected between each memory stage. When a relation stages up or down in the memory hierarchy, these preprocessing mechanisms can function to select tuples and attributes needed by a query and to arrange the relation for parallel processing. SPIRIT-III provides three basic preprocessing filters, called as a whole the Tuple Stream Filter: the tuple selector, the attribute selector, and the grouping filter, implemented with a hash function, which rearranges an original relation and groups the relation into subrelations. The operation of this grouping filter is the primitive preprocessing operation for executing Join and Projection. Then, without the overhead of interprocessor communications, each microprocessor can execute relational algebra operations to a few subsegments assigned to it in parallel. Therefore, SPIRIT-III can perform Join and Projection operations by O (N/L) (L = number of microprocessors), whereas the early RDBMs required O (N X N/L). The proposed SPIRIT-III, which includes features from data-staging architecture to relational algebra execution architecture under the total concept, is the most powerful RDBM based on the state of the art.

REFERENCES

• 1: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• 2: John Miles Smith , Philip Yen-Tang Chang, Optimizing the performance of a relational algebra database interface, Communications of the ACM, v.18 n.10, p.568-579, Oct. 1975 [doi>10.1145/361020.361025]
• 3: E. A. Ozkarahan , S. A. Schuster , K. C. Smith, RAP: an associative processor for data base management, Proceedings of the May 19-22, 1975, national computer conference and exposition, May 19-22, 1975, Anaheim, California [doi>10.1145/1499949.1500024]
• 4: S. A. Schuster , H. B. Nguyen , E. A. Ozkarahan , K. C. Smith, RAP.2 An Associative Processor for Databases and Its Applications, IEEE Transactions on Computers, v.28 n.6, p.446-458, June 1979 [doi>10.1109/TC.1979.1675383]
• 5: D. J. De Witt, Direct A Multiprocessor Organization for Supporting Relational Database Management Systems, IEEE Transactions on Computers, v.28 n.6, p.395-406, June 1979 [doi>10.1109/TC.1979.1675379]
• 6: E. Babb, Implementing a relational database by means of specialzed hardware, ACM Transactions on Database Systems (TODS), v.4 n.1, p.1-29, March 1979 [doi>10.1145/320064.320065]
• 7: Tanaka, Y., Y. Nazuka, and A. Masuyama. "Pipeline Searching and Sorting Modules as Components of a Data Flow Database Computer." Proceedings of the IFIP-80, pp. 427--432.
• 8: Kamibayashi, N., H. Kato, Y. Kiyoki, H. Ozawa, K. Seo, and H. Aiso. "SPIRIT: A New Relational Database Computer Employing Functional-Distributed Multi-Microprocessor Configuration." Proceedings of the First International Conference on Distributed Computing Systems, (1979), pp. 757--771.
• 9: Y. Kiyoki , K. Tanaka , H. Aiso , N. Kamibayashi, Design and evaluation of a relational data base machine employing advanced data structures and algorithms, Proceedings of the 8th annual symposium on Computer Architecture, p.407-423, May 12-14, 1981, Minneapolis, Minnesota, United States
• 10: K. Seo , A. Minematsu , H. Aiso , N. Kamibayashi, A look-ahead data staging architecture for relational data base machines, Proceedings of the 8th annual symposium on Computer Architecture, p.389-406, May 12-14, 1981, Minneapolis, Minnesota, United States
• 11: Toby J. Teorey , Tad B. Pinkerton, A comparative analysis of disk scheduling policies, Communications of the ACM, v.15 n.3, p.177-184, March 1972 [doi>10.1145/361268.361278]
• 12: Richard S. Brice , Stephen W. Sherman, An extension of the performance of a database manager in a virtual memory system using partially locked virtual buffers, ACM Transactions on Database Systems (TODS), v.2 n.2, p.196-207, June 1977 [doi>10.1145/320544.320556]
• 13: Chat-Yu Lam , Stuart E. Madnick, Propeties of storage hierarchy systems with multiple page sizes and redundant data, ACM Transactions on Database Systems (TODS), v.4 n.3, p.345-367, Sept. 1979 [doi>10.1145/320083.320095]