Parallel hash join threshold by nickitat · Pull Request #76185 · ClickHouse/ClickHouse

nickitat · 2025-02-14T22:49:54Z

Changelog category (leave one):

Performance Improvement

Related: #75261

Changelog entry (a user-readable short description of the changes that goes to CHANGELOG.md):

Introduced threshold (regulated by setting parallel_hash_join_threshold) to fall back to the hash algorithm when the size of the right table is below the threshold.

The new logic uses the right table size estimation to guess if the parallel_hash will be worth it. It is done here:

ClickHouse/src/Processors/QueryPlan/Optimizations/optimizeJoin.cpp

Lines 345 to 361 in 524c44b

    
           auto lhs_estimation = estimateReadRowsCount(*node.children[0]); 
        
           auto rhs_estimation = estimateReadRowsCount(*node.children[1]); 
        
           /// Consider estimations from hash table sizes cache too 
        
           if (const auto & hash_table_key_hashes = join_step->getHashTableKeyHashes(); 
        
               hash_table_key_hashes && optimization_settings.collect_hash_table_stats_during_joins) 
        
           { 
        
               StatsCollectingParams params{ 
        
                   /*key_=*/0, 
        
                   /*enable=*/true, 
        
                   optimization_settings.max_entries_for_hash_table_stats, 
        
                   optimization_settings.max_size_to_preallocate_for_joins}; 
        
               if (auto hint = getHashTablesStatistics<HashJoinEntry>().getSizeHint(params.setKey(hash_table_key_hashes->key_hash_left))) 
        
                   lhs_estimation = std::min<size_t>(lhs_estimation.value_or(std::numeric_limits<size_t>::max()), hint->source_rows); 
        
               if (auto hint = getHashTablesStatistics<HashJoinEntry>().getSizeHint(params.setKey(hash_table_key_hashes->key_hash_right))) 
        
                   rhs_estimation = std::min<size_t>(rhs_estimation.value_or(std::numeric_limits<size_t>::max()), hint->source_rows); 
        
           }

To make it happen, we now collect another data point in HashTablesStatistics - source_rows, meaning exactly the amount of rows in the right-hand side (not the amount of distinct join key values):

ClickHouse/src/Interpreters/HashTablesStatistics.h

Lines 54 to 62 in 524c44b

    
           struct HashJoinEntry 
        
           { 
        
               bool shouldBeUpdated(const HashJoinEntry & new_entry) const { return new_entry.ht_size < ht_size / 2 || ht_size < new_entry.ht_size; } 
        
               std::string dump() const { return fmt::format("ht_size={}", ht_size); } 
        
               size_t ht_size; // the size of the shared hash table 
        
               size_t source_rows; // the number of rows in the source table 
        
           };

It is needed to be able to differentiate between these two cases:

ClickHouse/tests/queries/0_stateless/03356_threshold_for_parallel_hash.sql

Lines 57 to 75 in 524c44b

    
           -- Check estimations obtained from the cache 
        
           -- Right table is big, regardless of cardinality of join key, we should use ConcurrentHashJoin 
        
           select * from lhs t0 join (select a % 10000 as a from rhs) t1 on t0.a = t1.a settings query_plan_join_swap_table = false format Null; 
        
           select trimBoth(explain) 
        
           from ( 
        
             explain actions=1 select * from lhs t0 join (select a % 10000 as a from rhs) t1 on t0.a = t1.a settings query_plan_join_swap_table = false 
        
           ) 
        
           where explain ilike '%Algorithm%'; 
        
           -- Right table is big, but only a small fraction of rows reaches the join - use HashJoin 
        
           select * from lhs t0 join rhs t1 on t0.a = t1.a where t1.a < 10000 settings query_plan_join_swap_table = false format Null; 
        
           select trimBoth(explain) 
        
           from ( 
        
             explain actions=1 select * from lhs t0 join rhs t1 on t0.a = t1.a where t1.a < 10000 settings query_plan_join_swap_table = false 
        
           ) 
        
           where explain ilike '%Algorithm%';

clickhouse-gh · 2025-02-14T22:50:21Z

Workflow [PR], commit [c194ed0]

nickitat · 2025-02-18T17:21:28Z

src/Planner/PlannerJoinTree.cpp

+        right_header,
+        planner_context->getQueryContext(),
+        std::move(hash_table_stat_cache_key),
+        /*rhs_estimation=*/{});


this means it will not take any effect if took this branch

ClickHouse/src/Planner/PlannerJoinTree.cpp

Lines 2044 to 2046 in 5daf76d

if (!settings[Setting::query_plan_use_new_logical_join_step] || settings[Setting::allow_experimental_parallel_reading_from_replicas])

return buildQueryPlanForJoinNodeLegacy(

join_table_expression, std::move(left_join_tree_query_plan), std::move(right_join_tree_query_plan), outer_scope_columns, planner_context, select_query_info);

nickitat · 2025-02-19T16:50:11Z

Integration tests (tsan, 3/6) - #75982
Integration tests (tsan, 6/6) - #76446

qoega · 2025-03-14T20:07:19Z

Do you plan to return to this PR?

