海量数据库解决方案

.第2章 索引的类型和特征43
2.1 b-tree 索引44
2.1.1 b-tree 索引的结构44
2.1.2 b-tree 索引的应用47
2.1.3 反向键索引52
2.2 位图索引53
2.2.1 位图索引的形成背景54
2.2.2 位图索引的结构和特征55
2.2.3 位图索引的读取57
2.3 基于自定义的函数索引60
2.3.1 基于自定义的函数索引的概念和结构60
2.3.2 基于自定义函数索引的约束61
2.3.3 基于自定义函数索引的灵活运用64
第3章 sql的执行计划（explain plan）74
3.1 sql和优化器75
3.1.1 优化器的作用和人的作用77
3.1.2 优化器的类型80
3.1.2.1 基于规则的优化器82
3.1.2.2 基于成本的优化器86
3.1.2.3 优化器目标的选择93
3.1.2.4 执行计划的固定化方案97
3.1.2.5 优化器的局限103
3.1.3 优化器的最优化步骤106
3.1.4 查询语句的转换112
3.1.4.1 传递性规则113
3.1.4.2 视图合并（view merging）116
3.1.4.3 查看用户定义的绑定变量122
3.1.5 开发者的作用123
3.2 执行计划的类型126
3.2.1 扫描的基本类型126
3.2.1.1 全表扫描127
3.2.1.2 rowid扫描132
3.2.1.3 索引扫描133
3.2.1.4 b-tree聚簇读取（cluster access）138
3.2.1.5 哈希聚簇读取（hash cluster access）139
3.2.1.6 采样表扫描（sample table scan）140
3.2.2 表连接的执行计划143
3.2.2.1 嵌套循环连接（nested loops join）143
3.2.2.2 排序合并连接（sort merge join）146
3.2.2.3 哈希连接（hash join）148
3.2.2.4 半连接（semi join）149
3.2.2.5 笛卡儿连接151
3.2.2.6 外连接（outer join）154
3.2.2.7 索引连接159
3.2.3 其他运算方式的执行计划161
3.2.3.1 in-list迭代执行计划162
3.2.3.2 连锁执行计划163
3.2.3.3 远程执行计划165
3.2.3.4 排序操作执行计划168
3.2.3.5 集合操作执行计划171
3.2.3.6 count(stopkey)执行计划174
3.2.4 位图（bitmap）执行计划175
3.2.4.1 各种条件运算符的位图执行计划176
3.2.4.2 子查询执行计划182
3.2.4.3 与b-tree索引相结合的执行计划184
3.2.5 其他特殊处理的执行计划185
3.2.5.1 递归展开（recursive implosion）执行计划186
3.2.5.2 修改子查询执行计划191
3.2.5.3 特殊类型的执行计划193
3.3 执行计划的控制203
3.3.1 提示的活用准则204
3.3.2 使用提示实现最优化目标206
3.3.3 使用提示改变表连接顺序207
3.3.4 表连接方式选择过程中提示的使用208
3.3.5 并行操作中提示的使用209
3.3.6 数据读取方法选择中提示的使用211
3.3.7 查询转换（query transformation）过程中提示的使用214
3.3.8 其他提示216
第4章 构建索引的战略方案221
4.1 索引的选定准则222
4.1.1 不同类型表的索引应用准则223
4.1.2 离散度和损益分界点227
4.1.3 索引合并和组合索引的比较229
4.1.4 组合索引的特征232
4.1.5 组合索引中列序的决定准则239
4.1.6 索引选定步骤242
4.2 决定聚簇类型的准则263
4.2.1 全局性聚簇263
4.2.2 局部性聚簇265
4.2.3 单表聚簇266
4.2.4 单位聚簇大小的决定267
4.2.5 确保聚簇被使用的措施270
第2部分 最优化数据读取方案
第5章 局部范围扫描（partial range scan）274
5.1 局部范围扫描的概念276
5.2 局部范围扫描的应用原则281
5.2.1 局部范围扫描的条件281
5.2.2 不同优化器模式下的局部范围扫描284
5.3 提高局部范围扫描执行速度的原理285
5.4 向局部范围扫描引导的方法289
5.4.1 利用访问路径实现对sort的代替289
5.4.2 只使用索引的局部范围扫描292
5.4.3 min、max 的处理293
5.4.4 filter型局部范围扫描298
5.4.5 rownum的灵活运用300
5.4.6 利用嵌套视图的局部范围扫描306
5.4.7 利用函数的局部范围扫描308
5.4.8 利用查询语句二元化特性的局部范围扫描316
5.4.9 web留言板中的局部范围扫描318
第6章 表连接的最优化方案336
6.1 join和loop query的比较339
6.1.1 全部范围扫描方式下的比较341
6.1.2 局部范围扫描方式下的比较349
6.2 连接条件状态对表连接的影响351
6.2.1 连接条件正常353
6.2.2 连接条件一边异常358
6.2.3 连接条件两边异常361
6.3 各种表连接方式的特征及活用方案365
6.3.1 嵌套循环连接366
6.3.1.1 嵌套循环连接的基本概念367
6.3.1.2 嵌套循环连接顺序的决定370
6.3.2 排序合并连接379
6.3.3 嵌套循环连接和排序合并连接的比较383
6.3.4 哈希连接（hash join）387
6.3.4.1 in-memory哈希连接392
6.3.4.2 延迟哈希连接395
6.3.5 半连接（semi join）398
6.3.5.1 半连接的概念和特征399
6.3.5.2 半连接的执行计划401
6.3.6 星型（star）连接417
6.3.7 星变形（star transformation）连接425
6.3.8 位图连接索引436

