# SAHA: A String Adaptive Hash Table for Analytical Databases
## 3 Constructs  
The main constructs of SAHA are the two sets of sub hash tables: Hash Table Sn and Hash Table L, along with a string key dispatcher. Figure 5 shows the architecture of SAHA. All the sub tables are \begin{table}
\begin{tabular}{c c c c c} \hline \hline
**Name** & **Inline String** & **Saved Hash** & **Compact** & **Description** \\ \hline SAHA & Hybrid & Hybrid & No & Linear probing after dispatching by length \\ Linear [3] & No & Yes & No & Linear probing \\ RobinHood [7] & No & Yes & No & Linear probing within limited distance \\ Hopgscott [8] & No & Yes & No & Neighborhood probing \\ Cuckoo [10] & No & Yes & No & Alternatively probing between two tables \\ Unordered & No & No & No & Chaining (GNU stdlibc++’s implementation) \\ SwissTable [16] & No & Partial & No & Quadratic probing with separated metadata \\ F14 Table [17] & No & Partial & No & Quadratic probing with inlined metadata \\ DenseHash [14] & No & No & No & Quadratic probing \\ SparseHash [14] & No & No & Yes & Quadratic probing over sparse table \\ HATTrie [21] & Yes & No & Yes & Trie tree with ArrayHash as leaf nodes \\ ArrayHash [24] & Yes & No & Yes & Chaining with compacted array \\ ARTTree [22] & Yes & No & Yes & Trie tree with hybrid nodes \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Hash tables. implemented as linear probing hash tables, except Hash Table S0, which is an array lookup table. An array lookup table interprets keys as array indices directly; as a result, it can do element lookup within one or two CPU instructions while not storing the key data at all. Array lookup tables are commonly used when the universal data's cardinality is small--small integers, for instance--whereas string data are not feasible because they have infinite cardinality. However, since we limit the string length to two bytes, there can only be 65,536 different keys for Hash Table S0; as a result, we can apply the array lookup technique even for string data. For string keys that have length longer than two bytes but shorter than 25 bytes, we store them in multiple implementations of Hash Table S. The main difference between these tables is the size of their slots. We reinterpret string keys as an array of integers. For string keys with lengths in \((2,8]\) bytes, we use one integer with eight bytes; for lengths in \((8,16]\), we use two; and for lengths \((16,24]\), we use three. These integers are stored in the slots directly without string pointers. The reason for using the linear probing hash table is because it achieves promising performance results in analytical workloads, and its implementation has smaller code size, which is important for SAHA. Since we are dispatching over multiple different hash table implementations, if a complex implementation is used, the code size would be bloated and will have a noticeable impact on performance. To verify this choice, we compare the linear probing hash table against an extensive number of other implementations in Section 5. For string keys longer than 24 bytes, we store the string pointers directly along with their computed hash values in Hash Table L. Since long strings are expensive to move around, holding pointers instead of inlining string keys makes insertion and rehashing faster. The reason for choosing 24 bytes as the threshold is because (1) we observe a good amount of string datasets which have 80% of strings shorter than 24 bytes and (2) using more integers to represent strings would offset the performance benefit due to excessive data copy introduced. It is also important to save the computed  
Figure 5: Architecture of SAHA with multiple hash tables to store strings with different length ranges. hash values for long strings, since hash recomputation is expensive and storing additional hash values has a negligible memory overhead compared to storing long strings. The saved hash can also be used to check whether a given slot contains the current key while doing linear probing.