Apply patches to optimize partition pruning

Maksim Milyutin · Maksim Milyutin · commit afc3f5599c34 · 2017-03-31T18:14:20.000+03:00
diff --git a/src/backend/catalog/pg_inherits.c b/src/backend/catalog/pg_inherits.c
@@ -28,9 +28,19 @@
 #include "parser/parse_type.h"
 #include "storage/lmgr.h"
 #include "utils/fmgroids.h"
+#include "utils/memutils.h"
 #include "utils/syscache.h"
 #include "utils/tqual.h"
 
+/*
+ * Entry of a hash table used in find_all_inheritors. See below.
+ */
+typedef struct SeenRelsEntry
+{
+	Oid			 rel_id;			/* relation oid */
+	ListCell	*numparents_cell;	/* corresponding list cell */
+} SeenRelsEntry;
+
 static int	oid_cmp(const void *p1, const void *p2);
 
 
@@ -158,10 +168,33 @@ find_inheritance_children(Oid parentrelId, LOCKMODE lockmode)
 List *
 find_all_inheritors(Oid parentrelId, LOCKMODE lockmode, List **numparents)
 {
+	/* hash table for O(1) rel_oid -> rel_numparents cell lookup */
+	HTAB		   *seen_rels;
+	HASHCTL			ctl;
+	MemoryContext	new_ctx;
 	List	   *rels_list,
 			   *rel_numparents;
 	ListCell   *l;
 
+	/*
+	 * We need a separate memory context for a hash table. This is because
+	 * hash table is used only in this procedure. To free a memory we need to
+	 * call hash_destroy which is just a wrapper around MemoryContextDelete.
+	 */
+	new_ctx = AllocSetContextCreate(CurrentMemoryContext,
+									"FindAllInheritorsSeenRelsContext",
+									ALLOCSET_DEFAULT_SIZES);
+
+	memset(&ctl, 0, sizeof(ctl));
+	ctl.keysize = sizeof(Oid);
+	ctl.entrysize = sizeof(SeenRelsEntry);
+	ctl.hcxt = new_ctx;
+
+	seen_rels = hash_create(
+		"find_all_inheritors temporary table",
+		32, /* start small and extend */
+		&ctl, HASH_ELEM | HASH_BLOBS | HASH_CONTEXT);
+
 	/*
 	 * We build a list starting with the given rel and adding all direct and
 	 * indirect children.  We can use a single list as both the record of
@@ -191,26 +224,21 @@ find_all_inheritors(Oid parentrelId, LOCKMODE lockmode, List **numparents)
 		foreach(lc, currentchildren)
 		{
 			Oid			child_oid = lfirst_oid(lc);
-			bool		found = false;
-			ListCell   *lo;
-			ListCell   *li;
+			bool			found;
+			SeenRelsEntry	*hash_entry;
 
-			/* if the rel is already there, bump number-of-parents counter */
-			forboth(lo, rels_list, li, rel_numparents)
+			hash_entry = hash_search(seen_rels, &child_oid, HASH_ENTER, &found);
+			if (found)
 			{
-				if (lfirst_oid(lo) == child_oid)
-				{
-					lfirst_int(li)++;
-					found = true;
-					break;
-				}
+				/* if the rel is already there, bump number-of-parents counter */
+				lfirst_int(hash_entry->numparents_cell)++;
 			}
-
-			/* if it's not there, add it. expect 1 parent, initially. */
-			if (!found)
+			else
 			{
+				/* if it's not there, add it. expect 1 parent, initially. */
 				rels_list = lappend_oid(rels_list, child_oid);
 				rel_numparents = lappend_int(rel_numparents, 1);
+				hash_entry->numparents_cell = rel_numparents->tail;
 			}
 		}
 	}
@@ -219,6 +247,9 @@ find_all_inheritors(Oid parentrelId, LOCKMODE lockmode, List **numparents)
 		*numparents = rel_numparents;
 	else
 		list_free(rel_numparents);
+
+	hash_destroy(seen_rels);
+
 	return rels_list;
 }
 
diff --git a/src/backend/postmaster/pgstat.c b/src/backend/postmaster/pgstat.c
@@ -160,6 +160,20 @@ typedef struct TabStatusArray
 
 static TabStatusArray *pgStatTabList = NULL;
 
