动态分片在线聚集  

Dynamic Data-Partitioned Online Aggregation

作　　者：安明远[1,2] 孙秀明[3] 孙凝晖[1] 

机构地区：[1]中国科学院计算技术研究所计算机系统结构重点实验室,北京100190 [2]中国科学院研究生院,北京100190 [3]中国科学院电子学研究所,北京100190

出　　处：《计算机研究与发展》2010年第11期1928-1935,共8页Journal of Computer Research and Development

基　　金：国家"八六三"高技术研究发展计划基金项目(2006AA01A102)~~

摘　　要：传统的在线聚集方法为了避免执行中随机I/O导致的性能下降,假设数据本身近似随机分布于数据文件中,用顺序I/O来代替随机I/O.数据随机分布于数据文件的假设在很多实际的应用场景中是难以成立的,从而导致查询结果产生很大误差.提出了动态数据分片在线聚集算法DDPOA(dynamicdata-partitioned online aggregation),将整个数据集分片,对各个子数据集独立计算,线性组合子集结果进而得到全集最终结果,一方面降低了在线聚集对整体数据集随机分布的要求,提高了准确性,另一方面动态调整分片数量以改善I/O性能,缩短完成时间.真实系统负载上的实验表明:DDPOA与传统在线聚集相比,在完成时间相差不大的情况下准确性有了大幅提高.To avoid the performance degradation due to random IO,traditional online aggregation algorithms assume that the source data are already randomized in the data file,so sequential access approximately equals to random sampling over the data.But this assumption doesn＇t hold in many real scenes which leads to obvious error when running the algorithms.The authors propose a new method： dynamic data-partitioned online aggregation（DDPOA）.DDPOA logically splits the data into non-conjunctive partitions,each of which consists of consecutive data items in the data file,computes estimates based on individual partition,and then uses specific linear combination of these values to estimate the final result.DDPOA weakens the randomization requirement over the whole dataset and makes the estimates more accurate.Accessing partitioned data could cause lower performance due to random disk IO.To handle IO performance issue,DDPOA dynamically adjusts the partitions during execution.Adjacent partitions that are similar enough will be judged and merged into one which improves the IO performance without losing the accuracy.Experiment on real dataset from network security monitor system DBroker shows that DDPOA is much better than traditional algorithms in terms of accuracy with little performance overhead.When it comes to the dataset satisfying the randomization assumption,DDPOA is as good as the traditional algorithms.

关 键 词：数据库 近似查询 在线聚集 采样 动态分片 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]