本節繼續介紹排序的實現,主要內容是tuplesort_puttupleslot->puttuple_common調用的inittapes和dumptuples函數.

在內存不能滿足排序需求時,使用了Polyphase Merging排序

一、數據結構

Tuplesortstate
Tuplesort操作的私有狀態.

/*
 * Possible states of a Tuplesort object.  These denote the states that
 * persist between calls of Tuplesort routines.
 * Tuplesort對象可能的狀態.
 * 這些標示在Tuplesort例程調用之間會持久存在的狀態.
 */
typedef enum
{
    //裝載元組,在內存限制之內
    TSS_INITIAL,                /* Loading tuples; still within memory limit */
    //裝載元組到有界堆中
    TSS_BOUNDED,                /* Loading tuples into bounded-size heap */
    //裝載元組,寫入到tape中
    TSS_BUILDRUNS,              /* Loading tuples; writing to tape */
    //完全在內存中完成排序
    TSS_SORTEDINMEM,            /* Sort completed entirely in memory */
    //完成排序,最后在tape上執行排序
    TSS_SORTEDONTAPE,           /* Sort completed, final run is on tape */
    //不落地執行最后的歸并
    TSS_FINALMERGE              /* Performing final merge on-the-fly */
} TupSortStatus;
/*
 * Parameters for calculation of number of tapes to use --- see inittapes()
 * and tuplesort_merge_order().
 * 用于計算需要使用多少個tapes的參數.--- 詳細參見inittapes()和tuplesort_merge_order().
 *
 * In this calculation we assume that each tape will cost us about 1 blocks
 * worth of buffer space.  This ignores the overhead of all the other data
 * structures needed for each tape, but it's probably close enough.
 * 在這個計算中,我們假定每一個tape會大概消耗緩存空間的一個block.
 * 雖然已經忽略了所有每個tape依賴的其他數據結構,但已經非常接近了.
 *
 * MERGE_BUFFER_SIZE is how much data we'd like to read from each input
 * tape during a preread cycle (see discussion at top of file).
 * MERGE_BUFFER_SIZE表示在每一輪讀周期中我們將要從每個輸入taple中讀取的數據大小
 */
#define MINORDER        6       /* minimum merge order */
#define MAXORDER        500     /* maximum merge order */
#define TAPE_BUFFER_OVERHEAD        BLCKSZ
#define MERGE_BUFFER_SIZE           (BLCKSZ * 32)
typedef int (*SortTupleComparator) (const SortTuple *a, const SortTuple *b,
                                    Tuplesortstate *state);
/*
 * Private state of a Tuplesort operation.
 * Tuplesort操作的私有狀態.
 */
