PostgreSQL Source Code  git master
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Macros
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-2017, 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/heapam.h"
24 #include "access/htup_details.h"
25 #include "catalog/indexing.h"
26 #include "catalog/pg_inherits.h"
27 #include "catalog/pg_inherits_fn.h"
28 #include "parser/parse_type.h"
29 #include "storage/lmgr.h"
30 #include "utils/builtins.h"
31 #include "utils/fmgroids.h"
32 #include "utils/syscache.h"
33 #include "utils/tqual.h"
34 
35 
36 /*
37  * find_inheritance_children
38  *
39  * Returns a list containing the OIDs of all relations which
40  * inherit *directly* from the relation with OID 'parentrelId'.
41  *
42  * The specified lock type is acquired on each child relation (but not on the
43  * given rel; caller should already have locked it). If lockmode is NoLock
44  * then no locks are acquired, but caller must beware of race conditions
45  * against possible DROPs of child relations.
46  */
47 List *
48 find_inheritance_children(Oid parentrelId, LOCKMODE lockmode)
49 {
50  List *list = NIL;
51  Relation relation;
52  SysScanDesc scan;
53  ScanKeyData key[1];
54  HeapTuple inheritsTuple;
55  Oid inhrelid;
56  Oid *oidarr;
57  int maxoids,
58  numoids,
59  i;
60 
61  /*
62  * Can skip the scan if pg_class shows the relation has never had a
63  * subclass.
64  */
65  if (!has_subclass(parentrelId))
66  return NIL;
67 
68  /*
69  * Scan pg_inherits and build a working array of subclass OIDs.
70  */
71  maxoids = 32;
72  oidarr = (Oid *) palloc(maxoids * sizeof(Oid));
73  numoids = 0;
74 
76 
77  ScanKeyInit(&key[0],
79  BTEqualStrategyNumber, F_OIDEQ,
80  ObjectIdGetDatum(parentrelId));
81 
82  scan = systable_beginscan(relation, InheritsParentIndexId, true,
83  NULL, 1, key);
84 
85  while ((inheritsTuple = systable_getnext(scan)) != NULL)
86  {
87  inhrelid = ((Form_pg_inherits) GETSTRUCT(inheritsTuple))->inhrelid;
88  if (numoids >= maxoids)
89  {
90  maxoids *= 2;
91  oidarr = (Oid *) repalloc(oidarr, maxoids * sizeof(Oid));
92  }
93  oidarr[numoids++] = inhrelid;
94  }
95 
96  systable_endscan(scan);
97 
98  heap_close(relation, AccessShareLock);
99 
100  /*
101  * If we found more than one child, sort them by OID. This ensures
102  * reasonably consistent behavior regardless of the vagaries of an
103  * indexscan. This is important since we need to be sure all backends
104  * lock children in the same order to avoid needless deadlocks.
105  */
106  if (numoids > 1)
107  qsort(oidarr, numoids, sizeof(Oid), oid_cmp);
108 
109  /*
110  * Acquire locks and build the result list.
111  */
112  for (i = 0; i < numoids; i++)
113  {
114  inhrelid = oidarr[i];
115 
116  if (lockmode != NoLock)
117  {
118  /* Get the lock to synchronize against concurrent drop */
119  LockRelationOid(inhrelid, lockmode);
120 
121  /*
122  * Now that we have the lock, double-check to see if the relation
123  * really exists or not. If not, assume it was dropped while we
124  * waited to acquire lock, and ignore it.
125  */
127  {
128  /* Release useless lock */
129  UnlockRelationOid(inhrelid, lockmode);
130  /* And ignore this relation */
131  continue;
132  }
133  }
134 
135  list = lappend_oid(list, inhrelid);
136  }
137 
138  pfree(oidarr);
139 
140  return list;
141 }
142 
143 
144 /*
145  * find_all_inheritors -
146  * Returns a list of relation OIDs including the given rel plus
147  * all relations that inherit from it, directly or indirectly.
148  * Optionally, it also returns the number of parents found for
149  * each such relation within the inheritance tree rooted at the
150  * given rel.
151  *
152  * The specified lock type is acquired on all child relations (but not on the
153  * given rel; caller should already have locked it). If lockmode is NoLock
154  * then no locks are acquired, but caller must beware of race conditions
155  * against possible DROPs of child relations.
156  */
157 List *
158 find_all_inheritors(Oid parentrelId, LOCKMODE lockmode, List **numparents)
159 {
160  List *rels_list,
161  *rel_numparents;
162  ListCell *l;
163 
164  /*
165  * We build a list starting with the given rel and adding all direct and
166  * indirect children. We can use a single list as both the record of
167  * already-found rels and the agenda of rels yet to be scanned for more
168  * children. This is a bit tricky but works because the foreach() macro
169  * doesn't fetch the next list element until the bottom of the loop.
170  */
171  rels_list = list_make1_oid(parentrelId);
172  rel_numparents = list_make1_int(0);
173 
174  foreach(l, rels_list)
175  {
176  Oid currentrel = lfirst_oid(l);
177  List *currentchildren;
178  ListCell *lc;
179 
180  /* Get the direct children of this rel */
181  currentchildren = find_inheritance_children(currentrel, lockmode);
182 
183  /*
184  * Add to the queue only those children not already seen. This avoids
185  * making duplicate entries in case of multiple inheritance paths from
186  * the same parent. (It'll also keep us from getting into an infinite
187  * loop, though theoretically there can't be any cycles in the
188  * inheritance graph anyway.)
189  */
190  foreach(lc, currentchildren)
191  {
192  Oid child_oid = lfirst_oid(lc);
193  bool found = false;
194  ListCell *lo;
195  ListCell *li;
196 
197  /* if the rel is already there, bump number-of-parents counter */
198  forboth(lo, rels_list, li, rel_numparents)
199  {
200  if (lfirst_oid(lo) == child_oid)
201  {
202  lfirst_int(li)++;
203  found = true;
204  break;
205  }
206  }
207 
208  /* if it's not there, add it. expect 1 parent, initially. */
209  if (!found)
210  {
211  rels_list = lappend_oid(rels_list, child_oid);
212  rel_numparents = lappend_int(rel_numparents, 1);
213  }
214  }
215  }
216 
217  if (numparents)
218  *numparents = rel_numparents;
219  else
220  list_free(rel_numparents);
221  return rels_list;
222 }
223 
224 
225 /*
226  * has_subclass - does this relation have any children?
227  *
228  * In the current implementation, has_subclass returns whether a
229  * particular class *might* have a subclass. It will not return the
230  * correct result if a class had a subclass which was later dropped.
231  * This is because relhassubclass in pg_class is not updated immediately
232  * when a subclass is dropped, primarily because of concurrency concerns.
233  *
234  * Currently has_subclass is only used as an efficiency hack to skip
235  * unnecessary inheritance searches, so this is OK. Note that ANALYZE
236  * on a childless table will clean up the obsolete relhassubclass flag.
237  *
238  * Although this doesn't actually touch pg_inherits, it seems reasonable
239  * to keep it here since it's normally used with the other routines here.
240  */
241 bool
242 has_subclass(Oid relationId)
243 {
244  HeapTuple tuple;
245  bool result;
246 
247  tuple = SearchSysCache1(RELOID, ObjectIdGetDatum(relationId));
248  if (!HeapTupleIsValid(tuple))
249  elog(ERROR, "cache lookup failed for relation %u", relationId);
250 
251  result = ((Form_pg_class) GETSTRUCT(tuple))->relhassubclass;
252  ReleaseSysCache(tuple);
253  return result;
254 }
255 
256 
257 /*
258  * Given two type OIDs, determine whether the first is a complex type
259  * (class type) that inherits from the second.
260  */
261 bool
262 typeInheritsFrom(Oid subclassTypeId, Oid superclassTypeId)
263 {
264  bool result = false;
265  Oid subclassRelid;
266  Oid superclassRelid;
267  Relation inhrel;
268  List *visited,
269  *queue;
270  ListCell *queue_item;
271 
272  /* We need to work with the associated relation OIDs */
273  subclassRelid = typeidTypeRelid(subclassTypeId);
274  if (subclassRelid == InvalidOid)
275  return false; /* not a complex type */
276  superclassRelid = typeidTypeRelid(superclassTypeId);
277  if (superclassRelid == InvalidOid)
278  return false; /* not a complex type */
279 
280  /* No point in searching if the superclass has no subclasses */
281  if (!has_subclass(superclassRelid))
282  return false;
283 
284  /*
285  * Begin the search at the relation itself, so add its relid to the queue.
286  */
287  queue = list_make1_oid(subclassRelid);
288  visited = NIL;
289 
291 
292  /*
293  * Use queue to do a breadth-first traversal of the inheritance graph from
294  * the relid supplied up to the root. Notice that we append to the queue
295  * inside the loop --- this is okay because the foreach() macro doesn't
296  * advance queue_item until the next loop iteration begins.
297  */
298  foreach(queue_item, queue)
299  {
300  Oid this_relid = lfirst_oid(queue_item);
301  ScanKeyData skey;
302  SysScanDesc inhscan;
303  HeapTuple inhtup;
304 
305  /*
306  * If we've seen this relid already, skip it. This avoids extra work
307  * in multiple-inheritance scenarios, and also protects us from an
308  * infinite loop in case there is a cycle in pg_inherits (though
309  * theoretically that shouldn't happen).
310  */
311  if (list_member_oid(visited, this_relid))
312  continue;
313 
314  /*
315  * Okay, this is a not-yet-seen relid. Add it to the list of
316  * already-visited OIDs, then find all the types this relid inherits
317  * from and add them to the queue.
318  */
319  visited = lappend_oid(visited, this_relid);
320 
321  ScanKeyInit(&skey,
323  BTEqualStrategyNumber, F_OIDEQ,
324  ObjectIdGetDatum(this_relid));
325 
326  inhscan = systable_beginscan(inhrel, InheritsRelidSeqnoIndexId, true,
327  NULL, 1, &skey);
328 
329  while ((inhtup = systable_getnext(inhscan)) != NULL)
330  {
332  Oid inhparent = inh->inhparent;
333 
334  /* If this is the target superclass, we're done */
335  if (inhparent == superclassRelid)
336  {
337  result = true;
338  break;
339  }
340 
341  /* Else add to queue */
342  queue = lappend_oid(queue, inhparent);
343  }
344 
345  systable_endscan(inhscan);
346 
347  if (result)
348  break;
349  }
350 
351  /* clean up ... */
352  heap_close(inhrel, AccessShareLock);
353 
354  list_free(visited);
355  list_free(queue);
356 
357  return result;
358 }
#define NIL
Definition: pg_list.h:69
#define Anum_pg_inherits_inhrelid
Definition: pg_inherits.h:50
#define forboth(cell1, list1, cell2, list2)
Definition: pg_list.h:174
void systable_endscan(SysScanDesc sysscan)
Definition: genam.c:499
#define GETSTRUCT(TUP)
Definition: htup_details.h:656
int LOCKMODE
Definition: lockdefs.h:26
void UnlockRelationOid(Oid relid, LOCKMODE lockmode)
Definition: lmgr.c:182
#define AccessShareLock
Definition: lockdefs.h:36
return result
Definition: formatting.c:1618
Oid typeidTypeRelid(Oid type_id)
Definition: parse_type.c:646
#define heap_close(r, l)
Definition: heapam.h:97
unsigned int Oid
Definition: postgres_ext.h:31
List * lappend_oid(List *list, Oid datum)
Definition: list.c:164
SysScanDesc systable_beginscan(Relation heapRelation, Oid indexId, bool indexOK, Snapshot snapshot, int nkeys, ScanKey key)
Definition: genam.c:328
#define SearchSysCache1(cacheId, key1)
Definition: syscache.h:152
HeapTuple systable_getnext(SysScanDesc sysscan)
Definition: genam.c:416
#define SearchSysCacheExists1(cacheId, key1)
Definition: syscache.h:170
void pfree(void *pointer)
Definition: mcxt.c:950
bool has_subclass(Oid relationId)
Definition: pg_inherits.c:242
#define ObjectIdGetDatum(X)
Definition: postgres.h:513
#define ERROR
Definition: elog.h:43
#define lfirst_int(lc)
Definition: pg_list.h:107
#define NoLock
Definition: lockdefs.h:34
#define list_make1_int(x1)
Definition: pg_list.h:139
List * lappend_int(List *list, int datum)
Definition: list.c:146
void ReleaseSysCache(HeapTuple tuple)
Definition: syscache.c:1116
#define Anum_pg_inherits_inhparent
Definition: pg_inherits.h:51
#define list_make1_oid(x1)
Definition: pg_list.h:145
Relation heap_open(Oid relationId, LOCKMODE lockmode)
Definition: heapam.c:1287
#define InheritsParentIndexId
Definition: indexing.h:169
#define InvalidOid
Definition: postgres_ext.h:36
List * find_inheritance_children(Oid parentrelId, LOCKMODE lockmode)
Definition: pg_inherits.c:48
bool list_member_oid(const List *list, Oid datum)
Definition: list.c:505
#define HeapTupleIsValid(tuple)
Definition: htup.h:77
#define NULL
Definition: c.h:229
bool typeInheritsFrom(Oid subclassTypeId, Oid superclassTypeId)
Definition: pg_inherits.c:262
int oid_cmp(const void *p1, const void *p2)
Definition: oid.c:336
#define InheritsRelidSeqnoIndexId
Definition: indexing.h:167
FormData_pg_inherits * Form_pg_inherits
Definition: pg_inherits.h:43
void * repalloc(void *pointer, Size size)
Definition: mcxt.c:963
#define InheritsRelationId
Definition: pg_inherits.h:29
FormData_pg_class * Form_pg_class
Definition: pg_class.h:95
List * find_all_inheritors(Oid parentrelId, LOCKMODE lockmode, List **numparents)
Definition: pg_inherits.c:158
tuple list
Definition: sort-test.py:11
void * palloc(Size size)
Definition: mcxt.c:849
void list_free(List *list)
Definition: list.c:1133
int i
void ScanKeyInit(ScanKey entry, AttrNumber attributeNumber, StrategyNumber strategy, RegProcedure procedure, Datum argument)
Definition: scankey.c:76
#define elog
Definition: elog.h:219
#define qsort(a, b, c, d)
Definition: port.h:440
void LockRelationOid(Oid relid, LOCKMODE lockmode)
Definition: lmgr.c:105
Definition: pg_list.h:45
#define BTEqualStrategyNumber
Definition: stratnum.h:31
#define lfirst_oid(lc)
Definition: pg_list.h:108