Re: sqlsmith crash incremental sort - Mailing list pgsql-hackers

On Wed, Apr 15, 2020 at 10:47 AM Tomas Vondra
<tomas.vondra@2ndquadrant.com> wrote:
>
> On Tue, Apr 14, 2020 at 01:16:33PM -0400, James Coleman wrote:
> >On Sun, Apr 12, 2020 at 8:09 PM Tomas Vondra
> ><tomas.vondra@2ndquadrant.com> wrote:
> >>
> >> On Sun, Apr 12, 2020 at 12:44:45AM +0200, Tomas Vondra wrote:
> >> >Hi,
> >> >
> >> >I've looked into this a bit, and at first I thought that maybe the
> >> >issue is in how cost_incremental_sort picks the EC members. It simply
> >> >does this:
> >> >
> >> >    EquivalenceMember *member = (EquivalenceMember *)
> >> >        linitial(key->pk_eclass->ec_members);
> >> >
> >> >so I was speculating that maybe there are multiple EC members and the
> >> >one we need is not the first one. That would have been easy to fix.
> >> >
> >> >But that doesn't seem to be the case - in this example the EC ony has a
> >> >single EC member anyway.
> >> >
> >> >    (gdb) p key->pk_eclass->ec_members
> >> >    $14 = (List *) 0x12eb958
> >> >    (gdb) p *key->pk_eclass->ec_members
> >> >    $15 = {type = T_List, length = 1, max_length = 5, elements = 0x12eb970, initial_elements = 0x12eb970}
> >> >
> >> >and the member is a Var with varno=0 (with a RelabelType on top, but
> >> >that's irrelevant).
> >> >
> >> >    (gdb) p *(Var*)((RelabelType*)member->em_expr)->arg
> >> >    $12 = {xpr = {type = T_Var}, varno = 0, varattno = 1, vartype = 12445, vartypmod = -1, varcollid = 950,
varlevelsup= 0, varnosyn = 0, varattnosyn = 1, location = -1}
 
> >> >
> >> >which then triggers the assert in find_base_rel. When looking for other
> >> >places calling estimate_num_groups I found this in prepunion.c:
> >> >
> >> >     * XXX you don't really want to know about this: we do the estimation
> >> >     * using the subquery's original targetlist expressions, not the
> >> >     * subroot->processed_tlist which might seem more appropriate.  The
> >> >     * reason is that if the subquery is itself a setop, it may return a
> >> >     * processed_tlist containing "varno 0" Vars generated by
> >> >     * generate_append_tlist, and those would confuse estimate_num_groups
> >> >     * mightily.  We ought to get rid of the "varno 0" hack, but that
> >> >     * requires a redesign of the parsetree representation of setops, so
> >> >     * that there can be an RTE corresponding to each setop's output.
> >> >
> >> >which seems pretty similar to the issue at hand, because the subpath is
> >> >T_UpperUniquePath (not sure if that passes as setop, but the symptoms
> >> >match nicely).
> >> >
> >> >Not sure what to do about it in cost_incremental_sort, though :-(
> >> >
> >>
> >> I've been messing with this the whole day, without much progress :-(
> >>
> >> I'm 99.9999% sure it's the same issue described by the quoted comment,
> >> because the plan looks like this:
> >>
> >>   Nested Loop Left Join
> >>     ->  Sample Scan on pg_namespace
> >>           Sampling: system ('7.2'::real)
> >>     ->  Incremental Sort
> >>           Sort Key: ...
> >>           Presorted Key: ...
> >>           ->  Unique
> >>                 ->  Sort
> >>                       Sort Key: ...
> >>                       ->  Append
> >>                             ->  Nested Loop
> >>                                 ...
> >>                             ->  Nested Loop
> >>                                 ...
> >>
> >> so yeah, the plan does have set operations, and generate_append_tlist
> >> does generate Vars with varno == 0, causing this issue.
> >
> >This is a bit of an oddly shaped plan anyway, right? In an ideal world
> >the sort for the unique would have knowledge about what would be
> >useful for the parent node, and we wouldn't need the incremental sort
> >at all.
> >
>
> Well, yeah. The problem is the Unique simply compares the columns in the
> order it sees them, and it does not match the column order desired by
> incremental sort. But we don't push down this information at all :-(
>
> In fact, there may be other reasons to reorder the comparisons, e.g.
> when the cost is different for different columns. There was a patch by
> Teodor IIRC correctly doing exactly that.
>
> >I'm not sure that that kind of thing is really a new problem, though,
> >and it might not even be entirely possible to fix directly by trying
> >to push down knowledge about useful sort keys to whatever created that
> >sort path; it might only be fixable by having the incremental sort (or
> >even regular sort) path creation know to "subsume" a sort underneath
> >it.
> >
> >Anyway, I think that's a bit off topic, but it stood out to me.
> >
>
> It's not a new problem. It's an optimization we don't have.
>
> >> But I'm not entirely sure what to do about it in cost_incremental_sort.
> >> The comment (introduced by 89deca582a in 2017) suggests a proper fix
> >> would require redesigning the parsetree representation of setops, and
> >> it's a bit too late for that.
> >>
> >> So I wonder what a possible solution might look like. I was hoping we
> >> might grab the original target list and use that, similarly to
> >> recurse_set_operations, but I'm not sure how/where to get it.
> >
> >This is also not an area I'm familiar with. Reading through the
> >prepunion.c code alongside cost_incremental_sort, it seems that we
> >don't have access to the same level of information as the prepunion
> >code (i.e., we're only looking at the result of the union, not the
> >components of it), and trying descend down into it seems even more
> >gross, so, see below...
> >
>
> Yeah. And I'm not even sure having that information would allow good
> estimates e.g. for UNIONs of multiple relations etc.
>
> >> Another option is to use something as simple as checking for Vars with
> >> varno==0 in cost_incremental_sort() and ignoring them somehow. We could
> >> simply use some arbitrary estimate - by assuming the rows are unique or
> >> something like that. Yes, I agree it's pretty ugly and I'd much rather
> >> find a way to generate something sensible, but I'm not even sure we can
> >> generate good estimate when doing UNION of data from different relations
> >> and so on. The attached (ugly) patch does this.
> >
> >...therefore I think this is worth proceeding with.
> >
>
> OK, then the question is what estimate to use in this case. Should we
> assume 1 group or uniqueness? I'd assume a single group produces costs
> slightly above regular sort, right?

Originally I'd intuitively leaned towards assuming they were unique.
But that would be the best case for memory/disk space usage, for
example, and the costing for incremental sort is always (at least
mildly) higher than regular sort if the number of groups is 1. That
also guarantees the startup cost is higher than regular sort also.

So I think using a number of groups estimate of 1, we just wouldn't
choose an incremental sort ever in this case.

Maybe that's the right choice? It'd certainly be the conservative
choice. What are your thoughts on the trade-offs there?

James