Oracle的排序算法
[English]
作者：
fuyuncat
来源：
www.HelloDBA.com
分享到
在进行SQL查询时，排序操作是在特定的内存中完成的，也就是排序工作区。初次进入排序区的数据是无序的，Oracle要选择一项合适的算法对这些无序数据进行排序。
在10g之前，工作区是固定分配的（sort_area_size设置）。除非在会话中重新设置，所有会话都只能分配相同大小的排序区。因此，这就决定了排序区大小通常不能太大。而也就成为Oracle选择排序算法的重要因素————空间复杂度小并且稳定。而在所有已知排序算法中，空间复杂度最小的算法为插入排序、选择排序和堆排序，复杂度为O(1)，但是选择排序和堆排序都具有不稳性，因此最终选择插入排序。
插入排序的实现也比较简单：
1、将数据逐个从无序数据集中取出，放入有序数据集中的合适位置；
2、有序数据集以特定数据结构组织，如链表、阵列等；在Oracle中，则是平衡二叉树。但是，插入排序的效率并不理想，其时间复杂度为O(n^2)，这使得在进行排序时，CPU的消耗也会比较高。我们称这一算法为版本1的算法。
在10g以后，对私有内存的管理发生了很大的变化。不仅PGA本身能灵活伸展，工作区的管理和分配也变得非常灵活。例如，在默认情况下，2G PGA允许会话的工作区大小从204k到40M之间伸缩。如此灵活的工作空间，使得Oracle选择效率更高的排序算法成为可能。
我们知道，在所有基于比较的排序算法中，效率最高的当属快速排序了（时间复杂度为O(n Log n)）。但是，快速排序无论是在时间效率还是空间效率方面，都属于一种不稳定的排序算法。因此，为了弥补它这方面的不足，很多研究人员会将它与其他一些排序算法（通常是一些非基于比较的排序算法）结合起来，在降低算法的不稳定性的同时，又提高其效率。
在Oracle 10g中，也同样是引入了快速排序的改进算法，而与其混合的算法则是所有算法中时间复杂度最低的基数排序算法。
基数排序是一种非基于比较的排序算法，它是另外一种排序算法————桶排序的改进算法，对数据的排序键值有一定要求：
1、它首先要求所有数据排序键值具有相同长度，如果长度不同，则按照最长数据位数进行左补0对齐；
2、为获得稳定性，它还要求知道当前排序键值最大、最小值，从而确定“桶”的范围。基数排序算法的基本思想如下：
1、从左向右（或从右向左），逐个针对键值中的每位数进行排序；
2、按照当前排序的数字位构造出一批“桶”，按照大小顺序、每个桶盛放一定大小范围的数据，每条数据则由前排序的数字位放入相应的桶当中；
3、所有数据都放入桶中后，当前一轮排序完成，键值排序位递进一位，并以该位数据再对每个桶中的数据再次进行排序；
4、如此递归，直到完成最后一个数据位的排序；
5、将所有桶的数据拼接到一起。基数排序是一种稳定（已知键值范围情况下）的排序算法，它的时间复杂度为O(n*k)，其中k为排序键值的位数，也是影响其效率的关键因素。例如，与快速排序向比较，如果k<Log(n)，则其效率比快速排序高。
因此，Oracle在混合这两种算法时，充分利用各自的优势来弥补对方的不足：
* 利用基数排序来提高算法的稳定性；
* 利用快速排序来减少基数排序中的匹配位数；在解释Oracle如何做到相互弥补之前，先看下快速排序是如何实现的：
1、从数据中找一个轴心数，依据这个轴心数将数据集分为3个分区：小于轴心数的数据放左边、相等的放中间、大于的放右边（有些实现方法分2个分区，将等于的放在左边或右边）；
2、递归地对左、右分区进行划分，直到分区中的数据只剩1个；不难理解，快速排序的不稳定性在于其轴心数的选择：在最坏情况下（总是选到最大、最小值），时间复杂度会达到O(n^2)。为了降低不稳定性，Oracle的改进算法在选择轴心数时，会先对数据进行采样，选择采样数据中的中间值为轴心数。另外一项降低不稳定性的举措则是：不直接对左、右分区进行快速排序，而是对它们进行基数排序————因为在做第一次分区时，已经扫描过每一条数据，因此基数排序所需的先决条件在扫描完成后都可以满足。特别指出的是：键值数据是以字节形式存储的，即每位字节的范围是在0～255之间。也即是说，在基数排序过程中，我们只需要构造256个桶。
除此以外，在快速排序的分区过程中，还完成了另外一件重要的事：找到每个分区中最左边的相同字节数。如果分区中所有数据最左边的部分字节（假定为m位）是相同的，那么在进行基数排序过程中，这m位数据就可以被跳过，即其实际复杂度就可以降为O(n*(k-m))。同样，基数排序过程中，对桶中的数据再次递归排序时，不是调用基数排序方法，而是调用快速排序方法，以再次减少位数。
如此，两种方法相互递归调用，使得整体算法的不稳定性和时间复杂度都被降低。在Oracle中，这一新算法被称为版本2的算法。
以下是我用Perl脚本写的该算法的模拟过程：
SQL代码
- D:\Documents\HelloDBA.COM\scripts>perl OracleNewSort.pl
- unsorted data:
- [[ 50 5]
- [ 30 7]
- [ 33 15]
- [ 12 28]
- [ 30 53]
- [ 1 321]
- [ 123 32]
- [ 32 1]
- [ 212 3]
- [ 1 32]
- ]
- sorted data:
- [[ 1 32]
- [ 1 321]
- [ 12 28]
- [ 30 7]
- [ 30 53]
- [ 32 1]
- [ 33 15]
- [ 50 5]
- [ 123 32]
- [ 212 3]
- ]
代码可以在此下载：
http://www.Hellodba.com/Download/OracleNewSort.zip--- Fuyuncat ---