Why are the initial queries up to minute slow on a 400M record PostgreSQL table? Consider the following query. The table consists of almost 400 million records and has appropriate indexes.
select
      r.id as id,
      r.text as body,
      r.answer as answer
from result r
where
  r.p_id = 12345 and
  r.dirty is null

p_id is the variable part of the query which selects the results of that poll. By querying a random p_id, the server takes as long as 60s to fetch results (~300K records). On consecutive calls with the same p_id, it replies almost instantly. I have validated those numbers with explain analyze, and they are both reported under Execution time (i.e. I'm not accounting for network transmission). It kind of makes sense, even though I don't know the internals of the database.
What I'm trying to improve is the initial time, but I'm not sure where to start. Can the query be further improved? Should I look into the configuration of the server? For the record, the machine seems idle with not a lot IOPS and load.
That are caching effects. The first time, data are read from disk, the other executions already find the data in RAM.
There are several options:

Have enough RAM in the machine to cache the whole table and the index. Then use pg_prewarm to load it into the cache before you begin.

Get faster storage.

Use a covering index (which may get large):
CREATE INDEX ON result (p_id) INCLUDE (id, text, answer) WHERE (dirty IS NULL);

See that the index is cached in RAM.