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-2017, 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. Do not return
100 : * INT_MIN, as callers are allowed to negate the result before using it.
101 : *
102 : * This may be either the authoritative comparator, or the abbreviated
103 : * comparator. Core code may switch this over the initial preference of
104 : * an opclass support function despite originally indicating abbreviation
105 : * was applicable, by assigning the authoritative comparator back.
106 : */
107 : int (*comparator) (Datum x, Datum y, SortSupport ssup);
108 :
109 : /*
110 : * "Abbreviated key" infrastructure follows.
111 : *
112 : * All callbacks must be set by sortsupport opclasses that make use of
113 : * this optional additional infrastructure (unless for whatever reasons
114 : * the opclass doesn't proceed with abbreviation, in which case
115 : * abbrev_converter must not be set).
116 : *
117 : * This allows opclass authors to supply a conversion routine, used to
118 : * create an alternative representation of the underlying type (an
119 : * "abbreviated key"). This representation must be pass-by-value and
120 : * typically will use some ad-hoc format that only the opclass has
121 : * knowledge of. An alternative comparator, used only with this
122 : * alternative representation must also be provided (which is assigned to
123 : * "comparator"). This representation is a simple approximation of the
124 : * original Datum. It must be possible to compare datums of this
125 : * representation with each other using the supplied alternative
126 : * comparator, and have any non-zero return value be a reliable proxy for
127 : * what a proper comparison would indicate. Returning zero from the
128 : * alternative comparator does not indicate equality, as with a
129 : * conventional support routine 1, though -- it indicates that it wasn't
130 : * possible to determine how the two abbreviated values compared. A
131 : * proper comparison, using "abbrev_full_comparator"/
132 : * ApplySortAbbrevFullComparator() is therefore required. In many cases
133 : * this results in most or all comparisons only using the cheap
134 : * alternative comparison func, which is typically implemented as code
135 : * that compiles to just a few CPU instructions. CPU cache miss penalties
136 : * are expensive; to get good overall performance, sort infrastructure
137 : * must heavily weigh cache performance.
138 : *
139 : * Opclass authors must consider the final cardinality of abbreviated keys
140 : * when devising an encoding scheme. It's possible for a strategy to work
141 : * better than an alternative strategy with one usage pattern, while the
142 : * reverse might be true for another usage pattern. All of these factors
143 : * must be considered.
144 : */
145 :
146 : /*
147 : * "abbreviate" concerns whether or not the abbreviated key optimization
148 : * is applicable in principle (that is, the sortsupport routine needs to
149 : * know if its dealing with a key where an abbreviated representation can
150 : * usefully be packed together. Conventionally, this is the leading
151 : * attribute key). Note, however, that in order to determine that
152 : * abbreviation is not in play, the core code always checks whether or not
153 : * the opclass has set abbrev_converter. This is a one way, one time
154 : * message to the opclass.
155 : */
156 : bool abbreviate;
157 :
158 : /*
159 : * Converter to abbreviated format, from original representation. Core
160 : * code uses this callback to convert from a pass-by-reference "original"
161 : * Datum to a pass-by-value abbreviated key Datum. Note that original is
162 : * guaranteed NOT NULL, because it doesn't make sense to factor NULLness
163 : * into ad-hoc cost model.
164 : *
165 : * abbrev_converter is tested to see if abbreviation is in play. Core
166 : * code may set it to NULL to indicate abbreviation should not be used
167 : * (which is something sortsupport routines need not concern themselves
168 : * with). However, sortsupport routines must not set it when it is
169 : * immediately established that abbreviation should not proceed (e.g., for
170 : * !abbreviate calls, or due to platform-specific impediments to using
171 : * abbreviation).
172 : */
173 : Datum (*abbrev_converter) (Datum original, SortSupport ssup);
174 :
175 : /*
176 : * abbrev_abort callback allows clients to verify that the current
177 : * strategy is working out, using a sortsupport routine defined ad-hoc
178 : * cost model. If there is a lot of duplicate abbreviated keys in
179 : * practice, it's useful to be able to abandon the strategy before paying
180 : * too high a cost in conversion (perhaps certain opclass-specific
181 : * adaptations are useful too).
182 : */
183 : bool (*abbrev_abort) (int memtupcount, SortSupport ssup);
184 :
185 : /*
186 : * Full, authoritative comparator for key that an abbreviated
187 : * representation was generated for, used when an abbreviated comparison
188 : * was inconclusive (by calling ApplySortComparatorFull()), or used to
189 : * replace "comparator" when core system ultimately decides against
190 : * abbreviation.
191 : */
192 : int (*abbrev_full_comparator) (Datum x, Datum y, SortSupport ssup);
193 : } SortSupportData;
194 :
195 :
196 : /*
197 : * Apply a sort comparator function and return a 3-way comparison result.
198 : * This takes care of handling reverse-sort and NULLs-ordering properly.
199 : */
200 : static inline int
201 30426100 : ApplySortComparator(Datum datum1, bool isNull1,
202 : Datum datum2, bool isNull2,
203 : SortSupport ssup)
204 : {
205 : int compare;
206 :
207 30426100 : if (isNull1)
208 : {
209 2506 : if (isNull2)
210 1429 : compare = 0; /* NULL "=" NULL */
211 1077 : else if (ssup->ssup_nulls_first)
212 609 : compare = -1; /* NULL "<" NOT_NULL */
213 : else
214 468 : compare = 1; /* NULL ">" NOT_NULL */
215 : }
216 30423594 : else if (isNull2)
217 : {
218 441 : if (ssup->ssup_nulls_first)
219 52 : compare = 1; /* NOT_NULL ">" NULL */
220 : else
221 389 : compare = -1; /* NOT_NULL "<" NULL */
222 : }
223 : else
224 : {
225 30423153 : compare = (*ssup->comparator) (datum1, datum2, ssup);
226 30423153 : if (ssup->ssup_reverse)
227 102688 : compare = -compare;
228 : }
229 :
230 30426100 : return compare;
231 : }
232 :
233 : /*
234 : * Apply a sort comparator function and return a 3-way comparison using full,
235 : * authoritative comparator. This takes care of handling reverse-sort and
236 : * NULLs-ordering properly.
237 : */
238 : static inline int
239 3416 : ApplySortAbbrevFullComparator(Datum datum1, bool isNull1,
240 : Datum datum2, bool isNull2,
241 : SortSupport ssup)
242 : {
243 : int compare;
244 :
245 3416 : if (isNull1)
246 : {
247 2 : if (isNull2)
248 2 : compare = 0; /* NULL "=" NULL */
249 0 : else if (ssup->ssup_nulls_first)
250 0 : compare = -1; /* NULL "<" NOT_NULL */
251 : else
252 0 : compare = 1; /* NULL ">" NOT_NULL */
253 : }
254 3414 : else if (isNull2)
255 : {
256 0 : if (ssup->ssup_nulls_first)
257 0 : compare = 1; /* NOT_NULL ">" NULL */
258 : else
259 0 : compare = -1; /* NOT_NULL "<" NULL */
260 : }
261 : else
262 : {
263 3414 : compare = (*ssup->abbrev_full_comparator) (datum1, datum2, ssup);
264 3414 : if (ssup->ssup_reverse)
265 0 : compare = -compare;
266 : }
267 :
268 3416 : return compare;
269 : }
270 :
271 : /* Other functions in utils/sort/sortsupport.c */
272 : extern void PrepareSortSupportComparisonShim(Oid cmpFunc, SortSupport ssup);
273 : extern void PrepareSortSupportFromOrderingOp(Oid orderingOp, SortSupport ssup);
274 : extern void PrepareSortSupportFromIndexRel(Relation indexRel, int16 strategy,
275 : SortSupport ssup);
276 :
277 : #endif /* SORTSUPPORT_H */
|
