Dependency-aware reordering for parallelizing query optimization in multi-core CPUs Export

@inproceedings{citeulike:5446819, abstract = {The state of the art commercial query optimizers employ cost-based optimization and exploit dynamic programming ( DP ) to find the optimal query execution plan ( QEP ) without evaluating redundant sub-plans. The number of alternative QEP s enumerated by the DP query optimizer can increase exponentially, as the number of joins in the query increases. Recently, by exploiting the coming wave of multi-core processor architectures, a state of the art parallel optimization algorithm [14], referred to as PDP sva , has been proposed to parallelize the "time-consuming" DP query optimization process itself. While PDP sva significantly extends the practical use of DP to queries having up to 20-25 tables, it has several limitations: 1) supporting only the size-driven DP enumerator, 2) statically allocating search space, and 3) not fully exploiting parallelism. In this paper, we propose the first generic solution for parallelizing any type of bottom-up optimizer, including the graph-traversal driven type, and for supporting dynamic search allocation and full parallelism. This is a challenging problem, since recently developed, state of art DP optimizers such as DP cpp [21] and DP hyp [22] are very difficult to parallelize due to tangled dependencies in the join pairs they generate. Unless the solution is very carefully devised, a lot of synchronization conflicts are bound to occur. By viewing a serial bottom-up optimizer as one which generates a totally ordered sequence of join pairs in a streaming fashion, we propose a novel concept of dependency-aware reordering , which minimizes waiting time caused by dependencies of join pairs. To maximize parallelism, we also introduce a series of novel performance optimization techniques: 1) pipelining of join pair generation and plan generation; 2) the synchronization-free global MEMO; and 3) threading across dependencies. Through extensive experiments with various query topologies, we show that our solution supports any type of bottom up optimization, achieving linear speedup for each type. Despite the fact that our solution is generic, due to sophisticated optimization techniques, our generic parallel optimizer outperforms PDP sva tailored to size-driven enumeration. Experimental results also show that our solution is much more robust than PDP sva with respect to search space allocation.}, address = {New York, NY, USA}, author = {Han, Wook S. and Lee, Jinsoo}, booktitle = {SIGMOD '09: Proceedings of the 35th SIGMOD international conference on Management of data}, citeulike-article-id = {5446819}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1559845.1559853}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/1559845.1559853}, doi = {10.1145/1559845.1559853}, isbn = {978-1-60558-551-2}, keywords = {2009, join, manycore, multicore, optimization, sigmod}, location = {Providence, Rhode Island, USA}, pages = {45--58}, posted-at = {2009-08-17 10:13:37}, priority = {2}, publisher = {ACM}, title = {Dependency-aware reordering for parallelizing query optimization in multi-core CPUs}, url = {http://dx.doi.org/10.1145/1559845.1559853}, year = {2009} }

TY - CONF ID - citeulike:5446819 L3 - citeulike-article-id:5446819 N2 - The state of the art commercial query optimizers employ cost-based optimization and exploit dynamic programming ( DP ) to find the optimal query execution plan ( QEP ) without evaluating redundant sub-plans. The number of alternative QEP s enumerated by the DP query optimizer can increase exponentially, as the number of joins in the query increases. Recently, by exploiting the coming wave of multi-core processor architectures, a state of the art parallel optimization algorithm [14], referred to as PDP sva , has been proposed to parallelize the "time-consuming" DP query optimization process itself. While PDP sva significantly extends the practical use of DP to queries having up to 20-25 tables, it has several limitations: 1) supporting only the size-driven DP enumerator, 2) statically allocating search space, and 3) not fully exploiting parallelism. In this paper, we propose the first generic solution for parallelizing any type of bottom-up optimizer, including the graph-traversal driven type, and for supporting dynamic search allocation and full parallelism. This is a challenging problem, since recently developed, state of art DP optimizers such as DP cpp [21] and DP hyp [22] are very difficult to parallelize due to tangled dependencies in the join pairs they generate. Unless the solution is very carefully devised, a lot of synchronization conflicts are bound to occur. By viewing a serial bottom-up optimizer as one which generates a totally ordered sequence of join pairs in a streaming fashion, we propose a novel concept of dependency-aware reordering , which minimizes waiting time caused by dependencies of join pairs. To maximize parallelism, we also introduce a series of novel performance optimization techniques: 1) pipelining of join pair generation and plan generation; 2) the synchronization-free global MEMO; and 3) threading across dependencies. Through extensive experiments with various query topologies, we show that our solution supports any type of bottom up optimization, achieving linear speedup for each type. Despite the fact that our solution is generic, due to sophisticated optimization techniques, our generic parallel optimizer outperforms PDP sva tailored to size-driven enumeration. Experimental results also show that our solution is much more robust than PDP sva with respect to search space allocation. CY - Providence, Rhode Island, USA SN - 978-1-60558-551-2 AD - New York, NY, USA EP - 58 TI - Dependency-aware reordering for parallelizing query optimization in multi-core CPUs PB - ACM T2 - SIGMOD '09: Proceedings of the 35th SIGMOD international conference on Management of data SP - 45 KW - 2009 KW - join KW - manycore KW - multicore KW - optimization KW - sigmod AU - Han, Wook AU - Lee, Jinsoo PY - 2009/// UR - http://dx.doi.org/10.1145/1559845.1559853 ER -