Parallel and Pipelined Filter Operator for Hardware-Accelerated Operator Graphs in Semantic Web Databases

S. Werner, D. Heinrich, M. Stelzner, S. Groppe, R. Backasch, T. Pionteck

Abstract

In this paper, we investigate the use of Field Programmable Gate Arrays (FPGAs) to enhance the performance of filter expressions in Semantic Web databases. The filter operator is a central part of query evaluation. Its main objective is to reduce the amount of data as early as possible in order to reduce the calculation costs for succeeding and more complex operators such as join operators. Due to the proximity to the data source it is essential for the overall query performance that the filter operator is able to evaluate single data items as fast as possible. In this work, the advantages of using FPGAs in query evaluation are outlined and an overview about the provided degree of parallelism is given. We propose two different approaches to implement the filter operator for the Semantic Web database LUPOSDATE. The Fully-Parallel Filter evaluates all conditions by dividing the input into several sub-items which are evaluated by dedicated sub-filters in parallel. The second approach creates a pipeline of sub-filters to evaluate the filter expression step-by-step. If an item reaches the end of this pipeline then it complies the whole filter expression. The final evaluation shows that both approaches of the hardware-implemented filter operator defeat the comparable software solution written in C running at 2.66 GHz. Processing 100M items per second, the hardware-accelerated filter running at 200 MHz provides a more than 5 times higher throughput than the general-purpose CPU. In contrast to the software solution, the total throughput is independent of the match rate and the structure of the filter expression, and is a valuable contribution to the hardware-accelerated query evaluation.
Original languageEnglish
Title of host publication2014 IEEE International Conference on Computer and Information Technology
Number of pages8
Place of Publication Xi'an, China
PublisherIEEE
Publication date01.09.2014
Pages539-546
ISBN (Electronic)978-1-4799-6239-6
DOIs
Publication statusPublished - 01.09.2014
Event14th IEEE International Conference on Computer and Information Technology - Xi'an, Shaanxi, China
Duration: 11.09.201413.09.2014

Research Areas and Centers

  • Research Area: Intelligent Systems
  • Centers: Center for Artificial Intelligence Luebeck (ZKIL)

DFG Research Classification Scheme

  • 409-04 Operating, Communication, Database and Distributed Systems

Fingerprint

Dive into the research topics of 'Parallel and Pipelined Filter Operator for Hardware-Accelerated Operator Graphs in Semantic Web Databases'. Together they form a unique fingerprint.

Cite this