PERFORMANCE ANALYSIS OF PARALLEL OBJECT-ORIENTED QUERY-PROCESSING ALGORITHMS

Advanced application domains such as computer-aided design, computer-a ided software engineering, and office automation are characterized by their need to store, retrieve, and manage large quantities of data hav ing complex structures. A number of object-oriented database managemen t systems (OODBMS) are currently available that can effectively captur e and process the complex data. The existing implementations of OODBMS outperform relational systems by maintaining and querying cross-refer ences among related objects. However, the existing OODBMS still do not meet the efficiency requirements of advanced applications that requir e the execution of complex queries involving the retrieval of a large number of data objects and relationships among them. Parallel executio n can significantly improve the performance of complex OO queries. In this paper, we analyze the performance of parallel OO query processing algorithms for various benchmark application domains. The application domains are characterized by specific mixes of queries of different s emantic complexities. The performance of the application domains has b een analyzed for various system and data parameters by running paralle l programs on a 32-node transputer based parallel machine developed at the IBM Research Center at Yorktown Heights. The parallel processing algorithms, data routing techniques, and query management and control strategies have been implemented to obtain accurate estimation of cont rolling and processing overheads. However, generation of large complex databases for the study was impractical. Hence, the data used in the simulation have been parameterized. The parallel OO query processing a lgorithms analyzed in this study are based on a query graph approach r ather than the traditional query tree approach. Using the query graph approach, a query is processed by simultaneously initiating the execut ion at several object classes, thereby, improving the parallelism. Dur ing processing, the algorithms avoid the execution of time-consuming j oin operations by making use of the object references among the object s. Further, the algorithms do not generate any temporary data, thereby , reducing disk accesses. This is accomplished by marking the selected objects and by employing a two-phase query processing strategy.