1 /*-------------------------------------------------------------------------
4 * Utility routines for the Postgres inverted index access method.
7 * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group
8 * Portions Copyright (c) 1994, Regents of the University of California
11 * src/backend/access/gin/ginutil.c
12 *-------------------------------------------------------------------------
17 #include "access/gin_private.h"
18 #include "access/ginxlog.h"
19 #include "access/reloptions.h"
20 #include "access/xloginsert.h"
21 #include "catalog/pg_collation.h"
22 #include "catalog/pg_type.h"
23 #include "miscadmin.h"
24 #include "storage/indexfsm.h"
25 #include "storage/lmgr.h"
26 #include "storage/predicate.h"
27 #include "utils/builtins.h"
28 #include "utils/index_selfuncs.h"
29 #include "utils/typcache.h"
33 * GIN handler function: return IndexAmRoutine with access method parameters
37 ginhandler(PG_FUNCTION_ARGS)
39 IndexAmRoutine *amroutine = makeNode(IndexAmRoutine);
41 amroutine->amstrategies = 0;
42 amroutine->amsupport = GINNProcs;
43 amroutine->amcanorder = false;
44 amroutine->amcanorderbyop = false;
45 amroutine->amcanbackward = false;
46 amroutine->amcanunique = false;
47 amroutine->amcanmulticol = true;
48 amroutine->amoptionalkey = true;
49 amroutine->amsearcharray = false;
50 amroutine->amsearchnulls = false;
51 amroutine->amstorage = true;
52 amroutine->amclusterable = false;
53 amroutine->ampredlocks = true;
54 amroutine->amcanparallel = false;
55 amroutine->amcaninclude = false;
56 amroutine->amkeytype = InvalidOid;
58 amroutine->ambuild = ginbuild;
59 amroutine->ambuildempty = ginbuildempty;
60 amroutine->aminsert = gininsert;
61 amroutine->ambulkdelete = ginbulkdelete;
62 amroutine->amvacuumcleanup = ginvacuumcleanup;
63 amroutine->amcanreturn = NULL;
64 amroutine->amcostestimate = gincostestimate;
65 amroutine->amoptions = ginoptions;
66 amroutine->amproperty = NULL;
67 amroutine->ambuildphasename = NULL;
68 amroutine->amvalidate = ginvalidate;
69 amroutine->ambeginscan = ginbeginscan;
70 amroutine->amrescan = ginrescan;
71 amroutine->amgettuple = NULL;
72 amroutine->amgetbitmap = gingetbitmap;
73 amroutine->amendscan = ginendscan;
74 amroutine->ammarkpos = NULL;
75 amroutine->amrestrpos = NULL;
76 amroutine->amestimateparallelscan = NULL;
77 amroutine->aminitparallelscan = NULL;
78 amroutine->amparallelrescan = NULL;
80 PG_RETURN_POINTER(amroutine);
84 * initGinState: fill in an empty GinState struct to describe the index
86 * Note: assorted subsidiary data is allocated in the CurrentMemoryContext.
89 initGinState(GinState *state, Relation index)
91 TupleDesc origTupdesc = RelationGetDescr(index);
94 MemSet(state, 0, sizeof(GinState));
97 state->oneCol = (origTupdesc->natts == 1) ? true : false;
98 state->origTupdesc = origTupdesc;
100 for (i = 0; i < origTupdesc->natts; i++)
102 Form_pg_attribute attr = TupleDescAttr(origTupdesc, i);
105 state->tupdesc[i] = state->origTupdesc;
108 state->tupdesc[i] = CreateTemplateTupleDesc(2);
110 TupleDescInitEntry(state->tupdesc[i], (AttrNumber) 1, NULL,
112 TupleDescInitEntry(state->tupdesc[i], (AttrNumber) 2, NULL,
116 TupleDescInitEntryCollation(state->tupdesc[i], (AttrNumber) 2,
121 * If the compare proc isn't specified in the opclass definition, look
122 * up the index key type's default btree comparator.
124 if (index_getprocid(index, i + 1, GIN_COMPARE_PROC) != InvalidOid)
126 fmgr_info_copy(&(state->compareFn[i]),
127 index_getprocinfo(index, i + 1, GIN_COMPARE_PROC),
128 CurrentMemoryContext);
132 TypeCacheEntry *typentry;
134 typentry = lookup_type_cache(attr->atttypid,
135 TYPECACHE_CMP_PROC_FINFO);
136 if (!OidIsValid(typentry->cmp_proc_finfo.fn_oid))
138 (errcode(ERRCODE_UNDEFINED_FUNCTION),
139 errmsg("could not identify a comparison function for type %s",
140 format_type_be(attr->atttypid))));
141 fmgr_info_copy(&(state->compareFn[i]),
142 &(typentry->cmp_proc_finfo),
143 CurrentMemoryContext);
146 /* Opclass must always provide extract procs */
147 fmgr_info_copy(&(state->extractValueFn[i]),
148 index_getprocinfo(index, i + 1, GIN_EXTRACTVALUE_PROC),
149 CurrentMemoryContext);
150 fmgr_info_copy(&(state->extractQueryFn[i]),
151 index_getprocinfo(index, i + 1, GIN_EXTRACTQUERY_PROC),
152 CurrentMemoryContext);
155 * Check opclass capability to do tri-state or binary logic consistent
158 if (index_getprocid(index, i + 1, GIN_TRICONSISTENT_PROC) != InvalidOid)
160 fmgr_info_copy(&(state->triConsistentFn[i]),
161 index_getprocinfo(index, i + 1, GIN_TRICONSISTENT_PROC),
162 CurrentMemoryContext);
165 if (index_getprocid(index, i + 1, GIN_CONSISTENT_PROC) != InvalidOid)
167 fmgr_info_copy(&(state->consistentFn[i]),
168 index_getprocinfo(index, i + 1, GIN_CONSISTENT_PROC),
169 CurrentMemoryContext);
172 if (state->consistentFn[i].fn_oid == InvalidOid &&
173 state->triConsistentFn[i].fn_oid == InvalidOid)
175 elog(ERROR, "missing GIN support function (%d or %d) for attribute %d of index \"%s\"",
176 GIN_CONSISTENT_PROC, GIN_TRICONSISTENT_PROC,
177 i + 1, RelationGetRelationName(index));
181 * Check opclass capability to do partial match.
183 if (index_getprocid(index, i + 1, GIN_COMPARE_PARTIAL_PROC) != InvalidOid)
185 fmgr_info_copy(&(state->comparePartialFn[i]),
186 index_getprocinfo(index, i + 1, GIN_COMPARE_PARTIAL_PROC),
187 CurrentMemoryContext);
188 state->canPartialMatch[i] = true;
192 state->canPartialMatch[i] = false;
196 * If the index column has a specified collation, we should honor that
197 * while doing comparisons. However, we may have a collatable storage
198 * type for a noncollatable indexed data type (for instance, hstore
199 * uses text index entries). If there's no index collation then
200 * specify default collation in case the support functions need
201 * collation. This is harmless if the support functions don't care
202 * about collation, so we just do it unconditionally. (We could
203 * alternatively call get_typcollation, but that seems like expensive
204 * overkill --- there aren't going to be any cases where a GIN storage
205 * type has a nondefault collation.)
207 if (OidIsValid(index->rd_indcollation[i]))
208 state->supportCollation[i] = index->rd_indcollation[i];
210 state->supportCollation[i] = DEFAULT_COLLATION_OID;
215 * Extract attribute (column) number of stored entry from GIN tuple
218 gintuple_get_attrnum(GinState *ginstate, IndexTuple tuple)
222 if (ginstate->oneCol)
224 /* column number is not stored explicitly */
225 colN = FirstOffsetNumber;
233 * First attribute is always int16, so we can safely use any tuple
234 * descriptor to obtain first attribute of tuple
236 res = index_getattr(tuple, FirstOffsetNumber, ginstate->tupdesc[0],
240 colN = DatumGetUInt16(res);
241 Assert(colN >= FirstOffsetNumber && colN <= ginstate->origTupdesc->natts);
248 * Extract stored datum (and possible null category) from GIN tuple
251 gintuple_get_key(GinState *ginstate, IndexTuple tuple,
252 GinNullCategory *category)
257 if (ginstate->oneCol)
260 * Single column index doesn't store attribute numbers in tuples
262 res = index_getattr(tuple, FirstOffsetNumber, ginstate->origTupdesc,
268 * Since the datum type depends on which index column it's from, we
269 * must be careful to use the right tuple descriptor here.
271 OffsetNumber colN = gintuple_get_attrnum(ginstate, tuple);
273 res = index_getattr(tuple, OffsetNumberNext(FirstOffsetNumber),
274 ginstate->tupdesc[colN - 1],
279 *category = GinGetNullCategory(tuple, ginstate);
281 *category = GIN_CAT_NORM_KEY;
287 * Allocate a new page (either by recycling, or by extending the index file)
288 * The returned buffer is already pinned and exclusive-locked
289 * Caller is responsible for initializing the page by calling GinInitBuffer
292 GinNewBuffer(Relation index)
297 /* First, try to get a page from FSM */
300 BlockNumber blkno = GetFreeIndexPage(index);
302 if (blkno == InvalidBlockNumber)
305 buffer = ReadBuffer(index, blkno);
308 * We have to guard against the possibility that someone else already
309 * recycled this page; the buffer may be locked if so.
311 if (ConditionalLockBuffer(buffer))
313 if (GinPageIsRecyclable(BufferGetPage(buffer)))
314 return buffer; /* OK to use */
316 LockBuffer(buffer, GIN_UNLOCK);
319 /* Can't use it, so release buffer and try again */
320 ReleaseBuffer(buffer);
323 /* Must extend the file */
324 needLock = !RELATION_IS_LOCAL(index);
326 LockRelationForExtension(index, ExclusiveLock);
328 buffer = ReadBuffer(index, P_NEW);
329 LockBuffer(buffer, GIN_EXCLUSIVE);
332 UnlockRelationForExtension(index, ExclusiveLock);
338 GinInitPage(Page page, uint32 f, Size pageSize)
340 GinPageOpaque opaque;
342 PageInit(page, pageSize, sizeof(GinPageOpaqueData));
344 opaque = GinPageGetOpaque(page);
345 memset(opaque, 0, sizeof(GinPageOpaqueData));
347 opaque->rightlink = InvalidBlockNumber;
351 GinInitBuffer(Buffer b, uint32 f)
353 GinInitPage(BufferGetPage(b), f, BufferGetPageSize(b));
357 GinInitMetabuffer(Buffer b)
359 GinMetaPageData *metadata;
360 Page page = BufferGetPage(b);
362 GinInitPage(page, GIN_META, BufferGetPageSize(b));
364 metadata = GinPageGetMeta(page);
366 metadata->head = metadata->tail = InvalidBlockNumber;
367 metadata->tailFreeSize = 0;
368 metadata->nPendingPages = 0;
369 metadata->nPendingHeapTuples = 0;
370 metadata->nTotalPages = 0;
371 metadata->nEntryPages = 0;
372 metadata->nDataPages = 0;
373 metadata->nEntries = 0;
374 metadata->ginVersion = GIN_CURRENT_VERSION;
377 * Set pd_lower just past the end of the metadata. This is essential,
378 * because without doing so, metadata will be lost if xlog.c compresses
381 ((PageHeader) page)->pd_lower =
382 ((char *) metadata + sizeof(GinMetaPageData)) - (char *) page;
386 * Compare two keys of the same index column
389 ginCompareEntries(GinState *ginstate, OffsetNumber attnum,
390 Datum a, GinNullCategory categorya,
391 Datum b, GinNullCategory categoryb)
393 /* if not of same null category, sort by that first */
394 if (categorya != categoryb)
395 return (categorya < categoryb) ? -1 : 1;
397 /* all null items in same category are equal */
398 if (categorya != GIN_CAT_NORM_KEY)
401 /* both not null, so safe to call the compareFn */
402 return DatumGetInt32(FunctionCall2Coll(&ginstate->compareFn[attnum - 1],
403 ginstate->supportCollation[attnum - 1],
408 * Compare two keys of possibly different index columns
411 ginCompareAttEntries(GinState *ginstate,
412 OffsetNumber attnuma, Datum a, GinNullCategory categorya,
413 OffsetNumber attnumb, Datum b, GinNullCategory categoryb)
415 /* attribute number is the first sort key */
416 if (attnuma != attnumb)
417 return (attnuma < attnumb) ? -1 : 1;
419 return ginCompareEntries(ginstate, attnuma, a, categorya, b, categoryb);
424 * Support for sorting key datums in ginExtractEntries
426 * Note: we only have to worry about null and not-null keys here;
427 * ginExtractEntries never generates more than one placeholder null,
428 * so it doesn't have to sort those.
438 FmgrInfo *cmpDatumFunc;
444 cmpEntries(const void *a, const void *b, void *arg)
446 const keyEntryData *aa = (const keyEntryData *) a;
447 const keyEntryData *bb = (const keyEntryData *) b;
448 cmpEntriesArg *data = (cmpEntriesArg *) arg;
454 res = 0; /* NULL "=" NULL */
456 res = 1; /* NULL ">" not-NULL */
459 res = -1; /* not-NULL "<" NULL */
461 res = DatumGetInt32(FunctionCall2Coll(data->cmpDatumFunc,
463 aa->datum, bb->datum));
466 * Detect if we have any duplicates. If there are equal keys, qsort must
467 * compare them at some point, else it wouldn't know whether one should go
468 * before or after the other.
471 data->haveDups = true;
478 * Extract the index key values from an indexable item
480 * The resulting key values are sorted, and any duplicates are removed.
481 * This avoids generating redundant index entries.
484 ginExtractEntries(GinState *ginstate, OffsetNumber attnum,
485 Datum value, bool isNull,
486 int32 *nentries, GinNullCategory **categories)
493 * We don't call the extractValueFn on a null item. Instead generate a
499 entries = (Datum *) palloc(sizeof(Datum));
500 entries[0] = (Datum) 0;
501 *categories = (GinNullCategory *) palloc(sizeof(GinNullCategory));
502 (*categories)[0] = GIN_CAT_NULL_ITEM;
506 /* OK, call the opclass's extractValueFn */
507 nullFlags = NULL; /* in case extractValue doesn't set it */
509 DatumGetPointer(FunctionCall3Coll(&ginstate->extractValueFn[attnum - 1],
510 ginstate->supportCollation[attnum - 1],
512 PointerGetDatum(nentries),
513 PointerGetDatum(&nullFlags)));
516 * Generate a placeholder if the item contained no keys.
518 if (entries == NULL || *nentries <= 0)
521 entries = (Datum *) palloc(sizeof(Datum));
522 entries[0] = (Datum) 0;
523 *categories = (GinNullCategory *) palloc(sizeof(GinNullCategory));
524 (*categories)[0] = GIN_CAT_EMPTY_ITEM;
529 * If the extractValueFn didn't create a nullFlags array, create one,
530 * assuming that everything's non-null.
532 if (nullFlags == NULL)
533 nullFlags = (bool *) palloc0(*nentries * sizeof(bool));
536 * If there's more than one key, sort and unique-ify.
538 * XXX Using qsort here is notationally painful, and the overhead is
539 * pretty bad too. For small numbers of keys it'd likely be better to use
540 * a simple insertion sort.
544 keyEntryData *keydata;
547 keydata = (keyEntryData *) palloc(*nentries * sizeof(keyEntryData));
548 for (i = 0; i < *nentries; i++)
550 keydata[i].datum = entries[i];
551 keydata[i].isnull = nullFlags[i];
554 arg.cmpDatumFunc = &ginstate->compareFn[attnum - 1];
555 arg.collation = ginstate->supportCollation[attnum - 1];
556 arg.haveDups = false;
557 qsort_arg(keydata, *nentries, sizeof(keyEntryData),
558 cmpEntries, (void *) &arg);
562 /* there are duplicates, must get rid of 'em */
565 entries[0] = keydata[0].datum;
566 nullFlags[0] = keydata[0].isnull;
568 for (i = 1; i < *nentries; i++)
570 if (cmpEntries(&keydata[i - 1], &keydata[i], &arg) != 0)
572 entries[j] = keydata[i].datum;
573 nullFlags[j] = keydata[i].isnull;
581 /* easy, no duplicates */
582 for (i = 0; i < *nentries; i++)
584 entries[i] = keydata[i].datum;
585 nullFlags[i] = keydata[i].isnull;
593 * Create GinNullCategory representation from nullFlags.
595 *categories = (GinNullCategory *) palloc0(*nentries * sizeof(GinNullCategory));
596 for (i = 0; i < *nentries; i++)
597 (*categories)[i] = (nullFlags[i] ? GIN_CAT_NULL_KEY : GIN_CAT_NORM_KEY);
603 ginoptions(Datum reloptions, bool validate)
605 relopt_value *options;
608 static const relopt_parse_elt tab[] = {
609 {"fastupdate", RELOPT_TYPE_BOOL, offsetof(GinOptions, useFastUpdate)},
610 {"gin_pending_list_limit", RELOPT_TYPE_INT, offsetof(GinOptions,
611 pendingListCleanupSize)}
614 options = parseRelOptions(reloptions, validate, RELOPT_KIND_GIN,
617 /* if none set, we're done */
621 rdopts = allocateReloptStruct(sizeof(GinOptions), options, numoptions);
623 fillRelOptions((void *) rdopts, sizeof(GinOptions), options, numoptions,
624 validate, tab, lengthof(tab));
628 return (bytea *) rdopts;
632 * Fetch index's statistical data into *stats
634 * Note: in the result, nPendingPages can be trusted to be up-to-date,
635 * as can ginVersion; but the other fields are as of the last VACUUM.
638 ginGetStats(Relation index, GinStatsData *stats)
642 GinMetaPageData *metadata;
644 metabuffer = ReadBuffer(index, GIN_METAPAGE_BLKNO);
645 LockBuffer(metabuffer, GIN_SHARE);
646 metapage = BufferGetPage(metabuffer);
647 metadata = GinPageGetMeta(metapage);
649 stats->nPendingPages = metadata->nPendingPages;
650 stats->nTotalPages = metadata->nTotalPages;
651 stats->nEntryPages = metadata->nEntryPages;
652 stats->nDataPages = metadata->nDataPages;
653 stats->nEntries = metadata->nEntries;
654 stats->ginVersion = metadata->ginVersion;
656 UnlockReleaseBuffer(metabuffer);
660 * Write the given statistics to the index's metapage
662 * Note: nPendingPages and ginVersion are *not* copied over
665 ginUpdateStats(Relation index, const GinStatsData *stats)
669 GinMetaPageData *metadata;
671 metabuffer = ReadBuffer(index, GIN_METAPAGE_BLKNO);
672 LockBuffer(metabuffer, GIN_EXCLUSIVE);
673 metapage = BufferGetPage(metabuffer);
674 metadata = GinPageGetMeta(metapage);
676 START_CRIT_SECTION();
678 metadata->nTotalPages = stats->nTotalPages;
679 metadata->nEntryPages = stats->nEntryPages;
680 metadata->nDataPages = stats->nDataPages;
681 metadata->nEntries = stats->nEntries;
684 * Set pd_lower just past the end of the metadata. This is essential,
685 * because without doing so, metadata will be lost if xlog.c compresses
686 * the page. (We must do this here because pre-v11 versions of PG did not
687 * set the metapage's pd_lower correctly, so a pg_upgraded index might
688 * contain the wrong value.)
690 ((PageHeader) metapage)->pd_lower =
691 ((char *) metadata + sizeof(GinMetaPageData)) - (char *) metapage;
693 MarkBufferDirty(metabuffer);
695 if (RelationNeedsWAL(index))
698 ginxlogUpdateMeta data;
700 data.node = index->rd_node;
702 data.newRightlink = data.prevTail = InvalidBlockNumber;
703 memcpy(&data.metadata, metadata, sizeof(GinMetaPageData));
706 XLogRegisterData((char *) &data, sizeof(ginxlogUpdateMeta));
707 XLogRegisterBuffer(0, metabuffer, REGBUF_WILL_INIT | REGBUF_STANDARD);
709 recptr = XLogInsert(RM_GIN_ID, XLOG_GIN_UPDATE_META_PAGE);
710 PageSetLSN(metapage, recptr);
713 UnlockReleaseBuffer(metabuffer);