Large-Scale RDF Processing with MapReduce - Large Scale and Big Data: Processing and Management - page 172

5.6.3 m ultiway J oin o Ptimization
Instead of processing concatenated triple patterns successively as a sequence of two-
way joins, some basic graph patterns allow to apply a multiway join approach to
process joins between several concatenated triple patterns at once in a single map
phase. This is typically the case for star pattern queries where triple patterns share
the same join variable. The SPARQL query introduced in Section 5.5 is an example
for such a query as all triple patterns share the same join variable ? article . This query
can be processed by a three-way join in a single map-phase instead of two consecu-
tive two-way joins.
We extended our approach to support this multiway join optimization. Again, the
first triple pattern p 1 is processed using a distributed table scan as input for the map
phase. But instead of using a sequence of n map phases to compute p 1 ⋈ p 2 ⋈ …
⋈ p n +1 we use a single map phase thus saving n − 1 MapReduce iterations. Hence,
the map function needs to retrieve all mappings for p 2 , p 3 , …, p n +1 that are compat-
ible to the input mapping μ 1 for p 1 . Therefore, the join variable ? v s in p 2 , p 3 , …, p n +1
(e.g., ? article ) is substituted with the corresponding variable binding μ 1 (? v s ). The
substituted triple patterns pp

subsub sub sub

=µ 1 () are then used to retrieve
the compatible mappings using HBase table lookups. This general case of the MAPSIN
multiway join is outlined in Algorithm 5.2.

, , ,  + with p p p

2 3 n 1 i i

Algorithm 5.2: MAPSIN multiway join: map(inKey, inValue)

input : inKey, inValue: value contains input mapping, key can be ignored
output : multiset of mappings
1 p n+i Cong.getNextPattern()
2
3
4 / / iterate over allsubsequent multiway patterns
5 for i 1 to # p do
6

μ n inValue .getInputMapping()
Ω n { μ n }

Ω n+i ∅, p n+i Config.getNextPattern()

7 p n+i μ n ( p n+i )/ / substitute shared vars in p n + i

sub

sub

8
9
10

results HBase.GET( p n + i ) / / table index lookup using substituted pattern

if results ≠ ∅ then

/ / merge previousmappingswith compatiblemappingsfor p n+i

11 foreach mapping μ in results do

12 foreach mapping μ' in Ω n+i −1

13
14 end
15 end
16 else
17 / / no compatible mappings for p n+i hence join result for μ n is empty
18 return
19 end
20 end
21 emit( null , Ω n +# p ) / / key is not used since there is no reduce phase

Ω n+i Ω n+i ( μ μ' )