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/[email protected] Thanks, Baji Shaik
0001-Fix-rescan-costing-of-single-batch-hash-joins.patch
Description: Binary data
repro_e2e.sql
Description: Binary data
repro_plain.sql
Description: Binary data
