Horton

Re: POC: GROUP BY optimization

Andrei Lepikhov <a.lepikhov@postgrespro.ru>

View thread
From: Andrey Lepikhov <a.lepikhov@postgrespro.ru>
To: Tomas Vondra <tomas.vondra@enterprisedb.com>, Teodor Sigaev <teodor@sigaev.ru>
Cc: Tomas Vondra <tomas.vondra@2ndquadrant.com>, PostgreSQL Developers <pgsql-hackers@lists.postgresql.org>
Date: 2022-01-21T11:09:01Z
Lists: pgsql-hackers

Commits

Same data as JSON: GET /api/v1/messages/:b64id/commits the thread's linked commits as JSON, with link sources. API reference →

  1. Restore preprocess_groupclause()

  2. Rename PathKeyInfo to GroupByOrdering

  3. Add invariants check to get_useful_group_keys_orderings()

  4. Fix asymmetry in setting EquivalenceClass.ec_sortref

  5. Multiple revisions to the GROUP BY reordering tests

  6. Get rid of pg_class usage in SJE regression tests

  7. Rename index "abc" in aggregates.sql

  8. Explore alternative orderings of group-by pathkeys during optimization.

  9. Generalize the common code of adding sort before processing of grouping

  10. Fix out-dated comment in preprocess_groupclause()

  11. Force parallelism in partition_aggregate

  12. Optimize order of GROUP BY keys

Attachments

On 7/22/21 3:58 AM, Tomas Vondra wrote:
> 4) I'm not sure it's actually a good idea to pass tuplesPerPrevGroup to
> estimate_num_groups_incremental. In principle yes, if we use "group
> size" from the previous step, then the returned value is the number of
> new groups after adding the "new" pathkey.
> But even if we ignore the issues with amplification mentioned in (3),
> there's an issue with non-linear behavior in estimate_num_groups,
> because at some point it's calculating
> 
>     D(N,n,p) = n * (1 - ((N-p)/N)^(N/n))
> 
> where N - total rows, p - sample size, n - number of distinct values.
> And if we have (N1,n1) and (N2,n2) then the ratio of calculated
> estimated (which is pretty much what calculating group size does)
> 
>     D(N2,n2,p2) / D(N1,n1,p1)
> 
> which will differ depending on p1 and p2. And if we're tweaking the
> tuplesPerPrevGroup all the time, that's really annoying, as it may make
> the groups smaller or larger, which is unpredictable and annoying, and I
> wonder if it might go against the idea of penalizing tuplesPerPrevGroup
> to some extent.
> We could simply use the input "tuples" value here, and then divide the
> current and previous estimate to calculate the number of new groups.
tuplesPerPrevGroup is only a top boundary for the estimation. I think, 
we should use result of previous estimation as a limit for the next 
during incremental estimation. Maybe we simply limit the 
tuplesPerPrevGroup value to ensure of monotonic non-growth of this 
value? - see in attachment patch to previous fixes.

-- 
regards,
Andrey Lepikhov
Postgres Professional