Subject: Re: Parallel Aggregates for string_agg and array_agg
To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: David Rowley <david.rowley@2ndquadrant.com>,
 Stephen Frost <sfrost@snowman.net>, Andres Freund <andres@anarazel.de>,
 PostgreSQL-development <pgsql-hackers@postgresql.org>
References: 
 <CAKJS1f8cB3cc5AK=wPvByhU_jKkgd81iRt2kE6cru8uxx2HCuA@mail.gmail.com>
 <c302afa6-6415-27a5-336a-e1d4332fab09@2ndquadrant.com>
 <CAKJS1f9xEZdTaBbBEKY+TCKEoSZYaH1oSAtsEJHSYDJCCNnQPQ@mail.gmail.com>
 <24abe018-b3c6-2117-b5b9-39e660db00bd@2ndquadrant.com>
 <CAKJS1f8LV7AT=AAhdYGKtGrGkSkEgO6C_SW2Ztz1sR3encisqw@mail.gmail.com>
 <1b6ee15c-c218-761e-0120-c1ed438e2db2@2ndquadrant.com>
 <657be73a-a21d-0ae1-5c62-870afbdfddd4@2ndquadrant.com>
 <CAKJS1f-bKAD+s-CJetRQPjmrR-gF-kfvwfzhQm-A0PA-nsr1xw@mail.gmail.com>
 <20180326022647.GL24540@tamriel.snowman.net>
 <CAKJS1f-axkksX3XzduLJuTL=o8CSwf1NaQYO6=iHSXR_B3pCKQ@mail.gmail.com>
 <20180326132009.GN24540@tamriel.snowman.net>
 <CAKJS1f8JVpUUkYP2c+RyVRdpS1dnjB_DA5fbcDSL3qfMRqc81Q@mail.gmail.com>
 <6538.1522096067@sss.pgh.pa.us>
 <cd620e7f-a9dd-ad15-72a8-6c0ac10ea4c3@2ndquadrant.com>
 <18594.1522099194@sss.pgh.pa.us>
From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Message-ID: <13a2ab54-0d83-d2a2-faa2-963310d8f75f@2ndquadrant.com>
Date: Tue, 27 Mar 2018 00:14:27 +0200
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101
 Thunderbird/52.4.0
MIME-Version: 1.0
In-Reply-To: <18594.1522099194@sss.pgh.pa.us>
Content-Type: text/plain; charset=utf-8
Content-Language: en-US
Content-Transfer-Encoding: 7bit
Precedence: bulk

On 03/26/2018 11:19 PM, Tom Lane wrote:
> Tomas Vondra <tomas.vondra@2ndquadrant.com> writes:
>> On 03/26/2018 10:27 PM, Tom Lane wrote:
>>> I fear that what will happen, if we commit this, is that something like
>>> 0.01% of the users of array_agg and string_agg will be pleased, another
>>> maybe 20% will be unaffected because they wrote ORDER BY which prevents
>>> parallel aggregation, and the remaining 80% will scream because we broke
>>> their queries.  Telling them they should've written ORDER BY isn't going
>>> to cut it, IMO, when the benefit of that breakage will accrue only to some
>>> very tiny fraction of use-cases.
> 
>> Isn't the ordering unreliable *already*?
> 
> Not if the query is such that what gets chosen is, say, an indexscan 
> or mergejoin. It might be theoretically unreliable and yet work fine 
> for a given application.
> 

What about parallel versions of those plans, though? That is, what
prevents the planner from generating plans like this

    Hash Aggregate
       -> Gather
          -> Partial Index Scan

AFAIK that's a valid plan, and it does not have the stable ordering
property of a non-parallel index scan. Similarly for Merge Join.

> I might be too pessimistic about the fraction of users who are depending
> on ordered input without having written anything that explicitly forces
> that ... but I stand by the theory that it substantially exceeds the
> fraction of users who could get any benefit.
> 

Not sure, it's pretty much impossible to produce a number that would
meaningfully represent the whole user base. All I can say is that the
number of people I know, who would benefit from this is significant.

>
> Your own example of assuming that separate aggregates are computed
> in the same order reinforces my point, I think.  In principle, anybody
> who's doing that should write
> 
>        array_agg(e order by x),
>        array_agg(f order by x),
>        string_agg(g order by x)
> 
> because otherwise they shouldn't assume that; the manual certainly doesn't
> promise it.  But nobody does that in production, because if they did
> they'd get killed by the fact that the sorts are all done independently.

Yes, the manual does not promise that. But I find that expectation way
more "natural" than deterministic ordering without ORDER BY clause. I
expect each tuple to be processed "at once" - that it's added to all
arrays in the same step, irrespectedly of the ordering of input tuples.

> (We should improve that someday, but it hasn't been done yet.)  So I think
> there are an awful lot of people out there who are assuming more than a
> lawyerly reading of the manual would allow.  Their reaction to this will
> be about like ours every time the GCC guys decide that some longstanding
> behavior of C code isn't actually promised by the text of the C standard.
> 

But we're not *already* providing reliable ordering without an ORDER BY
clause (both for queries as a whole and array_agg/string_agg). It can
produce arbitrary ordering, depending on what plan you happen to get.

So I don't think we'd be changing any longstanding behavior, because
it's already unreliable. If it was semi-reliable before, assuming the
query only ever chose index scans or merge joins, it likely got broken
by introduction of parallel versions of those plans. If the users
disable parallel queries (to get the old plans), they're going to get
non-parallel semi-reliable plans again.

OTOH we are currently accumulating all the arrays in the same order, so
the results will match. (At least that's what I believe is the current
reliable behavior.) So following the GCC analogy, changing this seems
much more akin to GCC people changing some longstanding behavior.

Also, if the arrays were not accumulated in the same way reliably,
wouldn't this mean all the discussion about reliable ordering with
certain plans is pointless?


regards

-- 
Tomas Vondra                  http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services