diff --git a/src/backend/commands/indexcmds.c b/src/backend/commands/indexcmds.c
index cb5d91e7640..d6f34a09646 100644
--- a/src/backend/commands/indexcmds.c
+++ b/src/backend/commands/indexcmds.c
@@ -85,8 +85,16 @@ static char *ChooseIndexName(const char *tabname, Oid namespaceId,
 				bool primary, bool isconstraint);
 static char *ChooseIndexNameAddition(List *colnames);
 static List *ChooseIndexColumnNames(List *indexElems);
+
+typedef struct RVCReindexParams
+{
+	Oid heapOid;
+	bool concurrently;
+} RVCReindexParams;
 static void RangeVarCallbackForReindexIndex(const RangeVar *relation,
 								Oid relId, Oid oldRelId, void *arg);
+static void RangeVarCallbackForReindexTable(const RangeVar *relation,
+								Oid relId, Oid oldRelId, void *arg);
 static bool ReindexRelationConcurrently(Oid relationOid, int options);
 static void ReindexPartitionedIndex(Relation parentIdx);
 static void update_relispartition(Oid relationId, bool newval);
@@ -2304,10 +2312,13 @@ void
 ReindexIndex(RangeVar *indexRelation, int options, bool concurrent)
 {
 	Oid			indOid;
-	Oid			heapOid = InvalidOid;
+	RVCReindexParams params;
 	Relation	irel;
 	char		persistence;
 
+	params.heapOid = InvalidOid;
+	params.concurrently = concurrent;
+
 	/*
 	 * Find and lock index, and check permissions on table; use callback to
 	 * obtain lock on table first, to avoid deadlock hazard.  The lock level
@@ -2317,7 +2328,7 @@ ReindexIndex(RangeVar *indexRelation, int options, bool concurrent)
 									  concurrent ? ShareUpdateExclusiveLock : AccessExclusiveLock,
 									  0,
 									  RangeVarCallbackForReindexIndex,
-									  (void *) &heapOid);
+									  (void *) &params);
 
 	/*
 	 * Obtain the current persistence of the existing index.  We already hold
@@ -2340,6 +2351,48 @@ ReindexIndex(RangeVar *indexRelation, int options, bool concurrent)
 		reindex_index(indOid, false, persistence, options);
 }
 
+static LOCKMODE
+table_lockmode_for_reindex(Oid heapOid, bool concurrently)
+{
+	if (concurrently)
+	{
+		/*
+		 * If concurrently were allowed on catalog tables this result would be
+		 * wrong, but it is not. We can't assert or throw an error here
+		 * however, as it's not yet guaranteed that this is the affected
+		 * table.
+		 */
+		return ShareUpdateExclusiveLock;
+	}
+	else if (heapOid == IndexRelationId ||
+		heapOid == RelationRelationId)
+	{
+		/*
+		 * When reindexing indexes for pg_class or pg_index it's not
+		 * sufficient to take a ShareLock on the respective table. While
+		 * reindexing those tables need to be modified, which requires a
+		 * RowExclusiveLock - which presents a form of an upgrade hazard (it
+		 * e.g. conflicts with ShareLock held by a concurrent REINDEX, but
+		 * other sessions could acquire a ShareLock themselves as ShareLock
+		 * doesn't self-conflict).  Thus, only when updating those system
+		 * tables, we have to take a lock that guarantees both a Share and
+		 * RowExclusive can be acquired.
+		 *
+		 * One might think that ShareRowExclusive lock is sufficient to
+		 * prevent such deadlock scenarios, but it's not. At least for
+		 * pg_class there's plenty other codepaths that, reasonably, expect to
+		 * be able to have an AccessShareLock on the table, and acquire
+		 * AccessShareLocks on its indexes.  That then otherwise could
+		 * deadlock with e.g. reindex_relation, which one-by-one locks indexes
+		 * with AccessExclusiveLock.  Therefore we need an
+		 * AccessExclusiveLock.
+		 */
+		return AccessExclusiveLock;
+	}
+	else
+		return ShareLock;
+}
+
 /*
  * Check permissions on table before acquiring relation lock; also lock
  * the heap before the RangeVarGetRelidExtended takes the index lock, to avoid
@@ -2350,7 +2403,7 @@ RangeVarCallbackForReindexIndex(const RangeVar *relation,
 								Oid relId, Oid oldRelId, void *arg)
 {
 	char		relkind;
-	Oid		   *heapOid = (Oid *) arg;
+	RVCReindexParams *params = (RVCReindexParams *) arg;
 
 	/*
 	 * If we previously locked some other index's heap, and the name we're
@@ -2360,8 +2413,10 @@ RangeVarCallbackForReindexIndex(const RangeVar *relation,
 	if (relId != oldRelId && OidIsValid(oldRelId))
 	{
 		/* lock level here should match reindex_index() heap lock */
