（计算机应用技术专业论文）mysql物理结构的自动优化.pdf

摘要 摘要 数据库物理结构( 索引，物化视图，裂片等) 的改变虽然不影响查询结果，但会影响数 据库性能。数据库的物理结构、查询优化引擎和执行引擎构成了影响数据库性能的三大要素。 第一代关系数据库系统主要用于联机事务处理，数据规模还不太大，其优化执行引擎相 对简单，物理结构设计的重要性还不凸显。现代数据库系统已广泛应用于决策支持等领域， 由于数据量大，查询语句复杂，查询优化引擎和执行引擎变得越来越复杂，物理结构也从单 一的索引扩展到索引、物化视图和裂片，数据库管理员( d b a ) 已经不能再依赖简单的优化 执行引擎模型，因此数据库系统的物理结构设计变得尤为重要。数据库查询优化引擎的复杂 性使d b a 不再能准确地预测数据库执行查询使用的存取路径。物理结构的选择是一个 n p h a r d 问题【l 心，所以也不能可能通过穷举的方法来选择。 数据库物理结构的选择日渐成为数据库领域的一个研究热点。现在主流商业数据库 ( m i c r o s o f is q ls e r v e r ，o r a c l e ，d b 2 ) 已经附带了数据库物理结构优化的实用工具。而最 流行的开源数据库m y s q l 却只能依赖低级的e x p l a i n 语句进行数据库性能调整，因此本文 将对m y s q l 进行研究，并重构m y s q l 使其支持数据库物理结构的自动优化功能。 本文在分析数据库物理结构自动优化的研究背景和最新研究成果的基础上，以m y s q l 6 0 0a l p h a 版为标准，介绍m y s q l 服务器的架构、查询解析模块和查询优化模块，进一步实 现数据库物理结构的自动优化工具。主要工作包括修改查询优化引擎使其支持“w h a t - i f 【剐 接口；添加虚拟索引生成模块进行受限的物理结构枚举并通过“肌a t - i f 接口将虚拟索引添 加到数据库服务器中，使查询优化引擎可以使用虚拟的物理结构；添加统计信息生成模块使 查询优化引擎可以比较准确地计算物理结构的性能；添加物理结构搜索模块为整个作业量搜 索合适的物理结构。还对添加的物理结构优化功能进行了性能测试。实验结果说明优化后 m y s q l 使用索引的频率有了明显的提高，全表扫描的频率和每个查询需要处理的信息量有了 明显的下降，数据库性能得到了显著的提升。 数据库自动优化是自主计算【4 】领域的重要组成部分，自主计算致力于研究自维护的软件 系统，减少软件系统的维护成本。数据库系统是现代软件系统的信息中枢，随着信息规模的 增大，数据库系统的性能对这些软件系统的有效性起着决定性的作用。本文解决了m y s q l 在自主计算领域的一个基本问题物理结构的自动优化，一定程度上降低了m y s q l 的维 护成本。 优化的过程需要d b a 的参与。进一步的工作包括添加系统监控模块，调整决策模块。系 统监控模块在线监控m y s q l 服务器状态，调整决策模块分析监控数据并决定是否需要调整 数据库。 关键词：m y s q l ，索引，物理结构，数据库优化，自动优化 东南大学硕士学位论文 a b s t r a c t p h y s i c a ld a t ai n d e p e n d e n c ei st h em o s ti m p o r tf o a t u r eo fr e l a t i o n a ld a t a b a s e 1 1 1 i sf e a t u r e a l l o w sp h y s i c a ls t r u c t u r e ss i l l c ha si n d e xt oc h a n g es e a m l e s s l yw i t h o u ta f f e c t i n gt h eo u t p u to ft h e q u e r y h o w e v e r , t h ec h a n g ed o e sa f f e c tt h ep e r f o r m a n c eo ft h ed a t a b a s e p h y s i c a ld a t a b a s ed e s i g n ， q u e r yo p t i m i z a t i o ne n g i n ea n dq u e r ye x e c u t i o ne n g i n em a k eu pt h em o s ti m p o r t a n tf a c t o r st h a t a f f e c tr e l a t i o n a ld a t a b a s ep e r f o r m a n c e e a r l yd a t a b a s es y s t e mm a i n l yt a r g e t sa to l t pw i m i t ss i m p l eo p t i m i z a t i o ne x e c u t i o ne n g i n e a n ds m a l ld a t av o l u m e st op r o c e s s w h i c hm a d ep h y s i c a ls t r u c t u r es e l e c t i o nl e s sap r o b l e m t h e i m p o r t a n c eo fp h y s i c a ld e s i g ni sa m p l i f i e da sq u e r yo p t i m i z e rb e c o m e sm o r es o p h i s t i c a t e dt oc o p e 谢t l lm o r ec o m p l e xd e c i s i o ns u p p o r tq u e r i e so v e rl a r g ed a t av o l u m e s ，a n dp h y s i c a ls t r u c t u r ei s e x t e n d e dw i t l lm a t e d a l i z o dv i e wa n dp a r t i t i o n s i n c eq u e r yo p t i m i z a t i o na n de x e c u t i o ne n g i n e b e c o m e sf a rm o r ea d v a n c e d ，a n dp h y s i c a ls t r u c t u r ei se x t e n d e d ，d b a sc o u l dn ol o n g e rr e l yo na s i m p l em o d e lo fo p t i m i z a t i o na n de x e c u t i o ne n g i n e t h u st h ec h o i c eo fp r o p e rp h y s i c a ls t r u c t u r e b e c o m e sc r u c i a lf o re 伍c i e n tq u e r ye x e c u t i o no v e rl a r g ed a t a b a s e a n dc o m m e r c i a ld a t a b a s es y s t e m s ， s u c ha sm ss q l s e r v e r , o r a c l ea n dd b 2 ，h a v ep r o v i d e dt h ep h y s i c a ld e s i g nt o o l s 眦sp a p e r s t u d i e sm y s q l ，w h i c hh a sn o ts u p p o r t e da u t o m a t i o no fp h y s i c a ld e s i g ny e t ，t om a k ei ts u p p o r t a u t o m a t i cp h y s i c a ls t r u c t u r es e l e c t i o n o nt h eb a s i so fa n a l y z i n gr e c e n tw o r ka n da c h i e v e m e n t si no p t i m i z i n gp h y s i c a ls t r u c t u r eo f d a t a b a s ea u t o m a t i c a l l y , t h i sp a p e rs t u d i e st h es t r u c t u r eo fm y s q li nb o t hl a r g ea n ds m a l ls c o p e , t o p r o v i d e st h ei n f o r m a t i o nn e e d e dt or e f a c tm y s q la n dr e f a c t sr e l a t e dm o d u l e si nm y s q l t oa d dt h e f u n c t i o no fp h y s i c a ld a t a b a s ed e s i g na u t o m a t i o n , i n c l u d i n gm a k i n gq u e r yo p t i m i z e rt os u p p o r t 珊a t - i fi n t e r f a c e a d d i n gam o d u l et oe n u m e r a t ev i r t u a lp h y s i c a ls t r u c t u r e s ，a d d i n gam o d u l et o g e n e r a t es t a t i s t i c sf o rv i r t u a lp h y s i c a ls t r u c t u r e sa n da d d i n gam o d u l et os e a r c hp h y s i c a ls t r u c t u r e s f o rt h ee n t i r ew o r k l o a d ac o m p r e h e n s i v ee x p e r i m e n ti sc o n d u c t e dt oe v a l u a t et h en e w l ya d d e d f u n c t i o n t h ee x p e r i m e n ts h o w sm a ta f t e ro p t i m i z a t i o nm y s o lt a k e sm o r ea d v a n t a g eo fi n d e x e st o e x e c u t eq u e r i e sa n dm a k e sl e s sf u l lt a b l es c a n s a sar e s u l tt h ep e r f o r m a n c eo fm y s q l i m p r o v e sb y 6 0 o p t i m i z i n gd a t a b a s es y s t e ma u t o m a t i c a l l yi sac r u c i a lp a r to fa u t o n o m i cc o m p u t i n g 引，w h i c h t a r g e t sa tb u i l d i n gs e l f - s u s t a i n i n gs o f t w a r es y s t e mt ol o w e rd o w nm a i n t e n a n c ec o s t w i t ht h e e x p l o s i o no fd a t av o l u m e s ，d a t a b a s es y s t e m ，w h i c hi st h ei n f o r m a t i o nc e n t e ro fm a n ym o d e m s o f t w a r es y s t e m s ，b e c o m e sac r u c i a lp a r tf o rs y s t e mp e r f o r m a n c e 1 h i sp a p e rp r o v i d e sas o l u t i o nt o p h y s i c a ld a t a b a s ed e s i g na u t o m a t i o ni nm y s q l ，a n dl o w e r st h em a i n t e n a n c ec o s to f m y s q l t h es o l u t i o nn e e d st h ep a r t i c i p a t i o no fd b a s f u t u r ew o r kw o u l di n c l u d ei m p l e m e n t i n gs o m e o t h e rm o d u l e s ，s u c ha sam o n i t o r i n gm o d u l e ，a na n a l y s i sm o d u l ea n ds o m eo t h e rt u n i n gm o d u l e s n em o n i t o r i n gm o d u l ei sr e s p o n s i b l ef o rm o n i t o r i n gt h ed a t a b a s es y s t e m r n l ea n a l y s i sm o d u l e t a k e st h em o n i t o r e dd a t aa si n p u ta n dd e t e r m i n e sw h e t h e rt ot u l l et h ed a t a b a s ea n dw h i c ha s p e c tt o t u n e k e y w o r d s ：m y s o l ，in d e x ，p h y s ic ais t r u c t u r e ，d a t a b a s eo p timiz a tio n p h y sic aid e sig n a u t o m a t i o n 东南大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过 的研究成果，也不包含为获得东南大学或其它教育机构的学位或证书而使用过的材料。与我 一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名：鲡e t 期：名垃芝罕墨 、2l 东南大学学位论文使用授权声明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印 件和电予文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质 论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括 以龟子信息形式刊登) 论文的全部内容或中、英文摘要等部分内容。论文的公布( 包括以电 子信息形式刊登) 授权东南大学研究生院办理。 研究生签名：二师签名研究生签名：鳖么趁贷师签名 第章绪论 第一章绪论 1 1 数据量的增长与数据库性能优化 数据量的增长是数据库性能优化研究的驱动力。小规模数据库一般不存在性能问题，数 据量较小的应用系统也不能从优化上得到实质性的性能提升，然而随着数据量的增长，物理 结构所提供的快速访问路径会变得很重要。 许多因素导致了数据量的飞速增长：网络及个人电脑的普及，个人通信设备的普及，商 业数据的增长等等。企业级应用系统的数据量已达到t b 数量级，应用于生物医学工程的人 类基因数据库需要在p b 量级的数据上进行计算分析。 伯克利1 9 9 9 年的调查表明企业部门的磁盘数据每年以l o o 的速度增长1 5 j 。2 0 0 0 年左右， 随着磁盘成本的下降，磁盘存储开始比纸张存储更经济，这一点也促使了数据量的增长( 图 1 1 ) 。对数据安全的需求导致很多企业还要将各种数据进行备份，如测试数据、操作数据以 及灾难恢复数据等，因此数据膨胀的问题已经非常严峻。2 0 0 9 年e m c 全球副总裁兼大中华 区总裁发言表示未来中国的数据量将会有3 0 倍的增长。 诸多因素使数据量急剧增长，但是人们对于数据库的速度要求并没有降低。虽然c p u 计 算能力的发展依然遵循摩尔定律，但是磁盘访问速度增长却较缓慢。人们不再是简单地处理 数据而是通过数据获取信息，数据挖掘和其它形式的商业智能应用要求更强的数据处理能力。 某些情况下优化后数据库的处理能力能够提高几个数量级，因此性能优化变得日益重要。 性能优化有许多方法，如使用并行技术，升级硬件，调整数据库服务器配置，调整物理结构 等。其中调整物理结构是数据库优化领域中最常用的方法，本文研究物理结构的使用机制并 在此基础上实现物理结构调整的自动化技术。 f f 、 尹 、蓦 f 纸张胶片成本莅田 羧絮卜- 冈稃 l l 蠢专矬 ；1 9 昕年开始电磁设备存鼙成本2 警誉 幺5 砖瑷盘 每年下降r 巍氛o 5 寸埂耋 ! 墨硬盘 i i d r a m 冈存 一纸利胶片l 图1 1 存储成本( 来自m m ) 东南大学硕士学位论文 1 2 数据库性能优化原则 图1 2 系统调整循环 d b a 对数据库性能进行调整也遵循图1 2 表示的循环。首先d b a 观察数据库系统的响 应时间、磁盘利用率、c p u 利用率，并根据系统的当前性能和用户对系统的性能预期决定是 否需要进行性能调整，然后通过可用手段，如添加索引，更新数据库统计信息，更改数据库 系统设置等，进行性能调整。接着再观察系统性能，决定下一步需要进行的调整。数据库性 能调整一般要遵循以下几个原则： 解决磁盘f o 、c p u 和r a m 的高负载率，不一定需要添置额外的硬件资源。重要的 是首先寻找系统负载高的根源，尝试从软件方面解决问题。 查询语句的执行时间要和执行频率一起考虑，低频语句即使有较大的性能提升空间也 不应该比有较小性能提升空间的高频语句更值得引起关注。 系统中总有一些组件降低系统的性能，找到系统的瓶颈可以大幅提高系统性能。 任何性能调整手段都需要成本，添置硬件需要资金，创建额外数据库对象需要磁盘资 源和时间。进行性能调整之前需要考虑收益和成本之间的关系。 索引物化视图需要维护成本。因此需要删除对系统性能有负面影响的无用数据库对 象。 1 3 影响数据库性能的因素 数据库性能受许多因素的影响，本文着重考虑影响数据库性能的软件因素，如索引，物 化视图，数据库统计信息，数据库系统的配置等。 1 3 1 索引 通过主键查找数据记录的效率很高，因为数据表中无重复的主键。数据库系统根据主键 索引可以快速准确地定位记录在磁盘上的位置。然而有大量的查询涉及数据表中的非主属性， 通过在这些属性上建立索引可以提升数据库系统的性能。索引是属性地址对的有序集合。属 性对应数据表逻辑结构的列。地址是记录标识符( r i d ) ，指向属性值对应记录在磁盘上的位置。 建立合适的索引可以提升数据库的性能，但正如数据库性能调整原则所述，索引的使用 和维护需要成本。首先索引需要占据磁盘空间，其次在计算查询计划( e q p ) 和执行更新操作时 索引还要占用c p u 时间。因此数据库中并不是索引越多越好，d b a 的职责之一就是为数据 库建立合适的索引。 2 第一章绪论 1 3 2 数据库统计信息 在计算查询计划时，查询优化器需要数据的分布信息指导查询计划的生成。通过统计信 息，查询优化器能够估算参与查询的每张表中符合查询条件的记录条数，从而为数据表选择 合适的连接顺序和存取路径。连接顺序通常是按数据表中符合条件记录数的升序排列。 与索引不同的是，数据库系统不主动维护数据库统计信息。当数据表改变时，系统并不 修改统计信息，因此统计信息不会给系统带来额外开销。这同样也意味着当数据表中数据分 布发生重大变动时，统计信息就会过期，查询优化器就会做出错误的估算生成低效率的查询 计划。这时d b a 需要更新统计信息，反映数据的分布情况。 1 3 3 裂片 把数据表分成多块放在多个磁盘上可以利用并行读取技术减轻全表扫描中单个磁盘的负 载，从而解决系统磁盘i o 瓶颈问题。现代数据库系统有多种裂片方式，根据关键列裂片， 根据值域裂片，哈希裂片等。 关键列裂片技术需要在数据表中增加一个数据列用以说明数据存放在哪个磁盘，数据库 系统根据这个列值决定记录的存取磁盘。值域裂片根据某数据列的值域进行数据存取，如列 值在 v 0 ，v 1 ) 区间的记录存放在第一个磁盘，列值在 v l ，v 2 ) 区间的记录存放在第二磁盘， 以此类推。哈希裂片首先给磁盘编号，然后根据哈希函数把记录分配到对应的磁盘。同索引 一样，只有当查询中使用了裂片表的关键列时，裂片技术才可能提升系统性能，否则将进行 全表扫描，可以通过在裂片表上建立索引来避免这一点。 1 3 4 物化视图 视图可以使s q l 语句用单表查询代替复杂的连接查询，也可以通过给数据表的不同视角 分配不同的安全等级以增强系统的安全性。然而每次计算查询中涉及视图的成本很高，因此 现代数据库系统将视图的数据保存在磁盘上，以加快查询的执行。在磁盘上存有实际数据的 视图称之为物化视图。 物化视图可以加快查询的执行，然而正如优化原则所述，数据库系统需要为物化视图付 出存储成本和维护成本。当物化视图的基本表发生改变时，数据库系统就需要对数据库进行 维护。根据数据库系统的不同和系统设置的不同，物化视图可以在基本表改变时立即更新， 定时更新或者手动更新。 和索引一样，只有被使用时物化视图才能提高系统的性能。根据优化原则，应该删除无 用的物化视图。 1 3 5 存储结构 表的存储结构会对不同查询的性能产生不同的影响。 表的堆存储结构把新记录直接添加到尾部，这种结构对i n s e r t 查询响应极快，但是对 于s e l e c t 查询却需做全表扫描，而且在重新组织表结构之前不能利用已删除记录的磁盘空 间，因此在支持这种结构的数据库关系系统里仅对极小的表使用此结构。 表的散列存储结构把表根据关键列的值用散列函数放到不同的页，这种结构对等值查询 响应极快，对不能优化为等值查询的范围查询需要做全表扫描，当数据页溢出时需要建立溢 出页，这会影响等值查询的性能。 3 东南大学硕士学位论文 表的静态树存储结构把表按主键组织成静态树，这种结构在主键上的等值和范围查询效 率很高，但由于树结构是静态的，在叶节点溢出时需要像散列结构一样建立溢出页，导致查 询效率的降低。 b 一树结构是灵活性最高的物理结构，当插入或删除记录时此结构动态调整叶节点。由于 b 树结构在多数情况下的表现都比其他结构优异，动态调整所带来的额外开销可以忽略不计。 1 4 数据库性能指示器 在进行性能调整之前d b a 需要确认数据库是否存在性能问题，有一些指示器可以帮助 d b a 完成这一工作。本节将分析最常用的几个指示器。 1 4 1c p u 时间和磁盘i o 虽然c p u 时间和磁盘i o 是两个不同的指示器，但是它们之间的关系非常密切：当一个 指示器空闲时，系统很有可能是在等待另一个。m y s q l 的查询优化器根据c p u 时间和磁盘 i o 去计算查询耗费，在计算过程中优化器把磁盘i o 转换为c p u 时间。在生查询行计划的 过程中，查询优化引擎根据估算的c p u 时间，对不同查询计划的性能进行比较。 1 4 2 统计信息 统计信息对数据库的性能有很大的影响，它是数据库物理表状态的缩影。查询优化引擎 跟据统计信息估算参与查询的数据表中符合条件的记录数然后确定表的连接顺序。如果统计 信息过期，与真实的数据表之间有太大的出入，计算出的查询计划必然不能高效地运行。 1 4 3 索引等物理结构的使用率 如上文所述，合理的使用索引等物理结构可以极大的提高数据库系统的性能，滥用这些 物理结构则会极大的损害系统的性能。d b a 需要对系统的作业量有很深的了解才能够判断系 统的物理结构是否合理。通过查询计划d b a 可以了解到系统正在使用哪些物理结构，需要添 加哪些物理结构，有哪些不理结构从来不被使用需要删除。 1 5 人工调整数据库性能的困难性 数据库性能调整主要是根据s q l 语句选择合适的物理结构，这一过程充满了技术和成本 方面的各种困难，包括： 1 复杂的优化执行引擎。早期数据库产品的优化执行引擎相对简单，d b a 可以较准确地 预测优化执行引擎的动作。随着数据库应用领域的扩展，优化执行引擎变得非常复杂，d b a 不再可能有效地预测优化执行引擎的动作。虽然有许多教程【5 】【6 j 指导人们如何选择物理结构， 但是随着数据量的急速膨胀，这些方法也不再行之有效，因为d b a 在实体化一个物理结构之 前无法准确预知其对数据库性能的影响，而在大数据集上实体化物理结构又是十分消耗资源 的工作。另外有些应用系统会自己生成大量的表，并在表上执行自动生成的查询语句，d b a 对这一部分表的优化力不从心。 4 第一苹绪论 2 来自管理方面的抵制。数据库性能调整是十分消耗成本的过程，管理者不愿意在这方 面投资是很常见的现象。很多情况下，d b a 必须进行成本收益分析以证明在硬件资源方面的 节省能够抵消数据库性能调整所需要的成本。 最终随着d b a 确定并调整高频使用的s q l 语句，d b a 节省的i t 系统成本会越来越低 ( 图1 3 ) ，当i t 系统节省的成本和d b a 付出的成本相等时，就应该停止数据库性能的调整。 停调点根据不同d b a 的经验和能力不同会有所不同。本文所研究的数据库物理结构自动优化 技术目的就是帮助d b a 节省优化成本，使停调点尽量向左移。 1 6 数据库性能的自动优化 硇 舒出成本 图1 3 性能调整成本图 人工调整数据库性能是一项非常耗时的工作，需要长时间监视数据库性能。现在某些数 据库系统可以帮助d b a 完成一些性能调整的工作。计算自动化是计算机领域的热点，这个领 域致力于研究可以自维护，自优化，自恢复的系统。作为计算自动化的一个重要部分，数据 库性能自动调整遵循人工优化的工作流程( 图1 2 ) 。作为自动优化系统这个过程可分为以下步 骤： 1 监视系统，采集某个时间段上的性能数据。 2 分析系统的新能数据。 3 根据分析结果自动调整系统性能。 数据库优化领域有几种方案可以在不同层面上实现上述步骤。最理想的实现方案是自给 自足的自维护系统，系统运行过程中不需要人的干预。此方案把数据库内部结构完全隐藏， 系统完全在无人干预的情况下管理存储结构、物理结构、存取方案和系统配置，检测系统瓶 颈，分析解决方案，实施解决方案，这些动作都在系统正常运行时自动完成。实际运行中会 出现许多状况，这种解决方案必须能够对未知状况做出动态响应，否则只能应用在某些固定 的环境中。前者将导致系统的优化开销太大，后者将导致系统不能广泛应用。 较低层次的解决方案需要d b a 的日常介入。解决方案只是为d b a 提供了更高效的管理 优化工具，d b a 可以根据这些工具提供的信息决定如何实行优化调整。总体来说在这种方案 中，数据库系统是半自动化的，一方面系统自动运行日常维护任务，另一方面当遇到较大的 问题时系统会提醒d b a 介入，并向d b a 提供问题的细节和可能的解决方案。 更低层的解决方案只给d b a 提供了优化向导，优化建议器。d b a 手动使用这些工具分 析数据库。在这种系统中d b a 只能被动的等待问题发生，或者不停的使用这些工具分析数据 库来防止问题的出现。 自动化程度越低，系统的日常运行开销就越小。自动化程度高的系统具有显著的优势， 在出现问题时高自动化系统能够快速地响应并修正问题，甚至能够通过预测分析防止问题的 出现，低自动化系统却往往只能提供一份问题报告。 5 东南大学硕士学位论文 1 7 数据库物理结构的自动优化 m y s q l 的功能相对简单，和商业数据相比仍有很大的差距，如m y s q l 不支持物化视图 功能。本文以m y s q l 6 0 0 版为基础探讨数据库性能自动优化问题，专注于数据库物理结构 的自动优化。m y s q le n t e r p r i s em o n i t o r 管理工具可以有效的监视m y s q l 的状态，d b a 发现 性能问题后可以使用物理结构自动优化工具计算合理的物理结构部署到系统中。 开展数据库物理结构的自动优化研究首先需要理解数据库的查询处理过程，本节首先介 绍这一过程，然后论述数据库物理结构自动优化技术。 1 7 1 查询优化和查询计划的生成 查询处理的三个步骤如下： 1 扫描、解析s q l 语句。此步骤检查s q l 语法的正确性，输出结果是s q l 语法树。 2 查询优化。此步骤以第一步的s q l 语法树为输入，输出是查询查询计划，包括全局优 化和局部优化。全局优化决定连接，选择和投影的顺序，并在可能的情况下将嵌套查询转化 为一般查询，将外连接转化为内连接。局部优化决定每张表的访问路径，根据物理结构信息 和数据库统计信息决定使用全表扫描还是通过某个物理结构访问数据表。这两种优化都基于 查询优化引擎的耗费估算，查询优化引擎通过比较不同的查询计划找到耗费最小的作为最终 查询计划。优化引擎的耗费通过数据库的统计信息和参与查询的每张表的统计信息计算而得。 3 执行查询。这一步中，执行引擎根据最终的查询计划按部就班地进行查询。 1 7 2 数据库物理结构自动优化问题 数据库物理结构的自动优化问题讨论如何在某个存储空间的限制下找到一组物理结构使 某个作业量的估算执行时间最短。问题的输入是一组查询语句的集合( 作业量) 和存储空间 的限制。问题的输出是某些物理结构的集合，称之为最优配置。估算执行时间是查询优化引 擎根据物理结构和数据库统计信息计算出的查询执行时间。 符号约定： w ：作业量集合。 s ：存储空间的限制。 c ：数据库物理结构的集合。 s i z e o f ( y ) ：物理结构y 所需的存储空间。 c o s t ( x ，y ) ：存在某组物理结构y 时，作业量x 的估算执行时间。 数据库物理结构自动优化的问题可表示为： 对于某个w w 和s ，找出一组满足以下条件的物理结构e ： c cas i z e o f ( c ) = s e o s t ( w ，c ) = m i n ( e o s t ( w ，y ) iy c 八s i z e o f ( y ) ) 本文考虑的优化针对决策支持查询，只考虑对s p j g 查询语句的优化。 1 7 3 数据库物理结构自动优化的研究概况 早在1 9 7 4 年人们就开始研究数据库物理结构。早期的工作 7 1 使用参量化的作业量作为问 题输入，文献【8 】创建了一个预测模型用以参量化作业量。之后的研究【9 】【1 0 】【1 1 1 开始显式地使用 6 第一章绪论 作业量作为问题的输入。显式作业量可以通过数据库的审计跟踪功能收集。有些研究限制作 业量的种类为单表查询，这些限制或者对研究中使用的索引选取技术是必要的，或者研究只 能证明他们的解决方案只适用于特定种类的作业量。 所有的研究都认为通过实体化物理结构来评价其性能是不可行的。在如何计算物理结构 的性能上不同的研究分成了几派。有些研究通过创建外部耗费模型计算物理结构的性能。这 种方法的优点是对数据库服务器的性能影响较小，其致命的缺点是外部耗费模型和查询优化 器的可能不一致，而最终采用那些物理结构进行查询是由查询优化器所决定的。 从文献 9 】的研究开始，另一部分研究使用查询优化器的耗费模型，由查询优化器在生成 查询计划的过程中计算物理结构的性能。这种方法需要在没有索引的数据列上创建自己的统 计信息，同时还需要修改数据库元数据以便查询优化器能够计算虚拟物理结构的性能。这种 方法对数据库性能的影响较大，因此需要尽量减少对服务器的优化调用【9 】【1 0 】。有些研究通过 近似的方法来减少优化调用，但这又将导致计算结果和查询优化器不一致。 文献 1 2 】指出了选择最优索引结构的困难性，这与查询优化领域的困难性相似，并提出 了解决这个问题的关键在于如何找到一组合适的启发式规则指导物理结构设计的过程。于是 另一部分研究提出了基于规则的专家系统解决方案。这些解决方案同样需要考虑查询结构和 数据库统计信息，但是独立于数据库系统。d e cr d b e x p e r t 工具即属于这一类解决方案。文 献 1 0 】使用了一个和查询优化器类似的外部耗费模型，根据每个查询的特征，使用启发式规 则搜索物理结构，整个过程中不需要调用数据库服务器查询优化器。 早期的研究主要关注如何为作业量推荐最优的索引结构【1 3 1 。现代数据库系统中包含了许 多新的物理结构，这些结构也对系统的性能起了至关重要的作用。物化视图可以使数据库系 统对决策支持查询做出快速的响应。水平垂直裂片通过减少额外的存储耗费、减少更新查询 的耗费提高系统性能。新物理结构的引入急剧地增大了搜索空间，目前的搜索方法可以分为 两类，文献 1 4 】 1 5 使用自下而上的搜索方法，文献 1 6 贝l j 采用自上而下的搜索方法。自下而 上的方法从空结构( 或者已存在的结构) 开始，使用贪心算法逐渐添加物理结构。由于多数 最优物理结构仅包含少量的结构，这种方法适用于存储空间比较少的情况。自上两下的方法 则从全局最优结构开始，由于最优结构通常会超出存储空间的限制，这种方法然后再通过合 并结构减小结构的体积，直到满足对存储空间的要求。 前文讨论的物理结构优化方法都需要d b a 提供一个作业量，通过数据库系统提供的工具 计算物理结构，这也是当前主流数据库系统提供的方案。这种方案将d b a 从选择物理结构的 工作中解放了出来，但是d b a 仍需决定什么时候使用优化工具，提供给优化工具什么样的作 业量作为输入，运行优化工具，检查推荐的物理结构并将合适的物理结构部署到数据库系统 中。 动态在线调整( 图1 4 ) 的研究旨在进一步减轻d b a 的工作量，将d b a 从上文的工作 中解放出来。动态在线调整技术的目标是建立一个服务器端永久在线的物理结构优化方案， 最大限度的减少系统的人工干预f l7 】【1 s 】【1 9 1 。动态调整模块跟踪作业量并根据需要在线做出物理 结构调整的决策。实现动态在线调整有三个难点：首先调整系统永久在线，这要求调整系统 不能影响数据库系统的性能和功能；其次调整系统需要权衡物理结构之间变化的耗费和这种 变化能够带来的性能提升之间的关系；最后调整系统应该避免震荡效应，当震荡效应发生时， 某个结构会被反复地创建删除，这将严重影响数据库系统的性能。 7 东南大学硕士学位论文 1 查询优化引擎卜+ 蔓至刊执行引擎卜 ( 二三氧在线优化引擎卜 - ，l i k e 等查询条件。 i n d e x ：对索引迸行顺序扫描。 b e s ta c c e s sp a t h 0 在一个局部查询计划的基础上计算新的局部查询计划，决定下一张进行 连接的表和其存取路径。局部查询计划很大程度上决定了下一个连接表及其存取路径。比如 局部查询计划a 中包含可用于索引存取的数据列，则新加入的表即可通过索引存取；局部查 询计划b 不包含这样的数据列，新加入的表需要做全表扫描。 m y s q l 提供两种方法解决查询优化问题的第二部分：穷举搜索( s q l k s q ls e l e c t c c 中的 f i n d ) 和贪心搜索 中的 。穷举搜索检查表的所有可能连b e s t 0 ( s q l k s q l s e l e c te c g r e e d y s e a r c h ( ) ) 接顺序并从中找到最优查询计划，这种方法的缺点是耗时。贪心算法的工作过程如下： 1 ) 若查询中表的数量n s y m b o l ； s y m g r o u ps y m _ g r o u p _ e o m m o n = f i f ，”) ； # d e f i n es y m ( a ) s y m _ o r _ n u l l ( a ) ，0 ，& s y m _ g r o u p _ e o m m o n 1 7 东南大学硕士学位论文 s t a t i cs y m b o ls y m b o l s = - t & ，s y m ( a n d _ a n d _ s y m ) ， - ”，s y m ( l t ) ， ” - ，s y m ( l e ) ， ”竹，s y m ( n e ) ， ”! 一，m ( n e ) ) ， t - _ ， y m ( e q ) ) ， 从以上代码片段可知，s y m b o l s 口数组定义s q l 语句中的语法元素和符号类型之间的对应 关系，符号类型在s q l _ y a c c y y 中定义。当需要为m y s q l 添加新的关键字时修改s y m b o l s 数 组即可，当需要添加新的符号类型时还需修改s q l _ y a c c y y 文件。s q l _ y a c c y y 中定义了m y s q l 的语法分析器。文献 2 8 详细介绍了y a e e 工具g n ub i s o n 的使用方法。 3 2m y s q l 索引结构 本文所说的索引结构不是某种具体索引文件的存储结构，而是m y s q l 的抽象索引结构。 实际上在m y s q l 里，不同的存储引擎各自管理自己的索引文件，不同存储引擎的索引文件 物理结构有所不同，m y s q l 通过存储引擎a p i 对索引文件进行存取。通过抽象索引结构 m y s q l 可以了解索引的统计信息，从而指导查询优化引擎计算查询计划。 唧f i e l d + k e y _ s s a r t ：b i t 皿a p+ k e y _ p a r t s ：u n s i g n e di n t 刁r y ：_ p a g r 一1 n f o 广- f l i e l d + p a r t _ o f _ k e y ：b i t m a p + a l g o r i t h m ：h a _ k e y _ a l $ + n a m e ：c h a r *+ p a r to f _ k e y _ n o tc l s t e r e d ：b i t m p + t e c j l e r j ”：u n s l p e dl o n f f 1 1 ii 1+ p a r to f _ s o r t _ k e y ：b t t n m p + j 在m y s q l 中索引和k e y 是同义词，本文将沿用这一习惯。由图3 1 可知，m y s q l 有四 种索引b 树索引，r 树索引，哈希索引和全文索引。每个k e y 由一个或多个k e y 一p a r t 组 成，在m y s q l 中k e yp a r t 是有序组，这是由m y s q l 对多列索引的使用机制决定的。有 序组意味着不同的排列代表不同的索引。k e y 中记录k e yp a r t 的信息，如k e y _ _ p a r t s 字段 记录k e y 有多少k e yp a r t ，k e yp a r t 的详细信息则由k e y 数组记录。 中的字段用以说明和数据列的联系。_ p a r t k e y p a r ti n f of i e l dk e yp a r tf i e l d 类代表某个数 据表的数据列，记录了数据列的类型，所属的表和与其相关的索引信息。f i e l d 类用位图记录 可用索引信息，查询优化引擎可以利用位图的位操作加快索引计算速度。数据表的完整索引 信息记录在t a b l es h a r e 结构的k e y 数组中，和 类中的位图保持对应关系。例_ i n f o f i e l d 如对于下列数据表： p u b l i s h e r 删， n a m e ， c i t y ，c o u n t r y ，s t a t e ) 假设此表有四个索引：k e y i ( p u bi d ) ，k e y 2 ( n a m e ) ，k e y 3 ( c i t y ， s t a t e ， c o u n t r y ) ， k e y 4 ( e o u n t r y ，s t a t e ，c i t y ) 。t a b l es h a r e 的k e y 数组为 ， ，_ i n f o ( k e y i k e y 2k e y 3k e y 4 ) 则f i e l d 的信息如表3 1 所示： 1 8 第三章m y s o l 核心数据结构 表3 1f i e l d 类字段示例 列名表名 k e y _ s t a r tp a r to fk e y p u b _ i d p u b l i s h e r 0 0 0 1 b0 0 0 1 b n a m e p u b l i s h e r 0 0 1 0 1 30 0 1 0 b c i t yp u b l i s h e r 0 1 0 0 b1 1 0 0 b c o u n t r yp u