Debian Codegraph @

src/backend/executor/execIndexing.c

raw
1 /*-------------------------------------------------------------------------
2 *
3 * execIndexing.c
4 * routines for inserting index tuples and enforcing unique and
5 * exclusion constraints.
6 *
7 * ExecInsertIndexTuples() is the main entry point. It's called after
8 * inserting a tuple to the heap, and it inserts corresponding index tuples
9 * into all indexes. At the same time, it enforces any unique and
10 * exclusion constraints:
11 *
12 * Unique Indexes
13 * --------------
14 *
15 * Enforcing a unique constraint is straightforward. When the index AM
16 * inserts the tuple to the index, it also checks that there are no
17 * conflicting tuples in the index already. It does so atomically, so that
18 * even if two backends try to insert the same key concurrently, only one
19 * of them will succeed. All the logic to ensure atomicity, and to wait
20 * for in-progress transactions to finish, is handled by the index AM.
21 *
22 * If a unique constraint is deferred, we request the index AM to not
23 * throw an error if a conflict is found. Instead, we make note that there
24 * was a conflict and return the list of indexes with conflicts to the
25 * caller. The caller must re-check them later, by calling index_insert()
26 * with the UNIQUE_CHECK_EXISTING option.
27 *
28 * Exclusion Constraints
29 * ---------------------
30 *
31 * Exclusion constraints are different from unique indexes in that when the
32 * tuple is inserted to the index, the index AM does not check for
33 * duplicate keys at the same time. After the insertion, we perform a
34 * separate scan on the index to check for conflicting tuples, and if one
35 * is found, we throw an error and the transaction is aborted. If the
36 * conflicting tuple's inserter or deleter is in-progress, we wait for it
37 * to finish first.
38 *
39 * There is a chance of deadlock, if two backends insert a tuple at the
40 * same time, and then perform the scan to check for conflicts. They will
41 * find each other's tuple, and both try to wait for each other. The
42 * deadlock detector will detect that, and abort one of the transactions.
43 * That's fairly harmless, as one of them was bound to abort with a
44 * "duplicate key error" anyway, although you get a different error
45 * message.
46 *
47 * If an exclusion constraint is deferred, we still perform the conflict
48 * checking scan immediately after inserting the index tuple. But instead
49 * of throwing an error if a conflict is found, we return that information
50 * to the caller. The caller must re-check them later by calling
51 * check_exclusion_constraint().
52 *
53 * Speculative insertion
54 * ---------------------
55 *
56 * Speculative insertion is a two-phase mechanism used to implement
57 * INSERT ... ON CONFLICT DO UPDATE/NOTHING. The tuple is first inserted
58 * to the heap and update the indexes as usual, but if a constraint is
59 * violated, we can still back out the insertion without aborting the whole
60 * transaction. In an INSERT ... ON CONFLICT statement, if a conflict is
61 * detected, the inserted tuple is backed out and the ON CONFLICT action is
62 * executed instead.
63 *
64 * Insertion to a unique index works as usual: the index AM checks for
65 * duplicate keys atomically with the insertion. But instead of throwing
66 * an error on a conflict, the speculatively inserted heap tuple is backed
67 * out.
68 *
69 * Exclusion constraints are slightly more complicated. As mentioned
70 * earlier, there is a risk of deadlock when two backends insert the same
71 * key concurrently. That was not a problem for regular insertions, when
72 * one of the transactions has to be aborted anyway, but with a speculative
73 * insertion we cannot let a deadlock happen, because we only want to back
74 * out the speculatively inserted tuple on conflict, not abort the whole
75 * transaction.
76 *
77 * When a backend detects that the speculative insertion conflicts with
78 * another in-progress tuple, it has two options:
79 *
80 * 1. back out the speculatively inserted tuple, then wait for the other
81 * transaction, and retry. Or,
82 * 2. wait for the other transaction, with the speculatively inserted tuple
83 * still in place.
84 *
85 * If two backends insert at the same time, and both try to wait for each
86 * other, they will deadlock. So option 2 is not acceptable. Option 1
87 * avoids the deadlock, but it is prone to a livelock instead. Both
88 * transactions will wake up immediately as the other transaction backs
89 * out. Then they both retry, and conflict with each other again, lather,
90 * rinse, repeat.
91 *
92 * To avoid the livelock, one of the backends must back out first, and then
93 * wait, while the other one waits without backing out. It doesn't matter
94 * which one backs out, so we employ an arbitrary rule that the transaction
95 * with the higher XID backs out.
96 *
97 *
98 * Portions Copyright (c) 1996-2025, PostgreSQL Global Development Group
99 * Portions Copyright (c) 1994, Regents of the University of California
100 *
101 *
102 * IDENTIFICATION
103 * src/backend/executor/execIndexing.c
104 *
105 *-------------------------------------------------------------------------
106 */
107 #include "postgres.h"
108
109 #include "access/genam.h"
110 #include "access/relscan.h"
111 #include "access/tableam.h"
112 #include "access/xact.h"
113 #include "catalog/index.h"
114 #include "executor/executor.h"
115 #include "nodes/nodeFuncs.h"
116 #include "storage/lmgr.h"
117 #include "utils/lsyscache.h"
118 #include "utils/multirangetypes.h"
119 #include "utils/rangetypes.h"
120 #include "utils/snapmgr.h"
121
122 /* waitMode argument to check_exclusion_or_unique_constraint() */
123 typedef enum
124 {
125 CEOUC_WAIT,
126 CEOUC_NOWAIT,
127 CEOUC_LIVELOCK_PREVENTING_WAIT,
128 } CEOUC_WAIT_MODE;
129
130 static bool check_exclusion_or_unique_constraint(Relation heap, Relation index,
131 IndexInfo *indexInfo,
132 ItemPointer tupleid,
133 const Datum *values, const bool *isnull,
134 EState *estate, bool newIndex,
135 CEOUC_WAIT_MODE waitMode,
136 bool violationOK,
137 ItemPointer conflictTid);
138
139 static bool index_recheck_constraint(Relation index, const Oid *constr_procs,
140 const Datum *existing_values, const bool *existing_isnull,
141 const Datum *new_values);
142 static bool index_unchanged_by_update(ResultRelInfo *resultRelInfo,
143 EState *estate, IndexInfo *indexInfo,
144 Relation indexRelation);
145 static bool index_expression_changed_walker(Node *node,
146 Bitmapset *allUpdatedCols);
147 static void ExecWithoutOverlapsNotEmpty(Relation rel, NameData attname, Datum attval,
148 char typtype, Oid atttypid);
149
150 /* ----------------------------------------------------------------
151 * ExecOpenIndices
152 *
153 * Find the indices associated with a result relation, open them,
154 * and save information about them in the result ResultRelInfo.
155 *
156 * At entry, caller has already opened and locked
157 * resultRelInfo->ri_RelationDesc.
158 * ----------------------------------------------------------------
159 */
160 void
161 ExecOpenIndices(ResultRelInfo *resultRelInfo, bool speculative)
162 {
163 Relation resultRelation = resultRelInfo->ri_RelationDesc;
164 List *indexoidlist;
165 ListCell *l;
166 int len,
167 i;
168 RelationPtr relationDescs;
169 IndexInfo **indexInfoArray;
170
171 resultRelInfo->ri_NumIndices = 0;
172
173 /* fast path if no indexes */
174 if (!RelationGetForm(resultRelation)->relhasindex)
175 return;
176
177 /*
178 * Get cached list of index OIDs
179 */
180 indexoidlist = RelationGetIndexList(resultRelation);
181 len = list_length(indexoidlist);
182 if (len == 0)
183 return;
184
185 /* This Assert will fail if ExecOpenIndices is called twice */
186 Assert(resultRelInfo->ri_IndexRelationDescs == NULL);
187
188 /*
189 * allocate space for result arrays
190 */
191 relationDescs = (RelationPtr) palloc(len * sizeof(Relation));
192 indexInfoArray = (IndexInfo **) palloc(len * sizeof(IndexInfo *));
193
194 resultRelInfo->ri_NumIndices = len;
195 resultRelInfo->ri_IndexRelationDescs = relationDescs;
196 resultRelInfo->ri_IndexRelationInfo = indexInfoArray;
197
198 /*
199 * For each index, open the index relation and save pg_index info. We
200 * acquire RowExclusiveLock, signifying we will update the index.
201 *
202 * Note: we do this even if the index is not indisready; it's not worth
203 * the trouble to optimize for the case where it isn't.
204 */
205 i = 0;
206 foreach(l, indexoidlist)
207 {
208 Oid indexOid = lfirst_oid(l);
209 Relation indexDesc;
210 IndexInfo *ii;
211
212 indexDesc = index_open(indexOid, RowExclusiveLock);
213
214 /* extract index key information from the index's pg_index info */
215 ii = BuildIndexInfo(indexDesc);
216
217 /*
218 * If the indexes are to be used for speculative insertion, add extra
219 * information required by unique index entries.
220 */
221 if (speculative && ii->ii_Unique && !indexDesc->rd_index->indisexclusion)
222 BuildSpeculativeIndexInfo(indexDesc, ii);
223
224 relationDescs[i] = indexDesc;
225 indexInfoArray[i] = ii;
226 i++;
227 }
228
229 list_free(indexoidlist);
230 }
231
232 /* ----------------------------------------------------------------
233 * ExecCloseIndices
234 *
235 * Close the index relations stored in resultRelInfo
236 * ----------------------------------------------------------------
237 */
238 void
239 ExecCloseIndices(ResultRelInfo *resultRelInfo)
240 {
241 int i;
242 int numIndices;
243 RelationPtr indexDescs;
244 IndexInfo **indexInfos;
245
246 numIndices = resultRelInfo->ri_NumIndices;
247 indexDescs = resultRelInfo->ri_IndexRelationDescs;
248 indexInfos = resultRelInfo->ri_IndexRelationInfo;
249
250 for (i = 0; i < numIndices; i++)
251 {
252 /* This Assert will fail if ExecCloseIndices is called twice */
253 Assert(indexDescs[i] != NULL);
254
255 /* Give the index a chance to do some post-insert cleanup */
256 index_insert_cleanup(indexDescs[i], indexInfos[i]);
257
258 /* Drop lock acquired by ExecOpenIndices */
259 index_close(indexDescs[i], RowExclusiveLock);
260
261 /* Mark the index as closed */
262 indexDescs[i] = NULL;
263 }
264
265 /*
266 * We don't attempt to free the IndexInfo data structures or the arrays,
267 * instead assuming that such stuff will be cleaned up automatically in
268 * FreeExecutorState.
269 */
270 }
271
272 /* ----------------------------------------------------------------
273 * ExecInsertIndexTuples
274 *
275 * This routine takes care of inserting index tuples
276 * into all the relations indexing the result relation
277 * when a heap tuple is inserted into the result relation.
278 *
279 * When 'update' is true and 'onlySummarizing' is false,
280 * executor is performing an UPDATE that could not use an
281 * optimization like heapam's HOT (in more general terms a
282 * call to table_tuple_update() took place and set
283 * 'update_indexes' to TU_All). Receiving this hint makes
284 * us consider if we should pass down the 'indexUnchanged'
285 * hint in turn. That's something that we figure out for
286 * each index_insert() call iff 'update' is true.
287 * (When 'update' is false we already know not to pass the
288 * hint to any index.)
289 *
290 * If onlySummarizing is set, an equivalent optimization to
291 * HOT has been applied and any updated columns are indexed
292 * only by summarizing indexes (or in more general terms a
293 * call to table_tuple_update() took place and set
294 * 'update_indexes' to TU_Summarizing). We can (and must)
295 * therefore only update the indexes that have
296 * 'amsummarizing' = true.
297 *
298 * Unique and exclusion constraints are enforced at the same
299 * time. This returns a list of index OIDs for any unique or
300 * exclusion constraints that are deferred and that had
301 * potential (unconfirmed) conflicts. (if noDupErr == true,
302 * the same is done for non-deferred constraints, but report
303 * if conflict was speculative or deferred conflict to caller)
304 *
305 * If 'arbiterIndexes' is nonempty, noDupErr applies only to
306 * those indexes. NIL means noDupErr applies to all indexes.
307 * ----------------------------------------------------------------
308 */
309 List *
310 ExecInsertIndexTuples(ResultRelInfo *resultRelInfo,
311 TupleTableSlot *slot,
312 EState *estate,
313 bool update,
314 bool noDupErr,
315 bool *specConflict,
316 List *arbiterIndexes,
317 bool onlySummarizing)
318 {
319 ItemPointer tupleid = &slot->tts_tid;
320 List *result = NIL;
321 int i;
322 int numIndices;
323 RelationPtr relationDescs;
324 Relation heapRelation;
325 IndexInfo **indexInfoArray;
326 ExprContext *econtext;
327 Datum values[INDEX_MAX_KEYS];
328 bool isnull[INDEX_MAX_KEYS];
329
330 Assert(ItemPointerIsValid(tupleid));
331
332 /*
333 * Get information from the result relation info structure.
334 */
335 numIndices = resultRelInfo->ri_NumIndices;
336 relationDescs = resultRelInfo->ri_IndexRelationDescs;
337 indexInfoArray = resultRelInfo->ri_IndexRelationInfo;
338 heapRelation = resultRelInfo->ri_RelationDesc;
339
340 /* Sanity check: slot must belong to the same rel as the resultRelInfo. */
341 Assert(slot->tts_tableOid == RelationGetRelid(heapRelation));
342
343 /*
344 * We will use the EState's per-tuple context for evaluating predicates
345 * and index expressions (creating it if it's not already there).
346 */
347 econtext = GetPerTupleExprContext(estate);
348
349 /* Arrange for econtext's scan tuple to be the tuple under test */
350 econtext->ecxt_scantuple = slot;
351
352 /*
353 * for each index, form and insert the index tuple
354 */
355 for (i = 0; i < numIndices; i++)
356 {
357 Relation indexRelation = relationDescs[i];
358 IndexInfo *indexInfo;
359 bool applyNoDupErr;
360 IndexUniqueCheck checkUnique;
361 bool indexUnchanged;
362 bool satisfiesConstraint;
363
364 if (indexRelation == NULL)
365 continue;
366
367 indexInfo = indexInfoArray[i];
368
369 /* If the index is marked as read-only, ignore it */
370 if (!indexInfo->ii_ReadyForInserts)
371 continue;
372
373 /*
374 * Skip processing of non-summarizing indexes if we only update
375 * summarizing indexes
376 */
377 if (onlySummarizing && !indexInfo->ii_Summarizing)
378 continue;
379
380 /* Check for partial index */
381 if (indexInfo->ii_Predicate != NIL)
382 {
383 ExprState *predicate;
384
385 /*
386 * If predicate state not set up yet, create it (in the estate's
387 * per-query context)
388 */
389 predicate = indexInfo->ii_PredicateState;
390 if (predicate == NULL)
391 {
392 predicate = ExecPrepareQual(indexInfo->ii_Predicate, estate);
393 indexInfo->ii_PredicateState = predicate;
394 }
395
396 /* Skip this index-update if the predicate isn't satisfied */
397 if (!ExecQual(predicate, econtext))
398 continue;
399 }
400
401 /*
402 * FormIndexDatum fills in its values and isnull parameters with the
403 * appropriate values for the column(s) of the index.
404 */
405 FormIndexDatum(indexInfo,
406 slot,
407 estate,
408 values,
409 isnull);
410
411 /* Check whether to apply noDupErr to this index */
412 applyNoDupErr = noDupErr &&
413 (arbiterIndexes == NIL ||
414 list_member_oid(arbiterIndexes,
415 indexRelation->rd_index->indexrelid));
416
417 /*
418 * The index AM does the actual insertion, plus uniqueness checking.
419 *
420 * For an immediate-mode unique index, we just tell the index AM to
421 * throw error if not unique.
422 *
423 * For a deferrable unique index, we tell the index AM to just detect
424 * possible non-uniqueness, and we add the index OID to the result
425 * list if further checking is needed.
426 *
427 * For a speculative insertion (used by INSERT ... ON CONFLICT), do
428 * the same as for a deferrable unique index.
429 */
430 if (!indexRelation->rd_index->indisunique)
431 checkUnique = UNIQUE_CHECK_NO;
432 else if (applyNoDupErr)
433 checkUnique = UNIQUE_CHECK_PARTIAL;
434 else if (indexRelation->rd_index->indimmediate)
435 checkUnique = UNIQUE_CHECK_YES;
436 else
437 checkUnique = UNIQUE_CHECK_PARTIAL;
438
439 /*
440 * There's definitely going to be an index_insert() call for this
441 * index. If we're being called as part of an UPDATE statement,
442 * consider if the 'indexUnchanged' = true hint should be passed.
443 */
444 indexUnchanged = update && index_unchanged_by_update(resultRelInfo,
445 estate,
446 indexInfo,
447 indexRelation);
448
449 satisfiesConstraint =
450 index_insert(indexRelation, /* index relation */
451 values, /* array of index Datums */
452 isnull, /* null flags */
453 tupleid, /* tid of heap tuple */
454 heapRelation, /* heap relation */
455 checkUnique, /* type of uniqueness check to do */
456 indexUnchanged, /* UPDATE without logical change? */
457 indexInfo); /* index AM may need this */
458
459 /*
460 * If the index has an associated exclusion constraint, check that.
461 * This is simpler than the process for uniqueness checks since we
462 * always insert first and then check. If the constraint is deferred,
463 * we check now anyway, but don't throw error on violation or wait for
464 * a conclusive outcome from a concurrent insertion; instead we'll
465 * queue a recheck event. Similarly, noDupErr callers (speculative
466 * inserters) will recheck later, and wait for a conclusive outcome
467 * then.
468 *
469 * An index for an exclusion constraint can't also be UNIQUE (not an
470 * essential property, we just don't allow it in the grammar), so no
471 * need to preserve the prior state of satisfiesConstraint.
472 */
473 if (indexInfo->ii_ExclusionOps != NULL)
474 {
475 bool violationOK;
476 CEOUC_WAIT_MODE waitMode;
477
478 if (applyNoDupErr)
479 {
480 violationOK = true;
481 waitMode = CEOUC_LIVELOCK_PREVENTING_WAIT;
482 }
483 else if (!indexRelation->rd_index->indimmediate)
484 {
485 violationOK = true;
486 waitMode = CEOUC_NOWAIT;
487 }
488 else
489 {
490 violationOK = false;
491 waitMode = CEOUC_WAIT;
492 }
493
494 satisfiesConstraint =
495 check_exclusion_or_unique_constraint(heapRelation,
496 indexRelation, indexInfo,
497 tupleid, values, isnull,
498 estate, false,
499 waitMode, violationOK, NULL);
500 }
501
502 if ((checkUnique == UNIQUE_CHECK_PARTIAL ||
503 indexInfo->ii_ExclusionOps != NULL) &&
504 !satisfiesConstraint)
505 {
506 /*
507 * The tuple potentially violates the uniqueness or exclusion
508 * constraint, so make a note of the index so that we can re-check
509 * it later. Speculative inserters are told if there was a
510 * speculative conflict, since that always requires a restart.
511 */
512 result = lappend_oid(result, RelationGetRelid(indexRelation));
513 if (indexRelation->rd_index->indimmediate && specConflict)
514 *specConflict = true;
515 }
516 }
517
518 return result;
519 }
520
521 /* ----------------------------------------------------------------
522 * ExecCheckIndexConstraints
523 *
524 * This routine checks if a tuple violates any unique or
525 * exclusion constraints. Returns true if there is no conflict.
526 * Otherwise returns false, and the TID of the conflicting
527 * tuple is returned in *conflictTid.
528 *
529 * If 'arbiterIndexes' is given, only those indexes are checked.
530 * NIL means all indexes.
531 *
532 * Note that this doesn't lock the values in any way, so it's
533 * possible that a conflicting tuple is inserted immediately
534 * after this returns. This can be used for either a pre-check
535 * before insertion or a re-check after finding a conflict.
536 *
537 * 'tupleid' should be the TID of the tuple that has been recently
538 * inserted (or can be invalid if we haven't inserted a new tuple yet).
539 * This tuple will be excluded from conflict checking.
540 * ----------------------------------------------------------------
541 */
542 bool
543 ExecCheckIndexConstraints(ResultRelInfo *resultRelInfo, TupleTableSlot *slot,
544 EState *estate, ItemPointer conflictTid,
545 ItemPointer tupleid, List *arbiterIndexes)
546 {
547 int i;
548 int numIndices;
549 RelationPtr relationDescs;
550 Relation heapRelation;
551 IndexInfo **indexInfoArray;
552 ExprContext *econtext;
553 Datum values[INDEX_MAX_KEYS];
554 bool isnull[INDEX_MAX_KEYS];
555 ItemPointerData invalidItemPtr;
556 bool checkedIndex = false;
557
558 ItemPointerSetInvalid(conflictTid);
559 ItemPointerSetInvalid(&invalidItemPtr);
560
561 /*
562 * Get information from the result relation info structure.
563 */
564 numIndices = resultRelInfo->ri_NumIndices;
565 relationDescs = resultRelInfo->ri_IndexRelationDescs;
566 indexInfoArray = resultRelInfo->ri_IndexRelationInfo;
567 heapRelation = resultRelInfo->ri_RelationDesc;
568
569 /*
570 * We will use the EState's per-tuple context for evaluating predicates
571 * and index expressions (creating it if it's not already there).
572 */
573 econtext = GetPerTupleExprContext(estate);
574
575 /* Arrange for econtext's scan tuple to be the tuple under test */
576 econtext->ecxt_scantuple = slot;
577
578 /*
579 * For each index, form index tuple and check if it satisfies the
580 * constraint.
581 */
582 for (i = 0; i < numIndices; i++)
583 {
584 Relation indexRelation = relationDescs[i];
585 IndexInfo *indexInfo;
586 bool satisfiesConstraint;
587
588 if (indexRelation == NULL)
589 continue;
590
591 indexInfo = indexInfoArray[i];
592
593 if (!indexInfo->ii_Unique && !indexInfo->ii_ExclusionOps)
594 continue;
595
596 /* If the index is marked as read-only, ignore it */
597 if (!indexInfo->ii_ReadyForInserts)
598 continue;
599
600 /* When specific arbiter indexes requested, only examine them */
601 if (arbiterIndexes != NIL &&
602 !list_member_oid(arbiterIndexes,
603 indexRelation->rd_index->indexrelid))
604 continue;
605
606 if (!indexRelation->rd_index->indimmediate)
607 ereport(ERROR,
608 (errcode(ERRCODE_OBJECT_NOT_IN_PREREQUISITE_STATE),
609 errmsg("ON CONFLICT does not support deferrable unique constraints/exclusion constraints as arbiters"),
610 errtableconstraint(heapRelation,
611 RelationGetRelationName(indexRelation))));
612
613 checkedIndex = true;
614
615 /* Check for partial index */
616 if (indexInfo->ii_Predicate != NIL)
617 {
618 ExprState *predicate;
619
620 /*
621 * If predicate state not set up yet, create it (in the estate's
622 * per-query context)
623 */
624 predicate = indexInfo->ii_PredicateState;
625 if (predicate == NULL)
626 {
627 predicate = ExecPrepareQual(indexInfo->ii_Predicate, estate);
628 indexInfo->ii_PredicateState = predicate;
629 }
630
631 /* Skip this index-update if the predicate isn't satisfied */
632 if (!ExecQual(predicate, econtext))
633 continue;
634 }
635
636 /*
637 * FormIndexDatum fills in its values and isnull parameters with the
638 * appropriate values for the column(s) of the index.
639 */
640 FormIndexDatum(indexInfo,
641 slot,
642 estate,
643 values,
644 isnull);
645
646 satisfiesConstraint =
647 check_exclusion_or_unique_constraint(heapRelation, indexRelation,
648 indexInfo, tupleid,
649 values, isnull, estate, false,
650 CEOUC_WAIT, true,
651 conflictTid);
652 if (!satisfiesConstraint)
653 return false;
654 }
655
656 if (arbiterIndexes != NIL && !checkedIndex)
657 elog(ERROR, "unexpected failure to find arbiter index");
658
659 return true;
660 }
661
662 /*
663 * Check for violation of an exclusion or unique constraint
664 *
665 * heap: the table containing the new tuple
666 * index: the index supporting the constraint
667 * indexInfo: info about the index, including the exclusion properties
668 * tupleid: heap TID of the new tuple we have just inserted (invalid if we
669 * haven't inserted a new tuple yet)
670 * values, isnull: the *index* column values computed for the new tuple
671 * estate: an EState we can do evaluation in
672 * newIndex: if true, we are trying to build a new index (this affects
673 * only the wording of error messages)
674 * waitMode: whether to wait for concurrent inserters/deleters
675 * violationOK: if true, don't throw error for violation
676 * conflictTid: if not-NULL, the TID of the conflicting tuple is returned here
677 *
678 * Returns true if OK, false if actual or potential violation
679 *
680 * 'waitMode' determines what happens if a conflict is detected with a tuple
681 * that was inserted or deleted by a transaction that's still running.
682 * CEOUC_WAIT means that we wait for the transaction to commit, before
683 * throwing an error or returning. CEOUC_NOWAIT means that we report the
684 * violation immediately; so the violation is only potential, and the caller
685 * must recheck sometime later. This behavior is convenient for deferred
686 * exclusion checks; we need not bother queuing a deferred event if there is
687 * definitely no conflict at insertion time.
688 *
689 * CEOUC_LIVELOCK_PREVENTING_WAIT is like CEOUC_NOWAIT, but we will sometimes
690 * wait anyway, to prevent livelocking if two transactions try inserting at
691 * the same time. This is used with speculative insertions, for INSERT ON
692 * CONFLICT statements. (See notes in file header)
693 *
694 * If violationOK is true, we just report the potential or actual violation to
695 * the caller by returning 'false'. Otherwise we throw a descriptive error
696 * message here. When violationOK is false, a false result is impossible.
697 *
698 * Note: The indexam is normally responsible for checking unique constraints,
699 * so this normally only needs to be used for exclusion constraints. But this
700 * function is also called when doing a "pre-check" for conflicts on a unique
701 * constraint, when doing speculative insertion. Caller may use the returned
702 * conflict TID to take further steps.
703 */
704 static bool
705 check_exclusion_or_unique_constraint(Relation heap, Relation index,
706 IndexInfo *indexInfo,
707 ItemPointer tupleid,
708 const Datum *values, const bool *isnull,
709 EState *estate, bool newIndex,
710 CEOUC_WAIT_MODE waitMode,
711 bool violationOK,
712 ItemPointer conflictTid)
713 {
714 Oid *constr_procs;
715 uint16 *constr_strats;
716 Oid *index_collations = index->rd_indcollation;
717 int indnkeyatts = IndexRelationGetNumberOfKeyAttributes(index);
718 IndexScanDesc index_scan;
719 ScanKeyData scankeys[INDEX_MAX_KEYS];
720 SnapshotData DirtySnapshot;
721 int i;
722 bool conflict;
723 bool found_self;
724 ExprContext *econtext;
725 TupleTableSlot *existing_slot;
726 TupleTableSlot *save_scantuple;
727
728 if (indexInfo->ii_ExclusionOps)
729 {
730 constr_procs = indexInfo->ii_ExclusionProcs;
731 constr_strats = indexInfo->ii_ExclusionStrats;
732 }
733 else
734 {
735 constr_procs = indexInfo->ii_UniqueProcs;
736 constr_strats = indexInfo->ii_UniqueStrats;
737 }
738
739 /*
740 * If this is a WITHOUT OVERLAPS constraint, we must also forbid empty
741 * ranges/multiranges. This must happen before we look for NULLs below, or
742 * a UNIQUE constraint could insert an empty range along with a NULL
743 * scalar part.
744 */
745 if (indexInfo->ii_WithoutOverlaps)
746 {
747 /*
748 * Look up the type from the heap tuple, but check the Datum from the
749 * index tuple.
750 */
751 AttrNumber attno = indexInfo->ii_IndexAttrNumbers[indnkeyatts - 1];
752
753 if (!isnull[indnkeyatts - 1])
754 {
755 TupleDesc tupdesc = RelationGetDescr(heap);
756 Form_pg_attribute att = TupleDescAttr(tupdesc, attno - 1);
757 TypeCacheEntry *typcache = lookup_type_cache(att->atttypid,
758 TYPECACHE_DOMAIN_BASE_INFO);
759 char typtype;
760
761 if (OidIsValid(typcache->domainBaseType))
762 typtype = get_typtype(typcache->domainBaseType);
763 else
764 typtype = typcache->typtype;
765
766 ExecWithoutOverlapsNotEmpty(heap, att->attname,
767 values[indnkeyatts - 1],
768 typtype, att->atttypid);
769 }
770 }
771
772 /*
773 * If any of the input values are NULL, and the index uses the default
774 * nulls-are-distinct mode, the constraint check is assumed to pass (i.e.,
775 * we assume the operators are strict). Otherwise, we interpret the
776 * constraint as specifying IS NULL for each column whose input value is
777 * NULL.
778 */
779 if (!indexInfo->ii_NullsNotDistinct)
780 {
781 for (i = 0; i < indnkeyatts; i++)
782 {
783 if (isnull[i])
784 return true;
785 }
786 }
787
788 /*
789 * Search the tuples that are in the index for any violations, including
790 * tuples that aren't visible yet.
791 */
792 InitDirtySnapshot(DirtySnapshot);
793
794 for (i = 0; i < indnkeyatts; i++)
795 {
796 ScanKeyEntryInitialize(&scankeys[i],
797 isnull[i] ? SK_ISNULL | SK_SEARCHNULL : 0,
798 i + 1,
799 constr_strats[i],
800 InvalidOid,
801 index_collations[i],
802 constr_procs[i],
803 values[i]);
804 }
805
806 /*
807 * Need a TupleTableSlot to put existing tuples in.
808 *
809 * To use FormIndexDatum, we have to make the econtext's scantuple point
810 * to this slot. Be sure to save and restore caller's value for
811 * scantuple.
812 */
813 existing_slot = table_slot_create(heap, NULL);
814
815 econtext = GetPerTupleExprContext(estate);
816 save_scantuple = econtext->ecxt_scantuple;
817 econtext->ecxt_scantuple = existing_slot;
818
819 /*
820 * May have to restart scan from this point if a potential conflict is
821 * found.
822 */
823 retry:
824 conflict = false;
825 found_self = false;
826 index_scan = index_beginscan(heap, index, &DirtySnapshot, NULL, indnkeyatts, 0);
827 index_rescan(index_scan, scankeys, indnkeyatts, NULL, 0);
828
829 while (index_getnext_slot(index_scan, ForwardScanDirection, existing_slot))
830 {
831 TransactionId xwait;
832 XLTW_Oper reason_wait;
833 Datum existing_values[INDEX_MAX_KEYS];
834 bool existing_isnull[INDEX_MAX_KEYS];
835 char *error_new;
836 char *error_existing;
837
838 /*
839 * Ignore the entry for the tuple we're trying to check.
840 */
841 if (ItemPointerIsValid(tupleid) &&
842 ItemPointerEquals(tupleid, &existing_slot->tts_tid))
843 {
844 if (found_self) /* should not happen */
845 elog(ERROR, "found self tuple multiple times in index \"%s\"",
846 RelationGetRelationName(index));
847 found_self = true;
848 continue;
849 }
850
851 /*
852 * Extract the index column values and isnull flags from the existing
853 * tuple.
854 */
855 FormIndexDatum(indexInfo, existing_slot, estate,
856 existing_values, existing_isnull);
857
858 /* If lossy indexscan, must recheck the condition */
859 if (index_scan->xs_recheck)
860 {
861 if (!index_recheck_constraint(index,
862 constr_procs,
863 existing_values,
864 existing_isnull,
865 values))
866 continue; /* tuple doesn't actually match, so no
867 * conflict */
868 }
869
870 /*
871 * At this point we have either a conflict or a potential conflict.
872 *
873 * If an in-progress transaction is affecting the visibility of this
874 * tuple, we need to wait for it to complete and then recheck (unless
875 * the caller requested not to). For simplicity we do rechecking by
876 * just restarting the whole scan --- this case probably doesn't
877 * happen often enough to be worth trying harder, and anyway we don't
878 * want to hold any index internal locks while waiting.
879 */
880 xwait = TransactionIdIsValid(DirtySnapshot.xmin) ?
881 DirtySnapshot.xmin : DirtySnapshot.xmax;
882
883 if (TransactionIdIsValid(xwait) &&
884 (waitMode == CEOUC_WAIT ||
885 (waitMode == CEOUC_LIVELOCK_PREVENTING_WAIT &&
886 DirtySnapshot.speculativeToken &&
887 TransactionIdPrecedes(GetCurrentTransactionId(), xwait))))
888 {
889 reason_wait = indexInfo->ii_ExclusionOps ?
890 XLTW_RecheckExclusionConstr : XLTW_InsertIndex;
891 index_endscan(index_scan);
892 if (DirtySnapshot.speculativeToken)
893 SpeculativeInsertionWait(DirtySnapshot.xmin,
894 DirtySnapshot.speculativeToken);
895 else
896 XactLockTableWait(xwait, heap,
897 &existing_slot->tts_tid, reason_wait);
898 goto retry;
899 }
900
901 /*
902 * We have a definite conflict (or a potential one, but the caller
903 * didn't want to wait). Return it to caller, or report it.
904 */
905 if (violationOK)
906 {
907 conflict = true;
908 if (conflictTid)
909 *conflictTid = existing_slot->tts_tid;
910 break;
911 }
912
913 error_new = BuildIndexValueDescription(index, values, isnull);
914 error_existing = BuildIndexValueDescription(index, existing_values,
915 existing_isnull);
916 if (newIndex)
917 ereport(ERROR,
918 (errcode(ERRCODE_EXCLUSION_VIOLATION),
919 errmsg("could not create exclusion constraint \"%s\"",
920 RelationGetRelationName(index)),
921 error_new && error_existing ?
922 errdetail("Key %s conflicts with key %s.",
923 error_new, error_existing) :
924 errdetail("Key conflicts exist."),
925 errtableconstraint(heap,
926 RelationGetRelationName(index))));
927 else
928 ereport(ERROR,
929 (errcode(ERRCODE_EXCLUSION_VIOLATION),
930 errmsg("conflicting key value violates exclusion constraint \"%s\"",
931 RelationGetRelationName(index)),
932 error_new && error_existing ?
933 errdetail("Key %s conflicts with existing key %s.",
934 error_new, error_existing) :
935 errdetail("Key conflicts with existing key."),
936 errtableconstraint(heap,
937 RelationGetRelationName(index))));
938 }
939
940 index_endscan(index_scan);
941
942 /*
943 * Ordinarily, at this point the search should have found the originally
944 * inserted tuple (if any), unless we exited the loop early because of
945 * conflict. However, it is possible to define exclusion constraints for
946 * which that wouldn't be true --- for instance, if the operator is <>. So
947 * we no longer complain if found_self is still false.
948 */
949
950 econtext->ecxt_scantuple = save_scantuple;
951
952 ExecDropSingleTupleTableSlot(existing_slot);
953
954 return !conflict;
955 }
956
957 /*
958 * Check for violation of an exclusion constraint
959 *
960 * This is a dumbed down version of check_exclusion_or_unique_constraint
961 * for external callers. They don't need all the special modes.
962 */
963 void
964 check_exclusion_constraint(Relation heap, Relation index,
965 IndexInfo *indexInfo,
966 ItemPointer tupleid,
967 const Datum *values, const bool *isnull,
968 EState *estate, bool newIndex)
969 {
970 (void) check_exclusion_or_unique_constraint(heap, index, indexInfo, tupleid,
971 values, isnull,
972 estate, newIndex,
973 CEOUC_WAIT, false, NULL);
974 }
975
976 /*
977 * Check existing tuple's index values to see if it really matches the
978 * exclusion condition against the new_values. Returns true if conflict.
979 */
980 static bool
981 index_recheck_constraint(Relation index, const Oid *constr_procs,
982 const Datum *existing_values, const bool *existing_isnull,
983 const Datum *new_values)
984 {
985 int indnkeyatts = IndexRelationGetNumberOfKeyAttributes(index);
986 int i;
987
988 for (i = 0; i < indnkeyatts; i++)
989 {
990 /* Assume the exclusion operators are strict */
991 if (existing_isnull[i])
992 return false;
993
994 if (!DatumGetBool(OidFunctionCall2Coll(constr_procs[i],
995 index->rd_indcollation[i],
996 existing_values[i],
997 new_values[i])))
998 return false;
999 }
1000
1001 return true;
1002 }
1003
1004 /*
1005 * Check if ExecInsertIndexTuples() should pass indexUnchanged hint.
1006 *
1007 * When the executor performs an UPDATE that requires a new round of index
1008 * tuples, determine if we should pass 'indexUnchanged' = true hint for one
1009 * single index.
1010 */
1011 static bool
1012 index_unchanged_by_update(ResultRelInfo *resultRelInfo, EState *estate,
1013 IndexInfo *indexInfo, Relation indexRelation)
1014 {
1015 Bitmapset *updatedCols;
1016 Bitmapset *extraUpdatedCols;
1017 Bitmapset *allUpdatedCols;
1018 bool hasexpression = false;
1019 List *idxExprs;
1020
1021 /*
1022 * Check cache first
1023 */
1024 if (indexInfo->ii_CheckedUnchanged)
1025 return indexInfo->ii_IndexUnchanged;
1026 indexInfo->ii_CheckedUnchanged = true;
1027
1028 /*
1029 * Check for indexed attribute overlap with updated columns.
1030 *
1031 * Only do this for key columns. A change to a non-key column within an
1032 * INCLUDE index should not be counted here. Non-key column values are
1033 * opaque payload state to the index AM, a little like an extra table TID.
1034 *
1035 * Note that row-level BEFORE triggers won't affect our behavior, since
1036 * they don't affect the updatedCols bitmaps generally. It doesn't seem
1037 * worth the trouble of checking which attributes were changed directly.
1038 */
1039 updatedCols = ExecGetUpdatedCols(resultRelInfo, estate);
1040 extraUpdatedCols = ExecGetExtraUpdatedCols(resultRelInfo, estate);
1041 for (int attr = 0; attr < indexInfo->ii_NumIndexKeyAttrs; attr++)
1042 {
1043 int keycol = indexInfo->ii_IndexAttrNumbers[attr];
1044
1045 if (keycol <= 0)
1046 {
1047 /*
1048 * Skip expressions for now, but remember to deal with them later
1049 * on
1050 */
1051 hasexpression = true;
1052 continue;
1053 }
1054
1055 if (bms_is_member(keycol - FirstLowInvalidHeapAttributeNumber,
1056 updatedCols) ||
1057 bms_is_member(keycol - FirstLowInvalidHeapAttributeNumber,
1058 extraUpdatedCols))
1059 {
1060 /* Changed key column -- don't hint for this index */
1061 indexInfo->ii_IndexUnchanged = false;
1062 return false;
1063 }
1064 }
1065
1066 /*
1067 * When we get this far and index has no expressions, return true so that
1068 * index_insert() call will go on to pass 'indexUnchanged' = true hint.
1069 *
1070 * The _absence_ of an indexed key attribute that overlaps with updated
1071 * attributes (in addition to the total absence of indexed expressions)
1072 * shows that the index as a whole is logically unchanged by UPDATE.
1073 */
1074 if (!hasexpression)
1075 {
1076 indexInfo->ii_IndexUnchanged = true;
1077 return true;
1078 }
1079
1080 /*
1081 * Need to pass only one bms to expression_tree_walker helper function.
1082 * Avoid allocating memory in common case where there are no extra cols.
1083 */
1084 if (!extraUpdatedCols)
1085 allUpdatedCols = updatedCols;
1086 else
1087 allUpdatedCols = bms_union(updatedCols, extraUpdatedCols);
1088
1089 /*
1090 * We have to work slightly harder in the event of indexed expressions,
1091 * but the principle is the same as before: try to find columns (Vars,
1092 * actually) that overlap with known-updated columns.
1093 *
1094 * If we find any matching Vars, don't pass hint for index. Otherwise
1095 * pass hint.
1096 */
1097 idxExprs = RelationGetIndexExpressions(indexRelation);
1098 hasexpression = index_expression_changed_walker((Node *) idxExprs,
1099 allUpdatedCols);
1100 list_free(idxExprs);
1101 if (extraUpdatedCols)
1102 bms_free(allUpdatedCols);
1103
1104 if (hasexpression)
1105 {
1106 indexInfo->ii_IndexUnchanged = false;
1107 return false;
1108 }
1109
1110 /*
1111 * Deliberately don't consider index predicates. We should even give the
1112 * hint when result rel's "updated tuple" has no corresponding index
1113 * tuple, which is possible with a partial index (provided the usual
1114 * conditions are met).
1115 */
1116 indexInfo->ii_IndexUnchanged = true;
1117 return true;
1118 }
1119
1120 /*
1121 * Indexed expression helper for index_unchanged_by_update().
1122 *
1123 * Returns true when Var that appears within allUpdatedCols located.
1124 */
1125 static bool
1126 index_expression_changed_walker(Node *node, Bitmapset *allUpdatedCols)
1127 {
1128 if (node == NULL)
1129 return false;
1130
1131 if (IsA(node, Var))
1132 {
1133 Var *var = (Var *) node;
1134
1135 if (bms_is_member(var->varattno - FirstLowInvalidHeapAttributeNumber,
1136 allUpdatedCols))
1137 {
1138 /* Var was updated -- indicates that we should not hint */
1139 return true;
1140 }
1141
1142 /* Still haven't found a reason to not pass the hint */
1143 return false;
1144 }
1145
1146 return expression_tree_walker(node, index_expression_changed_walker,
1147 allUpdatedCols);
1148 }
1149
1150 /*
1151 * ExecWithoutOverlapsNotEmpty - raise an error if the tuple has an empty
1152 * range or multirange in the given attribute.
1153 */
1154 static void
1155 ExecWithoutOverlapsNotEmpty(Relation rel, NameData attname, Datum attval, char typtype, Oid atttypid)
1156 {
1157 bool isempty;
1158 RangeType *r;
1159 MultirangeType *mr;
1160
1161 switch (typtype)
1162 {
1163 case TYPTYPE_RANGE:
1164 r = DatumGetRangeTypeP(attval);
1165 isempty = RangeIsEmpty(r);
1166 break;
1167 case TYPTYPE_MULTIRANGE:
1168 mr = DatumGetMultirangeTypeP(attval);
1169 isempty = MultirangeIsEmpty(mr);
1170 break;
1171 default:
1172 elog(ERROR, "WITHOUT OVERLAPS column \"%s\" is not a range or multirange",
1173 NameStr(attname));
1174 }
1175
1176 /* Report a CHECK_VIOLATION */
1177 if (isempty)
1178 ereport(ERROR,
1179 (errcode(ERRCODE_CHECK_VIOLATION),
1180 errmsg("empty WITHOUT OVERLAPS value found in column \"%s\" in relation \"%s\"",
1181 NameStr(attname), RelationGetRelationName(rel))));
1182 }