Received: from malur.postgresql.org ([217.196.149.56]) by arkaria.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1pGjDt-0001gg-AC for pgsql-general@arkaria.postgresql.org; Sat, 14 Jan 2023 16:17:37 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.92) (envelope-from ) id 1pGjDr-0003NX-F1 for pgsql-general@arkaria.postgresql.org; Sat, 14 Jan 2023 16:17:35 +0000 Received: from makus.postgresql.org ([2001:4800:3e1:1::229]) by malur.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1pGjDr-0003GE-3r for pgsql-general@lists.postgresql.org; Sat, 14 Jan 2023 16:17:35 +0000 Received: from sss.pgh.pa.us ([66.207.139.130]) by makus.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1pGjDk-0001sX-Lz for pgsql-general@lists.postgresql.org; Sat, 14 Jan 2023 16:17:34 +0000 Received: from sss1.sss.pgh.pa.us (localhost [127.0.0.1]) by sss.pgh.pa.us (8.15.2/8.15.2) with ESMTP id 30EGHOgI1007583; Sat, 14 Jan 2023 11:17:24 -0500 From: Tom Lane To: Dimitrios Apostolou cc: David Rowley , pgsql-general@lists.postgresql.org Subject: Re: Why is a hash join preferred when it does not fit in work_mem In-reply-to: References: <7ee75988-8408-36f8-3024-93dbf45b6f19@gmx.net> Comments: In-reply-to Dimitrios Apostolou message dated "Fri, 13 Jan 2023 13:49:15 +0100" MIME-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-ID: <1007581.1673713044.1@sss.pgh.pa.us> Date: Sat, 14 Jan 2023 11:17:24 -0500 Message-ID: <1007582.1673713044@sss.pgh.pa.us> List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk Dimitrios Apostolou 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