using index to speedup add not null constraints to a table

From ac1ec78395479c61844e122c90ef26d545d35f69 Mon Sep 17 00:00:00 2001
From: jian he <jian.universality@gmail.com>
Date: Tue, 31 Dec 2024 23:32:49 +0800
Subject: [PATCH v2 1/1] using index to speedup add not null constraint to
 existing table

This patch tries to use index_beginscan() / index_getnext() / index_endscan()
mentioned in [1] to speedup adding not-null constraints to the existing table.

There are two ways to add not-null constraints to an existing table.
1. ATExecAddConstraint->ATAddCheckNNConstraint->AddRelationNewConstraints
2. ATExecSetNotNull->AddRelationNewConstraints

The logic is:
1. In AddRelationNewConstraints, if condition meet (see get_index_for_validate_notnull)
   then attempt to use indexscan to pre check whether the column is NOT NULL.
2. AddRelationNewConstraints returned a list of CookedConstraint nodes.
   pass not-null cooked constraint to tab->constraints (a list of NewConstraint).
   code snippet:
    if (!ccon->skip_validation)
    {
        newcon = (NewConstraint *) palloc0(sizeof(NewConstraint));
        if (ccon->pre_validated)
            newcon->nn_attnum = ccon->attnum;
        tab->constraints = lappend(tab->constraints, newcon);
    }
3. In ATRewriteTable, if all attnums associated with not-null constraint have
already been prevalidated, then no need to needscan.

CAUTION:
ALTER TABLE SET DATA TYPE and ALTER TABLE SET EXPRESSION trigger an index
rebuild (refer to RememberAllDependentForRebuilding).  While the former cannot
be applied to partitioned tables, the latter can.  If an index rebuild occurs,
then indexscan cannot be used to prevalidate whether a column contains null
values.  Consequently, pre-validating a NOT NULL constraint is currently not
supported for partitioned tables.

concurrency concern:
ALTER TABLE SET NOT NULL will take an ACCESS EXCLUSIVE lock, so there is less
variant of racing issue can occur?  to prove accurate, I wrote some isolation
tests. see[2]

performance concern:
it will be slower than normal adding not-null constraint ONLY IF your index is
bloat and a large percent of bloat is related to null value data.
demo:

100% bloat and zero percent null value:
drop table if exists t \; create unlogged table t(a int, b int, c int);
insert into t select g, g+1 from generate_series(1,1_000_000) g;
create index t_idx_a on t(a);
delete from t;
alter table t add constraint t1 not null a;

patch Time:  1.873 ms
master Time: 648.312 ms
----------------------------------------------------
---- %20 percent column value is null and deleted from heap still on the index.
drop table if exists t \; create unlogged table t(a int, b int);
insert into t select case when g % 5 = 0 then null else g end, g+1
from generate_series(1,1_000_000) g;

create index t_idx_a on t(a);
delete from t where a is null;

alter table t add constraint t1 not null a;
patch Time:: 1080.407 ms (00:01.080)
master Time: 970.671 ms

references:
[1] https://postgr.es/m/CA%2BTgmoa5NKz8iGW_9v7wz%3D-%2BzQFu%3DE4SZoaTaU1znLaEXRYp-Q%40mail.gmail.com
[2] https://postgr.es/m/900056D1-32DF-4927-8251-3E0C0DC407FD%40anarazel.de

discussion: https://postgr.es/m/CACJufxFiW=4k1is=F1J=r-Cx1RuByXQPUrWB331U47rSnGz+hw@mail.gmail.com
---
 src/backend/catalog/heap.c                    |  88 +++++++++++-
 src/backend/catalog/pg_constraint.c           |   1 +
 src/backend/commands/tablecmds.c              |  80 +++++++++--
 src/backend/executor/execIndexing.c           |  93 ++++++++++++
 src/include/catalog/heap.h                    |   2 +
 src/include/executor/executor.h               |   1 +
 .../isolation/expected/fast-set-notnull.out   | 133 ++++++++++++++++++
 src/test/isolation/isolation_schedule         |   1 +
 .../isolation/specs/fast-set-notnull.spec     |  46 ++++++
 src/test/regress/expected/alter_table.out     |  38 +++++
 src/test/regress/sql/alter_table.sql          |  43 ++++++
 11 files changed, 516 insertions(+), 10 deletions(-)
 create mode 100644 src/test/isolation/expected/fast-set-notnull.out
 create mode 100644 src/test/isolation/specs/fast-set-notnull.spec

diff --git a/src/backend/catalog/heap.c b/src/backend/catalog/heap.c
index d7b88b61dc..7994b0c480 100644
--- a/src/backend/catalog/heap.c
+++ b/src/backend/catalog/heap.c
@@ -57,6 +57,7 @@
 #include "commands/tablecmds.h"
 #include "commands/typecmds.h"
 #include "common/int.h"
+#include "executor/executor.h"
 #include "miscadmin.h"
 #include "nodes/nodeFuncs.h"
 #include "optimizer/optimizer.h"
@@ -116,6 +117,7 @@ static Node *cookConstraint(ParseState *pstate,
 							char *relname);
 
 
+static Oid get_index_for_validate_notnull(Relation rel, int colnum);
 /* ----------------------------------------------------------------
  *				XXX UGLY HARD CODED BADNESS FOLLOWS XXX
  *
@@ -2298,6 +2300,8 @@ StoreConstraints(Relation rel, List *cooked_constraints, bool is_internal)
  * newConstraints: list of Constraint nodes
  * allow_merge: true if check constraints may be merged with existing ones
  * is_local: true if definition is local, false if it's inherited
+ * index_rebuild: true if the ALTER TABLE command and it's subcommands
+ * will do any index rebuild in the future.
  * is_internal: true if result of some internal process, not a user request
  * queryString: used during expression transformation of default values and
  *		cooked CHECK constraints
@@ -2322,6 +2326,7 @@ AddRelationNewConstraints(Relation rel,
 						  bool allow_merge,
 						  bool is_local,
 						  bool is_internal,
+						  bool index_rebuild,
 						  const char *queryString)
 {
 	List	   *cookedConstraints = NIL;
@@ -2409,6 +2414,7 @@ AddRelationNewConstraints(Relation rel,
 		cooked->is_local = is_local;
 		cooked->inhcount = is_local ? 0 : 1;
 		cooked->is_no_inherit = false;
+		cooked->pre_validated = false;
 		cookedConstraints = lappend(cookedConstraints, cooked);
 	}
 
@@ -2539,6 +2545,7 @@ AddRelationNewConstraints(Relation rel,
 			cooked->is_local = is_local;
 			cooked->inhcount = is_local ? 0 : 1;
 			cooked->is_no_inherit = cdef->is_no_inherit;
+			cooked->pre_validated = false;
 			cookedConstraints = lappend(cookedConstraints, cooked);
 		}
 		else if (cdef->contype == CONSTR_NOTNULL)
@@ -2547,6 +2554,7 @@ AddRelationNewConstraints(Relation rel,
 			AttrNumber	colnum;
 			int16		inhcount = is_local ? 0 : 1;
 			char	   *nnname;
+			Oid			indexoid = InvalidOid;
 
 			/* Determine which column to modify */
 			colnum = get_attnum(RelationGetRelid(rel), strVal(linitial(cdef->keys)));
@@ -2599,6 +2607,16 @@ AddRelationNewConstraints(Relation rel,
 								inhcount,
 								cdef->is_no_inherit);
 
+			/*
+			 * if there is any index to be rebuild, then we cannot do indexscan
+			 * in index_check_notnull; for re_added (is_internal is true)
+			 * not-null constraint also cannot use indexscan to check null
+			 * existence.
+			*/
+			if (rel->rd_rel->relkind == RELKIND_RELATION &&
+				!is_internal &&
+				!index_rebuild)
+				indexoid = get_index_for_validate_notnull(rel, colnum);
 			nncooked = (CookedConstraint *) palloc(sizeof(CookedConstraint));
 			nncooked->contype = CONSTR_NOTNULL;
 			nncooked->conoid = constrOid;
@@ -2609,7 +2627,17 @@ AddRelationNewConstraints(Relation rel,
 			nncooked->is_local = is_local;
 			nncooked->inhcount = inhcount;
 			nncooked->is_no_inherit = cdef->is_no_inherit;
-
+			nncooked->pre_validated = false;
+			if (OidIsValid(indexoid))
+			{
+				nncooked->pre_validated =
+						index_check_notnull(RelationGetRelid(rel),
+											indexoid,
+											colnum);
+			}
+			if (nncooked->pre_validated)
+				elog(DEBUG1, "already using index (%d) vertified that relation \"%s\" column number (%d) don't have null values",
+							  indexoid, RelationGetRelationName(rel), colnum);
 			cookedConstraints = lappend(cookedConstraints, nncooked);
 		}
 	}
@@ -2626,6 +2654,64 @@ AddRelationNewConstraints(Relation rel,
 	return cookedConstraints;
 }
 
+static Oid
+get_index_for_validate_notnull(Relation relation, int colnum)
+{
+	Relation	indrel;
+	SysScanDesc indscan;
+	ScanKeyData skey;
+	HeapTuple	htup;
+	TupleDesc	tupdesc;
+	Form_pg_attribute attr;
+	List	   *result = NIL;
+
+	tupdesc = RelationGetDescr(relation);
+
+	/* Prepare to scan pg_index for entries having indrelid = this rel. */
+	ScanKeyInit(&skey,
+				Anum_pg_index_indrelid,
+				BTEqualStrategyNumber, F_OIDEQ,
+				ObjectIdGetDatum(RelationGetRelid(relation)));
+
+	indrel = table_open(IndexRelationId, AccessShareLock);
+	indscan = systable_beginscan(indrel, IndexIndrelidIndexId, true,
+								 NULL, 1, &skey);
+
+	while (HeapTupleIsValid(htup = systable_getnext(indscan)))
+	{
+		Form_pg_index index = (Form_pg_index) GETSTRUCT(htup);
+
+		if (!index->indimmediate || !index->indisvalid || !index->indislive)
+			continue;
+
+		if (!heap_attisnull(htup, Anum_pg_index_indexprs, NULL) ||
+			!heap_attisnull(htup, Anum_pg_index_indpred, NULL))
+			continue;
+
+		for (int i = 0; i < index->indnkeyatts; i++)
+		{
+			attr = TupleDescAttr(tupdesc, (index->indkey.values[i]) - 1);
+			if (attr->attnum == colnum)
+			{
+				Assert(OidIsValid(index->indexrelid));
+				result = lappend_oid(result, index->indexrelid);
+				break;
+			}
+		}
+	}
+	systable_endscan(indscan);
+	table_close(indrel, AccessShareLock);
+
+	if(list_length(result) == 0)
+		return InvalidOid;
+	else
+	{
+		/* Sort the result list into OID order, make the result stable. */
+		list_sort(result, list_oid_cmp);
+		return list_nth_oid(result, 0);
+	}
+}
+
 /*
  * Check for a pre-existing check constraint that conflicts with a proposed
  * new one, and either adjust its conislocal/coninhcount settings or throw
diff --git a/src/backend/catalog/pg_constraint.c b/src/backend/catalog/pg_constraint.c
index 9c05a98d28..6638f1fbe2 100644
--- a/src/backend/catalog/pg_constraint.c
+++ b/src/backend/catalog/pg_constraint.c
@@ -826,6 +826,7 @@ RelationGetNotNullConstraints(Oid relid, bool cooked, bool include_noinh)
 			cooked->is_local = true;
 			cooked->inhcount = 0;
 			cooked->is_no_inherit = conForm->connoinherit;
+			cooked->pre_validated = false;
 
 			notnulls = lappend(notnulls, cooked);
 		}
diff --git a/src/backend/commands/tablecmds.c b/src/backend/commands/tablecmds.c
index 6ccae4cb4a..edaa4daca6 100644
--- a/src/backend/commands/tablecmds.c
+++ b/src/backend/commands/tablecmds.c
@@ -219,6 +219,8 @@ typedef struct NewConstraint
 	Oid			refindid;		/* OID of PK's index, if FOREIGN */
 	bool		conwithperiod;	/* Whether the new FOREIGN KEY uses PERIOD */
 	Oid			conid;			/* OID of pg_constraint entry, if FOREIGN */
+	int			nn_attnum;		/* already validated NOT-NULL constraint attnum.
+									-1 means not applicable */
 	Node	   *qual;			/* Check expr or CONSTR_FOREIGN Constraint */
 	ExprState  *qualstate;		/* Execution state for CHECK expr */
 } NewConstraint;
@@ -977,6 +979,7 @@ DefineRelation(CreateStmt *stmt, char relkind, Oid ownerId,
 			cooked->is_local = true;	/* not used for defaults */
 			cooked->inhcount = 0;	/* ditto */
 			cooked->is_no_inherit = false;
+			cooked->pre_validated = false;
 			cookedDefaults = lappend(cookedDefaults, cooked);
 			attr->atthasdef = true;
 		}
@@ -1060,7 +1063,7 @@ DefineRelation(CreateStmt *stmt, char relkind, Oid ownerId,
 	 */
 	if (rawDefaults)
 		AddRelationNewConstraints(rel, rawDefaults, NIL,
-								  true, true, false, queryString);
+								  true, true, false, false, queryString);
 
 	/*
 	 * Make column generation expressions visible for use by partitioning.
@@ -1291,7 +1294,7 @@ DefineRelation(CreateStmt *stmt, char relkind, Oid ownerId,
 	 */
 	if (stmt->constraints)
 		AddRelationNewConstraints(rel, NIL, stmt->constraints,
-								  true, true, false, queryString);
+								  true, true, false, false, queryString);
 
 	/*
 	 * Finally, merge the not-null constraints that are declared directly with
@@ -6038,6 +6041,7 @@ ATRewriteTable(AlteredTableInfo *tab, Oid OIDNewHeap, LOCKMODE lockmode)
 	TupleDesc	oldTupDesc;
 	TupleDesc	newTupDesc;
 	bool		needscan = false;
+	bool		prevalidated = true;
 	List	   *notnull_attrs;
 	int			i;
 	ListCell   *l;
@@ -6095,6 +6099,11 @@ ATRewriteTable(AlteredTableInfo *tab, Oid OIDNewHeap, LOCKMODE lockmode)
 				needscan = true;
 				con->qualstate = ExecPrepareExpr((Expr *) con->qual, estate);
 				break;
+
+			case CONSTR_NOTNULL:
+				if(con->nn_attnum == -1)
+					prevalidated = false;
+				break;
 			case CONSTR_FOREIGN:
 				/* Nothing to do here */
 				break;
@@ -6134,7 +6143,12 @@ ATRewriteTable(AlteredTableInfo *tab, Oid OIDNewHeap, LOCKMODE lockmode)
 			if (attr->attnotnull && !attr->attisdropped)
 				notnull_attrs = lappend_int(notnull_attrs, i);
 		}
-		if (notnull_attrs)
+
+		/*
+		 * we did some prevalidation at phase 2, so we can safely be sure no
+		 * need to scan. see AddRelationNewConstraints and index_check_notnull
+		*/
+		if (notnull_attrs && !prevalidated)
 			needscan = true;
 	}
 
@@ -7280,7 +7294,7 @@ ATExecAddColumn(List **wqueue, AlteredTableInfo *tab, Relation rel,
 		 * _list_ of defaults, but we just do one.
 		 */
 		AddRelationNewConstraints(rel, list_make1(rawEnt), NIL,
-								  false, true, false, NULL);
+								  false, true, false, false, NULL);
 
 		/* Make the additional catalog changes visible */
 		CommandCounterIncrement();
