BUG #7626: Query planner never returns, uses 100% CPU

The following bug has been logged on the website:

Bug reference: 7626
Logged by: Brian Dunavant
Email address: brian(at)omniti(dot)com
PostgreSQL version: 9.2.1
Operating system: MacOS + Others
Description:

Running this causes the thread to use 100% CPU and never returns (or at
least not for longer than my patience runs out).

This returns just fine on 8.4.1 and on 9.2beta.

CREATE TABLE foo (
id integer PRIMARY KEY
);

explain SELECT 1
FROM foo AS a
JOIN (SELECT 2 as aid) AS ag1 ON (ag1.aid=a.id)
JOIN (SELECT 3 as aid) AS ag2 ON (ag2.aid=a.id)
JOIN (SELECT 4 as aid) AS ag3 ON (ag3.aid=a.id)
JOIN (SELECT 5 as aid) AS ag4 ON (ag4.aid=a.id)
JOIN (SELECT 6 as aid) AS ag5 ON (ag5.aid=a.id)
JOIN (SELECT 7 as aid) AS ag6 ON (ag6.aid=a.id)
JOIN (SELECT 8 as aid) AS ag7 ON (ag7.aid=a.id)
JOIN (SELECT 9 as aid) AS ag8 ON (ag8.aid=a.id)
JOIN (SELECT 10 as aid) AS ag9 ON (ag9.aid=a.id)
JOIN (SELECT 11 as aid) AS ag10 ON (ag10.aid=a.id)
JOIN (SELECT 12 as aid) AS ag11 ON (ag11.aid=a.id)
JOIN (SELECT 13 as aid) AS ag12 ON (ag12.aid=a.id)
JOIN (SELECT 14 as aid) AS ag13 ON (ag13.aid=a.id)
JOIN (SELECT 15 as aid) AS ag14 ON (ag14.aid=a.id)
JOIN (SELECT 16 as aid) AS ag15 ON (ag15.aid=a.id)
JOIN (SELECT 17 as aid) AS ag16 ON (ag16.aid=a.id)
JOIN (SELECT 18 as aid) AS ag17 ON (ag17.aid=a.id)
JOIN (SELECT 19 as aid) AS ag18 ON (ag18.aid=a.id)
JOIN (SELECT 20 as aid) AS ag19 ON (ag19.aid=a.id)
JOIN (SELECT 21 as aid) AS ag20 ON (ag20.aid=a.id)
JOIN (SELECT 22 as aid) AS ag21 ON (ag21.aid=a.id)
JOIN (SELECT 23 as aid) AS ag22 ON (ag22.aid=a.id)
JOIN (SELECT 24 as aid) AS ag23 ON (ag23.aid=a.id)
JOIN (SELECT 25 as aid) AS ag24 ON (ag24.aid=a.id)
JOIN (SELECT 26 as aid) AS ag25 ON (ag25.aid=a.id)
JOIN (SELECT 27 as aid) AS ag26 ON (ag26.aid=a.id)
JOIN (SELECT 28 as aid) AS ag27 ON (ag27.aid=a.id)
JOIN (SELECT 29 as aid) AS ag28 ON (ag28.aid=a.id)
JOIN (SELECT 30 as aid) AS ag29 ON (ag29.aid=a.id)
JOIN (SELECT 1 as aid) AS ag30 ON (ag30.aid=a.id)
;

On 10/29/2012 12:29 PM, brian(at)omniti(dot)com wrote:
> The following bug has been logged on the website:
>
> Bug reference: 7626
> Logged by: Brian Dunavant
> Email address: brian(at)omniti(dot)com
> PostgreSQL version: 9.2.1
> Operating system: MacOS + Others
> Description:
>
> Running this causes the thread to use 100% CPU and never returns (or at
> least not for longer than my patience runs out).
>
> This returns just fine on 8.4.1 and on 9.2beta.

