本节继续介绍排序的实现,上一节介绍了ExecSort,本节介绍该函数中调用的排序的具体实现函数,本节是第一部分,包括tuplesort_begin_heap/tuplesort_puttupleslot.

### 一、数据结构
**SortState**
排序运行期状态信息
```

/* ----------------
 *	 SortState information
 *	 排序运行期状态信息
 * ----------------
 */
typedef struct SortState
{
	//基类
	ScanState	ss;				/* its first field is NodeTag */
	//是否需要随机访问排序输出?
	bool		randomAccess;	/* need random access to sort output? */
	//结果集是否存在边界?
	bool		bounded;		/* is the result set bounded? */
	//如存在边界,需要多少个元组?
	int64		bound;			/* if bounded, how many tuples are needed */
	//是否已完成排序?
	bool		sort_Done;		/* sort completed yet? */
	//是否使用有界值?
	bool		bounded_Done;	/* value of bounded we did the sort with */
	//使用的有界值?
	int64		bound_Done;		/* value of bound we did the sort with */
	//tuplesort.c的私有状态
	void	   *tuplesortstate; /* private state of tuplesort.c */
	//是否worker?
	bool		am_worker;		/* are we a worker? */
	//每个worker对应一个条目
	SharedSortInfo *shared_info;	/* one entry per worker */
} SortState;

/* ----------------
 *	 Shared memory container for per-worker sort information
 *	 per-worker排序信息的共享内存容器
 * ----------------
 */
typedef struct SharedSortInfo
{
	//worker个数?
	int			num_workers;
	//排序机制
	TuplesortInstrumentation sinstrument[FLEXIBLE_ARRAY_MEMBER];
} SharedSortInfo;

```

**TuplesortInstrumentation**
报告排序统计的数据结构.
```
/*
 * Data structures for reporting sort statistics.  Note that
 * TuplesortInstrumentation can't contain any pointers because we
 * sometimes put it in shared memory.
 * 报告排序统计的数据结构.
 * 注意TuplesortInstrumentation不能包含指针因为有时候会把该结构体放在共享内存中.
 */
typedef enum
{
	SORT_TYPE_STILL_IN_PROGRESS = 0,//仍然在排序中
	SORT_TYPE_TOP_N_HEAPSORT,//TOP N 堆排序
	SORT_TYPE_QUICKSORT,//快速排序
	SORT_TYPE_EXTERNAL_SORT,//外部排序
	SORT_TYPE_EXTERNAL_MERGE//外部排序后的合并
} TuplesortMethod;//排序方法

typedef enum
{
	SORT_SPACE_TYPE_DISK,//需要用上磁盘
	SORT_SPACE_TYPE_MEMORY//使用内存
} TuplesortSpaceType;

typedef struct TuplesortInstrumentation
{
	//使用的排序算法
	TuplesortMethod sortMethod; /* sort algorithm used */
	//排序使用空间类型
	TuplesortSpaceType spaceType;	/* type of space spaceUsed represents */
	//空间消耗(以K为单位)
	long		spaceUsed;		/* space consumption, in kB */
} TuplesortInstrumentation;

```

