Subject: Re: POC: GROUP BY optimization
From: "Andrey V. Lepikhov" <a.lepikhov@postgrespro.ru>
To: Tomas Vondra <tomas.vondra@enterprisedb.com>,
 Teodor Sigaev <teodor@sigaev.ru>
Cc: Tomas Vondra <tomas.vondra@2ndquadrant.com>,
 PostgreSQL Developers <pgsql-hackers@lists.postgresql.org>
References: <CA+q6zcVRrd-z4YZ4M43ccst7aGL9==w5r1fionRWhP9ot6mybQ@mail.gmail.com>
 <20200514235220.xewrrwjvatxzn3g6@development>
 <CALT9ZEFU60nW9TJqHUs9Ex_tqv__7t=jfF4Q=iwwxJTO0PY7Rg@mail.gmail.com>
 <20201026085721.g6h5xljxvodnmk34@localhost>
 <CALT9ZEF8FUZoijXnFsDXNgqbSHFzaCU2q0cmJFnZ4z2wNZO98w@mail.gmail.com>
 <20201026104040.6bigvej6f55vjvgp@localhost>
 <20201027201509.jfv6sfhrmxhdwlvk@development>
 <20201029145025.tn3tekboot37nkbf@localhost>
 <CALT9ZEEqnS+tObVjLWZrUme-PZQ-O0krpFCfQhwG-4ziSeSrBQ@mail.gmail.com>
 <CALtqXTdsuDq_dsbE0F0XHd8U2-ceSdvN9wr1zkap=sJypgBJBA@mail.gmail.com>
 <CALT9ZEFwfCQAzUVfUxak=fzhgwez3jn=5XcpsU9HbKQ_VjrZ-A@mail.gmail.com>
 <22c44f98-bfa8-8630-62b5-5155e11eb284@enterprisedb.com>
 <CALtqXTe4rKXHXxNNGVy0wHVwGYYJpy2QNPTN29qq+ErBJJakrA@mail.gmail.com>
 <b1d468ba-2961-044c-deab-817b9a900e9c@enterprisedb.com>
 <ba2eccf2-d623-c12c-f7c2-a58ac4917c83@enterprisedb.com>
 <006667af-fc50-0627-4be7-5d9cf665219f@enterprisedb.com>
 <dc933c66-41b9-8907-327e-f6361a690654@postgrespro.ru>
Organization: Postgres Professional
Message-ID: <82114b8f-d3a1-ee58-f840-466e695f90c0@postgrespro.ru>
Date: Tue, 1 Feb 2022 14:48:11 +0500
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101
 Thunderbird/78.14.0
MIME-Version: 1.0
In-Reply-To: <dc933c66-41b9-8907-327e-f6361a690654@postgrespro.ru>
Content-Type: multipart/mixed;
 boundary="------------CE5442F806F6CB3699CA908B"
Content-Language: en-US
Archived-At: <https://www.postgresql.org/message-id/82114b8f-d3a1-ee58-f840-466e695f90c0%40postgrespro.ru>
Precedence: bulk

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

> On 7/22/21 3:58 AM, Tomas Vondra wrote:
> I've simplified the costing a bit, and the attached version actually
> undoes all the "suspicious" plan changes in postgres_fdw. It changes one
> new plan, but that seems somewhat reasonable, as it pushes sort to the
> remote side.

I tried to justify heap-sort part of the compute_cpu_sort_cost() routine 
and realized, that here we may have a mistake.
After a week of efforts, I don't found any research papers on dependence 
of bounded heap-sort time compexity on number of duplicates.

So, I suppose self-made formula, based on simple logical constructions:

1. We should base on initial formula: cost ~ N*LOG2(M), where M - 
output_tuples.
2. Realize, that full representation of this formula is:

cost ~ N*LOG2(min{N,M})

3. In the case of multicolumn, number of comparisons for each next 
column can be estimated by the same formula, but arranged to a number of 
tuples per group:

comparisons ~ input * LOG2(min{input,M})

4. Realize, that for the case, when M > input, we should change this 
formula a bit:

comparisons ~ max{input,M} * LOG2(min{input,M})

Remember, that in our case M << tuples.
So, general formula for bounded heap sort can be written as:

cost ~ N * sum(max{n_i,M}/N * LOG2(min{n_i,M})), i=1,ncols

where n_1 == N, n_i - number of tuples per group, estimated from 
previous iteration.

In attachment - an implementation of this approach.

-- 
regards,
Andrey Lepikhov
Postgres Professional

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

