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.
|Number of pages||12|
|Journal||Proceedings of the VLDB Endowment|
|Publication status||Published - 2013 Dec|
|Event||Proceedings of the 40th International Conference on Very Large Data Bases, VLDB 2014 - Hangzhou, China|
Duration: 2014 Sept 1 → 2014 Sept 5