Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1qsIxk-007V8R-H1 for pgsql-hackers@arkaria.postgresql.org; Mon, 16 Oct 2023 08:28:32 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.94.2) (envelope-from ) id 1qsIxh-00H0Mw-Bh for pgsql-hackers@arkaria.postgresql.org; Mon, 16 Oct 2023 08:28:30 +0000 Received: from magus.postgresql.org ([2a02:c0:301:0:ffff::29]) by malur.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2) (envelope-from ) id 1qsIxh-00H0Mn-0g for pgsql-hackers@lists.postgresql.org; Mon, 16 Oct 2023 08:28:29 +0000 Received: from mail.postgrespro.ru ([93.174.131.139]) by magus.postgresql.org with esmtp (Exim 4.94.2) (envelope-from ) id 1qsIxc-000vuc-Fi for pgsql-hackers@lists.postgresql.org; Mon, 16 Oct 2023 08:28:29 +0000 Received: from [10.10.20.91] (unknown [1.20.187.109]) (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 15016E20E70; Mon, 16 Oct 2023 11:28:23 +0300 (MSK) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=postgrespro.ru; s=mx2023; t=1697444905; bh=b35XQdHQDqAplAy233LmciCiDFFDoAZWKTft8S4YImU=; h=Message-ID:Date:User-Agent:Subject:To:Cc:References:From: In-Reply-To:From; b=7cg46/hpubV/Ibx2o7bqKGzg66D3mIaqBEvq5geQcC4hjFnbv+lnqY/lYKzM4nozF TQfPc8H2nl8+5Oj343m8qnmca9AGVfUUVS0+zbrdadmcx+eLRfOMZt+fofNI/Ngnpo WcXH3rsGhthfCqG24u1/YapTMM676nsnhbdVM5rXHP/Ukre32TAy5meZ8YI8v0rf2K /lkmD5mEJ+T6ivq8iydH9BAGnE6vcpr7KO0sh8r9Nd70G6HxTKJYQSYWUPbd4bzMjt iJR0hJfG/hmhwtNhEzczT+7IQWPaL/rFj3n5tS0TuAFso5HrLkn5C30tMP/2eJtCkI uLHkjDU/XPMLw== Content-Type: multipart/mixed; boundary="------------4zLk4TpDwtoWQLCFtfjqfCTV" Message-ID: <8800ccf2-ae82-461c-92a1-d4c0a22f8cf2@postgrespro.ru> Date: Mon, 16 Oct 2023 15:28:13 +0700 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird Subject: Re: Removing unneeded self joins Content-Language: en-US To: Alexander Korotkov Cc: "Gregory Stark (as CFM)" , =?UTF-8?Q?Micha=C5=82_K=C5=82eczek?= , PostgreSQL Hackers References: <64486b0b-0404-e39e-322d-0801154901f3@postgrespro.ru> <0fd15c10-eaa5-51bd-b5c7-e635fe03a94d@postgrespro.ru> <20221206184643.zya44h5auv6f45zp@awork3.anarazel.de> <36579124-f9d9-a51e-38b3-af3511921c7e@postgrespro.ru> <88079CBD-B5BB-4C61-A68B-A8C67599E1C7@kleczek.org> <05469e80-454b-41d7-d04f-421f42bbd4a9@postgrespro.ru> <48c11b23-9c23-440e-9a3c-020e05196449@postgrespro.ru> From: Andrei Lepikhov Organization: Postgres Professional In-Reply-To: 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. --------------4zLk4TpDwtoWQLCFtfjqfCTV Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit On 12/10/2023 18:32, Alexander Korotkov wrote: > On Thu, Oct 5, 2023 at 12:17 PM Andrei Lepikhov > wrote: >> On 4/10/2023 14:34, Alexander Korotkov wrote: >>> > Relid replacement machinery is the most contradictory code here. We used >>> > a utilitarian approach and implemented a simplistic variant. >>> >>> > > 2) It would be nice to skip the insertion of IS NOT NULL checks when >>> > > they are not necessary. [1] points that infrastructure from [2] might >>> > > be useful. The patchset from [2] seems committed mow. However, I >>> > > can't see it is directly helpful in this matter. Could we just skip >>> > > adding IS NOT NULL clause for the columns, that have >>> > > pg_attribute.attnotnull set? >>> > Thanks for the links, I will look into that case. >> To be more precise, in the attachment, you can find a diff to the main >> patch, which shows the volume of changes to achieve the desired behaviour. >> Some explains in regression tests shifted. So, I've made additional tests: >> >> DROP TABLE test CASCADE; >> CREATE TABLE test (a int, b int not null); >> CREATE UNIQUE INDEX abc ON test(b); >> explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a) >> WHERE t1.b=t2.b; >> CREATE UNIQUE INDEX abc1 ON test(a,b); >> explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a) >> WHERE t1.b=t2.b; >> explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a) >> WHERE t1.b=t2.b AND (t1.a=t2.a OR t2.a=t1.a); >> DROP INDEX abc1; >> explain SELECT * FROM test t1 JOIN test t2 ON (t1.a=t2.a) >> WHERE t1.b=t2.b AND (t1.b=t2.b OR t2.b=t1.b); >> >> We have almost the results we wanted to have. But in the last explain >> you can see that nothing happened with the OR clause. We should use the >> expression mutator instead of walker to handle such clauses. But It >> doesn't process the RestrictInfo node ... I'm inclined to put a solution >> of this issue off for a while. > > OK. I think it doesn't worth to eliminate IS NULL quals with this > complexity (at least at this stage of work). > > I made improvements over the code. Mostly new comments, grammar > corrections of existing comments and small refactoring. > > Also, I found that the suggestion from David Rowley [1] to qsort > array of relations to faster find duplicates is still unaddressed. > I've implemented it. That helps to evade quadratic complexity with > large number of relations. > > Also I've incorporated improvements from Alena Rybakina except one for > skipping SJ removal when no SJ quals is found. It's not yet clear for > me if this check fix some cases. But at least optimization got skipped > in some useful cases (as you can see in regression tests). I would like to propose one more minor improvement (see in attachment). The idea here is that after removing a self-join and changing clauses we should re-probe the set of relids with the same Oid, because we can find more removable self-joins (see the demo test in join.sql). -- regards, Andrey Lepikhov Postgres Professional --------------4zLk4TpDwtoWQLCFtfjqfCTV Content-Type: text/plain; charset=UTF-8; name="iterative_elimination.diff" Content-Disposition: attachment; filename="iterative_elimination.diff" Content-Transfer-Encoding: base64 ZGlmZiAtLWdpdCBhL3NyYy9iYWNrZW5kL29wdGltaXplci9wbGFuL2FuYWx5emVqb2lucy5j IGIvc3JjL2JhY2tlbmQvb3B0aW1pemVyL3BsYW4vYW5hbHl6ZWpvaW5zLmMKaW5kZXggN2I4 ZGM3YTJiNy4uZjdjY2RhNTIzMSAxMDA2NDQKLS0tIGEvc3JjL2JhY2tlbmQvb3B0aW1pemVy L3BsYW4vYW5hbHl6ZWpvaW5zLmMKKysrIGIvc3JjL2JhY2tlbmQvb3B0aW1pemVyL3BsYW4v YW5hbHl6ZWpvaW5zLmMKQEAgLTIyOTgsNiArMjI5OCw3IEBAIHJlbW92ZV9zZWxmX2pvaW5z X3JlY3Vyc2UoUGxhbm5lckluZm8gKnJvb3QsIExpc3QgKmpvaW5saXN0LCBSZWxpZHMgdG9S ZW1vdmUpCiAJCQl7CiAJCQkJLyogQ3JlYXRlIGdyb3VwIG9mIHJlbGF0aW9uIGluZGV4ZXMg d2l0aCB0aGUgc2FtZSBvaWQgKi8KIAkJCQlSZWxpZHMJCWdyb3VwID0gTlVMTDsKKwkJCQlS ZWxpZHMJCXJlbW92ZWQ7CiAKIAkJCQl3aGlsZSAoaSA8IGopCiAJCQkJewpAQCAtMjMwNiw4 ICsyMzA3LDIxIEBAIHJlbW92ZV9zZWxmX2pvaW5zX3JlY3Vyc2UoUGxhbm5lckluZm8gKnJv b3QsIExpc3QgKmpvaW5saXN0LCBSZWxpZHMgdG9SZW1vdmUpCiAJCQkJfQogCiAJCQkJcmVs aWRzID0gYm1zX2RlbF9tZW1iZXJzKHJlbGlkcywgZ3JvdXApOwotCQkJCXRvUmVtb3ZlID0g Ym1zX2FkZF9tZW1iZXJzKHRvUmVtb3ZlLAotCQkJCQkJCQkJCXJlbW92ZV9zZWxmX2pvaW5z X29uZV9ncm91cChyb290LCBncm91cCkpOworCisJCQkJLyoKKwkJCQkgKiBUcnkgdG8gcmVt b3ZlIHNlbGYtam9pbnMgZnJvbSBhIGdyb3VwIG9mIGlkZW50aWNhbCBlbnRyaWVzLgorCQkJ CSAqIE1ha2UgbmV4dCBhdHRlbXB0IGl0ZXJhdGl2ZWx5IC0gaWYgc29tZXRoaW5nIGlzIGRl bGV0ZWQgZnJvbQorCQkJCSAqIGEgZ3JvdXAsIGNoYW5nZXMgaW4gY2xhdXNlcyBhbmQgZXF1 aXZhbGVuY2UgY2xhc3NlcyBjYW4gZ2l2ZQorCQkJCSAqIHVzIGEgY2hhbmNlIHRvIGZpbmQg bW9yZSBjYW5kaWRhdGVzLgorCQkJCSAqLworCQkJCWRvIHsKKwkJCQkJQXNzZXJ0KCFibXNf b3ZlcmxhcChncm91cCwgdG9SZW1vdmUpKTsKKwkJCQkJcmVtb3ZlZCA9IHJlbW92ZV9zZWxm X2pvaW5zX29uZV9ncm91cChyb290LCBncm91cCk7CisJCQkJCXRvUmVtb3ZlID0gYm1zX2Fk ZF9tZW1iZXJzKHRvUmVtb3ZlLCByZW1vdmVkKTsKKwkJCQkJZ3JvdXAgPSBibXNfZGVsX21l bWJlcnMoZ3JvdXAsIHJlbW92ZWQpOworCQkJCX0gd2hpbGUgKCFibXNfaXNfZW1wdHkocmVt b3ZlZCkgJiYKKwkJCQkJCSBibXNfbWVtYmVyc2hpcChncm91cCkgPT0gQk1TX01VTFRJUExF KTsKKwkJCQlibXNfZnJlZShyZW1vdmVkKTsKIAkJCQlibXNfZnJlZShncm91cCk7CiAJCQl9 CiAJCQllbHNlCmRpZmYgLS1naXQgYS9zcmMvdGVzdC9yZWdyZXNzL2V4cGVjdGVkL2pvaW4u b3V0IGIvc3JjL3Rlc3QvcmVncmVzcy9leHBlY3RlZC9qb2luLm91dAppbmRleCAxMmE5MGJk NDJlLi5jYjI0Mjk2NDVjIDEwMDY0NAotLS0gYS9zcmMvdGVzdC9yZWdyZXNzL2V4cGVjdGVk L2pvaW4ub3V0CisrKyBiL3NyYy90ZXN0L3JlZ3Jlc3MvZXhwZWN0ZWQvam9pbi5vdXQKQEAg LTY3ODYsNiArNjc4NiwzNiBAQCBTRUxFQ1QgKiBGUk9NIGVtcDEgZTEsIGVtcDEgZTIgV0hF UkUgZTEuaWQgPSBlMi5pZCBBTkQgZTIuY29kZSA8PiBlMS5jb2RlOwogICAgRmlsdGVyOiAo KGUyLmlkIElTIE5PVCBOVUxMKSBBTkQgKGUyLmNvZGUgPD4gZTIuY29kZSkpCiAoMyByb3dz KQogCistLSBTaHVmZmxlIHNlbGYtam9pbmVkIHJlbGF0aW9ucy4gT25seSBpbiB0aGUgY2Fz ZSBvZiBpdGVyYXRpdmUgZGVsZXRpb24KKy0tIGF0dGVtcHRzIGV4cGxhaW5zIG9mIHRoZXNl IHF1ZXJpZXMgd2lsbCBiZSBpZGVudGljYWwuCitDUkVBVEUgVU5JUVVFIElOREVYIE9OIGVt cDEoKGlkKmlkKSk7CitleHBsYWluIFNFTEVDVCBjb3VudCgqKSBGUk9NIGVtcDEgYzEsIGVt cDEgYzIsIGVtcDEgYzMKK1dIRVJFIGMxLmlkPWMyLmlkIEFORCBjMS5pZCpjMi5pZD1jMy5p ZCpjMy5pZDsKKyAgICAgICAgICAgICAgICAgICAgICAgICAgIFFVRVJZIFBMQU4gICAgICAg ICAgICAgICAgICAgICAgICAgICAgCistLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQorIEFnZ3JlZ2F0ZSAgKGNvc3Q9 NDMuODQuLjQzLjg1IHJvd3M9MSB3aWR0aD04KQorICAgLT4gIFNlcSBTY2FuIG9uIGVtcDEg YzMgIChjb3N0PTAuMDAuLjM4LjI1IHJvd3M9MjIzNyB3aWR0aD0wKQorICAgICAgICAgRmls dGVyOiAoKGlkIElTIE5PVCBOVUxMKSBBTkQgKChpZCAqIGlkKSBJUyBOT1QgTlVMTCkpCiso MyByb3dzKQorCitleHBsYWluIFNFTEVDVCBjb3VudCgqKSBGUk9NIGVtcDEgYzEsIGVtcDEg YzIsIGVtcDEgYzMKK1dIRVJFIGMxLmlkPWMzLmlkIEFORCBjMS5pZCpjMy5pZD1jMi5pZCpj Mi5pZDsKKyAgICAgICAgICAgICAgICAgICAgICAgICAgIFFVRVJZIFBMQU4gICAgICAgICAg ICAgICAgICAgICAgICAgICAgCistLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQorIEFnZ3JlZ2F0ZSAgKGNvc3Q9NDMu ODQuLjQzLjg1IHJvd3M9MSB3aWR0aD04KQorICAgLT4gIFNlcSBTY2FuIG9uIGVtcDEgYzMg IChjb3N0PTAuMDAuLjM4LjI1IHJvd3M9MjIzNyB3aWR0aD0wKQorICAgICAgICAgRmlsdGVy OiAoKGlkIElTIE5PVCBOVUxMKSBBTkQgKChpZCAqIGlkKSBJUyBOT1QgTlVMTCkpCisoMyBy b3dzKQorCitleHBsYWluIFNFTEVDVCBjb3VudCgqKSBGUk9NIGVtcDEgYzEsIGVtcDEgYzIs IGVtcDEgYzMKK1dIRVJFIGMzLmlkPWMyLmlkIEFORCBjMy5pZCpjMi5pZD1jMS5pZCpjMS5p ZDsKKyAgICAgICAgICAgICAgICAgICAgICAgICAgIFFVRVJZIFBMQU4gICAgICAgICAgICAg ICAgICAgICAgICAgICAgCistLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQorIEFnZ3JlZ2F0ZSAgKGNvc3Q9NDMuODQu LjQzLjg1IHJvd3M9MSB3aWR0aD04KQorICAgLT4gIFNlcSBTY2FuIG9uIGVtcDEgYzMgIChj b3N0PTAuMDAuLjM4LjI1IHJvd3M9MjIzNyB3aWR0aD0wKQorICAgICAgICAgRmlsdGVyOiAo KGlkIElTIE5PVCBOVUxMKSBBTkQgKChpZCAqIGlkKSBJUyBOT1QgTlVMTCkpCisoMyByb3dz KQorCiAtLSBXZSBjYW4gcmVtb3ZlIHRoZSBqb2luIGV2ZW4gaWYgd2UgZmluZCB0aGUgam9p biBjYW4ndCBkdXBsaWNhdGUgcm93cyBhbmQKIC0tIHRoZSBiYXNlIHF1YWxzIG9mIGVhY2gg c2lkZSBhcmUgZGlmZmVyZW50LiAgSW4gdGhlIGZvbGxvd2luZyBjYXNlIHdlIGVuZCB1cAog LS0gbW92aW5nIHF1YWxzIG92ZXIgdG8gczEgdG8gbWFrZSBpdCBzbyBpdCBjYW4ndCBtYXRj aCBhbnkgcm93cy4KZGlmZiAtLWdpdCBhL3NyYy90ZXN0L3JlZ3Jlc3Mvc3FsL2pvaW4uc3Fs IGIvc3JjL3Rlc3QvcmVncmVzcy9zcWwvam9pbi5zcWwKaW5kZXggNGQ0OWMwNzY3YS4uNTUx NDcyNjNjYSAxMDA2NDQKLS0tIGEvc3JjL3Rlc3QvcmVncmVzcy9zcWwvam9pbi5zcWwKKysr IGIvc3JjL3Rlc3QvcmVncmVzcy9zcWwvam9pbi5zcWwKQEAgLTI1NzYsNiArMjU3NiwxNiBA QCBDUkVBVEUgVEFCTEUgZW1wMSAoIGlkIFNFUklBTCBQUklNQVJZIEtFWSBOT1QgTlVMTCwg Y29kZSBpbnQpOwogZXhwbGFpbiAodmVyYm9zZSwgY29zdHMgb2ZmKQogU0VMRUNUICogRlJP TSBlbXAxIGUxLCBlbXAxIGUyIFdIRVJFIGUxLmlkID0gZTIuaWQgQU5EIGUyLmNvZGUgPD4g ZTEuY29kZTsKIAorLS0gU2h1ZmZsZSBzZWxmLWpvaW5lZCByZWxhdGlvbnMuIE9ubHkgaW4g dGhlIGNhc2Ugb2YgaXRlcmF0aXZlIGRlbGV0aW9uCistLSBhdHRlbXB0cyBleHBsYWlucyBv ZiB0aGVzZSBxdWVyaWVzIHdpbGwgYmUgaWRlbnRpY2FsLgorQ1JFQVRFIFVOSVFVRSBJTkRF WCBPTiBlbXAxKChpZCppZCkpOworZXhwbGFpbiBTRUxFQ1QgY291bnQoKikgRlJPTSBlbXAx IGMxLCBlbXAxIGMyLCBlbXAxIGMzCitXSEVSRSBjMS5pZD1jMi5pZCBBTkQgYzEuaWQqYzIu aWQ9YzMuaWQqYzMuaWQ7CitleHBsYWluIFNFTEVDVCBjb3VudCgqKSBGUk9NIGVtcDEgYzEs IGVtcDEgYzIsIGVtcDEgYzMKK1dIRVJFIGMxLmlkPWMzLmlkIEFORCBjMS5pZCpjMy5pZD1j Mi5pZCpjMi5pZDsKK2V4cGxhaW4gU0VMRUNUIGNvdW50KCopIEZST00gZW1wMSBjMSwgZW1w MSBjMiwgZW1wMSBjMworV0hFUkUgYzMuaWQ9YzIuaWQgQU5EIGMzLmlkKmMyLmlkPWMxLmlk KmMxLmlkOworCiAtLSBXZSBjYW4gcmVtb3ZlIHRoZSBqb2luIGV2ZW4gaWYgd2UgZmluZCB0 aGUgam9pbiBjYW4ndCBkdXBsaWNhdGUgcm93cyBhbmQKIC0tIHRoZSBiYXNlIHF1YWxzIG9m IGVhY2ggc2lkZSBhcmUgZGlmZmVyZW50LiAgSW4gdGhlIGZvbGxvd2luZyBjYXNlIHdlIGVu ZCB1cAogLS0gbW92aW5nIHF1YWxzIG92ZXIgdG8gczEgdG8gbWFrZSBpdCBzbyBpdCBjYW4n dCBtYXRjaCBhbnkgcm93cy4K --------------4zLk4TpDwtoWQLCFtfjqfCTV--