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 1q9iNV-0001BL-97 for pgsql-hackers@arkaria.postgresql.org; Thu, 15 Jun 2023 08:30:52 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.92) (envelope-from ) id 1q9iNT-0007K5-AZ for pgsql-hackers@arkaria.postgresql.org; Thu, 15 Jun 2023 08:30:47 +0000 Received: from magus.postgresql.org ([2a02:c0:301:0:ffff::29]) by malur.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1q9iNS-0007Jw-T5 for pgsql-hackers@lists.postgresql.org; Thu, 15 Jun 2023 08:30:47 +0000 Received: from mail.postgrespro.ru ([93.174.131.139]) by magus.postgresql.org with esmtp (Exim 4.94.2) (envelope-from ) id 1q9iNQ-002UiI-DR for pgsql-hackers@postgresql.org; Thu, 15 Jun 2023 08:30:46 +0000 Received: from [192.168.28.53] (unknown [192.168.28.53]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (Client did not present a certificate) (Authenticated sender: a.lepikhov@postgrespro.ru) by mail.postgrespro.ru (Postfix/587) with ESMTPSA id A276BE20E1F; Thu, 15 Jun 2023 11:30:11 +0300 (MSK) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=postgrespro.ru; s=mx2023; t=1686817812; bh=q/IB17JbgguLlbg2Rqs/xR6QDOy8rGNSvK6O+pR/qkQ=; h=Message-ID:Date:User-Agent:From:Subject:To:Cc:From; b=44t5T/PF/ZoBo13ICFaszdXNGbiXvcQ2pd3IG7N/KN5zbDywZXi6F5ufXWndYsz67 Pt1tzjt4iocGSmUn6KIxlCgksx7fFRcCIMdYh2K+kZinjPqWyX52udK3QoD2dK7yZw zHSeXNSV/u3Ey3RrGLgHtfmJD857glZ3PphWt64XNwgHiw1kf1+4kvOSJbUOR4dunI zdKFbraWZCbTS8tCDRrnpUhTToONY2hN6IKyvgQsjaEquSCXEphvjIe7YIpD0XG+po fm7QLoIg2VTMvfTrqHrFxV8Yiyh7kP7u3XGIolaTFc7a9ZFdqo/Tw7+ejzv2x6Whun tW5KrriVkPbpw== Content-Type: multipart/mixed; boundary="------------Vn1GuM7WAQipgakakPbglci9" Message-ID: <52257607-57f6-850d-399a-ec33a654457b@postgrespro.ru> Date: Thu, 15 Jun 2023 14:30:10 +0600 MIME-Version: 1.0 User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.15; rv:102.0) Gecko/20100101 Thunderbird/102.12.0 Content-Language: en-US From: Andrey Lepikhov Subject: MergeJoin beats HashJoin in the case of multiple hash clauses Organization: Postgres Professional To: PostgreSQL-development Cc: Tom Lane 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. --------------Vn1GuM7WAQipgakakPbglci9 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Hi, all. Some of my clients use JOIN's with three - four clauses. Quite frequently, I see complaints on unreasonable switch of JOIN algorithm to Merge Join instead of Hash Join. Quick research have shown one weak place - estimation of an average bucket size in final_cost_hashjoin (see q2.sql in attachment) with very conservative strategy. Unlike estimation of groups, here we use smallest ndistinct value across all buckets instead of multiplying them (or trying to make multivariate analysis). It works fine for the case of one clause. But if we have many clauses, and if each has high value of ndistinct, we will overestimate average size of a bucket and, as a result, prefer to use Merge Join. As the example in attachment shows, it leads to worse plan than possible, sometimes drastically worse. I assume, this is done with fear of functional dependencies between hash clause components. But as for me, here we should go the same way, as estimation of groups. The attached patch shows a sketch of the solution. -- regards, Andrey Lepikhov Postgres Professional --------------Vn1GuM7WAQipgakakPbglci9 Content-Type: application/sql; name="q2.sql" Content-Disposition: attachment; filename="q2.sql" Content-Transfer-Encoding: base64 RFJPUCBUQUJMRSBJRiBFWElTVFMgYSxiIENBU0NBREU7CgpDUkVBVEUgVEFCTEUgYSBBUwog IFNFTEVDVCAoKDMqZ3MpICUgMzAwKSBBUyB4LCAoKDMqZ3MrMSkgJSAzMDApIEFTIHksICgo MypncysyKSAlIDMwMCkgQVMgegogIEZST00gZ2VuZXJhdGVfc2VyaWVzKDEsMWU1KSBBUyBn czsKQ1JFQVRFIFRBQkxFIGIgQVMKICBTRUxFQ1QgZ3MgJSA0OSBBUyB4LCBncyAlIDUxIEFT IHksIGdzICU3MyBBUyB6LCAnYWJjJyB8fCBncyBBUyBwYXlsb2FkCiAgRlJPTSBnZW5lcmF0 ZV9zZXJpZXMoMSwxZTUpIEFTIGdzOwpBTkFMWVpFIGEsYjsKClNFVCBlbmFibGVfaGFzaGpv aW4gPSAnb24nOwpTRVQgZW5hYmxlX21lcmdlam9pbiA9ICdvZmYnOwoKRVhQTEFJTiAoQU5B TFlaRSwgQ09TVFMgT0ZGKQpTRUxFQ1QgKiBGUk9NIGEsYgpXSEVSRSBhLng9Yi54IEFORCBh Lnk9Yi55IEFORCBhLno9Yi56OwoKU0VUIGVuYWJsZV9tZXJnZWpvaW4gPSAnb24nOwpFWFBM QUlOIChBTkFMWVpFLCBDT1NUUyBPRkYpClNFTEVDVCAqIEZST00gYSxiCldIRVJFIGEueD1i LnggQU5EIGEueT1iLnkgQU5EIGEuej1iLno7CgovKgogICAgICAgICAgICAgICAgICAgICAg ICAgICAgICAgIFFVRVJZIFBMQU4gICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAK LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0tLS0tCiBIYXNoIEpvaW4gKGFjdHVhbCB0aW1lPTE5MS4xODMu LjE5MS4xODUgcm93cz0wIGxvb3BzPTEpCiAgIEhhc2ggQ29uZDogKChiLnggPSBhLngpIEFO RCAoYi55ID0gYS55KSBBTkQgKGIueiA9IGEueikpCiAgIC0+ICBTZXEgU2NhbiBvbiBiIChh Y3R1YWwgdGltZT0wLjAyMS4uMTcuMjY0IHJvd3M9MTAwMDAwIGxvb3BzPTEpCiAgIC0+ICBI YXNoIChhY3R1YWwgdGltZT0xMDguMDQ1Li4xMDguMDQ1IHJvd3M9MTAwMDAwIGxvb3BzPTEp CiAgICAgICAgIEJ1Y2tldHM6IDEzMTA3MiAgQmF0Y2hlczogMSAgTWVtb3J5IFVzYWdlOiA1 NjEya0IKICAgICAgICAgLT4gIFNlcSBTY2FuIG9uIGEgKGFjdHVhbCB0aW1lPTAuMDE2Li4y MC45MjMgcm93cz0xMDAwMDAgbG9vcHM9MSkKIFBsYW5uaW5nIFRpbWU6IDEuOTIxIG1zCiBF eGVjdXRpb24gVGltZTogMTkzLjQ5MSBtcwooOCByb3dzKQoKU0VUCiAgICAgICAgICAgICAg ICAgICAgICAgICAgICAgICAgUVVFUlkgUExBTiAgICAgICAgICAgICAgICAgICAgICAgICAg ICAgICAgIAotLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KIE1lcmdlIEpvaW4gKGFjdHVhbCB0aW1l PTg5OC4wMDEuLjg5OC4wMDMgcm93cz0wIGxvb3BzPTEpCiAgIE1lcmdlIENvbmQ6ICgoYi54 ID0gYS54KSBBTkQgKGIueSA9IGEueSkgQU5EIChiLnogPSBhLnopKQogICAtPiAgU29ydCAo YWN0dWFsIHRpbWU9NTQ5LjgyOS4uNjc0Ljk3MyByb3dzPTEwMDAwMCBsb29wcz0xKQogICAg ICAgICBTb3J0IEtleTogYi54LCBiLnksIGIuegogICAgICAgICBTb3J0IE1ldGhvZDogZXh0 ZXJuYWwgbWVyZ2UgIERpc2s6IDMzMjBrQgogICAgICAgICAtPiAgU2VxIFNjYW4gb24gYiAo YWN0dWFsIHRpbWU9MC4wMTguLjE2LjIwNiByb3dzPTEwMDAwMCBsb29wcz0xKQogICAtPiAg U29ydCAoYWN0dWFsIHRpbWU9MTYzLjg2NC4uMTY2LjQyMSByb3dzPTE3MDAxIGxvb3BzPTEp CiAgICAgICAgIFNvcnQgS2V5OiBhLngsIGEueSwgYS56CiAgICAgICAgIFNvcnQgTWV0aG9k OiBleHRlcm5hbCBzb3J0ICBEaXNrOiAyODQwa0IKICAgICAgICAgLT4gIFNlcSBTY2FuIG9u IGEgKGFjdHVhbCB0aW1lPTAuMDE1Li4xNC4yNjcgcm93cz0xMDAwMDAgbG9vcHM9MSkKIFBs YW5uaW5nIFRpbWU6IDEuMzk5IG1zCiBFeGVjdXRpb24gVGltZTogOTAyLjM2NyBtcwoqLw== --------------Vn1GuM7WAQipgakakPbglci9 Content-Type: text/plain; charset=UTF-8; name="fix_bucketsize.diff" Content-Disposition: attachment; filename="fix_bucketsize.diff" Content-Transfer-Encoding: base64 ZGlmZiAtLWdpdCBhL3NyYy9iYWNrZW5kL29wdGltaXplci9wYXRoL2Nvc3RzaXplLmMgYi9z cmMvYmFja2VuZC9vcHRpbWl6ZXIvcGF0aC9jb3N0c2l6ZS5jCmluZGV4IGVmNDc1ZDk1YTEu LjI2ZjI2ZDZhNDAgMTAwNjQ0Ci0tLSBhL3NyYy9iYWNrZW5kL29wdGltaXplci9wYXRoL2Nv c3RzaXplLmMKKysrIGIvc3JjL2JhY2tlbmQvb3B0aW1pemVyL3BhdGgvY29zdHNpemUuYwpA QCAtNDAzMywxMSArNDAzMywxMiBAQCBmaW5hbF9jb3N0X2hhc2hqb2luKFBsYW5uZXJJbmZv ICpyb290LCBIYXNoUGF0aCAqcGF0aCwKIAkJCQl0aGlzbWN2ZnJlcSA9IHJlc3RyaWN0aW5m by0+bGVmdF9tY3ZmcmVxOwogCQkJfQogCi0JCQlpZiAoaW5uZXJidWNrZXRzaXplID4gdGhp c2J1Y2tldHNpemUpCi0JCQkJaW5uZXJidWNrZXRzaXplID0gdGhpc2J1Y2tldHNpemU7Ci0J CQlpZiAoaW5uZXJtY3ZmcmVxID4gdGhpc21jdmZyZXEpCi0JCQkJaW5uZXJtY3ZmcmVxID0g dGhpc21jdmZyZXE7CisJCQlpbm5lcmJ1Y2tldHNpemUgKj0gdGhpc2J1Y2tldHNpemU7CisJ CQlpbm5lcm1jdmZyZXEgKj0gdGhpc21jdmZyZXE7CiAJCX0KKworCQlpZiAoaW5uZXJidWNr ZXRzaXplID4gdmlydHVhbGJ1Y2tldHMpCisJCQlpbm5lcmJ1Y2tldHNpemUgPSAxLjAgLyB2 aXJ0dWFsYnVja2V0czsKIAl9CiAKIAkvKgo= --------------Vn1GuM7WAQipgakakPbglci9--