本节继续介绍排序的实现,上一节介绍了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