基于多重加权树的并行数据库查询优化方法

MULTIPLE-WEIGHTED-TREE BASED QUERY OPTIMIZATION METHOD FOR PARALLEL DATABASE SYSTEMS

本文提出了一种基于多重加权树的查询优化方法，包括多重加权树并行查询计划模型、并行查询计划的复杂性模型和查询优化算法．该方法能够处理最常用的选择一投影一连接查询，支持多种并行连接算法，包括流水线缓冲区的存储器代化分配算法、数据操作的处理机与存储器优化分配算法和连接操作实现算法的优选算法．该方法已经用于作者设计与实现的并行关系数据库管理系统原型，效果良好．

A multiple-weighted-tree based query optimization method for paralleldatabase systems is proposed in this paper. The method consists of a multiple-weighted-tree based parallel query plan model, a cost model for parallel queryplans, and a query optimizer. The parallel query plan model is the first one to mod-el all basic relational operations, all three types of parallelism of query execution inparallel database systems, processor and memory allocation to operations, memoryallocation to the buffers between operations in pipelines and data redistribution a-mong processors- The cost model takes the waiting time of the operations inpipelining execution into consideration and is computable in bottom-up fashion.The query optimizer addresses the query optimization problem in the context of Se-lect-Project-Join queries that are widely used in commercial DBMSs. Several heuris-tics determining the processor allocation to operations are derived and used in the.query optimizer. The query optimizer is aware of memory resources in order to gen-erate good-quality plans. It includes the heuristics for determining the memory allo-cation to operations and buffers between operations in pipelines so that the memoryresource is fully exploit. In addition, multiple algorithms for implementing join op-erations are considered in the query optimizer.The query opery optimizer can make an op-timal choice of join algorithm for ezch join operation in a query.The proposed query optimization method has been used in a protoype parallel database manage-ment system designed and implemented by the author.