From: Tom Lane <tgl@sss.pgh.pa.us>
To: Dimitrios Apostolou <jimis@gmx.net>
Cc: David Rowley <dgrowleyml@gmail.com>
Cc: pgsql-general@lists.postgresql.org
Subject: Re: Why is a hash join preferred when it does not fit in work_mem
Date: Sat, 14 Jan 2023 11:17:24 -0500
Message-ID: <1007582.1673713044@sss.pgh.pa.us> (raw)
In-Reply-To: <a32ad594-5c54-7bb5-dcff-bd12f8ed368b@gmx.net>
References: <7ee75988-8408-36f8-3024-93dbf45b6f19@gmx.net>
<CAApHDvpPVydoNkEqLyBSbjWq8kq8M7YWdkA44rTeA2MNaO3jsw@mail.gmail.com>
<a32ad594-5c54-7bb5-dcff-bd12f8ed368b@gmx.net>
Dimitrios Apostolou <jimis@gmx.net> writes:
> Please correct me if I'm wrong, as I'm a newcomer to PostgreSQL, but here
> is how I understand things according to posts I've read, and classical
> algorithms:
> + The Hash Join is fastest when one side fits in work_mem. Then on one
> hand you have a hash table lookup (amortized O(1)) and on the other
> hand, if the table has M rows that that do not fit in memory, you have
> sequential reads from the disk (given low fragmentation of the table or
> index files): For every line you read from the disk, you lookup the key
> in the hash table.
> If the hash table does not fit in RAM then the cost becomes prohibitive.
> Every lookup is a random access possibly hitting the disk. The total
> cost should be random_page_cost * M.
That would be true of a simple hash join, but Postgres uses batched
hash joins: we split up the hash key space into subsets, where hopefully
each subset includes few enough inner-side rows to fit into work_mem.
While this can go wrong given pathological distribution of the inner-side
keys, it does mean that the join can perform well even when the inner
side is much larger than work_mem. So it's not the case that the planner
will simply disregard hash joins beyond work_mem. It will apply a cost
penalty for the predicted batching overhead; but that can still come out
cheaper than merge join, because the sorting needed for merge is generally
also far from cheap.
> So I would expect an increased random_page_cost to benefit the Merge Join
> algorithm. And since my setup involves spinning disks, it does makes sense
> to increase it.
What is probably really happening is that random_page_cost affects the
estimated cost of performing the sort using an index scan instead of
a bespoke sort step. AFAIR, cost_sort doesn't consider random_page_cost
at all, and neither does cost_hashjoin.
regards, tom lane
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients from your mail client; the link fills in
the headers below: reply via email
Some clients, webmail especially, drop In-Reply-To and References from
a link, and the reply then starts a new thread: use the mbox below.
To: pgsql-general@postgresql.org
Cc: tgl@sss.pgh.pa.us, jimis@gmx.net, dgrowleyml@gmail.com
Subject: Re: Why is a hash join preferred when it does not fit in work_mem
In-Reply-To: <1007582.1673713044@sss.pgh.pa.us>
References: <7ee75988-8408-36f8-3024-93dbf45b6f19@gmx.net> <CAApHDvpPVydoNkEqLyBSbjWq8kq8M7YWdkA44rTeA2MNaO3jsw@mail.gmail.com> <a32ad594-5c54-7bb5-dcff-bd12f8ed368b@gmx.net> <1007582.1673713044@sss.pgh.pa.us>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox