agora inbox for pgsql-bugs@postgresql.org
help / color / mirror / Atom feedBUG #19708: Hash Join becomes about 300x slower with higher work_mem
7+ messages / 4 participants
[nested] [flat]
* BUG #19708: Hash Join becomes about 300x slower with higher work_mem
@ 2026-09-20 11:57 PG Bug reporting form <noreply@postgresql.org>
2026-09-20 20:05 ` Re: BUG #19708: Hash Join becomes about 300x slower with higher work_mem Alexandre Felipe <o.alexandre.felipe@gmail.com>
0 siblings, 1 reply; 7+ messages in thread
From: PG Bug reporting form @ 2026-09-20 11:57 UTC (permalink / raw)
To: pgsql-bugs@lists.postgresql.org; +Cc: yanarnold5@gmail.com
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.[https://www.postgresql.org/message-id/244dc6c1-3b3d-4de2-b3de-b1511e6a6d10%40vondra.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.
^ permalink raw reply [nested|flat] 7+ messages in thread
* Re: BUG #19708: Hash Join becomes about 300x slower with higher work_mem
2026-09-20 11:57 BUG #19708: Hash Join becomes about 300x slower with higher work_mem PG Bug reporting form <noreply@postgresql.org>
@ 2026-09-20 20:05 ` Alexandre Felipe <o.alexandre.felipe@gmail.com>
2026-09-20 20:52 ` Re: BUG #19708: Hash Join becomes about 300x slower with higher work_mem shihao zhong <zhong950419@gmail.com>
2026-09-20 21:08 ` Re: BUG #19708: Hash Join becomes about 300x slower with higher work_mem Tom Lane <tgl@sss.pgh.pa.us>
0 siblings, 2 replies; 7+ messages in thread
From: Alexandre Felipe @ 2026-09-20 20:05 UTC (permalink / raw)
To: yanarnold5@gmail.com; pgsql-bugs@lists.postgresql.org
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
^ permalink raw reply [nested|flat] 7+ messages in thread
* Re: BUG #19708: Hash Join becomes about 300x slower with higher work_mem
2026-09-20 11:57 BUG #19708: Hash Join becomes about 300x slower with higher work_mem PG Bug reporting form <noreply@postgresql.org>
2026-09-20 20:05 ` Re: BUG #19708: Hash Join becomes about 300x slower with higher work_mem Alexandre Felipe <o.alexandre.felipe@gmail.com>
@ 2026-09-20 20:52 ` shihao zhong <zhong950419@gmail.com>
1 sibling, 0 replies; 7+ messages in thread
From: shihao zhong @ 2026-09-20 20:52 UTC (permalink / raw)
To: Alexandre Felipe <o.alexandre.felipe@gmail.com>; +Cc: yanarnold5@gmail.com; pgsql-bugs@lists.postgresql.org
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
Attachments:
[application/octet-stream] v1-0001-Collapse-hash-join-batches-when-the-inner-side-tu.patch (10.9K, ../../CAGRkXqQvppGcQspe2Ojc=bM=BwkUYUbZ6iDm5TRiT17A4eo3NA@mail.gmail.com/3-v1-0001-Collapse-hash-join-batches-when-the-inner-side-tu.patch)
download | inline diff:
From c71b1821f3acd958ee24125556fb72aa7ecc9c65 Mon Sep 17 00:00:00 2001
From: Shihao <zhong950419@gmail.com>
Date: Sun, 20 Sep 2026 16:17:58 -0400
Subject: [PATCH v1] Collapse hash join batches when the inner side turns out
to fit
The number of batches and buckets is chosen before execution, from the
planner's estimate of the inner side. When that estimate is far too high we
get many batches and a large bucket array. The relation would have fit in
memory all along. Every batch transition then clears the whole bucket array,
and that cost has nothing to do with how much data there really is.
Raising work_mem makes this worse. The initial batch count is capped by the
memory budget, so a larger budget starts from a larger count, and the
balancing loop added by a1b4f289bee then trades batches for buckets at a
fixed product. With a good estimate every batch is used and the trade is a
win. With a large overestimate the number of non empty batches collapses
towards the real row count, so only the bucket array grows.
Once the inner side has been read we know its real size, so redo the sizing
decision with the real row count. If it now comes out at one batch, rebuild
the hash table that way and read the spilled tuples back. Changing nbuckets
is safe here because we are moving to a single batch. The batch number then
no longer comes from the bits above log2_nbuckets.
This is the counterpart of ExecHashIncreaseNumBatches, which handles the
opposite estimation error.
Reported-by: iany <yanarnold5@gmail.com>
Discussion: https://postgr.es/m/19708-bca71f8de0d45605@postgresql.org
---
src/backend/executor/nodeHash.c | 135 ++++++++++++++++++++++++++++
src/backend/executor/nodeHashjoin.c | 78 ++++++++++++++++
src/include/executor/nodeHash.h | 1 +
3 files changed, 214 insertions(+)
diff --git a/src/backend/executor/nodeHash.c b/src/backend/executor/nodeHash.c
index 8825bb6fa23..5b12f4de4de 100644
--- a/src/backend/executor/nodeHash.c
+++ b/src/backend/executor/nodeHash.c
@@ -1759,6 +1759,141 @@ ExecParallelHashIncreaseNumBuckets(HashJoinTable hashtable)
}
}
+/*
+ * ExecHashUnbatch
+ * collapse a batched hash table back into a single batch
+ *
+ * nbatch and nbuckets are picked before execution starts, from the planner's
+ * estimate of the inner side. When that estimate is much too high we end up
+ * with many batches and a large bucket array for a relation that would have
+ * fit in memory all along. That costs one full clear of the bucket array per
+ * batch, plus two temp files per batch, and neither of those costs has
+ * anything to do with how much data there actually is.
+ *
+ * We have no way to fix that up front, but once the inner side has been read
+ * we know its real size, so redo the sizing decision with the real row count.
+ * If it now comes out at a single batch, rebuild the table that way. This is
+ * the counterpart of ExecHashIncreaseNumBatches, which handles the opposite
+ * error.
+ *
+ * Changing nbuckets is only safe here because we are going to nbatch = 1: with
+ * a single batch ExecHashGetBucketAndBatch stops deriving the batch number
+ * from the bits above log2_nbuckets, so moving that boundary cannot strand a
+ * tuple in the wrong batch.
+ *
+ * Only the tuples already in memory are rehashed here. The caller must load
+ * back whatever was spilled to the batch files, and close them.
+ *
+ * Returns false, leaving the hash table untouched, if the real size still
+ * needs more than one batch.
+ */
+bool
+ExecHashUnbatch(HashJoinTable hashtable, int tupwidth)
+{
+ size_t space_allowed;
+ int nbuckets;
+ int nbatch;
+ int num_skew_mcvs;
+ HashMemoryChunk oldchunks;
+ MemoryContext oldcxt;
+
+ Assert(hashtable->nbatch > 1);
+ Assert(hashtable->parallel_state == NULL);
+ Assert(hashtable->curbatch == 0);
+
+ /*
+ * Skew tuples live outside the main bucket array and only mean anything
+ * while we are batching, so leave those joins alone.
+ */
+ if (hashtable->skewEnabled)
+ return false;
+
+ /* Redo the sizing decision, this time with the row count we measured. */
+ ExecChooseHashTableSize(hashtable->totalTuples, tupwidth,
+ false, /* no skew table in a single-batch join */
+ false, /* not parallel */
+ 0,
+ &space_allowed,
+ &nbuckets, &nbatch, &num_skew_mcvs);
+
+ if (nbatch != 1)
+ return false;
+
+ /*
+ * Keep nbuckets_original and nbatch_original as they were: EXPLAIN
+ * reports them next to the current values, which is how the shrink
+ * becomes visible.
+ */
+ hashtable->nbatch = 1;
+ hashtable->nbuckets = nbuckets;
+ hashtable->nbuckets_optimal = nbuckets;
+ hashtable->log2_nbuckets = pg_ceil_log2_32(nbuckets);
+ hashtable->log2_nbuckets_optimal = hashtable->log2_nbuckets;
+ hashtable->spaceAllowed = space_allowed;
+ hashtable->spaceAllowedSkew = space_allowed * SKEW_HASH_MEM_PERCENT / 100;
+
+ Assert(hashtable->nbuckets == (1 << hashtable->log2_nbuckets));
+
+ /*
+ * Rebuild the bucket array at the new size, then rehash everything that
+ * is in memory into it. As in ExecHashIncreaseNumBatches we walk the
+ * dense-allocated chunks rather than the buckets, so we don't have to
+ * keep track of which tuples have already been moved; the tuples are
+ * copied into fresh chunks and the old ones freed as we go.
+ */
+ oldchunks = hashtable->chunks;
+ hashtable->chunks = NULL;
+ hashtable->spaceUsed = 0;
+
+ pfree(hashtable->buckets.unshared);
+ oldcxt = MemoryContextSwitchTo(hashtable->batchCxt);
+ hashtable->buckets.unshared = palloc0_array(HashJoinTuple, nbuckets);
+ MemoryContextSwitchTo(oldcxt);
+
+ while (oldchunks != NULL)
+ {
+ HashMemoryChunk nextchunk = oldchunks->next.unshared;
+ size_t idx = 0;
+
+ while (idx < oldchunks->used)
+ {
+ HashJoinTuple hashTuple = (HashJoinTuple) (HASH_CHUNK_DATA(oldchunks) + idx);
+ int hashTupleSize = (HJTUPLE_OVERHEAD +
+ HJTUPLE_MINTUPLE(hashTuple)->t_len);
+ HashJoinTuple copyTuple;
+ int bucketno;
+ int batchno;
+
+ ExecHashGetBucketAndBatch(hashtable, hashTuple->hashvalue,
+ &bucketno, &batchno);
+ Assert(batchno == 0);
+
+ copyTuple = (HashJoinTuple) dense_alloc(hashtable, hashTupleSize);
+ memcpy(copyTuple, hashTuple, hashTupleSize);
+
+ copyTuple->next.unshared = hashtable->buckets.unshared[bucketno];
+ hashtable->buckets.unshared[bucketno] = copyTuple;
+
+ hashtable->spaceUsed += hashTupleSize;
+
+ idx += MAXALIGN(hashTupleSize);
+
+ CHECK_FOR_INTERRUPTS();
+ }
+
+ pfree(oldchunks);
+ oldchunks = nextchunk;
+ }
+
+#ifdef HJDEBUG
+ printf("Hashjoin %p: unbatched %d batches into 1, nbuckets %d => %d\n",
+ hashtable, hashtable->nbatch_original,
+ hashtable->nbuckets_original, hashtable->nbuckets);
+#endif
+
+ return true;
+}
+
/*
* ExecHashTableInsert
* insert a tuple into the hash table depending on the hash value
diff --git a/src/backend/executor/nodeHashjoin.c b/src/backend/executor/nodeHashjoin.c
index 202dd866251..596a323c652 100644
--- a/src/backend/executor/nodeHashjoin.c
+++ b/src/backend/executor/nodeHashjoin.c
@@ -204,6 +204,7 @@ static TupleTableSlot *ExecHashJoinGetSavedTuple(HashJoinState *hjstate,
uint32 *hashvalue,
TupleTableSlot *tupleSlot);
static bool ExecHashJoinNewBatch(HashJoinState *hjstate);
+static void ExecHashJoinUnbatch(HashJoinState *hjstate, HashState *hashNode);
static bool ExecParallelHashJoinNewBatch(HashJoinState *hjstate);
static void ExecParallelHashJoinPartitionOuter(HashJoinState *hjstate);
@@ -375,6 +376,17 @@ ExecHashJoinImpl(PlanState *pstate, bool parallel)
return NULL;
}
+ /*
+ * The batch count was chosen from the planner's estimate of
+ * the inner side. Now that we have actually read it we know
+ * how big it really is, so if it would have fit in memory all
+ * along, collapse the batches before we touch the outer side.
+ * That saves a bucket-array clear per batch, and saves
+ * spilling the outer side at all.
+ */
+ if (!parallel && hashtable->nbatch > 1)
+ ExecHashJoinUnbatch(node, hashNode);
+
/*
* need to remember whether nbatch has increased since we
* began scanning the outer relation
@@ -1601,6 +1613,72 @@ ExecHashJoinSaveTuple(MinimalTuple tuple, uint32 hashvalue,
BufFileWrite(file, tuple, tuple->t_len);
}
+/*
+ * ExecHashJoinUnbatch
+ * collapse the batches once we know the inner side is small enough
+ *
+ * ExecHashUnbatch decides whether this is worth doing and rebuilds the bucket
+ * array for a single batch; what is left for us is to read back the tuples
+ * that were spilled and get rid of the batch files.
+ *
+ * plan_width is only an estimate, so the tuples we read back can turn out to
+ * need more memory than the sizing decision assumed. In that case
+ * ExecHashTableInsert starts batching again underneath us. To keep that safe
+ * we detach the old file array first: a new one is then allocated for the new
+ * batches, and the tuples we have not read yet are still reachable through our
+ * own pointer and get redistributed as they are inserted.
+ */
+static void
+ExecHashJoinUnbatch(HashJoinState *hjstate, HashState *hashNode)
+{
+ HashJoinTable hashtable = hjstate->hj_HashTable;
+ int oldnbatch = hashtable->nbatch;
+ Plan *innerPlan = outerPlan((Hash *) hashNode->ps.plan);
+ BufFile **oldInnerFiles;
+ BufFile **oldOuterFiles;
+ int i;
+
+ if (!ExecHashUnbatch(hashtable, innerPlan->plan_width))
+ return;
+
+ Assert(hashtable->nbatch == 1);
+
+ oldInnerFiles = hashtable->innerBatchFile;
+ oldOuterFiles = hashtable->outerBatchFile;
+ hashtable->innerBatchFile = NULL;
+ hashtable->outerBatchFile = NULL;
+
+ for (i = 1; i < oldnbatch; i++)
+ {
+ BufFile *innerFile = oldInnerFiles[i];
+ TupleTableSlot *slot;
+ uint32 hashvalue;
+
+ /* The outer side has not been scanned yet, so it has no files. */
+ Assert(oldOuterFiles[i] == NULL);
+
+ if (innerFile == NULL)
+ continue;
+
+ if (BufFileSeek(innerFile, 0, 0, SEEK_SET))
+ ereport(ERROR,
+ (errcode_for_file_access(),
+ errmsg("could not rewind hash-join temporary file")));
+
+ while ((slot = ExecHashJoinGetSavedTuple(hjstate,
+ innerFile,
+ &hashvalue,
+ hjstate->hj_HashTupleSlot)))
+ ExecHashTableInsert(hashtable, slot, hashvalue);
+
+ BufFileClose(innerFile);
+ oldInnerFiles[i] = NULL;
+ }
+
+ pfree(oldInnerFiles);
+ pfree(oldOuterFiles);
+}
+
/*
* ExecHashJoinGetSavedTuple
* read the next tuple from a batch file. Return NULL if no more.
diff --git a/src/include/executor/nodeHash.h b/src/include/executor/nodeHash.h
index 9ff493b627a..9ae5516c916 100644
--- a/src/include/executor/nodeHash.h
+++ b/src/include/executor/nodeHash.h
@@ -33,6 +33,7 @@ extern void ExecHashTableDetachBatch(HashJoinTable hashtable);
extern void ExecParallelHashTableSetCurrentBatch(HashJoinTable hashtable,
int batchno);
+extern bool ExecHashUnbatch(HashJoinTable hashtable, int tupwidth);
extern void ExecHashTableInsert(HashJoinTable hashtable,
TupleTableSlot *slot,
uint32 hashvalue);
--
2.37.1 (Apple Git-137.1)
[application/zip] flame.zip (128.5K, ../../CAGRkXqQvppGcQspe2Ojc=bM=BwkUYUbZ6iDm5TRiT17A4eo3NA@mail.gmail.com/4-flame.zip)
download
^ permalink raw reply [nested|flat] 7+ messages in thread
* Re: BUG #19708: Hash Join becomes about 300x slower with higher work_mem
2026-09-20 11:57 BUG #19708: Hash Join becomes about 300x slower with higher work_mem PG Bug reporting form <noreply@postgresql.org>
2026-09-20 20:05 ` Re: BUG #19708: Hash Join becomes about 300x slower with higher work_mem Alexandre Felipe <o.alexandre.felipe@gmail.com>
@ 2026-09-20 21:08 ` Tom Lane <tgl@sss.pgh.pa.us>
2026-09-21 23:31 ` Re: BUG #19708: Hash Join becomes about 300x slower with higher work_mem shihao zhong <zhong950419@gmail.com>
1 sibling, 1 reply; 7+ messages in thread
From: Tom Lane @ 2026-09-20 21:08 UTC (permalink / raw)
To: Alexandre Felipe <o.alexandre.felipe@gmail.com>; +Cc: yanarnold5@gmail.com; pgsql-bugs@lists.postgresql.org
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
^ permalink raw reply [nested|flat] 7+ messages in thread
* Re: BUG #19708: Hash Join becomes about 300x slower with higher work_mem
2026-09-20 11:57 BUG #19708: Hash Join becomes about 300x slower with higher work_mem PG Bug reporting form <noreply@postgresql.org>
2026-09-20 20:05 ` Re: BUG #19708: Hash Join becomes about 300x slower with higher work_mem Alexandre Felipe <o.alexandre.felipe@gmail.com>
2026-09-20 21:08 ` Re: BUG #19708: Hash Join becomes about 300x slower with higher work_mem Tom Lane <tgl@sss.pgh.pa.us>
@ 2026-09-21 23:31 ` shihao zhong <zhong950419@gmail.com>
2026-09-22 04:34 ` Re: BUG #19708: Hash Join becomes about 300x slower with higher work_mem Alexandre Felipe <o.alexandre.felipe@gmail.com>
0 siblings, 1 reply; 7+ messages in thread
From: shihao zhong @ 2026-09-21 23:31 UTC (permalink / raw)
To: Tom Lane <tgl@sss.pgh.pa.us>; +Cc: Alexandre Felipe <o.alexandre.felipe@gmail.com>; yanarnold5@gmail.com; pgsql-bugs@lists.postgresql.org; tomas@vondra.me
> 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
^ permalink raw reply [nested|flat] 7+ messages in thread
* Re: BUG #19708: Hash Join becomes about 300x slower with higher work_mem
2026-09-20 11:57 BUG #19708: Hash Join becomes about 300x slower with higher work_mem PG Bug reporting form <noreply@postgresql.org>
2026-09-20 20:05 ` Re: BUG #19708: Hash Join becomes about 300x slower with higher work_mem Alexandre Felipe <o.alexandre.felipe@gmail.com>
2026-09-20 21:08 ` Re: BUG #19708: Hash Join becomes about 300x slower with higher work_mem Tom Lane <tgl@sss.pgh.pa.us>
2026-09-21 23:31 ` Re: BUG #19708: Hash Join becomes about 300x slower with higher work_mem shihao zhong <zhong950419@gmail.com>
@ 2026-09-22 04:34 ` Alexandre Felipe <o.alexandre.felipe@gmail.com>
2026-09-24 01:02 ` Re: BUG #19708: Hash Join becomes about 300x slower with higher work_mem shihao zhong <zhong950419@gmail.com>
0 siblings, 1 reply; 7+ messages in thread
From: Alexandre Felipe @ 2026-09-22 04:34 UTC (permalink / raw)
To: shihao zhong <zhong950419@gmail.com>; +Cc: Tom Lane <tgl@sss.pgh.pa.us>; yanarnold5@gmail.com; pgsql-bugs@lists.postgresql.org; tomas@vondra.me
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
^ permalink raw reply [nested|flat] 7+ messages in thread
* Re: BUG #19708: Hash Join becomes about 300x slower with higher work_mem
2026-09-20 11:57 BUG #19708: Hash Join becomes about 300x slower with higher work_mem PG Bug reporting form <noreply@postgresql.org>
2026-09-20 20:05 ` Re: BUG #19708: Hash Join becomes about 300x slower with higher work_mem Alexandre Felipe <o.alexandre.felipe@gmail.com>
2026-09-20 21:08 ` Re: BUG #19708: Hash Join becomes about 300x slower with higher work_mem Tom Lane <tgl@sss.pgh.pa.us>
2026-09-21 23:31 ` Re: BUG #19708: Hash Join becomes about 300x slower with higher work_mem shihao zhong <zhong950419@gmail.com>
2026-09-22 04:34 ` Re: BUG #19708: Hash Join becomes about 300x slower with higher work_mem Alexandre Felipe <o.alexandre.felipe@gmail.com>
@ 2026-09-24 01:02 ` shihao zhong <zhong950419@gmail.com>
0 siblings, 0 replies; 7+ messages in thread
From: shihao zhong @ 2026-09-24 01:02 UTC (permalink / raw)
To: Alexandre Felipe <o.alexandre.felipe@gmail.com>; +Cc: Tom Lane <tgl@sss.pgh.pa.us>; yanarnold5@gmail.com; pgsql-bugs@lists.postgresql.org; tomas@vondra.me
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
^ permalink raw reply [nested|flat] 7+ messages in thread
end of thread, other threads:[~2026-09-24 01:02 UTC | newest]
Thread overview: 7+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2026-09-20 11:57 BUG #19708: Hash Join becomes about 300x slower with higher work_mem PG Bug reporting form <noreply@postgresql.org>
2026-09-20 20:05 ` Alexandre Felipe <o.alexandre.felipe@gmail.com>
2026-09-20 20:52 ` shihao zhong <zhong950419@gmail.com>
2026-09-20 21:08 ` Tom Lane <tgl@sss.pgh.pa.us>
2026-09-21 23:31 ` shihao zhong <zhong950419@gmail.com>
2026-09-22 04:34 ` Alexandre Felipe <o.alexandre.felipe@gmail.com>
2026-09-24 01:02 ` shihao zhong <zhong950419@gmail.com>
This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox