Skip to content

Commit c6e3ac1

Browse files
tglsfdctglsfdc
committed
Create a "sort support" interface API for faster sorting.
This patch creates an API whereby a btree index opclass can optionally provide non-SQL-callable support functions for sorting. In the initial patch, we only use this to provide a directly-callable comparator function, which can be invoked with a bit less overhead than the traditional SQL-callable comparator. While that should be of value in itself, the real reason for doing this is to provide a datatype-extensible framework for more aggressive optimizations, as in Peter Geoghegan's recent work. Robert Haas and Tom Lane
1 parent d2a6621 commit c6e3ac1

30 files changed

+870
-422
lines changed

‎doc/src/sgml/ref/alter_opfamily.sgml

Lines changed: 5 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -140,11 +140,12 @@ ALTER OPERATOR FAMILY <replaceable>name</replaceable> USING <replaceable class="
140140
<para>
141141
In an <literal>ADD FUNCTION</> clause, the operand data type(s) the
142142
function is intended to support, if different from
143-
the input data type(s) of the function. For B-tree and hash indexes
144-
it is not necessary to specify <replaceable
143+
the input data type(s) of the function. For B-tree comparison functions
144+
and hash functions it is not necessary to specify <replaceable
145145
class="parameter">op_type</replaceable> since the function's input
146-
data type(s) are always the correct ones to use. For GIN and GiST
147-
indexes it is necessary to specify the input data type the function
146+
data type(s) are always the correct ones to use. For B-tree sort
147+
support functions and all functions in GiST and GIN operator classes,
148+
it is necessary to specify the operand data type(s) the function
148149
is to be used with.
149150
</para>
150151

‎doc/src/sgml/ref/create_opclass.sgml

Lines changed: 8 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -169,13 +169,14 @@ CREATE OPERATOR CLASS <replaceable class="parameter">name</replaceable> [ DEFAUL
169169
<para>
170170
In a <literal>FUNCTION</> clause, the operand data type(s) the
171171
function is intended to support, if different from
172-
the input data type(s) of the function (for B-tree and hash indexes)
173-
or the class's data type (for GIN and GiST indexes). These defaults
174-
are always correct, so there is no point in specifying <replaceable
175-
class="parameter">op_type</replaceable> in a <literal>FUNCTION</> clause
176-
in <command>CREATE OPERATOR CLASS</>, but the option is provided
177-
for consistency with the comparable syntax in
178-
<command>ALTER OPERATOR FAMILY</>.
172+
the input data type(s) of the function (for B-tree comparison functions
173+
and hash functions)
174+
or the class's data type (for B-tree sort support functions and all
175+
functions in GiST and GIN operator classes). These defaults
176+
are correct, and so <replaceable
177+
class="parameter">op_type</replaceable> need not be specified in
178+
<literal>FUNCTION</> clauses, except for the case of a B-tree sort
179+
support function that is meant to support cross-data-type comparisons.
179180
</para>
180181
</listitem>
181182
</varlistentry>

‎doc/src/sgml/xindex.sgml

Lines changed: 23 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -311,7 +311,8 @@
311311
</para>
312312

313313
<para>
314-
B-trees require a single support function, shown in <xref
314+
B-trees require a single support function, and allow a second one to be
315+
supplied at the operator class author's option, as shown in <xref
315316
linkend="xindex-btree-support-table">.
316317
</para>
317318

@@ -333,12 +334,19 @@
333334
</entry>
334335
<entry>1</entry>
335336
</row>
337+
<row>
338+
<entry>
339+
Return the addresses of C-callable sort support function(s),
340+
as documented in <filename>utils/sortsupport.h</> (optional)
341+
</entry>
342+
<entry>2</entry>
343+
</row>
336344
</tbody>
337345
</tgroup>
338346
</table>
339347

340348
<para>
341-
Hash indexes likewise require one support function, shown in <xref
349+
Hash indexes require one support function, shown in <xref
342350
linkend="xindex-hash-support-table">.
343351
</para>
344352

