* grounds that 7 is the "sweet spot" on the tapes-to-passes curve according
* to Knuth's figure 70 (section 5.4.2). However, Knuth is assuming that
* tape drives are expensive beasts, and in particular that there will always
- * be many more runs than tape drives. In our implementation a "tape drive"
+ * be many more runs than tape drives. In our implementation a "tape drive"
* doesn't cost much more than a few Kb of memory buffers, so we can afford
* to have lots of them. In particular, if we can have as many tape drives
* as sorted runs, we can eliminate any repeated I/O at all. In the current
* above. Nonetheless, with large workMem we can have many tapes.
*
*
- * Portions Copyright (c) 1996-2006, PostgreSQL Global Development Group
+ * Portions Copyright (c) 1996-2007, PostgreSQL Global Development Group
* Portions Copyright (c) 1994, Regents of the University of California
*
* IDENTIFICATION
- * $PostgreSQL: pgsql/src/backend/utils/sort/tuplesort.c,v 1.68 2006/07/14 14:52:25 momjian Exp $
+ * $PostgreSQL: pgsql/src/backend/utils/sort/tuplesort.c,v 1.74 2007/01/10 18:06:04 tgl Exp $
*
*-------------------------------------------------------------------------
*/
/*
- * The objects we actually sort are SortTuple structs. These contain
+ * The objects we actually sort are SortTuple structs. These contain
* a pointer to the tuple proper (might be a MinimalTuple or IndexTuple),
* which is a separate palloc chunk --- we assume it is just one chunk and
* can be freed by a simple pfree(). SortTuples also contain the tuple's
* first key column in Datum/nullflag format, and an index integer.
*
* Storing the first key column lets us save heap_getattr or index_getattr
- * calls during tuple comparisons. We could extract and save all the key
+ * calls during tuple comparisons. We could extract and save all the key
* columns not just the first, but this would increase code complexity and
* overhead, and wouldn't actually save any comparison cycles in the common
* case where the first key determines the comparison result. Note that
* for a pass-by-reference datatype, datum1 points into the "tuple" storage.
*
* When sorting single Datums, the data value is represented directly by
- * datum1/isnull1. If the datatype is pass-by-reference and isnull1 is false,
+ * datum1/isnull1. If the datatype is pass-by-reference and isnull1 is false,
* then datum1 points to a separately palloc'd data value that is also pointed
* to by the "tuple" pointer; otherwise "tuple" is NULL.
*
* While building initial runs, tupindex holds the tuple's run number. During
* merge passes, we re-use it to hold the input tape number that each tuple in
* the heap was read from, or to hold the index of the next tuple pre-read
- * from the same tape in the case of pre-read entries. tupindex goes unused
+ * from the same tape in the case of pre-read entries. tupindex goes unused
* if the sort occurs entirely in memory.
*/
typedef struct
* 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.
+ * <0, 0, >0 according as a<b, a=b, a>b. The API must match
+ * qsort_arg_comparator.
*/
- int (*comparetup) (Tuplesortstate *state,
- const SortTuple *a, const SortTuple *b);
+ int (*comparetup) (const SortTuple *a, const SortTuple *b,
+ Tuplesortstate *state);
/*
* Function to copy a supplied input tuple into palloc'd space and set up
* state->availMem by the amount of memory space thereby released.
*/
void (*writetup) (Tuplesortstate *state, int tapenum,
- SortTuple *stup);
+ SortTuple *stup);
/*
* Function to read a stored tuple from tape back into memory. 'len' is
* the already-read length of the stored tuple. Create a palloc'd copy,
- * initialize tuple/datum1/isnull1 in the target SortTuple struct,
- * and decrease state->availMem by the amount of memory space consumed.
+ * initialize tuple/datum1/isnull1 in the target SortTuple struct, and
+ * decrease state->availMem by the amount of memory space consumed.
*/
void (*readtup) (Tuplesortstate *state, SortTuple *stup,
- int tapenum, unsigned int len);
+ int tapenum, unsigned int len);
/*
- * This array holds the tuples now in sort memory. If we are in state
+ * 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
int currentRun;
/*
- * Unless otherwise noted, all pointer variables below are pointers
- * to arrays of length maxTapes, holding per-tape data.
+ * Unless otherwise noted, all pointer variables below are pointers to
+ * arrays of length maxTapes, holding per-tape data.
*/
/*
int *mergeavailslots; /* slots left for prereading each tape */
long *mergeavailmem; /* availMem for prereading each tape */
int mergefreelist; /* head of freelist of recycled slots */
- int mergefirstfree; /* first slot never used in this merge */
+ int mergefirstfree; /* first slot never used in this merge */
/*
* Variables for Algorithm D. Note that destTape is a "logical" tape
* tuplesort_begin_heap and used only by the MinimalTuple routines.
*/
TupleDesc tupDesc;
- ScanKey scanKeys; /* array of length nKeys */
- SortFunctionKind *sortFnKinds; /* array of length nKeys */
+ ScanKey scanKeys; /* array of length nKeys */
/*
* These variables are specific to the IndexTuple case; they are set by
* tuplesort_begin_datum and used only by the DatumTuple routines.
*/
Oid datumType;
- Oid sortOperator;
FmgrInfo sortOpFn; /* cached lookup data for sortOperator */
- SortFunctionKind sortFnKind;
+ int sortFnFlags; /* equivalent to sk_flags */
/* we need typelen and byval in order to know how to copy the Datums. */
int datumTypeLen;
bool datumTypeByVal;
#endif
};
-#define COMPARETUP(state,a,b) ((*(state)->comparetup) (state, a, b))
-#define COPYTUP(state,stup,tup) ((*(state)->copytup) (state, stup, tup))
+#define COMPARETUP(state,a,b) ((*(state)->comparetup) (a, b, state))
+#define COPYTUP(state,stup,tup) ((*(state)->copytup) (state, stup, tup))
#define WRITETUP(state,tape,stup) ((*(state)->writetup) (state, tape, stup))
#define READTUP(state,stup,tape,len) ((*(state)->readtup) (state, stup, tape, len))
#define LACKMEM(state) ((state)->availMem < 0)
static void tuplesort_heap_siftup(Tuplesortstate *state, bool checkIndex);
static unsigned int getlen(Tuplesortstate *state, int tapenum, bool eofOK);
static void markrunend(Tuplesortstate *state, int tapenum);
-static int qsort_comparetup(const void *a, const void *b);
-static int comparetup_heap(Tuplesortstate *state,
- const SortTuple *a, const SortTuple *b);
+static int comparetup_heap(const SortTuple *a, const SortTuple *b,
+ Tuplesortstate *state);
static void copytup_heap(Tuplesortstate *state, SortTuple *stup, void *tup);
static void writetup_heap(Tuplesortstate *state, int tapenum,
- SortTuple *stup);
+ SortTuple *stup);
static void readtup_heap(Tuplesortstate *state, SortTuple *stup,
- int tapenum, unsigned int len);
-static int comparetup_index(Tuplesortstate *state,
- const SortTuple *a, const SortTuple *b);
+ int tapenum, unsigned int len);
+static int comparetup_index(const SortTuple *a, const SortTuple *b,
+ Tuplesortstate *state);
static void copytup_index(Tuplesortstate *state, SortTuple *stup, void *tup);
static void writetup_index(Tuplesortstate *state, int tapenum,
- SortTuple *stup);
+ SortTuple *stup);
static void readtup_index(Tuplesortstate *state, SortTuple *stup,
- int tapenum, unsigned int len);
-static int comparetup_datum(Tuplesortstate *state,
- const SortTuple *a, const SortTuple *b);
+ int tapenum, unsigned int len);
+static int comparetup_datum(const SortTuple *a, const SortTuple *b,
+ Tuplesortstate *state);
static void copytup_datum(Tuplesortstate *state, SortTuple *stup, void *tup);
static void writetup_datum(Tuplesortstate *state, int tapenum,
- SortTuple *stup);
+ SortTuple *stup);
static void readtup_datum(Tuplesortstate *state, SortTuple *stup,
- int tapenum, unsigned int len);
-
-/*
- * Since qsort(3) will not pass any context info to qsort_comparetup(),
- * we have to use this ugly static variable. It is set to point to the
- * active Tuplesortstate object just before calling qsort. It should
- * not be used directly by anything except qsort_comparetup().
- */
-static Tuplesortstate *qsort_tuplesortstate;
+ int tapenum, unsigned int len);
/*
MemoryContext oldcontext;
/*
- * Create a working memory context for this sort operation.
- * All data needed by the sort will live inside this context.
+ * Create a working memory context for this sort operation. All data
+ * needed by the sort will live inside this context.
*/
sortcontext = AllocSetContextCreate(CurrentMemoryContext,
"TupleSort",
ALLOCSET_DEFAULT_MAXSIZE);
/*
- * Make the Tuplesortstate within the per-sort context. This way,
- * we don't need a separate pfree() operation for it at shutdown.
+ * Make the Tuplesortstate within the per-sort context. This way, we
+ * don't need a separate pfree() operation for it at shutdown.
*/
oldcontext = MemoryContextSwitchTo(sortcontext);
Tuplesortstate *
tuplesort_begin_heap(TupleDesc tupDesc,
- int nkeys,
- Oid *sortOperators, AttrNumber *attNums,
+ int nkeys, AttrNumber *attNums,
+ Oid *sortOperators, bool *nullsFirstFlags,
int workMem, bool randomAccess)
{
Tuplesortstate *state = tuplesort_begin_common(workMem, randomAccess);
state->tupDesc = tupDesc; /* assume we need not copy tupDesc */
state->scanKeys = (ScanKey) palloc0(nkeys * sizeof(ScanKeyData));
- state->sortFnKinds = (SortFunctionKind *)
- palloc0(nkeys * sizeof(SortFunctionKind));
for (i = 0; i < nkeys; i++)
{
- RegProcedure sortFunction;
+ Oid sortFunction;
+ bool reverse;
- AssertArg(sortOperators[i] != 0);
AssertArg(attNums[i] != 0);
+ AssertArg(sortOperators[i] != 0);
- /* select a function that implements the sort operator */
- SelectSortFunction(sortOperators[i], &sortFunction,
- &state->sortFnKinds[i]);
+ if (!get_compare_function_for_ordering_op(sortOperators[i],
+ &sortFunction, &reverse))
+ elog(ERROR, "operator %u is not a valid ordering operator",
+ sortOperators[i]);
/*
* We needn't fill in sk_strategy or sk_subtype since these scankeys
InvalidStrategy,
sortFunction,
(Datum) 0);
+
+ /* However, we use btree's conventions for encoding directionality */
+ if (reverse)
+ state->scanKeys[i].sk_flags |= SK_BT_DESC;
+ if (nullsFirstFlags[i])
+ state->scanKeys[i].sk_flags |= SK_BT_NULLS_FIRST;
}
MemoryContextSwitchTo(oldcontext);
Tuplesortstate *
tuplesort_begin_datum(Oid datumType,
- Oid sortOperator,
+ Oid sortOperator, bool nullsFirstFlag,
int workMem, bool randomAccess)
{
Tuplesortstate *state = tuplesort_begin_common(workMem, randomAccess);
MemoryContext oldcontext;
- RegProcedure sortFunction;
+ Oid sortFunction;
+ bool reverse;
int16 typlen;
bool typbyval;
state->readtup = readtup_datum;
state->datumType = datumType;
- state->sortOperator = sortOperator;
- /* select a function that implements the sort operator */
- SelectSortFunction(sortOperator, &sortFunction, &state->sortFnKind);
- /* and look up the function */
+ /* lookup the ordering function */
+ if (!get_compare_function_for_ordering_op(sortOperator,
+ &sortFunction, &reverse))
+ elog(ERROR, "operator %u is not a valid ordering operator",
+ sortOperator);
fmgr_info(sortFunction, &state->sortOpFn);
+ /* set ordering flags */
+ state->sortFnFlags = reverse ? SK_BT_DESC : 0;
+ if (nullsFirstFlag)
+ state->sortFnFlags |= SK_BT_NULLS_FIRST;
+
/* lookup necessary attributes of the datum type */
get_typlenbyval(datumType, &typlen, &typbyval);
state->datumTypeLen = typlen;
/*
* Delete temporary "tape" files, if any.
*
- * Note: want to include this in reported total cost of sort, hence
- * need for two #ifdef TRACE_SORT sections.
+ * Note: want to include this in reported total cost of sort, hence need
+ * for two #ifdef TRACE_SORT sections.
*/
if (state->tapeset)
LogicalTapeSetClose(state->tapeset);
MemoryContextSwitchTo(oldcontext);
/*
- * Free the per-sort memory context, thereby releasing all working
- * memory, including the Tuplesortstate struct itself.
+ * Free the per-sort memory context, thereby releasing all working memory,
+ * including the Tuplesortstate struct itself.
*/
MemoryContextDelete(state->sortcontext);
}
{
/*
* We need to be sure that we do not cause LACKMEM to become true, else
- * the space management algorithm will go nuts. We assume here that
- * the memory chunk overhead associated with the memtuples array is
- * constant and so there will be no unexpected addition to what we ask
- * for. (The minimum array size established in tuplesort_begin_common
- * is large enough to force palloc to treat it as a separate chunk, so
- * this assumption should be good. But let's check it.)
+ * the space management algorithm will go nuts. We assume here that the
+ * memory chunk overhead associated with the memtuples array is constant
+ * and so there will be no unexpected addition to what we ask for. (The
+ * minimum array size established in tuplesort_begin_common is large
+ * enough to force palloc to treat it as a separate chunk, so this
+ * assumption should be good. But let's check it.)
*/
if (state->availMem <= (long) (state->memtupsize * sizeof(SortTuple)))
return false;
+
/*
* On a 64-bit machine, allowedMem could be high enough to get us into
* trouble with MaxAllocSize, too.
SortTuple stup;
/*
- * If it's a pass-by-reference value, copy it into memory we control,
- * and decrease availMem. Then call the common code.
+ * If it's a pass-by-reference value, copy it into memory we control, and
+ * decrease availMem. Then call the common code.
*/
if (isNull || state->datumTypeByVal)
{
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
+ * 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.
*/
if (state->memtupcount >= state->memtupsize - 1)
case TSS_BUILDRUNS:
/*
- * Insert the tuple into the heap, with run number
- * currentRun if it can go into the current run, else run number
- * currentRun+1. The tuple can go into the current run if it is
- * >= the first not-yet-output tuple. (Actually, it could go into
- * the current run if it is >= the most recently output tuple ...
- * but that would require keeping around the tuple we last output,
- * and it's simplest to let writetup free each tuple as soon as
- * it's written.)
+ * Insert the tuple into the heap, with run number currentRun if
+ * it can go into the current run, else run number currentRun+1.
+ * The tuple can go into the current run if it is >= the first
+ * not-yet-output tuple. (Actually, it could go into the current
+ * run if it is >= the most recently output tuple ... but that
+ * would require keeping around the tuple we last output, and it's
+ * simplest to let writetup free each tuple as soon as it's
+ * written.)
*
* Note there will always be at least one tuple in the heap at
* this point; see dumptuples.
* amount of memory. Just qsort 'em and we're done.
*/
if (state->memtupcount > 1)
- {
- qsort_tuplesortstate = state;
- qsort((void *) state->memtuples, state->memtupcount,
- sizeof(SortTuple), qsort_comparetup);
- }
+ qsort_arg((void *) state->memtuples,
+ state->memtupcount,
+ sizeof(SortTuple),
+ (qsort_arg_comparator) state->comparetup,
+ (void *) state);
state->current = 0;
state->eof_reached = false;
state->markpos_offset = 0;
int mOrder;
/*
- * We need one tape for each merge input, plus another one for the
- * output, and each of these tapes needs buffer space. In addition
- * we want MERGE_BUFFER_SIZE workspace per input tape (but the output
- * tape doesn't count).
+ * We need one tape for each merge input, plus another one for the output,
+ * and each of these tapes needs buffer space. In addition we want
+ * MERGE_BUFFER_SIZE workspace per input tape (but the output tape doesn't
+ * count).
*
* Note: you might be thinking we need to account for the memtuples[]
- * array in this calculation, but we effectively treat that as part of
- * the MERGE_BUFFER_SIZE workspace.
+ * array in this calculation, but we effectively treat that as part of the
+ * MERGE_BUFFER_SIZE workspace.
*/
mOrder = (allowedMem - TAPE_BUFFER_OVERHEAD) /
(MERGE_BUFFER_SIZE + TAPE_BUFFER_OVERHEAD);
/*
* We must have at least 2*maxTapes slots in the memtuples[] array, else
- * we'd not have room for merge heap plus preread. It seems unlikely
- * that this case would ever occur, but be safe.
+ * we'd not have room for merge heap plus preread. It seems unlikely that
+ * this case would ever occur, but be safe.
*/
maxTapes = Min(maxTapes, state->memtupsize / 2);
/*
* Decrease availMem to reflect the space needed for tape buffers; but
- * don't decrease it to the point that we have no room for tuples.
- * (That case is only likely to occur if sorting pass-by-value Datums;
- * in all other scenarios the memtuples[] array is unlikely to occupy
- * more than half of allowedMem. In the pass-by-value case it's not
- * important to account for tuple space, so we don't care if LACKMEM
- * becomes inaccurate.)
+ * don't decrease it to the point that we have no room for tuples. (That
+ * case is only likely to occur if sorting pass-by-value Datums; in all
+ * other scenarios the memtuples[] array is unlikely to occupy more than
+ * half of allowedMem. In the pass-by-value case it's not important to
+ * account for tuple space, so we don't care if LACKMEM becomes
+ * inaccurate.)
*/
tapeSpace = maxTapes * TAPE_BUFFER_OVERHEAD;
if (tapeSpace + GetMemoryChunkSpace(state->memtuples) < state->allowedMem)
/*
* If we produced only one initial run (quite likely if the total data
* volume is between 1X and 2X workMem), we can just use that tape as the
- * finished output, rather than doing a useless merge. (This obvious
+ * finished output, rather than doing a useless merge. (This obvious
* optimization is not in Knuth's algorithm.)
*/
if (state->currentRun == 1)
*/
while (state->memtupcount > 0)
{
- CHECK_FOR_INTERRUPTS();
/* write the tuple to destTape */
priorAvail = state->availMem;
srcTape = state->memtuples[0].tupindex;
memset(state->mergelast, 0,
state->maxTapes * sizeof(*state->mergelast));
state->mergefreelist = 0; /* nothing in the freelist */
- state->mergefirstfree = activeTapes; /* 1st slot avail for preread */
+ state->mergefirstfree = activeTapes; /* 1st slot avail for preread */
/*
* Initialize space allocation to let each active input tape have an equal
/*
* Heap manipulation routines, per Knuth's Algorithm 5.2.3H.
*
- * Compare two SortTuples. If checkIndex is true, use the tuple index
+ * Compare two SortTuples. If checkIndex is true, use the tuple index
* as the front of the sort key; otherwise, no.
*/
/*
* Insert a new tuple into an empty or existing heap, maintaining the
- * heap invariant. Caller is responsible for ensuring there's room.
+ * heap invariant. Caller is responsible for ensuring there's room.
*
* Note: we assume *tuple is a temporary variable that can be scribbled on.
* For some callers, tuple actually points to a memtuples[] entry above the
int j;
/*
- * Save the tupleindex --- see notes above about writing on *tuple.
- * It's a historical artifact that tupleindex is passed as a separate
- * argument and not in *tuple, but it's notationally convenient so
- * let's leave it that way.
+ * Save the tupleindex --- see notes above about writing on *tuple. It's a
+ * historical artifact that tupleindex is passed as a separate argument
+ * and not in *tuple, but it's notationally convenient so let's leave it
+ * that way.
*/
tuple->tupindex = tupleindex;
/*
- * qsort interface
- */
-
-static int
-qsort_comparetup(const void *a, const void *b)
-{
- /* The passed pointers are pointers to SortTuple ... */
- return COMPARETUP(qsort_tuplesortstate,
- (const SortTuple *) a,
- (const SortTuple *) b);
-}
-
-
-/*
- * This routine selects an appropriate sorting function to implement
- * a sort operator as efficiently as possible. The straightforward
- * method is to use the operator's implementation proc --- ie, "<"
- * comparison. However, that way often requires two calls of the function
- * per comparison. If we can find a btree three-way comparator function
- * associated with the operator, we can use it to do the comparisons
- * more efficiently. We also support the possibility that the operator
- * is ">" (descending sort), in which case we have to reverse the output
- * of the btree comparator.
- *
- * Possibly this should live somewhere else (backend/catalog/, maybe?).
+ * Set up for an external caller of ApplySortFunction. This function
+ * basically just exists to localize knowledge of the encoding of sk_flags
+ * used in this module.
*/
void
SelectSortFunction(Oid sortOperator,
- RegProcedure *sortFunction,
- SortFunctionKind *kind)
+ bool nulls_first,
+ Oid *sortFunction,
+ int *sortFlags)
{
- CatCList *catlist;
- int i;
- HeapTuple tuple;
- Form_pg_operator optup;
- Oid opclass = InvalidOid;
-
- /*
- * Search pg_amop to see if the target operator is registered as the "<"
- * or ">" operator of any btree opclass. It's possible that it might be
- * registered both ways (eg, if someone were to build a "reverse sort"
- * opclass for some reason); prefer the "<" case if so. If the operator is
- * registered the same way in multiple opclasses, assume we can use the
- * associated comparator function from any one.
- */
- catlist = SearchSysCacheList(AMOPOPID, 1,
- ObjectIdGetDatum(sortOperator),
- 0, 0, 0);
-
- for (i = 0; i < catlist->n_members; i++)
- {
- Form_pg_amop aform;
-
- tuple = &catlist->members[i]->tuple;
- aform = (Form_pg_amop) GETSTRUCT(tuple);
-
- if (!opclass_is_btree(aform->amopclaid))
- continue;
- /* must be of default subtype, too */
- if (aform->amopsubtype != InvalidOid)
- continue;
-
- if (aform->amopstrategy == BTLessStrategyNumber)
- {
- opclass = aform->amopclaid;
- *kind = SORTFUNC_CMP;
- break; /* done looking */
- }
- else if (aform->amopstrategy == BTGreaterStrategyNumber)
- {
- opclass = aform->amopclaid;
- *kind = SORTFUNC_REVCMP;
- /* keep scanning in hopes of finding a BTLess entry */
- }
- }
+ bool reverse;
- ReleaseSysCacheList(catlist);
+ if (!get_compare_function_for_ordering_op(sortOperator,
+ sortFunction, &reverse))
+ elog(ERROR, "operator %u is not a valid ordering operator",
+ sortOperator);
- if (OidIsValid(opclass))
- {
- /* Found a suitable opclass, get its default comparator function */
- *sortFunction = get_opclass_proc(opclass, InvalidOid, BTORDER_PROC);
- Assert(RegProcedureIsValid(*sortFunction));
- return;
- }
-
- /*
- * Can't find a comparator, so use the operator as-is. Decide whether it
- * is forward or reverse sort by looking at its name (grotty, but this
- * only matters for deciding which end NULLs should get sorted to). XXX
- * possibly better idea: see whether its selectivity function is
- * scalargtcmp?
- */
- tuple = SearchSysCache(OPEROID,
- ObjectIdGetDatum(sortOperator),
- 0, 0, 0);
- if (!HeapTupleIsValid(tuple))
- elog(ERROR, "cache lookup failed for operator %u", sortOperator);
- optup = (Form_pg_operator) GETSTRUCT(tuple);
- if (strcmp(NameStr(optup->oprname), ">") == 0)
- *kind = SORTFUNC_REVLT;
- else
- *kind = SORTFUNC_LT;
- *sortFunction = optup->oprcode;
- ReleaseSysCache(tuple);
-
- Assert(RegProcedureIsValid(*sortFunction));
+ *sortFlags = reverse ? SK_BT_DESC : 0;
+ if (nulls_first)
+ *sortFlags |= SK_BT_NULLS_FIRST;
}
/*
/*
* Apply a sort function (by now converted to fmgr lookup form)
* and return a 3-way comparison result. This takes care of handling
- * NULLs and sort ordering direction properly.
+ * reverse-sort and NULLs-ordering properly. We assume that DESC and
+ * NULLS_FIRST options are encoded in sk_flags the same way btree does it.
*/
static inline int32
-inlineApplySortFunction(FmgrInfo *sortFunction, SortFunctionKind kind,
+inlineApplySortFunction(FmgrInfo *sortFunction, int sk_flags,
Datum datum1, bool isNull1,
Datum datum2, bool isNull2)
{
- switch (kind)
- {
- case SORTFUNC_LT:
- if (isNull1)
- {
- if (isNull2)
- return 0;
- return 1; /* NULL sorts after non-NULL */
- }
- if (isNull2)
- return -1;
- if (DatumGetBool(myFunctionCall2(sortFunction, datum1, datum2)))
- return -1; /* a < b */
- if (DatumGetBool(myFunctionCall2(sortFunction, datum2, datum1)))
- return 1; /* a > b */
- return 0;
-
- case SORTFUNC_REVLT:
- /* We reverse the ordering of NULLs, but not the operator */
- if (isNull1)
- {
- if (isNull2)
- return 0;
- return -1; /* NULL sorts before non-NULL */
- }
- if (isNull2)
- return 1;
- if (DatumGetBool(myFunctionCall2(sortFunction, datum1, datum2)))
- return -1; /* a < b */
- if (DatumGetBool(myFunctionCall2(sortFunction, datum2, datum1)))
- return 1; /* a > b */
- return 0;
-
- case SORTFUNC_CMP:
- if (isNull1)
- {
- if (isNull2)
- return 0;
- return 1; /* NULL sorts after non-NULL */
- }
- if (isNull2)
- return -1;
- return DatumGetInt32(myFunctionCall2(sortFunction,
- datum1, datum2));
+ int32 compare;
- case SORTFUNC_REVCMP:
- if (isNull1)
- {
- if (isNull2)
- return 0;
- return -1; /* NULL sorts before non-NULL */
- }
- if (isNull2)
- return 1;
- return -DatumGetInt32(myFunctionCall2(sortFunction,
- datum1, datum2));
+ if (isNull1)
+ {
+ if (isNull2)
+ compare = 0; /* NULL "=" NULL */
+ else if (sk_flags & SK_BT_NULLS_FIRST)
+ compare = -1; /* NULL "<" NOT_NULL */
+ else
+ compare = 1; /* NULL ">" NOT_NULL */
+ }
+ else if (isNull2)
+ {
+ if (sk_flags & SK_BT_NULLS_FIRST)
+ compare = 1; /* NOT_NULL ">" NULL */
+ else
+ compare = -1; /* NOT_NULL "<" NULL */
+ }
+ else
+ {
+ compare = DatumGetInt32(myFunctionCall2(sortFunction,
+ datum1, datum2));
- default:
- elog(ERROR, "unrecognized SortFunctionKind: %d", (int) kind);
- return 0; /* can't get here, but keep compiler quiet */
+ if (sk_flags & SK_BT_DESC)
+ compare = -compare;
}
+
+ return compare;
}
/*
* C99's brain-dead notions about how to implement inline functions...
*/
int32
-ApplySortFunction(FmgrInfo *sortFunction, SortFunctionKind kind,
+ApplySortFunction(FmgrInfo *sortFunction, int sortFlags,
Datum datum1, bool isNull1,
Datum datum2, bool isNull2)
{
- return inlineApplySortFunction(sortFunction, kind,
+ return inlineApplySortFunction(sortFunction, sortFlags,
datum1, isNull1,
datum2, isNull2);
}
*/
static int
-comparetup_heap(Tuplesortstate *state, const SortTuple *a, const SortTuple *b)
+comparetup_heap(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
{
ScanKey scanKey = state->scanKeys;
HeapTupleData ltup;
int nkey;
int32 compare;
+ /* Allow interrupting long sorts */
+ CHECK_FOR_INTERRUPTS();
+
/* Compare the leading sort key */
- compare = inlineApplySortFunction(&scanKey->sk_func,
- state->sortFnKinds[0],
+ compare = inlineApplySortFunction(&scanKey->sk_func, scanKey->sk_flags,
a->datum1, a->isnull1,
b->datum1, b->isnull1);
if (compare != 0)
datum1 = heap_getattr(<up, attno, tupDesc, &isnull1);
datum2 = heap_getattr(&rtup, attno, tupDesc, &isnull2);
- compare = inlineApplySortFunction(&scanKey->sk_func,
- state->sortFnKinds[nkey],
+ compare = inlineApplySortFunction(&scanKey->sk_func, scanKey->sk_flags,
datum1, isnull1,
datum2, isnull2);
if (compare != 0)
*/
static int
-comparetup_index(Tuplesortstate *state, const SortTuple *a, const SortTuple *b)
+comparetup_index(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
{
/*
* This is similar to _bt_tuplecompare(), but we have already done the
- * index_getattr calls for the first column, and we need to keep track
- * of whether any null fields are present. Also see the special treatment
+ * index_getattr calls for the first column, and we need to keep track of
+ * whether any null fields are present. Also see the special treatment
* for equal keys at the end.
*/
ScanKey scanKey = state->indexScanKey;
int nkey;
int32 compare;
+ /* Allow interrupting long sorts */
+ CHECK_FOR_INTERRUPTS();
+
/* Compare the leading sort key */
- compare = inlineApplySortFunction(&scanKey->sk_func,
- SORTFUNC_CMP,
+ compare = inlineApplySortFunction(&scanKey->sk_func, scanKey->sk_flags,
a->datum1, a->isnull1,
b->datum1, b->isnull1);
if (compare != 0)
datum1 = index_getattr(tuple1, nkey, tupDes, &isnull1);
datum2 = index_getattr(tuple2, nkey, tupDes, &isnull2);
- /* see comments about NULLs handling in btbuild */
-
- /* the comparison function is always of CMP type */
- compare = inlineApplySortFunction(&scanKey->sk_func,
- SORTFUNC_CMP,
+ compare = inlineApplySortFunction(&scanKey->sk_func, scanKey->sk_flags,
datum1, isnull1,
datum2, isnull2);
-
if (compare != 0)
return compare; /* done when we find unequal attributes */
*/
static int
-comparetup_datum(Tuplesortstate *state, const SortTuple *a, const SortTuple *b)
+comparetup_datum(const SortTuple *a, const SortTuple *b, Tuplesortstate *state)
{
- return inlineApplySortFunction(&state->sortOpFn, state->sortFnKind,
+ /* Allow interrupting long sorts */
+ CHECK_FOR_INTERRUPTS();
+
+ return inlineApplySortFunction(&state->sortOpFn, state->sortFnFlags,
a->datum1, a->isnull1,
b->datum1, b->isnull1);
}
}
else
{
- void *raddr = palloc(tuplen);
+ void *raddr = palloc(tuplen);
if (LogicalTapeRead(state->tapeset, tapenum, raddr,
tuplen) != tuplen)
projects / postgresql / blobdiff