Sort节点概览
排序的朴素含义是将一个数据集按照某种特定的排序方式进行排列的算法，最常见的排列方式是数值顺序和字典序。排序算法的应用非常广泛，主要分为了两类：
内排序：在内存中完成的排序，常见的有插入排序、快速排序、堆排序、基数排序等。外排序：数据集过大，内存中无法全部存放，需要借助外存的排序，常见的有归并排序的各种变形。gpdb的排序节点会根据查询计划中的排序键对指定的元组进行排序，根据排序的数据量和其他的一些性质，gpdb会选择不同的排序算法：如果排序节点的工作内存可以容纳所有的元组时，排序节点使用快速排序或者堆排序。其中堆排序主要用于TopK查询，即只需要输出排序后元组的前K个，例如Sort节点之上还存在Limit节点。如果工作内存无法容纳所有的元组，则使用基于归并排序的外排序算法。排序节点除了本身对元组排序的功能外，在gpdb中的应用也广泛，查询优化器还会根据代价选择基于排序的聚集节点GroupAgg和连接节点MergeJoin。
此外，GroupBy，Distinct等sql关键字也和排序息息相关。
TupleSortTupleSort是gpdb各种排序功能的底层实现，各种需要排序的模块都会调用TupleSort对元组进行排序。TupleSort使用的排序算法如下所示：
其中，快速排序和堆排序都是标准的内存排序算法。
快速排序
快速排序（QuickSort）是最常见的内存排序算法，由TonyHoare在年发明。
快速排序的三个步骤：首先，挑选基准值，从数据集中挑选出一个基准元素，一般称为Pivot分割；接着，将所有比pivot小的数据放到pivot之前，比pivot大的数据放到pivot之后递归子序列；最后，使用递归将小于pivot的子序列和大于pivot的子序列分别进行排序。
gpdb中对于快速排序的实现如下：代码位置：
