Oracle排序算法

大牛jonathan lewis在圣诞节出了一个小题目：Holiday Quiz

I have a table with one million rows, there are no indexes on the table. The table has a column called sortcode which has no nulls, and has been generated in a highly random way so that no value appears more than four times. Consider the following queries:

How many rows are sorted in each of these two queries - and roughly how much memory would you expect Oracle to use ?

从表面上看，两个SQL仅仅是返回数量的不同，因为没有索引，所以就算只返回10行，但是也必须完成整个排序过程，所以从排序的资源消耗上，两者应该没有太大差异。

Jonathan公布了答案：Short sort，主要是Oracle引入了一个针对sort的改进，即version 1 sort，大致原理是用一个二叉树来保存最终需要返回的记录，并且记录这个二叉树中最大的值，针对每个值逐一与这个最大值比较，如果大于这个最大值就直接丢弃（因为这里要寻找最小的10条记录），如果小于最大值，则插入到这个二叉树中去，最终返回这10条记录。因为普通的排序要返回所有记录，如果也采用这个存储方式，即用二叉树来存储排序的结果，可能非常耗费内存，所以这个改进只针对返回结果集比较少的情况。另外用二叉树，可以迅速的找到插入的位置，减少比较的次数。最后Jonathan还用三个极端情况来证明了这个排序算法的效果，正序，反序和随机，正序和随机时，因为大部分值都在第一次比较就被丢弃，所以占用内存和比较次数都很少；相反，如果是反序的情况，因为几乎所有的值都需要插入到这个二叉树中，占用内存和比较次数都大幅度增加，关于这个话题大家可以看Jonathan的博客，这里不再赘述。

我这里想讨论另外一个话题，Oracle到底采用什么排序算法？我查阅了很多资料，都没有提及。学过计算机的人都知道排序算法是一个古老而又有趣的话题，我们熟知的有：冒泡排序，选择排序和插入排序，这三种排序算法比较简单，但是效率不高。高效率的排序算法有：快速排序，堆排序和归并排序，我们下来大致介绍下这三个排序算法。

快速排序是采用分治法的策略，即分而治之，首选选取一个中枢值（一般选序列中的第一个数），每次规划将序列按照这个中枢值分成两个序列，左边的序列都比中枢值小，而右边的序列都比中枢值大，一次规划完成后，中枢值找到了其最终的位置，并且将原有序列分为两个部分，然后再用同样的方法分别处理这两个序列，直到排序全部完成。快速排序是一种效率很高的排序算法，如果采用原地分割的算法，快速排序占用很少的额外空间。

堆排序有点类似于插入排序，但是他利用了堆积树（堆）这种数据结构，堆积树其实就是一棵完全二叉树，但是又满足堆属性：子节点的属性总是大于或者小于其父节点，即所谓的大根堆和小根堆。排序的过程实际上就是把数据不断插入到堆积树上，而返回排序结果的过程就是不断取堆的最大（大根堆）或者最小值（小根堆），并不断缩小堆的过程。

归并排序就是将两个或多个有序的序列合并为一个有序序列的排序过程，称为两路归并排序和多路归并排序。归并排序的算法是在每个有序队列上设置一个指针，通过不断移动指针，在每个序列上取出元素进行比较，并合并的过程。归并排序通常使用在外部排序中。

内排序和外排序，内排序指在内存中完成的排序过程，外排序指排序内容无法在内存中一次完成，而需要借助外部存储来完成排序的过程。

根据Jonathan的实验，我们可以看到上面这个排序优化的例子，实际上利用了堆排序的特性，但是由于堆积树本身需要额外的空间，在返回记录数很多的情况下，并不适合，实验也证明，如果采用堆积树来保存所有记录，需要占用更多的空间。关于Oracle的排序算法，虽然不是很明确，但是很可能是快速排序的一种，因为快速排序占用稳定的空间，通常情况下可以提供很好的效率。如果排序无法在内存中一次完成，Oracle需要借助Temp空间，这就是外排序，Oracle使用多路归并排序算法，按照排序区大小把结果集切分成多个子集，每个子集在内存中完成排序，然后将他们合并起来。排序区大小对归并排序的性能影响很大，排序区应该能至少容纳每个子集中的一条记录，否则性能会急剧下降。

Oracle的排序算法我们并不了解，以上内容很多也是基于Jonathan的实验的猜测，所以大家别较真。对于排序算法本身，我的描述并不一定正确，欢迎大家批评指正。