This response is not an effort to assist you, Brian, but just to make an observation for the developers that my bug post earlier this month has an uncanny resemblence to this post. My post involved real data but was basically a mutltiple rejoin of a couple of tables on differing values. The total number of joins was almost exactly what you have here. In my case it worked fine on 9.0 but would never return in 9.2.1. Due to the complexity of building a self-contained test case, I ended up reworking the query into something simpler using CTE's. My bug reference was... scratch that, it was only a posting to pgsql-admin on Oct. 12, entitled "query from 9.0 fails to return on 9.2".

>
> CREATE TABLE foo (
> id integer PRIMARY KEY
> );
>
> explain SELECT 1
> FROM foo AS a
> JOIN (SELECT 2 as aid) AS ag1 ON (ag1.aid=a.id)
> JOIN (SELECT 3 as aid) AS ag2 ON (ag2.aid=a.id)
> JOIN (SELECT 4 as aid) AS ag3 ON (ag3.aid=a.id)
> JOIN (SELECT 5 as aid) AS ag4 ON (ag4.aid=a.id)
> JOIN (SELECT 6 as aid) AS ag5 ON (ag5.aid=a.id)
> JOIN (SELECT 7 as aid) AS ag6 ON (ag6.aid=a.id)
> JOIN (SELECT 8 as aid) AS ag7 ON (ag7.aid=a.id)
> JOIN (SELECT 9 as aid) AS ag8 ON (ag8.aid=a.id)
> JOIN (SELECT 10 as aid) AS ag9 ON (ag9.aid=a.id)
> JOIN (SELECT 11 as aid) AS ag10 ON (ag10.aid=a.id)
> JOIN (SELECT 12 as aid) AS ag11 ON (ag11.aid=a.id)
> JOIN (SELECT 13 as aid) AS ag12 ON (ag12.aid=a.id)
> JOIN (SELECT 14 as aid) AS ag13 ON (ag13.aid=a.id)
> JOIN (SELECT 15 as aid) AS ag14 ON (ag14.aid=a.id)
> JOIN (SELECT 16 as aid) AS ag15 ON (ag15.aid=a.id)
> JOIN (SELECT 17 as aid) AS ag16 ON (ag16.aid=a.id)
> JOIN (SELECT 18 as aid) AS ag17 ON (ag17.aid=a.id)
> JOIN (SELECT 19 as aid) AS ag18 ON (ag18.aid=a.id)
> JOIN (SELECT 20 as aid) AS ag19 ON (ag19.aid=a.id)
> JOIN (SELECT 21 as aid) AS ag20 ON (ag20.aid=a.id)
> JOIN (SELECT 22 as aid) AS ag21 ON (ag21.aid=a.id)
> JOIN (SELECT 23 as aid) AS ag22 ON (ag22.aid=a.id)
> JOIN (SELECT 24 as aid) AS ag23 ON (ag23.aid=a.id)
> JOIN (SELECT 25 as aid) AS ag24 ON (ag24.aid=a.id)
> JOIN (SELECT 26 as aid) AS ag25 ON (ag25.aid=a.id)
> JOIN (SELECT 27 as aid) AS ag26 ON (ag26.aid=a.id)
> JOIN (SELECT 28 as aid) AS ag27 ON (ag27.aid=a.id)
> JOIN (SELECT 29 as aid) AS ag28 ON (ag28.aid=a.id)
> JOIN (SELECT 30 as aid) AS ag29 ON (ag29.aid=a.id)
> JOIN (SELECT 1 as aid) AS ag30 ON (ag30.aid=a.id)
> ;
>
>
>
>
>

brian(at)omniti(dot)com writes:
> Running this causes the thread to use 100% CPU and never returns (or at
> least not for longer than my patience runs out).
> This returns just fine on 8.4.1 and on 9.2beta.

Hmm ... seems to be a consequence of commit
3b8968f25232ad09001bf35ab4cc59f5a501193e. I wrote in that patch

+ * This looks expensive, but in practical cases there won't be very many
+ * distinct sets of outer rels to consider.

but evidently that was too optimistic :-(. Will need to think about
suitable heuristics for limiting the sets of outer relations we
consider building parameterized paths with.

regards, tom lane