MIME-Version: 1.0
Date: Sat, 11 Jun 2022 23:50:49 +0000
Content-Type: multipart/mixed;
 boundary="--=_RainLoop_139_103377132.1654991449"
From: "Josh" <postgres@sirjosh3917.com>
Message-ID: <d502b53a497ec80e5d1fcd18e353e7e9@sirjosh3917.com>
Subject: Missed query planner optimization: `n in (select q)` -> `n in
 (q)`
To: pgsql-performance@postgresql.org
Archived-At: 
 <https://www.postgresql.org/message-id/d502b53a497ec80e5d1fcd18e353e7e9%40sirjosh3917.com>
Precedence: bulk


----=_RainLoop_139_103377132.1654991449
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: quoted-printable

Hey y'all!=0A=0ASo recently, I ran into an issue where a query I wrote wa=
sn't using an index, presumably because what I was doing was too hard for=
 the query planner to figure out. I've distilled the problem into its ess=
ence to the best of my ability, and found that it's because `select` seem=
s to hinder it.=0A=0AThe problem boils down to the planner not figuring o=
ut that these two queries should use an index:=0A=0A```sql=0A-- Setup=0Ac=
reate table numbers(n int);=0Ainsert into numbers (n) select generate_ser=
ies(1, 1000000);=0Acreate index numbers_n_idx on numbers(n);=0A=0A-- Non-=
indexed queries=0Aexplain analyze select numbers.n from (values (5000000)=
) quantities(q)=0Ajoin numbers on numbers.n in (select q);=0A=0Aexplain a=
nalyze select numbers.n from (values (5000000)) quantities(q)=0Ajoin numb=
ers on numbers.n =3D any(select q);=0A```=0A=0AThese examples may seem si=
lly, so let me provide a "case study" query that should justify the need =
for such an optimization. I had a query that was generating an array of i=
tems, and wanted to join it to a table given that some column of that tab=
le was present in the array. It looked like so:=0A=0A```sql=0Aselect numb=
ers.n from quantities join numbers on numbers.n in (select unnest(quantit=
ies.q));=0A```=0A=0AThis turned out to be horrendously slow, because it w=
as performing a sequential scan! I did however end up settling on the fol=
lowing form:=0A=0A```sql=0Aselect numbers.n from quantities join numbers =
on numbers.n =3D any(quantities.q);=0A```=0A=0AThis was only possible bec=
ause I was dealing with arrays though, and an operation such as `in (sele=
ct unnest...)` can be easily converted to `=3D any(...)`. However for the=
 general case, I believe an optimization in this area may provide benefit=
 as there may exist a circumstance that does not have an alternative to a=
 sub-query select (`=3D any()` was my alternative), but I am just a datab=
ase newbie.=0A=0AI've noticed this problem has been around since at least=
 11.7, and is still present as of the `postgres:15beta1` docker image. I'=
ve attached a script which reproduces the issue. It uses docker, so I'm c=
onfident you'll be able to run it without issue.=0A=0AFinally, I ask:=0A=
=0A- Is this an issue that should be fixed? I'm a database newbie so I ha=
ve no idea about the deep semantics of SQL and what a select inside a `jo=
in_condition` could imply to the planner to prevent it from optimizing it=
.=0A=0A- If "yes" to the previous question, what would be the precise sem=
antics of such an optimization? I loosely say `n in (select q)` -> `n in =
(q)` for all n and q, but of course I don't have enough knowledge to know=
 that this is correct in terms of whatever Postgres' internal query optim=
ization IR is.=0A=0A- Can a database newbie like myself contribute an opt=
imization pass in Postgres to fix this? I'm fascinated by the work y'all =
do, and submitting a patch to Postgres that makes it into production woul=
d make my week.=0A=0AThank you for your time, and have a great day!

----=_RainLoop_139_103377132.1654991449
Content-Type: application/octet-stream; name="repro.sh"
Content-Disposition: attachment; filename="repro.sh"
Content-Transfer-Encoding: base64

