1 /*-------------------------------------------------------------------------
2 *
3 * ginutil.c
4 * Utility routines for the Postgres inverted index access method.
5 *
6 *
7 * Portions Copyright (c) 1996-2016, PostgreSQL Global Development Group
8 * Portions Copyright (c) 1994, Regents of the University of California
9 *
10 * IDENTIFICATION
11 * src/backend/access/gin/ginutil.c
12 *-------------------------------------------------------------------------
13 */
14
15 #include "postgres.h"
16
17 #include "access/gin_private.h"
18 #include "access/reloptions.h"
19 #include "access/xloginsert.h"
20 #include "catalog/pg_collation.h"
21 #include "catalog/pg_type.h"
22 #include "miscadmin.h"
23 #include "storage/indexfsm.h"
24 #include "storage/lmgr.h"
25 #include "utils/index_selfuncs.h"
26
27
28 /*
29 * GIN handler function: return IndexAmRoutine with access method parameters
30 * and callbacks.
31 */
32 Datum
ginhandler(PG_FUNCTION_ARGS)33 ginhandler(PG_FUNCTION_ARGS)
34 {
35 IndexAmRoutine *amroutine = makeNode(IndexAmRoutine);
36
37 amroutine->amstrategies = 0;
38 amroutine->amsupport = GINNProcs;
39 amroutine->amcanorder = false;
40 amroutine->amcanorderbyop = false;
41 amroutine->amcanbackward = false;
42 amroutine->amcanunique = false;
43 amroutine->amcanmulticol = true;
44 amroutine->amoptionalkey = true;
45 amroutine->amsearcharray = false;
46 amroutine->amsearchnulls = false;
47 amroutine->amstorage = true;
48 amroutine->amclusterable = false;
49 amroutine->ampredlocks = false;
50 amroutine->amkeytype = InvalidOid;
51
52 amroutine->ambuild = ginbuild;
53 amroutine->ambuildempty = ginbuildempty;
54 amroutine->aminsert = gininsert;
55 amroutine->ambulkdelete = ginbulkdelete;
56 amroutine->amvacuumcleanup = ginvacuumcleanup;
57 amroutine->amcanreturn = NULL;
58 amroutine->amcostestimate = gincostestimate;
59 amroutine->amoptions = ginoptions;
60 amroutine->amproperty = NULL;
61 amroutine->amvalidate = ginvalidate;
62 amroutine->ambeginscan = ginbeginscan;
63 amroutine->amrescan = ginrescan;
64 amroutine->amgettuple = NULL;
65 amroutine->amgetbitmap = gingetbitmap;
66 amroutine->amendscan = ginendscan;
67 amroutine->ammarkpos = NULL;
68 amroutine->amrestrpos = NULL;
69
70 PG_RETURN_POINTER(amroutine);
71 }
72
73 /*
74 * initGinState: fill in an empty GinState struct to describe the index
75 *
76 * Note: assorted subsidiary data is allocated in the CurrentMemoryContext.
77 */
78 void
initGinState(GinState * state,Relation index)79 initGinState(GinState *state, Relation index)
80 {
81 TupleDesc origTupdesc = RelationGetDescr(index);
82 int i;
83
84 MemSet(state, 0, sizeof(GinState));
85
86 state->index = index;
87 state->oneCol = (origTupdesc->natts == 1) ? true : false;
88 state->origTupdesc = origTupdesc;
89
90 for (i = 0; i < origTupdesc->natts; i++)
91 {
92 if (state->oneCol)
93 state->tupdesc[i] = state->origTupdesc;
94 else
95 {
96 state->tupdesc[i] = CreateTemplateTupleDesc(2, false);
97
98 TupleDescInitEntry(state->tupdesc[i], (AttrNumber) 1, NULL,
99 INT2OID, -1, 0);
100 TupleDescInitEntry(state->tupdesc[i], (AttrNumber) 2, NULL,
101 origTupdesc->attrs[i]->atttypid,
102 origTupdesc->attrs[i]->atttypmod,
103 origTupdesc->attrs[i]->attndims);
104 TupleDescInitEntryCollation(state->tupdesc[i], (AttrNumber) 2,
105 origTupdesc->attrs[i]->attcollation);
106 }
107
108 fmgr_info_copy(&(state->compareFn[i]),
109 index_getprocinfo(index, i + 1, GIN_COMPARE_PROC),
110 CurrentMemoryContext);
111 fmgr_info_copy(&(state->extractValueFn[i]),
112 index_getprocinfo(index, i + 1, GIN_EXTRACTVALUE_PROC),
113 CurrentMemoryContext);
114 fmgr_info_copy(&(state->extractQueryFn[i]),
115 index_getprocinfo(index, i + 1, GIN_EXTRACTQUERY_PROC),
116 CurrentMemoryContext);
117
118 /*
119 * Check opclass capability to do tri-state or binary logic consistent
120 * check.
121 */
122 if (index_getprocid(index, i + 1, GIN_TRICONSISTENT_PROC) != InvalidOid)
123 {
124 fmgr_info_copy(&(state->triConsistentFn[i]),
125 index_getprocinfo(index, i + 1, GIN_TRICONSISTENT_PROC),
126 CurrentMemoryContext);
127 }
128
129 if (index_getprocid(index, i + 1, GIN_CONSISTENT_PROC) != InvalidOid)
130 {
131 fmgr_info_copy(&(state->consistentFn[i]),
132 index_getprocinfo(index, i + 1, GIN_CONSISTENT_PROC),
133 CurrentMemoryContext);
134 }
135
136 if (state->consistentFn[i].fn_oid == InvalidOid &&
137 state->triConsistentFn[i].fn_oid == InvalidOid)
138 {
139 elog(ERROR, "missing GIN support function (%d or %d) for attribute %d of index \"%s\"",
140 GIN_CONSISTENT_PROC, GIN_TRICONSISTENT_PROC,
141 i + 1, RelationGetRelationName(index));
142 }
143
144 /*
145 * Check opclass capability to do partial match.
146 */
147 if (index_getprocid(index, i + 1, GIN_COMPARE_PARTIAL_PROC) != InvalidOid)
148 {
149 fmgr_info_copy(&(state->comparePartialFn[i]),
150 index_getprocinfo(index, i + 1, GIN_COMPARE_PARTIAL_PROC),
151 CurrentMemoryContext);
152 state->canPartialMatch[i] = true;
153 }
154 else
155 {
156 state->canPartialMatch[i] = false;
157 }
158
159 /*
160 * If the index column has a specified collation, we should honor that
161 * while doing comparisons. However, we may have a collatable storage
162 * type for a noncollatable indexed data type (for instance, hstore
163 * uses text index entries). If there's no index collation then
164 * specify default collation in case the support functions need
165 * collation. This is harmless if the support functions don't care
166 * about collation, so we just do it unconditionally. (We could
167 * alternatively call get_typcollation, but that seems like expensive
168 * overkill --- there aren't going to be any cases where a GIN storage
169 * type has a nondefault collation.)
170 */
171 if (OidIsValid(index->rd_indcollation[i]))
172 state->supportCollation[i] = index->rd_indcollation[i];
173 else
174 state->supportCollation[i] = DEFAULT_COLLATION_OID;
175 }
176 }
177
178 /*
179 * Extract attribute (column) number of stored entry from GIN tuple
180 */
181 OffsetNumber
gintuple_get_attrnum(GinState * ginstate,IndexTuple tuple)182 gintuple_get_attrnum(GinState *ginstate, IndexTuple tuple)
183 {
184 OffsetNumber colN;
185
186 if (ginstate->oneCol)
187 {
188 /* column number is not stored explicitly */
189 colN = FirstOffsetNumber;
190 }
191 else
192 {
193 Datum res;
194 bool isnull;
195
196 /*
197 * First attribute is always int16, so we can safely use any tuple
198 * descriptor to obtain first attribute of tuple
199 */
200 res = index_getattr(tuple, FirstOffsetNumber, ginstate->tupdesc[0],
201 &isnull);
202 Assert(!isnull);
203
204 colN = DatumGetUInt16(res);
205 Assert(colN >= FirstOffsetNumber && colN <= ginstate->origTupdesc->natts);
206 }
207
208 return colN;
209 }
210
211 /*
212 * Extract stored datum (and possible null category) from GIN tuple
213 */
214 Datum
gintuple_get_key(GinState * ginstate,IndexTuple tuple,GinNullCategory * category)215 gintuple_get_key(GinState *ginstate, IndexTuple tuple,
216 GinNullCategory *category)
217 {
218 Datum res;
219 bool isnull;
220
221 if (ginstate->oneCol)
222 {
223 /*
224 * Single column index doesn't store attribute numbers in tuples
225 */
226 res = index_getattr(tuple, FirstOffsetNumber, ginstate->origTupdesc,
227 &isnull);
228 }
229 else
230 {
231 /*
232 * Since the datum type depends on which index column it's from, we
233 * must be careful to use the right tuple descriptor here.
234 */
235 OffsetNumber colN = gintuple_get_attrnum(ginstate, tuple);
236
237 res = index_getattr(tuple, OffsetNumberNext(FirstOffsetNumber),
238 ginstate->tupdesc[colN - 1],
239 &isnull);
240 }
241
242 if (isnull)
243 *category = GinGetNullCategory(tuple, ginstate);
244 else
245 *category = GIN_CAT_NORM_KEY;
246
247 return res;
248 }
249
250 /*
251 * Allocate a new page (either by recycling, or by extending the index file)
252 * The returned buffer is already pinned and exclusive-locked
253 * Caller is responsible for initializing the page by calling GinInitBuffer
254 */
255 Buffer
GinNewBuffer(Relation index)256 GinNewBuffer(Relation index)
257 {
258 Buffer buffer;
259 bool needLock;
260
261 /* First, try to get a page from FSM */
262 for (;;)
263 {
264 BlockNumber blkno = GetFreeIndexPage(index);
265
266 if (blkno == InvalidBlockNumber)
267 break;
268
269 buffer = ReadBuffer(index, blkno);
270
271 /*
272 * We have to guard against the possibility that someone else already
273 * recycled this page; the buffer may be locked if so.
274 */
275 if (ConditionalLockBuffer(buffer))
276 {
277 if (GinPageIsRecyclable(BufferGetPage(buffer)))
278 return buffer; /* OK to use */
279
280 LockBuffer(buffer, GIN_UNLOCK);
281 }
282
283 /* Can't use it, so release buffer and try again */
284 ReleaseBuffer(buffer);
285 }
286
287 /* Must extend the file */
288 needLock = !RELATION_IS_LOCAL(index);
289 if (needLock)
290 LockRelationForExtension(index, ExclusiveLock);
291
292 buffer = ReadBuffer(index, P_NEW);
293 LockBuffer(buffer, GIN_EXCLUSIVE);
294
295 if (needLock)
296 UnlockRelationForExtension(index, ExclusiveLock);
297
298 return buffer;
299 }
300
301 void
GinInitPage(Page page,uint32 f,Size pageSize)302 GinInitPage(Page page, uint32 f, Size pageSize)
303 {
304 GinPageOpaque opaque;
305
306 PageInit(page, pageSize, sizeof(GinPageOpaqueData));
307
308 opaque = GinPageGetOpaque(page);
309 memset(opaque, 0, sizeof(GinPageOpaqueData));
310 opaque->flags = f;
311 opaque->rightlink = InvalidBlockNumber;
312 }
313
314 void
GinInitBuffer(Buffer b,uint32 f)315 GinInitBuffer(Buffer b, uint32 f)
316 {
317 GinInitPage(BufferGetPage(b), f, BufferGetPageSize(b));
318 }
319
320 void
GinInitMetabuffer(Buffer b)321 GinInitMetabuffer(Buffer b)
322 {
323 GinMetaPageData *metadata;
324 Page page = BufferGetPage(b);
325
326 GinInitPage(page, GIN_META, BufferGetPageSize(b));
327
328 metadata = GinPageGetMeta(page);
329
330 metadata->head = metadata->tail = InvalidBlockNumber;
331 metadata->tailFreeSize = 0;
332 metadata->nPendingPages = 0;
333 metadata->nPendingHeapTuples = 0;
334 metadata->nTotalPages = 0;
335 metadata->nEntryPages = 0;
336 metadata->nDataPages = 0;
337 metadata->nEntries = 0;
338 metadata->ginVersion = GIN_CURRENT_VERSION;
339 }
340
341 /*
342 * Compare two keys of the same index column
343 */
344 int
ginCompareEntries(GinState * ginstate,OffsetNumber attnum,Datum a,GinNullCategory categorya,Datum b,GinNullCategory categoryb)345 ginCompareEntries(GinState *ginstate, OffsetNumber attnum,
346 Datum a, GinNullCategory categorya,
347 Datum b, GinNullCategory categoryb)
348 {
349 /* if not of same null category, sort by that first */
350 if (categorya != categoryb)
351 return (categorya < categoryb) ? -1 : 1;
352
353 /* all null items in same category are equal */
354 if (categorya != GIN_CAT_NORM_KEY)
355 return 0;
356
357 /* both not null, so safe to call the compareFn */
358 return DatumGetInt32(FunctionCall2Coll(&ginstate->compareFn[attnum - 1],
359 ginstate->supportCollation[attnum - 1],
360 a, b));
361 }
362
363 /*
364 * Compare two keys of possibly different index columns
365 */
366 int
ginCompareAttEntries(GinState * ginstate,OffsetNumber attnuma,Datum a,GinNullCategory categorya,OffsetNumber attnumb,Datum b,GinNullCategory categoryb)367 ginCompareAttEntries(GinState *ginstate,
368 OffsetNumber attnuma, Datum a, GinNullCategory categorya,
369 OffsetNumber attnumb, Datum b, GinNullCategory categoryb)
370 {
371 /* attribute number is the first sort key */
372 if (attnuma != attnumb)
373 return (attnuma < attnumb) ? -1 : 1;
374
375 return ginCompareEntries(ginstate, attnuma, a, categorya, b, categoryb);
376 }
377
378
379 /*
380 * Support for sorting key datums in ginExtractEntries
381 *
382 * Note: we only have to worry about null and not-null keys here;
383 * ginExtractEntries never generates more than one placeholder null,
384 * so it doesn't have to sort those.
385 */
386 typedef struct
387 {
388 Datum datum;
389 bool isnull;
390 } keyEntryData;
391
392 typedef struct
393 {
394 FmgrInfo *cmpDatumFunc;
395 Oid collation;
396 bool haveDups;
397 } cmpEntriesArg;
398
399 static int
cmpEntries(const void * a,const void * b,void * arg)400 cmpEntries(const void *a, const void *b, void *arg)
401 {
402 const keyEntryData *aa = (const keyEntryData *) a;
403 const keyEntryData *bb = (const keyEntryData *) b;
404 cmpEntriesArg *data = (cmpEntriesArg *) arg;
405 int res;
406
407 if (aa->isnull)
408 {
409 if (bb->isnull)
410 res = 0; /* NULL "=" NULL */
411 else
412 res = 1; /* NULL ">" not-NULL */
413 }
414 else if (bb->isnull)
415 res = -1; /* not-NULL "<" NULL */
416 else
417 res = DatumGetInt32(FunctionCall2Coll(data->cmpDatumFunc,
418 data->collation,
419 aa->datum, bb->datum));
420
421 /*
422 * Detect if we have any duplicates. If there are equal keys, qsort must
423 * compare them at some point, else it wouldn't know whether one should go
424 * before or after the other.
425 */
426 if (res == 0)
427 data->haveDups = true;
428
429 return res;
430 }
431
432
433 /*
434 * Extract the index key values from an indexable item
435 *
436 * The resulting key values are sorted, and any duplicates are removed.
437 * This avoids generating redundant index entries.
438 */
439 Datum *
ginExtractEntries(GinState * ginstate,OffsetNumber attnum,Datum value,bool isNull,int32 * nentries,GinNullCategory ** categories)440 ginExtractEntries(GinState *ginstate, OffsetNumber attnum,
441 Datum value, bool isNull,
442 int32 *nentries, GinNullCategory **categories)
443 {
444 Datum *entries;
445 bool *nullFlags;
446 int32 i;
447
448 /*
449 * We don't call the extractValueFn on a null item. Instead generate a
450 * placeholder.
451 */
452 if (isNull)
453 {
454 *nentries = 1;
455 entries = (Datum *) palloc(sizeof(Datum));
456 entries[0] = (Datum) 0;
457 *categories = (GinNullCategory *) palloc(sizeof(GinNullCategory));
458 (*categories)[0] = GIN_CAT_NULL_ITEM;
459 return entries;
460 }
461
462 /* OK, call the opclass's extractValueFn */
463 nullFlags = NULL; /* in case extractValue doesn't set it */
464 entries = (Datum *)
465 DatumGetPointer(FunctionCall3Coll(&ginstate->extractValueFn[attnum - 1],
466 ginstate->supportCollation[attnum - 1],
467 value,
468 PointerGetDatum(nentries),
469 PointerGetDatum(&nullFlags)));
470
471 /*
472 * Generate a placeholder if the item contained no keys.
473 */
474 if (entries == NULL || *nentries <= 0)
475 {
476 *nentries = 1;
477 entries = (Datum *) palloc(sizeof(Datum));
478 entries[0] = (Datum) 0;
479 *categories = (GinNullCategory *) palloc(sizeof(GinNullCategory));
480 (*categories)[0] = GIN_CAT_EMPTY_ITEM;
481 return entries;
482 }
483
484 /*
485 * If the extractValueFn didn't create a nullFlags array, create one,
486 * assuming that everything's non-null. Otherwise, run through the array
487 * and make sure each value is exactly 0 or 1; this ensures binary
488 * compatibility with the GinNullCategory representation.
489 */
490 if (nullFlags == NULL)
491 nullFlags = (bool *) palloc0(*nentries * sizeof(bool));
492 else
493 {
494 for (i = 0; i < *nentries; i++)
495 nullFlags[i] = (nullFlags[i] ? true : false);
496 }
497 /* now we can use the nullFlags as category codes */
498 *categories = (GinNullCategory *) nullFlags;
499
500 /*
501 * If there's more than one key, sort and unique-ify.
502 *
503 * XXX Using qsort here is notationally painful, and the overhead is
504 * pretty bad too. For small numbers of keys it'd likely be better to use
505 * a simple insertion sort.
506 */
507 if (*nentries > 1)
508 {
509 keyEntryData *keydata;
510 cmpEntriesArg arg;
511
512 keydata = (keyEntryData *) palloc(*nentries * sizeof(keyEntryData));
513 for (i = 0; i < *nentries; i++)
514 {
515 keydata[i].datum = entries[i];
516 keydata[i].isnull = nullFlags[i];
517 }
518
519 arg.cmpDatumFunc = &ginstate->compareFn[attnum - 1];
520 arg.collation = ginstate->supportCollation[attnum - 1];
521 arg.haveDups = false;
522 qsort_arg(keydata, *nentries, sizeof(keyEntryData),
523 cmpEntries, (void *) &arg);
524
525 if (arg.haveDups)
526 {
527 /* there are duplicates, must get rid of 'em */
528 int32 j;
529
530 entries[0] = keydata[0].datum;
531 nullFlags[0] = keydata[0].isnull;
532 j = 1;
533 for (i = 1; i < *nentries; i++)
534 {
535 if (cmpEntries(&keydata[i - 1], &keydata[i], &arg) != 0)
536 {
537 entries[j] = keydata[i].datum;
538 nullFlags[j] = keydata[i].isnull;
539 j++;
540 }
541 }
542 *nentries = j;
543 }
544 else
545 {
546 /* easy, no duplicates */
547 for (i = 0; i < *nentries; i++)
548 {
549 entries[i] = keydata[i].datum;
550 nullFlags[i] = keydata[i].isnull;
551 }
552 }
553
554 pfree(keydata);
555 }
556
557 return entries;
558 }
559
560 bytea *
ginoptions(Datum reloptions,bool validate)561 ginoptions(Datum reloptions, bool validate)
562 {
563 relopt_value *options;
564 GinOptions *rdopts;
565 int numoptions;
566 static const relopt_parse_elt tab[] = {
567 {"fastupdate", RELOPT_TYPE_BOOL, offsetof(GinOptions, useFastUpdate)},
568 {"gin_pending_list_limit", RELOPT_TYPE_INT, offsetof(GinOptions,
569 pendingListCleanupSize)}
570 };
571
572 options = parseRelOptions(reloptions, validate, RELOPT_KIND_GIN,
573 &numoptions);
574
575 /* if none set, we're done */
576 if (numoptions == 0)
577 return NULL;
578
579 rdopts = allocateReloptStruct(sizeof(GinOptions), options, numoptions);
580
581 fillRelOptions((void *) rdopts, sizeof(GinOptions), options, numoptions,
582 validate, tab, lengthof(tab));
583
584 pfree(options);
585
586 return (bytea *) rdopts;
587 }
588
589 /*
590 * Fetch index's statistical data into *stats
591 *
592 * Note: in the result, nPendingPages can be trusted to be up-to-date,
593 * as can ginVersion; but the other fields are as of the last VACUUM.
594 */
595 void
ginGetStats(Relation index,GinStatsData * stats)596 ginGetStats(Relation index, GinStatsData *stats)
597 {
598 Buffer metabuffer;
599 Page metapage;
600 GinMetaPageData *metadata;
601
602 metabuffer = ReadBuffer(index, GIN_METAPAGE_BLKNO);
603 LockBuffer(metabuffer, GIN_SHARE);
604 metapage = BufferGetPage(metabuffer);
605 metadata = GinPageGetMeta(metapage);
606
607 stats->nPendingPages = metadata->nPendingPages;
608 stats->nTotalPages = metadata->nTotalPages;
609 stats->nEntryPages = metadata->nEntryPages;
610 stats->nDataPages = metadata->nDataPages;
611 stats->nEntries = metadata->nEntries;
612 stats->ginVersion = metadata->ginVersion;
613
614 UnlockReleaseBuffer(metabuffer);
615 }
616
617 /*
618 * Write the given statistics to the index's metapage
619 *
620 * Note: nPendingPages and ginVersion are *not* copied over
621 */
622 void
ginUpdateStats(Relation index,const GinStatsData * stats)623 ginUpdateStats(Relation index, const GinStatsData *stats)
624 {
625 Buffer metabuffer;
626 Page metapage;
627 GinMetaPageData *metadata;
628
629 metabuffer = ReadBuffer(index, GIN_METAPAGE_BLKNO);
630 LockBuffer(metabuffer, GIN_EXCLUSIVE);
631 metapage = BufferGetPage(metabuffer);
632 metadata = GinPageGetMeta(metapage);
633
634 START_CRIT_SECTION();
635
636 metadata->nTotalPages = stats->nTotalPages;
637 metadata->nEntryPages = stats->nEntryPages;
638 metadata->nDataPages = stats->nDataPages;
639 metadata->nEntries = stats->nEntries;
640
641 MarkBufferDirty(metabuffer);
642
643 if (RelationNeedsWAL(index))
644 {
645 XLogRecPtr recptr;
646 ginxlogUpdateMeta data;
647
648 data.node = index->rd_node;
649 data.ntuples = 0;
650 data.newRightlink = data.prevTail = InvalidBlockNumber;
651 memcpy(&data.metadata, metadata, sizeof(GinMetaPageData));
652
653 XLogBeginInsert();
654 XLogRegisterData((char *) &data, sizeof(ginxlogUpdateMeta));
655 XLogRegisterBuffer(0, metabuffer, REGBUF_WILL_INIT);
656
657 recptr = XLogInsert(RM_GIN_ID, XLOG_GIN_UPDATE_META_PAGE);
658 PageSetLSN(metapage, recptr);
659 }
660
661 UnlockReleaseBuffer(metabuffer);
662
663 END_CRIT_SECTION();
664 }
665