Parallel Join Processing on Graphics Processors for the Resource Description Framework

Abstract:
The Resource Description Framework (RDF) originated from the Semantic Web field and is now increasingly used in other areas as well. The database community in particular took up RDF as an alternative data representation model and is researching new ways of storing and querying information in this format. The focus has mostly been on physical design and data compression issues with query processing currently done in a conventional manner. Especially in terms of parallel query processing there has not been any work which concentrates on RDF exclusively. In this work, we present a parallel join algorithm designed for Graphics Processing Units (GPUs) that is intended to be used for a query processor that can handle RDF and its query language SPARQL, although it is not restricted to those. The algorithm is a generalization of three GPU joins published in previous work. We demonstrate that our algorithm has slightly better performance even with the overhead of generalization. Additionally, we present an extension framework which manages multiple joins running concurrently. The framework in combination with GPU parallel processing improves long-term query execution. If many joins are processed with the framework over a longer period, average execution time decreases. Experiment results indicate that the join algorithm and its extension framework contribute to better overall execution times, but are currently useful only with large data inputs due to hardware architecture restrictions.