日期:2014-05-16  浏览次数:20403 次

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的时候也能够处理掉。

?