@@ -363,6 +371,7 @@
363371
<para>
364372
GiST indexes require seven support functions, with an optional eighth, as
365373
shown in <xref linkend="xindex-gist-support-table">.
374+
(For more information see <xref linkend="GiST">.)
366375
</para>
367376

368377
<table tocentry="1" id="xindex-gist-support-table">
@@ -418,9 +427,7 @@
418427
</row>
419428
<row>
420429
<entry><function>distance</></entry>
421-
<entry>
422-
(optional method) determine distance from key to query value
423-
</entry>
430+
<entry>determine distance from key to query value (optional)</entry>
424431
<entry>8</entry>
425432
</row>
426433
</tbody>
@@ -430,6 +437,7 @@
430437
<para>
431438
GIN indexes require four support functions, with an optional fifth, as
432439
shown in <xref linkend="xindex-gin-support-table">.
440+
(For more information see <xref linkend="GIN">.)
433441
</para>
434442

435443
<table tocentry="1" id="xindex-gin-support-table">
@@ -470,10 +478,10 @@
470478
<row>
471479
<entry><function>comparePartial</></entry>
472480
<entry>
473-
(optional method) compare partial key from
481+
compare partial key from
474482
query and key from index, and return an integer less than zero, zero,
475483
or greater than zero, indicating whether GIN should ignore this index
476-
entry, treat the entry as a match, or stop the index scan
484+
entry, treat the entry as a match, or stop the index scan (optional)
477485
</entry>
478486
<entry>5</entry>
479487
</row>
@@ -486,7 +494,8 @@
486494
type the particular index method expects; for example in the case
487495
of the comparison function for B-trees, a signed integer. The number
488496
and types of the arguments to each support function are likewise
489-
dependent on the index method. For B-tree and hash the support functions
497+
dependent on the index method. For B-tree and hash the comparison and
498+
hashing support functions
490499
take the same input data types as do the operators included in the operator
491500
class, but this is not the case for most GIN and GiST support functions.
492501
</para>
@@ -748,7 +757,8 @@ DEFAULT FOR TYPE int8 USING btree FAMILY integer_ops AS
748757
OPERATOR 3 = ,
749758
OPERATOR 4 >= ,
750759
OPERATOR 5 > ,
751-
FUNCTION 1 btint8cmp(int8, int8) ;
760+
FUNCTION 1 btint8cmp(int8, int8) ,
761+
FUNCTION 2 btint8sortsupport(internal) ;
752762

753763
CREATE OPERATOR CLASS int4_ops
754764
DEFAULT FOR TYPE int4 USING btree FAMILY integer_ops AS
@@ -758,7 +768,8 @@ DEFAULT FOR TYPE int4 USING btree FAMILY integer_ops AS
758768
OPERATOR 3 = ,
759769
OPERATOR 4 >= ,
760770
OPERATOR 5 > ,
761-
FUNCTION 1 btint4cmp(int4, int4) ;
771+
FUNCTION 1 btint4cmp(int4, int4) ,
772+
FUNCTION 2 btint4sortsupport(internal) ;
762773

763774
CREATE OPERATOR CLASS int2_ops
764775
DEFAULT FOR TYPE int2 USING btree FAMILY integer_ops AS
@@ -768,7 +779,8 @@ DEFAULT FOR TYPE int2 USING btree FAMILY integer_ops AS
768779
OPERATOR 3 = ,
769780
OPERATOR 4 >= ,
770781
OPERATOR 5 > ,
771-
FUNCTION 1 btint2cmp(int2, int2) ;
782+
FUNCTION 1 btint2cmp(int2, int2) ,
783+
FUNCTION 2 btint2sortsupport(internal) ;
772784

773785
ALTER OPERATOR FAMILY integer_ops USING btree ADD
774786
-- cross-type comparisons int8 vs int2

‎src/backend/access/nbtree/nbtcompare.c

Lines changed: 106 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -49,6 +49,7 @@
4949
#include "postgres.h"
5050

