Age Owner Branch data TLA Line data Source code
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 : : */
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 : : */
199 : : static inline int
4512 tgl@sss.pgh.pa.us 200 :CBC 349694069 : ApplySortComparator(Datum datum1, bool isNull1,
201 : : Datum datum2, bool isNull2,
202 : : SortSupport ssup)
203 : : {
204 : : int compare;
205 : :
206 [ + + ]: 349694069 : if (isNull1)
207 : : {
208 [ + + ]: 207466 : if (isNull2)
209 : 191733 : compare = 0; /* NULL "=" NULL */
210 [ + + ]: 15733 : else if (ssup->ssup_nulls_first)
211 : 2506 : compare = -1; /* NULL "<" NOT_NULL */
212 : : else
213 : 13227 : compare = 1; /* NULL ">" NOT_NULL */
214 : : }
215 [ + + ]: 349486603 : else if (isNull2)
216 : : {
217 [ + + ]: 23504 : if (ssup->ssup_nulls_first)
218 : 51 : compare = 1; /* NOT_NULL ">" NULL */
219 : : else
220 : 23453 : compare = -1; /* NOT_NULL "<" NULL */
221 : : }
222 : : else
223 : : {
2411 peter_e@gmx.net 224 : 349463099 : compare = ssup->comparator(datum1, datum2, ssup);
4512 tgl@sss.pgh.pa.us 225 [ + + ]: 349463099 : if (ssup->ssup_reverse)
2018 226 [ + + ]: 4591548 : INVERT_COMPARE_RESULT(compare);
227 : : }
228 : :
4512 229 : 349694069 : return compare;
230 : : }
231 : :
232 : : static inline int
743 john.naylor@postgres 233 : 23184484 : ApplyUnsignedSortComparator(Datum datum1, bool isNull1,
234 : : Datum datum2, bool isNull2,
235 : : SortSupport ssup)
236 : : {
237 : : int compare;
238 : :
239 [ + + ]: 23184484 : if (isNull1)
240 : : {
241 [ + + ]: 1792 : if (isNull2)
242 : 175 : compare = 0; /* NULL "=" NULL */
243 [ + + ]: 1617 : else if (ssup->ssup_nulls_first)
244 : 114 : compare = -1; /* NULL "<" NOT_NULL */
245 : : else
246 : 1503 : compare = 1; /* NULL ">" NOT_NULL */
247 : : }
248 [ + + ]: 23182692 : else if (isNull2)
249 : : {
250 [ + + ]: 430 : if (ssup->ssup_nulls_first)
251 : 25 : compare = 1; /* NOT_NULL ">" NULL */
252 : : else
253 : 405 : compare = -1; /* NOT_NULL "<" NULL */
254 : : }
255 : : else
256 : : {
257 [ + + ]: 23182262 : compare = datum1 < datum2 ? -1 : datum1 > datum2 ? 1 : 0;
258 [ + + ]: 23182262 : if (ssup->ssup_reverse)
259 [ + + ]: 701299 : INVERT_COMPARE_RESULT(compare);
260 : : }
261 : :
262 : 23184484 : return compare;
263 : : }
264 : :
265 : : #if SIZEOF_DATUM >= 8
266 : : static inline int
267 : 2815248 : ApplySignedSortComparator(Datum datum1, bool isNull1,
268 : : Datum datum2, bool isNull2,
269 : : SortSupport ssup)
270 : : {
271 : : int compare;
272 : :
273 [ + + ]: 2815248 : if (isNull1)
274 : : {
275 [ + - ]: 6 : if (isNull2)
276 : 6 : compare = 0; /* NULL "=" NULL */
743 john.naylor@postgres 277 [ # # ]:UBC 0 : else if (ssup->ssup_nulls_first)
278 : 0 : compare = -1; /* NULL "<" NOT_NULL */
279 : : else
280 : 0 : compare = 1; /* NULL ">" NOT_NULL */
281 : : }
743 john.naylor@postgres 282 [ + + ]:CBC 2815242 : else if (isNull2)
283 : : {
284 [ - + ]: 6 : if (ssup->ssup_nulls_first)
743 john.naylor@postgres 285 :UBC 0 : compare = 1; /* NOT_NULL ">" NULL */
286 : : else
743 john.naylor@postgres 287 :CBC 6 : compare = -1; /* NOT_NULL "<" NULL */
288 : : }
289 : : else
290 : : {
703 291 [ + + ]: 2815236 : compare = DatumGetInt64(datum1) < DatumGetInt64(datum2) ? -1 :
292 : 832917 : DatumGetInt64(datum1) > DatumGetInt64(datum2) ? 1 : 0;
743 293 [ + + ]: 2815236 : if (ssup->ssup_reverse)
294 [ + + ]: 1068 : INVERT_COMPARE_RESULT(compare);
295 : : }
296 : :
297 : 2815248 : return compare;
298 : : }
299 : : #endif
300 : :
301 : : static inline int
302 : 26137569 : ApplyInt32SortComparator(Datum datum1, bool isNull1,
303 : : Datum datum2, bool isNull2,
304 : : SortSupport ssup)
305 : : {
306 : : int compare;
307 : :
308 [ + + ]: 26137569 : if (isNull1)
309 : : {
310 [ + + ]: 18790 : if (isNull2)
311 : 17087 : compare = 0; /* NULL "=" NULL */
312 [ + + ]: 1703 : else if (ssup->ssup_nulls_first)
313 : 409 : compare = -1; /* NULL "<" NOT_NULL */
314 : : else
315 : 1294 : compare = 1; /* NULL ">" NOT_NULL */
316 : : }
317 [ + + ]: 26118779 : else if (isNull2)
318 : : {
319 [ + + ]: 1619 : if (ssup->ssup_nulls_first)
320 : 347 : compare = 1; /* NOT_NULL ">" NULL */
321 : : else
322 : 1272 : compare = -1; /* NOT_NULL "<" NULL */
323 : : }
324 : : else
325 : : {
703 326 [ + + ]: 26117160 : compare = DatumGetInt32(datum1) < DatumGetInt32(datum2) ? -1 :
327 : 15682234 : DatumGetInt32(datum1) > DatumGetInt32(datum2) ? 1 : 0;
743 328 [ + + ]: 26117160 : if (ssup->ssup_reverse)
329 [ + + ]: 2591652 : INVERT_COMPARE_RESULT(compare);
330 : : }
331 : :
332 : 26137569 : 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
3373 rhaas@postgresql.org 341 : 2262746 : ApplySortAbbrevFullComparator(Datum datum1, bool isNull1,
342 : : Datum datum2, bool isNull2,
343 : : SortSupport ssup)
344 : : {
345 : : int compare;
346 : :
347 [ + + ]: 2262746 : if (isNull1)
348 : : {
349 [ + - ]: 176 : if (isNull2)
350 : 176 : compare = 0; /* NULL "=" NULL */
3373 rhaas@postgresql.org 351 [ # # ]:UBC 0 : else if (ssup->ssup_nulls_first)
352 : 0 : compare = -1; /* NULL "<" NOT_NULL */
353 : : else
354 : 0 : compare = 1; /* NULL ">" NOT_NULL */
355 : : }
3373 rhaas@postgresql.org 356 [ - + ]:CBC 2262570 : else if (isNull2)
357 : : {
3373 rhaas@postgresql.org 358 [ # # ]:UBC 0 : if (ssup->ssup_nulls_first)
359 : 0 : compare = 1; /* NOT_NULL ">" NULL */
360 : : else
361 : 0 : compare = -1; /* NOT_NULL "<" NULL */
362 : : }
363 : : else
364 : : {
2411 peter_e@gmx.net 365 :CBC 2262570 : compare = ssup->abbrev_full_comparator(datum1, datum2, ssup);
3373 rhaas@postgresql.org 366 [ + + ]: 2262570 : if (ssup->ssup_reverse)
2018 tgl@sss.pgh.pa.us 367 [ + + ]: 198408 : INVERT_COMPARE_RESULT(compare);
368 : : }
369 : :
3373 rhaas@postgresql.org 370 : 2262746 : 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 */
|
