（计算机软件与理论专业论文）数据库管理系统中查询优化的设计和实现.pdf

浙江大学硕士学位论文 摘要 两要 数据库管理系统软件是数据处理的核心，发展国产数据库软件一直都是我国 科研技术人员的目标。国防、政府、金融等要害部门对自主、安全的数据库管理 系统提出了非常追切的要求。在此背景下，发展国产数据库系统，将对我国软件 产业及相关产业发挥重大影响。本文就是在研究开发8 6 3 软件专项“数据库管理 系统及其应用”的过程中实现查询优化模块所作的研发丁：作，支撑数据库高效正 常运行。 查询优化是数据库管理系统的一个重要组成部分。本文在介绍了o s c a r 数据 库系统的体系结构之后，介绍了查询优化的功能，给出了o s c a r 数据库系统的查 询处理器工作步骤及其和数据库管理系统其他模块的关系。本文之后主要讨论了 o s c a r 数据库系统查询优化器的设计和实现。详细介绍了查询优化的基础。接着 本文介绍了查询优化的关键技术：预处理技术和子查询提升技术等，再接着详细 讨论了存取路径的选择和路径代价的估算方法。 相同模式的查询语句一般具有相同的优化结果，相同模式的查询语句只需作 一次语法分析和查询优化，为了避免多次的语法分析和查询优化，有必要对这些 查询语句进行缓冲，查询计划缓冲机制有效的解决了这个问题。 在本文提出的内容下，数据库管理系统的物理表模块在功能和性能上都得以 很好的实现，为自主研发数据库管理系统提出了很好的思路和做出了有益的实 践。 关键词：数据库管理系统：查询：查询优化：选择性因子 浙江大学硕l 学位论文 a b s t r a c t a b s t r a c t d a t a b a s es o f t w a r ei st h ek e r n e lo fd a t ap r o c e s s i n g ；0 1 2 1 s c i e n t i s l sa r ea l w a y st r y i n gt od e v e l o p o u ro w nd a t a b a s em a n a g e m e n ts y s t e m 。a tt h es a m et i m et h ev i t a ld e p a r t m e n t ss u c h3 sn a t i o n a l d e f e n s e ，g o v e r n m e n t ，f i n a n c ed e m a n das a f ed b m s s od e v e l o p i n go u ro w nd b m s w i l la f f e c t c h i n a ss o f t w a r ei n d u s t r ya n dp m t e c tn a t i o n a li n f o r m a t i o n 。t h i sp a p e ri sa b o u tt h er e s e a r c hw o r k f o r “d b m sa n da p p l i c a t i o n ”p r o j e c tw h i c hi st h en m i n n a l8 6 3h i g h q e c hp r o g r a m s ，i n t r o d u c i n g t h em o d u l e o f q u e r yo p t i m i z a t i o nw h i c hs u p p o r t st h es y s t e mw o r k i n g i ng o o do r d e ra n dw i t hh i g h p e r f o r m a n c e q u e r yo p t i m i z a t i o ni s a l l i m p o r t a n te l e m e n to fd a t a b a s em a n a g e rs y s t e m 。a f t e r d e s c r i b i n gt h ea r c h i t e c t u r eo f o u ro w l 2d b m s ，t h i sp a p e ri n t r o d u c et h ef i m c t i o no f q u e r yo p t i m i z a t i o n ，t h ec o m m o np r o c e s s i n gs t e p so fo s c a rq u e r yo p t i m i z a t i o nt h e r e l a t i o nw i t ho t h e rm o d u l e s t h e n ，t h i s p a p e rm a i n l y d i s c u s st h e d e s i g n a n d i m p l e m e n t a t i o no fo s c a rq u e r yo p t i m i z a t i o n i ti n t r o d u c e st h ec o m m o nr u l e so f q u e r yo p t i m i z a t i o n 。t h e nt h et e c h n i q u eo fq u e r yp r e p r o c e s s i n ga n dp u l l i n gs u bq u e r y u pi si n t r o d u c e d f i n a l l y , t h ea c c e s sp a t hs e l e c t i o na n dt h ea c c o u n tm e t h o do fc o n s t e v a l u a t i o na r ed i s c u s s e di nd e t a i l ， b e c a u s eq u e r ys e n t e n c e so ft h es a m ep a t t e mh a st h es a n l er e s u l to f o p t i m i z a t i o n i ng e n e r a l ，s oi tn e e do n l yb e o p t i m i z e do n et i m e i no r d e r t oi m p r o v e p e r f o r m a n c eo f q u e r y , w e c a n p r o v i d eac a c h et os a v eq u e r yr e s u l t i tr e s o l v e st h ep r o b l e me f f e c t i v e l y b a s e do f ft h ec o n t e n t so ft h i sp a p e r , q u e r yo p t i m i z a t i o nm o d u l ew a s i m p l e m e n t e d p r o p e d n i ti sau s e f u lp r a c t i c eo f d e v e l o p i n go u ro w nd b m s p r o d u c t k e yw o r d s ：d b m s ；q u e r y ；q u e r yo p t i m i z a t i o n ；s e l e c t i v i t 浙江大学硕上学位论文 第一章绪论 1 1 研究背景 第一章绪论 数据库技术是当今信息管理的最新技术，其核心就是数据库管理系统( 简 称d b m s ) 。d b m s 是各类管理信息系统的支撑平台，也是信息化建设中需求量最大、 应用最广泛的基础性软件。从2 0 世纪6 0 年代末开始，数据库技术经历了层次数 据库、网状数据库和关系数据库三个阶段。8 0 年代以来，数据库技术在商业领 域的巨大成功刺激了其他领域对数据库技术需求的迅速增长，这些新的领域为数 据库应用开辟了新的天地，需求直接推动了数据库技术的研究和发展，数据库技 术呈现出网络化、智能化、标准化和超大型化的发展趋势。 2 0 0 3 年，全球数据库软件市场达到7 0 6 亿美元。而根据市场调研机构i d c 预测，全球数据库市场规模到2 0 0 6 年将达到2 0 0 亿美元。在国内，2 0 0 0 年我国 数据库管理系统d b m s 市场额为3 2 亿元人民币，2 0 0 1 年为3 8 亿元人民币，2 0 0 2 年为4 5 亿人民币，2 0 0 3 年为5 4 亿元人民币，平均每年以2 0 左右的速度增长。 目前，中国的数据库市场虽大，但主要被国外主流数据库厂商如微软公司( s q l s e v e r ) 、s y b a s e 公司( s y b a s e ) 、( ) r a c l e 公司( o r a c l e ) 和i b m 公司( d b 2 ) 等 垄断，他们占据了9 6 4 以上的市场，而国外的软件价格昂贵，让我国政府和企 业不堪重负。早日改变d b m s 市场由国外软件占领的格局，保障国家信息安全， 研制具有自主版权的d b m s 一直是我国科研技术人员的梦想。 1 2 研究的意义与日的 操作系统、数据库等系统软件是信息系统的核心，是国家战略必争的高新技 术。实现信息化带动工业化需要自主产权d b m s ，提高我国企业创新能力和市场竞 争力需要自主产权d b m s ，国家信息安全离不开自己的d b m s ，我国民族i t 产业及 软件产业的发展更需要d b m s 的支撑，业界对这些观点已经逐步达成了共识。 数据库系统是绝大多数信息系统的核心，是企业信息系统必不可少的组成部 分，具有巨大的现实与潜在市场空问。中国加入w t o 的客观现实，对于政府和企 业加大信息系统建设投入、提高效率和竞争力提出了更高、更紧迫的要求，也使 圈家对于进一步规范软件市场的工作更加重视，这些都为包括数据库市场在内的 国内软件市场的发展带来了实实在在的需求和前景广阔的增长，对于国产软件业 无疑更是难得的发展机遇。 市场竞争的根本法则是以较低的价格提供适合用户需要的产品和服务。发展 浙江大学硕上学位论文 第一章绪论 自主知识产权的数据库软件，不仅可以从数据库市场上获得直接的回报，而且可 以对国外的产品形成竞争，降低国外产品的价格，每年将为国家、企业节约巨额 资金，这必将进一步推动数据库及其套件的广泛应用。 从超越经济意义的更深层次上来讲，随着计算机信息系统的发展和普及， 一个企业、行业乃至国家不仅在运转效率上，更在信息安全上越来越依赖于系统 软件的安全性。政务、商务机密的泄露可能造成严重的混乱或导致巨大的经济损 失。在军事上，利用信息技术攻击和破坏指挥系统已经取代常规武器的打击，成 为摧毁敌方战斗力的最有效方式。 我国自主研发的数据库已有金仓( 中国人民大学) 、o p e n b a s e ( 东大阿尔派) 、 d m 2 ( 华中理工大学) ，神舟o s c a r 等，但这些产品在功能和性能同国外成熟的 产品相比都还有不小差距。国家8 6 3 计划对困产数据库软件产品的研究开发给予 了特别支持，设立了国家8 6 3 计划“数据库管理系统及其应用”重大专项，极大 推动了国产数据库软件的成长。本文作者有幸参与这个项目，开发拥有自主知识 产权的大型通用国产数据库管理系统o s c a r ，本文就是关于国产数据库系统开发 过程中的一些技术问题和解决方案。本文论述主要集中在查询优化的设计实现， 查询优化是整个系统的重要组成部分。本课题就是对查询优化的各个部分的分析 研究和实现的论述。 1 3 论文的组织 本文主要介绍了园产数据库管理系统o s c a r 中查询优化器的设计和实现， 包括查询优化器的体系结构，查询优化的一般准则，查询优化器的关键技术，查 询优化器的重要算法和查询计划缓冲机制等。 本文的后续章节，将做以下安排： 第二章对o s c a r 体系结构做了概述，介绍了整个数据库管理系统的物理结构 和逻辑结构，d b m s 的内部核心模块和各个模块之间的联系，并介绍了查询优化 的定义、功能以及与其他模块的关系； 第三章介绍了o s c a r 中查询优化的关键技术，包括查询优化器的一般准则， 视图重写，查询优化预处理，量词优化，逻辑优化，连接树的构建子查询提丹 技术以及普通情况下的规划算法( 非基因算法) 和基因优化算法。 第四章讲述了查询优化的重要算法。包括系统采用的代价估算算法模型，存 取方法和存取路径的选择和各种具体的代价估算方法。 第五章讲述了查询计划缓冲机制，分析了查询计划缓冲机制的功能和体系 结构和关键算法和技术。 浙江大学硕士学位论文 第一章绪论 第六章对全文的研究作了总结，从文章的内容到系统的实现，总结出本文的 主要贡献和不足，并对接下来的研究方向作了展望。 浙江大学硕士学位论文第二章相关背景披技术简介 第二章相关背景及技术简介 2 1 数据库管理系统的历史 数据库技术的发展，已经成为先进信息技术的重要组成部分，是现代计算机 信息系统和计算机应用系统的基础和核心。数据库技术最初产生于2 0 世纪6 0 年代中期，根据数据模型的发展，可以划分为三个阶段：第一代的网状、层次数 据库系统；第二代的关系数据库系统；第三代的以面向对象模型为主要特征的数 据库系统。 第一代数据库的代表是1 9 6 9 年i b m 公司研制的层次模型的数据库管理系统 i m s 和7 0 年代美国数据库系统语言协商c o d a s y l 下属数据库任务组d b t g 提议的 网状模型。层次数据库的数据模型是有根的定向有序树，网状模型对应的是有向 图。这两种数据库奠定了现代数据库发展的基础。这两种数据库具有如下共同点： i 支持三级模式( 外模式、模式、内模式) 。保证数据库系统具有数据与程序的 物理独立性和一定的逻辑独立性；2 用存取路径来表示数据之间的联系；3 有独 立的数据定义语言；4 导航式的数据操纵语言。 第二代数据库的主要特征是支持关系数据模型( 数据结构、关系操作、数据 完整性) 。关系模型具有以下特点：1 关系模型的概念单一，实体和实体之间的 联系用关系来表示；2 以关系数学为基础；3 数据的物理存储和存取路径对用户 不透明；4 关系数据库语言是非过程化的。 第三代数据库产生于8 0 年代，随着科学技术的不断进步，各个行业领域对 数据库技术提出了更多的需求，关系型数据库已经不能完全满足需求，于是产生 了第三代数据库。主要有以下特征：1 支持数据管理、对象管理和知识管理：2 保持和继承了第二代数据库系统的技术；3 对其它系统开放，支持数据库语言标 准，支持标准网络协议，有良好的可移植性、可连接性、可扩展性和互操作性等。 第三代数据库支持多种数据模型( 比如关系模型和面向对象的模型) ，并和诸多 新技术相结合( 比如分布处理技术、并行计算技术、人工智能技术、多媒体技术、 模糊技术) ，广泛应用于多个领域( 商业管理、g i s 、计划统计等) ，由此也衍 生出多种新的数据库技术。 分布式数据库允许用户开发的应用程序把多个物理分开的、通过网络互联的 数据库当作一个完整的数据库看待。并行数据库通过c l u s t e r 技术把一个大的 事务分散到c u s t e r 中的多个节点去执行，提高了数据库的吞吐和容错性。多媒 体数据库提供了一系列用来存储图像、音频和视频对象类型，更好地对多媒体数 浙江火学硕士学位论文 第二章相关背景及技术简介 据进行存储、管理、查询。模糊数据库是存储、组织、管理和操纵模糊数据库的 数据库，可以用于模糊知识处理。 随着科学技术的发展，计算机技术不断应用到各行各业，数据存储不断膨 胀的需要，对未来的数据库技术将会有更高的要求。 2 2 国产数据库管理系统o s c a r 简介 神舟o s c a r 数据库，是拥有完全自主知识产权的企业级大型、通用对象关 系型数据库管理系统。它是在科技部重大软件专项“大型通用数据库管理系统及 其应用”和中国航天科技集团的大力支持f 研制成功的，也是目前科技部经费支 持力度最大的国产数据库产品。其目标是以市场需求为驱动，研制一个在功能、 性能、实用性、稳定性、安全性以及可扩展性等方面能够满足电子政务、企业信 息化、电子商务以及国防工业等敏感部门信息化建设需求的大型通用数据库产品 并在这些领域中逐步替换国外数据库系统。神舟o s c a r 数据库系统性能稳定、 功能完善，可广泛应用于各类企事业单位、政府机关，尤其是国防、航天、航空 等事关国家政治、军事、经济安全的各要害单位的信息化建设。神舟o s c a r 数 据库管理系统的成功研制和应用，一方面将可能彻底解决由于广泛应用国外数据 库产品可能带来的信息安全问题，另一方面也将在系统软件领域极大地推动我国 民族软件产业的发展。 2 3 国产数据库管理系统o s c a r 功能 神舟o s c a r 数据库系统基于c l i e n l j s e r v e r 架构实现，服务器具有通常数据 库管理系统的一切常见功能，此外还包括一些有助于提高系统对工程数据支持的 特别功能，而客户端则在提供了各种通用的应用开发接口的基础上，还具有丰富 的连接、操作和配置服务器端的能力。 其中，服务器端的主要功能包括： 1 )支持所有的常见数据类型，并可灵活地增加新类型及其对应的操作函 数： 2 )系统提供大对象支持，对于大对象的操作更为高效，并可支持大小达 4 g 以上的大对象； 3 )s q l 9 2 入门级标准符合度达到1 0 0 ，并部分支持s q l9 9 标准： 4 1支持t b 级的海量数据管理； 5 )支持大规模并发处理的进程结构： 6 )高效的查询处理方法和查询优化策略； 浙江大学硕士学位论文 第一二章相关背景及技术简介 7 1高性能的事务并发处理机制，支持多种事务隔离级别和多粒度的锁机 帝0 ： 8 、完备的数据恢复机制； 9 1多层次的数据库安全机制。 在客户端，系统提供以下主要功能： 1 )嵌入式s q l 支持； 2 1o d b c 支持： 3 1j d b c 支持； 4 1可编程存储过程和触发器支持： 5 1提供系统安装和卸载、d b a 工具、交互式s q l 、性能监测与调整以及 作业自动调度等丰富的管理工具； 6 )提供与o r a c l e 、s o ls e r v e r 、d b2 等主要大型商用数据库管理系统以 及t x t 、0 d b c 等标准格式之问的数据迁移工具。 2 4 国产数据库管理系统o s c a r 体系结构 o s c a r 数据库的体系结构可分为四个方面：逻辑结构、物理结构、内存结 构及进程。 2 4 1 逻辑结构 o s c a r 数据库的逻辑结构描述了数据库从逻辑上如何来存储数据库中的数 据。逻辑结构包括段、页、数据块和模式对象。数据库的逻辑结构将支配一个数 据库如何使用系统的物理空间。模式对象及其相互之间的联系则描述了关系数据 库之问的设计。 每一个表是由段( s e g m e n t ) 组成，一个段是由一组页( p a g e ) 所组成，一个页是 由一组连续的数据块( d a t a b a s eb l o c k ) 组成，对应硬盘上的个或多个物理块。一 个数据库存放在一个或多个数据库的物理文件( 即数据文件) 。一个数据库中的 数据被逻辑地存储在物理文件上。 数掘文件( d a t a f i l e ) o s c a r 数据库被划分为一个或多个数据文件中，它包括两类数据文件，系 统文件和非系统文件，其中，系统文件是建立数据库时自动建立的，它包含数据 库的全部数据字典，存储过程、包、函数和触发器的定义。除此之外，还能包含 用户数据。一个数据文件包含许多段，每个段有一些可以不连续的页组成，每个 页由一组连续的数据块组成。数据文件可以自动增长。数据库至少有一个数据文 件存储数据字典信息。 页( p a g e ) 6 浙江大学硕士学位论文 第= 幸相关背景及技术简介 页是由一组连续的数据块所组成的数据库存储空间分配的逻辑单位。对应磁 盘上一个或多个物理块，现在固定大小为8 k 。p c t f r e e 和p e r u s e d 两个参数用来优 化数据块空问的使用。 段( s e g m e n t ) 段( s e g m e n t ) 包含数据库中一种指定类型的逻辑存储结构，是由一组页 组成。在o s c a r 数据库中有几种类型的段：数据段、索引段和l 临时段。 数据段：对于每一个非聚集的表有一数据段，表的所有数据存放在该段。每 聚集有一个数据段，聚集中每一个表的数据存储在该段中。 索引段：每一个索引有一索引段，存储索引数据。 临时段：当一个s q l 语句需要临时工作区时，由o s c a r 建立。当语句执 行完毕，临时段的空间退回给系统。 o s c a r 对所有段的空间分配，以页为单位。 模式和模式对象( s c h e m ao b j e c t ) 一个模式( s c h e m a ) 为模式对象( s c h e m ao b j e c t ) 的一个集合，每个数据库用户 可以建立一个或多个模式，数据字典在c a t a l o g 模式中，默认还建立p u b l i c 模式。 模式对象为直接引用数据库数据的逻辑结构，模式对象包含如表、视图、索引、 聚集、序列、过程等结构。个模式对象存储在数据库的一个或多个数据文件中。 表 表( t a b l e ) 为数据库中数据存储的基本单位，其数据按行、列存储。每个表 具有一表名和列的集合。每。列有一个列名、数据类型、宽度或精度、比例。一 行是对应单个记录的列信息的集合。 视图 个视图( v i e w ) 是由一个或多个表( 或其他视图) 中的数据的一种定制的 表示，是用一个查询定义，所以可认为是一个存储的查询( s t o r e dq u e r y ) 或是一 个虚表( v i r t u a lt a b l e ) 。视图可在使用表的许多地方使用。由于视图是由表导出的， 视图和表存在许多类似。视图可以被查询，而在修改、插入或删除时具有一定的 限制，在视图上执行的全部操作真正地影响视图的基本表中的数据，受到基本表 的完整性约束和触发器的限制。 视图与表不同，一个视图不分配任何存储空问，视图不真正地包含数据。由 查询定义的视图相应于视图引用表中的数据。视图只在数据字典中存储其定义。 聚集 聚集( c l u s t e r ) 是存储表数据的可选择的方法。一个聚集是一组表，将具有 同公共列值的行存储在一起，并且它们经常一起使用。这些公共列构成聚集码。 例如：e m p 表各d e p t 表共享d e p t n o 列，所以e m p 表和d e p t 表可聚集在 浙江大学顿七学位论文 第二章相关背景及技术简介 一起，聚集码的列为d e p t n o 列，该聚集将每个部门的全部职工行各该部门的 行物理地存储在同一数据块中。 索引 索引( i n d e x ) 是与表和聚集相关的一种选择结构。索引是为提高数据检索的性 能而建立，利用它可快速地确定指定的信息。索引为表数据提供快速存取路径。 索引适用于一范围的行查啕或指定行的查询。 索引可建立在一表的一列或多列上，一旦建立，由系统自动维护和使用，对 用户是完全透明的。索引是逻辑地和物理地独立于数据，它们的建立或删除对表 没有影响，应用可继续处理。索引数据的检索性能几乎保持常数，而当一表上存 在许多索引时，修改、删除和插入操作的性能会下降。 索引有唯一索引各非唯一索引。唯一索引保证表中没有两行在定义索引的列 上具有重复值。系统在唯一码上自动地定义唯一索引实施u n i q u e 完整性约束。 组合索引是在表的多个列上所建立的一索引。组全索引可加快s e l e c t 语 句的检索速度，在其w h e r e 子旬中可引用组合索引的全部或主要部分。所以在 定义中给出列的次序，将经常存取的或选择最多的列放在首位。 序列 序列( s e q u e n c e ) 产生序列号。在多用户环境下该序列生成器特别有用，可生 成各返回序列号而不需要磁盘i o 或事务封锁。序列号生成是独立于表，所以同 一序列生成器可用于个和多个表。所生成序列号可用于生成唯一的主码。 程序单元( p r o g r a mu n i t ) 是指存储过程、函数。个过程和函数，是由s q l 语句或者其他高级语言语句组合在一起，为执行某个任务的一个可执行单位。 一个过程或函数可被建立，在数据库中存储其编译形式，可由用户或数据库应用 所执行。过程和函数差别在函数总返回单个值给调用者，而过程没有值返回给调 用者。0 s c a r 支持高级语言( 如c 语言) 写的过程和函数。 2 4 1 物理结构 物理数据库结构是由构成数据库的系统文件所决定，o s c a r 数据库文件包 括： 数据文件( d a t af i l e ) 数据文件用来存储数据库中的全部数据，例如数据库表中的数据和索引数 据。一个数据文件仅与一个数据库联系。数据库由一个或多个数据文件组成。数 据文件中的数据在需要时可以读取并存储在o s c a r 内存储区中。例如：用户要 存取数据库一表的某些数据，如果请求信息不在数据库的内存存储区内，则从相 应的数据文件中读取并存储在内存。当修改和插入新数据时，不必立刻写入数据 浙江大学硕士学位论文 第二章相关背景及技术简介 文件。为了减少磁盘输出的总数，提高性能，数据存储在内存，然后由后台进程 决定如何将其写入到相应的数据文件。 日志文件( r e d ol o gf i l e ) 每一个数据库有两个或多个日志文件组( r e d ol o gf i l eg r o u p ) ，每一个日志 文件组有一个或多个同志文件组成，日志文件用于收集数据库日志。日志的主要 功能是记录对数据所作的修改，所以对数据库作的全部修改是记录在日志中。在 出现故障时，如果不能将修改数据永久地写入数据文件，则可利用日志得到该修 改，所以从不会丢失已有操作成果。日志文件主要是保护数据库以防止故障。为 了防止日志文件本身的故障，o s c a r 允许一个日志组里面可以有多个订志文件， 以致可在不同磁盘上维护两个或多个日志副本。日志文件中的信息仅在系统故障 或介质故障恢复数据库时使用，这些故障阻止将数据库数据写入到数据库的数据 文件。然而任何丢失的数据在下一次数据库打开时，o s c a r 自动地应用日志文 件中的信息来恢复数据库数据文件。 控制文件( c o n t r o lf i l e ) 每一o s c a r 数据库有一个控制文件( c o n t r o lf i l e ) ，它记录数据库的物理结 构，包含下列信息类型： 数据库名； 数据库数据文件和f ：= 1 志文件的名字和位置： 数据库建立日期。 为了安全起见，控制文件可被镜像。每一次o s c a r 数据库的实例启动时， 它的控制文件用于标识数据库和目志文件，当开始数据库操作时它们必须被打 开。当数据库的物理组成更改时，o s c a r 自动更改该数据库的控制文件。数据 恢复时，也要使用控制文件。 配置文件 配置文件记录o s c a r 数据库运行时的一些重要参数，如：内存结构的配置 等。 2 4 3o s c a r 系统进程与内存结构 当在服务器上启动o s c a r 数据库后，服务器上启动了一个o o s c a r 实例 ( i n s t a n c e ) 。o s c a r 实例是存取和控制数据库的软件机制，它包含内存结构和 线程两部分。系统为实例分配一组共享内存缓冲区，用于存放数据库实例和控制 信息，以实现对数据库中数据的管理和操作。 线程是操作系统中一个极为重要的概念。一个线程执行一组操作，完成一个 特定的任务。对o o s c a r 数据库管理系统来说，线程由用户线程、服务器线程 和后台线程所组成。 浙江大学硕士学位论文第一章相咒背景及技术简介 当用户运行一个应用程序时，系统就为它建立一个用户线程。服务器线程处 理与之相连的用户线程的请求，它与用户线程相通讯，为相连的用户进程请求服 务。 为了提高系统性能，更好地实现多用户功能，o s c a r 还在系统后台启动一 些后台线程，用于数据库数据操作。 内存结构 启动一个实例，系统为实例分配一组共享内存缓冲区，它包含该实例的数据 和控制信息。共享内存根据存放信息的不同，可以分为如下几个区域： 1 数据缓冲区：存放数据库中数据库块的拷贝。它是由一组缓冲块所组成， 这些缓冲块为所有与该实例相链接的用户进程所共享。缓冲块的数目由初始化参 数d b b i ，0 c k b u f f e r s 确定，大的数据b u f f e r 可提高查询速度。 2 日志缓冲区r e d ol o gb u f f 。e r ：存放数据操作的更改信息。它们以f i = | 志 ( r e d oe n t r y ) 的形式存放在f i _ _ i 志缓冲区中。当需要进行数据库恢复时，日志项 用于重构或回滚对数据库所做的变更。同志缓冲区的大小由初始化参数 l o g b u f f e r 确定。大的日志缓冲区可减少日志文件i o 的次数。 3 数据字典c a c h e ：数据字典c a c h e 用于存放数据字典，它为所有用户进 程所共享。其他信息区：除了上述几个信息区外，还包括一些进程之间的通讯 信息( 如封锁信息) ，事务信息等。 2 5o s c a r 核心模块结构 图2 1 是o s c a r 核心各个模块的组成结构图。虚线上面f r o n t e n e 表示 客户端程序通过l i b o s c a r 模块和服务端连接通信，虚线以下即为整个后台数据库 服务器。 浙江大学硕士学位论文 第二章相关背景及技术简介 图2 - i o s c a r 体系结构 各个模块分别如下： l i b o s c a r ：客户端和服务器端的接口，网络传输 p a r s e r ：查询编译器，s q l 以及其他支持语句的语法解析 r e w r i t e ：语句重写模块 o p t i m i z e r ：查询优化模块 e x e c u t o r ：执行引擎 c o m m a n d s ：d d l 和d b a 处理模块 c a t a l o g ：数据字典模块 a c c e s sm e t h o d ：存取模块 h e a p ：物理表模块，实现记录物理存储 i n d e x ：包括r t r e e ，n b t r e e ，g i s t 不同的i n d e x 实现 t r a n s a m ：事务实现 l o g ：f 志模块 b u f f e r ：缓冲区 浙江大学硕士学位论文 第二章相关背景及技术简介 l o c k ：锁模块 u f i l s ：公用和基础模块包括内存管理，数据类型实现等 2 5 1 数据定义语言命令处理模块 进行模式修改的d d l 命令( d a t a d e f i n i t i o nl a n g u a g e ，数据定义语言) 由 p a r s e r 处理程序进行分析，然后传给c o m m a n d s 模块执行。由c o m m a n d s 模块经 过索7 1 文件记录管理器，去改变数据字典，即数据库的模式信息。 2 5 2 主存缓冲区和缓冲区管理器 数据库中的数据通常驻留在第_ ：= 级存储器中。在当今的计算机系统中，“第 二级存储器”通常就是磁盘。然而，数据必须在主存储器中，j 能对数据进行有 用的操作。于是，dbms 中有个称作缓冲区管理器的成分，它负责将可利 用的主存空间分割成缓冲区。缓冲区是与页面同等大小的区域，磁盘块的内容可 以传送到缓冲区中。这样，所有需要从磁盘得到信息的dbms 成分都与缓冲区 和缓冲区管理器打交道，或直接地，或通过执行引擎。dbms 需要的信息的类 型包括： 1 ) 数据：数据库自身的内容。 2 1 索引：支持对数据进行高效存取的数据结构。 2 5 3 事务处理 正如前面所讲，通常将一个或多个数据库操作组成一组，称作事务。事务是 必须被作为一个原子、外观上孤立于其他事务执行的单位。而且，dbms 保证 持久性，即已完成事务所做的工作决不会丢失。事务管理器从应用系统接受事务 命令，从而得知什么时候事务开始，什么时候事务结束，以及应用系统的期望信 息。事务处理器执行下列任务： 1 ) 日志记录：为了保证持久性，对于数据库的每一个变化都在磁盘上登记 同志。日志管理器遵循几种策略中的某一种进行工作，这些策略保证，不管在什 么时候系统发生故障或“崩溃”，恢复管理器都能察看关于数据库变化的日志， 并将数据库恢复到某个一致的状态。丌始时，臼志管理器将f _ | 忐写到缓冲区中， 然后它与缓冲区管理器协调，保证在适当的时候将缓冲区写到磁盘中( 磁盘中的 数据不受系统崩溃的影响) 。 2 ) 并发控制：事务的执行从表面上看必须是孤立的。但是在大多数系统中， 实际上有许多事务在同时执行。因此，调度器( 并发控制管理器) 必须保证多个 事务的每个动作以一种适当的顺序执行，从而使得最终的结果与这些事务一个执 浙江大学硕士学位论文 第二一章相关背景及技术简介 行完了再执行下一个的实际结果相同。典型的调度器通过在数据库的某些部分上 维护若干个锁来进行它的工作。这些锁防止两个事务一种错误的相互作用方式存 取数据的相同部分。调度器禁止执行引擎访问数据库中被封锁的部分，从而对查 询和其他数据库操作的执行发生影响。 3 1 死锁解决：当事务之间通过凋度器所授予的锁进行资源竞争时，可能会 进入这样一种情况：没有任何一个事务能够进行下去，因为每一个事务都需要另 一个事务所持有的某个资源。事务管理器有责任进行干预，取消一个或多个事务， 从而使其他的事务能进行下去。 2 5 4 查询处理器 数据库管理系统组成中对于用户所观察到的数据库性能影响最大的是查询 处理器。在图2 3 中，查询处理器主要为两个部分： 1 ) 查询编译器，它将查询翻译成一种内部形式，称作查询计划。查询计划 是要在数据上执行的一系列操作。查询编译器包括三个主要部分： ( a ) 查询分析器，它由文本形式的查询出发，建立一个树结构。 ( b ) 查询预处理器，它对查询进行语义检查( 例如，检查查询中所提到的关 系是否都确实存在) ，并进行某些树结构转换，将分析树转换为表示最初的查询 计划的代数操作符树。 ( c ) 查询重写器，实现v i e w 功能，对查询计划重写。 ( d ) 查询优化器，它将最初的查询计划转换为对于实际数据的最有效的操作 序列。查询编译器利用元数据和关于数据的统计数据来确定哪一个操作序列可能 是最快的。例如，一个索引的存在可能会使得某个查询计划比另一个计划快许多。 2 ) 执行引擎，它负责执行选中的查询计划中的每一步。执行引擎与d b ms 中大多数的其他成分都有交互，或直接交互，或通过缓冲区。为了对数据进行操 作，它必须从数据库取得数据并放到缓冲区中。它需要和调度器进行交互，以避 免访问被加了锁的数据。它需要和日志管理器进行交互，以确保对于数据库的所 有修改都正确地记了日志。 图2 - 2 查询优化处理步骤 9 m 一 ，lj= 浙江大学硕士学位论文第二章相关背景及技术简介 2 5 5 d b a 命令 数据库里面还有一类特殊的命令：d b a 命令，管理全局的数据库功能：建 立数据库，启动数据库，建立物理文件，建立用户权限控制等。这类命令都需要 d b a 权限才能执行，一般都是在数据库正常使用前使用，需要做特殊处理。 2 5 6 数据字典 数据字典又称元数据，是数据库系统中最重要的部分之一，是一组只读的表， 提供了数据库的所有系统信息，包括： 数据库中所有的对象的定义( 表，视图，索引，序列，函数，方 法，触发器等) 列的默认值 约束信息 数据库用户信息 用户的权限 统计信息 其他的如数据库文件，建立时间等 数据字典用表和视图方式存储，跟其他数据库中的数据一样。所有数据字典 的表和视图存在c a t a l o g 模式( s c h e m a ) 中。数据字典不仅是数据库的核 心，并且也是应用程序用户和d b a ( d a t a b a s ea d m i n i s t r a t o r s ) 的重要信息来源。 用s q l 可以查询数据字典，数据字典是只读的，只能发查询语旬( s e l e c t ) 。 要修改数据字典只能通过d d l 或者d b a 命令。 数据字典有3 大主要作用： 1 d b m s 读取数据字典来获得用户，对象和存储的信息 2 保存d d l d b a 命令的结果 3 用户通过数据字典获得数据库所有的信息 2 6o s c a r 查询优化 2 6 1 功能简述 在o s c a r 中，从用户发出一条查询命令到得到查询结果要以经过语法分析、 查询重写、规划优化和执行四个大步骤。该模块即o s c a r 的规划器优化器，它 接收经过语法分析和查询重写输出的查询树，创建一个查询规划( q u e r y p l a n ) 。 这个查询规划也就是执行器( e x e c u t o r ) 的输入。本模块首先创建所有可以得出 相同结果的可能的路径( 例如，如果待扫描的关系上有一个索引，那么扫描的路 浙江大学顸十学位论文第二章相关背景及技术简介 径就有两个。+ 个可能是简单的顺序查找，而另一个可能就是使用索引) ，然后 再计算出每个路径执行的开销，选择一个执行代价最小的路径，生成执行规划， 把它送给执行器。 查询优化模块共五个子模块，u t i l 模块作为一个辅助工具模块，p l a n 模块 是一个总调模块，查询树的规划入口在这个模块中，它调用p r e p 模块进行预处 理，调用p a t h 模块生成各种路径，寻找最优路径等进行规划。g e q o 是在处理多 表联接时可选的一种优化方法。一般情况可以不选用。在上面我们提到各子模块 功能的一些简单描述，下一小节来详细看一些各模块的功能。 图2 - 3 优化器模块结构总图 2 6 2 模块功能说明 2 6 2 1p r e p 模块 l i 叫 为了简化优化过程并产生更有效的查询规划，在进行真正优化前，需要对查 询树进行一些预处理工作，这包括对条件表达式的预处理把条件表达式转换 成合取范式( c n f ) 或析取范式( d n f ) 、去掉n o t 、尽可能把n o l l 下推等；对目 标列的预处理补全目标列、在u p d a t e 和d e l e t e 情况下增加c t i d 列、确保 查询树中目标列的顺序与表定义中的顺序一样等；对集合操作( u n i o n 、 i n t e r s e c t 、e x c e p t ) 的处理。下面举例说明这些处理过程。 预处理条件表达式 通常情况下，o s c a r 是把条件表达式转换成c n f 的。这意味着需要运用下面 的规则把所有的“o r ”语句放到条件表达式的最内层：ao f ( ba n dc ) = ( ao r b ) a n d ( ao rc ) 。这样优化器就可以合取范式中的每一个因子进行单独处理， 层层过滤查询结果。“尽可能地去掉n o t ”规则，需要把一个操作符变成它的否 定形式，如w h e r en o t ( a = 2 ) 可以转换成w h e r ea 2 ，这样做司以简化处理， 在某些情况下还能提高执行效率。如s e l e c tx x xf r o mxw h e r en o t ( i d 2 ) ， 浙江人学硕士学位论文 第= 章相关背景及技术简介 如果在属性i d 上定义了一个b + 树索引，由于b + 树操作只能用= 、 、 = 、 2 ) 。要实现此类转换，操作 符需要替换成它们相应的转向器( c o m l b u t a t o r ) ，如 和 = 与 r a 的表达式就可以转换成r a 2 的形式。 预处理目标列( 查询树的t a r g e t li s t ) 补全目标列主要是在i n s e r t 和u p d a t e 的情况。在i n s e r t 时，用户可能只 输入部分列的值，其它列的值根据表定义需要系统自动生成默认值( d e f a u l t ) 或空值( n u l l ) 。 排序检查主要用于当用户要i n s e r t 或u p d a t e 时，如果输入的属性列的顺序 与表定义中属性列的顺序不一样时，系统给出错误信息。 增加c t i d 属性列，主要是在d e l ，e t e 和u p d a t e 情况f ，对于要删除的元组， 系统会自动增加一下c t i d 来标识，执行器将根据该标识找到要删除或更新的元 组。 处理集合操作( u n i o n 、i n t e r s e c t 、e x c e p t ) 主要是对个包含集合操作符的查询进行规划。 2 6 2 2p a t h 模块 在计划优化的过程中，o s c a r 建立路径树( p a t ht r e e s ) 来表示执行查询的 不同方式。然后选择一条代价最小的路径，生成一条查询计划送给执行器( 通常 路径树和规划树是一一对应的，但是在p a t ht r e e s 中忽略了规划过程不需要的 信息，包含了规划过程需要但执行器不需要的信息) 。 优化器为查询中的每一个基表( b a s er e l a t i o n ) 创建了一个r e l o p t i n f o 结构。基表或者是原始的表，或者通过递归调用p l a n n e r 生成的子查询的结果 ( s u b q u e r y s u b s e l e c t st h a ta r e p l a n n e d v i aa s e p a r a t e r e c u r s i v e i n v o c a t i o no ft h ep l a n n e r ) 。在规划过程中的每一一个j o i nr e l a t i o n 也都有一 个r e l o p t i n f o 结构。一个联接表( j o i