Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1n289B-0007D1-Dm for pgsql-hackers@arkaria.postgresql.org; Tue, 28 Dec 2021 08:47:54 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.92) (envelope-from ) id 1n289A-00044W-9i for pgsql-hackers@arkaria.postgresql.org; Tue, 28 Dec 2021 08:47:52 +0000 Received: from makus.postgresql.org ([2001:4800:3e1:1::229]) by malur.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1n2899-00044N-Bh for pgsql-hackers@lists.postgresql.org; Tue, 28 Dec 2021 08:47:51 +0000 Received: from mail.postgrespro.ru ([93.174.131.139]) by makus.postgresql.org with esmtp (Exim 4.92) (envelope-from ) id 1n288x-0004T1-Q9 for pgsql-hackers@postgresql.org; Tue, 28 Dec 2021 08:47:50 +0000 Received: from [192.168.28.53] (cyclops.postgrespro.ru [93.174.131.138]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (Client did not present a certificate) by mail.postgrespro.ru (Postfix) with ESMTPSA id 8EB9421C46B3; Tue, 28 Dec 2021 11:47:36 +0300 (MSK) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=postgrespro.ru; s=mail; t=1640681257; bh=PyNrVE+bkmwFmrWQ0iYwmRt2WG8okDt8M251YzNK96Y=; h=Subject:To:Cc:References:From:Date:In-Reply-To; b=Fj+U0qCGd7G0mQqYZYywSr1mZ4jZzNapaU9tjfPflu9TAZgfQcHrcNF426Yww7sYG KzjQ8w66BxND0dmXYMkQfmEr1GD9uk24u8t83b+nNFrwxpp6SJ71RqOiFr3OBIQyvt 4KdR6Jyg1VDwgoxGO0FzUETx2KbSSDm9Ye4kuBvc= Subject: Re: POC: GROUP BY optimization To: Tomas Vondra Cc: PostgreSQL-development References: <20200901210743.lutgvnfzntvhuban@development> <20200902161201.ogkjrpf232a7htn3@development> From: "Andrey V. Lepikhov" Organization: Postgres Professional Message-ID: <16e9e7c3-7f6e-b3a8-ca74-38590631d9a2@postgrespro.ru> Date: Tue, 28 Dec 2021 13:47:35 +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: <20200902161201.ogkjrpf232a7htn3@development> Content-Type: multipart/mixed; boundary="------------FE1ED6BF0674B62EE378EE16" Content-Language: en-US List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk This is a multi-part message in MIME format. --------------FE1ED6BF0674B62EE378EE16 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 7bit On 9/2/20 9:12 PM, Tomas Vondra wrote: > We could simply use the input "tuples" value here, and then divide the > current and previous estimate to calculate the number of new groups. Performing a review of this patch I made a number of changes (see cleanup.txt). Maybe it will be useful. As I see, the code, which implements the main idea, is quite stable. Doubts localized in the cost estimation routine. Maybe try to finish this work by implementing an conservative strategy to a cost estimation of sorting? -- regards, Andrey Lepikhov Postgres Professional --------------FE1ED6BF0674B62EE378EE16 Content-Type: text/plain; charset=UTF-8; name="cleanup.txt" Content-Transfer-Encoding: base64 Content-Disposition: attachment; filename="cleanup.txt" ZGlmZiAtLWdpdCBhL3NyYy9iYWNrZW5kL29wdGltaXplci9wYXRoL2Nvc3RzaXplLmMgYi9z cmMvYmFja2VuZC9vcHRpbWl6ZXIvcGF0aC9jb3N0c2l6ZS5jCmluZGV4IGU2MTdlMmNlMGUu LjIxMWFlNjZiMzMgMTAwNjQ0Ci0tLSBhL3NyYy9iYWNrZW5kL29wdGltaXplci9wYXRoL2Nv c3RzaXplLmMKKysrIGIvc3JjL2JhY2tlbmQvb3B0aW1pemVyL3BhdGgvY29zdHNpemUuYwpA QCAtMTg2NSw3ICsxODY1LDcgQEAgZ2V0X3dpZHRoX2Nvc3RfbXVsdGlwbGllcihQbGFubmVy SW5mbyAqcm9vdCwgRXhwciAqZXhwcikKICAqCiAgKiBGb3IgbXVsdGktY29sdW1uIHNvcnRz IHdlIG5lZWQgdG8gZXN0aW1hdGUgdGhlIG51bWJlciBvZiBjb21wYXJpc29ucyBmb3IKICAq IGVhY2ggaW5kaXZpZHVhbCBjb2x1bW4gLSBmb3IgZXhhbXBsZSB3aXRoIGNvbHVtbnMgKGMx LCBjMiwgLi4uLCBjaykgd2UKLSAqIGNhbiBlc3RpbWF0ZSB0aGF0IG51bWJlciBvZiBjb21w YXJpb25zIG9uIGNrIGlzIHJvdWdobHkKKyAqIGNhbiBlc3RpbWF0ZSB0aGF0IG51bWJlciBv ZiBjb21wYXJpc29ucyBvbiBjayBpcyByb3VnaGx5CiAgKgogICoJbmNvbXBhcmlzb25zKGMx LCBjMiwgLi4uLCBjaykgLyBuY29tcGFyaXNvbnMoYzEsIGMyLCAuLi4sIGMoay0xKSkKICAq CkBAIC0xODc0LDEwICsxODc0LDEwIEBAIGdldF93aWR0aF9jb3N0X211bHRpcGxpZXIoUGxh bm5lckluZm8gKnJvb3QsIEV4cHIgKmV4cHIpCiAgKgogICoJTiAqIHN1bSggRmsgKiBsb2co R2spICkKICAqCi0gKiBOb3RlOiBXZSBhbHNvIGNvbnNpZGVyIGNvbHVtbiB3aXRkdGgsIG5v dCBqdXN0IHRoZSBjb21wYXJhdG9yIGNvc3QuCisgKiBOb3RlOiBXZSBhbHNvIGNvbnNpZGVy IGNvbHVtbiB3aWR0aCwgbm90IGp1c3QgdGhlIGNvbXBhcmF0b3IgY29zdC4KICAqCiAgKiBO T1RFOiBzb21lIGNhbGxlcnMgY3VycmVudGx5IHBhc3MgTklMIGZvciBwYXRoa2V5cyBiZWNh dXNlIHRoZXkKLSAqIGNhbid0IGNvbnZlbmllbnRseSBzdXBwbHkgdGhlIHNvcnQga2V5cy4g IEluIHRoaXMgY2FzZSwgaXQgd2lsbCBmYWxsYmFjayB0bworICogY2FuJ3QgY29udmVuaWVu dGx5IHN1cHBseSB0aGUgc29ydCBrZXlzLiBJbiB0aGlzIGNhc2UsIGl0IHdpbGwgZmFsbGJh Y2sgdG8KICAqIHNpbXBsZSBjb21wYXJpc29uIGNvc3QgZXN0aW1hdGUuCiAgKi8KIHN0YXRp YyBDb3N0CkBAIC0xOTI1LDEzICsxOTI1LDEzIEBAIGNvbXB1dGVfY3B1X3NvcnRfY29zdChQ bGFubmVySW5mbyAqcm9vdCwgTGlzdCAqcGF0aGtleXMsIGludCBuUHJlc29ydGVkS2V5cywK IAkgKi8KIAlmb3JlYWNoKGxjLCBwYXRoa2V5cykKIAl7Ci0JCVBhdGhLZXkJCQkJKnBhdGhr ZXkgPSAoUGF0aEtleSopbGZpcnN0KGxjKTsKKwkJUGF0aEtleQkJCQkqcGF0aGtleSA9IChQ YXRoS2V5KikgbGZpcnN0KGxjKTsKIAkJRXF1aXZhbGVuY2VNZW1iZXIJKmVtOwogCQlkb3Vi bGUJCQkJIG5Hcm91cHMsCiAJCQkJCQkJIGNvcnJlY3RlZE5Hcm91cHM7CiAKIAkJLyoKLQkJ ICogV2UgYmVsaWV2ZSB0aGFuIGVxdWl2YWxlbmNlIG1lbWJlcnMgYXJlbid0IHZlcnkgIGRp ZmZlcmVudCwgc28sIHRvCisJCSAqIFdlIGJlbGlldmUgdGhhbiBlcXVpdmFsZW5jZSBtZW1i ZXJzIGFyZW4ndCB2ZXJ5IGRpZmZlcmVudCwgc28sIHRvCiAJCSAqIGVzdGltYXRlIGNvc3Qg d2UgdGFrZSBqdXN0IGZpcnN0IG1lbWJlcgogCQkgKi8KIAkJZW0gPSAoRXF1aXZhbGVuY2VN ZW1iZXIgKikgbGluaXRpYWwocGF0aGtleS0+cGtfZWNsYXNzLT5lY19tZW1iZXJzKTsKQEAg LTE5NjQsNyArMTk2NCw3IEBAIGNvbXB1dGVfY3B1X3NvcnRfY29zdChQbGFubmVySW5mbyAq cm9vdCwgTGlzdCAqcGF0aGtleXMsIGludCBuUHJlc29ydGVkS2V5cywKIAogCQl0b3RhbEZ1 bmNDb3N0ICs9IGZ1bmNDb3N0OwogCi0JCS8qIHJlbWViZXIgaWYgd2UgaGF2ZSBhIGZha2Ug dmFyIGluIHBhdGhrZXlzICovCisJCS8qIFJlbWVtYmVyIGlmIHdlIGhhdmUgYSBmYWtlIHZh ciBpbiBwYXRoa2V5cyAqLwogCQloYXNfZmFrZV92YXIgfD0gaXNfZmFrZV92YXIoZW0tPmVt X2V4cHIpOwogCQlwYXRoa2V5RXhwcnMgPSBsYXBwZW5kKHBhdGhrZXlFeHBycywgZW0tPmVt X2V4cHIpOwogCkBAIC0xOTc0LDcgKzE5NzQsNyBAQCBjb21wdXRlX2NwdV9zb3J0X2Nvc3Qo UGxhbm5lckluZm8gKnJvb3QsIExpc3QgKnBhdGhrZXlzLCBpbnQgblByZXNvcnRlZEtleXMs CiAJCSAqLwogCQlpZiAoaGFzX2Zha2VfdmFyID09IGZhbHNlKQogCQkJLyoKLQkJCSAqIFJl Y3Vyc2l2ZWx5IGNvbXB1dGUgbnVtYmVyIG9mIGdyb3VwIGluIGdyb3VwIGZyb20gcHJldmlv dXMgc3RlcAorCQkJICogUmVjdXJzaXZlbHkgY29tcHV0ZSBudW1iZXIgb2YgZ3JvdXBzIGlu IGEgZ3JvdXAgZnJvbSBwcmV2aW91cyBzdGVwCiAJCQkgKi8KIAkJCW5Hcm91cHMgPSBlc3Rp bWF0ZV9udW1fZ3JvdXBzX2luY3JlbWVudGFsKHJvb3QsIHBhdGhrZXlFeHBycywKIAkJCQkJ CQkJCQkJCQkgIHR1cGxlc1BlclByZXZHcm91cCwgTlVMTCwgTlVMTCwKQEAgLTE5OTIsOCAr MTk5Miw3IEBAIGNvbXB1dGVfY3B1X3NvcnRfY29zdChQbGFubmVySW5mbyAqcm9vdCwgTGlz dCAqcGF0aGtleXMsIGludCBuUHJlc29ydGVkS2V5cywKIAkJCSAqCiAJCQkgKiBYWFggV2hh dCdzIHRoZSBsb2dpYyBvZiB0aGUgZm9sbG93aW5nIGZvcm11bGE/CiAJCQkgKi8KLQkJCW5H cm91cHMgPSBjZWlsKDIuMCArIHNxcnQodHVwbGVzKSAqCi0JCQkJbGlzdF9sZW5ndGgocGF0 aGtleUV4cHJzKSAvIGxpc3RfbGVuZ3RoKHBhdGhrZXlzKSk7CisJCQluR3JvdXBzID0gY2Vp bCgyLjAgKyBzcXJ0KHR1cGxlcykgKiAoaSArIDEpIC8gbGlzdF9sZW5ndGgocGF0aGtleXMp KTsKIAkJZWxzZQogCQkJbkdyb3VwcyA9IHR1cGxlczsKIApAQCAtMjAzMyw3ICsyMDMyLDcg QEAgY29tcHV0ZV9jcHVfc29ydF9jb3N0KFBsYW5uZXJJbmZvICpyb290LCBMaXN0ICpwYXRo a2V5cywgaW50IG5QcmVzb3J0ZWRLZXlzLAogCiAJCS8qCiAJCSAqIFdlIGNvdWxkIHNraXAg YWxsIGZvbGxvd2luZyBjb2x1bW5zIGZvciBjb3N0IGVzdGltYXRpb24sIGJlY2F1c2Ugd2UK LQkJICogYmVsaWV2ZSB0aGF0IHR1cGxlcyBhcmUgdW5pcXVlIGJ5IHNldCBvdCBwcmV2aW91 cyBjb2x1bW5zCisJCSAqIGJlbGlldmUgdGhhdCB0dXBsZXMgYXJlIHVuaXF1ZSBieSB0aGUg c2V0IG9mIHByZXZpb3VzIGNvbHVtbnMKIAkJICovCiAJCWlmICh0dXBsZXNQZXJQcmV2R3Jv dXAgPD0gMS4wKQogCQkJYnJlYWs7CmRpZmYgLS1naXQgYS9zcmMvYmFja2VuZC9vcHRpbWl6 ZXIvcGF0aC9wYXRoa2V5cy5jIGIvc3JjL2JhY2tlbmQvb3B0aW1pemVyL3BhdGgvcGF0aGtl eXMuYwppbmRleCA4MjgzMWE0ZmE0Li43MDdiNWJhNzViIDEwMDY0NAotLS0gYS9zcmMvYmFj a2VuZC9vcHRpbWl6ZXIvcGF0aC9wYXRoa2V5cy5jCisrKyBiL3NyYy9iYWNrZW5kL29wdGlt aXplci9wYXRoL3BhdGhrZXlzLmMKQEAgLTU0NCw5ICs1NDQsMTAgQEAgUGF0aGtleU11dGF0 b3JOZXh0KFBhdGhrZXlNdXRhdG9yU3RhdGUgKnN0YXRlKQogCXJldHVybiBzdGF0ZS0+ZWxl bXNMaXN0OwogfQogCi10eXBlZGVmIHN0cnVjdCB7Ci0JQ29zdCBjb3N0OwotCVBhdGhLZXkg KnBhdGhrZXk7Cit0eXBlZGVmIHN0cnVjdCBQYXRoa2V5U29ydENvc3QKK3sKKwlDb3N0CQlj b3N0OworCVBhdGhLZXkJICAgKnBhdGhrZXk7CiB9IFBhdGhrZXlTb3J0Q29zdDsKIAogc3Rh dGljIGludApAQCAtNzkzLDcgKzc5NCw3IEBAIGdldF91c2VmdWxfZ3JvdXBfa2V5c19vcmRl cmluZ3MoUGxhbm5lckluZm8gKnJvb3QsIGRvdWJsZSBucm93cywKIAkgKiBtb3JlIGNvbXBs ZXggbG9naWMgdG8gZGVjaWRlIHRoZSBvcmRlcmluZy4KIAkgKgogCSAqIFhYWCBJc24ndCB0 aGlzIHNvbWV3aGF0IHJlZHVuZGFudCB3aXRoIHByZXNvcnRlZF9rZXlzPyBBY3R1YWxseSwg aXQncwotCSAqIG1vcmUgYSBjb21wbGVtZW50LCBiZWNhdXNlIGl0IGFsbG93cyBiZW5lZmlu dGluZyBmcm9tIGluY3JlbWVudGFsIHNvcnQKKwkgKiBtb3JlIGEgY29tcGxlbWVudCwgYmVj YXVzZSBpdCBhbGxvd3MgYmVuZWZpdGluZyBmcm9tIGluY3JlbWVudGFsIHNvcnQKIAkgKiBh cyBtdWNoIGFzIHBvc3NpYmxlLgogCSAqCiAJICogWFhYIFRoaXMgZG9lcyBub3RoaW5nIGlm IChuX3ByZW9yZGVyZWQgPT0gMCkuIFdlIHNob3VsZG4ndCBjcmVhdGUgdGhlCmRpZmYgLS1n aXQgYS9zcmMvYmFja2VuZC9vcHRpbWl6ZXIvcGxhbi9wbGFubmVyLmMgYi9zcmMvYmFja2Vu ZC9vcHRpbWl6ZXIvcGxhbi9wbGFubmVyLmMKaW5kZXggN2E4OWNlZTg3OS4uZjI4MWEyM2Ji NyAxMDA2NDQKLS0tIGEvc3JjL2JhY2tlbmQvb3B0aW1pemVyL3BsYW4vcGxhbm5lci5jCisr KyBiL3NyYy9iYWNrZW5kL29wdGltaXplci9wbGFuL3BsYW5uZXIuYwpAQCAtNjE1OCw3ICs2 MTU4LDYgQEAgYWRkX3BhdGhzX3RvX2dyb3VwaW5nX3JlbChQbGFubmVySW5mbyAqcm9vdCwg UmVsT3B0SW5mbyAqaW5wdXRfcmVsLAogCQl7CiAJCQlMaXN0Q2VsbCAgICpsYzI7CiAJCQlQ YXRoCSAgICpwYXRoID0gKFBhdGggKikgbGZpcnN0KGxjKTsKLQkJCVBhdGgJICAgKnBhdGhf c2F2ZSA9IHBhdGg7CiAJCQlQYXRoCSAgICpwYXRoX29yaWdpbmFsID0gcGF0aDsKIAogCQkJ TGlzdAkgICAqcGF0aGtleV9vcmRlcmluZ3MgPSBOSUw7CkBAIC02MTgyLDkgKzYxODEsNiBA QCBhZGRfcGF0aHNfdG9fZ3JvdXBpbmdfcmVsKFBsYW5uZXJJbmZvICpyb290LCBSZWxPcHRJ bmZvICppbnB1dF9yZWwsCiAJCQkJaW50CQkJcHJlc29ydGVkX2tleXMgPSAwOwogCQkJCVBh dGhLZXlJbmZvICppbmZvID0gKFBhdGhLZXlJbmZvICopIGxmaXJzdChsYzIpOwogCi0JCQkJ LyogcmVzdG9yZSB0aGUgcGF0aCAod2UgcmVwbGFjZSBpdCBpbiB0aGUgbG9vcCkgKi8KLQkJ CQlwYXRoID0gcGF0aF9zYXZlOwotCiAJCQkJaXNfc29ydGVkID0gcGF0aGtleXNfY291bnRf Y29udGFpbmVkX2luKGluZm8tPnBhdGhrZXlzLAogCQkJCQkJCQkJCQkJCQlwYXRoLT5wYXRo a2V5cywKIAkJCQkJCQkJCQkJCQkJJnByZXNvcnRlZF9rZXlzKTsKQEAgLTY2NTMsNyArNjY0 OSw2IEBAIGNyZWF0ZV9wYXJ0aWFsX2dyb3VwaW5nX3BhdGhzKFBsYW5uZXJJbmZvICpyb290 LAogCQl7CiAJCQlMaXN0Q2VsbCAgICpsYzI7CiAJCQlQYXRoCSAgICpwYXRoID0gKFBhdGgg KikgbGZpcnN0KGxjKTsKLQkJCVBhdGgJICAgKnBhdGhfc2F2ZSA9IHBhdGg7CiAKIAkJCUxp c3QJICAgKnBhdGhrZXlfb3JkZXJpbmdzID0gTklMOwogCkBAIC02Njc2LDkgKzY2NzEsNiBA QCBjcmVhdGVfcGFydGlhbF9ncm91cGluZ19wYXRocyhQbGFubmVySW5mbyAqcm9vdCwKIAkJ CQlpbnQJCQlwcmVzb3J0ZWRfa2V5cyA9IDA7CiAJCQkJUGF0aEtleUluZm8gKmluZm8gPSAo UGF0aEtleUluZm8gKikgbGZpcnN0KGxjMik7CiAKLQkJCQkvKiByZXN0b3JlIHRoZSBwYXRo ICh3ZSByZXBsYWNlIGl0IGluIHRoZSBsb29wKSAqLwotCQkJCXBhdGggPSBwYXRoX3NhdmU7 Ci0KIAkJCQlpc19zb3J0ZWQgPSBwYXRoa2V5c19jb3VudF9jb250YWluZWRfaW4oaW5mby0+ cGF0aGtleXMsCiAJCQkJCQkJCQkJCQkJCXBhdGgtPnBhdGhrZXlzLAogCQkJCQkJCQkJCQkJ CQkmcHJlc29ydGVkX2tleXMpOwo= --------------FE1ED6BF0674B62EE378EE16 Content-Type: text/x-patch; charset=UTF-8; name="group-by-reorder-20211228.patch" Content-Transfer-Encoding: 7bit Content-Disposition: attachment; filename="group-by-reorder-20211228.patch"