struct Tuplesortstate
{
    //狀態 : 枚舉值詳見上面的信息
    TupSortStatus status;       /* enumerated value as shown above */
    //sort key中的列數
    int         nKeys;          /* number of columns in sort key */
    //調用者需要隨機訪問?
    bool        randomAccess;   /* did caller request random access? */
    //調用者是否指定了最大返回的元組的數目?
    bool        bounded;        /* did caller specify a maximum number of
                                 * tuples to return? */
    //使用有界堆,則返回T
    bool        boundUsed;      /* true if we made use of a bounded heap */
    //如為有界堆,這里存儲最大的元組個數
    int         bound;          /* if bounded, the maximum number of tuples */
    //SortTuple.tuple是否可以設置?
    bool        tuples;         /* Can SortTuple.tuple ever be set? */
    //剩余可用內存大小(單位:字節)
    int64       availMem;       /* remaining memory available, in bytes */
    //允許的內存總大小(單位:字節)
    int64       allowedMem;     /* total memory allowed, in bytes */
    //tapes個數
    int         maxTapes;       /* number of tapes (Knuth's T) */
    //tapes個數 - 1
    int         tapeRange;      /* maxTapes-1 (Knuth's P) */
    //主要用于排序數據的內存上下文
    MemoryContext sortcontext;  /* memory context holding most sort data */
    //用于元組數據的sortcontext的子上下文
    MemoryContext tuplecontext; /* sub-context of sortcontext for tuple data */
    //臨時文件中tapes的logtape.c對象
    LogicalTapeSet *tapeset;    /* logtape.c object for tapes in a temp file */
    /*
     * These function pointers decouple the routines that must know what kind
     * of tuple we are sorting from the routines that don't need to know it.
     * They are set up by the tuplesort_begin_xxx routines.
     * 這些函數指針將必須知道排序的哪種元組的例程與不需要知道它的例程解耦.
     *
     * Function to compare two tuples; result is per qsort() convention, ie:
     * <0, 0, >0 according as a<b, a=b, a>b.  The API must match
     * qsort_arg_comparator.
     * 比較兩個元組的函數,結果由每個qsort()約定,比如:
     *   < 0, 0, >0代表a<b,a=b,a>b.API必須匹配qsort_arg_comparator.
     */
    SortTupleComparator comparetup;
    /*
     * Function to copy a supplied input tuple into palloc'd space and set up
     * its SortTuple representation (ie, set tuple/datum1/isnull1).  Also,
     * state->availMem must be decreased by the amount of space used for the
     * tuple copy (note the SortTuple struct itself is not counted).
     * 該函數用于拷貝一個輸入的元組到由palloc分配的內存空間中,
     *   同時設置SortTuple數據結構(比如設置tuple/datum1/isnull1等).
     * 同時,state->availMem必須減去用于元組拷貝的空間大小(注意:SortTuple結構體不計算在內).
     */
    void        (*copytup) (Tuplesortstate *state, SortTuple *stup, void *tup);
    /*
     * Function to write a stored tuple onto tape.  The representation of the
     * tuple on tape need not be the same as it is in memory; requirements on
     * the tape representation are given below.  Unless the slab allocator is
     * used, after writing the tuple, pfree() the out-of-line data (not the
     * SortTuple struct!), and increase state->availMem by the amount of
     * memory space thereby released.
     * 用于寫入元組到taple的函數.
     * tape中的元組聲明不需要與內存中的一致,tape中的聲明要求詳見下面說明.
     * 除非使用slab分配器,在寫入元組后,pfree() out-of-line的數據(不是SortTuple結構體),
     *   同時把剛才釋放的內存空間加到state->availMem中.
     */
    void        (*writetup) (Tuplesortstate *state, int tapenum,
                             SortTuple *stup);
    /*
     * Function to read a stored tuple from tape back into memory. 'len' is
     * the already-read length of the stored tuple.  The tuple is allocated
     * from the slab memory arena, or is palloc'd, see readtup_alloc().
     * 從tape中讀取元組到內存中的函數.
     * 'len'是已讀取的存儲元組的長度.元組在slab內存空間/palloc中分配,詳細參考readtup_alloc()函數
     */
    void        (*readtup) (Tuplesortstate *state, SortTuple *stup,
                            int tapenum, unsigned int len);
    /*
     * This array holds the tuples now in sort memory.  If we are in state
     * INITIAL, the tuples are in no particular order; if we are in state
     * SORTEDINMEM, the tuples are in final sorted order; in states BUILDRUNS
     * and FINALMERGE, the tuples are organized in "heap" order per Algorithm
     * H.  In state SORTEDONTAPE, the array is not used.
     * 該數組保存排序內存中的元組.當前狀態為
     * INITIAL:元組沒有特定的順序;
     * SORTEDINMEM:元組處于最終已排序的狀態;
     * BUILDRUNS/FINALMERGE:元組按算法H的'堆'順序組織.
     * SORTEDONTAPE:數組未使用.
     */
    //SortTuple結構體數組
    SortTuple  *memtuples;      /* array of SortTuple structs */
    //當前存在的元組數
    int         memtupcount;    /* number of tuples currently present */
    //memtuples數組的已分配的大小
    int         memtupsize;     /* allocated length of memtuples array */
    //memtuples的增長仍在進行中?
    bool        growmemtuples;  /* memtuples' growth still underway? */
    /*
     * Memory for tuples is sometimes allocated using a simple slab allocator,
     * rather than with palloc().  Currently, we switch to slab allocation
     * when we start merging.  Merging only needs to keep a small, fixed
     * number of tuples in memory at any time, so we can avoid the
     * palloc/pfree overhead by recycling a fixed number of fixed-size slots
     * to hold the tuples.
     * 有時候元組的內存分配使用簡單的slab分配器實現而不是palloc().
     * 在開始歸并時,同步切換至slab分配器.歸并只需要在內存中保持簡單/固定的元組數目,
     *   因此可以避免頻繁回收固定數目固定大小的slots(用于保存元組)而導致的palloc/pfree過載.
     *
     * For the slab, we use one large allocation, divided into SLAB_SLOT_SIZE
     * slots.  The allocation is sized to have one slot per tape, plus one
     * additional slot.  We need that many slots to hold all the tuples kept
     * in the heap during merge, plus the one we have last returned from the
     * sort, with tuplesort_gettuple.
     * 對于slab,使用大型分配器,拆分為SLAB_SLOT_SIZE個大小的slots.
     * 分配器的大小為每個tape一個slot,外加一個為的slot.
     * 我們需要這么多slots是因為在歸并期間需要保存所有在堆中的元組,外加tuplesort_gettuple從排序中最終返回的元組
     *
     * Initially, all the slots are kept in a linked list of free slots.  When
     * a tuple is read from a tape, it is put to the next available slot, if
     * it fits.  If the tuple is larger than SLAB_SLOT_SIZE, it is palloc'd
     * instead.
     * 一開始,所有的slots在空閑slots中以鏈表的方式保存.
     * 從tape中讀取元組時,如合適的話,元組會放到下一個可用slot中.
     * 如果元組比SLAB_SLOT_SIZE要大,改用palloc分配內存空間.
     *
     * When we're done processing a tuple, we return the slot back to the free
     * list, or pfree() if it was palloc'd.  We know that a tuple was
     * allocated from the slab, if its pointer value is between
     * slabMemoryBegin and -End.
     * 如果已完成元組的處理,返回slot到空閑鏈表中,如果使用palloc分配則使用pfree回收空間.
     * 如果元組指針值在slabMemoryBegin和slabMemoryEnd之間,那么我們可以知道元組是從slab中分配的.
     *
     * When the slab allocator is used, the USEMEM/LACKMEM mechanism of
     * tracking memory usage is not used.
     * 如使用了slab分配器,不會使用USEMEM/LACKMEM機制跟蹤內存使用.
     */
    bool        slabAllocatorUsed;
    //slab內存空間的起始位置
    char       *slabMemoryBegin;    /* beginning of slab memory arena */
    //slab內存空間的結束位置
    char       *slabMemoryEnd;  /* end of slab memory arena */
    //鏈表頭
    SlabSlot   *slabFreeHead;   /* head of free list */
    /* Buffer size to use for reading input tapes, during merge. */
    //在歸并期間用于讀取輸入tapes的緩存大小
    size_t      read_buffer_size;
    /*
     * When we return a tuple to the caller in tuplesort_gettuple_XXX, that
     * came from a tape (that is, in TSS_SORTEDONTAPE or TSS_FINALMERGE
     * modes), we remember the tuple in 'lastReturnedTuple', so that we can
     * recycle the memory on next gettuple call.
     * 通過tuplesort_gettuple_XXX方法調用返回元組給調用者時,元組從tape中獲取
     * (也就是說,TSS_SORTEDONTAPE/TSS_FINALMERGE模式),這時候會把元組放在'lastReturnedTuple'中,
     *   因此可在下次gettuple調用中回收內存.
     */
    void       *lastReturnedTuple;
    /*
     * While building initial runs, this is the current output run number.
     * Afterwards, it is the number of initial runs we made.
     * 在構建initial運行時,這是當前輸出的run編號.
     * 后續這是我們構建好的initial runs的編號.
     */
    int         currentRun;
    /*
     * Unless otherwise noted, all pointer variables below are pointers to
     * arrays of length maxTapes, holding per-tape data.
     * 除非特別注意,下面所有的指針變量是指向長度為maxTapes的數組,保存per-tape數據.
     */
    /*
     * This variable is only used during merge passes.  mergeactive[i] is true
     * if we are reading an input run from (actual) tape number i and have not
     * yet exhausted that run.
     * 該變量在歸并過程中使用.
     * mergeactive[i]為T如果我們從編號為i的tape中讀取數據,仍未在該run中消耗完畢.
     */
    //活躍的輸入run源?
    bool       *mergeactive;    /* active input run source? */
    /*
     * Variables for Algorithm D.  Note that destTape is a "logical" tape
     * number, ie, an index into the tp_xxx[] arrays.  Be careful to keep
     * "logical" and "actual" tape numbers straight!
     * 用于算法D的變量.
     * 注意destTape是一個邏輯tape編號,例如,是指向tp_xxx[]數組的索引.
     * 注意保持"邏輯"和"實際"tape編號的連續性.
     */
    //Knuth's l
    int         Level;          /* Knuth's l */
    //當前輸出tape(Knuth's j)
    int         destTape;       /* current output tape (Knuth's j, less 1) */
    //目標斐波拉契run計數(A[])
    int        *tp_fib;         /* Target Fibonacci run counts (A[]) */
    //每一個tape上真正runs的編號
    int        *tp_runs;        /* # of real runs on each tape */
    //每一個tape(D[])上虛擬runs的編號
    int        *tp_dummy;       /* # of dummy runs for each tape (D[]) */
    //實際的tape編號(TAPE[])
    int        *tp_tapenum;     /* Actual tape numbers (TAPE[]) */
    //歸并輪中的活動輸入tapes編號
    int         activeTapes;    /* # of active input tapes in merge pass */
    /*
     * These variables are used after completion of sorting to keep track of
     * the next tuple to return.  (In the tape case, the tape's current read
     * position is also critical state.)
     * 這些變量用于在排序完成后保持下一個返回元組時的跟蹤.
     * (在tape情況下,tape的當前讀取位置也是重要的狀態)
     */
    //已完成輸出的實際tape編號
    int         result_tape;    /* actual tape number of finished output */
    //數組編號(僅用于SORTEDINMEM)
    int         current;        /* array index (only used if SORTEDINMEM) */
    //是否到達EOF(用于游標)
    bool        eof_reached;    /* reached EOF (needed for cursors) */
    /* markpos_xxx holds marked position for mark and restore */
    //markpos_xxx保持已標記的位置,用于標記和存儲
    //tape block編號(只用于SORTEDONTAPE)
    long        markpos_block;  /* tape block# (only used if SORTEDONTAPE) */
    //存儲的"current",或者tape塊中的偏移
    int         markpos_offset; /* saved "current", or offset in tape block */
    //存儲的eof_reached
    bool        markpos_eof;    /* saved "eof_reached" */
    /*
     * These variables are used during parallel sorting.
     * 這些變量用于并行排序.
     *
     * worker is our worker identifier.  Follows the general convention that
     * -1 value relates to a leader tuplesort, and values >= 0 worker
     * tuplesorts. (-1 can also be a serial tuplesort.)
     * worker是worker標識符ID.
     * 遵循一般約定，-1值與leader tuplesort相關，并且值>= 0表示worker tuplesorts。
     * (在串行tuplesort時,-1也可以表示這種情況)
     *
     * shared is mutable shared memory state, which is used to coordinate
     * parallel sorts.
     * shared是可變的共享內存狀態,用于協調并行排序.
     *
     * nParticipants is the number of worker Tuplesortstates known by the
     * leader to have actually been launched, which implies that they must
     * finish a run leader can merge.  Typically includes a worker state held
     * by the leader process itself.  Set in the leader Tuplesortstate only.
     * nParticipants是已知的worker Tuplesortstates的數目,這些worker由leader感知,是實際啟動的worker數,
     *   這也意味著在leader可以歸并前這些worker必須完成.
     * 典型的,leader進行自身包含至少一個worker狀態.
     * 只在leader的Tuplesortstate中設置.
     */
    int         worker;
    Sharedsort *shared;
    int         nParticipants;
    /*
     * The sortKeys variable is used by every case other than the hash index
     * case; it is set by tuplesort_begin_xxx.  tupDesc is only used by the
     * MinimalTuple and CLUSTER routines, though.
     * sortKeys變量用于every而不是hash index,通過tuplesort_begin_xxx設置.
     * tupDesc只由MinimalTuple和CLUSTER例程使用.
     */
    TupleDesc   tupDesc;
    //長度nKeys數組
    SortSupport sortKeys;       /* array of length nKeys */
    /*
     * This variable is shared by the single-key MinimalTuple case and the
     * Datum case (which both use qsort_ssup()).  Otherwise it's NULL.
     * 該變量在單鍵MinimalTuple和Datum情況下(使用qsort_ssup()函數)共享使用,否則的話值為NULL.
     */
    SortSupport onlyKey;
    /*
     * Additional state for managing "abbreviated key" sortsupport routines
     * (which currently may be used by all cases except the hash index case).
     * Tracks the intervals at which the optimization's effectiveness is
     * tested.
     * 管理"縮寫鍵"sortsupport過程的額外狀態.
     * (除了hash index外會被其他情況使用)
     * 跟蹤在優化器有效性測試時時間間隔. 
     */
    int64       abbrevNext;     /* Tuple # at which to next check
                                 * applicability */
    /*
     * These variables are specific to the CLUSTER case; they are set by
     * tuplesort_begin_cluster.
     * 這些變量僅在CLUSTER時生效,通過tuplesort_begin_cluster設置.
     */
    //將用于依賴的索引信息
    IndexInfo  *indexInfo;      /* info about index being used for reference */
    //解析索引表達式的運行期狀態
    EState     *estate;         /* for evaluating index expressions */
    /*
     * These variables are specific to the IndexTuple case; they are set by
     * tuplesort_begin_index_xxx and used only by the IndexTuple routines.
     * 這些變量僅用于IndexTuple.
     * 通過tuplesort_begin_index_xxx設置,僅用于IndexTuple例程.
     */
    //數據表
    Relation    heapRel;        /* table the index is being built on */
    //正在創建的index
    Relation    indexRel;       /* index being built */
    /* These are specific to the index_btree subcase: */
    //這些僅在index_btree下使用
    //如發現重復元組,則提示
    bool        enforceUnique;  /* complain if we find duplicate tuples */
    /* These are specific to the index_hash subcase: */
    //index_hash情況
    uint32      high_mask;      /* masks for sortable part of hash code */
    uint32      low_mask;
    uint32      max_buckets;
    /*
     * These variables are specific to the Datum case; they are set by
     * tuplesort_begin_datum and used only by the DatumTuple routines.
     * 這些變量用于Datum,通過tuplesort_begin_datum設置,僅用于DatumTuple例程.
     */
    Oid         datumType;
    /* we need typelen in order to know how to copy the Datums. */
    //需要typelen用于知道如何拷貝Datums.
    int         datumTypeLen;
    /*
     * Resource snapshot for time of sort start.
     * 在排序開始時的資源快照
     */
#ifdef TRACE_SORT
    PGRUsage    ru_start;
#endif
};

