Parallel forward pointer chasing algorithm for path expressions: Design and performance evaluation

Path expression is an essential query facility to locate complex objects in object database systems. Because computing path expressing is a time-consuming operation, the optimizing and paralleling execution of a path expression are critical factors for achieving high performance of object-oriented database systems. A parallel forward pointer chasing (PFPC) algorithm for computing path expressions in parallel was presented. The PFPC algorithm is a parallel version of forward pointer chasing algorithms that fully exploits pipelining parallelism and executes I/O operations in parallel. The algorithm was implemented in an object database system-FISH in NOW. The implementation details of the algorithm were described and the performance analysis was given.