Recursive Query Processing on a Connection Machine

Authors:	Thomas Zurek, Elspeth Minty, Peter Thanisch
Date:	January 1996
Published in:	"Parallel Information Processing", edited by J. Keane
Publisher:	UNICOM, Stanley Thornes Publishers

Abstract

In this paper we give an example of recursive query processing on an SIMD hardware architecture. On one hand the class of linear recursive queries is more general than the class of queries covered by traditional query languages and on the other hand parallelism provides several new possibilities for efficient query processing. This fits well into the arising needs caused by massively growing amounts of data and more expressive queries to be processed in reasonable amounts of time.

The paper presents a model that uncovers a variety of parallel strategies for query processing. We concentrate on two significantly different strategies: the bottom-up and the transitive closure strategy. The join and the transitive closure work out to be the most important operations according to efficiently processing linear recursive queries. Therefore data parallel algorithms for these operations are presented and their respective implementations are analysed. Finally performance results for the two processing strategies are given for two graph structures. The performance results show that neither of the strategies proves to be the best in every case but that a query optimizer can choose the best one in each single case by considering data and query parameters.

Thomas Zurek, <tz@dcs.ed.ac.uk>