Self-JOIN with occurrence count
Two major improvements:

SELECT *
FROM   certificates c
WHERE  c.expires_on &lt;= current_date + 30  -- sargable!
AND    NOT EXISTS (
   SELECT 1
   FROM   certificates
   WHERE  common_name = c.common_name
   AND    expires_on  > c.expires_on
   AND    state = 'issued'
   );


Make the first predicate sargable, so that an index can be used.
You second condition is that no qualifying row exists. So don't count, that would be expensive because Postgres has to scan all rows unconditionally. Use a NOT EXISTS anti-semi-join. Postgres can use an index again to quickly verify non-existence and can stop looking further as soon as the first qualifying row has been found. Typically much faster (depending on data distribution). There are several related techniques possible for this:


Select rows which are not present in other table



Ideally, you have at least two indexes:


on (expires_on):

CREATE INDEX ON certificates (expires_on);

A partial multicolumn index.

CREATE INDEX foo ON certificates (common_name, expires_on DESC)
WHERE  state = 'issued';



If state = 'issued' is true for most rows, then adding the condition to the index won't help.

Answer to additional question in comment

If the number of days for tolerance is variable and stored as integer with each row, use a functional index:

CREATE INDEX ON certificates ((expires_on + expiring_days));


And adapt the query accordingly:

SELECT *
FROM   certificates c
WHERE  expires_on + expiring_days &lt;= current_date  -- can use index
AND    NOT EXISTS (
   SELECT 1
   FROM   certificates
   WHERE  common_name = c.common_name
   AND    expires_on  &gt; c.expires_on
   AND    state = 'issued'
   );




Aside: A column like state typically only allows a couple of distinct values. If so, it's a candidate for normalization: add a table certificate_state listing allowed values and use state_id int REFERENCES state in the main table. Just like outlined here:


Low cardinality fields: integer or string