Subject: Re: POC: GROUP BY optimization
To: Teodor Sigaev <teodor@sigaev.ru>,
 Pgsql Hackers <pgsql-hackers@postgresql.org>
References: <7c79e6a5-8597-74e8-0671-1c39d124c9d6@sigaev.ru>
 <97d148b7-f3e7-1c39-07fd-74cbc66f6ec9@sigaev.ru>
 <6d1e0cdb-dde3-f62a-43e2-e90bbd9b0f42@2ndquadrant.com>
 <b2c0e7bf-0d38-0042-dbbe-7e50b6a3454f@sigaev.ru>
 <7edddb4f-9ddd-561d-2bde-47340f91d2a0@2ndquadrant.com>
 <2cb99655-7ae7-ec8d-2c74-3fea58987104@sigaev.ru>
 <6dddcce6-0d91-1868-794a-4d61dc5516f0@2ndquadrant.com>
 <a02225c6-96d3-2e85-9907-9459105d1244@sigaev.ru>
 <e33558a8-6528-f0c4-8f59-04ff7e2e529c@2ndquadrant.com>
 <523d1f60-c60c-5c8c-8cc5-c6c078970da6@2ndquadrant.com>
 <24c773b8-3a9a-8fe9-610d-01145758931b@sigaev.ru>
 <623f5e50-eeb2-1279-d30b-dc43611fb063@2ndquadrant.com>
 <c324d0be-16df-5c98-3b54-9c564596ab53@sigaev.ru>
 <1913e082-0d8d-5eb8-c8ca-053af828076a@2ndquadrant.com>
 <3bbdd1ee-544d-a549-b0c2-30485d9f6a16@sigaev.ru>
From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Message-ID: <83b0d707-405d-c2be-0d98-01267e68d671@2ndquadrant.com>
Date: Fri, 29 Jun 2018 17:03:13 +0200
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:52.0) Gecko/20100101
 Thunderbird/52.5.2
MIME-Version: 1.0
In-Reply-To: <3bbdd1ee-544d-a549-b0c2-30485d9f6a16@sigaev.ru>
Content-Type: text/plain; charset=koi8-r; format=flowed
Content-Language: en-US
Content-Transfer-Encoding: 7bit
Precedence: bulk

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