.　　本书将整体内容分为了两个部分，在第1部分中以影响数据读取效率的所有要素为类别，对其各自的概念、原理、 特征、应用准则，以及表的结构特征、多样化的索引类型、优化器的内部作用、优化器为各种结果制定的执行计划予以了详细说明，并以对优化器的正确理解为基础，提出了对执行计划和执行速度产生最大影响的索引构建战略方案。
　　在第2部分中主要介绍提高数据读取效率的具体战略方案。在这部分中，介绍与数据读取效率相关的局部范围扫描的原理和具体应用方法，以及对被认为是提高数据库使用效率基础的表连接的所有类型予以详细说明。
　　在第1部分的第1章中，主要对数据库在存储数据时所使用的基本存储结构进行详细说明。就像人类无法生活在水中，鱼类无法生活在陆地一样，结构上的特征对很多方面都有着根本性、决定性的影响。尽管不同的DBMS所使用的术语有所不同，但是当我们依据其本质进行分类时就会发现所有表现出来的形式都属于同一种类型。
　　在第1部分的第2章中，主要对优化器制定执行计划影响最大的所有索引类型进行详细说明。在此所涉及的索引类型有被广泛使用的最一般的B-Tree索引、在海量数据处理或数据仓库中能够获得较好效果的位图索引、基于虚拟列所创建的多样化的用户自定义函数索引等。
　　在第1部分的第3章中，主要对优化器进行深刻剖析。在此不仅介绍优化器在实现最优化操作时所执行的内部执行步骤，还对作为数据库处理数据步骤的执行计划的各种类型进行了分类说明。如果各位读者能够对各个具体的执行单位有一个很好的理解，那么仍然能够对将其组合在一起的整体执行计划有一个很好的理解。另外，为了引导优化器按照我们所期望的方式制订执行计划，又对各种类型的提示（Hint）进行了说明。
　　在第1部分的第4章中，非常具体地提出了对制订最优化执行计划有着非常大影响的索引构建战略方案。优化器并不能开辟出新的读取路径，而只能在现有的读取路径中选择出比较有效的路径。因为按照本书中所提出的索引构建战略方案所构建出的索引能够改变现有的读取路径，所以如果没有依据此方案来构建战略性的索引，那么数据的读取效率必然会在很大程度上受到影响。
　　在第2部分的第5章中，以对执行计划的正确理解为基础，通过具体事例，对只读取了部分数据就能获得结果的秘诀——局部范围扫描的原理和多样化的应用类型进行了详细说明。在这里从一个新的高度对前面所介绍的方法进行了扩充说明。最后对在各种比较流行的留言板中实现局部范围扫描的方法进行了详细说明。
　　在第2部分的第6章中，对表连接的所有类型进行了详细说明。在这里对作为传统型的表连接方式——嵌套循环连接和排序合并连接，以及能够有效实现海量数据连接目的的哈希连接的相关原理进行了彻底剖析，并提出了多种灵活运用准则。另外，又对以多样化类型出现的半连接和在数据仓库中必须要使用的星型连接，以及星变形连接进行了详细说明。最后附加性地提出了位图连接索引的基本概念和灵活运用方法。
　　在这里向各位读者郑重承诺，我将在尽可能短的时间内完成其他两本系列书籍的编写工作。由于我经常在读者所期待的时间内未能出版约定的书籍，也许各位读者对我如期完成这两本书并不抱太大的希望，所以在这里希望各位读者能够谅解。我在管理自己企业的同时，既要研究新的技术，又要提供解决方案和编写书籍，时间的不足真的让我窘迫和无奈。
　　由于这两本书会同时在国外出版发行，所以不论我被多少琐事所困扰，都必须在约定的时间内完成编写工作。因此，这次我可以在这里向各位读者郑重承诺，在本书出版发行后我会以最快的速度完成这两本系列书籍的编写工作。
　　只凭借对方法的理解是无法征服数据世界的，即使将本书已经阅读了数十遍也只不过是停留在对其表层内容的理解上而已。所以希望各位读者能够对自己提出更高的要求，不要停留在对表层内容的理解上，而是以对本书中所介绍的所有原理的正确理解为前提，以本书中所提供的案例为参考，在适当的实际案例中加以灵活运用。我希望各位读者能够通过自己的努力和奋斗，发现别人所不能发现的新世界，而不是仅将自己局限于众人都能够看到的世界里。要勇敢地去挑战自己的极限，走向更大的成功。
　　2005年12月13日
　　EN-CORE CONSULTING
　　代表咨询师 李华植
　　他山之石 可以攻玉
　　----《海量数据库解决方案》校订手记
　　经过三个月的艰苦努力，我和张乐奕（Kamus）、崔华（Dbsnake）最终完成了《海量数据库解决方案》的校译工作。能和两位好友一起字斟句酌、逐字逐句地将韩国同人的名作校译引入中国，于我们于书都是一种缘分与机缘，在校订过程中恩墨科技的罗晓程也协助我们做了大量的文字审阅工作，在此致以深深的谢意。
　　在各位读者开始阅读本书之前，我们将接触、接受、校译这本书的感触与来龙去脉记录一下，供大家参详。
　　Eygle —— 推动技术交流分享是一件功德
　　最早接触到这本书是在2009年，韩国EN-CORE公司的朋友找到我，希望我能够帮忙审阅并做些推荐，当时我正在新华社进行一个项目实施工作。
　　我当即表达了自己的几个观点：第一，如果是一本好书，我乐于阅读并做评荐，这是我的荣幸；第二，凡是促进技术交流与分享的事情，我都乐于支持并做出力所能及的工作；第三，我愿意义务地去做这样一件事情。
　　韩国朋友非常愉快地表达了对我的谢意，并向我介绍了这本书：在韩国数据库界，该书的作者李华植是教父级的人物，而该书更是圣经般的读物，有累计几十万册的销量，读者不仅仅是数据库从业人员，各类技术人员都将之奉为经典和必读。
　　我相信了他们的说法，并且向韩国同人表达了敬意。所有坚持不懈、执著于行的人，都值得我们尊敬。而如果能够促进亚洲数据库界的一些交流，那也是一件功德。
　　就这样我欣然答应了他们的请求，并期待看到这样一本书的出版。
　　当我拿到书稿时，一些新的问题出现了，我发现原译文太注重韩文的语言习惯，对于中文读者，阅读起来会非常吃力，甚至会出现难于理解的局面。我建议他们做出进一步的修订，否则很难传达出作者的本意。基于双方的理解，他们诚挚地邀请我来完成这个审较工作，而经过慎重考虑之后，我认为一个人还不够，我需要一个团队，张乐奕和崔华成为了我的伙伴，这个团队通过了他们的考察，就这样，我们接下了这个比想象的还要艰辛的工作。
　　从原译的传达，去理解作者的本意，这本就是隔了一层，再加上韩文和中文的语言习惯不同，修订的工作极其艰苦，经常每个小时只能完成2~3页的校对修正，然后我们三个人还要交叉校订。这期间的小插曲是，由于张乐奕是日语专业出身，他能够从该书的日文版借鉴不少东西，互相佐证。
　　就这样，三个月的时间转瞬即逝，我们的工作也已经接近尾声，我可以说的是，我还从来没有这么认真、字斟句酌地去读过一本书，而且是反反复复地阅读，这样阅读的一个好处是，我对这本书的理解和领会比任何其他一本书都要多。
　　书稿在手里就没有完美的一刻，我们还在不停地修正，直到出版前的最后一刻，我们真挚地希望能够有更多的读者喜欢它。虽然这期间我们已经尽了最大的努力，但是我们仍然不知道读者会如何评价，所以我一直心怀忐忑。
　　关于这本书，可以说的是，我从中学到了很多东西，作者的很多理念让我受益匪浅，这些学到的东西将会指导和影响我以后的学习之路。
　　首先这本书并不是仅仅写给数据库从业人员的，作者期望所有对数据库感兴趣的读者都可以流畅地阅读、透彻地理解。所以，作者在本书中通过大量的类比、比喻将艰深的数据库知识与生活对应起来，使得平时很多不易理解的概念变得浅显易懂。基于深刻的积累，作者能够从不同角度对技术进行概括和阐释，往往有让人豁然开朗的别样感觉，比如在讲到局部范围扫描时，作者用排队等车用户的顺序以及出租车的出发时间进行类比譬喻，精到而浅显，任何人都可以一目了然地理解后面蕴含的复杂技术原理。这或许就是作者的本意，技术原本就是对完美生活的引申与抽象。
　　又比如在战略性索引构建一章，作者提到“只要为各个索引分配合理的任务，即使需要创建大量的索引也应当果断地作出决定”，为索引指定任务使得索引拟人化地变成了一个工人，有明确任务而不是平时我们茫然地创建索引。作者依据这样一个思想展开了整章的内容，这也和我们的优化思路不谋而合，优化到极致的数据库，我们应当知道哪些SQL查询会使用到哪些索引，而索引又是为哪些查询服务的，必须详尽了解数据库与应用，才能对应用系统了如指掌、有的放矢。
　　读这本书，我们更多的是去理解作者高屋建瓴的数据库设计与优化思想，而不应该拘泥于具体的技术细节，比如作者所说的局部范围处理、战略性索引构建等，这些概念更多的是将细节的技术原理上升到生活道理与常规的思考，原本很多复杂的技术设计都是可以源自生活中浅显的道理，将技术、生活与常规的思考联系贯穿起来，在我看来，是作者带给我们的最大教益。
　　最初的一句承诺，导致了数月的锲而不舍，这期间的艰苦也让我们每个人都有所收获，当然更大的收获是我们几个朋友之间的友谊；感谢作者李华植带给我们的经典作品；感谢译者郑保卫，正是他的初始翻译才使得本书的中文版得以和广大读者见面；感谢博文视点的张春雨，他坚持不懈的沟通与推动促成了本书的最终出版。
　　愿这本书能为大家带来一些与众不同的感觉与收获！
　　盖国强
　　2010年7月22日星期四
　　Kamus——书读百遍其义自见
　　在今年（2010年）一月份的时候，Eygle跟我说有一本韩国IT届教父级的人物撰写的在韩国狂卖数十万册的数据库技术书籍，出版社希望引进到中国来。而这本韩文书已经有了初始中文译本，只是这份中文译本需要一些更熟悉Oracle数据库技术的人来进行再次修订。当第一次听见这个事情，我以为那就仅仅是校对，对于错别字的校正；对于技术术语把握的问题，我没有想到在真正开始着手以后会是如此的困难。
　　时间过了两个月，到了今年的3月份，正式拿到书稿，当开始修订我负责的第3章时，才发现这是一项巨大的工程，并不能说初始翻译不好，实际上已经很不错了，技术术语基本上也都准确，但是整段整段的句子读下来，却发现读一遍不明白在说什么，读两遍仍然似懂非懂，读三遍可能才知道，哦，应该是这个意思。而第3章是占全书比例最大的章节，有一百五十多页，而即使我全神贯注地去修订，进度也仅仅能够达到一个小时两到三页。之前我工作的环境是在客厅，前面是电视机，而为了修订这本书我不得不将工作环境转移到书房，因为哪怕是一点点声音的干扰也会让进度更加缓慢。这是我之前没有遇到过的情况，我一向自诩可以一心多用，但是修订这本书我遇到了极大挫折。究其原因，应该是初始翻译有不少是通篇大量同词语替换的情况，很多的修饰词都不符合中文的语言特点，而这些修饰词极大地干扰了阅读体验。另外一个重要的因素就是李华植先生在写作这本书的时候，对于很多他想极力阐述给大家的观点都辅以了大量的比喻，用出租车、用运动员、用下棋……而这些比喻的生动让阅读者会情不自禁地将自己代入这个环境，去仔细琢磨这个比喻的后面想表达的真实含义。
　　为了能够更准确地理解李华植先生原文的意思，我甚至找来了本书的日文译本出版物（我大学本科学了四年的日语），在我实在不明白原中文译本的含义时，我会去对照日文是如何翻译这段的。有趣的是，通常这很有效果，我甚至根据日文译本在中文译本中添加了一些文字（也许是原中文译本遗漏了），以便于读者能够更好地理解文章含义。
　　很令人欣喜的是，在修订的后期我已经能够逐渐跟上李华植先生的思维，甚至对于他的比喻已经心有戚戚，修订的速度也得以提高。更令人欣喜的是，如此字斟句酌地阅读李华植先生的这本著作，让我在Oracle数据库性能优化的思想和策略上都学到了很多东西。“书读百遍其义自见”很能贴切地描述修订这本书的过程。
　　我、Eygle和崔华在三个月中交叉修订，我修订完的第3章eygle会再次修订一遍然后传递给崔华，崔华再阅读一遍，同样Eygle修订完的第4章会给我再重新阅读。我们如此努力，只是希望在最后这本书呈现在大家面前的时候，是一本符合中文阅读习惯的、不需要再像我们这样费劲就能够有所收获的数据库技术书籍。这是辛苦的三个月，但同样是很有意义的三个月。
　　对于每一位能够将自己的经验写下来分享给读者的作者，我都深深敬佩。我个人虽然一直没有这样的耐性坐下来去真正写一本书，但是我也一直在努力创造一种乐于分享、收获快乐的环境，创办Oracle中国用户组(www.acoug.org)，每个月举办免费的活动，邀请演讲者来做技术分享，我一直在努力做自己力所能及的事情。
　　最后，即使我们如此修订这本书，一定还会有疏漏的地方，甚至是词不达意或者难以理解的部分，希望读者朋友们能够包容。但是更重要的一点是，在你觉得无法理解的时候，歇一段时间再去读第二遍、第三遍，要知道在我们修订的时候也是这样，“书读百遍其义自见”。
　　张乐奕（Kamus）
　　2010年7月4日
　　Dbsnake——循序渐进始有成
　　三个多月的时间一晃就过去了，我们也终于完成了《海量数据库解决方案》的修订工作。
　　当初Kamus打电话找我，问我是否有兴趣跟他和Eygle一起去修订一本韩国书的时候，我几乎是不假思索地马上就答应了，当时其实我并不知道要修订的是什么书，也不知道具体的工作量会有多少。满口答应只是因为这是Eygle和Kamus找我——我没有理由拒绝。
　　修订这本书的时候恰逢我跟进的一个项目上线，白天项目的事情已经是忙得焦头烂额了，修订的工作只能够放在晚上做。等到我真正开始修订的时候，才发现工作量真的是太大了，因为几乎是一直处于一种字斟句酌的状态，所以修订的进度非常缓慢，我常常是一个小时才能修订两到三页。怎么办？我怎样才能提高修订的速度，以至于不耽误整个团队的进度？没有别的办法，我只能压缩自己的睡眠时间，于是每个工作日我基本上都是12点左右入睡，早上5点半起床，就这样坚持了三个多月。
　　现在回头想想，我为什么能够坚持下来？除了要信守我自己的承诺之外，另外一个很重要的原因就是我对Oracle数据库太感兴趣了，再加上这本书确实是一本难得的好书！我在仔细修订这本书的过程中已经感觉到了自己的进步，这真的是一件令人非常兴奋的事情！
　　常常有朋友问我如何才能学好Oracle？我这里想说的是我也不知道该如何才能学好，因为Oracle我也只懂一点点。但是当我看到李华植先生将其20年的数据库经验毫不保留地写在《海量数据库解决方案》中的时候，我觉得我还是应该把我的一点经验写出来，这样也许就能够帮助更多的人。
　　现在回想起来，我的Oracle入门过程大致分为四个阶段。
　　第一阶段：从2004年到2006年8月，我用了大概两年多的时间断断续续地看完了OCP 9i的一套培训教材（一共4本书）。很惭愧，用了两年多的时间才看完。但是大家要理解我，我本科和研究生都是学数学的，2004年以前连最基本的SQL都不会写，而且那段时间项目的开发还是有一定的工作量的，我基本上只能够利用业余时间自学。
　　第二阶段：从2006年8月到2008年年初，因为那时候我的Oracle已经有了一点基础，所以我开始大量地看Oracle的各种官方文档，但是这些文档我大都只是过了一遍，唯一的例外就是《10gR2 Concepts》和《Oracle 10gR2 Clusterware and RAC Administration and Deployment Guide》，这两本书我都分别看过两遍。
　　第三阶段：从2008年年初到现在，我开始在metalink上大量阅读文章，在我真正开始接触metalink的时候我才发现，哇塞，这是多么精彩的一个世界！在我看来，metalink就是最好的老师了！直到现在，我工作的第一件事情依然是把metalink打开，平常没事就泡在上面，迄今为止，我已经在metalink上看过超过1500篇文章了。
　　第四阶段：从2009年3月到现在，我开始仔细阅读DSI（Data Server Internals）教材。DSI其实我看的并不多，迄今为止，只看过了如下几本：
　　DSI303-Advanced Backup,Restore and Recovery Techniques
　　DSI401-Dumps Crashes and Corruptions
　　DSI402-Space and Transaction Management
　　DSI402e-Data types and block structures
　　DSI403e-Recovery Architecture Components
　　DSI404e-query_optimizer
　　DSI405-Performance Tuning
　　总的感觉是DSI没什么，真的没有我想像得那么难。但是这里我想说的是DSI应该在你具有一定的基础后才开始看，早看反而无益！
　　前前后后六年的时间，当我看完DSI405后，我真的觉得自己的Oracle已经入门了。其实细心的朋友已经可以发现，我的Oracle入门过程用一句话来概括就是“循序渐进”。
　　当我看完DSI系列并且在我的个人网站（www.dbsnake.com）上撰写了100多篇文章后，终于迎来了属于我自己的机会——我结识了Eygle和Kamus，并且有机会和他们一起开始迎接许多梦寐以求的挑战。
　　一直以来，Eygle和Kamus都是我努力的目标，修订的这三个多月虽然辛苦，但是能和自己的知音益友一起做事情，于我而言是非常荣幸也是非常开心的事情，再辛苦又算得了什么？
　　这次我修订了第1部分的第1章、第2章和第2部分的第2章，交叉修订了第1部分的第3章。在修订过程中，我付出了大量的努力，以自己所学、所知去理解并传达作者的真知灼见。然而再怎么尽心竭力，我们的工作也难免存在种种不足，但是我们确确实实已经尽力，剩下的只能交给读者去评判吧。
　　虽然这次修订的过程是极其痛苦的，在殚精竭虑之后常常会感觉很崩溃；但是如果能有机会让我继续修订《海量数据库解决方案》的后续书籍，我非常愿意再多崩溃几次。
　　崔华（dbsnake）
　　2010年6月29日
　　好了，这就是几位校对者的心声，现在这本书已经翻越了山川、民族与语言的障碍，来到中国读者的面前，让我们一起来阅读和领会一下来自亚洲数据库界的声音吧！