Ordinarily this is checked during the ALTER TABLE by scanning the entire table; however, if a valid CHECK constraint is found which proves no NULL can exist, then the table scan is skipped.

Before 12 for huge tables to avoid long table lock I use next approach instead of SET NOT NULL:

ALTER TABLE tbl ADD CONSTRAINT cnstr CHECK (col IS NOT NULL) NOT VALID;

ALTER TABLE tbl VALIDATE CONSTRAINT cnstr;

With 12 you can extend this approach:

ALTER TABLE tbl ALTER COLUMN col SET NOT NULL;

ALTER TABLE tbl DROP CONSTRAINT cnstr;

But you can have similar approach for previous postgres too:

Postgres has ATExecSetNotNull function for SET NOT NULL that set attnotnull to true in pg_attribute and ATRewriteTable that check all values in column is not null. There are call tree and code:

AlterTable

  ATController

    ATRewriteCatalogs

      ATExecCmd

        ATExecSetNotNull

          ((Form_pg_attribute) GETSTRUCT(tuple))->attnotnull = true;

    ATRewriteTables

      ATRewriteTable

        ereport(ERROR, (errcode(ERRCODE_NOT_NULL_VIOLATION),

UPDATE pg_attribute SET attnotnull = TRUE WHERE attrelid = 'tbl'::regclass::oid AND attname = 'col';

Unfortunately this approach require superuser permissions for pg_catalog changes.

Why it important?

I will use django as example, it has migrations that can down you application for huge table and SET NOT NULL is one of them. So to avoid negative experience for 24x7 working application you probably want to avoid negative consequences with migrations.

I have django extension https://github.com/tbicr/django-pg-zero-downtime-migrations that provide same state as standard django, but use different tricks like described above to apply migrations more safe way and described tricks available now.