How are you doing this restore? Is it from a dump? Are you using or could you use custom format?
At [1] there are some tips to help.
2. Without indexes, retrieving from table is fast?
After creating an index on that table, then the retrieval become slow.
That is odd. Perhaps your indexes are bloat or you don't have proper statics on your tables?! Please, give us the EXPLAIN ANALYZE of the queries with and without the indexes (you could use [2]), and run ANALYZE on the table before it.