[kylin]Kylin 快速数据立方算法揭秘
Apache Kylin是一个开源的分布式分析引擎,提供Hadoop之上的SQL查询接口及多维分析(OLAP)能力以支持超大规模数据。它能在亚秒内查询巨大的Hive表。本文将详细介绍Apache Kylin 1.5中的Fast-Cubing算法。 Fast Cubing,也称快速数据立方算法, 是一个新的Cube算法。我们知道,Cube的思想是用空间换时间, 通过预先的计算,把索引及结果存储起来,以换取查询时候的高性能 。在Kylin v1.5以前,Kylin中的Cube只有一种算法:layered cubing,也称逐层算法:它是逐层由底向上,把所有组合算完的过程。 图1是一个四维Cube,有维度A、B、C、D;它会需要五轮的Map-Reduce来完成:第一轮MR的输入是源数据, 这一步会对维度列的值进行编码,并计算ABCD组合的结果。接下来的MR以上一轮的输出为输入,向上聚合计算三个维度的组合: ABC, BCD, ABD, 和ACD;依此类推,直到算出所有的维度组合。 这个算法的优势是每一轮MR以上一轮的输出为结果,这样可以减少重复结算;当计算到后半程的时候,随着数据的减小,计算...