1 /*-------------------------------------------------------------------------
4 * Utility routines for the Postgres inverted index access method.
7 * Portions Copyright (c) 1996-2022, 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 "commands/vacuum.h"
24 #include "miscadmin.h"
25 #include "storage/indexfsm.h"
26 #include "storage/lmgr.h"
27 #include "storage/predicate.h"
28 #include "utils/builtins.h"
29 #include "utils/index_selfuncs.h"
30 #include "utils/typcache.h"
34 * GIN handler function: return IndexAmRoutine with access method parameters
38 ginhandler(PG_FUNCTION_ARGS
)
40 IndexAmRoutine
*amroutine
= makeNode(IndexAmRoutine
);
42 amroutine
->amstrategies
= 0;
43 amroutine
->amsupport
= GINNProcs
;
44 amroutine
->amoptsprocnum
= GIN_OPTIONS_PROC
;
45 amroutine
->amcanorder
= false;
46 amroutine
->amcanorderbyop
= false;
47 amroutine
->amcanbackward
= false;
48 amroutine
->amcanunique
= false;
49 amroutine
->amcanmulticol
= true;
50 amroutine
->amoptionalkey
= true;
51 amroutine
->amsearcharray
= false;
52 amroutine
->amsearchnulls
= false;
53 amroutine
->amstorage
= true;
54 amroutine
->amclusterable
= false;
55 amroutine
->ampredlocks
= true;
56 amroutine
->amcanparallel
= false;
57 amroutine
->amcaninclude
= false;
58 amroutine
->amusemaintenanceworkmem
= true;
59 amroutine
->amhotblocking
= true;
60 amroutine
->amparallelvacuumoptions
=
61 VACUUM_OPTION_PARALLEL_BULKDEL
| VACUUM_OPTION_PARALLEL_CLEANUP
;
62 amroutine
->amkeytype
= InvalidOid
;
64 amroutine
->ambuild
= ginbuild
;
65 amroutine
->ambuildempty
= ginbuildempty
;
66 amroutine
->aminsert
= gininsert
;
67 amroutine
->ambulkdelete
= ginbulkdelete
;
68 amroutine
->amvacuumcleanup
= ginvacuumcleanup
;
69 amroutine
->amcanreturn
= NULL
;
70 amroutine
->amcostestimate
= gincostestimate
;
71 amroutine
->amoptions
= ginoptions
;
72 amroutine
->amproperty
= NULL
;
73 amroutine
->ambuildphasename
= NULL
;
74 amroutine
->amvalidate
= ginvalidate
;
75 amroutine
->amadjustmembers
= ginadjustmembers
;
76 amroutine
->ambeginscan
= ginbeginscan
;
77 amroutine
->amrescan
= ginrescan
;
78 amroutine
->amgettuple
= NULL
;
79 amroutine
->amgetbitmap
= gingetbitmap
;
80 amroutine
->amendscan
= ginendscan
;
81 amroutine
->ammarkpos
= NULL
;
82 amroutine
->amrestrpos
= NULL
;
83 amroutine
->amestimateparallelscan
= NULL
;
84 amroutine
->aminitparallelscan
= NULL
;
85 amroutine
->amparallelrescan
= NULL
;
87 PG_RETURN_POINTER(amroutine
);
91 * initGinState: fill in an empty GinState struct to describe the index
93 * Note: assorted subsidiary data is allocated in the CurrentMemoryContext.
96 initGinState(GinState
*state
, Relation index
)
98 TupleDesc origTupdesc
= RelationGetDescr(index
);
101 MemSet(state
, 0, sizeof(GinState
));
103 state
->index
= index
;
104 state
->oneCol
= (origTupdesc
->natts
== 1);
105 state
->origTupdesc
= origTupdesc
;
107 for (i
= 0; i
< origTupdesc
->natts
; i
++)
109 Form_pg_attribute attr
= TupleDescAttr(origTupdesc
, i
);
112 state
->tupdesc
[i
] = state
->origTupdesc
;
115 state
->tupdesc
[i
] = CreateTemplateTupleDesc(2);
117 TupleDescInitEntry(state
->tupdesc
[i
], (AttrNumber
) 1, NULL
,
119 TupleDescInitEntry(state
->tupdesc
[i
], (AttrNumber
) 2, NULL
,
123 TupleDescInitEntryCollation(state
->tupdesc
[i
], (AttrNumber
) 2,
128 * If the compare proc isn't specified in the opclass definition, look
129 * up the index key type's default btree comparator.
131 if (index_getprocid(index
, i
+ 1, GIN_COMPARE_PROC
) != InvalidOid
)
133 fmgr_info_copy(&(state
->compareFn
[i
]),
134 index_getprocinfo(index
, i
+ 1, GIN_COMPARE_PROC
),
135 CurrentMemoryContext
);
139 TypeCacheEntry
*typentry
;
141 typentry
= lookup_type_cache(attr
->atttypid
,
142 TYPECACHE_CMP_PROC_FINFO
);
143 if (!OidIsValid(typentry
->cmp_proc_finfo
.fn_oid
))
145 (errcode(ERRCODE_UNDEFINED_FUNCTION
),
146 errmsg("could not identify a comparison function for type %s",
147 format_type_be(attr
->atttypid
))));
148 fmgr_info_copy(&(state
->compareFn
[i
]),
149 &(typentry
->cmp_proc_finfo
),
150 CurrentMemoryContext
);
153 /* Opclass must always provide extract procs */
154 fmgr_info_copy(&(state
->extractValueFn
[i
]),
155 index_getprocinfo(index
, i
+ 1, GIN_EXTRACTVALUE_PROC
),
156 CurrentMemoryContext
);
157 fmgr_info_copy(&(state
->extractQueryFn
[i
]),
158 index_getprocinfo(index
, i
+ 1, GIN_EXTRACTQUERY_PROC
),
159 CurrentMemoryContext
);
162 * Check opclass capability to do tri-state or binary logic consistent
165 if (index_getprocid(index
, i
+ 1, GIN_TRICONSISTENT_PROC
) != InvalidOid
)
167 fmgr_info_copy(&(state
->triConsistentFn
[i
]),
168 index_getprocinfo(index
, i
+ 1, GIN_TRICONSISTENT_PROC
),
169 CurrentMemoryContext
);
172 if (index_getprocid(index
, i
+ 1, GIN_CONSISTENT_PROC
) != InvalidOid
)
174 fmgr_info_copy(&(state
->consistentFn
[i
]),
175 index_getprocinfo(index
, i
+ 1, GIN_CONSISTENT_PROC
),
176 CurrentMemoryContext
);
179 if (state
->consistentFn
[i
].fn_oid
== InvalidOid
&&
180 state
->triConsistentFn
[i
].fn_oid
== InvalidOid
)
182 elog(ERROR
, "missing GIN support function (%d or %d) for attribute %d of index \"%s\"",
183 GIN_CONSISTENT_PROC
, GIN_TRICONSISTENT_PROC
,
184 i
+ 1, RelationGetRelationName(index
));
188 * Check opclass capability to do partial match.
190 if (index_getprocid(index
, i
+ 1, GIN_COMPARE_PARTIAL_PROC
) != InvalidOid
)
192 fmgr_info_copy(&(state
->comparePartialFn
[i
]),
193 index_getprocinfo(index
, i
+ 1, GIN_COMPARE_PARTIAL_PROC
),
194 CurrentMemoryContext
);
195 state
->canPartialMatch
[i
] = true;
199 state
->canPartialMatch
[i
] = false;
203 * If the index column has a specified collation, we should honor that
204 * while doing comparisons. However, we may have a collatable storage
205 * type for a noncollatable indexed data type (for instance, hstore
206 * uses text index entries). If there's no index collation then
207 * specify default collation in case the support functions need
208 * collation. This is harmless if the support functions don't care
209 * about collation, so we just do it unconditionally. (We could
210 * alternatively call get_typcollation, but that seems like expensive
211 * overkill --- there aren't going to be any cases where a GIN storage
212 * type has a nondefault collation.)
214 if (OidIsValid(index
->rd_indcollation
[i
]))
215 state
->supportCollation
[i
] = index
->rd_indcollation
[i
];
217 state
->supportCollation
[i
] = DEFAULT_COLLATION_OID
;
222 * Extract attribute (column) number of stored entry from GIN tuple
225 gintuple_get_attrnum(GinState
*ginstate
, IndexTuple tuple
)
229 if (ginstate
->oneCol
)
231 /* column number is not stored explicitly */
232 colN
= FirstOffsetNumber
;
240 * First attribute is always int16, so we can safely use any tuple
241 * descriptor to obtain first attribute of tuple
243 res
= index_getattr(tuple
, FirstOffsetNumber
, ginstate
->tupdesc
[0],
247 colN
= DatumGetUInt16(res
);
248 Assert(colN
>= FirstOffsetNumber
&& colN
<= ginstate
->origTupdesc
->natts
);
255 * Extract stored datum (and possible null category) from GIN tuple
258 gintuple_get_key(GinState
*ginstate
, IndexTuple tuple
,
259 GinNullCategory
*category
)
264 if (ginstate
->oneCol
)
267 * Single column index doesn't store attribute numbers in tuples
269 res
= index_getattr(tuple
, FirstOffsetNumber
, ginstate
->origTupdesc
,
275 * Since the datum type depends on which index column it's from, we
276 * must be careful to use the right tuple descriptor here.
278 OffsetNumber colN
= gintuple_get_attrnum(ginstate
, tuple
);
280 res
= index_getattr(tuple
, OffsetNumberNext(FirstOffsetNumber
),
281 ginstate
->tupdesc
[colN
- 1],
286 *category
= GinGetNullCategory(tuple
, ginstate
);
288 *category
= GIN_CAT_NORM_KEY
;
294 * Allocate a new page (either by recycling, or by extending the index file)
295 * The returned buffer is already pinned and exclusive-locked
296 * Caller is responsible for initializing the page by calling GinInitBuffer
299 GinNewBuffer(Relation index
)
304 /* First, try to get a page from FSM */
307 BlockNumber blkno
= GetFreeIndexPage(index
);
309 if (blkno
== InvalidBlockNumber
)
312 buffer
= ReadBuffer(index
, blkno
);
315 * We have to guard against the possibility that someone else already
316 * recycled this page; the buffer may be locked if so.
318 if (ConditionalLockBuffer(buffer
))
320 if (GinPageIsRecyclable(BufferGetPage(buffer
)))
321 return buffer
; /* OK to use */
323 LockBuffer(buffer
, GIN_UNLOCK
);
326 /* Can't use it, so release buffer and try again */
327 ReleaseBuffer(buffer
);
330 /* Must extend the file */
331 needLock
= !RELATION_IS_LOCAL(index
);
333 LockRelationForExtension(index
, ExclusiveLock
);
335 buffer
= ReadBuffer(index
, P_NEW
);
336 LockBuffer(buffer
, GIN_EXCLUSIVE
);
339 UnlockRelationForExtension(index
, ExclusiveLock
);
345 GinInitPage(Page page
, uint32 f
, Size pageSize
)
347 GinPageOpaque opaque
;
349 PageInit(page
, pageSize
, sizeof(GinPageOpaqueData
));
351 opaque
= GinPageGetOpaque(page
);
353 opaque
->rightlink
= InvalidBlockNumber
;
357 GinInitBuffer(Buffer b
, uint32 f
)
359 GinInitPage(BufferGetPage(b
), f
, BufferGetPageSize(b
));
363 GinInitMetabuffer(Buffer b
)
365 GinMetaPageData
*metadata
;
366 Page page
= BufferGetPage(b
);
368 GinInitPage(page
, GIN_META
, BufferGetPageSize(b
));
370 metadata
= GinPageGetMeta(page
);
372 metadata
->head
= metadata
->tail
= InvalidBlockNumber
;
373 metadata
->tailFreeSize
= 0;
374 metadata
->nPendingPages
= 0;
375 metadata
->nPendingHeapTuples
= 0;
376 metadata
->nTotalPages
= 0;
377 metadata
->nEntryPages
= 0;
378 metadata
->nDataPages
= 0;
379 metadata
->nEntries
= 0;
380 metadata
->ginVersion
= GIN_CURRENT_VERSION
;
383 * Set pd_lower just past the end of the metadata. This is essential,
384 * because without doing so, metadata will be lost if xlog.c compresses
387 ((PageHeader
) page
)->pd_lower
=
388 ((char *) metadata
+ sizeof(GinMetaPageData
)) - (char *) page
;
392 * Compare two keys of the same index column
395 ginCompareEntries(GinState
*ginstate
, OffsetNumber attnum
,
396 Datum a
, GinNullCategory categorya
,
397 Datum b
, GinNullCategory categoryb
)
399 /* if not of same null category, sort by that first */
400 if (categorya
!= categoryb
)
401 return (categorya
< categoryb
) ? -1 : 1;
403 /* all null items in same category are equal */
404 if (categorya
!= GIN_CAT_NORM_KEY
)
407 /* both not null, so safe to call the compareFn */
408 return DatumGetInt32(FunctionCall2Coll(&ginstate
->compareFn
[attnum
- 1],
409 ginstate
->supportCollation
[attnum
- 1],
414 * Compare two keys of possibly different index columns
417 ginCompareAttEntries(GinState
*ginstate
,
418 OffsetNumber attnuma
, Datum a
, GinNullCategory categorya
,
419 OffsetNumber attnumb
, Datum b
, GinNullCategory categoryb
)
421 /* attribute number is the first sort key */
422 if (attnuma
!= attnumb
)
423 return (attnuma
< attnumb
) ? -1 : 1;
425 return ginCompareEntries(ginstate
, attnuma
, a
, categorya
, b
, categoryb
);
430 * Support for sorting key datums in ginExtractEntries
432 * Note: we only have to worry about null and not-null keys here;
433 * ginExtractEntries never generates more than one placeholder null,
434 * so it doesn't have to sort those.
444 FmgrInfo
*cmpDatumFunc
;
450 cmpEntries(const void *a
, const void *b
, void *arg
)
452 const keyEntryData
*aa
= (const keyEntryData
*) a
;
453 const keyEntryData
*bb
= (const keyEntryData
*) b
;
454 cmpEntriesArg
*data
= (cmpEntriesArg
*) arg
;
460 res
= 0; /* NULL "=" NULL */
462 res
= 1; /* NULL ">" not-NULL */
465 res
= -1; /* not-NULL "<" NULL */
467 res
= DatumGetInt32(FunctionCall2Coll(data
->cmpDatumFunc
,
469 aa
->datum
, bb
->datum
));
472 * Detect if we have any duplicates. If there are equal keys, qsort must
473 * compare them at some point, else it wouldn't know whether one should go
474 * before or after the other.
477 data
->haveDups
= true;
484 * Extract the index key values from an indexable item
486 * The resulting key values are sorted, and any duplicates are removed.
487 * This avoids generating redundant index entries.
490 ginExtractEntries(GinState
*ginstate
, OffsetNumber attnum
,
491 Datum value
, bool isNull
,
492 int32
*nentries
, GinNullCategory
**categories
)
499 * We don't call the extractValueFn on a null item. Instead generate a
505 entries
= (Datum
*) palloc(sizeof(Datum
));
506 entries
[0] = (Datum
) 0;
507 *categories
= (GinNullCategory
*) palloc(sizeof(GinNullCategory
));
508 (*categories
)[0] = GIN_CAT_NULL_ITEM
;
512 /* OK, call the opclass's extractValueFn */
513 nullFlags
= NULL
; /* in case extractValue doesn't set it */
515 DatumGetPointer(FunctionCall3Coll(&ginstate
->extractValueFn
[attnum
- 1],
516 ginstate
->supportCollation
[attnum
- 1],
518 PointerGetDatum(nentries
),
519 PointerGetDatum(&nullFlags
)));
522 * Generate a placeholder if the item contained no keys.
524 if (entries
== NULL
|| *nentries
<= 0)
527 entries
= (Datum
*) palloc(sizeof(Datum
));
528 entries
[0] = (Datum
) 0;
529 *categories
= (GinNullCategory
*) palloc(sizeof(GinNullCategory
));
530 (*categories
)[0] = GIN_CAT_EMPTY_ITEM
;
535 * If the extractValueFn didn't create a nullFlags array, create one,
536 * assuming that everything's non-null.
538 if (nullFlags
== NULL
)
539 nullFlags
= (bool *) palloc0(*nentries
* sizeof(bool));
542 * If there's more than one key, sort and unique-ify.
544 * XXX Using qsort here is notationally painful, and the overhead is
545 * pretty bad too. For small numbers of keys it'd likely be better to use
546 * a simple insertion sort.
550 keyEntryData
*keydata
;
553 keydata
= (keyEntryData
*) palloc(*nentries
* sizeof(keyEntryData
));
554 for (i
= 0; i
< *nentries
; i
++)
556 keydata
[i
].datum
= entries
[i
];
557 keydata
[i
].isnull
= nullFlags
[i
];
560 arg
.cmpDatumFunc
= &ginstate
->compareFn
[attnum
- 1];
561 arg
.collation
= ginstate
->supportCollation
[attnum
- 1];
562 arg
.haveDups
= false;
563 qsort_arg(keydata
, *nentries
, sizeof(keyEntryData
),
564 cmpEntries
, (void *) &arg
);
568 /* there are duplicates, must get rid of 'em */
571 entries
[0] = keydata
[0].datum
;
572 nullFlags
[0] = keydata
[0].isnull
;
574 for (i
= 1; i
< *nentries
; i
++)
576 if (cmpEntries(&keydata
[i
- 1], &keydata
[i
], &arg
) != 0)
578 entries
[j
] = keydata
[i
].datum
;
579 nullFlags
[j
] = keydata
[i
].isnull
;
587 /* easy, no duplicates */
588 for (i
= 0; i
< *nentries
; i
++)
590 entries
[i
] = keydata
[i
].datum
;
591 nullFlags
[i
] = keydata
[i
].isnull
;
599 * Create GinNullCategory representation from nullFlags.
601 *categories
= (GinNullCategory
*) palloc0(*nentries
* sizeof(GinNullCategory
));
602 for (i
= 0; i
< *nentries
; i
++)
603 (*categories
)[i
] = (nullFlags
[i
] ? GIN_CAT_NULL_KEY
: GIN_CAT_NORM_KEY
);
609 ginoptions(Datum reloptions
, bool validate
)
611 static const relopt_parse_elt tab
[] = {
612 {"fastupdate", RELOPT_TYPE_BOOL
, offsetof(GinOptions
, useFastUpdate
)},
613 {"gin_pending_list_limit", RELOPT_TYPE_INT
, offsetof(GinOptions
,
614 pendingListCleanupSize
)}
617 return (bytea
*) build_reloptions(reloptions
, validate
,
624 * Fetch index's statistical data into *stats
626 * Note: in the result, nPendingPages can be trusted to be up-to-date,
627 * as can ginVersion; but the other fields are as of the last VACUUM.
630 ginGetStats(Relation index
, GinStatsData
*stats
)
634 GinMetaPageData
*metadata
;
636 metabuffer
= ReadBuffer(index
, GIN_METAPAGE_BLKNO
);
637 LockBuffer(metabuffer
, GIN_SHARE
);
638 metapage
= BufferGetPage(metabuffer
);
639 metadata
= GinPageGetMeta(metapage
);
641 stats
->nPendingPages
= metadata
->nPendingPages
;
642 stats
->nTotalPages
= metadata
->nTotalPages
;
643 stats
->nEntryPages
= metadata
->nEntryPages
;
644 stats
->nDataPages
= metadata
->nDataPages
;
645 stats
->nEntries
= metadata
->nEntries
;
646 stats
->ginVersion
= metadata
->ginVersion
;
648 UnlockReleaseBuffer(metabuffer
);
652 * Write the given statistics to the index's metapage
654 * Note: nPendingPages and ginVersion are *not* copied over
657 ginUpdateStats(Relation index
, const GinStatsData
*stats
, bool is_build
)
661 GinMetaPageData
*metadata
;
663 metabuffer
= ReadBuffer(index
, GIN_METAPAGE_BLKNO
);
664 LockBuffer(metabuffer
, GIN_EXCLUSIVE
);
665 metapage
= BufferGetPage(metabuffer
);
666 metadata
= GinPageGetMeta(metapage
);
668 START_CRIT_SECTION();
670 metadata
->nTotalPages
= stats
->nTotalPages
;
671 metadata
->nEntryPages
= stats
->nEntryPages
;
672 metadata
->nDataPages
= stats
->nDataPages
;
673 metadata
->nEntries
= stats
->nEntries
;
676 * Set pd_lower just past the end of the metadata. This is essential,
677 * because without doing so, metadata will be lost if xlog.c compresses
678 * the page. (We must do this here because pre-v11 versions of PG did not
679 * set the metapage's pd_lower correctly, so a pg_upgraded index might
680 * contain the wrong value.)
682 ((PageHeader
) metapage
)->pd_lower
=
683 ((char *) metadata
+ sizeof(GinMetaPageData
)) - (char *) metapage
;
685 MarkBufferDirty(metabuffer
);
687 if (RelationNeedsWAL(index
) && !is_build
)
690 ginxlogUpdateMeta data
;
692 data
.node
= index
->rd_node
;
694 data
.newRightlink
= data
.prevTail
= InvalidBlockNumber
;
695 memcpy(&data
.metadata
, metadata
, sizeof(GinMetaPageData
));
698 XLogRegisterData((char *) &data
, sizeof(ginxlogUpdateMeta
));
699 XLogRegisterBuffer(0, metabuffer
, REGBUF_WILL_INIT
| REGBUF_STANDARD
);
701 recptr
= XLogInsert(RM_GIN_ID
, XLOG_GIN_UPDATE_META_PAGE
);
702 PageSetLSN(metapage
, recptr
);
705 UnlockReleaseBuffer(metabuffer
);