Abstract: This paper proposes a parallel percentile computing algorithm over flattening encoded star schema. Firstlyhierarchies of all dimensions pertaining to queries in a star schema are encoded into the fact table, the encodingscheme enables processing queries without joining between the fact table and dimension tables after query rewriting,thus data can be partitioned onto a large cluster evenly, and high performance is achieved through parallel processing.Percentile computing is not naturally parallelizable, this paper also puts forward an iterative parallel algorithm based on prediction. Through paying out the cost of data sampling, the algorithm converges quickly, and resolves the problem of computing percentile on a large scale cluster. Experiment results demonstrate that not only the algorithm converges quickly, but also the network overhead is acceptable.

Key words: star schema, percentile, parallel algorithm, iterative

摘要： 提出了星型模型扁平化编码方法上的百分点聚集函数的并行算法。把星型模型中维表上与查询相关的维度层次信息编码到事实表里，该编码方法使得经过改写的聚集查询，在查询处理过程中无需进行事实表和维表之间的连接，数据可以均匀分布到机群上，利用并行处理提高查询性能。百分点计算不具有天然的并行性，提出了基于采样预测的并行迭代式算法，通过付出采样数据的网络传输开销，使得算法快速收敛，解决了大规模机群上的百分点聚集函数计算的性能问题。实验结果证实，该算法不仅能快速收敛，而且其网络传输开销也是可以接受的。

关键词: 星型模型, 百分点, 并行算法, 迭代