What happens at low level when I add a column to a table in PostgreSQL? I have a table with number of rows in the order of billions. Let's say I want to add a column to that table. I would like to know what happens behind the scene to know the cost, expected time of this query.

Doesn't relational databases store row data pointers together so it will have to lookup each row to add a pointer of the added column to the end of that row block on disk? This is my current understanding.
In Postgres nothing really happens. 

It just adds a row to the system catalogs so that it knows that you added a column. It doesn't even touch the table data. So even on a table with a billion rows this would only take a few milliseconds once it could obtain the exclusive lock on the table. 

Starting with Postgres 11, this even is the case when adding a NOT NULL column with a constant as the default value, e.g. add some_flag integer not null default 42

If the default value is a volatile function (e.g. current_timestamp), Postgres is forced to call this once for each row and put in the result of that. Then this would take a substantial amount of time to add the column with billions of rows.