@@ -7722,6 +7736,8 @@ ATExecSetNotNull(List **wqueue, Relation rel, char *conName, char *colName,
 	CookedConstraint *ccon;
 	List	   *cooked;
 	bool		is_no_inherit = false;
+	bool		index_rebuild = false;
+	AlteredTableInfo *tab = NULL;
 
 	/* Guard against stack overflow due to overly deep inheritance tree. */
 	check_stack_depth();
@@ -7837,10 +7853,44 @@ ATExecSetNotNull(List **wqueue, Relation rel, char *conName, char *colName,
 	constraint->is_no_inherit = is_no_inherit;
 	constraint->conname = conName;
 
+	/*
+	 * for ALTER TABLE ALTER COLUMN SET EXPRESSION, RememberIndexForRebuilding
+	 * can only remember the partitioned index entry
+	 * (RELKIND_PARTITIONED_INDEX), not the regular index
+	 * (RELKIND_PARTITIONED_INDEX). So we can not use index_check_notnull to
+	 * fast check the column not-null status for the partitioned table now.
+	 * that is why if recursing is true, we blindly assume index_rebuild is
+	 * true.  in future, we can iterate changedIndexOids, find out if there is
+	 * any index over that not-null column or not.
+	 */
+	tab = ATGetQueueEntry(wqueue, rel);
+	if (list_length(tab->changedIndexOids) > 0 || recursing)
+		index_rebuild = true;
+
 	/* and do it */
 	cooked = AddRelationNewConstraints(rel, NIL, list_make1(constraint),
-									   false, !recursing, false, NULL);
+									   false, !recursing, false, index_rebuild, NULL);
 	ccon = linitial(cooked);
+
+	if (!ccon->skip_validation)
+	{
+		NewConstraint *newcon;
+
+		newcon = (NewConstraint *) palloc0(sizeof(NewConstraint));
+		newcon->name = ccon->name;
+		newcon->contype = ccon->contype;
+		if (ccon->pre_validated)
+		{
+			newcon->nn_attnum = ccon->attnum;
+			Assert(ccon->attnum > 0);
+		}
+		else
+			newcon->nn_attnum = -1;
+		newcon->qual = NULL;
+
+		tab->constraints = lappend(tab->constraints, newcon);
+	}
+
 	ObjectAddressSet(address, ConstraintRelationId, ccon->conoid);
 
 	InvokeObjectPostAlterHook(RelationRelationId,
@@ -7988,7 +8038,7 @@ ATExecColumnDefault(Relation rel, const char *colName,
 		 * _list_ of defaults, but we just do one.
 		 */
 		AddRelationNewConstraints(rel, list_make1(rawEnt), NIL,
-								  false, true, false, NULL);
+								  false, true, false, false, NULL);
 	}
 
 	ObjectAddressSubSet(address, RelationRelationId,
@@ -8450,7 +8500,7 @@ ATExecSetExpression(AlteredTableInfo *tab, Relation rel, const char *colName,
 
 	/* Store the generated expression */
 	AddRelationNewConstraints(rel, list_make1(rawEnt), NIL,
-							  false, true, false, NULL);
+							  false, true, false, false, NULL);
 
 	/* Make above new expression visible */
 	CommandCounterIncrement();
@@ -9554,6 +9604,10 @@ ATAddCheckNNConstraint(List **wqueue, AlteredTableInfo *tab, Relation rel,
 	List	   *children;
 	ListCell   *child;
 	ObjectAddress address = InvalidObjectAddress;
+	bool		index_rebuild = false;
+
+	if (list_length(tab->changedIndexOids) > 0 || recursing)
+		index_rebuild = true;
 
 	/* Guard against stack overflow due to overly deep inheritance tree. */
 	check_stack_depth();
@@ -9578,6 +9632,7 @@ ATAddCheckNNConstraint(List **wqueue, AlteredTableInfo *tab, Relation rel,
 										recursing || is_readd,	/* allow_merge */
 										!recursing, /* is_local */
 										is_readd,	/* is_internal */
+										index_rebuild,
 										NULL);	/* queryString not available
 												 * here */
 
@@ -9589,15 +9644,19 @@ ATAddCheckNNConstraint(List **wqueue, AlteredTableInfo *tab, Relation rel,
 	{
 		CookedConstraint *ccon = (CookedConstraint *) lfirst(lcon);
 
-		if (!ccon->skip_validation && ccon->contype != CONSTR_NOTNULL)
+		if (!ccon->skip_validation)
 		{
 			NewConstraint *newcon;
 
 			newcon = (NewConstraint *) palloc0(sizeof(NewConstraint));
 			newcon->name = ccon->name;
 			newcon->contype = ccon->contype;
+			if (ccon->pre_validated && ccon->contype == CONSTR_NOTNULL)
+				newcon->nn_attnum = ccon->attnum;
+			else
+				newcon->nn_attnum = -1;
+
 			newcon->qual = ccon->expr;
-
 			tab->constraints = lappend(tab->constraints, newcon);
 		}
 
@@ -10718,6 +10777,7 @@ addFkRecurseReferencing(List **wqueue, Constraint *fkconstraint, Relation rel,
 			newcon->refindid = indexOid;
 			newcon->conid = parentConstr;
 			newcon->conwithperiod = fkconstraint->fk_with_period;
+			newcon->nn_attnum = -1;
 			newcon->qual = (Node *) fkconstraint;
 
 			tab->constraints = lappend(tab->constraints, newcon);
@@ -12026,6 +12086,7 @@ ATExecValidateConstraint(List **wqueue, Relation rel, char *constrName,
 			newcon->refrelid = con->confrelid;
 			newcon->refindid = con->conindid;
 			newcon->conid = con->oid;
+			newcon->nn_attnum = -1;
 			newcon->qual = (Node *) fkconstraint;
 
 			/* Find or create work queue entry for this table */
@@ -12098,6 +12159,7 @@ ATExecValidateConstraint(List **wqueue, Relation rel, char *constrName,
 
 			val = SysCacheGetAttrNotNull(CONSTROID, tuple,
 										 Anum_pg_constraint_conbin);
+			newcon->nn_attnum = -1;
 			conbin = TextDatumGetCString(val);
 			newcon->qual = (Node *) stringToNode(conbin);
 
diff --git a/src/backend/executor/execIndexing.c b/src/backend/executor/execIndexing.c
index f0a5f8879a..37a7d3a96d 100644
--- a/src/backend/executor/execIndexing.c
+++ b/src/backend/executor/execIndexing.c
@@ -108,6 +108,7 @@
 
 #include "access/genam.h"
 #include "access/relscan.h"
+#include "access/table.h"
 #include "access/tableam.h"
 #include "access/xact.h"
 #include "catalog/index.h"
@@ -1166,3 +1167,95 @@ ExecWithoutOverlapsNotEmpty(Relation rel, NameData attname, Datum attval, char t
 				 errmsg("empty WITHOUT OVERLAPS value found in column \"%s\" in relation \"%s\"",
 						NameStr(attname), RelationGetRelationName(rel))));
 }
+
+bool
+index_check_notnull(Oid table_oid, Oid indexoid, AttrNumber colnum)
+{
+	Relation index;
+	Relation heap;
+
+	SnapshotData DirtySnapshot;
+	IndexScanDesc index_scan;
+	ScanKeyData scankeys[INDEX_MAX_KEYS];
+	TupleTableSlot *existing_slot;
+	IndexInfo  *indexInfo;
+	EState	   *estate;
+	int			indnkeyatts;
+	ExprContext *econtext;
+	bool all_not_null = true;
+	AttrNumber	sk_attno = -1;
+
+	heap = table_open(table_oid, NoLock);
+	index = index_open(indexoid, AccessShareLock);
+	/*
+	 * Need an EState for slot to hold the current tuple.
+	 *
+	 */
+	estate = CreateExecutorState();
+	econtext = GetPerTupleExprContext(estate);
+	existing_slot = table_slot_create(heap, NULL);
+
+	/* Arrange for econtext's scan tuple to be the tuple under test */
+	econtext->ecxt_scantuple = existing_slot;
+
+	indexInfo = BuildIndexInfo(index);
+	indnkeyatts = IndexRelationGetNumberOfKeyAttributes(index);
+
+	/*
+	 * Search the tuples that are in the index for any violations, including
+	 * tuples that aren't visible yet.
+	 */
+	InitDirtySnapshot(DirtySnapshot);
+
+	for (int i = 0; i < indnkeyatts; i++)
+	{
+		if (indexInfo->ii_IndexAttrNumbers[i] == colnum)
+		{
+			sk_attno = i+1;
+			break;
+		}
+	}
+
+	if (sk_attno == -1)
+		elog(ERROR, "index %u should effect on column number %d", indexoid, colnum);
+
+	for (int i = 0; i < indnkeyatts; i++)
+	{
+		/* set up an IS NULL scan key so that we ignore not nulls */
+		ScanKeyEntryInitialize(&scankeys[i],
+								SK_ISNULL | SK_SEARCHNULL,
+								sk_attno,		/* index col to scan */
+								InvalidStrategy,/* no strategy */
+								InvalidOid,		/* no strategy subtype */
+								InvalidOid,		/* no collation */
+								InvalidOid,		/* no reg proc for this */
+								(Datum) 0);		/* constant */
+	}
+
+	index_scan = index_beginscan(heap, index, &DirtySnapshot, indnkeyatts, 0);
+	index_rescan(index_scan, scankeys, indnkeyatts, NULL, 0);
+	while (index_getnext_slot(index_scan, ForwardScanDirection, existing_slot))
+	{
+		Datum		values[INDEX_MAX_KEYS];
+		bool		nulls[INDEX_MAX_KEYS];
+
+		/*
+		 * Extract the index column values and isnull flags from the existing
+		 * tuple.
+		 */
+		FormIndexDatum(indexInfo, existing_slot, estate, values, nulls);
+
+		if (nulls[sk_attno - 1])
+		{
+			all_not_null = false;
+			break;
+		}
+	}
+	index_endscan(index_scan);
+	table_close(heap, NoLock);
+	index_close(index, AccessShareLock);
+	ExecDropSingleTupleTableSlot(existing_slot);
+	FreeExecutorState(estate);
+
+	return all_not_null;
+}
\ No newline at end of file
diff --git a/src/include/catalog/heap.h b/src/include/catalog/heap.h
index 8c278f202b..45e2dd1cfa 100644
--- a/src/include/catalog/heap.h
+++ b/src/include/catalog/heap.h
@@ -45,6 +45,7 @@ typedef struct CookedConstraint
 	int16		inhcount;		/* number of times constraint is inherited */
 	bool		is_no_inherit;	/* constraint has local def and cannot be
 								 * inherited */
+	bool		pre_validated;  /* the constraint already validated? only for CONSTR_NOTNULL */
 } CookedConstraint;
 
 extern Relation heap_create(const char *relname,
@@ -113,6 +114,7 @@ extern List *AddRelationNewConstraints(Relation rel,
 									   bool allow_merge,
 									   bool is_local,
 									   bool is_internal,
+									   bool index_rebuild,
 									   const char *queryString);
 extern List *AddRelationNotNullConstraints(Relation rel,
 										   List *constraints,
diff --git a/src/include/executor/executor.h b/src/include/executor/executor.h
index 494ec4f2e5..355c3c192d 100644
--- a/src/include/executor/executor.h
+++ b/src/include/executor/executor.h
@@ -662,6 +662,7 @@ extern void check_exclusion_constraint(Relation heap, Relation index,
 									   const Datum *values, const bool *isnull,
 									   EState *estate, bool newIndex);
 
+extern bool index_check_notnull(Oid heap, Oid indexoid, AttrNumber colnum);
 /*
  * prototypes from functions in execReplication.c
  */
diff --git a/src/test/isolation/expected/fast-set-notnull.out b/src/test/isolation/expected/fast-set-notnull.out
new file mode 100644
index 0000000000..826f1dbe51
--- /dev/null
+++ b/src/test/isolation/expected/fast-set-notnull.out
@@ -0,0 +1,133 @@
+Parsed test spec with 2 sessions
+
+starting permutation: b1 m1 s0 s1 s2 r1 s2
+step b1: BEGIN ISOLATION LEVEL READ COMMITTED;
+step m1: DELETE FROM t;
+step s0: savepoint s0;
+step s1: ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a;
+step s2: SELECT conname, conrelid::regclass, contype, convalidated
+           FROM pg_constraint WHERE conname = 't1_nn';
+
+conname|conrelid|contype|convalidated
+-------+--------+-------+------------
+t1_nn  |t       |n      |t           
+(1 row)
+
+step r1: ROLLBACK;
+step s2: SELECT conname, conrelid::regclass, contype, convalidated
+           FROM pg_constraint WHERE conname = 't1_nn';
+
+conname|conrelid|contype|convalidated
+-------+--------+-------+------------
+(0 rows)
+
+
+starting permutation: b1 m1 s0 s1 s2 c1 s2
+step b1: BEGIN ISOLATION LEVEL READ COMMITTED;
+step m1: DELETE FROM t;
+step s0: savepoint s0;
+step s1: ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a;
+step s2: SELECT conname, conrelid::regclass, contype, convalidated
+           FROM pg_constraint WHERE conname = 't1_nn';
+
+conname|conrelid|contype|convalidated
+-------+--------+-------+------------
+t1_nn  |t       |n      |t           
+(1 row)
+
+step c1: COMMIT;
+step s2: SELECT conname, conrelid::regclass, contype, convalidated
+           FROM pg_constraint WHERE conname = 't1_nn';
+
+conname|conrelid|contype|convalidated
+-------+--------+-------+------------
+t1_nn  |t       |n      |t           
+(1 row)
+
+
+starting permutation: b1 b3 m1 hj c1 c3 s2
+step b1: BEGIN ISOLATION LEVEL READ COMMITTED;
+step b3: BEGIN ISOLATION LEVEL READ COMMITTED;
+step m1: DELETE FROM t;
+step hj: ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a; <waiting ...>
+step c1: COMMIT;
+step hj: <... completed>
+step c3: COMMIT;
+step s2: SELECT conname, conrelid::regclass, contype, convalidated
+           FROM pg_constraint WHERE conname = 't1_nn';
+
+conname|conrelid|contype|convalidated
+-------+--------+-------+------------
+t1_nn  |t       |n      |t           
+(1 row)
+
+
+starting permutation: b2 b4 m1 hj c1 c3 s2
+step b2: BEGIN;
+step b4: BEGIN;
+step m1: DELETE FROM t;
+step hj: ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a; <waiting ...>
+step c1: COMMIT;
+step hj: <... completed>
+step c3: COMMIT;
+step s2: SELECT conname, conrelid::regclass, contype, convalidated
+           FROM pg_constraint WHERE conname = 't1_nn';
+
+conname|conrelid|contype|convalidated
+-------+--------+-------+------------
+t1_nn  |t       |n      |t           
+(1 row)
+
+
+starting permutation: b1 b3 m2 s1 c3 c1 s2
+step b1: BEGIN ISOLATION LEVEL READ COMMITTED;
+step b3: BEGIN ISOLATION LEVEL READ COMMITTED;
+step m2: DELETE FROM t;
+step s1: ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a; <waiting ...>
+step c3: COMMIT;
+step s1: <... completed>
+step c1: COMMIT;
+step s2: SELECT conname, conrelid::regclass, contype, convalidated
+           FROM pg_constraint WHERE conname = 't1_nn';
+
+conname|conrelid|contype|convalidated
+-------+--------+-------+------------
+t1_nn  |t       |n      |t           
+(1 row)
+
+
+starting permutation: b1 b4 d1 m1 c2 s1 s2 r1
+step b1: BEGIN ISOLATION LEVEL READ COMMITTED;
+step b4: BEGIN;
+step d1: DROP INDEX t_ab_idx;
+step m1: DELETE FROM t; <waiting ...>
+step c2: ROLLBACK;
+step m1: <... completed>
+step s1: ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a;
+step s2: SELECT conname, conrelid::regclass, contype, convalidated
+           FROM pg_constraint WHERE conname = 't1_nn';
+
+conname|conrelid|contype|convalidated
+-------+--------+-------+------------
+t1_nn  |t       |n      |t           
+(1 row)
+
+step r1: ROLLBACK;
+
+starting permutation: b1 b4 d1 m1 c3 s1 s2 c1
+step b1: BEGIN ISOLATION LEVEL READ COMMITTED;
+step b4: BEGIN;
+step d1: DROP INDEX t_ab_idx;
+step m1: DELETE FROM t; <waiting ...>
+step c3: COMMIT;
+step m1: <... completed>
+step s1: ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a;
+step s2: SELECT conname, conrelid::regclass, contype, convalidated
+           FROM pg_constraint WHERE conname = 't1_nn';
+
+conname|conrelid|contype|convalidated
+-------+--------+-------+------------
+t1_nn  |t       |n      |t           
+(1 row)
+
+step c1: COMMIT;
diff --git a/src/test/isolation/isolation_schedule b/src/test/isolation/isolation_schedule
index 143109aa4d..32d7e51aa9 100644
--- a/src/test/isolation/isolation_schedule
+++ b/src/test/isolation/isolation_schedule
@@ -55,6 +55,7 @@ test: merge-delete
 test: merge-update
 test: merge-match-recheck
 test: merge-join
+test: fast-set-notnull
 test: delete-abort-savept
 test: delete-abort-savept-2
 test: aborted-keyrevoke
diff --git a/src/test/isolation/specs/fast-set-notnull.spec b/src/test/isolation/specs/fast-set-notnull.spec
new file mode 100644
index 0000000000..d8198c869a
--- /dev/null
+++ b/src/test/isolation/specs/fast-set-notnull.spec
@@ -0,0 +1,46 @@
+#
+# fast not-null tests
+#
+
+setup
+{
+  CREATE TABLE t (a int, b int);
+  CREATE INDEX t_ab_idx on t(a,b);
+  INSERT INTO t values (null, 1);
+  INSERT INTO t SELECT x, x*10 FROM generate_series(1,3) g(x);
+}
+
+teardown
+{
+  DROP TABLE t;
+}
+
+session s1
+step b1  { BEGIN ISOLATION LEVEL READ COMMITTED; }
+step b2  { BEGIN; }
+step m1  { DELETE FROM t;}
+step s0  { savepoint s0;}
+step s1  { ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a;}
+step s2  { SELECT conname, conrelid::regclass, contype, convalidated
+           FROM pg_constraint WHERE conname = 't1_nn';
+         }
+step r1  { ROLLBACK; }
+step c1  { COMMIT; }
+
+session s2
+step b3  { BEGIN ISOLATION LEVEL READ COMMITTED; }
+step b4  { BEGIN; }
+step hj  { ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a;}
+step m2  { DELETE FROM t;}
+step d1  { DROP INDEX t_ab_idx;}
+step c2  { ROLLBACK; }
+step c3  { COMMIT; }
+
+permutation b1 m1 s0 s1 s2 r1 s2
+permutation b1 m1 s0 s1 s2 c1 s2
+permutation b1 b3 m1 hj c1 c3 s2
+permutation b2 b4 m1 hj c1 c3 s2
+permutation b1 b3 m2 s1 c3 c1 s2
+permutation b1 b4 d1 m1 c2 s1 s2 r1
+permutation b1 b4 d1 m1 c3 s1 s2 c1
+
diff --git a/src/test/regress/expected/alter_table.out b/src/test/regress/expected/alter_table.out
index 12852aa612..35b80b49e6 100644
--- a/src/test/regress/expected/alter_table.out
+++ b/src/test/regress/expected/alter_table.out
@@ -4738,3 +4738,41 @@ drop publication pub1;
 drop schema alter1 cascade;
 drop schema alter2 cascade;
 NOTICE:  drop cascades to table alter2.t1
+-----fast add not-null constraint tests.
+CREATE TABLE tp (a int, b int GENERATED ALWAYS AS (22) stored) PARTITION BY range(a);
+CREATE TABLE tpp1(a int, b int GENERATED ALWAYS AS (a+1) stored);
+CREATE TABLE tpp2(a int, b int GENERATED ALWAYS AS (a+10) stored);
+ALTER TABLE tp ATTACH PARTITION tpp1 FOR values from ( 1 ) to (100);
+ALTER TABLE tp ATTACH PARTITION tpp2 default;
+CREATE INDEX ON tp(b);
+insert into tp select g from generate_series(100,120) g;
+--cannot fast ALTER TABLE SET NOT NULL or ALTER TABLE ADD CONSTRAINT NOT NULL
+--so won't interfere with the index rebuild.
+ALTER TABLE tp alter column b set not null, ALTER COLUMN b SET EXPRESSION AS (a * 3);
+ALTER TABLE tp alter column b drop not null;
+ALTER TABLE tp add constraint nn not null b, ALTER COLUMN b SET EXPRESSION AS (a * 11);
+------test non-partitioned table
+CREATE TABLE t1(f1 INT, f2 int, f3 int,f4 int);
+INSERT INTO t1 select g, g+1, g+2, g+3 from generate_series(1, 20) g;
+CREATE INDEX t1_f1_f2_idx ON t1(f1,f2);
+CREATE UNIQUE INDEX t1_f3idx ON t1(f3);
+CREATE INDEX t1_f3f4idx ON t1(f3) include(f4);
+--cannot fast ALTER TABLE SET NOT NULL or ALTER TABLE ADD CONSTRAINT NOT NULL
+--so won't interfere with the index rebuild.
+ALTER TABLE t1 alter column f1 set not null, ALTER f1 TYPE BIGINT;
+ALTER TABLE t1 alter column f1 drop not null;
+ALTER TABLE t1 add constraint nn not null f1, ALTER f1 TYPE bigint;
+--ok. with ALTER COLUMN SET NOT NULL variant
+ALTER TABLE t1 alter column f1 drop not null, alter column f2 drop not null;
+ALTER TABLE t1 alter column f2 set not null, alter column f1 set not null;
+--ok. with add constraint variants
+ALTER TABLE t1 alter column f1 drop not null, alter column f2 drop not null;
+ALTER TABLE t1 add constraint nn not null f2, add constraint nnf1 not null f1;
+--ok.
+ALTER TABLE t1 add constraint t_f3_pk primary key using index t1_f3idx;
+NOTICE:  ALTER TABLE / ADD CONSTRAINT USING INDEX will rename index "t1_f3idx" to "t_f3_pk"
+--cannot fast ALTER TABLE SET NOT NULL or ALTER TABLE ADD CONSTRAINT NOT NULL
+--for column f4 now, can only for keycolumn, not include column.
+ALTER TABLE t1 add constraint nnf4 not null f4;
+drop table t1;
+drop table tpp1, tpp2, tp;
diff --git a/src/test/regress/sql/alter_table.sql b/src/test/regress/sql/alter_table.sql
index c88f9eaab0..a92cddcdcc 100644
--- a/src/test/regress/sql/alter_table.sql
+++ b/src/test/regress/sql/alter_table.sql
@@ -3102,3 +3102,46 @@ alter table alter1.t1 set schema alter2;
 drop publication pub1;
 drop schema alter1 cascade;
 drop schema alter2 cascade;
+
+-----fast add not-null constraint tests.
+CREATE TABLE tp (a int, b int GENERATED ALWAYS AS (22) stored) PARTITION BY range(a);
+CREATE TABLE tpp1(a int, b int GENERATED ALWAYS AS (a+1) stored);
+CREATE TABLE tpp2(a int, b int GENERATED ALWAYS AS (a+10) stored);
+ALTER TABLE tp ATTACH PARTITION tpp1 FOR values from ( 1 ) to (100);
+ALTER TABLE tp ATTACH PARTITION tpp2 default;
+CREATE INDEX ON tp(b);
+insert into tp select g from generate_series(100,120) g;
+
+--cannot fast ALTER TABLE SET NOT NULL or ALTER TABLE ADD CONSTRAINT NOT NULL
+--so won't interfere with the index rebuild.
+ALTER TABLE tp alter column b set not null, ALTER COLUMN b SET EXPRESSION AS (a * 3);
+ALTER TABLE tp alter column b drop not null;
+ALTER TABLE tp add constraint nn not null b, ALTER COLUMN b SET EXPRESSION AS (a * 11);
+
+------test non-partitioned table
+CREATE TABLE t1(f1 INT, f2 int, f3 int,f4 int);
+INSERT INTO t1 select g, g+1, g+2, g+3 from generate_series(1, 20) g;
+CREATE INDEX t1_f1_f2_idx ON t1(f1,f2);
+CREATE UNIQUE INDEX t1_f3idx ON t1(f3);
+CREATE INDEX t1_f3f4idx ON t1(f3) include(f4);
+
+--cannot fast ALTER TABLE SET NOT NULL or ALTER TABLE ADD CONSTRAINT NOT NULL
+--so won't interfere with the index rebuild.
+ALTER TABLE t1 alter column f1 set not null, ALTER f1 TYPE BIGINT;
+ALTER TABLE t1 alter column f1 drop not null;
+ALTER TABLE t1 add constraint nn not null f1, ALTER f1 TYPE bigint;
+
+--ok. with ALTER COLUMN SET NOT NULL variant
+ALTER TABLE t1 alter column f1 drop not null, alter column f2 drop not null;
+ALTER TABLE t1 alter column f2 set not null, alter column f1 set not null;
+--ok. with add constraint variants
+ALTER TABLE t1 alter column f1 drop not null, alter column f2 drop not null;
+ALTER TABLE t1 add constraint nn not null f2, add constraint nnf1 not null f1;
+--ok.
+ALTER TABLE t1 add constraint t_f3_pk primary key using index t1_f3idx;
+
+--cannot fast ALTER TABLE SET NOT NULL or ALTER TABLE ADD CONSTRAINT NOT NULL
+--for column f4 now, can only for keycolumn, not include column.
+ALTER TABLE t1 add constraint nnf4 not null f4;
+drop table t1;
+drop table tpp1, tpp2, tp;
-- 
2.34.1

From be8fea79986339cadff21dbe9c4415b330a296a3 Mon Sep 17 00:00:00 2001
From: jian he <jian.universality@gmail.com>
Date: Wed, 5 Feb 2025 16:05:10 +0800
Subject: [PATCH v3 1/1] using index to speedup add not null constraint to
 existing table

This patch tries to use index_beginscan() / index_getnext() / index_endscan()
mentioned in [1] to speedup adding not-null constraints to the existing table.

There are two ways to add not-null constraints to an existing table.
1. ATExecAddConstraint->ATAddCheckNNConstraint->AddRelationNewConstraints
2. ATExecSetNotNull->AddRelationNewConstraints

The logic is:
1. In AddRelationNewConstraints, if condition meet (see get_index_for_validate_notnull)
   then attempt to use indexscan to pre check whether the column is NOT NULL.
2. AddRelationNewConstraints returned a list of CookedConstraint nodes.
   pass not-null cooked constraint to tab->constraints (a list of NewConstraint).
   code snippet:
    if (!ccon->skip_validation)
    {
        newcon = (NewConstraint *) palloc0(sizeof(NewConstraint));
        if (ccon->pre_validated)
            newcon->nn_attnum = ccon->attnum;
        tab->constraints = lappend(tab->constraints, newcon);
    }
3. In ATRewriteTable, if all attnums associated with not-null constraint have
already been prevalidated, then no need to needscan.

CAUTION:
ALTER TABLE SET DATA TYPE and ALTER TABLE SET EXPRESSION trigger an index
rebuild (refer to RememberAllDependentForRebuilding).  While the former cannot
be applied to partitioned tables, the latter can.  If an index rebuild occurs,
then indexscan cannot be used to prevalidate whether a column contains null
values.  Consequently, pre-validating a NOT NULL constraint is currently not
supported for partitioned tables.

concurrency concern:
ALTER TABLE SET NOT NULL will take an ACCESS EXCLUSIVE lock, so there is less
variant of racing issue can occur?  to prove accurate, I wrote some isolation
tests. see[2]

performance concern:
it will be slower than normal adding not-null constraint ONLY IF your index is
bloat and a large percent of bloat is related to null value data.
demo:

100% bloat and zero percent null value:
drop table if exists t \; create unlogged table t(a int, b int, c int);
insert into t select g, g+1 from generate_series(1,1_000_000) g;
create index t_idx_a on t(a);
delete from t;
alter table t add constraint t1 not null a;

patch Time:  1.873 ms
master Time: 648.312 ms
----------------------------------------------------
---- %20 percent column value is null and deleted from heap still on the index.
drop table if exists t \; create unlogged table t(a int, b int);
insert into t select case when g % 5 = 0 then null else g end, g+1
from generate_series(1,1_000_000) g;

create index t_idx_a on t(a);
delete from t where a is null;

alter table t add constraint t1 not null a;
patch Time:: 1080.407 ms (00:01.080)
master Time: 970.671 ms

references:
[1] https://postgr.es/m/CA%2BTgmoa5NKz8iGW_9v7wz%3D-%2BzQFu%3DE4SZoaTaU1znLaEXRYp-Q%40mail.gmail.com
[2] https://postgr.es/m/900056D1-32DF-4927-8251-3E0C0DC407FD%40anarazel.de
---
 src/backend/catalog/heap.c                    | 90 +++++++++++++++++
 src/backend/catalog/pg_constraint.c           |  1 +
 src/backend/commands/tablecmds.c              | 87 ++++++++++++++---
 src/backend/executor/execIndexing.c           | 97 +++++++++++++++++++
 src/include/catalog/heap.h                    |  3 +
 src/include/executor/executor.h               |  1 +
 .../isolation/expected/fast-set-notnull.out   | 97 +++++++++++++++++++
 src/test/isolation/isolation_schedule         |  1 +
 .../isolation/specs/fast-set-notnull.spec     | 43 ++++++++
 src/test/regress/expected/alter_table.out     | 41 ++++++++
 src/test/regress/sql/alter_table.sql          | 47 +++++++++
 11 files changed, 497 insertions(+), 11 deletions(-)
 create mode 100644 src/test/isolation/expected/fast-set-notnull.out
 create mode 100644 src/test/isolation/specs/fast-set-notnull.spec

diff --git a/src/backend/catalog/heap.c b/src/backend/catalog/heap.c
index 57ef466acc..35cd64e87c 100644
--- a/src/backend/catalog/heap.c
+++ b/src/backend/catalog/heap.c
@@ -57,6 +57,7 @@
 #include "commands/tablecmds.h"
 #include "commands/typecmds.h"
 #include "common/int.h"
+#include "executor/executor.h"
 #include "miscadmin.h"
 #include "nodes/nodeFuncs.h"
 #include "optimizer/optimizer.h"
@@ -117,6 +118,7 @@ static Node *cookConstraint(ParseState *pstate,
 							char *relname);
 
 
+static Oid get_index_for_validate_notnull(Relation rel, int colnum);
 /* ----------------------------------------------------------------
  *				XXX UGLY HARD CODED BADNESS FOLLOWS XXX
  *
@@ -2286,6 +2288,8 @@ StoreConstraints(Relation rel, List *cooked_constraints, bool is_internal)
  * newConstraints: list of Constraint nodes
  * allow_merge: true if check constraints may be merged with existing ones
  * is_local: true if definition is local, false if it's inherited
+ * index_rebuild: true if the ALTER TABLE command and it's subcommands
+ * will do any index rebuild in the future.
  * is_internal: true if result of some internal process, not a user request
  * queryString: used during expression transformation of default values and
  *		cooked CHECK constraints
@@ -2310,6 +2314,7 @@ AddRelationNewConstraints(Relation rel,
 						  bool allow_merge,
 						  bool is_local,
 						  bool is_internal,
+						  bool index_rebuild,
 						  const char *queryString)
 {
 	List	   *cookedConstraints = NIL;
@@ -2398,6 +2403,7 @@ AddRelationNewConstraints(Relation rel,
 		cooked->is_local = is_local;
 		cooked->inhcount = is_local ? 0 : 1;
 		cooked->is_no_inherit = false;
+		cooked->validated = false;
 		cookedConstraints = lappend(cookedConstraints, cooked);
 	}
 
@@ -2532,6 +2538,7 @@ AddRelationNewConstraints(Relation rel,
 			cooked->is_local = is_local;
 			cooked->inhcount = is_local ? 0 : 1;
 			cooked->is_no_inherit = cdef->is_no_inherit;
+			cooked->validated = false;
 			cookedConstraints = lappend(cookedConstraints, cooked);
 		}
 		else if (cdef->contype == CONSTR_NOTNULL)
@@ -2540,6 +2547,7 @@ AddRelationNewConstraints(Relation rel,
 			AttrNumber	colnum;
 			int16		inhcount = is_local ? 0 : 1;
 			char	   *nnname;
+			Oid			indexoid = InvalidOid;
 
 			/* Determine which column to modify */
 			colnum = get_attnum(RelationGetRelid(rel), strVal(linitial(cdef->keys)));
@@ -2592,6 +2600,15 @@ AddRelationNewConstraints(Relation rel,
 								inhcount,
 								cdef->is_no_inherit);
 
+			/*
+			 * if there is any index to be rebuild, then we cannot do indexscan
+			 * in index_check_notnull; for re_added (is_internal is true)
+			 * not-null constraint also cannot use indexscan to check null
+			 * existence.
+			*/
+			if (rel->rd_rel->relkind == RELKIND_RELATION && !is_internal && !index_rebuild)
+				indexoid = get_index_for_validate_notnull(rel, colnum);
+
 			nncooked = (CookedConstraint *) palloc(sizeof(CookedConstraint));
 			nncooked->contype = CONSTR_NOTNULL;
 			nncooked->conoid = constrOid;
@@ -2603,7 +2620,14 @@ AddRelationNewConstraints(Relation rel,
 			nncooked->is_local = is_local;
 			nncooked->inhcount = inhcount;
 			nncooked->is_no_inherit = cdef->is_no_inherit;
+			nncooked->validated = false;
+			if (OidIsValid(indexoid))
+				nncooked->validated = index_check_notnull(RelationGetRelid(rel), indexoid, colnum);
 
+			if (nncooked->validated)
+				ereport(DEBUG1,
+						errmsg_internal("using index (%d) vertified relation \"%s\" column number (%d) don't have null values",
+										 indexoid, RelationGetRelationName(rel), colnum));
 			cookedConstraints = lappend(cookedConstraints, nncooked);
 		}
 	}
@@ -2620,6 +2644,72 @@ AddRelationNewConstraints(Relation rel,
 	return cookedConstraints;
 }
 
+static Oid
+get_index_for_validate_notnull(Relation relation, int colnum)
+{
+	Relation	indrel;
+	Relation	index_rel;
+	SysScanDesc indscan;
+	ScanKeyData skey;
+	HeapTuple	htup;
+	TupleDesc	tupdesc;
+	Form_pg_attribute attr;
+	List	   *result = NIL;
+
+	tupdesc = RelationGetDescr(relation);
+
+	/* Prepare to scan pg_index for entries having indrelid = this rel. */
+	ScanKeyInit(&skey,
+				Anum_pg_index_indrelid,
+				BTEqualStrategyNumber, F_OIDEQ,
+				ObjectIdGetDatum(RelationGetRelid(relation)));
+
+	indrel = table_open(IndexRelationId, AccessShareLock);
+	indscan = systable_beginscan(indrel, IndexIndrelidIndexId, true,
+								 NULL, 1, &skey);
+
+	while (HeapTupleIsValid(htup = systable_getnext(indscan)))
+	{
+		Form_pg_index index = (Form_pg_index) GETSTRUCT(htup);
+
+		if (!index->indimmediate || !index->indisvalid || !index->indislive)
+			continue;
+
+		if (!heap_attisnull(htup, Anum_pg_index_indexprs, NULL) ||
+			!heap_attisnull(htup, Anum_pg_index_indpred, NULL))
+			continue;
+
+		for (int i = 0; i < index->indnkeyatts; i++)
+		{
+			attr = TupleDescAttr(tupdesc, (index->indkey.values[i]) - 1);
+			if (attr->attnum == colnum)
+			{
+				Assert(OidIsValid(index->indexrelid));
+
+				/* currently, only validate column not-null can only done by btree index */
+				index_rel = index_open(index->indexrelid, AccessShareLock);
+				if (index_rel->rd_rel->relkind == RELKIND_INDEX &&
+					index_rel->rd_rel->relam == BTREE_AM_OID)
+					result = lappend_oid(result, index->indexrelid);
+
+				index_close(index_rel, AccessShareLock);
+				break;
+			}
+		}
+	}
+	systable_endscan(indscan);
+	table_close(indrel, AccessShareLock);
+
+	if(list_length(result) == 0)
+		return InvalidOid;
+	else
+	{
+		/* Sort the result list into OID order, make the result stable. */
+		list_sort(result, list_oid_cmp);
+		return list_nth_oid(result, 0);
+	}
+}
+
 /*
  * Check for a pre-existing check constraint that conflicts with a proposed
  * new one, and either adjust its conislocal/coninhcount settings or throw
diff --git a/src/backend/catalog/pg_constraint.c b/src/backend/catalog/pg_constraint.c
index ac80652baf..ae1f779e8e 100644
--- a/src/backend/catalog/pg_constraint.c
+++ b/src/backend/catalog/pg_constraint.c
@@ -834,6 +834,7 @@ RelationGetNotNullConstraints(Oid relid, bool cooked, bool include_noinh)
 			cooked->is_local = true;
 			cooked->inhcount = 0;
 			cooked->is_no_inherit = conForm->connoinherit;
+			cooked->validated = false;
 
 			notnulls = lappend(notnulls, cooked);
 		}
diff --git a/src/backend/commands/tablecmds.c b/src/backend/commands/tablecmds.c
index 18f64db6e3..39f4fe54d6 100644
--- a/src/backend/commands/tablecmds.c
+++ b/src/backend/commands/tablecmds.c
@@ -210,15 +210,17 @@ typedef struct AlteredTableInfo
 } AlteredTableInfo;
 
 /* Struct describing one new constraint to check in Phase 3 scan */
-/* Note: new not-null constraints are handled elsewhere */
+/* Note: new not-null constraints are handled here also */
 typedef struct NewConstraint
 {
 	char	   *name;			/* Constraint name, or NULL if none */
-	ConstrType	contype;		/* CHECK or FOREIGN */
+	ConstrType	contype;		/* CHECK or FOREIGN or NOT-NULL */
 	Oid			refrelid;		/* PK rel, if FOREIGN */
 	Oid			refindid;		/* OID of PK's index, if FOREIGN */
 	bool		conwithperiod;	/* Whether the new FOREIGN KEY uses PERIOD */
 	Oid			conid;			/* OID of pg_constraint entry, if FOREIGN */
+	int			nn_attnum;		/* already validated NOT-NULL constraint attnum.
+								   -1 means not applicable */
 	Node	   *qual;			/* Check expr or CONSTR_FOREIGN Constraint */
 	ExprState  *qualstate;		/* Execution state for CHECK expr */
 } NewConstraint;
@@ -990,6 +992,7 @@ DefineRelation(CreateStmt *stmt, char relkind, Oid ownerId,
 			cooked->is_local = true;	/* not used for defaults */
 			cooked->inhcount = 0;	/* ditto */
 			cooked->is_no_inherit = false;
+			cooked->validated = false;
 			cookedDefaults = lappend(cookedDefaults, cooked);
 			attr->atthasdef = true;
 		}
@@ -1075,7 +1078,7 @@ DefineRelation(CreateStmt *stmt, char relkind, Oid ownerId,
 	 */
 	if (rawDefaults)
 		AddRelationNewConstraints(rel, rawDefaults, NIL,
-								  true, true, false, queryString);
+								  true, true, false, false, queryString);
 
 	/*
 	 * Make column generation expressions visible for use by partitioning.
@@ -1306,7 +1309,7 @@ DefineRelation(CreateStmt *stmt, char relkind, Oid ownerId,
 	 */
 	if (stmt->constraints)
 		AddRelationNewConstraints(rel, NIL, stmt->constraints,
-								  true, true, false, queryString);
+								  true, true, false, false, queryString);
 
 	/*
 	 * Finally, merge the not-null constraints that are declared directly with
@@ -6071,6 +6074,7 @@ ATRewriteTable(AlteredTableInfo *tab, Oid OIDNewHeap)
 	TupleDesc	oldTupDesc;
 	TupleDesc	newTupDesc;
 	bool		needscan = false;
+	bool		validated = true;
 	List	   *notnull_attrs;
 	int			i;
 	ListCell   *l;
@@ -6132,6 +6136,10 @@ ATRewriteTable(AlteredTableInfo *tab, Oid OIDNewHeap)
 				needscan = true;
 				con->qualstate = ExecPrepareExpr((Expr *) con->qual, estate);
 				break;
+			case CONSTR_NOTNULL:
+				if(con->nn_attnum == -1)
+					validated = false;
+				break;
 			case CONSTR_FOREIGN:
 				/* Nothing to do here */
 				break;
@@ -6171,7 +6179,15 @@ ATRewriteTable(AlteredTableInfo *tab, Oid OIDNewHeap)
 			if (attr->attnotnull && !attr->attisdropped)
 				notnull_attrs = lappend_int(notnull_attrs, i);
 		}
-		if (notnull_attrs)
+
+		/*
+		 * we may did some pre-validation at phase 2. if validated is true, then
+		 * all the not-null constraints for this DDL have already been
+		 * pre-validated, no need to scan it again.  tab->constraints already
+		 * include all CONSTR_NOTNULL constraint. See AddRelationNewConstraints
+		 * and index_check_notnull.
+		*/
+		if (notnull_attrs && !validated)
 			needscan = true;
 	}
 
@@ -7317,7 +7333,7 @@ ATExecAddColumn(List **wqueue, AlteredTableInfo *tab, Relation rel,
 		 * _list_ of defaults, but we just do one.
 		 */
 		AddRelationNewConstraints(rel, list_make1(rawEnt), NIL,
-								  false, true, false, NULL);
+								  false, true, false, false, NULL);
 
 		/* Make the additional catalog changes visible */
 		CommandCounterIncrement();
@@ -7759,6 +7775,8 @@ ATExecSetNotNull(List **wqueue, Relation rel, char *conName, char *colName,
 	CookedConstraint *ccon;
 	List	   *cooked;
 	bool		is_no_inherit = false;
+	bool		index_rebuild = false;
+	AlteredTableInfo *tab = NULL;
 
 	/* Guard against stack overflow due to overly deep inheritance tree. */
 	check_stack_depth();
@@ -7874,10 +7892,45 @@ ATExecSetNotNull(List **wqueue, Relation rel, char *conName, char *colName,
 	constraint->is_no_inherit = is_no_inherit;
 	constraint->conname = conName;
 
+	/*
+	 * for ALTER TABLE ALTER COLUMN SET EXPRESSION, function
+	 * RememberIndexForRebuilding can only remember the partitioned index entry
+	 * (RELKIND_PARTITIONED_INDEX), not the regular index.
+	 * so we can not use index_check_notnull to fast check the column not-null
+	 * status for the partitioned table now.
+	 * that is why if recursing is true, we blindly assume index_rebuild is
+	 * true.  in future, we can iterate changedIndexOids, find out if there is
+	 * any index rebuild over that not-null column or not.
+	 */
+	tab = ATGetQueueEntry(wqueue, rel);
+	if (list_length(tab->changedIndexOids) > 0 || recursing)
+		index_rebuild = true;
+
 	/* and do it */
 	cooked = AddRelationNewConstraints(rel, NIL, list_make1(constraint),
-									   false, !recursing, false, NULL);
+									   false, !recursing, false, index_rebuild, NULL);
 	ccon = linitial(cooked);
+
+	if (!ccon->skip_validation)
+	{
+		NewConstraint *newcon;
+
+		newcon = (NewConstraint *) palloc0(sizeof(NewConstraint));
+		newcon->name = ccon->name;
+
+		Assert(ccon->contype == CONSTR_NOTNULL);
+		newcon->contype = ccon->contype;
+		if (ccon->validated)
+		{
+			newcon->nn_attnum = ccon->attnum;
+			Assert(ccon->attnum > 0);
+		}
+		else
+			newcon->nn_attnum = -1;
+
+		tab->constraints = lappend(tab->constraints, newcon);
+	}
+
 	ObjectAddressSet(address, ConstraintRelationId, ccon->conoid);
 
 	InvokeObjectPostAlterHook(RelationRelationId,
@@ -8025,7 +8078,7 @@ ATExecColumnDefault(Relation rel, const char *colName,
 		 * _list_ of defaults, but we just do one.
 		 */
 		AddRelationNewConstraints(rel, list_make1(rawEnt), NIL,
-								  false, true, false, NULL);
+								  false, true, false, false, NULL);
 	}
 
 	ObjectAddressSubSet(address, RelationRelationId,
@@ -8487,7 +8540,7 @@ ATExecSetExpression(AlteredTableInfo *tab, Relation rel, const char *colName,
 
 	/* Store the generated expression */
 	AddRelationNewConstraints(rel, list_make1(rawEnt), NIL,
-							  false, true, false, NULL);
+							  false, true, false, false, NULL);
 
 	/* Make above new expression visible */
 	CommandCounterIncrement();
@@ -9591,6 +9644,10 @@ ATAddCheckNNConstraint(List **wqueue, AlteredTableInfo *tab, Relation rel,
 	List	   *children;
 	ListCell   *child;
 	ObjectAddress address = InvalidObjectAddress;
+	bool		index_rebuild = false;
+
+	if (list_length(tab->changedIndexOids) > 0 || recursing)
+		index_rebuild = true;
 
 	/* Guard against stack overflow due to overly deep inheritance tree. */
 	check_stack_depth();
@@ -9615,6 +9672,7 @@ ATAddCheckNNConstraint(List **wqueue, AlteredTableInfo *tab, Relation rel,
 										recursing || is_readd,	/* allow_merge */
 										!recursing, /* is_local */
 										is_readd,	/* is_internal */
+										index_rebuild,
 										NULL);	/* queryString not available
 												 * here */
 
@@ -9626,15 +9684,19 @@ ATAddCheckNNConstraint(List **wqueue, AlteredTableInfo *tab, Relation rel,
 	{
 		CookedConstraint *ccon = (CookedConstraint *) lfirst(lcon);
 
-		if (!ccon->skip_validation && ccon->contype != CONSTR_NOTNULL)
+		if (!ccon->skip_validation)
 		{
 			NewConstraint *newcon;
 
 			newcon = (NewConstraint *) palloc0(sizeof(NewConstraint));
 			newcon->name = ccon->name;
 			newcon->contype = ccon->contype;
+			if (ccon->validated && ccon->contype == CONSTR_NOTNULL)
+				newcon->nn_attnum = ccon->attnum;
+			else
+				newcon->nn_attnum = -1;
+
 			newcon->qual = ccon->expr;
-
 			tab->constraints = lappend(tab->constraints, newcon);
 		}
 
@@ -10732,6 +10794,7 @@ addFkRecurseReferencing(List **wqueue, Constraint *fkconstraint, Relation rel,
 			newcon->refindid = indexOid;
 			newcon->conid = parentConstr;
 			newcon->conwithperiod = fkconstraint->fk_with_period;
+			newcon->nn_attnum = -1;
 			newcon->qual = (Node *) fkconstraint;
 
 			tab->constraints = lappend(tab->constraints, newcon);
@@ -12146,6 +12209,7 @@ QueueFKConstraintValidation(List **wqueue, Relation conrel, Relation rel,
 		newcon->refrelid = con->confrelid;
 		newcon->refindid = con->conindid;
 		newcon->conid = con->oid;
+		newcon->nn_attnum = -1;
 		newcon->qual = (Node *) fkconstraint;
 
 		/* Find or create work queue entry for this table */
@@ -12285,6 +12349,7 @@ QueueCheckConstraintValidation(List **wqueue, Relation conrel, Relation rel,
 	newcon->refrelid = InvalidOid;
 	newcon->refindid = InvalidOid;
 	newcon->conid = con->oid;
+	newcon->nn_attnum = -1;
 
 	val = SysCacheGetAttrNotNull(CONSTROID, contuple,
 								 Anum_pg_constraint_conbin);
diff --git a/src/backend/executor/execIndexing.c b/src/backend/executor/execIndexing.c
index 7c87f012c3..bcef26f3cc 100644
--- a/src/backend/executor/execIndexing.c
+++ b/src/backend/executor/execIndexing.c
@@ -108,6 +108,7 @@
 
 #include "access/genam.h"
 #include "access/relscan.h"
+#include "access/table.h"
 #include "access/tableam.h"
 #include "access/xact.h"
 #include "catalog/index.h"
@@ -1166,3 +1167,99 @@ ExecWithoutOverlapsNotEmpty(Relation rel, NameData attname, Datum attval, char t
 				 errmsg("empty WITHOUT OVERLAPS value found in column \"%s\" in relation \"%s\"",
 						NameStr(attname), RelationGetRelationName(rel))));
 }
+
+/*
+ * colnum is the attnum where not-null constraint will be created on.
+*/
+bool
+index_check_notnull(Oid table_oid, Oid indexoid, AttrNumber colnum)
+{
+	Relation index;
+	Relation heap;
+
+	SnapshotData DirtySnapshot;
+	IndexScanDesc index_scan;
+	ScanKeyData scankeys[INDEX_MAX_KEYS];
+	TupleTableSlot *existing_slot;
+	IndexInfo  *indexInfo;
+	EState	   *estate;
+	int			indnkeyatts;
+	ExprContext *econtext;
+	bool all_not_null = true;
+	AttrNumber	sk_attno = -1;
+
+	heap = table_open(table_oid, NoLock);
+	index = index_open(indexoid, AccessShareLock);
+
+	/*
+	 * Need an EState for slot to hold the current tuple.
+	 *
+	 */
+	estate = CreateExecutorState();
+	econtext = GetPerTupleExprContext(estate);
+	existing_slot = table_slot_create(heap, NULL);
+
+	/* Arrange for econtext's scan tuple to be the tuple under test */
+	econtext->ecxt_scantuple = existing_slot;
+
+	indexInfo = BuildIndexInfo(index);
+	indnkeyatts = IndexRelationGetNumberOfKeyAttributes(index);
+
+	/*
+	 * Search the tuples that are in the index for any violations, including
+	 * tuples that aren't visible yet.
+	 */
+	InitDirtySnapshot(DirtySnapshot);
+
+	for (int i = 0; i < indnkeyatts; i++)
+	{
+		if (indexInfo->ii_IndexAttrNumbers[i] == colnum)
+		{
+			sk_attno = i+1;
+			break;
+		}
+	}
+
+	if (sk_attno == -1)
+		elog(ERROR, "index %u should effect on column number %d", indexoid, colnum);
+
+	for (int i = 0; i < indnkeyatts; i++)
+	{
+		/* set up an IS NULL scan key so that we ignore not nulls */
+		ScanKeyEntryInitialize(&scankeys[i],
+								SK_ISNULL | SK_SEARCHNULL,
+								sk_attno,		/* index col to scan */
+								InvalidStrategy,/* no strategy */
+								InvalidOid,		/* no strategy subtype */
+								InvalidOid,		/* no collation */
+								InvalidOid,		/* no reg proc for this */
+								(Datum) 0);		/* constant */
+	}
+
+	index_scan = index_beginscan(heap, index, &DirtySnapshot, indnkeyatts, 0);
+	index_rescan(index_scan, scankeys, indnkeyatts, NULL, 0);
+	while (index_getnext_slot(index_scan, ForwardScanDirection, existing_slot))
+	{
+		Datum		values[INDEX_MAX_KEYS];
+		bool		nulls[INDEX_MAX_KEYS];
+
+		/*
+		 * Extract the index column values and isnull flags from the existing
+		 * tuple.
+		 */
+		FormIndexDatum(indexInfo, existing_slot, estate, values, nulls);
+
+		if (nulls[sk_attno - 1])
+		{
+			all_not_null = false;
+			break;
+		}
+	}
+	index_endscan(index_scan);
+	table_close(heap, NoLock);
+	index_close(index, AccessShareLock);
+	ExecDropSingleTupleTableSlot(existing_slot);
+	FreeExecutorState(estate);
+
+	return all_not_null;
+}
\ No newline at end of file
diff --git a/src/include/catalog/heap.h b/src/include/catalog/heap.h
index cad830dc39..bbb75820c5 100644
--- a/src/include/catalog/heap.h
+++ b/src/include/catalog/heap.h
@@ -46,6 +46,8 @@ typedef struct CookedConstraint
 	int16		inhcount;		/* number of times constraint is inherited */
 	bool		is_no_inherit;	/* constraint has local def and cannot be
 								 * inherited */
+	bool		validated;  	/* is this constraint already validated?
+								 * only for CONSTR_NOTNULL in AddRelationNewConstraints */
 } CookedConstraint;
 
 extern Relation heap_create(const char *relname,
@@ -114,6 +116,7 @@ extern List *AddRelationNewConstraints(Relation rel,
 									   bool allow_merge,
 									   bool is_local,
 									   bool is_internal,
+									   bool index_rebuild,
 									   const char *queryString);
 extern List *AddRelationNotNullConstraints(Relation rel,
 										   List *constraints,
diff --git a/src/include/executor/executor.h b/src/include/executor/executor.h
index 45b80e6b98..d4f143c5aa 100644
--- a/src/include/executor/executor.h
+++ b/src/include/executor/executor.h
@@ -661,6 +661,7 @@ extern void check_exclusion_constraint(Relation heap, Relation index,
 									   const Datum *values, const bool *isnull,
 									   EState *estate, bool newIndex);
 
+extern bool index_check_notnull(Oid heap, Oid indexoid, AttrNumber colnum);
 /*
  * prototypes from functions in execReplication.c
  */
diff --git a/src/test/isolation/expected/fast-set-notnull.out b/src/test/isolation/expected/fast-set-notnull.out
new file mode 100644
index 0000000000..36ac14a2e4
--- /dev/null
+++ b/src/test/isolation/expected/fast-set-notnull.out
@@ -0,0 +1,97 @@
+Parsed test spec with 2 sessions
+
+starting permutation: b1 b3 m1 hj c1 c3 s2
+step b1: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step b3: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step m1: DELETE FROM t;
+step hj: ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a; <waiting ...>
+step c1: COMMIT;
+step hj: <... completed>
+step c3: COMMIT;
+step s2: SELECT conname, conrelid::regclass, contype, convalidated
+           FROM pg_constraint WHERE conname = 't1_nn';
+
+conname|conrelid|contype|convalidated
+-------+--------+-------+------------
+t1_nn  |t       |n      |t           
+(1 row)
+
+
+starting permutation: b2 b3 m1 hj c1 c3 s2
+step b2: BEGIN;
+step b3: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step m1: DELETE FROM t;
+step hj: ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a; <waiting ...>
+step c1: COMMIT;
+step hj: <... completed>
+step c3: COMMIT;
+step s2: SELECT conname, conrelid::regclass, contype, convalidated
+           FROM pg_constraint WHERE conname = 't1_nn';
+
+conname|conrelid|contype|convalidated
+-------+--------+-------+------------
+t1_nn  |t       |n      |t           
+(1 row)
+
+
+starting permutation: b1 b4 m1 hj c1 c3 s2
+step b1: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step b4: BEGIN;
+step m1: DELETE FROM t;
+step hj: ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a; <waiting ...>
+step c1: COMMIT;
+step hj: <... completed>
+step c3: COMMIT;
+step s2: SELECT conname, conrelid::regclass, contype, convalidated
+           FROM pg_constraint WHERE conname = 't1_nn';
+
+conname|conrelid|contype|convalidated
+-------+--------+-------+------------
+t1_nn  |t       |n      |t           
+(1 row)
+
+
+starting permutation: b1 b3 hj r1 c2
+step b1: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step b3: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step hj: ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a;
+ERROR:  column "a" of relation "t" contains null values
+step r1: ROLLBACK;
+step c2: ROLLBACK;
+
+starting permutation: b1 b4 d1 m1 c2 s1 s2 r1
+step b1: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step b4: BEGIN;
+step d1: DROP INDEX t_ab_idx;
+step m1: DELETE FROM t; <waiting ...>
+step c2: ROLLBACK;
+step m1: <... completed>
+step s1: ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a;
+step s2: SELECT conname, conrelid::regclass, contype, convalidated
+           FROM pg_constraint WHERE conname = 't1_nn';
+
+conname|conrelid|contype|convalidated
+-------+--------+-------+------------
+t1_nn  |t       |n      |t           
+(1 row)
+
+step r1: ROLLBACK;
+
+starting permutation: b2 b3 m1 d1 s0 s1 c1 c3 s2
+step b2: BEGIN;
+step b3: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step m1: DELETE FROM t;
+step d1: DROP INDEX t_ab_idx; <waiting ...>
+step s0: savepoint s0;
+step s1: ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a;
+step c1: COMMIT;
+step d1: <... completed>
+step c3: COMMIT;
+step s2: SELECT conname, conrelid::regclass, contype, convalidated
+           FROM pg_constraint WHERE conname = 't1_nn';
+
+conname|conrelid|contype|convalidated
+-------+--------+-------+------------
+t1_nn  |t       |n      |t           
+(1 row)
+
diff --git a/src/test/isolation/isolation_schedule b/src/test/isolation/isolation_schedule
index 143109aa4d..32d7e51aa9 100644
--- a/src/test/isolation/isolation_schedule
+++ b/src/test/isolation/isolation_schedule
@@ -55,6 +55,7 @@ test: merge-delete
 test: merge-update
 test: merge-match-recheck
 test: merge-join
+test: fast-set-notnull
 test: delete-abort-savept
 test: delete-abort-savept-2
 test: aborted-keyrevoke
diff --git a/src/test/isolation/specs/fast-set-notnull.spec b/src/test/isolation/specs/fast-set-notnull.spec
new file mode 100644
index 0000000000..a7e71b31e8
--- /dev/null
+++ b/src/test/isolation/specs/fast-set-notnull.spec
@@ -0,0 +1,43 @@
+#
+# fast not-null tests
+#
+
+setup
+{
+  CREATE TABLE t (a int, b int);
+  CREATE INDEX t_ab_idx on t(a,b);
+  INSERT INTO t values (null, 1);
+  INSERT INTO t SELECT x, x*10 FROM generate_series(1,3) g(x);
+}
+
+teardown
+{
+  DROP TABLE t;
+}
+
+session s1
+step b1  { BEGIN ISOLATION LEVEL REPEATABLE READ; }
+step b2  { BEGIN; }
+step m1  { DELETE FROM t;}
+step s0  { savepoint s0;}
+step s1  { ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a;}
+step s2  { SELECT conname, conrelid::regclass, contype, convalidated
+           FROM pg_constraint WHERE conname = 't1_nn';
+         }
+step r1  { ROLLBACK; }
+step c1  { COMMIT; }
+
+session s2
+step b3  { BEGIN ISOLATION LEVEL REPEATABLE READ; }
+step b4  { BEGIN; }
+step hj  { ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a;}
+step d1  { DROP INDEX t_ab_idx;}
+step c2  { ROLLBACK; }
+step c3  { COMMIT; }
+
+permutation b1 b3 m1 hj c1 c3 s2
+permutation b2 b3 m1 hj c1 c3 s2
+permutation b1 b4 m1 hj c1 c3 s2
+permutation b1 b3 hj r1 c2
+permutation b1 b4 d1 m1 c2 s1 s2 r1
+permutation b2 b3 m1 d1 s0 s1 c1 c3 s2
diff --git a/src/test/regress/expected/alter_table.out b/src/test/regress/expected/alter_table.out
index 362f38856d..38e247a7d4 100644
--- a/src/test/regress/expected/alter_table.out
+++ b/src/test/regress/expected/alter_table.out
@@ -4762,3 +4762,44 @@ drop publication pub1;
 drop schema alter1 cascade;
 drop schema alter2 cascade;
 NOTICE:  drop cascades to table alter2.t1
+-----fast add not-null constraint tests.
+CREATE TABLE tp (a int, b int GENERATED ALWAYS AS (22) stored) PARTITION BY range(a);
+CREATE TABLE tpp1(a int, b int GENERATED ALWAYS AS (a+1) stored);
+CREATE TABLE tpp2(a int, b int GENERATED ALWAYS AS (a+10) stored);
+ALTER TABLE tp ATTACH PARTITION tpp1 FOR values from ( 1 ) to (100);
+ALTER TABLE tp ATTACH PARTITION tpp2 default;
+CREATE INDEX ON tp(b);
+insert into tp select g from generate_series(100,120) g;
+--cannot fast ALTER TABLE SET NOT NULL or ALTER TABLE ADD CONSTRAINT NOT NULL
+--so won't interfere with the index rebuild.
+ALTER TABLE tp alter column b set not null, ALTER COLUMN b SET EXPRESSION AS (a * 3);
+ALTER TABLE tp alter column b drop not null;
+ALTER TABLE tp add constraint nna not null a;
+------test non-partitioned table
+CREATE TABLE t1(f1 INT, f2 int, f3 int,f4 int, f5 int);
+INSERT INTO t1 select g, g+1, g+2, g+3, g+4 from generate_series(1, 20) g;
+CREATE INDEX t1_f1_f2_idx ON t1(f1,f2);
+CREATE UNIQUE INDEX t1_f3idx ON t1(f3);
+CREATE INDEX t1_f3f4idx ON t1(f3) include(f4);
+CREATE INDEX hash_f5_idx ON t1 USING hash (f5 int4_ops);
+--cannot fast ALTER TABLE SET NOT NULL or ALTER TABLE ADD CONSTRAINT NOT NULL
+--so won't interfere with the index rebuild.
+ALTER TABLE t1 alter column f1 set not null, ALTER f1 TYPE BIGINT;
+ALTER TABLE t1 alter column f1 drop not null;
+ALTER TABLE t1 add constraint nn not null f1, ALTER f1 TYPE bigint;
+--cannot fast ALTER TABLE SET NOT NULL by utilizing hash index.
+ALTER TABLE t1 add constraint nn_f5 not null f5;
+--ok. with ALTER COLUMN SET NOT NULL variant
+ALTER TABLE t1 alter column f1 drop not null, alter column f2 drop not null;
+ALTER TABLE t1 alter column f2 set not null, alter column f1 set not null;
+--ok. with add constraint variants
+ALTER TABLE t1 alter column f1 drop not null, alter column f2 drop not null;
+ALTER TABLE t1 add constraint nn not null f2, add constraint nnf1 not null f1;
+--ok.
+ALTER TABLE t1 add constraint t_f3_pk primary key using index t1_f3idx;
+NOTICE:  ALTER TABLE / ADD CONSTRAINT USING INDEX will rename index "t1_f3idx" to "t_f3_pk"
+--cannot fast ALTER TABLE SET NOT NULL or ALTER TABLE ADD CONSTRAINT NOT NULL
+--for column f4 now, can only for key columns, not include column.
+ALTER TABLE t1 add constraint nnf4 not null f4;
+drop table t1;
+drop table tpp1, tpp2, tp;
diff --git a/src/test/regress/sql/alter_table.sql b/src/test/regress/sql/alter_table.sql
index 84e93ef575..cd0584b6c6 100644
--- a/src/test/regress/sql/alter_table.sql
+++ b/src/test/regress/sql/alter_table.sql
@@ -3109,3 +3109,50 @@ alter table alter1.t1 set schema alter2;
 drop publication pub1;
 drop schema alter1 cascade;
 drop schema alter2 cascade;
+
+-----fast add not-null constraint tests.
+CREATE TABLE tp (a int, b int GENERATED ALWAYS AS (22) stored) PARTITION BY range(a);
+CREATE TABLE tpp1(a int, b int GENERATED ALWAYS AS (a+1) stored);
+CREATE TABLE tpp2(a int, b int GENERATED ALWAYS AS (a+10) stored);
+ALTER TABLE tp ATTACH PARTITION tpp1 FOR values from ( 1 ) to (100);
+ALTER TABLE tp ATTACH PARTITION tpp2 default;
+CREATE INDEX ON tp(b);
+insert into tp select g from generate_series(100,120) g;
+
+--cannot fast ALTER TABLE SET NOT NULL or ALTER TABLE ADD CONSTRAINT NOT NULL
+--so won't interfere with the index rebuild.
+ALTER TABLE tp alter column b set not null, ALTER COLUMN b SET EXPRESSION AS (a * 3);
+ALTER TABLE tp alter column b drop not null;
+ALTER TABLE tp add constraint nna not null a;
+
+------test non-partitioned table
+CREATE TABLE t1(f1 INT, f2 int, f3 int,f4 int, f5 int);
+INSERT INTO t1 select g, g+1, g+2, g+3, g+4 from generate_series(1, 20) g;
+CREATE INDEX t1_f1_f2_idx ON t1(f1,f2);
+CREATE UNIQUE INDEX t1_f3idx ON t1(f3);
+CREATE INDEX t1_f3f4idx ON t1(f3) include(f4);
+CREATE INDEX hash_f5_idx ON t1 USING hash (f5 int4_ops);
+
+--cannot fast ALTER TABLE SET NOT NULL or ALTER TABLE ADD CONSTRAINT NOT NULL
+--so won't interfere with the index rebuild.
+ALTER TABLE t1 alter column f1 set not null, ALTER f1 TYPE BIGINT;
+ALTER TABLE t1 alter column f1 drop not null;
+ALTER TABLE t1 add constraint nn not null f1, ALTER f1 TYPE bigint;
+
+--cannot fast ALTER TABLE SET NOT NULL by utilizing hash index.
+ALTER TABLE t1 add constraint nn_f5 not null f5;
+
+--ok. with ALTER COLUMN SET NOT NULL variant
+ALTER TABLE t1 alter column f1 drop not null, alter column f2 drop not null;
+ALTER TABLE t1 alter column f2 set not null, alter column f1 set not null;
+--ok. with add constraint variants
+ALTER TABLE t1 alter column f1 drop not null, alter column f2 drop not null;
+ALTER TABLE t1 add constraint nn not null f2, add constraint nnf1 not null f1;
+--ok.
+ALTER TABLE t1 add constraint t_f3_pk primary key using index t1_f3idx;
+
+--cannot fast ALTER TABLE SET NOT NULL or ALTER TABLE ADD CONSTRAINT NOT NULL
+--for column f4 now, can only for key columns, not include column.
+ALTER TABLE t1 add constraint nnf4 not null f4;
+drop table t1;
+drop table tpp1, tpp2, tp;
-- 
2.34.1

From 0b4ad35e8fbc46f93ba6df2ef7013ff2f3055216 Mon Sep 17 00:00:00 2001
From: jian he <jian.universality@gmail.com>
Date: Fri, 18 Apr 2025 16:05:42 +0800
Subject: [PATCH v4 1/1] using indexscan to speedup add not null constraints

This patch tries to use index_beginscan() / index_getnext() / index_endscan()
mentioned in [1] to speedup adding not-null constraints to the existing table.

the main logic happen in phase3 ATRewriteTable
1. collect all not-null constraints.
2. does each not-null constraint have a corresponding index to vertify it, if
   not then do the normal processing.
3. if table scan, table rewrite, table was not in AccessExclusiveLock.
   not-null constraint was on virtual generated column
   then we can not use indexcan to fast check not-null constraint.
3. If a table scan or rewrite occurs and the table is not held with an
   AccessExclusiveLock, and the NOT NULL constraint is on a virtual generated
   column, then we can not use indexscan to fast validate not-null constraints.

concurrency concern:
ALTER TABLE SET NOT NULL will take an ACCESS EXCLUSIVE lock, so there is less
variant of racing issue can occur?  to prove accurate, I wrote some isolation
tests. see[2]

performance:
It will only be slower than usual to add a NOT NULL constraint if your index is
bloated and a significant portion of that bloat is due to rows with NULL values.

demo:
drop table if exists t;
create unlogged table t(a int, b int, c int) with (autovacuum_enabled = off);
insert into t select g, g+1 from generate_series(1,1_000_000) g;
create index t_idx_a on t(a);

COMMAND: alter table t add constraint t1 not null a;
patch Time: 1.178 ms
master Time:  15.137 ms

100% table bloat: via (delete from t)
COMMAND: alter table t add constraint t1 not null a;
patch Time:   0.962 ms
master Time: 16.404 ms

case when: %20 percent values are NULL and have been deleted from heap but they
still on the index.

drop table if exists t;
create unlogged table t(a int, b int) with (autovacuum_enabled = off);
insert into t select case when g % 5 = 0 then null else g end, g+1
from generate_series(1,1_000_000) g;
create index t_idx_a on t(a);
delete from t where a is null;

alter table t add constraint t1 not null a;
patch Time:: 17.443 ms
master Time: 23.045 ms

references:
[1] https://postgr.es/m/CA%2BTgmoa5NKz8iGW_9v7wz%3D-%2BzQFu%3DE4SZoaTaU1znLaEXRYp-Q%40mail.gmail.com
[2] https://postgr.es/m/900056D1-32DF-4927-8251-3E0C0DC407FD%40anarazel.de
discussion: https://postgr.es/m/CACJufxFiW=4k1is=F1J=r-Cx1RuByXQPUrWB331U47rSnGz+hw@mail.gmail.com
commitfest entry: https://commitfest.postgresql.org/patch/5444/
---
 src/backend/commands/tablecmds.c              | 129 ++++++++++-
 src/backend/executor/execIndexing.c           | 200 ++++++++++++++++++
 src/include/executor/executor.h               |   2 +
 .../expected/indexscan-check-notnull.out      | 102 +++++++++
 src/test/isolation/isolation_schedule         |   1 +
 .../specs/indexscan-check-notnull.spec        |  45 ++++
 src/test/regress/expected/aggregates.out      |   1 +
 src/test/regress/expected/alter_table.out     |  42 ++++
 src/test/regress/expected/indexing.out        |   2 +
 src/test/regress/expected/publication.out     |   1 +
 src/test/regress/expected/tablespace.out      |   1 +
 src/test/regress/sql/alter_table.sql          |  46 ++++
 12 files changed, 566 insertions(+), 6 deletions(-)
 create mode 100644 src/test/isolation/expected/indexscan-check-notnull.out
 create mode 100644 src/test/isolation/specs/indexscan-check-notnull.spec

diff --git a/src/backend/commands/tablecmds.c b/src/backend/commands/tablecmds.c
index b3ed69457fc..01011a72aea 100644
--- a/src/backend/commands/tablecmds.c
+++ b/src/backend/commands/tablecmds.c
@@ -209,16 +209,19 @@ typedef struct AlteredTableInfo
 	List	   *changedStatisticsDefs;	/* string definitions of same */
 } AlteredTableInfo;
 
-/* Struct describing one new constraint to check in Phase 3 scan */
-/* Note: new not-null constraints are handled elsewhere */
+/*
+ * Struct describing one new constraint to check in Phase 3 scan. Note: new
+ * not-null constraints are handled here too.
+*/
 typedef struct NewConstraint
 {
 	char	   *name;			/* Constraint name, or NULL if none */
-	ConstrType	contype;		/* CHECK or FOREIGN */
+	ConstrType	contype;		/* CHECK or FOREIGN or NOT-NULL */
 	Oid			refrelid;		/* PK rel, if FOREIGN */
 	Oid			refindid;		/* OID of PK's index, if FOREIGN */
 	bool		conwithperiod;	/* Whether the new FOREIGN KEY uses PERIOD */
 	Oid			conid;			/* OID of pg_constraint entry, if FOREIGN */
+	int			attnum;			/* NOT-NULL constraint attnum */
 	Node	   *qual;			/* Check expr or CONSTR_FOREIGN Constraint */
 	ExprState  *qualstate;		/* Execution state for CHECK expr */
 } NewConstraint;
@@ -6128,6 +6131,7 @@ ATRewriteTable(AlteredTableInfo *tab, Oid OIDNewHeap)
 	BulkInsertState bistate;
 	int			ti_options;
 	ExprState  *partqualstate = NULL;
+	bool		add_index = false;
 
 	/*
 	 * Open the relation(s).  We have surely already locked the existing
@@ -6181,6 +6185,9 @@ ATRewriteTable(AlteredTableInfo *tab, Oid OIDNewHeap)
 				needscan = true;
 				con->qualstate = ExecPrepareExpr((Expr *) expand_generated_columns_in_expr(con->qual, oldrel, 1), estate);
 				break;
+			case CONSTR_NOTNULL:
+				/* Nothing to do here */
+				break;
 			case CONSTR_FOREIGN:
 				/* Nothing to do here */
 				break;
@@ -6234,10 +6241,85 @@ ATRewriteTable(AlteredTableInfo *tab, Oid OIDNewHeap)
 														wholeatt->attnum);
 			}
 		}
-		if (notnull_attrs || notnull_virtual_attrs)
-			needscan = true;
 	}
 
+	/*
+	 * we better use existsing index to check not-null constraint, rather than
+	 * through underlying index created by this command.  XXX TODO maybe this is
+	 * not necessary?
+	*/
+	for (AlterTablePass pass = 0; pass < AT_NUM_PASSES; pass++)
+	{
+		List	   *subcmds = tab->subcmds[pass];
+
+		if (subcmds == NIL)
+			continue;
+
+		foreach_node(AlterTableCmd, cmd, subcmds)
+		{
+			if (cmd->subtype == AT_AddIndex ||
+				cmd->subtype == AT_ReAddIndex ||
+				cmd->subtype == AT_AddIndexConstraint)
+				add_index = true;
+		}
+	}
+
+	/*
+	 * The conditions for using indexscan mechanism fast checking not-null
+	 * constraints are quite strict.  If a table scan or rewrite is expected to
+	 * occur later, using indexscan would just waste cycle.  Additionally,
+	 * indexes cannot be created on virtual generated columns, so fast checking
+	 * not-null constraints is not applicable to them.  This optimization is
+	 * also limited to regular relations.
+	 *
+	 * To avoid concurrency issue, we only do it when table was locked in
+	 * AccessExclusiveLock.
+	*/
+	if (!needscan && notnull_virtual_attrs == NIL &&
+		newrel == NULL && !tab->rewrite &&
+		oldrel->rd_rel->relkind == RELKIND_RELATION &&
+		!add_index &&
+		CheckRelationLockedByMe(oldrel, AccessExclusiveLock, false))
+	{
+		List	   *notnull_attnums = NIL;
+
+		foreach(l, tab->constraints)
+		{
+			NewConstraint *con = lfirst(l);
+
+			Form_pg_attribute attr = TupleDescAttr(newTupDesc, con->attnum - 1);
+
+			if (con->contype != CONSTR_NOTNULL)
+				continue;
+
+			Assert(attr->attnotnull);
+			Assert(con->attnum > 0);
+			Assert(attr->attnum == con->attnum);
+
+			if (attr->attgenerated == ATTRIBUTE_GENERATED_VIRTUAL)
+			{
+				needscan = true;
+				break;
+			}
+
+			notnull_attnums = lappend_int(notnull_attnums, attr->attnum);
+		}
+
+		if (notnull_attnums != NIL)
+		{
+			Assert(CheckRelationLockedByMe(oldrel, AccessExclusiveLock, false));
+
+			if (!index_check_notnull(oldrel, notnull_attnums))
+				needscan = true;
+			else
+				ereport(NOTICE,
+						errmsg("all not-null constraints on relation \"%s\" are validated by index scan",
+								RelationGetRelationName(oldrel)));
+		}
+	}
+	else if (notnull_attrs || notnull_virtual_attrs)
+		needscan = true;
+
 	if (newrel || needscan)
 	{
 		ExprContext *econtext;
@@ -7909,6 +7991,7 @@ ATExecSetNotNull(List **wqueue, Relation rel, char *conName, char *colName,
 	CookedConstraint *ccon;
 	List	   *cooked;
 	bool		is_no_inherit = false;
+	AlteredTableInfo *tab = NULL;
 
 	/* Guard against stack overflow due to overly deep inheritance tree. */
 	check_stack_depth();
@@ -8033,10 +8116,31 @@ ATExecSetNotNull(List **wqueue, Relation rel, char *conName, char *colName,
 	constraint->is_no_inherit = is_no_inherit;
 	constraint->conname = conName;
 
+	tab = ATGetQueueEntry(wqueue, rel);
+
 	/* and do it */
 	cooked = AddRelationNewConstraints(rel, NIL, list_make1(constraint),
 									   false, !recursing, false, NULL);
 	ccon = linitial(cooked);
+
+	Assert(ccon->contype == CONSTR_NOTNULL);
+
+	/*
+	 * we may use indexscan to fast check not-null constraint. To do that, we
+	 * need add the not-null constraint to AlteredTableInfo->constraints.
+	*/
+	if (!ccon->skip_validation)
+	{
+		NewConstraint *newcon;
+		newcon = (NewConstraint *) palloc0(sizeof(NewConstraint));
+
+		newcon->name = ccon->name;
+		newcon->contype = ccon->contype;
+		newcon->attnum = ccon->attnum;
+
+		tab->constraints = lappend(tab->constraints, newcon);
+	}
+
 	ObjectAddressSet(address, ConstraintRelationId, ccon->conoid);
 
 	InvokeObjectPostAlterHook(RelationRelationId,
@@ -9887,13 +9991,15 @@ ATAddCheckNNConstraint(List **wqueue, AlteredTableInfo *tab, Relation rel,
 	{
 		CookedConstraint *ccon = (CookedConstraint *) lfirst(lcon);
 
-		if (!ccon->skip_validation && ccon->contype != CONSTR_NOTNULL)
+		if (!ccon->skip_validation)
 		{
 			NewConstraint *newcon;
 
 			newcon = (NewConstraint *) palloc0(sizeof(NewConstraint));
 			newcon->name = ccon->name;
 			newcon->contype = ccon->contype;
+			if (ccon->contype == CONSTR_NOTNULL)
+				newcon->attnum = ccon->attnum;
 			newcon->qual = ccon->expr;
 
 			tab->constraints = lappend(tab->constraints, newcon);
@@ -13146,6 +13252,7 @@ QueueNNConstraintValidation(List **wqueue, Relation conrel, Relation rel,
 	List	   *children = NIL;
 	AttrNumber	attnum;
 	char	   *colname;
+	NewConstraint *newcon;
 
 	con = (Form_pg_constraint) GETSTRUCT(contuple);
 	Assert(con->contype == CONSTRAINT_NOTNULL);
@@ -13209,7 +13316,17 @@ QueueNNConstraintValidation(List **wqueue, Relation conrel, Relation rel,
 	/* Set attnotnull appropriately without queueing another validation */
 	set_attnotnull(NULL, rel, attnum, true, false);
 
+	/* Queue validation for phase 3 */
+	newcon = (NewConstraint *) palloc0(sizeof(NewConstraint));
+	newcon->name = colname;
+	newcon->contype = CONSTR_NOTNULL;
+	newcon->attnum = attnum;
+
+	/* Find or create work queue entry for this table */
 	tab = ATGetQueueEntry(wqueue, rel);
+
+	tab->constraints = lappend(tab->constraints, newcon);
+
 	tab->verify_new_notnull = true;
 
 	/*
diff --git a/src/backend/executor/execIndexing.c b/src/backend/executor/execIndexing.c
index bdf862b2406..92a0e692d01 100644
--- a/src/backend/executor/execIndexing.c
+++ b/src/backend/executor/execIndexing.c
@@ -108,12 +108,15 @@
 
 #include "access/genam.h"
 #include "access/relscan.h"
+#include "access/table.h"
 #include "access/tableam.h"
 #include "access/xact.h"
 #include "catalog/index.h"
+#include "catalog/pg_am_d.h"
 #include "executor/executor.h"
 #include "nodes/nodeFuncs.h"
 #include "storage/lmgr.h"
+#include "utils/fmgroids.h"
 #include "utils/multirangetypes.h"
 #include "utils/rangetypes.h"
 #include "utils/snapmgr.h"
@@ -145,6 +148,7 @@ static bool index_expression_changed_walker(Node *node,
 											Bitmapset *allUpdatedCols);
 static void ExecWithoutOverlapsNotEmpty(Relation rel, NameData attname, Datum attval,
 										char typtype, Oid atttypid);
+static bool index_check_notnull_internal(Relation relation, List *attnums, List *idxs);
 
 /* ----------------------------------------------------------------
  *		ExecOpenIndices
@@ -1172,3 +1176,199 @@ ExecWithoutOverlapsNotEmpty(Relation rel, NameData attname, Datum attval, char t
 				 errmsg("empty WITHOUT OVERLAPS value found in column \"%s\" in relation \"%s\"",
 						NameStr(attname), RelationGetRelationName(rel))));
 }
+
+/*
+ * notnull_attnums: Attribute numbers for all newly added NOT NULL constraints.
+ *
+ * First check if relation have suitable index for each notnull_attnums. If it
+ * does, using indexscan mechanism to verify that all attributes on
+ * notnull_attnums are indeed NOT NULL.
+ */
+bool
+index_check_notnull(Relation relation, List *notnull_attnums)
+{
+	Relation	indrel;
+	Relation	index_rel;
+	SysScanDesc indscan;
+	ScanKeyData skey;
+	HeapTuple	htup;
+	TupleDesc	tupdesc;
+	Form_pg_attribute attr;
+	List	   *result = NIL;
+	List	   *attnums = NIL;
+
+	tupdesc = RelationGetDescr(relation);
+
+	/* Prepare to scan pg_index for entries having indrelid = this rel. */
+	ScanKeyInit(&skey,
+				Anum_pg_index_indrelid,
+				BTEqualStrategyNumber, F_OIDEQ,
+				ObjectIdGetDatum(RelationGetRelid(relation)));
+
+	indrel = table_open(IndexRelationId, AccessShareLock);
+	indscan = systable_beginscan(indrel, IndexIndrelidIndexId, true,
+								 NULL, 1, &skey);
+
+	while (HeapTupleIsValid(htup = systable_getnext(indscan)))
+	{
+		Form_pg_index index = (Form_pg_index) GETSTRUCT(htup);
+
+		/*
+		 * we can only use non-deferred, valid, and alive btree index to fast
+		 * check not-null
+		 */
+		if (!index->indimmediate || !index->indisvalid || !index->indislive)
+			continue;
+
+		/* can not use expression index or partical index too */
+		if (!heap_attisnull(htup, Anum_pg_index_indexprs, NULL) ||
+			!heap_attisnull(htup, Anum_pg_index_indpred, NULL))
+			continue;
+
+		for (int i = 0; i < index->indnkeyatts; i++)
+		{
+			attr = TupleDescAttr(tupdesc, (index->indkey.values[i] - 1));
+
+			if (list_member_int(notnull_attnums, attr->attnum))
+			{
+				index_rel = index_open(index->indexrelid, AccessShareLock);
+
+				if (index_rel->rd_rel->relkind == RELKIND_INDEX &&
+					index_rel->rd_rel->relam == BTREE_AM_OID &&
+					!list_member_int(attnums, attr->attnum))
+				{
+					attnums = lappend_int(attnums, attr->attnum);
+					result = lappend_oid(result, index->indexrelid);
+				}
+				index_close(index_rel, AccessShareLock);
+			}
+		}
+	}
+	systable_endscan(indscan);
+	table_close(indrel, AccessShareLock);
+
+	if (attnums == NIL)
+		return false;
+
+	/*
+	 * every not-null constraint requires an index for fast validatation.
+	 * Without an index, we better use normal tablescan to validate the not-null
+	 * constraints
+	*/
+	foreach_int(attno, notnull_attnums)
+	{
+		if(!list_member_int(attnums, attno))
+			return false;
+	}
+
+	return index_check_notnull_internal(relation, attnums, result);
+}
+
+/*
+ * Use indexscan mechanism to fast check each attribute in "attnums" are
+ * not-null or not.
+ */
+static bool
+index_check_notnull_internal(Relation relation, List *attnums, List *idxs)
+{
+	EState	   *estate;
+	ExprContext *econtext;
+	TupleTableSlot *existing_slot;
+	bool 		all_not_null = true;
+	ListCell   *lc,
+				*lc2;
+
+	/*
+	 * Need an EState for slot to hold the current tuple.
+	 *
+	*/
+	estate = CreateExecutorState();
+	econtext = GetPerTupleExprContext(estate);
+
+	forboth(lc, attnums, lc2, idxs)
+	{
+		SnapshotData DirtySnapshot;
+		IndexScanDesc index_scan;
+		ScanKeyData		scankeys[INDEX_MAX_KEYS];
+		IndexInfo  	*indexInfo;
+		AttrNumber	sk_attno = -1;
+		Relation 	index;
+		int			indnkeyatts;
+
+		AttrNumber	attno = lfirst_int(lc);
+		Oid		indexoid = lfirst_oid(lc2);
+
+		existing_slot = table_slot_create(relation, NULL);
+
+		/* Arrange for econtext's scan tuple to be the tuple under test */
+		econtext->ecxt_scantuple = existing_slot;
+
+		index = index_open(indexoid, AccessShareLock);
+
+		indexInfo = BuildIndexInfo(index);
+		indnkeyatts = IndexRelationGetNumberOfKeyAttributes(index);
+
+		/*
+		 * Search the tuples that are in the index for any violations, including
+		 * tuples that aren't visible yet.
+		*/
+		InitDirtySnapshot(DirtySnapshot);
+
+		for (int i = 0; i < indnkeyatts; i++)
+		{
+			if (indexInfo->ii_IndexAttrNumbers[i] == attno)
+			{
+				sk_attno = i+1;
+				break;
+			}
+		}
+
+		if (sk_attno == -1)
+			elog(ERROR, "index %u should effect on column number %d", indexoid, attno);
+
+		for (int i = 0; i < indnkeyatts; i++)
+		{
+			/* set up an IS NULL scan key so that we ignore not nulls */
+			ScanKeyEntryInitialize(&scankeys[i],
+									SK_ISNULL | SK_SEARCHNULL,
+									sk_attno,		/* index col to scan */
+									InvalidStrategy,/* no strategy */
+									InvalidOid,		/* no strategy subtype */
+									InvalidOid,		/* no collation */
+									InvalidOid,		/* no reg proc for this */
+									(Datum) 0);		/* constant */
+		}
+
+		index_scan = index_beginscan(relation, index, &DirtySnapshot, NULL, indnkeyatts, 0);
+		index_rescan(index_scan, scankeys, indnkeyatts, NULL, 0);
+
+		while (index_getnext_slot(index_scan, ForwardScanDirection, existing_slot))
+		{
+			Datum		values[INDEX_MAX_KEYS];
+			bool		nulls[INDEX_MAX_KEYS];
+
+			/*
+			 * Extract the index column values and isnull flags from the
+			 * existing tuple.
+			*/
+			FormIndexDatum(indexInfo, existing_slot, estate, values, nulls);
+
+			if (nulls[sk_attno - 1])
+			{
+				all_not_null = false;
+				break;
+			}
+		}
+
+		index_endscan(index_scan);
+		index_close(index, AccessShareLock);
+		ExecDropSingleTupleTableSlot(existing_slot);
+		if (!all_not_null)
+			return false;
+	}
+
+	FreeExecutorState(estate);
+
+	return true;
+}
+
diff --git a/src/include/executor/executor.h b/src/include/executor/executor.h
index ae99407db89..f42407ed75e 100644
--- a/src/include/executor/executor.h
+++ b/src/include/executor/executor.h
@@ -778,6 +778,8 @@ extern void check_exclusion_constraint(Relation heap, Relation index,
 									   const Datum *values, const bool *isnull,
 									   EState *estate, bool newIndex);
 
+extern bool index_check_notnull(Relation relation, List *notnull_attnums);
+
 /*
  * prototypes from functions in execReplication.c
  */
diff --git a/src/test/isolation/expected/indexscan-check-notnull.out b/src/test/isolation/expected/indexscan-check-notnull.out
new file mode 100644
index 00000000000..ac3b9f14c89
--- /dev/null
+++ b/src/test/isolation/expected/indexscan-check-notnull.out
@@ -0,0 +1,102 @@
+Parsed test spec with 2 sessions
+
+starting permutation: b1 b3 m1 hj c1 c3 sn
+step b1: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step b3: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step m1: DELETE FROM t;
+step hj: ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a; <waiting ...>
+step c1: COMMIT;
+s2: NOTICE:  all not-null constraints on relation "t" are validated by index scan
+step hj: <... completed>
+step c3: COMMIT;
+step sn: SELECT conname, conrelid::regclass, contype, convalidated
+           FROM pg_constraint WHERE conname = 't1_nn';
+
+conname|conrelid|contype|convalidated
+-------+--------+-------+------------
+t1_nn  |t       |n      |t           
+(1 row)
+
+
+starting permutation: b2 b3 m1 hj c1 c3 sn
+step b2: BEGIN;
+step b3: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step m1: DELETE FROM t;
+step hj: ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a; <waiting ...>
+step c1: COMMIT;
+s2: NOTICE:  all not-null constraints on relation "t" are validated by index scan
+step hj: <... completed>
+step c3: COMMIT;
+step sn: SELECT conname, conrelid::regclass, contype, convalidated
+           FROM pg_constraint WHERE conname = 't1_nn';
+
+conname|conrelid|contype|convalidated
+-------+--------+-------+------------
+t1_nn  |t       |n      |t           
+(1 row)
+
+
+starting permutation: b1 b4 m1 hj c1 c3 sn
+step b1: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step b4: BEGIN;
+step m1: DELETE FROM t;
+step hj: ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a; <waiting ...>
+step c1: COMMIT;
+s2: NOTICE:  all not-null constraints on relation "t" are validated by index scan
+step hj: <... completed>
+step c3: COMMIT;
+step sn: SELECT conname, conrelid::regclass, contype, convalidated
+           FROM pg_constraint WHERE conname = 't1_nn';
+
+conname|conrelid|contype|convalidated
+-------+--------+-------+------------
+t1_nn  |t       |n      |t           
+(1 row)
+
+
+starting permutation: b1 b3 hj r1 c2
+step b1: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step b3: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step hj: ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a;
+ERROR:  column "a" of relation "t" contains null values
+step r1: ROLLBACK;
+step c2: ROLLBACK;
+
+starting permutation: b1 b4 d1 m1 c2 s1 sn r1
+step b1: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step b4: BEGIN;
+step d1: DROP INDEX t_ab_idx;
+step m1: DELETE FROM t; <waiting ...>
+step c2: ROLLBACK;
+step m1: <... completed>
+s1: NOTICE:  all not-null constraints on relation "t" are validated by index scan
+step s1: ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a;
+step sn: SELECT conname, conrelid::regclass, contype, convalidated
+           FROM pg_constraint WHERE conname = 't1_nn';
+
+conname|conrelid|contype|convalidated
+-------+--------+-------+------------
+t1_nn  |t       |n      |t           
+(1 row)
+
+step r1: ROLLBACK;
+
+starting permutation: b2 b3 m1 d1 s0 s1 c1 c3 sn
+step b2: BEGIN;
+step b3: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step m1: DELETE FROM t;
+step d1: DROP INDEX t_ab_idx; <waiting ...>
+step s0: savepoint s0;
+s1: NOTICE:  all not-null constraints on relation "t" are validated by index scan
+step s1: ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a;
+step c1: COMMIT;
+step d1: <... completed>
+step c3: COMMIT;
+step sn: SELECT conname, conrelid::regclass, contype, convalidated
+           FROM pg_constraint WHERE conname = 't1_nn';
+
+conname|conrelid|contype|convalidated
+-------+--------+-------+------------
+t1_nn  |t       |n      |t           
+(1 row)
+
diff --git a/src/test/isolation/isolation_schedule b/src/test/isolation/isolation_schedule
index e3c669a29c7..1b9e8f932ac 100644
--- a/src/test/isolation/isolation_schedule
+++ b/src/test/isolation/isolation_schedule
@@ -56,6 +56,7 @@ test: merge-delete
 test: merge-update
 test: merge-match-recheck
 test: merge-join
+test: indexscan-check-notnull
 test: delete-abort-savept
 test: delete-abort-savept-2
 test: aborted-keyrevoke
diff --git a/src/test/isolation/specs/indexscan-check-notnull.spec b/src/test/isolation/specs/indexscan-check-notnull.spec
new file mode 100644
index 00000000000..d0ca928f3af
--- /dev/null
+++ b/src/test/isolation/specs/indexscan-check-notnull.spec
@@ -0,0 +1,45 @@
+
+#
+# using indexscan to check a column not-null constraint
+# is satisfied or not.
+#
+
+setup
+{
+  CREATE TABLE t (a int, b int);
+  CREATE INDEX t_ab_idx on t(a,b);
+  INSERT INTO t values (null, 1);
+  INSERT INTO t SELECT x, x*10 FROM generate_series(1,3) g(x);
+}
+
+teardown
+{
+  DROP TABLE t;
+}
+
+session s1
+step b1  { BEGIN ISOLATION LEVEL REPEATABLE READ; }
+step b2  { BEGIN; }
+step m1  { DELETE FROM t;}
+step s0  { savepoint s0;}
+step s1  { ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a;}
+step sn  { SELECT conname, conrelid::regclass, contype, convalidated
+           FROM pg_constraint WHERE conname = 't1_nn';
+         }
+step r1  { ROLLBACK; }
+step c1  { COMMIT; }
+
+session s2
+step b3  { BEGIN ISOLATION LEVEL REPEATABLE READ; }
+step b4  { BEGIN; }
+step hj  { ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a;}
+step d1  { DROP INDEX t_ab_idx;}
+step c2  { ROLLBACK; }
+step c3  { COMMIT; }
+
+permutation b1 b3 m1 hj c1 c3 sn
+permutation b2 b3 m1 hj c1 c3 sn
+permutation b1 b4 m1 hj c1 c3 sn
+permutation b1 b3 hj r1 c2
+permutation b1 b4 d1 m1 c2 s1 sn r1
+permutation b2 b3 m1 d1 s0 s1 c1 c3 sn
diff --git a/src/test/regress/expected/aggregates.out b/src/test/regress/expected/aggregates.out
index 6b6371c3e74..6dab127f73b 100644
--- a/src/test/regress/expected/aggregates.out
+++ b/src/test/regress/expected/aggregates.out
@@ -1461,6 +1461,7 @@ explain (costs off) select y,z from t2 group by y,z;
 
 -- Make the column NOT NULL and ensure we remove the redundant column
 alter table t2 alter column z set not null;
+NOTICE:  all not-null constraints on relation "t2" are validated by index scan
 explain (costs off) select y,z from t2 group by y,z;
       QUERY PLAN      
 ----------------------
diff --git a/src/test/regress/expected/alter_table.out b/src/test/regress/expected/alter_table.out
index 476266e3f4b..a00fe5175ba 100644
--- a/src/test/regress/expected/alter_table.out
+++ b/src/test/regress/expected/alter_table.out
@@ -4833,3 +4833,45 @@ drop publication pub1;
 drop schema alter1 cascade;
 drop schema alter2 cascade;
 NOTICE:  drop cascades to table alter2.t1
+-----fast add not-null constraint tests.
+CREATE TABLE tp (a int, b int GENERATED ALWAYS AS (22) stored) PARTITION BY range(a);
+CREATE TABLE tpp1(a int, b int GENERATED ALWAYS AS (a+1) stored);
+CREATE TABLE tpp2(a int, b int GENERATED ALWAYS AS (a+10) stored);
+ALTER TABLE tp ATTACH PARTITION tpp1 FOR values from ( 1 ) to (10);
+ALTER TABLE tp ATTACH PARTITION tpp2 FOR values from ( 10 ) to (21);
+INSERT INTO tp select g from generate_series(1,19) g;
+CREATE INDEX ON tp(b);
+ALTER TABLE tp alter column b set not null;
+NOTICE:  all not-null constraints on relation "tpp1" are validated by index scan
+NOTICE:  all not-null constraints on relation "tpp2" are validated by index scan
+ALTER TABLE tp alter column b drop not null;
+ALTER TABLE tpp1 alter column b set not null;
+NOTICE:  all not-null constraints on relation "tpp1" are validated by index scan
+ALTER TABLE tpp2 alter column b set not null;
+NOTICE:  all not-null constraints on relation "tpp2" are validated by index scan
+ALTER TABLE tp alter column b drop not null;
+ALTER TABLE tp alter column b set not null, ALTER COLUMN b SET EXPRESSION AS (a * 3);
+------test non-partitioned table
+CREATE TABLE t1(f1 INT, f2 int, f3 int,f4 int, f5 int);
+INSERT INTO t1 select g, g+1, g+2, g+3, g+4 from generate_series(1, 100) g;
+CREATE INDEX t1_f1_f2_idx ON t1(f1,f2);
+CREATE UNIQUE INDEX t1_f3idx ON t1(f3);
+CREATE INDEX t1_f3f4idx ON t1(f3) include(f4);
+CREATE INDEX hash_f5_idx ON t1 USING hash (f5 int4_ops);
+--table rewrite, so can not use indexscan to check not-null constraint.
+ALTER TABLE t1 alter column f1 set not null, ALTER f1 TYPE BIGINT;
+ALTER TABLE t1 alter column f1 drop not null;
+ALTER TABLE t1 add constraint nn not null f1, ALTER f1 TYPE BIGINT; --now ok
+ALTER TABLE t1 alter column f1 drop not null, alter column f2 drop not null;
+INSERT INTO t1 values(11, NULL, 1,2,3);
+ALTER TABLE t1 alter column f2 set not null, alter column f1 set not null; --error
+ERROR:  column "f2" of relation "t1" contains null values
+DELETE FROM t1 where f1 = 11;
+ALTER TABLE t1 alter column f2 set not null, alter column f1 set not null; --ok
+NOTICE:  all not-null constraints on relation "t1" are validated by index scan
+--using indexscan to check not-null can only apply to key columns, not include column
+ALTER TABLE t1 add constraint nnf4 not null f4;
+--cannot fast ALTER TABLE SET NOT NULL by utilizing hash index.
+ALTER TABLE t1 add constraint nn_f5 not null f5;
+drop table t1;
+drop table tpp1, tpp2, tp;
diff --git a/src/test/regress/expected/indexing.out b/src/test/regress/expected/indexing.out
index bcf1db11d73..5f106c74d87 100644
--- a/src/test/regress/expected/indexing.out
+++ b/src/test/regress/expected/indexing.out
@@ -1186,6 +1186,7 @@ create table idxpart0 partition of idxpart (i) for values with (modulus 2, remai
 create table idxpart1 partition of idxpart (i) for values with (modulus 2, remainder 1);
 alter table idxpart0 add primary key(i);
 alter table idxpart add primary key(i);
+NOTICE:  all not-null constraints on relation "idxpart1" are validated by index scan
 select indrelid::regclass, indexrelid::regclass, inhparent::regclass, indisvalid,
   conname, conislocal, coninhcount, connoinherit, convalidated
   from pg_index idx left join pg_inherits inh on (idx.indexrelid = inh.inhrelid)
@@ -1279,6 +1280,7 @@ alter table idxpart attach partition idxpart0 default;
 alter table only idxpart add primary key (a);  -- fail, no not-null constraint
 ERROR:  column "a" of table "idxpart0" is not marked NOT NULL
 alter table idxpart0 alter column a set not null;
+NOTICE:  all not-null constraints on relation "idxpart0" are validated by index scan
 alter table only idxpart add primary key (a);  -- now it works
 alter index idxpart_pkey attach partition idxpart0_a_key;
 drop table idxpart;
diff --git a/src/test/regress/expected/publication.out b/src/test/regress/expected/publication.out
index 4de96c04f9d..e985d4f5022 100644
--- a/src/test/regress/expected/publication.out
+++ b/src/test/regress/expected/publication.out
@@ -778,6 +778,7 @@ ALTER PUBLICATION testpub_fortable_insert ADD TABLE testpub_tbl5 (b, c);
 /* not all replica identities are good enough */
 CREATE UNIQUE INDEX testpub_tbl5_b_key ON testpub_tbl5 (b, c);
 ALTER TABLE testpub_tbl5 ALTER b SET NOT NULL, ALTER c SET NOT NULL;
+NOTICE:  all not-null constraints on relation "testpub_tbl5" are validated by index scan
 ALTER TABLE testpub_tbl5 REPLICA IDENTITY USING INDEX testpub_tbl5_b_key;
 -- error: replica identity (b,c) is not covered by column list (a, c)
 UPDATE testpub_tbl5 SET a = 1;
diff --git a/src/test/regress/expected/tablespace.out b/src/test/regress/expected/tablespace.out
index a90e39e5738..d28bccb5378 100644
--- a/src/test/regress/expected/tablespace.out
+++ b/src/test/regress/expected/tablespace.out
@@ -603,6 +603,7 @@ INSERT INTO testschema.test_default_tab_p VALUES (1);
 CREATE INDEX test_index1 on testschema.test_default_tab_p (val);
 CREATE INDEX test_index2 on testschema.test_default_tab_p (val) TABLESPACE regress_tblspace;
 ALTER TABLE testschema.test_default_tab_p ADD CONSTRAINT test_index3 PRIMARY KEY (id);
+NOTICE:  all not-null constraints on relation "test_default_tab_p1" are validated by index scan
 ALTER TABLE testschema.test_default_tab_p ADD CONSTRAINT test_index4 UNIQUE (id) USING INDEX TABLESPACE regress_tblspace;
 \d testschema.test_index1
 Partitioned index "testschema.test_index1"
diff --git a/src/test/regress/sql/alter_table.sql b/src/test/regress/sql/alter_table.sql
index 5ce9d1e429f..626fd3798f8 100644
--- a/src/test/regress/sql/alter_table.sql
+++ b/src/test/regress/sql/alter_table.sql
@@ -3125,3 +3125,49 @@ alter table alter1.t1 set schema alter2;
 drop publication pub1;
 drop schema alter1 cascade;
 drop schema alter2 cascade;
+
+-----fast add not-null constraint tests.
+CREATE TABLE tp (a int, b int GENERATED ALWAYS AS (22) stored) PARTITION BY range(a);
+CREATE TABLE tpp1(a int, b int GENERATED ALWAYS AS (a+1) stored);
+CREATE TABLE tpp2(a int, b int GENERATED ALWAYS AS (a+10) stored);
+ALTER TABLE tp ATTACH PARTITION tpp1 FOR values from ( 1 ) to (10);
+ALTER TABLE tp ATTACH PARTITION tpp2 FOR values from ( 10 ) to (21);
+INSERT INTO tp select g from generate_series(1,19) g;
+CREATE INDEX ON tp(b);
+
+ALTER TABLE tp alter column b set not null;
+ALTER TABLE tp alter column b drop not null;
+
+ALTER TABLE tpp1 alter column b set not null;
+ALTER TABLE tpp2 alter column b set not null;
+
+ALTER TABLE tp alter column b drop not null;
+ALTER TABLE tp alter column b set not null, ALTER COLUMN b SET EXPRESSION AS (a * 3);
+
+------test non-partitioned table
+CREATE TABLE t1(f1 INT, f2 int, f3 int,f4 int, f5 int);
+INSERT INTO t1 select g, g+1, g+2, g+3, g+4 from generate_series(1, 100) g;
+CREATE INDEX t1_f1_f2_idx ON t1(f1,f2);
+CREATE UNIQUE INDEX t1_f3idx ON t1(f3);
+CREATE INDEX t1_f3f4idx ON t1(f3) include(f4);
+CREATE INDEX hash_f5_idx ON t1 USING hash (f5 int4_ops);
+
+--table rewrite, so can not use indexscan to check not-null constraint.
+ALTER TABLE t1 alter column f1 set not null, ALTER f1 TYPE BIGINT;
+ALTER TABLE t1 alter column f1 drop not null;
+ALTER TABLE t1 add constraint nn not null f1, ALTER f1 TYPE BIGINT; --now ok
+
+ALTER TABLE t1 alter column f1 drop not null, alter column f2 drop not null;
+INSERT INTO t1 values(11, NULL, 1,2,3);
+ALTER TABLE t1 alter column f2 set not null, alter column f1 set not null; --error
+DELETE FROM t1 where f1 = 11;
+ALTER TABLE t1 alter column f2 set not null, alter column f1 set not null; --ok
+
+--using indexscan to check not-null can only apply to key columns, not include column
+ALTER TABLE t1 add constraint nnf4 not null f4;
+
+--cannot fast ALTER TABLE SET NOT NULL by utilizing hash index.
+ALTER TABLE t1 add constraint nn_f5 not null f5;
+
+drop table t1;
+drop table tpp1, tpp2, tp;
-- 
2.34.1

From 8072ef9578eafe6facf29996d08e129d60a8419e Mon Sep 17 00:00:00 2001
From: jian he <jian.universality@gmail.com>
Date: Mon, 28 Apr 2025 12:27:13 +0800
Subject: [PATCH v5 1/1] using indexscan to speedup add not null constraints

This patch tries to use index_beginscan() / index_getnext() / index_endscan()
mentioned in [1] to speedup adding not-null constraints to the existing table.

the main logic happen in phase3 ATRewriteTable
1. collect all not-null constraints.
2. does each not-null constraint have a corresponding index to vertify it, if
   not then do the normal processing.
3. if table scan, table rewrite, table was not in AccessExclusiveLock.
   not-null constraint was on virtual generated column
   then we can not use indexcan to fast check not-null constraint.
3. If a table scan or rewrite occurs and the table is not held with an
   AccessExclusiveLock, and the NOT NULL constraint is on a virtual generated
   column, then we can not use indexscan to fast validate not-null constraints.

concurrency concern:
ALTER TABLE SET NOT NULL will take an ACCESS EXCLUSIVE lock, so there is less
variant of racing issue can occur?  to prove accurate, I wrote some isolation
tests. see[2]

performance:
demo:
case when: %20 percent values are NULL and have been deleted from heap but they
still on the index.

drop table if exists t;
create unlogged table t(a int, b int) with (autovacuum_enabled = off, vacuum_index_cleanup=off);
insert into t select case when g % 5 = 0 then null else g end, g+1
from generate_series(1,1_000_000) g;
create index t_idx_a on t(a);
delete from t where a is null;

alter table t alter column a drop not null;
alter table t add constraint t1 not null a;

the above two statement running serval times:
patch Time:: 1.084  ms
master Time: 12.045 ms

references:
[1] https://postgr.es/m/CA%2BTgmoa5NKz8iGW_9v7wz%3D-%2BzQFu%3DE4SZoaTaU1znLaEXRYp-Q%40mail.gmail.com
[2] https://postgr.es/m/900056D1-32DF-4927-8251-3E0C0DC407FD%40anarazel.de
discussion: https://postgr.es/m/CACJufxFiW=4k1is=F1J=r-Cx1RuByXQPUrWB331U47rSnGz+hw@mail.gmail.com
commitfest entry: https://commitfest.postgresql.org/patch/5444
---
 src/backend/commands/tablecmds.c              | 113 +++++++++-
 src/backend/executor/execIndexing.c           | 195 ++++++++++++++++++
 src/include/executor/executor.h               |   2 +
 .../expected/indexscan-check-notnull.out      | 102 +++++++++
 src/test/isolation/isolation_schedule         |   1 +
 .../specs/indexscan-check-notnull.spec        |  45 ++++
 src/test/modules/test_misc/meson.build        |   1 +
 .../t/008_indexscan_validate_notnull.pl       | 138 +++++++++++++
 8 files changed, 591 insertions(+), 6 deletions(-)
 create mode 100644 src/test/isolation/expected/indexscan-check-notnull.out
 create mode 100644 src/test/isolation/specs/indexscan-check-notnull.spec
 create mode 100644 src/test/modules/test_misc/t/008_indexscan_validate_notnull.pl

diff --git a/src/backend/commands/tablecmds.c b/src/backend/commands/tablecmds.c
index 2705cf11330..a784dbfbeac 100644
--- a/src/backend/commands/tablecmds.c
+++ b/src/backend/commands/tablecmds.c
@@ -209,16 +209,19 @@ typedef struct AlteredTableInfo
 	List	   *changedStatisticsDefs;	/* string definitions of same */
 } AlteredTableInfo;
 
-/* Struct describing one new constraint to check in Phase 3 scan */
-/* Note: new not-null constraints are handled elsewhere */
+/*
+ * Struct describing one new constraint to check in Phase 3 scan. Note: new
+ * not-null constraints are handled here too.
+*/
 typedef struct NewConstraint
 {
 	char	   *name;			/* Constraint name, or NULL if none */
-	ConstrType	contype;		/* CHECK or FOREIGN */
+	ConstrType	contype;		/* CHECK or FOREIGN or NOT-NULL */
 	Oid			refrelid;		/* PK rel, if FOREIGN */
 	Oid			refindid;		/* OID of PK's index, if FOREIGN */
 	bool		conwithperiod;	/* Whether the new FOREIGN KEY uses PERIOD */
 	Oid			conid;			/* OID of pg_constraint entry, if FOREIGN */
+	int			attnum;			/* NOT-NULL constraint attribute number */
 	Node	   *qual;			/* Check expr or CONSTR_FOREIGN Constraint */
 	ExprState  *qualstate;		/* Execution state for CHECK expr */
 } NewConstraint;
@@ -6182,6 +6185,9 @@ ATRewriteTable(AlteredTableInfo *tab, Oid OIDNewHeap)
 				needscan = true;
 				con->qualstate = ExecPrepareExpr((Expr *) expand_generated_columns_in_expr(con->qual, oldrel, 1), estate);
 				break;
+			case CONSTR_NOTNULL:
+				/* Nothing to do here */
+				break;
 			case CONSTR_FOREIGN:
 				/* Nothing to do here */
 				break;
@@ -6235,10 +6241,70 @@ ATRewriteTable(AlteredTableInfo *tab, Oid OIDNewHeap)
 														wholeatt->attnum);
 			}
 		}
-		if (notnull_attrs || notnull_virtual_attrs)
-			needscan = true;
 	}
 
+	/*
+	 * The conditions for using indexscan mechanism fast validate not-null
+	 * constraints are quite strict. All of the following conditions must be
+	 * met.
+	 * 1. We must have the needs to validate not-null constraints
+	 *    (AlteredTableInfo->verify_new_notnull is true).
+	 * 2. If a table scan or table rewrite is expected later, using indexscan is
+	 *    just wastes cycles.
+	 * 3. indexes cannot be created on virtual generated columns, so fast
+	 *    checking not-null constraints is not applicable to them.
+	 * 4. optimization is also limited to regular relations.
+	 * 5. To avoid concurrency issue, we only do it when table was locked in
+	 *    AccessExclusiveLock.
+	*/
+	if (!needscan &&
+		newrel == NULL &&
+		!tab->rewrite &&
+		tab->verify_new_notnull &&
+		notnull_virtual_attrs == NIL &&
+		oldrel->rd_rel->relkind == RELKIND_RELATION &&
+		CheckRelationLockedByMe(oldrel, AccessExclusiveLock, false))
+	{
+		List	   *notnull_attnums = NIL;
+
+		foreach(l, tab->constraints)
+		{
+			NewConstraint *con = lfirst(l);
+
+			Form_pg_attribute attr = TupleDescAttr(newTupDesc, con->attnum - 1);
+
+			if (con->contype != CONSTR_NOTNULL)
+				continue;
+
+			Assert(attr->attnotnull);
+			Assert(con->attnum > 0);
+			Assert(attr->attnum == con->attnum);
+
+			if (attr->attgenerated == ATTRIBUTE_GENERATED_VIRTUAL)
+			{
+				needscan = true;
+				break;
+			}
+
+			notnull_attnums = lappend_int(notnull_attnums, attr->attnum);
+		}
+
+		/* notnull_attnums is all not-null attributes we validate later */
+		if (notnull_attnums != NIL)
+		{
+			Assert(CheckRelationLockedByMe(oldrel, AccessExclusiveLock, false));
+
+			if (!index_check_notnull(oldrel, notnull_attnums))
+				needscan = true;
+			else
+				ereport(DEBUG1,
+						errmsg_internal("all not-null constraints on relation \"%s\" are validated by index scan",
+										RelationGetRelationName(oldrel)));
+		}
+	}
+	else if (notnull_attrs || notnull_virtual_attrs)
+		needscan = true;
+
 	if (newrel || needscan)
 	{
 		ExprContext *econtext;
@@ -7910,6 +7976,7 @@ ATExecSetNotNull(List **wqueue, Relation rel, char *conName, char *colName,
 	CookedConstraint *ccon;
 	List	   *cooked;
 	bool		is_no_inherit = false;
+	AlteredTableInfo *tab = NULL;
 
 	/* Guard against stack overflow due to overly deep inheritance tree. */
 	check_stack_depth();
@@ -8034,10 +8101,31 @@ ATExecSetNotNull(List **wqueue, Relation rel, char *conName, char *colName,
 	constraint->is_no_inherit = is_no_inherit;
 	constraint->conname = conName;
 
+	tab = ATGetQueueEntry(wqueue, rel);
+
 	/* and do it */
 	cooked = AddRelationNewConstraints(rel, NIL, list_make1(constraint),
 									   false, !recursing, false, NULL);
 	ccon = linitial(cooked);
+
+	Assert(ccon->contype == CONSTR_NOTNULL);
+
+	/*
+	 * we may use indexscan to fast validate not-null constraint in Phase3.  Add
+	 * the to-be-validated not-null constraint to Phase 3's queue.
+	*/
+	if (!ccon->skip_validation)
+	{
+		NewConstraint *newcon;
+		newcon = (NewConstraint *) palloc0(sizeof(NewConstraint));
+
+		newcon->name = ccon->name;
+		newcon->contype = ccon->contype;
+		newcon->attnum = ccon->attnum;
+
+		tab->constraints = lappend(tab->constraints, newcon);
+	}
+
 	ObjectAddressSet(address, ConstraintRelationId, ccon->conoid);
 
 	InvokeObjectPostAlterHook(RelationRelationId,
@@ -9918,13 +10006,15 @@ ATAddCheckNNConstraint(List **wqueue, AlteredTableInfo *tab, Relation rel,
 	{
 		CookedConstraint *ccon = (CookedConstraint *) lfirst(lcon);
 
-		if (!ccon->skip_validation && ccon->contype != CONSTR_NOTNULL)
+		if (!ccon->skip_validation)
 		{
 			NewConstraint *newcon;
 
 			newcon = (NewConstraint *) palloc0(sizeof(NewConstraint));
 			newcon->name = ccon->name;
 			newcon->contype = ccon->contype;
+			if (ccon->contype == CONSTR_NOTNULL)
+				newcon->attnum = ccon->attnum;
 			newcon->qual = ccon->expr;
 
 			tab->constraints = lappend(tab->constraints, newcon);
@@ -13179,6 +13269,7 @@ QueueNNConstraintValidation(List **wqueue, Relation conrel, Relation rel,
 	List	   *children = NIL;
 	AttrNumber	attnum;
 	char	   *colname;
+	NewConstraint *newcon;
 
 	con = (Form_pg_constraint) GETSTRUCT(contuple);
 	Assert(con->contype == CONSTRAINT_NOTNULL);
@@ -13242,7 +13333,17 @@ QueueNNConstraintValidation(List **wqueue, Relation conrel, Relation rel,
 	/* Set attnotnull appropriately without queueing another validation */
 	set_attnotnull(NULL, rel, attnum, true, false);
 
+	/* Queue validation for phase 3 */
+	newcon = (NewConstraint *) palloc0(sizeof(NewConstraint));
+	newcon->name = colname;
+	newcon->contype = CONSTR_NOTNULL;
+	newcon->attnum = attnum;
+
+	/* Find or create work queue entry for this table */
 	tab = ATGetQueueEntry(wqueue, rel);
+
+	tab->constraints = lappend(tab->constraints, newcon);
+
 	tab->verify_new_notnull = true;
 
 	/*
diff --git a/src/backend/executor/execIndexing.c b/src/backend/executor/execIndexing.c
index bdf862b2406..648c696725b 100644
--- a/src/backend/executor/execIndexing.c
+++ b/src/backend/executor/execIndexing.c
@@ -108,12 +108,15 @@
 
 #include "access/genam.h"
 #include "access/relscan.h"
+#include "access/table.h"
 #include "access/tableam.h"
 #include "access/xact.h"
 #include "catalog/index.h"
+#include "catalog/pg_am_d.h"
 #include "executor/executor.h"
 #include "nodes/nodeFuncs.h"
 #include "storage/lmgr.h"
+#include "utils/fmgroids.h"
 #include "utils/multirangetypes.h"
 #include "utils/rangetypes.h"
 #include "utils/snapmgr.h"
@@ -145,6 +148,7 @@ static bool index_expression_changed_walker(Node *node,
 											Bitmapset *allUpdatedCols);
 static void ExecWithoutOverlapsNotEmpty(Relation rel, NameData attname, Datum attval,
 										char typtype, Oid atttypid);
+static bool index_check_notnull_internal(Relation relation, List *attnums, List *idxs);
 
 /* ----------------------------------------------------------------
  *		ExecOpenIndices
@@ -1172,3 +1176,194 @@ ExecWithoutOverlapsNotEmpty(Relation rel, NameData attname, Datum attval, char t
 				 errmsg("empty WITHOUT OVERLAPS value found in column \"%s\" in relation \"%s\"",
 						NameStr(attname), RelationGetRelationName(rel))));
 }
+
+/*
+ * notnull_attnums: Attribute numbers for all newly added NOT NULL constraints.
+ *
+ * First check if relation have suitable index for each not null attribute. If
+ * it does, then using indexscan mechanism to verify that *all* attributes on
+ * notnull_attnums are indeed NOT NULL.
+ */
+bool
+index_check_notnull(Relation relation, List *notnull_attnums)
+{
+	Relation	pg_index;
+	Relation	index_rel;
+	SysScanDesc indscan;
+	ScanKeyData skey;
+	HeapTuple	htup;
+	TupleDesc	tupdesc;
+	Form_pg_attribute attr;
+	List	   *result = NIL;
+	List	   *attnums = NIL;
+
+	tupdesc = RelationGetDescr(relation);
+
+	/* Prepare to scan pg_index for entries having indrelid = this rel. */
+	ScanKeyInit(&skey,
+				Anum_pg_index_indrelid,
+				BTEqualStrategyNumber, F_OIDEQ,
+				ObjectIdGetDatum(RelationGetRelid(relation)));
+
+	pg_index = table_open(IndexRelationId, AccessShareLock);
+	indscan = systable_beginscan(pg_index, IndexIndrelidIndexId, true,
+								 NULL, 1, &skey);
+
+	while (HeapTupleIsValid(htup = systable_getnext(indscan)))
+	{
+		Form_pg_index index = (Form_pg_index) GETSTRUCT(htup);
+
+		/*
+		 * we can only use non-deferred, valid, and alive btree index to
+		 * validate not-null constraints
+		 */
+		if (!index->indimmediate || !index->indisvalid || !index->indislive)
+			continue;
+
+		/* can not use expression index or partial index too */
+		if (!heap_attisnull(htup, Anum_pg_index_indexprs, NULL) ||
+			!heap_attisnull(htup, Anum_pg_index_indpred, NULL))
+			continue;
+
+		for (int i = 0; i < index->indnkeyatts; i++)
+		{
+			attr = TupleDescAttr(tupdesc, (index->indkey.values[i] - 1));
+
+			if (list_member_int(notnull_attnums, attr->attnum))
+			{
+				index_rel = index_open(index->indexrelid, AccessShareLock);
+
+				if (index_rel->rd_rel->relam == BTREE_AM_OID &&
+					!list_member_int(attnums, attr->attnum))
+				{
+					attnums = lappend_int(attnums, attr->attnum);
+					result = lappend_oid(result, index->indexrelid);
+				}
+				index_close(index_rel, AccessShareLock);
+			}
+		}
+	}
+	systable_endscan(indscan);
+	table_close(pg_index, AccessShareLock);
+
+	if (attnums == NIL)
+		return false;
+
+	/*
+	 * every not-null constraints require an index for fast validatation.
+	*/
+	foreach_int(attno, notnull_attnums)
+	{
+		if(!list_member_int(attnums, attno))
+			return false;
+	}
+
+	return index_check_notnull_internal(relation, attnums, result);
+}
+
+/*
+ * Use indexscan mechanism to fast check each attribute in "attnums" are
+ * not-null or not.
+ */
+static bool
+index_check_notnull_internal(Relation relation, List *attnums, List *idxs)
+{
+	EState	   *estate;
+	ExprContext *econtext;
+	TupleTableSlot *existing_slot;
+	bool 		all_not_null = true;
+	ListCell   *lc,
+				*lc2;
+
+	/*
+	 * Need an EState for slot to hold the current tuple.
+	*/
+	estate = CreateExecutorState();
+	econtext = GetPerTupleExprContext(estate);
+
+	forboth(lc, attnums, lc2, idxs)
+	{
+		SnapshotData DirtySnapshot;
+		IndexScanDesc index_scan;
+		ScanKeyData		scankeys[INDEX_MAX_KEYS];
+		IndexInfo  	*indexInfo;
+		AttrNumber	sk_attno = -1;
+		Relation 	index;
+		int			indnkeyatts;
+
+		AttrNumber	attno = lfirst_int(lc);
+		Oid		indexoid = lfirst_oid(lc2);
+
+		existing_slot = table_slot_create(relation, NULL);
+
+		/* Arrange for econtext's scan tuple to be the tuple under test */
+		econtext->ecxt_scantuple = existing_slot;
+
+		index = index_open(indexoid, AccessShareLock);
+
+		indexInfo = BuildIndexInfo(index);
+		indnkeyatts = IndexRelationGetNumberOfKeyAttributes(index);
+
+		/*
+		 * Search the tuples that are in the index for any violations, including
+		 * tuples that aren't visible yet.
+		*/
+		InitDirtySnapshot(DirtySnapshot);
+
+		for (int i = 0; i < indnkeyatts; i++)
+		{
+			if (indexInfo->ii_IndexAttrNumbers[i] == attno)
+			{
+				sk_attno = i+1;
+				break;
+			}
+		}
+
+		if (sk_attno == -1)
+			elog(ERROR, "index %u should effect on column number %d", indexoid, attno);
+
+		for (int i = 0; i < indnkeyatts; i++)
+		{
+			/* set up an IS NULL scan key so that we ignore not nulls */
+			ScanKeyEntryInitialize(&scankeys[i],
+									SK_ISNULL | SK_SEARCHNULL,
+									sk_attno,		/* index col to scan */
+									InvalidStrategy,/* no strategy */
+									InvalidOid,		/* no strategy subtype */
+									InvalidOid,		/* no collation */
+									InvalidOid,		/* no reg proc for this */
+									(Datum) 0);		/* constant */
+		}
+
+		index_scan = index_beginscan(relation, index, &DirtySnapshot, NULL, indnkeyatts, 0);
+		index_rescan(index_scan, scankeys, indnkeyatts, NULL, 0);
+
+		while (index_getnext_slot(index_scan, ForwardScanDirection, existing_slot))
+		{
+			Datum		values[INDEX_MAX_KEYS];
+			bool		nulls[INDEX_MAX_KEYS];
+
+			/*
+			 * Extract the index column values and isnull flags from the
+			 * existing tuple.
+			*/
+			FormIndexDatum(indexInfo, existing_slot, estate, values, nulls);
+
+			if (nulls[sk_attno - 1])
+			{
+				all_not_null = false;
+				break;
+			}
+		}
+
+		index_endscan(index_scan);
+		index_close(index, AccessShareLock);
+		ExecDropSingleTupleTableSlot(existing_slot);
+		if (!all_not_null)
+			return false;
+	}
+
+	FreeExecutorState(estate);
+
+	return true;
+}
diff --git a/src/include/executor/executor.h b/src/include/executor/executor.h
index ae99407db89..f42407ed75e 100644
--- a/src/include/executor/executor.h
+++ b/src/include/executor/executor.h
@@ -778,6 +778,8 @@ extern void check_exclusion_constraint(Relation heap, Relation index,
 									   const Datum *values, const bool *isnull,
 									   EState *estate, bool newIndex);
 
+extern bool index_check_notnull(Relation relation, List *notnull_attnums);
+
 /*
  * prototypes from functions in execReplication.c
  */
diff --git a/src/test/isolation/expected/indexscan-check-notnull.out b/src/test/isolation/expected/indexscan-check-notnull.out
new file mode 100644
index 00000000000..ac3b9f14c89
--- /dev/null
+++ b/src/test/isolation/expected/indexscan-check-notnull.out
@@ -0,0 +1,102 @@
+Parsed test spec with 2 sessions
+
+starting permutation: b1 b3 m1 hj c1 c3 sn
+step b1: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step b3: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step m1: DELETE FROM t;
+step hj: ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a; <waiting ...>
+step c1: COMMIT;
+s2: NOTICE:  all not-null constraints on relation "t" are validated by index scan
+step hj: <... completed>
+step c3: COMMIT;
+step sn: SELECT conname, conrelid::regclass, contype, convalidated
+           FROM pg_constraint WHERE conname = 't1_nn';
+
+conname|conrelid|contype|convalidated
+-------+--------+-------+------------
+t1_nn  |t       |n      |t           
+(1 row)
+
+
+starting permutation: b2 b3 m1 hj c1 c3 sn
+step b2: BEGIN;
+step b3: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step m1: DELETE FROM t;
+step hj: ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a; <waiting ...>
+step c1: COMMIT;
+s2: NOTICE:  all not-null constraints on relation "t" are validated by index scan
+step hj: <... completed>
+step c3: COMMIT;
+step sn: SELECT conname, conrelid::regclass, contype, convalidated
+           FROM pg_constraint WHERE conname = 't1_nn';
+
+conname|conrelid|contype|convalidated
+-------+--------+-------+------------
+t1_nn  |t       |n      |t           
+(1 row)
+
+
+starting permutation: b1 b4 m1 hj c1 c3 sn
+step b1: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step b4: BEGIN;
+step m1: DELETE FROM t;
+step hj: ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a; <waiting ...>
+step c1: COMMIT;
+s2: NOTICE:  all not-null constraints on relation "t" are validated by index scan
+step hj: <... completed>
+step c3: COMMIT;
+step sn: SELECT conname, conrelid::regclass, contype, convalidated
+           FROM pg_constraint WHERE conname = 't1_nn';
+
+conname|conrelid|contype|convalidated
+-------+--------+-------+------------
+t1_nn  |t       |n      |t           
+(1 row)
+
+
+starting permutation: b1 b3 hj r1 c2
+step b1: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step b3: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step hj: ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a;
+ERROR:  column "a" of relation "t" contains null values
+step r1: ROLLBACK;
+step c2: ROLLBACK;
+
+starting permutation: b1 b4 d1 m1 c2 s1 sn r1
+step b1: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step b4: BEGIN;
+step d1: DROP INDEX t_ab_idx;
+step m1: DELETE FROM t; <waiting ...>
+step c2: ROLLBACK;
+step m1: <... completed>
+s1: NOTICE:  all not-null constraints on relation "t" are validated by index scan
+step s1: ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a;
+step sn: SELECT conname, conrelid::regclass, contype, convalidated
+           FROM pg_constraint WHERE conname = 't1_nn';
+
+conname|conrelid|contype|convalidated
+-------+--------+-------+------------
+t1_nn  |t       |n      |t           
+(1 row)
+
+step r1: ROLLBACK;
+
+starting permutation: b2 b3 m1 d1 s0 s1 c1 c3 sn
+step b2: BEGIN;
+step b3: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step m1: DELETE FROM t;
+step d1: DROP INDEX t_ab_idx; <waiting ...>
+step s0: savepoint s0;
+s1: NOTICE:  all not-null constraints on relation "t" are validated by index scan
+step s1: ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a;
+step c1: COMMIT;
+step d1: <... completed>
+step c3: COMMIT;
+step sn: SELECT conname, conrelid::regclass, contype, convalidated
+           FROM pg_constraint WHERE conname = 't1_nn';
+
+conname|conrelid|contype|convalidated
+-------+--------+-------+------------
+t1_nn  |t       |n      |t           
+(1 row)
+
diff --git a/src/test/isolation/isolation_schedule b/src/test/isolation/isolation_schedule
index e3c669a29c7..1b9e8f932ac 100644
--- a/src/test/isolation/isolation_schedule
+++ b/src/test/isolation/isolation_schedule
@@ -56,6 +56,7 @@ test: merge-delete
 test: merge-update
 test: merge-match-recheck
 test: merge-join
+test: indexscan-check-notnull
 test: delete-abort-savept
 test: delete-abort-savept-2
 test: aborted-keyrevoke
diff --git a/src/test/isolation/specs/indexscan-check-notnull.spec b/src/test/isolation/specs/indexscan-check-notnull.spec
new file mode 100644
index 00000000000..d0ca928f3af
--- /dev/null
+++ b/src/test/isolation/specs/indexscan-check-notnull.spec
@@ -0,0 +1,45 @@
+
+#
+# using indexscan to check a column not-null constraint
+# is satisfied or not.
+#
+
+setup
+{
+  CREATE TABLE t (a int, b int);
+  CREATE INDEX t_ab_idx on t(a,b);
+  INSERT INTO t values (null, 1);
+  INSERT INTO t SELECT x, x*10 FROM generate_series(1,3) g(x);
+}
+
+teardown
+{
+  DROP TABLE t;
+}
+
+session s1
+step b1  { BEGIN ISOLATION LEVEL REPEATABLE READ; }
+step b2  { BEGIN; }
+step m1  { DELETE FROM t;}
+step s0  { savepoint s0;}
+step s1  { ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a;}
+step sn  { SELECT conname, conrelid::regclass, contype, convalidated
+           FROM pg_constraint WHERE conname = 't1_nn';
+         }
+step r1  { ROLLBACK; }
+step c1  { COMMIT; }
+
+session s2
+step b3  { BEGIN ISOLATION LEVEL REPEATABLE READ; }
+step b4  { BEGIN; }
+step hj  { ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a;}
+step d1  { DROP INDEX t_ab_idx;}
+step c2  { ROLLBACK; }
+step c3  { COMMIT; }
+
+permutation b1 b3 m1 hj c1 c3 sn
+permutation b2 b3 m1 hj c1 c3 sn
+permutation b1 b4 m1 hj c1 c3 sn
+permutation b1 b3 hj r1 c2
+permutation b1 b4 d1 m1 c2 s1 sn r1
+permutation b2 b3 m1 d1 s0 s1 c1 c3 sn
diff --git a/src/test/modules/test_misc/meson.build b/src/test/modules/test_misc/meson.build
index 9c50de7efb0..49fa16fb50e 100644
--- a/src/test/modules/test_misc/meson.build
+++ b/src/test/modules/test_misc/meson.build
@@ -16,6 +16,7 @@ tests += {
       't/005_timeouts.pl',
       't/006_signal_autovacuum.pl',
       't/007_catcache_inval.pl',
+      't/008_indexscan_validate_notnull.pl',
     ],
   },
 }
diff --git a/src/test/modules/test_misc/t/008_indexscan_validate_notnull.pl b/src/test/modules/test_misc/t/008_indexscan_validate_notnull.pl
new file mode 100644
index 00000000000..37787858ea0
--- /dev/null
+++ b/src/test/modules/test_misc/t/008_indexscan_validate_notnull.pl
@@ -0,0 +1,138 @@
+
+# Copyright (c) 2025, PostgreSQL Global Development Group
+
+# Verify that indexscan mechanism can speedup ALTER TABLE ADD NOT NULL
+
+
+use strict;
+use warnings FATAL => 'all';
+use PostgreSQL::Test::Cluster;
+use PostgreSQL::Test::Utils;
+use Test::More;
+
+# Initialize a test cluster
+my $node = PostgreSQL::Test::Cluster->new('primary');
+$node->init();
+# Turn message level up to DEBUG1 so that we get the messages we want to see
+$node->append_conf('postgresql.conf', 'client_min_messages = DEBUG1');
+$node->start;
+
+# Run a SQL command and return psql's stderr (including debug messages)
+sub run_sql_command
+{
+	my $sql = shift;
+	my $stderr;
+
+	$node->psql(
+		'postgres',
+		$sql,
+		stderr => \$stderr,
+		on_error_die => 1,
+		on_error_stop => 1);
+	return $stderr;
+}
+
+# Check whether result of run_sql_command shows that we did a verify pass
+sub is_table_verified
+{
+	my $output = shift;
+	return index($output, 'DEBUG:  verifying table') != -1;
+}
+
+# Check whether result of run_sql_command shows that we did a verify pass
+sub is_indexscan_veritify_notnull
+{
+	my $output = shift;
+	return index($output, 'DEBUG:  all not-null constraints on relation') != -1;
+}
+
+my $output;
+
+note "test alter table set not null using indexscan with partitioned table";
+
+run_sql_command(
+    'CREATE TABLE tp (a int, b int ) PARTITION BY range(a);
+     CREATE TABLE tpp1 partition of tp for values from ( 1 ) to (10);
+     CREATE TABLE tpp2 partition of tp for values from ( 10 ) to (21);
+     INSERT INTO tp select g, g + 10 from generate_series(1,19) g;
+     CREATE INDEX ON tp(b); ');
+
+$output = run_sql_command('ALTER TABLE tp alter column b set not null;');
+ok(is_indexscan_veritify_notnull($output),
+	'column b will use indexscan to vertify not-null status, no need scan table');
+ok( $output =~
+	  m/all not-null constraints on relation "tpp1" are validated by index scan/,
+	'all newly added constraints proved by indexscan');
+
+run_sql_command(
+	'ALTER TABLE tp alter column b drop not null;');
+
+# normal run will verify table data
+$output = run_sql_command('ALTER TABLE tpp1 alter column b set not null;');
+ok(is_indexscan_veritify_notnull($output), 'use indexscan to validate column b not-null will not scan table');
+ok(!is_table_verified($output), 'will not scan table');
+ok( $output =~
+	  m/all not-null constraints on relation "tpp1" are validated by index scan/,
+	'all newly added constraints proved by indexscan');
+
+
+$output = run_sql_command('ALTER TABLE tpp2 alter column b set not null;');
+ok(is_indexscan_veritify_notnull($output), 'use indexscan to validate column b not-null, will not scan table');
+ok(!is_table_verified($output), 'will not scan table');
+ok( $output =~
+	  m/all not-null constraints on relation "tpp2" are validated by index scan/,
+	'all newly added constraints proved by indexscan');
+
+run_sql_command(
+	'ALTER TABLE tp alter column b drop not null;');
+
+# we have check only for test_a column, so we need verify table for test_b
+$output = run_sql_command(
+	'ALTER TABLE tp alter column b set not null, alter column b SET data type bigint;'
+);
+ok(!is_table_verified($output), 'table was rewrite');
+ok(!is_indexscan_veritify_notnull($output), 'table was rewrite, can not use indexscan to vertify not null constraints');
+
+
+# test with non-partitioned table and other type index.
+note "test alter table set not null using indexscan with non-partitioned table";
+
+run_sql_command(
+    'CREATE TABLE t1(f1 INT, f2 int, f3 int,f4 int, f5 int);
+     INSERT INTO t1 select g, g+1, g+2, g+3, g+4 from generate_series(1, 100) g;
+     CREATE INDEX t1_f1_f2_idx ON t1(f1,f2);
+     CREATE UNIQUE INDEX t1_f3idx ON t1(f3);
+     CREATE INDEX t1_f3f4idx ON t1(f3) include(f4);
+     CREATE INDEX hash_f5_idx ON t1 USING hash (f5 int4_ops); ');
+
+$output = run_sql_command(
+	'ALTER TABLE t1 alter column f1 set not null, alter f1 type bigint;'
+);
+ok(!is_indexscan_veritify_notnull($output), 'table was rewrite, can not use indexscan to validate not null constraints');
+
+run_sql_command('ALTER TABLE t1 alter column f1 drop not null;');
+run_sql_command('ALTER TABLE t1 add constraint nn not null f1, alter f1 type bigint;');
+
+# can use indexscan mechanism to fast add multiple not-null constraints
+$output = run_sql_command(
+	'ALTER TABLE t1 alter column f2 set not null, alter column f1 set not null;'
+);
+ok( $output =~
+	  m/all not-null constraints on relation "t1" are validated by index scan/,
+	'all not-null constraints are validated by indexscan');
+
+# using indexscan mechanism to fast add a not-null can only apply to key columns, not include column
+$output = run_sql_command(
+	'ALTER TABLE t1 add constraint nnf4 not null f4;'
+);
+ok(!is_indexscan_veritify_notnull($output), 'can not use indexscan to valildate not-null constraint');
+
+# if index is not btree index then cannot use indexscan mechanism to fast add not-null constraint
+$output = run_sql_command(
+	'ALTER TABLE t1 add constraint nn_f5 not null f5;'
+);
+ok(!is_indexscan_veritify_notnull($output), 'can not use indexscan to validate not-null constraint');
+
+$node->stop('fast');
+
+done_testing();
-- 
2.34.1

From 8c9a668993386c67a3e6ab14e02c87a3184be83b Mon Sep 17 00:00:00 2001
From: jian he <jian.universality@gmail.com>
Date: Wed, 14 May 2025 17:14:36 +0800
Subject: [PATCH v6 1/1] using indexscan to speedup add not null constraints

This patch tries to use index_beginscan() / index_getnext() / index_endscan()
mentioned in [1] to speedup adding not-null constraints to the existing table.

The main logic happens in phase3 ATRewriteTable
1. collect all not-null constraints.
2. For each not-null constraint, check whether there is a corresponding index
available for validation. If not, then can not use indexscan to verify not-null
constraints.
3. If any of the following conditions are true
  * table scan or rewrite is required,
  * table wasn't locked with `AccessExclusiveLock`
  * the NOT NULL constraint applies to a virtual generated column
 then index scan cannot be used for fast validation.
4. If all conditions are satisfied, attempt to use indexscan to verify
whether the column contains any NULL values.

concurrency concern:
ALTER TABLE SET NOT NULL will take an ACCESS EXCLUSIVE lock, so there is less
variant of racing issue can occur?  to prove accurate, I wrote some isolation
tests. see[2]

performance:
demo:
case when: %20 percent values are NULL and have been deleted from heap but they
still on the index.

drop table if exists t;
create unlogged table t(a int, b int) with (autovacuum_enabled = off, vacuum_index_cleanup=off);
insert into t select case when g % 5 = 0 then null else g end, g+1
from generate_series(1,1_000_000) g;
create index t_idx_a on t(a);
delete from t where a is null;

alter table t alter column a drop not null;
alter table t add constraint t1 not null a;

the above two statement running several times:
patch Time:: 1.084  ms
master Time: 12.045 ms

references:
[1] https://postgr.es/m/CA%2BTgmoa5NKz8iGW_9v7wz%3D-%2BzQFu%3DE4SZoaTaU1znLaEXRYp-Q%40mail.gmail.com
[2] https://postgr.es/m/900056D1-32DF-4927-8251-3E0C0DC407FD%40anarazel.de
discussion: https://postgr.es/m/CACJufxFiW=4k1is=F1J=r-Cx1RuByXQPUrWB331U47rSnGz+hw@mail.gmail.com
commitfest entry: https://commitfest.postgresql.org/patch/5444
---
 src/backend/commands/tablecmds.c              | 125 ++++++++++-
 src/backend/executor/execIndexing.c           | 200 ++++++++++++++++++
 src/include/executor/executor.h               |   2 +
 .../expected/indexscan-check-notnull.out      |  97 +++++++++
 src/test/isolation/isolation_schedule         |   1 +
 .../specs/indexscan-check-notnull.spec        |  45 ++++
 src/test/modules/test_misc/meson.build        |   1 +
 .../t/008_indexscan_validate_notnull.pl       | 164 ++++++++++++++
 8 files changed, 630 insertions(+), 5 deletions(-)
 create mode 100644 src/test/isolation/expected/indexscan-check-notnull.out
 create mode 100644 src/test/isolation/specs/indexscan-check-notnull.spec
 create mode 100644 src/test/modules/test_misc/t/008_indexscan_validate_notnull.pl

diff --git a/src/backend/commands/tablecmds.c b/src/backend/commands/tablecmds.c
index 54ad38247aa..c276450aceb 100644
--- a/src/backend/commands/tablecmds.c
+++ b/src/backend/commands/tablecmds.c
@@ -209,16 +209,19 @@ typedef struct AlteredTableInfo
 	List	   *changedStatisticsDefs;	/* string definitions of same */
 } AlteredTableInfo;
 
-/* Struct describing one new constraint to check in Phase 3 scan */
-/* Note: new not-null constraints are handled elsewhere */
+/*
+ * Struct describing one new constraint to check in Phase 3 scan. Note: new
+ * not-null constraints are handled here too.
+*/
 typedef struct NewConstraint
 {
 	char	   *name;			/* Constraint name, or NULL if none */
-	ConstrType	contype;		/* CHECK or FOREIGN */
+	ConstrType	contype;		/* CHECK or FOREIGN or NOT NULL */
 	Oid			refrelid;		/* PK rel, if FOREIGN */
 	Oid			refindid;		/* OID of PK's index, if FOREIGN */
 	bool		conwithperiod;	/* Whether the new FOREIGN KEY uses PERIOD */
 	Oid			conid;			/* OID of pg_constraint entry, if FOREIGN */
+	int			attnum;			/* NOT NULL constraint attribute number */
 	Node	   *qual;			/* Check expr or CONSTR_FOREIGN Constraint */
 	ExprState  *qualstate;		/* Execution state for CHECK expr */
 } NewConstraint;
@@ -6182,6 +6185,9 @@ ATRewriteTable(AlteredTableInfo *tab, Oid OIDNewHeap)
 				needscan = true;
 				con->qualstate = ExecPrepareExpr((Expr *) expand_generated_columns_in_expr(con->qual, oldrel, 1), estate);
 				break;
+			case CONSTR_NOTNULL:
+				/* Nothing to do here */
+				break;
 			case CONSTR_FOREIGN:
 				/* Nothing to do here */
 				break;
@@ -6235,9 +6241,81 @@ ATRewriteTable(AlteredTableInfo *tab, Oid OIDNewHeap)
 														wholeatt->attnum);
 			}
 		}
-		if (notnull_attrs || notnull_virtual_attrs)
+	}
+
+	/*
+	 * The conditions for using indexscan mechanism fast vertifing not-null
+	 * constraints are quite strict. All of the following conditions must be
+	 * met.
+	 * 1. We must have the need to validate not-null constraints
+	 *    That means AlteredTableInfo->verify_new_notnull must be true.
+	 * 2. If table scan or table rewrite is expected later, using indexscan is
+	 *    just wastes cycles.
+	 * 3. Indexes cannot be created on virtual generated columns, so fast
+	 *    checking not-null constraints is not applicable to them.
+	 * 4. Only apply to regular relations.
+	 * 5. To avoid concurrency issue, we only do it when table was locked with
+	 *    an AccessExclusiveLock, which is the lock acquired during ALTER TABLE
+	 *    SET NOT NULL.
+	*/
+	if (!needscan &&
+		newrel == NULL &&
+		!tab->rewrite &&
+		tab->verify_new_notnull &&
+		notnull_virtual_attrs == NIL &&
+		oldrel->rd_rel->relkind == RELKIND_RELATION &&
+		CheckRelationLockedByMe(oldrel, AccessExclusiveLock, false))
+	{
+		List	   *notnull_attnums = NIL;
+
+		foreach(l, tab->constraints)
+		{
+			NewConstraint *con = lfirst(l);
+
+			Form_pg_attribute attr = TupleDescAttr(newTupDesc, con->attnum - 1);
+
+			if (con->contype != CONSTR_NOTNULL)
+				continue;
+
+			Assert(attr->attnotnull);
+			Assert(con->attnum > 0);
+			Assert(attr->attnum == con->attnum);
+
+			if (attr->attgenerated == ATTRIBUTE_GENERATED_VIRTUAL)
+			{
+				needscan = true;
+				break;
+			}
+
+			notnull_attnums = lappend_int(notnull_attnums, attr->attnum);
+		}
+
+		/*
+		 * notnull_attnums contains all attributes with NOT NULL constraints
+		 * that need validation.  If needscan is true, later table scan
+		 * will do the validation, indedxscan would just waste cycle.
+		*/
+		if (notnull_attnums != NIL && !needscan)
+		{
+			if (!index_check_notnull(oldrel, notnull_attnums))
+				needscan = true;
+			else
+				ereport(DEBUG1,
+						errmsg_internal("all new not-null constraints on relation \"%s\" have been validated by using index scan",
+										RelationGetRelationName(oldrel)));
+		}
+		else
+		{
+			/*
+			 * corner case: in Phase2, somehow we didn't add the NOT NULL
+			 * constraint to AlteredTableInfo->constraints, but already set
+			 * verify_new_notnull to true then table scan is needed.
+			*/
 			needscan = true;
+		}
 	}
+	else if (notnull_attrs || notnull_virtual_attrs)
+		needscan = true;
 
 	if (newrel || needscan)
 	{
@@ -7910,6 +7988,7 @@ ATExecSetNotNull(List **wqueue, Relation rel, char *conName, char *colName,
 	CookedConstraint *ccon;
 	List	   *cooked;
 	bool		is_no_inherit = false;
+	AlteredTableInfo *tab = NULL;
 
 	/* Guard against stack overflow due to overly deep inheritance tree. */
 	check_stack_depth();
@@ -8034,10 +8113,31 @@ ATExecSetNotNull(List **wqueue, Relation rel, char *conName, char *colName,
 	constraint->is_no_inherit = is_no_inherit;
 	constraint->conname = conName;
 
+	tab = ATGetQueueEntry(wqueue, rel);
+
 	/* and do it */
 	cooked = AddRelationNewConstraints(rel, NIL, list_make1(constraint),
 									   false, !recursing, false, NULL);
 	ccon = linitial(cooked);
+
+	Assert(ccon->contype == CONSTR_NOTNULL);
+
+	/*
+	 * we may use indexscan to validate not-null constraint in Phase3.  Add the
+	 * to-be-validated not-null constraint to Phase 3's queue.
+	*/
+	if (!ccon->skip_validation)
+	{
+		NewConstraint *newcon;
+		newcon = (NewConstraint *) palloc0(sizeof(NewConstraint));
+
+		newcon->name = ccon->name;
+		newcon->contype = ccon->contype;
+		newcon->attnum = ccon->attnum;
+
+		tab->constraints = lappend(tab->constraints, newcon);
+	}
+
 	ObjectAddressSet(address, ConstraintRelationId, ccon->conoid);
 
 	InvokeObjectPostAlterHook(RelationRelationId,
@@ -9918,13 +10018,15 @@ ATAddCheckNNConstraint(List **wqueue, AlteredTableInfo *tab, Relation rel,
 	{
 		CookedConstraint *ccon = (CookedConstraint *) lfirst(lcon);
 
-		if (!ccon->skip_validation && ccon->contype != CONSTR_NOTNULL)
+		if (!ccon->skip_validation)
 		{
 			NewConstraint *newcon;
 
 			newcon = (NewConstraint *) palloc0(sizeof(NewConstraint));
 			newcon->name = ccon->name;
 			newcon->contype = ccon->contype;
+			if (ccon->contype == CONSTR_NOTNULL)
+				newcon->attnum = ccon->attnum;
 			newcon->qual = ccon->expr;
 
 			tab->constraints = lappend(tab->constraints, newcon);
@@ -13166,6 +13268,7 @@ QueueNNConstraintValidation(List **wqueue, Relation conrel, Relation rel,
 	List	   *children = NIL;
 	AttrNumber	attnum;
 	char	   *colname;
+	NewConstraint *newcon;
 
 	con = (Form_pg_constraint) GETSTRUCT(contuple);
 	Assert(con->contype == CONSTRAINT_NOTNULL);
@@ -13229,7 +13332,19 @@ QueueNNConstraintValidation(List **wqueue, Relation conrel, Relation rel,
 	/* Set attnotnull appropriately without queueing another validation */
 	set_attnotnull(NULL, rel, attnum, true, false);
 
+	/*
+	 * Queue validation for phase 3.  ALTER TABLE SET NOT NULL will add NOT NULL
+	 * constraint to AlteredTableInfo->constraints, for consistency, do the same
+	 * here.
+	*/
+	newcon = (NewConstraint *) palloc0(sizeof(NewConstraint));
+	newcon->name = colname;
+	newcon->contype = CONSTR_NOTNULL;
+	newcon->attnum = attnum;
+
+	/* Find or create work queue entry for this table */
 	tab = ATGetQueueEntry(wqueue, rel);
+	tab->constraints = lappend(tab->constraints, newcon);
 	tab->verify_new_notnull = true;
 
 	/*
diff --git a/src/backend/executor/execIndexing.c b/src/backend/executor/execIndexing.c
index bdf862b2406..d1648e2a964 100644
--- a/src/backend/executor/execIndexing.c
+++ b/src/backend/executor/execIndexing.c
@@ -108,12 +108,15 @@
 
 #include "access/genam.h"
 #include "access/relscan.h"
+#include "access/table.h"
 #include "access/tableam.h"
 #include "access/xact.h"
 #include "catalog/index.h"
+#include "catalog/pg_am_d.h"
 #include "executor/executor.h"
 #include "nodes/nodeFuncs.h"
 #include "storage/lmgr.h"
+#include "utils/fmgroids.h"
 #include "utils/multirangetypes.h"
 #include "utils/rangetypes.h"
 #include "utils/snapmgr.h"
@@ -145,6 +148,7 @@ static bool index_expression_changed_walker(Node *node,
 											Bitmapset *allUpdatedCols);
 static void ExecWithoutOverlapsNotEmpty(Relation rel, NameData attname, Datum attval,
 										char typtype, Oid atttypid);
+static bool index_check_notnull_internal(Relation relation, List *attnums, List *idxs);
 
 /* ----------------------------------------------------------------
  *		ExecOpenIndices
@@ -1172,3 +1176,199 @@ ExecWithoutOverlapsNotEmpty(Relation rel, NameData attname, Datum attval, char t
 				 errmsg("empty WITHOUT OVERLAPS value found in column \"%s\" in relation \"%s\"",
 						NameStr(attname), RelationGetRelationName(rel))));
 }
+
+/*
+ * notnull_attnums: list of attribute numbers of all new not-null constraints.
+ *
+ * First check if the relation has a suitable index for each not-null attribute.
+ * If it does, then using indexscan mechanism to verify that *all* attributes on
+ * notnull_attnums are indeed not null.
+ *
+ * Returning true means by using indexscan mechanism, all new not-null
+ * constraints have been validated.
+ */
+bool
+index_check_notnull(Relation relation, List *notnull_attnums)
+{
+	Relation	pg_index;
+	Relation	index_rel;
+	SysScanDesc indscan;
+	ScanKeyData skey;
+	HeapTuple	htup;
+	TupleDesc	tupdesc;
+	Form_pg_attribute attr;
+	List	   *result = NIL;
+	List	   *attnums = NIL;
+
+	tupdesc = RelationGetDescr(relation);
+
+	/* Prepare to scan pg_index for entries having indrelid = this rel. */
+	ScanKeyInit(&skey,
+				Anum_pg_index_indrelid,
+				BTEqualStrategyNumber, F_OIDEQ,
+				ObjectIdGetDatum(RelationGetRelid(relation)));
+
+	pg_index = table_open(IndexRelationId, AccessShareLock);
+	indscan = systable_beginscan(pg_index, IndexIndrelidIndexId, true,
+								 NULL, 1, &skey);
+
+	while (HeapTupleIsValid(htup = systable_getnext(indscan)))
+	{
+		Form_pg_index index = (Form_pg_index) GETSTRUCT(htup);
+
+		/*
+		 * we can only use non-deferred, validated, and alive btree index to
+		 * validate not-null constraints
+		 */
+		if (!index->indimmediate || !index->indisvalid || !index->indislive)
+			continue;
+
+		/* can not use expression index or partial index too */
+		if (!heap_attisnull(htup, Anum_pg_index_indexprs, NULL) ||
+			!heap_attisnull(htup, Anum_pg_index_indpred, NULL))
+			continue;
+
+		/* can only apply to the btree index. also collect index attnums */
+		for (int i = 0; i < index->indnkeyatts; i++)
+		{
+			attr = TupleDescAttr(tupdesc, (index->indkey.values[i] - 1));
+
+			if (list_member_int(notnull_attnums, attr->attnum))
+			{
+				index_rel = index_open(index->indexrelid, AccessShareLock);
+
+				if (index_rel->rd_rel->relam == BTREE_AM_OID &&
+					!list_member_int(attnums, attr->attnum))
+				{
+					attnums = lappend_int(attnums, attr->attnum);
+					result = lappend_oid(result, index->indexrelid);
+				}
+				index_close(index_rel, AccessShareLock);
+			}
+		}
+	}
+	systable_endscan(indscan);
+	table_close(pg_index, AccessShareLock);
+
+	if (attnums == NIL)
+		return false;
+
+	/*
+	 * every not-null constraint requires an index for indexscan.  If no such
+	 * index exists, we need to use table scan to validate not-null constraints.
+	*/
+	foreach_int(attno, notnull_attnums)
+	{
+		if(!list_member_int(attnums, attno))
+			return false;
+	}
+
+	return index_check_notnull_internal(relation, attnums, result);
+}
+
+/*
+ * Use indexscan mechanism to fast verify each attribute in "attnums" are
+ * not-null or not.
+ */
+static bool
+index_check_notnull_internal(Relation relation, List *attnums, List *idxs)
+{
+	EState	   *estate;
+	ExprContext *econtext;
+	TupleTableSlot *existing_slot;
+	bool 		all_not_null = true;
+	ListCell   *lc,
+				*lc2;
+
+	/*
+	 * Need an EState for slot to hold the current tuple.
+	*/
+	estate = CreateExecutorState();
+	econtext = GetPerTupleExprContext(estate);
+
+	forboth(lc, attnums, lc2, idxs)
+	{
+		SnapshotData DirtySnapshot;
+		IndexScanDesc index_scan;
+		ScanKeyData		scankeys[INDEX_MAX_KEYS];
+		IndexInfo  	*indexInfo;
+		AttrNumber	sk_attno = -1;
+		Relation 	index;
+		int			indnkeyatts;
+
+		AttrNumber	attno = lfirst_int(lc);
+		Oid		indexoid = lfirst_oid(lc2);
+
+		existing_slot = table_slot_create(relation, NULL);
+
+		/* Arrange for econtext's scan tuple to be the tuple under test */
+		econtext->ecxt_scantuple = existing_slot;
+
+		index = index_open(indexoid, AccessShareLock);
+
+		indexInfo = BuildIndexInfo(index);
+		indnkeyatts = IndexRelationGetNumberOfKeyAttributes(index);
+
+		/*
+		 * Search the tuples that are in the index for any violations, including
+		 * tuples that aren't visible yet.
+		*/
+		InitDirtySnapshot(DirtySnapshot);
+
+		for (int i = 0; i < indnkeyatts; i++)
+		{
+			if (indexInfo->ii_IndexAttrNumbers[i] == attno)
+			{
+				sk_attno = i+1;
+				break;
+			}
+		}
+
+		if (sk_attno == -1)
+			elog(ERROR, "index %u should effect on column number %d", indexoid, attno);
+
+		for (int i = 0; i < indnkeyatts; i++)
+		{
+			/* set up an IS NULL scan key so that we ignore not nulls */
+			ScanKeyEntryInitialize(&scankeys[i],
+									SK_ISNULL | SK_SEARCHNULL,
+									sk_attno,		/* index col to scan */
+									InvalidStrategy,/* no strategy */
+									InvalidOid,		/* no strategy subtype */
+									InvalidOid,		/* no collation */
+									InvalidOid,		/* no reg proc for this */
+									(Datum) 0);		/* constant */
+		}
+
+		index_scan = index_beginscan(relation, index, &DirtySnapshot, NULL, indnkeyatts, 0);
+		index_rescan(index_scan, scankeys, indnkeyatts, NULL, 0);
+
+		while (index_getnext_slot(index_scan, ForwardScanDirection, existing_slot))
+		{
+			Datum		values[INDEX_MAX_KEYS];
+			bool		nulls[INDEX_MAX_KEYS];
+
+			/*
+			 * Extract the index column values and isnull flags from the
+			 * existing tuple.
+			*/
+			FormIndexDatum(indexInfo, existing_slot, estate, values, nulls);
+
+			if (nulls[sk_attno - 1])
+			{
+				all_not_null = false;
+				break;
+			}
+		}
+
+		index_endscan(index_scan);
+		index_close(index, AccessShareLock);
+		ExecDropSingleTupleTableSlot(existing_slot);
+		if (!all_not_null)
+			return false;
+	}
+
+	FreeExecutorState(estate);
+
+	return true;
+}
diff --git a/src/include/executor/executor.h b/src/include/executor/executor.h
index ae99407db89..f42407ed75e 100644
--- a/src/include/executor/executor.h
+++ b/src/include/executor/executor.h
@@ -778,6 +778,8 @@ extern void check_exclusion_constraint(Relation heap, Relation index,
 									   const Datum *values, const bool *isnull,
 									   EState *estate, bool newIndex);
 
+extern bool index_check_notnull(Relation relation, List *notnull_attnums);
+
 /*
  * prototypes from functions in execReplication.c
  */
diff --git a/src/test/isolation/expected/indexscan-check-notnull.out b/src/test/isolation/expected/indexscan-check-notnull.out
new file mode 100644
index 00000000000..2255335f00f
--- /dev/null
+++ b/src/test/isolation/expected/indexscan-check-notnull.out
@@ -0,0 +1,97 @@
+Parsed test spec with 2 sessions
+
+starting permutation: b1 b3 m1 hj c1 c3 sn
+step b1: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step b3: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step m1: DELETE FROM t;
+step hj: ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a; <waiting ...>
+step c1: COMMIT;
+step hj: <... completed>
+step c3: COMMIT;
+step sn: SELECT conname, conrelid::regclass, contype, convalidated
+           FROM pg_constraint WHERE conname = 't1_nn';
+
+conname|conrelid|contype|convalidated
+-------+--------+-------+------------
+t1_nn  |t       |n      |t           
+(1 row)
+
+
+starting permutation: b2 b3 m1 hj c1 c3 sn
+step b2: BEGIN;
+step b3: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step m1: DELETE FROM t;
+step hj: ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a; <waiting ...>
+step c1: COMMIT;
+step hj: <... completed>
+step c3: COMMIT;
+step sn: SELECT conname, conrelid::regclass, contype, convalidated
+           FROM pg_constraint WHERE conname = 't1_nn';
+
+conname|conrelid|contype|convalidated
+-------+--------+-------+------------
+t1_nn  |t       |n      |t           
+(1 row)
+
+
+starting permutation: b1 b4 m1 hj c1 c3 sn
+step b1: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step b4: BEGIN;
+step m1: DELETE FROM t;
+step hj: ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a; <waiting ...>
+step c1: COMMIT;
+step hj: <... completed>
+step c3: COMMIT;
+step sn: SELECT conname, conrelid::regclass, contype, convalidated
+           FROM pg_constraint WHERE conname = 't1_nn';
+
+conname|conrelid|contype|convalidated
+-------+--------+-------+------------
+t1_nn  |t       |n      |t           
+(1 row)
+
+
+starting permutation: b1 b3 hj r1 c2
+step b1: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step b3: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step hj: ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a;
+ERROR:  column "a" of relation "t" contains null values
+step r1: ROLLBACK;
+step c2: ROLLBACK;
+
+starting permutation: b1 b4 d1 m1 c2 s1 sn r1
+step b1: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step b4: BEGIN;
+step d1: DROP INDEX t_ab_idx;
+step m1: DELETE FROM t; <waiting ...>
+step c2: ROLLBACK;
+step m1: <... completed>
+step s1: ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a;
+step sn: SELECT conname, conrelid::regclass, contype, convalidated
+           FROM pg_constraint WHERE conname = 't1_nn';
+
+conname|conrelid|contype|convalidated
+-------+--------+-------+------------
+t1_nn  |t       |n      |t           
+(1 row)
+
+step r1: ROLLBACK;
+
+starting permutation: b2 b3 m1 d1 s0 s1 c1 c3 sn
+step b2: BEGIN;
+step b3: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step m1: DELETE FROM t;
+step d1: DROP INDEX t_ab_idx; <waiting ...>
+step s0: savepoint s0;
+step s1: ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a;
+step c1: COMMIT;
+step d1: <... completed>
+step c3: COMMIT;
+step sn: SELECT conname, conrelid::regclass, contype, convalidated
+           FROM pg_constraint WHERE conname = 't1_nn';
+
+conname|conrelid|contype|convalidated
+-------+--------+-------+------------
+t1_nn  |t       |n      |t           
+(1 row)
+
diff --git a/src/test/isolation/isolation_schedule b/src/test/isolation/isolation_schedule
index e3c669a29c7..1b9e8f932ac 100644
--- a/src/test/isolation/isolation_schedule
+++ b/src/test/isolation/isolation_schedule
@@ -56,6 +56,7 @@ test: merge-delete
 test: merge-update
 test: merge-match-recheck
 test: merge-join
+test: indexscan-check-notnull
 test: delete-abort-savept
 test: delete-abort-savept-2
 test: aborted-keyrevoke
diff --git a/src/test/isolation/specs/indexscan-check-notnull.spec b/src/test/isolation/specs/indexscan-check-notnull.spec
new file mode 100644
index 00000000000..d0ca928f3af
--- /dev/null
+++ b/src/test/isolation/specs/indexscan-check-notnull.spec
@@ -0,0 +1,45 @@
+
+#
+# using indexscan to check a column not-null constraint
+# is satisfied or not.
+#
+
+setup
+{
+  CREATE TABLE t (a int, b int);
+  CREATE INDEX t_ab_idx on t(a,b);
+  INSERT INTO t values (null, 1);
+  INSERT INTO t SELECT x, x*10 FROM generate_series(1,3) g(x);
+}
+
+teardown
+{
+  DROP TABLE t;
+}
+
+session s1
+step b1  { BEGIN ISOLATION LEVEL REPEATABLE READ; }
+step b2  { BEGIN; }
+step m1  { DELETE FROM t;}
+step s0  { savepoint s0;}
+step s1  { ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a;}
+step sn  { SELECT conname, conrelid::regclass, contype, convalidated
+           FROM pg_constraint WHERE conname = 't1_nn';
+         }
+step r1  { ROLLBACK; }
+step c1  { COMMIT; }
+
+session s2
+step b3  { BEGIN ISOLATION LEVEL REPEATABLE READ; }
+step b4  { BEGIN; }
+step hj  { ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a;}
+step d1  { DROP INDEX t_ab_idx;}
+step c2  { ROLLBACK; }
+step c3  { COMMIT; }
+
+permutation b1 b3 m1 hj c1 c3 sn
+permutation b2 b3 m1 hj c1 c3 sn
+permutation b1 b4 m1 hj c1 c3 sn
+permutation b1 b3 hj r1 c2
+permutation b1 b4 d1 m1 c2 s1 sn r1
+permutation b2 b3 m1 d1 s0 s1 c1 c3 sn
diff --git a/src/test/modules/test_misc/meson.build b/src/test/modules/test_misc/meson.build
index 9c50de7efb0..49fa16fb50e 100644
--- a/src/test/modules/test_misc/meson.build
+++ b/src/test/modules/test_misc/meson.build
@@ -16,6 +16,7 @@ tests += {
       't/005_timeouts.pl',
       't/006_signal_autovacuum.pl',
       't/007_catcache_inval.pl',
+      't/008_indexscan_validate_notnull.pl',
     ],
   },
 }
diff --git a/src/test/modules/test_misc/t/008_indexscan_validate_notnull.pl b/src/test/modules/test_misc/t/008_indexscan_validate_notnull.pl
new file mode 100644
index 00000000000..5f787cdd070
--- /dev/null
+++ b/src/test/modules/test_misc/t/008_indexscan_validate_notnull.pl
@@ -0,0 +1,164 @@
+
+# Copyright (c) 2025, PostgreSQL Global Development Group
+
+# Verify that indexscan mechanism can speedup ALTER TABLE ADD NOT NULL
+
+
+use strict;
+use warnings FATAL => 'all';
+use PostgreSQL::Test::Cluster;
+use PostgreSQL::Test::Utils;
+use Test::More;
+
+# Initialize a test cluster
+my $node = PostgreSQL::Test::Cluster->new('primary');
+$node->init();
+# Turn message level up to DEBUG1 so that we get the messages we want to see
+$node->append_conf('postgresql.conf', 'client_min_messages = DEBUG1');
+$node->start;
+
+# Run a SQL command and return psql's stderr (including debug messages)
+sub run_sql_command
+{
+	my $sql = shift;
+	my $stderr;
+
+	$node->psql(
+		'postgres',
+		$sql,
+		stderr => \$stderr,
+		on_error_die => 1,
+		on_error_stop => 1);
+	return $stderr;
+}
+
+# Check whether result of run_sql_command shows that we did a verify pass
+sub is_table_verified
+{
+	my $output = shift;
+	return index($output, 'DEBUG:  verifying table') != -1;
+}
+
+# Check whether result of run_sql_command shows that we did a verify pass
+sub is_indexscan_veritify_notnull
+{
+	my $output = shift;
+	return index($output, 'DEBUG:  all new not-null constraints on relation') != -1;
+}
+
+my $output;
+
+note "test alter table SET NOT NULL using indexscan with partitioned table";
+
+run_sql_command(
+    'CREATE TABLE tp (a int, b int, c int, d int ) PARTITION BY range(a);
+     CREATE TABLE tpp1 partition of tp for values from ( 1 ) to (10);
+     CREATE TABLE tpp2 partition of tp for values from ( 10 ) to (21);
+     INSERT INTO tp select g, g + 10, g + 15, g + random(min=>1::int, max=>10::int) from generate_series(1,19) g;
+     CREATE INDEX ON tp(b); ');
+
+$output = run_sql_command('ALTER TABLE tp ALTER COLUMN b SET NOT NULL;');
+ok(is_indexscan_veritify_notnull($output),
+	'column b will use indexscan to verify not-null status, no need scan table');
+ok( $output =~
+	  m/all new not-null constraints on relation "tpp1" have been validated by using index scan/,
+	'all newly added constraints proved by indexscan');
+
+run_sql_command(
+	'ALTER TABLE tp ALTER COLUMN b DROP NOT NULL;');
+
+# use indexes on partitions to fast vertifing not-null should be ok
+$output = run_sql_command('ALTER TABLE tpp1 ALTER COLUMN b SET NOT NULL;');
+ok(is_indexscan_veritify_notnull($output), 'use indexscan to validate column b not-null will not scan table');
+ok(!is_table_verified($output), 'no table scan for pp1');
+ok( $output =~
+	  m/all new not-null constraints on relation "tpp1" have been validated by using index scan/,
+	'all newly added constraints proved by indexscan');
+
+$output = run_sql_command('ALTER TABLE tpp2 ALTER COLUMN b SET NOT NULL;');
+ok(is_indexscan_veritify_notnull($output), 'use indexscan to validate column b not-null, will not scan table');
+ok(!is_table_verified($output), 'no table scan for tpp2');
+ok( $output =~
+	  m/all new not-null constraints on relation "tpp2" have been validated by using index scan/,
+	'all newly added constraints proved by indexscan');
+
+run_sql_command(
+	'ALTER TABLE tp ALTER COLUMN b DROP NOT NULL;');
+
+# table rewrite then can not use indexscan to verify not-null constraint
+$output = run_sql_command(
+	'ALTER TABLE tp ALTER COLUMN b SET NOT NULL, ALTER COLUMN b SET DATA TYPE bigint;'
+);
+ok(!is_table_verified($output), 'no table scan for tp');
+ok(!is_indexscan_veritify_notnull($output), 'table tp will rewrite, can not use indexscan to verify not-null constraints on it');
+
+# test using indexscan with multiple not-null constraints
+run_sql_command(
+    'ALTER TABLE tp ALTER COLUMN b DROP NOT NULL;
+	 CREATE INDEX ON tp(c);
+	 CREATE INDEX ON tp(d); ');
+
+# one column can use indexscan, another can not, so can not use indexscan to verify not-null
+$output = run_sql_command(
+	'ALTER TABLE tp ALTER COLUMN a SET NOT NULL, ADD CONSTRAINT c_nn NOT NULL c');
+ok(is_table_verified($output), 'table scan for tp');
+ok(!is_indexscan_veritify_notnull($output), 'can not use indexscan to verify not-null constraints on table tp');
+
+# all columns have index on it
+# use indexscan to verify multiple not-null constraints should just fine
+$output = run_sql_command(
+	'ALTER TABLE tp ALTER COLUMN d SET NOT NULL, ADD CONSTRAINT c_nn NOT NULL c, ALTER COLUMN b SET NOT NULL;');
+ok(!is_table_verified($output), 'no table scan for tp');
+ok(is_indexscan_veritify_notnull($output),
+	'using indexscan to verify not-null constraints on column b, c, d, no need table scan');
+
+# test with non-partitioned table and other non-Btree index.
+run_sql_command(
+    'CREATE TABLE t1(f1 INT, f2 int, f3 int,f4 int, f5 int);
+     INSERT INTO t1 select g, g+1, g+2, g+3, g+4 from generate_series(1, 100) g;
+     CREATE INDEX t1_f1_f2_idx ON t1(f1,f2);
+     CREATE UNIQUE INDEX t1_f3idx ON t1(f3);
+     CREATE INDEX t1_f3f4idx ON t1(f3) include(f4);
+     CREATE INDEX hash_f5_idx ON t1 USING hash (f5 int4_ops); ');
+
+# ALTER TABLE VALIDATE CONSTRAINT can not use indexscan,
+# because it only hold ShareUpdateExclusiveLock lock.
+run_sql_command('ALTER TABLE t1 ADD CONSTRAINT nn_t1_f2 NOT NULL f2 NOT VALID;');
+
+$output = run_sql_command(
+	'ALTER TABLE t1 VALIDATE CONSTRAINT nn_t1_f2;'
+);
+ok(!is_indexscan_veritify_notnull($output), 'can not use indexscan for ALTER TABLE VALIDATE CONSTRAINT command');
+run_sql_command('ALTER TABLE t1 DROP CONSTRAINT nn_t1_f2;');
+
+$output = run_sql_command(
+	'ALTER TABLE t1 ALTER COLUMN f1 SET NOT NULL, ALTER f1 type bigint;'
+);
+ok(!is_indexscan_veritify_notnull($output), 'table t1 will rewrite, can not use indexscan to validate not-null constraints on t1');
+
+run_sql_command('ALTER TABLE t1 ALTER COLUMN f1 DROP NOT NULL;');
+run_sql_command('ALTER TABLE t1 ADD CONSTRAINT nn NOT NULL f1, ALTER f1 type bigint;');
+
+# can use indexscan mechanism to fast add multiple not-null constraints
+$output = run_sql_command(
+	'ALTER TABLE t1 ALTER COLUMN f2 SET NOT NULL, ALTER COLUMN f1 SET NOT NULL;'
+);
+ok( $output =~
+	  m/all new not-null constraints on relation "t1" have been validated by using index scan/,
+	'all not-null constraints are validated by indexscan');
+
+# using indexscan mechanism to fast add a not-null can only apply to key columns, not include column
+$output = run_sql_command(
+	'ALTER TABLE t1 ADD CONSTRAINT nnf4 NOT NULL f4;'
+);
+ok(!is_indexscan_veritify_notnull($output), 'can not use indexscan to validate not-null constraint on t1');
+
+# if index is not btree index then cannot use indexscan mechanism to fast add not-null constraint
+$output = run_sql_command(
+	'ALTER TABLE t1 ADD CONSTRAINT nn_f5 NOT NULL f5;'
+);
+ok(!is_indexscan_veritify_notnull($output), 'can not use indexscan to validate not-null constraints on t1');
+
+$node->stop('fast');
+
+done_testing();
-- 
2.34.1

From 5a404c03556897b655359adef8057acd35246a1e Mon Sep 17 00:00:00 2001
From: jian he <jian.universality@gmail.com>
Date: Mon, 20 Oct 2025 13:29:32 +0800
Subject: [PATCH v7 1/1] using indexscan to speedup add not null constraints

This patch tries to use index_beginscan() / index_getnext() / index_endscan()
mentioned in [1] to speedup adding not-null constraints to the existing table.

The main logic happens in phase3 ATRewriteTable
1. collect all not-null constraints.
2. For each not-null constraint, check whether there is a corresponding index
available for validation. If not, then can not use indexscan to verify not-null
constraints.
3. If any of the following conditions are true
  * table scan or rewrite is required,
  * table wasn't locked with `AccessExclusiveLock`
  * the NOT NULL constraint applies to a virtual generated column
 then index scan cannot be used for fast validation.
4. If all conditions are satisfied, attempt to use indexscan to verify
whether the column contains any NULL values.

concurrency concern:
ALTER TABLE SET NOT NULL will take an ACCESS EXCLUSIVE lock, so there is less
variant of racing issue can occur?  to prove accurate, I wrote some isolation
tests. see[2]

performance:
demo:
case when: %20 percent values are NULL and have been deleted from heap but they
still on the index.

drop table if exists t;
create unlogged table t(a int, b int) with (autovacuum_enabled = off, vacuum_index_cleanup=off);
insert into t select case when g % 5 = 0 then null else g end, g+1
from generate_series(1,1_000_000) g;
create index t_idx_a on t(a);
delete from t where a is null;

alter table t alter column a drop not null;
alter table t add constraint t1 not null a;

the above two statement running several times:
patch Time:: 1.084  ms
master Time: 12.045 ms

references:
[1] https://postgr.es/m/CA%2BTgmoa5NKz8iGW_9v7wz%3D-%2BzQFu%3DE4SZoaTaU1znLaEXRYp-Q%40mail.gmail.com
[2] https://postgr.es/m/900056D1-32DF-4927-8251-3E0C0DC407FD%40anarazel.de
discussion: https://postgr.es/m/CACJufxFiW=4k1is=F1J=r-Cx1RuByXQPUrWB331U47rSnGz+hw@mail.gmail.com
commitfest entry: https://commitfest.postgresql.org/patch/5444
---
 src/backend/commands/tablecmds.c              | 120 +++++++++-
 src/backend/executor/execIndexing.c           | 213 ++++++++++++++++++
 src/include/executor/executor.h               |   2 +
 .../expected/indexscan-check-notnull.out      |  97 ++++++++
 src/test/isolation/isolation_schedule         |   1 +
 .../specs/indexscan-check-notnull.spec        |  45 ++++
 src/test/modules/test_misc/meson.build        |   1 +
 .../t/010_indexscan_validate_notnull.pl       | 163 ++++++++++++++
 8 files changed, 636 insertions(+), 6 deletions(-)
 create mode 100644 src/test/isolation/expected/indexscan-check-notnull.out
 create mode 100644 src/test/isolation/specs/indexscan-check-notnull.spec
 create mode 100644 src/test/modules/test_misc/t/010_indexscan_validate_notnull.pl

diff --git a/src/backend/commands/tablecmds.c b/src/backend/commands/tablecmds.c
index 5fd8b51312c..e686619d775 100644
--- a/src/backend/commands/tablecmds.c
+++ b/src/backend/commands/tablecmds.c
@@ -210,16 +210,19 @@ typedef struct AlteredTableInfo
 	List	   *changedStatisticsDefs;	/* string definitions of same */
 } AlteredTableInfo;
 
-/* Struct describing one new constraint to check in Phase 3 scan */
-/* Note: new not-null constraints are handled elsewhere */
+/*
+ * Struct describing one new constraint to check in Phase 3 scan. Note: new
+ * not-null constraints are handled here too.
+*/
 typedef struct NewConstraint
 {
 	char	   *name;			/* Constraint name, or NULL if none */
-	ConstrType	contype;		/* CHECK or FOREIGN */
+	ConstrType	contype;		/* CHECK or FOREIGN or NOT NULL */
 	Oid			refrelid;		/* PK rel, if FOREIGN */
 	Oid			refindid;		/* OID of PK's index, if FOREIGN */
 	bool		conwithperiod;	/* Whether the new FOREIGN KEY uses PERIOD */
 	Oid			conid;			/* OID of pg_constraint entry, if FOREIGN */
+	int			attnum;			/* NOT NULL constraint attribute number */
 	Node	   *qual;			/* Check expr or CONSTR_FOREIGN Constraint */
 	ExprState  *qualstate;		/* Execution state for CHECK expr */
 } NewConstraint;
@@ -6184,6 +6187,9 @@ ATRewriteTable(AlteredTableInfo *tab, Oid OIDNewHeap)
 				needscan = true;
 				con->qualstate = ExecPrepareExpr((Expr *) expand_generated_columns_in_expr(con->qual, oldrel, 1), estate);
 				break;
+			case CONSTR_NOTNULL:
+				/* Nothing to do here */
+				break;
 			case CONSTR_FOREIGN:
 				/* Nothing to do here */
 				break;
@@ -6237,10 +6243,75 @@ ATRewriteTable(AlteredTableInfo *tab, Oid OIDNewHeap)
 														wholeatt->attnum);
 			}
 		}
-		if (notnull_attrs || notnull_virtual_attrs)
-			needscan = true;
 	}
 
+	/*
+	 * The conditions for using indexscan mechanism fast vertifing not-null
+	 * constraints are quite strict. All of the following conditions must be
+	 * met.
+	 * 1. AlteredTableInfo->verify_new_notnull is true.
+	 * 2. If table scan (for other reason, like check constraint verification)
+	 *    or table rewrite is expected later, using indexscan is just wastes
+	 *    cycles.
+	 * 3. Indexes cannot be created on virtual generated columns, so fast
+	 *    checking not-null constraints is not applicable to them.
+	 * 4. This applies to plain relation only.
+	 * 5. To prevent possible concurrency issues, the table must already be
+	 *    locked with an AccessExclusiveLock, which is the lock obtained during
+	 *    ALTER TABLE SET NOT NULL.
+	 */
+	if (!needscan &&
+		newrel == NULL &&
+		tab->verify_new_notnull &&
+		notnull_virtual_attrs == NIL &&
+		oldrel->rd_rel->relkind == RELKIND_RELATION &&
+		CheckRelationLockedByMe(oldrel, AccessExclusiveLock, false))
+	{
+		List	   *notnull_attnums = NIL;
+
+		Assert(!tab->rewrite);
+
+		foreach(l, tab->constraints)
+		{
+			Form_pg_attribute 	attr;
+			NewConstraint *con = lfirst(l);
+
+			if (con->contype != CONSTR_NOTNULL)
+				continue;
+
+			attr = TupleDescAttr(newTupDesc, con->attnum - 1);
+
+			Assert(attr->attnotnull);
+			Assert(attr->attnum == con->attnum);
+
+			if (attr->attgenerated == ATTRIBUTE_GENERATED_VIRTUAL)
+			{
+				needscan = true;
+				break;
+			}
+
+			notnull_attnums = lappend_int(notnull_attnums, attr->attnum);
+		}
+
+		/*
+		 * notnull_attnums contains all attributes with NOT NULL constraints
+		 * that needs to be validation.
+		 * If needscan is really needed, later table scan will do the
+		 * validation, indedxscan would just waste cycle.
+		 */
+		if (notnull_attnums != NIL && !needscan)
+		{
+			if (!index_check_notnull(oldrel, notnull_attnums))
+				needscan = true;
+			else
+				ereport(DEBUG1,
+						errmsg_internal("all new not-null constraints on relation \"%s\" have been validated by using index scan",
+										RelationGetRelationName(oldrel)));
+		}
+	}
+	else if (notnull_attrs || notnull_virtual_attrs)
+		needscan = true;
+
 	if (newrel || needscan)
 	{
 		ExprContext *econtext;
@@ -7912,6 +7983,7 @@ ATExecSetNotNull(List **wqueue, Relation rel, char *conName, char *colName,
 	CookedConstraint *ccon;
 	List	   *cooked;
 	bool		is_no_inherit = false;
+	AlteredTableInfo *tab = NULL;
 
 	/* Guard against stack overflow due to overly deep inheritance tree. */
 	check_stack_depth();
@@ -8036,10 +8108,31 @@ ATExecSetNotNull(List **wqueue, Relation rel, char *conName, char *colName,
 	constraint->is_no_inherit = is_no_inherit;
 	constraint->conname = conName;
 
+	tab = ATGetQueueEntry(wqueue, rel);
+
 	/* and do it */
 	cooked = AddRelationNewConstraints(rel, NIL, list_make1(constraint),
 									   false, !recursing, false, NULL);
 	ccon = linitial(cooked);
+
+	Assert(ccon->contype == CONSTR_NOTNULL);
+
+	/*
+	 * We may use indexscan to vertify not-null constraint in Phase3.  Add the
+	 * to-be-validated not-null constraint to Phase 3's queue.
+	 */
+	if (!ccon->skip_validation)
+	{
+		NewConstraint *newcon;
+		newcon = (NewConstraint *) palloc0(sizeof(NewConstraint));
+
+		newcon->name = ccon->name;
+		newcon->contype = ccon->contype;
+		newcon->attnum = ccon->attnum;
+
+		tab->constraints = lappend(tab->constraints, newcon);
+	}
+
 	ObjectAddressSet(address, ConstraintRelationId, ccon->conoid);
 
 	InvokeObjectPostAlterHook(RelationRelationId,
@@ -9920,13 +10013,15 @@ ATAddCheckNNConstraint(List **wqueue, AlteredTableInfo *tab, Relation rel,
 	{
 		CookedConstraint *ccon = (CookedConstraint *) lfirst(lcon);
 
-		if (!ccon->skip_validation && ccon->contype != CONSTR_NOTNULL)
+		if (!ccon->skip_validation)
 		{
 			NewConstraint *newcon;
 
 			newcon = (NewConstraint *) palloc0(sizeof(NewConstraint));
 			newcon->name = ccon->name;
 			newcon->contype = ccon->contype;
+			if (ccon->contype == CONSTR_NOTNULL)
+				newcon->attnum = ccon->attnum;
 			newcon->qual = ccon->expr;
 
 			tab->constraints = lappend(tab->constraints, newcon);
@@ -13195,6 +13290,7 @@ QueueNNConstraintValidation(List **wqueue, Relation conrel, Relation rel,
 	List	   *children = NIL;
 	AttrNumber	attnum;
 	char	   *colname;
+	NewConstraint *newcon;
 
 	con = (Form_pg_constraint) GETSTRUCT(contuple);
 	Assert(con->contype == CONSTRAINT_NOTNULL);
@@ -13258,7 +13354,19 @@ QueueNNConstraintValidation(List **wqueue, Relation conrel, Relation rel,
 	/* Set attnotnull appropriately without queueing another validation */
 	set_attnotnull(NULL, rel, attnum, true, false);
 
+	/*
+	 * Queue validation for phase 3.
+	 * ALTER TABLE SET NOT NULL will add NOT NULL constraint to
+	 * AlteredTableInfo->constraints, for consistency, do the same here.
+	 */
+	newcon = (NewConstraint *) palloc0(sizeof(NewConstraint));
+	newcon->name = colname;
+	newcon->contype = CONSTR_NOTNULL;
+	newcon->attnum = attnum;
+
+	/* Find or create work queue entry for this table */
 	tab = ATGetQueueEntry(wqueue, rel);
+	tab->constraints = lappend(tab->constraints, newcon);
 	tab->verify_new_notnull = true;
 
 	/*
diff --git a/src/backend/executor/execIndexing.c b/src/backend/executor/execIndexing.c
index ca33a854278..7cb539a7bcf 100644
--- a/src/backend/executor/execIndexing.c
+++ b/src/backend/executor/execIndexing.c
@@ -108,12 +108,15 @@
 
 #include "access/genam.h"
 #include "access/relscan.h"
+#include "access/table.h"
 #include "access/tableam.h"
 #include "access/xact.h"
 #include "catalog/index.h"
+#include "catalog/pg_am_d.h"
 #include "executor/executor.h"
 #include "nodes/nodeFuncs.h"
 #include "storage/lmgr.h"
+#include "utils/fmgroids.h"
 #include "utils/multirangetypes.h"
 #include "utils/rangetypes.h"
 #include "utils/snapmgr.h"
@@ -145,6 +148,7 @@ static bool index_expression_changed_walker(Node *node,
 											Bitmapset *allUpdatedCols);
 static void ExecWithoutOverlapsNotEmpty(Relation rel, NameData attname, Datum attval,
 										char typtype, Oid atttypid);
+static bool index_check_notnull_internal(Relation relation, List *attnums, List *idxs);
 
 /* ----------------------------------------------------------------
  *		ExecOpenIndices
@@ -1172,3 +1176,212 @@ ExecWithoutOverlapsNotEmpty(Relation rel, NameData attname, Datum attval, char t
 				 errmsg("empty WITHOUT OVERLAPS value found in column \"%s\" in relation \"%s\"",
 						NameStr(attname), RelationGetRelationName(rel))));
 }
+
+/*
+ * notnull_attnums: list of attribute numbers of all new not-null constraints.
+ *
+ * First check whether the relation has a suitable index for each not-null
+ * attribute, then using indexscan mechanism to verify that *all* attributes on
+ * notnull_attnums are indeed not null.
+ *
+ * Returning true means all new not-null constraints have been verified, no
+ * need an extra scan to verify newly added not-null constraints.
+ */
+bool
+index_check_notnull(Relation relation, List *notnull_attnums)
+{
+	Relation	pg_index;
+	Relation	index_rel;
+	SysScanDesc indscan;
+	ScanKeyData skey;
+	HeapTuple	htup;
+	TupleDesc	tupdesc;
+	Form_pg_attribute attr;
+	List	   *idxs = NIL;
+	List	   *attnums = NIL;
+
+	tupdesc = RelationGetDescr(relation);
+
+	/* Prepare to scan pg_index for entries having indrelid = this rel */
+	ScanKeyInit(&skey,
+				Anum_pg_index_indrelid,
+				BTEqualStrategyNumber, F_OIDEQ,
+				ObjectIdGetDatum(RelationGetRelid(relation)));
+
+	pg_index = table_open(IndexRelationId, AccessShareLock);
+	indscan = systable_beginscan(pg_index, IndexIndrelidIndexId, true,
+								 NULL, 1, &skey);
+
+	while (HeapTupleIsValid(htup = systable_getnext(indscan)))
+	{
+		Form_pg_index index = (Form_pg_index) GETSTRUCT(htup);
+
+		/*
+		 * we can only use non-deferred, validated, and alive btree index to
+		 * validate not-null constraints
+		 */
+		if (!index->indimmediate || !index->indisvalid || !index->indislive)
+			continue;
+
+		/* can not use expression index or partial index too */
+		if (!heap_attisnull(htup, Anum_pg_index_indexprs, NULL) ||
+			!heap_attisnull(htup, Anum_pg_index_indpred, NULL))
+			continue;
+
+		index_rel = index_open(index->indexrelid, AccessShareLock);
+
+		/* can only apply to btree index */
+		if (index_rel->rd_rel->relam != BTREE_AM_OID)
+		{
+			index_close(index_rel, AccessShareLock);
+			continue;
+		}
+
+		/* collect index attnums while loop */
+		for (int i = 0; i < index->indnkeyatts; i++)
+		{
+			attr = TupleDescAttr(tupdesc, (index->indkey.values[i] - 1));
+
+			if (attr->attisdropped)
+				continue;
+
+			if (list_member_int(notnull_attnums, attr->attnum) &&
+				!list_member_int(attnums, attr->attnum))
+			{
+				attnums = lappend_int(attnums, attr->attnum);
+				idxs = lappend_oid(idxs, index->indexrelid);
+			}
+		}
+		index_close(index_rel, NoLock);
+	}
+	systable_endscan(indscan);
+	table_close(pg_index, AccessShareLock);
+
+	if (attnums == NIL)
+		return false;
+
+	/*
+	 * every not-null constraint requires an index for indexscan.  If no such
+	 * index exists, we need to use regular table scan to validate not-null
+	 * constraints.
+	 */
+	foreach_int(attno, notnull_attnums)
+	{
+		if(!list_member_int(attnums, attno))
+			return false;
+	}
+
+	return index_check_notnull_internal(relation, attnums, idxs);
+}
+
+/*
+ * Use indexscan mechanism to fast verify each attribute in "attnums" are
+ * not-null or not.
+ */
+static bool
+index_check_notnull_internal(Relation relation, List *attnums, List *idxs)
+{
+	EState	   *estate;
+	ExprContext *econtext;
+	TupleTableSlot *existing_slot;
+	bool 		all_not_null = true;
+	ListCell   *lc,
+			   *lc2;
+
+	/*
+	 * Need an EState for slot to hold the current tuple.
+	 */
+	estate = CreateExecutorState();
+	econtext = GetPerTupleExprContext(estate);
+
+	forboth(lc, attnums, lc2, idxs)
+	{
+		SnapshotData DirtySnapshot;
+		IndexScanDesc index_scan;
+		ScanKeyData		scankeys[INDEX_MAX_KEYS];
+		IndexInfo  	*indexInfo;
+		AttrNumber	sk_attno = -1;
+		Relation 	index;
+		int			indnkeyatts;
+
+		AttrNumber	attno = lfirst_int(lc);
+		Oid		indexoid = lfirst_oid(lc2);
+
+		existing_slot = table_slot_create(relation, NULL);
+
+		/* Arrange for econtext's scan tuple to be the tuple under test */
+		econtext->ecxt_scantuple = existing_slot;
+
+		index = index_open(indexoid, NoLock);
+
+		indexInfo = BuildIndexInfo(index);
+		indnkeyatts = IndexRelationGetNumberOfKeyAttributes(index);
+
+		/*
+		 * Search the tuples that are in the index for any violations, including
+		 * tuples that aren't visible yet.
+		 */
+		InitDirtySnapshot(DirtySnapshot);
+
+		for (int i = 0; i < indnkeyatts; i++)
+		{
+			if (indexInfo->ii_IndexAttrNumbers[i] == attno)
+			{
+				sk_attno = i+1;
+				break;
+			}
+		}
+
+		if (sk_attno == -1)
+			elog(ERROR, "cache lookup failed for attribute number %d on index %u", indexoid, attno);
+
+		for (int i = 0; i < indnkeyatts; i++)
+		{
+			/* set up an IS NULL scan key so that we ignore not nulls */
+			ScanKeyEntryInitialize(&scankeys[i],
+								   SK_ISNULL | SK_SEARCHNULL,
+								   sk_attno,		/* index col to scan */
+								   InvalidStrategy, /* no strategy */
+								   InvalidOid,		/* no strategy subtype */
+								   InvalidOid,		/* no collation */
+								   InvalidOid,		/* no reg proc for this */
+								   (Datum) 0);		/* constant */
+		}
+
+		index_scan = index_beginscan(relation, index, &DirtySnapshot, NULL, indnkeyatts, 0);
+		index_rescan(index_scan, scankeys, indnkeyatts, NULL, 0);
+
+		while (index_getnext_slot(index_scan, ForwardScanDirection, existing_slot))
+		{
+			Datum		values[INDEX_MAX_KEYS];
+			bool		nulls[INDEX_MAX_KEYS];
+
+			/*
+			 * Extract the index column values and isnull flags from the
+			 * existing tuple.
+			 */
+			FormIndexDatum(indexInfo, existing_slot, estate, values, nulls);
+
+			if (nulls[sk_attno - 1])
+			{
+				all_not_null = false;
+				break;
+			}
+		}
+
+		index_endscan(index_scan);
+		index_close(index, NoLock);
+		ExecDropSingleTupleTableSlot(existing_slot);
+
+		/* exit earlier */
+		if (!all_not_null)
+		{
+			FreeExecutorState(estate);
+			return false;
+		}
+	}
+
+	FreeExecutorState(estate);
+
+	return true;
+}
diff --git a/src/include/executor/executor.h b/src/include/executor/executor.h
index 3248e78cd28..20dad31f73c 100644
--- a/src/include/executor/executor.h
+++ b/src/include/executor/executor.h
@@ -753,6 +753,8 @@ extern void check_exclusion_constraint(Relation heap, Relation index,
 									   const Datum *values, const bool *isnull,
 									   EState *estate, bool newIndex);
 
+extern bool index_check_notnull(Relation relation, List *notnull_attnums);
+
 /*
  * prototypes from functions in execReplication.c
  */
diff --git a/src/test/isolation/expected/indexscan-check-notnull.out b/src/test/isolation/expected/indexscan-check-notnull.out
new file mode 100644
index 00000000000..c6a652e2518
--- /dev/null
+++ b/src/test/isolation/expected/indexscan-check-notnull.out
@@ -0,0 +1,97 @@
+Parsed test spec with 2 sessions
+
+starting permutation: s1_b1 s2_b1 s1_d1 s2_a1 s1_c1 s2_c1 s1_q1
+step s1_b1: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step s2_b1: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step s1_d1: DELETE FROM t;
+step s2_a1: ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a; <waiting ...>
+step s1_c1: COMMIT;
+step s2_a1: <... completed>
+step s2_c1: COMMIT;
+step s1_q1: SELECT conname, conrelid::regclass, contype, convalidated
+              FROM pg_constraint WHERE conname = 't1_nn';
+
+conname|conrelid|contype|convalidated
+-------+--------+-------+------------
+t1_nn  |t       |n      |t           
+(1 row)
+
+
+starting permutation: s1_b2 s2_b1 s1_d1 s2_a1 s1_c1 s2_c1 s1_q1
+step s1_b2: BEGIN;
+step s2_b1: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step s1_d1: DELETE FROM t;
+step s2_a1: ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a; <waiting ...>
+step s1_c1: COMMIT;
+step s2_a1: <... completed>
+step s2_c1: COMMIT;
+step s1_q1: SELECT conname, conrelid::regclass, contype, convalidated
+              FROM pg_constraint WHERE conname = 't1_nn';
+
+conname|conrelid|contype|convalidated
+-------+--------+-------+------------
+t1_nn  |t       |n      |t           
+(1 row)
+
+
+starting permutation: s1_b1 s2_b2 s1_d1 s2_a1 s1_c1 s2_c1 s1_q1
+step s1_b1: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step s2_b2: BEGIN;
+step s1_d1: DELETE FROM t;
+step s2_a1: ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a; <waiting ...>
+step s1_c1: COMMIT;
+step s2_a1: <... completed>
+step s2_c1: COMMIT;
+step s1_q1: SELECT conname, conrelid::regclass, contype, convalidated
+              FROM pg_constraint WHERE conname = 't1_nn';
+
+conname|conrelid|contype|convalidated
+-------+--------+-------+------------
+t1_nn  |t       |n      |t           
+(1 row)
+
+
+starting permutation: s1_b1 s2_b1 s2_a1 s1_r1 s2_r1
+step s1_b1: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step s2_b1: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step s2_a1: ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a;
+ERROR:  column "a" of relation "t" contains null values
+step s1_r1: ROLLBACK;
+step s2_r1: ROLLBACK;
+
+starting permutation: s1_b1 s2_b2 s2_d1 s1_d1 s2_r1 s1_a1 s1_q1 s1_r1
+step s1_b1: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step s2_b2: BEGIN;
+step s2_d1: DROP INDEX t_ab_idx;
+step s1_d1: DELETE FROM t; <waiting ...>
+step s2_r1: ROLLBACK;
+step s1_d1: <... completed>
+step s1_a1: ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a;
+step s1_q1: SELECT conname, conrelid::regclass, contype, convalidated
+              FROM pg_constraint WHERE conname = 't1_nn';
+
+conname|conrelid|contype|convalidated
+-------+--------+-------+------------
+t1_nn  |t       |n      |t           
+(1 row)
+
+step s1_r1: ROLLBACK;
+
+starting permutation: s1_b2 s2_b1 s1_d1 s2_d1 s1_s0 s1_a1 s1_c1 s2_c1 s1_q1
+step s1_b2: BEGIN;
+step s2_b1: BEGIN ISOLATION LEVEL REPEATABLE READ;
+step s1_d1: DELETE FROM t;
+step s2_d1: DROP INDEX t_ab_idx; <waiting ...>
+step s1_s0: SAVEPOINT s0;
+step s1_a1: ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a;
+step s1_c1: COMMIT;
+step s2_d1: <... completed>
+step s2_c1: COMMIT;
+step s1_q1: SELECT conname, conrelid::regclass, contype, convalidated
+              FROM pg_constraint WHERE conname = 't1_nn';
+
+conname|conrelid|contype|convalidated
+-------+--------+-------+------------
+t1_nn  |t       |n      |t           
+(1 row)
+
diff --git a/src/test/isolation/isolation_schedule b/src/test/isolation/isolation_schedule
index 5afae33d370..a5926dc81d7 100644
--- a/src/test/isolation/isolation_schedule
+++ b/src/test/isolation/isolation_schedule
@@ -59,6 +59,7 @@ test: merge-delete
 test: merge-update
 test: merge-match-recheck
 test: merge-join
+test: indexscan-check-notnull
 test: delete-abort-savept
 test: delete-abort-savept-2
 test: aborted-keyrevoke
diff --git a/src/test/isolation/specs/indexscan-check-notnull.spec b/src/test/isolation/specs/indexscan-check-notnull.spec
new file mode 100644
index 00000000000..05b4488550c
--- /dev/null
+++ b/src/test/isolation/specs/indexscan-check-notnull.spec
@@ -0,0 +1,45 @@
+
+#
+# using indexscan to check a column not-null constraint
+# is satisfied or not.
+#
+
+setup
+{
+  CREATE TABLE t (a int, b int);
+  CREATE INDEX t_ab_idx on t(a,b);
+  INSERT INTO t values (null, 1);
+  INSERT INTO t SELECT x, x*10 FROM generate_series(1,3) g(x);
+}
+
+teardown
+{
+  DROP TABLE t;
+}
+
+session s1
+step s1_b1  { BEGIN ISOLATION LEVEL REPEATABLE READ; }
+step s1_b2  { BEGIN; }
+step s1_d1  { DELETE FROM t;}
+step s1_s0  { SAVEPOINT s0;}
+step s1_a1  { ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a;}
+step s1_q1  { SELECT conname, conrelid::regclass, contype, convalidated
+              FROM pg_constraint WHERE conname = 't1_nn';
+            }
+step s1_r1  { ROLLBACK; }
+step s1_c1  { COMMIT; }
+
+session s2
+step s2_b1  { BEGIN ISOLATION LEVEL REPEATABLE READ; }
+step s2_b2  { BEGIN; }
+step s2_a1  { ALTER TABLE t ADD CONSTRAINT t1_nn NOT NULL a;}
+step s2_d1  { DROP INDEX t_ab_idx;}
+step s2_r1  { ROLLBACK; }
+step s2_c1  { COMMIT; }
+
+permutation s1_b1 s2_b1 s1_d1 s2_a1 s1_c1 s2_c1 s1_q1
+permutation s1_b2 s2_b1 s1_d1 s2_a1 s1_c1 s2_c1 s1_q1
+permutation s1_b1 s2_b2 s1_d1 s2_a1 s1_c1 s2_c1 s1_q1
+permutation s1_b1 s2_b1 s2_a1 s1_r1 s2_r1
+permutation s1_b1 s2_b2 s2_d1 s1_d1 s2_r1 s1_a1 s1_q1 s1_r1
+permutation s1_b2 s2_b1 s1_d1 s2_d1 s1_s0 s1_a1 s1_c1 s2_c1 s1_q1
diff --git a/src/test/modules/test_misc/meson.build b/src/test/modules/test_misc/meson.build
index f258bf1ccd9..cfcc7fa6a05 100644
--- a/src/test/modules/test_misc/meson.build
+++ b/src/test/modules/test_misc/meson.build
@@ -18,6 +18,7 @@ tests += {
       't/007_catcache_inval.pl',
       't/008_replslot_single_user.pl',
       't/009_log_temp_files.pl',
+      't/010_indexscan_validate_notnull.pl',
     ],
   },
 }
diff --git a/src/test/modules/test_misc/t/010_indexscan_validate_notnull.pl b/src/test/modules/test_misc/t/010_indexscan_validate_notnull.pl
new file mode 100644
index 00000000000..a3f3cb409b6
--- /dev/null
+++ b/src/test/modules/test_misc/t/010_indexscan_validate_notnull.pl
@@ -0,0 +1,163 @@
+# Copyright (c) 2025, PostgreSQL Global Development Group
+
+# Verify that indexscan mechanism can speedup ALTER TABLE ADD NOT NULL
+
+
+use strict;
+use warnings FATAL => 'all';
+use PostgreSQL::Test::Cluster;
+use PostgreSQL::Test::Utils;
+use Test::More;
+
+# Initialize a test cluster
+my $node = PostgreSQL::Test::Cluster->new('primary');
+$node->init();
+# Turn message level up to DEBUG1 so that we get the messages we want to see
+$node->append_conf('postgresql.conf', 'client_min_messages = DEBUG1');
+$node->start;
+
+# Run a SQL command and return psql's stderr (including debug messages)
+sub run_sql_command
+{
+	my $sql = shift;
+	my $stderr;
+
+	$node->psql(
+		'postgres',
+		$sql,
+		stderr => \$stderr,
+		on_error_die => 1,
+		on_error_stop => 1);
+	return $stderr;
+}
+
+# Check whether result of run_sql_command shows that we did a verify pass
+sub is_table_verified
+{
+	my $output = shift;
+	return index($output, 'DEBUG:  verifying table') != -1;
+}
+
+# Check whether result of run_sql_command shows that we did a verify pass
+sub is_indexscan_veritify_notnull
+{
+	my $output = shift;
+	return index($output, 'DEBUG:  all new not-null constraints on relation') != -1;
+}
+
+my $output;
+
+note "test alter table SET NOT NULL using indexscan with partitioned table";
+
+run_sql_command(
+    'CREATE TABLE tp (a int, b int, c int, d int ) PARTITION BY range(a);
+     CREATE TABLE tpp1 partition of tp for values from ( 1 ) to (10);
+     CREATE TABLE tpp2 partition of tp for values from ( 10 ) to (21);
+     INSERT INTO tp select g, g + 10, g + 15, g + random(min=>1::int, max=>10::int) from generate_series(1,19) g;
+     CREATE INDEX ON tp(b); ');
+
+$output = run_sql_command('ALTER TABLE tp ALTER COLUMN b SET NOT NULL;');
+ok(is_indexscan_veritify_notnull($output),
+	'column b will use indexscan to verify not-null status, no need scan table');
+ok( $output =~
+	  m/all new not-null constraints on relation "tpp1" have been validated by using index scan/,
+	'all newly added constraints proved by indexscan');
+
+run_sql_command(
+	'ALTER TABLE tp ALTER COLUMN b DROP NOT NULL;');
+
+# use indexes on partitions to fast vertifing not-null should be ok
+$output = run_sql_command('ALTER TABLE tpp1 ALTER COLUMN b SET NOT NULL;');
+ok(is_indexscan_veritify_notnull($output), 'use indexscan to validate column b not-null will not scan table');
+ok(!is_table_verified($output), 'no table scan for pp1');
+ok( $output =~
+	  m/all new not-null constraints on relation "tpp1" have been validated by using index scan/,
+	'all newly added constraints proved by indexscan');
+
+$output = run_sql_command('ALTER TABLE tpp2 ALTER COLUMN b SET NOT NULL;');
+ok(is_indexscan_veritify_notnull($output), 'use indexscan to validate column b not-null, will not scan table');
+ok(!is_table_verified($output), 'no table scan for tpp2');
+ok( $output =~
+	  m/all new not-null constraints on relation "tpp2" have been validated by using index scan/,
+	'all newly added constraints proved by indexscan');
+
+run_sql_command(
+	'ALTER TABLE tp ALTER COLUMN b DROP NOT NULL;');
+
+# table rewrite then can not use indexscan to verify not-null constraint
+$output = run_sql_command(
+	'ALTER TABLE tp ALTER COLUMN b SET NOT NULL, ALTER COLUMN b SET DATA TYPE bigint;'
+);
+ok(!is_table_verified($output), 'no table scan for tp');
+ok(!is_indexscan_veritify_notnull($output), 'table tp will rewrite, can not use indexscan to verify not-null constraints on it');
+
+# test using indexscan with multiple not-null constraints
+run_sql_command(
+    'ALTER TABLE tp ALTER COLUMN b DROP NOT NULL;
+	 CREATE INDEX ON tp(c);
+	 CREATE INDEX ON tp(d); ');
+
+# one column can use indexscan, another can not, so can not use indexscan to verify not-null
+$output = run_sql_command(
+	'ALTER TABLE tp ALTER COLUMN a SET NOT NULL, ADD CONSTRAINT c_nn NOT NULL c');
+ok(is_table_verified($output), 'table scan for tp');
+ok(!is_indexscan_veritify_notnull($output), 'can not use indexscan to verify not-null constraints on table tp');
+
+# all columns have index on it
+# use indexscan to verify multiple not-null constraints should just fine
+$output = run_sql_command(
+	'ALTER TABLE tp ALTER COLUMN d SET NOT NULL, ADD CONSTRAINT c_nn NOT NULL c, ALTER COLUMN b SET NOT NULL;');
+ok(!is_table_verified($output), 'no table scan for tp');
+ok(is_indexscan_veritify_notnull($output),
+	'using indexscan to verify not-null constraints on column b, c, d, no need table scan');
+
+# test with non-partitioned table and other non-Btree index.
+run_sql_command(
+    'CREATE TABLE t1(f1 INT, f2 int, f3 int,f4 int, f5 int);
+     INSERT INTO t1 select g, g+1, g+2, g+3, g+4 from generate_series(1, 100) g;
+     CREATE INDEX t1_f1_f2_idx ON t1(f1,f2);
+     CREATE UNIQUE INDEX t1_f3idx ON t1(f3);
+     CREATE INDEX t1_f3f4idx ON t1(f3) include(f4);
+     CREATE INDEX hash_f5_idx ON t1 USING hash (f5 int4_ops); ');
+
+# ALTER TABLE VALIDATE CONSTRAINT can not use indexscan,
+# because it only hold ShareUpdateExclusiveLock lock.
+run_sql_command('ALTER TABLE t1 ADD CONSTRAINT nn_t1_f2 NOT NULL f2 NOT VALID;');
+
+$output = run_sql_command(
+	'ALTER TABLE t1 VALIDATE CONSTRAINT nn_t1_f2;'
+);
+ok(!is_indexscan_veritify_notnull($output), 'can not use indexscan for ALTER TABLE VALIDATE CONSTRAINT command');
+run_sql_command('ALTER TABLE t1 DROP CONSTRAINT nn_t1_f2;');
+
+$output = run_sql_command(
+	'ALTER TABLE t1 ALTER COLUMN f1 SET NOT NULL, ALTER f1 type bigint;'
+);
+ok(!is_indexscan_veritify_notnull($output), 'table t1 will rewrite, can not use indexscan to validate not-null constraints on t1');
+
+run_sql_command('ALTER TABLE t1 ALTER COLUMN f1 DROP NOT NULL;');
+run_sql_command('ALTER TABLE t1 ADD CONSTRAINT nn NOT NULL f1, ALTER f1 type bigint;');
+
+# can use indexscan mechanism to fast add multiple not-null constraints
+$output = run_sql_command(
+	'ALTER TABLE t1 ALTER COLUMN f2 SET NOT NULL, ALTER COLUMN f1 SET NOT NULL;'
+);
+ok( $output =~
+	  m/all new not-null constraints on relation "t1" have been validated by using index scan/,
+	'all not-null constraints are validated by indexscan');
+
+# using indexscan mechanism to fast add a not-null can only apply to key columns, not include column
+$output = run_sql_command(
+	'ALTER TABLE t1 ADD CONSTRAINT nnf4 NOT NULL f4;'
+);
+ok(!is_indexscan_veritify_notnull($output), 'can not use indexscan to validate not-null constraint on t1');
+
+# if index is not btree index then cannot use indexscan mechanism to fast add not-null constraint
+$output = run_sql_command(
+	'ALTER TABLE t1 ADD CONSTRAINT nn_f5 NOT NULL f5;'
+);
+ok(!is_indexscan_veritify_notnull($output), 'can not use indexscan to validate not-null constraints on t1');
+
+$node->stop('fast');
+
+done_testing();
-- 
2.34.1