Re: BUG #3519: Postgres takes the wrong query plan resulting in performance issues

The following bug has been logged online:

Bug reference: 3519
Logged by: Mouhamadou DIA
Email address: mdia(at)accovia(dot)com
PostgreSQL version: 8.2.4
Operating system: Solaris 10 and Linux Redhat 4
Description: Postgres takes the wrong query plan resulting in
performance issues
Details:

Hello,

I have a Postgres instance (version 8.1.19) running on a Solaris 10 machine.
When I run the following query

SELECT * FROM PROR_ORG, ( ( ( ( (PRPT_PRT LEFT OUTER JOIN PRPT_PRTADR ON
PRPT_PRT.PRT_NRI = PRPT_PRTADR.PRT_NRI AND PRPT_PRTADR.ADR_F_DEF=true)

LEFT OUTER JOIN PLGE_CTY ON PRPT_PRTADR.CTY_NRI = PLGE_CTY.CTY_NRI) LEFT

OUTER JOIN PLGE_CTY1 PLGE_CTY_PLGE_CTY1 ON PLGE_CTY.CTY_NRI =

PLGE_CTY_PLGE_CTY1.CTY_NRI AND PLGE_CTY_PLGE_CTY1.LNG_CD = 'fr') LEFT

OUTER JOIN PLGE_CTRSD ON PRPT_PRTADR.CTRSD_CD = PLGE_CTRSD.CTRSD_CD

AND PRPT_PRTADR.CTR_ISO_CD = PLGE_CTRSD.CTR_ISO_CD) LEFT OUTER JOIN

PLGE_CTR ON PRPT_PRTADR.CTR_ISO_CD = PLGE_CTR.CTR_ISO_CD) , PROR_ORG1

PROR_ORG_PROR_ORG1, PROR_ORGT, PROR_ORGT1 PROR_ORGT_PROR_ORGT1

WHERE ( (PROR_ORG.ORGT_CD = PROR_ORGT.ORGT_CD) AND

(PROR_ORGT.ORGT_CD = PROR_ORGT_PROR_ORGT1.ORGT_CD AND

PROR_ORGT_PROR_ORGT1.LNG_CD = 'fr') AND (PROR_ORG.PRT_NRI =

PROR_ORG_PROR_ORG1.PRT_NRI AND PROR_ORG_PROR_ORG1.LNG_CD = 'fr') AND

(PROR_ORG.PRT_NRI = PRPT_PRT.PRT_NRI) ) AND ( ((PROR_ORG.ORGT_CD ='CHAIN'))
)

it takes 45 seconds to run. In this case the optimizer does a sequential
scan of the PRPT_PRT table (which is the largest one) despite the existence
of an index on PRT_NRI column of PRPT_PRT table.

Ive activated the GEQO but it still takes nearly the same time to run
(between 40 and 45s).

When I change the order of PRPT_PRT and PROR_ORG tables, it takes only 30
milliseconds to run. In this case the optimizer uses the index on PRT_NRI
column of PRPT_PRT table, what is normal and what I was expecting.

Is there a known problem with the Postgres optimizer?

For your information, the same query takes 20 milliseconds to run on
Informix and 60 milliseconds to run on Oracle independently of the order of
the tables in the query.

PRPT_PRT has 1.3 millions rows

PRPT_PRTADR has 300.000 rows

PROR_ORG has 1500 rows

These are the largest tables, all the others are small tables. All
statistics are up to date.

I read from the release notes that starting from Postgres 8.2 the optimizer
supports reordering outer joins.
I've migrated to Postgres 8.2.4 and run the same query. It takes now 20
seconds which is still not acceptable.

PS: I did the same test using Redhat Linux 4 and I have similar times
Please help

Thanks

Mouhamadou DIA wrote:
> I've migrated to Postgres 8.2.4 and run the same query. It takes now 20
> seconds which is still not acceptable.

To help you with that, we'd need to see the EXPLAIN ANALYZE output of
the query, and the CREATE TABLE statements of the tables involved in the
query and their indexes.

Have you vacuumed and ANALYZEd your database recently?

PS. This is not a bug. Please don't use the bug reporting form for
classic performance issues.

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com

I'm sending in attachment the output of the explain analyze command and the create table statements of tables involved in the query.
Yes, I have vacuumed and analyzed my database this morning before running the query.

I'm sorry; I thought it was a bug with the optimizer, that's why I used the reporting bug

Thanks for your help

