PostgreSQL Source Code  git master
pg_inherits.c
Go to the documentation of this file.
1 /*-------------------------------------------------------------------------
2  *
3  * pg_inherits.c
4  * routines to support manipulation of the pg_inherits relation
5  *
6  * Note: currently, this module only contains inquiry functions; the actual
7  * creation and deletion of pg_inherits entries is done in tablecmds.c.
8  * Perhaps someday that code should be moved here, but it'd have to be
9  * disentangled from other stuff such as pg_depend updates.
10  *
11  * Portions Copyright (c) 1996-2019, PostgreSQL Global Development Group
12  * Portions Copyright (c) 1994, Regents of the University of California
13  *
14  *
15  * IDENTIFICATION
16  * src/backend/catalog/pg_inherits.c
17  *
18  *-------------------------------------------------------------------------
19  */
20 #include "postgres.h"
21 
22 #include "access/genam.h"
23 #include "access/htup_details.h"
24 #include "access/table.h"
25 #include "catalog/indexing.h"
26 #include "catalog/pg_inherits.h"
27 #include "parser/parse_type.h"
28 #include "storage/lmgr.h"
29 #include "utils/builtins.h"
30 #include "utils/fmgroids.h"
31 #include "utils/memutils.h"
32 #include "utils/syscache.h"
33 
34 /*
35  * Entry of a hash table used in find_all_inheritors. See below.
36  */
37 typedef struct SeenRelsEntry
38 {
39  Oid rel_id; /* relation oid */
40  int list_index; /* its position in output list(s) */
42 
43 /*
44  * find_inheritance_children
45  *
46  * Returns a list containing the OIDs of all relations which
47  * inherit *directly* from the relation with OID 'parentrelId'.
48  *
49  * The specified lock type is acquired on each child relation (but not on the
50  * given rel; caller should already have locked it). If lockmode is NoLock
51  * then no locks are acquired, but caller must beware of race conditions
52  * against possible DROPs of child relations.
53  */
54 List *
55 find_inheritance_children(Oid parentrelId, LOCKMODE lockmode)
56 {
57  List *list = NIL;
58  Relation relation;
59  SysScanDesc scan;
60  ScanKeyData key[1];
61  HeapTuple inheritsTuple;
62  Oid inhrelid;
63  Oid *oidarr;
64  int maxoids,
65  numoids,
66  i;
67 
68  /*
69  * Can skip the scan if pg_class shows the relation has never had a
70  * subclass.
71  */
72  if (!has_subclass(parentrelId))
73  return NIL;
74 
75  /*
76  * Scan pg_inherits and build a working array of subclass OIDs.
77  */
78  maxoids = 32;
79  oidarr = (Oid *) palloc(maxoids * sizeof(Oid));
80  numoids = 0;
81 
82  relation = table_open(InheritsRelationId, AccessShareLock);
83 
84  ScanKeyInit(&key[0],
85  Anum_pg_inherits_inhparent,
86  BTEqualStrategyNumber, F_OIDEQ,
87  ObjectIdGetDatum(parentrelId));
88 
89  scan = systable_beginscan(relation, InheritsParentIndexId, true,
90  NULL, 1, key);
91 
92  while ((inheritsTuple = systable_getnext(scan)) != NULL)
93  {
94  inhrelid = ((Form_pg_inherits) GETSTRUCT(inheritsTuple))->inhrelid;
95  if (numoids >= maxoids)
96  {
97  maxoids *= 2;
98  oidarr = (Oid *) repalloc(oidarr, maxoids * sizeof(Oid));
99  }
100  oidarr[numoids++] = inhrelid;
101  }
102 
103  systable_endscan(scan);
104 
105  table_close(relation, AccessShareLock);
106 
107  /*
108  * If we found more than one child, sort them by OID. This ensures
109  * reasonably consistent behavior regardless of the vagaries of an
110  * indexscan. This is important since we need to be sure all backends
111  * lock children in the same order to avoid needless deadlocks.
112  */
113  if (numoids > 1)
114  qsort(oidarr, numoids, sizeof(Oid), oid_cmp);
115 
116  /*
117  * Acquire locks and build the result list.
118  */
119  for (i = 0; i < numoids; i++)
120  {
121  inhrelid = oidarr[i];
122 
123  if (lockmode != NoLock)
124  {
125  /* Get the lock to synchronize against concurrent drop */
126  LockRelationOid(inhrelid, lockmode);
127 
128  /*
129  * Now that we have the lock, double-check to see if the relation
130  * really exists or not. If not, assume it was dropped while we
131  * waited to acquire lock, and ignore it.
132  */
134  {
135  /* Release useless lock */
136  UnlockRelationOid(inhrelid, lockmode);
137  /* And ignore this relation */
138  continue;
139  }
140  }
141 
142  list = lappend_oid(list, inhrelid);
143  }
144 
145  pfree(oidarr);
146 
147  return list;
148 }
149 
150 
151 /*
152  * find_all_inheritors -
153  * Returns a list of relation OIDs including the given rel plus
154  * all relations that inherit from it, directly or indirectly.
155  * Optionally, it also returns the number of parents found for
156  * each such relation within the inheritance tree rooted at the
157  * given rel.
158  *
159  * The specified lock type is acquired on all child relations (but not on the
160  * given rel; caller should already have locked it). If lockmode is NoLock
161  * then no locks are acquired, but caller must beware of race conditions
162  * against possible DROPs of child relations.
163  */
164 List *
165 find_all_inheritors(Oid parentrelId, LOCKMODE lockmode, List **numparents)
166 {
167  /* hash table for O(1) rel_oid -> rel_numparents cell lookup */
168  HTAB *seen_rels;
169  HASHCTL ctl;
170  List *rels_list,
171  *rel_numparents;
172  ListCell *l;
173 
174  memset(&ctl, 0, sizeof(ctl));
175  ctl.keysize = sizeof(Oid);
176  ctl.entrysize = sizeof(SeenRelsEntry);
178 
179  seen_rels = hash_create("find_all_inheritors temporary table",
180  32, /* start small and extend */
181  &ctl,
183 
184  /*
185  * We build a list starting with the given rel and adding all direct and
186  * indirect children. We can use a single list as both the record of
187  * already-found rels and the agenda of rels yet to be scanned for more
188  * children. This is a bit tricky but works because the foreach() macro
189  * doesn't fetch the next list element until the bottom of the loop. Note
190  * that we can't keep pointers into the output lists; but an index is
191  * sufficient.
192  */
193  rels_list = list_make1_oid(parentrelId);
194  rel_numparents = list_make1_int(0);
195 
196  foreach(l, rels_list)
197  {
198  Oid currentrel = lfirst_oid(l);
199  List *currentchildren;
200  ListCell *lc;
201 
202  /* Get the direct children of this rel */
203  currentchildren = find_inheritance_children(currentrel, lockmode);
204 
205  /*
206  * Add to the queue only those children not already seen. This avoids
207  * making duplicate entries in case of multiple inheritance paths from
208  * the same parent. (It'll also keep us from getting into an infinite
209  * loop, though theoretically there can't be any cycles in the
210  * inheritance graph anyway.)
211  */
212  foreach(lc, currentchildren)
213  {
214  Oid child_oid = lfirst_oid(lc);
215  bool found;
216  SeenRelsEntry *hash_entry;
217 
218  hash_entry = hash_search(seen_rels, &child_oid, HASH_ENTER, &found);
219  if (found)
220  {
221  /* if the rel is already there, bump number-of-parents counter */
222  ListCell *numparents_cell;
223 
224  numparents_cell = list_nth_cell(rel_numparents,
225  hash_entry->list_index);
226  lfirst_int(numparents_cell)++;
227  }
228  else
229  {
230  /* if it's not there, add it. expect 1 parent, initially. */
231  hash_entry->list_index = list_length(rels_list);
232  rels_list = lappend_oid(rels_list, child_oid);
233  rel_numparents = lappend_int(rel_numparents, 1);
234  }
235  }
236  }
237 
238  if (numparents)
239  *numparents = rel_numparents;
240  else
241  list_free(rel_numparents);
242 
243  hash_destroy(seen_rels);
244 
245  return rels_list;
246 }
247 
248 
249 /*
250  * has_subclass - does this relation have any children?
251  *
252  * In the current implementation, has_subclass returns whether a
253  * particular class *might* have a subclass. It will not return the
254  * correct result if a class had a subclass which was later dropped.
255  * This is because relhassubclass in pg_class is not updated immediately
256  * when a subclass is dropped, primarily because of concurrency concerns.
257  *
258  * Currently has_subclass is only used as an efficiency hack to skip
259  * unnecessary inheritance searches, so this is OK. Note that ANALYZE
260  * on a childless table will clean up the obsolete relhassubclass flag.
261  *
262  * Although this doesn't actually touch pg_inherits, it seems reasonable
263  * to keep it here since it's normally used with the other routines here.
264  */
265 bool
266 has_subclass(Oid relationId)
267 {
268  HeapTuple tuple;
269  bool result;
270 
271  tuple = SearchSysCache1(RELOID, ObjectIdGetDatum(relationId));
272  if (!HeapTupleIsValid(tuple))
273  elog(ERROR, "cache lookup failed for relation %u", relationId);
274 
275  result = ((Form_pg_class) GETSTRUCT(tuple))->relhassubclass;
276  ReleaseSysCache(tuple);
277  return result;
278 }
279 
280 /*
281  * has_superclass - does this relation inherit from another? The caller
282  * should hold a lock on the given relation so that it can't be concurrently
283  * added to or removed from an inheritance hierarchy.
284  */
285 bool
286 has_superclass(Oid relationId)
287 {
288  Relation catalog;
289  SysScanDesc scan;
290  ScanKeyData skey;
291  bool result;
292 
293  catalog = table_open(InheritsRelationId, AccessShareLock);
294  ScanKeyInit(&skey, Anum_pg_inherits_inhrelid, BTEqualStrategyNumber,
295  F_OIDEQ, ObjectIdGetDatum(relationId));
296  scan = systable_beginscan(catalog, InheritsRelidSeqnoIndexId, true,
297  NULL, 1, &skey);
298  result = HeapTupleIsValid(systable_getnext(scan));
299  systable_endscan(scan);
300  table_close(catalog, AccessShareLock);
301 
302  return result;
303 }
304 
305 /*
306  * Given two type OIDs, determine whether the first is a complex type
307  * (class type) that inherits from the second.
308  *
309  * This essentially asks whether the first type is guaranteed to be coercible
310  * to the second. Therefore, we allow the first type to be a domain over a
311  * complex type that inherits from the second; that creates no difficulties.
312  * But the second type cannot be a domain.
313  */
314 bool
315 typeInheritsFrom(Oid subclassTypeId, Oid superclassTypeId)
316 {
317  bool result = false;
318  Oid subclassRelid;
319  Oid superclassRelid;
320  Relation inhrel;
321  List *visited,
322  *queue;
323  ListCell *queue_item;
324 
325  /* We need to work with the associated relation OIDs */
326  subclassRelid = typeOrDomainTypeRelid(subclassTypeId);
327  if (subclassRelid == InvalidOid)
328  return false; /* not a complex type or domain over one */
329  superclassRelid = typeidTypeRelid(superclassTypeId);
330  if (superclassRelid == InvalidOid)
331  return false; /* not a complex type */
332 
333  /* No point in searching if the superclass has no subclasses */
334  if (!has_subclass(superclassRelid))
335  return false;
336 
337  /*
338  * Begin the search at the relation itself, so add its relid to the queue.
339  */
340  queue = list_make1_oid(subclassRelid);
341  visited = NIL;
342 
343  inhrel = table_open(InheritsRelationId, AccessShareLock);
344 
345  /*
346  * Use queue to do a breadth-first traversal of the inheritance graph from
347  * the relid supplied up to the root. Notice that we append to the queue
348  * inside the loop --- this is okay because the foreach() macro doesn't
349  * advance queue_item until the next loop iteration begins.
350  */
351  foreach(queue_item, queue)
352  {
353  Oid this_relid = lfirst_oid(queue_item);
354  ScanKeyData skey;
355  SysScanDesc inhscan;
356  HeapTuple inhtup;
357 
358  /*
359  * If we've seen this relid already, skip it. This avoids extra work
360  * in multiple-inheritance scenarios, and also protects us from an
361  * infinite loop in case there is a cycle in pg_inherits (though
362  * theoretically that shouldn't happen).
363  */
364  if (list_member_oid(visited, this_relid))
365  continue;
366 
367  /*
368  * Okay, this is a not-yet-seen relid. Add it to the list of
369  * already-visited OIDs, then find all the types this relid inherits
370  * from and add them to the queue.
371  */
372  visited = lappend_oid(visited, this_relid);
373 
374  ScanKeyInit(&skey,
375  Anum_pg_inherits_inhrelid,
376  BTEqualStrategyNumber, F_OIDEQ,
377  ObjectIdGetDatum(this_relid));
378 
379  inhscan = systable_beginscan(inhrel, InheritsRelidSeqnoIndexId, true,
380  NULL, 1, &skey);
381 
382  while ((inhtup = systable_getnext(inhscan)) != NULL)
383  {
385  Oid inhparent = inh->inhparent;
386 
387  /* If this is the target superclass, we're done */
388  if (inhparent == superclassRelid)
389  {
390  result = true;
391  break;
392  }
393 
394  /* Else add to queue */
395  queue = lappend_oid(queue, inhparent);
396  }
397 
398  systable_endscan(inhscan);
399 
400  if (result)
401  break;
402  }
403 
404  /* clean up ... */
405  table_close(inhrel, AccessShareLock);
406 
407  list_free(visited);
408  list_free(queue);
409 
410  return result;
411 }
412 
413 /*
414  * Create a single pg_inherits row with the given data
415  */
416 void
417 StoreSingleInheritance(Oid relationId, Oid parentOid, int32 seqNumber)
418 {
419  Datum values[Natts_pg_inherits];
420  bool nulls[Natts_pg_inherits];
421  HeapTuple tuple;
422  Relation inhRelation;
423 
424  inhRelation = table_open(InheritsRelationId, RowExclusiveLock);
425 
426  /*
427  * Make the pg_inherits entry
428  */
429  values[Anum_pg_inherits_inhrelid - 1] = ObjectIdGetDatum(relationId);
430  values[Anum_pg_inherits_inhparent - 1] = ObjectIdGetDatum(parentOid);
431  values[Anum_pg_inherits_inhseqno - 1] = Int32GetDatum(seqNumber);
432 
433  memset(nulls, 0, sizeof(nulls));
434 
435  tuple = heap_form_tuple(RelationGetDescr(inhRelation), values, nulls);
436 
437  CatalogTupleInsert(inhRelation, tuple);
438 
439  heap_freetuple(tuple);
440 
441  table_close(inhRelation, RowExclusiveLock);
442 }
443 
444 /*
445  * DeleteInheritsTuple
446  *
447  * Delete pg_inherits tuples with the given inhrelid. inhparent may be given
448  * as InvalidOid, in which case all tuples matching inhrelid are deleted;
449  * otherwise only delete tuples with the specified inhparent.
450  *
451  * Returns whether at least one row was deleted.
452  */
453 bool
454 DeleteInheritsTuple(Oid inhrelid, Oid inhparent)
455 {
456  bool found = false;
457  Relation catalogRelation;
459  SysScanDesc scan;
460  HeapTuple inheritsTuple;
461 
462  /*
463  * Find pg_inherits entries by inhrelid.
464  */
465  catalogRelation = table_open(InheritsRelationId, RowExclusiveLock);
466  ScanKeyInit(&key,
467  Anum_pg_inherits_inhrelid,
468  BTEqualStrategyNumber, F_OIDEQ,
469  ObjectIdGetDatum(inhrelid));
470  scan = systable_beginscan(catalogRelation, InheritsRelidSeqnoIndexId,
471  true, NULL, 1, &key);
472 
473  while (HeapTupleIsValid(inheritsTuple = systable_getnext(scan)))
474  {
475  Oid parent;
476 
477  /* Compare inhparent if it was given, and do the actual deletion. */
478  parent = ((Form_pg_inherits) GETSTRUCT(inheritsTuple))->inhparent;
479  if (!OidIsValid(inhparent) || parent == inhparent)
480  {
481  CatalogTupleDelete(catalogRelation, &inheritsTuple->t_self);
482  found = true;
483  }
484  }
485 
486  /* Done */
487  systable_endscan(scan);
488  table_close(catalogRelation, RowExclusiveLock);
489 
490  return found;
491 }
#define NIL
Definition: pg_list.h:65
void hash_destroy(HTAB *hashp)
Definition: dynahash.c:814
void table_close(Relation relation, LOCKMODE lockmode)
Definition: table.c:133
void systable_endscan(SysScanDesc sysscan)
Definition: genam.c:525
#define GETSTRUCT(TUP)
Definition: htup_details.h:655
Oid typeOrDomainTypeRelid(Oid type_id)
Definition: parse_type.c:687
#define HASH_CONTEXT
Definition: hsearch.h:93
#define HASH_ELEM
Definition: hsearch.h:87
static ListCell * list_nth_cell(const List *list, int n)
Definition: pg_list.h:265
MemoryContext hcxt
Definition: hsearch.h:78
#define RelationGetDescr(relation)
Definition: rel.h:449
int LOCKMODE
Definition: lockdefs.h:26
void UnlockRelationOid(Oid relid, LOCKMODE lockmode)
Definition: lmgr.c:199
bool relhassubclass
Definition: pg_class.h:102
#define AccessShareLock
Definition: lockdefs.h:36
bool DeleteInheritsTuple(Oid inhrelid, Oid inhparent)
Definition: pg_inherits.c:454
Size entrysize
Definition: hsearch.h:73
Oid typeidTypeRelid(Oid type_id)
Definition: parse_type.c:666
void CatalogTupleDelete(Relation heapRel, ItemPointer tid)
Definition: indexing.c:269
HeapTuple heap_form_tuple(TupleDesc tupleDescriptor, Datum *values, bool *isnull)
Definition: heaptuple.c:1020
void * hash_search(HTAB *hashp, const void *keyPtr, HASHACTION action, bool *foundPtr)
Definition: dynahash.c:906
void heap_freetuple(HeapTuple htup)
Definition: heaptuple.c:1338
unsigned int Oid
Definition: postgres_ext.h:31
List * lappend_oid(List *list, Oid datum)
Definition: list.c:358
#define OidIsValid(objectId)
Definition: c.h:639
SysScanDesc systable_beginscan(Relation heapRelation, Oid indexId, bool indexOK, Snapshot snapshot, int nkeys, ScanKey key)
Definition: genam.c:352
signed int int32
Definition: c.h:347
Definition: dynahash.c:208
HeapTuple systable_getnext(SysScanDesc sysscan)
Definition: genam.c:444
#define SearchSysCacheExists1(cacheId, key1)
Definition: syscache.h:183
void pfree(void *pointer)
Definition: mcxt.c:1056
bool has_subclass(Oid relationId)
Definition: pg_inherits.c:266
#define ObjectIdGetDatum(X)
Definition: postgres.h:507
#define ERROR
Definition: elog.h:43
#define lfirst_int(lc)
Definition: pg_list.h:191
ItemPointerData t_self
Definition: htup.h:65
bool has_superclass(Oid relationId)
Definition: pg_inherits.c:286
#define NoLock
Definition: lockdefs.h:34
#define RowExclusiveLock
Definition: lockdefs.h:38
MemoryContext CurrentMemoryContext
Definition: mcxt.c:38
#define list_make1_int(x1)
Definition: pg_list.h:238
void StoreSingleInheritance(Oid relationId, Oid parentOid, int32 seqNumber)
Definition: pg_inherits.c:417
List * lappend_int(List *list, int datum)
Definition: list.c:340
struct SeenRelsEntry SeenRelsEntry
HeapTuple SearchSysCache1(int cacheId, Datum key1)
Definition: syscache.c:1116
#define HASH_BLOBS
Definition: hsearch.h:88
uintptr_t Datum
Definition: postgres.h:367
HTAB * hash_create(const char *tabname, long nelem, HASHCTL *info, int flags)
Definition: dynahash.c:316
void ReleaseSysCache(HeapTuple tuple)
Definition: syscache.c:1164
#define list_make1_oid(x1)
Definition: pg_list.h:249
Size keysize
Definition: hsearch.h:72
#define InheritsParentIndexId
Definition: indexing.h:173
#define InvalidOid
Definition: postgres_ext.h:36
List * find_inheritance_children(Oid parentrelId, LOCKMODE lockmode)
Definition: pg_inherits.c:55
bool list_member_oid(const List *list, Oid datum)
Definition: list.c:675
#define HeapTupleIsValid(tuple)
Definition: htup.h:78
bool typeInheritsFrom(Oid subclassTypeId, Oid superclassTypeId)
Definition: pg_inherits.c:315
int oid_cmp(const void *p1, const void *p2)
Definition: oid.c:336
#define InheritsRelidSeqnoIndexId
Definition: indexing.h:171
FormData_pg_inherits * Form_pg_inherits
Definition: pg_inherits.h:44
static int list_length(const List *l)
Definition: pg_list.h:169
void * repalloc(void *pointer, Size size)
Definition: mcxt.c:1069
static Datum values[MAXATTR]
Definition: bootstrap.c:167
FormData_pg_class * Form_pg_class
Definition: pg_class.h:150
List * find_all_inheritors(Oid parentrelId, LOCKMODE lockmode, List **numparents)
Definition: pg_inherits.c:165
#define Int32GetDatum(X)
Definition: postgres.h:479
void * palloc(Size size)
Definition: mcxt.c:949
void list_free(List *list)
Definition: list.c:1377
#define elog(elevel,...)
Definition: elog.h:228
int i
void ScanKeyInit(ScanKey entry, AttrNumber attributeNumber, StrategyNumber strategy, RegProcedure procedure, Datum argument)
Definition: scankey.c:76
#define qsort(a, b, c, d)
Definition: port.h:492
void LockRelationOid(Oid relid, LOCKMODE lockmode)
Definition: lmgr.c:108
Relation table_open(Oid relationId, LOCKMODE lockmode)
Definition: table.c:39
Definition: pg_list.h:50
void CatalogTupleInsert(Relation heapRel, HeapTuple tup)
Definition: indexing.c:183
#define BTEqualStrategyNumber
Definition: stratnum.h:31
#define lfirst_oid(lc)
Definition: pg_list.h:192