本文为本人在阅读由Goetz Graefe所著 《Executing Nested Queries》一文的读书笔记 。本文主要讨论了数据库中的一个重要问题，执行效率的问题：如果有效的提高系统的效率，尤其是执行效率。而在数据库执行过程中，对于嵌套循环查询的的处理，又是整个执行效率的瓶颈所在。因为，对于MergeJoin或者是HashJoin等我们可以利用Merge或者Hash操作来加速相应连接操作的执行效率；但是对于嵌套循环连接的处理则较为复杂。例如：对于内表有无索引，是否已排序等有着不同的处理策略。而本文正是从这些方面来讨论了嵌套循环查询的处理。通过从不同的角度来分析如何提高嵌套循环查询的执行效率。例如：从IO操作方面，Cache方面等等。

通常情况下，B树索引的时间与数据库的大小成对数关系。 即： travel-b-tree-time = O(lgSize). 这里Size为数据库的大小。

同时在执行表扫描的时候，由于操作系统的会将每次执行IO操作时候将buffer给清除掉，因此为了能够提高效率的话，我们需要操作系统能够理解我们之前所进行的IO操作。 大规模的scan的话，会极度影响到性能，因为每次重复的会将相应的缓存清空，使得缓存的作用减少。即：对于CPU中的Cache-Level-1甚至到Cache-Level-3中的数据进行清查，从而使得Cache所带来的优势全部消失殆尽。 即：数据的局部特性所带来的收益将会被严重的消除。

因此，基于上述的原因，在磁盘容量及磁盘带宽不断增长的情况下，对于物化的，索引化的视图已经成为现在主流关系数据库的通行做法。因此对于查询引擎的效率将取决于嵌套循环的迭代算法的效率。

相关的技术：
（1）Merged indexes for caching in nested iteration.
（2）How to manage batched correlation bindings in the outer and inner plans.

因此，我们详细的讨论了，数据流，控制流等对于查询引擎效率的影响。 上述这些技术的讨论有助于我们对于研究顺序执行或者并行执行的效率有个深入的研究。

那么又存在着哪些影响执行引擎效率的因素呢？

通常情况下，存在着如下形式的嵌套循环查询连接的算法：
（1）朴素的嵌套循环连接算法；Naive Nested Loops Join。
（2）块嵌套循环连接算法；这里又分为四类嵌套循环算法：两个属于outer-most循环迭代算法；两个属于inner-most循环迭代算法；

此时，IO操作的数量通过外表的连接参数大小来决定。 例如：对于每个外表输入数据块中的数据量。但此时的连接谓词的估值如同朴素的嵌套循环一样。当如果我们在对内表输入数据执行向前或者向后扫描时候，此时我们可以预见将会减少相应的IO操作，因为在执行向前或者向后扫描的时候，我们可以利用buffer的缓存特性。

除非内表的大小非常小，否则的话在实际的应用过程中，我们通常是使用索引嵌套循环连接算法（index nested loops join）。通常有些优化器会在，内表中不存在有效的（helpful）索引的情况下使用所谓的临时索引来，提供连接的执行效率。 这里我们对于索引的类型并不做严格的要求，因为无论是B-tree索引还是Hash索引还是其他类型的索引，只要该索引能够对于连接谓词中所给定的条件有着高效的支持即可（即：可以利用索引技术来高效的获取数据）。

对于一类特殊的案例：例如在实际的应用场景下，我们通常是通过参数绑定的方式来完成对于查询语句的绑定，在用户执行查询的时候，才会对该查询语句的相关参数进行绑定。此时，对于此类的案例我们通常会从（1）优化阶段；（2）执行阶段两个方面进行讨论。例如：类似于prepared语句的执行。

两个重要的概念：Convered query(全覆盖查询) 和Convering index （覆盖索引）。 Convered Query：当查询中的返回列，均是索引列时，即：返回列来自于一个或者多个索引列。 例如：

create table foo (
int a ,
int b
) ;

create index idx_a on foo (a) ;
create index idx_b on foo (b) ;

SELECT a FROM foo; 此时，我们成该查询为 Convered查询。
或
create index idx_all on foo (a,b) ;
select a,b from foo;

