pg.ddx.io  pgsql-general@postgresql.org mailing list archive  
help / color / mirror / Atom feed
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





view thread (6+ messages)  latest in thread

Message-ID: <1007582.1673713044@sss.pgh.pa.us>
Permalink:  ../1007582.1673713044@sss.pgh.pa.us/
Also on:    postgresql.org/message-id/1007582.1673713044@sss.pgh.pa.us

 · 

reply

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