Shared-nothing 并行数据库系统查询优化技术.pdf

金小仓

11页

1次

2024-03-01

免费下载

第23卷 第1期

2000年1月

计  算  机  学  报

CHINESE JCOMPUT ERS

Vol23 No1

Jan2000

Shared



nothing

并行数据库系统查询优化技术

文继荣

1）

 陈 红

1） 2）

 王 珊

2）

1）

（中国科学院计算技术研究所 北京 100080）

2）

（中国人民大学数据与知识工程研究所 北京100872）

收稿日期19990125修改稿收到日期19990622本课题得到国家自然科学基金（6988300）和八六三高技术研究发展计划（863

306

0102041）资助文继荣男1972年生获博士学位现任微软中国研究院副研究员主要研究方向包括数据库与知识库系统

Web

数据组织和查询并行计算等陈 红女1965年生在职博士研究生副教授主要研究方向为数据库与知识库系统王 珊女

1944年生教授博士生导师主要研究方向为数据库与知识库系统

摘 要 查询优化是并行数据库系统的核心技术该文介绍作者自行研制的一个

Shared



nothing

并行数据库系统

PBASE

2中独特的两阶段优化策略为了缩减并行查询优化庞大的搜索空间

PBASE

2将并行查询优化划分为顺

序优化和并行化两个阶段在顺序优化阶段对并行化后的通信代价进行预先估算将通信开销加入顺序优化的代

价模型同时对动态规划搜索算法进行了修正和扩展保证了顺序优化阶段得到的最小代价计划在并行化后代价

仍然最小并行化阶段的优化目标是实现查询工作量在系统内多种资源上的负载平衡提出了资源负载平衡因子

的概念并且通过启发式规则任务调度等机制保证了并行查询执行计划的优化性

关键词 并行数据库系统并行查询优化

Shared



nothing

两阶段优化资源负载平衡

中图法分类号

T P

311

Query Optimization Techniques of A Shared



nothing Parallel Database System

WEN Ji



Rong

1）



CHEN Hong

1） 2）



WANG Shan

2）

1）

（

I nstitute of Comp uting T echnology



Chinese A cademy of S ciences



Beij ing

100080）

2）

（

I nstitute of Data and K now ledge Engineer ing



Renmin University of China



Beij ing

100872）

Abstract



Query optimization is the critical technique of parallel database systems



T his paper

addresses the distinguishing two



phase optimization strategy implemented in a shared



nothing

parallel database system PBASE

2

In order to cut down the enormous search space of parallel

query optimization



PBASE

2

divides parallel query processing into two phases



sequential

optimization and parallelization



In sequential optimization



PBASE

2

predicts the

communication cost of parallel execution



and addes communication cost into cost model



At the

same time



the traditional dynamic programming search algorithm is modified and extended



these mechanisms



it is guaranteed that the sequential minimal



cost plan also is the parallel

minimal



cost plan



T he object of parallelization phase is to balance the query w ork loading among

various resources in the system



T hus



a new concept



resources load



balancing factor



is put

forward



Other techniques such as heuristics



dynamic programming



based parallelizaion

algorithm



and task scheduling ensure the quality of the outgoing parallel query evaluation plans



Keywords



parallel database system



parallel query optimization



Shared



nothing



two



phase

optimization



resources load



balance

1 引 言

并行查询优化主要涉及到三方面的工作首先

需要设计一个并行查询执行计划（

PQEP

简称计

划）表示模型

任意一个查询

可以用模型

中若干等价的计划表示这些等价的计划构成了查

询

的计划搜索空间

其次给定一个代价模型



可以为

中的任意一个计划计算一个代

价指标

Cost

（

PQEP

） 最后给出高效的搜索策略

从

中搜索出一个执行计划

使得

Cost

（

） 

Min

P∈E



Cost

（

） 所有关于查询优化的研究工作

都是围绕这三个方面进行的

并行查询执行计划表示模型定义并行查询执行

计划的基本结构和应当附加的主要标注信息它描

述查询执行的各种重要属性为执行引擎提供足够

