# SAHA: A String Adaptive Hash Table for Analytical Databases
## 5 Evaluation
Some of them are widely used, such as MurmurHash, while others are more modern and claim to achieve promising results, such as t1 ha and xxHash. Due to the similarity of the hashing operations in each benchmark, we only use the group benchmark for comparison. Since a hash function might affect the performance of the underlying hash table, we select six hash tables from previous benchmarks and substitute their hash functions to rerun the test. We also use two significantly different datasets, Weibo and SearchPhrase, to evaluate the influence of string length distributions over the hash functions. As shown in Figure 14, CRC32 Hash is the fastest among all cases. The result indicates that hash functions perform consistently over different hash tables. The difference among hash functions is higher on the long string dataset, SearchPhrase, compared to the Weibo dataset, which is dominated by short strings. This is because the hashing operation occupies a smaller proportion of total runtime when processing short strings; thus, the benchmark on the Weibo dataset is less sensitive to different hash functions. The performance advantage of CRC32 is mainly because of the native instructions such as _mm_crc32_u64 in modern CPUs. As a result it is the default hash function in SAHA. Figure 12: A bar graph of the accumulated runtime of Linear, SAHA with naive dispatching and SAHA for SetBuild, SetLookup, group and join benchmarks on all datasets. Figure 13: A line figure of time consumption of various hash tables for group and join benchmarks on the real world Weibo dataset. As our goal is to optimize the real world workloads in analytical databases. We implemented SAHA in the ClickHouse database and compared its end-to-end time consumption against the builtin hash table implementation. Due to the current limitation of ClickHouse's join mechanism, we only evaluated the group benchmark, and it can serve as a good indicator for the query's runtime improvements. We used \"SELECT str, count(*) FROM <table> GROUP BY str\" as the benchmark query, where <table> was any of the datasets we used in previous evaluations. It was populated with one column named str and of type string. As can be seen from Figure 15, SAHA helps improve the total query runtime up to 40%, and it is consistently faster on all string data distributions. Because there are other operations participating when doing the end-to-end group benchmarking, such as data scanning, memory copying and various string manipulations, we cannot get the same improvements as shown in the aforementioned hash table evaluations; however, for a highly optimized application such as an analytical database, 40% is remarkable and also shows that hash tables play an important role in analytical queries like group. Moreover, the memory consumption reduced drastically when evaluated on short string datasets, because we had short strings represented as numeric values, and no saved hash values were used. Figure 14: A bar graph of the time consumption of various hash functions for group benchmarks on two datasets with short and long string length distributions (Weibo and SearchPhrase). Figure 15: Two bar graphs of the time and memory consumption of ClickHouse’s builtin hash table and SAHA with pre-hashing enabled for an end-to-end group query benchmark on various datasets.