MIME-Version: 1.0
From: Richard Guo <guofenglinux@gmail.com>
Date: Fri, 9 Dec 2022 17:16:47 +0800
Message-ID: 
 <CAMbWs48jLxn0pAPZpJ50EThZ569Xrw+=4Ac3QvkpQvNszbeoNg@mail.gmail.com>
Subject: Check lateral references within PHVs for memoize cache keys
To: PostgreSQL-development <pgsql-hackers@postgresql.org>
Content-Type: multipart/mixed; boundary="00000000000095ed7105ef619d8f"
Archived-At: 
 <https://www.postgresql.org/message-id/CAMbWs48jLxn0pAPZpJ50EThZ569Xrw%2B%3D4Ac3QvkpQvNszbeoNg%40mail.gmail.com>
Precedence: bulk

--00000000000095ed7105ef619d8f
Content-Type: multipart/alternative; boundary="00000000000095ed6f05ef619d8d"

--00000000000095ed6f05ef619d8d
Content-Type: text/plain; charset="UTF-8"

If we intend to generate a memoize node atop a path, we need some kind
of cache key.  Currently we search the path's parameterized clauses and
its parent's lateral_vars for that.  ISTM this is not sufficient because
their might be lateral references derived from PlaceHolderVars, which
can also act as cache key but we neglect to take into consideration.  As
an example, consider

create table t(a int);
insert into t values (1), (1), (1), (1);
analyze t;

explain (costs off) select * from t t1 left join lateral (select t1.a as
t1a, t2.a as t2a from t t2) s on true where s.t1a = s.t2a;
         QUERY PLAN
----------------------------
 Nested Loop
   ->  Seq Scan on t t1
   ->  Seq Scan on t t2
         Filter: (t1.a = a)
(4 rows)

We cannot find available cache keys for memoize node because the inner
side has neither parameterized path clauses nor lateral_vars.  However
if we are able to look in the PHV for lateral references, we will find
the cache key 't1.a'.

Actually we do have checked PHVs for lateral references, earlier in
create_lateral_join_info.  But that time we only marked lateral_relids
and direct_lateral_relids, without remembering the lateral expressions.
So I'm wondering whether we can fix that by fetching Vars (or PHVs) of
lateral references within PlaceHolderVars and remembering them in the
baserel's lateral_vars.

Attach a draft patch to show my thoughts.

Thanks
Richard

--00000000000095ed6f05ef619d8d
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">If we intend to generate a memoize node atop a path, we ne=
ed some kind<br>of cache key.=C2=A0 Currently we search the path&#39;s para=
meterized clauses and<br>its parent&#39;s lateral_vars for that.=C2=A0 ISTM=
 this is not sufficient because<br>their might be lateral references derive=
d from PlaceHolderVars, which<br>can also act as cache key but we neglect t=
o take into consideration.=C2=A0 As<br>an example, consider<br><br>create t=
able t(a int);<br>insert into t values (1), (1), (1), (1);<br>analyze t;<br=
><br>explain (costs off) select * from t t1 left join lateral (select t1.a =
as t1a, t2.a as t2a from t t2) s on true where s.t1a =3D s.t2a;<br>=C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0QUERY PLAN<br>----------------------------<br>=
=C2=A0Nested Loop<br>=C2=A0 =C2=A0-&gt; =C2=A0Seq Scan on t t1<br>=C2=A0 =
=C2=A0-&gt; =C2=A0Seq Scan on t t2<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Fil=
ter: (t1.a =3D a)<br>(4 rows)<br><br>We cannot find available cache keys fo=
r memoize node because the inner<br>side has neither parameterized path cla=
uses nor lateral_vars.=C2=A0 However<br>if we are able to look in the PHV f=
or lateral references, we will find<br>the cache key &#39;t1.a&#39;.<br><br=
>Actually we do have checked PHVs for lateral references, earlier in<br>cre=
ate_lateral_join_info.=C2=A0 But that time we only marked lateral_relids<br=
>and direct_lateral_relids, without remembering the lateral expressions.<br=
>So I&#39;m wondering whether we can fix that by fetching Vars (or PHVs) of=
<br>lateral references within PlaceHolderVars and remembering them in the<b=
r>baserel&#39;s lateral_vars.<br><br>Attach a draft patch to show my though=
ts.<br><br>Thanks<br>Richard<br></div>

--00000000000095ed6f05ef619d8d--

--00000000000095ed7105ef619d8f
Content-Type: application/octet-stream;
	name="v1-0001-Check-lateral-references-within-PHVs-for-memoize-.patch"
