BUG #19708: Hash Join becomes about 300x slower with higher work_mem
The following bug has been logged on the website:
Bug reference: 19708
Logged by: iany
Email address: yanarnold5@gmail.com
PostgreSQL version: 18.6
Operating system: Ubuntu 22.04
Description:
Reproduced on PostgreSQL master 20devel, commit
9e17d25e79d4756be08b4a5521b4b58450217137.
Source build used --without-readline --without-zlib.
Reproducer (run with psql -X):
CREATE TABLE a();
INSERT INTO a DEFAULT VALUES;
SET enable_mergejoin = off;
SET work_mem = '64kB';
EXPLAIN (ANALYZE, TIMING OFF, SUMMARY ON)
WITH x AS (
SELECT g
FROM a a1, a a2, generate_series(1,768) g
)
SELECT l.g
FROM x l
JOIN x r USING (g);
SET work_mem = '16MB';
EXPLAIN (ANALYZE, TIMING OFF, SUMMARY ON)
WITH x AS (
SELECT g
FROM a a1, a a2, generate_series(1,768) g
)
SELECT l.g
FROM x l
JOIN x r USING (g);
Observed runtimes on master:
work_mem runtime
64kB 0.0248s
256kB 0.1290s
1MB 6.8825s
16MB 7.8372s
All executions returned the same 768 rows. Increasing work_mem from 64kB to
16MB made the query approximately 315x slower.
Could you please confirm whether this degree of slowdown as work_mem
increases is expected for the same Hash Join and cardinality estimate?
At 1MB, EXPLAIN ANALYZE reported 4,194,304 original/final hash buckets and
4,096 original/final hash batches.
This appears related to the earlier "Fix overflow of nbatch"
discussion.[/messages/by-id/244dc6c1-3b3d-4de2-b3de-b1511e6a6d10@vondra.me]
That discussion noted that initial nbatch can increase with work_mem but
considered it probably harmless because runtime batching could compensate.
Runtime batch growth does not occur in this case.
Hi Iany,
Thank you for the report, and the nice reproduction script.
Your query grows with the 4th power of the number of rows, and the table
statistics
show 2910 rows for that table. So the plan estimates 211 quadrillion rows,
see
a decluttered plan showing the row estimates.
Hash Join (rows=211477613278003200) -- (m * n^2)^2 / (200)
Hash Cond: (l.g = r.g)
CTE x
-> Nested Loop (rows=6503500800) -- m * n ^2
-> Function Scan on generate_series g (rows=768) -- m
-> Materialize (rows=8468100) -- n^2
-> Nested Loop (rows=8468100) -- n^2
-> Seq Scan on a a1 (rows=2910) -- n
-> Materialize (rows=2910) -- n
-> Seq Scan on a a2 (rows=2910) -- n
-> CTE Scan on x l (rows=6503500800) -- m * n^2
-> Hash (rows=6503500800) -- m * n^2
-> CTE Scan on x r (rows=6503500800) -- m * n ^ 2
CREATE TABLE a();
INSERT INTO a DEFAULT VALUES;
If you run an analyse here you get an accurate estimate of the number rows
in the table.
If analyse your table before the table
----
CREATE TABLE a();
INSERT INTO a DEFAULT VALUES;
+ANALYSE a;
SET enable_mergejoin = off;
----
It uses the same plan
work_mem exec time
64 kB 0.271 ms
16 MB 0.227 ms
Would you be able to reproduce the issue having rows = actual rows in the
plans.
--
Alexandre
Hi,
Thank you for the report, and I am able to reproduce it.
The loop added by a1b4f289bee is fine when the estimate holds. Buckets are
about a seventh of the budget and every batch is full, so clearing them is
noise. The trouble is that the array is sized from work_mem while the number
of non empty batches saturates at the real row count, so the waste scales
with work_mem times real rows, not with the data. Your query estimates 6.5
billion inner rows and gets 768. At 256MB that is 69GB of memset, where a
profile spends 84 percent of its time, up from 8 percent at 64kB.
ANALYZE does fix your case, worth saying. But the mechanism does not need
stale statistics. Join selectivity multiplies, so a
moderate error on one relation becomes a large one after a few joins. Your
unanalyzed table is off by 2910x and the self join squares that to 8.5
million. A thousandfold overestimate is already enough to show this, which
is ordinary for a join of several tables with correlated columns.
Before a1b4f289bee the time does not move with work_mem at all. I measured
153 ms at every setting from 64kB to 16MB.
Median of 6 runs on master, and with the attached patch:
Attached flame.zip shows the flame graph of these experiments.
work_mem master patched Buckets Batches
64kB 45 ms 262144 256
64MB 327 ms 64 ms 4194304 4096
128MB 461 ms 59 ms 8388608 2048
256MB 709 ms 54 ms 16777216 1024
The patch redoes the sizing decision once the inner side has been read,
using
the real row count. If it now fits in one batch it rebuilds the table that
way and reads the spilled tuples back. Changing nbuckets is safe there
because a single batch no longer takes the batch number from the bits above
log2_nbuckets.
It only shrink to one batch. Shrinking to fewer batches also works, since
the batch
number is the same rotated value under a narrower mask, so old batch i
merges
into new batch i & (new - 1) and nothing is rehashed. But nbuckets is
frozen then,
because moving it changes every batch number, so that path only speed up
and
not reduce any memory footprint.
Thanks,
Shihao
Alexandre Felipe <o.alexandre.felipe@gmail.com> writes:
Your query grows with the 4th power of the number of rows, and the table
statistics show 2910 rows for that table.
Actually there aren't any statistics. Rather than trust the observed
fact that the table is of size zero, the planner assumes it's 10
pages, and then 2910 rows is what could be expected to fit with
zero-column rows. (The alternative of trusting the table to be empty
is not better: it leads to planning failures in the other direction
where we make a plan for trivial amounts of data and then it runs
forever because there's more data than the planner thought.)
So the plan estimates 211 quadrillion rows,
Yeah. Specifically, the CTE is estimated to produce 2910*2910*768
rows, and then the planner thinks it's dealing with a darn big hash
join, so it instructs the executor to set up for that:
-> Hash (cost=130070016.00..130070016.00 rows=6503500800 width=4) (actual time=5.853..5.853 rows=768.00 loops=1)
Buckets: 4194304 Batches: 4096 Memory Usage: 32768kB
It's the overhead of setting up and tearing down all those batches
that is making the query take so long. (If you don't suppress the
timing figures, you'll see that that overhead is charged to the Hash
Join node not the Hash node, which is a bit of an implementation
artifact.) If we actually did have that much data to contend with,
of course the setup overhead would be negligible, but with a trivial
amount of actual data it dominates the runtime. Reducing work_mem
reduces this overhead by constraining how much memory the executor
is allowed to allocate --- but that would be a pretty bad idea if
there actually were a lot of rows to join.
If you run an analyse here you get an accurate estimate of the number rows
in the table.
Indeed. So I think this is an uninteresting contrived case.
regards, tom lane
Indeed. So I think this is an uninteresting contrived case.
I agree the reproducer is contrived, and that assuming
10 pages for a never vacuumed table is the right call.
My concern is that ANALYZE does not always get us out of it. The
n_distinct estimator is known to undershoot on long tailed columns.
I did a mini benchmark:
Take a 5M row orders table where half the rows come from 1000 big customers
and half from one time customers. Right after ANALYZE it gets n_distinct
31846, against a true value of 2.5M. A join of two such tables is
estimated at 780M rows and returns 2.5M. That is one join, and each
further join multiplies the error.
So the same shape comes out of fresh statistics on an ordinary schema,
and the extra cost only appeared in 18. That is why I think it is worth
handling.
Thanks,
Shihao
On Tue, Sep 22, 2026 at 12:31 AM shihao zhong <zhong950419@gmail.com> wrote:
Indeed. So I think this is an uninteresting contrived case.
I agree the reproducer is contrived, and that assuming
10 pages for a never vacuumed table is the right call.My concern is that ANALYZE does not always get us out of it. The
n_distinct estimator is known to undershoot on long tailed columns.I did a mini benchmark:
Take a 5M row orders table where half the rows come from 1000 big
customers
and half from one time customers. Right after ANALYZE it gets n_distinct
31846, against a true value of 2.5M. A join of two such tables is
estimated at 780M rows and returns 2.5M. That is one join, and each
further join multiplies the error.
True, that sort of error should compound over multiple joins, and so the
number
of rows.
Could you include your script?
So the same shape comes out of fresh statistics on an ordinary schema,
and the extra cost only appeared in 18. That is why I think it is worth
handling.
Regards,
Alexandre
Hi Alexandre,
Here it is. Two tables of 5M rows. Half the rows come from 1000 repeat
customers and half from one time customers. The repeat customers are
different people in the two tables, so the join returns the one time matches
only.
DROP TABLE IF EXISTS orders, tickets;
CREATE TABLE orders AS
SELECT CASE WHEN g % 2 = 0 THEN (g / 2) % 1000 + 1
ELSE 1000000 + g END AS customer_id,
g AS order_id
FROM generate_series(1, 5000000) g;
CREATE TABLE tickets AS
SELECT CASE WHEN g % 2 = 0 THEN (g / 2) % 1000 + 2001
ELSE 1000000 + g END AS customer_id,
g AS ticket_id
FROM generate_series(1, 5000000) g;
ANALYZE orders, tickets;
SET max_parallel_workers_per_gather = 0;
SET enable_mergejoin = off;
SET enable_nestloop = off;
EXPLAIN (ANALYZE, TIMING OFF, BUFFERS OFF)
SELECT count(*) FROM orders o JOIN tickets t USING (customer_id);
n_distinct comes out at 31626 for orders and 31744 for tickets, against a
true value of 2501000 for both. The plan:
Aggregate (actual rows=1.00 loops=1)
-> Hash Join (cost=154176.00..36256745.52 rows=783432952 width=0)
(actual rows=2500000.00 loops=1)
Hash Cond: (o.customer_id = t.customer_id)
-> Seq Scan on orders o (cost=0.00..72144.00 rows=5000000
width=4) (actual rows=5000000.00 loops=1)
-> Hash (cost=72144.00..72144.00 rows=5000000 width=4) (actual
rows=5000000.00 loops=1)
Buckets: 262144 Batches: 64 Memory Usage: 5015kB
-> Seq Scan on tickets t (cost=0.00..72144.00 rows=5000000
width=4) (actual rows=5000000.00 loops=1)
Execution Time: 1334.874 ms
That is 313 times too high on statistics that are one second old. The exact
numbers move a little between runs because ANALYZE samples.
I should be clear that this query on its own does not show the hash join
problem. The hashed side here is a base table and its row count is estimated
correctly, so 64 batches is the right answer. It takes one more join for the
inflated estimate to land on the inner side of a hash, and that is where the
batch count runs away.
Thanks,
Shihao