Oracle排序算法

12 30th, 2009 | Posted by jacky | Filed under 大话技术

大牛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:

select sortcode
from t1
order by sortcode;

select  sortcode
from (
select sortcode
from t1
order by sortcode
) where rownum <= 10;

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的实验的猜测,所以大家别较真。对于排序算法本身,我的描述并不一定正确,欢迎大家批评指正。

–EOF–

标签:
  1. P.Linux
    12 30th, 200918:12

    应该先顺序取需要的条数建立好初始堆,然后才能开始调堆的算法吧。例如要取前10条,那么就是先顺序扫描10条记录建立初始堆。取N个数据的话,每次调堆的代价是logN,如果运气不好开始入堆的都是最大的,那么几乎每次拿一个数来都要调堆,如果一共M条记录,最终是M*logN,对比全排序的M*LogM,运气最不好的情况小效率还是有点差。
    当年我们设计一个算法是利用快排的算法,随机一个比较元素MID,然后按快排的方法分堆,但不排序,这样我们可以处理只要中间或者前部或者后部几乎一个无序数列中任意一段而不用全部排序。例如我们要M个数中前N条,我会通过二分,直到左侧的元素少于N的2倍,就对这部分开始排序。通过随机中间比较元素,基本可以达到左右两侧数字数量相近,避免了堆在不改变输入顺序的情况下殊数据可能导致的大量调堆操作,算法复杂度近似于O(M+M/2+M/4……),约等于O(M)数量级,最后剩余不到2*N条记录时进入排序,2*N*log(2*N)复杂度。最终复杂度O(M+2*N*log2*N),N很小的话近似于O(M)了,内存峰值消耗M/2(第一趟可以分批载入硬盘数据),然后每次筛掉约1半。不过这种方法也只有在比赛中用了,只有在比赛中会有专门针对问题设计的变态数据让算法效率急剧下降。

  2. jacky
    12 31st, 200909:51

    堆排序是必须预先建立好堆,取出数据的过程是堆不断减小的过程。其实Oracle内排序的算法,我们并不确定,也许是冒泡法:)

  3. jacky
    12 31st, 200909:53

    另外一个疑惑是,Jonathan怎么知道Oracle是用二叉树结构的?从实验数据上无法推断。

  4. P.Linux
    12 31st, 200910:07

    从数量级上可以判断,排序算法分为2派,基于比较和不基于比较。不基于比较的排序存在基尔排序、基数排序、桶排序等,效率一般在线性O(N),但是都有局限性,像桶排序一般只用来实现数值震荡很小的排序,利用的是为每个数建立一个桶,记录下每个数出现多少次,然后根据次数输出。基于比较的也分为2类,树形处理和线性处理,树形处理包括快排、平衡树、归并排序、堆排序等等,效率平均为O(NlogN)这个数量级;线性处理的就是冒泡、插入排序、选择排序等,效率在O(N^2)数量级。
    不过只要是基于比较的排序,本质上都是一刻树,只是线性处理就变成一颗偏树了,数组本身就是树形结构的偏数特例,快排就是很容易退化到偏数的一种排序,所以经常用随机数当中间数才能保证效率平均在O(NlogN)。
    黑盒测试一个排序用的是那种算法,就可以采用基准比较。首先测试出当前处理器单位时间能处理的数量级O(M),然后用N个数据测试算法,看最终处理耗费单位时间P,用P*O(M)就能得出处理的数量级,看近似于O(N),O(NlogN),O(N^2)哪个,就知道是哪种算法了。
    一般不是图写的方便的话,都是会采用树形结构来排序的,尤其是大数据。

  5. jacky
    12 31st, 200910:47

    关于算法,我都忘得七七八八了。Oracle应该是基于比较的排序,所以我猜测Oracle的内排序算法是快速排序。

  6. lihan
    1 6th, 201022:54

    看起来好像是经典的topk算法?算法导论里的经典解法是用了快排

  7. baikaishiuc
    4 14th, 201010:14

    1L说的是对的,这是得出大批数据中小部分按序排列的最好办法了。

    大学的数据结构中假如认真看,就有对这个的分析。

    但是快排很容易被针对性的数据击毁。

    Doug McIlroy’s 1999年的论文r“A Killer Adversary for Quicksort” (http://www.cs.dartmouth.edu/~doug/mdmspe.pdf)有描述这个玩意。

  8. baikaishiuc
    4 14th, 201010:34

    纠正下我自己说的:

    1. 1L说的方法是我自己已知最好的
    2. 我所知道的排序都容易被针对性的数据击毁,貌似还没有万金油出现

  9. P.Linux
    5 4th, 201018:54

    @baikaishiuc 利用中间数的随机,可以有效的避免的针对性数据的冲击,因为中间元素无法预知,也就没办法涉及针对性的数据了。