当然这些，返回列不仅仅限于上述的查询返回列，同样也包括任何在如下子句中的列： JOIN, WHERE, HAVING, ORDER BY. 通常我们认为convered查询语句具有更高的效率，毕竟查询语句可以利用其中的索引来获得高效的数据访问效率。

当对于一个大查询语句为全覆盖查询语句时候，嵌套循环迭代的方式相较于merge join或者是hashjoin有较大的优势。毕竟查询语句中可以利用全覆盖索引来加速查询语句的执行。

对于hash join在某些情况下，例如：当表中的数据大于buffer大小的时候，会导致系统无法使用使用由buffer所带来的收益，且hash join需要大量的内存，同样在执行hash join时候同样会为溢出文件产生大量的IO操作。 因为，作为hash join来说，在大数据量的情况下，我们很难保证我们的hash function产生均匀的hash 分布。

但对于两个已经完成预排序的基表，此时执行Merge Join将会获得较大收益，因为考虑到已排序的数据，我们可以利用其所带来的数据局部性，获得cache所带来的收益。

通常，研究表明在一个索引配置良好的数据库中，索引嵌套循环连接，mergejoin具有非常相似磁盘访问模式，且索引嵌套循环连接具有和mergejoin一样的高效性能。

异步IO并不仅仅限于顺序扫描操作。在朴素的索引嵌套循环的实现中，每个索引的查找已经数据的存取均在下一次迭代的启动之前完成。为了能够高效的利用磁盘，通常我们在系统中的将系统中的最少线程数保持与磁盘数一致。因为这样就不会有空闲的磁盘。因为磁盘是一个非常宝贵的资源。

如果我们对于索引嵌套循环连接能够正确的实现，则我们可以利用异步IO所带来的收益。例如：在IBM的产品中，会将为解析的记录封装在一起并将其保存在一个固定大小的列表中，当列表被装满后，同步启动IO。

通常情况下，稳定的IO操作的效率要优于突发无规律的IO操作。始终保持多并发的IO活动进给系统性能带来极大的收益。同时，我们也可以思考，随着现代磁盘技术的发展，传统的机械磁盘系统的变化对于数据库设计和实现所带来的挑战。

同样，即使是在多并发用户环境下，我们仍然能够通过减少锁的竞争来提高系统的吞吐量，虽然可能会由于多用户环境会造成资源利用率的增加，响应时间的减少等等。 例如：我们可以通过增加相应的工作线程来尽量的使用磁盘资源，但是并非是越多线程的数量与性能成正相关。当线程的数量到达到一定的数量后，线程数量的增加并不会提高系统的性能，反而会导致性能的急剧下降。 有可能的时候，我们依据CPU的数量来限制线程数量，从而能够将系统性能提高到一个叫合理的状态。

同样，异步IO的作用要优于多线程状态下的同步IO的性能。我们知道，过多的线程，将会导致线程在运行过程中过多频繁的上下文切换。而上下文的切换有是一个特别消耗系统资源的操作。 （由于系统会涉及到大量的寄存器数据拷贝，线程状态信息的拷贝以及系统态到用户态的切换等等）。进一步的讲，线程在切换前后，CPU的各级Cache中所缓存的数据将会被清洗，从而使得Cache的数据缓存作用消失。

虽然提高IO效率最为一个有效的提升数据库性能的一个有效方法，所谓“开源节流”，开源作为上述我们所讨论的一个手段；同样，节流所带来的收益同样不可忽视。Caching作为计算机系统中广泛使用的技术手段，其不仅用来数据访问的效率，而且还可以用来避免多余的IO操作。

Caching，文件系统或者数据库系统中的buffer均是避免过度IO的有效方法。 当我们在求解复杂的嵌套循环的时候，我们将结果缓存，会使得我们的求解过程获得极大的收益。即使，这些计算结果当前并未存在与IO系统的buffer，且需要更多的IO操作时候。因为，Cache系统实质上会比非缓存方案需要更少的IO操作，当我们需要重新计算Cache中的内容时候。

Caching系统，通常不仅可以避免重复的计算，同样可以避免由于需要进行相关IO操作而进行的重复的锁管理系统函数的调用。在进行Cache操作时候，我们只需要对Cache模块中数据缓存接口进行相应的上锁和解锁，使得我们锁的粒度变小，而锁的粒度又会极大的影响到数据库系统的整体性能。但同时带来的一个问题是，可能由Cache数据存取所带来的系能瓶颈，但是相对应IO所带来的瓶颈，Cache系统所带来的瓶颈具有更多的解决方案。