二、源碼解讀

inittapes
初始化tape sorting(Polyphase Merging).

/*
 * inittapes - initialize for tape sorting.
 * inittapes - 初始化tape sorting(Polyphase Merging).
 *
 * This is called only if we have found we won't sort in memory.
 * 在內存不足以滿足排序需求時才調用此函數.
 */
static void
inittapes(Tuplesortstate *state, bool mergeruns)
{
    int         maxTapes,//最大tapes
                j;
    Assert(!LEADER(state));
    if (mergeruns)
    {
        /* Compute number of tapes to use: merge order plus 1 */
        //計算tapes數 : 歸并順序 + 1
        /*
        #define MINORDER        6       
        #define MAXORDER        500     
        #define TAPE_BUFFER_OVERHEAD        BLCKSZ
        #define MERGE_BUFFER_SIZE           (BLCKSZ * 32)
        mOrder = (allowedMem - TAPE_BUFFER_OVERHEAD) /
        (MERGE_BUFFER_SIZE + TAPE_BUFFER_OVERHEAD);
        mOrder = Max(mOrder, MINORDER);
        mOrder = Min(mOrder, MAXORDER);
        */
        maxTapes = tuplesort_merge_order(state->allowedMem) + 1;
    }
    else
    {
        /* Workers can sometimes produce single run, output without merge */
        //Worker進程有時可能產生單個run,不需要歸并直接輸出.
        Assert(WORKER(state));
        maxTapes = MINORDER + 1;
    }
#ifdef TRACE_SORT
    if (trace_sort)
        elog(LOG, "worker %d switching to external sort with %d tapes: %s",
             state->worker, maxTapes, pg_rusage_show(&state->ru_start));
#endif
    /* Create the tape set and allocate the per-tape data arrays */
    //創建tape集合并分配per-tape數據數組
    inittapestate(state, maxTapes);
    state->tapeset =
        LogicalTapeSetCreate(maxTapes, NULL,
                             state->shared ? &state->shared->fileset : NULL,
                             state->worker);
    state->currentRun = 0;
    /*
     * Initialize variables of Algorithm D (step D1).
     * 初始化算法D的變量(step D1)
     */
    for (j = 0; j < maxTapes; j++)
    {
        state->tp_fib[j] = 1;
        state->tp_runs[j] = 0;
        state->tp_dummy[j] = 1;
        state->tp_tapenum[j] = j;
    }
    state->tp_fib[state->tapeRange] = 0;
    state->tp_dummy[state->tapeRange] = 0;
    state->Level = 1;
    state->destTape = 0;
    //變更狀態為TSS_BUILDRUNS
    state->status = TSS_BUILDRUNS;
}

