Subject: Re: performance issue in remove_from_unowned_list()
To: Alvaro Herrera <alvherre@2ndquadrant.com>
Cc: Postgres hackers <pgsql-hackers@lists.postgresql.org>
References: <20190310200923.GA4108@alvherre.pgsql>
From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Message-ID: <7c599eff-8125-091c-61ef-90e02aa57486@2ndquadrant.com>
Date: Tue, 12 Mar 2019 23:54:31 +0100
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:60.0) Gecko/20100101
 Thunderbird/60.5.1
MIME-Version: 1.0
In-Reply-To: <20190310200923.GA4108@alvherre.pgsql>
Content-Type: multipart/mixed;
 boundary="------------B29FDC0D4D64E7EBF44CF999"
Content-Language: en-US
Precedence: bulk

This is a multi-part message in MIME format.
--------------B29FDC0D4D64E7EBF44CF999
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: 7bit


On 3/10/19 9:09 PM, Alvaro Herrera wrote:
> On 2019-Feb-07, Tomas Vondra wrote:
> 
>> Attached is a WIP patch removing the optimization from DropRelationFiles
>> and adding it to smgrDoPendingDeletes. This resolves the issue, at least
>> in the cases I've been able to reproduce. But maybe we should deal with
>> this issue earlier by ensuring the two lists are ordered the same way
>> from the very beginning, somehow.
> 
> I noticed that this patch isn't in the commitfest.  Are you planning to
> push it soon?
> 

I wasn't planning to push anything particularly soon, for two reasons:
Firstly, the issue is not particularly pressing except with non-trivial
number of relations (and I only noticed that during benchmarking).
Secondly, I still have a feeling I'm missing something about b4166911
because for me that commit does not actually fix the issue - i.e. I can
create a lot of relations in a transaction, abort it, and observe that
the replica actually accesses the relations in exactly the wrong order.
So that commit does not seem to actually fix anything.

Attached is a patch adopting the dlist approach - it seems to be working
quite fine, and is a bit cleaner than just slapping another pointer into
the SMgrRelationData struct. So I'd say this is the way to go.

I see b4166911 was actually backpatched to all supported versions, on
the basis that it fixes oversight in 279628a0a7. So I suppose this fix
should also be backpatched.

regards

-- 
Tomas Vondra                  http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

--------------B29FDC0D4D64E7EBF44CF999
Content-Type: text/x-patch;
 name="smgr-dlist-wip-fix.patch"
Content-Transfer-Encoding: 7bit
Content-Disposition: attachment;
 filename="smgr-dlist-wip-fix.patch"

diff --git a/src/backend/storage/smgr/smgr.c b/src/backend/storage/smgr/smgr.c
index 0c0bba4ab3..10e84dc571 100644
--- a/src/backend/storage/smgr/smgr.c
+++ b/src/backend/storage/smgr/smgr.c
@@ -18,6 +18,7 @@
 #include "postgres.h"
 
 #include "commands/tablespace.h"
+#include "lib/ilist.h"
 #include "storage/bufmgr.h"
 #include "storage/ipc.h"
 #include "storage/smgr.h"
@@ -97,7 +98,7 @@ static const int NSmgr = lengthof(smgrsw);
  */
 static HTAB *SMgrRelationHash = NULL;
 
-static SMgrRelation first_unowned_reln = NULL;
+static dlist_head	unowned_relns;
 
 /* local function prototypes */
 static void smgrshutdown(int code, Datum arg);
@@ -165,7 +166,7 @@ smgropen(RelFileNode rnode, BackendId backend)
 		ctl.entrysize = sizeof(SMgrRelationData);
 		SMgrRelationHash = hash_create("smgr relation table", 400,
 									   &ctl, HASH_ELEM | HASH_BLOBS);
-		first_unowned_reln = NULL;
+		dlist_init(&unowned_relns);
 	}
 
 	/* Look up or create an entry */
@@ -258,9 +259,7 @@ smgrclearowner(SMgrRelation *owner, SMgrRelation reln)
 static void
 add_to_unowned_list(SMgrRelation reln)
 {
-	/* place it at head of the list (to make smgrsetowner cheap) */
-	reln->next_unowned_reln = first_unowned_reln;
-	first_unowned_reln = reln;
+	dlist_push_tail(&unowned_relns, &reln->node);
 }
 
 /*
@@ -268,31 +267,19 @@ add_to_unowned_list(SMgrRelation reln)
  *
  * If the reln is not present in the list, nothing happens.  Typically this
  * would be caller error, but there seems no reason to throw an error.
- *
- * In the worst case this could be rather slow; but in all the cases that seem
- * likely to be performance-critical, the reln being sought will actually be
- * first in the list.  Furthermore, the number of unowned relns touched in any
- * one transaction shouldn't be all that high typically.  So it doesn't seem
- * worth expending the additional space and management logic needed for a
- * doubly-linked list.
  */
 static void
 remove_from_unowned_list(SMgrRelation reln)
 {
-	SMgrRelation *link;
-	SMgrRelation cur;
+	/* if not in the list, do nothing */
+	if ((reln->node.prev == NULL) && (reln->node.next == NULL))
+		return;
 
-	for (link = &first_unowned_reln, cur = *link;
-		 cur != NULL;
-		 link = &cur->next_unowned_reln, cur = *link)
-	{
-		if (cur == reln)
-		{
-			*link = cur->next_unowned_reln;
-			cur->next_unowned_reln = NULL;
-			break;
-		}
-	}
+	dlist_delete(&reln->node);
+
+	/* reset the dlist pointers */
+	reln->node.prev = NULL;
+	reln->node.next = NULL;
 }
 
 /*
@@ -812,13 +799,19 @@ smgrpostckpt(void)
 void
 AtEOXact_SMgr(void)
 {
+	dlist_mutable_iter	iter;
+
 	/*
 	 * Zap all unowned SMgrRelations.  We rely on smgrclose() to remove each
 	 * one from the list.
 	 */
-	while (first_unowned_reln != NULL)
+	dlist_foreach_modify(iter, &unowned_relns)
 	{
-		Assert(first_unowned_reln->smgr_owner == NULL);
-		smgrclose(first_unowned_reln);
+		SMgrRelation	rel = dlist_container(SMgrRelationData, node,
+											  iter.cur);
+
+		Assert(rel->smgr_owner == NULL);
+
+		smgrclose(rel);
 	}
 }
diff --git a/src/include/storage/smgr.h b/src/include/storage/smgr.h
index 4d60b28dac..8e98273878 100644
--- a/src/include/storage/smgr.h
+++ b/src/include/storage/smgr.h
@@ -14,6 +14,7 @@
 #ifndef SMGR_H
 #define SMGR_H
 
+#include "lib/ilist.h"
 #include "storage/block.h"
 #include "storage/relfilenode.h"
 
@@ -71,7 +72,7 @@ typedef struct SMgrRelationData
 	struct _MdfdVec *md_seg_fds[MAX_FORKNUM + 1];
 
 	/* if unowned, list link in list of all unowned SMgrRelations */
-	struct SMgrRelationData *next_unowned_reln;
+	dlist_node	node;
 } SMgrRelationData;
 
 typedef SMgrRelationData *SMgrRelation;

--------------B29FDC0D4D64E7EBF44CF999--