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-2019, 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
58typedef struct SortSupportData *SortSupport;
59
60typedef 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 */
155 bool abbreviate;
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 */
172 Datum (*abbrev_converter) (Datum original, SortSupport ssup);
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 */
191 int (*abbrev_full_comparator) (Datum x, Datum y, SortSupport ssup);
192} SortSupportData;
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 */
199static inline int
200ApplySortComparator(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)
226 INVERT_COMPARE_RESULT(compare);
227 }
228
229 return compare;
230}
231
232/*
233 * Apply a sort comparator function and return a 3-way comparison using full,
234 * authoritative comparator. This takes care of handling reverse-sort and
235 * NULLs-ordering properly.
236 */
237static inline int
238ApplySortAbbrevFullComparator(Datum datum1, bool isNull1,
239 Datum datum2, bool isNull2,
240 SortSupport ssup)
241{
242 int compare;
243
244 if (isNull1)
245 {
246 if (isNull2)
247 compare = 0; /* NULL "=" NULL */
248 else if (ssup->ssup_nulls_first)
249 compare = -1; /* NULL "<" NOT_NULL */
250 else
251 compare = 1; /* NULL ">" NOT_NULL */
252 }
253 else if (isNull2)
254 {
255 if (ssup->ssup_nulls_first)
256 compare = 1; /* NOT_NULL ">" NULL */
257 else
258 compare = -1; /* NOT_NULL "<" NULL */
259 }
260 else
261 {
262 compare = ssup->abbrev_full_comparator(datum1, datum2, ssup);
263 if (ssup->ssup_reverse)
264 INVERT_COMPARE_RESULT(compare);
265 }
266
267 return compare;
268}
269
270/* Other functions in utils/sort/sortsupport.c */
271extern void PrepareSortSupportComparisonShim(Oid cmpFunc, SortSupport ssup);
272extern void PrepareSortSupportFromOrderingOp(Oid orderingOp, SortSupport ssup);
273extern void PrepareSortSupportFromIndexRel(Relation indexRel, int16 strategy,
274 SortSupport ssup);
275
276#endif /* SORTSUPPORT_H */
277