diff --git a/src/backend/catalog/index.c b/src/backend/catalog/index.c
index e9399be..0dbc410 100644
--- a/src/backend/catalog/index.c
+++ b/src/backend/catalog/index.c
@@ -185,12 +185,28 @@ relationHasPrimaryKey(Relation rel)
  *
  * We check for a pre-existing primary key, and that all columns of the index
  * are simple column references (not expressions), and that all those
- * columns are marked NOT NULL.  If they aren't (which can only happen during
- * ALTER TABLE ADD CONSTRAINT, since the parser forces such columns to be
- * created NOT NULL during CREATE TABLE), do an ALTER SET NOT NULL to mark
- * them so --- or fail if they are not in fact nonnull.
+ * columns are marked NOT NULL.
  *
- * As of PG v10, the SET NOT NULL is applied to child tables as well, so
+ * If any column is not so marked, then:
+ *
+ * 1. If we're in an ALTER TABLE, fail; the ALTER TABLE machinery should have
+ * already taken care of making it NOT NULL.  (Hence, we don't really expect
+ * to hit that error, but it seems wise to check anyway.)
+ *
+ * 2. Otherwise, perform our own ALTER TABLE to set such column(s) NOT NULL.
+ * We should not hit this case either, in simple CREATE TABLE cases, because
+ * the parser would've marked the columns NOT NULL to start with.  However,
+ * it is possible to hit the case in unusual scenarios, for example when the
+ * column is inherited from another table or from a composite type.
+ *
+ * The reason we don't try to do another ALTER TABLE when inside ALTER TABLE
+ * is that we don't know what else the outer ALTER TABLE might be doing, and
+ * we're quite likely to end up doing things in the wrong order.  Even if
+ * it worked reliably, it would be very inefficient, because we would be
+ * performing our own scan of the table in addition to whatever the outer
+ * ALTER TABLE might need to do.
+ *
+ * As of PG v10, SET NOT NULL is applied to child tables as well, so
  * that the behavior is like a manual SET NOT NULL.
  *
  * Caller had better have at least ShareLock on the table, else the not-null
