Date: Fri, 15 May 2020 01:52:20 +0200
From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
To: Dmitry Dolgov <9erthalion6@gmail.com>
Cc: Teodor Sigaev <teodor@sigaev.ru>,
	Gavin Flower <GavinFlower@archidevsys.co.nz>,
	Andres Freund <andres@anarazel.de>,
	Michael Paquier <michael@paquier.xyz>,
	PostgreSQL Developers <pgsql-hackers@lists.postgresql.org>
Subject: Re: POC: GROUP BY optimization
Message-ID: <20200514235220.xewrrwjvatxzn3g6@development>
References: <0b3ee377-2f67-f58d-6177-bc2ed4626499@archidevsys.co.nz>
 <20181002021626.GF11712@paquier.xyz>
 <CA+q6zcVFEB--p=e2S-mY6UB87YCBBh=5WXdw2Gqr-2nBGtLkjg@mail.gmail.com>
 <20190131112407.zpbysdvghjyh4z47@alap3.anarazel.de>
 <CA+q6zcVfsx_YuETPmjkNq-1=kJCS5JuShrL2ZNzm_HRVZ-tiYg@mail.gmail.com>
 <20190409152100.5q25whnxs27zws5m@development>
 <CA+q6zcVRrd-z4YZ4M43ccst7aGL9==w5r1fionRWhP9ot6mybQ@mail.gmail.com>
 <20190503215510.bcr5ycszntqg65tw@development>
 <CA+q6zcVjCVkAhoLD6rjDoPGdfWDjQLD=N2tvfH1yU+Eq+iby9w@mail.gmail.com>
 <20190524225725.embuha33qvc5avz3@development>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Disposition: inline
In-Reply-To: <20190524225725.embuha33qvc5avz3@development>
Precedence: bulk

Hi,

I wonder if anyone has plans to try again with this optimization in v14
cycle? The patches no longer apply thanks to the incremental sort patch,
but I suppose fixing that should not be extremely hard.

The 2020-07 CF is still a couple weeks away, but it'd be good to know if
there are any plans to revive this. I'm willing to spend some time on
reviewing / testing this, etc.


I've only quickly skimmed the old thread, but IIRC there were two main
challenges in getting the optimization right:


1) deciding which orderings are interesting / worth additional work

I think we need to consider these orderings, in addition to the one
specified in GROUP BY:

1) as specified in ORDER BY (if different from 1)

2) one with cheapest sort on unsorted input (depending on number of
distinct values, cost of comparisons, etc.)

3) one with cheapest sort on partially sorted input (essentially what we
do with the incremental sort paths, but matching the pathkeys in a more
elaborate way)


2) costing the alternative orderings

I think we've already discussed various ways to leverage as much
available info as possible (extended stats, MCVs, ...) but I think the
patch only does some of it.


regards

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