Re: POC: GROUP BY optimization

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