IyEvYmluL3NoCkNPTlRBSU5FUl9OQU1FPSQoCiAgICBkb2NrZXIgY29udGFpbmVyIHJ1biBc
CiAgICAgICAgLWQgXAogICAgICAgIC1lIFBPU1RHUkVTX0hPU1RfQVVUSF9NRVRIT0Q9dHJ1
c3QgXAogICAgICAgIHBvc3RncmVzOjE1YmV0YTEKKQoKZWNobyAiV2FpdGluZyBmb3IgZGF0
YWJhc2UgdG8gc3RhcnQgdXAiCnNsZWVwIDEKCnJ1bl9xdWVyeSgpIHsKICAgIGVjaG8gIiIK
ICAgIGVjaG8gIiQxIgogICAgZWNobyAiIgogICAgZG9ja2VyIGNvbnRhaW5lciBleGVjIC1p
dCAkQ09OVEFJTkVSX05BTUUgcHNxbCAtaCBsb2NhbGhvc3QgLVUgcG9zdGdyZXMgLWMgIiQy
Igp9CgpydW5fcXVlcnkgIkNyZWF0aW5nIGR1bW15IGRhdGEiICcKY3JlYXRlIHRhYmxlIG51
bWJlcnMobiBpbnQpOwppbnNlcnQgaW50byBudW1iZXJzIChuKSBzZWxlY3QgZ2VuZXJhdGVf
c2VyaWVzKDEsIDEwMDAwMDApOwpjcmVhdGUgaW5kZXggbnVtYmVyc19uX2lkeCBvbiBudW1i
ZXJzKG4pOwonCgpydW5fcXVlcnkgJ0luZGV4ZWQgUXVlcnk6IGluIChxKScgJwpleHBsYWlu
IGFuYWx5emUgc2VsZWN0IG51bWJlcnMubiBmcm9tICh2YWx1ZXMgKDUwMDAwMDApKSBxdWFu
dGl0aWVzKHEpIGpvaW4gbnVtYmVycyBvbiBudW1iZXJzLm4gaW4gKHEpOwonCgpydW5fcXVl
cnkgJ0luZGV4ZWQgUXVlcnk6ID0gKHNlbGVjdCBxKScgJwpleHBsYWluIGFuYWx5emUgc2Vs
ZWN0IG51bWJlcnMubiBmcm9tICh2YWx1ZXMgKDUwMDAwMDApKSBxdWFudGl0aWVzKHEpIGpv
aW4gbnVtYmVycyBvbiBudW1iZXJzLm4gPSAoc2VsZWN0IHEpOwonCgpydW5fcXVlcnkgJ1Nl
cXVlbnRpYWwgUXVlcnk6ID0gYW55KHNlbGVjdCBxKScgJwpleHBsYWluIGFuYWx5emUgc2Vs
ZWN0IG51bWJlcnMubiBmcm9tICh2YWx1ZXMgKDUwMDAwMDApKSBxdWFudGl0aWVzKHEpIGpv
aW4gbnVtYmVycyBvbiBudW1iZXJzLm4gPSBhbnkoc2VsZWN0IHEpOwonCgpydW5fcXVlcnkg
J1NlcXVlbnRpYWwgUXVlcnk6IGluIChzZWxlY3QgcSknICcKZXhwbGFpbiBhbmFseXplIHNl
bGVjdCBudW1iZXJzLm4gZnJvbSAodmFsdWVzICg1MDAwMDAwKSkgcXVhbnRpdGllcyhxKSBq
b2luIG51bWJlcnMgb24gbnVtYmVycy5uIGluIChzZWxlY3QgcSk7CicKCnJ1bl9xdWVyeSAn
Q2FzZSBTdHVkeScgJwpleHBsYWluIGFuYWx5emUgd2l0aCBxdWFudGl0aWVzKHEpIGFzICgK
CXNlbGVjdCBhcnJheVsxMDAwMDAwMCwgMTAwMDAwMCwgMTAwMDAwLCAxMDAwMCwgMTAwMCwg
MTAwLCAxMCwgMV06OmludFtdCikKc2VsZWN0IG51bWJlcnMubiBmcm9tIHF1YW50aXRpZXMg
am9pbiBudW1iZXJzIG9uIG51bWJlcnMubiBpbiAoc2VsZWN0IHVubmVzdChxdWFudGl0aWVz
LnEpKTsKJwoKZG9ja2VyIGNvbnRhaW5lciBzdG9wICRDT05UQUlORVJfTkFNRQpkb2NrZXIg
Y29udGFpbmVyIHJtICRDT05UQUlORVJfTkFNRQo=

----=_RainLoop_139_103377132.1654991449--