的执行信息设计一个有效的并行查询执行计划表

示模型是整个并行查询处理的基础和出发点

7



代价模型的主要功能是按照给定的代价指标

根据操作的处理特性操作间的相互关系数据的物

理统计信息等计算查询执行计划的代价由于操作

间操作内并行性并行化的额外开销流水线延迟

（

Pipeline latency

） 数据倾斜（

Data skew

） 操作间

的资源冲突等因素的影响使得精确的并行计划代价

模型的构造非常困难

1313



并行查询优化的主要困难在于如何缩减其庞大

的计划搜索空间文献13给出了一个包含

个关

系的查询的连接树的数目为



（2n2） 

（ n1） 

可以看

出

具有指数级的复杂度而一个顺序执行计划

又可以通过不同的并行化方法生成大量的并行执行

计划因此并行执行计划的搜索空间规模比顺序执

行计划的搜索空间又要庞大许多如果说在传统数

据库系统中对查询空间进行穷尽搜索还有可能的话

（例如

≤5） 那么对于并行数据库系统来说穷尽

搜索方法的性能是完全不可接受的因此必须采用

适当的方法对搜索空间的规模进行限制尽量排除

那些不可能是优化的执行计划解决这个问题有两

种最主要的思路

1）采用启发式搜索方法通过一些启发式规则

在搜索过程中逐步排除掉那些不可能是优化的计

划从而只搜索整个空间的部分子空间最有影响的

启发式搜索方法有动态规划算法

11

贪心算法随

机算法

8

等

2）对搜索空间的大小预先进行限制使得搜索

空间的规模达到可以接受的程度这实际上等同于

采用预设的启发式规则对搜索空间进行缩减限制

搜索空间的典型方法有两阶段方法

5

多阶段方

法

9

限制连接树形状的方法（例如线性树）

6

等

以上两种方案的共同点是通过对影响计划质量

的一些因素之间的关系进行分析从中提炼出一些

启发式规则通过应用这些规则可以不经过代价比

较而直接裁减掉某些在这些规则看来不可能是优化

的计划如果这些规则是预设的（即无条件的） 则被

称为缩减计划空间的启发式规则如果这些规则是

在搜索过程中动态使用的（即需要一定条件激活

的） 则被称为加速搜索的启发式规则

并行查询优化必须采用适当的启发式规则来降

低优化的复杂度启发式规则的质量是影响并行查

询优化器性能的关键因素好的启发式规则应当在

明显缩减搜索空间的同时又能尽量保留那些优化的

计划

XPRS

系统中采用的两阶段优化方法是最有影

响的缩减并行查询优化搜索空间的方法

5

其基本

思想是把查询优化划分为两个阶段第一阶段采用

传统的查询优化方法产生一个高效的顺序查询执行

计划第二阶段称为并行化阶段对第一阶段产生的

顺序查询执行计划进行并行化产生一个优化的并

行查询执行计划两阶段优化能够明显地缩减搜索

空间并且可以直接利用传统的成熟的顺序优化技

术系统设计人员只需将精力集中于并行化阶段

两阶段优化技术的有效性依赖于一个重要的假

设（称为两阶段假设） 对最优顺序计划的并行化可

以得到最优的并行计划因此两阶段优化策略面临

的关键问题是如何保证顺序优化阶段得到的最优

计划在并行化后仍然保持其优化性一般来说要保

证两阶段假设成立必须有两个前提

1）系统资源消耗最小的顺序计划在并行化后

代价资源消耗仍然最小否则最优的顺序计划可能

会因为并行化额外开销的增加而不再最优

2）顺序优化阶段得到的最优计划可以被任意

地并行化否则最优的顺序计划可能会因为并行化

不充分而不再最优

以前的研究指出两阶段假设仅在

Shared



everything

（简称

）环境下并且只采用操作内并

行方式的情况下才有效在

结构中并行化开销

很小操作系统可以自动地将任务在处理机间动态

分配比较容易达到处理机间的负载平衡另外如

1期文继荣等

Shared



nothing

并行数据库系统查询优化技术

of 11

免费下载

关注

评论