Age Owner Branch data TLA Line data Source code
1 : : /*-------------------------------------------------------------------------
2 : : *
3 : : * spgutils.c
4 : : * various support functions for SP-GiST
5 : : *
6 : : *
7 : : * Portions Copyright (c) 1996-2024, PostgreSQL Global Development Group
8 : : * Portions Copyright (c) 1994, Regents of the University of California
9 : : *
10 : : * IDENTIFICATION
11 : : * src/backend/access/spgist/spgutils.c
12 : : *
13 : : *-------------------------------------------------------------------------
14 : : */
15 : :
16 : : #include "postgres.h"
17 : :
18 : : #include "access/amvalidate.h"
19 : : #include "access/htup_details.h"
20 : : #include "access/reloptions.h"
21 : : #include "access/spgist_private.h"
22 : : #include "access/toast_compression.h"
23 : : #include "access/transam.h"
24 : : #include "access/xact.h"
25 : : #include "catalog/pg_amop.h"
26 : : #include "commands/vacuum.h"
27 : : #include "nodes/nodeFuncs.h"
28 : : #include "parser/parse_coerce.h"
29 : : #include "storage/bufmgr.h"
30 : : #include "storage/indexfsm.h"
31 : : #include "utils/catcache.h"
32 : : #include "utils/fmgrprotos.h"
33 : : #include "utils/index_selfuncs.h"
34 : : #include "utils/lsyscache.h"
35 : : #include "utils/rel.h"
36 : : #include "utils/syscache.h"
37 : :
38 : :
39 : : /*
40 : : * SP-GiST handler function: return IndexAmRoutine with access method parameters
41 : : * and callbacks.
42 : : */
43 : : Datum
3010 tgl@sss.pgh.pa.us 44 :CBC 652 : spghandler(PG_FUNCTION_ARGS)
45 : : {
46 : 652 : IndexAmRoutine *amroutine = makeNode(IndexAmRoutine);
47 : :
48 : 652 : amroutine->amstrategies = 0;
2908 teodor@sigaev.ru 49 : 652 : amroutine->amsupport = SPGISTNProc;
1476 akorotkov@postgresql 50 : 652 : amroutine->amoptsprocnum = SPGIST_OPTIONS_PROC;
3010 tgl@sss.pgh.pa.us 51 : 652 : amroutine->amcanorder = false;
2034 akorotkov@postgresql 52 : 652 : amroutine->amcanorderbyop = true;
3010 tgl@sss.pgh.pa.us 53 : 652 : amroutine->amcanbackward = false;
54 : 652 : amroutine->amcanunique = false;
55 : 652 : amroutine->amcanmulticol = false;
56 : 652 : amroutine->amoptionalkey = true;
57 : 652 : amroutine->amsearcharray = false;
58 : 652 : amroutine->amsearchnulls = true;
1106 59 : 652 : amroutine->amstorage = true;
3010 60 : 652 : amroutine->amclusterable = false;
61 : 652 : amroutine->ampredlocks = false;
2615 rhaas@postgresql.org 62 : 652 : amroutine->amcanparallel = false;
128 tomas.vondra@postgre 63 :GNC 652 : amroutine->amcanbuildparallel = false;
1105 tgl@sss.pgh.pa.us 64 :CBC 652 : amroutine->amcaninclude = true;
1551 akapila@postgresql.o 65 : 652 : amroutine->amusemaintenanceworkmem = false;
391 tomas.vondra@postgre 66 : 652 : amroutine->amsummarizing = false;
1551 akapila@postgresql.o 67 : 652 : amroutine->amparallelvacuumoptions =
68 : : VACUUM_OPTION_PARALLEL_BULKDEL | VACUUM_OPTION_PARALLEL_COND_CLEANUP;
3010 tgl@sss.pgh.pa.us 69 : 652 : amroutine->amkeytype = InvalidOid;
70 : :
71 : 652 : amroutine->ambuild = spgbuild;
72 : 652 : amroutine->ambuildempty = spgbuildempty;
73 : 652 : amroutine->aminsert = spginsert;
141 tomas.vondra@postgre 74 :GNC 652 : amroutine->aminsertcleanup = NULL;
3010 tgl@sss.pgh.pa.us 75 :CBC 652 : amroutine->ambulkdelete = spgbulkdelete;
76 : 652 : amroutine->amvacuumcleanup = spgvacuumcleanup;
77 : 652 : amroutine->amcanreturn = spgcanreturn;
78 : 652 : amroutine->amcostestimate = spgcostestimate;
79 : 652 : amroutine->amoptions = spgoptions;
2034 akorotkov@postgresql 80 : 652 : amroutine->amproperty = spgproperty;
1839 alvherre@alvh.no-ip. 81 : 652 : amroutine->ambuildphasename = NULL;
3010 tgl@sss.pgh.pa.us 82 : 652 : amroutine->amvalidate = spgvalidate;
1352 83 : 652 : amroutine->amadjustmembers = spgadjustmembers;
3010 84 : 652 : amroutine->ambeginscan = spgbeginscan;
85 : 652 : amroutine->amrescan = spgrescan;
86 : 652 : amroutine->amgettuple = spggettuple;
87 : 652 : amroutine->amgetbitmap = spggetbitmap;
88 : 652 : amroutine->amendscan = spgendscan;
89 : 652 : amroutine->ammarkpos = NULL;
90 : 652 : amroutine->amrestrpos = NULL;
2637 rhaas@postgresql.org 91 : 652 : amroutine->amestimateparallelscan = NULL;
92 : 652 : amroutine->aminitparallelscan = NULL;
93 : 652 : amroutine->amparallelrescan = NULL;
94 : :
3010 tgl@sss.pgh.pa.us 95 : 652 : PG_RETURN_POINTER(amroutine);
96 : : }
97 : :
98 : : /*
99 : : * GetIndexInputType
100 : : * Determine the nominal input data type for an index column
101 : : *
102 : : * We define the "nominal" input type as the associated opclass's opcintype,
103 : : * or if that is a polymorphic type, the base type of the heap column or
104 : : * expression that is the index's input. The reason for preferring the
105 : : * opcintype is that non-polymorphic opclasses probably don't want to hear
106 : : * about binary-compatible input types. For instance, if a text opclass
107 : : * is being used with a varchar heap column, we want to report "text" not
108 : : * "varchar". Likewise, opclasses don't want to hear about domain types,
109 : : * so if we do consult the actual input type, we make sure to flatten domains.
110 : : *
111 : : * At some point maybe this should go somewhere else, but it's not clear
112 : : * if any other index AMs have a use for it.
113 : : */
114 : : static Oid
1106 115 : 211 : GetIndexInputType(Relation index, AttrNumber indexcol)
116 : : {
117 : : Oid opcintype;
118 : : AttrNumber heapcol;
119 : : List *indexprs;
120 : : ListCell *indexpr_item;
121 : :
122 [ - + ]: 211 : Assert(index->rd_index != NULL);
123 [ + - - + ]: 211 : Assert(indexcol > 0 && indexcol <= index->rd_index->indnkeyatts);
124 : 211 : opcintype = index->rd_opcintype[indexcol - 1];
125 [ + - + - : 211 : if (!IsPolymorphicType(opcintype))
+ - + - +
+ + - + -
+ - + - +
- + - ]
126 : 159 : return opcintype;
127 : 52 : heapcol = index->rd_index->indkey.values[indexcol - 1];
128 [ + + ]: 52 : if (heapcol != 0) /* Simple index column? */
129 : 46 : return getBaseType(get_atttype(index->rd_index->indrelid, heapcol));
130 : :
131 : : /*
132 : : * If the index expressions are already cached, skip calling
133 : : * RelationGetIndexExpressions, as it will make a copy which is overkill.
134 : : * We're not going to modify the trees, and we're not going to do anything
135 : : * that would invalidate the relcache entry before we're done.
136 : : */
137 [ - + ]: 6 : if (index->rd_indexprs)
1106 tgl@sss.pgh.pa.us 138 :UBC 0 : indexprs = index->rd_indexprs;
139 : : else
1106 tgl@sss.pgh.pa.us 140 :CBC 6 : indexprs = RelationGetIndexExpressions(index);
141 : 6 : indexpr_item = list_head(indexprs);
142 [ + - ]: 6 : for (int i = 1; i <= index->rd_index->indnkeyatts; i++)
143 : : {
144 [ + - ]: 6 : if (index->rd_index->indkey.values[i - 1] == 0)
145 : : {
146 : : /* expression column */
147 [ - + ]: 6 : if (indexpr_item == NULL)
1106 tgl@sss.pgh.pa.us 148 [ # # ]:UBC 0 : elog(ERROR, "wrong number of index expressions");
1106 tgl@sss.pgh.pa.us 149 [ + - ]:CBC 6 : if (i == indexcol)
150 : 6 : return getBaseType(exprType((Node *) lfirst(indexpr_item)));
1106 tgl@sss.pgh.pa.us 151 :UBC 0 : indexpr_item = lnext(indexprs, indexpr_item);
152 : : }
153 : : }
154 [ # # ]: 0 : elog(ERROR, "wrong number of index expressions");
155 : : return InvalidOid; /* keep compiler quiet */
156 : : }
157 : :
158 : : /* Fill in a SpGistTypeDesc struct with info about the specified data type */
159 : : static void
4502 tgl@sss.pgh.pa.us 160 :CBC 648 : fillTypeDesc(SpGistTypeDesc *desc, Oid type)
161 : : {
162 : : HeapTuple tp;
163 : : Form_pg_type typtup;
164 : :
165 : 648 : desc->type = type;
1105 166 : 648 : tp = SearchSysCache1(TYPEOID, ObjectIdGetDatum(type));
167 [ - + ]: 648 : if (!HeapTupleIsValid(tp))
1105 tgl@sss.pgh.pa.us 168 [ # # ]:UBC 0 : elog(ERROR, "cache lookup failed for type %u", type);
1105 tgl@sss.pgh.pa.us 169 :CBC 648 : typtup = (Form_pg_type) GETSTRUCT(tp);
170 : 648 : desc->attlen = typtup->typlen;
171 : 648 : desc->attbyval = typtup->typbyval;
172 : 648 : desc->attalign = typtup->typalign;
1057 173 : 648 : desc->attstorage = typtup->typstorage;
1105 174 : 648 : ReleaseSysCache(tp);
4502 175 : 648 : }
176 : :
177 : : /*
178 : : * Fetch local cache of AM-specific info about the index, initializing it
179 : : * if necessary
180 : : */
181 : : SpGistCache *
4500 182 : 1344359 : spgGetCache(Relation index)
183 : : {
184 : : SpGistCache *cache;
185 : :
186 [ + + ]: 1344359 : if (index->rd_amcache == NULL)
187 : : {
188 : : Oid atttype;
189 : : spgConfigIn in;
190 : : FmgrInfo *procinfo;
191 : :
192 : 211 : cache = MemoryContextAllocZero(index->rd_indexcxt,
193 : : sizeof(SpGistCache));
194 : :
195 : : /* SPGiST must have one key column and can also have INCLUDE columns */
1105 196 [ - + ]: 211 : Assert(IndexRelationGetNumberOfKeyAttributes(index) == 1);
197 [ - + ]: 211 : Assert(IndexRelationGetNumberOfAttributes(index) <= INDEX_MAX_KEYS);
198 : :
199 : : /*
200 : : * Get the actual (well, nominal) data type of the key column. We
201 : : * pass this to the opclass config function so that polymorphic
202 : : * opclasses are possible.
203 : : */
204 : 211 : atttype = GetIndexInputType(index, spgKeyColumn + 1);
205 : :
206 : : /* Call the config function to get config info for the opclass */
4500 207 : 211 : in.attType = atttype;
208 : :
209 : 211 : procinfo = index_getprocinfo(index, 1, SPGIST_CONFIG_PROC);
210 : 211 : FunctionCall2Coll(procinfo,
1105 211 : 211 : index->rd_indcollation[spgKeyColumn],
212 : : PointerGetDatum(&in),
4500 213 : 211 : PointerGetDatum(&cache->config));
214 : :
215 : : /*
216 : : * If leafType isn't specified, use the declared index column type,
217 : : * which index.c will have derived from the opclass's opcintype.
218 : : * (Although we now make spgvalidate.c warn if these aren't the same,
219 : : * old user-defined opclasses may not set the STORAGE parameter
220 : : * correctly, so believe leafType if it's given.)
221 : : */
1106 222 [ + + ]: 211 : if (!OidIsValid(cache->config.leafType))
223 : : {
224 : 196 : cache->config.leafType =
1105 225 : 196 : TupleDescAttr(RelationGetDescr(index), spgKeyColumn)->atttypid;
226 : :
227 : : /*
228 : : * If index column type is binary-coercible to atttype (for
229 : : * example, it's a domain over atttype), treat it as plain atttype
230 : : * to avoid thinking we need to compress.
231 : : */
876 232 [ + + + - ]: 203 : if (cache->config.leafType != atttype &&
233 : 7 : IsBinaryCoercible(cache->config.leafType, atttype))
234 : 7 : cache->config.leafType = atttype;
235 : : }
236 : :
237 : : /* Get the information we need about each relevant datatype */
4500 238 : 211 : fillTypeDesc(&cache->attType, atttype);
239 : :
1106 240 [ + + ]: 211 : if (cache->config.leafType != atttype)
241 : : {
2305 teodor@sigaev.ru 242 [ - + ]: 15 : if (!OidIsValid(index_getprocid(index, 1, SPGIST_COMPRESS_PROC)))
2305 teodor@sigaev.ru 243 [ # # ]:UBC 0 : ereport(ERROR,
244 : : (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
245 : : errmsg("compress method must be defined when leaf type is different from input type")));
246 : :
2305 teodor@sigaev.ru 247 :CBC 15 : fillTypeDesc(&cache->attLeafType, cache->config.leafType);
248 : : }
249 : : else
250 : : {
251 : : /* Save lookups in this common case */
252 : 196 : cache->attLeafType = cache->attType;
253 : : }
254 : :
4500 tgl@sss.pgh.pa.us 255 : 211 : fillTypeDesc(&cache->attPrefixType, cache->config.prefixType);
256 : 211 : fillTypeDesc(&cache->attLabelType, cache->config.labelType);
257 : :
258 : : /*
259 : : * Finally, if it's a real index (not a partitioned one), get the
260 : : * lastUsedPages data from the metapage
261 : : */
115 262 [ + + ]: 211 : if (index->rd_rel->relkind != RELKIND_PARTITIONED_INDEX)
263 : : {
264 : : Buffer metabuffer;
265 : : SpGistMetaPageData *metadata;
266 : :
267 : 208 : metabuffer = ReadBuffer(index, SPGIST_METAPAGE_BLKNO);
268 : 208 : LockBuffer(metabuffer, BUFFER_LOCK_SHARE);
269 : :
270 : 208 : metadata = SpGistPageGetMeta(BufferGetPage(metabuffer));
271 : :
272 [ - + ]: 208 : if (metadata->magicNumber != SPGIST_MAGIC_NUMBER)
115 tgl@sss.pgh.pa.us 273 [ # # ]:UBC 0 : elog(ERROR, "index \"%s\" is not an SP-GiST index",
274 : : RelationGetRelationName(index));
275 : :
115 tgl@sss.pgh.pa.us 276 :CBC 208 : cache->lastUsedPages = metadata->lastUsedPages;
277 : :
278 : 208 : UnlockReleaseBuffer(metabuffer);
279 : : }
280 : :
4500 281 : 211 : index->rd_amcache = (void *) cache;
282 : : }
283 : : else
284 : : {
285 : : /* assume it's up to date */
286 : 1344148 : cache = (SpGistCache *) index->rd_amcache;
287 : : }
288 : :
289 : 1344359 : return cache;
290 : : }
291 : :
292 : : /*
293 : : * Compute a tuple descriptor for leaf tuples or index-only-scan result tuples.
294 : : *
295 : : * We can use the relcache's tupdesc as-is in many cases, and it's always
296 : : * OK so far as any INCLUDE columns are concerned. However, the entry for
297 : : * the key column has to match leafType in the first case or attType in the
298 : : * second case. While the relcache's tupdesc *should* show leafType, this
299 : : * might not hold for legacy user-defined opclasses, since before v14 they
300 : : * were not allowed to declare their true storage type in CREATE OPCLASS.
301 : : * Also, attType can be different from what is in the relcache.
302 : : *
303 : : * This function gives back either a pointer to the relcache's tupdesc
304 : : * if that is suitable, or a palloc'd copy that's been adjusted to match
305 : : * the specified key column type. We can avoid doing any catalog lookups
306 : : * here by insisting that the caller pass an SpGistTypeDesc not just an OID.
307 : : */
308 : : TupleDesc
1105 309 : 122346 : getSpGistTupleDesc(Relation index, SpGistTypeDesc *keyType)
310 : : {
311 : : TupleDesc outTupDesc;
312 : : Form_pg_attribute att;
313 : :
314 : 122346 : if (keyType->type ==
315 [ + + ]: 122346 : TupleDescAttr(RelationGetDescr(index), spgKeyColumn)->atttypid)
316 : 122281 : outTupDesc = RelationGetDescr(index);
317 : : else
318 : : {
319 : 65 : outTupDesc = CreateTupleDescCopy(RelationGetDescr(index));
320 : 65 : att = TupleDescAttr(outTupDesc, spgKeyColumn);
321 : : /* It's sufficient to update the type-dependent fields of the column */
322 : 65 : att->atttypid = keyType->type;
323 : 65 : att->atttypmod = -1;
324 : 65 : att->attlen = keyType->attlen;
325 : 65 : att->attbyval = keyType->attbyval;
326 : 65 : att->attalign = keyType->attalign;
327 : 65 : att->attstorage = keyType->attstorage;
328 : : /* We shouldn't need to bother with making these valid: */
329 : 65 : att->attcompression = InvalidCompressionMethod;
1057 330 : 65 : att->attcollation = InvalidOid;
331 : : /* In case we changed typlen, we'd better reset following offsets */
1105 332 [ + + ]: 73 : for (int i = spgFirstIncludeColumn; i < outTupDesc->natts; i++)
333 : 8 : TupleDescAttr(outTupDesc, i)->attcacheoff = -1;
334 : : }
335 : 122346 : return outTupDesc;
336 : : }
337 : :
338 : : /* Initialize SpGistState for working with the given index */
339 : : void
4502 340 : 121894 : initSpGistState(SpGistState *state, Relation index)
341 : : {
342 : : SpGistCache *cache;
343 : :
1105 344 : 121894 : state->index = index;
345 : :
346 : : /* Get cached static information about index */
4500 347 : 121894 : cache = spgGetCache(index);
348 : :
349 : 121894 : state->config = cache->config;
350 : 121894 : state->attType = cache->attType;
2305 teodor@sigaev.ru 351 : 121894 : state->attLeafType = cache->attLeafType;
4500 tgl@sss.pgh.pa.us 352 : 121894 : state->attPrefixType = cache->attPrefixType;
353 : 121894 : state->attLabelType = cache->attLabelType;
354 : :
355 : : /* Ensure we have a valid descriptor for leaf tuples */
1105 356 : 121894 : state->leafTupDesc = getSpGistTupleDesc(state->index, &state->attLeafType);
357 : :
358 : : /* Make workspace for constructing dead tuples */
4502 359 : 121894 : state->deadTupleStorage = palloc0(SGDTSIZE);
360 : :
361 : : /* Set XID to use in redirection tuples */
362 : 121894 : state->myXid = GetTopTransactionIdIfAny();
363 : :
364 : : /* Assume we're not in an index build (spgbuild will override) */
365 : 121894 : state->isBuild = false;
366 : 121894 : }
367 : :
368 : : /*
369 : : * Allocate a new page (either by recycling, or by extending the index file).
370 : : *
371 : : * The returned buffer is already pinned and exclusive-locked.
372 : : * Caller is responsible for initializing the page by calling SpGistInitBuffer.
373 : : */
374 : : Buffer
375 : 3281 : SpGistNewBuffer(Relation index)
376 : : {
377 : : Buffer buffer;
378 : :
379 : : /* First, try to get a page from FSM */
380 : : for (;;)
4502 tgl@sss.pgh.pa.us 381 :UBC 0 : {
4502 tgl@sss.pgh.pa.us 382 :CBC 3281 : BlockNumber blkno = GetFreeIndexPage(index);
383 : :
384 [ + + ]: 3281 : if (blkno == InvalidBlockNumber)
385 : 3276 : break; /* nothing known to FSM */
386 : :
387 : : /*
388 : : * The fixed pages shouldn't ever be listed in FSM, but just in case
389 : : * one is, ignore it.
390 : : */
4417 391 [ - + ]: 5 : if (SpGistBlockIsFixed(blkno))
4502 tgl@sss.pgh.pa.us 392 :UBC 0 : continue;
393 : :
4502 tgl@sss.pgh.pa.us 394 :CBC 5 : buffer = ReadBuffer(index, blkno);
395 : :
396 : : /*
397 : : * We have to guard against the possibility that someone else already
398 : : * recycled this page; the buffer may be locked if so.
399 : : */
400 [ + - ]: 5 : if (ConditionalLockBuffer(buffer))
401 : : {
2916 kgrittn@postgresql.o 402 : 5 : Page page = BufferGetPage(buffer);
403 : :
4502 tgl@sss.pgh.pa.us 404 [ + + ]: 5 : if (PageIsNew(page))
405 : 1 : return buffer; /* OK to use, if never initialized */
406 : :
407 [ + - + - ]: 4 : if (SpGistPageIsDeleted(page) || PageIsEmpty(page))
408 : 4 : return buffer; /* OK to use */
409 : :
4502 tgl@sss.pgh.pa.us 410 :UBC 0 : LockBuffer(buffer, BUFFER_LOCK_UNLOCK);
411 : : }
412 : :
413 : : /* Can't use it, so release buffer and try again */
414 : 0 : ReleaseBuffer(buffer);
415 : : }
416 : :
235 tmunro@postgresql.or 417 :CBC 3276 : buffer = ExtendBufferedRel(BMR_REL(index), MAIN_FORKNUM, NULL,
418 : : EB_LOCK_FIRST);
419 : :
4502 tgl@sss.pgh.pa.us 420 : 3276 : return buffer;
421 : : }
422 : :
423 : : /*
424 : : * Update index metapage's lastUsedPages info from local cache, if possible
425 : : *
426 : : * Updating meta page isn't critical for index working, so
427 : : * 1 use ConditionalLockBuffer to improve concurrency
428 : : * 2 don't WAL-log metabuffer changes to decrease WAL traffic
429 : : */
430 : : void
431 : 121440 : SpGistUpdateMetaPage(Relation index)
432 : : {
433 : 121440 : SpGistCache *cache = (SpGistCache *) index->rd_amcache;
434 : :
435 [ + - ]: 121440 : if (cache != NULL)
436 : : {
437 : : Buffer metabuffer;
438 : :
439 : 121440 : metabuffer = ReadBuffer(index, SPGIST_METAPAGE_BLKNO);
440 : :
441 [ + - ]: 121440 : if (ConditionalLockBuffer(metabuffer))
442 : : {
2355 443 : 121440 : Page metapage = BufferGetPage(metabuffer);
444 : 121440 : SpGistMetaPageData *metadata = SpGistPageGetMeta(metapage);
445 : :
4500 446 : 121440 : metadata->lastUsedPages = cache->lastUsedPages;
447 : :
448 : : /*
449 : : * Set pd_lower just past the end of the metadata. This is
450 : : * essential, because without doing so, metadata will be lost if
451 : : * xlog.c compresses the page. (We must do this here because
452 : : * pre-v11 versions of PG did not set the metapage's pd_lower
453 : : * correctly, so a pg_upgraded index might contain the wrong
454 : : * value.)
455 : : */
2355 456 : 121440 : ((PageHeader) metapage)->pd_lower =
457 : 121440 : ((char *) metadata + sizeof(SpGistMetaPageData)) - (char *) metapage;
458 : :
4502 459 : 121440 : MarkBufferDirty(metabuffer);
460 : 121440 : UnlockReleaseBuffer(metabuffer);
461 : : }
462 : : else
463 : : {
4502 tgl@sss.pgh.pa.us 464 :UBC 0 : ReleaseBuffer(metabuffer);
465 : : }
466 : : }
4502 tgl@sss.pgh.pa.us 467 :CBC 121440 : }
468 : :
469 : : /* Macro to select proper element of lastUsedPages cache depending on flags */
470 : : /* Masking flags with SPGIST_CACHED_PAGES is just for paranoia's sake */
471 : : #define GET_LUP(c, f) (&(c)->lastUsedPages.cachedPage[((unsigned int) (f)) % SPGIST_CACHED_PAGES])
472 : :
473 : : /*
474 : : * Allocate and initialize a new buffer of the type and parity specified by
475 : : * flags. The returned buffer is already pinned and exclusive-locked.
476 : : *
477 : : * When requesting an inner page, if we get one with the wrong parity,
478 : : * we just release the buffer and try again. We will get a different page
479 : : * because GetFreeIndexPage will have marked the page used in FSM. The page
480 : : * is entered in our local lastUsedPages cache, so there's some hope of
481 : : * making use of it later in this session, but otherwise we rely on VACUUM
482 : : * to eventually re-enter the page in FSM, making it available for recycling.
483 : : * Note that such a page does not get marked dirty here, so unless it's used
484 : : * fairly soon, the buffer will just get discarded and the page will remain
485 : : * as it was on disk.
486 : : *
487 : : * When we return a buffer to the caller, the page is *not* entered into
488 : : * the lastUsedPages cache; we expect the caller will do so after it's taken
489 : : * whatever space it will use. This is because after the caller has used up
490 : : * some space, the page might have less space than whatever was cached already
491 : : * so we'd rather not trash the old cache entry.
492 : : */
493 : : static Buffer
494 : 2926 : allocNewBuffer(Relation index, int flags)
495 : : {
496 : 2926 : SpGistCache *cache = spgGetCache(index);
4417 497 : 2926 : uint16 pageflags = 0;
498 : :
499 [ + + ]: 2926 : if (GBUF_REQ_LEAF(flags))
500 : 2873 : pageflags |= SPGIST_LEAF;
501 [ - + ]: 2926 : if (GBUF_REQ_NULLS(flags))
4417 tgl@sss.pgh.pa.us 502 :UBC 0 : pageflags |= SPGIST_NULLS;
503 : :
504 : : for (;;)
4502 tgl@sss.pgh.pa.us 505 :CBC 43 : {
506 : : Buffer buffer;
507 : :
508 : 2969 : buffer = SpGistNewBuffer(index);
4417 509 : 2969 : SpGistInitBuffer(buffer, pageflags);
510 : :
511 [ + + ]: 2969 : if (pageflags & SPGIST_LEAF)
512 : : {
513 : : /* Leaf pages have no parity concerns, so just use it */
4502 514 : 2873 : return buffer;
515 : : }
516 : : else
517 : : {
518 : 96 : BlockNumber blkno = BufferGetBlockNumber(buffer);
4326 bruce@momjian.us 519 : 96 : int blkFlags = GBUF_INNER_PARITY(blkno);
520 : :
4417 tgl@sss.pgh.pa.us 521 [ + + ]: 96 : if ((flags & GBUF_PARITY_MASK) == blkFlags)
522 : : {
523 : : /* Page has right parity, use it */
4502 524 : 53 : return buffer;
525 : : }
526 : : else
527 : : {
528 : : /* Page has wrong parity, record it in cache and try again */
4417 529 [ - + ]: 43 : if (pageflags & SPGIST_NULLS)
4417 tgl@sss.pgh.pa.us 530 :UBC 0 : blkFlags |= GBUF_NULLS;
4417 tgl@sss.pgh.pa.us 531 :CBC 43 : cache->lastUsedPages.cachedPage[blkFlags].blkno = blkno;
532 : 43 : cache->lastUsedPages.cachedPage[blkFlags].freeSpace =
2916 kgrittn@postgresql.o 533 : 43 : PageGetExactFreeSpace(BufferGetPage(buffer));
4502 tgl@sss.pgh.pa.us 534 : 43 : UnlockReleaseBuffer(buffer);
535 : : }
536 : : }
537 : : }
538 : : }
539 : :
540 : : /*
541 : : * Get a buffer of the type and parity specified by flags, having at least
542 : : * as much free space as indicated by needSpace. We use the lastUsedPages
543 : : * cache to assign the same buffer previously requested when possible.
544 : : * The returned buffer is already pinned and exclusive-locked.
545 : : *
546 : : * *isNew is set true if the page was initialized here, false if it was
547 : : * already valid.
548 : : */
549 : : Buffer
550 : 5456 : SpGistGetBuffer(Relation index, int flags, int needSpace, bool *isNew)
551 : : {
552 : 5456 : SpGistCache *cache = spgGetCache(index);
553 : : SpGistLastUsedPage *lup;
554 : :
555 : : /* Bail out if even an empty page wouldn't meet the demand */
556 [ - + ]: 5456 : if (needSpace > SPGIST_PAGE_CAPACITY)
4502 tgl@sss.pgh.pa.us 557 [ # # ]:UBC 0 : elog(ERROR, "desired SPGiST tuple size is too big");
558 : :
559 : : /*
560 : : * If possible, increase the space request to include relation's
561 : : * fillfactor. This ensures that when we add unrelated tuples to a page,
562 : : * we try to keep 100-fillfactor% available for adding tuples that are
563 : : * related to the ones already on it. But fillfactor mustn't cause an
564 : : * error for requests that would otherwise be legal.
565 : : */
1602 michael@paquier.xyz 566 [ + - - + :CBC 5456 : needSpace += SpGistGetTargetPageFreeSpace(index);
+ + ]
4502 tgl@sss.pgh.pa.us 567 [ + + ]: 5456 : needSpace = Min(needSpace, SPGIST_PAGE_CAPACITY);
568 : :
569 : : /* Get the cache entry for this flags setting */
570 : 5456 : lup = GET_LUP(cache, flags);
571 : :
572 : : /* If we have nothing cached, just turn it over to allocNewBuffer */
573 [ + + ]: 5456 : if (lup->blkno == InvalidBlockNumber)
574 : : {
575 : 91 : *isNew = true;
576 : 91 : return allocNewBuffer(index, flags);
577 : : }
578 : :
579 : : /* fixed pages should never be in cache */
4417 580 [ - + ]: 5365 : Assert(!SpGistBlockIsFixed(lup->blkno));
581 : :
582 : : /* If cached freeSpace isn't enough, don't bother looking at the page */
4502 583 [ + + ]: 5365 : if (lup->freeSpace >= needSpace)
584 : : {
585 : : Buffer buffer;
586 : : Page page;
587 : :
588 : 2530 : buffer = ReadBuffer(index, lup->blkno);
589 : :
590 [ - + ]: 2530 : if (!ConditionalLockBuffer(buffer))
591 : : {
592 : : /*
593 : : * buffer is locked by another process, so return a new buffer
594 : : */
4502 tgl@sss.pgh.pa.us 595 :UBC 0 : ReleaseBuffer(buffer);
596 : 0 : *isNew = true;
597 : 0 : return allocNewBuffer(index, flags);
598 : : }
599 : :
2916 kgrittn@postgresql.o 600 :CBC 2530 : page = BufferGetPage(buffer);
601 : :
4502 tgl@sss.pgh.pa.us 602 [ + - + - : 2530 : if (PageIsNew(page) || SpGistPageIsDeleted(page) || PageIsEmpty(page))
+ + ]
603 : : {
604 : : /* OK to initialize the page */
4417 605 : 92 : uint16 pageflags = 0;
606 : :
607 [ + + ]: 92 : if (GBUF_REQ_LEAF(flags))
608 : 89 : pageflags |= SPGIST_LEAF;
609 [ - + ]: 92 : if (GBUF_REQ_NULLS(flags))
4417 tgl@sss.pgh.pa.us 610 :UBC 0 : pageflags |= SPGIST_NULLS;
4417 tgl@sss.pgh.pa.us 611 :CBC 92 : SpGistInitBuffer(buffer, pageflags);
4502 612 : 92 : lup->freeSpace = PageGetExactFreeSpace(page) - needSpace;
613 : 92 : *isNew = true;
614 : 92 : return buffer;
615 : : }
616 : :
617 : : /*
618 : : * Check that page is of right type and has enough space. We must
619 : : * recheck this since our cache isn't necessarily up to date.
620 : : */
4417 621 [ + + + - : 4876 : if ((GBUF_REQ_LEAF(flags) ? SpGistPageIsLeaf(page) : !SpGistPageIsLeaf(page)) &&
+ - ]
622 [ - + ]: 2438 : (GBUF_REQ_NULLS(flags) ? SpGistPageStoresNulls(page) : !SpGistPageStoresNulls(page)))
623 : : {
4502 624 : 2438 : int freeSpace = PageGetExactFreeSpace(page);
625 : :
626 [ + - ]: 2438 : if (freeSpace >= needSpace)
627 : : {
628 : : /* Success, update freespace info and return the buffer */
629 : 2438 : lup->freeSpace = freeSpace - needSpace;
630 : 2438 : *isNew = false;
631 : 2438 : return buffer;
632 : : }
633 : : }
634 : :
635 : : /*
636 : : * fallback to allocation of new buffer
637 : : */
4502 tgl@sss.pgh.pa.us 638 :UBC 0 : UnlockReleaseBuffer(buffer);
639 : : }
640 : :
641 : : /* No success with cache, so return a new buffer */
4502 tgl@sss.pgh.pa.us 642 :CBC 2835 : *isNew = true;
643 : 2835 : return allocNewBuffer(index, flags);
644 : : }
645 : :
646 : : /*
647 : : * Update lastUsedPages cache when done modifying a page.
648 : : *
649 : : * We update the appropriate cache entry if it already contained this page
650 : : * (its freeSpace is likely obsolete), or if this page has more space than
651 : : * whatever we had cached.
652 : : */
653 : : void
654 : 1213170 : SpGistSetLastUsedPage(Relation index, Buffer buffer)
655 : : {
656 : 1213170 : SpGistCache *cache = spgGetCache(index);
657 : : SpGistLastUsedPage *lup;
658 : : int freeSpace;
2916 kgrittn@postgresql.o 659 : 1213170 : Page page = BufferGetPage(buffer);
4502 tgl@sss.pgh.pa.us 660 : 1213170 : BlockNumber blkno = BufferGetBlockNumber(buffer);
661 : : int flags;
662 : :
663 : : /* Never enter fixed pages (root pages) in cache, though */
4417 664 [ + + ]: 1213170 : if (SpGistBlockIsFixed(blkno))
4502 665 : 402681 : return;
666 : :
667 [ + + ]: 810489 : if (SpGistPageIsLeaf(page))
668 : 418077 : flags = GBUF_LEAF;
669 : : else
670 : 392412 : flags = GBUF_INNER_PARITY(blkno);
4417 671 [ - + ]: 810489 : if (SpGistPageStoresNulls(page))
4417 tgl@sss.pgh.pa.us 672 :UBC 0 : flags |= GBUF_NULLS;
673 : :
4502 tgl@sss.pgh.pa.us 674 :CBC 810489 : lup = GET_LUP(cache, flags);
675 : :
676 : 810489 : freeSpace = PageGetExactFreeSpace(page);
677 [ + + + + ]: 810489 : if (lup->blkno == InvalidBlockNumber || lup->blkno == blkno ||
678 [ + + ]: 228350 : lup->freeSpace < freeSpace)
679 : : {
680 : 586452 : lup->blkno = blkno;
681 : 586452 : lup->freeSpace = freeSpace;
682 : : }
683 : : }
684 : :
685 : : /*
686 : : * Initialize an SPGiST page to empty, with specified flags
687 : : */
688 : : void
689 : 3820 : SpGistInitPage(Page page, uint16 f)
690 : : {
691 : : SpGistPageOpaque opaque;
692 : :
1103 michael@paquier.xyz 693 : 3820 : PageInit(page, BLCKSZ, sizeof(SpGistPageOpaqueData));
4502 tgl@sss.pgh.pa.us 694 : 3820 : opaque = SpGistPageGetOpaque(page);
695 : 3820 : opaque->flags = f;
696 : 3820 : opaque->spgist_page_id = SPGIST_PAGE_ID;
697 : 3820 : }
698 : :
699 : : /*
700 : : * Initialize a buffer's page to empty, with specified flags
701 : : */
702 : : void
703 : 3704 : SpGistInitBuffer(Buffer b, uint16 f)
704 : : {
705 [ - + ]: 3704 : Assert(BufferGetPageSize(b) == BLCKSZ);
2916 kgrittn@postgresql.o 706 : 3704 : SpGistInitPage(BufferGetPage(b), f);
4502 tgl@sss.pgh.pa.us 707 : 3704 : }
708 : :
709 : : /*
710 : : * Initialize metadata page
711 : : */
712 : : void
713 : 108 : SpGistInitMetapage(Page page)
714 : : {
715 : : SpGistMetaPageData *metadata;
716 : : int i;
717 : :
718 : 108 : SpGistInitPage(page, SPGIST_META);
719 : 108 : metadata = SpGistPageGetMeta(page);
720 : 108 : memset(metadata, 0, sizeof(SpGistMetaPageData));
721 : 108 : metadata->magicNumber = SPGIST_MAGIC_NUMBER;
722 : :
723 : : /* initialize last-used-page cache to empty */
4417 724 [ + + ]: 972 : for (i = 0; i < SPGIST_CACHED_PAGES; i++)
725 : 864 : metadata->lastUsedPages.cachedPage[i].blkno = InvalidBlockNumber;
726 : :
727 : : /*
728 : : * Set pd_lower just past the end of the metadata. This is essential,
729 : : * because without doing so, metadata will be lost if xlog.c compresses
730 : : * the page.
731 : : */
2355 732 : 108 : ((PageHeader) page)->pd_lower =
733 : 108 : ((char *) metadata + sizeof(SpGistMetaPageData)) - (char *) page;
4502 734 : 108 : }
735 : :
736 : : /*
737 : : * reloptions processing for SPGiST
738 : : */
739 : : bytea *
3010 740 : 54 : spgoptions(Datum reloptions, bool validate)
741 : : {
742 : : static const relopt_parse_elt tab[] = {
743 : : {"fillfactor", RELOPT_TYPE_INT, offsetof(SpGistOptions, fillfactor)},
744 : : };
745 : :
1602 michael@paquier.xyz 746 : 54 : return (bytea *) build_reloptions(reloptions, validate,
747 : : RELOPT_KIND_SPGIST,
748 : : sizeof(SpGistOptions),
749 : : tab, lengthof(tab));
750 : : }
751 : :
752 : : /*
753 : : * Get the space needed to store a non-null datum of the indicated type
754 : : * in an inner tuple (that is, as a prefix or node label).
755 : : * Note the result is already rounded up to a MAXALIGN boundary.
756 : : * Here we follow the convention that pass-by-val types are just stored
757 : : * in their Datum representation (compare memcpyInnerDatum).
758 : : */
759 : : unsigned int
1109 tgl@sss.pgh.pa.us 760 : 6185 : SpGistGetInnerTypeSize(SpGistTypeDesc *att, Datum datum)
761 : : {
762 : : unsigned int size;
763 : :
4502 764 [ + + ]: 6185 : if (att->attbyval)
765 : 3264 : size = sizeof(Datum);
766 [ + + ]: 2921 : else if (att->attlen > 0)
767 : 1984 : size = att->attlen;
768 : : else
769 [ - + - - : 937 : size = VARSIZE_ANY(datum);
- - - - +
+ ]
770 : :
771 : 6185 : return MAXALIGN(size);
772 : : }
773 : :
774 : : /*
775 : : * Copy the given non-null datum to *target, in the inner-tuple case
776 : : */
777 : : static void
1109 778 : 6185 : memcpyInnerDatum(void *target, SpGistTypeDesc *att, Datum datum)
779 : : {
780 : : unsigned int size;
781 : :
4502 782 [ + + ]: 6185 : if (att->attbyval)
783 : : {
784 : 3264 : memcpy(target, &datum, sizeof(Datum));
785 : : }
786 : : else
787 : : {
788 [ + + - + : 2921 : size = (att->attlen > 0) ? att->attlen : VARSIZE_ANY(datum);
- - - - -
- + + ]
789 : 2921 : memcpy(target, DatumGetPointer(datum), size);
790 : : }
791 : 6185 : }
792 : :
793 : : /*
794 : : * Compute space required for a leaf tuple holding the given data.
795 : : *
796 : : * This must match the size-calculation portion of spgFormLeafTuple.
797 : : */
798 : : Size
1105 799 : 9731092 : SpGistGetLeafTupleSize(TupleDesc tupleDescriptor,
800 : : const Datum *datums, const bool *isnulls)
801 : : {
802 : : Size size;
803 : : Size data_size;
804 : 9731092 : bool needs_null_mask = false;
805 : 9731092 : int natts = tupleDescriptor->natts;
806 : :
807 : : /*
808 : : * Decide whether we need a nulls bitmask.
809 : : *
810 : : * If there is only a key attribute (natts == 1), never use a bitmask, for
811 : : * compatibility with the pre-v14 layout of leaf tuples. Otherwise, we
812 : : * need one if any attribute is null.
813 : : */
814 [ + + ]: 9731092 : if (natts > 1)
815 : : {
816 [ + + ]: 498517 : for (int i = 0; i < natts; i++)
817 : : {
818 [ + + ]: 341077 : if (isnulls[i])
819 : : {
820 : 8849 : needs_null_mask = true;
821 : 8849 : break;
822 : : }
823 : : }
824 : : }
825 : :
826 : : /*
827 : : * Calculate size of the data part; same as for heap tuples.
828 : : */
829 : 9731092 : data_size = heap_compute_data_size(tupleDescriptor, datums, isnulls);
830 : :
831 : : /*
832 : : * Compute total size.
833 : : */
834 : 9731092 : size = SGLTHDRSZ(needs_null_mask);
835 : 9731092 : size += data_size;
836 : 9731092 : size = MAXALIGN(size);
837 : :
838 : : /*
839 : : * Ensure that we can replace the tuple with a dead tuple later. This test
840 : : * is unnecessary when there are any non-null attributes, but be safe.
841 : : */
842 [ - + ]: 9731092 : if (size < SGDTSIZE)
1105 tgl@sss.pgh.pa.us 843 :UBC 0 : size = SGDTSIZE;
844 : :
1105 tgl@sss.pgh.pa.us 845 :CBC 9731092 : return size;
846 : : }
847 : :
848 : : /*
849 : : * Construct a leaf tuple containing the given heap TID and datum values
850 : : */
851 : : SpGistLeafTuple
4417 852 : 765138 : spgFormLeafTuple(SpGistState *state, ItemPointer heapPtr,
853 : : const Datum *datums, const bool *isnulls)
854 : : {
855 : : SpGistLeafTuple tup;
1105 856 : 765138 : TupleDesc tupleDescriptor = state->leafTupDesc;
857 : : Size size;
858 : : Size hoff;
859 : : Size data_size;
860 : 765138 : bool needs_null_mask = false;
861 : 765138 : int natts = tupleDescriptor->natts;
862 : : char *tp; /* ptr to tuple data */
863 : 765138 : uint16 tupmask = 0; /* unused heap_fill_tuple output */
864 : :
865 : : /*
866 : : * Decide whether we need a nulls bitmask.
867 : : *
868 : : * If there is only a key attribute (natts == 1), never use a bitmask, for
869 : : * compatibility with the pre-v14 layout of leaf tuples. Otherwise, we
870 : : * need one if any attribute is null.
871 : : */
872 [ + + ]: 765138 : if (natts > 1)
873 : : {
874 [ + + ]: 210388 : for (int i = 0; i < natts; i++)
875 : : {
876 [ + + ]: 146180 : if (isnulls[i])
877 : : {
878 : 5953 : needs_null_mask = true;
879 : 5953 : break;
880 : : }
881 : : }
882 : : }
883 : :
884 : : /*
885 : : * Calculate size of the data part; same as for heap tuples.
886 : : */
887 : 765138 : data_size = heap_compute_data_size(tupleDescriptor, datums, isnulls);
888 : :
889 : : /*
890 : : * Compute total size.
891 : : */
892 : 765138 : hoff = SGLTHDRSZ(needs_null_mask);
893 : 765138 : size = hoff + data_size;
894 : 765138 : size = MAXALIGN(size);
895 : :
896 : : /*
897 : : * Ensure that we can replace the tuple with a dead tuple later. This test
898 : : * is unnecessary when there are any non-null attributes, but be safe.
899 : : */
4502 900 [ - + ]: 765138 : if (size < SGDTSIZE)
4502 tgl@sss.pgh.pa.us 901 :UBC 0 : size = SGDTSIZE;
902 : :
903 : : /* OK, form the tuple */
4502 tgl@sss.pgh.pa.us 904 :CBC 765138 : tup = (SpGistLeafTuple) palloc0(size);
905 : :
906 : 765138 : tup->size = size;
1105 907 : 765138 : SGLT_SET_NEXTOFFSET(tup, InvalidOffsetNumber);
4502 908 : 765138 : tup->heapPtr = *heapPtr;
909 : :
1105 910 : 765138 : tp = (char *) tup + hoff;
911 : :
912 [ + + ]: 765138 : if (needs_null_mask)
913 : : {
914 : : bits8 *bp; /* ptr to null bitmap in tuple */
915 : :
916 : : /* Set nullmask presence bit in SpGistLeafTuple header */
917 : 5953 : SGLT_SET_HASNULLMASK(tup, true);
918 : : /* Fill the data area and null mask */
919 : 5953 : bp = (bits8 *) ((char *) tup + sizeof(SpGistLeafTupleData));
920 : 5953 : heap_fill_tuple(tupleDescriptor, datums, isnulls, tp, data_size,
921 : : &tupmask, bp);
922 : : }
923 [ + + + + ]: 759185 : else if (natts > 1 || !isnulls[spgKeyColumn])
924 : : {
925 : : /* Fill data area only */
926 : 759149 : heap_fill_tuple(tupleDescriptor, datums, isnulls, tp, data_size,
927 : : &tupmask, (bits8 *) NULL);
928 : : }
929 : : /* otherwise we have no data, nor a bitmap, to fill */
930 : :
4502 931 : 765138 : return tup;
932 : : }
933 : :
934 : : /*
935 : : * Construct a node (to go into an inner tuple) containing the given label
936 : : *
937 : : * Note that the node's downlink is just set invalid here. Caller will fill
938 : : * it in later.
939 : : */
940 : : SpGistNodeTuple
941 : 20283 : spgFormNodeTuple(SpGistState *state, Datum label, bool isnull)
942 : : {
943 : : SpGistNodeTuple tup;
944 : : unsigned int size;
945 : 20283 : unsigned short infomask = 0;
946 : :
947 : : /* compute space needed (note result is already maxaligned) */
948 : 20283 : size = SGNTHDRSZ;
949 [ + + ]: 20283 : if (!isnull)
1109 950 : 2919 : size += SpGistGetInnerTypeSize(&state->attLabelType, label);
951 : :
952 : : /*
953 : : * Here we make sure that the size will fit in the field reserved for it
954 : : * in t_info.
955 : : */
4502 956 [ - + ]: 20283 : if ((size & INDEX_SIZE_MASK) != size)
4502 tgl@sss.pgh.pa.us 957 [ # # ]:UBC 0 : ereport(ERROR,
958 : : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
959 : : errmsg("index row requires %zu bytes, maximum size is %zu",
960 : : (Size) size, (Size) INDEX_SIZE_MASK)));
961 : :
4502 tgl@sss.pgh.pa.us 962 :CBC 20283 : tup = (SpGistNodeTuple) palloc0(size);
963 : :
964 [ + + ]: 20283 : if (isnull)
965 : 17364 : infomask |= INDEX_NULL_MASK;
966 : : /* we don't bother setting the INDEX_VAR_MASK bit */
967 : 20283 : infomask |= size;
968 : 20283 : tup->t_info = infomask;
969 : :
970 : : /* The TID field will be filled in later */
971 : 20283 : ItemPointerSetInvalid(&tup->t_tid);
972 : :
973 [ + + ]: 20283 : if (!isnull)
1109 974 : 2919 : memcpyInnerDatum(SGNTDATAPTR(tup), &state->attLabelType, label);
975 : :
4502 976 : 20283 : return tup;
977 : : }
978 : :
979 : : /*
980 : : * Construct an inner tuple containing the given prefix and node array
981 : : */
982 : : SpGistInnerTuple
983 : 4265 : spgFormInnerTuple(SpGistState *state, bool hasPrefix, Datum prefix,
984 : : int nNodes, SpGistNodeTuple *nodes)
985 : : {
986 : : SpGistInnerTuple tup;
987 : : unsigned int size;
988 : : unsigned int prefixSize;
989 : : int i;
990 : : char *ptr;
991 : :
992 : : /* Compute size needed */
993 [ + + ]: 4265 : if (hasPrefix)
1109 994 : 3266 : prefixSize = SpGistGetInnerTypeSize(&state->attPrefixType, prefix);
995 : : else
4502 996 : 999 : prefixSize = 0;
997 : :
998 : 4265 : size = SGITHDRSZ + prefixSize;
999 : :
1000 : : /* Note: we rely on node tuple sizes to be maxaligned already */
1001 [ + + ]: 29638 : for (i = 0; i < nNodes; i++)
1002 : 25373 : size += IndexTupleSize(nodes[i]);
1003 : :
1004 : : /*
1005 : : * Ensure that we can replace the tuple with a dead tuple later. This
1006 : : * test is unnecessary given current tuple layouts, but let's be safe.
1007 : : */
1008 [ - + ]: 4265 : if (size < SGDTSIZE)
4502 tgl@sss.pgh.pa.us 1009 :UBC 0 : size = SGDTSIZE;
1010 : :
1011 : : /*
1012 : : * Inner tuple should be small enough to fit on a page
1013 : : */
4502 tgl@sss.pgh.pa.us 1014 [ - + ]:CBC 4265 : if (size > SPGIST_PAGE_CAPACITY - sizeof(ItemIdData))
4502 tgl@sss.pgh.pa.us 1015 [ # # ]:UBC 0 : ereport(ERROR,
1016 : : (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),
1017 : : errmsg("SP-GiST inner tuple size %zu exceeds maximum %zu",
1018 : : (Size) size,
1019 : : SPGIST_PAGE_CAPACITY - sizeof(ItemIdData)),
1020 : : errhint("Values larger than a buffer page cannot be indexed.")));
1021 : :
1022 : : /*
1023 : : * Check for overflow of header fields --- probably can't fail if the
1024 : : * above succeeded, but let's be paranoid
1025 : : */
4502 tgl@sss.pgh.pa.us 1026 [ + - + - ]:CBC 4265 : if (size > SGITMAXSIZE ||
1027 [ - + ]: 4265 : prefixSize > SGITMAXPREFIXSIZE ||
1028 : : nNodes > SGITMAXNNODES)
4502 tgl@sss.pgh.pa.us 1029 [ # # ]:UBC 0 : elog(ERROR, "SPGiST inner tuple header field is too small");
1030 : :
1031 : : /* OK, form the tuple */
4502 tgl@sss.pgh.pa.us 1032 :CBC 4265 : tup = (SpGistInnerTuple) palloc0(size);
1033 : :
1034 : 4265 : tup->nNodes = nNodes;
1035 : 4265 : tup->prefixSize = prefixSize;
1036 : 4265 : tup->size = size;
1037 : :
1038 [ + + ]: 4265 : if (hasPrefix)
1109 1039 [ + - ]: 3266 : memcpyInnerDatum(SGITDATAPTR(tup), &state->attPrefixType, prefix);
1040 : :
4502 1041 : 4265 : ptr = (char *) SGITNODEPTR(tup);
1042 : :
1043 [ + + ]: 29638 : for (i = 0; i < nNodes; i++)
1044 : : {
1045 : 25373 : SpGistNodeTuple node = nodes[i];
1046 : :
1047 : 25373 : memcpy(ptr, node, IndexTupleSize(node));
1048 : 25373 : ptr += IndexTupleSize(node);
1049 : : }
1050 : :
1051 : 4265 : return tup;
1052 : : }
1053 : :
1054 : : /*
1055 : : * Construct a "dead" tuple to replace a tuple being deleted.
1056 : : *
1057 : : * The state can be SPGIST_REDIRECT, SPGIST_DEAD, or SPGIST_PLACEHOLDER.
1058 : : * For a REDIRECT tuple, a pointer (blkno+offset) must be supplied, and
1059 : : * the xid field is filled in automatically.
1060 : : *
1061 : : * This is called in critical sections, so we don't use palloc; the tuple
1062 : : * is built in preallocated storage. It should be copied before another
1063 : : * call with different parameters can occur.
1064 : : */
1065 : : SpGistDeadTuple
1066 : 7296 : spgFormDeadTuple(SpGistState *state, int tupstate,
1067 : : BlockNumber blkno, OffsetNumber offnum)
1068 : : {
1069 : 7296 : SpGistDeadTuple tuple = (SpGistDeadTuple) state->deadTupleStorage;
1070 : :
1071 : 7296 : tuple->tupstate = tupstate;
1072 : 7296 : tuple->size = SGDTSIZE;
1105 1073 : 7296 : SGLT_SET_NEXTOFFSET(tuple, InvalidOffsetNumber);
1074 : :
4502 1075 [ + + ]: 7296 : if (tupstate == SPGIST_REDIRECT)
1076 : : {
1077 : 1206 : ItemPointerSet(&tuple->pointer, blkno, offnum);
4273 1078 [ - + ]: 1206 : Assert(TransactionIdIsValid(state->myXid));
4502 1079 : 1206 : tuple->xid = state->myXid;
1080 : : }
1081 : : else
1082 : : {
1083 : 6090 : ItemPointerSetInvalid(&tuple->pointer);
1084 : 6090 : tuple->xid = InvalidTransactionId;
1085 : : }
1086 : :
1087 : 7296 : return tuple;
1088 : : }
1089 : :
1090 : : /*
1091 : : * Convert an SPGiST leaf tuple into Datum/isnull arrays.
1092 : : *
1093 : : * The caller must allocate sufficient storage for the output arrays.
1094 : : * (INDEX_MAX_KEYS entries should be enough.)
1095 : : */
1096 : : void
1105 1097 : 30509 : spgDeformLeafTuple(SpGistLeafTuple tup, TupleDesc tupleDescriptor,
1098 : : Datum *datums, bool *isnulls, bool keyColumnIsNull)
1099 : : {
1100 : 30509 : bool hasNullsMask = SGLT_GET_HASNULLMASK(tup);
1101 : : char *tp; /* ptr to tuple data */
1102 : : bits8 *bp; /* ptr to null bitmap in tuple */
1103 : :
1104 [ - + - - ]: 30509 : if (keyColumnIsNull && tupleDescriptor->natts == 1)
1105 : : {
1106 : : /*
1107 : : * Trivial case: there is only the key attribute and we're in a nulls
1108 : : * tree. The hasNullsMask bit in the tuple header should not be set
1109 : : * (and thus we can't use index_deform_tuple_internal), but
1110 : : * nonetheless the result is NULL.
1111 : : *
1112 : : * Note: currently this is dead code, because noplace calls this when
1113 : : * there is only the key attribute. But we should cover the case.
1114 : : */
1105 tgl@sss.pgh.pa.us 1115 [ # # ]:UBC 0 : Assert(!hasNullsMask);
1116 : :
1117 : 0 : datums[spgKeyColumn] = (Datum) 0;
1118 : 0 : isnulls[spgKeyColumn] = true;
1119 : 0 : return;
1120 : : }
1121 : :
1105 tgl@sss.pgh.pa.us 1122 :CBC 30509 : tp = (char *) tup + SGLTHDRSZ(hasNullsMask);
1123 : 30509 : bp = (bits8 *) ((char *) tup + sizeof(SpGistLeafTupleData));
1124 : :
1125 : 30509 : index_deform_tuple_internal(tupleDescriptor,
1126 : : datums, isnulls,
1127 : : tp, bp, hasNullsMask);
1128 : :
1129 : : /*
1130 : : * Key column isnull value from the tuple should be consistent with
1131 : : * keyColumnIsNull flag from the caller.
1132 : : */
1133 [ - + ]: 30509 : Assert(keyColumnIsNull == isnulls[spgKeyColumn]);
1134 : : }
1135 : :
1136 : : /*
1137 : : * Extract the label datums of the nodes within innerTuple
1138 : : *
1139 : : * Returns NULL if label datums are NULLs
1140 : : */
1141 : : Datum *
4502 1142 : 9341749 : spgExtractNodeLabels(SpGistState *state, SpGistInnerTuple innerTuple)
1143 : : {
1144 : : Datum *nodeLabels;
1145 : : int i;
1146 : : SpGistNodeTuple node;
1147 : :
1148 : : /* Either all the labels must be NULL, or none. */
4246 heikki.linnakangas@i 1149 : 9341749 : node = SGITNODEPTR(innerTuple);
1150 [ + + ]: 9341749 : if (IndexTupleHasNulls(node))
1151 : : {
1152 [ + + ]: 50352126 : SGITITERATE(innerTuple, i, node)
1153 : : {
1154 [ - + ]: 41126783 : if (!IndexTupleHasNulls(node))
4246 heikki.linnakangas@i 1155 [ # # ]:UBC 0 : elog(ERROR, "some but not all node labels are null in SPGiST inner tuple");
1156 : : }
1157 : : /* They're all null, so just return NULL */
4502 tgl@sss.pgh.pa.us 1158 :CBC 9225343 : return NULL;
1159 : : }
1160 : : else
1161 : : {
4246 heikki.linnakangas@i 1162 : 116406 : nodeLabels = (Datum *) palloc(sizeof(Datum) * innerTuple->nNodes);
1163 [ + + ]: 1335863 : SGITITERATE(innerTuple, i, node)
1164 : : {
1165 [ - + ]: 1219457 : if (IndexTupleHasNulls(node))
4246 heikki.linnakangas@i 1166 [ # # ]:UBC 0 : elog(ERROR, "some but not all node labels are null in SPGiST inner tuple");
4246 heikki.linnakangas@i 1167 [ + - ]:CBC 1219457 : nodeLabels[i] = SGNTDATUM(node, state);
1168 : : }
1169 : 116406 : return nodeLabels;
1170 : : }
1171 : : }
1172 : :
1173 : : /*
1174 : : * Add a new item to the page, replacing a PLACEHOLDER item if possible.
1175 : : * Return the location it's inserted at, or InvalidOffsetNumber on failure.
1176 : : *
1177 : : * If startOffset isn't NULL, we start searching for placeholders at
1178 : : * *startOffset, and update that to the next place to search. This is just
1179 : : * an optimization for repeated insertions.
1180 : : *
1181 : : * If errorOK is false, we throw error when there's not enough room,
1182 : : * rather than returning InvalidOffsetNumber.
1183 : : */
1184 : : OffsetNumber
4502 tgl@sss.pgh.pa.us 1185 : 810676 : SpGistPageAddNewItem(SpGistState *state, Page page, Item item, Size size,
1186 : : OffsetNumber *startOffset, bool errorOK)
1187 : : {
1188 : 810676 : SpGistPageOpaque opaque = SpGistPageGetOpaque(page);
1189 : : OffsetNumber i,
1190 : : maxoff,
1191 : : offnum;
1192 : :
1193 [ + + ]: 810676 : if (opaque->nPlaceholder > 0 &&
1194 [ + - ]: 229986 : PageGetExactFreeSpace(page) + SGDTSIZE >= MAXALIGN(size))
1195 : : {
1196 : : /* Try to replace a placeholder */
1197 : 229986 : maxoff = PageGetMaxOffsetNumber(page);
1198 : 229986 : offnum = InvalidOffsetNumber;
1199 : :
1200 : : for (;;)
1201 : : {
1202 [ + + + + ]: 229986 : if (startOffset && *startOffset != InvalidOffsetNumber)
1203 : 57240 : i = *startOffset;
1204 : : else
1205 : 172746 : i = FirstOffsetNumber;
1206 [ + - ]: 15692571 : for (; i <= maxoff; i++)
1207 : : {
1208 : 15692571 : SpGistDeadTuple it = (SpGistDeadTuple) PageGetItem(page,
1209 : : PageGetItemId(page, i));
1210 : :
1211 [ + + ]: 15692571 : if (it->tupstate == SPGIST_PLACEHOLDER)
1212 : : {
1213 : 229986 : offnum = i;
1214 : 229986 : break;
1215 : : }
1216 : : }
1217 : :
1218 : : /* Done if we found a placeholder */
1219 [ + - ]: 229986 : if (offnum != InvalidOffsetNumber)
1220 : 229986 : break;
1221 : :
4502 tgl@sss.pgh.pa.us 1222 [ # # # # ]:UBC 0 : if (startOffset && *startOffset != InvalidOffsetNumber)
1223 : : {
1224 : : /* Hint was no good, re-search from beginning */
1225 : 0 : *startOffset = InvalidOffsetNumber;
1226 : 0 : continue;
1227 : : }
1228 : :
1229 : : /* Hmm, no placeholder found? */
1230 : 0 : opaque->nPlaceholder = 0;
1231 : 0 : break;
1232 : : }
1233 : :
4502 tgl@sss.pgh.pa.us 1234 [ + - ]:CBC 229986 : if (offnum != InvalidOffsetNumber)
1235 : : {
1236 : : /* Replace the placeholder tuple */
1237 : 229986 : PageIndexTupleDelete(page, offnum);
1238 : :
1239 : 229986 : offnum = PageAddItem(page, item, size, offnum, false, false);
1240 : :
1241 : : /*
1242 : : * We should not have failed given the size check at the top of
1243 : : * the function, but test anyway. If we did fail, we must PANIC
1244 : : * because we've already deleted the placeholder tuple, and
1245 : : * there's no other way to keep the damage from getting to disk.
1246 : : */
1247 [ + - ]: 229986 : if (offnum != InvalidOffsetNumber)
1248 : : {
1249 [ - + ]: 229986 : Assert(opaque->nPlaceholder > 0);
1250 : 229986 : opaque->nPlaceholder--;
1251 [ + + ]: 229986 : if (startOffset)
1252 : 58552 : *startOffset = offnum + 1;
1253 : : }
1254 : : else
980 peter@eisentraut.org 1255 [ # # ]:UBC 0 : elog(PANIC, "failed to add item of size %zu to SPGiST index page",
1256 : : size);
1257 : :
4502 tgl@sss.pgh.pa.us 1258 :CBC 229986 : return offnum;
1259 : : }
1260 : : }
1261 : :
1262 : : /* No luck in replacing a placeholder, so just add it to the page */
1263 : 580690 : offnum = PageAddItem(page, item, size,
1264 : : InvalidOffsetNumber, false, false);
1265 : :
1266 [ - + - - ]: 580690 : if (offnum == InvalidOffsetNumber && !errorOK)
980 peter@eisentraut.org 1267 [ # # ]:UBC 0 : elog(ERROR, "failed to add item of size %zu to SPGiST index page",
1268 : : size);
1269 : :
4502 tgl@sss.pgh.pa.us 1270 :CBC 580690 : return offnum;
1271 : : }
1272 : :
1273 : : /*
1274 : : * spgproperty() -- Check boolean properties of indexes.
1275 : : *
1276 : : * This is optional for most AMs, but is required for SP-GiST because the core
1277 : : * property code doesn't support AMPROP_DISTANCE_ORDERABLE.
1278 : : */
1279 : : bool
2034 akorotkov@postgresql 1280 : 93 : spgproperty(Oid index_oid, int attno,
1281 : : IndexAMProperty prop, const char *propname,
1282 : : bool *res, bool *isnull)
1283 : : {
1284 : : Oid opclass,
1285 : : opfamily,
1286 : : opcintype;
1287 : : CatCList *catlist;
1288 : : int i;
1289 : :
1290 : : /* Only answer column-level inquiries */
1291 [ + + ]: 93 : if (attno == 0)
1292 : 33 : return false;
1293 : :
1294 [ + + ]: 60 : switch (prop)
1295 : : {
1296 : 6 : case AMPROP_DISTANCE_ORDERABLE:
1297 : 6 : break;
1298 : 54 : default:
1299 : 54 : return false;
1300 : : }
1301 : :
1302 : : /*
1303 : : * Currently, SP-GiST distance-ordered scans require that there be a
1304 : : * distance operator in the opclass with the default types. So we assume
1305 : : * that if such an operator exists, then there's a reason for it.
1306 : : */
1307 : :
1308 : : /* First we need to know the column's opclass. */
1309 : 6 : opclass = get_index_column_opclass(index_oid, attno);
1310 [ - + ]: 6 : if (!OidIsValid(opclass))
1311 : : {
2034 akorotkov@postgresql 1312 :UBC 0 : *isnull = true;
1313 : 0 : return true;
1314 : : }
1315 : :
1316 : : /* Now look up the opclass family and input datatype. */
2034 akorotkov@postgresql 1317 [ - + ]:CBC 6 : if (!get_opclass_opfamily_and_input_type(opclass, &opfamily, &opcintype))
1318 : : {
2034 akorotkov@postgresql 1319 :UBC 0 : *isnull = true;
1320 : 0 : return true;
1321 : : }
1322 : :
1323 : : /* And now we can check whether the operator is provided. */
2034 akorotkov@postgresql 1324 :CBC 6 : catlist = SearchSysCacheList1(AMOPSTRATEGY,
1325 : : ObjectIdGetDatum(opfamily));
1326 : :
1327 : 6 : *res = false;
1328 : :
1329 [ + + ]: 51 : for (i = 0; i < catlist->n_members; i++)
1330 : : {
1331 : 48 : HeapTuple amoptup = &catlist->members[i]->tuple;
1332 : 48 : Form_pg_amop amopform = (Form_pg_amop) GETSTRUCT(amoptup);
1333 : :
1334 [ + + ]: 48 : if (amopform->amoppurpose == AMOP_ORDER &&
1335 [ - + ]: 3 : (amopform->amoplefttype == opcintype ||
1336 [ - - + - ]: 3 : amopform->amoprighttype == opcintype) &&
1337 : 3 : opfamily_can_sort_type(amopform->amopsortfamily,
1338 : : get_op_rettype(amopform->amopopr)))
1339 : : {
1340 : 3 : *res = true;
1341 : 3 : break;
1342 : : }
1343 : : }
1344 : :
1345 : 6 : ReleaseSysCacheList(catlist);
1346 : :
1347 : 6 : *isnull = false;
1348 : :
1349 : 6 : return true;
1350 : : }
|
