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 1pGj3r-0000fN-Fx for pgsql-general@arkaria.postgresql.org; Sat, 14 Jan 2023 16:07:15 +0000 Received: from localhost ([127.0.0.1] helo=malur.postgresql.org) by malur.postgresql.org with esmtp (Exim 4.92) (envelope-from ) id 1pGj3q-0006Nf-DL for pgsql-general@arkaria.postgresql.org; Sat, 14 Jan 2023 16:07:14 +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 1pGJUo-00082V-9t for pgsql-general@lists.postgresql.org; Fri, 13 Jan 2023 12:49:22 +0000 Received: from mout.gmx.net ([212.227.17.22]) by makus.postgresql.org with esmtps (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1pGJUl-0004qN-HN for pgsql-general@lists.postgresql.org; Fri, 13 Jan 2023 12:49:21 +0000 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=gmx.net; s=s31663417; t=1673614156; bh=9PfJarzvKbAm4SYot1CKPI/R1PpIJ477PMjP9nluIuE=; h=X-UI-Sender-Class:Date:From:To:cc:Subject:In-Reply-To:References; b=COCvvL3bPI3gjdUnGCi6IiGjvNrGK9KAm9PWkJ2z/74RdlBndRKFuDAkaSUiLm9ia 19S1a25IXPznOv7+onK5V+VgYK4EcVi2FZ1eBsq7bEmAnrIlos0Poyx6jmSO3YLwpl iGdesAe4d9SQDbK4AiFSMKqjElontGv+rvZy+UIsj5C8VcjYtz8/xmx/xlRDZ4wOjO 88xcyAKBbshMSE1mk0nWoJE95cLLWuul9VJoRlP+XbaDWz1US1ByN1HbZ6w4BPG7fD 78ekjjgyyRkytv3GORs6nixHHj8wZeIlfgqLN5gq5KHIxpVi1kOGpAl43c+LE/N+Bx JoLm8HvPBpojg== X-UI-Sender-Class: 724b4f7f-cbec-4199-ad4e-598c01a50d3a Received: from [10.9.70.36] ([185.55.107.82]) by mail.gmx.net (mrgmx105 [212.227.17.168]) with ESMTPSA (Nemesis) id 1MFKGP-1pVSj722Tx-00FiYY; Fri, 13 Jan 2023 13:49:16 +0100 Date: Fri, 13 Jan 2023 13:49:15 +0100 (CET) From: Dimitrios Apostolou To: David Rowley cc: pgsql-general@lists.postgresql.org Subject: Re: Why is a hash join preferred when it does not fit in work_mem In-Reply-To: Message-ID: References: <7ee75988-8408-36f8-3024-93dbf45b6f19@gmx.net> MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII; format=flowed X-Provags-ID: V03:K1:M3Ki6sThg4Fzr5X7KPTvkMFd/wfqDN+lFpFkEGiGq1Fjv+HjKQ/ 4/2JO6RJi9rcCYSrTa7LxVYm01TOMMZOWEDItBIerJ+zjhm7UKs1gRZVI0M3d3kNaCMrXK4 irv1Obft0/ffNNLs5AxGQXnnxort18wougQtPAAfX9IyglHclTmGqfC2yWIuReKyMRNJk5u 2abGS6V1mYG3Tw/Ctgc0w== X-Spam-Flag: NO UI-OutboundReport: notjunk:1;M01:P0:pey2UsGiMoY=;550ga6K3fxpE2LSX0Xdpe9i+ibV Mh3KLi1jeG1boaMdljpBEy/wcafufqDk/gerJjwMxKjugFFDQC3iGm+IcS/7ThIbvBCycGdUM 1129OCF37wuKjmPIsp+3aVeBtugvS3smEjGLu0OSwjd/riaO+HZVuC3pWItF+n0biFANrjf6w PcOp4Kb7MDbJW9F07bpgyqdSBzEHuWzVmTp89eoaqiBIoVQ40Niz0HpyKSLcWQ1iMZ4XWAS+B gkGMYQfnsVsjsiiGSEbnvRvfD8jUamorPnL0SEnHAVuqPIfzvEO6lCLLY8kc2yZPWGvkD00g3 TO+SdGp6AufpVwOFiRFFaaATf2Xc3zGvCAfpP9s1oLrxd9mDNA3Biz9q3MhDKpw3GDbslHtrf mUe+nVEFn842z7QSMVOZSunJ32jzzx9hBTLbZn9FrPDQLrErwwyObKEcrjLWMXvH0S988bGIY D+WD4li1AarhbIs8pI7RwhXt9HvnwcUAb5GJt9SuMIzS6Hne1ka4g1lUsL29dL0ptyXJWYpva 078bEnvPEclLPkaqb5lrSaapHxfMq8C8/ezsGSZHkmPy85owlof07gZ5aaZjOtI+YFGOJpAfn MOxxJ1wkyud2hyOUoKOMpRp3kLJmI8VsC7gx049821SRqbJ8JgXmVXmiFFdDzJirWbNER5G5z iugum5a2hJeCXOO130+ip7aj+uyaAli+ljixX21nf2fMcvb5MSVRizqh2tYeVyHmYRN0fUG0X PG9HBRHl6DIbR+jhuKywMhfOYMt2VQnBXL3honnXjeKV1VAZN/htLKDd9BbTcHCAOl+buLePh L5sYWyTo42IwmTD5sTQztzXU1B8HURMwmYG4yqdui25teydC+G8v+tojfxIqGggFbYKTFZeYB JVjGLDbtzN6aHOUG0y9AkvNqPX2SjHy9+ckJGX6thQHQ3YiQ7qY3BPqhc Content-Transfer-Encoding: quoted-printable List-Id: List-Help: List-Subscribe: List-Post: List-Owner: List-Archive: Archived-At: Precedence: bulk On Fri, 13 Jan 2023, David Rowley wrote: > > I'd expect reducing random_page_cost to make the Mege Join cheaper as > that's where the Index Scan is. I'm not quite sure where you think the > random I/O is coming from in a batched hash join. Thanks for the feedback, indeed you are right! Decreasing random_page_cost to values way below the default makes the planner prefer the merge join! This seems strange to me. 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 ke= y 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. + The Merge Join involves mostly sequential accesses if the disk files are not fragmented. It reads sequentially and in parallel from both tables, merging the results where the key matches. It requires on-disk sorting (because tables don't fit in work_mem), but even this operation requires little disk seeking. A merge-sort algorith= m might have a random access cost of logN * random_page_cost. 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. > It would be interesting to see the same plans with SET track_io_timing > =3D on; set. It's possible that there's less *actual* I/O going on with > the Merge Join plan vs the Hash Join plan. Since we do buffered I/O, > without track_io_timing, we don't know if the read buffers resulted in > an actual disk read or a read from the kernel buffers. The database has been VACUUM ANALYZEd first and is otherwise idle. Every query has been run twice, and I paste here only the 2nd run. Slow Hash Join: # EXPLAIN (ANALYZE,VERBOSE,BUFFERS,SETTINGS) SELECT * FROM tasks_mm_workit= ems NATURAL JOIN workitem_ids; Hash Join (cost=3D121222.68..257633.01 rows=3D3702994 width=3D241) (act= ual time=3D145641.295..349682.387 rows=3D3702994 loops=3D1) Output: tasks_mm_workitems.workitem_n, tasks_mm_workitems.task_n, work= item_ids.workitem_id Inner Unique: true Hash Cond: (tasks_mm_workitems.workitem_n =3D workitem_ids.workitem_n) Buffers: shared hit=3D12121 read=3D50381, temp read=3D56309 written=3D= 56309 I/O Timings: shared/local read=3D745.925, temp read=3D162199.307 write= =3D172758.699 -> Seq Scan on public.tasks_mm_workitems (cost=3D0.00..53488.94 rows= =3D3702994 width=3D8) (actual time=3D0.114..1401.896 rows=3D3702994 loops= =3D1) Output: tasks_mm_workitems.workitem_n, tasks_mm_workitems.task_n Buffers: shared hit=3D65 read=3D16394 I/O Timings: shared/local read=3D183.959 -> Hash (cost=3D59780.19..59780.19 rows=3D1373719 width=3D237) (actu= al time=3D145344.555..145344.557 rows=3D1373737 loops=3D1) Output: workitem_ids.workitem_id, workitem_ids.workitem_n Buckets: 4096 Batches: 512 Memory Usage: 759kB Buffers: shared hit=3D12056 read=3D33987, temp written=3D43092 I/O Timings: shared/local read=3D561.966, temp write=3D142221.74= 0 -> Seq Scan on public.workitem_ids (cost=3D0.00..59780.19 rows= =3D1373719 width=3D237) (actual time=3D0.033..1493.652 rows=3D1373737 loop= s=3D1) Output: workitem_ids.workitem_id, workitem_ids.workitem_n Buffers: shared hit=3D12056 read=3D33987 I/O Timings: shared/local read=3D561.966 Settings: effective_cache_size =3D '500MB', enable_memoize =3D 'off', ha= sh_mem_multiplier =3D '1', max_parallel_workers_per_gather =3D '1', work_m= em =3D '1MB' Planning: Buffers: shared hit=3D8 Planning Time: 0.693 ms Execution Time: 350290.496 ms (24 rows) Fast Merge Join: # SET enable_hashjoin TO off; SET # EXPLAIN (ANALYZE,VERBOSE,BUFFERS,SETTINGS) SELECT * FROM tasks_mm_workit= ems NATURAL JOIN workitem_ids; Merge Join (cost=3D609453.49..759407.78 rows=3D3702994 width=3D241) (ac= tual time=3D4602.623..9700.435 rows=3D3702994 loops=3D1) Output: tasks_mm_workitems.workitem_n, tasks_mm_workitems.task_n, work= item_ids.workitem_id Merge Cond: (workitem_ids.workitem_n =3D tasks_mm_workitems.workitem_n= ) Buffers: shared hit=3D5310 read=3D66086, temp read=3D32621 written=3D3= 2894 I/O Timings: shared/local read=3D566.121, temp read=3D228.063 write=3D= 526.739 -> Index Scan using workitem_ids_pkey on public.workitem_ids (cost= =3D0.43..81815.86 rows=3D1373719 width=3D237) (actual time=3D0.034..1080.8= 00 rows=3D1373737 loops=3D1) Output: workitem_ids.workitem_n, workitem_ids.workitem_id Buffers: shared hit=3D5310 read=3D49627 I/O Timings: shared/local read=3D448.952 -> Materialize (cost=3D609372.91..627887.88 rows=3D3702994 width=3D8= ) (actual time=3D4602.576..6621.072 rows=3D3702994 loops=3D1) Output: tasks_mm_workitems.workitem_n, tasks_mm_workitems.task_n Buffers: shared read=3D16459, temp read=3D32621 written=3D32894 I/O Timings: shared/local read=3D117.168, temp read=3D228.063 wr= ite=3D526.739 -> Sort (cost=3D609372.91..618630.40 rows=3D3702994 width=3D8)= (actual time=3D4602.569..5414.072 rows=3D3702994 loops=3D1) Output: tasks_mm_workitems.workitem_n, tasks_mm_workitems.= task_n Sort Key: tasks_mm_workitems.workitem_n Sort Method: external merge Disk: 65256kB Buffers: shared read=3D16459, temp read=3D32621 written=3D= 32894 I/O Timings: shared/local read=3D117.168, temp read=3D228.= 063 write=3D526.739 -> Seq Scan on public.tasks_mm_workitems (cost=3D0.00..5= 3488.94 rows=3D3702994 width=3D8) (actual time=3D0.034..1113.868 rows=3D37= 02994 loops=3D1) Output: tasks_mm_workitems.workitem_n, tasks_mm_work= items.task_n Buffers: shared read=3D16459 I/O Timings: shared/local read=3D117.168 Settings: effective_cache_size =3D '500MB', enable_hashjoin =3D 'off', e= nable_memoize =3D 'off', hash_mem_multiplier =3D '1', max_parallel_workers= _per_gather =3D '1', work_mem =3D '1MB' Planning: Buffers: shared hit=3D2 read=3D6 I/O Timings: shared/local read=3D0.152 Planning Time: 0.570 ms Execution Time: 12165.894 ms (29 rows) Regards, Dimitris