Date: Sat, 20 Jun 2020 16:30:10 +0200
From: Dmitry Dolgov <9erthalion6@gmail.com>
To: Tomas Vondra <tomas.vondra@2ndquadrant.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: <20200620143010.z3af7wa4v22h4lu4@localhost>
References: <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>
 <20200514235220.xewrrwjvatxzn3g6@development>
 <20200516122431.b7wtpm7dspsaxfro@localhost>
 <20200516145609.vm7nrqy7frj4ha6r@development>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <20200516145609.vm7nrqy7frj4ha6r@development>
Precedence: bulk

> On Sat, May 16, 2020 at 04:56:09PM +0200, Tomas Vondra wrote:
>
> So I don't think there will be a single "interesting" grouping pathkeys
> (i.e. root->group_pathkeys), but a collection of pathkeys. And we'll
> need to build grouping paths for all of those, and leave the planner to
> eventually pick the one giving us the cheapest plan ...
>
> A "brute-force" approach would be to generate all possible orderings of
> group_pathkeys, but that's probably not going to fly - it might easily
> cause an explosion in number of paths we track, etc. So we'll need to
> pick/prioritize orderings that are more likely to give us efficient
> plans, and ORDER BY seems like a good example because it means we won't
> need an explicit sort.

Yes, I see. I've already rebased the original version of patch and now
working on your suggestions. In the meantime one question:

> But there are also decisions that can be made only after we build the
> grouping paths. For example, we may have both GROUP BY and ORDER BY, and
> there is no "always correct" way to combine those. In some cases it may
> be correct to use the same pathkeys, in other cases it's better to use
> different ones (which will require an extra Sort, with additional cost).

Do I understand correctly, your idea is that in some cases it's cheaper
to use different order for GROUP BY than in ORDER BY even with an extra
sorting? In the current patch implementation there is an assumption that
says it's always better to match the order of pathkeys for both GROUP
BY/ORDER BY (which means that the only degree of freedom there is to
reorder the tail, which in turn makes both "unsorted input" and
"partially sorted input" cases from your original email essentially the
same). Can you show such an example when this assumption is invalid?

> 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:

Yes, looks like the current patch implementation together with
preprocess_groupclause already implements this, although maybe not that
flexible.

> 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.

Right, there were couple of ideas what to do in case of a few groups
which are too big they can invalidate current assumptions about costs.
E.g. do not apply reordering if we detected such situation, or use
"conservative" approach and take the biggest group for estimations.