codekingpro/portable-devtools

1/*-------------------------------------------------------------------------2 *3 * sortsupport.h4 *	  Framework for accelerated sorting.5 *6 * Traditionally, PostgreSQL has implemented sorting by repeatedly invoking7 * an SQL-callable comparison function "cmp(x, y) returns int" on pairs of8 * values to be compared, where the comparison function is the BTORDER_PROC9 * pg_amproc support function of the appropriate btree index opclass.10 *11 * This file defines alternative APIs that allow sorting to be performed with12 * reduced overhead.  To support lower-overhead sorting, a btree opclass may13 * provide a BTSORTSUPPORT_PROC pg_amproc entry, which must take a single14 * argument of type internal and return void.  The argument is actually a15 * 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 allow20 * multiple acceleration mechanisms to be supported, but no opclass is21 * required to provide all of them.  The BTSORTSUPPORT function should22 * simply not set any function pointers for mechanisms it doesn't support.23 * Opclasses that provide BTSORTSUPPORT and don't provide a comparator24 * function will have a shim set up by sort support automatically.  However,25 * opclasses that support the optional additional abbreviated key capability26 * must always provide an authoritative comparator used to tie-break27 * inconclusive abbreviated comparisons and also used when aborting28 * abbreviation.  Furthermore, a converter and abort/costing function must be29 * provided.30 *31 * All sort support functions will be passed the address of the32 * SortSupportData struct when called, so they can use it to store33 * additional private data as needed.  In particular, for collation-aware34 * datatypes, the ssup_collation field is set before calling BTSORTSUPPORT35 * and is available to all support functions.  Additional opclass-dependent36 * data can be stored using the ssup_extra field.  Any such data37 * 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-type41 * comparison.  This could sensibly be used to provide a fast comparator42 * function for such cases, but probably not any other acceleration method.43 *44 *45 * Portions Copyright (c) 1996-2023, PostgreSQL Global Development Group46 * Portions Copyright (c) 1994, Regents of the University of California47 *48 * src/include/utils/sortsupport.h49 *50 *-------------------------------------------------------------------------51 */52#ifndef SORTSUPPORT_H53#define SORTSUPPORT_H54 55#include "access/attnum.h"56#include "utils/relcache.h"57 58typedef struct SortSupportData *SortSupport;59 60typedef struct SortSupportData61{62	/*63	 * These fields are initialized before calling the BTSORTSUPPORT function64	 * 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 be71	 * changed after BTSORTSUPPORT is called, so don't use them in selecting72	 * 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 by79	 * 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 is85	 * 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 btree97	 * comparison function, ie, return <0, 0, or >0 according as x is less98	 * than, equal to, or greater than y.  Note that x and y are guaranteed99	 * not null, and there is no way to return null either.100	 *101	 * This may be either the authoritative comparator, or the abbreviated102	 * comparator.  Core code may switch this over the initial preference of103	 * an opclass support function despite originally indicating abbreviation104	 * 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 of112	 * this optional additional infrastructure (unless for whatever reasons113	 * the opclass doesn't proceed with abbreviation, in which case114	 * abbrev_converter must not be set).115	 *116	 * This allows opclass authors to supply a conversion routine, used to117	 * create an alternative representation of the underlying type (an118	 * "abbreviated key").  This representation must be pass-by-value and119	 * typically will use some ad-hoc format that only the opclass has120	 * knowledge of.  An alternative comparator, used only with this121	 * alternative representation must also be provided (which is assigned to122	 * "comparator").  This representation is a simple approximation of the123	 * original Datum.  It must be possible to compare datums of this124	 * representation with each other using the supplied alternative125	 * comparator, and have any non-zero return value be a reliable proxy for126	 * what a proper comparison would indicate. Returning zero from the127	 * alternative comparator does not indicate equality, as with a128	 * conventional support routine 1, though -- it indicates that it wasn't129	 * possible to determine how the two abbreviated values compared.  A130	 * proper comparison, using "abbrev_full_comparator"/131	 * ApplySortAbbrevFullComparator() is therefore required.  In many cases132	 * this results in most or all comparisons only using the cheap133	 * alternative comparison func, which is typically implemented as code134	 * that compiles to just a few CPU instructions.  CPU cache miss penalties135	 * are expensive; to get good overall performance, sort infrastructure136	 * must heavily weigh cache performance.137	 *138	 * Opclass authors must consider the final cardinality of abbreviated keys139	 * when devising an encoding scheme.  It's possible for a strategy to work140	 * better than an alternative strategy with one usage pattern, while the141	 * reverse might be true for another usage pattern.  All of these factors142	 * must be considered.143	 */144 145	/*146	 * "abbreviate" concerns whether or not the abbreviated key optimization147	 * is applicable in principle (that is, the sortsupport routine needs to148	 * know if its dealing with a key where an abbreviated representation can149	 * usefully be packed together.  Conventionally, this is the leading150	 * attribute key).  Note, however, that in order to determine that151	 * abbreviation is not in play, the core code always checks whether or not152	 * the opclass has set abbrev_converter.  This is a one way, one time153	 * message to the opclass.154	 */155	bool		abbreviate;156 157	/*158	 * Converter to abbreviated format, from original representation.  Core159	 * 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 is161	 * guaranteed NOT NULL, because it doesn't make sense to factor NULLness162	 * into ad-hoc cost model.163	 *164	 * abbrev_converter is tested to see if abbreviation is in play.  Core165	 * code may set it to NULL to indicate abbreviation should not be used166	 * (which is something sortsupport routines need not concern themselves167	 * with). However, sortsupport routines must not set it when it is168	 * immediately established that abbreviation should not proceed (e.g., for169	 * !abbreviate calls, or due to platform-specific impediments to using170	 * abbreviation).171	 */172	Datum		(*abbrev_converter) (Datum original, SortSupport ssup);173 174	/*175	 * abbrev_abort callback allows clients to verify that the current176	 * strategy is working out, using a sortsupport routine defined ad-hoc177	 * cost model. If there is a lot of duplicate abbreviated keys in178	 * practice, it's useful to be able to abandon the strategy before paying179	 * too high a cost in conversion (perhaps certain opclass-specific180	 * adaptations are useful too).181	 */182	bool		(*abbrev_abort) (int memtupcount, SortSupport ssup);183 184	/*185	 * Full, authoritative comparator for key that an abbreviated186	 * representation was generated for, used when an abbreviated comparison187	 * was inconclusive (by calling ApplySortAbbrevFullComparator()), or used188	 * to replace "comparator" when core system ultimately decides against189	 * 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 int200ApplySortComparator(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		else213			compare = 1;		/* NULL ">" NOT_NULL */214	}215	else if (isNull2)216	{217		if (ssup->ssup_nulls_first)218			compare = 1;		/* NOT_NULL ">" NULL */219		else220			compare = -1;		/* NOT_NULL "<" NULL */221	}222	else223	{224		compare = ssup->comparator(datum1, datum2, ssup);225		if (ssup->ssup_reverse)226			INVERT_COMPARE_RESULT(compare);227	}228 229	return compare;230}231 232static inline int233ApplyUnsignedSortComparator(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		else246			compare = 1;		/* NULL ">" NOT_NULL */247	}248	else if (isNull2)249	{250		if (ssup->ssup_nulls_first)251			compare = 1;		/* NOT_NULL ">" NULL */252		else253			compare = -1;		/* NOT_NULL "<" NULL */254	}255	else256	{257		compare = datum1 < datum2 ? -1 : datum1 > datum2 ? 1 : 0;258		if (ssup->ssup_reverse)259			INVERT_COMPARE_RESULT(compare);260	}261 262	return compare;263}264 265#if SIZEOF_DATUM >= 8266static inline int267ApplySignedSortComparator(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		else280			compare = 1;		/* NULL ">" NOT_NULL */281	}282	else if (isNull2)283	{284		if (ssup->ssup_nulls_first)285			compare = 1;		/* NOT_NULL ">" NULL */286		else287			compare = -1;		/* NOT_NULL "<" NULL */288	}289	else290	{291		compare = DatumGetInt64(datum1) < DatumGetInt64(datum2) ? -1 :292			DatumGetInt64(datum1) > DatumGetInt64(datum2) ? 1 : 0;293		if (ssup->ssup_reverse)294			INVERT_COMPARE_RESULT(compare);295	}296 297	return compare;298}299#endif300 301static inline int302ApplyInt32SortComparator(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		else315			compare = 1;		/* NULL ">" NOT_NULL */316	}317	else if (isNull2)318	{319		if (ssup->ssup_nulls_first)320			compare = 1;		/* NOT_NULL ">" NULL */321		else322			compare = -1;		/* NOT_NULL "<" NULL */323	}324	else325	{326		compare = DatumGetInt32(datum1) < DatumGetInt32(datum2) ? -1 :327			DatumGetInt32(datum1) > DatumGetInt32(datum2) ? 1 : 0;328		if (ssup->ssup_reverse)329			INVERT_COMPARE_RESULT(compare);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 and338 * NULLs-ordering properly.339 */340static inline int341ApplySortAbbrevFullComparator(Datum datum1, bool isNull1,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		else354			compare = 1;		/* NULL ">" NOT_NULL */355	}356	else if (isNull2)357	{358		if (ssup->ssup_nulls_first)359			compare = 1;		/* NOT_NULL ">" NULL */360		else361			compare = -1;		/* NOT_NULL "<" NULL */362	}363	else364	{365		compare = ssup->abbrev_full_comparator(datum1, datum2, ssup);366		if (ssup->ssup_reverse)367			INVERT_COMPARE_RESULT(compare);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 comparator376 * are eligible for faster sorting.377 */378extern int	ssup_datum_unsigned_cmp(Datum x, Datum y, SortSupport ssup);379#if SIZEOF_DATUM >= 8380extern int	ssup_datum_signed_cmp(Datum x, Datum y, SortSupport ssup);381#endif382extern int	ssup_datum_int32_cmp(Datum x, Datum y, SortSupport ssup);383 384/* Other functions in utils/sort/sortsupport.c */385extern void PrepareSortSupportComparisonShim(Oid cmpFunc, SortSupport ssup);386extern void PrepareSortSupportFromOrderingOp(Oid orderingOp, SortSupport ssup);387extern void PrepareSortSupportFromIndexRel(Relation indexRel, int16 strategy,388										   SortSupport ssup);389extern void PrepareSortSupportFromGistIndexRel(Relation indexRel, SortSupport ssup);390 391#endif							/* SORTSUPPORT_H */392