Flexible data partitioning schemes for parallel merge joins in semantic web queries

Abstract

In the context of the Semantic Web, large amounts of data must be preprocessed and stored so that they can be queried efficiently later. The key technology in this topic are triple stores, in which all information is stored in the form of (subject, predicate and object) triple patterns. Depending on the triple patterns used within the queries, very different value distributions can be observed within these datasets. Currently, these properties are only exploited implicitly during join optimization in the form of histograms or similar technologies. This paper proposes a new way to take advantage of these different distributions using different partitioning schemes at runtime. This means that an optimal partitioning scheme can be used depending on the data access in order to improve query performance. In the experiments we achieve speedups up to a factor of 5.92 in comparison to no partitioning, and a performance improvement of up to 81% compared to a not optimal number of partitions.