public inbox for [email protected]  

help / color / mirror / Atom feed

From: Tomas Vondra <[email protected]>
To: Teodor Sigaev <[email protected]>
To: Pgsql Hackers <[email protected]>
Subject: Re: POC: GROUP BY optimization
Date: Fri, 29 Jun 2018 17:03:13 +0200
Message-ID: <[email protected]> (raw)
In-Reply-To: <[email protected]>
References: <[email protected]>
	<[email protected]>
	<[email protected]>
	<[email protected]>
	<[email protected]>
	<[email protected]>
	<[email protected]>
	<[email protected]>
	<[email protected]>
	<[email protected]>
	<[email protected]>
	<[email protected]>
	<[email protected]>
	<[email protected]>
	<[email protected]>

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

view thread (89+ messages)  latest in thread

reply

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients using the --to and --cc options:
  reply via email

  To: [email protected]
  Cc: [email protected], [email protected]
  Subject: Re: POC: GROUP BY optimization
  In-Reply-To: <[email protected]>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox