Paper Info
Title
Old techniques for new join algorithms: A case study in RDF processing
Abstract
Recently there has been significant interest around designing specialized RDF engines, as traditional query processing mechanisms incur orders of magnitude performance gaps on many RDF workloads. At the same time researchers have released new worst-case optimal join algorithms which can be asymptotically better than the join algorithms in traditional engines. In this paper we apply worst-case optimal join algorithms to a standard RDF workload, the LUBM benchmark, for the first time. We do so using two worst-case optimal engines: (1) LogicBlox, a commercial database engine, and (2) EmptyHeaded, our prototype research engine with enhanced worst-case optimal join algorithms. We show that without any added optimizations both LogicBlox and EmptyHeaded outperform two state-of-the-art specialized RDF engines, RDF-3X and TripleBit, by up to 6× on cyclic join queries-the queries where traditional optimizers are suboptimal. On the remaining, less complex queries in the LUBM benchmark, we show that three classic query optimization techniques enable EmptyHeaded to compete with RDF engines, even when there is no asymptotic advantage to the worst-case optimal approach. We validate that our design has merit as EmptyHeaded outperforms MonetDB by three orders of magnitude and LogicBlox by two orders of magnitude, while remaining within an order of magnitude of RDF-3X and TripleBit.
Year
DOI
Venue
2016
10.1109/ICDEW.2016.7495625
2016 IEEE 32nd International Conference on Data Engineering Workshops (ICDEW)
Keywords
DocType
Volume
RDF processing,query processing mechanisms,worst-case optimal join algorithms,LUBM benchmark,LogicBlox,commercial database engine,EmptyHeaded,query optimization techniques,TripleBit,RDF-3X,semantic Web
Conference
abs/1602.03557
Citations 
PageRank 
References 
7
0.47
13
Authors
4
Name
Order
Citations
PageRank
Ré Christopher13422192.34
Ré Christopher23422192.34
susan tu3431.71
Kunle Olukotun44532373.50