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.
26 * All sort support functions will be passed the address of the
27 * SortSupportData struct when called, so they can use it to store
28 * additional private data as needed. In particular, for collation-aware
29 * datatypes, the ssup_collation field is set before calling BTSORTSUPPORT
30 * and is available to all support functions. Additional opclass-dependent
31 * data can be stored using the ssup_extra field. Any such data
32 * should be allocated in the ssup_cxt memory context.
34 * Note: since pg_amproc functions are indexed by (lefttype, righttype)
35 * it is possible to associate a BTSORTSUPPORT function with a cross-type
36 * comparison. This could sensibly be used to provide a fast comparator
37 * function for such cases, but probably not any other acceleration method.
40 * Portions Copyright (c) 1996-2014, PostgreSQL Global Development Group
41 * Portions Copyright (c) 1994, Regents of the University of California
43 * src/include/utils/sortsupport.h
45 *-------------------------------------------------------------------------
50 #include "access/attnum.h"
51 #include "utils/relcache.h"
53 typedef struct SortSupportData *SortSupport;
55 typedef struct SortSupportData
58 * These fields are initialized before calling the BTSORTSUPPORT function
59 * and should not be changed later.
61 MemoryContext ssup_cxt; /* Context containing sort info */
62 Oid ssup_collation; /* Collation to use, or InvalidOid */
65 * Additional sorting parameters; but unlike ssup_collation, these can be
66 * changed after BTSORTSUPPORT is called, so don't use them in selecting
67 * sort support functions.
69 bool ssup_reverse; /* descending-order sort? */
70 bool ssup_nulls_first; /* sort nulls first? */
73 * These fields are workspace for callers, and should not be touched by
74 * opclass-specific functions.
76 AttrNumber ssup_attno; /* column number to sort */
79 * ssup_extra is zeroed before calling the BTSORTSUPPORT function, and is
80 * not touched subsequently by callers.
82 void *ssup_extra; /* Workspace for opclass functions */
85 * Function pointers are zeroed before calling the BTSORTSUPPORT function,
86 * and must be set by it for any acceleration methods it wants to supply.
87 * The comparator pointer must be set, others are optional.
91 * Comparator function has the same API as the traditional btree
92 * comparison function, ie, return <0, 0, or >0 according as x is less
93 * than, equal to, or greater than y. Note that x and y are guaranteed
94 * not null, and there is no way to return null either. Do not return
95 * INT_MIN, as callers are allowed to negate the result before using it.
97 int (*comparator) (Datum x, Datum y, SortSupport ssup);
100 * Additional sort-acceleration functions might be added here later.
106 * ApplySortComparator should be inlined if possible. See STATIC_IF_INLINE
109 #ifndef PG_USE_INLINE
110 extern int ApplySortComparator(Datum datum1, bool isNull1,
111 Datum datum2, bool isNull2,
113 #endif /* !PG_USE_INLINE */
114 #if defined(PG_USE_INLINE) || defined(SORTSUPPORT_INCLUDE_DEFINITIONS)
116 * Apply a sort comparator function and return a 3-way comparison result.
117 * This takes care of handling reverse-sort and NULLs-ordering properly.
120 ApplySortComparator(Datum datum1, bool isNull1,
121 Datum datum2, bool isNull2,
129 compare = 0; /* NULL "=" NULL */
130 else if (ssup->ssup_nulls_first)
131 compare = -1; /* NULL "<" NOT_NULL */
133 compare = 1; /* NULL ">" NOT_NULL */
137 if (ssup->ssup_nulls_first)
138 compare = 1; /* NOT_NULL ">" NULL */
140 compare = -1; /* NOT_NULL "<" NULL */
144 compare = (*ssup->comparator) (datum1, datum2, ssup);
145 if (ssup->ssup_reverse)
151 #endif /*-- PG_USE_INLINE || SORTSUPPORT_INCLUDE_DEFINITIONS */
153 /* Other functions in utils/sort/sortsupport.c */
154 extern void PrepareSortSupportComparisonShim(Oid cmpFunc, SortSupport ssup);
155 extern void PrepareSortSupportFromOrderingOp(Oid orderingOp, SortSupport ssup);
156 extern void PrepareSortSupportFromIndexRel(Relation indexRel, int16 strategy,
159 #endif /* SORTSUPPORT_H */