Horton

Re: POC: GROUP BY optimization

Tomas Vondra <tomas.vondra@2ndquadrant.com>

View thread
From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
To: Teodor Sigaev <teodor@sigaev.ru>, Pgsql Hackers <pgsql-hackers@postgresql.org>
Date: 2018-06-29T15:03:13Z
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

On 06/29/2018 04:51 PM, Teodor Sigaev wrote:
> 
>>> I tried to attack the cost_sort() issues and hope on that basis we 
>>> can solve problems with 0002 patch and improve incremental sort patch.
>>>
>>
>> OK, will do. Thanks for working on this!
> 
> I hope, now we have a better cost_sort(). The obvious way is a try all 
> combination of pathkeys in get_cheapest_group_keys_order() and choose 
> cheapest one by cost_sort().

> But it requires N! operations and potentially could be very
> expensive in case of large number of pathkeys and doesn't solve the
> issue with user-knows-what-he-does pathkeys.

Not sure. There are N! combinations, but this seems like a good 
candidate for backtracking [1]. You don't have to enumerate and evaluate 
all N! combinations, just construct one and then abandon whole classes 
of combinations as soon as they get more expensive than the currently 
best one. That's thanks to additive nature of the comparison costing, 
because appending a column to the sort key can only make it more 
expensive. My guess is this will make this a non-issue.

[1] https://en.wikipedia.org/wiki/Backtracking

>
> We could suggest an order of pathkeys as patch suggests now and if 
> cost_sort() estimates cost is less than 80% (arbitrary chosen) cost
> of user-suggested pathkeys then it use our else user pathkeys.
> 

I really despise such arbitrary thresholds. I'd much rather use a more 
reliable heuristics by default, even if it gets it wrong in some cases 
(which it will, but that's natural).

regards

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