### 二、源码解读
tuplesort_begin_heap和tuplesort_puttupleslot都是准备工作,把tuple放到数组(堆)中,为后续的实际排序实现作准备.
**tuplesort_begin_heap**
```

Tuplesortstate *
tuplesort_begin_heap(TupleDesc tupDesc,//元组描述符
					 int nkeys, //排序键个数
					 AttrNumber *attNums,//属性编号
					 Oid *sortOperators, //排序操作符
					 Oid *sortCollations,//排序规则
					 bool *nullsFirstFlags,//标记
					 int workMem, //内存大小
					 SortCoordinate coordinate,//协调器 
					 bool randomAccess)//是否随机访问
{
	//获取排序状态
	Tuplesortstate *state = tuplesort_begin_common(workMem, coordinate,
												   randomAccess);
	MemoryContext oldcontext;
	int			i;

oldcontext = MemoryContextSwitchTo(state->sortcontext);

AssertArg(nkeys > 0);

#ifdef TRACE_SORT
	if (trace_sort)
		elog(LOG,
			 "begin tuple sort: nkeys = %d, workMem = %d, randomAccess = %c",
			 nkeys, workMem, randomAccess ? 't' : 'f');
#endif

state->nKeys = nkeys;

TRACE_POSTGRESQL_SORT_START(HEAP_SORT,
								false,	/* no unique check */
								nkeys,
								workMem,
								randomAccess,
								PARALLEL_SORT(state));
	//设置运行状态
	state->comparetup = comparetup_heap;
	state->copytup = copytup_heap;
	state->writetup = writetup_heap;
	state->readtup = readtup_heap;
	//假定不需要拷贝元组描述符
	state->tupDesc = tupDesc;	/* assume we need not copy tupDesc */
	state->abbrevNext = 10;

/* Prepare SortSupport data for each column */
	//为每一列准备SortSupport数据(分配内存空间)
	state->sortKeys = (SortSupport) palloc0(nkeys * sizeof(SortSupportData));

for (i = 0; i < nkeys; i++)
	{
		//------- 遍历排序键
		//排序键
		SortSupport sortKey = state->sortKeys + i;

AssertArg(attNums[i] != 0);
		AssertArg(sortOperators[i] != 0);
		//设置SortSupport
		sortKey->ssup_cxt = CurrentMemoryContext;
		sortKey->ssup_collation = sortCollations[i];
		sortKey->ssup_nulls_first = nullsFirstFlags[i];
		sortKey->ssup_attno = attNums[i];
		/* Convey if abbreviation optimization is applicable in principle */
		//缩写优化是否原则上可用?
		sortKey->abbreviate = (i == 0);
		//设置
		PrepareSortSupportFromOrderingOp(sortOperators[i], sortKey);
	}

/*
	 * The "onlyKey" optimization cannot be used with abbreviated keys, since
	 * tie-breaker comparisons may be required.  Typically, the optimization
	 * is only of value to pass-by-value types anyway, whereas abbreviated
	 * keys are typically only of value to pass-by-reference types.
	 * 对于缩写优化"onlyKey"优化不能使用,因为可能需要tie-breaker比较.
	 * 典型的,优化器只对按值传递类型有价值,而缩写建通常只对引用传递类型有价值.
	 */
	if (nkeys == 1 && !state->sortKeys->abbrev_converter)
		state->onlyKey = state->sortKeys;

MemoryContextSwitchTo(oldcontext);

return state;
}

```

