  One of the major challenges in large-scale data processing with MapReduce is
the smart computation of joins. Since Semantic Web datasets published in RDF
have increased rapidly over the last few years, scalable join techniques become
an important issue for SPARQL query processing as well. In this paper, we
introduce the Map-Side Index Nested Loop Join (MAPSIN join) which combines
scalable indexing capabilities of NoSQL storage systems like HBase, that suffer
from an insufficient distributed processing layer, with MapReduce, which in
turn does not provide appropriate storage structures for efficient large-scale
join processing. While retaining the flexibility of commonly used reduce-side
joins, we leverage the effectiveness of map-side joins without any changes to
the underlying framework. We demonstrate the significant benefits of MAPSIN
joins for the processing of SPARQL basic graph patterns on large RDF datasets
by an evaluation with the LUBM and SP2Bench benchmarks. For most queries,
MAPSIN join based query execution outperforms reduce-side join based execution
by an order of magnitude.