nickitat · 2025-03-14T22:58:42Z

Do you plan to return to this PR?

Yes, it awaited #76613

Cherry pick #76185 to 25.3: Parallel hash join threshold

Cherry pick #76185 to 25.4: Parallel hash join threshold

Make #76185 backportable

Cherry pick #79665 to 25.4: Make #76185 backportable

Cherry pick #79665 to 25.3: Make #76185 backportable

Backport #79665 to 25.4: Make #76185 backportable

Backport #79665 to 25.3: Make #76185 backportable

Backport #76185 to 25.4: Parallel hash join threshold

Backport #76185 to 25.3: Parallel hash join threshold

nickitat added 2 commits February 14, 2025 23:45

impl

2ca010f

Merge branch 'master' into parallel_hash_join_threshold

96e80f1

clickhouse-gh bot added the pr-performance Pull request with some performance improvements label Feb 14, 2025

nickitat commented Feb 18, 2025

View reviewed changes

nickitat added 6 commits February 18, 2025 18:30

clarify new setting

f62c63c

Merge branch 'master' into parallel_hash_join_threshold

5bc87f7

impl

a12f2e5

upd test

642c6f0

better

a672ece

fix tidy

735ecaf

Merge branch 'master' into parallel_hash_join_threshold

6708003

nickitat mentioned this pull request Feb 25, 2025

Refactor cache key calculation for joins #76613

Merged

nickitat added 11 commits March 25, 2025 13:45

Merge branch 'master' into parallel_hash_join_threshold

9fa486c

fix

22b1622

fix

674e545

Merge branch 'master' into parallel_hash_join_threshold

75d1d71

refactor

1c69742

use estimation from cache

685697c

impl

b936bae

fix

87ef2ce

better

7cae3fd

fix

adfbcb4

fix

0fc678a

nickitat force-pushed the parallel_hash_join_threshold branch from f0de853 to 0fc678a Compare March 26, 2025 21:33

nickitat added 2 commits March 31, 2025 11:56

fix

32ef711

Merge branch 'master' into parallel_hash_join_threshold

d85db3a

nickitat added 4 commits April 22, 2025 17:40

fix tidy

8265aba

fix test

9ea7838

fix setting changes

2c6d759

Merge branch 'master' into parallel_hash_join_threshold

c194ed0

nickitat enabled auto-merge April 25, 2025 19:24

nickitat added this pull request to the merge queue Apr 25, 2025

Merged via the queue into master with commit a93baca Apr 25, 2025
116 of 121 checks passed

nickitat deleted the parallel_hash_join_threshold branch April 25, 2025 22:05

This was referenced Apr 25, 2025

Cherry pick #76185 to 25.3: Parallel hash join threshold #79624

Merged

Cherry pick #76185 to 25.4: Parallel hash join threshold #79625

Merged

robot-ch-test-poll4 added the pr-synced-to-cloud The PR is synced to the cloud repo label Apr 25, 2025

nickitat added a commit that referenced this pull request Apr 28, 2025

Merge pull request #79624 from ClickHouse/cherrypick/25.3/76185

3fa6ee3

Cherry pick #76185 to 25.3: Parallel hash join threshold

robot-clickhouse added a commit that referenced this pull request Apr 28, 2025

Backport #76185 to 25.3: Parallel hash join threshold

f82b7fd

robot-ch-test-poll mentioned this pull request Apr 28, 2025

Backport #76185 to 25.3: Parallel hash join threshold #79660

Merged

robot-ch-test-poll4 added the pr-backports-created-cloud deprecated label, NOOP label Apr 28, 2025

nickitat added a commit that referenced this pull request Apr 28, 2025

Merge pull request #79625 from ClickHouse/cherrypick/25.4/76185

a1cc2e6

Cherry pick #76185 to 25.4: Parallel hash join threshold

robot-clickhouse added a commit that referenced this pull request Apr 28, 2025

Backport #76185 to 25.4: Parallel hash join threshold

69e7497

robot-ch-test-poll3 mentioned this pull request Apr 28, 2025

Backport #76185 to 25.4: Parallel hash join threshold #79662

Merged

robot-ch-test-poll added the pr-backports-created Backport PRs are successfully created, it won't be processed by CI script anymore label Apr 28, 2025

github-merge-queue bot pushed a commit that referenced this pull request Apr 29, 2025

Merge pull request #79665 from ClickHouse/follow_up_76185

13a8559

Make #76185 backportable

robot-ch-test-poll2 added a commit that referenced this pull request Apr 29, 2025

Merge pull request #79685 from ClickHouse/cherrypick/25.4/79665

c00531d

Cherry pick #79665 to 25.4: Make #76185 backportable

robot-clickhouse added a commit that referenced this pull request Apr 29, 2025

Backport #79665 to 25.4: Make #76185 backportable

058b775

nickitat added a commit that referenced this pull request Apr 29, 2025

Merge pull request #79684 from ClickHouse/cherrypick/25.3/79665

8f49caf

Cherry pick #79665 to 25.3: Make #76185 backportable

robot-clickhouse added a commit that referenced this pull request Apr 29, 2025

Backport #79665 to 25.3: Make #76185 backportable