@@ -206,8 +222,8 @@ index_check_primary_key(Relation heapRel,
 	int			i;
 
 	/*
-	 * If ALTER TABLE and CREATE TABLE .. PARTITION OF, check that there isn't
-	 * already a PRIMARY KEY.  In CREATE TABLE for an ordinary relations, we
+	 * If ALTER TABLE or CREATE TABLE .. PARTITION OF, check that there isn't
+	 * already a PRIMARY KEY.  In CREATE TABLE for an ordinary relation, we
 	 * have faith that the parser rejected multiple pkey clauses; and CREATE
 	 * INDEX doesn't have a way to say PRIMARY KEY, so it's no problem either.
 	 */
@@ -222,7 +238,7 @@ index_check_primary_key(Relation heapRel,
 
 	/*
 	 * Check that all of the attributes in a primary key are marked as not
-	 * null, otherwise attempt to ALTER TABLE .. SET NOT NULL
+	 * null, otherwise consider using ALTER TABLE .. SET NOT NULL.
 	 */
 	cmds = NIL;
 	for (i = 0; i < indexInfo->ii_NumIndexKeyAttrs; i++)
@@ -250,25 +266,32 @@ index_check_primary_key(Relation heapRel,
 
 		if (!attform->attnotnull)
 		{
-			/* Add a subcommand to make this one NOT NULL */
-			AlterTableCmd *cmd = makeNode(AlterTableCmd);
+			if (is_alter_table)
+			{
+				/* Complain, per comments above */
+				ereport(ERROR,
+						(errcode(ERRCODE_INVALID_TABLE_DEFINITION),
+						 errmsg("primary key column \"%s\" is not marked NOT NULL",
+								NameStr(attform->attname))));
+			}
+			else
+			{
+				/* Prepare a subcommand to make this one NOT NULL */
+				AlterTableCmd *cmd = makeNode(AlterTableCmd);
 
-			cmd->subtype = AT_SetNotNull;
-			cmd->name = pstrdup(NameStr(attform->attname));
-			cmds = lappend(cmds, cmd);
+				cmd->subtype = AT_SetNotNull;
+				cmd->name = pstrdup(NameStr(attform->attname));
+				cmds = lappend(cmds, cmd);
+			}
 		}
 
 		ReleaseSysCache(atttuple);
 	}
 
-	/*
-	 * XXX: possible future improvement: when being called from ALTER TABLE,
-	 * it would be more efficient to merge this with the outer ALTER TABLE, so
-	 * as to avoid two scans.  But that seems to complicate DefineIndex's API
-	 * unduly.
-	 */
+	/* Perform the internal ALTER TABLE if needed */
 	if (cmds)
 	{
+		Assert(!is_alter_table);
 		EventTriggerAlterTableStart((Node *) stmt);
 		AlterTableInternal(RelationGetRelid(heapRel), cmds, true);
 		EventTriggerAlterTableEnd();
diff --git a/src/backend/commands/tablecmds.c b/src/backend/commands/tablecmds.c
index d48a947..6209d6e 100644
--- a/src/backend/commands/tablecmds.c
+++ b/src/backend/commands/tablecmds.c
@@ -142,9 +142,9 @@ static List *on_commits = NIL;
 #define AT_PASS_ALTER_TYPE		1	/* ALTER COLUMN TYPE */
 #define AT_PASS_OLD_INDEX		2	/* re-add existing indexes */
 #define AT_PASS_OLD_CONSTR		3	/* re-add existing constraints */
-#define AT_PASS_COL_ATTRS		4	/* set other column attributes */
 /* We could support a RENAME COLUMN pass here, but not currently used */
-#define AT_PASS_ADD_COL			5	/* ADD COLUMN */
+#define AT_PASS_ADD_COL			4	/* ADD COLUMN */
+#define AT_PASS_COL_ATTRS		5	/* set other column attributes */
 #define AT_PASS_ADD_INDEX		6	/* ADD indexes */
 #define AT_PASS_ADD_CONSTR		7	/* ADD constraints, defaults */
 #define AT_PASS_MISC			8	/* other stuff */
@@ -370,9 +370,13 @@ static void add_column_datatype_dependency(Oid relid, int32 attnum, Oid typid);
 static void add_column_collation_dependency(Oid relid, int32 attnum, Oid collid);
 static void ATPrepDropNotNull(Relation rel, bool recurse, bool recursing);
 static ObjectAddress ATExecDropNotNull(Relation rel, const char *colName, LOCKMODE lockmode);
-static void ATPrepSetNotNull(Relation rel, bool recurse, bool recursing);
+static void ATPrepSetNotNull(List **wqueue, Relation rel,
+				 AlterTableCmd *cmd, bool recurse, bool recursing,
+				 LOCKMODE lockmode);
 static ObjectAddress ATExecSetNotNull(AlteredTableInfo *tab, Relation rel,
 				 const char *colName, LOCKMODE lockmode);
+static void ATExecCheckNotNull(AlteredTableInfo *tab, Relation rel,
+				   const char *colName, LOCKMODE lockmode);
 static bool NotNullImpliedByRelConstraints(Relation rel, Form_pg_attribute attr);
 static bool ConstraintImpliedByRelConstraint(Relation scanrel,
 									 List *partConstraint, List *existedConstraints);
@@ -3765,6 +3769,15 @@ AlterTableGetLockLevel(List *cmds)
 				cmd_lockmode = AccessExclusiveLock;
 				break;
 
+			case AT_CheckNotNull:
+
+				/*
+				 * This only examines the table's schema; but lock must be
+				 * strong enough to prevent concurrent DROP NOT NULL.
+				 */
+				cmd_lockmode = AccessShareLock;
+				break;
+
 			default:			/* oops */
 				elog(ERROR, "unrecognized alter table type: %d",
 					 (int) cmd->subtype);
@@ -3889,15 +3902,19 @@ ATPrepCmd(List **wqueue, Relation rel, AlterTableCmd *cmd,
 			ATSimplePermissions(rel, ATT_TABLE | ATT_FOREIGN_TABLE);
 			ATPrepDropNotNull(rel, recurse, recursing);
 			ATSimpleRecursion(wqueue, rel, cmd, recurse, lockmode);
-			/* No command-specific prep needed */
 			pass = AT_PASS_DROP;
 			break;
 		case AT_SetNotNull:		/* ALTER COLUMN SET NOT NULL */
 			ATSimplePermissions(rel, ATT_TABLE | ATT_FOREIGN_TABLE);
-			ATPrepSetNotNull(rel, recurse, recursing);
+			/* Need command-specific recursion decision */
+			ATPrepSetNotNull(wqueue, rel, cmd, recurse, recursing, lockmode);
+			pass = AT_PASS_COL_ATTRS;
+			break;
+		case AT_CheckNotNull:	/* check column is already marked NOT NULL */
+			ATSimplePermissions(rel, ATT_TABLE | ATT_FOREIGN_TABLE);
 			ATSimpleRecursion(wqueue, rel, cmd, recurse, lockmode);
 			/* No command-specific prep needed */
-			pass = AT_PASS_ADD_CONSTR;
+			pass = AT_PASS_COL_ATTRS;
 			break;
 		case AT_SetStatistics:	/* ALTER COLUMN SET STATISTICS */
 			ATSimpleRecursion(wqueue, rel, cmd, recurse, lockmode);
@@ -4214,6 +4231,9 @@ ATExecCmd(List **wqueue, AlteredTableInfo *tab, Relation rel,
 		case AT_SetNotNull:		/* ALTER COLUMN SET NOT NULL */
 			address = ATExecSetNotNull(tab, rel, cmd->name, lockmode);
 			break;
+		case AT_CheckNotNull:	/* check column is already marked NOT NULL */
+			ATExecCheckNotNull(tab, rel, cmd->name, lockmode);
+			break;
 		case AT_SetStatistics:	/* ALTER COLUMN SET STATISTICS */
 			address = ATExecSetStatistics(rel, cmd->name, cmd->num, cmd->def, lockmode);
 			break;
@@ -5990,6 +6010,7 @@ ATPrepDropNotNull(Relation rel, bool recurse, bool recursing)
 					 errhint("Do not specify the ONLY keyword.")));
 	}
 }
+
 static ObjectAddress
 ATExecDropNotNull(Relation rel, const char *colName, LOCKMODE lockmode)
 {
@@ -6116,23 +6137,33 @@ ATExecDropNotNull(Relation rel, const char *colName, LOCKMODE lockmode)
  */
 
 static void
-ATPrepSetNotNull(Relation rel, bool recurse, bool recursing)
+ATPrepSetNotNull(List **wqueue, Relation rel,
+				 AlterTableCmd *cmd, bool recurse, bool recursing,
+				 LOCKMODE lockmode)
 {
 	/*
-	 * If the parent is a partitioned table, like check constraints, NOT NULL
-	 * constraints must be added to the child tables.  Complain if requested
-	 * otherwise and partitions exist.
+	 * If we're already recursing, there's nothing to do; the topmost
+	 * invocation of ATSimpleRecursion already visited all children.
 	 */
-	if (rel->rd_rel->relkind == RELKIND_PARTITIONED_TABLE)
+	if (recursing)
+		return;
+
+	/*
+	 * If we have ALTER TABLE ONLY ... SET NOT NULL on a partitioned table,
+	 * apply ALTER TABLE ... CHECK NOT NULL to every child.  Otherwise, use
+	 * normal recursion logic.
+	 */
+	if (rel->rd_rel->relkind == RELKIND_PARTITIONED_TABLE &&
+		!recurse)
 	{
-		PartitionDesc partdesc = RelationGetPartitionDesc(rel);
+		AlterTableCmd *newcmd = makeNode(AlterTableCmd);
 
-		if (partdesc && partdesc->nparts > 0 && !recurse && !recursing)
-			ereport(ERROR,
-					(errcode(ERRCODE_INVALID_TABLE_DEFINITION),
-					 errmsg("cannot add constraint to only the partitioned table when partitions exist"),
-					 errhint("Do not specify the ONLY keyword.")));
+		newcmd->subtype = AT_CheckNotNull;
+		newcmd->name = pstrdup(cmd->name);
+		ATSimpleRecursion(wqueue, rel, newcmd, true, lockmode);
 	}
+	else
+		ATSimpleRecursion(wqueue, rel, cmd, recurse, lockmode);
 }
 
 /*
@@ -6208,6 +6239,46 @@ ATExecSetNotNull(AlteredTableInfo *tab, Relation rel,
 }
 
 /*
+ * ALTER TABLE ALTER COLUMN CHECK NOT NULL
+ *
+ * This doesn't exist in the grammar, but we generate AT_CheckNotNull
+ * commands against the partitions of a partitioned table if the user
+ * writes ALTER TABLE ONLY ... SET NOT NULL on the partitioned table,
+ * or tries to create a primary key on it (which internally creates
+ * AT_SetNotNull on the partitioned table).   Such a command doesn't
+ * allow us to actually modify any partition, but we want to let it
+ * go through if the partitions are already properly marked.
+ */
+static void
+ATExecCheckNotNull(AlteredTableInfo *tab, Relation rel,
+				   const char *colName, LOCKMODE lockmode)
+{
+	HeapTuple	tuple;
+
+	tuple = SearchSysCacheAttName(RelationGetRelid(rel), colName);
+
+	if (!HeapTupleIsValid(tuple))
+		ereport(ERROR,
+				(errcode(ERRCODE_UNDEFINED_COLUMN),
+				 errmsg("column \"%s\" of relation \"%s\" does not exist",
+						colName, RelationGetRelationName(rel))));
+
+	if (!((Form_pg_attribute) GETSTRUCT(tuple))->attnotnull)
+	{
+		/*
+		 * This error message may seem pretty inapropos, but it corresponds to
+		 * what we did in a previous implementation of this check.
+		 */
+		ereport(ERROR,
+				(errcode(ERRCODE_INVALID_TABLE_DEFINITION),
+				 errmsg("cannot add constraint to only the partitioned table when partitions exist"),
+				 errhint("Do not specify the ONLY keyword.")));
+	}
+
+	ReleaseSysCache(tuple);
+}
+
+/*
  * NotNullImpliedByRelConstraints
  *		Does rel's existing constraints imply NOT NULL for the given attribute?
  */
@@ -11269,6 +11340,16 @@ ATPostAlterTypeParse(Oid oldId, Oid oldRelId, Oid refRelId, char *cmd,
 											 NIL,
 											 con->conname);
 				}
+				else if (cmd->subtype == AT_SetNotNull)
+				{
+					/*
+					 * The parser will create AT_SetNotNull subcommands for
+					 * columns of PRIMARY KEY indexes/constraints, but we need
+					 * not do anything with them here, because the columns'
+					 * NOT NULL marks will already have been propagated into
+					 * the new table definition.
+					 */
+				}
 				else
 					elog(ERROR, "unexpected statement subtype: %d",
 						 (int) cmd->subtype);
diff --git a/src/backend/parser/parse_utilcmd.c b/src/backend/parser/parse_utilcmd.c
index 674f4b9..94bcd63 100644
--- a/src/backend/parser/parse_utilcmd.c
+++ b/src/backend/parser/parse_utilcmd.c
@@ -3236,13 +3236,36 @@ transformAlterTableStmt(Oid relid, AlterTableStmt *stmt,
 	 * Push any index-creation commands into the ALTER, so that they can be
 	 * scheduled nicely by tablecmds.c.  Note that tablecmds.c assumes that
 	 * the IndexStmt attached to an AT_AddIndex or AT_AddIndexConstraint
-	 * subcommand has already been through transformIndexStmt.
+	 * subcommand has already been through transformIndexStmt, and that any
+	 * NOT NULL constraints required for PRIMARY KEY indexes are handled by
+	 * earlier AT_SetNotNull commands.
 	 */
 	foreach(l, cxt.alist)
 	{
 		IndexStmt  *idxstmt = lfirst_node(IndexStmt, l);
 
 		idxstmt = transformIndexStmt(relid, idxstmt, queryString);
+
+		/*
+		 * If it's PRIMARY KEY, also insert SET NOT NULL commands for each
+		 * column.
+		 */
+		if (idxstmt->primary)
+		{
+			ListCell   *l2;
+
+			foreach(l2, idxstmt->indexParams)
+			{
+				IndexElem  *ielem = lfirst(l2);
+
+				Assert(ielem->name);	/* should not have any index exprs */
+				newcmd = makeNode(AlterTableCmd);
+				newcmd->subtype = AT_SetNotNull;
+				newcmd->name = pstrdup(ielem->name);
+				newcmds = lappend(newcmds, newcmd);
+			}
+		}
+
 		newcmd = makeNode(AlterTableCmd);
 		newcmd->subtype = OidIsValid(idxstmt->indexOid) ? AT_AddIndexConstraint : AT_AddIndex;
 		newcmd->def = (Node *) idxstmt;
diff --git a/src/include/nodes/parsenodes.h b/src/include/nodes/parsenodes.h
index 94c0b7a..462237d 100644
--- a/src/include/nodes/parsenodes.h
+++ b/src/include/nodes/parsenodes.h
@@ -1764,6 +1764,7 @@ typedef enum AlterTableType
 	AT_ColumnDefault,			/* alter column default */
 	AT_DropNotNull,				/* alter column drop not null */
 	AT_SetNotNull,				/* alter column set not null */
+	AT_CheckNotNull,			/* check column is already marked not null */
 	AT_SetStatistics,			/* alter column set statistics */
 	AT_SetOptions,				/* alter column set ( options ) */
 	AT_ResetOptions,			/* alter column reset ( options ) */
diff --git a/src/test/modules/test_ddl_deparse/expected/alter_table.out b/src/test/modules/test_ddl_deparse/expected/alter_table.out
index 7da847d..141060f 100644
--- a/src/test/modules/test_ddl_deparse/expected/alter_table.out
+++ b/src/test/modules/test_ddl_deparse/expected/alter_table.out
@@ -23,8 +23,7 @@ NOTICE:  DDL test: type simple, tag CREATE TABLE
 CREATE TABLE part1 PARTITION OF part FOR VALUES FROM (1) to (100);
 NOTICE:  DDL test: type simple, tag CREATE TABLE
 ALTER TABLE part ADD PRIMARY KEY (a);
-NOTICE:  DDL test: type alter table, tag CREATE INDEX
+NOTICE:  DDL test: type alter table, tag ALTER TABLE
 NOTICE:    subcommand: SET NOT NULL
 NOTICE:    subcommand: SET NOT NULL
-NOTICE:  DDL test: type alter table, tag ALTER TABLE
 NOTICE:    subcommand: ADD INDEX
diff --git a/src/test/modules/test_ddl_deparse/test_ddl_deparse.c b/src/test/modules/test_ddl_deparse/test_ddl_deparse.c
index 2fe0c24..7f77f19 100644
--- a/src/test/modules/test_ddl_deparse/test_ddl_deparse.c
+++ b/src/test/modules/test_ddl_deparse/test_ddl_deparse.c
@@ -117,6 +117,9 @@ get_altertable_subcmdtypes(PG_FUNCTION_ARGS)
 			case AT_SetNotNull:
 				strtype = "SET NOT NULL";
 				break;
+			case AT_CheckNotNull:
+				strtype = "CHECK NOT NULL";
+				break;
 			case AT_SetStatistics:
 				strtype = "SET STATS";
 				break;
diff --git a/src/test/regress/expected/alter_table.out b/src/test/regress/expected/alter_table.out
index 2a26aa3..aa80038 100644
--- a/src/test/regress/expected/alter_table.out
+++ b/src/test/regress/expected/alter_table.out
@@ -978,7 +978,7 @@ drop table atacc1;
 create table atacc1 ( test int );
 -- add a primary key constraint (fails)
 alter table atacc1 add constraint atacc_test1 primary key (test1);
-ERROR:  column "test1" named in key does not exist
+ERROR:  column "test1" of relation "atacc1" does not exist
 drop table atacc1;
 -- adding a new column as primary key to a non-empty table.
 -- should fail unless the column has a non-null default value.
@@ -1404,9 +1404,9 @@ ERROR:  column "a" does not exist
 alter table atacc1 rename "........pg.dropped.1........" to x;
 ERROR:  column "........pg.dropped.1........" does not exist
 alter table atacc1 add primary key(a);
-ERROR:  column "a" named in key does not exist
+ERROR:  column "a" of relation "atacc1" does not exist
 alter table atacc1 add primary key("........pg.dropped.1........");
-ERROR:  column "........pg.dropped.1........" named in key does not exist
+ERROR:  column "........pg.dropped.1........" of relation "atacc1" does not exist
 alter table atacc1 add unique(a);
 ERROR:  column "a" named in key does not exist
 alter table atacc1 add unique("........pg.dropped.1........");
