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 1tz4zL-00EjEN-Qn for pgsql-hackers@arkaria.postgresql.org; Mon, 31 Mar 2025 02:35:00 +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 1tz4yJ-00GJWc-RO for pgsql-hackers@arkaria.postgresql.org; Mon, 31 Mar 2025 02:33:55 +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 1tz4yJ-00GJWU-AX for pgsql-hackers@lists.postgresql.org; Mon, 31 Mar 2025 02:33:55 +0000 Received: from mail.postgrespro.ru ([93.174.132.70]) by magus.postgresql.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.96) (envelope-from ) id 1tz4yG-0029K5-0X for pgsql-hackers@postgresql.org; Mon, 31 Mar 2025 02:33:54 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=postgrespro.ru; s=mx2023; t=1743388430; bh=PhkcZ4JnT0ProxuRICkuYC3XVFbuL7Qoxa7s5rhmrcA=; h=Message-ID:Date:User-Agent:Subject:To:Cc:References:From: In-Reply-To:From; b=JYADa0GtfNnftFDQVZlbNkwVpHjScxDTTfi7Wz1gKXGFLjB4E3kYYrERga3mgT2aR Vd/GGB6EYxGxCzTAs0DCzM2Q4TTKQo8fiM5OkWNDcEOpXgvcPS6+n4RRReqmg0C2PO +HOXrpTBvwyXtBDERoVIsdn4Ch9fuNR11DnIk1ZdIrVz0XK97BN7sfhBx1fIQW1mSp OMFRzoYAJmzlAnMwhM2S09fFF/ek8F/gdUjdZ/RK88v5/AdITCY/9HJZpcO8pAKchV YfCyy2x3iR7a5jQ4h+cbBFq2mPbkWRodWXKlub7sr5BumYOinHHwRubVEmI05V/hZb 38iEEIhbu7RaA== Received: from [172.30.48.74] (unknown [93.174.131.138]) (using TLSv1.3 with cipher TLS_AES_128_GCM_SHA256 (128/128 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (Client did not present a certificate) (Authenticated sender: a.rybakina@postgrespro.ru) by mail.postgrespro.ru (Postfix/587) with ESMTPSA id 1FFDA60363; Mon, 31 Mar 2025 05:33:50 +0300 (MSK) Content-Type: multipart/mixed; boundary="------------5frCZXa9xZPKpVNNUQHuD0CJ" Message-ID: <26e6dd23-ad56-4e00-8a24-c84b508267aa@postgrespro.ru> Date: Mon, 31 Mar 2025 05:33:49 +0300 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird Subject: Re: Memoize ANTI and SEMI JOIN inner To: Andrei Lepikhov Cc: David Rowley , PostgreSQL-development References: <60bf8d26-7c7e-4915-b544-afdb9020011d@gmail.com> <95586c5d-2632-4f1c-bfb9-4c391f260de4@gmail.com> Content-Language: en-US From: Alena Rybakina In-Reply-To: X-KSMG-AntiPhishing: NotDetected, bases: 2025/03/31 01:25:00 X-KSMG-AntiSpam-Interceptor-Info: not scanned X-KSMG-AntiSpam-Status: not scanned, disabled by settings X-KSMG-AntiVirus: Kaspersky Secure Mail Gateway, version 2.1.0.7854, bases: 2025/03/31 01:22:00 #27841732 X-KSMG-AntiVirus-Status: NotDetected, skipped X-KSMG-LinksScanning: not scanned, disabled by settings X-KSMG-Message-Action: skipped X-KSMG-Rule-ID: 1 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. --------------5frCZXa9xZPKpVNNUQHuD0CJ Content-Type: multipart/alternative; boundary="------------QMv6gBHA5XjGf20cq7sCdN6P" --------------QMv6gBHA5XjGf20cq7sCdN6P Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Hi! On 21.03.2025 18:56, Andrei Lepikhov wrote: > On 20/3/2025 07:02, David Rowley wrote: >> On Thu, 20 Mar 2025 at 06:16, Andrei Lepikhov wrote: >>> How can we be sure that semi or anti-join needs only one tuple? I think >>> it would be enough to control the absence of join clauses and >>> filters in >>> the join. Unfortunately, we only have such a guarantee in the plan >>> creation stage (maybe even setrefs.c). So, it seems we need to >>> invent an >>> approach like AlternativeSubplan. >> >> I suggest looking at what 9e215378d did.  You might be able to also >> allow semi and anti-joins providing the cache keys cover the entire >> join condition. I think this might be safe as Nested Loop will only >> ask its inner subnode for the first match before skipping to the next >> outer row and with anti-join, there's no reason to look for additional >> rows after the first. Semi-join and unique joins do the same thing in >> nodeNestloop.c. To save doing additional checks at run-time, the code >> does: > Thank you for the clue! I almost took the wrong direction. > I have attached the new patch, which includes corrected comments for > better clarification of the changes, as well as some additional tests. > I now feel much more confident about this version since I have > resolved that concern. > I reviewed your patch and made a couple of suggestions. The first change is related to your comment (and the one before it). I fixed some grammar issues and simplified the wording to make it clearer and easier to understand. The second change involves adding an Assert when generating the Memoize path. Based on the existing comment and the surrounding logic (shown below), I believe it's worth asserting that both inner_unique and single_mode are not true at the same time — just as a safety check. /* * We may do this for SEMI or ANTI joins when they need only one tuple from * the inner side to produce the result. Following if condition checks that * rule. * * XXX Currently we don't attempt to mark SEMI/ANTI joins as inner_unique * = true. Should we? See add_paths_to_joinrel() */ if(!extra->inner_unique&& (jointype== JOIN_SEMI|| jointype== JOIN_ANTI)) single_mode= true; -- Regards, Alena Rybakina Postgres Professional --------------QMv6gBHA5XjGf20cq7sCdN6P Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: 8bit

Hi!

On 21.03.2025 18:56, Andrei Lepikhov wrote:
On 20/3/2025 07:02, David Rowley wrote:
On Thu, 20 Mar 2025 at 06:16, Andrei Lepikhov <lepihov@gmail.com> wrote:
How can we be sure that semi or anti-join needs only one tuple? I think
it would be enough to control the absence of join clauses and filters in
the join. Unfortunately, we only have such a guarantee in the plan
creation stage (maybe even setrefs.c). So, it seems we need to invent an
approach like AlternativeSubplan.

I suggest looking at what 9e215378d did.  You might be able to also
allow semi and anti-joins providing the cache keys cover the entire
join condition. I think this might be safe as Nested Loop will only
ask its inner subnode for the first match before skipping to the next
outer row and with anti-join, there's no reason to look for additional
rows after the first. Semi-join and unique joins do the same thing in
nodeNestloop.c. To save doing additional checks at run-time, the code
does:
Thank you for the clue! I almost took the wrong direction.
I have attached the new patch, which includes corrected comments for better clarification of the changes, as well as some additional tests.
I now feel much more confident about this version since I have resolved that concern.


I reviewed your patch and made a couple of suggestions.

The first change is related to your comment (and the one before it). I fixed some grammar issues and simplified the wording to make it clearer and easier to understand.

The second change involves adding an Assert when generating the Memoize path. Based on the existing comment and the surrounding logic (shown below),
I believe it's worth asserting that both inner_unique and single_mode are not true at the same time — just as a safety check.
/*
* We may do this for SEMI or ANTI joins when they need only one tuple from
* the inner side to produce the result. Following if condition checks that
* rule.
*
* XXX Currently we don't attempt to mark SEMI/ANTI joins as inner_unique
* = true. Should we? See add_paths_to_joinrel()
*/
if (!extra->inner_unique && (jointype == JOIN_SEMI ||
jointype == JOIN_ANTI))
single_mode = true;

-- 
Regards,
Alena Rybakina
Postgres Professional
--------------QMv6gBHA5XjGf20cq7sCdN6P-- --------------5frCZXa9xZPKpVNNUQHuD0CJ Content-Type: text/x-patch; charset=UTF-8; name="memoize.diff" Content-Disposition: attachment; filename="memoize.diff" Content-Transfer-Encoding: base64 ZGlmZiAtLWdpdCBhL3NyYy9iYWNrZW5kL29wdGltaXplci9wYXRoL2pvaW5wYXRoLmMgYi9z cmMvYmFja2VuZC9vcHRpbWl6ZXIvcGF0aC9qb2lucGF0aC5jCmluZGV4IGM3NTQwOGY1NTJi Li4yNTJjYjcxMjk0MyAxMDA2NDQKLS0tIGEvc3JjL2JhY2tlbmQvb3B0aW1pemVyL3BhdGgv am9pbnBhdGguYworKysgYi9zcmMvYmFja2VuZC9vcHRpbWl6ZXIvcGF0aC9qb2lucGF0aC5j CkBAIC03MjgsMTQgKzcyOCwxNiBAQCBnZXRfbWVtb2l6ZV9wYXRoKFBsYW5uZXJJbmZvICpy b290LCBSZWxPcHRJbmZvICppbm5lcnJlbCwKIAkJc2luZ2xlX21vZGUgPSB0cnVlOwogCiAJ LyoKLQkgKiBNZW1vaXplIG5vcm1hbGx5IG1hcmtzIGNhY2hlIGVudHJpZXMgYXMgY29tcGxl dGUgd2hlbiBpdCBydW5zIG91dCBvZgotCSAqIHR1cGxlcyB0byByZWFkIGZyb20gaXRzIHN1 YnBsYW4uICBIb3dldmVyLCB3aXRoIHVuaXF1ZSBqb2lucywgTmVzdGVkCi0JICogTG9vcCB3 aWxsIHNraXAgdG8gdGhlIG5leHQgb3V0ZXIgdHVwbGUgYWZ0ZXIgZmluZGluZyB0aGUgZmly c3QgbWF0Y2hpbmcKLQkgKiBpbm5lciB0dXBsZS4gQW5vdGhlciBjYXNlIGlzIGEgc2VtaSBv ciBhbnRpIGpvaW4uIElmIG51bWJlciBvZiBqb2luCi0JICogY2xhdXNlcywgcHVzaGVkIHRv IHRoZSBpbm5lciBhcyBwYXJhbWV0ZXJpc2VkIGZpbHRlciBubyBsZXNzIHRoYW4gdGhlCi0J ICogbnVtYmVyIG9mIGpvaW4gY2xhdXNlcywgdGhhdCBtZWFucyBhbGwgdGhlIGNsYXVzZXMg aGF2ZSBiZWVuIHB1c2hlZCB0bwotCSAqIHRoZSBpbm5lciBhbmQgYW55IHR1cGxlIGNvbWlu ZyBmcm9tIHRoZSBpbm5lciBzaWRlIHdpbGwgYmUgc3VjY2Vzc2Z1bGx5Ci0JICogdXNlZCB0 byBidWlsZCB0aGUgam9pbiByZXN1bHQuCisJICogTm9ybWFsbHksIG1lbW9pemUgbWFya3Mg Y2FjaGUgZW50cmllcyBhcyBjb21wbGV0ZSB3aGVuIGl0IGV4aGF1c3RzCisJICogYWxsIHR1 cGxlcyBmcm9tIGl0cyBzdWJwbGFuLiAgSG93ZXZlciwgaW4gdW5pcXVlIGpvaW5zLCBOZXN0 ZWQgTG9vcAorCSAqIHdpbGwgc2tpcCB0byB0aGUgbmV4dCBvdXRlciB0dXBsZSBhZnRlciBm aW5kaW5nIHRoZSBmaXJzdCBtYXRjaGluZworCSAqIGlubmVyIHR1cGxlLgorCSAqIEFub3Ro ZXIgY2FzZSBpcyBhIFNFTUkgb3IgQU5USSBqb2lucy4gSWYgdGhlIG51bWJlciBvZiBqb2lu IGNsYXVzZXMsCisJICogcHVzaGVkIHRvIHRoZSBpbm5lciBhcyBwYXJhbWV0ZXJpc2VkIGZp bHRlciBpcyBlcXVhbCB0byBvciBncmVhdGVyCisJICogdGhhbiB0aGUgdG90YWwgbnVtYmVy IG9mIGpvaW4gY2xhdXNlcy4gVGhpcyBpbXBsaWVzIHRoYXQgYWxsIHJlbGV2YW50CisJICog am9pbiBjb25kaXRpb25zIGhhdmUgYmVlbiBhcHBsaWVkIG9uIHRoZSBpbm5lciBzaWRlLCBz byBhbnkgcmV0dXJuZWQKKwkgKiBpbm5lciB0dXBsZSB3aWxsIGJlIGd1YXJhbnRlZWQgdG8g c2F0aXNmeSB0aGUgam9pbiBjb25kaXRpb24sIG1ha2luZworCSAqIGl0IHNhZmUgdG8gbWVt b2l6ZS4KIAkgKiBUaGlzIG1lYW5zIHRoYXQgd2UgbWF5IG5vdCByZWFkIHRoZSBpbm5lciBz aWRlIG9mIHRoZQogCSAqIGpvaW4gdG8gY29tcGxldGlvbiB3aGljaCBsZWF2ZXMgbm8gb3Bw b3J0dW5pdHkgdG8gbWFyayB0aGUgY2FjaGUgZW50cnkKIAkgKiBhcyBjb21wbGV0ZS4gIFRv IHdvcmsgYXJvdW5kIHRoYXQsIHdoZW4gdGhlIGpvaW4gaXMgdW5pcXVlIHdlCkBAIC04MDgs NiArODEwLDggQEAgZ2V0X21lbW9pemVfcGF0aChQbGFubmVySW5mbyAqcm9vdCwgUmVsT3B0 SW5mbyAqaW5uZXJyZWwsCiAJCQkJCQkJCQkmaGFzaF9vcGVyYXRvcnMsCiAJCQkJCQkJCQkm YmluYXJ5X21vZGUpKQogCXsKKwkJQXNzZXJ0KCEoZXh0cmEtPmlubmVyX3VuaXF1ZSAmJiBz aW5nbGVfbW9kZSkpOworCiAJCXJldHVybiAoUGF0aCAqKSBjcmVhdGVfbWVtb2l6ZV9wYXRo KHJvb3QsCiAJCQkJCQkJCQkJCWlubmVycmVsLAogCQkJCQkJCQkJCQlpbm5lcl9wYXRoLAo= --------------5frCZXa9xZPKpVNNUQHuD0CJ--