Content-Type: multipart/mixed; boundary="------------jva0Ml2gbHvAGY448JqAX0p6"
Message-ID: <f7a8729d-86d4-43ad-8b68-a7a3ace9d0fc@postgrespro.ru>
Date: Thu, 18 Jan 2024 16:48:54 +0700
MIME-Version: 1.0
User-Agent: Mozilla Thunderbird
Subject: Re: POC: GROUP BY optimization
To: Alexander Korotkov <aekorotkov@gmail.com>,
 Richard Guo <guofenglinux@gmail.com>
Cc: Pavel Borisov <pashkin.elfe@gmail.com>, vignesh C <vignesh21@gmail.com>,
 PostgreSQL Developers <pgsql-hackers@lists.postgresql.org>,
 Tomas Vondra <tomas.vondra@enterprisedb.com>,
 Teodor Sigaev <teodor@sigaev.ru>, David Rowley <dgrowleyml@gmail.com>,
 "a.rybakina" <a.rybakina@postgrespro.ru>, Tom Lane <tgl@sss.pgh.pa.us>
References: 
 <CA+q6zcVRrd-z4YZ4M43ccst7aGL9==w5r1fionRWhP9ot6mybQ@mail.gmail.com>
 <CAPpHfdtzaVa7S4onKy3YvttF2rrH5hQNHx9HtcSTLbpjx+MJ+w@mail.gmail.com>
 <add93f4d-07d8-4b95-b9be-0d84652a5943@postgrespro.ru>
 <CALDaNm2CP2XQGTdNYKHnETeQZUV_TUBM-S297-298VqiwrFrLg@mail.gmail.com>
 <138cb2df-1a0d-48c0-be80-48aaf62e8aeb@postgrespro.ru>
 <CALT9ZEFbBHxjaFwRxhqf1tj2M5wmGiiZwUY5ts8eq3jwxFJ_mg@mail.gmail.com>
 <CAPpHfdsrEfOqJfNuObNvM+-3D4sVzsCkmJXLLNZKf8t04dUgsg@mail.gmail.com>
 <d1254c2a-2da7-4290-a81a-ca09c99ebb49@postgrespro.ru>
 <CAPpHfdscoK4u4PhR354Swso3Tx0cFOjJKcbG02mi98jTwRxW9A@mail.gmail.com>
 <f0ea5a6e-3e9b-48b2-b122-9196ee450cbd@postgrespro.ru>
 <CAPpHfdtWiQk587H3F-SHm4VUrb26rU7kBF1GtzV1CKOzz+GcOw@mail.gmail.com>
 <CAMbWs48jZKgqnCuWKzaxrzgthDW5MfJTfesnTGUOs+oWCn+uEw@mail.gmail.com>
 <CAPpHfdtqS1LXRSPNKjuG-gCxDdYaRk3YUisNgQco4yR3KmD0Zw@mail.gmail.com>
 <CAMbWs4-7oUGax4qWUwdiuyPKYKDO-DtKrcPedmjbPZyC-uYYrg@mail.gmail.com>
 <CAPpHfdsfHn89cAFEa6-6Xm1sB_xf8Rf2WNab6DQzb8Rvs0yD8g@mail.gmail.com>
Content-Language: en-US
From: Andrei Lepikhov <a.lepikhov@postgrespro.ru>
Organization: Postgres Professional
In-Reply-To: 
 <CAPpHfdsfHn89cAFEa6-6Xm1sB_xf8Rf2WNab6DQzb8Rvs0yD8g@mail.gmail.com>
Archived-At: 
 <https://www.postgresql.org/message-id/f7a8729d-86d4-43ad-8b68-a7a3ace9d0fc%40postgrespro.ru>
Precedence: bulk

This is a multi-part message in MIME format.
--------------jva0Ml2gbHvAGY448JqAX0p6
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit

