# SAHA: A String Adaptive Hash Table for Analytical Databases
## 5 Evaluation
As shown in Figure 10, SAHA is memory efficient when dealing with short strings, close to the compact implementations, and it achieves the best runtime performance. HATrie has the lowest memory consumption, 30 percent lower than SAHA, but its runtime is four times slower. For long string datasets, SAHA does not provide memory optimizations and uses the same amount of memory as all the implementations with saved hash. As we have not yet included pre-hasing optimizations, it also has the same performance characteristics as Linear. Compact hash tables and trie tree based implementations are very memory efficient but take much more time and should be used with care. Vectorized hash tables consume slightly less memory than other open addressing implementations, because they allocate memory in chunks and have less wasted space introduced by memory aligning. As mentioned in previous sections, in order to get better performance when dealing with long strings, we introduced pre-hashing optimization. From the previous benchmarks we saw that the Linear hash table can serve as a good baseline. Thus, we do detailed comparison between Linear and SAHA and demonstrate the benefits of pre-hashing for long strings in Figure 11. The evaluation shows pre-hashing improves the performance on a large margin for long string datasets, and it also benefits short string datasets too. There are two datasets, SearchPhrase and Term48, in which SAHA without pre-hashing introduces a little performance regression due to code bloating; however, it is completely offset by the pre-hashing optimization. The only dataset which is slower than without pre-hashing  
Figure 9: A heat map of slowdowns of various hash tables compared to the fastest of all hash tables for SetBuild, SetLookup, group and join benchmarks, on four datasets with varying string length distributions (HotSpot, Weibo, Twitter, SearchPhrase). Lower numbers (green) are better, with one being the fastest for the specific benchmark running on the specific dataset. is Term2, because it contains tiny strings and hash computation is trivial in such cases. But the total runtime is also small and the regression is negligible. As a result, pre-hashing should always be used as it improves the hash table's performance in general. We also evaluate the optimization of SAHA's string dispatcher. The benchmark is similar to what we did for evaluating the pre-hashing optimization. We use a naive implementation of string dispatcher to serve as a baseline. It is implemented without the memory loading optimization, and the code size is larger. From Figure 12 we can see that compared to naive dispatching, our optimization doubles the performance gain in most test cases. However, the optimization does not affect the performance when dealing with datasets containing tiny or long strings, because these two cases are barely affected by memory loading. To understand the scalability of different hash tables and their performances on large datasets, we use a real world string dataset gathered from website weibo.com--with one billion rows. Figure 13 compares multiple hash tables using a line graph to reveal the scalability of each hash table. It can be seen that SAHA scales linearly, and thanks to our string inlining optimization, SAHA is memory friendlier and thus improves more when processing large datasets. Moreover, since the join workload mainly contains key lookup operations, the performance advantage of SAHA becomes more prominent. Figure 11: A bar graph of accumulated runtime of Linear, SAHA and SAHA with pre-hashing enabled for SetBuild, SetLookup, group and join benchmarks on all datasets. Figure 10: A combined bar and line graph of the memory and time consumption of various hash tables for group benchmarks on two datasets with short and long string length distributions (Weibo and SearchPhrase). The bar graph is grouped by memory consumption characteristics. To validate the advantages of using the CRC32 instruction as the hash function, we evaluate it against other seven hash functions.