Publications
Search

Publications :: Search

Dependency-Aware Reordering for Parallelizing Query Optimization in Multi-Core CPUs

Show publication

On this page you see the details of the selected publication.

    Publication properties
    Title: Dependency-Aware Reordering for Parallelizing Query Optimization in Multi-Core CPUs
    Rating: (1)
    Discussion: 0 comments
    Date: 2009
    Publication type: Conference paper
    Authors:
    No. First name Last name Show
    1. Wook-Shin Han
    2. Jinsoo Lee
    Download (by DOI): 10.1145/1559845.1559853
    BibTeX: conf/sigmod/HanL09
    DBLP: db/conf/sigmod/sigmod2009.html#HanL09
    Bookmark:

    The following keywords have been assigned to this publication so far. If you have logged in, you can tag this publication with additional keywords.

    Keywords
    No keywords have been assigned to this publication yet.

    If you log in you can tag this publication with additional keywords

    A publication can refer to another publication (outgoing references) or it can be referred to by other publications (incoming references).

    Incoming References
    No incoming references have been assigned to this publication yet.
    Outgoing References
    No outgoing references have been assigned to this publication yet.

    If you log in you can add references to other publications

    A publication can be assigned to a conference, a journal or a school.

    Conference Track
    Conference Name: ACM SIGMOD International Conference on Management of Data, SIGMOD 2009, Providence, Rhode Island, USA, June 29 - July 2, 2009 2009
    Track Name: Research
    URL: http://www.sigmod09.org/

    Abstract

    The state of art commercial query optimizers employ cost-based optimization, and exploits dynamic programming (DP) to find the optimal query execution plan (QEP) without evaluating redundant sub-plans. The number of alternative QEPs enumerated by the DP optimizer can increase exponentially, as the number of joins in the query increases. Recently, by exploiting the new wave of multi-core processor architectures, a state of art parallel optimization referred to as PDPsize has been proposed to parallelize the DP optimization process itself. While PDPsize significantly extends the practical use of DP by up to queries having up to 22-25 tables, it has severe fundamental limitations: 1) supporting only the size-driven DP enumerator, 2) static search space allocation, 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 DPccp and DPhyp are very difficult to parallelize due to tangled dependencies in their join pairs generated. 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 generated. To maximize parallelism, we also introduce a series of novel tuning techniques. Through extensive experiments with various query topologies, we show that our solution supports any type of bottom-up enumerator, achieving linear speedup for each type. Experimental results also show that our solution is much more robust than the state-of-art algorithm with respect to search space allocation, outperforming PDPsize by up to an order of magnitude, when some cores are highly loaded.