Re: Adding a non-null column without noticeable downtime

I think index should help.
Why don't you try it out and check the explain plan of it?
If you are planning to break it down as below:
1. ALTER TABLE "foo" ADD COLUMN "bar" boolean;
2. UPDATE foo SET bar = False; -- Done in batches
3. ALTER TABLE "foo" ALTER COLUMN "bar" SET DEFAULT False;
4. ALTER TABLE "foo" ALTER COLUMN "bar" SET NOT NULL;

I would suggest on interchanging operation 2 and 3 in sequence