dumptuples
清除memtuples中的元組并寫入初始run到tape中

/*
 * dumptuples - remove tuples from memtuples and write initial run to tape
 * 清除memtuples中的元組并寫入初始run到tape中
 *
 * When alltuples = true, dump everything currently in memory.  (This case is
 * only used at end of input data.)
 * 如alltuples為T,dump內存中的所有數據.
 * (僅適用于與輸入數據結束時)
 */
static void
dumptuples(Tuplesortstate *state, bool alltuples)
{
    int         memtupwrite;
    int         i;
    /*
     * Nothing to do if we still fit in available memory and have array slots,
     * unless this is the final call during initial run generation.
     * 如果可以放入可用內存中并且仍有數據slots,并且當前不是在初始run產生時的最后一次調用,則返回
     */
    if (state->memtupcount < state->memtupsize && !LACKMEM(state) &&
        !alltuples)
        return;
    /*
     * Final call might require no sorting, in rare cases where we just so
     * happen to have previously LACKMEM()'d at the point where exactly all
     * remaining tuples are loaded into memory, just before input was
     * exhausted.
     * 最后一次調用可能不需要排序,在極少數情況下,
     *   我們恰好在輸入耗盡之前調用了LACKMEM()'d,此時所有剩余的元組都被加載到內存中.
     *
     * In general, short final runs are quite possible.  Rather than allowing
     * a special case where there was a superfluous selectnewtape() call (i.e.
     * a call with no subsequent run actually written to destTape), we prefer
     * to write out a 0 tuple run.
     * 通常來說,最后的runs很有可能較短.
     * 與其允許存在一個額外的selectnewtape()函數調用(即沒有后續運行實際寫入到destTape的調用),
     *   還不如編寫一個0元組的run.
     *
     * mergereadnext() is prepared for 0 tuple runs, and will reliably mark
     * the tape inactive for the merge when called from beginmerge().  This
     * case is therefore similar to the case where mergeonerun() finds a dummy
     * run for the tape, and so doesn't need to merge a run from the tape (or
     * conceptually "merges" the dummy run, if you prefer).  According to
     * Knuth, Algorithm D "isn't strictly optimal" in its method of
     * distribution and dummy run assignment; this edge case seems very
     * unlikely to make that appreciably worse.
     * mergereadnext()為0元組runs作準備,在beginmerge()函數調用該函數時將標記tape為非活動狀態.
     * 這種情況與mergeonerun()為tape檢索到虛擬run類似,因此不需要歸并(如果你愿意,可以執行名義上的歸并).
     * 按照Knuth的說法,算法D不是嚴格分布和虛擬run分配優化的,但這種極端的情況不太可能讓情況很糟糕.
     */
    Assert(state->status == TSS_BUILDRUNS);
    /*
     * It seems unlikely that this limit will ever be exceeded, but take no
     * chances
     * 越界了.
     */
    if (state->currentRun == INT_MAX)
        ereport(ERROR,
                (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
                 errmsg("cannot have more than %d runs for an external sort",
                        INT_MAX)));
    state->currentRun++;
#ifdef TRACE_SORT
    if (trace_sort)
        elog(LOG, "worker %d starting quicksort of run %d: %s",
             state->worker, state->currentRun,
             pg_rusage_show(&state->ru_start));
#endif
    /*
     * Sort all tuples accumulated within the allowed amount of memory for
     * this run using quicksort
     * 使用快速排序對內存中的元組進行排序.
     */
    tuplesort_sort_memtuples(state);
#ifdef TRACE_SORT
    if (trace_sort)
        elog(LOG, "worker %d finished quicksort of run %d: %s",
             state->worker, state->currentRun,
             pg_rusage_show(&state->ru_start));
#endif
    //寫入到tape中
    memtupwrite = state->memtupcount;
    for (i = 0; i < memtupwrite; i++)
    {
        WRITETUP(state, state->tp_tapenum[state->destTape],
                 &state->memtuples[i]);
        state->memtupcount--;
    }
    /*
     * Reset tuple memory.  We've freed all of the tuples that we previously
     * allocated.  It's important to avoid fragmentation when there is a stark
     * change in the sizes of incoming tuples.  Fragmentation due to
     * AllocSetFree's bucketing by size class might be particularly bad if
     * this step wasn't taken.
     * 重置tuple內存上下文.
     * 目的是為了避免內存碎片.
     */
    MemoryContextReset(state->tuplecontext);
    markrunend(state, state->tp_tapenum[state->destTape]);
    state->tp_runs[state->destTape]++;
    state->tp_dummy[state->destTape]--; /* per Alg D step D2 */
#ifdef TRACE_SORT
    if (trace_sort)
        elog(LOG, "worker %d finished writing run %d to tape %d: %s",
             state->worker, state->currentRun, state->destTape,
             pg_rusage_show(&state->ru_start));
#endif
    //未完成所有元組的處理,分配新的tape
    if (!alltuples)
        selectnewtape(state);
}

三、跟蹤分析

N/A

四、參考資料

Merge sort
Polyphase merge sort
Sorting Algorithms: Internal and External