bb37aad

nickitat added a commit that referenced this pull request Apr 30, 2025

Merge pull request #79686 from ClickHouse/backport/25.4/79665

586c667

Backport #79665 to 25.4: Make #76185 backportable

nickitat added a commit that referenced this pull request Apr 30, 2025

Merge pull request #79692 from ClickHouse/backport/25.3/79665

06abd36

Backport #79665 to 25.3: Make #76185 backportable

nickitat added a commit that referenced this pull request Apr 30, 2025

Merge pull request #79662 from ClickHouse/backport/25.4/76185

0b6c6f4

Backport #76185 to 25.4: Parallel hash join threshold

nickitat added a commit that referenced this pull request Apr 30, 2025

Merge pull request #79660 from ClickHouse/backport/25.3/76185

7bdfc75

Backport #76185 to 25.3: Parallel hash join threshold

robot-clickhouse added the pr-must-backport-synced The `*-must-backport` labels are synced into the cloud Sync PR label Jul 2, 2025

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Parallel hash join threshold#76185

Parallel hash join threshold#76185
nickitat merged 33 commits intomasterfrom
parallel_hash_join_threshold

nickitat commented Feb 14, 2025 •

edited

Loading

Uh oh!

clickhouse-gh bot commented Feb 14, 2025 •

edited

Loading

Uh oh!

nickitat Feb 18, 2025

Uh oh!

nickitat commented Feb 19, 2025

Uh oh!

qoega commented Mar 14, 2025

Uh oh!

nickitat commented Mar 14, 2025

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

7 participants

	auto lhs_estimation = estimateReadRowsCount(*node.children[0]);
	auto rhs_estimation = estimateReadRowsCount(*node.children[1]);

	/// Consider estimations from hash table sizes cache too
	if (const auto & hash_table_key_hashes = join_step->getHashTableKeyHashes();
	hash_table_key_hashes && optimization_settings.collect_hash_table_stats_during_joins)
	{
	StatsCollectingParams params{
	/key_=/0,
	/enable=/true,
	optimization_settings.max_entries_for_hash_table_stats,
	optimization_settings.max_size_to_preallocate_for_joins};
	if (auto hint = getHashTablesStatistics<HashJoinEntry>().getSizeHint(params.setKey(hash_table_key_hashes->key_hash_left)))
	lhs_estimation = std::min<size_t>(lhs_estimation.value_or(std::numeric_limits<size_t>::max()), hint->source_rows);
	if (auto hint = getHashTablesStatistics<HashJoinEntry>().getSizeHint(params.setKey(hash_table_key_hashes->key_hash_right)))
	rhs_estimation = std::min<size_t>(rhs_estimation.value_or(std::numeric_limits<size_t>::max()), hint->source_rows);
	}

	struct HashJoinEntry
	{
	bool shouldBeUpdated(const HashJoinEntry & new_entry) const { return new_entry.ht_size < ht_size / 2 \|\| ht_size < new_entry.ht_size; }

	std::string dump() const { return fmt::format("ht_size={}", ht_size); }

	size_t ht_size; // the size of the shared hash table
	size_t source_rows; // the number of rows in the source table
	};

	-- Check estimations obtained from the cache

	-- Right table is big, regardless of cardinality of join key, we should use ConcurrentHashJoin
	select * from lhs t0 join (select a % 10000 as a from rhs) t1 on t0.a = t1.a settings query_plan_join_swap_table = false format Null;

	select trimBoth(explain)
	from (
	explain actions=1 select * from lhs t0 join (select a % 10000 as a from rhs) t1 on t0.a = t1.a settings query_plan_join_swap_table = false
	)
	where explain ilike '%Algorithm%';

	-- Right table is big, but only a small fraction of rows reaches the join - use HashJoin
	select * from lhs t0 join rhs t1 on t0.a = t1.a where t1.a < 10000 settings query_plan_join_swap_table = false format Null;

	select trimBoth(explain)
	from (
	explain actions=1 select * from lhs t0 join rhs t1 on t0.a = t1.a where t1.a < 10000 settings query_plan_join_swap_table = false
	)
	where explain ilike '%Algorithm%';

	if (!settings[Setting::query_plan_use_new_logical_join_step] \|\| settings[Setting::allow_experimental_parallel_reading_from_replicas])
	return buildQueryPlanForJoinNodeLegacy(
	join_table_expression, std::move(left_join_tree_query_plan), std::move(right_join_tree_query_plan), outer_scope_columns, planner_context, select_query_info);

Conversation

nickitat commented Feb 14, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Changelog category (leave one):

Changelog entry (a user-readable short description of the changes that goes to CHANGELOG.md):

Uh oh!

clickhouse-gh bot commented Feb 14, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

nickitat Feb 18, 2025

Choose a reason for hiding this comment

Uh oh!

nickitat commented Feb 19, 2025

Uh oh!

qoega commented Mar 14, 2025

Uh oh!

nickitat commented Mar 14, 2025

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

7 participants

nickitat commented Feb 14, 2025 •

edited

Loading

clickhouse-gh bot commented Feb 14, 2025 •

edited

Loading