NOT VALID, then VALIDATE

The expensive half is the scan

ADD CONSTRAINT … CHECK (…) does two things: it records the rule, and it proves every existing row obeys it. The first is a catalog write. The second is a full scan, and it happens under ACCESS EXCLUSIVE.

NOT VALID splits them. The rule applies to every new and updated row immediately; existing rows are simply not checked. The statement returns in milliseconds.

VALIDATE CONSTRAINT then does the scan — under SHARE UPDATE EXCLUSIVE, which conflicts with neither reads nor writes. Same total work, and none of it in anybody's way.

ALTER TABLE orders ADD CONSTRAINT total_positive CHECK (total >= 0) NOT VALID;
ALTER TABLE orders VALIDATE CONSTRAINT total_positive;

Foreign keys lock more than you asked for

Adding a foreign key from orders.customer_id to customers.id is a change to orders. That is not the whole story.

ALTER TABLE orders ADD CONSTRAINT orders_customer_fkey
  FOREIGN KEY (customer_id) REFERENCES customers (id);

A CHECK can buy you a NOT NULL

SET NOT NULL has no NOT VALID form. It scans the whole table under ACCESS EXCLUSIVE, and there is no keyword that changes that.

There is a way round it that is not a trick. Add CHECK (col IS NOT NULL) as NOT VALID, validate it under the weak lock, and then run SET NOT NULL. PostgreSQL sees a validated constraint that already proves the fact, trusts it, and skips the scan entirely. The final statement becomes a catalog update.

Once the column is NOT NULL the CHECK is redundant and can be dropped.

ALTER TABLE orders ALTER COLUMN note SET NOT NULL;

ALTER TABLE orders ADD CONSTRAINT note_set CHECK (note IS NOT NULL) NOT VALID;
ALTER TABLE orders VALIDATE CONSTRAINT note_set;
ALTER TABLE orders ALTER COLUMN note SET NOT NULL;
ALTER TABLE orders DROP CONSTRAINT note_set;

This is the shape of almost every safe migration: more statements, each of them cheap, instead of one that is correct and unshippable.