2010YOUY01 commented on PR #26227: URL: https://github.com/apache/datafusion/pull/26227#issuecomment-6794724142
I'd like to rework this PR, and will post update later this week. I'll ping the reviewers in this PR in the replacement PR. I've experimented with a different hash table physical layout, and the results look promising. I think we can make the current PR the first step toward this improvement, which should make the broader refactor easier to review and merge. The main idea is keeping the existing SwissTable but replaces the linked-list-based match chains with contiguous storage for rows sharing the same key. ```text ┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┳━━━━━━━━━━━┳━━━━━━━━━━━┳━━━━━━━━━━━━━━━┓ ┃ Query ┃ main ┃ vec-ht ┃ Change ┃ ┡━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━╇━━━━━━━━━━━╇━━━━━━━━━━━╇━━━━━━━━━━━━━━━┩ │ QQuery 1_density=1_prob_hit=1_25*1.5M │ 1.68 ms │ 1.17 ms │ +1.44x faster │ │ QQuery 2_density=0.026_prob_hit=1_25*1.5M │ 3.46 ms │ 4.25 ms │ 1.23x slower │ │ QQuery 3_density=1_prob_hit=1_100K*60M │ 56.49 ms │ 31.99 ms │ +1.77x faster │ │ QQuery 4_density=1_prob_hit=0.1_100K*60M │ 170.09 ms │ 127.48 ms │ +1.33x faster │ │ QQuery 5_density=0.75_prob_hit=1_100K*60M │ 613.80 ms │ 145.40 ms │ +4.22x faster │ │ QQuery 6_density=0.75_prob_hit=0.1_100K*60M │ 222.31 ms │ 178.41 ms │ +1.25x faster │ │ QQuery 7_density=0.5_prob_hit=1_100K*60M │ 593.76 ms │ 143.72 ms │ +4.13x faster │ │ QQuery 8_density=0.5_prob_hit=0.1_100K*60M │ 210.85 ms │ 170.99 ms │ +1.23x faster │ │ QQuery 9_density=0.2_prob_hit=1_100K*60M │ 599.94 ms │ 146.35 ms │ +4.10x faster │ │ QQuery 10_density=0.2_prob_hit=0.1_100K*60M │ 215.38 ms │ 175.27 ms │ +1.23x faster │ │ QQuery 11_density=0.1_prob_hit=1_100K*60M │ 600.52 ms │ 146.16 ms │ +4.11x faster │ │ QQuery 12_density=0.1_prob_hit=0.1_100K*60M │ 214.02 ms │ 185.23 ms │ +1.16x faster │ │ QQuery 13_density=0.01_prob_hit=1_100K*60M │ 624.33 ms │ 160.53 ms │ +3.89x faster │ │ QQuery 14_density=0.01_prob_hit=0.1_100K*60M │ 212.33 ms │ 196.60 ms │ +1.08x faster │ │ QQuery 15_density=0.2_prob_hit=0.1_100K_(20%_dups)*60M │ 196.30 ms │ 147.55 ms │ +1.33x faster │ │ QQuery 16_density=1_prob_hit=1_25*1.5M_RightSemi │ 1.49 ms │ 1.55 ms │ no change │ │ QQuery 17_density=1_prob_hit=1_100K*60M_RightSemi │ 59.00 ms │ 34.30 ms │ +1.72x faster │ │ QQuery 18_density=1_prob_hit=0.1_100K*60M_RightSemi │ 71.96 ms │ 45.98 ms │ +1.57x faster │ │ QQuery 19_density=1_prob_hit=1_25*1.5M_RightAnti │ 1.16 ms │ 1.34 ms │ 1.15x slower │ │ QQuery 20_density=1_prob_hit=1_100K*60M_RightAnti │ 52.93 ms │ 30.36 ms │ +1.74x faster │ │ QQuery 21_density=1_prob_hit=0.1_100K*60M_RightAnti │ 79.34 ms │ 54.52 ms │ +1.46x faster │ │ QQuery 22_density=1_prob_hit=0.01_100K_(fanout_100)*60M_RightSemi │ 80.04 ms │ 60.76 ms │ +1.32x faster │ │ QQuery 23_density=1_prob_hit=1_32K_(fanout~78)*2.3M_long_keys_count │ 90.52 ms │ 33.50 ms │ +2.70x faster │ │ QQuery 24_density=1_prob_hit=1_3K_(single_hot_bucket)*20K_long_keys_count │ 277.89 ms │ 46.72 ms │ +5.95x faster │ │ QQuery 25_density=1_prob_hit=1_20K_(fanout~78_multi_key)*240K_multi_key_count │ 116.32 ms │ 34.42 ms │ +3.38x faster │ │ QQuery 26_density=1_prob_hit=0.027_270K_dense_keys*15M │ 43.65 ms │ 45.75 ms │ no change │ │ QQuery 27_density=0.027_prob_hit=0.027_270K_sparse_keys*15M │ 48.23 ms │ 47.78 ms │ no change │ └───────────────────────────────────────────────────────────────────────────────┴───────────┴───────────┴───────────────┘ ``` -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
