作者：李海翔
出版社：机械工业出版社
格式: AZW3, DOCX, EPUB, MOBI, PDF, TXT
数据库查询优化器的艺术：原理解析与SQL性能优化试读：
前言
为什么写这本书数据库引擎是一项包罗万象的技术大全，纷繁复杂，不能轻易穷尽。
数据库查询优化器是数据库引擎的重中之重。掌握了查询优化器，就等于掌握了数据库的精髓，得查询优化器者则得数据库天下。
在数据库查询优化技术领域，尚没有一本将理论与实践结合的书籍，能帮助查询优化技术的爱好者掌握其全貌、掌握其细节、掌握其精髓、掌握其奥妙。
如果能有一本书可以包括数据库查询优化技术的完整面貌，相信一定会使探索者少些崎岖摸索，这自然是一件好事。于是笔者心怀忐忑，虽自知力不能及，但还是决定奋笔一试，如工匠砌砖、蝼蚁啃土，一点一滴，将自己多年总结的经验汇集于此，终于小成。本书的主要内容
本书主要讨论以下问题：
❏ “查询优化”究竟包括什么样的优化技术？为什么能做那些优化？
❏ “查询优化器”是怎么实现的？“查询优化器”是怎么做优化工作的？
❏ PostgreSQL和MySQL的查询优化器各自实现了什么样的查询优化技术？
❏ PostgreSQL和MySQL的查询优化功能有什么异同？
第一个问题在第一篇中进行了讨论。第二、第三个问题在第二、第三篇中通过对PostgreSQL和MySQL查询优化器的源码分析进行了回答。第四个问题在第四篇中通过对PostgreSQL和MySQL查询优化的功能对比，对两者的差异进行了回答。
从全书来看，本书涉及查询优化器的原理、代码实现、工程实践3个部分。
原理部分，概括总结了查询优化器的两大优化策略，一是逻辑优化，二是物理优化。在每一个优化策略中，都结合原理、运用示例，努力展示了查询优化器的全貌。这部分内容将解答：“查询优化”究竟包括什么样的优化技术？为什么能做那些优化？
代码实现部分，通过深入数据库内核的源码，对查询优化器的实现进行深度的、全方位的探索，力求为程序员和数据库爱好者展示数据库引擎查询优化器的真实面目。行文选取了开源数据库PostgreSQL和MySQL的查询优化器，抽丝剥茧，进行了详细、全面的分析。这部分内容将解答：“查询优化器”是怎么实现的？“查询优化器”是怎么做优化工作的？
工程实践部分，通过原理分析、代码分析和示例，进行了以下3个对比：
❏ 对比PostgreSQL和MySQL的查询优化器的实现异同。
❏ 对比PostgreSQL和MySQL的查询优化器的功能异同。
❏ 对比查询优化器和原理之间的异同。
工程实践部分还通过大量详细的示例比较，总结了PostgreSQL、MySQL支持的优化点和不支持的优化点，为DBA调优提供了许多新颖的、好的思路。揭秘内核，帮助读者掌握其实现方式，可使读者在面对SQL调优时不再是雾里看花，而是心中有数。系统地掌握这些，可以超越依靠日积月累的学习方式，能够快速进阶。
工程实践部分通过3个对比，完成了以下3个结合：
❏ 通过代码分析，首次将关系代数、代价估算等查询优化原理与代码实现、工程实践结合。
❏ 通过对PostgreSQL和MySQL的对比，首次揭秘了两大开源数据库的查询优化器的异同，使得数据库爱好者能够以本书为基础，更好地结合查询优化技术，进而掌握各种类型的数据库SQL调优。
❏ 通过原理、代码、分析、示例，完成了将数据库爱好者对查询优化器强烈渴望掌握的愿望与轻松掌握的现实的结合，使得查询优化器不再那么神秘莫测。本书的主要特色
本书的主要特色如下：
❏ 全面揭秘数据库查询优化技术。把数据库的各种查询优化技术以工程化的视角进行剖析，集原理、源码分析、示例实践为一体。
❏ 重点分析了PostgreSQL和MySQL的查询优化器的实现。以两大开源数据库的查询优化器的实现为蓝本，分析了它们的实现过程、实现原理，帮助读者深入理解掌握数据库的核心技术，使他们在SQL调优过程中不仅掌握怎么调优而且知道为什么可以调优。
❏ 详细对比了PostgreSQL和MySQL的查询优化技术的支持能力。通过大量示例，分析对比了两大开源数据库的查询优化功能的强弱，帮助读者掌握两个数据库查询优化功能相同和不同之处，为应用系统选型提供衡量查询优化功能的依据。本书面向的主要读者
如果您是一名数据库内核的工作者，本书对数据库查询优化器的内核代码分析，一定会帮您全面掌握查询优化这一技术。再结合理论部分，将使您理解得更加深刻。
本书不仅讲述了PostgreSQL查询优化器的实现，还讲述了MySQL查询优化器的实现，这对于从事这两个数据库内核开发的人员来说尤其有帮助。如果您能把结合本书和源码（务必要读代码）两者相互印证进行掌握，将像弄潮儿涛头立，查询优化技术尽在您的掌中。
本书从理论角度出发构造了大量示例，通过源码和功能的对比分析，更是进一步揭示了这两个数据库查询优化器的功能异同。对于从事查询优化器性能提升的工作人员帮助更大——因为原理部分讲了为什么，代码分析部分讲了怎么做，示例与对比部分讲了有什么不同，可做的事情仅剩下“没有实现的优化怎么做”了。路已铺垫，启示已明，发挥就靠您自己了。
如果您是一名数据库实践者、DBA，本书一定会帮到您。查询优化器能做什么样的优化？为什么查询优化器能做某种类型的优化？对于这两个问题，原理部分能帮您解惑。如果您是一名DBA，您将更多地从代码分析、工程实践部分获益。源码级的内幕揭秘，无疑能帮您更好地做好SQL语句的日常优化工作；代码、功能、实践的比较，无疑能帮助您从初学到理解，进而过渡到得心应手地应用。
生活不是一成不变的，工作中您也许会在PostgreSQL与MySQL间切换，掌握原理又能帮您以不变应万变。本书所涉及的查询优化器的知识，适用于Oracle的DBA、DB2的DBA、SQLServer的DBA、SYSBASE的DBA。也许从此以后，您会成为一名万能的DBA！
如果您是一名数据库研究者、开发者、教学者、学生、爱好者，那么本书对您来说是一本不可多得的参考资料。查询优化器作为数据库中最重要、最难学、最精彩的部分，探索起来道路漫长，艰苦而无趣，也许本书能有幸成为您的同行伙伴，一路走来，不离不弃。探索数据库内核，犹如面对一座大山，陡峭艰险，无路可寻。看似非常艰难的事情，当您一书在手，仿佛为您提供了一柄手杖，步行于山涧沟壑时，且健且速。
特别是对于学生，如果能凭着这本薄书摸索进入数据库内核的世界，当是笔者最大的心愿。学生是未来的栋梁，是将技术发扬光大的希望。
多年来，作者一直翘首以盼，希望能有这么一类书，与己成为好友。现在，有了这么一本薄书，唯愿读者开卷有益。如何阅读本书
从模块的角度看，本书可分为4部分：原理、PostgreSQL实现、MySQL实现、三者对比总结。所以建议读者以模块为单位分别阅读。如果是读PostgreSQL实现、MySQL实现的章节，则应结合代码，前后联系沟通为好，不要掌握局部忽视整体。
从内容的分布上看，原理是综述部分，既讲述了原理对查询优化的指导，也对PostgreSQL实现、MySQL实现进行了总结，所以要从实践个例上升到理论的高度才能看清全貌。把原理和PostgreSQL实现结合起来，反复互为印证，会对掌握PostgreSQL有帮助；把原理和MySQL实现结合起来，反复互为印证，会对掌握MySQL有帮助；把4部分完全结合起来一起掌握，不仅可以帮助DBA和爱好者理解PostgreSQL、MySQL，还可以帮助他们理解其他数据库。因为本书中的两套源码的比较加上原理的解析，有助于帮助理解其他数据库查询优化器的原理；示例则有助于在其他数据库上执行以检查数据库对查询优化的支持程度。
另外，为便于读者更好地掌握数据库查询优化技术及本书内容，本书的附录从方法学的角度对阅读本书提供了4个方面的建议。为什么特别推荐学生阅读本书
对于爱好数据库技术的学生来说，选择数据处理技术，是一条明智之路。数据越来越多，数据源越来越多，大数据的时代不仅已经来临了，而且会一直发展、不断发展。数据库技术是处理大数据的核心技术，数据库技术会随着时代的需求，一直前进。而查询优化，在数据库领域，不仅有着重要的理论地位，而且在实践中也异常重要且用途广泛，SQL调优占据着数据库性能调优的半壁江山。
现今，就业竞争异常激烈，一份好的工作往往会有数以千计的人同时去争取。这对于诸多刚刚毕业、没有什么工作经验的学生来说，无疑是非常严峻的考验，尤其对于想找到理想工作的学生更是难上加难。因为现在用人单位提供的工作岗位对应聘者的素质和技能的要求越来越高，这无疑是刚刚毕业的学生最大的短板。
对于用人单位来说，想招到一名合格的员工也不容易，招到一名技能纯熟、素质高的员工更难。
在这样的大背景下，如果学生在求学期间能够打下良好的专业基础，找工作时定会增加很多机会；如果学生能够在自己的专业领域深入探索，对数据结构、操作系统、数据库等重要课程熟练掌握，使自己具备良好的专业素质，必然能使自己在找工作时具备更强的竞争力；如果学生能在某些课程上把理论和实践结合起来，把理论和源码结合起来，熟练掌握重量级软件的内核代码，找到心仪的工作将更为容易。用人单位喜欢有理论、工作初始就能上手做事的人才。而学生们想成为这样的人才，就需要在学校里打下坚实的基础。
本书在数据库领域就能起到这样的作用。引领学生把数据库理论和数据库实践结合起来，把数据库理论和数据库引擎源码结合起来，有效帮助读者梳理数据库技术中最重要的部分——查询优化技术的全貌，这必定对掌握这部分技术有很大的帮助。
所以，笔者特别推荐学生阅读本书。建议在本科高年级阶段或研究生阶段，大家能与本书为伴，边读源码（PostgreSQL和MySQL的源码）边读本书，互为印证。笔者相信通过短短数月的努力，大家得到的将是足够好的技能、足够高的起点、足够强的竞争力！
学生是未来、是希望，学生强，社会亦将受益。学生若能通过本书使自己变强，将是笔者最大之幸。勘误及支持
由于笔者的水平有限，书中难免会有笔误、差错、格式错误或遗漏等问题，希望广大读者能把发现的错误告诉笔者，我将不胜感谢。本书的进步和完善，有您的帮助和爱护，定能再上一层楼。您可以发送电子邮件到：database_XX@163.com。由于时间有限，也许笔者不能一一答复所有的电子邮件，但是会定期整理并汇总信息到笔者的博客（http://bolg.163.com/li_hx）上。
书中分析、探索的数据库源码的下载地址如下：
PostgreSQL，V9.2.3，源自http://www.postgresql.org/ftp/source/v9.2.3/。
MySQL，V5.6.10，源自http://dev.mysql.com/downloads/mysql/。致谢
在我的生命中，家人是最重要的。伏案疾书不舍昼夜，心中一直牵挂的是父母、姐妹、妻子和各地的亲人们。他们是我写作的动力源泉，他们是我得以坚持完稿的坚强后盾。感谢父母给予了我生命并育我成人，感谢妻子朝夕相伴给予我鼓励和慰藉，感谢我远方的亲人们让我心意暖暖。
感谢中国人民大学信息学院王珊教授多年的教导，并高屋建瓴地为本书提出修订意见，她严谨的工作作风影响了本书的风格。成书之际，王老师乐为作序，我心怀感激，念念在心。
感谢为开源社区无私奉献的人们，没有他们就没有本书。本书的内容源于对开源数据库内核代码的分析，故笔者认为本书也应该回归社区为众人服务。坚持写下自己的所得，与他人共享，是一件快事，也是一件幸事。
感谢编辑杨福川先生和孙海亮先生为本书付出的努力和耗费的心血，书名源于杨先生，书稿样式由孙先生设定。写了一本书，交了两个好朋友。谢谢他们。
感谢每一位读者，我们一起进步，你们将是本书继续完善的新动力。
我深知本书尚不能达到书名标识的高度，而今迈步从头越。第一篇 查询优化技术
本篇介绍了数据库的查询优化技术，从数据库的理论出发界定查询优化技术的范围，讨论了包括逻辑查询优化、物理查询优化两个方面的查询优化技术。全篇立足于数据库的基本理论——关系代数，在第1章首先界定了本书讨论的查询优化的技术范围；在第2章运用关系代数理论和关系法则，对逻辑查询优化进行全面而深入的探讨，对各种逻辑查询优化技术进行全面介绍，指出关系代数对于查询优化技术的指导意义，通过示例巩固对查询优化技术的理解和认识；在第3章，通过对代价估算模型、索引和表扫描、表连接算法的介绍，对各种物理查询优化技术进行全面描绘，构造了清晰、完整的物理查询优化技术图谱；在第4章，对实现查询优化技术的数据库查询优化器的相关模块进行了介绍，意在使读者了解查询优化技术的相关上下文内容。第1章 数据管理系统的查询优化
数据库管理系统（DataBase Management System，DBMS，简称数据库）是位于用户与操作系统之间的一层数据管理软件，主要功能包括：数据定义、数据操纵、数据库的运行管理、数据库的建立和
[1]维护等。
数据操纵是数据库管理系统中一种最基本的操作，这种操作包括查询、插入、删除和修改等，其中，查询操作称为查询处理。
查询的执行，就是查询处理的过程，即数据库按用户指定的SQL语句中的语义，执行语义所限定的操作。但SQL语句的执行效率对数据库的效率影响较大。为了提高查询语句的执行效率，对查询语句进行优化是必不可少的。
对查询语句进行优化的技术就是查询优化技术，运用查询技术实现数据操纵功能的过程是确定给定查询的高效执行计划的过程。所谓执行计划就是查询树，它由一系列内部的操作符组成，这些操作符按一定的运算关系构成查询的一个执行方案。查询优化的追求目标，就是在数据库查询优化引擎生成一个执行策略的过程中，尽量使查询的总开销（总开销通常包括IO、CPU、网络传输等）达到最小。
数据库查询优化技术主要包括查询重用技术、查询重写规则、查询算法优化技术、并行查询优化技术、分布式查询优化技术及其他方面（如框架结构）的优化技术，这6项技术构成了一个“广义的数据库查询优化”的概念。
本书重点探讨“查询重写规则”和“查询算法优化”，这是多数书籍在提及“数据库查询优化”时所限定的范围，这两项技术在本书中称为“狭义的数据库查询优化”。从优化的内容角度看，查询优化又分为代数优化和非代数优化，或称为逻辑优化和物理优化。逻辑优化主要依据关系代数的等价变换做一些逻辑变换，物理优化主要根据数据读取、表连接方式、表连接顺序、排序等技术对查询进行优化。“查询重写规则”属于逻辑优化方式，运用了关系代数和启发式规则；“查询算法优化”属于物理优化方式，运用了基于代价估算的多表连接算法求解最小花费的技术。
查询优化技术中“查询重写规则”的理论基础是关系代数，但本书的重点不是讨论关系代数理论，而是着眼于关系代数和查询优化相结合的部分，指出理论与实践的对应关系，分析理论是如何指导数据库引擎执行查询优化的，进而使读者明白数据库查询优化器的实现原理，掌握SQL语句的优化方法。这些主要包括以下内容：
❏ 查询优化引擎能做什么样的查询优化操作。这第1章的重点内容，将全面指明查询优化技术的范围，以期建立查询优化技术的全局概念。
❏ 查询优化引擎为什么能进行查询优化。这是第2章和第3章的重点内容，将从理论的角度出发进行介绍。其中第2章介绍逻辑优化包括的具体技术、为什么可做逻辑优化，以及怎么做逻辑优化；第3章介绍物理优化的具体技术、为什么可做物理优化，以及怎么做物理优化。
对于并行查询优化、分布式并行查询优化、其他优化等只做简单介绍，之所以如此，是为了保持全文的完整性，提醒读者从概念上要明确“数据库的查询优化技术”的范围。
本章先从数据库层面的优化进行概述，这是全局级别的优化，着眼点在整个数据库管理系统，借以区别本书重点——查询优化技术。接着，详细介绍查询优化技术，这是局部的、SQL语句级别的优化，也是本书着重探讨的内容。
[1]《数据库系统概论》，王珊，萨师暄。1.1 数据库调优
数据库调优可以使数据库应用运行得更快，其目标是使数据库有更高的吞吐量和更短的响应时间。被调优的对象是整个数据库管理系统总体。
在数据库层面进行调优，有很多的资源、数据库配置参数需要考虑。数据库调优的方式通常有如下几种：
❏ 人工调优。主要依赖于人，效率低下；要求操作者完全理解常识所依赖的原理，还需要对应用、数据库管理系统、操作系统以及硬件有广泛而深刻的理解。
❏ 基于案例的调优。总结典型应用案例情况中数据库参数的推荐配置值、数据逻辑层设计等情况，从而为用户的调优工作提供一定的参考和借鉴。但这种方式忽略了系统的动态性和不同系统间存在的差异。
❏ 自调优。为数据库系统建立一个模型，根据“影响数据库系统性能效率的因素”，数据库系统自动进行参数的配置。一些商业数据库实现了部分自调优技术，典型的如Oracle提供了如下一些技术或工具。
○ Redo Logfile Sizing Advisor：为避免因频繁出现的检查点而导致过多的磁盘IO，系统可推荐重做日志文件的最佳大小。
○ Automatic Checkpoint Tuning：为取得良好的恢复速度，同时降低对正常吞吐量的影响，系统可以自动优检查点。
○ Automatic Shared Memory Tuning：为高效地利用可用内存并提高性能，系统可自动地配置与System Global Area（SGA）内存相关的参数（如缓冲区缓存、共享池等）。
○ Transaction Rollback and Recovery Monitoring：为掌握事务状况，系统可估计回滚一个事务要花多少时间，监视被恢复的事务的进度，并估计事务恢复的平均速度。
○ SQL Tuning Advisor：为提高SQL语句的执行效率，系统可自动调优高成本的SQL语句，给出建立索引的建议、SQL重写的建议等。
○ SQL Analyzer：对SQL语句的不同查询执行计划进行性能分析和比较。
○ SQL Access Advisor：对物理设计给出改进建议。
○ SQL Plan Management：使SQL语句能够根据环境的变化选择稳定、高效的查询执行计划。
○ Segment Advisor：根据对象内的空间碎片化程度，给出是否应该对对象执行新的在线收缩操作的建议；提供关于段的历史增长趋势的报告，为容量规划提供有效的信息。
Undo Advisor：帮助管理员在flashback和非flashback特性中调整撤销表空间大小时做出正确的判断；为管理员恰当地设置UNDO_RETENTION提供建议，避免快照过于陈旧。
通常，数据库调优主要分为5阶段，如表1-1所示。涉及的技术主要有以下几种：
❏ 应用情况的估算。应用的使用方式（把业务逻辑转换为数据库的读写分布逻辑，以读多写少或读写均衡等来区分OLAP和OLTP；应用对数据库的并发情况、并发是否可以池化等）、数据量、对数据库的压力、峰值压力等做一个预估。
❏ 系统选型策略。确定什么样的数据库可以适用应用需求，并确定使用开源的数据库还是商业的数据库，使用集群还是单机的系统，同时对操作系统、中间件、硬件、网络等进行选型。
❏ 数据模型的设计。主要根据业务逻辑，从几个角度考虑表的逻辑结构，内容如下。
○ E-R模型设计：遵循E-R模型设计原理。偶尔的、适当程度的非规范化可以改善系统查询性能。
○ 数据逻辑分布策略：目的是减少数据请求中不必要的数据量，只返回用户需要的数据。可用的技术如分区、用E-R模型分表等（如互联网企业典型的用法，根据业务的不同，进行分库、分表等操作）。
○ 数据物理存储策略：目的是减少IO操作，如启用压缩技术、把索引和表数据的存储分开，不同的表数据分布在不同的表空间上，不同的表空间分布在不同的物理存储上（尤其是读写量大的表空间分布在不同的物理存储上），日志、索引和数据分布在不同的物理存储上等。
○ 索引：在查询频繁的对象上建立恰当的索引，使索引的正效应大于负效应（索引的维护存在消耗）。
❏ SQL设计。编写正确的、查询效率高的SQL语句，依据的主要是“查询重写规则”。编写语句的过程中要注意，要有意识地保障SQL能利用到索引。
❏ 数据库功能的启用。数据库为提高性能提供了一些功能，可合理使用，具体如下。
○ 查询重用：根据实际情况进行配置，可缓存查询执行计划、查询结果等。
○ 数据库参数的设置：可设置合适的参数，如数据缓冲区等。
❏ 模型系统预运行。在备用系统上模拟实际运行环境，加大压力进行系统测试，提前发现问题。
❏ 系统监控与分析。在工业环境下，加强对系统的运行监控和日常的分析工作，具体如下。
○ 应用系统表现：收集用户对应用系统的使用意见、系统存在问题等，因为这些可能是用户在第一时间发现的。
○ OS环境监控：实时监控CPU、内存、IO等，并对比实时情况与历史正常情况。
○ 数据库内部状况监控：一些数据库提供系统表、视图、工具等手段，向用户提供数据库运行过程中内部状况的信息，如锁的情况，这些都需要实时监控，并对比实时情况与历史正常情况。
○ 日志分析：在数据库的日志、操作系统的日志中找出异常事件，定位问题。表1-1 数据库调优5个阶段1.2 查询优化技术
查询优化技术是SQL层面的优化，属于局部优化，有别于“数据库调优”式的全局优化。上面我们说过，查询优化技术主要包括查询重用技术、查询重写规则技术、查询算法优化技术、并行查询的优化技术、分布式查询优化技术、其他优化技术6个方面的技术。下面我们就从这6个方面介绍查询优化技术。1.2.1 查询重用
查询重用是指尽可能利用先前的执行结果，以达到节约查询计算全过程的时间并减少资源消耗的目的。
目前查询重用技术主要集中在两个方面：
❏ 查询结果的重用。在缓存区中分配一块缓冲块，存放该SQL语句文本和最后的结果集，当遇到同样的SQL输入时，可直接把结果返回。查询结果的重用技术节约了查询计划生成时间和查询执行过程的时间，减少了查询执行全过程的资源消耗。
❏ 查询计划的重用。缓存一条查询语句的执行计划及其相应语法树结构。查询计划的重用技术减少了查询计划生成的时间和资源消耗。
查询重用技术有利有弊：弊端，如结果集很大会消耗很大的内存资源，同样的SQL不同用户获取的结果集可能不完全相同；益处，节约了CPU和IO消耗。在使用的过程中，趋利避害，应根据实际情况选用。1.2.2 查询重写规则
查询重写是查询语句的一种等价转换，即对于任何相关模式的任意状态都会产生相同的结果（相同的关系替代两个表达式中相应的关系，所得到的结果是相同的）。查询重写有两个目标：
❏ 将查询转换为等价的、效率更高的形式，例如将效率低的谓词转换为效率高的谓词、消除重复条件等。
❏ 尽量将查询重写为等价、简单且不受表顺序限制的形式，为物理查询优化阶段提供更多的选择，如视图的重写、子查询的合并转换等。
查询重写的依据，是关系代数。关系代数的等价变换规则对查询重写提供了理论上的支持。查询重写后，查询优化器可能生成多个连接路径，可以从候选者中择优。
对查询优化技术进行分类，可有以下4个角度：
❏ 语法级。查询语言层的优化，基于语法进行优化。
❏ 代数级。查询使用形式逻辑进行优化，运用关系代数的原理进行优化。
❏ 语义级。根据完整性约束，对查询语句进行语义理解，推知一些可优化的操作。
❏ 物理级。物理优化技术，基于代价估算模型，比较得出各种执行方式中代价最小的。
查询重写是基于语法级、代数级、语义级的优化，可以统一归属到逻辑优化的范畴：基于代价估算模型是物理层面的优化，是从连接路径中选择代价最小的路径的过程。
查询重写技术优化思路主要包括：
❏ 将过程性查询转换为描述性的查询，如视图重写。
❏ 将复杂的查询（如嵌套子查询、外连接、嵌套连接）尽可能转换为多表连接查询。
❏ 将效率低的谓词转换为等价的效率高的谓词（如等价谓词重写）。
❏ 利用等式和不等式的性质，简化WHERE、HAVING和ON条件。
如何改进现有查询重写规则的效率，如何发现更多更有效的重写规则，是查询优化的研究内容之一。常见的查询重写技术类型，每一类都有自己的规则，这些规则没有确定的、统一的规律，但重写的核心一定是“等价转换”，只有等价才能转换，这是需要特别强调的。1.2.3 查询算法优化
查询优化即求解给定查询语句的高效执行计划（有的书籍称为执行方案）的过程。
查询计划，也称为查询树，它由一系列内部的操作符组成，这些操作符按一定的运算关系构成查询的一个执行方案。简单说，就是先将表A和表B连接得到中间结果，然后再和另外的表C连接得到新的中间方式，直至所有表连接完毕（连接操作就是操作符，这个示例有两个连接操作符。A连接B连接C、C连接B连接A就是两种不同的执行方案，是两个不同的执行计划，查询优化要选出最高效的一个执行方案）。
查询计划，从形式上看是一颗二叉树，树叶是每个单表对象，两个树叶的父结点是一个连接操作符（如左外连接操作符，A left-out join B）连接后的中间结果（另外还有一些其他结点如排序操作等也可以作为中间结果），这个结果是一个临时“关系”，这样直至根结点。
所以从一个查询计划看，涉及的主要“关系结点”包括：
❏ 单表结点。考虑单表的数据获取方式，是直接通过IO获得数据，还是通过索引获取数据，或者是通过索引定位数据的位置后再经过IO到数据块中获取数据。这是一个从物理存储到内存解析成逻辑字段的过程，即符合冯·诺依曼体系结构的要求（外存数据读入内存才能被处理）。
❏ 两表结点。考虑两表以何种方式连接、代价有多大、连接路径有哪些等。表示的是内存中的元组怎么进行元组间的连接。此时，元组通常已经存在于内存中，直接使用即可。这是一个完成用户语义的逻辑操作，但是只是局部操作，只涉及两个具体的关系。完成用户全部语义（用户连接的语义），需要配合多表的连接顺序的操作。不同的连接算法导致的连接效率不同，如数据多时可使用Hash连接，外表数据量小且内表数据量大时可使用嵌套连接，数据如果有序可使用归并连接或先排序后使用归并连接等。
❏ 多表中间结点。考虑多表连接顺序如何构成代价最少的“执行计划”。决定是AB先连接还是BC先连接，这是一个比较花费大小的运算。如果判断的连接方式太多，也会导致效率问题。多个关系采用不同次序进行连接，花费的CPU资源、内存资源差异可能较大。许多数据库采用左深树、右深树、紧密树3种方式或其中一部分对多表进行连接，得到多种连接路径。
查询优化目的就是生成最好的查询计划。生成最好的查询计划的策略通常有两个：
❏ 基于规则优化。根据经验或一些已经探知或被证明有效的方式，定义为“规则”（如根据关系代数得知的规则、根据经验得知的规则等），用这些规则化简查询计划生成过程中符合可被化简的操作，使用启发式规则排除一些明显不好的存取路径，这就是基于规则的优化。
❏ 基于代价优化。根据一个代价评估模型，在生成查询计划的过程中，计算每条存取路径（存取路径主要包括上述3个“关系结点”）的花费，然后选择代价最小的作为子路径，这样直至所有表连接完毕得到一个完整的路径。主流数据库都采用了基于代价策略进行优化的技术。
基于规则优化具有操作简单且能快速确定连接方式的优点，但这种方法只是排除了一部分不好的可能，所以得到的结果未必是最好的；基于代价优化是对各种可能的情况进行量化比较，从而可以得到花费最小的情况，但如果组合情况比较多则花费的判断时间就会很多；查询优化器的实现，多是两种优化策略组合使用，如MySQL和PostgreSQL就采取了基于规则和代价估算的查询优化策略。
多表连接的优化算法中，使用最广泛的算法有如下几种：
❏ SYSTEM-R算法。近乎穷举的搜索算法（一种空间搜索算法，其变形算法与其本质相同）。
❏ 启发式搜索算法。基于规则（基于“启发式规则”抛弃不好的存取路径挑选好的）。
❏ 贪婪算法。根据某种优化方式，以当前情况为基础做出最优选择，认为每次搜索过的局部存取路径是最优的，然后继续探索与其他表的连接路径。
❏ 动态规划算法。将待求解的问题分解为若干个子问题（阶段），按顺序求解子问题，前一子问题的解，为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些可能达到最优的局部解，丢弃其他局部解。依次解决各子问题，最后一个子问题就是初始问题的解。
❏ 遗传算法。一种启发式的优化算法，抛弃了传统的搜索方式，模拟自然界生物进化过程，基于自然群体遗传演化机制，采用人工进化的方式对目标空间进行随机化搜索。
我们知道，查询的基本操作是选择、投影和连接。选择和投影的优化规则适用于SPJ（Select-Project-Join）和非SPJ（SPJ+GROUPBY等操作）；连接包括两表连接和多表连接，多表连接是其中最难的，因为多个表连接时可以有多种不同的连接次序，所以查询的执行计划的数目会随着该查询包含的表个数呈指数级增长（最大组合次数是n个关系全排列），当表个数很多时，将导致搜索空间极度膨胀，仅搜索花费最小的查询计划就需要耗费巨大的时间和资源，这是查询优化器实现时需要考虑的问题。1.2.4 并行查询优化
传统单机数据库系统中，给定一个查询（Query），查询优化算法只需找到查询的一个具有最小执行花费的执行计划，这样的计划必定具有最快的响应时间。
在并行数据库系统中，查询优化的目标是寻找具有最小响应时间的查询执行计划，这需要把查询工作分解为一些可以并行运行的子工作。一些商业数据库提供了并行查询的功能，用以优化查询执行操作。
一个查询能否并行执行，取决于以下因素：
❏ 系统中的可用资源（如内存、高速缓存中的数据量等）。
❏ CPU的数目。
❏ 运算中的特定代数运算符。如A、B、C、D4个表进行连接，每个表的单表扫描可以并行进行；在生成4个表连接的查询计划过程中，可选择A和B连接的同时C和D进行连接，这样连接操作能并行运行。不同商业数据库，对查询并行的实现也不尽相同。在同一个SQL内，查询并行可以分为以下两种：
○ 操作内并行。将同一操作如单表扫描操作、两表连接操作、排序操作等分解成多个独立的子操作，由不同的CPU同时执行。
○ 操作间并行。一条SQL查询语句可以分解成多个子操作，由多个CPU执行。1.2.5 分布式查询优化
在分布式数据库系统中，查询策略优化（主要是数据传输策略，A、B两结点的数据进行连接，是A结点数据传输到B结点或从B到A或先各自进行过滤然后再传输等）和局部处理优化（传统的单结点数据库的查询优化技术）是查询优化的重点。
在查询优化策略中，数据的通信开销是优化算法考虑的主要因素。分布式查询优化以减少传输的次数和数据量作为查询优化的目标。所以，分布式数据库系统中的代价估算模型，除了考虑CPU代价和IO代价外，还要考虑通过网络在结点间传输数据的代价。这是分布式并行查询优化技术与传统单结点数据库系统最大的不同之处。
在分布式数据库系统中，代价估算模型如下：总代价=IO代价+CPU代价+通信代价1.2.6 其他优化
数据库的查询性能，还取决于其他一些因素，如数据库集群系统中的SD（Share Disk）集群和SN（Share Nothing）集群，不同的架构查询优化技术也不同。SD集群采用的是共享存储方式，在数据的读写时可能产生读写冲突，所以单表扫描会受到影响；SN集群采用的是非共享式存储方式，所以在考虑了通信代价后单结点的优化方式依然适用。这些都不作为本书的重点，所以就不过多介绍了。1.3 本章小结
本章辨析了数据库调优和查询优化技术的区别，从整体上介绍了查询优化涉及的主要技术，但本章内容不涉及原理的证明，只是从利于工程实践的角度出发，力图构建查询优化技术的整体概念，描绘查询优化技术的范围，从而帮助读者全面了解查询优化的技术。第2章 逻辑查询优化
查询优化器在逻辑优化阶段主要解决的问题是：如何找出SQL语句等价的变换形式，使得SQL执行更高效。
一条SQL查询语句结构复杂，包含多种类型的子句，优化操作依赖于表的一些属性信息（如索引和约束等）。可用于优化的思路包括：
❏ 子句局部优化。每种类型子句都可能存在优化方式，这是子句局部的优化，如等价谓词重写、WHERE和HAVING条件化简中的大部分情况，都属于这种子句范围内的局部优化。
❏ 子句间关联优化。子句与子句之间关联的语义存在优化的可能，如外连接消除、连接消除、子查询优化、视图重写等都属于子句间的关联优化，因为它们的优化都需要借助其他子句、表定义或列属性等信息进行。
❏ 局部与整体的优化。需要协同考虑局部表达式和整体的关系，如OR重写并集规则需要考虑UNION操作（UNION是变换后的整体的形式）的花费和OR操作（OR是局部表达式）的花费。
❏ 形式变化优化。多个子句存在嵌套，可以通过形式的变化完成优化，如嵌套连接消除。
❏ 语义优化。根据完整性约束、SQL表达的含义等信息对语句进行语义优化。
❏ 其他优化。根据一些规则对非SPJ做的其他优化、根据硬件环境进行的并行查询优化等。
各种逻辑优化技术依据关系代数和启发式规则进行。2.1 查询优化技术的理论基础
查询优化技术的理论基础是关系代数。本节就关系代数的最基本内容进行介绍，目的是引出关系代数对查询优化的指导意义。2.1.1 关系代数
1970年，E.F.Codd在题为《A Relational Model of Data for Shared Data Banks》的论文中提出了数据的关系模型的概念。Codd提议将关系代数作为数据库查询语言的基础。关系数据库基于关系代数。关系数据库的对外接口是SQL语句，所以SQL语句中的DML、DQL基于关系代数实现了关系的运算。
作为数据库查询语言的基础，关系模型由关系数据结构、关系操作集合和关系完整性约束三部分组成。以下是几个和关系模型有关的概念：
❏ 关系模型的数据结构就是我们在关系数据库中提到的二维结构，是一个横纵结合的二维表。在关系模型中，现实世界的实体以及实体间的各种联系均用关系来表示。
❏ 关系是一种对象。
❏ 关系的另外一个常用词是表，在本书中，关系和表混用，因为它们基本表达同一含义，只是关系更偏向于理论，表更偏向于实际数据库中可进行增、删、改、查等操作的表对象。
❏ 关系的元数据，即表的结构，通常称为列或属性。数据库实现中，有的用field表示，有的用Item表示。
❏ 关系的数据，即表的行数据，通常称为元组（tuple），也称为记录（record）。一个表可有多行元组。
❏ 对关系进行的操作就是关系运算。关系运算是将一定的运算符作用于一定的关系对象上，得到预期的运算结果（预期就是用户语义，用户语义通过运算符表达基本语义，通过对不同对象上的各种运算进行组合表达其对关系操作的真实语义）。运算对象、运算符、运算结果是运算的三大要素，所以关系运算就是关系运算符作用在关系上、得到的结果形式也是关系形式的操作。[2]
关系代数的运算符包括以下4类：
❏ 传统集合运算符。并（UNION）、交（INTERSECTION）、差（DIFFERENCE）、积（EXTENDED CARTESIAN PRODUCT）。
❏ 专门的关系运算符。选择（SELECT）、投影（PROJECT）、连接（JOIN）、除（DIVIDE）。
❏ 辅助运算符。用来辅助专门的关系运算符进行操作的，包括算术比较符和逻辑运算符。
❏ Codd定义了8个基本关系运算符后，许多人提出了新的代数操作符——关系扩展运算符，如半连接（SEMIJOIN）、半差（SEMIDIFFERENCE）、扩展（EXTEND）、合计（COMPOSITION）、传递闭包（TCLOSE）等，这些操作符增强了关系代数的表达能力，但不常用。
关系代数基本关系运算如表2-1所示，各种连接运算的语义如表2-2所示。表2-1 基本关系运算与对应的SQL表表2-2 各种连接运算的语义表
自然连接：在数据库中对应了主外键的语义。
[2]Codd的代数的6个原始运算是选择、投影、笛卡儿积（又称叉积或交叉连接）、并集、差集和重命名。2.1.2 关系代数等价变换规则对优化的指导意义
关系代数表达式的等价：也就是说用相同的关系代替两个表达式中相应的关系，所得到的结果是相同的。两个关系表达式El和E2是等价的，记为E1≡E2。[3]
查询语句可以表示为一棵二叉树，其中：
❏ 叶子是关系。
❏ 内部结点是运算符（或称算子、操作符，如LEFT OUT JOIN），表示左右子树的运算方式。
❏ 子树是子表达式或SQL片段。
❏ 根结点是最后运算的操作符。
❏ 根结点运算之后，得到的是SQL查询优化后的结果。
❏ 这样一棵树就是一个查询的路径。
❏ 多个关系连接，连接顺序不同，可以得出多个类似的二叉树。
❏ 查询优化就是找出代价最小的二叉树，即最优的查询路径。每条路径的生成，包括了单表扫描、两表连接、多表连接顺序、多表连接搜索空间等技术。
❏ 基于代价估算的查询优化就是通过计算和比较，找出花费最少的最优二叉树。
上述的最后两项，主要依据本章查询重写规则和第3章物理查询优化中涉及的技术，对查询优化引擎做关系代数和启发式规则的逻辑查询优化、基于代价估算模型择优的物理查询优化，从而帮助数据库查询优化器实现查询优化。
1.从运算符的角度考虑优化
不同运算符根据其特点，可以对查询语句做不同的优化，优化可以减少中间生成物的大小和数量，节约IO、内存等，从而提高了执行速度。但优化的前提是：优化前和优化后的语义必须等价。不同运算符的优化规则和可优化的原因如表2-3所示。表2-3 运算符主导的优化
合取：如WHERE A.a=B.b AND B.b=C.c可以合并为={A.a,B.b,C.c}而不是两个等式={A.a,B.b}和={B.b,C.c}。
析取：如WHERE A.a=3 OR A.b>8，如果A.a、A.b列上分别有索引，也许SELECT*FROM A WHERE A.a=3；UNION SELECT*FROM A WHERE A.b>8可以分别利用各自的索引提高查询效率。表2-4 选择下推到集合的运算表2-5 投影下推到集合的运算
对于表2-4和表2-5，我们以“σA(R×S)”为例，表明它们可做优化的共同意义。
初始式是σA(R×S)，条件A可分解为“B∧C∧D”，条件B只与关系R有关，条件C只与关系S有关，则初始式可以变形为：σB∧C∧D(R×S)，表示为查询树的结构如图2-1所示。图2-1 查询树结构的初始样式
图2-2所示为第一层做完选择后，每个叶子结点对应的元组数“可能”比图2-1中的R和S少，如果B条件和C条件至少有一个能够大量减少R或S的元组，则中间结果大量减少，优化的效果会更好（B条件和C条件对元组过滤程度依赖于“选择率”）。如果R和S上有B条件、C条件可以使用的索引，则利用索引可加快元组的获取，优化的效果会更好。图2-2 查询树结构等价的变形式
如果索引是唯一索引或主键（主键不允许重复，不允许为NULL值，多数数据库为主键实现了一个唯一索引）之类，条件表达式是等值表达式（=运算非范围运算），定位元组的速度更快（可直接利用索引而不用扫描数据）、满足条件的元组更少，所以优化的效果会更佳。
图2-1中在连接后进行选择操作，一是中间结果的元组数量大，二是需要对中间结果的每条元组都进行B、C、D3个条件的判断，增加了条件判断的成本，效率很低。
经过等价变换优化带来的好处，再加上避免了原始方式引入的坏处，使得查询效率明显获得提升。
2.从运算规则的角度考虑优化
前面我们从运算符的角度出发考虑了优化。因为运算符中考虑的子类型（见表2-3中的“子类型”列）实则是部分考虑了运算符间的关系、运算符和操作数间的关系，其本质是运算规则在起作用。所以前节考虑过关系代数运算规则对优化的作用，但不完整，这里补充余下的对优化有作用的主要关系代数运算规则。下面的运算规则是查询重写技术作等价转换的基础，如表2-6所示。表2-6 运算规则主导的优化
连接：，表示连接；×，表示积。
笛卡儿积交换律：并和交操作，也满足交换律，但优化的意义不大。
连接、笛卡儿积的结合率：并和交操作，也满足结合律，但优化的意义不大。
[3]“查询语句表示为一棵二叉树”的过程，首先是语法分析得到一棵查询树的过程；其次伴有语义分析等工作；再次是根据关系代数进行了数据库的逻辑查询优化；最后是根据代价估算算法进行物理查询优化。优化后的结果，被送到执行器执行。2.2 查询重写规则
传统的联机事务处理（On-line Transaction Processing，OLTP）使用基于选择（SELECT）、投影（PROJECT）、连接（JOIN）3种基本操作相结合的查询，这种查询称为SPJ查询。
数据库在查询优化的过程中，会对这3种基本操作进行优化。优化的方式如下：
❏ 选择操作。对应的是限制条件（格式类似field
❏ 投影操作。对应的SELECT查询的目的列对象，优化方式是投影操作下推，目的是尽量减少连接操作前的列数，使得中间临时关系尽量小（特别注意差别：选择操作是使元组的个数“尽量少”，投影操作是使一条元组“尽量小”），这样虽然不能减少IO（多数数据库存储方式是行存储，元组是读取的最基本单位，所以要想操作列则必须读取一行数据），但可以各减少连接后的中间关系的元组大小，节约内存空间。
❏ 连接操作。对应的是连接条件（格式类似field_1
○ 多表连接中每个表被连接的顺序决定着效率。如果一个查询语句只有一个表，则这样的语句很简单；但如果有多个表，则会涉及表之间以什么样的顺序连接效率最高效（如A、B、C三表连接，如果ABC、ACB、BCA等连接后的结果集一样，则计算哪种连接次序的效率最高，是需要考虑的问题）。
○ 多表连接每个表被连接的顺序由用户语义决定。查询语句多表连接有着不同的语义（如是笛卡儿集、内连接，还是外连接中的左外连接等），这决定着表之间的前后连接次序是不能随意更换的，否则，结果集中数据是不同的。因此，表的前后连接次序是不能随意交换的。
另外，根据SQL语句的形式特点，还可以做如下区分：
❏ 针对SPJ的查询优化。基于选择、投影、连接3种基本操作相结合的查询。
❏ 针对非SPJ的查询优化。在SPJ的基础上存在GROUPBY操作的查询，这是一种较为复杂的查询。
所以，针对SPJ和非SPJ的查询优化，其实是对以上多种操作的优化。“选择”和“投影”操作，可以在关系代数规则的指导下进行优化。表连接，需要多表连接的相关算法完成优化。其他操作的优化多是基于索引和代价估算完成的。2.2.1 子查询的优化
子查询是查询语句中经常出现的一种类型，是比较耗时的操作。优化子查询对查询效率的提升有着直接的影响，所以子查询优化技术，是数据库查询优化引擎的重要研究内容。
从子查询出现在SQL语句的位置看，它可以出现在目标列、FROM子句、WHERE子句、JOIN/ON子句、GROUPBY子句、HAVING子句、ORDERBY子句等位置。子查询出现在不同位置对优化的影响如下：
❏ 目标列位置。子查询如果位于目标列，则只能是标量子查询，否则数据库可能返回类似“错误：子查询必须只能返回一个字段”的提示。
❏ FROM子句位置。相关子查询出现在FROM子句中，数据库可能返回类似“在FROM子句中的子查询无法参考相同查询级别中的关系”的提示，所以相关子查询不能出现在FROM子句中；非相关子查询出现在FROM子句中，可上拉子查询到父层，在多表连接时统一考虑连接代价后择优。
❏ WHERE子句位置。出现在WHERE子句中的子查询是一个条件表达式的一部分，而表达式可以分解为操作符和操作数；根据参与运算的数据类型的不同，操作符也不尽相同，如INT型有>、<、=、<>等操作，这对子查询均有一定的要求（如INT型的等值操作，要求子查询必须是标量子查询）。另外，子查询出现在WHERE子句中的格式也有用谓词指定的一些操作，如IN、BETWEEN、EXISTS等。
❏ JOIN/ON子句位置。JOIN/ON子句可以拆分为两部分，一是JOIN块类似于FROM子句，二是ON子句块类似于WHERE子句，这两部分都可以出现子查询。子查询的处理方式同FROM子句和WHERE子句。[4]
❏ GROUPBY子句位置。目标列必须和GROUPBY关联。可将子查询写在GROUPBY位置处，但子查询用在GROUPBY处没有实用意义。
❏ ORDERBY子句位置。可将子查询写在ORDERBY位置处。但ORDERBY操作是作用在整条SQL语句上的，子查询用在ORDERBY处没有实用意义。
1.子查询的分类
根据子查询中涉及的关系对象与外层关系对象间的关系，子查询可以分为以下两类：
❏ 相关子查询。子查询的执行依赖于外层父查询的一些属性值。子查询因依赖于父查询的参数，当父查询的参数改变时，子查询需要根据新参数值重新执行（查询优化器对相关子查询进行优化有一定意义），如：
试读结束[说明：试读内容隐藏了图片]