Content-Disposition: attachment;
	filename="v1-0001-Check-lateral-references-within-PHVs-for-memoize-.patch"
Content-Transfer-Encoding: base64
Content-ID: <f_lbgam4wp0>
X-Attachment-Id: f_lbgam4wp0

RnJvbSA4NDI2NjA5YjcxNmNmYzdjZDg4NDJmOGQyMmFmNGU0ZjVlMjkzNWIyIE1vbiBTZXAgMTcg
MDA6MDA6MDAgMjAwMQpGcm9tOiBSaWNoYXJkIEd1byA8Z3VvZmVuZ2xpbnV4QGdtYWlsLmNvbT4K
RGF0ZTogRnJpLCA5IERlYyAyMDIyIDEyOjA3OjE1ICswODAwClN1YmplY3Q6IFtQQVRDSCB2MV0g
Q2hlY2sgbGF0ZXJhbCByZWZlcmVuY2VzIHdpdGhpbiBQSFZzIGZvciBtZW1vaXplIGNhY2hlCiBr
ZXlzCgotLS0KIHNyYy9iYWNrZW5kL29wdGltaXplci9wbGFuL2luaXRzcGxhbi5jIHwgNTEgKysr
KysrKysrKysrKysrKysrKysrKysrKysKIHNyYy90ZXN0L3JlZ3Jlc3MvZXhwZWN0ZWQvbWVtb2l6
ZS5vdXQgIHwgMzEgKysrKysrKysrKysrKysrKwogc3JjL3Rlc3QvcmVncmVzcy9zcWwvbWVtb2l6
ZS5zcWwgICAgICAgfCAxMSArKysrKysKIDMgZmlsZXMgY2hhbmdlZCwgOTMgaW5zZXJ0aW9ucygr
KQoKZGlmZiAtLWdpdCBhL3NyYy9iYWNrZW5kL29wdGltaXplci9wbGFuL2luaXRzcGxhbi5jIGIv
c3JjL2JhY2tlbmQvb3B0aW1pemVyL3BsYW4vaW5pdHNwbGFuLmMKaW5kZXggZmQ4Y2JiMWRjNy4u
NjhmZjA5NzVkMSAxMDA2NDQKLS0tIGEvc3JjL2JhY2tlbmQvb3B0aW1pemVyL3BsYW4vaW5pdHNw
bGFuLmMKKysrIGIvc3JjL2JhY2tlbmQvb3B0aW1pemVyL3BsYW4vaW5pdHNwbGFuLmMKQEAgLTUy
MywxMiArNTIzLDQ5IEBAIGNyZWF0ZV9sYXRlcmFsX2pvaW5faW5mbyhQbGFubmVySW5mbyAqcm9v
dCkKIAkJUGxhY2VIb2xkZXJJbmZvICpwaGluZm8gPSAoUGxhY2VIb2xkZXJJbmZvICopIGxmaXJz
dChsYyk7CiAJCVJlbGlkcwkJZXZhbF9hdCA9IHBoaW5mby0+cGhfZXZhbF9hdDsKIAkJaW50CQkJ
dmFybm87CisJCUxpc3QJICAgKnZhcnM7CisJCUxpc3QJICAgKnBoX2xhdGVyYWxfdmFyczsKKwkJ
TGlzdENlbGwgICAqY2VsbDsKIAogCQlpZiAocGhpbmZvLT5waF9sYXRlcmFsID09IE5VTEwpCiAJ
CQljb250aW51ZTsJCQkvKiBQSFYgaXMgdW5pbnRlcmVzdGluZyBpZiBubyBsYXRlcmFsIHJlZnMg
Ki8KIAogCQlmb3VuZF9sYXRlcmFscyA9IHRydWU7CiAKKwkJLyogRmV0Y2ggVmFycyBhbmQgUEhW
cyBvZiBsYXRlcmFsIHJlZmVyZW5jZXMgd2l0aGluIFBsYWNlSG9sZGVyVmFycyAqLworCQl2YXJz
ID0gcHVsbF92YXJzX29mX2xldmVsKChOb2RlICopIHBoaW5mby0+cGhfdmFyLT5waGV4cHIsIDAp
OworCisJCXBoX2xhdGVyYWxfdmFycyA9IE5JTDsKKwkJZm9yZWFjaChjZWxsLCB2YXJzKQorCQl7
CisJCQlOb2RlCSAgICpub2RlID0gKE5vZGUgKikgbGZpcnN0KGNlbGwpOworCisJCQlub2RlID0g
Y29weU9iamVjdChub2RlKTsKKwkJCWlmIChJc0Eobm9kZSwgVmFyKSkKKwkJCXsKKwkJCQlWYXIJ
CSAgICp2YXIgPSAoVmFyICopIG5vZGU7CisKKwkJCQlBc3NlcnQodmFyLT52YXJsZXZlbHN1cCA9
PSAwKTsKKworCQkJCWlmIChibXNfaXNfbWVtYmVyKHZhci0+dmFybm8sIHBoaW5mby0+cGhfbGF0
ZXJhbCkpCisJCQkJCXBoX2xhdGVyYWxfdmFycyA9IGxhcHBlbmQocGhfbGF0ZXJhbF92YXJzLCBu
b2RlKTsKKwkJCX0KKwkJCWVsc2UgaWYgKElzQShub2RlLCBQbGFjZUhvbGRlclZhcikpCisJCQl7
CisJCQkJUGxhY2VIb2xkZXJWYXIgKnBodiA9IChQbGFjZUhvbGRlclZhciAqKSBub2RlOworCisJ
CQkJQXNzZXJ0KHBodi0+cGhsZXZlbHN1cCA9PSAwKTsKKworCQkJCWlmIChibXNfaXNfc3Vic2V0
KGZpbmRfcGxhY2Vob2xkZXJfaW5mbyhyb290LCBwaHYpLT5waF9ldmFsX2F0LAorCQkJCQkJCQkg
IHBoaW5mby0+cGhfbGF0ZXJhbCkpCisJCQkJCXBoX2xhdGVyYWxfdmFycyA9IGxhcHBlbmQocGhf
bGF0ZXJhbF92YXJzLCBub2RlKTsKKwkJCX0KKwkJCWVsc2UKKwkJCQlBc3NlcnQoZmFsc2UpOwor
CQl9CisKKwkJbGlzdF9mcmVlKHZhcnMpOworCiAJCWlmIChibXNfZ2V0X3NpbmdsZXRvbl9tZW1i
ZXIoZXZhbF9hdCwgJnZhcm5vKSkKIAkJewogCQkJLyogRXZhbHVhdGlvbiBzaXRlIGlzIGEgYmFz
ZXJlbCAqLwpAQCAtNTQwLDYgKzU3NywxMyBAQCBjcmVhdGVfbGF0ZXJhbF9qb2luX2luZm8oUGxh
bm5lckluZm8gKnJvb3QpCiAJCQlicmVsLT5sYXRlcmFsX3JlbGlkcyA9CiAJCQkJYm1zX2FkZF9t
ZW1iZXJzKGJyZWwtPmxhdGVyYWxfcmVsaWRzLAogCQkJCQkJCQlwaGluZm8tPnBoX2xhdGVyYWwp
OworCisJCQkvKgorCQkJICogUmVtZW1iZXIgdGhlIGxhdGVyYWwgcmVmZXJlbmNlcy4gV2UgbmVl
ZCB0aGlzIGluZm8gZm9yIHNlYXJjaGluZworCQkJICogbWVtb2l6ZSBjYWNoZSBrZXlzLgorCQkJ
ICovCisJCQlicmVsLT5sYXRlcmFsX3ZhcnMgPQorCQkJCWxpc3RfY29uY2F0KGJyZWwtPmxhdGVy
YWxfdmFycywgcGhfbGF0ZXJhbF92YXJzKTsKIAkJfQogCQllbHNlCiAJCXsKQEAgLTU1MSw2ICs1
OTUsMTMgQEAgY3JlYXRlX2xhdGVyYWxfam9pbl9pbmZvKFBsYW5uZXJJbmZvICpyb290KQogCiAJ
CQkJYnJlbC0+bGF0ZXJhbF9yZWxpZHMgPSBibXNfYWRkX21lbWJlcnMoYnJlbC0+bGF0ZXJhbF9y
ZWxpZHMsCiAJCQkJCQkJCQkJCQkJICAgcGhpbmZvLT5waF9sYXRlcmFsKTsKKworCQkJCS8qCisJ
CQkJICogUmVtZW1iZXIgdGhlIGxhdGVyYWwgcmVmZXJlbmNlcy4gV2UgbmVlZCB0aGlzIGluZm8g
Zm9yCisJCQkJICogc2VhcmNoaW5nIG1lbW9pemUgY2FjaGUga2V5cy4KKwkJCQkgKi8KKwkJCQli
cmVsLT5sYXRlcmFsX3ZhcnMgPSBsaXN0X2NvbmNhdChicmVsLT5sYXRlcmFsX3ZhcnMsCisJCQkJ
CQkJCQkJCQkgcGhfbGF0ZXJhbF92YXJzKTsKIAkJCX0KIAkJfQogCX0KZGlmZiAtLWdpdCBhL3Ny
Yy90ZXN0L3JlZ3Jlc3MvZXhwZWN0ZWQvbWVtb2l6ZS5vdXQgYi9zcmMvdGVzdC9yZWdyZXNzL2V4
cGVjdGVkL21lbW9pemUub3V0CmluZGV4IGRlNDNhZmE3NmUuLmNmMjM4NjYxZDIgMTAwNjQ0Ci0t
LSBhL3NyYy90ZXN0L3JlZ3Jlc3MvZXhwZWN0ZWQvbWVtb2l6ZS5vdXQKKysrIGIvc3JjL3Rlc3Qv
cmVncmVzcy9leHBlY3RlZC9tZW1vaXplLm91dApAQCAtOTAsNiArOTAsMzcgQEAgV0hFUkUgdDEu
dW5pcXVlMSA8IDEwMDA7CiAgIDEwMDAgfCA5LjUwMDAwMDAwMDAwMDAwMDAKICgxIHJvdykKIAor
LS0gVHJ5IHdpdGggTEFURVJBTCByZWZlcmVuY2VzIHdpdGhpbiBQbGFjZUhvbGRlclZhcnMKK1NF
TEVDVCBleHBsYWluX21lbW9pemUoJworU0VMRUNUIENPVU5UKCopLEFWRyh0MS50d2VudHkpIEZS
T00gdGVuazEgdDEgTEVGVCBKT0lOCitMQVRFUkFMIChTRUxFQ1QgdDEudHdlbnR5IGFzIGMxLCB0
Mi51bmlxdWUxIGFzIGMyIEZST00gdGVuazEgdDIpIHMgb24gdHJ1ZQorV0hFUkUgcy5jMSA9IHMu
YzIgYW5kIHQxLnVuaXF1ZTEgPCAxMDAwOycsIGZhbHNlKTsKKyAgICAgICAgICAgICAgICAgICAg
ICAgICAgICAgICAgICAgICAgZXhwbGFpbl9tZW1vaXplICAgICAgICAgICAgICAgICAgICAgICAg
ICAgICAgICAgICAgICAKKy0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t
LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KKyBBZ2dy
ZWdhdGUgKGFjdHVhbCByb3dzPTEgbG9vcHM9TikKKyAgIC0+ICBOZXN0ZWQgTG9vcCAoYWN0dWFs
IHJvd3M9MTAwMCBsb29wcz1OKQorICAgICAgICAgLT4gIFNlcSBTY2FuIG9uIHRlbmsxIHQxIChh
Y3R1YWwgcm93cz0xMDAwIGxvb3BzPU4pCisgICAgICAgICAgICAgICBGaWx0ZXI6ICh1bmlxdWUx
IDwgMTAwMCkKKyAgICAgICAgICAgICAgIFJvd3MgUmVtb3ZlZCBieSBGaWx0ZXI6IDkwMDAKKyAg
ICAgICAgIC0+ICBNZW1vaXplIChhY3R1YWwgcm93cz0xIGxvb3BzPU4pCisgICAgICAgICAgICAg
ICBDYWNoZSBLZXk6IHQxLnR3ZW50eQorICAgICAgICAgICAgICAgQ2FjaGUgTW9kZTogYmluYXJ5
CisgICAgICAgICAgICAgICBIaXRzOiA5ODAgIE1pc3NlczogMjAgIEV2aWN0aW9uczogWmVybyAg
T3ZlcmZsb3dzOiAwICBNZW1vcnkgVXNhZ2U6IE5rQgorICAgICAgICAgICAgICAgLT4gIEluZGV4
IE9ubHkgU2NhbiB1c2luZyB0ZW5rMV91bmlxdWUxIG9uIHRlbmsxIHQyIChhY3R1YWwgcm93cz0x
IGxvb3BzPU4pCisgICAgICAgICAgICAgICAgICAgICBGaWx0ZXI6ICh0MS50d2VudHkgPSB1bmlx
dWUxKQorICAgICAgICAgICAgICAgICAgICAgUm93cyBSZW1vdmVkIGJ5IEZpbHRlcjogOTk5OQor
ICAgICAgICAgICAgICAgICAgICAgSGVhcCBGZXRjaGVzOiBOCisoMTMgcm93cykKKworLS0gQW5k
IGNoZWNrIHdlIGdldCB0aGUgZXhwZWN0ZWQgcmVzdWx0cy4KK1NFTEVDVCBDT1VOVCgqKSxBVkco
dDEudHdlbnR5KSBGUk9NIHRlbmsxIHQxIExFRlQgSk9JTgorTEFURVJBTCAoU0VMRUNUIHQxLnR3
ZW50eSBhcyBjMSwgdDIudW5pcXVlMSBhcyBjMiBGUk9NIHRlbmsxIHQyKSBzIG9uIHRydWUKK1dI
RVJFIHMuYzEgPSBzLmMyIGFuZCB0MS51bmlxdWUxIDwgMTAwMDsKKyBjb3VudCB8ICAgICAgICBh
dmcgICAgICAgICAKKy0tLS0tLS0rLS0tLS0tLS0tLS0tLS0tLS0tLS0KKyAgMTAwMCB8IDkuNTAw
MDAwMDAwMDAwMDAwMAorKDEgcm93KQorCiAtLSBSZWR1Y2Ugd29ya19tZW0gYW5kIGhhc2hfbWVt
X211bHRpcGxpZXIgc28gdGhhdCB3ZSBzZWUgc29tZSBjYWNoZSBldmljdGlvbnMKIFNFVCB3b3Jr
X21lbSBUTyAnNjRrQic7CiBTRVQgaGFzaF9tZW1fbXVsdGlwbGllciBUTyAxLjA7CmRpZmYgLS1n
aXQgYS9zcmMvdGVzdC9yZWdyZXNzL3NxbC9tZW1vaXplLnNxbCBiL3NyYy90ZXN0L3JlZ3Jlc3Mv
c3FsL21lbW9pemUuc3FsCmluZGV4IDE3YzViNGJmYWIuLjUxMmM2ZGZlYmEgMTAwNjQ0Ci0tLSBh
L3NyYy90ZXN0L3JlZ3Jlc3Mvc3FsL21lbW9pemUuc3FsCisrKyBiL3NyYy90ZXN0L3JlZ3Jlc3Mv
c3FsL21lbW9pemUuc3FsCkBAIC01NSw2ICs1NSwxNyBAQCBTRUxFQ1QgQ09VTlQoKiksQVZHKHQy
LnVuaXF1ZTEpIEZST00gdGVuazEgdDEsCiBMQVRFUkFMIChTRUxFQ1QgdDIudW5pcXVlMSBGUk9N
IHRlbmsxIHQyIFdIRVJFIHQxLnR3ZW50eSA9IHQyLnVuaXF1ZTEpIHQyCiBXSEVSRSB0MS51bmlx
dWUxIDwgMTAwMDsKIAorLS0gVHJ5IHdpdGggTEFURVJBTCByZWZlcmVuY2VzIHdpdGhpbiBQbGFj
ZUhvbGRlclZhcnMKK1NFTEVDVCBleHBsYWluX21lbW9pemUoJworU0VMRUNUIENPVU5UKCopLEFW
Ryh0MS50d2VudHkpIEZST00gdGVuazEgdDEgTEVGVCBKT0lOCitMQVRFUkFMIChTRUxFQ1QgdDEu
dHdlbnR5IGFzIGMxLCB0Mi51bmlxdWUxIGFzIGMyIEZST00gdGVuazEgdDIpIHMgb24gdHJ1ZQor
V0hFUkUgcy5jMSA9IHMuYzIgYW5kIHQxLnVuaXF1ZTEgPCAxMDAwOycsIGZhbHNlKTsKKworLS0g
QW5kIGNoZWNrIHdlIGdldCB0aGUgZXhwZWN0ZWQgcmVzdWx0cy4KK1NFTEVDVCBDT1VOVCgqKSxB
VkcodDEudHdlbnR5KSBGUk9NIHRlbmsxIHQxIExFRlQgSk9JTgorTEFURVJBTCAoU0VMRUNUIHQx
LnR3ZW50eSBhcyBjMSwgdDIudW5pcXVlMSBhcyBjMiBGUk9NIHRlbmsxIHQyKSBzIG9uIHRydWUK
K1dIRVJFIHMuYzEgPSBzLmMyIGFuZCB0MS51bmlxdWUxIDwgMTAwMDsKKwogLS0gUmVkdWNlIHdv
cmtfbWVtIGFuZCBoYXNoX21lbV9tdWx0aXBsaWVyIHNvIHRoYXQgd2Ugc2VlIHNvbWUgY2FjaGUg
ZXZpY3Rpb25zCiBTRVQgd29ya19tZW0gVE8gJzY0a0InOwogU0VUIGhhc2hfbWVtX211bHRpcGxp
ZXIgVE8gMS4wOwotLSAKMi4zMS4wCgo=
--00000000000095ed7105ef619d8f--