Query Optimization for Parallel Relational Databases

本研究针对通用并行机的关系查询优化问题进行研究。这个项目的主要目标是开发查询优化器，为并行机生成高效的查询计划。数据库查询优化器的三个主要组件是其查询计划表示、成本模型和搜索算法。该项目解决了开发包含运算器内和运算器间并行性以及流水线的计划表示的问题。此外，还将开发成本模型，区分完成的总工作量，即单处理机所需的(顺序)时间和多处理机所需的总(并行)时间。成本模型取决于查询和数据库参数以及体系结构参数。基于成本的搜索算法选择高效(低成本)的查询计划。由于搜索空间比单处理器查询优化的搜索空间大得多，本研究将开发新的启发式算法来剪除搜索空间。此外，由于有多处理器可用，研究还将调查并行处理对优化过程本身的适用性。这一研究结果将对并行关系数据库中高效的查询处理产生影响。

This research address the problem of relational query optimization for general purpose parallel machines. The principle objective of this project to develop query optimizer that will generate efficient query plans for parallel machines. The three main components of a database query optimizer are its query plan representation, its cost model, and its search algorithm. This project addresses the issue of developing a plan representation that incorporates intra- and inter-operator parallelism, as well as pipelining. Furthermore, cost models will be developed which distinguish between the total work done, i.e. the (sequential) time it would take on a uni-processor and total (parallel) time taken on a multi-processor. The cost model depends on the query and database parameters, as well as architecture parameters. A cost-based search algorithm selects efficient (low cost) query plans. Since the search space is much larger than that found in uni-processor query optimization, this research will develop new heuristics to prune the search space. Furthermore, since a multiprocessor is available, the research will also investigate applicability of parallel processing to the optimization process itself. The results of this research will have an impact on efficient query processing in parallel relational databases.