5151
#include "utils/builtins.h"
52+
#include "utils/sortsupport.h"
5253

5354

5455
Datum
@@ -69,6 +70,24 @@ btint2cmp(PG_FUNCTION_ARGS)
6970
PG_RETURN_INT32((int32) a - (int32) b);
7071
}
7172

73+
static int
74+
btint2fastcmp(Datum x, Datum y, SortSupport ssup)
75+
{
76+
int16 a = DatumGetInt16(x);
77+
int16 b = DatumGetInt16(y);
78+
79+
return (int) a - (int) b;
80+
}
81+
82+
Datum
83+
btint2sortsupport(PG_FUNCTION_ARGS)
84+
{
85+
SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
86+
87+
ssup->comparator = btint2fastcmp;
88+
PG_RETURN_VOID();
89+
}
90+
7291
Datum
7392
btint4cmp(PG_FUNCTION_ARGS)
7493
{
@@ -83,6 +102,29 @@ btint4cmp(PG_FUNCTION_ARGS)
83102
PG_RETURN_INT32(-1);
84103
}
85104

105+
static int
106+
btint4fastcmp(Datum x, Datum y, SortSupport ssup)
107+
{
108+
int32 a = DatumGetInt32(x);
109+
int32 b = DatumGetInt32(y);
110+
111+
if (a > b)
112+
return 1;
113+
else if (a == b)
114+
return 0;
115+
else
116+
return -1;
117+
}
118+
119+
Datum
120+
btint4sortsupport(PG_FUNCTION_ARGS)
121+
{
122+
SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
123+
124+
ssup->comparator = btint4fastcmp;
125+
PG_RETURN_VOID();
126+
}
127+
86128
Datum
87129
btint8cmp(PG_FUNCTION_ARGS)
88130
{
@@ -97,6 +139,29 @@ btint8cmp(PG_FUNCTION_ARGS)
97139
PG_RETURN_INT32(-1);
98140
}
99141

142+
static int
143+
btint8fastcmp(Datum x, Datum y, SortSupport ssup)
144+
{
145+
int64 a = DatumGetInt64(x);
146+
int64 b = DatumGetInt64(y);
147+
148+
if (a > b)
149+
return 1;
150+
else if (a == b)
151+
return 0;
152+
else
153+
return -1;
154+
}
155+
156+
Datum
157+
btint8sortsupport(PG_FUNCTION_ARGS)
158+
{
159+
SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
160+
161+
ssup->comparator = btint8fastcmp;
162+
PG_RETURN_VOID();
163+
}
164+
100165
Datum
101166
btint48cmp(PG_FUNCTION_ARGS)
102167
{
@@ -195,6 +260,29 @@ btoidcmp(PG_FUNCTION_ARGS)
195260
PG_RETURN_INT32(-1);
196261
}
197262

263+
static int
264+
btoidfastcmp(Datum x, Datum y, SortSupport ssup)
265+
{
266+
Oid a = DatumGetObjectId(x);
267+
Oid b = DatumGetObjectId(y);
268+
269+
if (a > b)
270+
return 1;
271+
else if (a == b)
272+
return 0;
273+
else
274+
return -1;
275+
}
276+
277+
Datum
278+
btoidsortsupport(PG_FUNCTION_ARGS)
279+
{
280+
SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
281+
282+
ssup->comparator = btoidfastcmp;
283+
PG_RETURN_VOID();
284+
}
285+
198286
Datum
199287
btoidvectorcmp(PG_FUNCTION_ARGS)
200288
{
@@ -237,3 +325,21 @@ btnamecmp(PG_FUNCTION_ARGS)
237325

238326
PG_RETURN_INT32(strncmp(NameStr(*a), NameStr(*b), NAMEDATALEN));
239327
}
328+
329+
static int
330+
btnamefastcmp(Datum x, Datum y, SortSupport ssup)
331+
{
332+
Name a = DatumGetName(x);
333+
Name b = DatumGetName(y);
334+
335+
return strncmp(NameStr(*a), NameStr(*b), NAMEDATALEN);
336+
}
337+
338+
Datum
339+
btnamesortsupport(PG_FUNCTION_ARGS)
340+
{
341+
SortSupport ssup = (SortSupport) PG_GETARG_POINTER(0);
342+
343+
ssup->comparator = btnamefastcmp;
344+
PG_RETURN_VOID();
345+
}

