Planning performance problem (67626.278ms)

[Krzysztof Plocharz <plocharz@xxxxxxxxxxxxxx>]

Hi

We have some very strange query planning problem. Long story short it 
takes 67626.278ms just to plan. Query execution takes 12ms.

Query has 7 joins and 2 subselects.
It looks like the issue is not deterministic, sometimes is takes few ms 
to plan the query.

One of the tables has 550,485,942 live tuples and 743,504,012 dead 
tuples. Running ANALYZE on that tables solves the problem only temporarily.

Question is how can we debug what is going on?

Best Regards,
Krzysztof Płocharz