Fix rescan costing of single-batch hash joins

Hi,

While working on a performance issue, I traced a slow plan choice to how
cost_rescan() costs a hash join on the inner side of a nested loop.

For a single-batch hash join, cost_rescan() assumes the startup cost "is
exactly the cost of hash table building" and charges nothing for it on
rescan. But that startup cost also includes the outer path's startup cost,
and ExecReScanHashJoin() reruns the outer side on every rescan. Also, the
hash table is only reused when the inner side has no changed parameters,
which the costing doesn't check. So when the hash join's input is a LATERAL
subquery with ORDER BY ... LIMIT, the sort that runs on every loop is
costed as if it ran once.

The attached repro_plain.sql shows it with a plain query, no prepared
statements. 100 groups, a LATERAL top-500 per group, joined to a 10k-row
table:

master: hash join inside the nested loop, cost 7,282, 43-60 ms
patched: nested loop + Memoize, cost 52,028, ~1.5 ms

On master the hash join costs 5,441 for its first run, but the whole
100-loop nested loop is only 7,269, so the 99 reruns are nearly free. With
a larger lookup table (1M rows) both builds pick the same plan, because the
hash join already loses the single-run comparison before rescan costing
matters. That's also in the file.

The assumption goes back to cost_rescan() itself [1], and was kept when the
multi-batch case was fixed [2]. It was close to true then. Since
parameterized paths [3] and LATERAL [4], the hash join's inputs can depend
on the outer row and really rerun every loop. Besides ORDER BY ... LIMIT, I
see the same underestimate with GROUP BY, DISTINCT and ORDER BY without
LIMIT in the LATERAL, and with SQL set-returning functions called with an
outer column, since those get inlined into a LATERAL subquery.

This matters more since SQL functions started using the plan cache in 18
[5]. After five calls the plan cache builds a generic plan and keeps it
only if its estimated cost isn't higher than the custom plans'. With the
custom plan underestimated, the generic plan never wins. This can be
reproduced end to end with the attached repro_e2e.sql: a prepared statement
and a SQL function both stay on custom plans (0 generic, 10 custom). The
custom plan is estimated at 25,565 and takes about 19 ms per call, while
the generic plan is estimated at 50,101 and takes 0.7 ms. With the patch,
both switch to generic after five calls.

The patch charges the outer path's own rescan cost on each rescan instead
of nothing, and charges the full cost when the inner path is parameterized,
since the hash table is then rebuilt every loop. It adds a test in join.sql
that changes plan without the fix. make check, contrib and isolation tests
pass, and no existing regression plans change. As a costing change it's for
master only.

This is related to, but doesn't fix, Andrei's report in [6]. There the
rescanned node is an Aggregate, so cost_rescan() never looks at the hash
join.

Patch and both repro scripts attached.

Let me know if I am missing anything.

[1]
https://git.postgresql.org/gitweb/?p=postgresql.git;a=commitdiff;h=9bb342811bf
[2]
https://git.postgresql.org/gitweb/?p=postgresql.git;a=commitdiff;h=69995c3b3fd
[3]
https://git.postgresql.org/gitweb/?p=postgresql.git;a=commitdiff;h=e2fa76d80ba
[4]
https://git.postgresql.org/gitweb/?p=postgresql.git;a=commitdiff;h=5ebaaa49445
[5]
https://git.postgresql.org/gitweb/?p=postgresql.git;a=commitdiff;h=0dca5d68d7b
[6]
https://www.postgresql.org/message-id/74632f86-2b03-4259-ac23-b837958acbb6@gmail.com

Thanks,
Baji Shaik