]> granicus.if.org Git - postgresql/commit
Fix ancient thinko in mergejoin cost estimation.
authorTom Lane <tgl@sss.pgh.pa.us>
Tue, 18 Dec 2018 16:19:39 +0000 (11:19 -0500)
committerTom Lane <tgl@sss.pgh.pa.us>
Tue, 18 Dec 2018 16:19:39 +0000 (11:19 -0500)
commit72a626e688ffedbdcc8d8073ac936db2f658ebb6
tree738d3dad55b9d6b8226dafa7f26b3b5ca04c3b47
parent5c96dc8f652ea6b0b9b8e224d7e6c74570767dc4
Fix ancient thinko in mergejoin cost estimation.

"rescanratio" was computed as 1 + rescanned-tuples / total-inner-tuples,
which is sensible if it's to be multiplied by total-inner-tuples or a cost
value corresponding to scanning all the inner tuples.  But in reality it
was (mostly) multiplied by inner_rows or a related cost, numbers that take
into account the possibility of stopping short of scanning the whole inner
relation thanks to a limited key range in the outer relation.  This'd
still make sense if we could expect that stopping short would result in a
proportional decrease in the number of tuples that have to be rescanned.
It does not, however.  The argument that establishes the validity of our
estimate for that number is independent of whether we scan all of the inner
relation or stop short, and experimentation also shows that stopping short
doesn't reduce the number of rescanned tuples.  So the correct calculation
is 1 + rescanned-tuples / inner_rows, and we should be sure to multiply
that by inner_rows or a corresponding cost value.

Most of the time this doesn't make much difference, but if we have
both a high rescan rate (due to lots of duplicate values) and an outer
key range much smaller than the inner key range, then the error can
be significant, leading to a large underestimate of the cost associated
with rescanning.

Per report from Vijaykumar Jain.  This thinko appears to go all the way
back to the introduction of the rescan estimation logic in commit
70fba7043, so back-patch to all supported branches.

Discussion: https://postgr.es/m/CAE7uO5hMb_TZYJcZmLAgO6iD68AkEK6qCe7i=vZUkCpoKns+EQ@mail.gmail.com
src/backend/optimizer/path/costsize.c