On 16/1/2024 22:05, Alexander Korotkov wrote:
> On Tue, Jan 16, 2024 at 4:48 AM Richard Guo <guofenglinux@gmail.com> wrote:
>> * When trying to match the ordering of GROUP BY to that of ORDER BY in
>> get_useful_group_keys_orderings, this patch checks against the length of
>> path->pathkeys.  This does not make sense.  I guess this is a typo and
>> the real intention is to check against root->sort_pathkeys.
Thanks! It is really my blunder - fresh look works.
>>
>> --- a/src/backend/optimizer/path/pathkeys.c
>> +++ b/src/backend/optimizer/path/pathkeys.c
>> @@ -504,7 +504,7 @@ get_useful_group_keys_orderings(PlannerInfo *root, Path *path)
>>                                             root->num_groupby_pathkeys);
>>
>>          if (n > 0 &&
>> -           (enable_incremental_sort || n == list_length(path->pathkeys)))
>> +           (enable_incremental_sort || n == list_length(root->sort_pathkeys)))
>>
>> However, I think this is also incorrect.  When incremental sort is
>> disabled, it is reasonable to consider reordering the GROUP BY keys only
>> if the number of matching pathkeys is equal to the length of
>> root->group_pathkeys i.e. if 'n == list_length(root->group_pathkeys)'.
> 
> Hmm... Why should this be list_length(root->group_pathkeys) while
> we're targeting root->sort_pathkeys.  I yet changed that to
> list_length(root->sort_pathkeys).
I think, in the first case, when we are trying to arrange group-by keys 
according to underlying pathkeys with incremental sort = off, it makes 
sense to do if we fetch all group-by keys regardless of a more or equal 
number of path keys the incoming path contains. The code and test case 
are in step1.txt.
> 
>> * When the original ordering of GROUP BY keys matches the path's
>> pathkeys or ORDER BY keys, get_useful_group_keys_orderings would
>> generate duplicate PathKeyInfos.  Consequently, this duplication would
>> lead to the creation and addition of identical paths multiple times.
>> This is not great.  Consider the query below:
>>
>> create table t (a int, b int);
>> create index on t (a, b);
>> set enable_hashagg to off;
>>
>> explain select count(*) from t group by a, b;
>>                                      QUERY PLAN
>> ----------------------------------------------------------------------------------
>>   GroupAggregate  (cost=0.15..97.27 rows=226 width=16)
>>     Group Key: a, b
>>     ->  Index Only Scan using t_a_b_idx on t  (cost=0.15..78.06 rows=2260 width=8)
>> (3 rows)
>>
>> The same path with group keys {a, b} is created and added twice.
> 
> I tried to address that.
> 
>> * Part of the work performed in this patch overlaps with that of
>> preprocess_groupclause.  They are both trying to adjust the ordering of
>> the GROUP BY keys to match ORDER BY.  I wonder if it would be better to
>> perform this work only once.
> 
> Andrei, could you take a look.
As I see, the PathKeyInfo list often contains duplicated pathkeys, 
coming from either sort_pathkeys or path->pathkeys orderings. So, I can 
propose to check duplicates each time (see step2.txt in attachment).
> 
>> * When reordering the GROUP BY keys, I think the following checks need
>> some improvements.
>>
>> +       /*
>> +        * Since 1349d27 pathkey coming from underlying node can be in the
>> +        * root->group_pathkeys but not in the processed_groupClause. So, we
>> +        * should be careful here.
>> +        */
>> +       sgc = get_sortgroupref_clause_noerr(pathkey->pk_eclass->ec_sortref,
>> +                                           *group_clauses);
>> +       if (!sgc)
>> +           /* The grouping clause does not cover this pathkey */
>> +           break;
>>
>> I think we need to check or assert 'pathkey->pk_eclass->ec_sortref' is
>> valid before calling get_sortgroupref_clause_noerr with it.  Also, how
>> can we guarantee that the returned GROUP BY item is sortable?  Should we
>> check that with OidIsValid(sgc->sortop)?
> 
> Added.
Reviewed it, looks good.

-- 
regards,
Andrei Lepikhov
Postgres Professional

--------------jva0Ml2gbHvAGY448JqAX0p6
Content-Type: text/plain; charset=UTF-8; name="step1.txt"
Content-Disposition: attachment; filename="step1.txt"
Content-Transfer-Encoding: base64