**tuplesort_puttupleslot**
接收一个元组(一行)
```

/*
 * Accept one tuple while collecting input data for sort.
 * 接收一个元组(一行)
 *
 * Note that the input data is always copied; the caller need not save it.
 * 注意输入数据通常会被拷贝,调用者不需要保存这些数据.
 */
void
tuplesort_puttupleslot(Tuplesortstate *state, TupleTableSlot *slot)
{
	MemoryContext oldcontext = MemoryContextSwitchTo(state->sortcontext);
	SortTuple	stup;

/*
	 * Copy the given tuple into memory we control, and decrease availMem.
	 * Then call the common code.
	 * 拷贝给定的元组在我们控制的内存中,同时减少可用内存.
	 * 然后调用puttuple_common函数.
	 */
	//#define COPYTUP(state,stup,tup) ((*(state)->copytup) (state, stup, tup))
	COPYTUP(state, &stup, (void *) slot);

puttuple_common(state, &stup);

MemoryContextSwitchTo(oldcontext);
}

/*
 * Shared code for tuple and datum cases.
 * 元组和datum共享的代码.
 */
static void
puttuple_common(Tuplesortstate *state, SortTuple *tuple)
{
	Assert(!LEADER(state));

switch (state->status)
	{
		case TSS_INITIAL://初始化

/*
			 * Save the tuple into the unsorted array.  First, grow the array
			 * as needed.  Note that we try to grow the array when there is
			 * still one free slot remaining --- if we fail, there'll still be
			 * room to store the incoming tuple, and then we'll switch to
			 * tape-based operation.
			 * 在未排序的数组中存储元组.
			 * 首先,如需要则扩展数组大小.注意在只有1个slot剩下来的时候才尝试扩展数组.
			 * 假如扩展失败,仍有空间可用于存储输入的元组,然后将切换至tape-based(基于磁带)操作.
			 */
			if (state->memtupcount >= state->memtupsize - 1)
			{
				(void) grow_memtuples(state);
				Assert(state->memtupcount < state->memtupsize);
			}
			state->memtuples[state->memtupcount++] = *tuple;//在数组中保存元组

/*
			 * Check if it's time to switch over to a bounded heapsort. We do
			 * so if the input tuple count exceeds twice the desired tuple
			 * count (this is a heuristic for where heapsort becomes cheaper
			 * than a quicksort), or if we've just filled workMem and have
			 * enough tuples to meet the bound.
			 * 检查是否切换至有界heapsort.
			 * 在输入元组个数超出期望元组个数两倍的情况下执行该检查
			 * (在堆排序比快速排序成本更低时所获得的洞见),
			 *   或者如果我们已经填充了workMem并且有足够的元组满足bound时也执行该检查.
			 *
			 * Note that once we enter TSS_BOUNDED state we will always try to
			 * complete the sort that way.  In the worst case, if later input
			 * tuples are larger than earlier ones, this might cause us to
			 * exceed workMem significantly.
			 * 注意我们一旦进入TSS_BOUNDED状态,将尝试按指定的方式完成排序.
			 * 在最坏的情况下,如果后续的输入元组比早前的要大,这可能会导致内存大小会超出workMem.
			 */
			if (state->bounded &&
				(state->memtupcount > state->bound * 2 ||
				 (state->memtupcount > state->bound && LACKMEM(state))))
			{
#ifdef TRACE_SORT
				if (trace_sort)
					elog(LOG, "switching to bounded heapsort at %d tuples: %s",
						 state->memtupcount,
						 pg_rusage_show(&state->ru_start));
#endif
				//切换至堆排序
				make_bounded_heap(state);
				return;
			}

/*
			 * Done if we still fit in available memory and have array slots.
			 * 如果内存空间可用并且数组有位置存储,则已完成任务!
			 */
			if (state->memtupcount < state->memtupsize && !LACKMEM(state))
				return;

/*
			 * Nope; time to switch to tape-based operation.
			 * 切换至tape-base操作
			 */
			inittapes(state, true);

/*
			 * Dump all tuples.
			 * dump所有元组
			 */
			dumptuples(state, false);
			break;

case TSS_BOUNDED://有界堆排序

/*
			 * We don't want to grow the array here, so check whether the new
			 * tuple can be discarded before putting it in.  This should be a
			 * good speed optimization, too, since when there are many more
			 * input tuples than the bound, most input tuples can be discarded
			 * with just this one comparison.  Note that because we currently
			 * have the sort direction reversed, we must check for <= not >=.
			 * 不希望在这里扩展数组,因此检查在放到数组前检查是否可用废弃某些新元组.
			 * 这将是一个很好的性能优化,因为存在比边界要大得多的输入元组,
			 *   大多数输入元组会通过对比被废弃.
			 */
			if (COMPARETUP(state, tuple, &state->memtuples[0]) <= 0)
			{
				/* new tuple <= top of the heap, so we can discard it */
				// 新元组 <= 堆顶,可以废弃
				free_sort_tuple(state, tuple);
				CHECK_FOR_INTERRUPTS();
			}
			else
			{
				/* discard top of heap, replacing it with the new tuple */
				//废弃堆顶,使用新元组替换
				free_sort_tuple(state, &state->memtuples[0]);
				tuplesort_heap_replace_top(state, tuple);
			}
			break;

case TSS_BUILDRUNS://构建运行期信息

/*
			 * Save the tuple into the unsorted array (there must be space)
			 * 保存元组到未排序数组中(存在空闲空间)
			 */
			state->memtuples[state->memtupcount++] = *tuple;

/*
			 * If we are over the memory limit, dump all tuples.
			 * 如果已超出内存限制,则dump所有元组
			 */
			dumptuples(state, false);
			break;

default:
			elog(ERROR, "invalid tuplesort state");
			break;
	}
}

```

### 三、跟踪分析
N/A

### 四、参考资料
N/A

ITPub博客

PostgreSQL 源码解读（194）- 查询#110(排序#3 - 实现)

最新文章