1/*-------------------------------------------------------------------------
4 * Framework for accelerated sorting.
6 * Traditionally, PostgreSQL has implemented sorting by repeatedly invoking
7 * an SQL-callable comparison function "cmp(x, y) returns int" on pairs of
8 * values to be compared, where the comparison function is the BTORDER_PROC
9 * pg_amproc support function of the appropriate btree index opclass.
11 * This file defines alternative APIs that allow sorting to be performed with
12 * reduced overhead. To support lower-overhead sorting, a btree opclass may
13 * provide a BTSORTSUPPORT_PROC pg_amproc entry, which must take a single
14 * argument of type internal and return void. The argument is actually a
15 * pointer to a SortSupportData struct, which is defined below.
17 * If provided, the BTSORTSUPPORT function will be called during sort setup,
18 * and it must initialize the provided struct with pointers to function(s)
19 * that can be called to perform sorting. This API is defined to allow
20 * multiple acceleration mechanisms to be supported, but no opclass is
21 * required to provide all of them. The BTSORTSUPPORT function should
22 * simply not set any function pointers for mechanisms it doesn't support.
23 * Opclasses that provide BTSORTSUPPORT and don't provide a comparator
24 * function will have a shim set up by sort support automatically. However,
25 * opclasses that support the optional additional abbreviated key capability
26 * must always provide an authoritative comparator used to tie-break
27 * inconclusive abbreviated comparisons and also used when aborting
28 * abbreviation. Furthermore, a converter and abort/costing function must be
31 * All sort support functions will be passed the address of the
32 * SortSupportData struct when called, so they can use it to store
33 * additional private data as needed. In particular, for collation-aware
34 * datatypes, the ssup_collation field is set before calling BTSORTSUPPORT
35 * and is available to all support functions. Additional opclass-dependent
36 * data can be stored using the ssup_extra field. Any such data
37 * should be allocated in the ssup_cxt memory context.
39 * Note: since pg_amproc functions are indexed by (lefttype, righttype)
40 * it is possible to associate a BTSORTSUPPORT function with a cross-type
41 * comparison. This could sensibly be used to provide a fast comparator
42 * function for such cases, but probably not any other acceleration method.
45 * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
46 * Portions Copyright (c) 1994, Regents of the University of California
48 * src/include/utils/sortsupport.h
50 *-------------------------------------------------------------------------
63 * These fields are initialized before calling the BTSORTSUPPORT function
64 * and should not be changed later.
70 * Additional sorting parameters; but unlike ssup_collation, these can be
71 * changed after BTSORTSUPPORT is called, so don't use them in selecting
72 * sort support functions.
78 * These fields are workspace for callers, and should not be touched by
79 * opclass-specific functions.
84 * ssup_extra is zeroed before calling the BTSORTSUPPORT function, and is
85 * not touched subsequently by callers.
90 * Function pointers are zeroed before calling the BTSORTSUPPORT function,
91 * and must be set by it for any acceleration methods it wants to supply.
92 * The comparator pointer must be set, others are optional.
96 * Comparator function has the same API as the traditional btree
97 * comparison function, ie, return <0, 0, or >0 according as x is less
98 * than, equal to, or greater than y. Note that x and y are guaranteed
99 * not null, and there is no way to return null either.
101 * This may be either the authoritative comparator, or the abbreviated
102 * comparator. Core code may switch this over the initial preference of
103 * an opclass support function despite originally indicating abbreviation
104 * was applicable, by assigning the authoritative comparator back.
109 * "Abbreviated key" infrastructure follows.
111 * All callbacks must be set by sortsupport opclasses that make use of
112 * this optional additional infrastructure (unless for whatever reasons
113 * the opclass doesn't proceed with abbreviation, in which case
114 * abbrev_converter must not be set).
116 * This allows opclass authors to supply a conversion routine, used to
117 * create an alternative representation of the underlying type (an
118 * "abbreviated key"). This representation must be pass-by-value and
119 * typically will use some ad-hoc format that only the opclass has
120 * knowledge of. An alternative comparator, used only with this
121 * alternative representation must also be provided (which is assigned to
122 * "comparator"). This representation is a simple approximation of the
123 * original Datum. It must be possible to compare datums of this
124 * representation with each other using the supplied alternative
125 * comparator, and have any non-zero return value be a reliable proxy for
126 * what a proper comparison would indicate. Returning zero from the
127 * alternative comparator does not indicate equality, as with a
128 * conventional support routine 1, though -- it indicates that it wasn't
129 * possible to determine how the two abbreviated values compared. A
130 * proper comparison, using "abbrev_full_comparator"/
131 * ApplySortAbbrevFullComparator() is therefore required. In many cases
132 * this results in most or all comparisons only using the cheap
133 * alternative comparison func, which is typically implemented as code
134 * that compiles to just a few CPU instructions. CPU cache miss penalties
135 * are expensive; to get good overall performance, sort infrastructure
136 * must heavily weigh cache performance.
138 * Opclass authors must consider the final cardinality of abbreviated keys
139 * when devising an encoding scheme. It's possible for a strategy to work
140 * better than an alternative strategy with one usage pattern, while the
141 * reverse might be true for another usage pattern. All of these factors
142 * must be considered.
146 * "abbreviate" concerns whether or not the abbreviated key optimization
147 * is applicable in principle (that is, the sortsupport routine needs to
148 * know if its dealing with a key where an abbreviated representation can
149 * usefully be packed together. Conventionally, this is the leading
150 * attribute key). Note, however, that in order to determine that
151 * abbreviation is not in play, the core code always checks whether or not
152 * the opclass has set abbrev_converter. This is a one way, one time
153 * message to the opclass.
158 * Converter to abbreviated format, from original representation. Core
159 * code uses this callback to convert from a pass-by-reference "original"
160 * Datum to a pass-by-value abbreviated key Datum. Note that original is
161 * guaranteed NOT NULL, because it doesn't make sense to factor NULLness
162 * into ad-hoc cost model.
164 * abbrev_converter is tested to see if abbreviation is in play. Core
165 * code may set it to NULL to indicate abbreviation should not be used
166 * (which is something sortsupport routines need not concern themselves
167 * with). However, sortsupport routines must not set it when it is
168 * immediately established that abbreviation should not proceed (e.g., for
169 * !abbreviate calls, or due to platform-specific impediments to using
175 * abbrev_abort callback allows clients to verify that the current
176 * strategy is working out, using a sortsupport routine defined ad-hoc
177 * cost model. If there is a lot of duplicate abbreviated keys in
178 * practice, it's useful to be able to abandon the strategy before paying
179 * too high a cost in conversion (perhaps certain opclass-specific
180 * adaptations are useful too).
185 * Full, authoritative comparator for key that an abbreviated
186 * representation was generated for, used when an abbreviated comparison
187 * was inconclusive (by calling ApplySortAbbrevFullComparator()), or used
188 * to replace "comparator" when core system ultimately decides against
196 * Apply a sort comparator function and return a 3-way comparison result.
197 * This takes care of handling reverse-sort and NULLs-ordering properly.
201 Datum datum2,
bool isNull2,
209 compare = 0;
/* NULL "=" NULL */
211 compare = -1;
/* NULL "<" NOT_NULL */
213 compare = 1;
/* NULL ">" NOT_NULL */
218 compare = 1;
/* NOT_NULL ">" NULL */
220 compare = -1;
/* NOT_NULL "<" NULL */
234 Datum datum2,
bool isNull2,
242 compare = 0;
/* NULL "=" NULL */
244 compare = -1;
/* NULL "<" NOT_NULL */
246 compare = 1;
/* NULL ">" NOT_NULL */
251 compare = 1;
/* NOT_NULL ">" NULL */
253 compare = -1;
/* NOT_NULL "<" NULL */
257 compare = datum1 < datum2 ? -1 : datum1 > datum2 ? 1 : 0;
267 Datum datum2,
bool isNull2,
275 compare = 0;
/* NULL "=" NULL */
277 compare = -1;
/* NULL "<" NOT_NULL */
279 compare = 1;
/* NULL ">" NOT_NULL */
284 compare = 1;
/* NOT_NULL ">" NULL */
286 compare = -1;
/* NOT_NULL "<" NULL */
301 Datum datum2,
bool isNull2,
309 compare = 0;
/* NULL "=" NULL */
311 compare = -1;
/* NULL "<" NOT_NULL */
313 compare = 1;
/* NULL ">" NOT_NULL */
318 compare = 1;
/* NOT_NULL ">" NULL */
320 compare = -1;
/* NOT_NULL "<" NULL */
334 * Apply a sort comparator function and return a 3-way comparison using full,
335 * authoritative comparator. This takes care of handling reverse-sort and
336 * NULLs-ordering properly.
340 Datum datum2,
bool isNull2,
348 compare = 0;
/* NULL "=" NULL */
350 compare = -1;
/* NULL "<" NOT_NULL */
352 compare = 1;
/* NULL ">" NOT_NULL */
357 compare = 1;
/* NOT_NULL ">" NULL */
359 compare = -1;
/* NOT_NULL "<" NULL */
372 * Datum comparison functions that we have specialized sort routines for.
373 * Datatypes that install these as their comparator or abbreviated comparator
374 * are eligible for faster sorting.
380/* Other functions in utils/sort/sortsupport.c */
387#endif /* SORTSUPPORT_H */
#define INVERT_COMPARE_RESULT(var)
static int compare(const void *arg1, const void *arg2)
static int64 DatumGetInt64(Datum X)
static int32 DatumGetInt32(Datum X)
static int ApplySortAbbrevFullComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
struct SortSupportData SortSupportData
struct SortSupportData * SortSupport
int ssup_datum_signed_cmp(Datum x, Datum y, SortSupport ssup)
int ssup_datum_unsigned_cmp(Datum x, Datum y, SortSupport ssup)
static int ApplySignedSortComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
static int ApplySortComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
void PrepareSortSupportFromGistIndexRel(Relation indexRel, SortSupport ssup)
static int ApplyUnsignedSortComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
int ssup_datum_int32_cmp(Datum x, Datum y, SortSupport ssup)
void PrepareSortSupportComparisonShim(Oid cmpFunc, SortSupport ssup)
void PrepareSortSupportFromIndexRel(Relation indexRel, bool reverse, SortSupport ssup)
static int ApplyInt32SortComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
void PrepareSortSupportFromOrderingOp(Oid orderingOp, SortSupport ssup)
int(* comparator)(Datum x, Datum y, SortSupport ssup)
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
int(* abbrev_full_comparator)(Datum x, Datum y, SortSupport ssup)
bool(* abbrev_abort)(int memtupcount, SortSupport ssup)