Why PG uses nested-loop join when no indexes are available?

David Grelaud <dgrelaud@ideolys.com> writes:

Statistics are not propagated when Common Table Expressions (CTE) are used.
The cardinality of a CTE is equal to 1 most of the time

Really?

The rest of this seems to be proceeding from completely false assumptions.

regards, tom lane

--
Sent via pgsql-general mailing list (pgsql-general@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-general

Thank you for your fast response!

I'm sorry, my vocabulary may be not correct and my "french approach" to
explain my problem is not efficient ;).

But the underestimation problem in complex queries is still there? ... and
generates potential "dangerous" plans (nested loop).

We thought at the beginning we were alone but it seems to be a problem of
most database systems.
What do you think about the paragraph 4.1 of this paper
http://www.vldb.org/pvldb/vol9/p204-leis.pdf ?

Regards,
-------------------
David Grelaud,
Ideolys.

2016-01-13 16:02 GMT+01:00 Tom Lane <tgl@sss.pgh.pa.us>:

On 14 January 2016 at 03:48, David Grelaud <dgrelaud@ideolys.com> wrote:

3) Always avoid nested-loop join when no indexes are available?

Tom Lane said "There might be some cases where this would help, but there
would be many more where it would be useless or counterproductive."
Who is right between Tom Lane and the Leis Viktor's paper above?

We tried to disable nested_loop all the time in a production environment
and we observed an overall improvement in all queries where Indexes are not
useful or not available (CTEs), which confirms the paper.
In fact, one of our production environment is still running with
"nested_loop off" because benefits are a lot greater than drawbacks as long
as some tables are relatively small (Indexes not used).

I don't really think any of them are wrong. Simply Tom is talking in
general terms for no specific workload, and the paper is dealing with one
specific workload. Of course there are cases when a non-parameterised
nested loop are the fastest way, I mean what could possibility be faster if
there's only 1 row to be joined, for example. It's just that it's not that
much faster since such a join is likely to perform very quickly no matter
which join algorithm is used.

On the other hand, if your tables are not tiny, or you're never just
joining to just a few rows, and you are suffering from stats
underestimations, then it's quite probable that you'll improve your
workload overall by doing enable_nestloop = off. But you have to remember
that if you do this, then you miss out on parameterised inner scans on
nested loops. Quite often these are the fastest option, even when the
number of rows is fairly large, as it might save building a hash table on a
very large relation, or having to sort that relation for a merge join.

Perhaps separating out enable_nestloop so that it only disables
non-parameterised nested loops, and add another GUC for parameterised
nested loops would be a good thing to do. Likely setting enable_nestloop to
off in production would be a slightly easier decision to make, if that was
the case.

It looks pretty simple to do this, so I hacked it up, and attached it here.
There's no doc changes and I'm not that interested in fighting for this
change, it's more just an idea for consideration.

--
David Rowley http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services

David Rowley <david.rowley@2ndquadrant.com> writes:

Perhaps separating out enable_nestloop so that it only disables
non-parameterised nested loops, and add another GUC for parameterised
nested loops would be a good thing to do. Likely setting enable_nestloop to
off in production would be a slightly easier decision to make, if that was
the case.
It looks pretty simple to do this, so I hacked it up, and attached it here.
There's no doc changes and I'm not that interested in fighting for this
change, it's more just an idea for consideration.

I'm not terribly excited by this idea either. If making such a change
actually makes things better for someone consistently, I'd argue that
the problem is a mistaken cost estimate elsewhere, and we'd be better off
to find and fix the real problem. (There have already been discussions
of only believing single-row rowcount estimates when they're provably
true, which might help if we can figure out how to do it cheaply enough.)

Having said that, if we did split enable_nestloop like this, what I think
you'd want to discriminate against is nestloops where the inner rel is
not parameterized *by the outer rel*. This test isn't doing that; it will
happily accept inner rels that are parameterized by some unrelated rel.

regards, tom lane

--
Sent via pgsql-general mailing list (pgsql-general@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-general

On 15 January 2016 at 04:00, Tom Lane <tgl@sss.pgh.pa.us> wrote:

David Rowley <david.rowley@2ndquadrant.com> writes:

Perhaps separating out enable_nestloop so that it only disables
non-parameterised nested loops, and add another GUC for parameterised
nested loops would be a good thing to do. Likely setting enable_nestloop

to

off in production would be a slightly easier decision to make, if that

was

the case.
It looks pretty simple to do this, so I hacked it up, and attached it

here.

There's no doc changes and I'm not that interested in fighting for this
change, it's more just an idea for consideration.

I'm not terribly excited by this idea either. If making such a change
actually makes things better for someone consistently, I'd argue that
the problem is a mistaken cost estimate elsewhere, and we'd be better off
to find and fix the real problem. (There have already been discussions
of only believing single-row rowcount estimates when they're provably
true, which might help if we can figure out how to do it cheaply enough.)

Actually, it's not very hard to hit a bad underestimate at all. All you
need is a join on two columns which are co-related. Since PostgreSQL
multiplies the estimated selectivities the row count is going to come out
too low. This also tricks the planner into thinking that this is a good
join to perform early, since (it thinks that) it does not produce many rows
at all. You only need 1 more join to occur after that to choose a nested
loop join mistakenly to hit the issue.

FWIW TPC-H Q9 has this exact trip hazard with the partsupp table, which is
the exact reason why this patch was born:
https://commitfest.postgresql.org/7/210/

I also think that the attitude that we can *always* fix the costs and
estimates is not the right one. The planner is never going to get it right
100% of the time. If we ever think we can build such a planner then someone
needs to come along and direct us back into the real world.

--
David Rowley http://www.2ndQuadrant.com/
<http://www.2ndquadrant.com/&gt;
PostgreSQL Development, 24x7 Support, Training & Services

Thank you both for your help.

We will test your patch but we need to understand a bit more the code in
order to follow your discussions.
Actually, your patch helps us to find where to start in the code ;).

The planner is never going to get it right 100% of the time.

Yes, I agree.
In production environnements, even if PostgreSQL chooses such a bad plan 1%
of the time, it is enough to make clients angry. My goal is to eradicate
this risk of choosing a nested loop in certain cases, which freezes
PostgreSQL during many minutes, whereas a hash-join or something else takes
only 2 seconds to complete. The performance difference is huge.
I mean, even if the plan is not the best one 100% of the time, it should at
least choose a "risk-free" plan, without these "bad" nested-loops. It is
maybe easier said than done but we want to try.

Regards,

*David Grelaud*

2016-01-15 2:16 GMT+01:00 David Rowley <david.rowley@2ndquadrant.com>: