Skip to content

Aggregator support new hash function#9872

Merged
ti-chi-bot[bot] merged 10 commits intopingcap:masterfrom
guo-shaoge:hashagg_new_hasher_1
Feb 20, 2025
Merged

Aggregator support new hash function#9872
ti-chi-bot[bot] merged 10 commits intopingcap:masterfrom
guo-shaoge:hashagg_new_hasher_1

Conversation

@guo-shaoge
Copy link
Contributor

@guo-shaoge guo-shaoge commented Feb 13, 2025 •
edited
Loading

What problem does this PR solve?

Issue Number: close #9704

Problem Summary:

Workload: tpch50g

Queries: same as #9679

key_int256							
Q7-1 Limit	explain analyze select /*+ mpp_1phase_agg() */ sum(l_suppkey) from lineitem group by l_suppkey, l_tax, l_discount, l_partkey limit 1;						
Q7-1 Having 	explain analyze select /*+ mpp_1phase_agg() */ sum(l_suppkey) as csum from lineitem group by l_suppkey, l_tax, l_discount, l_partkey having csum = 10;						
clickbench-q35	explain analyze SELECT ClientIP, ClientIP - 1, ClientIP - 2, ClientIP - 3, COUNT(*) AS c FROM hits GROUP BY ClientIP, ClientIP - 1, ClientIP - 2, ClientIP - 3 ORDER BY c DESC LIMIT 10;						
							
key_int128							
Q5-2 Limit	explain analyze select /*+ mpp_1phase_agg() */ sum(l_linenumber), l_discount from lineitem group by l_suppkey, l_discount limit 1 offset 4000000;						
Q5-2 Having	explain analyze select /*+ mpp_1phase_agg() */ sum(l_linenumber) as csum, l_discount from lineitem group by l_suppkey,               l_discount having csum > 800;						
clickbench-q40	explain analyze SELECT URLHash, EventDate, COUNT(*) AS PageViews FROM hits WHERE CounterID = 62 AND EventDate >= '2013-07-01' AND EventDate <= '2013-07-31' AND IsRefresh = 0 AND TraficSourceID IN (-1, 6) AND RefererHash =                    3594120000172545465 GROUP BY URLHash, EventDate ORDER BY PageViews DESC LIMIT 10 OFFSET 100;						
							
							
key_int64							
clickbench-q4	explain analyze SELECT COUNT(DISTINCT UserID) FROM hits;						
clickbench-q15	explain analyze SELECT UserID, COUNT(*) FROM hits GROUP BY UserID ORDER BY COUNT(*) DESC LIMIT 10;						
							
							
low card(300M->77) key_int128							
Q5-1 	explain analyze select /*+ mpp_1phase_agg() */ sum(l_linenumber), l_discount from lineitem group by l_linenumber, l_discount;

Query Performance

key type query name nightly-20250211 607d850 opt-magic_hash ratio
int256 Q7-1 Limit 6.86 5.67 17.35%
Q7-1 Having 9.23 8.04 12.89%
clickbench-q35 0.4 0.44 -10.00%
int128 Q5-2 Limit 3.46 2.75 20.52%
Q5-2 Having 3.29 2.67 18.84%
int64 clickbench-q4 0.38 0.38 0.00%
clickbench-q15 0.49 0.49 0.00%
low card Q5-1 1.37 1.44 -5.11%

HashTable Collisions

key type query name nightly-20250211 607d850 opt-magic_hash ratio
int256 Q7-1 Having 1,224,406,741 117,644,428 10.41
clickbench-q35 2,874,446 2,894,834 0.99
int128 Q5-2 Having 715,328,567 16,263,780 43.98
int64 Q1-2 Having 152,139,744 24,644,081 6.17

Analysis:

  1. MagicHash has significantly lower collisions, especially in high-cardinality scenarios. For example, in Q5-2, the collision rate of HashCRC32 is 43 times higher than that of MagicHash.
  2. Lower collision rates greatly impact the performance of high-cardinality queries. For instance, Q5-2 and Q7-1 show significant performance improvements when using MagicHash.
  3. MagicHash is slower in computation compared to HashCRC32. This can be observed in low-cardinality queries like Q5-1 (300M → 77). When the collision rate difference is negligible, the slower computation of MagicHash may lead to performance regression, as seen in clickbench-Q35.

NOTE:

  1. ratio in table Query Performance is: (opt-maigc_hash - nightly)/nightly
  2. ratio in table HashTable Collisions is: nightly/opt-magic_hash
  3. check the detailed query info in description in Aggregator support prefetch #9679

What is changed and how it works?

Check List

Tests

  • Unit test
  • Integration test
  • Manual test (add detailed scripts or steps below)
  • No code

Side effects

  • Performance regression: Consumes more CPU
  • Performance regression: Consumes more Memory
  • Breaking backward compatibility

Documentation

  • Affects user behaviors: new config hashagg_use_magic_hash added. When you meet very high cardinatity workload of group by, you can turn on this config, it may improve performance.
  • Contains syntax changes
  • Contains variable changes
  • Contains experimental features
  • Changes MySQL compatibility

Release note

Aggregator support new hash function

