> First you add a not null check NOT VALIDATED - Then you add a not null constraint (it will require a full table scan, but with minimal locking) - Afterwards you can remove the unnecessary not null check

This is still quite long and complicated. What stops Postgres from automatically tracking whether a column has any nulls on each insert?