Title :
The design and implementation of a parallel join algorithm for nested relations on shared-memory multiprocessors
Author :
Deshpande, V. ; Larson, P.-A.
Author_Institution :
Dept. of Comput. Sci., Waterloo Univ., Ont., Canada
Abstract :
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
Keywords :
database theory; file organisation; parallel algorithms; programming theory; relational databases; CPU parallelism; I/O parallelism; flat relations; input output parallelism; nested relations; nesting levels; parallel hash-based join algorithm; partitioned nested hashed-loops algorithm; shared-everything environment; shared-memory multiprocessors; Algebra; Algorithm design and analysis; Computer science; Information technology; Parallel architectures; Parallel processing; Partitioning algorithms; Prototypes; Query processing; Relational databases;
Conference_Titel :
Data Engineering, 1992. Proceedings. Eighth International Conference on
Conference_Location :
Tempe, AZ
Print_ISBN :
0-8186-2545-7
DOI :
10.1109/ICDE.1992.213204