Adding a check constraint on a new column with default value on a large table
It doesn't seem to be that smart, no, from my trying it in psql with \timing on. Increasing the size of the table causes ALTER TABLE to get slower, and it seems linear, so I assume it's still doing a scan. You can verify this pretty easily interactively:
testdb=# \timing on
Timing is on.
testdb=# create table target(a bigint);
CREATE TABLE
Time: 4.176 ms
testdb=# insert into target select x from generate_series(1, 15000000) x;
INSERT 0 15000000
Time: 8661.110 ms (00:08.661)
testdb=# begin; alter table target add column y bigint default 0 check(y&gt;=0); rollback;
BEGIN
Time: 0.128 ms
ALTER TABLE
Time: 1130.251 ms (00:01.130)
ROLLBACK
Time: 0.106 ms
testdb=# insert into target select x from generate_series(1, 15000000) x;
INSERT 0 15000000
Time: 8948.767 ms (00:08.949)
testdb=# begin; alter table target add column y bigint default 0 check(y&gt;=0); rollback;
BEGIN
Time: 0.139 ms
ALTER TABLE
Time: 1955.840 ms (00:01.956)
ROLLBACK
Time: 0.129 ms
testdb=# insert into target select x from generate_series(1, 15000000) x;
INSERT 0 15000000
Time: 8836.126 ms (00:08.836)
testdb=# begin; alter table target add column y bigint default 0 check(y&gt;=0); rollback;
BEGIN
Time: 0.114 ms
ALTER TABLE
Time: 2751.619 ms (00:02.752)
ROLLBACK
Time: 1.010 ms

I think your planned approach is fine.