A technique for SPARQL OPTIONAL (left-outer-join) queries
Medha Atre · arXiv (Cornell University) · 2013
SPARQL basic graph pattern (BGP) (aka SQL inner-join) query optimization is a well researched area. But optimization of OP-TIONAL pattern queries (SQL left-outer-joins) poses additional challenges, because of the restriction on the reorderability of left-joins. Query logs of SPARQL endpoints like that of DBPedia show that the occurrence of OPTIONAL pattern queries is as high as 17-50%. Previously published work on SQL left-outer-joins pro-poses free-reorderability of left-outer-joins, using additional opera-tors like nullification and best-match to remove spurious (incorrect) results. In this paper, we present a novel technique – OptBitMat – for nested SPARQL OPTIONAL and BGP queries. first constructs and manipulates a query graph of hypernodes. Further OptBitMat’s 2-phase query processing algorithm uses this query graph to (i) ag-gressively prune the candidate RDF triples, and (ii) generate final results without pairwise joins, unlike the traditional join query pro-cessors. OptBitMat keeps the memory footprint of the query pro-cessor low by using compressed bit-matrices (BitMats) to represent an RDF graph, works on them without uncompressing, and does not generate spurious intermediate results. We have demonstrated OptBitMat’s superior performance in comparison to MonetDB and IBM DB2 using nested SPARQL BGP and OPTIONAL pattern queries of varying complexity and selectivity, over RDF graphs of up to 1.33 billion triples (much larger than the previously published work on left-outer-joins), using a commodity Linux machine.