-----Message d'origine-----
De : Heikki Linnakangas [mailto:hlinnaka(at)gmail(dot)com] De la part de Heikki Linnakangas
Envoyé : 6 août 2007 14:32
À : Mouhamadou Dia
Cc : pgsql-bugs(at)postgresql(dot)org
Objet : Re: [BUGS] BUG #3519: Postgres takes the wrong query plan resulting in performance issues

Mouhamadou DIA wrote:
> I've migrated to Postgres 8.2.4 and run the same query. It takes now 20
> seconds which is still not acceptable.

To help you with that, we'd need to see the EXPLAIN ANALYZE output of
the query, and the CREATE TABLE statements of the tables involved in the
query and their indexes.

Have you vacuumed and ANALYZEd your database recently?

PS. This is not a bug. Please don't use the bug reporting form for
classic performance issues.

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com

Mouhamadou Dia wrote:
> I'm sending in attachment the output of the explain analyze command and the create table statements of tables involved in the query.

Wait, you said that the query takes 20 seconds on 8.2, but the explain
analyze output says that it actually took 50 seconds. Is this the output
from 8.2.4?

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com

Sorry,
This output is coming from PG 8.1.19
I'm attaching the one that is coming from 8.2.4
Thanks and sorry for the confusion

-----Message d'origine-----
De : Heikki Linnakangas [mailto:hlinnaka(at)gmail(dot)com] De la part de Heikki Linnakangas
Envoyé : 6 août 2007 15:32
À : Mouhamadou Dia
Cc : pgsql-bugs(at)postgresql(dot)org
Objet : Re: RE : [BUGS] BUG #3519: Postgres takes the wrong query plan resulting in performance issues

Mouhamadou Dia wrote:
> I'm sending in attachment the output of the explain analyze command and the create table statements of tables involved in the query.

Wait, you said that the query takes 20 seconds on 8.2, but the explain
analyze output says that it actually took 50 seconds. Is this the output
from 8.2.4?

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com

Hmm. I don't see anything terribly wrong in the planner's estimates. The
only estimate that's off is the # of rows in pror_org matching the qual
orgt_cd = 'CHAIN', 27 estimated vs 1 actual. You could try increasing
the statistics target for that column to get that estimate right. That
might tip the planner to choose a plan with nested loop joins instead of
hash joins.

Have you played with enable_seqscan=off or enable_hashjoin=off? That's
not a good long term solution, but it would be interesting to see what
happens.

Mouhamadou Dia wrote:
> Sorry,
> This output is coming from PG 8.1.19
> I'm attaching the one that is coming from 8.2.4
> Thanks and sorry for the confusion
>
>
> -----Message d'origine-----
> De : Heikki Linnakangas [mailto:hlinnaka(at)gmail(dot)com] De la part de Heikki Linnakangas
> Envoyé : 6 août 2007 15:32
> À : Mouhamadou Dia
> Cc : pgsql-bugs(at)postgresql(dot)org
> Objet : Re: RE : [BUGS] BUG #3519: Postgres takes the wrong query plan resulting in performance issues
>
> Mouhamadou Dia wrote:
>> I'm sending in attachment the output of the explain analyze command and the create table statements of tables involved in the query.
>
> Wait, you said that the query takes 20 seconds on 8.2, but the explain
> analyze output says that it actually took 50 seconds. Is this the output
> from 8.2.4?
>

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com

"Heikki Linnakangas" <heikki(at)enterprisedb(dot)com> writes:

> Have you played with enable_seqscan=off or enable_hashjoin=off? That's
> not a good long term solution, but it would be interesting to see what
> happens.

I think this is a case where Postgres just doesn't know it can re-order near
an outer join. Outer joins often can't be re-ordered and Postgres isn't a
general theorem prover, it can't always figure out whether it's safe to
re-order them.

The structure of your query is a whole series of left outer joins, the result
of which is then (inner) joined with one more table. The outer joins return a
whole lot of records but the inner join is only going to match a few of them.

The only hope you have of a reasonable plan here is if Postgres can figure out
that it can do the inner join first so that it only has to perform the outer
join on the resulting records.

I think it could actually re-order the inner query to happen first in this
case. But I'm not certain, it's tricky to tell. But the fact that Oracle finds
a way to execute it quickly gives me some confidence that it ought to be
possible since I think Oracle does get join orderings reasonably right. I'm
not so sure about Informix.

--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com

