Thread: Analyzing bug 8049

I looked into the problem reported at
http://www.postgresql.org/message-id/E1UPa3B-0004K0-PJ@wrigleys.postgresql.org
which is that we're deriving a bogus plan for this query:

SELECT * FROM
( SELECT (COALESCE(h_n || '/', '') || l_n)::text AS fault FROM (SELECT _bug_header.h_n, _bug_line.l_nFROM _bug_lineLEFT
OUTERJOIN _bug_header on (_bug_line.h_n = _bug_header.h_n) ) AS tmp
 
) AS tmp2
WHERE (lower(fault) = '1')
ORDER BY lower(fault);

With use of a nestloop forced, we get this plan:
Nested Loop Left Join  (cost=0.16..513.11 rows=11 width=8)  ->  Seq Scan on _bug_line  (cost=0.00..31.40 rows=2140
width=8) ->  Index Only Scan using _bug_header_unique on _bug_header  (cost=0.16..0.21 rows=1 width=4)        Index
Cond:(h_n = _bug_line.h_n)        Filter: (lower((COALESCE(((h_n)::text || '/'::text), ''::text) ||
(_bug_line.l_n)::text))= '1'::text)
 

in which the problem is pretty obvious: the upper WHERE condition has been
pushed to the scan of _bug_header, at which level we get the wrong answers
from the COALESCE because the reference to _bug_header.h_n doesn't go to
NULL when it should do so because of the outer join.

Curiously, this doesn't happen without the ORDER BY.  (If you're wondering
why there's no sort step in this plan, it's because the planner figures
out that the equality constraint on lower(fault) renders the ORDER BY a
no-op.  But the damage has already been done by then.)

In HEAD, this happens because join_clause_is_movable_to() thinks it's safe
to move the join clause (lower(fault) = '1') to be evaluated inside the
nestloop.  Now, that function is perfectly aware of this type of hazard,
so it's faithfully checking the clause's nullable_relids to make sure it
doesn't push a clause from above an outer join into the RHS of the join.
However, it's seeing NULL as the value of the clause's nullable_relids.
Ooops.  And the reason for that is that what it's seeing isn't actually
the original WHERE clause, but a reconstructed version that's been
regurgitated by the EquivalenceClass machinery.  And that machinery is
failing to stamp the constructed clause with the right nullable_relids.
I thought I'd fixed that type of problem last fall, in commit
72a4231f0c80f213a4fa75356dc3c6b7c7419059, which added code to attempt
to compute those relid sets at need.  But there was an oversight in
that patch: get_eclass_for_sort_expr() always sets nullable_relids to
NULL in any new equivalence-class members that it creates to represent
sort keys.  In this example, it's obviously bogus for the ORDER BY
key "lower(fault)" to be considered as having no nullable_relids, because
it's above an outer join that can null _bug_header.h_n.  This explains
why the ORDER BY clause is needed for the bug to manifest --- if the
equivalence-class member for "lower(fault)" is created as a result of
processing the WHERE clause, then it's all good because the member is
created with the right em_nullable_relids.

So, okay, we need to fix get_eclass_for_sort_expr() to compute valid
nullable_relids for any sort clauses it's processing.  This is a bit
problematic because the information isn't readily available to it,
but we can certainly add some code to compute that.

However, reflecting on this example convinces me that there's a bigger
problem: the equivalence-class machinery assumes that textually equivalent
expressions (more formally, equal() expression trees) mean the same
thing.  They don't necessarily.  In this example, _bug_header.h_n means
something different below the outer join than it does above it.  We have
hacked around that problem in the past via various ad-hoc rules involving
not treating equality constraints as true equivalences if they were
affected by outer joins.  But that approach was always pretty squishy,
and I've wished for some more principled way to define the rules.
I now think I see one: to consider two expressions equivalent, we ought
to consider not only textual equality, but whether they are subject to
the effects of the same outer joins, which we could represent as the
relevant nullable_relids sets.  So basically this would mean changing
equivclass.c to consider the identity of an EquivalenceMember as defined
by em_expr plus em_nullable_relids, not just em_expr.  Having done that
I think we could remove all the bizarre code about below_outer_join and
so forth, which is both of dubious correctness and an obstacle to
complete optimization of queries.

