MapReduce之Join操作(4)

• 半连接(semijoin)

      之前已经讨论了reduce-side join和map-side join(replicated join)，第一种较通用但效率不高，第二种对于表的大小有需求。然而即使存在表的大小不对称的情况，在许多情况下较小的表仍然不能存到内存中。这里讨论一下半连接(semijoin)，这是传统的关系型数据库中的概念。它对应这样一种常见需求：用户只关心合并之后的某些元组。例如，在前面的例子中，我只想知道Customer ID为3的元组信息。这时，前面那些方法就传输了大量的无用数据，Customer ID为1,2,4的完全可以舍弃掉。

      既然如此，那么只需要将Customers表中ID为3的元组作为“背景数据”放在DistributedCache中即可。这也就是将join后过滤变为过滤后join，减小了数据传输量。进一步优化，实际上只放Customer ID就行了。但是如果这些Customer ID数量仍然非常大，怎么办？比如用户需要知道Customer ID为1-1000000000的信息，该如何处理？这就需要用到下面的BloomFilter了。

 

 

• 半连接之BloomFilter处理
  

       BloomFilter是一种比较优雅的数据结构，关于其介绍可见http://bjyjtdj.iteye.com/blog/1455029。只需要将这些k值放在BloomFilter中就可以大大减小空间，即使有“漏网之鱼”，在最后join的时候也能够处理掉。