BUG #14263: Query planner is slow to plan UPDATE on a table with many partitions

The following bug has been logged on the website:

Bug reference: 14263
Logged by: Linas Valiukas
Email address: shirshegsm(at)gmail(dot)com
PostgreSQL version: 9.3.13
Operating system: Ubuntu 12.04.5 LTS
Description:

Hi there,

We have a partitioned table, "bitly_clicks_total", with 600 partitions, up
to 1m rows in each sub-table. Property constraint_exclusion is
'partition'.

SELECTs on said table work as expected, but UPDATEs spend a lot of time on
query planner phase, even though executing the plan afterwards is very fast,
i.e. see https://paste.fedoraproject.org/393750/16797914/.

Here's a way to replicate the issue on an empty table with 600 partitions
too, so it doesn't depend on the number of rows in the partitioned table:
https://paste.fedoraproject.org/393751/91680241/

After some discussion on #postgresql @ Freenode (abridged version:
https://paste.fedoraproject.org/393752/16805914/) it seems that the query
planner has O(n^2) complexity for the number of partitions in a partitioned
table. Thus, I've been advised to split the table into less partitions, but
I found it unexpected that a sheer number of tables could slow down UPDATEs
like that, so I think that this behaviour could be at very least documented
accordingly.

Regards,

Linas