# SAHA: A String Adaptive Hash Table for Analytical Databases
## 5 Evaluation  
In this section, we evaluate SAHA's performance using a physical server with four benchmarks (SetBuild, SetLookup, group and join). Four real world datasets are used with different string length distributions properties described in Table 3. We also generate additional synthetic datasets to further investigate the performance with regard to different string length distributions. The physical server contains two Intel Xeon E5-2640v4 CPUs with 128 GB memory. We synthesized the Term datasets with binomial string length distribution using different mean values. We compare SAHA to a number of different hash tables, as shown in Table 1. We first evaluate these hash tables with four benchmarks on all the real world datasets, and accumulate the runtime to gain an overview of performance comparison. For each dataset and benchmark, we show a heat map of slowdowns compared to the fastest of all hash tables in Figure 9. Then we evaluate the fastest ones with additional detailed comparison tests. This helps reduce the number of further detailed benchmarks. \begin{table}
\begin{tabular}{c c c c c c c c c} \hline \hline \multirow{2}{*}{**Name**} & \multirow{2}{*}{**Description**} & \multirow{2}{*}{**\# Strings**} & \multirow{2}{*}{**\# Distinct**} & \multicolumn{6}{c}{**String Length Quantiles**} \\ \cline{5-10}  & & & & **0.2** & **0.4** & **0.6** & **0.8** & **1.0** \\ \hline \multicolumn{10}{c}{**Real World Datasets**} \\ \hline
**Hotspot** & Weibo’s hot topics & 8,974,818 & 1,590,098 & 12 & 15 & 18 & 24 & 837 \\
**Weibo** & Weibo’s user nicknames & 8,993,849 & 4,381,094 & 10 & 12 & 16 & 21 & 45 \\
**Twitter** & Twitter’s user nicknames & 8,982,748 & 7,998,096 & 8 & 9 & 11 & 13 & 20 \\
**SearchPhrase** & Yandex’s web search phrases & 8,928,475 & 4,440,301 & 29 & 44 & 57 & 77 & 2025 \\ \hline \multicolumn{10}{c}{**Synthetic Datasets (with Binomial Distributions)**} \\ \hline
**Term2** & Mean length 2 & 8,758,194 & 835,147 & 1 & 1 & 2 & 3 & 14 \\
**Term4** & Mean length 4 & 8,758,194 & 3,634,680 & 2 & 3 & 4 & 6 & 17 \\
**Term8** & Mean length 8 & 8,758,194 & 8,247,994 & 6 & 7 & 9 & 10 & 25 \\
**Term16** & Mean length 16 & 8,758,194 & 8,758,189 & 13 & 15 & 17 & 19 & 40 \\
**Term24** & Mean length 24 & 8,758,194 & 8,758,194 & 20 & 23 & 25 & 28 & 47 \\
**Term48** & Mean length 48 & 8,758,194 & 8,758,194 & 44 & 47 & 49 & 52 & 73 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: Datasets. \begin{table}
\begin{tabular}{c c} // vanilla emplace & void emplace( \\ StringRef key, \\ Slot*\&slot) \{ \\ uint64\_t hash = hashing(key);  slot = HashTable.probing(hash); \} \\ \hline / Aggregating for (StringRef*key : keys) \{  Slot*slot;  emplace(key,slot);  if (slot == nullptr) slot->value = 1;  else ++ slot->value; } \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Comparison of the emplace routine with and without vectorization in pseudo C++. Additionally, as we are trying to select the leading hash tables, the pre-hashing optimization is excluded, since not all hash tables are feasible with pre-hashing. From Figure 9 we can see that SAHA achieves the best performance in almost all benchmarks. It is only slightly slower than the ClickHouse's linear probing hash table when dealing with long strings. Trie based implementations are extremely slow and should not be used for group and join workloads. Of all the open addressing hash tables, linear probing is good enough without complex probing schemes and achieves the second best performance among all implementations. Vectorized hash tables do not show performance advantages in all four benchmarks. To complete the evaluation, we compare the peak memory allocated when benchmarking each hash table. In order to get accurate memory accounting, we use malloc hooks to record every allocation and deallocation, while keeping track of the maximum reached value. We only evaluate the group benchmark on two datasets, as it is enough to measure the memory consumption characteristics.