PostgreSQL Source Code  git master
sortsupport.h
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * sortsupport.h
4  * Framework for accelerated sorting.
5  *
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.
10  *
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.
16  *
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
29  * provided.
30  *
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.
38  *
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.
43  *
44  *
45  * Portions Copyright (c) 1996-2024, PostgreSQL Global Development Group
46  * Portions Copyright (c) 1994, Regents of the University of California
47  *
48  * src/include/utils/sortsupport.h
49  *
50  *-------------------------------------------------------------------------
51  */
52 #ifndef SORTSUPPORT_H
53 #define SORTSUPPORT_H
54 
55 #include "access/attnum.h"
56 #include "utils/relcache.h"
57 
58 typedef struct SortSupportData *SortSupport;
59 
60 typedef struct SortSupportData
61 {
62  /*
63  * These fields are initialized before calling the BTSORTSUPPORT function
64  * and should not be changed later.
65  */
66  MemoryContext ssup_cxt; /* Context containing sort info */
67  Oid ssup_collation; /* Collation to use, or InvalidOid */
68 
69  /*
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.
73  */
74  bool ssup_reverse; /* descending-order sort? */
75  bool ssup_nulls_first; /* sort nulls first? */
76 
77  /*
78  * These fields are workspace for callers, and should not be touched by
79  * opclass-specific functions.
80  */
81  AttrNumber ssup_attno; /* column number to sort */
82 
83  /*
84  * ssup_extra is zeroed before calling the BTSORTSUPPORT function, and is
85  * not touched subsequently by callers.
86  */
87  void *ssup_extra; /* Workspace for opclass functions */
88 
89  /*
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.
93  */
94 
95  /*
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.
100  *
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.
105  */
106  int (*comparator) (Datum x, Datum y, SortSupport ssup);
107 
108  /*
109  * "Abbreviated key" infrastructure follows.
110  *
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).
115  *
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.
137  *
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.
143  */
144 
145  /*
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.
154  */
156 
157  /*
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.
163  *
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
170  * abbreviation).
171  */
173 
174  /*
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).
181  */
182  bool (*abbrev_abort) (int memtupcount, SortSupport ssup);
183 
184  /*
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
189  * abbreviation.
190  */
193 
194 
195 /*
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.
198  */
199 static inline int
200 ApplySortComparator(Datum datum1, bool isNull1,
201  Datum datum2, bool isNull2,
202  SortSupport ssup)
203 {
204  int compare;
205 
206  if (isNull1)
207  {
208  if (isNull2)
209  compare = 0; /* NULL "=" NULL */
210  else if (ssup->ssup_nulls_first)
211  compare = -1; /* NULL "<" NOT_NULL */
212  else
213  compare = 1; /* NULL ">" NOT_NULL */
214  }
215  else if (isNull2)
216  {
217  if (ssup->ssup_nulls_first)
218  compare = 1; /* NOT_NULL ">" NULL */
219  else
220  compare = -1; /* NOT_NULL "<" NULL */
221  }
222  else
223  {
224  compare = ssup->comparator(datum1, datum2, ssup);
225  if (ssup->ssup_reverse)
227  }
228 
229  return compare;
230 }
231 
232 static inline int
233 ApplyUnsignedSortComparator(Datum datum1, bool isNull1,
234  Datum datum2, bool isNull2,
235  SortSupport ssup)
236 {
237  int compare;
238 
239  if (isNull1)
240  {
241  if (isNull2)
242  compare = 0; /* NULL "=" NULL */
243  else if (ssup->ssup_nulls_first)
244  compare = -1; /* NULL "<" NOT_NULL */
245  else
246  compare = 1; /* NULL ">" NOT_NULL */
247  }
248  else if (isNull2)
249  {
250  if (ssup->ssup_nulls_first)
251  compare = 1; /* NOT_NULL ">" NULL */
252  else
253  compare = -1; /* NOT_NULL "<" NULL */
254  }
255  else
256  {
257  compare = datum1 < datum2 ? -1 : datum1 > datum2 ? 1 : 0;
258  if (ssup->ssup_reverse)
260  }
261 
262  return compare;
263 }
264 
265 #if SIZEOF_DATUM >= 8
266 static inline int
267 ApplySignedSortComparator(Datum datum1, bool isNull1,
268  Datum datum2, bool isNull2,
269  SortSupport ssup)
270 {
271  int compare;
272 
273  if (isNull1)
274  {
275  if (isNull2)
276  compare = 0; /* NULL "=" NULL */
277  else if (ssup->ssup_nulls_first)
278  compare = -1; /* NULL "<" NOT_NULL */
279  else
280  compare = 1; /* NULL ">" NOT_NULL */
281  }
282  else if (isNull2)
283  {
284  if (ssup->ssup_nulls_first)
285  compare = 1; /* NOT_NULL ">" NULL */
286  else
287  compare = -1; /* NOT_NULL "<" NULL */
288  }
289  else
290  {
291  compare = DatumGetInt64(datum1) < DatumGetInt64(datum2) ? -1 :
292  DatumGetInt64(datum1) > DatumGetInt64(datum2) ? 1 : 0;
293  if (ssup->ssup_reverse)
295  }
296 
297  return compare;
298 }
299 #endif
300 
301 static inline int
302 ApplyInt32SortComparator(Datum datum1, bool isNull1,
303  Datum datum2, bool isNull2,
304  SortSupport ssup)
305 {
306  int compare;
307 
308  if (isNull1)
309  {
310  if (isNull2)
311  compare = 0; /* NULL "=" NULL */
312  else if (ssup->ssup_nulls_first)
313  compare = -1; /* NULL "<" NOT_NULL */
314  else
315  compare = 1; /* NULL ">" NOT_NULL */
316  }
317  else if (isNull2)
318  {
319  if (ssup->ssup_nulls_first)
320  compare = 1; /* NOT_NULL ">" NULL */
321  else
322  compare = -1; /* NOT_NULL "<" NULL */
323  }
324  else
325  {
326  compare = DatumGetInt32(datum1) < DatumGetInt32(datum2) ? -1 :
327  DatumGetInt32(datum1) > DatumGetInt32(datum2) ? 1 : 0;
328  if (ssup->ssup_reverse)
330  }
331 
332  return compare;
333 }
334 
335 /*
336  * Apply a sort comparator function and return a 3-way comparison using full,
337  * authoritative comparator. This takes care of handling reverse-sort and
338  * NULLs-ordering properly.
339  */
340 static inline int
342  Datum datum2, bool isNull2,
343  SortSupport ssup)
344 {
345  int compare;
346 
347  if (isNull1)
348  {
349  if (isNull2)
350  compare = 0; /* NULL "=" NULL */
351  else if (ssup->ssup_nulls_first)
352  compare = -1; /* NULL "<" NOT_NULL */
353  else
354  compare = 1; /* NULL ">" NOT_NULL */
355  }
356  else if (isNull2)
357  {
358  if (ssup->ssup_nulls_first)
359  compare = 1; /* NOT_NULL ">" NULL */
360  else
361  compare = -1; /* NOT_NULL "<" NULL */
362  }
363  else
364  {
365  compare = ssup->abbrev_full_comparator(datum1, datum2, ssup);
366  if (ssup->ssup_reverse)
368  }
369 
370  return compare;
371 }
372 
373 /*
374  * Datum comparison functions that we have specialized sort routines for.
375  * Datatypes that install these as their comparator or abbreviated comparator
376  * are eligible for faster sorting.
377  */
378 extern int ssup_datum_unsigned_cmp(Datum x, Datum y, SortSupport ssup);
379 #if SIZEOF_DATUM >= 8
380 extern int ssup_datum_signed_cmp(Datum x, Datum y, SortSupport ssup);
381 #endif
382 extern int ssup_datum_int32_cmp(Datum x, Datum y, SortSupport ssup);
383 
384 /* Other functions in utils/sort/sortsupport.c */
385 extern void PrepareSortSupportComparisonShim(Oid cmpFunc, SortSupport ssup);
386 extern void PrepareSortSupportFromOrderingOp(Oid orderingOp, SortSupport ssup);
387 extern void PrepareSortSupportFromIndexRel(Relation indexRel, int16 strategy,
388  SortSupport ssup);
389 extern void PrepareSortSupportFromGistIndexRel(Relation indexRel, SortSupport ssup);
390 
391 #endif /* SORTSUPPORT_H */
int16 AttrNumber
Definition: attnum.h:21
#define INVERT_COMPARE_RESULT(var)
Definition: c.h:1093
signed short int16
Definition: c.h:480
unsigned char bool
Definition: c.h:443
static int compare(const void *arg1, const void *arg2)
Definition: geqo_pool.c:145
int y
Definition: isn.c:72
int x
Definition: isn.c:71
static int64 DatumGetInt64(Datum X)
Definition: postgres.h:385
uintptr_t Datum
Definition: postgres.h:64
static int32 DatumGetInt32(Datum X)
Definition: postgres.h:202
unsigned int Oid
Definition: postgres_ext.h:31
static int ApplySortAbbrevFullComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
Definition: sortsupport.h:341
struct SortSupportData SortSupportData
struct SortSupportData * SortSupport
Definition: sortsupport.h:58
int ssup_datum_unsigned_cmp(Datum x, Datum y, SortSupport ssup)
Definition: tuplesort.c:3171
static int ApplySortComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
Definition: sortsupport.h:200
void PrepareSortSupportFromGistIndexRel(Relation indexRel, SortSupport ssup)
Definition: sortsupport.c:188
static int ApplyUnsignedSortComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
Definition: sortsupport.h:233
int ssup_datum_int32_cmp(Datum x, Datum y, SortSupport ssup)
Definition: tuplesort.c:3198
void PrepareSortSupportComparisonShim(Oid cmpFunc, SortSupport ssup)
Definition: sortsupport.c:68
static int ApplyInt32SortComparator(Datum datum1, bool isNull1, Datum datum2, bool isNull2, SortSupport ssup)
Definition: sortsupport.h:302
void PrepareSortSupportFromOrderingOp(Oid orderingOp, SortSupport ssup)
Definition: sortsupport.c:134
void PrepareSortSupportFromIndexRel(Relation indexRel, int16 strategy, SortSupport ssup)
Definition: sortsupport.c:161
AttrNumber ssup_attno
Definition: sortsupport.h:81
int(* comparator)(Datum x, Datum y, SortSupport ssup)
Definition: sortsupport.h:106
bool ssup_nulls_first
Definition: sortsupport.h:75
Datum(* abbrev_converter)(Datum original, SortSupport ssup)
Definition: sortsupport.h:172
void * ssup_extra
Definition: sortsupport.h:87
MemoryContext ssup_cxt
Definition: sortsupport.h:66
int(* abbrev_full_comparator)(Datum x, Datum y, SortSupport ssup)
Definition: sortsupport.h:191
bool(* abbrev_abort)(int memtupcount, SortSupport ssup)
Definition: sortsupport.h:182