Even if I close a connection and open a new one and execute the same query, the planning time is considerably less than the first time. Only when I restart the Postgres server then I face high planning time again.
Oh. I've not seen that before. But then again I don't often restart my server and then immediately run very large queries with a stringent time deadline.
You can try pg_prewarm, on pg_statistic table and its index. But I'd probably just put an entry in my db startup script to run this query immediately after startng the server, and let the query warm the cache itself.
Why do you restart your database often enough for this to be an issue?