Postgres: How is SET NOT NULL "more efficient" than CHECK constraint
My wild guess: "more efficient" means "less time is required to perform the check" (time advantage). It may also mean "less memory is required to perform the check" (space advantage). It might also mean "has less side effects" (such as not locking something or locking it for shorter periods of time)... but I don't have a way to know or check that "extra advantage".

I cannot think of an easy way to check for a possible space advantage (which, I guess, is not that important when memory nowadays is cheap). On the other hand, it's not that difficult to check for the possible time advantage: just create two tables which are the same, with the only exception of the constraint. Insert a sufficiently large number of rows, repeat a few times, and check the timings.

This is the table setup:

CREATE TABLE t1
(
   id serial PRIMARY KEY, 
   value integer NOT NULL
) ;

CREATE TABLE t2
(
  id serial PRIMARY KEY,
  value integer
) ;

ALTER TABLE t2
  ADD CONSTRAINT explicit_check_not_null
  CHECK (value IS NOT NULL);


This is an extra table, used for storing timings:

CREATE TABLE timings
(
   test_number integer, 
   table_tested integer /* 1 or 2 */, 
   start_time timestamp without time zone,
   end_time timestamp without time zone,
   PRIMARY KEY(test_number, table_tested)
) ;


And this is the test performed, using pgAdmin III, and the pgScript feature.

declare @trial_number;
set @trial_number = 0;

BEGIN TRANSACTION;
while @trial_number &lt;= 100
begin
    -- TEST FOR TABLE t1
    -- Insert start time
    INSERT INTO timings(test_number, table_tested, start_time) 
    VALUES (@trial_number, 1, clock_timestamp());

    -- Do the trial
    INSERT INTO t1(value) 
    SELECT 1.0
      FROM generate_series(1, 200000) ;

    -- Insert end time
    UPDATE timings 
       SET end_time=clock_timestamp() 
     WHERE test_number=@trial_number and table_tested = 1;

    -- TEST FOR TABLE t2
    -- Insert start time
    INSERT INTO timings(test_number, table_tested, start_time) 
    VALUES (@trial_number, 2, clock_timestamp());

        -- Do the trial
    INSERT INTO t2(value) 
    SELECT 1.0
    FROM generate_series(1, 200000) ;

    -- Insert end time
    UPDATE timings 
       SET end_time=clock_timestamp() 
     WHERE test_number=@trial_number and table_tested = 2;

    -- Increase loop counter
    set @trial_number = @trial_number + 1;
end 
COMMIT TRANSACTION;


The result is summarised in the following query:

SELECT
    table_tested, 
    sum(delta_time), 
    avg(delta_time), 
    min(delta_time), 
    max(delta_time), 
    stddev_pop(delta_time) 
FROM
    (
    SELECT
        table_tested, extract(epoch from (end_time - start_time)) AS delta_time
    FROM
        timings
    ) AS delta_times
GROUP BY
    table_tested 
ORDER BY
    table_tested ;


With the following results:

table_tested | sum     | min   | max   | avg   | stddev_pop
-------------+---------+-------+-------+-------+-----------
           1 | 176.740 | 1.592 | 2.280 | 1.767 | 0.08913
           2 | 177.548 | 1.593 | 2.289 | 1.775 | 0.09159


A graph of the values shows an important variability:



So, in practice, the CHECK(column IS NOT NULL) is very slightly slower (by a 0.5%). However, this small difference can be due to any random reason, provided that the variability of the timings is far larger than that. So, it's not statistically significant.

From a practical point of view, I would very much ignore the "more efficient" NOT NULL, because I don't really see it's significant; whereas I think that the absence of an AccessExclusiveLock is an advantage.