@guo-shaoge
Aggregator support new hash function
66a138e 
Signed-off-by: guo-shaoge <shaoge1994@163.com>
@ti-chi-bot ti-chi-bot bot added do-not-merge/needs-linked-issue release-note-none Denotes a PR that doesn't merit a release note. size/L Denotes a PR that changes 100-499 lines, ignoring generated files. labels Feb 13, 2025
@guo-shaoge
print collisions
e8efe48 
Signed-off-by: guo-shaoge <shaoge1994@163.com>
@guo-shaoge
Revert "print collisions"
858c3c9 
This reverts commit e8efe48.
@guo-shaoge
refine
9e58e5c 
Signed-off-by: guo-shaoge <shaoge1994@163.com>
@ti-chi-bot ti-chi-bot bot added size/XL Denotes a PR that changes 500-999 lines, ignoring generated files. release-note Denotes a PR that will be considered when it comes time to generate release notes. and removed size/L Denotes a PR that changes 100-499 lines, ignoring generated files. do-not-merge/needs-linked-issue release-note-none Denotes a PR that doesn't merit a release note. labels Feb 13, 2025
@guo-shaoge
case
a0656e5 
Signed-off-by: guo-shaoge <shaoge1994@163.com>
@guo-shaoge
refine
f5a5ddd 
Signed-off-by: guo-shaoge <shaoge1994@163.com>
@guo-shaoge
Copy link
Contributor Author

guo-shaoge commented Feb 14, 2025

/retest

@guo-shaoge guo-shaoge requested a review from yibin87 February 17, 2025 08:54
windtalker
windtalker reviewed Feb 18, 2025
View reviewed changes
@guo-shaoge
remove magic int64/int32
b6a287a 
Signed-off-by: guo-shaoge <shaoge1994@163.com>
@guo-shaoge
hash sign for int256
9d6b862 
Signed-off-by: guo-shaoge <shaoge1994@163.com>
windtalker
windtalker reviewed Feb 18, 2025
View reviewed changes
dbms/src/Interpreters/Aggregator.h
using AggregationMethod_serialized_hash64 = AggregationMethodSerialized<AggregatedDataWithStringKeyHash64>;

using AggregationMethod_key_int256_magic_hash
= AggregationMethodOneNumber<Int256, AggregatedDataWithInt256KeyMagicHash>;
Copy link
Contributor

@windtalker windtalker Feb 18, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Any usage for this? I think in TiFlash there is no int256 column

Copy link
Contributor Author

@guo-shaoge guo-shaoge Feb 18, 2025 •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

group by column decimal256 will use it

dbms/src/Interpreters/Aggregator.h
using AggregationMethod_keys256_magic_hash = AggregationMethodKeysFixed<AggregatedDataWithKeys256MagicHash>;

using AggregationMethod_key_int256_magic_hash_two_level
= AggregationMethodOneNumber<Int256, AggregatedDataWithInt256KeyMagicHashTwoLevel>;
Copy link
Contributor

@windtalker windtalker Feb 18, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Ditto

windtalker
windtalker approved these changes Feb 18, 2025
View reviewed changes
Copy link
Contributor

@windtalker windtalker left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

lgtm

@ti-chi-bot ti-chi-bot bot added the needs-1-more-lgtm Indicates a PR needs 1 more LGTM. label Feb 18, 2025
yibin87
yibin87 approved these changes Feb 19, 2025
View reviewed changes
Copy link
Contributor

@yibin87 yibin87 left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

LGTM

@ti-chi-bot ti-chi-bot bot added lgtm and removed needs-1-more-lgtm Indicates a PR needs 1 more LGTM. labels Feb 19, 2025
@ti-chi-bot
Copy link
Contributor

ti-chi-bot bot commented Feb 19, 2025

[LGTM Timeline notifier]

Timeline:

  • 2025-02-18 09:04:26.420937238 +0000 UTC m=+952108.817159300: ☑️ agreed by windtalker.
  • 2025-02-19 03:28:49.665687276 +0000 UTC m=+1018372.061909338: ☑️ agreed by yibin87.

@ti-chi-bot
Copy link
Contributor

ti-chi-bot bot commented Feb 20, 2025

[APPROVALNOTIFIER] This PR is APPROVED

This pull-request has been approved by: windtalker, yibin87, yudongusa

The full list of commands accepted by this bot can be found here.

The pull request process is described here

Details Needs approval from an approver in each of these files:

Approvers can indicate their approval by writing /approve in a comment
Approvers can cancel approval by writing /approve cancel in a comment

@ti-chi-bot ti-chi-bot bot added the approved label Feb 20, 2025
@ti-chi-bot ti-chi-bot bot merged commit 594b512 into pingcap:master Feb 20, 2025
5 checks passed
@guo-shaoge guo-shaoge deleted the hashagg_new_hasher_1 branch February 20, 2025 03:44
guo-shaoge added a commit to guo-shaoge/tiflash that referenced this pull request Feb 20, 2025
@guo-shaoge
Revert "Aggregator support new hash function (pingcap#9872)"
ca0975e 
This reverts commit 594b512.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@windtalker windtalker windtalker approved these changes

@yibin87 yibin87 yibin87 approved these changes

+1 more reviewer

@yudongusa yudongusa yudongusa approved these changes

Reviewers whose approvals may not affect merge requirements

Assignees

No one assigned

Labels

approved lgtm release-note Denotes a PR that will be considered when it comes time to generate release notes. size/XL Denotes a PR that changes 500-999 lines, ignoring generated files.

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

Aggregator support new Hash Function

4 participants

@guo-shaoge @windtalker @yibin87 @yudongusa