This idea needs more fleshing out, but it's seeming awfully attractive
right now.  The big problem with it is that it's going to be a more
invasive patch than I feel terribly comfortable about back-patching.
However, I'm not sure there's much choice, because I don't see any narrow
fix for 9.2 that would not result in very substantial degradation of its
optimization ability.  We can't just lobotomize equivalence-class
processing.

The plan I'm considering is to get this written and committed to HEAD
in the next week, so that it can go out in 9.3beta1.  After the patch
has survived a reasonable amount of beta testing, I'd be more comfortable
about back-patching into 9.2.

BTW, I am also suspicious that there are related examples that fail
pre-9.2, though I don't have one yet.  I previously back-patched
72a4231f0c80f213a4fa75356dc3c6b7c7419059 into all the older branches,
so I am wondering if we might need to back-patch this rewrite further
than 9.2 as well.

Comments?
        regards, tom lane

On Thu, Apr 11, 2013 at 1:25 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> This idea needs more fleshing out, but it's seeming awfully attractive
> right now.  The big problem with it is that it's going to be a more
> invasive patch than I feel terribly comfortable about back-patching.
> However, I'm not sure there's much choice, because I don't see any narrow
> fix for 9.2 that would not result in very substantial degradation of its
> optimization ability.  We can't just lobotomize equivalence-class
> processing.
>
> The plan I'm considering is to get this written and committed to HEAD
> in the next week, so that it can go out in 9.3beta1.  After the patch
> has survived a reasonable amount of beta testing, I'd be more comfortable
> about back-patching into 9.2.

I'm not very sanguine about the chances that back-patching this won't
provoke any screams of agony ... but I don't have a better idea,
either.  Letting queries return wrong answers isn't a superior
solution, for sure.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

Robert Haas <robertmhaas@gmail.com> writes:
> On Thu, Apr 11, 2013 at 1:25 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
>> The plan I'm considering is to get this written and committed to HEAD
>> in the next week, so that it can go out in 9.3beta1.  After the patch
>> has survived a reasonable amount of beta testing, I'd be more comfortable
>> about back-patching into 9.2.

> I'm not very sanguine about the chances that back-patching this won't
> provoke any screams of agony ... but I don't have a better idea,
> either.  Letting queries return wrong answers isn't a superior
> solution, for sure.

The only alternative I can see is to make a back-patch that just teaches
get_eclass_for_sort_expr() to compute valid nullable_relids for the sort
expression.  That's necessary code in any case, and it would fix the
immediately complained-of bug.  The thing that scares me is that it is
now clear that equivclass.c is capable of considering two expressions to
be equivalent when they should not be; that is, I'm afraid there are
variants of the problem that would not be cured by such a limited
back-patch.  But maybe I should try to create such an example before
proposing the more invasive approach.
        regards, tom lane

Em Sex, 2013-04-12 às 10:58 -0400, Tom Lane escreveu:
> Robert Haas <robertmhaas@gmail.com> writes:
> > On Thu, Apr 11, 2013 at 1:25 PM, Tom Lane <tgl@sss.pgh.pa.us> wrote:
> >> The plan I'm considering is to get this written and committed to HEAD
> >> in the next week, so that it can go out in 9.3beta1.  After the patch
> >> has survived a reasonable amount of beta testing, I'd be more comfortable
> >> about back-patching into 9.2.
>
> > I'm not very sanguine about the chances that back-patching this won't
> > provoke any screams of agony ... but I don't have a better idea,
> > either.  Letting queries return wrong answers isn't a superior
> > solution, for sure.
>
> The only alternative I can see is to make a back-patch that just teaches
> get_eclass_for_sort_expr() to compute valid nullable_relids for the sort
> expression.


In my tests, after ANALYZE _bug_header and _bug_line, the query plan
changes and query results returns as expected. Is this a chance that
things isn't too bad?


[]s
--
Dickson S. Guedes
mail/xmpp: guedes@guedesoft.net - skype: guediz
http://guedesoft.net - http://www.postgresql.org.br
http://www.rnp.br/keyserver/pks/lookup?search=0x8F3E3C06D428D10A

"Dickson S. Guedes" <listas@guedesoft.net> writes:
> In my tests, after ANALYZE _bug_header and _bug_line, the query plan
> changes and query results returns as expected. Is this a chance that
> things isn't too bad?

No, it just means that in this particular scenario, the bug only
manifests if a nestloop plan is chosen --- without that, there's no
possibility of pushing a join clause down to the scan level anyway.
        regards, tom lane

