Re: Why is a hash join preferred when it does not fit in work_mem
Hello again, I am back with new experiments. First of all, I have a concrete set of steps that replicate the slowness of the hash join that I described. If you have a system with spinning disks lying around, I would appreciate if you can verify the scenario. Can you also replicate it in different kind of systems? CREATE TABLE descriptions (description_id serial PRIMARY KEY, description text); INSERT INTO descriptions (description_id, description) SELECT s, repeat(encode(sha512(s::text::bytea), 'hex'), 4) FROM generate_series(0,1200300) AS s; CREATE TABLE descriptions_in_books (description_id integer REFERENCES descriptions(description_id), book_id integer); INSERT INTO descriptions_in_books (description_id, book_id) SELECT s % 1200300, s FROM generate_series(0,5200300) AS s; SET work_mem TO '1MB'; SET hash_mem_multiplier = 1.0; SET track_io_timing TO on; EXPLAIN (ANALYZE,VERBOSE,BUFFERS,SETTINGS) SELECT * FROM descriptions NATURAL JOIN descriptions_in_books; SET enable_hashjoin TO off; EXPLAIN (ANALYZE,VERBOSE,BUFFERS,SETTINGS) SELECT * FROM descriptions NATURAL JOIN descriptions_in_books; The first JOIN query uses a hash join with Batches: 1024 and takes 622s! For the longest part, I can see the disk writing most of the time around 1-2 MB/s, so I have to assume it's not writing sequentially. The second identical JOIN uses a merge join that completes in 14s. The I/O happens in a much higher rate (10x maybe), so I'm assuming it's mostly sequential. Another observation is that the hash join deteriorates as the length of the TEXT column grows. In fact, if I fill it with only 32 char long strings, then the hash join is split in only 128 batches, and it completes almost as fast as the merge join. Could it be that the cost estimation is underestimating the I/O pattern related to splitting in batches? Here are the measurements: Hash Join (cost=192450.84..401456.02 rows=5200486 width=524) (actual time=344516.004..621725.562 rows=5200301 loops=1) Output: descriptions.description_id, descriptions.description, descriptions_in_books.book_id Inner Unique: true Hash Cond: (descriptions_in_books.description_id = descriptions.description_id) Buffers: shared hit=15586 read=93161, temp read=97829 written=97829 I/O Timings: shared/local read=1402.597, temp read=229252.170 write=371508.313 -> Seq Scan on public.descriptions_in_books (cost=0.00..75015.86 rows=5200486 width=8) (actual time=0.068..1819.629 rows=5200301 loops=1) Output: descriptions_in_books.book_id, descriptions_in_books.description_id Buffers: shared hit=32 read=22979 I/O Timings: shared/local read=249.910 -> Hash (cost=97739.04..97739.04 rows=1200304 width=520) (actual time=343268.470..343268.471 rows=1200301 loops=1) Output: descriptions.description_id, descriptions.description Buckets: 2048 Batches: 1024 Memory Usage: 686kB Buffers: shared hit=15554 read=70182, temp written=78538 I/O Timings: shared/local read=1152.687, temp write=338883.205 -> Seq Scan on public.descriptions (cost=0.00..97739.04 rows=1200304 width=520) (actual time=0.028..2278.791 rows=1200301 loops=1) Output: descriptions.description_id, descriptions.description Buffers: shared hit=15554 read=70182 I/O Timings: shared/local read=1152.687 Settings: hash_mem_multiplier = '1', work_mem = '1MB' Planning Time: 0.303 ms Execution Time: 622495.279 ms (22 rows) SET enable_hashjoin TO off; Merge Join (cost=868411.87..1079330.96 rows=5200301 width=524) (actual time=6091.932..13304.924 rows=5200301 loops=1) Output: descriptions.description_id, descriptions.description, descriptions_in_books.book_id Merge Cond: (descriptions.description_id = descriptions_in_books.description_id) Buffers: shared hit=67 read=111962 written=1, temp read=45806 written=46189 I/O Timings: shared/local read=1007.043 write=28.575, temp read=344.937 write=794.483 -> Index Scan using descriptions_pkey on public.descriptions (cost=0.43..116919.99 rows=1200304 width=520) (actual time=0.028..1596.387 rows=1200301 loops=1) Output: descriptions.description_id, descriptions.description Buffers: shared hit=3 read=89015 written=1 I/O Timings: shared/local read=834.732 write=28.575 -> Materialize (cost=868408.84..894410.35 rows=5200301 width=8) (actual time=6091.892..9171.796 rows=5200301 loops=1) Output: descriptions_in_books.book_id, descriptions_in_books.description_id Buffers: shared hit=64 read=22947, temp read=45806 written=46189 I/O Timings: shared/local read=172.311, temp read=344.937 write=794.483 -> Sort (cost=868408.84..881409.60 rows=5200301 width=8) (actual time=6091.885..7392.828 rows=5200301 loops=1) Output: descriptions_in_books.book_id, descriptions_in_books.description_id Sort Key: description
Re: Why is a hash join preferred when it does not fit in work_mem
On Sat, 14 Jan 2023, Tom Lane wrote: 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; Thanks for this, I found a page [1] that describes the hash join and now I understand a bit more. [1] https://www.interdb.jp/pg/pgsql03.html I'm not sure whether the key distribution is pathological in my case. The join condition is: Hash Cond: (tasks_mm_workitems.workitem_n = workitem_ids.workitem_n) and workitem_ids.workitem_n is an integer GENERATED AS IDENTITY and PUBLIC KEY. The TABLE workitem_ids har 1.7M rows, and the other table has 3.7M rows. None of them fit in workmem. In my (simplified and pathological) case of work_mem == 1MB, the hash join does 512 batches (Buckets: 4,096 Batches: 512 Memory Usage: 759kB). I'm not sure which hash-merge strategy is followed, but based on that document, it should be the "hybrid hash join with skew". I don't quite follow the I/O requirements of this algorithm, yet. :-) but that can still come out cheaper than merge join, because the sorting needed for merge is generally also far from cheap. I was under the impression that on-disk merge-sort is a relatively cheap (logN) operation, regarding random I/O. 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. On the last EXPLAIN I posted for the forced merge-join, I see that it uses an index-scan on the "small" table. It makes sense since the join happens on the primary key of the table. On the large table it does not use an index scan, because an index doesn't exist for that column. It sorts the 3.7M rows of the table (and FWIW that table only has two integer columns). If I understood correctly what you meant with "performing the sort using an index scan". The problem I see is that the estimated cost of the sort operation is 609,372.91..618,630.40. It's already way above the whole hash-join cost (121,222.68..257,633.01). However the real timings are very different. Actual time for Sort is 4,602.569..5,414.072 ms while for the whole hash join it is 145,641.295..349,682.387 ms. Am I missing some configuration knobs to put some sense to the planner? Thanks, Dimitris
Re: Why is a hash join preferred when it does not fit in work_mem
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
Re: Why is a hash join preferred when it does not fit in work_mem
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 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. + 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 algorithm 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 = 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_workitems NATURAL JOIN workitem_ids; Hash Join (cost=121222.68..257633.01 rows=3702994 width=241) (actual time=145641.295..349682.387 rows=3702994 loops=1) Output: tasks_mm_workitems.workitem_n, tasks_mm_workitems.task_n, workitem_ids.workitem_id Inner Unique: true Hash Cond: (tasks_mm_workitems.workitem_n = workitem_ids.workitem_n) Buffers: shared hit=12121 read=50381, temp read=56309 written=56309 I/O Timings: shared/local read=745.925, temp read=162199.307 write=172758.699 -> Seq Scan on public.tasks_mm_workitems (cost=0.00..53488.94 rows=3702994 width=8) (actual time=0.114..1401.896 rows=3702994 loops=1) Output: tasks_mm_workitems.workitem_n, tasks_mm_workitems.task_n Buffers: shared hit=65 read=16394 I/O Timings: shared/local read=183.959 -> Hash (cost=59780.19..59780.19 rows=1373719 width=237) (actual time=145344.555..145344.557 rows=1373737 loops=1) Output: workitem_ids.workitem_id, workitem_ids.workitem_n Buckets: 4096 Batches: 512 Memory Usage: 759kB Buffers: shared hit=12056 read=33987, temp written=43092 I/O Timings: shared/local read=561.966, temp write=142221.740 -> Seq Scan on public.workitem_ids (cost=0.00..59780.19 rows=1373719 width=237) (actual time=0.033..1493.652 rows=1373737 loops=1) Output: workitem_ids.workitem_id, workitem_ids.workitem_n Buffers: shared hit=12056 read=33987 I/O Timings: shared/local read=561.966 Settings: effective_cache_size = '500MB', enable_memoize = 'off', hash_mem_multiplier = '1', max_parallel_workers_per_gather = '1', work_mem = '1MB' Planning: Buffers: shared hit=8 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_workitems NATURAL JOIN workitem_ids; Merge Join (cost=609453.49..759407.78 rows=3702994 width=241) (actual time=4602.623..9700.435 rows=3702994 loops=1) Output: tasks_mm_workitems.workitem_n, tasks_mm_workitems.task_n, workitem_ids.workitem_id Merge Cond: (workitem_ids.workitem_n = tasks_mm_workitems.workitem_n) Buffers: shared hit=5310 read=66086, temp read=32621 written=32894 I/O Timings: shared/local read=566.121, temp read=228.063 write=526.739 -> Index Scan using workitem_ids_pkey on public.workitem_ids (cost=0.43..81815.86 rows=1373719 width=237) (actual time=0.034..1080.800 rows=1373737 loops=1) Output: workitem_ids.workitem_n, workitem_ids.workitem_id Buffers: shared hit=5310 read=49627 I/O Timings: shared/local read=448.952 -> Materialize (cost=609372.9
Re: Why is a hash join preferred when it does not fit in work_mem
On Fri, 13 Jan 2023 at 07:33, Dimitrios Apostolou wrote: > > I have a very simple NATURAL JOIN that does not fit in the work_mem. Why > does the query planner prefer a hash join that needs 361s, while with a > sort operation and a merge join it takes only 13s? It's a simple matter of that the Hash Join plan appears cheaper based on the costs that the planner has calculated. A better question to ask would be, where are the costs inaccurate? and why. One thing I noticed in your EXPLAIN ANALYZE output is that the Index Scan to workitems_ids costed more expensively than the Seq scan, yet was faster. > -> Seq Scan on public.workitem_ids (cost=0.00..59780.19 rows=1373719 > width=237) (actual time=0.026..1912.312 rows=1373737 loops=1) > -> Index Scan using workitem_ids_pkey on public.workitem_ids > (cost=0.43..81815.86 rows=1373719 width=237) (actual time=0.111..1218.363 > rows=1373737 loops=1) Perhaps the Seq scan is doing more actual I/O than the index scan is. > The low work_mem and the disabled memoization are set on purpose, in order > to simplify a complex query, while reproducing the same problem that I > experienced there. This result is the simplest query I could get, where > the optimizer does not go for a faster merge join. > > From my point of view a merge join is clearly faster, because the hash > table does not fit in memory and I expect a hash join to do a lot of > random I/O. But the query planner does not see that, and increasing > random_page_cost does not help either. In fact the opposite happens: the > merge join gets a higher cost difference to the hash join, as I increase > the random page cost! 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. It would be interesting to see the same plans with SET track_io_timing = 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. David
Why is a hash join preferred when it does not fit in work_mem
Hello list, I have a very simple NATURAL JOIN that does not fit in the work_mem. Why does the query planner prefer a hash join that needs 361s, while with a sort operation and a merge join it takes only 13s? The server is an old Mac Mini with hard disk drive and only 4GB RAM. Postgres version info: PostgreSQL 15.0 on x86_64-apple-darwin20.6.0, compiled by Apple clang version 12.0.0 (clang-1200.0.32.29), 64-bit The low work_mem and the disabled memoization are set on purpose, in order to simplify a complex query, while reproducing the same problem that I experienced there. This result is the simplest query I could get, where the optimizer does not go for a faster merge join. From my point of view a merge join is clearly faster, because the hash table does not fit in memory and I expect a hash join to do a lot of random I/O. But the query planner does not see that, and increasing random_page_cost does not help either. In fact the opposite happens: the merge join gets a higher cost difference to the hash join, as I increase the random page cost! # EXPLAIN (ANALYZE,VERBOSE,BUFFERS,SETTINGS) SELECT * FROM tasks_mm_workitems NATURAL JOIN workitem_ids; QUERY PLAN -- Hash Join (cost=121222.68..257633.01 rows=3702994 width=241) (actual time=184498.464..360606.257 rows=3702994 loops=1) Output: tasks_mm_workitems.workitem_n, tasks_mm_workitems.task_n, workitem_ids.workitem_id Inner Unique: true Hash Cond: (tasks_mm_workitems.workitem_n = workitem_ids.workitem_n) Buffers: shared hit=15068 read=47434, temp read=56309 written=56309 -> Seq Scan on public.tasks_mm_workitems (cost=0.00..53488.94 rows=3702994 width=8) (actual time=0.040..1376.084 rows=3702994 loops=1) Output: tasks_mm_workitems.workitem_n, tasks_mm_workitems.task_n Buffers: shared read=16459 -> Hash (cost=59780.19..59780.19 rows=1373719 width=237) (actual time=184361.874..184361.875 rows=1373737 loops=1) Output: workitem_ids.workitem_id, workitem_ids.workitem_n Buckets: 4096 Batches: 512 Memory Usage: 759kB Buffers: shared hit=15068 read=30975, temp written=43092 -> Seq Scan on public.workitem_ids (cost=0.00..59780.19 rows=1373719 width=237) (actual time=0.026..1912.312 rows=1373737 loops=1) Output: workitem_ids.workitem_id, workitem_ids.workitem_n Buffers: shared hit=15068 read=30975 Settings: effective_cache_size = '500MB', enable_memoize = 'off', hash_mem_multiplier = '1', max_parallel_workers_per_gather = '1', work_mem = '1MB' Planning: Buffers: shared hit=2 read=6 Planning Time: 0.568 ms Execution Time: 361106.876 ms (20 rows) # EXPLAIN (ANALYZE,VERBOSE,BUFFERS,SETTINGS) SELECT * FROM tasks_mm_workitems NATURAL JOIN workitem_ids; QUERY PLAN --- Merge Join (cost=609453.49..759407.78 rows=3702994 width=241) (actual time=5062.513..10866.313 rows=3702994 loops=1) Output: tasks_mm_workitems.workitem_n, tasks_mm_workitems.task_n, workitem_ids.workitem_id Merge Cond: (workitem_ids.workitem_n = tasks_mm_workitems.workitem_n) Buffers: shared hit=5343 read=66053, temp read=32621 written=32894 -> Index Scan using workitem_ids_pkey on public.workitem_ids (cost=0.43..81815.86 rows=1373719 width=237) (actual time=0.111..1218.363 rows=1373737 loops=1) Output: workitem_ids.workitem_n, workitem_ids.workitem_id Buffers: shared hit=5310 read=49627 -> Materialize (cost=609372.91..627887.88 rows=3702994 width=8) (actual time=5062.389..7392.640 rows=3702994 loops=1) Output: tasks_mm_workitems.workitem_n, tasks_mm_workitems.task_n Buffers: shared hit=33 read=16426, temp read=32621 written=32894 -> Sort (cost=609372.91..618630.40 rows=3702994 width=8) (actual time=5062.378..6068.703 rows=3702994 loops=1) 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 hit=33 read=16426, temp read=32621 written=32894 -> Seq Scan on public.tasks_mm_workitems (cost=0.00..53488.94 rows=3702994 width=8) (actual time=0.045..1177.202 rows=3702994 loops=1) Output: tasks_mm_workitems.workitem_n, tasks_mm_workitems.task_n Buffers: shared hit=33 read=16426 Settings: effective_cache_size = '500MB', enable_hashjoin = 'off', enable_memoize = 'off', hash_mem_multiplier = '1', max_parallel_workers_per_gather = '1', work_mem = '1MB' Planning: Buffers: shared hit=8 Planning Time: 0.677 ms Execution Time: 13364.545 ms (23 rows) Thank you in advance, Dim
