Re: POC: GROUP BY optimization

Hi Teodor,

Thanks for the patch. This (missing) optimization popped-up repeatedly
recently, and I was planning to look into it for PG12. So now I don't
have to, because you've done all the hard work ;-)

I've have done only very basic review so far, but ISTM the general
approach of considering additional indexes in create_index_paths is
correct. That being said, I do have a couple of comments:

1) add_path() ensures that we only keep the one cheapest path sorted
path for each pathkeys. This patch somewhat defeats that because it
considers additional pathkeys (essentially any permutation of group
keys) as interesting. So we may end up with more paths in the list.

I wonder if we should make the add_path() logic smarter to recognize
when two paths have different pathkeys but were generated to match the
same grouping, to reduce the number of paths added by this optimization.
Currently we do that for each pathkeys list independently, but we're
considering many more pathkeys orderings ...

That being said, maybe this concern is moot - to generate large number
of new paths, there would have to be a lot of indexes matching the group
by clause (as a prefix), and the group by clause would need to be fairly
large (to have many permutations). That seems like a fairly rare case. I
do know a couple of people who do create large numbers of indexes on
tables, but those are usually single-column indexes.

2) sort reordering based on ndistinct estimates

This part of the patch (reordering the columns in an explicit sort node)
seems to be largely independent of the "consider other indexes" part. So
I do suggest separating those two, and discussing them independently.

But thinking about this optimization, I'm worried it relies on a couple
of important assumptions. For now those decisions could have be made by
the person writing the SQL query, but this optimization makes that
impossible. So we really need to get this right.

For example, it seems to disregard that different data types have
different comparison costs. For example comparing bytea will be far more
expensive compared to int4, so it may be much more efficient to compare
int4 columns first, even if there are far fewer distinct values in them.

This costing is probably related to abbreviated keys too, which is a
huge improvement for text and other varlena-based types.

Also, simply sorting the columns by their ndistinct estimate is somewhat
naive, because it assumes the columns are independent. Imagine for
example a table with three columns:

CREATE TABLE t (a INT, b INT, c INT);

INSERT INTO t SELECT mod(i,100), mod(i,100)/2, 49*random()
FROM generate_series(1,1000000) s(i);

Clearly, "a" has the most distinct values (100), while both "b" and "c"
have 50 distinct values. But "b" does not actually split any of the "a"
groups, while "c" does:

select count(*) from (select 1 from t group by a,b) foo;
count
-------
100
(1 row)

select count(*) from (select 1 from t group by a,c) foo;
count
-------
5000
(1 row)

So clearly, when evaluating GROUP BY a,b,c it'd be more efficient to use
"(a,c,b)" than "(a,b,c)" but there is no way to decide this merely using
per-column ndistinct values. Luckily, we now have ndistinct multi-column
coefficients which could be used to decide this I believe (but I haven't
tried).

The real issue however is that this decision can't be made entirely
locally. Consider for example this:

explain select a,b,c, count(*) from t group by a,b,c order by c,b,a;
QUERY PLAN

------------------------------------------------------------------------------
Sort (cost=156010.16..156260.16 rows=100000 width=20)
Sort Key: c, b, a
-> GroupAggregate (cost=132154.34..145654.34 rows=100000 width=20)
Group Key: a, c, b
-> Sort (cost=132154.34..134654.34 rows=1000000 width=12)
Sort Key: a, c, b
-> Seq Scan on t (cost=0.00..15406.00 rows=1000000
width=12)
(7 rows)

while without the patch, this would happen:

explain select a,b,c, count(*) from t group by a,b,c order by c,b,a;
QUERY PLAN

------------------------------------------------------------------------
GroupAggregate (cost=132154.34..145654.34 rows=100000 width=20)
Group Key: c, b, a
-> Sort (cost=132154.34..134654.34 rows=1000000 width=12)
Sort Key: c, b, a
-> Seq Scan on t (cost=0.00..15406.00 rows=1000000 width=12)
(5 rows)

Which is clearly cheaper (at least according to the optimizer) than
doing two separate sorts. So the optimization actually does the wrong
thing here, and it needs to somehow consider the other ordering
requirements (in this case ORDER BY) - either by generating multiple
paths with different orderings or some heuristics.

I'm also wondering how freely we can change the group by result
ordering. Assume you disable hash aggregate and parallel query -
currently we are guaranteed to use group aggregate that produces exactly
the ordering as specified in GROUP BY, but this patch removes that
"guarantee" and we can produce arbitrary permutation of the ordering.
But as I argued in other threads, such implicit guarantees are really
fragile, can silently break for arbitrary reasons (say, parallel query
will do just that) and can be easily fixed by adding a proper ORDER BY.
So I don't think this is an issue.

The other random thought is how will/could this interact with the
incremental sorts patch. I know Alexander wanted to significantly limit
where we actually consider the incremental sort, but I'm not sure if
this was one of those places or not (is sure looks like a place where we
would greatly benefit from it).

So to summarize this initial review - I do suggest splitting the patch
into two parts. One that does the index magic, and one for this
reordering optimization. The first part (additional indexes) seems quite
fairly safe, likely to get committable soon. The other part (ndistinct
reordering) IMHO requires more thought regarding costing and interaction
with other query parts.

regards

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