ZGlmZiAtLWdpdCBhL3NyYy9iYWNrZW5kL29wdGltaXplci9wYXRoL2Nvc3RzaXplLmMgYi9z
cmMvYmFja2VuZC9vcHRpbWl6ZXIvcGF0aC9jb3N0c2l6ZS5jCmluZGV4IDY4YTMyNzQwZDcu
LjJjM2NjZTU3YWEgMTAwNjQ0Ci0tLSBhL3NyYy9iYWNrZW5kL29wdGltaXplci9wYXRoL2Nv
c3RzaXplLmMKKysrIGIvc3JjL2JhY2tlbmQvb3B0aW1pemVyL3BhdGgvY29zdHNpemUuYwpA
QCAtMTg3Miw2ICsxODcyLDE1IEBAIGdldF93aWR0aF9jb3N0X211bHRpcGxpZXIoUGxhbm5l
ckluZm8gKnJvb3QsIEV4cHIgKmV4cHIpCiAgKgogICoJTiAqIHN1bSggRmsgKiBsb2coR2sp
ICkKICAqCisgKiBGb3IgYm91bmRlZCBoZWFwIHNvcnQgd2UgaGF2ZW4ndCBzdWNoIGEgZHVw
bGljYXRlcy1yZWxhdGVkIHJlc2VhcmNoLiBTbyBpbnZlbnQKKyAqIGl0IGJhc2VkIG9uIGEg
c2ltcGxlIGxvZ2ljIChNIC0gbnVtYmVyIG9mIG91dHB1dCB0dXBsZXMpOgorICogRm9yIG9u
ZSBjb2x1bW4gd2UgY2FuIGVzdGltYXRlIG51bWJlciBvZiBjb21wYXJpc29ucyBhczoKKyAq
IE4gKiBsb2cobWlue04sTX0pCisgKiBGb3IgdGhlIGNhc2Ugb2YgbWFueSBjb2x1bW5zIHdl
IGNhbiBuYXRpdmVseSBlc3RpbWF0ZSBudW1iZXIgb2YgY29tcGFyaXNvbnMgYnkKKyAqIHRo
ZSBmb3JtdWxhOgorICogc3VtKG1heHtuX2ksTX0gKiBsb2cobWlue04sTX0pKSwKKyAqIHdo
ZXJlIG5fMCA9PSBOLCBuX2kgLSBudW1iZXIgb2YgdHVwbGVzIHBlciBncm91cCwgZXN0aW1h
dGVkIG9uIHByZXZpb3VzIHN0ZXAuCisgKgogICogTm90ZTogV2UgYWxzbyBjb25zaWRlciBj
b2x1bW4gd2lkdGgsIG5vdCBqdXN0IHRoZSBjb21wYXJhdG9yIGNvc3QuCiAgKgogICogTk9U
RTogc29tZSBjYWxsZXJzIGN1cnJlbnRseSBwYXNzIE5JTCBmb3IgcGF0aGtleXMgYmVjYXVz
ZSB0aGV5CkBAIC0xODgxLDcgKzE4OTAsNyBAQCBnZXRfd2lkdGhfY29zdF9tdWx0aXBsaWVy
KFBsYW5uZXJJbmZvICpyb290LCBFeHByICpleHByKQogc3RhdGljIENvc3QKIGNvbXB1dGVf
Y3B1X3NvcnRfY29zdChQbGFubmVySW5mbyAqcm9vdCwgTGlzdCAqcGF0aGtleXMsIGludCBu
UHJlc29ydGVkS2V5cywKIAkJCQkJICBDb3N0IGNvbXBhcmlzb25fY29zdCwgZG91YmxlIHR1
cGxlcywgZG91YmxlIG91dHB1dF90dXBsZXMsCi0JCQkJCSAgYm9vbCBoZWFwU29ydCkKKwkJ
CQkJICBib29sIGJvdW5kZWRfc29ydCkKIHsKIAlDb3N0CQlwZXJfdHVwbGVfY29zdCA9IDAu
MDsKIAlMaXN0Q2VsbAkqbGM7CkBAIC0xOTA3LDcgKzE5MTYsNyBAQCBjb21wdXRlX2NwdV9z
b3J0X2Nvc3QoUGxhbm5lckluZm8gKnJvb3QsIExpc3QgKnBhdGhrZXlzLCBpbnQgblByZXNv
cnRlZEtleXMsCiAJCSAqIG9mIHRoaXMgZnVuY3Rpb24sIGJ1dCBJJ20gbm90IHN1cmUuIEkg
c3VnZ2VzdCB3ZSBpbnRyb2R1Y2Ugc29tZSBzaW1wbGUKIAkJICogY29uc3RhbnRzIGZvciB0
aGF0LCBpbnN0ZWFkIG9mIG1hZ2ljIHZhbHVlcy4KIAkJICovCi0JCW91dHB1dF90dXBsZXMg
PSAoaGVhcFNvcnQpID8gMi4wICogb3V0cHV0X3R1cGxlcyA6IHR1cGxlczsKKwkJb3V0cHV0
X3R1cGxlcyA9IChib3VuZGVkX3NvcnQpID8gMi4wICogb3V0cHV0X3R1cGxlcyA6IHR1cGxl
czsKIAkJcGVyX3R1cGxlX2Nvc3QgKz0gMi4wICogY3B1X29wZXJhdG9yX2Nvc3QgKiBMT0cy
KG91dHB1dF90dXBsZXMpOwogCiAJCS8qIGFkZCBjb3N0IHByb3ZpZGVkIGJ5IGNhbGxlciAq
LwpAQCAtMTkyNSw4ICsxOTM0LDcgQEAgY29tcHV0ZV9jcHVfc29ydF9jb3N0KFBsYW5uZXJJ
bmZvICpyb290LCBMaXN0ICpwYXRoa2V5cywgaW50IG5QcmVzb3J0ZWRLZXlzLAogCXsKIAkJ
UGF0aEtleQkJCQkqcGF0aGtleSA9IChQYXRoS2V5KikgbGZpcnN0KGxjKTsKIAkJRXF1aXZh
bGVuY2VNZW1iZXIJKmVtOwotCQlkb3VibGUJCQkJIG5Hcm91cHMsCi0JCQkJCQkJIGNvcnJl
Y3RlZE5Hcm91cHM7CisJCWRvdWJsZQkJCQkgbkdyb3VwczsKIAogCQkvKgogCQkgKiBXZSBi
ZWxpZXZlIHRoYXQgZXF1aXZhbGVuY2UgbWVtYmVycyBhcmVuJ3QgdmVyeSBkaWZmZXJlbnQs
IHNvLCB0bwpAQCAtMjAwMCwyNCArMjAwOCwxNiBAQCBjb21wdXRlX2NwdV9zb3J0X2Nvc3Qo
UGxhbm5lckluZm8gKnJvb3QsIExpc3QgKnBhdGhrZXlzLCBpbnQgblByZXNvcnRlZEtleXMs
CiAJCSAqLwogCQlpZiAoaSA+PSBuUHJlc29ydGVkS2V5cykKIAkJewotCQkJaWYgKGhlYXBT
b3J0KQotCQkJewotCQkJCWRvdWJsZSBoZWFwX3R1cGxlczsKLQotCQkJCS8qIGhhdmUgdG8g
a2VlcCBhdCBsZWFzdCBvbmUgZ3JvdXAsIGFuZCBhIG11bHRpcGxlIG9mIGdyb3VwIHNpemUg
Ki8KLQkJCQloZWFwX3R1cGxlcyA9IE1heChjZWlsKG91dHB1dF90dXBsZXMgLyB0dXBsZXNQ
ZXJQcmV2R3JvdXApICogdHVwbGVzUGVyUHJldkdyb3VwLAotCQkJCQkJCQkgIHR1cGxlc1Bl
clByZXZHcm91cCk7Ci0KLQkJCQkvKiBzbyBob3cgbWFueSAod2hvbGUpIGdyb3VwcyBpcyB0
aGF0PyAqLwotCQkJCWNvcnJlY3RlZE5Hcm91cHMgPSBjZWlsKGhlYXBfdHVwbGVzIC8gdHVw
bGVzUGVyUHJldkdyb3VwKTsKLQkJCX0KKwkJCS8qCisJCQkgKiBRdWljayBzb3J0IGFuZCAn
dG9wLU4nIHNvcnRpbmcgKGJvdW5kZWQgaGVhcCBzb3J0KSBhbGdvcml0aG1zCisJCQkgKiBo
YXZlIGRpZmZlcmVudCBmb3JtdWxhcyBmb3IgdGltZSBjb21wbGV4aXR5IGVzdGltYXRpb24u
CisJCQkgKi8KKwkJCWlmIChib3VuZGVkX3NvcnQpCisJCQkJcGVyX3R1cGxlX2Nvc3QgKz0g
dG90YWxGdW5jQ29zdCAqCisJCQkJCQkJCSAgKE1heCh0dXBsZXNQZXJQcmV2R3JvdXAsIG91
dHB1dF90dXBsZXMpIC8gdHVwbGVzKSAqCisJCQkJCQkJCSAgTE9HMigyLjAgKiBNaW4odHVw
bGVzUGVyUHJldkdyb3VwLCBvdXRwdXRfdHVwbGVzKSk7CiAJCQllbHNlCi0JCQkJLyogYWxs
IGdyb3VwcyBpbiB0aGUgaW5wdXQgKi8KLQkJCQljb3JyZWN0ZWROR3JvdXBzID0gbkdyb3Vw
czsKLQotCQkJY29ycmVjdGVkTkdyb3VwcyA9IE1heCgxLjAsIGNlaWwoY29ycmVjdGVkTkdy
b3VwcykpOwotCi0JCQlwZXJfdHVwbGVfY29zdCArPSB0b3RhbEZ1bmNDb3N0ICogTE9HMihj
b3JyZWN0ZWROR3JvdXBzKTsKKwkJCQlwZXJfdHVwbGVfY29zdCArPSB0b3RhbEZ1bmNDb3N0
ICogTE9HMihuR3JvdXBzKTsKIAkJfQogCiAJCWkrKzsK
--------------CE5442F806F6CB3699CA908B--