Optimize PostgreSQL read-only tables

Columns that are used for filtering or joining (or, to a lesser degree, sorting) are of interest for indexing. Columns that are just selected are barely relevant! For the following query only indexes on a and e may be useful:

SELECT a,b,c,d
FROM   tbl_a
WHERE  a = $some_value
AND    e < $other_value;

Here, f and possibly c are candidates, too:

SELECT a,b,c,d
FROM   tbl_a
JOIN   tbl_b USING (f)
WHERE  a = $some_value
AND    e < $other_value
ORDER  BY c;

After creating indexes, test to see if they are actually useful with EXPLAIN ANALYZE. Also compare execution times with and without the indexes. Deleting and recreating indexes is fast and easy. There are also parameters to experiment with EXPLAIN ANALYZE. The difference may be staggering or nonexistent.
As your tables are read only, index maintenance is cheap. It's merely a question of disk space.

If you really want to know what you are doing, start by reading the docs.

If you don't know what queries to expect ...

1. Try logging enough queries to find typical use cases. Log queries with the parameter log_statement = all for that. Or just log slow queries using log_min_duration_statement.

2. Create indexes that might be useful and check the statistics after some time to see what actually gets used. PostgreSQL has a whole infrastructure in place for monitoring statistics. One convenient way to study statistics (and many other tasks) is pgAdmin where you can chose your table / function / index and get all the data on the "statistics" tab in the object browser (main window).

3. Proceed as described above to see if indexes in use actually speed things up.

4. If the query planner should chose to use one or more of your indexes but to no or adverse effect then something is probably wrong with your setup and you need to study the basics of performance optimization: vacuum, analyze, cost parameters, memory usage, ...