I did an analyize and tried to delete 50 rows from the 1.5M table and it took over 120 seconds. Deleting 100 rows took nearly twice as long. An explain of the delete query showed that indexes were being used. I found that changing the variable enable_seqscan = off and restarting the database, deleting 50 rows took less then two seconds. 500 rows was quick as well. The explain output does not indicate how the foreign keys are processed. Do I just have to set the varible locally on the connection? Is this what is expected? BackGround: Postgresql 8.2.4 184 tables in schema of interest. table of interest has about 1.5M rows. This table references 30 other tables via foreign keys. All foreign keys are "on update restrict on delete restrict", except 2 are "on update restrict on delete set null. (No cascading deletes) Two other tables reference this table. btree indexes exist on the foreign key and also the referenced table's referenced field (primary key). I verified all of these foreign key / referenced field use the same datatype.