I wrote:
> The only alternative I can see is to make a back-patch that just teaches
> get_eclass_for_sort_expr() to compute valid nullable_relids for the sort
> expression.  That's necessary code in any case, and it would fix the
> immediately complained-of bug.  The thing that scares me is that it is
> now clear that equivclass.c is capable of considering two expressions to
> be equivalent when they should not be; that is, I'm afraid there are
> variants of the problem that would not be cured by such a limited
> back-patch.  But maybe I should try to create such an example before
> proposing the more invasive approach.

In thinking about how to compute valid nullable_relids in
get_eclass_for_sort_expr, I realized that it is impractical to do it
in the current code structure, because computing nullable_relids
requires that the joininfo list has been built by deconstruct_jointree,
which hasn't been run yet at the time grouping_planner computes the
pathkeys for the ORDER BY and related clauses.  So I concluded that
we need to postpone computation of those pathkeys lists until after
deconstruct_jointree.

Working through this, I realized that we could, in fact, simply delay
computation of all five of group_pathkeys, window_pathkeys,
distinct_pathkeys, sort_pathkeys, and query_pathkeys until the point
where we currently do canonicalize_all_pathkeys.  There isn't anything
that looks at those lists in-between.  The only reason they're set up by
grouping_planner is separation of concerns --- query_planner doesn't
really have any business dealing with group_pathkeys for instance.
Furthermore, if we delay computation of those lists, then we can get rid
of the notion of non-canonical pathkeys altogether: there is noplace
that needs to generate a PathKey at all before this point.  So that
results in a nice conceptual simplification as well as saving a few
cycles.

Once I'd finished moving the pathkeys calculations, I was a tad
surprised to discover that bug 8049 was gone!  The reason for this is
that now, if an ORDER BY item matches some expression that has another
reason to be in an EquivalenceClass, the ORDER BY item will get matched
to a pre-existing EC item and so there will be no opportunity for
get_eclass_for_sort_expr() to do the wrong thing.  If an ORDER BY item
doesn't match anything, then it will be created as a new single-item
EquivalenceClass, containing arguably-incorrect NULL em_nullable_relids,
but there is nothing that will notice that.

I remain suspicious that there are or will someday be cases where we
actually need to generate valid em_nullable_relids for an ORDER BY item,
but in the absence of a demonstrated bug it doesn't seem real prudent to
add a bunch of new code here, either in 9.2 or 9.3.  Therefore, I think
what we ought to do is apply something like the attached patch to 9.2
and 9.3 and call it a day for now.

The difficulty with back-patching this patch is that it involves API
changes for query_planner() and make_pathkeys_for_sortclauses(), as well
as outright removal of canonicalize_pathkeys().  So there's a risk of
breaking third-party code that calls any of those functions.  I don't
have the slightest hesitation about changing these APIs in 9.3, but
back-patching them into 9.2 is a bit more nervous-making.

It would be trivial to make make_pathkeys_for_sortclauses() ignore
its "canonicalize" parameter in 9.2, or maybe better add an Assert
(not a runtime test) that the parameter is "true".  And we could
turn canonicalize_pathkeys() into a no-op function in 9.2.  However,
I'm not seeing a better alternative to adding the callback parameter
to query_planner().  The difficulty is that in order to compute those
pathkey lists, we need access to the "tlist" and "activeWindows" values,
which heretofore have just been local in grouping_planner().  We could
add fields to PlannerInfo to carry them, and then grouping_planner()
could just call some new function in planner.c rather than needing an
explicit callback argument.  But new fields in PlannerInfo are an ABI
break that in my judgment would be more risky in 9.2 than changing
query_planner()'s signature --- I think it's somewhat unlikely that
any plug-ins are calling query_planner() directly.

Thoughts?  Anybody know of a counterexample to the idea that no plug-ins
call query_planner()?

            regards, tom lane

On 4/28/13 7:00 PM, Tom Lane wrote:
> Thoughts?  Anybody know of a counterexample to the idea that no plug-ins
> call query_planner()?

I would assume that anyone writing anything that calls such a low-level function reads -hackers regularly and would
easilybe able to handle whatever changes to their code that the new callback parameter required. We would obviously
wantto send notice about this ahead-of-time in addition to sticking something in the release notes.
 

That said, I'd be rather surprised if anything actually calls planner functions directly.
-- 
Jim C. Nasby, Data Architect                       jim@nasby.net
512.569.9461 (cell)                         http://jim.nasby.net