Research Catalog

Title

Optimization of SQL queries for parallel machines / Waqar Hasan.

Author

Hasan, Waqar.

Publication

Berlin ; New York : Springer, ©1996.

Items in the Library & Off-site

Details

Description

xviii, 133 pages : illustrations; 24 cm

Summary

• Parallel execution offers a method for reducing the response time of queries against large databases. We address the problem of parallel query optimization: Given a declarative SQL query, find a procedural parallel plan that delivers the query result in minimal time.
• We develop optimization algorithms using models that incorporate both sources and obstacles to speedup. We address independent, pipelined and partitioned parallelism. We incorporate inherent constraints on available parallelism and the extra cost of parallel execution. Our models are motivated by experiments with NonStop SQL, a commercial parallel DBMS.
• We adopt a two-phase approach to parallel query optimization: JOQR (join ordering and query rewrite), followed by parallelization. JOQR minimizes total work. Then, parallelization spreads work among processors to minimize response time.
• For JOQR, we model communication costs and abstract physical characteristics of data as colors. We devise tree coloring and reordering algorithms that are efficient and optimal.
• We model parallelization as scheduling a tree whose nodes represent operators and edges represent parallel/precedence constraints. Computation/communication costs are represented as node/edge weights. We prove worst-case bounds on the performance ratios of our algorithms and measure average cases using simulation.
• Our results enable the construction of SQL compilers that effectively exploit parallel machines.

Series Statement

Lecture notes in computer science, 0302-9743 ; 1182

Uniform Title

Lecture notes in computer science ; 1182.

Subject

• Solid Quality Learning Melbourne
• SQL (Computer program language)
• Parallel processing (Electronic computers)
• Response-Zeit
• Parallelle verwerking
• SQL
• SQL (langage de programmation)
• Ordinateurs parallèles
• Parallélisme (informatique)
• Parallelle datamaskiner

Bibliography (note)

• Includes bibliographical references (p. [121]-129) and index.

Additional Formats (note)

• Also available in an electronic version.

Contents

1. Introduction -- 2. Price of Parallelism -- 3. JOQR Optimizations -- 4. Scheduling Pipelined Parallelism -- 5. Scheduling Mixed Parallelism -- 6. Summary and Future Work.

ISBN

• 3540620656
• 9783540620655

LCCN

96039704

OCLC

• ocm35978631
• 35978631
• SCSB-2102701

Owning Institutions

Princeton University Library