(Elaborating on @dezso's answer, which should be accepted as correct in preference to this one):
However, the table already has clustered index on pid.
No, it doesn't, because PostgreSQL (at least in 9.3 and below) does not have clustered indexes ("index-oriented tables" in the language of some other DB vendors). All tables in PostgreSQL are heaps with secondary indexes.
CLUSTER on an index to sort the heap according to the index, but it's a one-time thing. Pg doesn't attempt to maintain that ordering with subsequent updates/inserts, so it cannot rely on the table being in that order. See the docs:
"When a table is
CLUSTERed, it is physically reordered based on the index information. Clustering is a one-time operation: when the table is subsequently updated, the changes are not clustered. That is, no attempt is made to store new or updated rows according to their index order."
The closest thing Pg offers to index-only tables is support for index-only scans over secondary indexes in 9.2 and above. If there was an index on
(pid, did) and the visibility map was sufficiently solid (ie: not too high a churn rate, autovacuum running frequently enough) then Pg might choose to perform an index-only scan. It would fetch most of the data from the secondary index and only goes to the heap for a minority of rows where it needs to check visibility information.
So: Consider upgrading to 9.2 and creating an index on