Analyzes the costs, and describes the implementation, of three hash-based join algorithms for a general purpose shared-memory multiprocessor. The three algorithms considered are the hashed loops, GRACE and hybrid algorithms. We also describe the results of a set of experiments that validate the cost models presented and demonstrate the relative performance of the three algorithms.>

The authors examine the problem of performing a join involving nested relations in a parallel, shared-everything environment. First they show the difference between joining flat relations and joining nested relations, and then develop a parallel hash-based join algorithm, called the partitioned nested hashed-loops algorithm. Both input/output (I/O) and CPU parallelism are addressed. The implementation and experimental results are presented. The experiments include the effect of the number of CPUs, the amount of memory, the size of the result, the effect of projections, and the effect of the levels of nesting. The experiments showed excellent CPU parallelism speedup.>

Traversal recursion is a class of recursive queries where the evaluation of the query involves traversal of a graph or a tree. This limited type of recursion arises in many applications. In this report we investigate a simple file structure that efficiently supports traversal recursion over large, acyclic graphs. The nodes of the graph are sorted in topological order and stored in a B-tree. Hence, traversal of the graph can be done in a single scan. Nodes and edges can also be inserted, deleted, and modified efficiently.