ZGlmZiAtLWdpdCBhL3NyYy9iYWNrZW5kL29wdGltaXplci9wYXRoL3BhdGhrZXlzLmMgYi9z
cmMvYmFja2VuZC9vcHRpbWl6ZXIvcGF0aC9wYXRoa2V5cy5jCmluZGV4IDkxOWQ1NGRkNzku
LjEwOTViNzNkYWMgMTAwNjQ0Ci0tLSBhL3NyYy9iYWNrZW5kL29wdGltaXplci9wYXRoL3Bh
dGhrZXlzLmMKKysrIGIvc3JjL2JhY2tlbmQvb3B0aW1pemVyL3BhdGgvcGF0aGtleXMuYwpA
QCAtNDg5LDggKzQ4OSw5IEBAIGdldF91c2VmdWxfZ3JvdXBfa2V5c19vcmRlcmluZ3MoUGxh
bm5lckluZm8gKnJvb3QsIFBhdGggKnBhdGgpCiAJCW4gPSBncm91cF9rZXlzX3Jlb3JkZXJf
YnlfcGF0aGtleXMocGF0aC0+cGF0aGtleXMsICZwYXRoa2V5cywgJmNsYXVzZXMsCiAJCQkJ
CQkJCQkJICAgcm9vdC0+bnVtX2dyb3VwYnlfcGF0aGtleXMpOwogCi0JCWlmIChuID4gMCAm
JiBjb21wYXJlX3BhdGhrZXlzKHBhdGhrZXlzLCByb290LT5ncm91cF9wYXRoa2V5cykgIT0g
UEFUSEtFWVNfRVFVQUwgJiYKLQkJCShlbmFibGVfaW5jcmVtZW50YWxfc29ydCB8fCBuID09
IGxpc3RfbGVuZ3RoKHBhdGgtPnBhdGhrZXlzKSkpCisJCWlmIChuID4gMCAmJgorCQkJKGVu
YWJsZV9pbmNyZW1lbnRhbF9zb3J0IHx8IG4gPT0gcm9vdC0+bnVtX2dyb3VwYnlfcGF0aGtl
eXMpICYmCisJCQljb21wYXJlX3BhdGhrZXlzKHBhdGhrZXlzLCByb290LT5ncm91cF9wYXRo
a2V5cykgIT0gUEFUSEtFWVNfRVFVQUwpCiAJCXsKIAkJCWluZm8gPSBtYWtlTm9kZShQYXRo
S2V5SW5mbyk7CiAJCQlpbmZvLT5wYXRoa2V5cyA9IHBhdGhrZXlzOwpkaWZmIC0tZ2l0IGEv
c3JjL3Rlc3QvcmVncmVzcy9leHBlY3RlZC9hZ2dyZWdhdGVzLm91dCBiL3NyYy90ZXN0L3Jl
Z3Jlc3MvZXhwZWN0ZWQvYWdncmVnYXRlcy5vdXQKaW5kZXggY2EzOGU3OGYyMS4uNjdkZDIw
ZjM3NSAxMDA2NDQKLS0tIGEvc3JjL3Rlc3QvcmVncmVzcy9leHBlY3RlZC9hZ2dyZWdhdGVz
Lm91dAorKysgYi9zcmMvdGVzdC9yZWdyZXNzL2V4cGVjdGVkL2FnZ3JlZ2F0ZXMub3V0CkBA
IC0yODU2LDYgKzI4NTYsMjMgQEAgZXhwbGFpbiAoQ09TVFMgT0ZGKSBTRUxFQ1QgeCx3IEZS
T00gYnRnIEdST1VQIEJZIHcseCx5LHogT1JERVIgQlkgeCp4LHo7CiAgICAgICAgICAgICAg
ICAtPiAgSW5kZXggU2NhbiB1c2luZyBhYmMgb24gYnRnCiAoOCByb3dzKQogCitTRVQgZW5h
YmxlX2luY3JlbWVudGFsX3NvcnQgPSBvZmY7CistLSBUaGUgY2FzZSB3aGVuIHRoZSBudW1i
ZXIgb2YgaW5jb21pbmcgc3VidHJlZSBwYXRoIGtleXMgaXMgbW9yZSB0aGFuCistLSB0aGUg
bnVtYmVyIG9mIGdyb3VwaW5nIGtleXMuCitDUkVBVEUgSU5ERVggaWR4X3lfeF96IE9OIGJ0
Zyh5LHgsdyk7CitFWFBMQUlOIChWRVJCT1NFLCBDT1NUUyBPRkYpCitTRUxFQ1QgeSx4LGFy
cmF5X2FnZyhkaXN0aW5jdCB3KSBGUk9NIGJ0ZyBXSEVSRSB5IDwgMCBHUk9VUCBCWSB4LHk7
CisgICAgICAgICAgICAgICAgICAgICBRVUVSWSBQTEFOICAgICAgICAgICAgICAgICAgICAg
IAorLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t
LS0KKyBHcm91cEFnZ3JlZ2F0ZQorICAgT3V0cHV0OiB5LCB4LCBhcnJheV9hZ2coRElTVElO
Q1QgdykKKyAgIEdyb3VwIEtleTogYnRnLnksIGJ0Zy54CisgICAtPiAgSW5kZXggT25seSBT
Y2FuIHVzaW5nIGlkeF95X3hfeiBvbiBwdWJsaWMuYnRnCisgICAgICAgICBPdXRwdXQ6IHks
IHgsIHcKKyAgICAgICAgIEluZGV4IENvbmQ6IChidGcueSA8IDApCisoNiByb3dzKQorCitS
RVNFVCBlbmFibGVfaW5jcmVtZW50YWxfc29ydDsKIERST1AgVEFCTEUgYnRnOwogLS0gVGhl
IGNhc2UsIHdoZW4gc2Nhbm5pbmcgc29ydCBvcmRlciBjb3JyZXNwb25kIHRvIGFnZ3JlZ2F0
ZSBzb3J0IG9yZGVyIGJ1dAogLS0gY2FuIG5vdCBiZSBmb3VuZCBpbiB0aGUgZ3JvdXAtYnkg
bGlzdApkaWZmIC0tZ2l0IGEvc3JjL3Rlc3QvcmVncmVzcy9zcWwvYWdncmVnYXRlcy5zcWwg
Yi9zcmMvdGVzdC9yZWdyZXNzL3NxbC9hZ2dyZWdhdGVzLnNxbAppbmRleCA5ODgwYTE4OGQz
Li41MjRiZGZhNjdkIDEwMDY0NAotLS0gYS9zcmMvdGVzdC9yZWdyZXNzL3NxbC9hZ2dyZWdh
dGVzLnNxbAorKysgYi9zcmMvdGVzdC9yZWdyZXNzL3NxbC9hZ2dyZWdhdGVzLnNxbApAQCAt
MTE4Miw3ICsxMTgyLDYgQEAgU0VMRUNUIGJhbGsoaHVuZHJlZCkgRlJPTSB0ZW5rMTsKIFJP
TExCQUNLOwogCiAtLSBHUk9VUCBCWSBvcHRpbWl6YXRpb24gYnkgcmVvcmRlciBjb2x1bW5z
Ci0KIENSRUFURSBUQUJMRSBidGcgQVMgU0VMRUNUCiAgIGkgJSAxMDAgQVMgeCwKICAgaSAl
IDEwMCBBUyB5LApAQCAtMTIyMyw4ICsxMjIyLDExIEBAIGV4cGxhaW4gKENPU1RTIE9GRikg
U0VMRUNUIHgseSBGUk9NIGJ0ZyBHUk9VUCBCWSB3LHgseix5IE9SREVSIEJZIHkseCx6LHc7
CiBleHBsYWluIChDT1NUUyBPRkYpIFNFTEVDVCB4LHcgRlJPTSBidGcgR1JPVVAgQlkgdyx4
LHkseiBPUkRFUiBCWSB4KngsejsKIAogU0VUIGVuYWJsZV9pbmNyZW1lbnRhbF9zb3J0ID0g
b2ZmOwotRVhQTEFJTiAoVkVSQk9TRSwgQ09TVFMgT04pCi1TRUxFQ1QgeCx5LCBhcnJheV9h
Z2coeikgRlJPTSBidGcgV0hFUkUgeCA8IDIgR1JPVVAgQlkgeSx4OworLS0gVGhlIGNhc2Ug
d2hlbiB0aGUgbnVtYmVyIG9mIGluY29taW5nIHN1YnRyZWUgcGF0aCBrZXlzIGlzIG1vcmUg
dGhhbgorLS0gdGhlIG51bWJlciBvZiBncm91cGluZyBrZXlzLgorQ1JFQVRFIElOREVYIGlk
eF95X3hfeiBPTiBidGcoeSx4LHcpOworRVhQTEFJTiAoVkVSQk9TRSwgQ09TVFMgT0ZGKQor
U0VMRUNUIHkseCxhcnJheV9hZ2coZGlzdGluY3QgdykgRlJPTSBidGcgV0hFUkUgeSA8IDAg
R1JPVVAgQlkgeCx5OwogUkVTRVQgZW5hYmxlX2luY3JlbWVudGFsX3NvcnQ7CiAKIERST1Ag
VEFCTEUgYnRnOwo=

--------------jva0Ml2gbHvAGY448JqAX0p6--