【University of Tokyo 】 GRACE Parallel Relational Database Machine

Masaru Kitsuregawa led the research into GRACE beginning in about 1981. In a conventional relational database, a join operation creates a new relationship from two relations via common keys. Querying all records of the two relations in this case has a complexity on the order of m×n where m and n are the number of records in each relation. However, a join operation that finds the hash value of keys in each relation, forms clusters of records belonging to identical hash values, and joins the relations by cluster is significantly less complex, on the order of m + n. GRACE was developed based on this insight. The key component of the machine was the processing module. After being passed records organized in clusters, each processing module sorted, merged, and joined records by key with a pipeline method and, when necessary, found the hash value of the result.

In terms of architecture, GRACE consisted of multiple processing modules, a memory module, and a disk module that contained the database. Two separate ring networks connected processing modules with the memory module and the memory module with the disk module. An LSI sorter was embedded in each processing module, and a hash function was incorporated in the disk module and processing modules.

Compiled from pp.195-196, "The History of Japanese Computers", edited by the Special Committee for the History of Computing, IPSJ. Ohmsha, 2010.


  
University of Tokyo's GRACE