Spark环境下基于多维布隆过滤器的星型连接算法

Star join algorithm based on multi-dimensional Bloom filter in Spark

为了适应联机分析处理(OLAP)系统中实时数据高性能分析需求不断提高的需求,提出一种能够适合Spark环境并结合多维Bloom Filter(MDBF)的星型连接算法SMDBFSJ。首先,根据多个维表构建MDBF,利用其占用空间小的特点,广播到所有节点;然后,在本地节点完成事实表过滤操作,事实表不需要在节点间移动数据;最后,过滤后的事实表与维表采用重划分方式进行连接,进而得到最终结果。SMDBFSJ算法避免了事实表数据移动,通过MDBF减小了需要广播的数据量,充分结合了广播连接和重划分连接的优势。实验结果表明了该算法的有效性,在单机和集群环境下,该算法相比重划分连接均获得了3倍左右的性能提升。

To meet the high performance analysis requirements for real-time data in On-Line Analytical Processing（ OLAP） system, a new star join algorithm which is suitable for Spark platform was proposed based on Multi-Dimensional Bloom Filter（ MDBF）, namely SMDBFSJ（ Spark Multi-Dimensional Bloom Filter Star Join）. First of all, MDBF was built according to the dimension tables and broadcasted to all the nodes based on the feature of small size. Then the fact table was filtered completely on the local node, and there was no data movement between nodes. Finally, the filtered fact table and dimension tables were joined using repartition join model to get the final result. SMDBFSJ algorithm avoides the data moving of fact table, reduces the size of broadcasting data using MDBF, as well as fully combines the advantages of broadcast join and repartition join. The experimental results prove the validity of SMDBFSJ algorithm, in stand-alone and cluster environments.SMDBFSJ algorithm can obtain about three times of performance improvement compared with repartition join in Spark.