‎src/backend/commands/analyze.c

Lines changed: 13 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -47,8 +47,8 @@
4747
#include "utils/lsyscache.h"
4848
#include "utils/memutils.h"
4949
#include "utils/pg_rusage.h"
50+
#include "utils/sortsupport.h"
5051
#include "utils/syscache.h"
51-
#include "utils/tuplesort.h"
5252
#include "utils/timestamp.h"
5353
#include "utils/tqual.h"
5454

@@ -1774,8 +1774,7 @@ typedef struct
17741774

17751775
typedef struct
17761776
{
1777-
FmgrInfo *cmpFn;
1778-
int cmpFlags;
1777+
SortSupport ssup;
17791778
int *tupnoLink;
17801779
} CompareScalarsContext;
17811780

@@ -2222,9 +2221,7 @@ compute_scalar_stats(VacAttrStatsP stats,
22222221
bool is_varwidth = (!stats->attrtype->typbyval &&
22232222
stats->attrtype->typlen < 0);
22242223
double corr_xysum;
2225-
Oid cmpFn;
2226-
int cmpFlags;
2227-
FmgrInfo f_cmpfn;
2224+
SortSupportData ssup;
22282225
ScalarItem *values;
22292226
int values_cnt = 0;
22302227
int *tupnoLink;
@@ -2238,8 +2235,13 @@ compute_scalar_stats(VacAttrStatsP stats,
22382235
tupnoLink = (int *) palloc(samplerows * sizeof(int));
22392236
track = (ScalarMCVItem *) palloc(num_mcv * sizeof(ScalarMCVItem));
22402237

2241-
SelectSortFunction(mystats->ltopr, false, &cmpFn, &cmpFlags);
2242-
fmgr_info(cmpFn, &f_cmpfn);
2238+
memset(&ssup, 0, sizeof(ssup));
2239+
ssup.ssup_cxt = CurrentMemoryContext;
2240+
/* We always use the default collation for statistics */
2241+
ssup.ssup_collation = DEFAULT_COLLATION_OID;
2242+
ssup.ssup_nulls_first = false;
2243+
2244+
PrepareSortSupportFromOrderingOp(mystats->ltopr, &ssup);
22432245

22442246
/* Initial scan to find sortable values */
22452247
for (i = 0; i < samplerows; i++)
@@ -2307,8 +2309,7 @@ compute_scalar_stats(VacAttrStatsP stats,
23072309
CompareScalarsContext cxt;
23082310

23092311
/* Sort the collected values */
2310-
cxt.cmpFn = &f_cmpfn;
2311-
cxt.cmpFlags = cmpFlags;
2312+
cxt.ssup = &ssup;
23122313
cxt.tupnoLink = tupnoLink;
23132314
qsort_arg((void *) values, values_cnt, sizeof(ScalarItem),
23142315
compare_scalars, (void *) &cxt);
@@ -2712,12 +2713,9 @@ compare_scalars(const void *a, const void *b, void *arg)
27122713
Datum db = ((const ScalarItem *) b)->value;
27132714
int tb = ((const ScalarItem *) b)->tupno;
27142715
CompareScalarsContext *cxt = (CompareScalarsContext *) arg;
2715-
int32 compare;
2716+
int compare;
27162717

2717-
/* We always use the default collation for statistics */
2718-
compare = ApplySortFunction(cxt->cmpFn, cxt->cmpFlags,
2719-
DEFAULT_COLLATION_OID,
2720-
da, false, db, false);
2718+
compare = ApplySortComparator(da, false, db, false, cxt->ssup);
27212719
if (compare != 0)
27222720
return compare;
27232721

0 commit comments

Comments
 (0)