众所周知，当内查询不涉及到引用外查询语句中的对象时候，我们可以将内部中的数据进行缓存到cache中。因为由于未引用外查询块中对象，因此对于外查询块的数据不会影响到内查询块的数据。故而可以将内查询块的结果进行cache缓存。 此时，内查询相当于一个常量函数。此种方式最为简单且容易实现。 同时由于嵌套迭代时候，外查询的输出结果被严格的现在在一条单个记录行。因此，对于单条记录的caching操作似乎就显得不那么有效。

对于计算代价昂贵的用户定义函数（user-defined functions）与嵌套查询非常相近。由于两个用户定义函数可以进行相互调用，因此对于函数间的生命周期的界定有一定的难度。在理论研究和实际领域内，用户定义函数与嵌套查询有着不同的侧重点。首先，在代价估算方面，嵌套查询优于用户定义函数。嵌套查询基于数据库内部的统计信息；相反，对于用户定义函数，我们将无法使用数据库内的统计信息。其次，用户定义的函数的返回结果通常标量结果，例如：单值返回值；但是嵌套循环的返回值多为记录组的形式。

另外一个避免过度IO操作的方法为：物理聚集(Physical Clustering)。

对于视图的物化和索引可以看作是一种特殊形式的cache形式。 在现行的设计中，我们会将结果较小的基表进行物化处理，尤其是在处理嵌套循环连接的过程。例如：在PostgreSQL的优化处理过程中，会将相应的嵌套循环连接的内表进行物化处理。

由于我们在实现MergeJoin或是HashJoin的时候，均需要对原始数据进行排序操作。同时，对于已排序好的数据，系统也可以利用数据的局部特性（由于相同的数据处于连续的内存或磁盘空间上），来加速系统性能。

为了能够最大化的利用排序所带来的运行时系统代价的收益，我们需要将排序操作的实现与查询处理相关的操作相结合。前述查询的结果将直接作为后续排序操作的输入数据直接输入到排序操作中。只有在我们需要将排序的中间结果写入到运行时文件时候，我们方才进行IO操作。这样使得我们在查询执行的过程中大部分的操作均在内存中完成，从而能够大大的减少IO操作所带来的由于磁盘读写带宽所带来的瓶颈。

我们知道在Pg的索引创建过程中，首先会将数据进行排序并将其保存在BTBuildState中的spool/spool2中，然后由spool2中取出数据并建立索引，由于我们所进行的数据排序通常数据量较大，故而多采用外排形式进行，我们知道外排操作需要进行大量的IO读写操作。因此如果改进排序算法也是我们对于系统优化的一个努力方向。 同时，我们对已排序的数据进行索引创建，或者索引查找的时候，我们都可以利用数据的局部特性。

我们知道，对于外部的Merge Sort其代价是非常高昂的，为了能够已更加高效的方式来处理外部Merge Sort操作，我们采取分批的方式进行处理。

为了能够在执行的过程中保持中间结果的在查询计划内的稳定性，基于等级的优先级队列的替换选择排序算法将是一个优于“读-排序-写”这样流程的快排算法。虽然，选择排序的运行时间可能会长与快排。

在分布式内存并行数据库中，通常对内查询进行并行执行。 在并行执行的过程中，首先会遇到如下几个问题：

（1）跨线程，进程甚至是机器范围的通信，而该通信的代码确实异常昂贵的。因为，在此过程中，涉及到数据的封装，解封，以及通信线程的调用，操作系统对线程间的调度问题。而这些操作的代价均是异常昂贵的。同时，由于线程多线程（多进程）环境，同样会涉及数据竞争，进程等待等等问题。因为，一旦发生线程的切换，其上下文必然发生变化，从而导致CPUcache中的数据发生冲洗现象，这点对于高性能尤为关键。

（2）消费者线程的参数绑定以及生产者线程的执行。（此处的消费者-生产者模型为我们在构建嵌套循环连接时候所采用的一种架构模型，其基于数据流的模型而构建）。此类模型下，需要我们特别注意的是对于消费者线程与生产者线程数量的匹配度，我们需要将生成者与消费者的数量之间的比例控制在一个合理的范围内，否则容易造成线程数量的爆炸式增长。