Content-Type: multipart/mixed; boundary="------------DjRSRGkh6iApmzN68q7arihX"
Message-ID: <95586c5d-2632-4f1c-bfb9-4c391f260de4@gmail.com>
Date: Wed, 19 Mar 2025 18:15:54 +0100
MIME-Version: 1.0
User-Agent: Mozilla Thunderbird
Subject: Re: Memoize ANTI and SEMI JOIN inner
From: Andrei Lepikhov <lepihov@gmail.com>
To: PostgreSQL-development <pgsql-hackers@postgresql.org>
References: <60bf8d26-7c7e-4915-b544-afdb9020011d@gmail.com>
Content-Language: en-US
In-Reply-To: <60bf8d26-7c7e-4915-b544-afdb9020011d@gmail.com>
Archived-At: 
 <https://www.postgresql.org/message-id/95586c5d-2632-4f1c-bfb9-4c391f260de4%40gmail.com>
Precedence: bulk

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

On 6/3/2025 14:08, Andrei Lepikhov wrote:
> Hi,
> 
> In case of NestLoop with parameterised inner semi-join for each outer 
> tuple requires only a single tuple from its inner relation to produce a 
> result. It seems that the same principle applies to an anti-join. This 
> approach could effectively allow the Memoize node to enhance the 
> performance of pulled-up EXISTS and NOT EXISTS sublinks.
> 
> In attachment see a sketch of the feature. Since we are using single_row 
> mode, adapting this method to cache semi-join inner results should not 
> be extremely complex. However, I am unsure about potential corner cases 
> and would appreciate any feedback or criticisms regarding this approach.
I found a corner case that breaks this approach: when NestLoop has a 
join clause or a filter, it may filter inner tuples, thus scanning more 
than only one time for each outer. You can see the reproduction script 
in the attachment. Each of the reproduction queries throws the error:
ERROR: cache entry already complete

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.

-- 
regards, Andrei Lepikhov
--------------DjRSRGkh6iApmzN68q7arihX
Content-Type: application/sql; name="repro.sql"
Content-Disposition: attachment; filename="repro.sql"
Content-Transfer-Encoding: base64

Q1JFQVRFIFRBQkxFIG1lbV9zZW1pX2lubmVyX2EgKHggaW50KTsKQ1JFQVRFIFRBQkxFIG1l
bV9zZW1pX2lubmVyX2IgKHggaW50LCB5IGludCk7CkNSRUFURSBUQUJMRSBtZW1fc2VtaV9p
bm5lcl9jICh4IGludCwgeSBpbnQpOwpJTlNFUlQgSU5UTyBtZW1fc2VtaV9pbm5lcl9hICh4
KQogIChTRUxFQ1QgdmFsdWUlMiBGUk9NIGdlbmVyYXRlX3NlcmllcygxLDEwKSBBUyB2YWx1
ZSk7CklOU0VSVCBJTlRPIG1lbV9zZW1pX2lubmVyX2IgKHgseSkKICAoU0VMRUNUIHZhbHVl
JTUsIC12YWx1ZSU1LTEgRlJPTSBnZW5lcmF0ZV9zZXJpZXMoMSwxMCkgQVMgdmFsdWUpOwpJ
TlNFUlQgSU5UTyBtZW1fc2VtaV9pbm5lcl9jICh4LHkpCiAgKFNFTEVDVCB2YWx1ZSU1MCwg
dmFsdWUgRlJPTSBnZW5lcmF0ZV9zZXJpZXMoMSwxMDApIEFTIHZhbHVlKTsKQ1JFQVRFIElO
REVYIE9OIG1lbV9zZW1pX2lubmVyX2IoeCk7CkNSRUFURSBJTkRFWCBPTiBtZW1fc2VtaV9p
bm5lcl9jKHgpOwpWQUNVVU0gQU5BTFlaRSBtZW1fc2VtaV9pbm5lcl9hLG1lbV9zZW1pX2lu
bmVyX2IsbWVtX3NlbWlfaW5uZXJfYzsKCi0tIEZvcmNlIE5lc3RMb29wIGFuZCBJbmRleFNj
YW4uIEhvcGUsIHRoZSBNZW1vaXplIG5vZGUgd2luIHRoZSBjb3N0Ci0tIGNvbXBldGl0aW9u
IG9uIHRoZSBpbm5lciBjIHRhYmxlIHNjYW4uClNFVCBlbmFibGVfaGFzaGpvaW4gPSAnb2Zm
JzsKU0VUIGVuYWJsZV9tZXJnZWpvaW4gPSAnb2ZmJzsKU0VUIGVuYWJsZV9zZXFzY2FuID0g
J29mZic7CgotLSBUaGUgdGVzdCBuZWVkcyB0aGUgTWVtb2l6ZSBub2RlIG92ZXIgdGhlICJT
Y2FuIGMiIG9wZXJhdG9yLgpFWFBMQUlOIChBTkFMWVpFLCBDT1NUUyBPRkYpClNFTEVDVCBh
LngsIGIueCBGUk9NIG1lbV9zZW1pX2lubmVyX2EgYQogIExFRlQgSk9JTiBtZW1fc2VtaV9p
bm5lcl9iIGIgT04gKGEueD1iLngpCldIRVJFIE5PVCBFWElTVFMgKAogIFNFTEVDVCAxIEZS
T00gbWVtX3NlbWlfaW5uZXJfYyBjIFdIRVJFIGMueD1hLnggQU5EIGMueT1iLnkpOwoKLS0g
VGhlIHRlc3QgbmVlZHMgdGhlIE1lbW9pemUgbm9kZSBvdmVyIHRoZSAiU2NhbiBjIiBvcGVy
YXRvci4KRVhQTEFJTiAoQU5BTFlaRSwgQ09TVFMgT0ZGKQpTRUxFQ1QgYS54LCBiLnggRlJP
TSBtZW1fc2VtaV9pbm5lcl9hIGEKICBMRUZUIEpPSU4gbWVtX3NlbWlfaW5uZXJfYiBiIE9O
IChhLng9Yi54KQpXSEVSRSBFWElTVFMgKAogIFNFTEVDVCAxIEZST00gbWVtX3NlbWlfaW5u
ZXJfYyBjIFdIRVJFIGMueD1hLnggQU5EIGMueT1iLnkpOwpEUk9QIFRBQkxFIG1lbV9zZW1p
X2lubmVyX2EsbWVtX3NlbWlfaW5uZXJfYixtZW1fc2VtaV9pbm5lcl9jOw==

--------------DjRSRGkh6iApmzN68q7arihX--