Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit827d6f9

Browse files
committed
Improve performance of find_all_inheritors()
Previous coding uses three nested loops which obviously were a pain forlarge number of table's children. Patch replaces inner loop witha hashmap.Author: Aleksander AlekseevReviewed-by: mehttps://commitfest.postgresql.org/13/1058/
1 parent5196f13 commit827d6f9

File tree

1 file changed

+44
-14
lines changed

1 file changed

+44
-14
lines changed

‎src/backend/catalog/pg_inherits.c

Lines changed: 44 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -31,7 +31,16 @@
3131
#include"utils/fmgroids.h"
3232
#include"utils/syscache.h"
3333
#include"utils/tqual.h"
34+
#include"utils/memutils.h"
3435

36+
/*
37+
* Entry of a hash table used in find_all_inheritors. See below.
38+
*/
39+
typedefstructSeenRelsEntry
40+
{
41+
Oidrel_id;/* relation oid */
42+
ListCell*numparents_cell;/* corresponding list cell */
43+
}SeenRelsEntry;
3544

3645
/*
3746
* find_inheritance_children
@@ -157,10 +166,33 @@ find_inheritance_children(Oid parentrelId, LOCKMODE lockmode)
157166
List*
158167
find_all_inheritors(OidparentrelId,LOCKMODElockmode,List**numparents)
159168
{
169+
/* hash table for O(1) rel_oid -> rel_numparents cell lookup */
170+
HTAB*seen_rels;
171+
HASHCTLctl;
172+
MemoryContextnew_ctx;
160173
List*rels_list,
161174
*rel_numparents;
162175
ListCell*l;
163176

177+
/*
178+
* We need a separate memory context for a hash table. This is because
179+
* hash table is used only in this procedure. To free a memory we need to
180+
* call hash_destroy which is just a wrapper around MemoryContextDelete.
181+
*/
182+
new_ctx=AllocSetContextCreate(CurrentMemoryContext,
183+
"FindAllInheritorsSeenRelsContext",
184+
ALLOCSET_DEFAULT_SIZES);
185+
186+
memset(&ctl,0,sizeof(ctl));
187+
ctl.keysize=sizeof(Oid);
188+
ctl.entrysize=sizeof(SeenRelsEntry);
189+
ctl.hcxt=new_ctx;
190+
191+
seen_rels=hash_create(
192+
"find_all_inheritors temporary table",
193+
32,/* start small and extend */
194+
&ctl,HASH_ELEM |HASH_BLOBS |HASH_CONTEXT);
195+
164196
/*
165197
* We build a list starting with the given rel and adding all direct and
166198
* indirect children. We can use a single list as both the record of
@@ -190,26 +222,21 @@ find_all_inheritors(Oid parentrelId, LOCKMODE lockmode, List **numparents)
190222
foreach(lc,currentchildren)
191223
{
192224
Oidchild_oid=lfirst_oid(lc);
193-
boolfound= false;
194-
ListCell*lo;
195-
ListCell*li;
225+
boolfound;
226+
SeenRelsEntry*hash_entry;
196227

197-
/* if the rel is already there, bump number-of-parents counter */
198-
forboth(lo,rels_list,li,rel_numparents)
228+
hash_entry=hash_search(seen_rels,&child_oid,HASH_ENTER,&found);
229+
if (found)
199230
{
200-
if (lfirst_oid(lo)==child_oid)
201-
{
202-
lfirst_int(li)++;
203-
found= true;
204-
break;
205-
}
231+
/* if the rel is already there, bump number-of-parents counter */
232+
lfirst_int(hash_entry->numparents_cell)++;
206233
}
207-
208-
/* if it's not there, add it. expect 1 parent, initially. */
209-
if (!found)
234+
else
210235
{
236+
/* if it's not there, add it. expect 1 parent, initially. */
211237
rels_list=lappend_oid(rels_list,child_oid);
212238
rel_numparents=lappend_int(rel_numparents,1);
239+
hash_entry->numparents_cell=rel_numparents->tail;
213240
}
214241
}
215242
}
@@ -218,6 +245,9 @@ find_all_inheritors(Oid parentrelId, LOCKMODE lockmode, List **numparents)
218245
*numparents=rel_numparents;
219246
else
220247
list_free(rel_numparents);
248+
249+
hash_destroy(seen_rels);
250+
221251
returnrels_list;
222252
}
223253

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp