Date: Thu, 29 Sep 2022 16:32:58 +0200
Subject: Re: disfavoring unparameterized nested loops
From: Benjamin Coutu <ben.coutu@zeyos.com>
To: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Cc: Tom Lane <tgl@sss.pgh.pa.us>,
	Robert Haas <robertmhaas@gmail.com>,
	David Rowley <dgrowleyml@gmail.com>,
	Peter Geoghegan <pg@bowt.ie>
Message-ID: <0d3f9971e82d2d969a5f@zeyos.com>
MIME-Version: 1.0
Content-Type: text/plain;
	charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Archived-At: 
 <https://www.postgresql.org/message-id/0d3f9971e82d2d969a5f%40zeyos.com>
Precedence: bulk

I'd like to revamp this important discussion.=0A=0AAs is well described in =
this fairly recent paper here https://www.vldb.org/pvldb/vol9/p204-leis.pdf=
 (which also looks at Postgres) "estimation errors quickly grow as the numb=
er of joins increases, and that these errors are usually the reason for bad=
 plans" - I think we can all get behind that statement.=0A=0AWhile nested l=
oop joins work great when cardinality estimates are correct, they are notor=
iously bad when the optimizer underestimates and they degrade very fast in =
such cases - the good vs. bad here is very asymmetric. On the other hand ha=
sh joins degrade much more gracefully - they are considered very robust aga=
inst underestimation. The above mentioned paper illustrates that all mayor =
DBMS (including Postgres) tend to underestimate and usually that underestim=
ation increases drastically with the number of joins (see Figures 3+4 of th=
e paper).=0A=0ANow, a simple approach to guarding against bad plans that ar=
ise from underestimation could be to use what I would call a nested-loop-co=
nviction-multiplier based on the current depth of the join tree, e.g. for a=
 base table that multiplier would obviously be 1, but would then grow (e.g.=
) quadratically. That conviction-multiplier would *NOT* be used to skew the=
 cardinality estimates themselves, but rather be applied to the overall nes=
ted loop join cost at each particular stage of the plan when comparing it t=
o other more robust join strategies like hash or sort-merge joins. That way=
 when we can be sure to have a good estimate at the bottom of the join tree=
 we treat all things equal, but favor nested loops less and less as we move=
 up the join tree for the sake of robustness.=0AAlso, we can expand the mul=
tiplier whenever we fall back to using the default cardinality constant as =
surely all bets are off at that point - we should definitely treat nested l=
oop joins as out of favor in this instance and that could easily be incorpo=
rated by simply increasing the conviction-mutliplier.=0A=0AWhat are your th=
oughts on this simple idea - is it perhaps too simple?=0A=0ACheers, Ben