-		UnlockRelationOid(*heapOid, ShareLock);
-		*heapOid = InvalidOid;
+		UnlockRelationOid(params->heapOid,
+						  table_lockmode_for_reindex(params->heapOid,
+													 params->concurrently));
+		params->heapOid = InvalidOid;
 	}
 
 	/* If the relation does not exist, there's nothing more to do. */
@@ -2394,9 +2449,54 @@ RangeVarCallbackForReindexIndex(const RangeVar *relation,
 		 * isn't valid, it means the index as concurrently dropped, which is
 		 * not a problem for us; just return normally.
 		 */
-		*heapOid = IndexGetRelation(relId, true);
-		if (OidIsValid(*heapOid))
-			LockRelationOid(*heapOid, ShareLock);
+		params->heapOid = IndexGetRelation(relId, true);
+		if (OidIsValid(params->heapOid))
+			LockRelationOid(params->heapOid,
+							table_lockmode_for_reindex(params->heapOid, params->concurrently));
+	}
+}
+
+static void
+RangeVarCallbackForReindexTable(const RangeVar *relation,
+								Oid relId, Oid oldRelId, void *arg)
+{
+	char		relkind;
+	RVCReindexParams *params = (RVCReindexParams *) arg;
+
+	if (relId != oldRelId && OidIsValid(oldRelId))
+	{
+		/* lock level here should match reindex_index() heap lock */
+		UnlockRelationOid(oldRelId,
+						  table_lockmode_for_reindex(oldRelId,
+													 params->concurrently));
+	}
+
+	/* If the relation does not exist, there's nothing more to do. */
+	if (!OidIsValid(relId))
+		return;
+
+	/*
+	 * If the relation does exist, check whether it's an index.  But note that
+	 * the relation might have been dropped between the time we did the name
+	 * lookup and now.  In that case, there's nothing to do.
+	 */
+	relkind = get_rel_relkind(relId);
+	if (!relkind)
+		return;
+	if (relkind != RELKIND_RELATION && relkind != RELKIND_TOASTVALUE &&
+		relkind != RELKIND_MATVIEW && relkind != RELKIND_PARTITIONED_TABLE)
+		ereport(ERROR,
+				(errcode(ERRCODE_WRONG_OBJECT_TYPE),
+				 errmsg("\"%s\" is not a table or materialized view", relation->relname)));
+
+	/* Check permissions */
+	if (!pg_class_ownercheck(relId, GetUserId()))
+		aclcheck_error(ACLCHECK_NOT_OWNER, get_relkind_objtype(get_rel_relkind(relId)), relation->relname);
+
+	if (relId != oldRelId)
+	{
+		LockRelationOid(relId,
+						table_lockmode_for_reindex(relId, params->concurrently));
 	}
 }
 
@@ -2408,13 +2508,24 @@ Oid
 ReindexTable(RangeVar *relation, int options, bool concurrent)
 {
 	Oid			heapOid;
+	RVCReindexParams params;
 	bool		result;
 
-	/* The lock level used here should match reindex_relation(). */
+	params.heapOid = InvalidOid;
+	params.concurrently = concurrent;
+
+	/*
+	 * While we have RangeVarGetRelidExtended only acquire a AccessShareLock,
+	 * RangeVarCallbackForReindexTable acquires the appropriate type of lock
+	 * (which depends on whether the target is a catalog table). Have to
+	 * acquire some lock via RangeVarGetRelidExtended, as it otherwise won't
+	 * do all the necessary concurrency-safe trickery (indicate via flag
+	 * instead?).
+	 */
 	heapOid = RangeVarGetRelidExtended(relation,
-									   concurrent ? ShareUpdateExclusiveLock : ShareLock,
+									   AccessShareLock,
 									   0,
-									   RangeVarCallbackOwnsTable, NULL);
+									   RangeVarCallbackForReindexTable, &params);
 
 	if (concurrent)
 		result = ReindexRelationConcurrently(heapOid, options);