Gregory Stark <stark(at)enterprisedb(dot)com> writes:
> The structure of your query is a whole series of left outer joins, the result
> of which is then (inner) joined with one more table. The outer joins return a
> whole lot of records but the inner join is only going to match a few of them.

Hmmm ... actually I see 6 tables inside the join-tree and four more
loose in the FROM-clause, ten relations altogether. Which means the OP
is falling foul of from_collapse_limit, and it's not investigating every
possible join order. Try setting from_collapse_limit to more than 10.

regards, tom lane

"Tom Lane" <tgl(at)sss(dot)pgh(dot)pa(dot)us> writes:

> Gregory Stark <stark(at)enterprisedb(dot)com> writes:
>> The structure of your query is a whole series of left outer joins, the result
>> of which is then (inner) joined with one more table. The outer joins return a
>> whole lot of records but the inner join is only going to match a few of them.
>
> Hmmm ... actually I see 6 tables inside the join-tree and four more
> loose in the FROM-clause, ten relations altogether. Which means the OP
> is falling foul of from_collapse_limit, and it's not investigating every
> possible join order. Try setting from_collapse_limit to more than 10.

The three other loose ones are attached to a table inside outer joins though.
Doesn't that prevent any possibility of them being done earlier? But the first
one looks like it ought to be driving the join.

--
Gregory Stark
EnterpriseDB http://www.enterprisedb.com

I've played with both parameters but it doesn't help in this case
Thanks

-----Message d'origine-----
De : Heikki Linnakangas [mailto:hlinnaka(at)gmail(dot)com] De la part de Heikki Linnakangas
Envoyé : 6 août 2007 16:58
À : Mouhamadou Dia
Cc : pgsql-bugs(at)postgresql(dot)org
Objet : Re: RE : RE : [BUGS] BUG #3519: Postgres takes the wrong query plan resulting in performance issues

Hmm. I don't see anything terribly wrong in the planner's estimates. The
only estimate that's off is the # of rows in pror_org matching the qual
orgt_cd = 'CHAIN', 27 estimated vs 1 actual. You could try increasing
the statistics target for that column to get that estimate right. That
might tip the planner to choose a plan with nested loop joins instead of
hash joins.

Have you played with enable_seqscan=off or enable_hashjoin=off? That's
not a good long term solution, but it would be interesting to see what
happens.

Mouhamadou Dia wrote:
> Sorry,
> This output is coming from PG 8.1.19
> I'm attaching the one that is coming from 8.2.4
> Thanks and sorry for the confusion
>
>
> -----Message d'origine-----
> De : Heikki Linnakangas [mailto:hlinnaka(at)gmail(dot)com] De la part de Heikki Linnakangas
> Envoyé : 6 août 2007 15:32
> À : Mouhamadou Dia
> Cc : pgsql-bugs(at)postgresql(dot)org
> Objet : Re: RE : [BUGS] BUG #3519: Postgres takes the wrong query plan resulting in performance issues
>
> Mouhamadou Dia wrote:
>> I'm sending in attachment the output of the explain analyze command and the create table statements of tables involved in the query.
>
> Wait, you said that the query takes 20 seconds on 8.2, but the explain
> analyze output says that it actually took 50 seconds. Is this the output
> from 8.2.4?
>

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com

Thanks Tom,
By setting from_collapse_limit to more than 10, the query takes 133ms instead of 20s.
My question is: why even if from_collapse_limit is set to 8 (it's default value), the same query takes 30ms just by changing the order of PRPT_PRT and PROR_ORG tables in the query?

-----Message d'origine-----
De : Tom Lane [mailto:tgl(at)sss(dot)pgh(dot)pa(dot)us]
Envoyé : 6 août 2007 21:31
À : Gregory Stark
Cc : Heikki Linnakangas; Mouhamadou Dia; pgsql-bugs(at)postgresql(dot)org
Objet : Re: RE : RE : [BUGS] BUG #3519: Postgres takes the wrong query plan resulting in performance issues

Gregory Stark <stark(at)enterprisedb(dot)com> writes:
> The structure of your query is a whole series of left outer joins, the result
> of which is then (inner) joined with one more table. The outer joins return a
> whole lot of records but the inner join is only going to match a few of them.

Hmmm ... actually I see 6 tables inside the join-tree and four more
loose in the FROM-clause, ten relations altogether. Which means the OP
is falling foul of from_collapse_limit, and it's not investigating every
possible join order. Try setting from_collapse_limit to more than 10.

regards, tom lane