+/*
+ * pgStatTabHash entry
+ */
+typedef struct TabStatHashEntry
+{
+	Oid t_id;
+	PgStat_TableStatus* tsa_entry;
+} TabStatHashEntry;
+
+/*
+ * Hash table for O(1) t_id -> tsa_entry lookup
+ */
+static HTAB *pgStatTabHash = NULL;
+
 /*
  * Backends store per-function info that's waiting to be sent to the collector
  * in this hash table (indexed by function OID).
@@ -817,6 +831,14 @@ pgstat_report_stat(bool force)
 		tsa->tsa_used = 0;
 	}
 
+	/*
+	 * pgStatTabHash is outdated on this point so we have to clean it,
+	 * hash_destroy() will remove hash memory context, allocated in
+	 * make_sure_stat_tab_initialized()
+	 */
+	hash_destroy(pgStatTabHash);
+	pgStatTabHash = NULL;
+
 	/*
 	 * Send partial messages.  Make sure that any pending xact commit/abort
 	 * gets counted, even if there are no table stats to send.
@@ -1661,60 +1683,88 @@ pgstat_initstats(Relation rel)
 	rel->pgstat_info = get_tabstat_entry(rel_id, rel->rd_rel->relisshared);
 }
 
+/*
+ * Make sure pgStatTabList and pgStatTabHash are initialized.
+ */
+static void
+make_sure_stat_tab_initialized()
+{
+	HASHCTL			ctl;
+	MemoryContext	new_ctx;
+
+	if(!pgStatTabList)
+	{
+		/* This is first time procedure is called */
+		pgStatTabList = (TabStatusArray *) MemoryContextAllocZero(TopMemoryContext,
+												sizeof(TabStatusArray));
+	}
+
+	if(pgStatTabHash)
+		return;
+
+	/* Hash table was freed or never existed.  */
+
+	new_ctx = AllocSetContextCreate(
+		TopMemoryContext,
+		"PGStatLookupHashTableContext",
+		ALLOCSET_DEFAULT_SIZES);
+
+	memset(&ctl, 0, sizeof(ctl));
+	ctl.keysize = sizeof(Oid);
+	ctl.entrysize = sizeof(TabStatHashEntry);
+	ctl.hcxt = new_ctx;
+
+	pgStatTabHash = hash_create("pgstat t_id to tsa_entry lookup hash table",
+		TABSTAT_QUANTUM, &ctl, HASH_ELEM | HASH_BLOBS | HASH_CONTEXT);
+}
+
 /*
  * get_tabstat_entry - find or create a PgStat_TableStatus entry for rel
  */
 static PgStat_TableStatus *
 get_tabstat_entry(Oid rel_id, bool isshared)
 {
+	TabStatHashEntry* hash_entry;
 	PgStat_TableStatus *entry;
 	TabStatusArray *tsa;
-	TabStatusArray *prev_tsa;
-	int			i;
+	bool found;
+
+	make_sure_stat_tab_initialized();
 
 	/*
-	 * Search the already-used tabstat slots for this relation.
+	 * Find an entry or create a new one.
 	 */
-	prev_tsa = NULL;
-	for (tsa = pgStatTabList; tsa != NULL; prev_tsa = tsa, tsa = tsa->tsa_next)
+	hash_entry = hash_search(pgStatTabHash, &rel_id, HASH_ENTER, &found);
+	if(found)
+		return hash_entry->tsa_entry;
+
+	/*
+	 * `hash_entry` was just created and now we have to fill it.
+	 * First make sure there is a free space in a last element of pgStatTabList.
+	 */
+	tsa = pgStatTabList;
+	while(tsa->tsa_used == TABSTAT_QUANTUM)
 	{
-		for (i = 0; i < tsa->tsa_used; i++)
+		if(tsa->tsa_next == NULL)
 		{
-			entry = &tsa->tsa_entries[i];
-			if (entry->t_id == rel_id)
-				return entry;
+			tsa->tsa_next = (TabStatusArray *) MemoryContextAllocZero(TopMemoryContext,
+														sizeof(TabStatusArray));
 		}
 
-		if (tsa->tsa_used < TABSTAT_QUANTUM)
-		{
-			/*
-			 * It must not be present, but we found a free slot instead. Fine,
-			 * let's use this one.  We assume the entry was already zeroed,
-			 * either at creation or after last use.
-			 */
-			entry = &tsa->tsa_entries[tsa->tsa_used++];
-			entry->t_id = rel_id;
-			entry->t_shared = isshared;
-			return entry;
-		}
+		tsa = tsa->tsa_next;
 	}
 
 	/*
-	 * We ran out of tabstat slots, so allocate more.  Be sure they're zeroed.
-	 */
-	tsa = (TabStatusArray *) MemoryContextAllocZero(TopMemoryContext,
-													sizeof(TabStatusArray));
-	if (prev_tsa)
-		prev_tsa->tsa_next = tsa;
-	else
-		pgStatTabList = tsa;
-
-	/*
-	 * Use the first entry of the new TabStatusArray.
+	 * Add an entry.
 	 */
 	entry = &tsa->tsa_entries[tsa->tsa_used++];
 	entry->t_id = rel_id;
 	entry->t_shared = isshared;
+
+	/*
+	 * Add a corresponding entry to pgStatTabHash.
+	 */
+	hash_entry->tsa_entry = entry;
 	return entry;
 }
 
@@ -1726,22 +1776,19 @@ get_tabstat_entry(Oid rel_id, bool isshared)
 PgStat_TableStatus *
 find_tabstat_entry(Oid rel_id)
 {
-	PgStat_TableStatus *entry;
-	TabStatusArray *tsa;
-	int			i;
+	TabStatHashEntry* hash_entry;
 
-	for (tsa = pgStatTabList; tsa != NULL; tsa = tsa->tsa_next)
-	{
-		for (i = 0; i < tsa->tsa_used; i++)
-		{
-			entry = &tsa->tsa_entries[i];
-			if (entry->t_id == rel_id)
-				return entry;
-		}
-	}
+	/*
+	 * There are no entries at all.
+	 */
+	if(!pgStatTabHash)
+		return NULL;
 
-	/* Not present */
-	return NULL;
+	hash_entry = hash_search(pgStatTabHash, &rel_id, HASH_FIND, NULL);
+	if(!hash_entry)
+		return NULL;
+
+	return hash_entry->tsa_entry;
 }
 
 /*
