Flow algorithms for parallel query optimization

Amol Deshpande, Lisa Hellerstein

    Research output: Chapter in Book/Report/Conference proceedingConference contribution


    We address the problem of minimizing the response time of a multi-way join query using pipelined (inter-operator) parallelism, in a parallel or a distributed environment. We observe that in order to fully exploit the parallelism in the system, we must consider a new class of " interleaving" plans, where multiple query plans are used simultaneously to minimize the response time of a query (or to maximize the tuple-throughput of the system). We cast the query planning problem in this environment as a "flow maximization problem", and present polynomial-time algorithms that (statically) And the optimal set of plans to use for a given query, for a large class of multi-way join queries. Our proposed algorithms also naturally extend to query optimization over web services. Finally we present an extensive experimental evaluation that demonstrates both the need to consider such plans in parallel query processing and the effectiveness of our algorithms.

    Original languageEnglish (US)
    Title of host publicationProceedings of the 2008 IEEE 24th International Conference on Data Engineering, ICDE'08
    Number of pages10
    StatePublished - 2008
    Event2008 IEEE 24th International Conference on Data Engineering, ICDE'08 - Cancun, Mexico
    Duration: Apr 7 2008Apr 12 2008

    Publication series

    NameProceedings - International Conference on Data Engineering
    ISSN (Print)1084-4627


    Other2008 IEEE 24th International Conference on Data Engineering, ICDE'08

    ASJC Scopus subject areas

    • Software
    • Signal Processing
    • Information Systems


    Dive into the research topics of 'Flow algorithms for parallel query optimization'. Together they form a unique fingerprint.

    Cite this