MySQL cleverly maps

CREATE INDEX foo_bar ON Foo(Bar);

to

LOCK TABLE Foo WRITE;
CREATE TEMPORARY TABLE A-Foo ( .... INDEX foo_bar (Bar));
INSERT INTO A-Foo SELECT * FROM Foo;
ALTER TABLE Foo RENAME TO B-Foo;
ALTER TABLE A-Foo RENAME TO Foo;
DROP TABLE B-Foo;

If you have a very large table, expect this operation to take a) a lot of disk space, b) a very very long time and c) block any writes to the table in the process. I don't recommend adding indexes or altering any very large tables that are in production on MySQL, because you won't be in production for quite some time.

Update: Tom Haddon asked me if this applied to recent versions of MySQL or to PostgreSQL. Looking at the docs, it appears to still apply to 5.1:

• http://dev.mysql.com/doc/refman/5.1/en/create-index.html
• http://dev.mysql.com/doc/refman/5.1/en/alter-table.html

  In some cases, no temporary table is necessary:

  • If you use ALTER TABLE tbl_name RENAME TO new_tbl_name without any other options, MySQL simply renames any files that correspond to the table tbl_name. (You can also use the RENAME TABLE statement to rename tables. See Section 13.1.16, “RENAME TABLE Syntax”.)

  • ALTER TABLE ... ADD PARTITION creates no temporary table except for MySQL Cluster. ADD or DROP operations for RANGE or LIST partitions are immediate operations or nearly so. ADD or COALESCE operations for HASH or KEY partitions copy data between changed partitions; unless LINEAR HASH/KEY was used, this is much the same as creating a new table (although the operation is done partition by partition). REORGANIZE operations copy only changed partitions and do not touch unchanged ones.

  If other cases, MySQL creates a temporary table, even if the data wouldn't strictly need to be copied (such as when you change the name of a column).

• http://dev.mysql.com/doc/refman/5.1/en/alter-table-problems.html

As far as PostgreSQL is concerned, it doesn't mention anything about doing the same thing, but does mention that it does a full sequential scan of the table. During this time writes are blocked. You can use the CONCURRENTLY keyword to allow writes to happen, but it does two scans and will take longer, but you can still use your database.

http://www.postgresql.org/docs/8.2/interactive/sql-createindex.html