Optimization for iterative queries on MapReduce
Optimization for iterative queries on MapReduce
复制标题
DOI：
10.14778/2732240.2732243
复制
发表时间：
2013-12
期刊：
影响因子：
--
通讯作者：
Makoto Onizuka;H. Kato;S. Hidaka;Keisuke Nakano;Zhenjiang Hu
中科院分区：
文献类型：
--
作者：
Makoto Onizuka;H. Kato;S. Hidaka;Keisuke Nakano;Zhenjiang Hu
提出了一种面向分布式环境下迭代查询的查询优化方法OptIQ。OptIQ通过扩展传统的视图物化和增量视图评估技术，消除了不同迭代之间的冗余计算。首先，OptIQ将迭代查询分解为不变视图和变量视图，并物化前者。通过在迭代之间重用物化视图来消除冗余计算。其次，OptIQ递增地评估变体视图，从而通过跳过对变体视图中收敛的元组的评估来消除多余的计算。通过对真实数据集进行PageRank和k-Means聚类查询，验证了OptIQ算法的有效性。结果表明，OptIQ实现了高效率，在不消除迭代之间的冗余计算的情况下，速度最高可达5倍。
We propose OptIQ, a query optimization approach for iterative queries in distributed environment. OptIQ removes redundant computations among different iterations by extending the traditional techniques of view materialization and incremental view evaluation. First, OptIQ decomposes iterative queries into invariant and variant views, and materializes the former view. Redundant computations are removed by reusing the materialized view among iterations. Second, OptIQ incrementally evaluates the variant view, so that redundant computations are removed by skipping the evaluation on converged tuples in the variant view. We verify the effectiveness of OptIQ through the queries of PageRank and k-means clustering on real datasets. The results show that OptIQ achieves high efficiency, up to five times faster than is possible without removing the redundant computations among iterations.